OpenRaiser/Intern-Atlas huggingface dataset:
Deep Convolutional Neural Fields for Depth Estimation from a Single Image
Venue: arXiv cs.CV 2014
Year: 2014

We consider the problem of depth estimation from a single monocular image in this work. It is a challenging task as no reliable depth cues are available, e.g., stereo correspondences, motions, etc. Previous efforts have been focusing on exploiting geometric priors or additional sources of information, with all using hand-crafted features. Recently, there is mounting evidence that features from deep convolutional neural networks (CNN) are setting new records for various vision applications. On the other hand, considering the continuous characteristic of the depth values, depth estimations can be naturally formulated into a continuous conditional random field (CRF) learning problem. Therefore, we in this paper present a deep convolutional neural field model for estimating depths from a single image, aiming to jointly explore the capacity of deep CNN and continuous CRF. Specifically, we propose a deep structured learning scheme which learns the unary and pairwise potentials of continuous CRF in a unified deep CNN framework. The proposed method can be used for depth estimations of general scenes with no geometric priors nor any extra information injected. In our case, the integral of the partition function can be analytically calculated, thus we can exactly solve the log-likelihood optimization. Moreover, solving the MAP problem for predicting depths of a new image is highly efficient as closed-form solutions exist. We experimentally demonstrate that the proposed method outperforms state-of-the-art depth estimation methods on both indoor and outdoor scene datasets.
Interference Cancellation trough Interference Alignment for Downlink of Cognitive Cellular Networks
Venue: arXiv cs.IT 2014
Year: 2014

In this letter, we propose the interference cancellation through interference alignment at the downlink of cognitive cellular networks. Interference alignment helps the spatial resources to be shared among primary and secondary cells and thus, it can provide higher degrees of freedom through interference cancellation. We derive and depict the achievable degrees of freedom. We also analyse and calculate the achievable sum rates applying water-filling optimal power allocation.
Reconstruction of Sub-Nyquist Random Sampling for Sparse and Multi-Band Signals
Venue: arXiv cs.IT 2014
Year: 2014

As technology grows, higher frequency signals are required to be processed in various applications. In order to digitize such signals, conventional analog to digital convertors are facing implementation challenges due to the higher sampling rates. Hence, lower sampling rates (i.e., sub-Nyquist) are considered to be cost efficient. A well-known approach is to consider sparse signals that have fewer nonzero frequency components compared to the highest frequency component. For the prior knowledge of the sparse positions, well-established methods already exist. However, there are applications where such information is not available. For such cases, a number of approaches have recently been proposed. In this paper, we propose several random sampling recovery algorithms which do not require any anti-aliasing filter. Moreover, we offer certain conditions under which these recovery techniques converge to the signal. Finally, we also confirm the performance of the above methods through extensive simulations.
A Greedy, Flexible Algorithm to Learn an Optimal Bayesian Network Structure
Venue: arXiv cs.AI 2014
Year: 2014

In this report paper we first present a report of the Advanced Machine Learning Course Project on the provided data set and then present a novel heuristic algorithm for exact Bayesian network (BN) structure discovery that uses decomposable scoring functions. Our algorithm follows a different approach to solve the problem of BN structure discovery than the previously used methods such as Dynamic Programming (DP) and Branch and Bound to reduce the search space and find the global optima space for the problem. The algorithm we propose has some degree of flexibility that can make it more or less greedy. The more the algorithm is set to be greedy, the more the speed of the algorithm will be, and the less optimal the final structure. Our algorithm runs in a much less time than the previously known methods and guarantees to have an optimality of close to 99%. Therefore, it sacrifices less than one percent of score of an optimal structure in order to gain a much lower running time and make the algorithm feasible for large data sets (we may note that we never used any toolbox except for result validation)
From orphan works, a new role of libraries for the public domain and public interest (Dalle opere orfane, un nuovo ruolo delle biblioteche per il pubblico dominio e l'utilità sociale)
Venue: arXiv cs.DL 2014
Year: 2014

Summarising the new orphan works law of Italy, we show how it makes the public interest prevail and allows libraries and other beneficiaries to improve their services. We then argue that such services are part of their mission towards the public domain and are a first step for its complete accomplishment, by the work of each and a reform of european copyright. Failing that, European culture will disappear. -- Sintetizzando le nuove norme sulle opere orfane, mostriamo come esse affermino la prevalenza dell'interesse pubblico e consentano a biblioteche e altri enti beneficiari di migliorare i propri servizi. Sosteniamo quindi che questi si inquadrano nella loro missione nei confronti del pubblico dominio e sono un primo passo per la sua completa realizzazione, mediante il lavoro di ciascuno e la riforma del diritto d'autore europeo. In caso contrario, la cultura europea sparirà.
The square root rank of the correlation polytope is exponential
Venue: arXiv cs.CC 2014
Year: 2014

The square root rank of a nonnegative matrix $A$ is the minimum rank of a matrix $B$ such that $A=B \circ B$, where $\circ$ denotes entrywise product. We show that the square root rank of the slack matrix of the correlation polytope is exponential. Our main technique is a way to lower bound the rank of certain matrices under arbitrary sign changes of the entries using properties of the roots of polynomials in number fields. The square root rank is an upper bound on the positive semidefinite rank of a matrix, and corresponds the special case where all matrices in the factorization are rank-one.
Accelerated Parallel Optimization Methods for Large Scale Machine Learning
Venue: arXiv cs.LG 2014
Year: 2014

The growing amount of high dimensional data in different machine learning applications requires more efficient and scalable optimization algorithms. In this work, we consider combining two techniques, parallelism and Nesterov's acceleration, to design faster algorithms for L1-regularized loss. We first simplify BOOM, a variant of gradient descent, and study it in a unified framework, which allows us to not only propose a refined measurement of sparsity to improve BOOM, but also show that BOOM is provably slower than FISTA. Moving on to parallel coordinate descent methods, we then propose an efficient accelerated version of Shotgun, improving the convergence rate from $O(1/t)$ to $O(1/t^2)$. Our algorithm enjoys a concise form and analysis compared to previous work, and also allows one to study several connected work in a unified way.
Modified Apriori Approach for Evade Network Intrusion Detection System
Venue: arXiv cs.CR 2014
Year: 2014

Intrusion Detection System or IDS is a software or hardware tool that repeatedly scans and monitors events that took place in a computer or a network. A set of rules are used by Signature based Network Intrusion Detection Systems or NIDS to detect hostile traffic in network segments or packets, which are so important in detecting malicious and anomalous behaviour over the network like known attacks that hackers look for new techniques to go unseen. Sometime, a single failure at any layer will cause the NIDS to miss that attack. To overcome this problem, a technique is used that will trigger a failure in that layer. Such technique is known as Evasive technique. An Evasion can be defined as any technique that modifies a visible attack into any other form in order to stay away from being detect. The proposed system is used for detecting attacks which are going on the network and also gives actual categorization of attacks. The proposed system has advantage of getting low false alarm rate and high detection rate. So that leads into decrease in complexity and overhead on the system. The paper presents the Evasion technique for customized apriori algorithm. The paper aims to make a new functional structure to evade NIDS. This framework can be used to audit NIDS. This framework shows that a proof of concept showing how to evade a self built NIDS considering two publicly available datasets.
Codes with the Identifiable Parent Property for Multimedia Fingerprinting
Venue: arXiv cs.IT 2014
Year: 2014

Let ${\cal C}$ be a $q$-ary code of length $n$ and size $M$, and ${\cal C}(i) = \{{\bf c}(i) \ | \ {\bf c}=({\bf c}(1), {\bf c}(2), \ldots, {\bf c}(n))^{T} \in {\cal C}\}$ be the set of $i$th coordinates of ${\cal C}$. The descendant code of a sub-code ${\cal C}^{'} \subseteq {\cal C}$ is defined to be ${\cal C}^{'}(1) \times {\cal C}^{'}(2) \times \cdots \times {\cal C}^{'}(n)$. In this paper, we introduce a multimedia analogue of codes with the identifiable parent property (IPP), called multimedia IPP codes or $t$-MIPPC$(n, M, q)$, so that given the descendant code of any sub-code ${\cal C}^{'}$ of a multimedia $t$-IPP code ${\cal C}$, one can always identify, as IPP codes do in the generic digital scenario, at least one codeword in ${\cal C}^{'}$. We first derive a general upper bound on the size $M$ of a multimedia $t$-IPP code, and then investigate multimedia $3$-IPP codes in more detail. We characterize a multimedia $3$-IPP code of length $2$ in terms of a bipartite graph and a generalized packing, respectively. By means of these combinatorial characterizations, we further derive a tight upper bound on the size of a multimedia $3$-IPP code of length $2$, and construct several infinite families of (asymptotically) optimal multimedia $3$-IPP codes of length $2$.
Improved Algorithmic Results for Unsplittable Stable Allocation Problems
Venue: arXiv cs.DS 2014
Year: 2014

The stable allocation problem is a many-to-many generalization of the well-known stable marriage problem, where we seek a bipartite assignment between, say, jobs (of varying sizes) and machines (of varying capacities) that is "stable" based on a set of underlying preference lists submitted by the jobs and machines. We study a natural "unsplittable" variant of this problem, where each assigned job must be fully assigned to a single machine. Such unsplittable bipartite assignment problems generally tend to be NP-hard, including previously-proposed variants of the unsplittable stable allocation problem. Our main result is to show that under an alternative model of stability, the unsplittable stable allocation problem becomes solvable in polynomial time; although this model is less likely to admit feasible solutions than the model proposed iby McDermid and Manlove, we show that in the event there is no feasible solution, our approach computes a solution of minimal total congestion (overfilling of all machines collectively beyond their capacities). We also describe a technique for rounding the solution of a stable allocation problem to produce "relaxed" unsplit solutions that are only mildly infeasible, where each machine is overcongested by at most a single job.
Multimedia IPP Codes with Efficient Tracing
Venue: arXiv cs.IT 2014
Year: 2014

Binary multimedia identifiable parent property codes (binary $t$-MIPPCs) are used in multimedia fingerprinting schemes where the identification of users taking part in the averaging collusion attack to illegally redistribute content is required. In this paper, we first introduce a binary strong multimedia identifiable parent property code (binary $t$-SMIPPC) whose tracing algorithm is more efficient than that of a binary $t$-MIPPC. Then a composition construction for binary $t$-SMIPPCs from $q$-ary $t$-SMIPPCs is provided. Several infinite series of optimal $q$-ary $t$-SMIPPCs of length $2$ with $t = 2, 3$ are derived from the relationships among $t$-SMIPPCs and other fingerprinting codes, such as $\overline{t}$-separable codes and $t$-MIPPCs. Finally, combinatorial properties of $q$-ary $2$-SMIPPCs of length $3$ are investigated, and optimal $q$-ary $2$-SMIPPCs of length $3$ with $q \equiv 0, 1, 2, 5 \pmod 6$ are constructed.
The Miner's Dilemma
Venue: arXiv cs.CR 2014
Year: 2014

An open distributed system can be secured by requiring participants to present proof of work and rewarding them for participation. The Bitcoin digital currency introduced this mechanism, which is adopted by almost all contemporary digital currencies and related services. A natural process leads participants of such systems to form pools, where members aggregate their power and share the rewards. Experience with Bitcoin shows that the largest pools are often open, allowing anyone to join. It has long been known that a member can sabotage an open pool by seemingly joining it but never sharing its proofs of work. The pool shares its revenue with the attacker, and so each of its participants earns less. We define and analyze a game where pools use some of their participants to infiltrate other pools and perform such an attack. With any number of pools, no-pool-attacks is not a Nash equilibrium. With two pools, or any number of identical pools, there exists an equilibrium that constitutes a tragedy of the commons where the pools attack one another and all earn less than they would have if none had attacked. For two pools, the decision whether or not to attack is the miner's dilemma, an instance of the iterative prisoner's dilemma. The game is played daily by the active Bitcoin pools, which apparently choose not to attack. If this balance breaks, the revenue of open pools might diminish, making them unattractive to participants.
Real time Detection of Lane Markers in Urban Streets
Venue: arXiv cs.CV 2014
Year: 2014

We present a robust and real time approach to lane marker detection in urban streets. It is based on generating a top view of the road, filtering using selective oriented Gaussian filters, using RANSAC line fitting to give initial guesses to a new and fast RANSAC algorithm for fitting Bezier Splines, which is then followed by a post-processing step. Our algorithm can detect all lanes in still images of the street in various conditions, while operating at a rate of 50 Hz and achieving comparable results to previous techniques.
Spectral Efficiency Optimization in Flexi-Grid Long-Haul Optical Systems
Venue: arXiv cs.IT 2014
Year: 2014

Flexible grid optical networks allow a better exploitation of fiber capacity, by enabling a denser frequency allocation. A tighter channel spacing, however, requires narrower filters, which increase linear intersymbol interference (ISI), and may dramatically reduce system reach. Commercial coherent receivers are based on symbol by symbol detectors, which are quite sensitive to ISI. In this context, Nyquist spacing is considered as the ultimate limit to wavelength-division multiplexing (WDM) packing. In this paper, we show that by introducing a limited-complexity trellis processing at the receiver, either the reach of Nyquist WDM flexi-grid networks can be significantly extended, or a denser-than-Nyquist channel packing (i.e., a higher spectral efficiency (SE)) is possible at equal reach. By adopting well-known information-theoretic techniques, we design a limited-complexity trellis processing and quantify its SE gain in flexi-grid architectures where wavelength selective switches over a frequency grid of 12.5GHz are employed.
Efficient SimRank Computation via Linearization
Venue: arXiv cs.DS 2014
Year: 2014

SimRank, proposed by Jeh and Widom, provides a good similarity measure that has been successfully used in numerous applications. While there are many algorithms proposed for computing SimRank, their computational costs are very high. In this paper, we propose a new computational technique, "SimRank linearization," for computing SimRank, which converts the SimRank problem to a linear equation problem. By using this technique, we can solve many SimRank problems, such as single-pair compuation, single-source computation, all-pairs computation, top k searching, and similarity join problems, efficiently.
De-anonymizing scale-free social networks by percolation graph matching
Venue: arXiv cs.SI 2014
Year: 2014

We address the problem of social network de-anonymization when relationships between people are described by scale-free graphs. In particular, we propose a rigorous, asymptotic mathematical analysis of the network de-anonymization problem while capturing the impact of power-law node degree distribution, which is a fundamental and quite ubiquitous feature of many complex systems such as social networks. By applying bootstrap percolation and a novel graph slicing technique, we prove that large inhomogeneities in the node degree lead to a dramatic reduction of the initial set of nodes that must be known a priori (the seeds) in order to successfully identify all other users. We characterize the size of this set when seeds are selected using different criteria, and we show that their number can be as small as $n^ε$, for any small ${ε>0}$. Our results are validated through simulation experiments on a real social network graph.
Diffusion and Superposition Distances for Signals Supported on Networks
Venue: arXiv cs.SI 2014
Year: 2014

We introduce the diffusion and superposition distances as two metrics to compare signals supported in the nodes of a network. Both metrics consider the given vectors as initial temperature distributions and diffuse heat trough the edges of the graph. The similarity between the given vectors is determined by the similarity of the respective diffusion profiles. The superposition distance computes the instantaneous difference between the diffused signals and integrates the difference over time. The diffusion distance determines a distance between the integrals of the diffused signals. We prove that both distances define valid metrics and that they are stable to perturbations in the underlying network. We utilize numerical experiments to illustrate their utility in classifying signals in a synthetic network as well as in classifying ovarian cancer histologies using gene mutation profiles of different patients. We also reinterpret diffusion as a transformation of interrelated feature spaces and use it as preprocessing tool for learning. We use diffusion to increase the accuracy of handwritten digit classification.
Unweighted Stochastic Local Search can be Effective for Random CSP Benchmarks
Venue: arXiv cs.AI 2014
Year: 2014

We present ULSA, a novel stochastic local search algorithm for random binary constraint satisfaction problems (CSP). ULSA is many times faster than the prior state of the art on a widely-studied suite of random CSP benchmarks. Unlike the best previous methods for these benchmarks, ULSA is a simple unweighted method that does not require dynamic adaptation of weights or penalties. ULSA obtains new record best solutions satisfying 99 of 100 variables in the challenging frb100-40 benchmark instance.
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas
Venue: arXiv cs.CC 2014
Year: 2014

In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models. For depth-3 multilinear formulas, of size $\exp(n^δ)$, we give a hitting set of size $\exp(\tilde{O}(n^{2/3 + 2δ/3}))$. This implies a lower bound of $\exp(\tildeΩ(n^{1/2}))$ for depth-3 multilinear formulas, for some explicit polynomial. For depth-4 multilinear formulas, of size $\exp(n^δ)$, we give a hitting set of size $\exp(\tilde{O}(n^{2/3 + 4δ/3}))$. This implies a lower bound of $\exp(\tildeΩ(n^{1/4}))$ for depth-4 multilinear formulas, for some explicit polynomial. A regular formula consists of alternating layers of $+,\times$ gates, where all gates at layer $i$ have the same fan-in. We give a hitting set of size (roughly) $\exp\left(n^{1- δ} \right)$, for regular depth-$d$ multilinear formulas of size $\exp(n^δ)$, where $δ= O(\frac{1}{\sqrt{5}^d})$. This result implies a lower bound of roughly $\exp(\tildeΩ(n^{\frac{1}{\sqrt{5}^d}}))$ for such formulas. We note that better lower bounds are known for these models, but also that none of these bounds was achieved via construction of a hitting set. Moreover, no lower bound that implies such PIT results, even in the white-box model, is currently known. Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth-4 formula, and then to a read-once algebraic branching program (from depth-3 formulas we go straight to read-once algebraic branching programs).
Improving the Performance of the Zero-Forcing Multiuser MISO Downlink Precoder through User Grouping
Venue: arXiv cs.IT 2014
Year: 2014

We consider the Multiple Input Single Output (MISO) Gaussian Broadcast channel with $N_t$ antennas at the base station (BS) and $N_u$ single-antenna users in the downlink. We propose a novel user grouping precoder which improves the sum rate performance of the Zero-Forcing (ZF) precoder specially when the channel is ill-conditioned. The proposed precoder partitions all the users into small groups of equal size. Downlink beamforming is then done in such a way that, at each user's receiver the interference from the signal intended for users not in its group is nulled out. Intra-group interference still remains, and is cancelled through successive interference pre-subtraction at the BS using Dirty Paper Coding (DPC). The proposed user grouping method is different from user selection, since it is a method for precoding of information to the selected (scheduled) users, and not for selecting which users are to be scheduled. Through analysis and simulations, the proposed user grouping based precoder is shown to achieve significant improvement in the achievable sum rate when compared to the ZF precoder. When users are paired (i.e., each group has two users), the complexity of the proposed precoder is $O(N_u^3) + O(N_u^2 N_t)$ which is the same as that of the ZF precoder.
Analyzing Web Application Log Files to Find Hit Count Through the Utilization of Hadoop MapReduce in Cloud Computing Environment
Venue: arXiv cs.DC 2014
Year: 2014

MapReduce has been widely applied in various fields of data and compute intensive applications and also it is important programming model for cloud computing. Hadoop is an open-source implementation of MapReduce which operates on terabytes of data using commodity hardware. We have applied this Hadoop MapReduce programming model for analyzing web log files so that we could get hit count of specific web application. This system uses Hadoop file system to store log file and results are evaluated using Map and Reduce function. Experimental results show hit count for each field in log file. Also due to MapReduce runtime parallelization response time is reduced.