OpenRaiser/Intern-Atlas huggingface dataset:
Unsupervised Learning of Invariant Representations in Hierarchical Architectures
Venue: arXiv cs.CV 2014
Year: 2014

The present phase of Machine Learning is characterized by supervised learning algorithms relying on large sets of labeled examples ($n \to \infty$). The next phase is likely to focus on algorithms capable of learning from very few labeled examples ($n \to 1$), like humans seem able to do. We propose an approach to this problem and describe the underlying theory, based on the unsupervised, automatic learning of a ``good'' representation for supervised learning, characterized by small sample complexity ($n$). We consider the case of visual object recognition though the theory applies to other domains. The starting point is the conjecture, proved in specific cases, that image representations which are invariant to translations, scaling and other transformations can considerably reduce the sample complexity of learning. We prove that an invariant and unique (discriminative) signature can be computed for each image patch, $I$, in terms of empirical distributions of the dot-products between $I$ and a set of templates stored during unsupervised learning. A module performing filtering and pooling, like the simple and complex cells described by Hubel and Wiesel, can compute such estimates. Hierarchical architectures consisting of this basic Hubel-Wiesel moduli inherit its properties of invariance, stability, and discriminability while capturing the compositional organization of the visual world in terms of wholes and parts. The theory extends existing deep learning convolutional architectures for image and speech recognition. It also suggests that the main computational goal of the ventral stream of visual cortex is to provide a hierarchical representation of new objects/images which is invariant to transformations, stable, and discriminative for recognition---and that this representation may be continuously learned in an unsupervised way during development and visual experience.
Temporal scaling in information propagation
Venue: arXiv cs.SI 2014
Year: 2014

For the study of information propagation, one fundamental problem is uncovering universal laws governing the dynamics of information propagation. This problem, from the microscopic perspective, is formulated as estimating the propagation probability that a piece of information propagates from one individual to another. Such a propagation probability generally depends on two major classes of factors: the intrinsic attractiveness of information and the interactions between individuals. Despite the fact that the temporal effect of attractiveness is widely studied, temporal laws underlying individual interactions remain unclear, causing inaccurate prediction of information propagation on evolving social networks. In this report, we empirically study the dynamics of information propagation, using the dataset from a population-scale social media website. We discover a temporal scaling in information propagation: the probability a message propagates between two individuals decays with the length of time latency since their latest interaction, obeying a power-law rule. Leveraging the scaling law, we further propose a temporal model to estimate future propagation probabilities between individuals, reducing the error rate of information propagation prediction from 6.7% to 2.6% and improving viral marketing with 9.7% incremental customers.
Optimal approximation for submodular and supermodular optimization with bounded curvature
Venue: arXiv cs.DS 2014
Year: 2014

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a nondecreasing submodular function or minimize a nonincreasing supermodular function in the setting of bounded total curvature $c$. In the case of submodular maximization with curvature $c$, we obtain a $(1-c/e)$-approximation --- the first improvement over the greedy $(1-e^{-c})/c$-approximation of Conforti and Cornuejols from 1984, which holds for a cardinality constraint, as well as recent approaches that hold for an arbitrary matroid constraint. Our approach is based on modifications of the continuous greedy algorithm and non-oblivious local search, and allows us to approximately maximize the sum of a nonnegative, nondecreasing submodular function and a (possibly negative) linear function. We show how to reduce both submodular maximization and supermodular minimization to this general problem when the objective function has bounded total curvature. We prove that the approximation results we obtain are the best possible in the value oracle model, even in the case of a cardinality constraint. We define an extension of the notion of curvature to general monotone set functions and show $(1-c)$-approximation for maximization and $1/(1-c)$-approximation for minimization cases. Finally, we give two concrete applications of our results in the settings of maximum entropy sampling, and the column-subset selection problem.
Editing to a Graph of Given Degrees
Venue: arXiv cs.DS 2014
Year: 2014

We consider the Editing to a Graph of Given Degrees problem that asks for a graph G, non-negative integers d,k and a function δ:V(G)->{1,...,d}, whether it is possible to obtain a graph G' from G such that the degree of v is δ(v) for any vertex v by at most k vertex or edge deletions or edge additions. We construct an FPT-algorithm for Editing to a Graph of Given Degrees parameterized by d+k. We complement this result by showing that the problem has no polynomial kernel unless NP\subseteq coNP/poly.
Dynamic Package Interfaces - Extended Version
Venue: arXiv cs.SE 2014
Year: 2014

A hallmark of object-oriented programming is the ability to perform computation through a set of interacting objects. A common manifestation of this style is the notion of a package, which groups a set of commonly used classes together. A challenge in using a package is to ensure that a client follows the implicit protocol of the package when calling its methods. Violations of the protocol can cause a runtime error or latent invariant violations. These protocols can extend across different, potentially unboundedly many, objects, and are specified informally in the documentation. As a result, ensuring that a client does not violate the protocol is hard. We introduce dynamic package interfaces (DPI), a formalism to explicitly capture the protocol of a package. The DPI of a package is a finite set of rules that together specify how any set of interacting objects of the package can evolve through method calls and under what conditions an error can happen. We have developed a dynamic tool that automatically computes an approximation of the DPI of a package, given a set of abstraction predicates. A key property of DPI is that the unbounded number of configurations of objects of a package are summarized finitely in an abstract domain. This uses the observation that many packages behave monotonically: the semantics of a method call over a configuration does not essentially change if more objects are added to the configuration. We have exploited monotonicity and have devised heuristics to obtain succinct yet general DPIs. We have used our tool to compute DPIs for several commonly used Java packages with complex protocols, such as JDBC, HashSet, and ArrayList.
Convergence Tools for Consensus in Multi-Agent Systems with Switching Topologies
Venue: arXiv cs.SY 2014
Year: 2014

We present two main theorems along the lines of Lyapunov's second method that guarantee asymptotic state consensus in multi-agent systems of agents in R^m with switching interconnection topologies. The two theorems complement each other in the sense that the first one is formulated in terms of the states of the agents in the multi-agent system, whereas the second one is formulated in terms of the pairwise states for each pair of agents in the multi-agent system. In the first theorem, under the assumption that the interconnection topology is uniformly strongly connected and the agents are contained in a compact set, a strong form of attractiveness of the consensus set is assured. In the second theorem, under the weaker assumption that the interconnection topology is uniformly quasi strongly connected, the consensus set is guaranteed to be uniformly asymptotically stable.
Clustering and Relational Ambiguity: from Text Data to Natural Data
Venue: arXiv cs.CL 2014
Year: 2014

Text data is often seen as "take-away" materials with little noise and easy to process information. Main questions are how to get data and transform them into a good document format. But data can be sensitive to noise oftenly called ambiguities. Ambiguities are aware from a long time, mainly because polysemy is obvious in language and context is required to remove uncertainty. I claim in this paper that syntactic context is not suffisant to improve interpretation. In this paper I try to explain that firstly noise can come from natural data themselves, even involving high technology, secondly texts, seen as verified but meaningless, can spoil content of a corpus; it may lead to contradictions and background noise.
Flexible Invariants Through Semantic Collaboration
Venue: arXiv cs.SE 2014
Year: 2014

Modular reasoning about class invariants is challenging in the presence of dependencies among collaborating objects that need to maintain global consistency. This paper presents semantic collaboration: a novel methodology to specify and reason about class invariants of sequential object-oriented programs, which models dependencies between collaborating objects by semantic means. Combined with a simple ownership mechanism and useful default schemes, semantic collaboration achieves the flexibility necessary to reason about complicated inter-object dependencies but requires limited annotation burden when applied to standard specification patterns. The methodology is implemented in AutoProof, our program verifier for the Eiffel programming language (but it is applicable to any language supporting some form of representation invariants). An evaluation on several challenge problems proposed in the literature demonstrates that it can handle a variety of idiomatic collaboration patterns, and is more widely applicable than the existing invariant methodologies.
Performance Guarantees for Adaptive Estimation of Sparse Signals
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies adaptive sensing for estimating the nonzero amplitudes of a sparse signal with the aim of providing analytical guarantees on the performance gain due to adaptive resource allocation. We consider a previously proposed optimal two-stage policy for allocating sensing resources. For positive powers q, we derive tight upper bounds on the mean qth-power error resulting from the optimal two-stage policy and corresponding lower bounds on the improvement over non-adaptive uniform sensing. It is shown that the adaptation gain is related to the detectability of nonzero signal components as characterized by Chernoff coefficients, thus quantifying analytically the dependence on the sparsity level of the signal, the signal-to-noise ratio, and the sensing resource budget. For fixed sparsity levels and increasing signal-to-noise ratio or sensing budget, we obtain the rate of convergence to oracle performance and the rate at which the fraction of resources spent on the first exploratory stage decreases to zero. For a vanishing fraction of nonzero components, the gain increases without bound as a function of signal-to-noise ratio and sensing budget. Numerical simulations demonstrate that the bounds on adaptation gain are quite tight in non-asymptotic regimes as well.
Schemas for Unordered XML on a DIME
Venue: arXiv cs.DB 2014
Year: 2014

We investigate schema languages for unordered XML having no relative order among siblings. First, we propose unordered regular expressions (UREs), essentially regular expressions with unordered concatenation instead of standard concatenation, that define languages of unordered words to model the allowed content of a node (i.e., collections of the labels of children). However, unrestricted UREs are computationally too expensive as we show the intractability of two fundamental decision problems for UREs: membership of an unordered word to the language of a URE and containment of two UREs. Consequently, we propose a practical and tractable restriction of UREs, disjunctive interval multiplicity expressions (DIMEs). Next, we employ DIMEs to define languages of unordered trees and propose two schema languages: disjunctive interval multiplicity schema (DIMS), and its restriction, disjunction-free interval multiplicity schema (IMS). We study the complexity of the following static analysis problems: schema satisfiability, membership of a tree to the language of a schema, schema containment, as well as twig query satisfiability, implication, and containment in the presence of schema. Finally, we study the expressive power of the proposed schema languages and compare them with yardstick languages of unordered trees (FO, MSO, and Presburger constraints) and DTDs under commutative closure. Our results show that the proposed schema languages are capable of expressing many practical languages of unordered trees and enjoy desirable computational properties.
Energy Harvesting Broadband Communication Systems with Processing Energy Cost
Venue: arXiv cs.IT 2014
Year: 2014

Communication over a broadband fading channel powered by an energy harvesting transmitter is studied. Assuming non-causal knowledge of energy/data arrivals and channel gains, optimal transmission schemes are identified by taking into account the energy cost of the processing circuitry as well as the transmission energy. A constant processing cost for each active sub-channel is assumed. Three different system objectives are considered: i) throughput maximization, in which the total amount of transmitted data by a deadline is maximized for a backlogged transmitter with a finite capacity battery; ii) energy maximization, in which the remaining energy in an infinite capacity battery by a deadline is maximized such that all the arriving data packets are delivered; iii) transmission completion time minimization, in which the delivery time of all the arriving data packets is minimized assuming infinite size battery. For each objective, a convex optimization problem is formulated, the properties of the optimal transmission policies are identified, and an algorithm which computes an optimal transmission policy is proposed. Finally, based on the insights gained from the offline optimizations, low-complexity online algorithms performing close to the optimal dynamic programming solution for the throughput and energy maximization problems are developed under the assumption that the energy/data arrivals and channel states are known causally at the transmitter.
Critical Graphs in Index Coding
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we define critical graphs as minimal graphs that support a given set of rates for the index coding problem, and study them for both the one-shot and asymptotic setups. For the case of equal rates, we find the critical graph with minimum number of edges for both one-shot and asymptotic cases. For the general case of possibly distinct rates, we show that for one-shot and asymptotic linear index coding, as well as asymptotic non-linear index coding, each critical graph is a union of disjoint strongly connected subgraphs (USCS). On the other hand, we identify a non-USCS critical graph for a one-shot non-linear index coding problem. Next, we identify a few graph structures that are critical. We also generalize some of our results to the groupcast problem. In addition, we show that the capacity region of the index coding is additive for union of disjoint graphs.
Electromagnetic Lens-focusing Antenna Enabled Massive MIMO: Performance Improvement and Cost Reduction
Venue: arXiv cs.IT 2014
Year: 2014

Massive multiple-input multiple-output (MIMO) techniques have been recently advanced to tremendously improve the performance of wireless communication networks. However, the use of very large antenna arrays at the base stations (BSs) brings new issues, such as the significantly increased hardware and signal processing costs. In order to reap the enormous gain of massive MIMO and yet reduce its cost to an affordable level, this paper proposes a novel system design by integrating an electromagnetic (EM) lens with the large antenna array, termed the EM-lens enabled MIMO. The EM lens has the capability of focusing the power of an incident wave to a small area of the antenna array, while the location of the focal area varies with the angle of arrival (AoA) of the wave. Therefore, in practical scenarios where the arriving signals from geographically separated users have different AoAs, the EM-lens enabled system provides two new benefits, namely energy focusing and spatial interference rejection. By taking into account the effects of imperfect channel estimation via pilot-assisted training, in this paper we analytically show that the average received signal-to-noise ratio (SNR) in both the single-user and multiuser uplink transmissions can be strictly improved by the EM-lens enabled system. Furthermore, we demonstrate that the proposed design makes it possible to considerably reduce the hardware and signal processing costs with only slight degradations in performance. To this end, two complexity/cost reduction schemes are proposed, which are small-MIMO processing with parallel receiver filtering applied over subgroups of antennas to reduce the computational complexity, and channel covariance based antenna selection to reduce the required number of radio frequency (RF) chains. Numerical results are provided to corroborate our analysis.
Nonlinear Dimensionality Reduction via Path-Based Isometric Mapping
Venue: arXiv cs.CG 2014
Year: 2014

Nonlinear dimensionality reduction methods have demonstrated top-notch performance in many pattern recognition and image classification tasks. Despite their popularity, they suffer from highly expensive time and memory requirements, which render them inapplicable to large-scale datasets. To leverage such cases we propose a new method called "Path-Based Isomap". Similar to Isomap, we exploit geodesic paths to find the low-dimensional embedding. However, instead of preserving pairwise geodesic distances, the low-dimensional embedding is computed via a path-mapping algorithm. Due to the much fewer number of paths compared to number of data points, a significant improvement in time and memory complexity without any decline in performance is achieved. The method demonstrates state-of-the-art performance on well-known synthetic and real-world datasets, as well as in the presence of noise.
Large deviations, Basic information theorem for fitness preferential attachment random networks
Venue: arXiv cs.IT 2014
Year: 2014

For fitness preferential attachment random networks, we define the empirical degree and pair measure, which counts the number of vertices of a given degree and the number of edges with given fits, and the sample path empirical degree distribution. For the empirical degree and pair distribution for the fitness preferential attachment random networks, we find a large deviation upper bound. From this result we obtain a weak law of large numbers for the empirical degree and pair distribution, and the basic information theorem or an asymptotic equipartition property for fitness preferential attachment random networks.
Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians
Venue: arXiv cs.DS 2014
Year: 2014

We provide an algorithm for properly learning mixtures of two single-dimensional Gaussians without any separability assumptions. Given $\tilde{O}(1/\varepsilon^2)$ samples from an unknown mixture, our algorithm outputs a mixture that is $\varepsilon$-close in total variation distance, in time $\tilde{O}(1/\varepsilon^5)$. Our sample complexity is optimal up to logarithmic factors, and significantly improves upon both Kalai et al., whose algorithm has a prohibitive dependence on $1/\varepsilon$, and Feldman et al., whose algorithm requires bounds on the mixture parameters and depends pseudo-polynomially in these parameters. One of our main contributions is an improved and generalized algorithm for selecting a good candidate distribution from among competing hypotheses. Namely, given a collection of $N$ hypotheses containing at least one candidate that is $\varepsilon$-close to an unknown distribution, our algorithm outputs a candidate which is $O(\varepsilon)$-close to the distribution. The algorithm requires ${O}(\log{N}/\varepsilon^2)$ samples from the unknown distribution and ${O}(N \log N/\varepsilon^2)$ time, which improves previous such results (such as the Scheffé estimator) from a quadratic dependence of the running time on $N$ to quasilinear. Given the wide use of such results for the purpose of hypothesis selection, our improved algorithm implies immediate improvements to any such use.
Explicit Convergence Rate of a Distributed Alternating Direction Method of Multipliers
Venue: arXiv cs.DC 2014
Year: 2014

Consider a set of N agents seeking to solve distributively the minimization problem $\inf_{x} \sum_{n = 1}^N f_n(x)$ where the convex functions $f_n$ are local to the agents. The popular Alternating Direction Method of Multipliers has the potential to handle distributed optimization problems of this kind. We provide a general reformulation of the problem and obtain a class of distributed algorithms which encompass various network architectures. The rate of convergence of our method is considered. It is assumed that the infimum of the problem is reached at a point $x_\star$, the functions $f_n$ are twice differentiable at this point and $\sum \nabla^2 f_n(x_\star) > 0$ in the positive definite ordering of symmetric matrices. With these assumptions, it is shown that the convergence to the consensus $x_\star$ is linear and the exact rate is provided. Application examples where this rate can be optimized with respect to the ADMM free parameter $ρ$ are also given.
Scalability of the plasma physics code GEM
Venue: arXiv cs.DC 2014
Year: 2014

We discuss a detailed weak scaling analysis of GEM, a 3D MPI-parallelised gyrofluid code used in theoretical plasma physics at the Max Planck Institute of Plasma Physics, IPP at Garching b. München, Germany. Within a PRACE Preparatory Access Project various versions of the code have been analysed on the HPC systems SuperMUC at LRZ and JUQUEEN at Jülich Supercomputing Centre (JSC) to improve the parallel scalability of the application. The diagnostic tool Scalasca has been used to filter out suboptimal routines. The code uses the electromagnetic gyrofluid model which is a superset of magnetohydrodynamic and drift-Alfvén microturbulance and also includes several relevant kinetic processes. GEM can be used with different geometries depending on the targeted use case, and has been proven to show good scalability when the computational domain is distributed amongst two dimensions. Such a distribution allows grids with sufficient size to describe small scale tokamak devices. In order to enable simulation of very large tokamaks (such as the next generation nuclear fusion device ITER in Cadarache, France) the third dimension has been parallelised and weak scaling has been achieved for significantly larger grids.