We introduce a setting for learning possibilistic logic theories from defaults of the form "if alpha then typically beta". We first analyse this problem from the point of view of machine learning theory, determining the VC dimension of possibilistic stratifications as well as the complexity of the associated learning problems, after which we present a heuristic learning algorithm that can easily scale to thousands of defaults. An important property of our approach is that it is inherently able to handle noisy and conflicting sets of defaults. Among others, this allows us to learn possibilistic logic theories from crowdsourced data and to approximate propositional Markov logic networks using heuristic MAP solvers. We present experimental results that demonstrate the effectiveness of this approach.
Reasoning with defaults of the form if @math then typically @math '', denoted as @math , has been widely studied @cite_2 @cite_0 @cite_8 @cite_14 @cite_27 @cite_23 . A central problem in this context is to determine what other defaults can be derived from a given input set. Note, however, that the existing approaches for reasoning about default rules all require some form of consistency (e.g. the input set cannot contain both @math and @math ). As a result, these approaches cannot directly be used for reasoning about noisy crowdsourced defaults.
@cite_14 @cite_8 @cite_0 @cite_27 @cite_23 @cite_2
2035416838 2167907160 2143336154 2136661655 2003374324 2080142817
Abstract In recent years, two conceptually different interpretations of default expressions have been advanced: extensional interpretations, in which defaults are regarded as prescriptions for extending one's set of beliefs, and conditional interpretations, in which defaults are regarded as beliefs whose validity is bound to a particular context. The two interpretations possess virtues and limitations that are practically orthogonal to each other. The conditional interpretations successfully resolve arguments of different “specificity” (e.g., “penguins don't fly in spite of being birds”) but fail to capture arguments of “irrelevance” (e.g., concluding “ red birds fly” from “birds fly”). The opposite is true for the extensional interpretations. This paper develops a new account of defaults, called conditional entailment , which combines the benefits of the two interpretations. Like prioritized circumscriptions, conditional entailment resolves arguments by enforcing priorities among defaults. However, instead of having to be specified by the user, these priorities are extracted automatically from the knowledge base. Similarly, conditional entailment possesses a sound and complete proof theory, based on interacting arguments and amenable to implementation in conventional ATMSs. Abstract This paper presents a logical approach to nonmonotonic reasoning based on the notion of a nonmonotonic consequence relation. A conditional knowledge base, consisting of a set of conditional assertions of the type if … then … , represents the explicit defeasible knowledge an agent has about the way the world generally behaves. We look for a plausible definition of the set of all conditional assertions entailed by a conditional knowledge base. In a previous paper, Kraus and the authors defined and studied preferential consequence relations. They noticed that not all preferential relations could be considered as reasonable inference procedures. This paper studies a more restricted class of consequence relations, rational relations. It is argued that any reasonable nonmonotonic inference procedure should define a rational relation. It is shown that the rational relations are exactly those that may be represented by a ranked preferential model, or by a (nonstandard) probabilistic model. The rational closure of a conditional knowledge base is defined and shown to provide an attractive answer to the question of the title. Global properties of this closure operation are proved: it is a cumulative operation. It is also computationally tractable. This paper assumes the underlying language is propositional. Recent progress towards unifying the probabilistic and preferential models semantics for non-monotonic reasoning has led to a remarkable observation: Any consistent system of default rules imposes an unambiguous and natural ordering on these rules which, to emphasize its simple and basic character, we term "Z-ordering." This ordering can be used with various levels of refinement, to prioritize conflicting arguments, to rank the degree of abnormality of states of the world, and to define plausible consequence relationships. This paper defines the Z-ordering, briefly mentions its semantical origins, and illustrates two simple entailment relationships induced by the ordering. Two extensions are then described, maximum-entropy and conditional entailment, which trade in computational simplicity for semantic refinements. An approach to nonmonotonic reasoning that combines the principle of infinitesimal probabilities with that of maximum entropy, thus extending the inferential power of the probabilistic interpretation of defaults, is proposed. A precise formalization of the consequences entailed by a conditional knowledge base is provided, the computational machinery necessary for drawing these consequences is developed, and the behavior of the maximum entropy approach is compared to related work in default reasoning. The resulting formalism offers a compromise between two extremes: the cautious approach based on the conditional interpretations of defaults and the bold approach based on minimizing abnormalities. > Abstract This short paper relates the conditional object-based and possibility theory-based approaches for reasoning with conditional statements pervaded with exceptions, to other methods in nonmonotonic reasoning which have been independently proposed: namely, Lehmann's preferential and rational closure entailments which obey normative postulates, the infinitesimal probability approach, and the conditional (modal) logics-based approach. All these methods are shown to be equivalent with respect to their capabilities for reasoning with conditional knowledge although they are based on different modeling frameworks. It thus provides a unified understanding of nonmonotonic consequence relations. More particularly, conditional objects, a purely qualitative counterpart to conditional probabilities, offer a very simple semantics, based on a 3-valued calculus, for the preferential entailment, while in the purely ordinal setting of possibility theory both the preferential and the rational closure entailments can be represented. Abstract Many systems that exhibit nonmonotonic behavior have been described and studied already in the literature. The general notion of nonmonotonic reasoning, though, has almost always been described only negatively, by the property it does not enjoy, i.e. monotonicity. We study here general patterns of nonmonotonic reasoning and try to isolate properties that could help us map the field of nonmonotonic reasoning by reference to positive properties. We concentrate on a number of families of nonmonotonic consequence relations, defined in the style of Gentzen [13]. Both proof-theoretic and semantic points of view are developed in parallel. The former point of view was pioneered by Gabbay [10], while the latter has been advocated by Shoham [38]. Five such families are defined and characterized by representation theorems, relating the two points of view. One of the families of interest, that of preferential relations, turns out to have been studied by Adams [2]. The preferential models proposed here are a much stronger tool than Adams' probabilistic semantics. The basic language used in this paper is that of propositional logic. The extension of our results to first-order predicate calculi and the study of the computational complexity of the decision problems described in this paper will be treated in another paper.