Search

As uncertainty pervades the real world, it seems obvious that the decisions we make, the conclusions we reach, and the explanations we offer are usually based on our judgements of the probability of uncertain events such as success in a new medical treatment or the state of the market. For example, if an agent wishes to employ the expected-utility paradigm of decision theory in order to guide its actions, it must assign subjective probabilities to various assertions. Less obvious, however, is the question of how to elicit such degrees of beliefs.

Constraint programming is rapidly becoming the technology of choice for modelling and solving complex combinatorial problems. However, users of this technology need significant expertise in order to model their problems appropriately. The lack of availability of such expertise is a significant bottleneck to the broader uptake of constraint technology in the real world. We present a new SAT-based version space algorithm for acquiring constraint satisfaction problems from examples of solutions and non-solutions of a target problem. An important advantage is the ease with which domain-specific knowledge can be exploited using the new algorithm. Finally, we empirically demonstrate the algorithm and the effect of exploiting domain-specific knowledge on improving the quality of the acquired constraint network.

International audience; A central issue in logical concept induction is the prospect of inconsistency. This problem may arise due to noise in the training data, or because the target concept does not fit the underlying concept class. In this paper, we introduce the paradigm of inductive belief merging which handles this issue within a uniform framework. The key idea is to base learning on a belief merging operator that selects the concepts which are as close as possible to the set of training examples. From a computational perspective, we apply this paradigm to robust k-DNF learning. To this end, we develop a greedy algorithm which approximates the optimal concepts to within a logarithmic factor. The time complexity of the algorithm is polynomial in the size of k. Moreover, the method bidirectional and returns one maximally specific concept and one maximally general concept. We present experimental results showing the effectiveness of our algorithm on both nominal and numerical datasets.

In classical approaches to knowledge representation, reasoners are assumed to derive all the logical consequences of their knowledge base. As a result, reasoning in the first-order case is only semi-decidable. Even in the restricted case of finite universes of discourse, reasoning remains inherently intractable, as the reasoner has to deal with two independent sources of complexity: unbounded chaining and unbounded quantification. The purpose of this study is to handle these difficulties in a logic-oriented framework based on the paradigm of approximate reasoning. The logic is semantically founded on the notion of resource, an accuracy measure, which controls at the same time the two barriers of complexity. Moreover, a stepwise technique is included for improving approximations. Finally, both sound approximations and complete ones are covered. Based on the logic, we develop an approximation algorithm with a simple modification of classical instance-based theorem provers. The procedure yields approximate proofs whose precision increases as the reasoner has more resources at her disposal. The algorithm is interruptible, improvable, dual, and can be exploited for anytime computation. Moreover, the algorithm is flexible enough to be used with a wide range of propositional satisfiability methods.

A great deal of research has been devoted to nontrivial reasoning in inconsistent knowledge bases. Coherence-based approaches proceed by a consolidation operation which selects several consistent subsets of the knowledge base and an entailment operation which uses classical implication on these subsets in order to conclude. An important advantage of these formalisms is their flexibility: consolidation operations can take into account the priorities of declarations stored in the base, and different entailment operations can be distinguished according to the cautiousness of reasoning. However, one of the main drawbacks of these approaches is their high computational complexity. The purpose of our study is to define a logical framework which handles this difficulty by introducing the concepts of anytime consolidation and anytime entailment. The framework is semantically founded on the notion of resource which captures both the accuracy and the computational cost of anytime operations. Moreover, a stepwise procedure is included for improving approximations. Finally, both sound approximations and complete ones are covered. Based on these properties, we show that an anytime view of coherence-based reasoning is tenable.

One of the main characteristics of reasoning in knowledge based systems is its high computational complexity. Anytime deduction and anytime compilation are two attractive approaches that have been proposed for addressing such a difficulty. The first one offers a compromise between the time complexity needed to compute approximate answers and the quality of these answers. The second one proposes a trade-off between the space complexity of the compiled theory and the number of possible answers it can efficiently process. The purpose of our study is to define a logic which handles these two approaches by incorporating several major features. First, the logic is semantically founded on the notion of resource which captures both the accuracy and the cost of approximation. Second, a stepwise procedure is included for improving approximate answers. Third, both sound approximations and complete ones are covered. Fourth and finally, the reasoning task may be done off-line and compiled theories can be used for answering many queries.

Just as cooperation in multi-agent systems is a central issue for solving complex decision problems, so too is the ability for an intelligent agent to reason about combined knowledge, coming from its background knowledge and the communicated information. Specifically, such an agent is confronted with three main difficulties: the prospect of inconsistency which arises when different beliefs are grouped together, the presence of uncertainty which may occur due to not fully reliable beliefs, and the high computational complexity of reasoning with very large pools of collected information. The purpose of this paper is to define a formal framework which handles these three aspects and which is useful to specify resource bounded agents. Based on the concept of approximate reasoning, our framework includes several major features. First, a model checking approach is advocated, which enables an agent to perform decidable reasoning with a first-order representation language. Second, a stepwise procedure is included for improving approximate answers and allowing their convergence to the correct answer. Third and finally, both sound approximations and complete ones are covered. This method is flexible enough for modeling tractable reasoning in very large, inconsistent and uncertain sets of knowledge.