{'fraction_non_alphanumeric': 0.0436930314613349, 'fraction_numerical': 0.00911496618641576, 'mean_word_length': 4.099250374812594, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning Abduction under Partial Observability

Juba recently proposed a formulation of learning abductive reasoning from examples, in which both the relative plausibility of various explanations, as well as which explanations are valid, are learned directly from data. The main shortcoming of this formulation of the task is that it assumes access to full-information (i.e., fully specified) examples; relatedly, it offers no role for declarative background knowledge, as such knowledge is rendered redundant in the abduction task by complete information. In this work, we extend the formulation to utilize such partially specified examples, along with declarative background knowledge about the missing data. We show that it is possible to use implicitly learned rules together with the explicitly given declarative knowledge to support hypotheses in the course of abduction. We observe that when a small explanation exists, it is possible to obtain a much-improved guarantee in the challenging exception-tolerant setting. Such small, human-understandable explanations are of particular interest for potential applications of the task.


Introduction
Abduction is the task of inferring a plausible hypothesis to explain an observed or hypothetical condition. Although it is most prominently observed in scientific inquiry as the step of proposing a hypothesis to be investigated, it is also an everyday mode of inference. Simple tasks such as understanding stories from Hobbs et al. (1990) and images from Cox and Pietrzykowski (1986) and Poole (1990) involve a process of abduction to infer an interpretation of the larger events, context, and motivations that are only partially depicted. Its significance to AI was first recognized by Charniak and McDermott (1985).
In this work, we consider a PAC-learning (Valiant, 1984(Valiant, , 2000 formulation of the combined task of learning to abduce, introduced by Juba (2016). In this formulation, one is given a collection of examples drawn from the prior distribution (i.e., example jointly sampled values of attributes) together with a condition to explain, represented as a Boolean formula c on the attributes. The task is then to propose a formula h, which essentially must be a k-DNF for computational reasons, satisfying the following two criteria: 1. Plausibility: the probability that h is satisfied on the prior distribution must be at least some (given) minimum value µ > 0 2. Entailment: the probability that the condition to explain c is satisfied, conditioned on the hypothesis h holding, is at least 1 − ǫ for some given error tolerance ǫ > 0.
By casting the task as operating directly on examples, Juba avoids the problem of explicitly learning and representing the prior distribution. The main shortcoming of this formulation is that it assumes access to complete information, so any attributes to be invoked in the explanation must be recorded in all of the examples. This is a problem, for example, when we wish to infer the intentions of characters in stories, which are frequently either left ambiguous or are assumed to be clear from the given context. It is also a problem if, for example, we would like to use the abduced hypothesis to guide further exploration that may include attributes that we previously were not measuring.
Our work extends Juba's formulation of the abduction task to use partial examples and draw on declaratively specified background knowledge. We observe that by using a covering algorithm, it is possible to guarantee significantly better explanations when a small hypothesis (using relatively few terms) is adequate. Concretely, when some r-term k-DNF explanation on n attributes has an error rate of ǫ * , we obtain an error rate ofÕ(r(log log n + log k)ǫ * ), in contrast to the bound obtained for the state-of-the-art algorithm of Zhang, Mathew, and Juba (2017), which gave an error rate of O( √ n k ǫ * ) (but does not consider the effect of the size of the hypothesis).

Partial Observability
In the real world, it is hard to require each example to contain all of the attributes. So, we want to make inferences with incomplete data. Partial observability means that some attributes of examples may be unknown. We represent this by allowing the value of each attribute to be 1 (true), 0 (false), or * (unobserved). For instance, an example ρ (i) could be [x 1 = 1, x 2 = * , · · · , x n = 0]. (For convenience, we denote ρ (i) to be the ith example and ρ i to be the ith coordinate of an example ρ.) In our abduction task, we say our partial examples are drawn from such a masked distribution M (D).

Implicit Learning
The main tool to deal with partial observability is implicit learning. Implicit learning means learning without producing explicit representations. Given a knowledge base (a set of formulas), and a query formula, we want to know if the knowledge base can derive the query formula. The main theorem of implicit learning says, as long as the formulas in a knowledge base are sufficiently observed in partial examples, we can determine whether the knowledge base can derive the query without explicitly constructing or representing the knowledge base.
Definition 1 (Witnessed Formula) Given a partial example ρ, we say a formula φ is witnessed if φ| ρ is 0 or 1, where φ| ρ means the formula φ restricted to example ρ.
Formally, a restricted formula φ| ρ is defined recursively: we break down a formula at its logical connectives ({¬, ∨, ∧}) recursively up to single variables, where for the base cases, these singletons are set by the values from the example ρ. Restricted formulas' explicit expressions can be computed in linear time.
Informally speaking, we get the restricted formula by plugging in the observed value of the given example, resulting in a (shorter) formula of the unobserved variables. For instance, let φ = x 1 ∨ x 2 , and in a partial example, x 1 = 1; x 2 = * . Then φ is witnessed (true) even though x 2 is not observed. But it could be hard to determine the value for more complex formulas; in general, this may be as hard as deciding if the formula is a tautology, which is NP-hard. Notice that each formula can be either witnessed true, witnessed false, or not witnessed.
Proof system Given a knowledge base KB (a set of formulas) and a query formula φ, for our purposes a proof system is an algorithm that can determine whether we can derive φ. If we can derive φ, we say φ is provable and denote it as ⊢ φ.
A proof system is restriction-closed if whenever there is a proof of a formula φ, there is also a proof of φ| ρ for any partial assignment ρ. In general, if there is a proof of φ| ρ from KB| ρ , we say that φ is provable from KB under ρ. The formal language may be confusing, but the definition is indeed intuitive. Consider the following example: Notice that most common propositional proof systems such as Resolution, (Forward) Chaining, Cutting Planes, and Polynomial Calculus are indeed restriction closed.

DecidePAC Algorithm
Besides the information we directly witness from the examples, we want to know further what we can infer, given some knowledge base (a set of additional formulas). From the previous work by Juba (2013), we have an algorithm that can tell whether a formula is provable or not. Given knowledge base KB and partial examples {ρ (1) , · · · , ρ (m) } drawn from M (D), for a query formula φ, DecidePAC can tell whether there is a proof of φ if the knowledge we need is witnessed sufficiently often: DecidePAC will Accept if there exists a proof of φ in from KB and formulas ψ 1 , ψ 2 , · · · that are simultaneously witnessed true with probability at least 1 − ǫ + γ on M (D); otherwise, if [KB⇒ φ] is not true with probability at least (1 − ǫ − γ), then DecidePAC will reject formula φ.
Notice that there are three different concepts of being true: 1. observed (or witnessed), 2. provable, and 3. true. For example, let t = x 1 ∧ ¬x 2 . In example ρ (1) , it is observed that x 1 = 1, x 2 = 0, so t is observed to be true in ρ (1) ; in example ρ (2) , x 1 = 1 while x 2 is unobserved, but if we assume in KB we have x 1 ⇒ ¬x 2 , then x 2 is provable, so t is provable; in example ρ (3) , nothing is observed and we know nothing, but in fact, t can be true. Notice that being observed can imply being provable, and being provable can imply truth. We want to bridge from the witnessed values of examples to their ground truth, through logical inference.
DecidePAC was analyzed by Juba using an additive Chernoff bound. We can obtain an analogous multiplicative (1 ± γ) guarantee by instead using the multiplicative Chernoff bound: 3 Abduction under Partial Observability Given a query or an event, abduction is the task of finding an explanation for the query or event.
An explanation is a combination of some conditions that may have caused the query. For example, when the query is "Engine does not run," an explanation can be "No gas, or key is not turned." We require the resulting explanation to satisfy two conditions, "plausibility" and "entailment." Entailment means that when the conditions in the explanation are true, the query should also often be true, or at least rarely false. Thus, the explanation is a (potential) cause of the query. Plausibility means the explanation is often true. In other words, for many examples, these conditions are observed. This suppresses unlikely explanations such as "A comet hits the car." which is a valid entailment, but not plausible. Recall, a k-DNF explanation h with r terms is in the following form: h = t 1 ∨ t 2 ∨ · · · ∨ t r , where each term t i = ℓ i1 ∧ ℓ i2 ∧ · · · ∧ ℓ i k . For convenience, we say t i ∈ h and ℓ ij ∈ t i .

Choice of Formulation
We have chosen to relax the condition that h(x) = 1 in Juba's complete information abduction task to the condition that some term of h is provable under ρ. This is of intermediate strength between h being observed and h being provable. Provability captures whether or not an agent "knows" t is true of a given partial example ρ. Our choice is somewhat like the notion of vivid knowledge by Levesque (1986), that the individual literals of some definite t should be known. The weaker condition that merely h is provable is also interesting, but seems much harder to work with; we leave it as a direction for future work. We could also have relaxed this to cases where ¬h is not provable, but observe that this includes the cases where h is unknown in its favor. Note that this may "mix" many cases where h was actually false into our estimate of the effect of h occurring, which is not desirable, and we anticipate that it would harm the quality of the inferences we can draw.
We made the opposite decision for c(x) = 1, relaxing it to the condition that ¬c is not provable. The main reason for this choice is that we wish to not penalize a good h if it is often impossible to check whether or not c holds. We use this liberal notion of entailment for our explanations because the intended semantics of the task is merely to propose possible causes given some tentative partial knowledge of the world, perhaps to guide further investigation. At the same time, we would like to take ǫ to be very small, so that we can aggressively rule out h's for which c is frequently known to fail to occur. But, if we are including the outcome of c being unknown as a "failure" of h, then this suggests that in the cases where c is indeed often unknown, then ǫ must be large, even for a good h.

Implicit Abduction Algorithm
A k-DNF explanation is actually a disjunction of terms, h = t 1 ∨ t 2 ∨ · · · ∨ t r . Each term represents a condition, or a possibility. Our goal is to find a formula that covers as many such conditions as possible while still being a potential cause of the query c.
We observe there is a natural correspondence between our k-DNF abduction task and set cover: each example of abduction is an element of the set cover problem, and each term is a set. We say a term covers an example when the term is provable in that example. The number of examples from the distribution is equivalent to its frequency or empirical probability with respect to the distribution M(D). If the resulting explanation consists of terms that are provable in most of examples, then we can conclude that our explanation is provable with high probability.
Algorithm 1: Implicit Abduction input :Knowledge base KB, , query c and parameters µ, ǫ, δ, γ ∈ [0, 1] output :A k-DNF explanation h begin Initialize T to be the set of all terms of at most k-literals. Draw partial examples Run greedy algorithm for set cover: use terms in T to cover a µ-fraction of the examples. Get {t 1 , · · · , t r }. h ← t 1 ∨ · · · ∨ t r return h.
In the implicit abduction algorithm, we enumerate through all possible k literal terms: 1. Check all the terms using the same technique underlying DecidePAC: We count the number of bad examples where ¬c and t are both provable. If the bad examples are more than a µǫ-fraction, then we delete this term. By the Chernoff bound, all the terms that pass the test then satisfy weak entailment: the error condition [⊢ t and ⊢ ¬c] has probability at most µǫ(1 + γ). 2. Then use the greedy algorithm to choose an explanation. If the algorithm can find an explanation covering a µ-fraction of examples, then we can argue explanation has probability larger than µ by the Chernoff bound.
Thus, if there exists a good explanation, we can find an explanation satisfying entailment and plausibility.
Remark If µ * is the optimal probability that the terms of a potential explanation h * can be provable, Juba (2016) showed that a multiplicative approximation to µ * can be easily found by binary search. We assume that such an estimate µ is given as input.

Proof of the Main Theorem
Soundness. We first show that if the implicit abduction algorithm returns an explanation h, then h satisfies weak entailment. Plausibility will follow from the assumption that a good explanation exists, so we postpone its discussion to our discussion of completeness, below.
Completeness. We just proved that every output satisfies weak entailment with probability 1 − δ/2 + 2δ ′ . Now, we want to show if there is an optimal r-term k-DNF explanation h * satisfying 1. (Plausibility) for a (1 + γ)µ-fraction of examples, some term t ∈ h * is provable, and 2. (Weak Entailment) if some t ∈ h * is provable, then with high probability ¬c is not provable then we are able to find a good solution that satisfies plausibility and weak entailment.
Claim 6 If there exists a solution h * = t * 1 ∨ t * 2 ∨ · · · ∨ t * r such that [¬c is provable when some t * i is provable] has probability at most (1 − γ)µǫ, then all these terms t * can pass the first test with probability 1 − δ ′ .
Proof of Claim 6 We are given that By a Chernoff bound, for our choice of m, [(⊢ t * | ρ ) ∧ (⊢ (¬c)| ρ )] happens for any t * in h * in less than µǫ-fraction of examples with probability, 1 − δ ′ so all these terms t * pass the first test.
Next, we show the number of terms r ′ is controlled, since r ′ depends upon the solution of the set cover problem.
Proof of Claim 7 Following Claims 5 and 6, with probability at least 1 − δ/2 + δ ′ , all terms t * in h * can pass the first test, so they are available for set cover. Moreover, by another Chernoff bound, since at least one of the terms of h * is provable with probability (1 + γ)µ in each example, with probability 1 − δ ′ at least one of the terms is provable in at least a µ-fraction of the m examples. Thus, there is a set of r terms (the terms of t * ) that pass these tests and indeed cover a µm examples. For the greedy algorithm, if Opt (h * ) covers µm examples using r sets, then our greedy algorithm can find a cover using r ′ = r log(µm) sets that also covers µm examples Slavík (1997).
To see that the returned h satisfies plausibility, we consider a Chernoff bound for the fraction of examples in which each possible r ′ -term k-DNF has a provable term withδ = δ/2|T | r ′ . So when we take a union bound on all k-DNF explanations, any r ′ -term explanation found will actually have plausibility (1 − γ)µ with probability 1 − δ/2. Therefore, it suffices to have m ≥ 3 µγ 2 log 2|T | r ′ δ or m ≥ 3r log(µm) µγ 2 log 2|T | δ .
Here we apply the inequality Lemma 8 For a ≥ 1, if x ≥ 2a log a, then x ≥ a log x.
By plugging in x = µm and a = 3r γ 2 log 2|T | δ , we get m ≥ 6r γ 2 µ log( 2|T | δ ) log(a) examples suffice. Here, log a is dominated by other terms, so we get m =Õ( r γ 2 µ log n k δ ). Since we condition on some t ∈ h provable and Pr[∃t ∈ h provable under ρ] > (1 − γ)µ, and thus, we indeed find an h satisfying weak entailment with the claimed error rate with probability 1 − δ.
Running time. The test is run for each term of size at most k, of which there may be ∼ n k . And DecidePAC runs in time polynomial in n, |ϕ|, |KB| (the running time of the underlying algorithm for the proof system), and 1 γ 2 log 1 δ ; the overall running time is also polynomial, as needed.