OpenRaiser/Intern-Atlas huggingface dataset:
List Decoding of Lifted Gabidulin Codes via the Plücker Embedding
Venue: arXiv cs.IT 2013
Year: 2013

Codes in the Grassmannian have recently found an application in random network coding. All the codewords in such codes are subspaces of $\F_q^n$ with a given dimension. In this paper, we consider the problem of list decoding of a certain family of codes in the Grassmannian, called lifted Gabidulin codes. For this purpose we use the Plücker embedding of the Grassmannian. We describe a way of representing a subset of the Plücker coordinates of lifted Gabidulin codes as linear block codes. The union of the parity-check equations of these block codes and the equations which arise from the description of a ball around a subspace in the Plücker coordinates describe the list of codewords with distance less than a given parameter from the received word.
Variational MCMC
Venue: arXiv cs.LG 2013
Year: 2013

We propose a new class of learning algorithms that combines variational approximation and Markov chain Monte Carlo (MCMC) simulation. Naive algorithms that use the variational approximation as proposal distribution can perform poorly because this approximation tends to underestimate the true variance and other features of the data. We solve this problem by introducing more sophisticated MCMC algorithms. One of these algorithms is a mixture of two MCMC kernels: a random walk Metropolis kernel and a blockMetropolis-Hastings (MH) kernel with a variational approximation as proposaldistribution. The MH kernel allows one to locate regions of high probability efficiently. The Metropolis kernel allows us to explore the vicinity of these regions. This algorithm outperforms variationalapproximations because it yields slightly better estimates of the mean and considerably better estimates of higher moments, such as covariances. It also outperforms standard MCMC algorithms because it locates theregions of high probability quickly, thus speeding up convergence. We demonstrate this algorithm on the problem of Bayesian parameter estimation for logistic (sigmoid) belief networks.
Discovering Multiple Constraints that are Frequently Approximately Satisfied
Venue: arXiv cs.LG 2013
Year: 2013

Some high-dimensional data.sets can be modelled by assuming that there are many different linear constraints, each of which is Frequently Approximately Satisfied (FAS) by the data. The probability of a data vector under the model is then proportional to the product of the probabilities of its constraint violations. We describe three methods of learning products of constraints using a heavy-tailed probability distribution for the violations.
Expectation Propagation for approximate Bayesian inference
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents a new deterministic approximation technique in Bayesian networks. This method, "Expectation Propagation", unifies two previous techniques: assumed-density filtering, an extension of the Kalman filter, and loopy belief propagation, an extension of belief propagation in Bayesian networks. All three algorithms try to recover an approximate distribution which is close in KL divergence to the true distribution. Loopy belief propagation, because it propagates exact belief states, is useful for a limited class of belief networks, such as those which are purely discrete. Expectation Propagation approximates the belief states by only retaining certain expectations, such as mean and variance, and iterates until these expectations are consistent throughout the network. This makes it applicable to hybrid networks with discrete and continuous nodes. Expectation Propagation also extends belief propagation in the opposite direction - it can propagate richer belief states that incorporate correlations between nodes. Experiments with Gaussian mixture models show Expectation Propagation to be convincingly better than methods with similar computational cost: Laplace's method, variational Bayes, and Monte Carlo. Expectation Propagation also provides an efficient algorithm for training Bayes point machine classifiers.
A Case Study in Knowledge Discovery and Elicitation in an Intelligent Tutoring Application
Venue: arXiv cs.AI 2013
Year: 2013

Most successful Bayesian network (BN) applications to datehave been built through knowledge elicitation from experts.This is difficult and time consuming, which has lead to recentinterest in automated methods for learning BNs from data. We present a case study in the construction of a BN in anintelligent tutoring application, specifically decimal misconceptions. Wedescribe the BN construction using expert elicitation and then investigate how certainexisting automated knowledge discovery methods might support the BN knowledge engineering process.
Toward General Analysis of Recursive Probability Models
Venue: arXiv cs.AI 2013
Year: 2013

There is increasing interest within the research community in the design and use of recursive probability models. Although there still remains concern about computational complexity costs and the fact that computing exact solutions can be intractable for many nonrecursive models and impossible in the general case for recursive problems, several research groups are actively developing computational techniques for recursive stochastic languages. We have developed an extension to the traditional lambda-calculus as a framework for families of Turing complete stochastic languages. We have also developed a class of exact inference algorithms based on the traditional reductions of the lambda-calculus. We further propose that using the deBruijn notation (a lambda-calculus notation with nameless dummies) supports effective caching in such systems (caching being an essential component of efficient computation). Finally, our extension to the lambda-calculus offers a foundation and general theory for the construction of recursive stochastic modeling languages as well as promise for effective caching and efficient approximation algorithms for inference.
Maximum Likelihood Bounded Tree-Width Markov Networks
Venue: arXiv cs.LG 2013
Year: 2013

Chow and Liu (1968) studied the problem of learning a maximumlikelihood Markov tree. We generalize their work to more complexMarkov networks by considering the problem of learning a maximumlikelihood Markov network of bounded complexity. We discuss howtree-width is in many ways the appropriate measure of complexity andthus analyze the problem of learning a maximum likelihood Markovnetwork of bounded tree-width.Similar to the work of Chow and Liu, we are able to formalize thelearning problem as a combinatorial optimization problem on graphs. Weshow that learning a maximum likelihood Markov network of boundedtree-width is equivalent to finding a maximum weight hypertree. Thisequivalence gives rise to global, integer-programming based,approximation algorithms with provable performance guarantees, for thelearning problem. This contrasts with heuristic local-searchalgorithms which were previously suggested (e.g. by Malvestuto 1991).The equivalence also allows us to study the computational hardness ofthe learning problem. We show that learning a maximum likelihoodMarkov network of bounded tree-width is NP-hard, and discuss thehardness of approximation.
A Novel Analytical Method for Evolutionary Graph Theory Problems
Venue: arXiv cs.GT 2013
Year: 2013

Evolutionary graph theory studies the evolutionary dynamics of populations structured on graphs. A central problem is determining the probability that a small number of mutants overtake a population. Currently, Monte Carlo simulations are used for estimating such fixation probabilities on general directed graphs, since no good analytical methods exist. In this paper, we introduce a novel deterministic framework for computing fixation probabilities for strongly connected, directed, weighted evolutionary graphs under neutral drift. We show how this framework can also be used to calculate the expected number of mutants at a given time step (even if we relax the assumption that the graph is strongly connected), how it can extend to other related models (e.g. voter model), how our framework can provide non-trivial bounds for fixation probability in the case of an advantageous mutant, and how it can be used to find a non-trivial lower bound on the mean time to fixation. We provide various experimental results determining fixation probabilities and expected number of mutants on different graphs. Among these, we show that our method consistently outperforms Monte Carlo simulations in speed by several orders of magnitude. Finally we show how our approach can provide insight into synaptic competition in neurology.
Dynamic Transparent General Purpose Process Migration For Linux
Venue: arXiv cs.DC 2013
Year: 2013

Process migration refers to the act of transferring a process in the middle of its execution from one machine to another in a network. In this paper, we proposed a process migration framework for Linux OS. It is a multilayer architecture to confine every functionality independent section of the system in separate layer. This architecture is capable of supporting diverse applications due to generic user space interface and dynamic structure that can be modified according to demands.
Reduced-Rank Space-Time Interference Suppression with Joint Iterative Least Squares Algorithms for Spread Spectrum Systems
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents novel adaptive space-time reduced-rank interference suppression least squares algorithms based on joint iterative optimization of parameter vectors. The proposed space-time reduced-rank scheme consists of a joint iterative optimization of a projection matrix that performs dimensionality reduction and an adaptive reduced-rank parameter vector that yields the symbol estimates. The proposed techniques do not require singular value decomposition (SVD) and automatically find the best set of basis for reduced-rank processing. We present least squares (LS) expressions for the design of the projection matrix and the reduced-rank parameter vector and we conduct an analysis of the convergence properties of the LS algorithms. We then develop recursive least squares (RLS) adaptive algorithms for their computationally efficient estimation and an algorithm for automatically adjusting the rank of the proposed scheme. A convexity analysis of the LS algorithms is carried out along with the development of a proof of convergence for the proposed algorithms. Simulations for a space-time interference suppression application with a DS-CDMA system show that the proposed scheme outperforms in convergence and tracking the state-of-the-art reduced-rank schemes at a comparable complexity.
A Sliding Mode Multimodel Control for a Sensorless Photovoltaic System
Venue: arXiv cs.SY 2013
Year: 2013

In this work we will talk about a new control test using the sliding mode control with a nonlinear sliding mode observer, which are very solicited in tracking problems, for a sensorless photovoltaic panel. In this case, the panel system will has as a set point the sun position at every second during the day for a period of five years; then the tracker, using sliding mode multimodel controller and a sliding mode observer, will track these positions to make the sunrays orthogonal to the photovoltaic cell that produces more energy. After sunset, the tracker goes back to the initial position (which of sunrise). Experimental measurements show that this autonomic dual axis Sun Tracker increases the power production by over 40%.
Distributed Consensus Formation Through Unconstrained Gossiping
Venue: arXiv cs.SY 2013
Year: 2013

Gossip algorithms are widely used to solve the distributed consensus problem, but issues can arise when nodes receive multiple signals either at the same time or before they are able to finish processing their current work load. Specifically, a node may assume a new state that represents a linear combination of all received signals; even if such a state makes no sense in the problem domain. As a solution to this problem, we introduce the notion of conflict resolution for gossip algorithms and prove that their application leads to a valid consensus state when the underlying communication network possesses certain properties. We also introduce a methodology based on absorbing Markov chains for analyzing gossip algorithms that make use of these conflict resolution algorithms. This technique allows us to calculate both the probabilities of converging to a specific consensus state and the time that such convergence is expected to take. Finally, we make use of simulation to validate our methodology and explore the temporal behavior of gossip algorithms as the size of the network, the number of states per node, and the network density increase.
A parallel implementation of a derivative pricing model incorporating SABR calibration and probability lookup tables
Venue: arXiv cs.DC 2013
Year: 2013

We describe a high performance parallel implementation of a derivative pricing model, within which we introduce a new parallel method for the calibration of the industry standard SABR (stochastic-αβρ) stochastic volatility model using three strike inputs. SABR calibration involves a non-linear three dimensional minimisation and parallelisation is achieved by incorporating several assumptions unique to the SABR class of models. Our calibration method is based on principles of surface intersection, guarantees convergence to a unique solution and operates by iteratively refining a two dimensional grid with local mesh refinement. As part of our pricing model we additionally present a fast parallel iterative algorithm for the creation of dynamically sized cumulative probability lookup tables that are able to cap maximum estimated linear interpolation error. We optimise performance for probability distributions that exhibit clustering of linear interpolation error. We also make an empirical assessment of error propagation through our pricing model as a result of changes in accuracy parameters within the pricing model's multiple algorithmic steps. Algorithms are implemented on a GPU (graphics processing unit) using Nvidia's Fermi architecture. The pricing model targets the evaluation of spread options using copula methods, however the presented algorithms can be applied to a wider class of financial instruments.
Lazy abstractions for timed automata
Venue: arXiv cs.LO 2013
Year: 2013

We consider the reachability problem for timed automata. A standard solution to this problem involves computing a search tree whose nodes are abstractions of zones. For efficiency reasons, they are parametrized by the maximal lower and upper bounds (LU-bounds) occurring in the guards of the automaton. We propose an algorithm that is updating LU-bounds during exploration of the search tree. In order to keep them as small as possible, the bounds are refined only when they enable a transition that is impossible in the unabstracted system. So our algorithm can be seen as a kind of lazy CEGAR algorithm for timed automata. We show that on several standard benchmarks, the algorithm is capable of keeping very small LU-bounds, and in consequence reduce the search space substantially.
Approximating Metrics by Tree Metrics of Small Distance-Weighted Average Stretch
Venue: arXiv cs.DS 2013
Year: 2013

We study the problem of how well a tree metric is able to preserve the sum of pairwise distances of an arbitrary metric. This problem is closely related to low-stretch metric embeddings and is interesting by its own flavor from the line of research proposed in the literature. As the structure of a tree imposes great constraints on the pairwise distances, any embedding of a metric into a tree metric is known to have maximum pairwise stretch of $Ω(\log n)$. We show, however, from the perspective of average performance, there exist tree metrics which preserve the sum of pairwise distances of the given metric up to a small constant factor, for which we also show to be no worse than twice what we can possibly expect. The approach we use to tackle this problem is more direct compared to a previous result of [4], and also leads to a provably better guarantee. Second, when the given metric is extracted from a Euclidean point set of finite dimension $d$, we show that there exist spanning trees of the given point set such that the sum of pairwise distances is preserved up to a constant which depends only on $d$. Both of our proofs are constructive. The main ingredient in our result is a special point-set decomposition which relates two seemingly-unrelated quantities.
Multi-agent learning using Fictitious Play and Extended Kalman Filter
Venue: arXiv cs.MA 2013
Year: 2013

Decentralised optimisation tasks are important components of multi-agent systems. These tasks can be interpreted as n-player potential games: therefore game-theoretic learning algorithms can be used to solve decentralised optimisation tasks. Fictitious play is the canonical example of these algorithms. Nevertheless fictitious play implicitly assumes that players have stationary strategies. We present a novel variant of fictitious play where players predict their opponents' strategies using Extended Kalman filters and use their predictions to update their strategies. We show that in 2 by 2 games with at least one pure Nash equilibrium and in potential games where players have two available actions, the proposed algorithm converges to the pure Nash equilibrium. The performance of the proposed algorithm was empirically tested, in two strategic form games and an ad-hoc sensor network surveillance problem. The proposed algorithm performs better than the classic fictitious play algorithm in these games and therefore improves the performance of game-theoretical learning in decentralised optimisation.
Constraint Expressions and Workflow Satisfiability
Venue: arXiv cs.DS 2013
Year: 2013

A workflow specification defines a set of steps and the order in which those steps must be executed. Security requirements and business rules may impose constraints on which users are permitted to perform those steps. A workflow specification is said to be satisfiable if there exists an assignment of authorized users to workflow steps that satisfies all the constraints. An algorithm for determining whether such an assignment exists is important, both as a static analysis tool for workflow specifications, and for the construction of run-time reference monitors for workflow management systems. We develop new methods for determining workflow satisfiability based on the concept of constraint expressions, which were introduced recently by Khan and Fong. These methods are surprising versatile, enabling us to develop algorithms for, and determine the complexity of, a number of different problems related to workflow satisfiability.
Technical Report: Beaconless Geo-Routing Under The Spotlight: Practical Link Models and Application Scenarios
Venue: arXiv cs.NI 2013
Year: 2013

Analysis and simulation of beaconless geo-routing protocols have been traditionally conducted assuming equal communication ranges for the data and control packets. In reality, this is not true since the communication range is actually function of the packet length. Control packets are typically much shorter than data packets. As a consequence, a substantial discrepancy exists in practice between their respective communication ranges. In this paper, we devise a practical link model for computing the effective communication range. We further introduce two simple strategies for bridging the gap between the control and data packet communication ranges. Our primary objective in this paper is to construct a realistic analytical framework describing the end-to-end performance of beaconless geo-routing protocols. Two flagship protocols are selected in this paper for further investigation under the developed framework. For a better perspective, the two protocols are actually compared to a hypothetical limit case; one which offers optimal energy and latency performance. Finally, we present four different application scenarios. For each scenario, we highlight the geo-routing protocol which performs the best and discuss the reasons behind it.
Zero-Shot Learning Through Cross-Modal Transfer
Venue: arXiv cs.CV 2013
Year: 2013

This work introduces a model that can recognize objects in images even if no training data is available for the objects. The only necessary knowledge about the unseen categories comes from unsupervised large text corpora. In our zero-shot framework distributional information in language can be seen as spanning a semantic basis for understanding what objects look like. Most previous zero-shot learning models can only differentiate between unseen classes. In contrast, our model can both obtain state of the art performance on classes that have thousands of training images and obtain reasonable performance on unseen classes. This is achieved by first using outlier detection in the semantic space and then two separate recognition models. Furthermore, our model does not require any manually defined semantic features for either words or images.
Learning Output Kernels for Multi-Task Problems
Venue: arXiv cs.LG 2013
Year: 2013

Simultaneously solving multiple related learning tasks is beneficial under a variety of circumstances, but the prior knowledge necessary to correctly model task relationships is rarely available in practice. In this paper, we develop a novel kernel-based multi-task learning technique that automatically reveals structural inter-task relationships. Building over the framework of output kernel learning (OKL), we introduce a method that jointly learns multiple functions and a low-rank multi-task kernel by solving a non-convex regularization problem. Optimization is carried out via a block coordinate descent strategy, where each subproblem is solved using suitable conjugate gradient (CG) type iterative methods for linear operator equations. The effectiveness of the proposed approach is demonstrated on pharmacological and collaborative filtering data.
Stochastic Logic Programs: Sampling, Inference and Applications
Venue: arXiv cs.AI 2013
Year: 2013

Algorithms for exact and approximate inference in stochastic logic programs (SLPs) are presented, based respectively, on variable elimination and importance sampling. We then show how SLPs can be used to represent prior distributions for machine learning, using (i) logic programs and (ii) Bayes net structures as examples. Drawing on existing work in statistics, we apply the Metropolis-Hasting algorithm to construct a Markov chain which samples from the posterior distribution. A Prolog implementation for this is described. We also discuss the possibility of constructing explicit representations of the posterior.
A Differential Approach to Inference in Bayesian Networks
Venue: arXiv cs.AI 2013
Year: 2013

We present a new approach for inference in Bayesian networks, which is mainly based on partial differentiation. According to this approach, one compiles a Bayesian network into a multivariate polynomial and then computes the partial derivatives of this polynomial with respect to each variable. We show that once such derivatives are made available, one can compute in constant-time answers to a large class of probabilistic queries, which are central to classical inference, parameter estimation, model validation and sensitivity analysis. We present a number of complexity results relating to the compilation of such polynomials and to the computation of their partial derivatives. We argue that the combined simplicity, comprehensiveness and computational complexity of the presented framework is unique among existing frameworks for inference in Bayesian networks.