OpenRaiser/Intern-Atlas huggingface dataset:
Global Conditioning for Probabilistic Inference in Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we propose a new approach to probabilistic inference on belief networks, global conditioning, which is a simple generalization of Pearl's (1986b) method of loopcutset conditioning. We show that global conditioning, as well as loop-cutset conditioning, can be thought of as a special case of the method of Lauritzen and Spiegelhalter (1988) as refined by Jensen et al (199Oa; 1990b). Nonetheless, this approach provides new opportunities for parallel processing and, in the case of sequential processing, a tradeoff of time for memory. We also show how a hybrid method (Suermondt and others 1990) combining loop-cutset conditioning with Jensen's method can be viewed within our framework. By exploring the relationships between these methods, we develop a unifying framework in which the advantages of each approach can be combined successfully.
Ignorance and the Expressiveness of Single- and Set-Valued Probability Models of Belief
Venue: arXiv cs.AI 2013
Year: 2013

Over time, there have hen refinements in the way that probability distributions are used for representing beliefs. Models which rely on single probability distributions depict a complete ordering among the propositions of interest, yet human beliefs are sometimes not completely ordered. Non-singleton sets of probability distributions can represent partially ordered beliefs. Convex sets are particularly convenient and expressive, but it is known that there are reasonable patterns of belief whose faithful representation require less restrictive sets. The present paper shows that prior ignorance about three or more exclusive alternatives and the emergence of partially ordered beliefs when evidence is obtained defy representation by any single set of distributions, but yield to a representation baud on several uts. The partial order is shown to be a partial qualitative probability which shares some intuitively appealing attributes with probability distributions.
General Belief Measures
Venue: arXiv cs.AI 2013
Year: 2013

Probability measures by themselves, are known to be inappropriate for modeling the dynamics of plain belief and their excessively strong measurability constraints make them unsuitable for some representational tasks, e.g. in the context of firstorder knowledge. In this paper, we are therefore going to look for possible alternatives and extensions. We begin by delimiting the general area of interest, proposing a minimal list of assumptions to be satisfied by any reasonable quasi-probabilistic valuation concept. Within this framework, we investigate two particularly interesting kinds of quasi-measures which are not or much less affected by the traditional problems. * Ranking measures, which generalize Spohn-type and possibility measures. * Cumulative measures, which combine the probabilistic and the ranking philosophy, allowing thereby a fine-grained account of static and dynamic belief.
On Axiomatization of Probabilistic Conditional Independencies
Venue: arXiv cs.AI 2013
Year: 2013

This paper studies the connection between probabilistic conditional independence in uncertain reasoning and data dependency in relational databases. As a demonstration of the usefulness of this preliminary investigation, an alternate proof is presented for refuting the conjecture suggested by Pearl and Paz that probabilistic conditional independencies have a complete axiomatization.
Inter-causal Independence and Heterogeneous Factorization
Venue: arXiv cs.AI 2013
Year: 2013

It is well known that conditional independence can be used to factorize a joint probability into a multiplication of conditional probabilities. This paper proposes a constructive definition of inter-causal independence, which can be used to further factorize a conditional probability. An inference algorithm is developed, which makes use of both conditional independence and inter-causal independence to reduce inference complexity in Bayesian networks.
Using Virtual Addresses with Communication Channels
Venue: arXiv cs.DC 2013
Year: 2013

While for single processor and SMP machines, memory is the allocatable quantity, for machines made up of large amounts of parallel computing units, each with its own local memory, the allocatable quantity is a single computing unit. Where virtual address management is used to keep memory coherent and allow allocation of more than physical memory is actually available, virtual communication channel references can be used to make computing units stay connected across allocation and swapping.
Online Learning for Time Series Prediction
Venue: arXiv cs.LG 2013
Year: 2013

In this paper we address the problem of predicting a time series using the ARMA (autoregressive moving average) model, under minimal assumptions on the noise terms. Using regret minimization techniques, we develop effective online learning algorithms for the prediction problem, without assuming that the noise terms are Gaussian, identically distributed or even independent. Furthermore, we show that our algorithm's performances asymptotically approaches the performance of the best ARMA model in hindsight.
Describing the complexity of systems: multi-variable "set complexity" and the information basis of systems biology
Venue: arXiv cs.IT 2013
Year: 2013

Context dependence is central to the description of complexity. Keying on the pairwise definition of "set complexity" we use an information theory approach to formulate general measures of systems complexity. We examine the properties of multi-variable dependency starting with the concept of interaction information. We then present a new measure for unbiased detection of multi-variable dependency, "differential interaction information." This quantity for two variables reduces to the pairwise "set complexity" previously proposed as a context-dependent measure of information in biological systems. We generalize it here to an arbitrary number of variables. Critical limiting properties of the "differential interaction information" are key to the generalization. This measure extends previous ideas about biological information and provides a more sophisticated basis for study of complexity. The properties of "differential interaction information" also suggest new approaches to data analysis. Given a data set of system measurements differential interaction information can provide a measure of collective dependence, which can be represented in hypergraphs describing complex system interaction patterns. We investigate this kind of analysis using simulated data sets. The conjoining of a generalized set complexity measure, multi-variable dependency analysis, and hypergraphs is our central result. While our focus is on complex biological systems, our results are applicable to any complex system.
Measuring the Size of Large No-Limit Poker Games
Venue: arXiv cs.GT 2013
Year: 2013

In the field of computational game theory, games are often compared in terms of their size. This can be measured in several ways, including the number of unique game states, the number of decision points, and the total number of legal actions over all decision points. These numbers are either known or estimated for a wide range of classic games such as chess and checkers. In the stochastic and imperfect information game of poker, these sizes are easily computed in "limit" games which restrict the players' available actions, but until now had only been estimated for the more complicated "no-limit" variants. In this paper, we describe a simple algorithm for quickly computing the size of two-player no-limit poker games, provide an implementation of this algorithm, and present for the first time precise counts of the number of game states, information sets, actions and terminal nodes in the no-limit poker games played in the Annual Computer Poker Competition.
Syllogisms in Rudimentary Linear Logic, Diagrammatically
Venue: arXiv cs.LO 2013
Year: 2013

We present a reading of the traditional syllogistics in a fragment of the propositional intuitionistic multiplicative linear logic and prove that with respect to a diagrammatic logical calculus that we introduced in a previous paper, a syllogism is provable in such a fragment if and only if it is diagrammatically provable. We extend this result to syllogistics with complemented terms à la De Morgan, with respect to a suitable extension of the diagrammatic reasoning system for the traditional case and a corresponding reading of such De Morgan style syllogistics in the previously referred to fragment of linear logic.
The Rise and Fall of a Central Contributor: Dynamics of Social Organization and Performance in the Gentoo Community
Venue: arXiv cs.SE 2013
Year: 2013

Social organization and division of labor crucially influence the performance of collaborative software engineering efforts. In this paper, we provide a quantitative analysis of the relation between social organization and performance in Gentoo, an Open Source community developing a Linux distribution. We study the structure and dynamics of collaborations as recorded in the project's bug tracking system over a period of ten years. We identify a period of increasing centralization after which most interactions in the community were mediated by a single central contributor. In this period of maximum centralization, the central contributor unexpectedly left the project, thus posing a significant challenge for the community. We quantify how the rise, the activity as well as the subsequent sudden dropout of this central contributor affected both the social organization and the bug handling performance of the Gentoo community. We analyze social organization from the perspective of network theory and augment our quantitative findings by interviews with prominent members of the Gentoo community which shared their personal insights.
Modeling Stable Matching Problems with Answer Set Programming
Venue: arXiv cs.AI 2013
Year: 2013

The Stable Marriage Problem (SMP) is a well-known matching problem first introduced and solved by Gale and Shapley (1962). Several variants and extensions to this problem have since been investigated to cover a wider set of applications. Each time a new variant is considered, however, a new algorithm needs to be developed and implemented. As an alternative, in this paper we propose an encoding of the SMP using Answer Set Programming (ASP). Our encoding can easily be extended and adapted to the needs of specific applications. As an illustration we show how stable matchings can be found when individuals may designate unacceptable partners and ties between preferences are allowed. Subsequently, we show how our ASP based encoding naturally allows us to select specific stable matchings which are optimal according to a given criterion. Each time, we can rely on generic and efficient off-the-shelf answer set solvers to find (optimal) stable matchings.
Online Similarity Prediction of Networked Data from Known and Unknown Graphs
Venue: arXiv cs.LG 2013
Year: 2013

We consider online similarity prediction problems over networked data. We begin by relating this task to the more standard class prediction problem, showing that, given an arbitrary algorithm for class prediction, we can construct an algorithm for similarity prediction with "nearly" the same mistake bound, and vice versa. After noticing that this general construction is computationally infeasible, we target our study to {\em feasible} similarity prediction algorithms on networked data. We initially assume that the network structure is {\em known} to the learner. Here we observe that Matrix Winnow \cite{w07} has a near-optimal mistake guarantee, at the price of cubic prediction time per round. This motivates our effort for an efficient implementation of a Perceptron algorithm with a weaker mistake guarantee but with only poly-logarithmic prediction time. Our focus then turns to the challenging case of networks whose structure is initially {\em unknown} to the learner. In this novel setting, where the network structure is only incrementally revealed, we obtain a mistake-bounded algorithm with a quadratic prediction time per round.
A connection between concurrency and language theory
Venue: arXiv cs.LO 2013
Year: 2013

We show that three fixed point structures equipped with (sequential) composition, a sum operation, and a fixed point operation share the same valid equations. These are the theories of (context-free) languages, (regular) tree languages, and simulation equivalence classes of (regular) synchronization trees (or processes). The results reveal a close relationship between classical language theory and process algebra.
Tracking the Empirical Distribution of a Markov-modulated Duplication-Deletion Random Graph
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers a Markov-modulated duplication-deletion random graph where at each time instant, one node can either join or leave the network; the probabilities of joining or leaving evolve according to the realization of a finite state Markov chain. The paper comprises of 2 results. First, motivated by social network applications, we analyze the asymptotic behavior of the degree distribution of the Markov-modulated random graph. Using the asymptotic degree distribution, an expression is obtained for the delay in searching such graphs. Second, a stochastic approximation algorithm is presented to track empirical degree distribution as it evolves over time. The tracking performance of the algorithm is analyzed in terms of mean square error and a functional central limit theorem is presented for the asymptotic tracking error.
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
Venue: arXiv cs.CC 2013
Year: 2013

Mulmuley recently gave an explicit version of Noether's Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are deterministic black-box algorithms for polynomial identity testing (PIT). He argued that this gives evidence that constructing such algorithms for PIT is beyond current techniques. In this work, we show this is not the case. That is, we improve Mulmuley's reduction and correspondingly weaken the conjecture regarding PIT needed to give explicit Noether Normalization. We then observe that the weaker conjecture has recently been nearly settled by the authors, who gave quasipolynomial size hitting sets for the class of read-once oblivious algebraic branching programs (ROABPs). This gives the desired explicit Noether Normalization unconditionally, up to quasipolynomial factors. As a consequence of our proof we give a deterministic parallel polynomial-time algorithm for deciding if two matrix tuples have intersecting orbit closures, under simultaneous conjugation. We also study the strength of conjectures that Mulmuley requires to obtain similar results as ours. We prove that his conjectures are stronger, in the sense that the computational model he needs PIT algorithms for is equivalent to the well-known algebraic branching program (ABP) model, which is provably stronger than the ROABP model. Finally, we consider the depth-3 diagonal circuit model as defined by Saxena, as PIT algorithms for this model also have implications in Mulmuley's work. Previous work have given quasipolynomial size hitting sets for this model. In this work, we give a much simpler construction of such hitting sets, using techniques of Shpilka and Volkovich.
Half-Duplex or Full-Duplex Relaying: A Capacity Analysis under Self-Interference
Venue: arXiv cs.IT 2013
Year: 2013

In this paper multi-antenna half-duplex and full-duplex relaying are compared from the perspective of achievable rates. Full-duplexing operation requires additional resources at the relay such as antennas and RF chains for self-interference cancellation. Using a practical model for the residual self-interference, full-duplex achievable rates and degrees of freedom are computed for the cases for which the relay has the same number of antennas or the same number of RF chains as in the half-duplex case, and compared with their half-duplex counterparts. It is shown that power scaling at the relay is necessary to maximize the the degrees of freedom in the full-duplex mode.
Direct Proof of Security of Wegman-Carter Authentication with Partially Known Key
Venue: arXiv cs.CR 2013
Year: 2013

Information-theoretically secure (ITS) authentication is needed in Quantum Key Distribution (QKD). In this paper, we study security of an ITS authentication scheme proposed by Wegman & Carter, in the case of partially known authentication key. This scheme uses a new authentication key in each authentication attempt, to select a hash function from an Almost Strongly Universal$_2$ hash function family. The partial knowledge of the attacker is measured as the trace distance between the authentication key distribution and the uniform distribution; this is the usual measure in QKD. We provide direct proofs of security of the scheme, when using partially known key, first in the information-theoretic setting and then in terms of witness indistinguishability as used in the Universal Composability (UC) framework. We find that if the authentication procedure has a failure probability $ε$ and the authentication key has an $ε'$ trace distance to the uniform, then under ITS, the adversary's success probability conditioned on an authentic message-tag pair is only bounded by $ε+|\mT|ε'$, where $|\mT|$ is the size of the set of tags. Furthermore, the trace distance between the authentication key distribution and the uniform increases to $|\mT|ε'$ after having seen an authentic message-tag pair. Despite this, we are able to prove directly that the authenticated channel is indistinguishable from an (ideal) authentic channel (the desired functionality), except with probability less than $ε+ε'$. This proves that the scheme is ($ε+ε'$)-UC-secure, without using the composability theorem.
The Semantic Web takes Wing: Programming Ontologies with Tawny-OWL
Venue: arXiv cs.AI 2013
Year: 2013

The Tawny-OWL library provides a fully-programmatic environment for ontology building; it enables the use of a rich set of tools for ontology development, by recasting development as a form of programming. It is built in Clojure - a modern Lisp dialect, and is backed by the OWL API. Used simply, it has a similar syntax to OWL Manchester syntax, but it provides arbitrary extensibility and abstraction. It builds on existing facilities for Clojure, which provides a rich and modern programming tool chain, for versioning, distributed development, build, testing and continuous integration. In this paper, we describe the library, this environment and the its potential implications for the ontology development process.
Computable Compressed Matrices
Venue: arXiv cs.DS 2013
Year: 2013

The biggest cost of computing with large matrices in any modern computer is related to memory latency and bandwidth. The average latency of modern RAM reads is 150 times greater than a clock step of the processor. Throughput is a little better but still 25 times slower than the CPU can consume. The application of bitstring compression allows for larger matrices to be moved entirely to the cache memory of the computer, which has much better latency and bandwidth (average latency of L1 cache is 3 to 4 clock steps). This allows for massive performance gains as well as the ability to simulate much larger models efficiently. In this work, we propose a methodology to compress matrices in such a way that they retain their mathematical properties. Considerable compression of the data is also achieved in the process Thus allowing for the computation of much larger linear problems within the same memory constraints when compared with the traditional representation of matrices.
A Review On Securing Distributed Systems Using Symmetric Key Cryptography
Venue: arXiv cs.DC 2013
Year: 2013

This review is aimed to evaluate the importance of Symmetric Key Cryptography for Security in Distributed Systems. Businesses around the world as well as research and other such areas rely heavily on distributed systems these days. Hence, security is also a major concern due to the openness of the system. Out of the various available security measures, we, in this paper, concentrate in general on the symmetric key cryptographic technique. We review two widely used and popular symmetric key cryptographic algorithms, viz. DES and AES. These two algorithms are evaluated on the parameters such as key size, block size, number of iterations, etc.
Incremental Algorithms for Network Management and Analysis based on Closeness Centrality
Venue: arXiv cs.DS 2013
Year: 2013

Analyzing networks requires complex algorithms to extract meaningful information. Centrality metrics have shown to be correlated with the importance and loads of the nodes in network traffic. Here, we are interested in the problem of centrality-based network management. The problem has many applications such as verifying the robustness of the networks and controlling or improving the entity dissemination. It can be defined as finding a small set of topological network modifications which yield a desired closeness centrality configuration. As a fundamental building block to tackle that problem, we propose incremental algorithms which efficiently update the closeness centrality values upon changes in network topology, i.e., edge insertions and deletions. Our algorithms are proven to be efficient on many real-life networks, especially on small-world networks, which have a small diameter and a spike-shaped shortest distance distribution. In addition to closeness centrality, they can also be a great arsenal for the shortest-path-based management and analysis of the networks. We experimentally validate the efficiency of our algorithms on large networks and show that they update the closeness centrality values of the temporal DBLP-coauthorship network of 1.2 million users 460 times faster than it would take to compute them from scratch. To the best of our knowledge, this is the first work which can yield practical large-scale network management based on closeness centrality values.
Non-Asymptotic Output Statistics of Random Binning and Its Applications
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we develop a finite blocklength version of the Output Statistics of Random Binning (OSRB) framework. The framework is shown to be optimal in the point-to-point case. New second order regions for broadcast channel and wiretap channel with strong secrecy criterion are derived.
Low-complexity dominance-based Sphere Decoder for MIMO Systems
Venue: arXiv cs.IT 2013
Year: 2013

The sphere decoder (SD) is an attractive low-complexity alternative to maximum likelihood (ML) detection in a variety of communication systems. It is also employed in multiple-input multiple-output (MIMO) systems where the computational complexity of the optimum detector grows exponentially with the number of transmit antennas. We propose an enhanced version of the SD based on an additional cost function derived from conditions on worst case interference, that we call dominance conditions. The proposed detector, the king sphere decoder (KSD), has a computational complexity that results to be not larger than the complexity of the sphere decoder and numerical simulations show that the complexity reduction is usually quite significant.