OpenRaiser/Intern-Atlas huggingface dataset:
Exploration of synergistic and redundant information sharing in static and dynamical Gaussian systems
Venue: arXiv cs.IT 2015
Year: 2015

To fully characterize the information that two `source' variables carry about a third `target' variable, one must decompose the total information into redundant, unique and synergistic components, i.e. obtain a partial information decomposition (PID). However Shannon's theory of information does not provide formulae to fully determine these quantities. Several recent studies have begun addressing this. Some possible definitions for PID quantities have been proposed, and some analyses have been carried out on systems composed of discrete variables. Here we present the first in-depth analysis of PIDs on Gaussian systems, both static and dynamical. We show that, for a broad class of Gaussian systems, previously proposed PID formulae imply that: (i) redundancy reduces to the minimum information provided by either source variable, and hence is independent of correlation between sources; (ii) synergy is the extra information contributed by the weaker source when the stronger source is known, and can either increase or decrease with correlation between sources. We find that Gaussian systems frequently exhibit net synergy, i.e. the information carried jointly by both sources is greater than the sum of informations carried by each source individually. Drawing from several explicit examples, we discuss the implications of these findings for measures of information transfer and information-based measures of complexity, both generally and within a neuroscience setting. Importantly, by providing independent formulae for synergy and redundancy applicable to continuous time-series data, we open up a new approach to characterizing and quantifying information sharing amongst complex system variables.
A linear time algorithm for the orbit problem over cyclic groups
Venue: arXiv cs.CC 2015
Year: 2015

The orbit problem is at the heart of symmetry reduction methods for model checking concurrent systems. It asks whether two given configurations in a concurrent system (represented as finite strings over some finite alphabet) are in the same orbit with respect to a given finite permutation group (represented by their generators) acting on this set of configurations by permuting indices. It is known that the problem is in general as hard as the graph isomorphism problem, whose precise complexity (whether it is solvable in polynomial-time) is a long-standing open problem. In this paper, we consider the restriction of the orbit problem when the permutation group is cyclic (i.e. generated by a single permutation), an important restriction of the problem. It is known that this subproblem is solvable in polynomial-time. Our main result is a linear-time algorithm for this subproblem.
Tracking Triadic Cardinality Distributions for Burst Detection in Social Activity Streams
Venue: arXiv cs.SI 2015
Year: 2015

In everyday life, we often observe unusually frequent interactions among people before or during important events, e.g., we receive/send more greetings from/to our friends on Christmas Day, than usual. We also observe that some videos suddenly go viral through people's sharing in online social networks (OSNs). Do these seemingly different phenomena share a common structure? All these phenomena are associated with sudden surges of user activities in networks, which we call "bursts" in this work. We find that the emergence of a burst is accompanied with the formation of triangles in networks. This finding motivates us to propose a new method to detect bursts in OSNs. We first introduce a new measure, "triadic cardinality distribution", corresponding to the fractions of nodes with different numbers of triangles, i.e., triadic cardinalities, within a network. We demonstrate that this distribution changes when a burst occurs, and is naturally immunized against spamming social-bot attacks. Hence, by tracking triadic cardinality distributions, we can reliably detect bursts in OSNs. To avoid handling massive activity data generated by OSN users, we design an efficient sample-estimate solution to estimate the triadic cardinality distribution from sampled data. Extensive experiments conducted on real data demonstrate the usefulness of this triadic cardinality distribution and the effectiveness of our sample-estimate solution.
Containment Control of Multi-Agent Systems with Dynamic Leaders Based on a $PI^n$-Type Approach
Venue: arXiv cs.SY 2015
Year: 2015

This paper studies the containment control problem of multi-agent systems with multiple dynamic leaders in both the discrete-time domain and the continuous-time domain. The leaders' motions are described by $(n-1)$-order polynomial trajectories. This setting makes practical sense because given some critical points, the leaders' trajectories are usually planned by the polynomial interpolations. In order to drive all followers into the convex hull spanned by the leaders, a $PI^n$-type ($P$ and $I$ are short for {\it Proportion} and {\it Integration}, respectively; $I^n$ implies that the algorithm includes high-order integral terms) containment algorithm is proposed. It is theoretically proved that the $PI^n$-type containment algorithm is able to solve the containment problem of multi-agent systems where the followers are described by any order integral dynamics. Compared with the previous results on the multi-agent systems with dynamic leaders, the distinguished features of this paper are that: (1) the containment problem is studied not only in the continuous-time domain but also in the discrete-time domain while most existing results only work in the continuous-time domain; (2) to deal with the leaders with the $(n-1)$-order polynomial trajectories, existing results require the follower's dynamics to be $n$-order integral while the followers considered in this paper can be described by any-order integral; and (3) the "sign" function is not employed in the proposed algorithm, which avoids the chattering phenomenon. Furthermore, in order to illustrate the practical value of the proposed approach, an application, the containment control of multiple mobile robots is studied. Finally, two simulation examples are given to demonstrate the effectiveness of the proposed algorithm.
Cross-Modal Similarity Learning : A Low Rank Bilinear Formulation
Venue: arXiv cs.MM 2015
Year: 2015

The cross-media retrieval problem has received much attention in recent years due to the rapid increasing of multimedia data on the Internet. A new approach to the problem has been raised which intends to match features of different modalities directly. In this research, there are two critical issues: how to get rid of the heterogeneity between different modalities and how to match the cross-modal features of different dimensions. Recently metric learning methods show a good capability in learning a distance metric to explore the relationship between data points. However, the traditional metric learning algorithms only focus on single-modal features, which suffer difficulties in addressing the cross-modal features of different dimensions. In this paper, we propose a cross-modal similarity learning algorithm for the cross-modal feature matching. The proposed method takes a bilinear formulation, and with the nuclear-norm penalization, it achieves low-rank representation. Accordingly, the accelerated proximal gradient algorithm is successfully imported to find the optimal solution with a fast convergence rate O(1/t^2). Experiments on three well known image-text cross-media retrieval databases show that the proposed method achieves the best performance compared to the state-of-the-art algorithms.
SIRF: Simultaneous Image Registration and Fusion in A Unified Framework
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose a novel method for image fusion with a high-resolution panchromatic image and a low-resolution multispectral image at the same geographical location. The fusion is formulated as a convex optimization problem which minimizes a linear combination of a least-squares fitting term and a dynamic gradient sparsity regularizer. The former is to preserve accurate spectral information of the multispectral image, while the latter is to keep sharp edges of the high-resolution panchromatic image. We further propose to simultaneously register the two images during the fusing process, which is naturally achieved by virtue of the dynamic gradient sparsity property. An efficient algorithm is then devised to solve the optimization problem, accomplishing a linear computational complexity in the size of the output image in each iteration. We compare our method against seven state-of-the-art image fusion methods on multispectral image datasets from four satellites. Extensive experimental results demonstrate that the proposed method substantially outperforms the others in terms of both spatial and spectral qualities. We also show that our method can provide high-quality products from coarsely registered real-world datasets. Finally, a MATLAB implementation is provided to facilitate future research.
A Pooling Approach to Modelling Spatial Relations for Image Retrieval and Annotation
Venue: arXiv cs.CV 2015
Year: 2015

Over the last two decades we have witnessed strong progress on modeling visual object classes, scenes and attributes that have significantly contributed to automated image understanding. On the other hand, surprisingly little progress has been made on incorporating a spatial representation and reasoning in the inference process. In this work, we propose a pooling interpretation of spatial relations and show how it improves image retrieval and annotations tasks involving spatial language. Due to the complexity of the spatial language, we argue for a learning-based approach that acquires a representation of spatial relations by learning parameters of the pooling operator. We show improvements on previous work on two datasets and two different tasks as well as provide additional insights on a new dataset with an explicit focus on spatial relations.
Characterization of repetitions in Sturmian words: A new proof
Venue: arXiv cs.DM 2015
Year: 2015

We present a new, dynamical way to study powers (that is, repetitions) in Sturmian words based on results from Diophantine approximation theory. As a result, we provide an alternative and shorter proof of a result by Damanik and Lenz characterizing powers in Sturmian words [Powers in Sturmian sequences, Eur. J. Combin. 24 (2003), 377--390]. Further, as a consequence, we obtain a previously known formula for the fractional index of a Sturmian word based on the continued fraction expansion of its slope.
Fuzzy Adaptive Resonance Theory, Diffusion Maps and their applications to Clustering and Biclustering
Venue: arXiv cs.NE 2015
Year: 2015

In this paper, we describe an algorithm FARDiff (Fuzzy Adaptive Resonance Dif- fusion) which combines Diffusion Maps and Fuzzy Adaptive Resonance Theory to do clustering on high dimensional data. We describe some applications of this method and some problems for future research.
Packing While Traveling: Mixed Integer Programming for a Class of Nonlinear Knapsack Problems
Venue: arXiv cs.DS 2015
Year: 2015

Packing and vehicle routing problems play an important role in the area of supply chain management. In this paper, we introduce a non-linear knapsack problem that occurs when packing items along a fixed route and taking into account travel time. We investigate constrained and unconstrained versions of the problem and show that both are NP-hard. In order to solve the problems, we provide a pre-processing scheme as well as exact and approximate mixed integer programming (MIP) solutions. Our experimental results show the effectiveness of the MIP solutions and in particular point out that the approximate MIP approach often leads to near optimal results within far less computation time than the exact approach.
Quadratic Zonotopes:An extension of Zonotopes to Quadratic Arithmetics
Venue: arXiv cs.LO 2015
Year: 2015

Affine forms are a common way to represent convex sets of $\mathbb{R}$ using a base of error terms $ε\in [-1, 1]^m$. Quadratic forms are an extension of affine forms enabling the use of quadratic error terms $ε_i ε_j$. In static analysis, the zonotope domain, a relational abstract domain based on affine forms has been used in a wide set of settings, e.g. set-based simulation for hybrid systems, or floating point analysis, providing relational abstraction of functions with a cost linear in the number of errors terms. In this paper, we propose a quadratic version of zonotopes. We also present a new algorithm based on semi-definite programming to project a quadratic zonotope, and therefore quadratic forms, to intervals. All presented material has been implemented and applied on representative examples.
Compound Rank-k Projections for Bilinear Analysis
Venue: arXiv cs.LG 2015
Year: 2015

In many real-world applications, data are represented by matrices or high-order tensors. Despite the promising performance, the existing two-dimensional discriminant analysis algorithms employ a single projection model to exploit the discriminant information for projection, making the model less flexible. In this paper, we propose a novel Compound Rank-k Projection (CRP) algorithm for bilinear analysis. CRP deals with matrices directly without transforming them into vectors, and it therefore preserves the correlations within the matrix and decreases the computation complexity. Different from the existing two dimensional discriminant analysis algorithms, objective function values of CRP increase monotonically.In addition, CRP utilizes multiple rank-k projection models to enable a larger search space in which the optimal solution can be found. In this way, the discriminant ability is enhanced.
Structure Regularization for Structured Prediction: Theories and Experiments
Venue: arXiv cs.LG 2015
Year: 2015

While there are many studies on weight regularization, the study on structure regularization is rare. Many existing systems on structured prediction focus on increasing the level of structural dependencies within the model. However, this trend could have been misdirected, because our study suggests that complex structures are actually harmful to generalization ability in structured prediction. To control structure-based overfitting, we propose a structure regularization framework via \emph{structure decomposition}, which decomposes training samples into mini-samples with simpler structures, deriving a model with better generalization power. We show both theoretically and empirically that structure regularization can effectively control overfitting risk and lead to better accuracy. As a by-product, the proposed method can also substantially accelerate the training speed. The method and the theoretical results can apply to general graphical models with arbitrary structures. Experiments on well-known tasks demonstrate that our method can easily beat the benchmark systems on those highly-competitive tasks, achieving state-of-the-art accuracies yet with substantially faster training speed.
Resource Allocation for Energy-Efficient 3-Way Relay Channels
Venue: arXiv cs.IT 2015
Year: 2015

Throughput and energy efficiency in 3-way relay channels are studied in this paper. Unlike previous contributions, we consider a circular message exchange. First, an outer bound and achievable sum rate expressions for different relaying protocols are derived for 3-way relay channels. The sum capacity is characterized for certain SNR regimes. Next, leveraging the derived achievable sum rate expressions, cooperative and competitive maximization of the energy efficiency are considered. For the cooperative case, both low-complexity and globally optimal algorithms for joint power allocation at the users and at the relay are designed so as to maximize the system global energy efficiency. For the competitive case, a game theoretic approach is taken, and it is shown that the best response dynamics is guaranteed to converge to a Nash equilibrium. A power consumption model for mmWave board-to-board communications is developed, and numerical results are provided to corroborate and provide insight on the theoretical findings.
Computational issues in time-inconsistent planning
Venue: arXiv cs.GT 2015
Year: 2015

Time-inconsistency refers to a paradox in decision making where agents exhibit inconsistent behaviors over time. Examples are procrastination where agents tends to costly postpone easy tasks, and abandonments where agents start a plan and quit in the middle. These behaviors are undesirable in the sense that agents make clearly suboptimal decisions over optimal ones. To capture such behaviors and more importantly, to quantify inefficiency caused by such behaviors, [Kleinberg & Oren 2014] propose a graph model which is essentially same as the standard planning model except for the cost structure. Using this model, they initiate the study of several interesting problems: 1) cost ratio: the worst ratio between the actual cost of the agent and the optimal cost, over all graph instances; 2) motivating subgraph: how to motivate the agent to reach the goal by deleting nodes and edges; 3) Intermediate rewards: how to motivate agents to reach the goal by placing intermediate rewards. Kleinberg and Oren give partial answers to these questions, but the main problems are still open. In fact, they raise these problems explicitly as open problems in their paper. In this paper, we give answers to all three open problems in [Kleinberg & Oren 2014]. First, we show a tight upper bound of cost ratio for graphs without Akerlof's structure, thus confirm the conjecture by Kleinberg and Oren that Akerlof's structure is indeed the worst case for cost ratio. Second, we prove that finding a motivating subgraph is NP-hard, showing that it is generally inefficient to motivate agents by deleting nodes and edges in the graph. Last but not least, we show that computing a strategy to place minimum amount of total reward is also NP-hard. Therefore, it is computational inefficient to motivate agents by placing intermediate rewards. The techniques we use to prove these results are nontrivial and of independent interests.
On the Expressive Efficiency of Sum Product Networks
Venue: arXiv cs.LG 2015
Year: 2015

Sum Product Networks (SPNs) are a recently developed class of deep generative models which compute their associated unnormalized density functions using a special type of arithmetic circuit. When certain sufficient conditions, called the decomposability and completeness conditions (or "D&C" conditions), are imposed on the structure of these circuits, marginal densities and other useful quantities, which are typically intractable for other deep generative models, can be computed by what amounts to a single evaluation of the network (which is a property known as "validity"). However, the effect that the D&C conditions have on the capabilities of D&C SPNs is not well understood. In this work we analyze the D&C conditions, expose the various connections that D&C SPNs have with multilinear arithmetic circuits, and consider the question of how well they can capture various distributions as a function of their size and depth. Among our various contributions is a result which establishes the existence of a relatively simple distribution with fully tractable marginal densities which cannot be efficiently captured by D&C SPNs of any depth, but which can be efficiently captured by various other deep generative models. We also show that with each additional layer of depth permitted, the set of distributions which can be efficiently captured by D&C SPNs grows in size. This kind of "depth hierarchy" property has been widely conjectured to hold for various deep models, but has never been proven for any of them. Some of our other contributions include a new characterization of the D&C conditions as sufficient and necessary ones for a slightly strengthened notion of validity, and various state-machine characterizations of the types of computations that can be performed efficiently by D&C SPNs.
Performance laws of large heterogeneous cellular networks
Venue: arXiv cs.NI 2015
Year: 2015

We propose a model for heterogeneous cellular networks assuming a space-time Poisson process of call arrivals, independently marked by data volumes, and served by different types of base stations (having different transmission powers) represented by the superposition of independent Poisson processes on the plane. Each station applies a processor sharing policy to serve users arriving in its vicinity, modeled by the Voronoi cell perturbed by some random signal propagation effects (shadowing). Users' peak service rates depend on their signal-to-interference-and-noise ratios (SINR) with respect to the serving station. The mutual-dependence of the cells (due to the extra-cell interference) is captured via some system of cell-load equations impacting the spatial distribution of the SINR. We use this model to study in a semi-analytic way (involving only static simulations, with the temporal evolution handled by the queuing theoretic results) network performance metrics (cell loads, mean number of users) and the quality of service perceived by the users (mean throughput) served by different types of base stations. Our goal is to identify macroscopic laws regarding these performance metrics, involving averaging both over time and the network geometry. The reveled laws are validated against real field measurement in an operational network.
An Abstract Interpretation-based Model of Tracing Just-In-Time Compilation
Venue: arXiv cs.PL 2015
Year: 2015

Tracing just-in-time compilation is a popular compilation technique for the efficient implementation of dynamic languages, which is commonly used for JavaScript, Python and PHP. We provide a formal model of tracing JIT compilation of programs using abstract interpretation. Hot path detection corresponds to an abstraction of the trace semantics of the program. The optimization phase corresponds to a transform of the original program that preserves its trace semantics up to an observation modeled by some abstraction. We provide a generic framework to express dynamic optimizations and prove them correct. We instantiate it to prove the correctness of dynamic type specialization and constant variable folding. We show that our framework is more general than the model of tracing compilation introduced by Guo and Palsberg [2011] based on operational bisimulations.
Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs
Venue: arXiv cs.DS 2015
Year: 2015

We give new rounding schemes for the standard linear programming relaxation of the correlation clustering problem, achieving approximation factors almost matching the integrality gaps: - For complete graphs our appoximation is $2.06 - \varepsilon$ for a fixed constant $\varepsilon$, which almost matches the previously known integrality gap of $2$. - For complete $k$-partite graphs our approximation is $3$. We also show a matching integrality gap. - For complete graphs with edge weights satisfying triangle inequalities and probability constraints, our approximation is $1.5$, and we show an integrality gap of $1.2$. Our results improve a long line of work on approximation algorithms for correlation clustering in complete graphs, previously culminating in a ratio of $2.5$ for the complete case by Ailon, Charikar and Newman (JACM'08). In the weighted complete case satisfying triangle inequalities and probability constraints, the same authors give a $2$-approximation; for the bipartite case, Ailon, Avigdor-Elgrabli, Liberty and van Zuylen give a $4$-approximation (SICOMP'12).