OpenRaiser/Intern-Atlas huggingface dataset:
Combinatorial Optimization in Pattern Assembly
Venue: arXiv cs.CC 2013
Year: 2013

Pattern self-assembly tile set synthesis (PATS) is a combinatorial optimization problem which aim at minimizing a rectilinear tile assembly system (RTAS) that uniquely self-assembles a given rectangular pattern, and is known to be NP-hard. PATS gets practically meaningful when it is parameterized by a constant c such that any given pattern is guaranteed to contain at most c colors (c-PATS). We first investigate simple patterns and properties of minimum RTASs for them. Then based on them, we design a 59-colored pattern to which 3SAT is reduced, and prove that 59-PATS is NP-hard.
The Complexity of Decentralized Control of Markov Decision Processes
Venue: arXiv cs.AI 2013
Year: 2013

Planning for distributed agents with partial state information is considered from a decision- theoretic perspective. We describe generalizations of both the MDP and POMDP models that allow for decentralized control. For even a small number of agents, the finite-horizon problems corresponding to both of our models are complete for nondeterministic exponential time. These complexity results illustrate a fundamental difference between centralized and decentralized control of Markov processes. In contrast to the MDP and POMDP problems, the problems we consider provably do not admit polynomial-time algorithms and most likely require doubly exponential time to solve in the worst case. We have thus provided mathematical evidence corresponding to the intuition that decentralized planning problems cannot easily be reduced to centralized problems and solved exactly using established techniques.
Mix-nets: Factored Mixtures of Gaussians in Bayesian Networks With Mixed Continuous And Discrete Variables
Venue: arXiv cs.LG 2013
Year: 2013

Recently developed techniques have made it possible to quickly learn accurate probability density functions from data in low-dimensional continuous space. In particular, mixtures of Gaussians can be fitted to data very quickly using an accelerated EM algorithm that employs multiresolution kd-trees (Moore, 1999). In this paper, we propose a kind of Bayesian networks in which low-dimensional mixtures of Gaussians over different subsets of the domain's variables are combined into a coherent joint probability model over the entire domain. The network is also capable of modeling complex dependencies between discrete variables and continuous variables without requiring discretization of the continuous variables. We present efficient heuristic algorithms for automatically learning these networks from data, and perform comparative experiments illustrated how well these networks model real scientific data and synthetic data. We also briefly discuss some possible improvements to the networks, as well as possible applications.
Learning Graphical Models of Images, Videos and Their Spatial Transformations
Venue: arXiv cs.CV 2013
Year: 2013

Mixtures of Gaussians, factor analyzers (probabilistic PCA) and hidden Markov models are staples of static and dynamic data modeling and image and video modeling in particular. We show how topographic transformations in the input, such as translation and shearing in images, can be accounted for in these models by including a discrete transformation variable. The resulting models perform clustering, dimensionality reduction and time-series analysis in a way that is invariant to transformations in the input. Using the EM algorithm, these transformation-invariant models can be fit to static data and time series. We give results on filtering microscopy images, face and facial pose clustering, handwritten digit modeling and recognition, video clustering, object tracking, and removal of distractions from video sequences.
Being Bayesian about Network Structure
Venue: arXiv cs.LG 2013
Year: 2013

In many domains, we are interested in analyzing the structure of the underlying distribution, e.g., whether one variable is a direct parent of the other. Bayesian model-selection attempts to find the MAP model and use its structure to answer these questions. However, when the amount of available data is modest, there might be many models that have non-negligible posterior. Thus, we want compute the Bayesian posterior of a feature, i.e., the total posterior probability of all models that contain it. In this paper, we propose a new approach for this task. We first show how to efficiently compute a sum over the exponential number of networks that are consistent with a fixed ordering over network variables. This allows us to compute, for a given ordering, both the marginal probability of the data and the posterior of a feature. We then use this result as the basis for an algorithm that approximates the Bayesian posterior of a feature. Our approach uses a Markov Chain Monte Carlo (MCMC) method, but over orderings rather than over network structures. The space of orderings is much smaller and more regular than the space of structures, and has a smoother posterior `landscape'. We present empirical results on synthetic and real-life datasets that compare our approach to full model averaging (when possible), to MCMC over network structures, and to a non-Bayesian bootstrap approach.
Gaussian Process Networks
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we address the problem of learning the structure of a Bayesian network in domains with continuous variables. This task requires a procedure for comparing different candidate structures. In the Bayesian framework, this is done by evaluating the {em marginal likelihood/} of the data given a candidate structure. This term can be computed in closed-form for standard parametric families (e.g., Gaussians), and can be approximated, at some computational cost, for some semi-parametric families (e.g., mixtures of Gaussians). We present a new family of continuous variable probabilistic networks that are based on {em Gaussian Process/} priors. These priors are semi-parametric in nature and can learn almost arbitrary noisy functional relations. Using these priors, we can directly compute marginal likelihoods for structure learning. The resulting method can discover a wide range of functional dependencies in multivariate data. We develop the Bayesian score of Gaussian Process Networks and describe how to learn them from data. We present empirical results on artificial data as well as on real-life domains with non-linear dependencies.
Tractable Bayesian Learning of Tree Belief Networks
Venue: arXiv cs.LG 2013
Year: 2013

In this paper we present decomposable priors, a family of priors over structure and parameters of tree belief nets for which Bayesian learning with complete observations is tractable, in the sense that the posterior is also decomposable and can be completely determined analytically in polynomial time. This follows from two main results: First, we show that factored distributions over spanning trees in a graph can be integrated in closed form. Second, we examine priors over tree parameters and show that a set of assumptions similar to (Heckerman and al. 1995) constrain the tree parameter priors to be a compactly parameterized product of Dirichlet distributions. Beside allowing for exact Bayesian learning, these results permit us to formulate a new class of tractable latent variable models in which the likelihood of a data point is computed through an ensemble average over tree structures.
Evaluating Influence Diagrams using LIMIDs
Venue: arXiv cs.AI 2013
Year: 2013

We present a new approach to the solution of decision problems formulated as influence diagrams. The approach converts the influence diagram into a simpler structure, the LImited Memory Influence Diagram (LIMID), where only the requisite information for the computation of optimal policies is depicted. Because the requisite information is explicitly represented in the diagram, the evaluation procedure can take advantage of it. In this paper we show how to convert an influence diagram to a LIMID and describe the procedure for finding an optimal strategy. Our approach can yield significant savings of memory and computational time when compared to traditional methods.
Adaptive Importance Sampling for Estimation in Structured Domains
Venue: arXiv cs.AI 2013
Year: 2013

Sampling is an important tool for estimating large, complex sums and integrals over high dimensional spaces. For instance, important sampling has been used as an alternative to exact methods for inference in belief networks. Ideally, we want to have a sampling distribution that provides optimal-variance estimators. In this paper, we present methods that improve the sampling distribution by systematically adapting it as we obtain information from the samples. We present a stochastic-gradient-descent method for sequentially updating the sampling distribution based on the direct minization of the variance. We also present other stochastic-gradient-descent methods based on the minimizationof typical notions of distance between the current sampling distribution and approximations of the target, optimal distribution. We finally validate and compare the different methods empirically by applying them to the problem of action evaluation in influence diagrams.
Value-Directed Belief State Approximation for POMDPs
Venue: arXiv cs.AI 2013
Year: 2013

We consider the problem belief-state monitoring for the purposes of implementing a policy for a partially-observable Markov decision process (POMDP), specifically how one might approximate the belief state. Other schemes for belief-state approximation (e.g., based on minimixing a measures such as KL-diveregence between the true and estimated state) are not necessarily appropriate for POMDPs. Instead we propose a framework for analyzing value-directed approximation schemes, where approximation quality is determined by the expected error in utility rather than by the error in the belief state itself. We propose heuristic methods for finding good projection schemes for belief state estimation - exhibiting anytime characteristics - given a POMDP value fucntion. We also describe several algorithms for constructing bounds on the error in decision quality (expected utility) associated with acting in accordance with a given belief state approximation.
Pivotal Pruning of Trade-offs in QPNs
Venue: arXiv cs.AI 2013
Year: 2013

Qualitative probabilistic networks have been designed for probabilistic reasoning in a qualitative way. Due to their coarse level of representation detail, qualitative probabilistic networks do not provide for resolving trade-offs and typically yield ambiguous results upon inference. We present an algorithm for computing more insightful results for unresolved trade-offs. The algorithm builds upon the idea of using pivots to zoom in on the trade-offs and identifying the information that would serve to resolve them.
Dynamic Trees: A Structured Variational Method Giving Efficient Propagation Rules
Venue: arXiv cs.LG 2013
Year: 2013

Dynamic trees are mixtures of tree structured belief networks. They solve some of the problems of fixed tree networks at the cost of making exact inference intractable. For this reason approximate methods such as sampling or mean field approaches have been used. However, mean field approximations assume a factorized distribution over node states. Such a distribution seems unlickely in the posterior, as nodes are highly correlated in the prior. Here a structured variational approach is used, where the posterior distribution over the non-evidential nodes is itself approximated by a dynamic tree. It turns out that this form can be used tractably and efficiently. The result is a set of update rules which can propagate information through the network to obtain both a full variational approximation, and the relevant marginals. The progagtion rules are more efficient than the mean field approach and give noticeable quantitative and qualitative improvement in the inference. The marginals calculated give better approximations to the posterior than loopy propagation on a small toy problem.
Model Criticism of Bayesian Networks with Latent Variables
Venue: arXiv cs.AI 2013
Year: 2013

The application of Bayesian networks (BNs) to cognitive assessment and intelligent tutoring systems poses new challenges for model construction. When cognitive task analyses suggest constructing a BN with several latent variables, empirical model criticism of the latent structure becomes both critical and complex. This paper introduces a methodology for criticizing models both globally (a BN in its entirety) and locally (observable nodes), and explores its value in identifying several kinds of misfit: node errors, edge errors, state errors, and prior probability errors in the latent structure. The results suggest the indices have potential for detecting model misfit and assisting in locating problematic components of the model.
Stable Routing for achieving Quality of Service in wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

Networking in Wireless Sensor networks is a challenging task due to the lack of resources in the network as well as the frequent changes in network topology. Although lots of research has been done on supporting QoS in the Internet and other networks, but they are not suitable for wireless sensor networks and still QoS support for such networks remains an open problem. In this paper, a new scheme has been proposed for achieving QoS in terms of packet delivery, multiple connections, better power management and stable routes in case of failure. It offers quick adaptation to distributed processing, dynamic linking, low processing overhead and loop freedom at all times. The proposed scheme has been incorporated using QDPRA protocol and by extensive simulation the performance has been studied, and it is clearly shown that the proposed scheme performs very well for different network scenarios.
Evolutionary Algorithms and Dynamic Programming
Venue: arXiv cs.NE 2013
Year: 2013

Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation which enables them to construct solutions in a dynamic programming fashion. We take a general approach and relate the construction of such algorithms to the development of algorithms using dynamic programming techniques. Thereby, we give general guidelines on how to develop evolutionary algorithms that have the additional ability of carrying out dynamic programming steps. Finally, we show that for a wide class of the so-called DP-benevolent problems (which are known to admit FPTAS) there exists a fully polynomial-time randomized approximation scheme based on an evolutionary algorithm.
Affinity Weighted Embedding
Venue: arXiv cs.IR 2013
Year: 2013

Supervised (linear) embedding models like Wsabie and PSI have proven successful at ranking, recommendation and annotation tasks. However, despite being scalable to large datasets they do not take full advantage of the extra data due to their linear nature, and typically underfit. We propose a new class of models which aim to provide improved performance while retaining many of the benefits of the existing class of embedding models. Our new approach works by iteratively learning a linear embedding model where the next iteration's features and labels are reweighted as a function of the previous iteration. We describe several variants of the family, and give some initial results.
A new entropy power inequality for integer-valued random variables
Venue: arXiv cs.IT 2013
Year: 2013

The entropy power inequality (EPI) provides lower bounds on the differential entropy of the sum of two independent real-valued random variables in terms of the individual entropies. Versions of the EPI for discrete random variables have been obtained for special families of distributions with the differential entropy replaced by the discrete entropy, but no universal inequality is known (beyond trivial ones). More recently, the sumset theory for the entropy function provides a sharp inequality $H(X+X')-H(X)\geq 1/2 -o(1)$ when $X,X'$ are i.i.d. with high entropy. This paper provides the inequality $H(X+X')-H(X) \geq g(H(X))$, where $X,X'$ are arbitrary i.i.d. integer-valued random variables and where $g$ is a universal strictly positive function on $\mR_+$ satisfying $g(0)=0$. Extensions to non identically distributed random variables and to conditional entropies are also obtained.
View-based propagation of decomposable constraints
Venue: arXiv cs.AI 2013
Year: 2013

Constraints that may be obtained by composition from simpler constraints are present, in some way or another, in almost every constraint program. The decomposition of such constraints is a standard technique for obtaining an adequate propagation algorithm from a combination of propagators designed for simpler constraints. The decomposition approach is appealing in several ways. Firstly because creating a specific propagator for every constraint is clearly infeasible since the number of constraints is infinite. Secondly, because designing a propagation algorithm for complex constraints can be very challenging. Finally, reusing existing propagators allows to reduce the size of code to be developed and maintained. Traditionally, constraint solvers automatically decompose constraints into simpler ones using additional auxiliary variables and propagators, or expect the users to perform such decomposition themselves, eventually leading to the same propagation model. In this paper we explore views, an alternative way to create efficient propagators for such constraints in a modular, simple and correct way, which avoids the introduction of auxiliary variables and propagators.
English Sentence Recognition using Artificial Neural Network through Mouse-based Gestures
Venue: arXiv cs.AI 2013
Year: 2013

Handwriting is one of the most important means of daily communication. Although the problem of handwriting recognition has been considered for more than 60 years there are still many open issues, especially in the task of unconstrained handwritten sentence recognition. This paper focuses on the automatic system that recognizes continuous English sentence through a mouse-based gestures in real-time based on Artificial Neural Network. The proposed Artificial Neural Network is trained using the traditional backpropagation algorithm for self supervised neural network which provides the system with great learning ability and thus has proven highly successful in training for feed-forward Artificial Neural Network. The designed algorithm is not only capable of translating discrete gesture moves, but also continuous gestures through the mouse. In this paper we are using the efficient neural network approach for recognizing English sentence drawn by mouse. This approach shows an efficient way of extracting the boundary of the English Sentence and specifies the area of the recognition English sentence where it has been drawn in an image and then used Artificial Neural Network to recognize the English sentence. The proposed approach English sentence recognition (ESR) system is designed and tested successfully. Experimental results show that the higher speed and accuracy were examined.
A MATLAB Code for Three Dimensional Linear Elastostatics using Constant Boundary Elements
Venue: arXiv cs.CE 2013
Year: 2013

Present work presents a code written in the very simple programming language MATLAB, for three dimensional linear elastostatics, using constant boundary elements. The code, in full or in part, is not a translation or a copy of any of the existing codes. Present paper explains how the code is written, and lists all the formulae used. Code is verified by using the code to solve a simple problem which has the well known approximate analytical solution. Of course, present work does not make any contribution to research on boundary elements, in terms of theory. But the work is justified by the fact that, to the best of author's knowledge, as of now, one cannot find an open access MATLAB code for three dimensional linear elastostatics using constant boundary elements. Author hopes this paper to be of help to beginners who wish to understand how a simple but complete boundary element code works, so that they can build upon and modify the present open access code to solve complex engineering problems quickly and easily. The code is available online for open access (as supplementary file for the present paper), and may be downloaded from the website for the present journal.
Binary Patterns in Binary Cube-Free Words: Avoidability and Growth
Venue: arXiv cs.FL 2013
Year: 2013

The avoidability of binary patterns by binary cube-free words is investigated and the exact bound between unavoidable and avoidable patterns is found. All avoidable patterns are shown to be D0L-avoidable. For avoidable patterns, the growth rates of the avoiding languages are studied. All such languages, except for the overlap-free language, are proved to have exponential growth. The exact growth rates of languages avoiding minimal avoidable patterns are approximated through computer-assisted upper bounds. Finally, a new example of a pattern-avoiding language of polynomial growth is given.
Practical Bijective S-box Design
Venue: arXiv cs.CR 2013
Year: 2013

We construct 8 x 8 bijective cryptographically strong S-boxes. Our construction is based on using non-bijective power functions over the finite filed.
Physical Channel Access (PCA): Time and Frequency Access Methods Emulation in NS-2
Venue: arXiv cs.NI 2013
Year: 2013

We present an NS-2 module, Physical Channel Access (PCA), to simulate different access methods on a link shared with Multi-Frequency Time Division Multiple Access (MF-TDMA). This tech- nique is widely used in various network technologies, such as satellite communication. In this context, different access methods at the gateway induce different queuing delays and available capacities, which strongly impact transport layer performance. Depending on QoS requirements, design of new congestion and flow control mechanisms and/or access methods requires evaluation through simulations. PCA module emulates the delays that packets will experience using the shared link, based on descriptive parameters of lower layers characteris- tics. Though PCA has been developed with DVB-RCS2 considerations in mind (for which we present a use case), other MF-TDMA-based appli- cations can easily be simulated by adapting input parameters. Moreover, the presented implementation details highlight the main methods that might need modifications to implement more specific functionality or emulate other similar access methods (e.g., OFDMA).
On the Behavior of the Residual in Conjugate Gradient Method
Venue: arXiv cs.NA 2013
Year: 2013

In conjugate gradient method, it is well known that the recursively computed residual differs from true one as the iteration proceeds in finite arithmetic. Some work have been devoted to analyze this be-havior and to evaluate the lower and the upper bounds of the difference. This paper focuses on the behavior of these two kinds of residuals, especially their lower bounds caused by the loss of trailing digit, respectively.
Pattern Matching for Self- Tuning of MapReduce Jobs
Venue: arXiv cs.DC 2013
Year: 2013

In this paper, we study CPU utilization time patterns of several MapReduce applications. After extracting running patterns of several applications, they are saved in a reference database to be later used to tweak system parameters to efficiently execute unknown applications in future. To achieve this goal, CPU utilization patterns of new applications are compared with the already known ones in the reference database to find/predict their most probable execution patterns. Because of different patterns lengths, the Dynamic Time Warping (DTW) is utilized for such comparison; a correlation analysis is then applied to DTWs outcomes to produce feasible similarity patterns. Three real applications (WordCount, Exim Mainlog parsing and Terasort) are used to evaluate our hypothesis in tweaking system parameters in executing similar applications. Results were very promising and showed effectiveness of our approach on pseudo-distributed MapReduce platforms.