OpenRaiser/Intern-Atlas huggingface dataset:
Learning Convex Inference of Marginals
Venue: arXiv cs.LG 2012
Year: 2012

Graphical models trained using maximum likelihood are a common tool for probabilistic inference of marginal distributions. However, this approach suffers difficulties when either the inference process or the model is approximate. In this paper, the inference process is first defined to be the minimization of a convex function, inspired by free energy approximations. Learning is then done directly in terms of the performance of the inference process at univariate marginal prediction. The main novelty is that this is a direct minimization of emperical risk, where the risk measures the accuracy of predicted marginals.
Projected Subgradient Methods for Learning Sparse Gaussians
Venue: arXiv cs.LG 2012
Year: 2012

Gaussian Markov random fields (GMRFs) are useful in a broad range of applications. In this paper we tackle the problem of learning a sparse GMRF in a high-dimensional space. Our approach uses the l1-norm as a regularization on the inverse covariance matrix. We utilize a novel projected gradient method, which is faster than previous methods in practice and equal to the best performing of these in asymptotic complexity. We also extend the l1-regularized objective to the problem of sparsifying entire blocks within the inverse covariance matrix. Our methods generalize fairly easily to this case, while other methods do not. We demonstrate that our extensions give better generalization performance on two real domains--biological network analysis and a 2D-shape modeling image task.
Gibbs Sampling in Factorized Continuous-Time Markov Processes
Venue: arXiv cs.AI 2012
Year: 2012

A central task in many applications is reasoning about processes that change over continuous time. Continuous-Time Bayesian Networks is a general compact representation language for multi-component continuous-time processes. However, exact inference in such processes is exponential in the number of components, and thus infeasible for most models of interest. Here we develop a novel Gibbs sampling procedure for multi-component processes. This procedure iteratively samples a trajectory for one of the components given the remaining ones. We show how to perform exact sampling that adapts to the natural time scale of the sampled process. Moreover, we show that this sampling procedure naturally exploits the structure of the network to reduce the computational cost of each step. This procedure is the first that can provide asymptotically unbiased approximation in such processes.
Convex Point Estimation using Undirected Bayesian Transfer Hierarchies
Venue: arXiv cs.LG 2012
Year: 2012

When related learning tasks are naturally arranged in a hierarchy, an appealing approach for coping with scarcity of instances is that of transfer learning using a hierarchical Bayes framework. As fully Bayesian computations can be difficult and computationally demanding, it is often desirable to use posterior point estimates that facilitate (relatively) efficient prediction. However, the hierarchical Bayes framework does not always lend itself naturally to this maximum aposteriori goal. In this work we propose an undirected reformulation of hierarchical Bayes that relies on priors in the form of similarity measures. We introduce the notion of "degree of transfer" weights on components of these similarity measures, and show how they can be automatically learned within a joint probabilistic framework. Importantly, our reformulation results in a convex objective for many learning problems, thus facilitating optimal posterior point estimation using standard optimization techniques. In addition, we no longer require proper priors, allowing for flexible and straightforward specification of joint distributions over transfer hierarchies. We show that our framework is effective for learning models that are part of transfer hierarchies for two real-life tasks: object shape modeling using Gaussian density estimation and document classification.
Latent Topic Models for Hypertext
Venue: arXiv cs.IR 2012
Year: 2012

Latent topic models have been successfully applied as an unsupervised topic discovery technique in large document collections. With the proliferation of hypertext document collection such as the Internet, there has also been great interest in extending these approaches to hypertext [6, 9]. These approaches typically model links in an analogous fashion to how they model words - the document-link co-occurrence matrix is modeled in the same way that the document-word co-occurrence matrix is modeled in standard topic models. In this paper we present a probabilistic generative model for hypertext document collections that explicitly models the generation of links. Specifically, links from a word w to a document d depend directly on how frequent the topic of w is in d, in addition to the in-degree of d. We show how to perform EM learning on this model efficiently. By not modeling links as analogous to words, we end up using far fewer free parameters and obtain better link prediction results.
Cumulative distribution networks and the derivative-sum-product algorithm
Venue: arXiv cs.LG 2012
Year: 2012

We introduce a new type of graphical model called a "cumulative distribution network" (CDN), which expresses a joint cumulative distribution as a product of local functions. Each local function can be viewed as providing evidence about possible orderings, or rankings, of variables. Interestingly, we find that the conditional independence properties of CDNs are quite different from other graphical models. We also describe a messagepassing algorithm that efficiently computes conditional cumulative distributions. Due to the unique independence properties of the CDN, these messages do not in general have a one-to-one correspondence with messages exchanged in standard algorithms, such as belief propagation. We demonstrate the application of CDNs for structured ranking learning using a previously-studied multi-player gaming dataset.
Convergent Message-Passing Algorithms for Inference over General Graphs with Convex Free Energies
Venue: arXiv cs.LG 2012
Year: 2012

Inference problems in graphical models can be represented as a constrained optimization of a free energy function. It is known that when the Bethe free energy is used, the fixedpoints of the belief propagation (BP) algorithm correspond to the local minima of the free energy. However BP fails to converge in many cases of interest. Moreover, the Bethe free energy is non-convex for graphical models with cycles thus introducing great difficulty in deriving efficient algorithms for finding local minima of the free energy for general graphs. In this paper we introduce two efficient BP-like algorithms, one sequential and the other parallel, that are guaranteed to converge to the global minimum, for any graph, over the class of energies known as "convex free energies". In addition, we propose an efficient heuristic for setting the parameters of the convex free energy based on the structure of the graph.
Partitioned Linear Programming Approximations for MDPs
Venue: arXiv cs.AI 2012
Year: 2012

Approximate linear programming (ALP) is an efficient approach to solving large factored Markov decision processes (MDPs). The main idea of the method is to approximate the optimal value function by a set of basis functions and optimize their weights by linear programming (LP). This paper proposes a new ALP approximation. Comparing to the standard ALP formulation, we decompose the constraint space into a set of low-dimensional spaces. This structure allows for solving the new LP efficiently. In particular, the constraints of the LP can be satisfied in a compact form without an exponential dependence on the treewidth of ALP constraints. We study both practical and theoretical aspects of the proposed approach. Moreover, we demonstrate its scale-up potential on an MDP with more than 2^100 states.
CT-NOR: Representing and Reasoning About Events in Continuous Time
Venue: arXiv cs.AI 2012
Year: 2012

We present a generative model for representing and reasoning about the relationships among events in continuous time. We apply the model to the domain of networked and distributed computing environments where we fit the parameters of the model from timestamp observations, and then use hypothesis testing to discover dependencies between the events and changes in behavior for monitoring and diagnosis. After introducing the model, we present an EM algorithm for fitting the parameters and then present the hypothesis testing approach for both dependence discovery and change-point detection. We validate the approach for both tasks using real data from a trace of network events at Microsoft Research Cambridge. Finally, we formalize the relationship between the proposed model and the noisy-or gate for cases when time can be discretized.
Model-Based Bayesian Reinforcement Learning in Large Structured Domains
Venue: arXiv cs.AI 2012
Year: 2012

Model-based Bayesian reinforcement learning has generated significant interest in the AI community as it provides an elegant solution to the optimal exploration-exploitation tradeoff in classical reinforcement learning. Unfortunately, the applicability of this type of approach has been limited to small domains due to the high complexity of reasoning about the joint posterior over model parameters. In this paper, we consider the use of factored representations combined with online planning techniques, to improve scalability of these methods. The main contribution of this paper is a Bayesian framework for learning the structure and parameters of a dynamical system, while also simultaneously planning a (near-)optimal sequence of actions.
Learning the Bayesian Network Structure: Dirichlet Prior versus Data
Venue: arXiv cs.LG 2012
Year: 2012

In the Bayesian approach to structure learning of graphical models, the equivalent sample size (ESS) in the Dirichlet prior over the model parameters was recently shown to have an important effect on the maximum-a-posteriori estimate of the Bayesian network structure. In our first contribution, we theoretically analyze the case of large ESS-values, which complements previous work: among other results, we find that the presence of an edge in a Bayesian network is favoured over its absence even if both the Dirichlet prior and the data imply independence, as long as the conditional empirical distribution is notably different from uniform. In our second contribution, we focus on realistic ESS-values, and provide an analytical approximation to the "optimal" ESS-value in a predictive sense (its accuracy is also validated experimentally): this approximation provides an understanding as to which properties of the data have the main effect determining the "optimal" ESS-value.
Propagation using Chain Event Graphs
Venue: arXiv cs.AI 2012
Year: 2012

A Chain Event Graph (CEG) is a graphial model which designed to embody conditional independencies in problems whose state spaces are highly asymmetric and do not admit a natural product structure. In this paer we present a probability propagation algorithm which uses the topology of the CEG to build a transporter CEG. Intriungly,the transporter CEG is directly analogous to the triangulated Bayesian Network (BN) in the more conventional junction tree propagation algorithms used with BNs. The propagation method uses factorization formulae also analogous to (but different from) the ones using potentials on cliques and separators of the BN. It appears that the methods will be typically more efficient than the BN algorithms when applied to contexts where there is significant asymmetry present.
Additive Approximation for Near-Perfect Phylogeny Construction
Venue: arXiv cs.DS 2012
Year: 2012

We study the problem of constructing phylogenetic trees for a given set of species. The problem is formulated as that of finding a minimum Steiner tree on $n$ points over the Boolean hypercube of dimension $d$. It is known that an optimal tree can be found in linear time if the given dataset has a perfect phylogeny, i.e. cost of the optimal phylogeny is exactly $d$. Moreover, if the data has a near-perfect phylogeny, i.e. the cost of the optimal Steiner tree is $d+q$, it is known that an exact solution can be found in running time which is polynomial in the number of species and $d$, yet exponential in $q$. In this work, we give a polynomial-time algorithm (in both $d$ and $q$) that finds a phylogenetic tree of cost $d+O(q^2)$. This provides the best guarantees known - namely, a $(1+o(1))$-approximation - for the case $\log(d) \ll q \ll \sqrt{d}$, broadening the range of settings for which near-optimal solutions can be efficiently found. We also discuss the motivation and reasoning for studying such additive approximations.
Coalitional Games for Transmitter Cooperation in MIMO Multiple Access Channels
Venue: arXiv cs.IT 2012
Year: 2012

Cooperation between nodes sharing a wireless channel is becoming increasingly necessary to achieve performance goals in a wireless network. The problem of determining the feasibility and stability of cooperation between rational nodes in a wireless network is of great importance in understanding cooperative behavior. This paper addresses the stability of the grand coalition of transmitters signaling over a multiple access channel using the framework of cooperative game theory. The external interference experienced by each TX is represented accurately by modeling the cooperation game between the TXs in \emph{partition form}. Single user decoding and successive interference cancelling strategies are examined at the receiver. In the absence of coordination costs, the grand coalition is shown to be \emph{sum-rate optimal} for both strategies. Transmitter cooperation is \emph{stable}, if and only if the core of the game (the set of all divisions of grand coalition utility such that no coalition deviates) is nonempty. Determining the stability of cooperation is a co-NP-complete problem in general. For a single user decoding receiver, transmitter cooperation is shown to be \emph{stable} at both high and low SNRs, while for an interference cancelling receiver with a fixed decoding order, cooperation is stable only at low SNRs and unstable at high SNR. When time sharing is allowed between decoding orders, it is shown using an approximate lower bound to the utility function that TX cooperation is also stable at high SNRs. Thus, this paper demonstrates that ideal zero cost TX cooperation over a MAC is stable and improves achievable rates for each individual user.
Simple Regret Optimization in Online Planning for Markov Decision Processes
Venue: arXiv cs.AI 2012
Year: 2012

We consider online planning in Markov decision processes (MDPs). In online planning, the agent focuses on its current state only, deliberates about the set of possible policies from that state onwards and, when interrupted, uses the outcome of that exploratory deliberation to choose what action to perform next. The performance of algorithms for online planning is assessed in terms of simple regret, which is the agent's expected performance loss when the chosen action, rather than an optimal one, is followed. To date, state-of-the-art algorithms for online planning in general MDPs are either best effort, or guarantee only polynomial-rate reduction of simple regret over time. Here we introduce a new Monte-Carlo tree search algorithm, BRUE, that guarantees exponential-rate reduction of simple regret and error probability. This algorithm is based on a simple yet non-standard state-space sampling scheme, MCTS2e, in which different parts of each sample are dedicated to different exploratory objectives. Our empirical evaluation shows that BRUE not only provides superior performance guarantees, but is also very effective in practice and favorably compares to state-of-the-art. We then extend BRUE with a variant of "learning by forgetting." The resulting set of algorithms, BRUE(alpha), generalizes BRUE, improves the exponential factor in the upper bound on its reduction rate, and exhibits even more attractive empirical performance.
A Dynamic Programming Algorithm for Inference in Recursive Probabilistic Programs
Venue: arXiv cs.AI 2012
Year: 2012

We describe a dynamic programming algorithm for computing the marginal distribution of discrete probabilistic programs. This algorithm takes a functional interpreter for an arbitrary probabilistic programming language and turns it into an efficient marginalizer. Because direct caching of sub-distributions is impossible in the presence of recursion, we build a graph of dependencies between sub-distributions. This factored sum-product network makes (potentially cyclic) dependencies between subproblems explicit, and corresponds to a system of equations for the marginal distribution. We solve these equations by fixed-point iteration in topological order. We illustrate this algorithm on examples used in teaching probabilistic models, computational cognitive science research, and game theory.
Alan Turing and the "Hard" and "Easy" Problem of Cognition: Doing and Feeling
Venue: arXiv cs.AI 2012
Year: 2012

The "easy" problem of cognitive science is explaining how and why we can do what we can do. The "hard" problem is explaining how and why we feel. Turing's methodology for cognitive science (the Turing Test) is based on doing: Design a model that can do anything a human can do, indistinguishably from a human, to a human, and you have explained cognition. Searle has shown that the successful model cannot be solely computational. Sensory-motor robotic capacities are necessary to ground some, at least, of the model's words, in what the robot can do with the things in the world that the words are about. But even grounding is not enough to guarantee that -- nor to explain how and why -- the model feels (if it does). That problem is much harder to solve (and perhaps insoluble).
Unsupervised adaptation of brain machine interface decoders
Venue: arXiv cs.LG 2012
Year: 2012

The performance of neural decoders can degrade over time due to nonstationarities in the relationship between neuronal activity and behavior. In this case, brain-machine interfaces (BMI) require adaptation of their decoders to maintain high performance across time. One way to achieve this is by use of periodical calibration phases, during which the BMI system (or an external human demonstrator) instructs the user to perform certain movements or behaviors. This approach has two disadvantages: (i) calibration phases interrupt the autonomous operation of the BMI and (ii) between two calibration phases the BMI performance might not be stable but continuously decrease. A better alternative would be that the BMI decoder is able to continuously adapt in an unsupervised manner during autonomous BMI operation, i.e. without knowing the movement intentions of the user. In the present article, we present an efficient method for such unsupervised training of BMI systems for continuous movement control. The proposed method utilizes a cost function derived from neuronal recordings, which guides a learning algorithm to evaluate the decoding parameters. We verify the performance of our adaptive method by simulating a BMI user with an optimal feedback control model and its interaction with our adaptive BMI decoder. The simulation results show that the cost function and the algorithm yield fast and precise trajectories towards targets at random orientations on a 2-dimensional computer screen. For initially unknown and non-stationary tuning parameters, our unsupervised method is still able to generate precise trajectories and to keep its performance stable in the long term. The algorithm can optionally work also with neuronal error signals instead or in conjunction with the proposed unsupervised adaptation.
Multiparty Cloud Computation
Venue: arXiv cs.CR 2012
Year: 2012

With the increasing popularity of the cloud, clients oursource their data to clouds in order to take advantage of unlimited virtualized storage space and the low management cost. Such trend prompts the privately oursourcing computation, called \emph{multiparty cloud computation} (\MCC): Given $k$ clients storing their data in the cloud, how can they perform the joint functionality by contributing their private data as inputs, and making use of cloud's powerful computation capability. Namely, the clients wish to oursource computation to the cloud together with their private data stored in the cloud, which naturally happens when the computation is involved with large datasets, e.g., to analyze malicious URLs. We note that the \MCC\ problem is different from widely considered concepts, e.g., secure multiparty computation and multiparty computation with server aid. To address this problem, we introduce the notion of \emph{homomorphic threshold proxy re-encryption} schemes, which are encryption schemes that enjoy three promising properties: proxy re-encryption -- transforming encrypted data of one user to encrypted data of target user, threshold decryption -- decrypting encrypted data by combining secret key shares obtained by a set of users, and homomorphic computation -- evaluating functions on the encrypted data. To demonstrate the feasibility of the proposed approach, we present an encryption scheme which allows anyone to compute arbitrary many additions and at most one multiplications.
Constraint-free Graphical Model with Fast Learning Algorithm
Venue: arXiv cs.LG 2012
Year: 2012

In this paper, we propose a simple, versatile model for learning the structure and parameters of multivariate distributions from a data set. Learning a Markov network from a given data set is not a simple problem, because Markov networks rigorously represent Markov properties, and this rigor imposes complex constraints on the design of the networks. Our proposed model removes these constraints, acquiring important aspects from the information geometry. The proposed parameter- and structure-learning algorithms are simple to execute as they are based solely on local computation at each node. Experiments demonstrate that our algorithms work appropriately.
Cryptographic Key Management for Smart Power Grids - Approaches and Issues
Venue: arXiv cs.CR 2012
Year: 2012

The smart power grid promises to improve efficiency and reliability of power delivery. This report introduces the logical components, associated technologies, security protocols, and network designs of the system. Undermining the potential benefits are security threats, and those threats related to cyber security are described in this report. Concentrating on the design of the smart meter and its communication links, this report describes the ZigBee technology and implementation, and the communication between the smart meter and the collector node, with emphasis on security attributes. It was observed that many of the secure features are based on keys that must be maintained; therefore, secure key management techniques become the basis to securing the entire grid. The descriptions of current key management techniques are delineated, highlighting their weaknesses. Finally some initial research directions are outlined.
A Study on Internet of Things based Applications
Venue: arXiv cs.NI 2012
Year: 2012

This paper gives a detail analysis of various applications based on Internet of Thing (IoT)s. This explains about how internet of things evolved from mobile computing and ubiquitous computing. It emphasises the fact that objects are connected over the internet rather than people. The properties of Internet of Things (IOT) are product information, electronic tag, standard expressed and uploading information. It utilises the Radio Frequency Identification (RFID) technology and wireless sensor networks (WSN). IOT applications are used in domains such as healthcare, supply chain management, defence and agriculture. Lastly the paper focuses on issues involved in IOT. Though it is a boon, IOT faces certain crucial issues like privacy and security.