OpenRaiser/Intern-Atlas huggingface dataset:
A Logical Characterization of Constraint-Based Causal Discovery
Venue: arXiv cs.AI 2012
Year: 2012

We present a novel approach to constraint-based causal discovery, that takes the form of straightforward logical inference, applied to a list of simple, logical statements about causal relations that are derived directly from observed (in)dependencies. It is both sound and complete, in the sense that all invariant features of the corresponding partial ancestral graph (PAG) are identified, even in the presence of latent variables and selection bias. The approach shows that every identifiable causal relation corresponds to one of just two fundamental forms. More importantly, as the basic building blocks of the method do not rely on the detailed (graphical) structure of the corresponding PAG, it opens up a range of new opportunities, including more robust inference, detailed accountability, and application to large models.
Ensembles of Kernel Predictors
Venue: arXiv cs.LG 2012
Year: 2012

This paper examines the problem of learning with a finite and possibly large set of p base kernels. It presents a theoretical and empirical analysis of an approach addressing this problem based on ensembles of kernel predictors. This includes novel theoretical guarantees based on the Rademacher complexity of the corresponding hypothesis sets, the introduction and analysis of a learning algorithm based on these hypothesis sets, and a series of experiments using ensembles of kernel predictors with several data sets. Both convex combinations of kernel-based hypotheses and more general Lq-regularized nonnegative combinations are analyzed. These theoretical, algorithmic, and empirical results are compared with those achieved by using learning kernel techniques, which can be viewed as another approach for solving the same problem.
Boosting as a Product of Experts
Venue: arXiv cs.LG 2012
Year: 2012

In this paper, we derive a novel probabilistic model of boosting as a Product of Experts. We re-derive the boosting algorithm as a greedy incremental model selection procedure which ensures that addition of new experts to the ensemble does not decrease the likelihood of the data. These learning rules lead to a generic boosting algorithm - POE- Boost which turns out to be similar to the AdaBoost algorithm under certain assumptions on the expert probabilities. The paper then extends the POEBoost algorithm to POEBoost.CS which handles hypothesis that produce probabilistic predictions. This new algorithm is shown to have better generalization performance compared to other state of the art algorithms.
Dynamic consistency and decision making under vacuous belief
Venue: arXiv cs.AI 2012
Year: 2012

The ideas about decision making under ignorance in economics are combined with the ideas about uncertainty representation in computer science. The combination sheds new light on the question of how artificial agents can act in a dynamically consistent manner. The notion of sequential consistency is formalized by adapting the law of iterated expectation for plausibility measures. The necessary and sufficient condition for a certainty equivalence operator for Nehring-Puppe's preference to be sequentially consistent is given. This result sheds light on the models of decision making under uncertainty.
Bregman divergence as general framework to estimate unnormalized statistical models
Venue: arXiv cs.LG 2012
Year: 2012

We show that the Bregman divergence provides a rich framework to estimate unnormalized statistical models for continuous or discrete random variables, that is, models which do not integrate or sum to one, respectively. We prove that recent estimation methods such as noise-contrastive estimation, ratio matching, and score matching belong to the proposed framework, and explain their interconnection based on supervised learning. Further, we discuss the role of boosting in unsupervised learning.
Sequential Inference for Latent Force Models
Venue: arXiv cs.LG 2012
Year: 2012

Latent force models (LFMs) are hybrid models combining mechanistic principles with non-parametric components. In this article, we shall show how LFMs can be equivalently formulated and solved using the state variable approach. We shall also show how the Gaussian process prior used in LFMs can be equivalently formulated as a linear statespace model driven by a white noise process and how inference on the resulting model can be efficiently implemented using Kalman filter and smoother. Then we shall show how the recently proposed switching LFM can be reformulated using the state variable approach, and how we can construct a probabilistic model for the switches by formulating a similar switching LFM as a switching linear dynamic system (SLDS). We illustrate the performance of the proposed methodology in simulated scenarios and apply it to inferring the switching points in GPS data collected from car movement data in urban environment.
What Cannot be Learned with Bethe Approximations
Venue: arXiv cs.LG 2012
Year: 2012

We address the problem of learning the parameters in graphical models when inference is intractable. A common strategy in this case is to replace the partition function with its Bethe approximation. We show that there exists a regime of empirical marginals where such Bethe learning will fail. By failure we mean that the empirical marginals cannot be recovered from the approximated maximum likelihood parameters (i.e., moment matching is not achieved). We provide several conditions on empirical marginals that yield outer and inner bounds on the set of Bethe learnable marginals. An interesting implication of our results is that there exists a large class of marginals that cannot be obtained as stable fixed points of belief propagation. Taken together our results provide a novel approach to analyzing learning with Bethe approximations and highlight when it can be expected to work or fail.
Detecting low-complexity unobserved causes
Venue: arXiv cs.LG 2012
Year: 2012

We describe a method that infers whether statistical dependences between two observed variables X and Y are due to a "direct" causal link or only due to a connecting causal path that contains an unobserved variable of low complexity, e.g., a binary variable. This problem is motivated by statistical genetics. Given a genetic marker that is correlated with a phenotype of interest, we want to detect whether this marker is causal or it only correlates with a causal one. Our method is based on the analysis of the location of the conditional distributions P(Y|x) in the simplex of all distributions of Y. We report encouraging results on semi-empirical data.
Learning Determinantal Point Processes
Venue: arXiv cs.LG 2012
Year: 2012

Determinantal point processes (DPPs), which arise in random matrix theory and quantum physics, are natural models for subset selection problems where diversity is preferred. Among many remarkable properties, DPPs offer tractable algorithms for exact inference, including computing marginal probabilities and sampling; however, an important open question has been how to learn a DPP from labeled training data. In this paper we propose a natural feature-based parameterization of conditional DPPs, and show how it leads to a convex and efficient learning formulation. We analyze the relationship between our model and binary Markov random fields with repulsive potentials, which are qualitatively similar but computationally intractable. Finally, we apply our approach to the task of extractive summarization, where the goal is to choose a small subset of sentences conveying the most important information from a set of documents. In this task there is a fundamental tradeoff between sentences that are highly relevant to the collection as a whole, and sentences that are diverse and not repetitive. Our parameterization allows us to naturally balance these two characteristics. We evaluate our system on data from the DUC 2003/04 multi-document summarization task, achieving state-of-the-art results.
Improving the Scalability of Optimal Bayesian Network Learning with External-Memory Frontier Breadth-First Branch and Bound Search
Venue: arXiv cs.AI 2012
Year: 2012

Previous work has shown that the problem of learning the optimal structure of a Bayesian network can be formulated as a shortest path finding problem in a graph and solved using A* search. In this paper, we improve the scalability of this approach by developing a memory-efficient heuristic search algorithm for learning the structure of a Bayesian network. Instead of using A*, we propose a frontier breadth-first branch and bound search that leverages the layered structure of the search graph of this problem so that no more than two layers of the graph, plus solution reconstruction information, need to be stored in memory at a time. To further improve scalability, the algorithm stores most of the graph in external memory, such as hard disk, when it does not fit in RAM. Experimental results show that the resulting algorithm solves significantly larger problems than the current state of the art.
Asymptotic Efficiency of Deterministic Estimators for Discrete Energy-Based Models: Ratio Matching and Pseudolikelihood
Venue: arXiv cs.LG 2012
Year: 2012

Standard maximum likelihood estimation cannot be applied to discrete energy-based models in the general case because the computation of exact model probabilities is intractable. Recent research has seen the proposal of several new estimators designed specifically to overcome this intractability, but virtually nothing is known about their theoretical properties. In this paper, we present a generalized estimator that unifies many of the classical and recently proposed estimators. We use results from the standard asymptotic theory for M-estimators to derive a generic expression for the asymptotic covariance matrix of our generalized estimator. We apply these results to study the relative statistical efficiency of classical pseudolikelihood and the recently-proposed ratio matching estimator.
Nonparametric Divergence Estimation with Applications to Machine Learning on Distributions
Venue: arXiv cs.LG 2012
Year: 2012

Low-dimensional embedding, manifold learning, clustering, classification, and anomaly detection are among the most important problems in machine learning. The existing methods usually consider the case when each instance has a fixed, finite-dimensional feature representation. Here we consider a different setting. We assume that each instance corresponds to a continuous probability distribution. These distributions are unknown, but we are given some i.i.d. samples from each distribution. Our goal is to estimate the distances between these distributions and use these distances to perform low-dimensional embedding, clustering/classification, or anomaly detection for the distributions. We present estimation algorithms, describe how to apply them for machine learning tasks on distributions, and show empirical results on synthetic data, real word images, and astronomical data sets.
Distributed Anytime MAP Inference
Venue: arXiv cs.AI 2012
Year: 2012

We present a distributed anytime algorithm for performing MAP inference in graphical models. The problem is formulated as a linear programming relaxation over the edges of a graph. The resulting program has a constraint structure that allows application of the Dantzig-Wolfe decomposition principle. Subprograms are defined over individual edges and can be computed in a distributed manner. This accommodates solutions to graphs whose state space does not fit in memory. The decomposition master program is guaranteed to compute the optimal solution in a finite number of iterations, while the solution converges monotonically with each iteration. Formulating the MAP inference problem as a linear program allows additional (global) constraints to be defined; something not possible with message passing algorithms. Experimental results show that our algorithm's solution quality outperforms most current algorithms and it scales well to large problems.
The Structure of Signals: Causal Interdependence Models for Games of Incomplete Information
Venue: arXiv cs.GT 2012
Year: 2012

Traditional economic models typically treat private information, or signals, as generated from some underlying state. Recent work has explicated alternative models, where signals correspond to interpretations of available information. We show that the difference between these formulations can be sharply cast in terms of causal dependence structure, and employ graphical models to illustrate the distinguishing characteristics. The graphical representation supports inferences about signal patterns in the interpreted framework, and suggests how results based on the generated model can be extended to more general situations. Specific insights about bidding games in classical auction mechanisms derive from qualitative graphical models.
Sparse matrix-variate Gaussian process blockmodels for network modeling
Venue: arXiv cs.LG 2012
Year: 2012

We face network data from various sources, such as protein interactions and online social networks. A critical problem is to model network interactions and identify latent groups of network nodes. This problem is challenging due to many reasons. For example, the network nodes are interdependent instead of independent of each other, and the data are known to be very noisy (e.g., missing edges). To address these challenges, we propose a new relational model for network data, Sparse Matrix-variate Gaussian process Blockmodel (SMGB). Our model generalizes popular bilinear generative models and captures nonlinear network interactions using a matrix-variate Gaussian process with latent membership variables. We also assign sparse prior distributions on the latent membership variables to learn sparse group assignments for individual network nodes. To estimate the latent variables efficiently from data, we develop an efficient variational expectation maximization method. We compared our approaches with several state-of-the-art network models on both synthetic and real-world network datasets. Experimental results demonstrate SMGBs outperform the alternative approaches in terms of discovering latent classes or predicting unknown interactions.
Physical Layer Security for Two-Way Untrusted Relaying with Friendly Jammers
Venue: arXiv cs.GT 2012
Year: 2012

In this paper, we consider a two-way relay network where two sources can communicate only through an untrusted intermediate relay, and investigate the physical layer security issue of this two-way relay scenario. Specifically, we treat the intermediate relay as an eavesdropper from which the information transmitted by the sources needs to be kept secret, despite the fact that its cooperation in relaying this information is essential. We indicate that a non-zero secrecy rate is indeed achievable in this two-way relay network even without external friendly jammers. As for the system with friendly jammers, after further analysis, we can obtain that the secrecy rate of the sources can be effectively improved by utilizing proper jamming power from the friendly jammers. Then, we formulate a Stackelberg game model between the sources and the friendly jammers as a power control scheme to achieve the optimized secrecy rate of the sources, in which the sources are treated as the sole buyer and the friendly jammers are the sellers. In addition, the optimal solutions of the jamming power and the asking prices are given and a distributed updating algorithm to obtain the Stakelberg equilibrium is provided for the proposed game. Finally, the simulations results verify the properties and the efficiency of the proposed Stackelberg game based scheme.
Exploring Geometric Shapes with Touch
Venue: arXiv cs.HC 2012
Year: 2012

We propose a new technique to help users to explore geometric shapes without vision. This technique is based on a guidance using directional cues with a pin array. This is an alternative to the usual technique that consists of raising the pins corresponding to dark pixels around the cursor. In this paper we compare the exploration of geometric shapes with our new technique in unimanual and bimanual conditions. The users made fewer errors in unimanual condition than in bimanual condition. However they did not explore the shapes more quickly and there was no difference in confidence in their answer.
Alternating register automata on finite words and trees
Venue: arXiv cs.DB 2012
Year: 2012

We study alternating register automata on data words and data trees in relation to logics. A data word (resp. data tree) is a word (resp. tree) whose every position carries a label from a finite alphabet and a data value from an infinite domain. We investigate one-way automata with alternating control over data words or trees, with one register for storing data and comparing them for equality. This is a continuation of the study started by Demri, Lazic and Jurdzinski. From the standpoint of register automata models, this work aims at two objectives: (1) simplifying the existent decidability proofs for the emptiness problem for alternating register automata; and (2) exhibiting decidable extensions for these models. From the logical perspective, we show that (a) in the case of data words, satisfiability of LTL with one register and quantification over data values is decidable; and (b) the satisfiability problem for the so-called forward fragment of XPath on XML documents is decidable, even in the presence of DTDs and even of key constraints. The decidability is obtained through a reduction to the automata model introduced. This fragment contains the child, descendant, next-sibling and following-sibling axes, as well as data equality and inequality tests.
Generalized Principal Component Analysis (GPCA)
Venue: arXiv cs.CV 2012
Year: 2012

This paper presents an algebro-geometric solution to the problem of segmenting an unknown number of subspaces of unknown and varying dimensions from sample data points. We represent the subspaces with a set of homogeneous polynomials whose degree is the number of subspaces and whose derivatives at a data point give normal vectors to the subspace passing through the point. When the number of subspaces is known, we show that these polynomials can be estimated linearly from data; hence, subspace segmentation is reduced to classifying one point per subspace. We select these points optimally from the data set by minimizing certain distance function, thus dealing automatically with moderate noise in the data. A basis for the complement of each subspace is then recovered by applying standard PCA to the collection of derivatives (normal vectors). Extensions of GPCA that deal with data in a high- dimensional space and with an unknown number of subspaces are also presented. Our experiments on low-dimensional data show that GPCA outperforms existing algebraic algorithms based on polynomial factorization and provides a good initialization to iterative techniques such as K-subspaces and Expectation Maximization. We also present applications of GPCA to computer vision problems such as face clustering, temporal video segmentation, and 3D motion segmentation from point correspondences in multiple affine views.
Simple transmission strategies for interference channel
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we investigate performances of simple transmission strategies. We first consider two user SISO Gaussian symmetric interference channel (IC) for which Etkin, Tse and Wang proposed a scheme (ETW scheme) which achieves one bit gap to the capacity. We compare performance of point-to-point (p2p) codes with that of the ETW scheme in practical range of transmitter power. It turns out that p2p coding scheme performs better or as nearly good as the ETW scheme. Next, we consider K user SISO Gaussian symmetric IC. We define interference regimes for K user SISO Gaussian symmetric IC and provide closed-form characterization of the symmetric rate achieved by the p2p scheme and the ETW scheme. Using this characterization, we evaluate performances of simple strategies with K=3, and show the similar trend to two user case.
On Channels with Action-Dependent States
Venue: arXiv cs.IT 2012
Year: 2012

Action-dependent channels model scenarios in which transmission takes place in two successive phases. In the first phase, the encoder selects an "action" sequence, with the twofold aim of conveying information to the receiver and of affecting in a desired way the state of the channel to be used in the second phase. In the second phase, communication takes place in the presence the mentioned action-dependent state. In this work, two extensions of the original action-dependent channel are studied. In the first, the decoder is interested in estimating not only the message, but also the state sequence within an average per-letter distortion. Under the constraint of common knowledge (i.e., the decoder's estimate of the state must be recoverable also at the encoder) and assuming non-causal state knowledge at the encoder in the second phase, we obtain a single-letter characterization of the achievable rate-distortion-cost trade-off. In the second extension, we study an action-dependent degraded broadcast channel. Under the assumption that the encoder knows the state sequence causally in the second phase, the capacity-cost region is identified. Various examples, including Gaussian channels and a model with a "probing" encoder, are also provided to show the advantage of a proper joint design of the two communication phases.
MIMO capacity for deterministic channel models: sublinear growth
Venue: arXiv cs.IT 2012
Year: 2012

This is the second paper of the authors in a series concerned with the development of a deterministic model for the transfer matrix of a MIMO system. Starting from the Maxwell equations, we have described in \cite{BCFM} the generic structure of such a deterministic transfer matrix. In the current paper we apply the results of \cite{BCFM} in order to study the (Shannon-Foschini) capacity behavior of a MIMO system as a function of the deterministic spread function of the environment, and the number of transmitting and receiving antennas. The antennas are assumed to fill in a given, fixed volume. Under some generic assumptions, we prove that the capacity grows much more slowly than linearly with the number of antennas. These results reinforce previous heuristic results obtained from statistical models of the transfer matrix, which also predict a sublinear behavior.
Noncontinous additive entropies of partitions
Venue: arXiv cs.IT 2012
Year: 2012

In a previous paper: A. Paszkiewicz, T. Sobieszek, Additive Entropies of Partitions, we have given a description of additive partition entropies that is real functions $I$ on the set of finite partitions that are additive on stochastically independent partitions in a given probability space. We now present an analogical result, this time without assuming continuity. As a by-product of our efforts we solve a 2-cocycle functional equation for certain subsets of convex cones.