Search

International audience; Constraint programming is used to model and solve complex combina- torial problems. The modeling task requires some expertise in constraint programming. This requirement is a bottleneck to the broader uptake of constraint technology. Several approaches have been proposed to assist the non-expert user in the modelling task. This paper presents the basic architecture for acquiring constraint networks from examples classified by the user. The theoretical questions raised by constraint acquisition are stated and their complexity is given. We then propose Conacq, a sys- tem that uses a concise representation of the learner’s version space into a clausal formula. Based on this logical representation, our architecture uses strategies for eliciting constraint networks in both the passive acquisition context, where the learner is only provided a pool of examples, and the active acquisition context, where the learner is allowed to ask membership queries to the user. The computational properties of our strategies are analyzed and their practical effectiveness is experimentally evaluated.

In this paper, we investigate the problem of sparse online linear classification in changing environments. We first analyze the tracking performance of standard online linear classifiers, which use gradient descent for minimizing the regularized hinge loss. The derived shifting bounds highlight the importance of choosing appropriate step sizes in the presence of concept drifts. Notably, we show that a better adaptability to concept drifts can be achieved using constant step sizes rather than the state-of-the-art decreasing step sizes. Based on these observations, we then propose a novel sparse approximated linear classifier, called sparse approximated linear classification (SALC), which uses a constant step size. In essence, SALC simply rounds small weights to zero for achieving sparsity and controls the truncation error in a principled way for achieving a low tracking regret. The degree of sparsity obtained by SALC is continuous and can be controlled by a parameter which captures the tradeoff between the sparsity of the model and the regret performance of the algorithm. Experiments on nine stationary data sets show that SALC is superior to the state-of-the-art sparse online learning algorithms, especially when the solution is required to be sparse; on seven groups of nonstationary data sets with various total shifting amounts, SALC also presents a good ability to track drifts. When wrapped with a drift detector, SALC achieves a remarkable tracking performance regardless of the total shifting amount.

International audience; Conditional preference networks (CP-nets) have recently emerged as a popular language capable of representing ordinal preference relations in a compact and structured manner. In this paper, we investigate the problem of learning CP-nets in the well-known model of exact identification with equivalence and membership queries. The goal is to identify a target preference ordering with a binary-valued CP-net by interacting with the user through a small number of queries. Each example supplied by the user or the learner is a preference statement on a pair of outcomes. In this model, we show that acyclic CP-nets are not learnable with equivalence queries alone, even if the examples are restricted to swaps for which dominance testing takes linear time. By contrast, acyclic CP-nets are what is called attribute-efficiently learnable when both equivalence queries and membership queries are available: we indeed provide a learning algorithm whose query complexity is linear in the description size of the target concept, but only logarithmic in the total number of attributes. Interestingly, similar properties are derived for tree-structured CP-nets in the presence of arbitrary examples. Our learning algorithms are shown to be quasi-optimal by deriving lower bounds on the VC-dimension of CP-nets. In a nutshell, our results reveal that active queries are required for efficiently learning CP-nets in large multi-attribute domains.

The challenge of General Game Playing (GGP) is to devise game playing programs that take as input the rules of any strategic game, described in the Game Description Language (GDL), and that effectively play without human intervention. The aim of this paper is to address the GGP challenge by casting GDL games (potentially with chance events) into the Stochastic Constraint Satisfaction Problem (SCSP). The stochastic constraint network of a game is decomposed into a sequence of µSCSPs (also know as one-stage SCSP), each associated with a game round. Winning strategies are searched by coupling the MAC (Maintaining Arc Consistency) algorithm, used to solve each µSCSP in turn, together with the UCB (Upper Confidence Bound) policy for approximating the values of those strategies obtained by the last µSCSP in the sequence. Extensive experiments conducted on various GDL games with different deliberation times per round, demonstrate that the MAC-UCB algorithm significantly outperforms the state-of-the-art UCT (Upper Confidence bounds for Trees) algorithm.

Much like relational probabilistic models, the need for relational preference models naturally arises in real-world applications involving multiple, heterogeneous, and richly interconnected objects. On the one hand, relational preferences should be represented into statements which are natural for human users to express. On the other hand, relational preference models should be endowed with a structure that supports tractable forms of reasoning and learning. Based on these criteria, this paper introduces the framework of relational conditional preference networks (RCP-nets), that maintains the spirit of the popular "CP-nets" by expressing relational preferences in a natural way using the ceteris paribus semantics. We show that acyclic RCP-nets support tractable inference for optimization and ranking tasks. In addition, we show that in the online learning model, tree-structured RCP-nets (with bipartite orderings) are efficiently learnable from both optimization tasks and ranking tasks, using linear loss functions. Our results are corroborated by experiments on a large-scale movie recommendation dataset.

International audience; A recurrent issue in decision making is to extract a preference structure by observing the user's behavior in different situations. In this paper, we investigate the problem of learning ordinal preference orderings over discrete multi-attribute, or combinatorial, domains. Specifically, we focus on the learnability issue of conditional preference networks, or CP- nets, that have recently emerged as a popular graphical language for representing ordinal preferences in a concise and intuitive manner. This paper provides results in both passive and active learning. In the passive setting, the learner aims at finding a CP-net compatible with a supplied set of examples, while in the active setting the learner searches for the cheapest interaction policy with the user for acquiring the target CP-net.

International audience; A recurrent problem in the development of reasoning agents is how to assign degrees of beliefs to uncertain events in a complex environment. The standard knowledge representation framework imposes a sharp separation between learning and reasoning; the agent starts by acquiring a “model” of its environment, represented into an expressive language, and then uses this model to quantify the likelihood of various queries. Yet, even for simple queries, the problem of evaluating probabilities from a general purpose representation is computationally prohibitive. In contrast, this study embarks on the learning to reason (L2R) framework that aims at eliciting degrees of belief in an inductive manner. The agent is viewed as an anytime reasoner that iteratively improves its performance in light of the knowledge induced from its mistakes. Indeed, by coupling exponentiated gradient strategies in learning and weighted model counting techniques in reasoning, the L2R framework is shown to provide efficient solutions to relational probabilistic reasoning problems that are provably intractable in the classical paradigm.

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.

Online learning algorithms such as Winnow have received much attention in Machine Learning. Their performance degrades only logarithmically with the input dimension, making them useful in large spaces such as relational theories. However, online first-order learners are intrinsically limited by a computational barrier: even in the finite, function-free case, the number of possible features grows exponentially with the number of first-order atoms generated from the vocabulary. To circumvent this issue, we exploit the paradigm of closure-based learning which allows the learner to focus on the features that lie in the closure space generated from the examples which have lead to a mistake. Based on this idea, we develop an online algorithm for learning theories formed by disjunctions of existentially quantified conjunctions of atoms. In this setting, we show that the number of mistakes depends only logarithmically on the number of features. Furthermore, the computational cost is essentially bounded by the size of the closure lattice.

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.

also took place at San Sebastian (Spain); International audience; A student is facing a teacher, who is probing her knowledge of mathematics. The student is a new recruit and important questions must be answered: What are her strengths and weakness ? Which topics is she ready to study ? Should the student take a remedial course in some subject ? The teacher will ask a question and listen to the student’s response. Other questions will then be asked. After a few questions, a picture of the student’s state of knowledge will emerge, which will become increasingly sharper in the course of the examination.

International audience; It has long been recognized that the concept of inconsistency is a central part of com-monsense reasoning. In this issue, a number of authors have explored the idea of reasoning with maximal consistent subsets of an inconsistent stratified knowledge base. This paradigm, often called "coherent-based reasoning", has resulted in some interesting proposals for para-consistent reasoning, non-monotonic reasoning, and argumentation systems. Unfortunately, coherent-based reasoning is computationally very expensive. This paper harnesses the approach of approximate entailment by Schaerf and Cadoli [SCH 95] to develop the concept of "approximate coherent-based reasoning". To this end, we begin to present a multi-modal propo-sitional logic that incorporates two dual families of modalities: 2S and 3S defined for each subset S of the set of atomic propositions. The resource parameter S indicates what atoms are taken into account when evaluating formulas. Next, we define resource-bounded consolidation operations that limit and control the generation of maximal consistent subsets of a stratified knowledge base. Then, we present counterparts to existential, universal, and argumentative inference that are prominent in coherence-based approaches. By virtue of modalities 2S and 3S, these inferences are approximated from below and from above, in an incremental fashion. Based on these features, we show that an anytime view of coherent-based reasoning is tenable.

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.

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.