News for hackers. Stuff that matters.
Re:The Art of Abduction by YeGoblynQueenne on Thursday July 21, 2022 @07:58AM (#32178297)
Sometimes I understand abduction, other times, not. I'm a bit of a fan of logic programming so I try to describe the three inference modes using definite clauses.

Deduction: we go from facts (positive literals) and rules (definite clauses) to facts:

  swan(alice).   white(X) ← swan(X).
  ----------------------------------
            white(alice)
(If we know that Alice is a swan, and all swans are white, we can infer that alice is white).

Induction: we go from facts and rules to new rules:

  has_feathers(X) ← bird(X).  bird(X) ← swan(X).
  ----------------------------------------------
             has_feathers(X) ← swan(X).
(If we know that all birds have feathers and all swans are birds, we can infer that all swans have feathers).

Abduction: we go from facts and rules to _goals_ (negative literals):

  white(alice).   white(X) ← swan(X).
  -----------------------------------
            swan(alice)
(If we know that Alice is white and all swans are white, we can infer that Alice is a swan).

The last inference is of course not sound, as such - Alice could be white because she's a yogurt, say. But, if we operate under the assumption that only what we can prove is true (the so-called "closed world assumption") and the only rule we have about the concept of "white" is that "all swans are white", then the reasoning step becomes sound: the only way that we know for Alice to be white is for her to be a swan.

What if we know multiple ways for an "X" to be white? For example, what if we have the rule "white(X) ← yogurt(X)"? Well then, we can make this inference also:

  white(alice).   white(X) ← yogurt(X).
  -------------------------------------
            yogurt(alice)
And now we have two contradictory hypotheses about Alice: either she's a swan, or she's a yogurt^. We can resolve the contradiction when we learn more about yogurts and swans, and Alice. For example, if we have the information that Alice has feathers, we can figure out that Alice is a swan.

The closed world assumption is the simplest way to handle uncertainty (or in any case there are no simpler methods). It is also non-monotonic, in that new facts and rules can change the truth value of facts inferred from a theory. Which is great because that way we 're not stuck with the conclusions of initial premises.

Anyway, that's my logic-programmer's model for abduction. And it may be horribly wrong at places (my model for logic programming was horribly wrong the first ten years so...).

_______________

^Correction: Actually... alice can be a swan _and_ a yogurt. swan(alice) and yogurt(alice) are not contradictory unless we have some proof that they are.

Re:The Art of Abduction by dreamcompiler on Thursday July 21, 2022 @10:06AM (#32179562)
Thanks. This is the closest I've come to understanding abductive reasoning and it's because you've explained it in a way my Prolog brain can understand it. Even though I've never written a Prolog program that abduces goals on its own, now I kind of want to try.
Re:The Art of Abduction by YeGoblynQueenne on Thursday July 21, 2022 @10:20AM (#32179744)
Thanks! Note that the first two inferences I show above are valid resolution steps since they have literals that are complements under unification, like swan(alice) and swam(X)← (the latter being a negative literal, since it's in the body). But the third and fourth inferences can't be made with resolution.

There is a whole bunch of work on abductive reasoning in a first-order framework, but I'm far from an expert on it. Antonis Kakas is a prominent name in the subject. For example, see:

Abductive Logic Programming, A.C. Kakas, R. A. Kowalski, F. Toni

https://academic.oup.com/logcom/article-abstract/2/6/719/942...

Although behind a paywall. And yes, that's that Kowalski. Here's an unpaywalled overview:

Abduction in Logic Programming, Marc Denecker and Antonis Kakas

https://web.stanford.edu/class/cs227/Readings/Abudction%20in...

And here's one on the application to learning:

Abductive concept learning, Antonis C. Kakas & Fabrizio Riguzzi

https://link.springer.com/article/10.1007/BF03037531

Re:The Art of Abduction by routerl on Saturday July 30, 2022 @03:18PM (#32289484)
Yes, this is fantastic and accurate. It captures exactly the uncertainty that underpins this type of reasoning.

Abductive reasoning is usually an evidence-gathering process, so that we can narrow down the set of inferences that still produce meaningful conclusions.

Thus "once you've eliminated the impossible, whatever remains, however improbable, must be the truth."