An Empirical Investigation of Ceteris Paribus Learnability

1 Introduction

In an era of online commercial transactions and massive online open courses, the ability to personalize products and services becomes more pertinent than ever before. Accommodating this personalization requires a means not only to represent the preferences of those involved, but also to elicit them.

Conditional Preference Networks (CP-nets) have been proposed as a formalism to represent and reason with such preferences [Boutilier et al., 2004], and their learnability has been studied [Dimopoulos et al., 2009; Lang and Mengin, 2009; Koriche and Zanuttini, 2010] in situations resembling the following: Assume that a user's preferences are expressible by a fixed unknown CP-net, henceforth called the target CP-net. A system observes (or queries) the user expressing preferences between choices (e.g., indicating which course to take, movie to rent, or web-link to follow, among pairs of such), and seeks to approximate the target CP-net. If such an approximation can be achieved reliably, efficiently, and non-intrusively, then the user may choose to employ such a system so that, after an initial training phase, the user's choices in analogous but novel future situations can be delegated to the system.

We take herein (i) reliability to mean the offering of predictive guarantees in novel situations, (ii) efficiency to mean the running of the learning and reasoning processes in time polynomial in the relevant problem parameters, and (iii) nonintrusiveness to mean only the passive observation of a user's stated preferences without the user's active involvement.

Although previous work identified formal conditions under which one can ensure such reliability, efficiency (albeit for the learning process only), and non-intrusiveness [Dimopoulos et al., 2009], no systematic empirical investigation of the learning algorithm proposed therein has been performed. The present work seeks to push that empirical front. In the process of our investigation, we extend the known efficiency guarantees to the reasoning process also, by developing a novel reasoning algorithm for CP-nets. Our algorithm is shown to be sound and complete on all transparently entailed preferences, a natural subclass of preferences identified by previous work.

2 Background on CP-nets

A CP-net N is a graph with a vertex set V = {X1 , . . . , Xn } corresponding to the variables over which preferences are expressed. The set PaN(Xt ) of vertices with incoming edges to vertex Xt is the parent set of variable Xt according to N. Each variable Xt is associated with a domain dom(Xt ) = {xt1 , xt2 , . . .} determining the values the variable ranges over.

A subclass of CP-nets that has received special attention in the literature is that of acyclic CP-nets over binary attributes. We shall restrict our attention to this subclass henceforth.

For any subset X ⊆ V of variables, dom(X) is the crossproduct of the domains of variables in X in order of increasing index; that is, dom(X) is the set of all possible assignments of values to all variables in X, so that each variable Xt ∈ X is mapped to a value in its domain dom(Xt ). The assignments in dom(V) (i.e., when X = V) are also called outcomes. We denote by o[X] ∈ dom(X) the assignment of values that outcome o associates with the variables X ⊆ V. For disjoint subsets of variables X , Y ⊆ V, xy ∈ dom(X ∪ Y) is the assignment obtained from the assignments x ∈ dom(X) and y ∈ dom(Y) when variables are appropriately reordered.

N associates each variable Xt with a conditional preference table CPT(Xt ) specifying an order ≻t over dom(Xt ) for each assignment u ∈ dom(PaN(Xt )) to Xt 's parents. Although more generality is possible [Boutilier et al., 2004], for our purposes it suffices to assume ≻t is total, so that either u : xti ≻t xtj or u : xtj ≻t xti for every xti , xtj ∈ dom(Xt ).

Example 1. Figure 1 shows CP-net N ∗ : V = {A, B, C, D}, dom(A) = {a1, a2} and PaN(A) = {}, dom(B) = {b1, b2} and PaN(B) = {A}, dom(C) = {c1, c2} and PaN(C) = {A, B}, dom(D) = {d1, d2} and PaN (D) = {B, C}.

The semantics of a CP-net can be given in terms of satisfaction of preference orderings that one defines over all possible outcomes. Instead of replicating here the relevant definitions

[Boutilier et al., 2004, Definitions 2-3], we present the semantics of a CP-net through an equivalent (for acyclic CPnets [Boutilier et al., 2004, Theorems 7-8]) procedural lens, which we shall find easier to refer to in the sequel.

A flipping sequence from o1 to om with respect to a CPnet N is a sequence of outcomes o1, o2, . . . , om ∈ dom(V) such that for every pair of consecutive outcomes os, os+1 in the sequence there exists a unique variable Xt ∈ V such that os[Xt ] ̸= os+1[Xt ], and, furthermore, for this variable it holds that os[PaN(Xt )] : os[Xt ] ≻t os+1[Xt ] is in CPT(Xt ).

We can now use such flipping sequences to define when a CP-net prefers an outcome oi over another outcome oj, thus: A CP-net N entails a comparison oi ≻ oj if and only if there exists a flipping sequence from oi to oj with respect to N.

Example 2. The CP-net N ∗ in Figure 1 entails the comparison a1b2c1d1 ≻ a2b1c2d2, by the existence of the flipping sequence a1b2c1d1 ≻ a1b1c1d1 ≻ a1b1c1d2 ≻ a2b1c1d2 ≻ a2b1c2d2; underlined is the one value that changes each time.

Example 3. The CP-net N ∗ in Figure 1 does not entail the comparison a2b2c1d2 ≻ a2b2c2d1, by a reductio ad absurdum argument: Assume there exists a flipping sequence from a2b2c1d2 to a2b2c2d1. Then, c1 changes to c2 between some two outcomes in the sequence. This is possible only if a2b1 holds in the earlier of the two outcomes. Since a2b2 holds in the initial outcome, b2 changes to b1 between some two outcomes in the sequence. This is possible only if a1 holds in the earlier of the two outcomes. Since a2 holds in the initial outcome, a2 changes to a1 between some two outcomes in the sequence. This is, however, not possible; a contradiction.

3 Transparent Entailment

It is known that reasoning with, or checking for entailment of, general comparisons in CP-nets (even if acyclic over binary attributes) is intractable [Boutilier et al., 2004, Section 4.4]. The same is true for learning CP-nets (even if acyclic over binary attributes) from general comparisons [Dimopoulos et al., 2009, Theorem 1]. The latter work has investigated a natural subclass of comparisons for which learnability is tractable.

Definition 1 (Transparent Entailment (as given in [Dimopoulos et al., 2009])). Consider a CP-net N over a set V of variables that entails every comparison in a set P of pairwise comparisons between outcomes over V. N

entails P transparently if for every oioi[PaN(X)]oi[X] ≻ ojoj[PaN(X)]oj[X] ∈ P with oi[X] ̸= oj[X], N entails either ooi[PaN(X)]oi[X] ≻ ooi[PaN(X)]oj[X] or ooj[PaN(X)]oi[X] ≻ ooj[PaN(X)]oj[X] for some o ∈ dom(V \ (PaN(X)∪{X})).

In other words, a comparison oi ≻ oj is transparently entailed by a CP-net N if and only if: (i) oi ≻ oj is entailed by N; and (ii) for any variable Xt ∈ V that is assigned different values xti , xtj ∈ dom(Xt ) in oi and oj respectively, it is the case that CPT(Xt ) includes the preference u : xti ≻t xtj for an assignment u ∈ dom(PaN(Xt )) to the parents of Xt as determined by either oi or oj. Thus, the reason for preferring oi over oj is not hidden, but it is made transparent in oi ≻ oj. Example 4. Recall from Example 2 that the CP-net N ∗ in Figure 1 entails the comparison a1b2c1d1 ≻ a2b1c2d2. Looking at the flipping sequence used to establish this, one may observe that d1 changes to d2 at a point where its parents have values b1c1. Furthermore, this is true for all flipping sequences, except possibly that the parents have values b2c2 in them. These values are present in neither the initial nor the final outcome, but only in an intermediate (or hidden) outcome. In this sense, the comparison is not transparent to the reasons that support the change in the value of variable D, and the comparison is not transparently entailed by N ∗ . This is so independently of how the rest of the variables change.

Example 5. The CP-net N ∗ in Figure 1 entails the comparison a1b2c2d1 ≻ a2b1c1d1, by the existence of the flipping sequence a1b2c2d1 ≻ a1b1c2d1 ≻ a1b1c1d1 ≻ a2b1c1d1; underlined is the one value that changes each time. One may observe that c2 changes to c1 at a point where its parents have values a1b1, which are present in neither the initial nor the final outcome. However, the entailment of the comparison a1b2c2d1 ≻ a2b1c1d1 by N ∗ can be established through another flipping sequence a1b2c2d1 ≻ a1b2c1d1 ≻ a1b1c1d1 ≻ a2b1c1d1 also, in which this hiding is avoided (for all variables). Thus, the comparison is transparently entailed by N ∗ .

Although the learnability of CP-nets from transparently entailed preferences has been established [Dimopoulos et al., 2009, Corollary 3] under the Probably Approximate Correct semantics [Valiant, 1984], the efficient checking for transparent entailment of comparisons remains open. On the one hand, the transparent entailment of a comparison implies the entailment of that comparison, and checking for entailment is known [Boutilier et al., 2004] to be either intractable (cf. dominance queries), or incomplete in a rather strong sense (cf. ordering queries). On the other hand, the extra structure of transparently entailed preferences makes it plausible that a more efficient decision process can be devised. We propose and formally analyze such a decision process next.

Effectively, Algorithm 1 seeks to create a flipping sequence that would support the entailment of comparison oi ≻ oj by the CP-net N. For entailment in general, the order in which variables change values in such a flipping sequence could be very involved and intractable to identify. If transparent entailment is of interest, however, Algorithm 1 prescribes a short and universal order (the existence of which is hinted in Example 5) in which variables need to be checked: first in a reverse topological order, and then in a normal topological order, as determined by the graphical representation of the CP-net N.

Algorithm 1 reason(CP-net N, comparison oi ≻ oj)

1: Set V to include the variables over which N is defined. 2: Set V ↑ to be a reverse topological ordering of V w.r.t. N. 3: Set V ↓ to be a normal topological ordering of V w.r.t. N. 4: Set X to be the concatenation of list V ↑ before list V ↓ . 5: Set o∗ := oi. \∗ current outcome in flipping sequence ∗\ 6: while X ̸= ∅ and o∗ ̸= oj do 7: Remove fromX the variable Xt that is ordered first. 8: if o∗[PaN(Xt )] : o∗[Xt ] ≻t oj[Xt ] is in CPT(Xt ) then 9: Update o∗ by replacing o∗[Xt ] with oj[Xt ] in o∗. 10: end if 11: end while 12: if o∗ = oj then 13: return true. \∗ oi ≻ oj transparently entailed ∗\ 14: else {o∗ ̸= oj} 15: return false. \∗ oi ≻ oj not transparently entailed ∗\ 16: end if

Example 6. Recall from Examples 2 and 4 that the CP-net N ∗ in Figure 1 entails - but not transparently - the comparison a1b2c1d1 ≻ a2b1c2d2. Looking at the flipping sequence used to establish the entailment, one may observe that the parents of variable D have their values changed both before and after D has its value changed. Such an ordering of variables is not - and rightly so - accepted by Algorithm 1.

Example 7. Recall from Example 5 that the CP-net N ∗ in Figure 1 transparently entails the comparison a1b2c2d1 ≻ a2b1c1d1. Looking at the flipping sequence (the second in Example 5) used to establish this, one may observe that each variable that changes value does so before its parents. Such an ordering of variables is accepted by Algorithm 1.

We establish next that Algorithm 1 is sound, complete, and computationally efficient for deciding transparent entailment.

Theorem1 (Soundness of reason(·,·)). If the call reason(N, oi ≻ oj) returns true, then N transparently entails oi ≻ oj .

Proof (sketch). Entailment follows since the algorithm constructs a flipping sequence from oi to oj. Transparency follows since for every variable that changes value in the constructed flipping sequence, the parents of that variable change values either only before or only after the variable.

Theorem 2 (Completeness of reason (·,·)). If N transparently entails oi ≻ oj , then the call reason(N, oi ≻ oj ) returns true.

Proof (sketch). A change in the value of a variable that is conditioned on its parents having values as specified by oi will be identified when traversing V ↑ . A change in the value of any remaining variable will be identified when traversing V ↓ .

Theorem 3 (Efficiency of reason(·,·)). The call reason(N, oi ≻ oj) returns true or false in time polynomial in size(N).

Proof (sketch). Topological ordering can be carried out efficiently. The algorithm loops at most twice for each variable, and the test it performs can be carried out efficiently.

4 Empirical Investigation

Our empirical investigation seeks to quantitatively evaluate the performance of an algorithm for learning CP-nets, known to formally guarantee that learning happens in a reliable, efficient, and non-intrusive manner [Dimopoulos et al., 2009].

The algorithm first receives a training set P of comparisons between outcomes, that are entailed by an arbitrary target and hidden CP-net N. For each variable X, the algorithm seeks to find a set U of other variables on which the preferences over the values of X can be conditioned. For each candidate set U, the algorithm translates the set P of comparisons into an appropriate 2-SAT formula, a solution to which prescribes the entries of CPT(X), with Pah(X) = U. Variables X are not considered in an arbitrary order, but all are considered first with |U| = 0 and those for which a CPT can be constructed are kept; the remaining ones are considered with |U| = 1, and so on. Once CPTs for all variables are constructed, the algorithm returns the resulting CP-net h. Pseudocode for the algorithm appears in [Dimopoulos et al., 2009]. The algorithm is shown to be a PAC leaner [Valiant, 1984], in that it runs efficiently, and offers provable guarantees on the performance of the learned CP-net h in terms of its accuracy in entailing previously unseen comparisons (with N being the gold standard for evaluation). The accuracy guarantee is known to hold assuming P contains only transparently entailed preferences.

4.1 Methodology Used

The methodology followed in our experiments comprises the following steps: (i) construct a target CP-net N; (ii) construct a set Pall of some comparisons entailed by N; (iii) keep the subset P of comparisons in Pall that are transparently entailed by N; (iv) learn a CP-net h on a training subset of P; (v) evaluate the performance of h on a testing subset of P.

Constructing a Target CP-net N

This step takes as input a number n of variables, and a maximum number k of parents. It first selects each variable independently at random (with prob. 0.3) as one of the roots. If no root is chosen, the selection is repeated with successively increasing probability (+ 0.1 prob.) until it succeeds. For each remaining variable X, it selects each variable independently at random (with prob. 0.3) to become the parent of X, as long as this choice does not create cycles, nor results in X having more than k parents. Once the parents of X are chosen, its CPT is completed with uniformly at random assigned preferences. The steps returns the constructed CP-net N.

Constructing Comparisons Pall

This step takes as input a number m of comparisons, a length ℓ for flipping sequences, and an "equality" bit. It constructs a comparison oi ≻ oj entailed by N by first selecting uniformly at random either i or j. It then chooses the value of oi (resp., oj ) uniformly at random among all possible outcomes, sets o∗ := oi (resp., o∗ := oj), and repeats the following cycle: It chooses a variable X uniformly at random, and checks whether the value of X can be changed to a less (resp., more) preferred value, given its CPT and the values that its parents have in o∗. If so, it changes the value of X in o∗, and marks the entry of the CPT that was used to support this change.

The cycle is repeated until f changes / flips have been made in o∗, at which point the step sets oj := o∗ (resp., oi := o∗). Thus, N |= oi ≻ oj is established by a flipping sequence of length f, and is added in Pall. The value of f is such that: either it is always equal to ℓ, if the "equality" bit is set; or it is chosen uniformly at random between 1 and ℓ at the beginning of the construction of each comparison, otherwise.

If n attempts are made without managing to get f changes, then the outcome oi (resp., oj) is discarded and chosen again; the change "direction" (i or j) is retained as initially chosen. The step records the average number of discarded outcomes per comparison that is constructed, and the average number of flip attempts per successful flip that was not later discarded.

Once Pall is of size m, the step records the utilization (or "involvement") of N during the construction in two ways: (i) the percentage U1 of marked entries over the total number of entries in N; (ii) the average U2 of the percentage of marked entries in a CPT over the total number of entries in that CPT.

Keeping a Transparent Subset P

For each comparison oi ≻ oj ∈ Pall, this step invokes directly the test given below Definition 1, and keeps the comparison in P if and only if it passes the test. Since the comparison is already known to be entailed, it remains to check the second part of the test, which can be done efficiently. Alternatively, Algorithm 1 could have been used to the same effect. When this step concludes, it records the percentage |P|/|Pall| of comparisons in Pall that are transparently entailed.

Learning a Hypothesis CP-net h

Set P is partitioned into a training subset Pr and a testing subset Pe in a 70%- 30% random split. The training set is further randomly partitioned into subsets P s r . The following is then repeated for s = 0, 1, 2, . . ., in ascending order: The learning algorithm is given P 1 r ∪P 2 r ∪ . . . ∪P s r as a training set, and produces a hypothesis CP-net hs . The resulting CPnet is evaluated on the testing set Pe, and its performance is recorded. Thus, the learning algorithm faces larger training sets during successive training epochs, which always expand the ones given in preceding epochs. Note that the training set size across epochs need not increase linearly with s. Indeed, we have chosen to increase it much more slowly for smaller values of s (i.e., |P s r | is small), to observe in more detail the performance improvement from the extra training data. For larger values of s the performance is nearly stable, so the size increase can be more rapid without major loss of information.

Evaluating the Performance of h

Each learned CP-net hs is evaluated to quantify the extent to which it entails comparisons also entailed by N. Since testing for entailment is generally intractable (cf. dominance queries [Boutilier et al., 2004]), we are left with the choice of either (i) checking for entailment by the tractable but incomplete use of ordering queries, or (ii) checking for transparent entailment by the tractable and complete use of Algorithm 1.

In fact, it would suffice to do the latter, without any loss of generality. Indeed, one can observe that the result establishing the PAC learnability of CP-nets (cf. [Dimopoulos et al., 2009, Corollary 3]) can be easily extended to show that the performance guarantees of the learned CP-net are not only in terms of entailment but also transparent entailment. Thus, our empirical evaluation would accurately measure what the learning algorithm is claiming to do. Nonetheless, we chose to evaluate the performance of hs using both approaches, as a way to evaluate the approaches against each other as well.

To evaluate hs we first present it with an unordered pair of outcomes oi, oj from the testing set. We then invoke the first approach to obtain one of the following [Boutilier et al., 2004, Theorem 5] mutually exclusive predictions: hs ̸|= oi ≻ oj but no decision on oj ≻ oi; hs ̸|= oj ≻ oi but no decision on oi ≻ oj; hs ̸|= oi ≻ oj and hs ̸|= oj ≻ oi. We also invoke the second approach to obtain one of the following mutually exclusive predictions: hs |= oi ≻ oj; hs |= oj ≻ oi; hs ̸|= oi ≻ oj and hs ̸|= oj ≻ oi. We plot the accuracy of each of the six predictions against the ground truth of the testing set.

4.2 Results and Analysis

The recorded information for a variety of values to the experimental parameters is presented in Table 1 and Figures 2,3,4.

The first line of analysis of the empirical results that we pursue relates to properties of the learned CP-nets that derive from the PAC semantics enjoyed by the learning algorithm.

Observe that across all considered settings of Figure 2 and Table 1, the learned CP-net converges rather quickly to a high (above 90%) and then perfect (100%) performance on the testing set. The high speed of convergence can be best appreciated by considering the target CP-net with 20 variables associated with the top-right graph of Figure 2 and setting S2 of Table 1. In that particular setting, high and perfect performance is achieved after only 200 and 700 training examples, respectively, even though the testing set itself contains 2829 comparisons, and there exist more than one million possible outcomes, and more than one trillion possible comparisons.

To further appreciate the efficiency, note that it is achieved despite the target CP-nets having complex structure, and being heavily utilized when constructing the set of training and testing comparisons. An illustration of the complex structure of a target CP-net can be found in Figure 3. In the rightmost CP-net, one can observe: long chains between variables (8 → 9 → 7 → 5 → 6 → 2); variables that act as hubs (variables 1 and 4 each have three incoming and two outgoing edges); multiple roots, leaves, and undirected cycles. The values for the utilization metrics U1 and U2 across all the experiments presented in Figure 2 can be seen in Table 1. This high utilization is an indication that the complex structure of the target CP-nets ends up being encoded in the constructed comparisons, which the learned CP-net needs to decode in order to achieve good performance. And it does so, quickly.

Performance of the learned CP-net is not equated with its structural distance from the target CP-net; structurally replicating the hidden CP-net is not a goal in itself. Rather, the goal is to sufficiently approximate the target CP-net in terms of the comparisons it entails. Figure 3 shows how the learned CP-net evolves in setting S1 of Table 1, corresponding to the upper-left graph of Figure 2. The right-most CP-net of Figure 3 corresponds to the target CP-net. The first-from-left CPnet is trained on 10 instances, and although it exhibits very little structure, it achieves more than 55% performance. The second-from-left CP-net is trained on 100 instances, exhibits much of the structure of the target CP-net, and achieves more than 90% performance. The third-from-left CP-net is trained on the entire training set, its structure almost replicates that of the target CP-net (except for 0 → 6), and achieves 100% performance. Even then, however, the learned CP-net still structurally differs from the target CP-net (due to the two CP-nets disagreeing on the entailment of comparisons that are unimportant / rare, and are not represented in the training set).

During the evolution of the learned CP-net, some spurious dependencies between variables might be included (shown with red / thick arrows in Figure 3), as they may suffice to "explain" the comparisons in the part of the training set that was observed thus far. In the process of receiving more training instances, these dependencies might be refuted, or become obsolete. In Figure 3, for instance: the dependency of variable 6 on variable 1 is removed when both 6 and 1 are found to have a common dependency on variable 5; the direct dependency of variable 2 on variable 7 is removed in the presence of an indirect dependency through the chain 7 → 5 → 6 → 2.

The second line of analysis of the empirical results that we pursue relates to the notion of transparent entailment.

Despite its seemingly restrictive nature, transparent entailment in no way restricts the complexity of the target CP-net; any target CP-net can be shown to transparently entail at least some (and, more precisely, exponentially many in n) comparisons. But how common is transparent entailment among the entailed comparisons of a target CP-net? Figure 4 presents this percentage for a variety of settings (including the ones found in Figure 2). Even as CP-nets get larger and more complex, and even as it becomes increasingly difficult to construct entailed comparisons (as shown by the increasing values of DS and AT), the percentage of the comparisons that are transparently entailed is rather high, and more so for comparisons with not too long supporting flipping sequences.

One could argue that short flipping sequences are more likely to occur in certain real-world settings, and that, by extension, the preferences with which one has to deal in such settings would be reasonably expected to often be (transparently entailed and thus) amenable to the treatment followed in this work. We shall not attempt to make this argument herein, other than state that finding empirical evidence to support it would constitute an intriguing direction for further research.

Finally, we emphasize the advantage of the new reasoning algorithm over the existing one when checking for transparent entailment. All graphs of Figure 2 show that the use of ordering queries overestimates the preference (blue / circle lines) and underestimates the indifference (green / rhombus lines) of the learned CP-net against what is the case. This departure from reality is at times rather dramatic, reaching a distance of 30 percentile units (bottom-left graph of Figure 2). Although further quantification of this phenomenon is needed, it is clear that the new algorithm is a more reliable and equally efficient alternative, when transparent entailment is concerned.

5 Conclusions

This work presents the first systematic empirical investigation of CP-net learnability when the reliability, efficiency, and non-intrusiveness of the learning process are important. It is demonstrated that the learned preferences have high predictive ability on previously unseen situations, after only a very short training phase, and without the active involvement of a user. Equally importantly, the learned preferences are shown to be amenable to efficient reasoning, so that their employment for decision support and recommendations is not merely a conceptual possibility, but a practical and realistic option.

We are aware only of one other (very recent) empirical investigation of CP-net learnability [Liu et al., 2013]. In that work, the authors propose a statistical test that can be used to learn CP-nets in the presence of noisy training examples. Although that work shares the non-intrusiveness property of our investigated algorithm, it does not respect reliability and efficiency. Despite the authors' claim that their learning process is polynomial-time, it seems not to be so in the learning parameters that are typically used in Machine Learning, leading to an algorithm that is ultimately not scalable. Furthermore, the predictive ability of the learned preferences is not evaluated on a distinguished testing set, as done typically in Machine Learning, but only on the training set. Their empirical results exemplify the departure from efficiency and reliability, showing that even for tiny CP-nets over 3 or 5 variables, a few hundred training instances (which corresponds to a significant fraction of all possible training instances) is needed to get a respectable (training set) accuracy. Finally, the learned preferences (irrespectively of any concerns on how they were obtained) cannot be efficiently reasoned with, unlike our case.

Nonetheless, the aforementioned work raises two interesting points: (i) how can learning deal with noise, and (ii) how often can transparent entailment be reasonably assumed? Regarding the former point, our investigated learning algorithm relies on a reduction of training instances to satisfiability instances and the use of a SAT solver [Dimopoulos et al., 2009]. Dealing with noise can, then, be accommodated by using a MAX-SAT solver and following the standard practice of identifying a best-fit hypothesis when learning from noisy data. Regarding the latter point, our empirical results already show that transparent entailment is a rather common property. Both points are certainly worth looking into as part of future work.