OpenRaiser/Intern-Atlas huggingface dataset:
Infinite Shift-invariant Grouped Multi-task Learning for Gaussian Processes
Venue: arXiv cs.LG 2013
Year: 2013

Multi-task learning leverages shared information among data sets to improve the learning performance of individual tasks. The paper applies this framework for data where each task is a phase-shifted periodic time series. In particular, we develop a novel Bayesian nonparametric model capturing a mixture of Gaussian processes where each task is a sum of a group-specific function and a component capturing individual variation, in addition to each task being phase shifted. We develop an efficient \textsc{em} algorithm to learn the parameters of the model. As a special case we obtain the Gaussian mixture model and \textsc{em} algorithm for phased-shifted periodic time series. Furthermore, we extend the proposed model by using a Dirichlet Process prior and thereby leading to an infinite mixture model that is capable of doing automatic model selection. A Variational Bayesian approach is developed for inference in this model. Experiments in regression, classification and class discovery demonstrate the performance of the proposed models using both synthetic data and real-world time series data from astrophysics. Our methods are particularly useful when the time series are sparsely and non-synchronously sampled.
Rate Maximization for Half-Duplex Multiple Access with Cooperating Transmitters
Venue: arXiv cs.IT 2013
Year: 2013

We derive the optimal resource allocation of a practical half-duplex scheme for the Gaussian multiple access channel with transmitter cooperation (MAC-TC). Based on rate splitting and superposition coding, two users transmit information to a destination over 3 phases, such that the users partially exchange their information during the first 2 phases and cooperatively transmit to the destination during the last one. This scheme is near capacity-achieving when the inter-user links are stronger than each user-destination link; it also includes partial decode-forward relaying as a special case. We propose efficient algorithms to find the optimal resource allocation for maximizing either the individual or the sum rate and identify the corresponding optimal scheme for each channel configuration. For fixed phase durations, the power allocation problem is convex and can be solved analytically based on the KKT conditions. The optimal phase durations can then be obtained numerically using simple search methods. Results show that as the interuser link qualities increase, the optimal scheme moves from no cooperation to partial then to full cooperation, in which the users fully exchange their information and cooperatively send it to the destination. Therefore, in practical systems with strong inter-user links, simple decode-forward relaying at both users is rate-optimal.
Existence of equilibria in countable games: an algebraic approach
Venue: arXiv cs.GT 2013
Year: 2013

Although mixed extensions of finite games always admit equilibria, this is not the case for countable games, the best-known example being Wald's pick-the-larger-integer game. Several authors have provided conditions for the existence of equilibria in infinite games. These conditions are typically of topological nature and are rarely applicable to countable games. Here we establish an existence result for the equilibrium of countable games when the strategy sets are a countable group and the payoffs are functions of the group operation. In order to obtain the existence of equilibria, finitely additive mixed strategies have to be allowed. This creates a problem of selection of a product measure of mixed strategies. We propose a family of such selections and prove existence of an equilibrium that does not depend on the selection. As a byproduct we show that if finitely additive mixed strategies are allowed, then Wald's game admits an equilibrium. We also prove existence of equilibria for nontrivial extensions of matching-pennies and rock-scissors-paper. Finally we extend the main results to uncountable games.
Information Theory of DNA Shotgun Sequencing
Venue: arXiv cs.IT 2013
Year: 2013

DNA sequencing is the basic workhorse of modern day biology and medicine. Shotgun sequencing is the dominant technique used: many randomly located short fragments called reads are extracted from the DNA sequence, and these reads are assembled to reconstruct the original sequence. A basic question is: given a sequencing technology and the statistics of the DNA sequence, what is the minimum number of reads required for reliable reconstruction? This number provides a fundamental limit to the performance of {\em any} assembly algorithm. For a simple statistical model of the DNA sequence and the read process, we show that the answer admits a critical phenomena in the asymptotic limit of long DNA sequences: if the read length is below a threshold, reconstruction is impossible no matter how many reads are observed, and if the read length is above the threshold, having enough reads to cover the DNA sequence is sufficient to reconstruct. The threshold is computed in terms of the Renyi entropy rate of the DNA sequence. We also study the impact of noise in the read process on the performance.
Generalized fuzzy rough sets based on fuzzy coverings
Venue: arXiv cs.IT 2013
Year: 2013

This paper further studies the fuzzy rough sets based on fuzzy coverings. We first present the notions of the lower and upper approximation operators based on fuzzy coverings and derive their basic properties. To facilitate the computation of fuzzy coverings for fuzzy covering rough sets, the concepts of fuzzy subcoverings, the reducible and intersectional elements, the union and intersection operations are provided and their properties are discussed in detail. Afterwards, we introduce the concepts of consistent functions and fuzzy covering mappings and provide a basic theoretical foundation for the communication between fuzzy covering information systems. In addition, the notion of homomorphisms is proposed to reveal the relationship between fuzzy covering information systems. We show how large-scale fuzzy covering information systems and dynamic fuzzy covering information systems can be converted into small-scale ones by means of homomorphisms. Finally, an illustrative example is employed to show that the attribute reduction can be simplified significantly by our proposed approach.
Agreement in Directed Dynamic Networks
Venue: arXiv cs.DC 2013
Year: 2013

We study distributed computation in synchronous dynamic networks where an omniscient adversary controls the unidirectional communication links. Its behavior is modeled as a sequence of directed graphs representing the active (i.e. timely) communication links per round. We prove that consensus is impossible under some natural weak connectivity assumptions, and introduce vertex-stable root components as a means for circumventing this impossibility. Essentially, we assume that there is a short period of time during which an arbitrary part of the network remains strongly connected, while its interconnect topology may keep changing continuously. We present a consensus algorithm that works under this assumption, and prove its correctness. Our algorithm maintains a local estimate of the communication graphs, and applies techniques for detecting stable network properties and univalent system configurations. Our possibility results are complemented by several impossibility results and lower bounds for consensus and other distributed computing problems like leader election, revealing that our algorithm is asymptotically optimal.
Testing Booleanity and the Uncertainty Principle
Venue: arXiv cs.DM 2013
Year: 2013

Let f:{-1,1}^n -> R be a real function on the hypercube, given by its discrete Fourier expansion, or, equivalently, represented as a multilinear polynomial. We say that it is Boolean if its image is in {-1,1}. We show that every function on the hypercube with a sparse Fourier expansion must either be Boolean or far from Boolean. In particular, we show that a multilinear polynomial with at most k terms must either be Boolean, or output values different than -1 or 1 for a fraction of at least 2/(k+2)^2 of its domain. It follows that given oracle access to f, together with the guarantee that its representation as a multilinear polynomial has at most k terms, one can test Booleanity using O(k^2) queries. We show an Ω(k) queries lower bound for this problem. Our proof crucially uses Hirschman's entropic version of Heisenberg's uncertainty principle.
Sharp Bounds on Davenport-Schinzel Sequences of Every Order
Venue: arXiv cs.DM 2013
Year: 2013

One of the longest-standing open problems in computational geometry is to bound the lower envelope of $n$ univariate functions, each pair of which crosses at most $s$ times, for some fixed $s$. This problem is known to be equivalent to bounding the length of an order-$s$ Davenport-Schinzel sequence, namely a sequence over an $n$-letter alphabet that avoids alternating subsequences of the form $a \cdots b \cdots a \cdots b \cdots$ with length $s+2$. These sequences were introduced by Davenport and Schinzel in 1965 to model a certain problem in differential equations and have since been applied to bounding the running times of geometric algorithms, data structures, and the combinatorial complexity of geometric arrangements. Let $λ_s(n)$ be the maximum length of an order-$s$ DS sequence over $n$ letters. What is $λ_s$ asymptotically? This question has been answered satisfactorily (by Hart and Sharir, Agarwal, Sharir, and Shor, Klazar, and Nivasch) when $s$ is even or $s\le 3$. However, since the work of Agarwal, Sharir, and Shor in the mid-1980s there has been a persistent gap in our understanding of the odd orders. In this work we effectively close the problem by establishing sharp bounds on Davenport-Schinzel sequences of every order $s$. Our results reveal that, contrary to one's intuition, $λ_s(n)$ behaves essentially like $λ_{s-1}(n)$ when $s$ is odd. This refutes conjectures due to Alon et al. (2008) and Nivasch (2010).
Spectral Shape of Doubly-Generalized LDPC Codes: Efficient and Exact Evaluation
Venue: arXiv cs.IT 2013
Year: 2013

This paper analyzes the asymptotic exponent of the weight spectrum for irregular doubly-generalized LDPC (D-GLDPC) codes. In the process, an efficient numerical technique for its evaluation is presented, involving the solution of a 4 x 4 system of polynomial equations. The expression is consistent with previous results, including the case where the normalized weight or stopping set size tends to zero. The spectral shape is shown to admit a particularly simple form in the special case where all variable nodes are repetition codes of the same degree, a case which includes Tanner codes; for this case it is also shown how certain symmetry properties of the local weight distribution at the CNs induce a symmetry in the overall weight spectral shape function. Finally, using these new results, weight and stopping set size spectral shapes are evaluated for some example generalized and doubly-generalized LDPC code ensembles.
Block-Structured Adaptive Mesh Refinement Algorithms for Vlasov Simulation
Venue: arXiv cs.MS 2013
Year: 2013

Direct discretization of continuum kinetic equations, like the Vlasov equation, are under-utilized because the distribution function generally exists in a high-dimensional (>3D) space and computational cost increases geometrically with dimension. We propose to use high-order finite-volume techniques with block-structured adaptive mesh refinement (AMR) to reduce the computational cost. The primary complication comes from a solution state comprised of variables of different dimensions. We develop the algorithms required to extend standard single-dimension block structured AMR to the multi-dimension case. Specifically, algorithms for reduction and injection operations that transfer data between mesh hierarchies of different dimensions are explained in detail. In addition, modifications to the basic AMR algorithm that enable the use of high-order spatial and temporal discretizations are discussed. Preliminary results for a standard 1D+1V Vlasov-Poisson test problem are presented. Results indicate that there is potential for significant savings for some classes of Vlasov problems.
Solving Weighted Voting Game Design Problems Optimally: Representations, Synthesis, and Enumeration
Venue: arXiv cs.GT 2013
Year: 2013

We study the inverse power index problem for weighted voting games: the problem of finding a weighted voting game in which the power of the players is as close as possible to a certain target distribution. Our goal is to find algorithms that solve this problem exactly. Thereto, we study various subclasses of simple games, and their associated representation methods. We survey algorithms and impossibility results for the synthesis problem, i.e., converting a representation of a simple game into another representation. We contribute to the synthesis problem by showing that it is impossible to compute in polynomial time the list of ceiling coalitions (also known as shift-maximal losing coalitions) of a game from its list of roof coalitions (also known as shift-minimal winning coalitions), and vice versa. Then, we proceed by studying the problem of enumerating the set of weighted voting games. We present first a naive algorithm for this, running in doubly exponential time. Using our knowledge of the synthesis problem, we then improve on this naive algorithm, and we obtain an enumeration algorithm that runs in quadratic exponential time (that is, O(2^(n^2) p(n)) for a polynomial p). Moreover, we show that this algorithm runs in output-polynomial time, making it the best possible enumeration algorithm up to a polynomial factor. Finally, we propose an exact anytime algorithm for the inverse power index problem that runs in exponential time. This algorithm is straightforward and general: it computes the error for each game enumerated, and outputs the game that minimizes this error. By the genericity of our approach, our algorithm can be used to find a weighted voting game that optimizes any exponential time computable function. We implement our algorithm for the case of the normalized Banzhaf index, and we perform experiments in order to study performance and error convergence.
A Game-Theoretic Model Motivated by the DARPA Network Challenge
Venue: arXiv cs.GT 2013
Year: 2013

In this paper we propose a game-theoretic model to analyze events similar to the 2009 \emph{DARPA Network Challenge}, which was organized by the Defense Advanced Research Projects Agency (DARPA) for exploring the roles that the Internet and social networks play in incentivizing wide-area collaborations. The challenge was to form a group that would be the first to find the locations of ten moored weather balloons across the United States. We consider a model in which $N$ people (who can form groups) are located in some topology with a fixed coverage volume around each person's geographical location. We consider various topologies where the players can be located such as the Euclidean $d$-dimension space and the vertices of a graph. A balloon is placed in the space and a group wins if it is the first one to report the location of the balloon. A larger team has a higher probability of finding the balloon, but we assume that the prize money is divided equally among the team members. Hence there is a competing tension to keep teams as small as possible. \emph{Risk aversion} is the reluctance of a person to accept a bargain with an uncertain payoff rather than another bargain with a more certain, but possibly lower, expected payoff. In our model we consider the \emph{isoelastic} utility function derived from the Arrow-Pratt measure of relative risk aversion. The main aim is to analyze the structures of the groups in Nash equilibria for our model. For the $d$-dimensional Euclidean space ($d\geq 1$) and the class of bounded degree regular graphs we show that in any Nash Equilibrium the \emph{richest} group (having maximum expected utility per person) covers a constant fraction of the total volume.
A Spectral Algorithm for Latent Dirichlet Allocation
Venue: arXiv cs.LG 2013
Year: 2013

The problem of topic modeling can be seen as a generalization of the clustering problem, in that it posits that observations are generated due to multiple latent factors (e.g., the words in each document are generated as a mixture of several active topics, as opposed to just one). This increased representational power comes at the cost of a more challenging unsupervised learning problem of estimating the topic probability vectors (the distributions over words for each topic), when only the words are observed and the corresponding topics are hidden. We provide a simple and efficient learning procedure that is guaranteed to recover the parameters for a wide class of mixture models, including the popular latent Dirichlet allocation (LDA) model. For LDA, the procedure correctly recovers both the topic probability vectors and the prior over the topics, using only trigram statistics (i.e., third order moments, which may be estimated with documents containing just three words). The method, termed Excess Correlation Analysis (ECA), is based on a spectral decomposition of low order moments (third and fourth order) via two singular value decompositions (SVDs). Moreover, the algorithm is scalable since the SVD operations are carried out on $k\times k$ matrices, where $k$ is the number of latent factors (e.g. the number of topics), rather than in the $d$-dimensional observed space (typically $d \gg k$).
Multi-level agent-based modeling - A literature survey
Venue: arXiv cs.MA 2013
Year: 2013

During last decade, multi-level agent-based modeling has received significant and dramatically increasing interest. In this article we present a comprehensive and structured review of literature on the subject. We present the main theoretical contributions and application domains of this concept, with an emphasis on social, flow, biological and biomedical models.
On projections of arbitrary lattices
Venue: arXiv cs.CG 2013
Year: 2013

In this paper we prove that given any two point lattices $Λ_1 \subset \mathbb{R}^n$ and $ Λ_2 \subset \nobreak \mathbb{R}^{n-k}$, there is a set of $k$ vectors $\bm{v}_i \in Λ_1$ such that $Λ_2$ is, up to similarity, arbitrarily close to the projection of $Λ_1$ onto the orthogonal complement of the subspace spanned by $\bm{v}_1, \ldots, \bm{v}_k$. This result extends the main theorem of \cite{Sloane2} and has applications in communication theory.
Proving Inequalities and Solving Global Optimization Problems via Simplified CAD Projection
Venue: arXiv cs.SC 2013
Year: 2013

Let $\xx_n=(x_1,\ldots,x_n)$ and $f\in \R[\xx_n,k]$. The problem of finding all $k_0$ such that $f(\xx_n,k_0)\ge 0$ on $\mathbb{R}^n$ is considered in this paper, which obviously takes as a special case the problem of computing the global infimum or proving the semi-definiteness of a polynomial. For solving the problems, we propose a simplified Brown's CAD projection operator, \Nproj, of which the projection scale is always no larger than that of Brown's. For many problems, the scale is much smaller than that of Brown's. As a result, the lifting phase is also simplified. Some new algorithms based on \Nproj\ for solving those problems are designed and proved to be correct. Comparison to some existing tools on some examples is reported to illustrate the effectiveness of our new algorithms.
A note on the factorization conjecture
Venue: arXiv cs.FL 2013
Year: 2013

We give partial results on the factorization conjecture on codes proposed by Schutzenberger. We consider finite maximal codes C over the alphabet A = {a, b} with C \cap a^* = a^p, for a prime number p. Let P, S in Z <A>, with S = S_0 + S_1, supp(S_0) \subset a^* and supp(S_1) \subset a^*b supp(S_0). We prove that if (P,S) is a factorization for C then (P,S) is positive, that is P,S have coefficients 0,1, and we characterize the structure of these codes. As a consequence, we prove that if C is a finite maximal code such that each word in C has at most 4 occurrences of b's and a^p is in C, then each factorization for C is a positive factorization. We also discuss the structure of these codes. The obtained results show once again relations between (positive) factorizations and factorizations of cyclic groups.
Optimum Commutative Group Codes
Venue: arXiv cs.IT 2013
Year: 2013

A method for finding an optimum $n$-dimensional commutative group code of a given order $M$ is presented. The approach explores the structure of lattices related to these codes and provides a significant reduction in the number of non-isometric cases to be analyzed. The classical factorization of matrices into Hermite and Smith normal forms and also basis reduction of lattices are used to characterize isometric commutative group codes. Several examples of optimum commutative group codes are also presented.
Diffusion Adaptation over Networks
Venue: arXiv cs.MA 2013
Year: 2013

Adaptive networks are well-suited to perform decentralized information processing and optimization tasks and to model various types of self-organized and complex behavior encountered in nature. Adaptive networks consist of a collection of agents with processing and learning abilities. The agents are linked together through a connection topology, and they cooperate with each other through local interactions to solve distributed optimization, estimation, and inference problems in real-time. The continuous diffusion of information across the network enables agents to adapt their performance in relation to streaming data and network conditions; it also results in improved adaptation and learning performance relative to non-cooperative agents. This article provides an overview of diffusion strategies for adaptation and learning over networks. The article is divided into several sections: 1. Motivation; 2. Mean-Square-Error Estimation; 3. Distributed Optimization via Diffusion Strategies; 4. Adaptive Diffusion Strategies; 5. Performance of Steepest-Descent Diffusion Strategies; 6. Performance of Adaptive Diffusion Strategies; 7. Comparing the Performance of Cooperative Strategies; 8. Selecting the Combination Weights; 9. Diffusion with Noisy Information Exchanges; 10. Extensions and Further Considerations; Appendix A: Properties of Kronecker Products; Appendix B: Graph Laplacian and Network Connectivity; Appendix C: Stochastic Matrices; Appendix D: Block Maximum Norm; Appendix E: Comparison with Consensus Strategies; References.
Large Social Networks can be Targeted for Viral Marketing with Small Seed Sets
Venue: arXiv cs.SI 2013
Year: 2013

In a "tipping" model, each node in a social network, representing an individual, adopts a behavior if a certain number of his incoming neighbors previously held that property. A key problem for viral marketers is to determine an initial "seed" set in a network such that if given a property then the entire network adopts the behavior. Here we introduce a method for quickly finding seed sets that scales to very large networks. Our approach finds a set of nodes that guarantees spreading to the entire network under the tipping model. After experimentally evaluating 31 real-world networks, we found that our approach often finds such sets that are several orders of magnitude smaller than the population size. Our approach also scales well - on a Friendster social network consisting of 5.6 million nodes and 28 million edges we found a seed sets in under 3.6 hours. We also find that highly clustered local neighborhoods and dense network-wide community structure together suppress the ability of a trend to spread under the tipping model.