OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Step Regression Learning for Compositional Distributional Semantics
Venue: arXiv cs.CL 2013
Year: 2013

We present a model for compositional distributional semantics related to the framework of Coecke et al. (2010), and emulating formal semantics by representing functions as tensors and arguments as vectors. We introduce a new learning method for tensors, generalising the approach of Baroni and Zamparelli (2010). We evaluate it on two benchmark data sets, and find it to outperform existing leading methods. We argue in our analysis that the nature of this learning method also renders it suitable for solving more subtle problems compositional distributional models might face.
Quantifying Morphological Computation
Venue: arXiv cs.AI 2013
Year: 2013

The field of embodied intelligence emphasises the importance of the morphology and environment with respect to the behaviour of a cognitive system. The contribution of the morphology to the behaviour, commonly known as morphological computation, is well-recognised in this community. We believe that the field would benefit from a formalisation of this concept as we would like to ask how much the morphology and the environment contribute to an embodied agent's behaviour, or how an embodied agent can maximise the exploitation of its morphology within its environment. In this work we derive two concepts of measuring morphological computation, and we discuss their relation to the Information Bottleneck Method. The first concepts asks how much the world contributes to the overall behaviour and the second concept asks how much the agent's action contributes to a behaviour. Various measures are derived from the concepts and validated in two experiments which highlight their strengths and weaknesses.
Towards Optimal Broadcast in Wireless Networks
Venue: arXiv cs.NI 2013
Year: 2013

Broadcast is a fundamental operation in networks, especially in wireless Mobile Ad Hoc NETworks (MANET). For example, some form of broadcasting is used by all on-demand MANET routing protocols, when there is uncertainty as to the location of the destination node, or for service discovery. Being such a basic operation of the networking protocols, the importance of efficient broadcasting has long been recognized by the networking community. Numerous papers proposed increasingly more efficient implementation of broadcasting, while other studies presented bounds on broadcast performance. In this work, we present a new approach to efficient broadcast in networks with dynamic topologies, such as MANET, and we introduce a new broadcasting algorithm for such networking environments. We evaluate our algorithm, showing that its performance comes remarkably close to the corresponding theoretical performance bounds, even in the presence of packet loss due to, for example, MAC-layer collisions. Furthermore, we compare the performance of the proposed algorithm with other recently proposed schemes, including in various mobility settings.
Data Analysis on the High-Frequency Pollution Data Collected in India
Venue: arXiv cs.OH 2013
Year: 2013

Fine grained 1Hz Carbon Monoxide pollution data were collected on a busy road in Hyderabad, India. In this paper we report the findings from analysing the experimental data, in which it was found that the data were log-normally distributed and nonlinear. The dominant frequencies at peak hours were caused by the pattern of traffic flow.
On the Semantics and Automated Deduction for PLFC, a Logic of Possibilistic Uncertainty and Fuzziness
Venue: arXiv cs.AI 2013
Year: 2013

Possibilistic logic is a well-known graded logic of uncertainty suitable to reason under incomplete information and partially inconsistent knowledge, which is built upon classical first order logic. There exists for Possibilistic logic a proof procedure based on a refutation complete resolution-style calculus. Recently, a syntactical extension of first order Possibilistic logic (called PLFC) dealing with fuzzy constants and fuzzily restricted quantifiers has been proposed. Our aim is to present steps towards both the formalization of PLFC itself and an automated deduction system for it by (i) providing a formal semantics; (ii) defining a sound resolution-style calculus by refutation; and (iii) describing a first-order proof procedure for PLFC clauses based on (ii) and on a novel notion of most general substitution of two literals in a resolution step. In contrast to standard Possibilistic logic semantics, truth-evaluation of formulas with fuzzy constants are many-valued instead of boolean, and consequently an extended notion of possibilistic uncertainty is also needed.
Decentralized Minimum-Cost Repair for Distributed Storage Systems
Venue: arXiv cs.IT 2013
Year: 2013

There have been emerging lots of applications for distributed storage systems e.g., those in wireless sensor networks or cloud storage. Since storage nodes in wireless sensor networks have limited battery, it is valuable to find a repair scheme with optimal transmission costs (e.g., energy). The optimal-cost repair has been recently investigated in a centralized way. However a centralized control mechanism may not be available or is very expensive. For the scenarios, it is interesting to study optimal-cost repair in a decentralized setup. We formulate the optimal-cost repair as convex optimization problems for the network with convex transmission costs. Then we use primal and dual decomposition approaches to decouple the problem into subproblems to be solved locally. Thus, each surviving node, collaborating with other nodes, can minimize its transmission cost such that the global cost is minimized. We further study the optimality and convergence of the algorithms. Finally, we discuss the code construction and determine the field size for finding feasible network codes in our approaches.
The phase transition in inhomogeneous random intersection graphs
Venue: arXiv cs.DM 2013
Year: 2013

We analyze the component evolution in inhomogeneous random intersection graphs when the average degree is close to 1. As the average degree increases, the size of the largest component in the random intersection graph goes through a phase transition. We give bounds on the size of the largest components before and after this transition. We also prove that the largest component after the transition is unique. These results are similar to the phase transition in Erdős-Rényi random graphs; one notable difference is that the jump in the size of the largest component varies in size depending on the parameters of the random intersection graph.
Codes on Lattices for Random SAF Routing
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, a construction of constant weight codes based on the unique decomposition of elements in lattices is presented. The conditions for unique primary decomposition and unique irreducible decomposition in lattices are discussed and connections with the decomposition of ideals in Noetherian commutative rings established. In this context it is shown, drawing on the definitive works of Dilworth, Ward and others, that, as opposed to Noetherian commutative rings, the existence of unique irreducible decomposition in lattices does not guarantee unique primary decomposition. The source alphabet in our proposed construction is a set of uniquely decomposable elements constructed from a chosen subset of irreducible or primary elements of the appropriate lattice. The distance function between two lattice elements is based on the symmetric distance between sets of constituent elements. It is known that constructing such constant weight codes is equivalent to constructing a Johnson graph with appropriate parameters. Some bounds on the code sizes are also presented and a method to obtain codes of optimal size, utilizing the Johnson graph description of the codes, is discussed. As an application we show how these codes can be used for error and erasure correction in random networks employing store-and-forward (SAF) routing.
Structured Reachability Analysis for Markov Decision Processes
Venue: arXiv cs.AI 2013
Year: 2013

Recent research in decision theoretic planning has focussed on making the solution of Markov decision processes (MDPs) more feasible. We develop a family of algorithms for structured reachability analysis of MDPs that are suitable when an initial state (or set of states) is known. Using compact, structured representations of MDPs (e.g., Bayesian networks), our methods, which vary in the tradeoff between complexity and accuracy, produce structured descriptions of (estimated) reachable states that can be used to eliminate variables or variable values from the problem description, reducing the size of the MDP and making it easier to solve. One contribution of our work is the extension of ideas from GRAPHPLAN to deal with the distributed nature of action representations typically embodied within Bayes nets and the problem of correlated action effects. We also demonstrate that our algorithm can be made more complete by using k-ary constraints instead of binary constraints. Another contribution is the illustration of how the compact representation of reachability constraints can be exploited by several existing (exact and approximate) abstraction algorithms for MDPs.
Query Expansion in Information Retrieval Systems using a Bayesian Network-Based Thesaurus
Venue: arXiv cs.IR 2013
Year: 2013

Information Retrieval (IR) is concerned with the identification of documents in a collection that are relevant to a given information need, usually represented as a query containing terms or keywords, which are supposed to be a good description of what the user is looking for. IR systems may improve their effectiveness (i.e., increasing the number of relevant documents retrieved) by using a process of query expansion, which automatically adds new terms to the original query posed by an user. In this paper we develop a method of query expansion based on Bayesian networks. Using a learning algorithm, we construct a Bayesian network that represents some of the relationships among the terms appearing in a given document collection; this network is then used as a thesaurus (specific for that collection). We also report the results obtained by our method on three standard test collections.
Dealing with Uncertainty in Situation Assessment: towards a Symbolic Approach
Venue: arXiv cs.AI 2013
Year: 2013

The situation assessment problem is considered, in terms of object, condition, activity, and plan recognition, based on data coming from the real-word {em via} various sensors. It is shown that uncertainty issues are linked both to the models and to the matching algorithm. Three different types of uncertainties are identified, and within each one, the numerical and the symbolic cases are distinguished. The emphasis is then put on purely symbolic uncertainties: it is shown that they can be dealt with within a purely symbolic framework resulting from a transposition of classical numerical estimation tools.
Marginalizing in Undirected Graph and Hypergraph Models
Venue: arXiv cs.AI 2013
Year: 2013

Given an undirected graph G or hypergraph X model for a given set of variables V, we introduce two marginalization operators for obtaining the undirected graph GA or hypergraph HA associated with a given subset A c V such that the marginal distribution of A factorizes according to GA or HA, respectively. Finally, we illustrate the method by its application to some practical examples. With them we show that hypergraph models allow defining a finer factorization or performing a more precise conditional independence analysis than undirected graph models.
Minimum Encoding Approaches for Predictive Modeling
Venue: arXiv cs.LG 2013
Year: 2013

We analyze differences between two information-theoretically motivated approaches to statistical inference and model selection: the Minimum Description Length (MDL) principle, and the Minimum Message Length (MML) principle. Based on this analysis, we present two revised versions of MML: a pointwise estimator which gives the MML-optimal single parameter model, and a volumewise estimator which gives the MML-optimal region in the parameter space. Our empirical results suggest that with small data sets, the MDL approach yields more accurate predictions than the MML estimators. The empirical results also demonstrate that the revised MML estimators introduced here perform better than the original MML estimator suggested by Wallace and Freeman.
An Anytime Algorithm for Decision Making under Uncertainty
Venue: arXiv cs.AI 2013
Year: 2013

We present an anytime algorithm which computes policies for decision problems represented as multi-stage influence diagrams. Our algorithm constructs policies incrementally, starting from a policy which makes no use of the available information. The incremental process constructs policies which includes more of the information available to the decision maker at each step. While the process converges to the optimal policy, our approach is designed for situations in which computing the optimal policy is infeasible. We provide examples of the process on several large decision problems, showing that, for these examples, the process constructs valuable (but sub-optimal) policies before the optimal policy would be available by traditional methods.
Using Qualitative Relationships for Bounding Probability Distributions
Venue: arXiv cs.AI 2013
Year: 2013

We exploit qualitative probabilistic relationships among variables for computing bounds of conditional probability distributions of interest in Bayesian networks. Using the signs of qualitative relationships, we can implement abstraction operations that are guaranteed to bound the distributions of interest in the desired direction. By evaluating incrementally improved approximate networks, our algorithm obtains monotonically tightening bounds that converge to exact distributions. For supermodular utility functions, the tightening bounds monotonically reduce the set of admissible decision alternatives as well.
Resolving Conflicting Arguments under Uncertainties
Venue: arXiv cs.AI 2013
Year: 2013

Distributed knowledge based applications in open domain rely on common sense information which is bound to be uncertain and incomplete. To draw the useful conclusions from ambiguous data, one must address uncertainties and conflicts incurred in a holistic view. No integrated frameworks are viable without an in-depth analysis of conflicts incurred by uncertainties. In this paper, we give such an analysis and based on the result, propose an integrated framework. Our framework extends definite argumentation theory to model uncertainty. It supports three views over conflicting and uncertain knowledge. Thus, knowledge engineers can draw different conclusions depending on the application context (i.e. view). We also give an illustrative example on strategical decision support to show the practical usefulness of our framework.
Logarithmic Time Parallel Bayesian Inference
Venue: arXiv cs.AI 2013
Year: 2013

I present a parallel algorithm for exact probabilistic inference in Bayesian networks. For polytree networks with n variables, the worst-case time complexity is O(log n) on a CREW PRAM (concurrent-read, exclusive-write parallel random-access machine) with n processors, for any constant number of evidence variables. For arbitrary networks, the time complexity is O(r^{3w}*log n) for n processors, or O(w*log n) for r^{3w}*n processors, where r is the maximum range of any variable, and w is the induced width (the maximum clique size), after moralizing and triangulating the network.
Context-Specific Approximation in Probabilistic Inference
Venue: arXiv cs.AI 2013
Year: 2013

There is evidence that the numbers in probabilistic inference don't really matter. This paper considers the idea that we can make a probabilistic model simpler by making fewer distinctions. Unfortunately, the level of a Bayesian network seems too coarse; it is unlikely that a parent will make little difference for all values of the other parents. In this paper we consider an approximation scheme where distinctions can be ignored in some contexts, but not in other contexts. We elaborate on a notion of a parent context that allows a structured context-specific decomposition of a probability distribution and the associated probabilistic inference scheme called probabilistic partial evaluation (Poole 1997). This paper shows a way to simplify a probabilistic model by ignoring distinctions which have similar probabilities, a method to exploit the simpler model, a bound on the resulting errors, and some preliminary empirical results on simple networks.
On the Geometry of Bayesian Graphical Models with Hidden Variables
Venue: arXiv cs.LG 2013
Year: 2013

In this paper we investigate the geometry of the likelihood of the unknown parameters in a simple class of Bayesian directed graphs with hidden variables. This enables us, before any numerical algorithms are employed, to obtain certain insights in the nature of the unidentifiability inherent in such models, the way posterior densities will be sensitive to prior densities and the typical geometrical form these posterior densities might take. Many of these insights carry over into more complicated Bayesian networks with systematic missing data.
Opinion Maximization in Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

The process of opinion formation through synthesis and contrast of different viewpoints has been the subject of many studies in economics and social sciences. Today, this process manifests itself also in online social networks and social media. The key characteristic of successful promotion campaigns is that they take into consideration such opinion-formation dynamics in order to create a overall favorable opinion about a specific information item, such as a person, a product, or an idea. In this paper, we adopt a well-established model for social-opinion dynamics and formalize the campaign-design problem as the problem of identifying a set of target individuals whose positive opinion about an information item will maximize the overall positive opinion for the item in the social network. We call this problem CAMPAIGN. We study the complexity of the CAMPAIGN problem, and design algorithms for solving it. Our experiments on real data demonstrate the efficiency and practical utility of our algorithms.
Multiset Codes for Permutation Channels
Venue: arXiv cs.IT 2013
Year: 2013

This paper introduces the notion of multiset codes as relevant to the problem of reliable information transmission over permutation channels. The motivation for studying permutation channels comes from the effect of out of order delivery of packets in some types of packet networks. The proposed codes are a generalization of the so-called subset codes, recently proposed by the authors. Some of the basic properties of multiset codes are established, among which their equivalence to integer codes under the Manhattan metric. The presented coding-theoretic framework follows closely the one proposed by Koetter and Kschischang for the operator channels. The two mathematical models are similar in many respects, and the basic idea is presented in a way which admits a unified view on coding for these types of channels.
Paradoxes in Social Networks with Multiple Products
Venue: arXiv cs.GT 2013
Year: 2013

Recently, we introduced in arXiv:1105.2434 a model for product adoption in social networks with multiple products, where the agents, influenced by their neighbours, can adopt one out of several alternatives. We identify and analyze here four types of paradoxes that can arise in these networks. To this end, we use social network games that we recently introduced in arxiv:1202.2209. These paradoxes shed light on possible inefficiencies arising when one modifies the sets of products available to the agents forming a social network. One of the paradoxes corresponds to the well-known Braess paradox in congestion games and shows that by adding more choices to a node, the network may end up in a situation that is worse for everybody. We exhibit a dual version of this, where removing available choices from someone can eventually make everybody better off. The other paradoxes that we identify show that by adding or removing a product from the choice set of some node may lead to permanent instability. Finally, we also identify conditions under which some of these paradoxes cannot arise.
Energy-Efficient Power Allocation in OFDM Systems with Wireless Information and Power Transfer
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers an orthogonal frequency division multiplexing (OFDM) downlink point-to-point system with simultaneous wireless information and power transfer. It is assumed that the receiver is able to harvest energy from noise, interference, and the desired signals. We study the design of power allocation algorithms maximizing the energy efficiency of data transmission (bit/Joule delivered to the receiver). In particular, the algorithm design is formulated as a high-dimensional non-convex optimization problem which takes into account the circuit power consumption, the minimum required data rate, and a constraint on the minimum power delivered to the receiver. Subsequently, by exploiting the properties of nonlinear fractional programming, the considered non-convex optimization problem, whose objective function is in fractional form, is transformed into an equivalent optimization problem having an objective function in subtractive form, which enables the derivation of an efficient iterative power allocation algorithm. In each iteration, the optimal power allocation solution is derived based on dual decomposition and a one-dimensional search. Simulation results illustrate that the proposed iterative power allocation algorithm converges to the optimal solution, and unveil the trade-off between energy efficiency, system capacity, and wireless power transfer: (1) In the low transmit power regime, maximizing the system capacity may maximize the energy efficiency. (2) Wireless power transfer can enhance the energy efficiency, especially in the interference limited regime.
Approximate Optimal Trajectory Tracking for Continuous Time Nonlinear Systems
Venue: arXiv cs.SY 2013
Year: 2013

Approximate dynamic programming has been investigated and used as a method to approximately solve optimal regulation problems. However, the extension of this technique to optimal tracking problems for continuous time nonlinear systems has remained a non-trivial open problem. The control development in this paper guarantees ultimately bounded tracking of a desired trajectory, while also ensuring that the controller converges to an approximate optimal policy.
Extending the logical update view with transaction support
Venue: arXiv cs.PL 2013
Year: 2013

Since the database update view was standardised in the Prolog ISO standard, the so called logical update view is available in all actively maintained Prolog systems. While this update view provided a well defined update semantics and allows for efficient handling of dynamic code, it does not help in maintaining consistency of the dynamic database. With the introduction of multiple threads and deployment of Prolog in continuously running server applications, consistency of the dynamic database becomes important. In this article, we propose an extension to the generation-based implementation of the logical update view that supports transactions. Generation-based transactions have been implemented according to this description in the SWI-Prolog RDF store. The aim of this paper is to motivate transactions, outline an implementation and generate discussion on the desirable semantics and interface prior to implementation.