OpenRaiser/Intern-Atlas huggingface dataset:
Alternating Directions Dual Decomposition
Venue: arXiv cs.AI 2012
Year: 2012

We propose AD3, a new algorithm for approximate maximum a posteriori (MAP) inference on factor graphs based on the alternating directions method of multipliers. Like dual decomposition algorithms, AD3 uses worker nodes to iteratively solve local subproblems and a controller node to combine these local solutions into a global update. The key characteristic of AD3 is that each local subproblem has a quadratic regularizer, leading to a faster consensus than subgradient-based dual decomposition, both theoretically and in practice. We provide closed-form solutions for these AD3 subproblems for binary pairwise factors and factors imposing first-order logic constraints. For arbitrary factors (large or combinatorial), we introduce an active set method which requires only an oracle for computing a local MAP configuration, making AD3 applicable to a wide range of problems. Experiments on synthetic and realworld problems show that AD3 compares favorably with the state-of-the-art.
Blind Adaptive Interference Suppression Based on Set-Membership Constrained Constant-Modulus Algorithms with Time-Varying Bounds
Venue: arXiv cs.IT 2012
Year: 2012

This work presents blind constrained constant modulus (CCM) adaptive algorithms based on the set-membership filtering (SMF) concept and incorporates dynamic bounds {for interference suppression} applications. We develop stochastic gradient and recursive least squares type algorithms based on the CCM design criterion in accordance with the specifications of the SMF concept. We also propose a blind framework that includes channel and amplitude estimators that take into account parameter estimation dependency, multiple access interference (MAI) and inter-symbol interference (ISI) to address the important issue of bound specification in multiuser communications. A convergence and tracking analysis of the proposed algorithms is carried out along with the development of analytical expressions to predict their performance. Simulations for a number of scenarios of interest with a DS-CDMA system show that the proposed algorithms outperform previously reported techniques with a smaller number of parameter updates and a reduced risk of overbounding or underbounding.
Exploring mutexes, the Oracle RDBMS retrial spinlocks
Venue: arXiv cs.DB 2012
Year: 2012

Spinlocks are widely used in database engines for processes synchronization. KGX mutexes is new retrial spinlocks appeared in contemporary Oracle versions for submicrosecond synchronization. The mutex contention is frequently observed in highly concurrent OLTP environments. This work explores how Oracle mutexes operate, spin, and sleep. It develops predictive mathematical model and discusses parameters and statistics related to mutex performance tuning, as well as results of contention experiments.
Blind Adaptive MIMO Receivers for Space-Time Block-Coded DS-CDMA Systems in Multipath Channels Using the Constant Modulus Criterion
Venue: arXiv cs.IT 2012
Year: 2012

We propose blind adaptive multi-input multi-output (MIMO) linear receivers for DS-CDMA systems using multiple transmit antennas and space-time block codes (STBC) in multipath channels. A space-time code-constrained constant modulus (CCM) design criterion based on constrained optimization techniques is considered and recursive least squares (RLS) adaptive algorithms are developed for estimating the parameters of the linear receivers. A blind space-time channel estimation method for MIMO DS-CDMA systems with STBC based on a subspace approach is also proposed along with an efficient RLS algorithm. Simulations for a downlink scenario assess the proposed algorithms in several situations against existing methods.
A Trichotomy for Regular Simple Path Queries on Graphs
Venue: arXiv cs.DB 2012
Year: 2012

Regular path queries (RPQs) select nodes connected by some path in a graph. The edge labels of such a path have to form a word that matches a given regular expression. We investigate the evaluation of RPQs with an additional constraint that prevents multiple traversals of the same nodes. Those regular simple path queries (RSPQs) find several applications in practice, yet they quickly become intractable, even for basic languages such as (aa)* or a*ba*. In this paper, we establish a comprehensive classification of regular languages with respect to the complexity of the corresponding regular simple path query problem. More precisely, we identify the fragment that is maximal in the following sense: regular simple path queries can be evaluated in polynomial time for every regular language L that belongs to this fragment and evaluation is NP-complete for languages outside this fragment. We thus fully characterize the frontier between tractability and intractability for RSPQs, and we refine our results to show the following trichotomy: Evaluations of RSPQs is either AC0, NL-complete or NP-complete in data complexity, depending on the regular language L. The fragment identified also admits a simple characterization in terms of regular expressions. Finally, we also discuss the complexity of the following decision problem: decide, given a language L, whether finding a regular simple path for L is tractable. We consider several alternative representations of L: DFAs, NFAs or regular expressions, and prove that this problem is NL-complete for the first representation and PSPACE-complete for the other two. As a conclusion we extend our results from edge-labeled graphs to vertex-labeled graphs and vertex-edge labeled graphs.
About Multichannel Speech Signal Extraction and Separation Techniques
Venue: arXiv cs.SD 2012
Year: 2012

The extraction of a desired speech signal from a noisy environment has become a challenging issue. In the recent years, the scientific community has particularly focused on multichannel techniques which are dealt with in this review. In fact, this study tries to classify these multichannel techniques into three main ones: Beamforming, Independent Com-ponent Analysis (ICA) and Time Frequency (T-F) masking. This paper also highlights their advantages and drawbacks. However these previously mentioned techniques could not afford satisfactory results. This fact leads to the idea that a combination of those techniques, which is depicted along this study, may probably provide more efficient results. In-deed, giving the fact that those approaches are still be considered as being not totally efficient, has led us to review these mentioned above in the hope that further researches will provide this domain with suitable innovations.
Predictive Non-equilibrium Social Science
Venue: arXiv cs.SI 2012
Year: 2012

Non-Equilibrium Social Science (NESS) emphasizes dynamical phenomena, for instance the way political movements emerge or competing organizations interact. This paper argues that predictive analysis is an essential element of NESS, occupying a central role in its scientific inquiry and representing a key activity of practitioners in domains such as economics, public policy, and national security. We begin by clarifying the distinction between models which are useful for prediction and the much more common explanatory models studied in the social sciences. We then investigate a challenging real-world predictive analysis case study, and find evidence that the poor performance of standard prediction methods does not indicate an absence of human predictability but instead reflects (1.) incorrect assumptions concerning the predictive utility of explanatory models, (2.) misunderstanding regarding which features of social dynamics actually possess predictive power, and (3.) practical difficulties exploiting predictive representations.
Bipolar Possibilistic Representations
Venue: arXiv cs.AI 2012
Year: 2012

Recently, it has been emphasized that the possibility theory framework allows us to distinguish between i) what is possible because it is not ruled out by the available knowledge, and ii) what is possible for sure. This distinction may be useful when representing knowledge, for modelling values which are not impossible because they are consistent with the available knowledge on the one hand, and values guaranteed to be possible because reported from observations on the other hand. It is also of interest when expressing preferences, to point out values which are positively desired among those which are not rejected. This distinction can be encoded by two types of constraints expressed in terms of necessity measures and in terms of guaranteed possibility functions, which induce a pair of possibility distributions at the semantic level. A consistency condition should ensure that what is claimed to be guaranteed as possible is indeed not impossible. The present paper investigates the representation of this bipolar view, including the case when it is stated by means of conditional measures, or by means of comparative context-dependent constraints. The interest of this bipolar framework, which has been recently stressed for expressing preferences, is also pointed out in the representation of diagnostic knowledge.
Learning with Scope, with Application to Information Extraction and Classification
Venue: arXiv cs.LG 2012
Year: 2012

In probabilistic approaches to classification and information extraction, one typically builds a statistical model of words under the assumption that future data will exhibit the same regularities as the training data. In many data sets, however, there are scope-limited features whose predictive power is only applicable to a certain subset of the data. For example, in information extraction from web pages, word formatting may be indicative of extraction category in different ways on different web pages. The difficulty with using such features is capturing and exploiting the new regularities encountered in previously unseen data. In this paper, we propose a hierarchical probabilistic model that uses both local/scope-limited features, such as word formatting, and global features, such as word content. The local regularities are modeled as an unobserved random parameter which is drawn once for each local data set. This random parameter is estimated during the inference process and then used to perform classification with both the local and global features--- a procedure which is akin to automatically retuning the classifier to the local regularities on each newly encountered web page. Exact inference is intractable and we present approximations via point estimates and variational methods. Empirical results on large collections of web data demonstrate that this method significantly improves performance from traditional models of global features alone.
Qualitative MDPs and POMDPs: An Order-Of-Magnitude Approximation
Venue: arXiv cs.AI 2012
Year: 2012

We develop a qualitative theory of Markov Decision Processes (MDPs) and Partially Observable MDPs that can be used to model sequential decision making tasks when only qualitative information is available. Our approach is based upon an order-of-magnitude approximation of both probabilities and utilities, similar to epsilon-semantics. The result is a qualitative theory that has close ties with the standard maximum-expected-utility theory and is amenable to general planning techniques.
Finding Optimal Bayesian Networks
Venue: arXiv cs.AI 2012
Year: 2012

In this paper, we derive optimality results for greedy Bayesian-network search algorithms that perform single-edge modifications at each step and use asymptotically consistent scoring criteria. Our results extend those of Meek (1997) and Chickering (2002), who demonstrate that in the limit of large datasets, if the generative distribution is perfect with respect to a DAG defined over the observable variables, such search algorithms will identify this optimal (i.e. generative) DAG model. We relax their assumption about the generative distribution, and assume only that this distribution satisfies the {em composition property} over the observable variables, which is a more realistic assumption for real domains. Under this assumption, we guarantee that the search algorithms identify an {em inclusion-optimal} model; that is, a model that (1) contains the generative distribution and (2) has no sub-model that contains this distribution. In addition, we show that the composition property is guaranteed to hold whenever the dependence relationships in the generative distribution can be characterized by paths between singleton elements in some generative graphical model (e.g. a DAG, a chain graph, or a Markov network) even when the generative model includes unobserved variables, and even when the observed data is subject to selection bias.
Iterative Join-Graph Propagation
Venue: arXiv cs.AI 2012
Year: 2012

The paper presents an iterative version of join-tree clustering that applies the message passing of join-tree clustering algorithm to join-graphs rather than to join-trees, iteratively. It is inspired by the success of Pearl's belief propagation algorithm as an iterative approximation scheme on one hand, and by a recently introduced mini-clustering i. success as an anytime approximation method, on the other. The proposed Iterative Join-graph Propagation IJGP belongs to the class of generalized belief propagation methods, recently proposed using analogy with algorithms in statistical physics. Empirical evaluation of this approach on a number of problem classes demonstrates that even the most time-efficient variant is almost always superior to IBP and MC i, and is sometimes more accurate by as much as several orders of magnitude.
Almost-everywhere algorithmic stability and generalization error
Venue: arXiv cs.LG 2012
Year: 2012

We explore in some detail the notion of algorithmic stability as a viable framework for analyzing the generalization error of learning algorithms. We introduce the new notion of training stability of a learning algorithm and show that, in a general setting, it is sufficient for good bounds on generalization error. In the PAC setting, training stability is both necessary and sufficient for learnability.\ The approach based on training stability makes no reference to VC dimension or VC entropy. There is no need to prove uniform convergence, and generalization error is bounded directly via an extended McDiarmid inequality. As a result it potentially allows us to deal with a broader class of learning algorithms than Empirical Risk Minimization. \ We also explore the relationships among VC dimension, generalization error, and various notions of stability. Several examples of learning algorithms are considered.
Formalizing Scenario Analysis
Venue: arXiv cs.AI 2012
Year: 2012

We propose a formal treatment of scenarios in the context of a dialectical argumentation formalism for qualitative reasoning about uncertain propositions. Our formalism extends prior work in which arguments for and against uncertain propositions were presented and compared in interaction spaces called Agoras. We now define the notion of a scenario in this framework and use it to define a set of qualitative uncertainty labels for propositions across a collection of scenarios. This work is intended to lead to a formal theory of scenarios and scenario analysis.
Factored Particles for Scalable Monitoring
Venue: arXiv cs.AI 2012
Year: 2012

Exact monitoring in dynamic Bayesian networks is intractable, so approximate algorithms are necessary. This paper presents a new family of approximate monitoring algorithms that combine the best qualities of the particle filtering and Boyen-Koller methods. Our algorithms maintain an approximate representation the belief state in the form of sets of factored particles, that correspond to samples of clusters of state variables. Empirical results show that our algorithms outperform both ordinary particle filtering and the Boyen-Koller algorithm on large systems.
MAP Complexity Results and Approximation Methods
Venue: arXiv cs.AI 2012
Year: 2012

MAP is the problem of finding a most probable instantiation of a set of nvariables in a Bayesian network, given some evidence. MAP appears to be a significantly harder problem than the related problems of computing the probability of evidence Pr, or MPE a special case of MAP. Because of the complexity of MAP, and the lack of viable algorithms to approximate it,MAP computations are generally avoided by practitioners. This paper investigates the complexity of MAP. We show that MAP is complete for NP. We also provide negative complexity results for elimination based algorithms. It turns out that MAP remains hard even when MPE, and Pr are easy. We show that MAP is NPcomplete when the networks are restricted to polytrees, and even then can not be effectively approximated. Because there is no approximation algorithm with guaranteed results, we investigate best effort approximations. We introduce a generic MAP approximation framework. As one instantiation of it, we implement local search coupled with belief propagation BP to approximate MAP. We show how to extract approximate evidence retraction information from belief propagation which allows us to perform efficient local search. This allows MAP approximation even on networks that are too complex to even exactly solve the easier problems of computing Pr or MPE. Experimental results indicate that using BP and local search provides accurate MAP estimates in many cases.
Inference with Seperately Specified Sets of Probabilities in Credal Networks
Venue: arXiv cs.AI 2012
Year: 2012

We present new algorithms for inference in credal networks --- directed acyclic graphs associated with sets of probabilities. Credal networks are here interpreted as encoding strong independence relations among variables. We first present a theory of credal networks based on separately specified sets of probabilities. We also show that inference with polytrees is NP-hard in this setting. We then introduce new techniques that reduce the computational effort demanded by inference, particularly in polytrees, by exploring separability of credal sets.
Inductive Policy Selection for First-Order MDPs
Venue: arXiv cs.AI 2012
Year: 2012

We select policies for large Markov Decision Processes (MDPs) with compact first-order representations. We find policies that generalize well as the number of objects in the domain grows, potentially without bound. Existing dynamic-programming approaches based on flat, propositional, or first-order representations either are impractical here or do not naturally scale as the number of objects grows without bound. We implement and evaluate an alternative approach that induces first-order policies using training data constructed by solving small problem instances using PGraphplan (Blum & Langford, 1999). Our policies are represented as ensembles of decision lists, using a taxonomic concept language. This approach extends the work of Martin and Geffner (2000) to stochastic domains, ensemble learning, and a wider variety of problems. Empirically, we find "good" policies for several stochastic first-order MDPs that are beyond the scope of previous approaches. We also discuss the application of this work to the relational reinforcement-learning problem.
Protecting Online Documents from an Unauthorized External Access (in Bulgarian)
Venue: arXiv cs.CR 2012
Year: 2012

The modern multi-tier web applications and information systems store and process various types of data. Some of them are stored in a database, controlled by an external database management system, while other data are stored directly within the server's file system. The database is secured by the database management system itself, but it is a programmer's responsibility to design and develop a security protection of the files managed by the information system. This paper summarizes the existing and suggests new rules for design and implementation of an in-depth security protection of file resources, published on the Internet, from an unauthorized external access. The paper is in Bulgarian.
Data linkage algebra, data linkage dynamics, and priority rewriting
Venue: arXiv cs.LO 2013
Year: 2013

We introduce an algebra of data linkages. Data linkages are intended for modelling the states of computations in which dynamic data structures are involved. We present a simple model of computation in which states of computations are modelled as data linkages and state changes take place by means of certain actions. We describe the state changes and replies that result from performing those actions by means of a term rewriting system with rule priorities. The model in question is an upgrade of molecular dynamics. The upgrading is mainly concerned with the features to deal with values and the features to reclaim garbage.
Sequential Design of Experiments via Linear Programming
Venue: arXiv cs.DS 2013
Year: 2013

The celebrated multi-armed bandit problem in decision theory models the basic trade-off between exploration, or learning about the state of a system, and exploitation, or utilizing the system. In this paper we study the variant of the multi-armed bandit problem where the exploration phase involves costly experiments and occurs before the exploitation phase; and where each play of an arm during the exploration phase updates a prior belief about the arm. The problem of finding an inexpensive exploration strategy to optimize a certain exploitation objective is NP-Hard even when a single play reveals all information about an arm, and all exploration steps cost the same. We provide the first polynomial time constant-factor approximation algorithm for this class of problems. We show that this framework also generalizes several problems of interest studied in the context of data acquisition in sensor networks. Our analyses also extends to switching and setup costs, and to concave utility objectives. Our solution approach is via a novel linear program rounding technique based on stochastic packing. In addition to yielding exploration policies whose performance is within a small constant factor of the adaptive optimal policy, a nice feature of this approach is that the resulting policies explore the arms sequentially without revisiting any arm. Sequentiality is a well-studied concept in decision theory, and is very desirable in domains where multiple explorations can be conducted in parallel, for instance, in the sensor network context.
Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks
Venue: arXiv cs.DC 2013
Year: 2013

We address the problem of building and maintaining distributed spanning trees in highly dynamic networks, in which topological events can occur at any time and any rate, and no stable periods can be assumed. In these harsh environments, we strive to preserve some properties such as cycle-freeness or the existence of a root in each tree, in order to make it possible to keep using the trees uninterruptedly (to a possible extent). Our algorithm operates at a coarse-grain level, using atomic pairwise interactions in a way akin to recent population protocol models. The algorithm relies on a perpetual alternation of \emph{topology-induced splittings} and \emph{computation-induced mergings} of a forest of spanning trees. Each tree in the forest hosts exactly one token (also called root) that performs a random walk {\em inside} the tree, switching parent-child relationships as it crosses edges. When two tokens are located on both sides of a same edge, their trees are merged upon this edge and one token disappears. Whenever an edge that belongs to a tree disappears, its child endpoint regenerates a new token instantly. The main features of this approach is that both \emph{merging} and \emph{splitting} are purely localized phenomenons. In this paper, we present and motivate the algorithm, and we prove its correctness in arbitrary dynamic networks. Then we discuss several implementation choices around this general principle. Preliminary results regarding its analysis are also discussed, in particular an analytical expression of the expected merging time for two given trees in a static context.