OpenRaiser/Intern-Atlas huggingface dataset:
Measure Selection: Notions of Rationality and Representation Independence
Venue: arXiv cs.AI 2013
Year: 2013

We take another look at the general problem of selecting a preferred probability measure among those that comply with some given constraints. The dominant role that entropy maximization has obtained in this context is questioned by arguing that the minimum information principle on which it is based could be supplanted by an at least as plausible "likelihood of evidence" principle. We then review a method for turning given selection functions into representation independent variants, and discuss the tradeoffs involved in this transformation.
Dealing with Uncertainty on the Initial State of a Petri Net
Venue: arXiv cs.AI 2013
Year: 2013

This paper proposes a method to find the actual state of a complex dynamic system from information coming from the sensors on the system himself, or on its environment. The nominal evolution of the system is a priori known and can be modeled (by an expert, for example), by different methods. In this paper, the Petri nets have been chosen. Contrary to the usual use of the Petri nets, the initial state of the system is unknown. So a degree of belief is bound to each places, or set of places. The theory used to model this uncertainty is the Dempster-Shafer's one which is well adapted to this type of problems. From the given Petri net characterizing the nominal evolution of the dynamic system, and from the observation inputs, the proposed method allows to determine according to the reliability of the model and the inputs, the state of the system at any time.
Mixture Representations for Inference and Learning in Boltzmann Machines
Venue: arXiv cs.LG 2013
Year: 2013

Boltzmann machines are undirected graphical models with two-state stochastic variables, in which the logarithms of the clique potentials are quadratic functions of the node states. They have been widely studied in the neural computing literature, although their practical applicability has been limited by the difficulty of finding an effective learning algorithm. One well-established approach, known as mean field theory, represents the stochastic distribution using a factorized approximation. However, the corresponding learning algorithm often fails to find a good solution. We conjecture that this is due to the implicit uni-modality of the mean field approximation which is therefore unable to capture multi-modality in the true distribution. In this paper we use variational methods to approximate the stochastic distribution using multi-modal mixtures of factorized distributions. We present results for both inference and learning to demonstrate the effectiveness of this approach.
Planning with Partially Observable Markov Decision Processes: Advances in Exact Solution Method
Venue: arXiv cs.AI 2013
Year: 2013

There is much interest in using partially observable Markov decision processes (POMDPs) as a formal model for planning in stochastic domains. This paper is concerned with finding optimal policies for POMDPs. We propose several improvements to incremental pruning, presently the most efficient exact algorithm for solving POMDPs.
A Framework for the Verification of Certifying Computations
Venue: arXiv cs.LO 2013
Year: 2013

Formal verification of complex algorithms is challenging. Verifying their implementations goes beyond the state of the art of current automatic verification tools and usually involves intricate mathematical theorems. Certifying algorithms compute in addition to each output a witness certifying that the output is correct. A checker for such a witness is usually much simpler than the original algorithm - yet it is all the user has to trust. The verification of checkers is feasible with current tools and leads to computations that can be completely trusted. We describe a framework to seamlessly verify certifying computations. We use the automatic verifier VCC for establishing the correctness of the checker and the interactive theorem prover Isabelle/HOL for high-level mathematical properties of algorithms. We demonstrate the effectiveness of our approach by presenting the verification of typical examples of the industrial-level and widespread algorithmic library LEDA.
Information driven self-organization of complex robotic behaviors
Venue: arXiv cs.RO 2013
Year: 2013

Information theory is a powerful tool to express principles to drive autonomous systems because it is domain invariant and allows for an intuitive interpretation. This paper studies the use of the predictive information (PI), also called excess entropy or effective measure complexity, of the sensorimotor process as a driving force to generate behavior. We study nonlinear and nonstationary systems and introduce the time-local predicting information (TiPI) which allows us to derive exact results together with explicit update rules for the parameters of the controller in the dynamical systems framework. In this way the information principle, formulated at the level of behavior, is translated to the dynamics of the synapses. We underpin our results with a number of case studies with high-dimensional robotic systems. We show the spontaneous cooperativity in a complex physical system with decentralized control. Moreover, a jointly controlled humanoid robot develops a high behavioral variety depending on its physics and the environment it is dynamically embedded into. The behavior can be decomposed into a succession of low-dimensional modes that increasingly explore the behavior space. This is a promising way to avoid the curse of dimensionality which hinders learning systems to scale well.
Non-Adaptive Group Testing based on Sparse Pooling Graphs
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, an information theoretic analysis on non-adaptive group testing schemes based on sparse pooling graphs is presented. The binary status of the objects to be tested are modeled by i.i.d. Bernoulli random variables with probability p. An (l, r, n)-regular pooling graph is a bipartite graph with left node degree l and right node degree r, where n is the number of left nodes. Two scenarios are considered: a noiseless setting and a noisy one. The main contributions of this paper are direct part theorems that give conditions for the existence of an estimator achieving arbitrary small estimation error probability. The direct part theorems are proved by averaging an upper bound on estimation error probability of the typical set estimator over an (l,r, n)-regular pooling graph ensemble. Numerical results indicate sharp threshold behaviors in the asymptotic regime.
An Analysis on Minimum s-t Cut Capacity of Random Graphs with Specified Degree Distribution
Venue: arXiv cs.IT 2013
Year: 2013

The capacity (or maximum flow) of an unicast network is known to be equal to the minimum s-t cut capacity due to the max-flow min-cut theorem. If the topology of a network (or link capacities) is dynamically changing or unknown, it is not so trivial to predict statistical properties on the maximum flow of the network. In this paper, we present a probabilistic analysis for evaluating the accumulate distribution of the minimum s-t cut capacity on random graphs. The graph ensemble treated in this paper consists of weighted graphs with arbitrary specified degree distribution. The main contribution of our work is a lower bound for the accumulate distribution of the minimum s-t cut capacity. From some computer experiments, it is observed that the lower bound derived here reflects the actual statistical behavior of the minimum s-t cut capacity of random graphs with specified degrees.
An Extended Fano's Inequality for the Finite Blocklength Coding
Venue: arXiv cs.IT 2013
Year: 2013

Fano's inequality reveals the relation between the conditional entropy and the probability of error . It has been the key tool in proving the converse of coding theorems in the past sixty years. In this paper, an extended Fano's inequality is proposed, which is tighter and more applicable for codings in the finite blocklength regime. Lower bounds on the mutual information and an upper bound on the codebook size are also given, which are shown to be tighter than the original Fano's inequality. Especially, the extended Fano's inequality is tight for some symmetric channels such as the $q$-ary symmetric channels (QSC).
Parallel Local Search: Experiments with a PGAS-based programming model
Venue: arXiv cs.PL 2013
Year: 2013

Local search is a successful approach for solving combinatorial optimization and constraint satisfaction problems. With the progressing move toward multi and many-core systems, GPUs and the quest for Exascale systems, parallelism has become mainstream as the number of cores continues to increase. New programming models are required and need to be better understood as well as data structures and algorithms. Such is the case for local search algorithms when run on hundreds or thousands of processing units. In this paper, we discuss some experiments we have been doing with Adaptive Search and present a new parallel version of it based on GPI, a recent API and programming model for the development of scalable parallel applications. Our experiments on different problems show interesting speedups and, more importantly, a deeper interpretation of the parallelization of Local Search methods.
On extremal self-dual codes of length 120
Venue: arXiv cs.IT 2013
Year: 2013

We prove that the only primes which may divide the order of the automorphism group of a putative binary self-dual doubly-even [120, 60, 24] code are 2, 3, 5, 7, 19, 23 and 29. Furthermore we prove that automorphisms of prime order $p \geq 5$ have a unique cycle structure.
Dynamic 2D Dictionary Matching in Small Space
Venue: arXiv cs.DS 2013
Year: 2013

The dictionary matching problem preprocesses a set of patterns and finds all occurrences of each of the patterns in a text when it is provided. We focus on the dynamic setting, in which patterns can be inserted to and removed from the dictionary, without reprocessing the entire dictionary. This article presents the first algorithm that performs \emph{dynamic} dictionary matching on two-dimensional data within small space. The time complexity of our algorithm is almost linear. The only slowdown is incurred by querying the compressed self-index that replaces the dictionary. The dictionary is updated in time proportional to the size of the pattern that is being inserted to or removed from the dictionary. Our algorithm is suitable for rectangular patterns that are of uniform size in one dimension.
Plug-and-Play Decentralized Model Predictive Control
Venue: arXiv cs.SY 2013
Year: 2013

In this paper we consider a linear system structured into physically coupled subsystems and propose a decentralized control scheme capable to guarantee asymptotic stability and satisfaction of constraints on system inputs and states. The design procedure is totally decentralized, since the synthesis of a local controller uses only information on a subsystem and its neighbors, i.e. subsystems coupled to it. We first derive tests for checking if a subsystem can be plugged into (or unplugged from) an existing plant without spoiling overall stability and constraint satisfaction. When this is possible, we show how to automatize the design of local controllers so that it can be carried out in parallel by smart actuators equipped with computational resources and capable to exchange information with neighboring subsystems. In particular, local controllers exploit tube-based Model Predictive Control (MPC) in order to guarantee robustness with respect to physical coupling among subsystems. Finally, an application of the proposed control design procedure to frequency control in power networks is presented.
A Bound on the Throughput of Radio Networks
Venue: arXiv cs.DS 2013
Year: 2013

We consider the well-studied radio network model: a synchronous model with a graph G=(V,E) with |V|=n where in each round, each node either transmits a packet, with length B=Omega(log n) bits, or listens. Each node receives a packet iff it is listening and exactly one of its neighbors is transmitting. We consider the problem of k-message broadcast, where k messages, each with Theta(B) bits, are placed in an arbitrary nodes of the graph and the goal is to deliver all messages to all the nodes. We present a simple proof showing that there exist a radio network with radius 2 where for any k, broadcasting k messages requires at least Omega(k log n) rounds. That is, in this network, regardless of the algorithm, the maximum achievable broadcast throughput is O(1/log n).
Signal reconstruction in linear mixing systems with different error metrics
Venue: arXiv cs.IT 2013
Year: 2013

We consider the problem of reconstructing a signal from noisy measurements in linear mixing systems. The reconstruction performance is usually quantified by standard error metrics such as squared error, whereas we consider any additive error metric. Under the assumption that relaxed belief propagation (BP) can compute the posterior in the large system limit, we propose a simple, fast, and highly general algorithm that reconstructs the signal by minimizing the user-defined error metric. For two example metrics, we provide performance analysis and convincing numerical results. Finally, our algorithm can be adjusted to minimize the $\ell_\infty$ error, which is not additive. Interestingly, $\ell_{\infty}$ minimization only requires to apply a Wiener filter to the output of relaxed BP.
A New Constructive Method to Optimize Neural Network Architecture and Generalization
Venue: arXiv cs.NE 2013
Year: 2013

In this paper, after analyzing the reasons of poor generalization and overfitting in neural networks, we consider some noise data as a singular value of a continuous function - jump discontinuity point. The continuous part can be approximated with the simplest neural networks, which have good generalization performance and optimal network architecture, by traditional algorithms such as constructive algorithm for feed-forward neural networks with incremental training, BP algorithm, ELM algorithm, various constructive algorithm, RBF approximation and SVM. At the same time, we will construct RBF neural networks to fit the singular value with every error in, and we prove that a function with jumping discontinuity points can be approximated by the simplest neural networks with a decay RBF neural networks in by each error, and a function with jumping discontinuity point can be constructively approximated by a decay RBF neural networks in by each error and the constructive part have no generalization influence to the whole machine learning system which will optimize neural network architecture and generalization performance, reduce the overfitting phenomenon by avoid fitting the noisy data.
A multi-lane traffic simulation model via continuous cellular automata
Venue: arXiv cs.MA 2013
Year: 2013

Traffic models based on cellular automata have high computational efficiency because of their simplicity in describing unrealistic vehicular behavior and the versatility of cellular automata to be implemented on parallel processing. On the other hand, the other microscopic traffic models such as car-following models are computationally more expensive, but they have more realistic driver behaviors and detailed vehicle characteristics. We propose a new class between these two categories, defining a traffic model based on continuous cellular automata where we combine the efficiency of cellular automata models with the accuracy of the other microscopic models. More precisely, we introduce a stochastic cellular automata traffic model in which the space is not coarse-grain but continuous. The continuity also allows us to embed a multi-agent fuzzy system proposed to handle uncertainties in decision making on road traffic. Therefore, we simulate different driver behaviors and study the effect of various compositions of vehicles within the traffic stream from the macroscopic point of view. The experimental results show that our model is able to reproduce the typical traffic flow phenomena showing a variety of effects due to the heterogeneity of traffic.
Low-Complexity Reduced-Rank Beamforming Algorithms
Venue: arXiv cs.IT 2013
Year: 2013

A reduced-rank framework with set-membership filtering (SMF) techniques is presented for adaptive beamforming problems encountered in radar systems. We develop and analyze stochastic gradient (SG) and recursive least squares (RLS)-type adaptive algorithms, which achieve an enhanced convergence and tracking performance with low computational cost as compared to existing techniques. Simulations show that the proposed algorithms have a superior performance to prior methods, while the complexity is lower.
A game-theoretic framework for classifier ensembles using weighted majority voting with local accuracy estimates
Venue: arXiv cs.LG 2013
Year: 2013

In this paper, a novel approach for the optimal combination of binary classifiers is proposed. The classifier combination problem is approached from a Game Theory perspective. The proposed framework of adapted weighted majority rules (WMR) is tested against common rank-based, Bayesian and simple majority models, as well as two soft-output averaging rules. Experiments with ensembles of Support Vector Machines (SVM), Ordinary Binary Tree Classifiers (OBTC) and weighted k-nearest-neighbor (w/k-NN) models on benchmark datasets indicate that this new adaptive WMR model, employing local accuracy estimators and the analytically computed optimal weights outperform all the other simple combination rules.
RandomBoost: Simplified Multi-class Boosting through Randomization
Venue: arXiv cs.LG 2013
Year: 2013

We propose a novel boosting approach to multi-class classification problems, in which multiple classes are distinguished by a set of random projection matrices in essence. The approach uses random projections to alleviate the proliferation of binary classifiers typically required to perform multi-class classification. The result is a multi-class classifier with a single vector-valued parameter, irrespective of the number of classes involved. Two variants of this approach are proposed. The first method randomly projects the original data into new spaces, while the second method randomly projects the outputs of learned weak classifiers. These methods are not only conceptually simple but also effective and easy to implement. A series of experiments on synthetic, machine learning and visual recognition data sets demonstrate that our proposed methods compare favorably to existing multi-class boosting algorithms in terms of both the convergence rate and classification accuracy.
Circuit proposition for copying the value of a resistor into a memristive device supported by HSPICE simulation
Venue: arXiv cs.OH 2013
Year: 2013

Memristor is the fourth fundamental passive circuit element with potential applications in development of analog memories, artificial brains (with the capacity of hardware training) and neuro-science. In most of these applications the memristance of the device should be set to the desired value, which is currently performed by trial and error. The aim of this paper is to propose a circuit for copying the value of the given resistor into a memristive device. HSPICE simulations are also presented to confirm the efficiency of the proposed circuit.
Short lists with short programs in short time - a short proof
Venue: arXiv cs.CC 2013
Year: 2013

Bauwens, Mahklin, Vereshchagin and Zimand [ECCC TR13-007] and Teutsch [arxiv:1212.6104] have shown that given a string x it is possible to construct in polynomial time a list containing a short description of it. We simplify their technique and present a shorter proof of this result.
A Comparison of Superposition Coding Schemes
Venue: arXiv cs.IT 2013
Year: 2013

There are two variants of superposition coding schemes. Cover's original superposition coding scheme has code clouds of the identical shape, while Bergmans's superposition coding scheme has code clouds of independently generated shapes. These two schemes yield identical achievable rate regions in several scenarios, such as the capacity region for degraded broadcast channels. This paper shows that under the optimal maximum likelihood decoding, these two superposition coding schemes can result in different rate regions. In particular, it is shown that for the two-receiver broadcast channel, Cover's superposition coding scheme can achieve rates strictly larger than Bergmans's scheme.
Hybrid Image Segmentation using Discerner Cluster in FCM and Histogram Thresholding
Venue: arXiv cs.CV 2013
Year: 2013

Image thresholding has played an important role in image segmentation. This paper presents a hybrid approach for image segmentation based on the thresholding by fuzzy c-means (THFCM) algorithm for image segmentation. The goal of the proposed approach is to find a discerner cluster able to find an automatic threshold. The algorithm is formulated by applying the standard FCM clustering algorithm to the frequencies (y-values) on the smoothed histogram. Hence, the frequencies of an image can be used instead of the conventional whole data of image. The cluster that has the highest peak which represents the maximum frequency in the image histogram will play as an excellent role in determining a discerner cluster to the grey level image. Then, the pixels belong to the discerner cluster represent an object in the gray level histogram while the other clusters represent a background. Experimental results with standard test images have been obtained through the proposed approach (THFCM).
Kriging Interpolation Filter to Reduce High Density Salt and Pepper Noise
Venue: arXiv cs.CV 2013
Year: 2013

Image denoising is a critical issue in the field of digital image processing. This paper proposes a novel Salt & Pepper noise suppression by developing a Kriging Interpolation Filter (KIF) for image denoising. Gray-level images degraded with Salt & Pepper noise have been considered. A sequential search for noise detection was made using kXk window size to determine non-noisy pixels only. The non-noisy pixels are passed into Kriging interpolation method to predict their absent neighbor pixels that were noisy pixels at the first phase. The utilization of Kriging interpolation filter proves that it is very impressive to suppress high noise density. It has been found that Kriging Interpolation filter achieves noise reduction without loss of edges and detailed information. Comparisons with existing algorithms are done using quality metrics like PSNR and MSE to assess the proposed filter.
Semantic integration process of business components to support information system designers
Venue: arXiv cs.SE 2013
Year: 2013

The present work is inscribed within the intersection of two scientific thematic: the engineering by reuse of components and ontologies alignment. The integration of Business Components (BC) is a research problem that has been identified in the field of engineering by reuse. Our proposal aims to provide assistance to designers of information systems in the integration phase. It is a process guided by domain ontology to provide semantic integration of BC. This process allows the detection and resolution of semantic conflicts naming type encountered in the process of integration of BC.
Correlated Action Effects in Decision Theoretic Regression
Venue: arXiv cs.AI 2013
Year: 2013

Much recent research in decision theoretic planning has adopted Markov decision processes (MDPs) as the model of choice, and has attempted to make their solution more tractable by exploiting problem structure. One particular algorithm, structured policy construction achieves this by means of a decision theoretic analog of goal regression using action descriptions based on Bayesian networks with tree-structured conditional probability tables. The algorithm as presented is not able to deal with actions with correlated effects. We describe a new decision theoretic regression operator that corrects this weakness. While conceptually straightforward, this extension requires a somewhat more complicated technical approach.