Abduction for (non-ominiscient) agents

Abduction for (non-omniscient) agents Fernando Soler-Toscano and Fernando R. Vel´ azquez-Quesada Abstract Among the non-monotonic reasoning processes, abduction is one of the most important. Usually described as the process of looking for explanations, it has been recognized as one of the most commonly used in our daily activities. Still, the traditional definitions of an abductive problem and an abductive solution mention only theories and formulas, leaving agency out of the picture. Our work proposes a study of abductive reasoning from an epistemic and dynamic perspective, making special emphasis on non-ideal agents. We begin by exploring what an abductive problem is in terms of an agent’s information, and what an abductive solution is in terms of the actions that modify it. Then we explore the different kinds of abductive problems and abductive solutions that arise when we consider agents whose information is not closed under logical consequence, and agents whose reasoning abilities are not complete. 1 Abductive reasoning Beyond the obvious facts that he has at some time done manual labour, that he takes snuff, that he is a Freemason, that he has been in China, and that he has done a considerable amount of writing lately, I can [get] nothing else. Sherlock Holmes The Red-Headed League Among the non-monotonic reasoning processes, abduction [1] is one of the most important. Usually described as the process of looking for an explanation, it has been recognized as one of the most commonly used in our daily activities. Observing that Mr. Wilson’s right cuffis very shiny for five inches and the left one has a smooth patch near the elbow, Holmes assumes that he (Mr. Wilson) has done a considerable amount of writing lately. Given the symptoms Aand B, a doctor suspects that the patient suffers from C. Karen knows that when it rains, the grass gets wet, and that the grass is wet right now; then, she suspects that it has rained. 1 51 But though traditional examples of abductive reasoning are given in terms of an agent’s information and its changes, classical definitions of an abductive problem and its solutions are given in terms of theories and formulas, without mentioning the agent’s information and how it is modified. The present work proposes a study of abductive reasoning from an epistemic and dynamic perspective. After recalling the classical definitions of an abductive problem and an abductive solution (the rest of the current section), we explore what an abductive problem is in terms of the agent’s information, and what an abductive solution is in terms of the actions that modify it (Section 2). Then we focus on non-ideal agents, analyzing not only the cases that arise when the agent’s information is not closed under logical consequence (Section 3) but also those that arise when the agent’s reasoning abilities are not complete (Section 4). We finish with a summary, proposing lines for further work (Section 5). In this paper we will use the term information in the most general sense, with the notions of knowledge or belief being particular instances that impose further restrictions, like truth or consistency. Moreover, though we will use formulas in Epistemic Logic (EL; [9]) and Dynamic Epistemic Logic style (DEL; [5]), we will not commit ourselves to any particular semantic model. The main goal of this work is to explore the possibilities and concepts that emerge from a dynamic epistemic analysis of abductive reasoning. 1.1 The classical approach to abduction Traditionally, it is said that there is an abductive problem when there is a formula χthat is not predicted by the current theory Φ. Recently, it has been observed that, even if the theory does not entail χ, it might entail its negation. Following [1], we can identify two basic abductive problems. Definition 1.1 (Abductive problem).Let Φand χbe a theory and a formula, respectively, in some language L. Let �be a consequence relation on L. The pair (Φ, χ) is a novel abductive problem when neither χnor ¬χare consequences of Φ, i.e., when Φ�χand Φ�¬χ The pair (Φ, χ) is an anomalous abductive problem when, though χis not a consequences of Φ,¬χis, i.e., when Φ�χand Φ� ¬χ Traditionally, a solution for an abductive problem (Φ, χ) is a formula ψ that, together with Φ, entails χ. This solves the problem because now the theory is strong enough to explain χ. The anomalous case requires an extra initial step, since adding directly such ψwill make the theory to entail both χand ¬χ. The agent should perform first a theory revision that stop ¬χfrom being a consequence of Φ. Here are the formal definitions. 2 52 Definition 1.2 (Abductive solution). •Given a novel abductive problem (Φ, χ), the formula ψis an abductive solution if Φ, ψ �χ •Given an anomalous abductive problem (Φ, χ), the formula ψis an abductive solution if it is possible to perform a theory revision to get a novel problem (Φ�, χ) for which ψis a solution. In some cases, Definition 1.2 is too weak since it allows trivial solutions, like χitself. Again, following [1], it is possible to make a further classification. Definition 1.3 (Classification of abductive solutions).Let (Φ, χ) be an abductive problem. An abductive solution ψis consistent if Φ, ψ �⊥ explanatory if ψ�χ minimal if, for every other abductive solution ϕ,ψ�ϕimplies ϕ�ψ The consistency requirement discards those ψinconsistent with Φand the explanatory requirement discards χitself. Minimality works as the Occam’s razor, asking for the solution ψto be logically equivalent to any other solution it implies. 2 From an agent’s perspective Most of the examples of abductive reasoning involve an agent and its information. It is Holmes who observes that Mr. Wilson’s right cuffis very shiny; it is a doctor who observes the symptoms Aand B; it is Karen who observes that the grass is wet. So when does an agent has an abductive problem (Φ, χ)? By interpreting Φas the agent’s information, we get the following definitions. We use formulas in EL style, where Inf ϕis read as “ϕis part of the agent’s information”. Definition 2.1 (Subjective abductive problem).Let χbe a formula. We say that an agent has a novel χ-abductive problem when neither χnor ¬χare part of her information, i.e., when the following formula holds: ¬Inf χ∧ ¬Inf ¬χ(1) We say that an agent has an anomalous χ-abductive problem when χis not part of her information but ¬χis, i.e., when the following formula holds: ¬Inf χ∧Inf ¬χ(2) 3 53 So an agent has a χ-abductive problem when χis not part of her information. What about an abductive solution? Definition 1.2 states that ψis a solution to a novel problem if, when added to the theory Φ, we get a theory that entails χ. But a theory is actually closed under logical consequence, so ψis a solution if, when added to the theory, makes χpart of the theory too. The anomalous case needs another step, since a revision is required first. We have identified Φwith the agent’s information. Then, a solution for the subjective novel case is a formula ψthat, when added to the agent’s information, makes the agent informed about χ. This highlights the fact the requisites of a solution involve an action; an action that changes the agent’s information by adding ψto it. In the subjective anomalous case, the action was already clear, since the theory should be modified. But now we can see that the requisites for this case involves two actions: removing a piece of information and then incorporating a new one. We will express changes in the agent’s information by using formulas in DEL style. In particular, formulas of the form �Addφ�ϕwill be read as “φcan be added to the agent’s information and, after that, ϕis the case”, and formulas of the form �Remφ�ϕwill be read as“φcan be removed from the agent’s information and, after that, ϕis the case”. Definition 2.2 (Subjective abductive solution).Suppose an agent has a novel χ-abductive problem, that is, ¬Inf χ∧ ¬Inf ¬χholds. A formula ψis an abductive solution to this problem if, when added to the agent’s information, the agent becomes informed about χ. In a formula, �Addψ�Inf χ Now suppose the agent has an anomalous χ-abductive problem, that is, ¬Inf χ∧Inf ¬χholds. A formula ψis an abductive solution to this problem if the agent can revise her information to remove ¬χfrom it and, after it, the incorporation of ψmakes χpart of her information. In a formula, �Rem¬χ��¬Inf ¬χ∧ �Addψ�Inf χ� What about the further classification for abductive solutions? We can also provide formulas that characterize them. Definition 2.3 (Classification of subjective abductive solutions).Suppose an agent has a χ-abductive problem. A formula ψis a(n) •consistent abductive solution if it is a solution and can be added to the agent’s information without making the latter inconsistent: �Addψ��Inf χ∧ ¬Inf ⊥� 4 54 •explanatory abductive solution if it is a solution and it does not imply χ, that is, it only complements the agent’s information to produce χ: ¬(ψ→χ)∧ �Addψ�Inf χ •minimal abductive solution if it is a solution and, for any ϕ, if ϕis a solution that becomes part of the agent’s information after ψis added, then ψalso becomes part of the agent’s information after ϕis added. �Addψ�Inf χ∧�(�Addϕ�Inf χ∧ �Addψ�Inf ϕ)→ �Addϕ�Inf ψ� 3 A non-omniscient agent In the classical definition of an abductive problem, the set of formulas Φis understood as a theory, usually assumed to be closed under logical consequence, as we mentioned before. If this is the case, then we have actually revised an omniscient case. But our agent does not need to be ideal. And if the agent’s information is not closed under logical consequence, then we should make a difference between the information she actually has, her explicit information, and what follows logically from it, her implicit information [12; 11; 15]. 3.1 Abductive problems A non-omniscient agent has an abductive problem whenever χis not part of her explicit information. As a consequence, the modality Inf in Definition 2.1 becomes InfEx . But now each of our two abductive problems splits into four, according to the agent’s implicit information (InfIm ) about χand ¬χ. These eight cases include inconsistent situations in which the agent is implicitly informed about both χand ¬χ. They can be discarded under particular interpretations of the agent’s information, like knowledge or consistent beliefs, but we have chosen to keep them here for the sake of generality. Still, not all these cases are possible. We have said that implicit information is what follows logically from the explicit one, so explicit information itself should be implicit information, that is, InfEx ϕ→InfIm ϕ By assuming this formula, we can drop the cases in which some formula is in the agent’s explicit information, but not in her implicit one. Definition 3.1 (Non-omniscient abductive problems).A non-omniscient agent can face six different abductive problems, each one of them characterized by a formula in Table 1. 5 55 ¬InfEx χ∧ ¬InfEx ¬χ∧                ¬InfIm χ∧ ¬InfIm ¬χ(1.1) InfIm χ∧ ¬InfIm ¬χ(1.2) ¬InfIm χ∧InfIm ¬χ(1.3) InfIm χ∧InfIm ¬χ(1.4) ¬InfEx χ∧InfEx ¬χ∧       ¬InfIm χ∧InfIm ¬χ(2.3) InfIm χ∧InfIm ¬χ(2.4) Table 1: Abductive problems for non-omniscient agents. Let us review each one of the novel cases. In case (1.1), the truly novel one, the agent lacks explicit and implicit information about both χand ¬χ; the formula χis a real novelty for her. But in case (1.2), the not implicit novelty one, though the agent does not have explicit information about neither χnot ¬χ, she has implicit information about χ. In other words, χis a novelty for the agent’s explicit information, but not for her implicit one since χfollows logically from what she explicitly has. In case (1.3), the implicitly anomaly one, the agent lacks explicit information about both χand ¬χ, but implicitly she is informed about ¬χ. Finally we have the implicitly inconsistent case, (1.4), in which the agent lacks explicit information about both χand ¬χ, but has an implicit inconsistency. Now for the anomalous cases. Case (2.3) is the truly anomalous one: the agent has both explicit and implicit information about ¬χ, and lacks both explicit and implicit information about χ. In the remaining one (2.4), called anomaly with implicit inconsistency, though the agent has explicit information about ¬χbut not about χ, the latter follows from her explicit information. Omniscience as a particular case An agent is omniscient when she has explicitly all her implicit information. With this extra requirement, expressed by the formula InfIm ϕ→InfEx ϕ, cases (1.2),(1.3),(1.4) and (2.4) can be discarded since explicit and implicit information do not coincide. This leaves us only with cases (1.1) and (2.3); exactly the two cases of Definition 2.1. 3.2 Abductive solutions We have defined non-omniscient χ-abductive problems as situations in the agent is not explicitly informed about χ. Accordingly, for defining a solution, we will look for an action (or a sequence of them) that makes the agent explicitly informed about χ, without having neither implicit nor explicit information about ¬χ. We will focus on cases (1.1),(1.2),(1.3) and (2.3), leaving the inconsistent ones, (1.4) and (2.4), for future work. Consider the truly novel case (1.1): the agent lacks explicit and implicit information about both χand ¬χ. Then, just like in the omniscient case, a solution is a formula ψthat when added to the agent’s explicit information makes the agent explicitly informed about χ. 6 56 Now consider the not implicit novelty case (1.2): though the agent does not have χexplicitly, she has it implicitly. A solution for case (1.1), adding some ψ, would also work here, but the agent does not really need this external interaction, since a non-omniscient agent has another possibility: she can make the implicit χexplicit by performing the adequate reasoning steps. And this gives us new possibilities not only this case. For example, in (1.1), the agent does not need a ψthat makes χexplicit after added: a ψ that makes χimplicit is also a solution, since now she can make χexplicit by only reasoning. In fact, there are several strategies for solving each one of the abductive problems, but for simplicity we will focus on the most representative one for each one of them. In case (1.3), reasoning will only make the anomaly explicit. But then the agent will be in the truly anomaly case (2.3), which can be solved by revising the agent’s information to remove ¬χfrom the explicit and implicit part, and then adding a ψthat makes χpart of her explicit information. In the following definition, formulas of the form �α�ϕindicates that the agent can perform some reasoning step αafter which ϕis the case. Definition 3.2 (Non-omniscient abductive solutions).Solutions for consistent non-omniscient abductive problems are provided in Table 2. Case Solution (1.1) A formula ψsuch that �Addψ�InfEx χ (1.2) A reasoning αsuch that �α�InfEx χ (1.3) A reasoning αand a formula ψsuch that �α��InfEx ¬χ∧ �Rem¬χ�(¬InfIm ¬χ∧ �Addψ�InfEx χ)� (2.3) A formula ψsuch that �Rem¬χ��¬InfIm ¬χ∧ �Addψ�InfEx χ� Table 2: Solutions for consistent non-omniscient abductive problems. Note how actions take us from some abductive problem to another. In case (1.3), the proper reasoning will take the agent to case (2.3) from which, by applying the proper revision, the agent will reach case (1.1), where a new piece of information is needed. The flowchart of Figure 1 shows this. Classification of abductive solutions The extra requisites of Definition 2.3 can be adapted in this non-omniscient case. For the consistency and the explanatory requirements there are no important changes: we just require for the agent’s implicit (and therefore her explicit information too) to be consistent at the end of the sequence of actions (¬InfIm ⊥), and for the formula ψto not imply χ(¬(ψ→χ)) in the cases in which it is needed 7 57 1.3 InfEx ¬χ2.3 ¬InfIm ¬χ1.1 InfEx χ 1.2 InfEx χSolved αRem¬χ Addψ α Yes No Yes No Yes Yes No No Figure 1: Flowchart of abductive solutions for non-omniscient agents. ((1.1),(1.3) and (2.3)). The minimality requirement now gives us more options. We can define it over the action �Addψ�, looking for the weakest formula ψ, but it can also be defined over the action �Rem¬χ�, looking for the revision that removes the smallest amount of information. It can even be defined over the action �α�, looking for the shortest reasoning chain. 4 A non-dynamically-omniscient agent Even though the agents of the previous section are non-omniscient, there is still an idealization about them. We have defined the agent’s implicit information as what follows logically from her explicit information, but a more ‘real’ agent does not need to be dynamically omniscient in the sense that she does not need to have complete reasoning abilities. In other words, she may not be able to derive all logical consequences of her explicit information. This difference is important, because then a solution for a χ-abductive problem does not need to be as strong as a formula that, when added, also informs explicitly the agent about χ; it can also be some formula that, when added, allow the agent to derive χ 4.1 Abductive problems Now we can make a further refinement. We can distinguish between what follows logically from the agent’s explicit information, the objective implicit information InfIm , and what the agent can actually derive, the subjective implicit information InfDer . In other words, InfDer ϕholds when the agent can perform a sequence of reasoning steps that make ϕexplicit information. In particular, an empty sequence of reasoning steps makes explicit the information that is already explicit, so we assume InfEx ϕ→InfDer ϕ 8 58 Though not complete, we can assume that the agent’s reasoning abilities are sound. This makes subjective implicit information part of objective implicit one, giving us InfDer ϕ→InfIm ϕ Each one of the six abductive problems of Table 1 turns into four cases, according to whether the agent can derive or not what follows logically from her explicit information, that is, according to whether InfDer χand InfDer ¬χhold or not. Our two assumptions allow us to discards some of the cases, leaving us with the following. Definition 4.1 (Extended abductive problems).A non-omniscient agent without complete reasoning abilities can face eleven different abductive problems, each one of them characterized by a formula in Table 3. ¬InfEx χ∧ ¬InfEx ¬χ∧�¬InfDer χ∧ ¬InfDer ¬χ�∧ ¬InfIm χ∧ ¬InfIm ¬χ(1.1.a) ¬InfEx χ∧ ¬InfEx ¬χ∧       ¬InfDer χ∧ ¬InfDer ¬χ InfDer χ∧ ¬InfDer ¬χ        ∧InfIm χ∧ ¬InfIm ¬χ(1.2.a) (1.2.b) ¬InfEx χ∧ ¬InfEx ¬χ∧       ¬InfDer χ∧ ¬InfDer ¬χ ¬InfDer χ∧InfDer ¬χ        ∧ ¬InfIm χ∧InfIm ¬χ(1.3.a) (1.3.c) ¬InfEx χ∧ ¬InfEx ¬χ∧                ¬InfDer χ∧ ¬InfDer ¬χ InfDer χ∧ ¬InfDer ¬χ ¬InfDer χ∧InfDer ¬χ InfDer χ∧InfDer ¬χ                ∧InfIm χ∧InfIm ¬χ (1.4.a) (1.4.b) (1.4.c) (1.4.d) ¬InfEx χ∧InfEx ¬χ∧�¬InfDer χ∧InfDer ¬χ�∧ ¬InfIm χ∧InfIm ¬χ(2.3.c) ¬InfEx χ∧InfEx ¬χ∧�InfDer χ∧InfDer ¬χ�∧InfIm χ∧InfIm ¬χ(2.4.d) Table 3: Abductive problems with subjective/objective implicit information. 4.2 Abductive solutions Recall that different abductive problems in Table 1 can have the same solution. For example, though abductive problem (1.2), the non-implicit novelty case, can be solved by means of reasoning steps (see Table 2), we mentioned that it can also be solved like case (1.1). But the further refinement that we have just done really makes them different. In case (1.2.b),χis subjective implicit information, so the agent can derive it and solve the problem by only reasoning. Nevertheless, this is not possible in (1.2.a) since χis objective but not subjective implicit information. The agent cannot derive χ; she needs a formula that, when added to her explicit information, makes χ explicit (like in the truly novel case); or, more interesting, she can extend her reasoning abilities with a formula/rule that allows her to derive χ. 9 59