On the Learnability of Possibilistic Theories

1 Introduction

Uncertainty is found in many phases of learning, such as model selection and processing noisy, imperfect, incomplete or limited data. In most cases, knowledge-based systems are constrained to live under conditions of ignorance. There are different approaches to deal with uncertainty [Parsons and Hunter, 1998]. A well-studied formalism for dealing with it is possibilistic logic [Didier Dubois and Prade, 1994; Lang, 2000]. It admits a graded notion of possibility and makes a clear distinction between the concepts of truth and belief [Dubois and Prade, 2001]. Uncertainty of formulas in possibilistic logic is not subject to the complement rule as in probability theory [Agarwal and Nayal, 2015; Dubois and Prade, 1993]. Indeed, complementary formulas may be considered fully possible, meaning complete ignorance about their truth value.

Example 1. Consider a doctor who has to diagnose a patient that suffers from extreme fatigue. A doctor can consider blood-related conditions: iron deficiency, iron overload, and vitamin B12 deficiency. Within possibility theory, one can model cases of complete uncertainty. Both iron deficiency and iron overload, which are two mutually exclusive conditions, can be considered fully possible. Consider that vitamin B12 deficiency is considered to be less possible, e.g. associated with the value 1/3, based on some information provided by the patient. In probability theory, complete ignorance of the first two conditions would make us assign probability 1/3 to every condition (Laplace criterion). Thus, it would not model the knowledge about vitamin B12 deficiency and the ignorance about iron deficiency and iron overload. ◁

∗Contact Author: Ana.Ozaki@uib.no

Although possibilistic logic has been extensively studied [Dubois and Prade, 2015], there are not many works that investigate learnability of possibilistic theories. In this work, we partially cover this gap by studying whether possibilistic theories are learnable in Angluin's exact learning model [Angluin, 1988]. In this model, a learner interacts with a teacher to exactly identify an abstract target concept. One can see the doctor, in Example 1, as a learner who inquires the patient (playing the role of a teacher) in order to identify a disease.

The most studied communication protocol in this model contains queries of two kinds, called membership and equivalence queries. Membership queries allow the learner to know whether a certain statement holds. Equivalence queries allow the learner to check whether a hypothesis (e.g. a diagnose) is correct and, if not, to fix it using a counterexample. In our toy scenario, the patient may not be able to provide a counterexample but new symptoms or reactions can reveal that the hypothesis is not correct. To the best of our knowledge, this is the first work where learnability of possibilistic theories is investigated in Angluin's model. We consider cases in which only membership, only equivalence, and both kinds of queries can be posed by the learner. We also study whether known polynomial time exact learning results for classical logic can be transferred to possibilistic settings.

Our main result is that, for a large class of problems, polynomial time learnability (with both types of queries) can be transferred from classical logic to the respective possibilistic extension (Theorem 17). If only membership queries are allowed (and the maximal precision of valuations in the target is fixed) then polynomial time learnability of a classical logic can also be transferred to the possibilistic extension. We leave open the case in which only equivalence queries can be asked. With our main result, we establish, e.g., that the possibilistic extension of propositional Horn [Angluin et al., 1992; Frazier and Pitt, 1993; Hermo and Ozaki, 2020] and fragments of first-order Horn [Arimura, 1997; Reddy and Tadepalli, 1998; Konev et al., 2018] are exactly learnable in polynomial time. As polynomial time learnability in the exact model is transferable to the probably approximately correct (PAC) [Valiant, 1984] model extended with membership queries, our work also establishes such results in this model.

Related Work. Among the works that combine learning and possibilistic logic, we can find results on learning possibilistic logic theories from default rules within the PAC learning model [Kuzelka et al., 2016]. Possibilistic logic has been used to reason with default rules [Benferhat et al., 1992] to select the most plausible rule and in inductive logic programming to handle exceptions [Serrurier and Prade, 2007]. In statistical relational learning, possibilistic logic has been used as a formal encoding of statistical regularities found in relational data [Kuzelka et al., 2017]. Possibilistic formulas can encode Markov logic networks [Kuzelka et al., 2015]. Formal concept analysis has been applied to generate attribute implications with a degree of certainty [Djouadi et al., 2010]. We also point out an extension of version space learning that deals with examples associated with possibility degrees [Prade and Serrurier, 2008].

In Section 2, we present basic definitions. In Section 3, we investigate whether possibilistic logic theories can be learned and, in Section 4, we show transferability of polynomial time learnability results.

2 Basics

In the following, we provide relevant notions of possibilistic logic and learning theory used in the paper.

2.1 Possibilistic Theories

Let L be a propositional or a first-order (FO) language (restricted to well-formed formulas without free variables) with the semantics of classical FO logic. We say that ϕ ∈ L is satisfiable if there is an interpretation I such that ϕ is satisfied in I. Moreover, ϕ is falsifiable if its negation ¬ϕ is satisfiable. An FO knowledge base (FO KB) is a finite set of FO formulas. An FO KB is non-trivial if it is satisfiable and falsifiable. The possibilistic extension of an FO language L is defined as follows. A possibilistic formula is a pair (ϕ, α), where ϕ ∈ L and α is a real number (with finite precision) in the interval (0, 1], called the valuation of ϕ. A possibilistic KB (or a possibilistic theory) is a finite set K of possibilistic formulas. Given a set Ω of interpretations for L, a possibility distribution π is a function from Ω to the interval [0, 1]. The possibility and necessity measures, Π and N, are functions (induced by π) from L to [0, 1], defined respectively as

A possibility distribution π satisfies a possibilistic formula (ϕ, α), written π |= (ϕ, α), if N(ϕ) ≥ α, and it satisfies a possibilistic KB K = {(ϕi, αi) | 0 ≤ i < n} if it satisfies each (ϕi, αi) ∈ K. We have that (ϕ, α) is entailed by K, written K |= (ϕ, α), if all possibility distributions that satisfy K also satisfy (ϕ, α). Given K as above and I ∈ Ω, we define the possibility distribution πK as follows: πK(I) = 1, if I |= ϕi, for every (ϕi, αi) ∈ K; otherwise, πK(I) = min{1-αi | I |= ¬ϕi, 0 ≤ i < n}.

The FO projection of K is the set K∗ = {ϕi | (ϕi, αi) ∈ K}. The α-cut and the α-cut of K, with α ∈ (0, 1], are defined respectively as Kα = {(ϕ, β) ∈ K | β ≥ α} and Kα = {(ϕ, β) ∈ K | β > α}. The set of all valuations occurring in K is Kv = {α | (ϕ, α) ∈ K}. Moreover, val(ϕ, K) = sup{α | K |= (ϕ, α)} is the least upper bound of the valuations of formulas entailed by K. Finally, the inconsistency degree of K is defined as inc(K) = sup{α | K |= (⊥, α)}.

Lemma 2. [Didier Dubois and Prade, 1994] Let K be a possibilistic KB. For every possibilistic formula (φ, α),

1. K |= (φ, α) iff K∗α |= φ;

2. K |= (φ, α) iff α ≤ val(φ, K); and

Proof. Point 1 is a consequence of Propositions 3.5.2, 3.5.5, and 3.5.6, and Point 2 is Property 1 at page 453 in [Didier Dubois and Prade, 1994]. We argue about Point 3. By definition of πK, for all I ∈ Ω, πK(I) is either 1 or 1 - β for some β ∈ Kv . Let NK be the necessity measure induced by πK. By definition of NK, NK(φ) = inf{1 - πK(I) | I ∈ Ω, I |= ¬ϕ}. Then, NK(φ) ∈ Kv ∪ {0, 1} (recall that inf{} is 1, which is the case for tautologies). By the semantics of possibilistic logic, NK(φ) = val(φ, K) [Didier Dubois and Prade, 1994, Corollary 3.2.3]. As (φ, α) is a possibilistic formula, α > 0. So, by Point 2, NK(φ) = val(φ, K) ∈ Kv ∪ {1}.

We denote by =p the operator that checks if two numbers are equal up to precision p. For example 0.124 =2 0.12345 but 0.124 ̸=3 0.12345. Assume α ∈ (0, 1] has finite precision. We write prec(α) for the precision of α and prec(t) for sup{prec(α) | (φ, α) ∈ t}. Given an interval I, we write Ip for the set containing all α ∈ I with prec(α) = p.

Example 3. One can express (1) mutual exclusion of iron deficiency and iron overload and (2) lower necessity of iron overload to be the cause of fatigue than iron deficiency with the possibilistic KB {(∀x(IronDef(x) → ¬IronOver(x)), 1), (∀x(IronDef(x) → Fatigue(x)), 0.9), (∀x(IronOver(x) → Fatigue(x), 0.8)}. ◁

2.2 Learnability

In learning theory, examples are pieces of information that characterise an abstract target the learner wants to learn. We consider the problem of learning targets represented in decidable fragments of FO logic or in their possibilistic extensions. Examples in our case are formulas expressed in the chosen logic (in this context called 'entailments').

A learning framework F is a pair (E, L); where E is a nonempty and countable set of examples, and L is a non-empty and countable set of concept representations (also called hypothesis space). Each element l of L is assumed to be represented using a finite set of symbols Σl (the signature of l). In all learning frameworks considered in this work, E is a set of formulas and L is a set of KBs (in a chosen language). We say that e ∈ E is a positive example for l ∈ L if l |= e and a negative example for l if l ̸|= e. Given a learning framework F = (E,L), we are interested in the exact identification of a target t ∈ L, by posing queries to oracles. Let MQF,t be the oracle that takes as input some e ∈ E and returns 'yes' if t |= e and 'no' otherwise. A membership query is a call to the oracle MQF,t. Given t, h ∈ L, a counterexample for t and h is an example e ∈ E s.t. t |= e and h ̸|= e (or vice-versa, h |= e and t ̸|= e). For every t ∈ L, we denote by EQF,t an oracle that takes as input a hypothesis h ∈ L and returns 'yes' if h ≡ t and a counterexample otherwise. There is no assumption regarding which counterexample is chosen by the oracle. An equivalence query is a call to EQF,t.

Example 4. A blood test to check for vitamin B12 deficiency on patient 42 can be modelled with a call to MQF,t with (B12Def(patient 42), α) for some α ∈ (0, 1] as input (depending on the result and accuracy of the test). ◁

A learner for F = (E, L) is a deterministic algorithm that, for a fixed but arbitrary t ∈ L, takes Σt as input, is allowed to pose queries to MQF,t and EQF,t (without knowing the target t), and that eventually halts and outputs some h ∈ L with h ≡ t. This notion of an algorithm with access to oracles can be formalised using learning systems [Watanabe, 1990], where posing a query to an oracle means writing down the query in an (additional) communication tape, entering in a query state, and waiting. The oracle then writes the answer in the communication tape, enters in an answer state, and stops. After that, the learner resumes its execution and can now read the answer in the communication tape.

We say that F is (exactly) learnable if there is a learner for F and that F is polynomial time learnable if it is learnable by a learner A such that at every step (the time used by an oracle to write an answer is not taken into account) of computation the time used by A up to that step is bounded by a polynomial p(|t|, |e|), where t ∈ L is the target and e ∈ E is the largest counterexample seen so far. We denote by PTIMEL the class of learning frameworks which are polynomial time learnable and the complexity of the entailment problem is in PTIME 1 . We also consider cases in which the learner can only pose one type of query (only membership or only equivalence queries). Whenever this is the case we write this explicitly.

Let F = (E, L) be a learning framework where E is a set of FO formulas and L is a set of FO KBs. We call such F an FO learning framework. We say that F is non-trivial if L contains a non-trivial FOKB; and that it is safe if l ∈ L implies that l′ ∈ L, for all l′ ⊆ l. A possibilistic extension lπ of an FO KB l is a possibilistic KB obtained by adding a possibilistic valuation α to every formula ϕ ∈ l. The possibilistic extension Fπ of F is the pair (Eπ, Lπ) where Lπ is the set of all possibilistic extensions of each l ∈ L, and Eπ is the set of all possibilistic formulas entailed by an element of Lπ.

We write N+ for the set of positive natural numbers. Given p ∈ N+, we denote by Fpπ = (Eπ, Lpπ ) the result of removing from Lπ in Fπ every l ∈ Lπ that does not satisfy prec(l) = p.

Remark 1. Let F = (E, L) be an FO learning framework and let t ∈ L be the target. If a learner A has access to MQF,t then we can assume w.l.o.g. that all counterexamples returned by EQF,t are positive: the learner can check whether each φ ∈ h is entailed by t. The same holds for Fπ.

1 In general, non-trivial algorithms need to perform entailment checks to combine the information of the examples. So polynomial time learning algorithms are normally for logics in which the entailment problem is tractable. This is the case e.g. for the Horn results mentioned in the Introduction.

3 Learnability Results

We start by studying the problem of whether there is a learner for a learning framework such that it always terminates with a hypothesis equivalent to the target. The main difficulty in learning with only membership queries (even for plain FO settings) is that the learner would 'not know' whether it has found a formula equivalent to a (non-trivial) target.

Example 5. Let Φn := ∃x1 . . . ∃xn. ∧0≤i<n r(xi, xi+1). A learner may ask membership queries of the form ∃x0Φn for an arbitrarily large n without being able to distinguish whether the target theory is ∃x0Φn or ∀x0(Φn → Φn+1) (knowing the signature of the target theory does not help the learner). ◁

For possibilistic theories, another difficulty arises even for the propositional case. As the precision of a formula can be arbitrarily high, the learner may not know when to stop (e.g., is the target (p, 0.1)? or (p, 0.11)?). Theorem 6 states that, except for trivial cases, learnability cannot be guaranteed.

Theorem 6. Let F be a non-trivial FO learning framework. Fπ is not (exactly) learnable with only membership queries.

Sketch. The existence of a learner A for the possibilistic extension Fπ = (Eπ, Lπ) of a non-trivial learning framework F would imply the existence of a procedure that terminates in n steps. A would not distinguish between the elements of Lπ with precision higher than n.

If the precision of the target is known or fixed, learnability of an FO learning framework can be transferred to its possibilistic extension. We state this in Theorem 8. To show this theorem, we use the following technical result.

Lemma 7. Let t be a possibilistic KB. Let I be a set of valuations such that tv ⊆ I. If for each α ∈ I there is some FO KB k∗α such that k∗α ≡ t∗α then t ≡ {(φ, α) | φ ∈ k∗α, α ∈ I}.

Proof. Let h = {(φ, α) | φ ∈ k∗α, α ∈ I}. Assume h |= (φ, γ). If γ = 1 and γ ̸∈ I then φ is a tautology. In this case, for all β ∈ (0, 1], t |= (φ, β). Suppose this is not the case. By Points 2 and 3 of Lemma 2, γ ≤ α, α = val(φ, h) ∈ hv ∪ {1}. Also, h |= (φ, α). By construction of h, hv = I, so α ∈ I. Moreover, for every β ∈ I, we know that h∗β = k∗β . Therefore k∗α ≡ h∗α. By Point 1 of Lemma 2, h |= (φ, α) implies h∗α |= φ. Then, k∗α |= φ. As k∗α ≡ t∗α, we have that t∗α |= φ. Again by Point 1 (of Lemma 2), t∗α |= φ iff t |= (φ, α). Since α ≥ γ, t |= (φ, γ) by Point 2. The other direction can be proved similarly.

Theorem 8. Suppose F is an FO learning framework that is learnable with only membership queries. For all p ∈ N+, Fpπ = (Eπ, Lpπ ) is learnable with only membership queries.

Proof. Let A be a learner for F and let t ∈ Lpπ be the target. For each α ∈ (0, 1]p, we run an instance of A, denoted Aα. Whenever Aα calls MQF,t∗α with φ as input, we call MQFπ,t with (φ, α) as input. By Point 1 of Lemma 2, MQF,t∗α (φ) = MQFπ,t(φ, α). Since A is a learner for F, every Aα eventually halts and outputs a hypothesis k∗α such that k∗α ≡ t∗α. Since t ∈ Lpπ , tv ⊆ (0, 1]p. By Lemma 7, t ≡ {(φ, α) | φ ∈ k∗α, α ∈ (0, 1]p}. Thus, we can transfer learnability of F (with only membership queries) to Fpπ .

If, e.g., MQFπ,t((φ, 0.01)) = 'yes', MQFπ,t((φ, 0.02)) = 'no', and the precision of the target is 2, then val(φ, t) = 0.01. So, knowing the precision is important for learning with membership queries only. If equivalence queries are allowed then a learner can build a hypothesis equivalent to the target without knowing the precision in advance by simply enumerating all possible hypothesis and asking them to the oracle, one by one (Theorem 9).

Theorem 9. The possibilistic extension Fπ of an FO learning framework F is learnable with only equivalence queries.

If both membership and equivalence query oracles are available, learnability is guaranteed by the previous theorem.

Corollary 1. Let F be an FO learning framework. F is learnable iff Fπ is learnable.

4 Polynomial Time Reduction

We now investigate whether results showing that an FO learning framework is in PTIMEL can be transferred to their possibilistic extensions and vice-versa. Theorem 10 shows the transferability of PTIMEL membership from the possibilistic extension Fπ of an FO learning framework F to F.

Theorem 10. Let F be an FO learning framework. If Fπ is in PTIMEL then F is in PTIMEL.

Proof. In our proof, we use the following claim.

Claim 10.1. Let k be an FO KB and let t be the possibilistic KB {(φ, 1) | φ ∈ k}. For all (φ, α), k |= φ iff t |= (φ, α).

Proof. If t |= (φ, α), since t∗ |= t∗α and k = t∗ , k |= φ. If k |= φ, by construction t∗1 |= φ. By Point 1 of Lemma 2, t∗1 |= φ iff t |= (φ, 1), so, for all α ∈ (0, 1], t |= (φ, α).

Let F = (E,L) and let k ∈ L be the target. Since Fπ is in PTIMEL, there is a learner Aπ for Fπ. We start the execution of Aπ that attempts to learn a hypothesis h equivalent to t = {(φ, 1) | φ ∈ k}. By Claim 10.1, for all α ∈ (0, 1], MQFπ,t((φ, α)) = MQF,k(φ). Also, we can simulate a call to EQFπ,t with h as input by calling EQF,k with h∗ as input. By Claim 10.1, for all α ∈ (0, 1], k |= φ iff t |= (φ, α), in particular, for α = 1. By Remark 1, we can assume that all counterexamples returned by EQF,k are positive. Whenever we receive a (positive) counterexample φ, we return (φ, 1) to Aπ. Eventually, Aπ will output a hypothesis h ≡ t in polynomial time w.r.t. |t| and the largest counterexample received so far. Clearly, h∗ is as required.

By Theorem 11, the converse of Theorem 10 does not hold.

Theorem 11. There exists an FO learning framework F such that F is in PTIMEL but Fπ = (Eπ, Lπ) is not in PTIMEL.

Proof. Let F = (E,L) be an FO learning framework that is not in PTIMEL. Such F exists, one can consider, for instance, the EL learning framework [Konev et al., 2018, Theorem 68] 2 . We use F to define the learning framework F⊥ = (E,L⊥) where L⊥ = {h ∪ {φ, ¬φ} | h ∈ L} for a fixed but arbitrary non-trivial FO formula φ. Even though F is not learnable in polynomial time, F⊥ is. The learner can learn any l ∈ L⊥ by returning the hypothesis {⊥} (in constant time). Assume that F⊥π = (Eπ, L⊥π ) is in PTIMEL. This means that for every target l ∈ L⊥π we can learn in polynomial time a hypothesis h such that h ≡ l. By construction, for every t ∈ L there is l ∈ L⊥π such that t ≡ l∗ inc(l) . By learning h such that h ≡ l we have also learned a hypothesis h such that h∗inc(h) ≡ t. By Theorem 10, F ∈ PTIMEL, which contradicts our assumption that this is not the case. Therefore we have found an FO learning framework F⊥ that is is in PTIMEL but its possibilistic extension F⊥π is not in PTIMEL.

The FO learning framework F⊥ in the proof of Theorem 11 is not safe (see definition in Subsection 2.2) because, for l ̸⊆ {φ, ¬φ} we have l ∈ L⊥ with (l \{φ, ¬φ}) ̸∈ L⊥. Intuitively, non-safe learning frameworks allow cases in which the target is easy to learn if we aim at learning the whole target, not a subset of it. In the following, we focus on FO learning frameworks that are safe 3 . The first transferability result we present is for the case in which the learner has access to only membership queries. To show the reduction, we use a procedure called FindValuationt. This procedure takes as input a precision p and a formula φ and returns the highest valuation β with precision p of a formula φ entailed by the target t (or zero if it is not entailed). That is, β is such that β =p val(φ, t). For any γ ∈ [0, 1]p the procedure can check if t |= (φ, γ) by calling the oracle MQFπ,t with (φ, γ) as input. To compute β such that β =p val(φ, t), FindValuationt performs a binary search on [0, 1]p. Lemma 12 states the correctness and the complexity of FindValuationt.

Lemma 12. Let Fπ = (Eπ,Lπ) be a possibilistic learning framework and let t ∈ Lπ be the target. FindValuationt, with input a precision p ∈ N+ and φ ∈ Eπ, runs in polynomial time in p and |φ| and outputs β such that β =p val(φ, t).

Sketch. By Point 2 of Lemma 2, FindValuationt can determine β such that β =p val(φ, t) by performing a binary search on the interval of numbers [0, 1]p. So the number of iterations is bounded by log2(10p + 1), which is polynomial in p. Each iteration can be performed in polynomial time in |φ| and p.

By Thm. 13, for safe FO learning frameworks, polynomial time results with only membership queries can be transferred to their possibilistic extensions if the precision of the target is known (by Thm. 6, we cannot remove this assumption).

Theorem 13. Let F be a safe FO learning framework. For all p ∈ N+, when only membership queries can be asked, F is in PTIMEL iff Fpπ is in PTIMEL.

2 Non-polynomial query learnability is proved in [Konev et al., 2018, Theorem 68], which implies non-polynomial time learnability.

3 All learning from entailment results we found in the literature could be formulated in terms of safe learning frameworks.

Proof. To show the transferability of PTIMEL membership from F to Fπ, we use the following claim.

Claim 13.1. Assume F = (E, L) is safe and in PTIMEL with only membership queries. For every p ∈ N+ and framework Fpπ = (Eπ, Lpπ ) with t ∈ Lpπ , given a valuation α with prec(α) = p, one can learn k∗α such that k∗α ≡ t∗α in time polynomial w.r.t. |t| with only membership queries.

Proof. We start the execution of a polynomial time learner A for F. Whenever A calls MQF,t∗α with φ as input, we call MQFπ,t with (φ, α + 10-p ) as input and we return the same answer to A. By Point 1 of Lemma 2, MQF,t∗α (φ) = MQFπ,t(φ, α + 10-p ). Since F is safe, A will build a hypothesis k∗α such that k∗α ≡ t∗α in polynomial time w.r.t. |t|.

We set γ := 0 and S := ∅. By Claim 13.1 we can find in polynomial time w.r.t. |t| a hypothesis k∗ γ such that k∗ γ ≡ t∗γ . For every φ ∈ k∗ γ , we run FindValuationt with p = prec(t) and φ as input to find val(φ, t). In this way, by Point 3 of Lemma 2 and Lemma 12, we identify in polynomial time w.r.t. |t| some β ∈ tv ∪ {1} such that k∗ γ ≡ t∗β . We set k∗β := k∗ γ and add k∗β to S. Then, we update γ to the value β and apply Claim 13.1 again. For every φ ∈ k∗ γ , we run FindValuationt again with p = prec(t) and φ as input to find val(φ, t). We repeat this process until we find k∗ γ ≡ ∅ or γ+10-p > 1. Each time we run FindValuationt, we identify a higher valuation in tv . Therefore, this happens at most |tv | times. For all α ∈ tv , there is k∗α ∈ S that satisfies k∗α ≡ t∗α, therefore, by Lemma 7,

is such that h ≡ t.

We now show the transferability of PTIMEL membership from Fπ to F. Let k ∈ L be the target. We start the execution of a learner Aπ for Fπ that attempts to learn a hypothesis equivalent to t = {(φ, 1) | φ ∈ k}. By Claim 10.1 of Theorem 10, we can simulate a call to MQFπ,t with input (φ, 1) by calling MQF,k with φ as input and returning the same answer to Aπ. Aπ terminates in polynomial time w.r.t. |t| with a hypothesis h such that h ≡ t. As h∗ ≡ t∗ = k, h∗ is as required.

When we want to transfer learnability results from F to Fπ it is important to learn one hα such that hα ≡ tα for each α ∈ tv , where t is the target (Example 14).

Example 14. Let t = {(p → q1, 0.3), (p → q2, 0.7)}. We can use the polynomial time algorithm for propositional Horn [Frazier and Pitt, 1993] to learn a hypothesis k∗ = {p → (q1 ∧ q2)} ≡ t∗ . However, if h = {(φ, val(φ, t)) | φ ∈ k∗ } then h = {(p → (q1 ∧ q2), 0.3)} ̸≡ t.

A learner that has access to both membership and equivalence query oracle has a way of finding the precision of the target when it is unknown. With membership queries, we can use FindValuationt to find the valuation of formulas up to a given precision. By Lemma 15, we can obtain useful information about the precision of the target with the counterexamples obtained after an equivalence query.

Lemma 15. Assume Fπ = (Eπ,Lπ) is the possibilistic extension of a safe FO learning framework and t ∈ Lπ is the target. Given p ∈ N+, one can determine that p < prec(t) or compute h ∈ Lπ such that h ≡ t, in polynomial time w.r.t. |t|, p, and the largest counterexample seen so far.

Proof. In our proof, we use the following claims.

Claim 15.1. Given h ∈ Lπ such that t |= h, one can construct in polynomial time in |h| some h′ ∈ Lπ such that t |= h′ |= h and, for all (φ, α) ∈ h′ , t |= (φ, α) and α =prec(h′ ) val(φ, t).

Proof. Let h′ be the set of all (φ, β) such that (φ, α) ∈ h and FindValuationt returns β with φ and prec(h) as input. As t |= h, by construction of h′ , t |= h′ |= h. By Lemma 12, h′ can be constructed in polynomial time in |h| and is as required.

Claim 15.2. Let h ∈ Lπ be such that, for all (φ, α) ∈ h, t |= (φ, α) and α =prec(h) val(φ, t). If EQFπ,t with input h returns (φ, α) then either we know that prec(t) > prec(h) or h∗β ̸|= φ where β =prec(h) val(φ, t).

Proof. By Point 1 of Lemma 2, h∗β |= φ iff h |= (φ, β). If h |= (φ, β) or β = 0 (note: β can be 0 because, e.g., 0.01 =1 0), then prec(val(φ, t)) > prec(h). By Point 3 of Lemma 2, val(φ, t) ∈ tv ∪ {1}, so prec(t) > prec(h).

By Remark 1, we can assume at all times in this proof that any hypothesis constructed is entailed by the target (possibilistic or not). Moreover, by Claim 15.1, we can assume that, for any target and hypothesis t, h ∈ Lπ, we have that, for all (φ, α) ∈ h, t |= (φ, α) and α =prec(h) val(φ, t). So we can assume at all times in our proof that the hypothesis h we construct (Equation 1) satisfies the conditions of Claim 15.2.

Let A be a polynomial time learner 4 for F. As in the proof of Theorem 13, we run multiple instances of A. We denote by R the set of instances of A. Each instance in R is denoted Aβ and attempts to learn a hypothesis equivalent to t∗β , where β is a valuation. We sometimes write Anβ to indicate that the instance Aβ has asked n equivalence queries so far. We denote by kβ,n the hypothesis given as input by Anβ when it asks its n-th equivalence query. For n = 0, we assume that kβ,n = ∅.

Initially, R := {A010-p}. Whenever Aβ ∈ R asks a membership query with input φ ∈ E, by Point 1 of Lemma 2, we can simulate MQF,t∗β by calling MQFπ,t with (φ, β) as input and returning the same answer to Aβ. Let h0 be {(φ⊤, α)} where φ⊤ is a tautology and α is a valuation with prec(α) = p. Whenever Anβ ∈ R asks its n-th equivalence query, we leave Anβ waiting in the query state (see description of a learning system in Subsection 2.2). When all Amα ∈ R are waiting in the query state, we create

4 Assume w.l.o.g. that A always eventually asks an equivalence query until it finds an equivalent hypothesis (but may execute other steps and ask membership queries between each equivalence query).

and call EQFπ,t with h as input (note: each instance Aα ∈ R may have asked a different number of equivalence queries when Anβ asks its n-th equivalence query). If the answer is 'yes', we have computed h such that h ≡ t and we are done. Upon receiving a (positive) counterexample (φ, γ), we run FindValuationt with φ and prec(h) as input and compute a valuation β such that β =prec(h) val(φ, t) (Lemma 12). If Aβ ̸∈ R, we start the execution of the instance Aβ of algorithm A and add Aβ to R. Otherwise, Aβ ∈ R and we check whether kβ,m |= φ (assume m is the number of equivalence queries posed so far by Aβ). If kβ,m |= φ then, by Claim 15.2, we know that prec(h) < prec(t) then we are done. If kβ,m ̸|= φ then φ is a (positive) counterexample for kβ,m and t∗β . We return φ to every Amα ∈ R such that α ≤ β and kα,m ̸|= φ and these instances resume their executions. Observe that, since h0 ⊆ h, by the construction of h, at all times prec(h) = p.

We now argue that this procedure terminates in polynomial time w.r.t. |t|, p, and the largest counterexample seen so far. Since there is only one instance Aβ in R for each valuation β such that β =p val(φ, t), by Point 3 of Lemma 2, we have that at all times |R| is linear in |tv |, which is bounded by |t|. By Lemma 12, whenever we run FindValuationt to compute a valuation with φ and p as input, only polynomially many steps in |φ| and p are needed. Since F is safe and A is a polynomial time learner for F either we can determine that p < prec(t) or each Aβ ∈ R terminates, in polynomial time in the size of t∗β and the largest counterexample seen so far, and outputs kβ,n = h∗β such that h∗β ≡ t∗β . In this case, by Lemma 7, h ≡ t and the process terminates.

The constructive proof of Lemma 15 delineates the steps made in Example 16 where the precision of the target is 1.

Example 16. Let F = (E, L) be the safe learning framework where L is the set of all propositional Horn KBs and E is the set of all (propositional) Horn clauses. Let t ∈ Lπ and A be, respectively, the target and the learner of Example 14. Following our argument in Lemma 15, we start an instance A0.1 of A. When A0.1 is waiting in the query state, we build h = {(φ⊤, 0.1)} (Equation 1) and call EQFπ,t with h as input (Point (a) in Figure 1). Assume we receive the positive counterexample (p → q1, 0.1). We run FindValuationt with 1 and p → q1 as input, which computes val(p → q1, t) = 0.3. Since A0.3 ̸∈ R, we start A0.3. When all learners are waiting in the query state, we call again EQFπ,t with h as input (Point (b) in Figure 1). At this point, R = {A0.1, A0.3}.

Assume we receive (p → q1, 0.1) again. We have that val(p → q1, t) = 0.3 and A0.3 ∈ R. Since k0.3,1 ̸|= p → q1

and k0.1,1 ̸|= p → q1, we return p → q1 to both A10.1 and A10.3 and they resume their executions. All learners will eventually be waiting in query state. When this happens we call EQFπ,t with h′ = {(φ⊤, 0.1), (p → q1, 0.1), (p → q1, 0.3)} as input.

Assume the response is (p → q2, 0.21). We run FindValuationt with 1 and p → q2 as input, which returns val(p → q2, t) = 0.7. As before, we start A0.7 (Point (c) in Figure 1) and add it to R. When all learners are waiting again we call EQFπ,t with h′ as input. Assume we receive (p → q2, 0.1). We then send p → q2 to every learner in R. Next time we call EQFπ,t, with h′ ∪ {(p → q2, 0.7), (p → q2, 0.3), (p → q2, 0.1)} as input. The answer is 'yes' and we are done. ◁

A direct consequence of Lemma 15 is Theorem 17.

Theorem 17. For every safe FO learning frameworks F we have, F is in PTIMEL iff Fπ is in PTIMEL.

Proof. One direction holds by Theorem 10. We prove the other direction. Let F be a safe FO learning framework in PTIMEL and let Fπ = (Eπ, Lπ) be its possibilistic extension. Consider a learner that initially estimates precision p of the target t ∈ Lπ to be 1. Using Lemma 15, we can assume that this learner can either determine that p < prec(t) or find a hypothesis h such that h ≡ t, in time polynomial with respect to |t|, p and the largest counterexample seen so far. In the former case, this learner sets the estimated precision p of the target to p + 1. This happens at most prec(t) times, which is bounded by |t|. As a consequence, Fπ is in PTIMEL.

We end this section recalling that our results can be transferred to the PAC model [Valiant, 1984] extended with membership queries (Theorem 18).

Theorem 18 ([Angluin, 1988; Mohri et al., 2012]). Let PTIMEPL be the class of all learning frameworks that are PAC learnable with membership queries in polynomial time. Then, PTIMEL ⊆ PTIMEPL.

By Theorems 17 and 18, the following holds.

Corollary 2. For all safe FO learning frameworks F, if F ∈ PTIMEL then Fπ ∈ PTIMEPL.

5 Conclusion

Uncertainty is widespread in learning processes. Among different uncertainty formalisms, possibilistic logic stands out because of its ability to express preferences among worlds and model ignorance. We presented the first study on the exact (polynomial) learnability of possibilistic theories. It follows from our results that various algorithms designed for exact learning fragments of first-order logic can be adapted to learn their possibilistic extensions. We leave open the problem of polynomial time transferability with only equivalence queries.

Acknowledgements

We are supported by the University of Bergen. We would like to thank Andrea Mazzullo for joining initial discussions.