Learning Possibilistic Logic Theories from Default Rules

1 Introduction

Structured information plays an increasingly important role in applications such as information extraction [Dong et al., 2014], question answering [Kalyanpur et al., 2012] and robotics [Beetz et al., 2011]. With the notable exceptions of CYC and WordNet, most of the knowledge bases that are used in such applications have at least partially been obtained using some form of crowdsourcing (e.g. Freebase, Wikidata, ConceptNet). To date, such knowledge bases are mostly limited to facts (e.g. Obama is the current president of the US) and simple taxonomic relationships (e.g. every president is a human). One of the main barriers to crowdsourcing more complex domain theories is that most users are not trained in logic. This is exacerbated by the fact that often (commonsense) domain knowledge is easiest to formalize as defaults (e.g. birds typically fly), and, even for non-monotonic reasoning (NMR) experts, it can be challenging to formulate sets of default rules without introducing inconsistencies (w.r.t. a given NMR semantics) or unintended consequences.

In this paper, we propose a method for learning consistent domain theories from crowdsourced examples of defaults and non-defaults. Since these examples are provided by different users, who may only have an intuitive understanding of the semantics of defaults, together they will typically be inconsistent. The problem we consider is to construct a set of defaults Steven Schockaert Cardiff University, UK SchockaertS1@cardiff.ac.uk which is consistent w.r.t. the System P semantics [Kraus et al., 1990], and which entails as many of the given defaults and as few of the non-defaults as possible. Taking advantage of the relation between System P and possibilistic logic [Benferhat et al., 1997], we treat this as a learning problem, in which we need to select and stratify a set of propositional formulas.

The contributions of this paper are as follows. First, we show that the problem of deciding whether a possibilistic logic theory exists that perfectly covers all positive and negative examples is ⌃P2 -complete. Second, we formally study the problem of learning from defaults in a standard learning theory setting and we determine the corresponding VCdimension, which allows us to derive theoretical bounds on how much training data we need, on average, to obtain a system that can classify defaults as being valid or invalid with a given accuracy level. Third, we introduce a heuristic algorithm for learning possibilistic logic theories from defaults and non-defaults. To the best of our knowledge, our method is the first that can learn a consistent logical theory from a set of noisy defaults. We evaluate the performance of this algorithm in two crowdsourcing experiments. In addition, we show how it can be used for approximating maximum a posteriori (MAP) inference in propositional Markov logic networks [Richardson and Domingos, 2006; Dupin de Saint-Cyr et al., 1994]. An online appendix to this paper with additional details is available. 1

2 Related work

Reasoning with defaults of the form "if ↵ then typically β", denoted as ↵ ♣⇠β, has been widely studied [Kraus et al., 1990; Pearl, 1990; Lehmann and Magidor, 1992; Geffner and Pearl, 1992; Goldszmidt et al., 1993; Benferhat et al., 1997]. 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 a ♣⇠b and a ♣⇠≻b). As a result, these approaches cannot directly be used for reasoning about noisy crowdsourced defaults.

To the best of our knowledge, this is the first paper that considers a machine learning setting where the input consists of default rules. Several authors have proposed approaches for constructing possibility distributions from data; see [Dubois and Prade, 2015] for a recent survey. However, such methods are generally not practical for constructing possibilistic logic theories. The possibilistic counterpart of the Z-ranking constructs a possibilistic logic theory from a set of defaults, but it requires that these defaults are consistent and cannot handle non-defaults [Benferhat et al., 1997], although an extension of the Z-ranking that can cope with non-defaults was proposed in [Booth and Paris, 1998]. Some authors have also looked at the problem of learning sets of defaults from data [Benferhat et al., 2003; Kern-Isberner et al., 2008], but the performance of these methods has not been experimentally tested. In [Serrurier and Prade, 2007], a possibilistic inductive logic programming (ILP) system is proposed, which uses a variant of possibilistic logic for learning rules with exceptions. However, as is common for ILP systems, this method only considers classification problems, and cannot readily be applied to learn general possibilistic logic theories. Our work can also be seen as conceptually related to belief merging, although we are not aware of any existing methods for merging inconsistent sets of default rules. Finally note that the setting of learning from default rules as introduced in this paper can be seen as a nonmonotonic counterpart of an ILP setting called learning from entailment [De Raedt, 1997].

1 http://arxiv.org/abs/1604.05273

3 Background

3.1 Possibilistic logic

A stratification of a propositional theory T is an ordered partition of the set of formulas in T . A theory in possibilistic logic [Dubois et al., 1994] is a set of formulas of the form (↵↪ λ), with ↵ a propositional formula and λ 2]0↪ 1] a certainty weight. These certainty weights are interpreted in a purely ordinal fashion, hence a possibilistic logic theory is essentially a stratification of a propositional theory. The strict λ-cut ⇥λ of a possibilistic logic theory ⇥ is defined as ⇥λ = ¶↵ ♣ (↵↪ θ) 2 ⇥↪ θ > λ♦. The inconsistency level inc(⇥) of ⇥ is the lowest certainty level λ in [0↪ 1] for which the classical theory ⇥λ is consistent. An inconsistency-tolerant inference relation `poss for possibilistic logic can then be defined as follows:

We will write (⇥↪ ↵) `poss β as an abbreviation for ⇥ [ ¶(↵↪ 1)♦ `poss β. It can be shown that ⇥ `poss (↵↪ λ) can be decided by making O(log2 k) calls to a SAT solver, with k the number of certaintly levels in ⇥ [Lang, 2001].

There is a close relationship between possibilistic logic and the rational closure of a set of defaults. Recall that ↵ ♣⇠β is tolerated by a set of defaults ¶↵1 ♣⇠β1↪ ▷▷▷↪ ↵n ♣⇠βn♦ if the classical formula ↵ ^ β ^ Vi (≻↵i _ βi) is consistent [Pearl, 1990]. Let ∆ be a set of defaults. The rational closure of ∆ is based on a stratification ∆1↪ ▷▷▷↪ ∆k, known as the Z-ordering, where each ∆j contains all defaults from ∆∩ (∆1 [ ▷▷▷∆j-1) which are tolerated by ∆ ∩ (∆1 [ ▷▷▷ [∆j-1). Intuitively, ∆1 contains the most general default rules, ∆2 contains exceptions to these rules, ∆3 contains exceptions to these exceptions, etc. Given the stratification ∆1↪ ▷▷▷↪∆k we define the possibilistic logic theory ⇥ = ¶(≻↵_β↪ λi) ♣ (↵ ♣⇠ β) 2 ∆i♦, where we assume 0 < λ1 < ▷▷▷ < λk  1. It then holds that ↵ ♣⇠β is in the rational closure of ∆ iff (⇥↪ ↵) `poss β [Benferhat et al., 1998].

3.2 Learning Theory

We now cover some basic notions from statistical learning theory [Vapnik, 1995]. We restrict ourselves to binary classification problems, where the two labels are 1 and -1. Let X be a set of examples. A hypothesis is a function h : X ! ¶-1↪ 1♦. A hypothesis h is said to cover an example e 2 X if h(e) = 1. Consider a set S ✓ X ⇥ ¶-1↪ 1♦ of n labeled examples that have been iid sampled from a distribution p. A hypothesis h's sample error rate is errS(h↪ S) = 1n P(x↪c)2S 1(h(x) 6= c) where 1(↵) = 1 if ↵ ⌘ true and 1(↵) = 0 otherwise. A hypothesis h's expected error w.r.t. the probability distribution p is given by errp(h) = E(X↪C)⇠p[1(h(X) 6= C)]▷ Statistical learning theory provides tools for bounding the probability P(suph2H ♣errp(h) - errS(h↪ S)♣ ≥ ✏), where S is known to be sampled iid from p but p itself is unknown. These bounds link h's training set error to its (probable) performance on other examples drawn from the same distribution, and therefore permits theoretically controlling overfitting. The most important bounds of this type depend on the Vapnik-Chervonenkis (VC) dimension [Vapnik, 1995].

Definition 1 (Vapnik-Chervonenkis (VC) dimension). A hypothesis set H is said to shatter a set of examples Y if for every subset Z ✓ Y there is a hypothesis h 2 H such that h(e) = 1 for every e 2 Z and h(e) = -1 for every e 2 Y∩Z. The VC dimension of H is the cardinality of the largest set that is shattered by H.

Upper bounds based on the VC dimension are increasing functions of the VC dimension and decreasing functions of the number of examples in the training sample S. Ideally, the goal is to minimize expected error, but this cannot be evaluated since p is unknown. Structural risk minimization [Vapnik, 1995] helps with this if the hypothesis set can be organized into a hierarchy of nested hypothesis classes of increasing VC dimension. It suggests selecting hypotheses that minimize a risk composed of the training set error and a complexity term, e.g. if two hypotheses have the same training set error, the one originating from the class with lower VC dimension should be preferred.

4 Learning fromDefault Rules

In this section, we formally describe a new learning setting for possibilistic logic called learning from default rules. We assume a finite alphabet ⌃ is given. An example is a default rule over ⌃ and a hypothesis is a possibilistic logic theory over ⌃. A hypothesis h predicts the class of an example e = ↵ ♣⇠β by checking if h covers e, in the following sense.

Definition 2 (Covering). A hypothesis h 2 H covers an example e = ↵ ♣⇠β if (h↪ ↵) `poss β.

The hypothesis h predicts positive, i.e. h(↵ ♣⇠β) = 1, iff h covers e, and else predicts negative, i.e. h(↵ ♣⇠β) = -1.

Example 1. Let us consider the following set of examples

The following hypotheses over the alphabet ¶bird↪ flies↪ antarctic♦ cover all positive and no negative examples:

The learning task can be formally described as follows.

Given: A multi-set S which is an i.i.d. sample from a set of default rules over a given finite alphabet ⌃.

Do: Learn a possiblistic logic theory that covers all positive examples and none of the negative examples in S.

The above definition assumes that S is perfectly separable, i.e. it is possible to perfectly distinguish positive examples from negative examples. In practice, we often relax this requirement, and instead aim to find a theory that minimizes the training set error. Similar to learning in graphical models, this learning task can be decomposed into parameter learning and structure learning. In our context, the goal of parameter learning is to convert a set of propositional formulas into a possibilistic logic theory, while the goal of structure learning is to decide what that set of propositional formulas should be.

4.1 Parameter Learning

Parameter learning assumes that the formulas of the possibilistic logic theory are fixed, and only the certainty weights need to be assigned. As the exact numerical values of the certainty weights are irrelevant, we will treat parameter learning as the process of finding the most suitable stratification of a given set of formulas, e.g. the one which minimizes training error or structural risk (cf. Section 4.2).

Example 2. Let S = ¶(penguin ♣⇠bird↪ 1)↪ (bird ♣⇠flies↪ 1)↪ (penguin ♣⇠ ≻flies↪ 1)↪ ( ♣⇠ bird↪ -1)↪ (bird ♣⇠ penguin↪ -1)♦ and T = ¶bird↪ flies↪ penguin↪ ≻penguin _ ≻flies♦▷ A stratification of T which minimizes the training error on the examples from S is T ⇤ = ¶(bird↪ 0▷25)↪ (penguin↪ 0▷25)↪ (flies↪ 0▷5)↪ (≻penguin _ ≻flies↪ 1)♦ which is equivalent to T ⇤⇤ = ¶(flies↪ 0▷5)↪ (≻penguin _ ≻flies↪ 1)♦ because inc(T ⇤ ) = 0▷25. Note that T ⇤⇤ correctly classifies all examples except (penguin ♣⇠bird↪ 1).

Example 3. Let us consider the following set of examples S = ¶( ♣⇠≻x↪ 1)↪ ( ♣⇠≻y↪ 1)↪ (x ♣⇠ a↪ 1)↪ (y ♣⇠ b↪ 1)↪ (x ^ y ♣⇠a↪-1)♦▷ Let T = ¶≻x↪ ≻y↪ ≻x _ a↪ ≻y _ b♦. The following stratification is a separating stratification of S + and S -: h = ¶(≻x↪ 0▷25)↪ (≻x_a↪ 0▷5)↪ (≻y↪ 0▷75)↪ (≻y _ b↪ 1)♦. Note that the Z-ranking of S + also corresponds to a stratification of T , as T contains exactly the clause representations of the positive examples. However using the Zranking leads to a different stratification, which is: hz = ¶(≻x↪ 0▷5)↪ (≻y↪ 0▷5)↪ (≻x _ a↪ 1)↪ (≻y _ b↪ 1)♦▷ Note that hz(x ^ y ♣⇠ a) = 1 whereas h(x ^ y ♣⇠ a) = -1.

Given a set of examples S, we write S + = ¶↵♣(↵↪ 1) 2 S♦ and S - = ¶↵♣(↵↪ -1) 2 S♦). A stratification T ⇤ of a theory T is a separating stratification of S + and S - if it covers all examples from S + and no examples from S -.

Because arbitrary stratifications can be chosen, there is substantial freedom to ensure that negative examples are not covered. This is true even when the set of considered formulas is restricted to the clause representations of the positive examples, as seen in Example 3. Unfortunately, the problem of finding an optimal stratification is computationally hard.

Theorem 1. Deciding whether a separating stratification exists for given T , S + and S - is a ⌃P2 -complete problem.

Proof. The proof of the membership result is trivial. We show the hardness result by reduction from the ⌃P2 -complete problem of deciding the satisfiability of quantified Boolean formulas of the form 9X8Y : Φ(X↪ Y ) where X and Y are vectors of propositional variables and Φ(X↪ Y ) is a propositional formula. Let T = X [ ¶≻x : x 2 X♦ [ ¶Φ(X↪ Y ) ! aux♦ be a propositional theory, let S + = ¶ ♣⇠aux♦ and S - = ;. We need to show that 9X8Y : Φ(X↪ Y ) is satisfiable if and only if there exists a separating stratification for T , S + and S -. ()) Let ✓ be an assignment of variables in X such that 8Y : Φ(X✓↪ Y ) is true. Then we can construct the separating stratification as

Since Φ(X↪ Y ) will always be true in any model consistent with the highest level of the stratification, because of the way we chose x and ≻x for this level, so will aux. (() Let T ⇤ be a stratification of T which entails the default rule ♣⇠aux. We can assume w.l.o.g. that T ⇤ has only two levels. Since T ⇤ is a separating stratification, we must have T ⇤ `poss aux. Therefore the highest level L⇤ of T ⇤ must be a consistent theory and Φ(X↪ Y ) must be true in all of its models. Let X0 = ¶x 2 X : x 2 L⇤ or ≻x 2 L⇤ ♦ and X00 = X ∩X0 . We can construct an assignment ✓ to variables in X0 by setting x✓ = 1 for x 2 L⇤ and x✓ = 0 for ≻x 2 L⇤ . It follows from the construction that 8X008Y : Φ(X✓↪ Y ) must be true.

As this result reveals, in practice we will need to rely on heuristic methods for parameter learning. In Section 4.3 we will propose such a heuristic method, which will moreover also include structure learning.

4.2 VCDimension of Possibilistic Logic Theories

We explore the VC dimension of the set of possible stratifications of a propositional theory, as this will allow us to provide probabilistic bounds on the generalization ability of a learned possibilistic logic theory. Let us write Strat(T ) for the set of all stratifications of a propositional theory T , and let Strat(k) (T ) be the set of all stratifications with at most k levels. The following proposition provides an upper bound for the VC dimension and can be proved by bounding the cardinality of Strat(k) (T ).

Proposition 1. Let T be a set of n propositional formulas. Then V C(Strat(k) (T ))  n log2 k.

In the next theorem, we establish a lower bound on the VC dimension of stratifications with at most k levels which shows that the above upper bound is asymptotically tight.

Theorem 2. For every k↪ n, k  n, there is a propositional theory T consisting of n formulas such that

To prove Theorem 2, we need the following lemmas; some straightforward proofs are omitted due to space constraints.

Lemma 1. If S is a totally ordered set, let kth(S↪ i) denote the i-th highest element of S. Let X = ¶x1↪ ▷ ▷ ▷ ↪ xn♦ be a set of cardinality n = 2m where m 2 N ∩ ¶0♦. Let

Lemma 2. Let at-leastk(x1↪ x2↪ ▷ ▷ ▷ ↪ xn) denote a Boolean formula which is true if and only if at least k of the arguments are true. Let X = ¶x1↪ ▷ ▷ ▷ ↪ xm♦ be a set of propositional logic variables and ⇡ = (xi1 ↪ xi2 ↪ ▷ ▷ ▷ ↪ xim ) be a permutation of elements from X . Let 0  k  min¶my↪ mz♦. Let

be a set of 12 n log2 n inequalities. Then for any C 0 ✓ C there is a permutation of X satisfying all constraints from C 0 and no constraints from C ∩ C 0 .

be a possibilistic logic theory. Let Y = ¶y1↪ ▷ ▷ ▷ ↪ ymy ♦ and Z = ¶z1↪ ▷ ▷ ▷ ↪ zmz ♦ be disjoint subsets of X . Then

iff kth(¶y1↪ ▷ ▷ ▷ ↪ ymy ♦↪ k) < kth(¶z1↪ ▷ ▷ ▷ ↪ zmz ♦↪ k) w.r.t. the ordering given by the permutation ⇡.

Lemma 3. For every n = 2m there is a propositional theory T consisting of n formulas such that

Proof. Let T = ¶x1↪ ▷ ▷ ▷ ↪ xn♦ be a set of propositional variables where n = 2m, m 2 N ∩ ¶0♦ and let C be defined as in Lemma 1. Let D =

i.e. D contains one default rule for every inequality from C. It follows from Lemma 1 and Lemma 2 that the set D can be shattered by stratifications of the propositional theory T . The cardinality of D is 12 n log2 n. Therefore the VC dimension of stratifications of T is at least 12 n log2 n.

Proof of Theorem 2. We show that if k and n are powers of two then 12 n log2 k is a lower bound of the VC dimension. The general case of the theorem then follows straightforwardly. Let T = Snk i=1 ¶x(i-1)·k+1↪ ▷ ▷ ▷ ↪ xi·k♦ and let Di be a set of default rules of cardinality 12 k log2 k shattered by Strat(¶x(i-1)·k+1↪ ▷ ▷ ▷ ↪ xi·k♦). It follows from Lemma 3 that such a set Di always exists. Let D = Snk i=1 Di. Then D has cardinality 12 n log2 k and is shattered by Strat(k) (T ). To see that the latter holds, note that the sets of formulas Strat(¶x(i-1)·k+1↪ ▷ ▷ ▷ ↪ xi·k♦) are disjoint. Therefore, if we want to find a stratification from Strat(k) (T ) which covers only examples from an arbitrary set D0 ✓ D and no other examples from D then we can merge stratifications of ¶x(i-1)·k+1↪ ▷ ▷ ▷ ↪ xi·k♦ which cover exactly the examples from Di \ D0 , where merging stratifications is done by levelwise unions.

Combining the derived lower bounds and upper bounds on the VC dimension together with the structural risk minimization principle, we find that given two stratifications with the same training set error rate, we should prefer the one with the fewest levels. Furthermore, when structure learning is used, it is desirable for learned theories to be compact. A natural learning problem then consists of selecting a small subset of T , where T corresponds to the set of formulas considered by the structure learner, and identifying a stratification only for that subset. The results in this section can readily be extended to provide bounds on the VC dimension of this problem. Let T be a propositional theory of cardinality n and let m < n be a positive integer. The VC dimension of the set of hypotheses involving at most m formulas from T and having at most k levels is bounded by m(log2 n + log2 k). This can simply be obtained by upper-bounding the number of the different stratifications with at most k levels and m formulas selected from a set of cardinality n, by nm · km.

4.3 Heuristic Learning Algorithm

In this section, we propose a practical heuristic algorithm for learning a possibilistic logic theory from a set S of positive and negative examples of default rules. Our method combines greedy structure learning with greedy weight learning. We assume that every default or non-default ↵ ♣⇠β in S is such that ≻↵ and β correspond to clauses.

The algorithm starts by initializing the "working" stratification T ⇤ to be an empty list. Then it repeats the following revision procedure for a user-defined number of iterations n, or until a timeout is reached. First, it generates a set of candidate propositional clauses C as follows:

• ÷ It samples a set of defaults ↵ ♣⇠β from the examples that are misclassified by T ⇤ .
• ÷ For each default ↵ ♣⇠β which has been sampled, it samples a subclause ≻↵0 of ≻↵ and a subclause β0 of β. If ↵ ♣⇠β is a positive example then ≻↵0 _ β0 is added to C; if it is a negative example, then ≻↵0 _ β00 is added instead, where β00 is obtained from β0 by negating each of the literals.

The algorithm then tries to add each formula in C to an existing level of T ⇤ or to a newly inserted level. It picks the clause c whose addition leads to the highest accuracy and adds it to T ⇤ . The other clauses from C are discarded. In case of ties, the clause which leads to the stratification with the fewest levels is selected, in accordance with the structural risk minimization principle and our derived VC dimension. If there are multiple such clauses, then it selects the shortest among them. Subsequently, the algorithm tries to greedily minimize the newly added clause c, by repeatedly removing literals as long as this does not lead to an increase in the training set error. Next, the algorithm tries to revise T ⇤ by greedily removing clauses whose deletion does not increase the training set error. Finally, as the last step of each iteration, the weights of all clauses are optimized by greedily reinserting each clause in the theory.

5 Experiments

We evaluate our heuristic learning algorithm 2 in two different applications: learning domain theories from crowdsourced default rules and approximating MAP inference in propositional Markov logic networks. As we are not aware of any existing methods that can learn a consistent logical theory from a set of noisy defaults, there are no baseline methods to which our method can directly be compared. However, if we fix a target literal l, we can train standard classifiers to predict for each propositional context ↵ whether the default ↵ ♣⇠ l holds. This can only be done consistently with "parallel" rules, where the literals in the consequent do not appear in antecedents. We will thus compare our method to three traditional classifiers on two crowdsourced datasets of parallel rules: random forests [Breiman, 2001], C4.5 decision trees [Quinlan, 1993], and the rule learner RIPPER [Cohen, 1995]. Random forests achieve state-of-the-art accuracy 3 but its models are difficult to interpret. Decision trees are often less accurate but more interpretable than random forests. Finally, rule learners have the most interpretable models, but often at the expense of lower accuracy. In the second experiment, approximating MAP inference, we do not restrict ourselves to parallel rules. In this case, only our method can guarantee that the predicted defaults will be consistent.

5.1 Methodology

Our learning algorithm is implemented in Java and uses the SAT4j library [Berre and Parrain, 2010]. The implementation contains a number of optimizations which make it possible to handle datasets of thousands of default rules, including caching, parallelization, detection of relevant possibilistic subtheories for deciding entailment queries and unit propagation in the possibilistic logic theories.

We use the Weka [Hall et al., 2009] implementations for the three baselines. When using our heuristic learning algorithm, we run it for a maximum time of 10 hours for the crowdsourcing experiments reported in Section 5.2 and for one hour for the experiments reported in Section 5.3. For C4.5 and RIPPER, we use the default settings. For random forests, we used the default settings and set the number of trees to 100.

2 The data, code, and learned models are available from https: //github.com/supertweety/.

3 A recent large-scale empirical evaluation has shown that variants of the random forest algorithm tend to perform best on real-life datasets [Fern´andez-Delgado et al., 2014].

5.2 Learning fromCrowdsourced Examples

We used CrowdFlower, an online crowdsourcing platform, to collect expert rules about two domains. In the first experiment, we created 3706 scenarios for a team on offense in American football by varying the field position, down and distance, time left, and score difference. Then we presented six choices for a play call (punt, field goal, run, pass, kneel down, do not know/it depends) and asked the user to select the most appropriate one. All scenarios were presented to 5 annotators. A manual inspection of a subset of the rules revealed that they are of reasonably high quality. In a second experiment, users were presented with 2388 scenarios based on Texas hold'em poker situations, where users were asked whether in a given situation they would typically fold, call or raise, with a fourth option again being "do not know/it depends". Each scenario was again presented to 5 annotators. Given the highly subjective nature of poker strategy, it was not possible to enforce the usual quality control mechanism on CrowdFlower in this case, and the quality of the collected rules was accordingly found to be more variable.

In both cases, the positive examples are the rules obtained via crowdsourcing, while negative examples are created by taking positive examples and randomly selecting a different consequent. To create training and testing sets, we divided the data based on annotator ID so that all rules labeled by a given annotated appear only in the training set or only in the testing set, to prevent leakage of information. We added a set of hard rules to the possibilistic logic theories to enforce that only one choice should be selected for a game situation. The baseline methods were presented with the same information, in the sense that the problem was presented as a multi-class classification problem, i.e. given a game situation, the different algorithms were used to predict the most typical action (with one additional option being that none of the actions is typical). The results are summarized in Table 1.

In the poker experiment, our approach obtained slightly higher accuracy than random forest and RIPPER but performed slightly worse than C4.5. However, a manual inspection showed that a meaningful theory about poker strategy was learned. For example, at the lowest level, the possibilistic logic theory contains the rule "call", which makes sense given the nature of the presented scenarios. At a higher level, it contains more specific rules such as "if you have three of a kind then raise". At the level above, it contains exceptions to these more specific rules such as "If you have three of a kind, there are three hearts on the board and your opponent raised on the river then call".

In the American football experiment, our approach obtained lower accuracy than the competing algorithms. The best accuracy was achieved by C4.5. Again, we also manually inspected the learned possibilistic logic theory and found that it captures some general intuitions and known strategy about the game. For example, the most general rule is "pass"

which is the most common play type. Another example is that second most general level has several rules that say on fourth down and long you should punt. More specific levels allow for cases when you should not punt on fourth down, such as when you are in field goal range.

Despite not achieving the same accuracy as C4.5 in this experiment, it nonetheless seems that our method is useful for building up domain theories by crowdsourcing opinions. The learned domain theories are easy to interpret (e.g., the size of the poker theory, as a sum of rule lengths, is more than 10 times smaller than the number of nodes in the learned tree) and capture relevant strategies for both games. The models obtained by classifiers such as C4.5, on the other hand, are often difficult to interpret. Moreover, traditional classifiers such as C4.5 can only be applied to parallel rules, and will typically lead to inconsistent logical theories in more complex domains. In contrast, our method can cope with arbitrary default rules as input, making it much more broadly applicable for learning domain theories.

5.3 ApproximatingMAP Inference

Markov logic networks can be seen as weighted logical theories. The weights assigned to formulas are intuitively seen as penalties; they are used to induce a probability distribution over the set of possible world. Here we are interested in maximum a posteriori (MAP) inference. Specifically, we consider the following entailment relation from [Dupin de Saint-Cyr et al., 1994]: (M↪ ↵) `MAP β iff 8! 2 max(M↪ ↵) : ! ♣= β where M is an MLN, ↵ and β are propositional formulas and max(M↪ ↵) is the set of most probable models of ↵, w.r.t. the probability distribution induced by M. Note that MAP inference only depends on an ordering of possible worlds. It was shown in [Kuˇzelka et al., 2015] that for every propositional MLNM there exists a possibilistic logic theory ⇥ such that (M↪ ↵) `MAP β iff (⇥↪ ↵) `poss β. Such a translation can be useful in practice, as possibilistic logic theories tend to be much easier to interpret, given that the weights associated with different formulas in an MLN can interact in non-trivial ways. Unfortunately, in general ⇥ is exponentially larger thanM. Moreover, the translation from [Kuˇzelka et al., 2015] requires an exact MAP solver, whereas most such solvers are approximate.

Therefore, rather than trying to capture MAP inference exactly, here we propose to learn a possibilistic logic theory from a set of examples of valid and invalid MAP entailments (M↪ ↵) `MAP β. Since our learning algorithm can handle non-separable data, we can use approximate MAP solvers for generating these examples, which leads to further gains in scalability. As is common, the evidence ↵ consists of conjunctions of up to k literals, and the conclusion β consists of an individual literal. To create examples, we randomly generate a large number of evidence formulas ↵, each time considering a large number of possible βs. If β is MAP-entailed by ↵, we add ↵ ♣⇠ β to the set of positive examples; otherwise we add it to the set of negative examples. Notice that defaults in these experiments are not restricted to be just "parallel" rules.

We considered propositional MLNs learned from NLTCS, MSNBC, Plants and DNA data using the method from [Lowd and Davis, 2014]. These are standard datasets, and have 16, 17, 69 and 180 Boolean random variables, respectively. We used the existing train/tune/test division of the data. For each dataset, we generated 1000 training examples and 1000 testing examples of default rules as described above, and considered evidence formulas ↵ of up 5 literals. We learn the possibilistic logic theory on the training examples, and report results on the held-out testing examples. To use the classical learners, we represent the antecedent using two Boolean attributes for each variable in the domain: the first indicates the variable's positive presence in the antecedent while the second indicates its negative presence. We represent the consequent in the same way. The label of an example is positive if it appears in the default theory and negative otherwise. While this allows us to predict whether a default a ♣⇠ b should be true, the set of defaults predicted by the classical methods will in general not be consistent.

The last four rows of Table 1 show the test set accuracy for each approach on each domain. Overall, the learned possibilistic logic theories have similar performance to the decision tree and random forest models, and outperform RIPPER. This is quite remarkable, as the possibilistic logic theories are much more interpretable (containing approximately 50% fewer literals than the decision trees), which usually means that we have to accept a lower accuracy. Moreover, while the other methods can also be used for predicting MAP entailment, only our method results in a consistent logical theory, which could e.g. easily be combined with expert knowledge.

6 Conclusions

The aim of this paper was to study the problem of reasoning with default rules from a machine learning perspective. We have formally introduced the problem of learning from defaults and have analyzed its theoretical properties. Among others, we have shown that the complexity of the main decision problem is ⌃P2 complete, and we have established asymptotically tight bounds on the VC-dimension. At the practical level, we have proposed practical heuristic learning algorithm, which can scale to datasets with thousands of rules. We have presented experimental results that show the application potential of the proposed learning algorithm, considering two different application settings: learning domain theories by crowdsourcing expert opinions and approximating propositional MLNs. We believe that the methods proposed in this paper will open the door to a wider range of applications of default reasoning, where we see defaults as a convenient interface between experts and learned domain models.

Acknowledgments

This work has been supported by a grant from the Leverhulme Trust (RPG-2014-164). Jesse Davis is partially supported by the KU Leuven Research Fund (C22/15/015), and FWO-Vlaanderen (G.0356.12, SBO-150033).