OpenRaiser/Intern-Atlas huggingface dataset:
Markov Chain Monte Carlo using Tree-Based Priors on Model Structure
Venue: arXiv cs.AI 2013
Year: 2013

We present a general framework for defining priors on model structure and sampling from the posterior using the Metropolis-Hastings algorithm. The key idea is that structure priors are defined via a probability tree and that the proposal mechanism for the Metropolis-Hastings algorithm operates by traversing this tree, thereby defining a cheaply computable acceptance probability. We have applied this approach to Bayesian net structure learning using a number of priors and tree traversal strategies. Our results show that these must be chosen appropriately for this approach to be successful.
Multivariate Information Bottleneck
Venue: arXiv cs.LG 2013
Year: 2013

The Information bottleneck method is an unsupervised non-parametric data organization technique. Given a joint distribution P(A,B), this method constructs a new variable T that extracts partitions, or clusters, over the values of A that are informative about B. The information bottleneck has already been applied to document classification, gene expression, neural code, and spectral analysis. In this paper, we introduce a general principled framework for multivariate extensions of the information bottleneck method. This allows us to consider multiple systems of data partitions that are inter-related. Our approach utilizes Bayesian networks for specifying the systems of clusters and what information each captures. We show that this construction provides insight about bottleneck variations and enables us to characterize solutions of these variations. We also present a general framework for iterative algorithms for constructing solutions, and apply it to several examples.
Classifier Learning with Supervised Marginal Likelihood
Venue: arXiv cs.LG 2013
Year: 2013

It has been argued that in supervised classification tasks, in practice it may be more sensible to perform model selection with respect to some more focused model selection score, like the supervised (conditional) marginal likelihood, than with respect to the standard marginal likelihood criterion. However, for most Bayesian network models, computing the supervised marginal likelihood score takes exponential time with respect to the amount of observed data. In this paper, we consider diagnostic Bayesian network classifiers where the significant model parameters represent conditional distributions for the class variable, given the values of the predictor variables, in which case the supervised marginal likelihood can be computed in linear time with respect to the data. As the number of model parameters grows in this case exponentially with respect to the number of predictors, we focus on simple diagnostic models where the number of relevant predictors is small, and suggest two approaches for applying this type of models in classification. The first approach is based on mixtures of simple diagnostic models, while in the second approach we apply the small predictor sets of the simple diagnostic models for augmenting the Naive Bayes classifier.
Iterative Markov Chain Monte Carlo Computation of Reference Priors and Minimax Risk
Venue: arXiv cs.LG 2013
Year: 2013

We present an iterative Markov chainMonte Carlo algorithm for computingreference priors and minimax risk forgeneral parametric families. Ourapproach uses MCMC techniques based onthe Blahut-Arimoto algorithm forcomputing channel capacity ininformation theory. We give astatistical analysis of the algorithm,bounding the number of samples requiredfor the stochastic algorithm to closelyapproximate the deterministic algorithmin each iteration. Simulations arepresented for several examples fromexponential families. Although we focuson applications to reference priors andminimax risk, the methods and analysiswe develop are applicable to a muchbroader class of optimization problemsand iterative algorithms.
Hypothesis Management in Situation-Specific Network Construction
Venue: arXiv cs.AI 2013
Year: 2013

This paper considers the problem of knowledge-based model construction in the presence of uncertainty about the association of domain entities to random variables. Multi-entity Bayesian networks (MEBNs) are defined as a representation for knowledge in domains characterized by uncertainty in the number of relevant entities, their interrelationships, and their association with observables. An MEBN implicitly specifies a probability distribution in terms of a hierarchically structured collection of Bayesian network fragments that together encode a joint probability distribution over arbitrarily many interrelated hypotheses. Although a finite query-complete model can always be constructed, association uncertainty typically makes exact model construction and evaluation intractable. The objective of hypothesis management is to balance tractability against accuracy. We describe an application to the problem of using intelligence reports to infer the organization and activities of groups of military vehicles. Our approach is compared to related work in the tracking and fusion literature.
Solving Influence Diagrams using HUGIN, Shafer-Shenoy and Lazy Propagation
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we compare three different architectures for the evaluation of influence diagrams: HUGIN, Shafer-Shenoy, and Lazy Evaluation architecture. The computational complexity of the architectures are compared on the LImited Memory Influence Diagram (LIMID): a diagram where only the requiste information for the computation of the optimal policies are depicted. Because the requsite information is explicitly represented in the LIMID the evaluation can take advantage of it, and significant savings in computational can be obtained. In this paper we show how the obtained savings is considerably increased when the computations performed on the LIMID is according to the Lazy Evaluation scheme.
Lattice Particle Filters
Venue: arXiv cs.AI 2013
Year: 2013

A standard approach to approximate inference in state-space models isto apply a particle filter, e.g., the Condensation Algorithm.However, the performance of particle filters often varies significantlydue to their stochastic nature.We present a class of algorithms, called lattice particle filters, thatcircumvent this difficulty by placing the particles deterministicallyaccording to a Quasi-Monte Carlo integration rule.We describe a practical realization of this idea, discuss itstheoretical properties, and its efficiency.Experimental results with a synthetic 2D tracking problem show that thelattice particle filter is equivalent to a conventional particle filterthat has between 10 and 60% more particles, depending ontheir "sparsity" in the state-space.We also present results on inferring 3D human motion frommoving light displays.
Direct and Indirect Effects
Venue: arXiv cs.AI 2013
Year: 2013

The direct effect of one eventon another can be defined and measured byholding constant all intermediate variables between the two.Indirect effects present conceptual andpractical difficulties (in nonlinear models), because they cannot be isolated by holding certain variablesconstant. This paper shows a way of defining any path-specific effectthat does not invoke blocking the remainingpaths.This permits the assessment of a more naturaltype of direct and indirect effects, one thatis applicable in both linear and nonlinear models. The paper establishesconditions under which such assessments can be estimated consistentlyfrom experimental and nonexperimental data,and thus extends path-analytic techniques tononlinear and nonparametric models.
Vector-space Analysis of Belief-state Approximation for POMDPs
Venue: arXiv cs.AI 2013
Year: 2013

We propose a new approach to value-directed belief state approximation for POMDPs. The value-directed model allows one to choose approximation methods for belief state monitoring that have a small impact on decision quality. Using a vector space analysis of the problem, we devise two new search procedures for selecting an approximation scheme that have much better computational properties than existing methods. Though these provide looser error bounds, we show empirically that they have a similar impact on decision quality in practice, and run up to two orders of magnitude more quickly.
Symmetric Collaborative Filtering Using the Noisy Sensor Model
Venue: arXiv cs.IR 2013
Year: 2013

Collaborative filtering is the process of making recommendations regarding the potential preference of a user, for example shopping on the Internet, based on the preference ratings of the user and a number of other users for various items. This paper considers collaborative filtering based on explicitmulti-valued ratings. To evaluate the algorithms, weconsider only {em pure} collaborative filtering, using ratings exclusively, and no other information about the people or items.Our approach is to predict a user's preferences regarding a particularitem by using other people who rated that item and other items ratedby the user as noisy sensors. The noisy sensor model uses Bayes' theorem to compute the probability distribution for the user'srating of a new item. We give two variant models: in one, we learn a{em classical normal linear regression} model of how users rate items; in another,we assume different users rate items the same, but the accuracy of thesensors needs to be learned. We compare these variant models withstate-of-the-art techniques and show how they are significantly better,whether a user has rated only two items or many. We reportempirical results using the EachMovie database footnote{http://research.compaq.com/SRC/eachmovie/} of movie ratings. Wealso show that by considering items similarity along with theusers similarity, the accuracy of the prediction increases.
The Optimal Reward Baseline for Gradient-Based Reinforcement Learning
Venue: arXiv cs.LG 2013
Year: 2013

There exist a number of reinforcement learning algorithms which learnby climbing the gradient of expected reward. Their long-runconvergence has been proved, even in partially observableenvironments with non-deterministic actions, and without the need fora system model. However, the variance of the gradient estimator hasbeen found to be a significant practical problem. Recent approacheshave discounted future rewards, introducing a bias-variance trade-offinto the gradient estimate. We incorporate a reward baseline into thelearning system, and show that it affects variance without introducingfurther bias. In particular, as we approach the zero-bias,high-variance parameterization, the optimal (or variance minimizing)constant reward baseline is equal to the long-term average expectedreward. Modified policy-gradient algorithms are presented, and anumber of experiments demonstrate their improvement over previous work.
Belief Optimization for Binary Networks: A Stable Alternative to Loopy Belief Propagation
Venue: arXiv cs.AI 2013
Year: 2013

We present a novel inference algorithm for arbitrary, binary, undirected graphs. Unlike loopy belief propagation, which iterates fixed point equations, we directly descend on the Bethe free energy. The algorithm consists of two phases, first we update the pairwise probabilities, given the marginal probabilities at each unit,using an analytic expression. Next, we update the marginal probabilities, given the pairwise probabilities by following the negative gradient of the Bethe free energy. Both steps are guaranteed to decrease the Bethe free energy, and since it is lower bounded, the algorithm is guaranteed to converge to a local minimum. We also show that the Bethe free energy is equal to the TAP free energy up to second order in the weights. In experiments we confirm that when belief propagation converges it usually finds identical solutions as our belief optimization method. However, in cases where belief propagation fails to converge, belief optimization continues to converge to reasonable beliefs. The stable nature of belief optimization makes it ideally suited for learning graphical models from data.
Application of Hopfield Network to Saccades
Venue: arXiv cs.CV 2013
Year: 2013

Human eye movement mechanisms (saccades) are very useful for scene analysis, including object representation and pattern recognition. In this letter, a Hopfield neural network to emulate saccades is proposed. The network uses an energy function that includes location and identification tasks. Computer simulation shows that the network performs those tasks cooperatively. The result suggests that the network is applicable to shift-invariant pattern recognition.
Event-B/SLP
Venue: arXiv cs.SE 2013
Year: 2013

We show how the event-based notation offered by Event-B may be augmented by algorithmic modelling constructs without disrupting the refinement-based development process.
Query-driven Frequent Co-occurring Term Extraction over Relational Data using MapReduce
Venue: arXiv cs.DB 2013
Year: 2013

In this paper we study how to efficiently compute \textit{frequent co-occurring terms} (FCT) in the results of a keyword query in parallel using the popular MapReduce framework. Taking as input a keyword query q and an integer k, an FCT query reports the k terms that are not in q, but appear most frequently in the results of the keyword query q over multiple joined relations. The returned terms of FCT search can be used to do query expansion and query refinement for traditional keyword search. Different from the method of FCT search in a single platform, our proposed approach can efficiently answer a FCT query using the MapReduce Paradigm without pre-computing the results of the original keyword query, which is run in parallel platform. In this work, we can output the final FCT search results by two MapReduce jobs: the first is to extract the statistical information of the data; and the second is to calculate the total frequency of each term based on the output of the first job. At the two MapReduce jobs, we would guarantee the load balance of mappers and the computational balance of reducers as much as possible. Analytical and experimental evaluations demonstrate the efficiency and scalability of our proposed approach using TPC-H benchmark datasets with different sizes.
Modeling complex systems with adaptive networks
Venue: arXiv cs.SI 2013
Year: 2013

Adaptive networks are a novel class of dynamical networks whose topologies and states coevolve. Many real-world complex systems can be modeled as adaptive networks, including social networks, transportation networks, neural networks and biological networks. In this paper, we introduce fundamental concepts and unique properties of adaptive networks through a brief, non-comprehensive review of recent literature on mathematical/computational modeling and analysis of such networks. We also report our recent work on several applications of computational adaptive network modeling and analysis to real-world problems, including temporal development of search and rescue operational networks, automated rule discovery from empirical network evolution data, and cultural integration in corporate merger.
Active Self-Assembly of Algorithmic Shapes and Patterns in Polylogarithmic Time
Venue: arXiv cs.DS 2013
Year: 2013

We describe a computational model for studying the complexity of self-assembled structures with active molecular components. Our model captures notions of growth and movement ubiquitous in biological systems. The model is inspired by biology's fantastic ability to assemble biomolecules that form systems with complicated structure and dynamics, from molecular motors that walk on rigid tracks and proteins that dynamically alter the structure of the cell during mitosis, to embryonic development where large-scale complicated organisms efficiently grow from a single cell. Using this active self-assembly model, we show how to efficiently self-assemble shapes and patterns from simple monomers. For example, we show how to grow a line of monomers in time and number of monomer states that is merely logarithmic in the length of the line. Our main results show how to grow arbitrary connected two-dimensional geometric shapes and patterns in expected time that is polylogarithmic in the size of the shape, plus roughly the time required to run a Turing machine deciding whether or not a given pixel is in the shape. We do this while keeping the number of monomer types logarithmic in shape size, plus those monomers required by the Kolmogorov complexity of the shape or pattern. This work thus highlights the efficiency advantages of active self-assembly over passive self-assembly and motivates experimental effort to construct general-purpose active molecular self-assembly systems.
Upper-Bounding the Capacity of Relay Communications - Part I
Venue: arXiv cs.IT 2013
Year: 2013

This paper focuses on the capacity of point-to-point relay communications wherein the transmitter is assisted by an intermediate relay. We detail the mathematical model of cutset and amplify and forward (AF) relaying strategy. We present the upper bound capacity of each relaying strategy from information theory viewpoint and also in networks with Gaussian channels. We exemplify various outer region capacities of the addressed strategies with two different case studies. The results exhibit that in low signal-to-noise ratio (SNR) environments the cutset performance is better than amplify and forward strategy.
Computational Intelligence for Deepwater Reservoir Depositional Environments Interpretation
Venue: arXiv cs.NE 2013
Year: 2013

Predicting oil recovery efficiency of a deepwater reservoir is a challenging task. One approach to characterize a deepwater reservoir and to predict its producibility is by analyzing its depositional information. This research proposes a deposition-based stratigraphic interpretation framework for deepwater reservoir characterization. In this framework, one critical task is the identification and labeling of the stratigraphic components in the reservoir, according to their depositional environments. This interpretation process is labor intensive and can produce different results depending on the stratigrapher who performs the analysis. To relieve stratigrapher's workload and to produce more consistent results, we have developed a novel methodology to automate this process using various computational intelligence techniques. Using a well log data set, we demonstrate that the developed methodology and the designed workflow can produce finite state transducer models that interpret deepwater reservoir depositional environments adequately.
Approachability, Regret and Calibration; implications and equivalences
Venue: arXiv cs.GT 2013
Year: 2013

Blackwell approachability, regret minimization and calibration are three criteria evaluating a strategy (or an algorithm) in different sequential decision problems, or repeated games between a player and Nature. Although they have at first sight nothing in common, links between have been discovered: both consistent and calibrated strategies can be constructed by following, in some auxiliary game, an approachability strategy. We gathered famous or recent results and provide new ones in order to develop and generalize Blackwell's elegant theory. The final goal is to show how it can be used as a basic powerful tool to exhibit a new class of intuitive algorithms, based on simple geometric properties. In order to be complete, we also prove that approachability can be seen as a byproduct of the very existence of consistent or calibrated strategies.
A High-Order Sliding Mode Observer: Torpedo Guidance Application
Venue: arXiv cs.SY 2013
Year: 2013

The guidance of a torpedo represents a hard task because of the smooth nonlinear aspect of this system and because of the extreme external disturbances. The torpedo guidance reposes on the speed and the position control. In fact, the control approach which is very solicited for the electromechanical systems is the sliding mode control (SMC) which proved its effectiveness through the different studies. The SMC is robust versus disturbances and model uncertainties; however, a sharp discontinuous control is needed which induces the chattering phenomenon. The angular velocity measurement is a hard task because of the high level of disturbances. In this way, the sliding mode observer could be a solution for the velocity estimation instead of a sensor. This article deals with torpedo guidance by SMC to reach the desired path in a short time and with high precision quality. Simulation results show that this control strategy and observer can attain excellent control performances with no chattering problem.
A Characterization of Approximation Resistance for Even $k$-Partite CSPs
Venue: arXiv cs.CC 2013
Year: 2013

A constraint satisfaction problem (CSP) is said to be \emph{approximation resistant} if it is hard to approximate better than the trivial algorithm which picks a uniformly random assignment. Assuming the Unique Games Conjecture, we give a characterization of approximation resistance for $k$-partite CSPs defined by an even predicate.
A New Proof of P-time Completeness of Linear Lambda Calculus
Venue: arXiv cs.LO 2013
Year: 2013

We give a new proof of P-time completeness of Linear Lambda Calculus, which was originally given by H. Mairson in 2003. Our proof uses an essentially different Boolean type from the type Mairson used. Moreover the correctness of our proof can be machined-checked using an implementation of Standard ML.
SpeedRead: A Fast Named Entity Recognition Pipeline
Venue: arXiv cs.CL 2013
Year: 2013

Online content analysis employs algorithmic methods to identify entities in unstructured text. Both machine learning and knowledge-base approaches lie at the foundation of contemporary named entities extraction systems. However, the progress in deploying these approaches on web-scale has been been hampered by the computational cost of NLP over massive text corpora. We present SpeedRead (SR), a named entity recognition pipeline that runs at least 10 times faster than Stanford NLP pipeline. This pipeline consists of a high performance Penn Treebank- compliant tokenizer, close to state-of-art part-of-speech (POS) tagger and knowledge-based named entity recognizer.
An Outline of Security in Wireless Sensor Networks: Threats, Countermeasures and Implementations
Venue: arXiv cs.NI 2013
Year: 2013

With the expansion of wireless sensor networks (WSNs), the need for securing the data flow through these networks is increasing. These sensor networks allow for easy-to-apply and flexible installations which have enabled them to be used for numerous applications. Due to these properties, they face distinct information security threats. Security of the data flowing through across networks provides the researchers with an interesting and intriguing potential for research. Design of these networks to ensure the protection of data faces the constraints of limited power and processing resources. We provide the basics of wireless sensor network security to help the researchers and engineers in better understanding of this applications field. In this chapter, we will provide the basics of information security with special emphasis on WSNs. The chapter will also give an overview of the information security requirements in these networks. Threats to the security of data in WSNs and some of their counter measures are also presented.