OpenRaiser/Intern-Atlas huggingface dataset:
Exploiting Structure in Weighted Model Counting Approaches to Probabilistic Inference
Venue: arXiv cs.AI 2014
Year: 2014

Previous studies have demonstrated that encoding a Bayesian network into a SAT formula and then performing weighted model counting using a backtracking search algorithm can be an effective method for exact inference. In this paper, we present techniques for improving this approach for Bayesian networks with noisy-OR and noisy-MAX relations---two relations that are widely used in practice as they can dramatically reduce the number of probabilities one needs to specify. In particular, we present two SAT encodings for noisy-OR and two encodings for noisy-MAX that exploit the structure or semantics of the relations to improve both time and space efficiency, and we prove the correctness of the encodings. We experimentally evaluated our techniques on large-scale real and randomly generated Bayesian networks. On these benchmarks, our techniques gave speedups of up to two orders of magnitude over the best previous approaches for networks with noisy-OR/MAX relations and scaled up to larger networks. As well, our techniques extend the weighted model counting approach for exact inference to networks that were previously intractable for the approach.
Efficient Multi-Start Strategies for Local Search Algorithms
Venue: arXiv cs.LG 2014
Year: 2014

Local search algorithms applied to optimization problems often suffer from getting trapped in a local optimum. The common solution for this deficiency is to restart the algorithm when no progress is observed. Alternatively, one can start multiple instances of a local search algorithm, and allocate computational resources (in particular, processing time) to the instances depending on their behavior. Hence, a multi-start strategy has to decide (dynamically) when to allocate additional resources to a particular instance and when to start new instances. In this paper we propose multi-start strategies motivated by works on multi-armed bandit problems and Lipschitz optimization with an unknown constant. The strategies continuously estimate the potential performance of each algorithm instance by supposing a convergence rate of the local search algorithm up to an unknown constant, and in every phase allocate resources to those instances that could converge to the optimum for a particular range of the constant. Asymptotic bounds are given on the performance of the strategies. In particular, we prove that at most a quadratic increase in the number of times the target function is evaluated is needed to achieve the performance of a local search algorithm started from the attraction region of the optimum. Experiments are provided using SPSA (Simultaneous Perturbation Stochastic Approximation) and k-means as local search algorithms, and the results indicate that the proposed strategies work well in practice, and, in all cases studied, need only logarithmically more evaluations of the target function as opposed to the theoretically suggested quadratic increase.
The Opposite of Smoothing: A Language Model Approach to Ranking Query-Specific Document Clusters
Venue: arXiv cs.IR 2014
Year: 2014

Exploiting information induced from (query-specific) clustering of top-retrieved documents has long been proposed as a means for improving precision at the very top ranks of the returned results. We present a novel language model approach to ranking query-specific clusters by the presumed percentage of relevant documents that they contain. While most previous cluster ranking approaches focus on the cluster as a whole, our model utilizes also information induced from documents associated with the cluster. Our model substantially outperforms previous approaches for identifying clusters containing a high relevant-document percentage. Furthermore, using the model to produce document ranking yields precision-at-top-ranks performance that is consistently better than that of the initial ranking upon which clustering is performed. The performance also favorably compares with that of a state-of-the-art pseudo-feedback-based retrieval method.
Interpolable Formulas in Equilibrium Logic and Answer Set Programming
Venue: arXiv cs.LO 2014
Year: 2014

Interpolation is an important property of classical and many non-classical logics that has been shown to have interesting applications in computer science and AI. Here we study the Interpolation Property for the the non-monotonic system of equilibrium logic, establishing weaker or stronger forms of interpolation depending on the precise interpretation of the inference relation. These results also yield a form of interpolation for ground logic programs under the answer sets semantics. For disjunctive logic programs we also study the property of uniform interpolation that is closely related to the concept of variable forgetting. The first-order version of equilibrium logic has analogous Interpolation properties whenever the collection of equilibrium models is (first-order) definable. Since this is the case for so-called safe programs and theories, it applies to the usual situations that arise in practical answer set programming.
First-Order Stable Model Semantics and First-Order Loop Formulas
Venue: arXiv cs.LO 2014
Year: 2014

Lin and Zhaos theorem on loop formulas states that in the propositional case the stable model semantics of a logic program can be completely characterized by propositional loop formulas, but this result does not fully carry over to the first-order case. We investigate the precise relationship between the first-order stable model semantics and first-order loop formulas, and study conditions under which the former can be represented by the latter. In order to facilitate the comparison, we extend the definition of a first-order loop formula which was limited to a nondisjunctive program, to a disjunctive program and to an arbitrary first-order theory. Based on the studied relationship we extend the syntax of a logic program with explicit quantifiers, which allows us to do reasoning involving non-Herbrand stable models using first-order reasoners. Such programs can be viewed as a special class of first-order theories under the stable model semantics, which yields more succinct loop formulas than the general language due to their restricted syntax.
Multi-Robot Adversarial Patrolling: Facing a Full-Knowledge Opponent
Venue: arXiv cs.MA 2014
Year: 2014

The problem of adversarial multi-robot patrol has gained interest in recent years, mainly due to its immediate relevance to various security applications. In this problem, robots are required to repeatedly visit a target area in a way that maximizes their chances of detecting an adversary trying to penetrate through the patrol path. When facing a strong adversary that knows the patrol strategy of the robots, if the robots use a deterministic patrol algorithm, then in many cases it is easy for the adversary to penetrate undetected (in fact, in some of those cases the adversary can guarantee penetration). Therefore this paper presents a non-deterministic patrol framework for the robots. Assuming that the strong adversary will take advantage of its knowledge and try to penetrate through the patrols weakest spot, hence an optimal algorithm is one that maximizes the chances of detection in that point. We therefore present a polynomial-time algorithm for determining an optimal patrol under the Markovian strategy assumption for the robots, such that the probability of detecting the adversary in the patrols weakest spot is maximized. We build upon this framework and describe an optimal patrol strategy for several robotic models based on their movement abilities (directed or undirected) and sensing abilities (perfect or imperfect), and in different environment models - either patrol around a perimeter (closed polygon) or an open fence (open polyline).
MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees
Venue: arXiv cs.AI 2014
Year: 2014

Multi-agent path planning is a challenging problem with numerous real-life applications. Running a centralized search such as A* in the combined state space of all units is complete and cost-optimal, but scales poorly, as the state space size is exponential in the number of mobile units. Traditional decentralized approaches, such as FAR and WHCA*, are faster and more scalable, being based on problem decomposition. However, such methods are incomplete and provide no guarantees with respect to the running time or the solution quality. They are not necessarily able to tell in a reasonable time whether they would succeed in finding a solution to a given instance. We introduce MAPP, a tractable algorithm for multi-agent path planning on undirected graphs. We present a basic version and several extensions. They have low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. Even though all algorithmic versions are incomplete in the general case, each provides formal guarantees on problems it can solve. For each version, we discuss the algorithms completeness with respect to clearly defined subclasses of instances. Experiments were run on realistic game grid maps. MAPP solved 99.86% of all mobile units, which is 18--22% better than the percentage of FAR and WHCA*. MAPP marked 98.82% of all units as provably solvable during the first stage of plan computation. Parts of MAPPs computation can be re-used across instances on the same map. Speed-wise, MAPP is competitive or significantly faster than WHCA*, depending on whether MAPP performs all computations from scratch. When data that MAPP can re-use are preprocessed offline and readily available, MAPP is slower than the very fast FAR algorithm by a factor of 2.18 on average. MAPPs solutions are on average 20% longer than FARs solutions and 7--31% longer than WHCA*s solutions.
Multiply Constant-Weight Codes and the Reliability of Loop Physically Unclonable Functions
Venue: arXiv cs.IT 2014
Year: 2014

We introduce the class of multiply constant-weight codes to improve the reliability of certain physically unclonable function (PUF) response. We extend classical coding methods to construct multiply constant-weight codes from known $q$-ary and constant-weight codes. Analogues of Johnson bounds are derived and are shown to be asymptotically tight to a constant factor under certain conditions. We also examine the rates of the multiply constant-weight codes and interestingly, demonstrate that these rates are the same as those of constant-weight codes of suitable parameters. Asymptotic analysis of our code constructions is provided.
Performance Evaluation of Bit Division Multiplexing combined with Non-Uniform QAM
Venue: arXiv cs.IT 2014
Year: 2014

Broadcasting systems have to deal with channel variability in order to offer the best spectral efficiency to the receivers. However, the transmission parameters that maximise the spectral efficiency generally leads to a large link unavailability. In this paper, we study analytically the trade-off between spectral efficiency and coverage for various channel resource allocation strategies when broadcasting two services. More precisely, we consider the following strategies: time sharing, hierarchical modulation and bit division multiplexing. Our main contribution is the combination of bit division multiplexing with non-uniform QAM to improve the performance of broadcasting systems. The results show that this scheme outperforms all the previous channel resource allocation strategies.
Towards a Cellular Automata Based Network Intrusion Detection System with Power Level Metric in Wireless Adhoc Networks (IDFADNWCA)
Venue: arXiv cs.NI 2014
Year: 2014

Adhoc wireless network with their changing topology and distributed nature are more prone to intruders. The efficiency of an Intrusion detection system in the case of an adhoc network is not only determined by its dynamicity in monitoring but also in its flexibility in utilizing the available power in each of its nodes. In this paper we propose a hybrid intrusion detection system, based on a power level metric for potential adhoc hosts, which is used to determine the duration for which a particular node can support a network-monitoring node. The detection of intrusions in the network is done with the help of Cellular Automata (CA). IDFADNWCA (Intrusion Detection for Adhoc Networks with Cellular Automata) focuses on the available power level in each of the nodes and determines the network monitors. Power Level Metric in the network results in maintaining power for network monitoring, with monitors changing often, since it is an iterative power optimal solution to identify nodes for distributed agent based intrusion detection. The advantage of this approach entails is the inherent flexibility it provides, by means of considering only fewer nodes for reestablishing network monitors.
Robust Recursive State Estimation with Random Measurements Droppings
Venue: arXiv cs.SY 2014
Year: 2014

A recursive state estimation procedure is derived for a linear time varying system with both parametric uncertainties and stochastic measurement droppings. This estimator has a similar form as that of the Kalman filter with intermittent observations, but its parameters should be adjusted when a plant output measurement arrives. A new recursive form is derived for the pseudo-covariance matrix of estimation errors, which plays important roles in analyzing its asymptotic properties. Based on a Riemannian metric for positive definite matrices, some necessary and sufficient conditions have been obtained for the strict contractiveness of an iteration of this recursion. It has also been proved that under some controllability and observability conditions, as well as some weak requirements on measurement arrival probability, the gain matrix of this recursive robust state estimator converges in probability one to a stationary distribution. Numerical simulation results show that estimation accuracy of the suggested procedure is more robust against parametric modelling errors than the Kalman filter.
Analysis of Probabilistic Basic Parallel Processes
Venue: arXiv cs.LO 2014
Year: 2014

Basic Parallel Processes (BPPs) are a well-known subclass of Petri Nets. They are the simplest common model of concurrent programs that allows unbounded spawning of processes. In the probabilistic version of BPPs, every process generates other processes according to a probability distribution. We study the decidability and complexity of fundamental qualitative problems over probabilistic BPPs -- in particular reachability with probability 1 of different classes of target sets (e.g. upward-closed sets). Our results concern both the Markov-chain model, where processes are scheduled randomly, and the MDP model, where processes are picked by a scheduler.
Arguments using ontological and causal knowledge
Venue: arXiv cs.AI 2014
Year: 2014

We investigate an approach to reasoning about causes through argumentation. We consider a causal model for a physical system, and look for arguments about facts. Some arguments are meant to provide explanations of facts whereas some challenge these explanations and so on. At the root of argumentation here, are causal links ({A_1, ... ,A_n} causes B) and ontological links (o_1 is_a o_2). We present a system that provides a candidate explanation ({A_1, ... ,A_n} explains {B_1, ... ,B_m}) by resorting to an underlying causal link substantiated with appropriate ontological links. Argumentation is then at work from these various explaining links. A case study is developed: a severe storm Xynthia that devastated part of France in 2010, with an unaccountably high number of casualties.
Entropy analysis of word-length series of natural language texts: Effects of text language and genre
Venue: arXiv cs.CL 2014
Year: 2014

We estimate the $n$-gram entropies of natural language texts in word-length representation and find that these are sensitive to text language and genre. We attribute this sensitivity to changes in the probability distribution of the lengths of single words and emphasize the crucial role of the uniformity of probabilities of having words with length between five and ten. Furthermore, comparison with the entropies of shuffled data reveals the impact of word length correlations on the estimated $n$-gram entropies.
Complexity Analysis of Heuristic Pulse Interleaving Algorithms for Multi-Target Tracking with Multiple Simultaneous Receive Beams
Venue: arXiv cs.SY 2014
Year: 2014

This paper presents heuristic algorithms for interleaved pulse scheduling problems on multi-target tracking in pulse Doppler phased array radars that can process multiple simultaneous received beams. The interleaved pulse scheduling problems for element and subarray level digital beamforming architectures are formulated as the same integer program and the asymptotic time complexities of the algorithms are analyzed.
Robust Bayesian compressed sensing over finite fields: asymptotic performance analysis
Venue: arXiv cs.IT 2014
Year: 2014

This paper addresses the topic of robust Bayesian compressed sensing over finite fields. For stationary and ergodic sources, it provides asymptotic (with the size of the vector to estimate) necessary and sufficient conditions on the number of required measurements to achieve vanishing reconstruction error, in presence of sensing and communication noise. In all considered cases, the necessary and sufficient conditions asymptotically coincide. Conditions on the sparsity of the sensing matrix are established in presence of communication noise. Several previously published results are generalized and extended.
Do altmetrics correlate with citations? Extensive comparison of altmetric indicators with citations from a multidisciplinary perspective
Venue: arXiv cs.DL 2014
Year: 2014

An extensive analysis of the presence of different altmetric indicators provided by Altmetric.com across scientific fields is presented, particularly focusing on their relationship with citations. Our results confirm that the presence and density of social media altmetric counts are still very low and not very frequent among scientific publications, with 15%-24% of the publications presenting some altmetric activity and concentrating in the most recent publications, although their presence is increasing over time. Publications from the social sciences, humanities and the medical and life sciences show the highest presence of altmetrics, indicating their potential value and interest for these fields. The analysis of the relationships between altmetrics and citations confirms previous claims of positive correlations but relatively weak, thus supporting the idea that altmetrics do not reflect the same concept of impact as citations. Also, altmetric counts do not always present a better filtering of highly cited publications than journal citation scores. Altmetrics scores (particularly mentions in blogs) are able to identify highly cited publications with higher levels of precision than journal citation scores (JCS), but they have a lower level of recall. The value of altmetrics as a complementary tool of citation analysis is highlighted, although more research is suggested to disentangle the potential meaning and value of altmetric indicators for research evaluation.
Weak MSO: Automata and Expressiveness Modulo Bisimilarity
Venue: arXiv cs.LO 2014
Year: 2014

We prove that the bisimulation-invariant fragment of weak monadic second-order logic (WMSO) is equivalent to the fragment of the modal $μ$-calculus where the application of the least fixpoint operator $μp.φ$ is restricted to formulas $φ$ that are continuous in $p$. Our proof is automata-theoretic in nature; in particular, we introduce a class of automata characterizing the expressive power of WMSO over tree models of arbitrary branching degree. The transition map of these automata is defined in terms of a logic $\mathrm{FOE}_1^\infty$ that is the extension of first-order logic with a generalized quantifier $\exists^\infty$, where $\exists^\infty x. ϕ$ means that there are infinitely many objects satisfying $ϕ$. An important part of our work consists of a model-theoretic analysis of $\mathrm{FOE}_1^\infty$.
Towards plant wires
Venue: arXiv cs.ET 2014
Year: 2014

In experimental laboratory studies we evaluate a possibility of making electrical wires from living plants. In scoping experiments we use lettuce seedlings as a prototype model of a plant wire. We approximate an electrical potential transfer function by applying direct current voltage to the lettuce seedlings and recording output voltage. We analyse oscillation frequencies of the output potential and assess noise immunity of the plant wires. Our findings will be used in future designs of self-growing wetware circuits and devices, and integration of plant-based electronic components into future and emergent bio-hybrid systems.
Reliable, Deniable, and Hidable Communication over Multipath Networks
Venue: arXiv cs.IT 2014
Year: 2014

We consider the scenario wherein Alice wants to (potentially) communicate to the intended receiver Bob over a network consisting of multiple parallel links in the presence of a passive eavesdropper Willie, who observes an unknown subset of links. A primary goal of our communication protocol is to make the communication "deniable", {\it i.e.}, Willie should not be able to {\it reliably} estimate whether or not Alice is transmitting any {\it covert} information to Bob. Moreover, if Alice is indeed actively communicating, her covert messages should be information-theoretically "hidable" in the sense that Willie's observations should not {\it leak any information} about Alice's (potential) message to Bob -- our notion of hidability is slightly stronger than the notion of information-theoretic strong secrecy well-studied in the literature, and may be of independent interest. It can be shown that deniability does not imply either hidability or (weak or strong) information-theoretic secrecy; nor does any form of information-theoretic secrecy imply deniability. We present matching inner and outer bounds on the capacity for deniable and hidable communication over {\it multipath networks}.
Temporal Logics for Hyperproperties
Venue: arXiv cs.LO 2014
Year: 2014

Two new logics for verification of hyperproperties are proposed. Hyperproperties characterize security policies, such as noninterference, as a property of sets of computation paths. Standard temporal logics such as LTL, CTL, and CTL* can refer only to a single path at a time, hence cannot express many hyperproperties of interest. The logics proposed here, HyperLTL and HyperCTL*, add explicit and simultaneous quantification over multiple paths to LTL and to CTL*. This kind of quantification enables expression of hyperproperties. A model checking algorithm for the proposed logics is given. For a fragment of HyperLTL, a prototype model checker has been implemented.