5 Propositions and Inference

The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).

5.7 Abduction

Abduction is a form of reasoning where assumptions are made to explain observations. For example, if an agent were to observe that some light was not working, it hypothesizes what is happening in the world to explain why the light was not working. An intelligent tutoring system could try to explain why a student gives some answer in terms of what the student understands and does not understand.

The term abduction was coined by Peirce (1839–1914) to differentiate this type of reasoning from deduction, which involves determining what logically follows from a set of axioms, and induction, which involves inferring general relationships from examples.

In abduction, an agent hypothesizes what may be true about an observed case. An agent determines what implies its observations – what could be true to make the observations true. Observations are trivially implied by contradictions (as a contradiction logically implies everything), so we want to exclude contradictions from our explanation of the observations.

To formalize abduction, we use the language of Horn clauses and assumables. The system is given

  • •

    a knowledge base, KB, which is a set of of Horn clauses, and

  • •

    a set A of atoms, called the assumables, which are the building blocks of hypotheses.

Instead of adding observations to the knowledge base, observations must be explained.

A scenario of ⟨KB,A⟩ is a subset H of A such that KB∪H is satisfiable. KB∪H is satisfiable if a model exists in which every element of KB and every element H is true. This happens if no subset of H is a conflict of KB.

An explanation of proposition g from ⟨KB,A⟩ is a scenario that, together with KB, implies g.

That is, an explanation of proposition g is a set H, H⊆A such that

KB∪H⊧g
KB∪H⊧̸false.

A minimal explanation of g from ⟨KB,A⟩ is an explanation H of g from ⟨KB,A⟩ such that no strict subset of H is also an explanation of g from ⟨KB,A⟩.

Example 5.33.

Consider the following simplistic knowledge base and assumables for a diagnostic assistant:

𝑏𝑟𝑜𝑛𝑐ℎ𝑖𝑡𝑖𝑠←𝑖𝑛𝑓𝑙𝑢𝑒𝑛𝑧𝑎.
𝑏𝑟𝑜𝑛𝑐ℎ𝑖𝑡𝑖𝑠←𝑠𝑚𝑜𝑘𝑒𝑠.
𝑐𝑜𝑢𝑔ℎ𝑖𝑛𝑔←𝑏𝑟𝑜𝑛𝑐ℎ𝑖𝑡𝑖𝑠.
𝑤ℎ𝑒𝑒𝑧𝑖𝑛𝑔←𝑏𝑟𝑜𝑛𝑐ℎ𝑖𝑡𝑖𝑠.
𝑓𝑒𝑣𝑒𝑟←𝑖𝑛𝑓𝑙𝑢𝑒𝑛𝑧𝑎.
𝑓𝑒𝑣𝑒𝑟←𝑖𝑛𝑓𝑒𝑐𝑡𝑖𝑜𝑛.
sore_throat←𝑖𝑛𝑓𝑙𝑢𝑒𝑛𝑧𝑎.
𝑓𝑎𝑙𝑠𝑒←𝑠𝑚𝑜𝑘𝑒𝑠∧𝑛𝑜𝑛𝑠𝑚𝑜𝑘𝑒𝑟.
𝘢𝘴𝘴𝘶𝘮𝘢𝘣𝘭𝘦⁢𝑠𝑚𝑜𝑘𝑒𝑠,𝑛𝑜𝑛𝑠𝑚𝑜𝑘𝑒𝑟,𝑖𝑛𝑓𝑙𝑢𝑒𝑛𝑧𝑎,𝑖𝑛𝑓𝑒𝑐𝑡𝑖𝑜𝑛.

If the agent observes wheezing, there are two minimal explanations:

{𝑖𝑛𝑓𝑙𝑢𝑒𝑛𝑧𝑎}⁢ and ⁢{𝑠𝑚𝑜𝑘𝑒𝑠}

These explanations imply bronchitis and coughing.

If 𝑤ℎ𝑒𝑒𝑧𝑖𝑛𝑔∧𝑓𝑒𝑣𝑒𝑟 is observed, the minimal explanations are

{𝑖𝑛𝑓𝑙𝑢𝑒𝑛𝑧𝑎}⁢ and ⁢{𝑠𝑚𝑜𝑘𝑒𝑠,𝑖𝑛𝑓𝑒𝑐𝑡𝑖𝑜𝑛}.

If 𝑤ℎ𝑒𝑒𝑧𝑖𝑛𝑔∧𝑛𝑜𝑛𝑠𝑚𝑜𝑘𝑒𝑟 was observed, there is one minimal explanation:

{𝑖𝑛𝑓𝑙𝑢𝑒𝑛𝑧𝑎,𝑛𝑜𝑛𝑠𝑚𝑜𝑘𝑒𝑟}.

The other explanation of wheezing is inconsistent with being a non-smoker.

Example 5.34.

Consider the knowledge base:

𝑎𝑙𝑎𝑟𝑚←𝑡𝑎𝑚𝑝𝑒𝑟𝑖𝑛𝑔.
𝑎𝑙𝑎𝑟𝑚←𝑓𝑖𝑟𝑒.
𝑠𝑚𝑜𝑘𝑒←𝑓𝑖𝑟𝑒.

If alarm is observed, there are two minimal explanations:

{𝑡𝑎𝑚𝑝𝑒𝑟𝑖𝑛𝑔}⁢ and ⁢{𝑓𝑖𝑟𝑒}.

If 𝑎𝑙𝑎𝑟𝑚∧𝑠𝑚𝑜𝑘𝑒 is observed, there is one minimal explanation:

{𝑓𝑖𝑟𝑒}.

Notice how, when smoke is observed, there is no need to hypothesize tampering to explain alarm; it has been explained away by fire.

Determining what is going on inside a system based on observations about the behavior is the problem of diagnosis or recognition. In abductive diagnosis, the agent hypothesizes diseases or malfunctions, as well as that some parts are working normally, to explain the observed symptoms.

This differs from consistency-based diagnosis (CBD) in the following ways:

  • •

    In CBD, only normal behavior needs to be represented, and the hypotheses are assumptions of normal behavior. In abductive diagnosis, faulty behavior as well as normal behavior needs to be represented, and the assumables need to be for normal behavior and for each fault (or different behavior).

  • •

    In abductive diagnosis, observations need to be explained. In CBD observations are added to the knowledge base, and f⁢a⁢l⁢s⁢e is proved.

Abductive diagnosis requires more detailed modeling and gives more detailed diagnoses, because the knowledge base has to be able to actually prove the observations from the knowledge base and the assumptions. Abductive diagnosis is also used to diagnose systems in which there is no normal behavior. For example, in an intelligent tutoring system, by observing what a student does, the tutoring system can hypothesize what the student understands and does not understand, which can guide the actions of the tutoring system.

Abduction can also be used for design, in which the query to be explained is a design goal and the assumables are the building blocks of the designs. The explanation is the design. Consistency means that the design is possible. The implication of the design goal means that the design provably achieved the design goal.

Example 5.35.

Consider the electrical domain of Figure 5.2. Similar to the representation of the example for consistency-based diagnosis in Example 5.23, we axiomatize what follows from the assumptions of what may be happening in the system. In abductive diagnosis, we must axiomatize what follows both from faults and from normality assumptions. For each atom that could be observed, we axiomatize how it could be produced.

A user could observe that l1 is lit or is dark. We must write rules that axiomatize how the system must be to make these true. Light l1 is lit if it is ok and there is power coming in. The light is dark if it is broken or there is no power. The system can assume l1 is ok or broken, but not both:

lit_l1←live_w0∧ok_l1.
dark_l1←broken_l1.
dark_l1←dead_w0.
𝖺𝗌𝗌𝗎𝗆𝖺𝖻𝗅𝖾 ok_l1.
𝖺𝗌𝗌𝗎𝗆𝖺𝖻𝗅𝖾 broken_l1.
𝑓𝑎𝑙𝑠𝑒←ok_l1∧broken_l1.

Wire w0 is live or dead depending on the switch positions and whether the wires coming in are alive or dead:

live_w0←live_w1∧up_s2∧ok_s2.
live_w0←live_w2∧down_s2∧ok_s2.
dead_w0←broken_s2.
dead_w0←up_s2∧dead_w1.
dead_w0←down_s2∧dead_w2.
𝖺𝗌𝗌𝗎𝗆𝖺𝖻𝗅𝖾 ok_s2.
𝖺𝗌𝗌𝗎𝗆𝖺𝖻𝗅𝖾 broken_s2.
𝑓𝑎𝑙𝑠𝑒←ok_s2∧broken_s2.

The other wires are axiomatized similarly. Some of the wires depend on whether the circuit breakers are ok or broken:

live_w3←live_w5∧ok_cb1.
dead_w3←broken_cb1.
dead_w3←dead_w5.
𝖺𝗌𝗌𝗎𝗆𝖺𝖻𝗅𝖾 ok_cb1.
𝖺𝗌𝗌𝗎𝗆𝖺𝖻𝗅𝖾 broken_cb1.
𝑓𝑎𝑙𝑠𝑒←ok_cb1∧broken_cb1.

For the rest of this example, we assume that the other light and wires are represented analogously.

The outside power can be live or the power can be down:

live_w5←live_outside.
dead_w5←outside_power_down.
𝖺𝗌𝗌𝗎𝗆𝖺𝖻𝗅𝖾 live_outside.
𝖺𝗌𝗌𝗎𝗆𝖺𝖻𝗅𝖾 outside_power_down.
𝑓𝑎𝑙𝑠𝑒←live_outside∧outside_power_down.

The switches can be assumed to be up or down:

𝖺𝗌𝗌𝗎𝗆𝖺𝖻𝗅𝖾 up_s1.
𝖺𝗌𝗌𝗎𝗆𝖺𝖻𝗅𝖾 down_s1.
𝑓𝑎𝑙𝑠𝑒←up_s1∧down_s1.

There are two minimal explanations of lit_l1:

{live_outside,ok_cb1,ok_l1,ok_s1,ok_s2,up_s1,up_s2}
{live_outside,ok_cb1,ok_l1,ok_s1,ok_s2,down_s1,down_s2}.

This could be seen in design terms as a way to make sure the light is on: put both switches up or both switches down, and ensure the switches all work. It could also be seen as a way to determine what is going on if the agent observed that l1 is lit; one of these two scenarios must hold.

There are ten minimal explanations of dark_l1:

{broken_l1}
{broken_s2}
{down_s1,up_s2}
{broken_s1,up_s2}
{broken_cb1,up_s1,up_s2}
{outside_power_down,up_s1,up_s2}
{down_s2,up_s1}
{broken_s1,down_s2}
{broken_cb1,down_s1,down_s2}
{down_s1,down_s2,outside_power_down}

There are six minimal explanations of dark_l1∧lit_l2:

{broken_l1,live_outside,ok_cb1,ok_l2,ok_s3,up_s3}
{broken_s2,live_outside,ok_cb1,ok_l2,ok_s3,up_s3}
{down_s1,live_outside,ok_cb1,ok_l2,ok_s3,up_s2,up_s3}
{broken_s1,live_outside,ok_cb1,ok_l2,ok_s3,up_s2,up_s3}
{down_s2,live_outside,ok_cb1,ok_l2,ok_s3,up_s1,up_s3}
{broken_s1,down_s2,live_outside,ok_cb1,ok_l2,ok_s3,up_s3}

Notice how the explanations cannot include outside_power_down or broken_cb1 because they are inconsistent with the explanation of l2 being lit.

Both the bottom-up and top-down implementations for assumption-based reasoning with Horn clauses can be used for abduction. The bottom-up algorithm of Figure 5.9 computes the minimal explanations for each atom; at the end of the repeat loop, C contains the minimal explanations of each atom (as well as potentially some non-minimal explanations). The refinement of pruning dominated explanations can also be used. The top-down algorithm can be used to find the explanations of any g by first generating the conflicts and, using the same code and knowledge base, proving g instead of f⁢a⁢l⁢s⁢e. The minimal explanations of g are the minimal sets of assumables collected to prove g such that no subset is a conflict.