We investigate the problem of mining numerical data with Formal Concept Analysis. The usual way is to use a scaling procedure —transforming numerical attributes into binary ones — leading either to a loss of information or of efficiency, in particular w.r.t. the volume of extracted patterns. By contrast, we propose to directly work on numerical data in a more precise and efficient way. For that, the notions of closed patterns, generators and equivalent classes are revisited in the numerical context. Moreover, two original algorithms are proposed and tested in an evaluation involving real-world data, showing the quality of the present approach.

ADOPT and BnB-ADOPT are two optimal DCOP search algorithms that are similar except for their search strategies: the former uses best-first search and the latter uses depth-first branch-and-bound search. In this paper, we present a new algorithm, called ADOPT( k ), that generalizes them. Its behavior depends on the k parameter. It behaves like ADOPT when k = 1, like BnB-ADOPT when k = ∞ and like a hybrid of ADOPT and BnB-ADOPT when 1 < k < ∞. We prove that ADOPT( k ) is a correct and complete algorithm and experimentally show that ADOPT( k ) outperforms ADOPT and BnB-ADOPT on several benchmarks across several metrics.

We present unsupervised approaches to the problem of modeling dialog acts in asynchronous conversations; i.e., conversations where participants collaborate with each other at different times. In particular, we investigate a graph-theoretic deterministic framework and two probabilistic conversation models (i.e., HMM and HMM+Mix) for modeling dialog acts in emails and forums. We train and test our conversation models on (a) temporal order and (b) graph-structural order of the datasets. Empirical evaluation suggests (i) the graph-theoretic framework that relies on lexical and structural similarity metrics is not the right model for this task, (ii) conversation models perform better on the graph-structural order than the temporal order of the datasets and (iii) HMM+Mix is a better conversation model than the simple HMM model.

We propose a new additive decomposition of probability tables that preserves equivalence of the joint distribution while reducing the size of potentials, without extra variables. We formulate the Most Probable Explanation (MPE) problem in belief networks as a Weighted Constraint Satisfaction Problem (WCSP). Our pairwise decomposition allows to replace a cost function with smaller-arity functions. The resulting pairwise decomposed WCSP is then easier to solve using state-of-the-art WCSP techniques. Although testing pairwise decomposition is equivalent to testing pairwise independence in the original belief network, we show how to efficiently test and enforce it, even in the presence of hard constraints. Furthermore, we infer additional information from the resulting nonbinary cost functions by projecting and subtracting them on binary functions. We observed huge improvements by preprocessing with pairwise decomposition and project&subtract compared to the current state-of-the-art solvers on two difficult sets of benchmark.

Computational social choice literature has successfully studied the complexity of manipulation in variousvoting systems. However, the existing modelsof coalitional manipulation view the manipulatingcoalition as an exogenous input, ignoring thequestion of the coalition formation process. While such analysis is useful as a first approximation, a richer framework is required to model voting manipulationin the real world more accurately, and, inparticular, to explain how a manipulating coalitionarises and chooses its action. In this paper, we apply tools from cooperative game theory to developa model that considers the coalition formation processand determines which coalitions are likely toform and what actions they are likely to take. We explore the computational complexity of several standard coalitional game theory solution concepts in our setting, and study the relationship betweenour model and the classic coalitional manipulation problem as well as the now-standard bribery model.

As more and more application areas require higher scalability, the study of fragments of expressive The high computational complexity of the expressive DLs with better computational properties has become an Description Logics (DLs) that underlie the important area of research. OWL standard has motivated the study of their Horn fragments of DLs, which are obtained by restricting Horn fragments, which are usually tractable in data the syntax of a DL in such a way that disjunction is not complexity and can also have lower combined complexity, expressible, were first considered in [Hustadt et al., 2005] particularly for query answering. In this paper as expressive fragments with tractable data complexity (see we provide algorithms for answering conjunctive also [Krötzsch et al., 2007]). It was later identified that they 2-way regular path queries (2CRPQs), a nontrivial can also exhibit lower combined complexity when it comes generalization of plain conjunctive queries, to query answering. Indeed, answering conjunctive queries in the Horn fragments of the DLs SHOIQ and (CQs), a kind of database-inspired queries that have become SROIQ underlying OWL 1 and OWL 2. We show the standard for querying DLs, is in ExpTime for the Horn that the combined complexity of the problem is ExpTime-complete fragment of the prominent SHIQ [Eiter et al., 2008], while it for Horn-SHOIQ and 2ExpTimecomplete is already 2ExpTime-hard for quite restricted (non Horn) fragments for the more expressive Horn-SROIQ, of SHIQ, like ALCI [Lutz, 2008] and SH [Eiter et but is PTime-complete in data complexity for both.

Many applications of causal inference, such as finding the relationship between stock prices and news reports, involve both discrete and continuous variables observed over time. Inference with these complex sets of temporal data, though, has remained difficult and required a number of simplifications. We show that recent approaches for inferring temporal relationships (represented as logical formulas) can be adapted for inference with continuous valued effects. Building on advances in logic, PCTLc (an extension of PCTL with numerical constraints) is introduced here to allow representation and inference of relationships with a mixture of discrete and continuous components. Then, finding significant relationships in the continuous case can be done using the conditional expectation of an effect, rather than its conditional probability. We evaluate this approach on both synthetically generated and actual financial market data, demonstrating that it can allow us to answer different questions than the discrete approach can.

Learning from Demonstration (LfD) is a popular technique for building decision-making agents from human help. Traditional LfD methods use demonstrations as training examples for supervised learning, but complex tasks can require more examples than is practical to obtain. We present Abstraction from Demonstration (AfD), a novel form of LfD that uses demonstrations to infer state abstractions and reinforcement learning (RL) methods in those abstract state spaces to build a policy. Empirical results show that AfD is greater than an order of magnitude more sample efficient than jus tusing demonstrations as training examples, and exponentially faster than RL alone.

Planning under uncertainty for multiagent systems can be formalized as a decentralized partially observable Markov decision process. We advance the state of the art for optimal solution of this model, building on the Multiagent A* heuristic search method. A key insight is that we can avoid the full expansion of a search node that generates a number of children that is doubly exponential in the node's depth. Instead, we incrementally expand the children only when a next child might have the highest heuristic value. We target a subsequent bottleneck by introducing a more memory-efficient representation for our heuristic functions. Proof is given that the resulting algorithm is correct and experiments demonstrate a significant speedup over the state of the art, allowing for optimal solutions over longer horizons for many benchmark problems.

The paper describes a method of relation extraction, which is based on parsing the input text using a combination of a generic HPSG-based grammar and a highly focused domain- and relation-specific lexicon. We also show a method of unsupervised acquisition of such a lexicon from a large unlabeled corpus. Together, the methods introduce a novel approach to the “Open IE” task, which is superior in accuracy and in quality of relation identification to the existing approaches.