Editing Abductive reasoning (section)

==Formalizations of abduction==

===Logic-based abduction===
In [[logic]], [[explanation]] is accomplished through the use of a [[logical theory]] <math>T</math> representing a [[domain of discourse|domain]] and a set of observations <math>O</math>. Abduction is the process of deriving a set of explanations of <math>O</math> according to <math>T</math> and picking out one of those explanations. For <math>E</math> to be an explanation of <math>O</math> according to <math>T</math>, it should satisfy two conditions:

* <math>O</math> follows from <math>E</math> and <math>T</math>;
* <math>E</math> is [[Consistent|consistent]] with <math>T</math>.

In formal logic, <math>O</math> and <math>E</math> are assumed to be sets of [[Literal (mathematical logic)|literal]]s. The two conditions for <math>E</math> being an explanation of <math>O</math> according to theory <math>T</math> are formalized as:

:<math>T \cup E \models O;</math>
:<math>T \cup E</math> is consistent.

Among the possible explanations <math>E</math> satisfying these two conditions, some other condition of minimality is usually imposed to avoid irrelevant facts (not contributing to the entailment of <math>O</math>) being included in the explanations. Abduction is then the process that picks out some member of <math>E</math>. Criteria for picking out a member representing "the best" explanation include the [[simplicity]], the [[prior probability]], or the explanatory power of the explanation.

A [[Proof theory|proof-theoretical]] abduction method for [[first-order logic|first-order]] classical logic based on the [[sequent calculus]] and a dual one, based on semantic tableaux ([[analytic tableaux]]) have been proposed.<ref>Cialdea Mayer, Marta and Pirri, Fiora (1993) "First order abduction via tableau and sequent calculi" Logic Jnl IGPL 1993 1: 99–117; {{doi|10.1093/jigpal/1.1.99}}. Oxford Journals</ref> The methods are sound and complete and work for full first-order logic, without requiring any preliminary reduction of formulae into normal forms. These methods have also been extended to [[modal logic]].<ref>Cialdea Mayer, Marta and Pirri, Fiora (1993) "Propositional abduction in modal logic" Logic Jnl IGPL 1995 3(6) 907–919; {{doi|10.1093/jigpal/3.6.907}}. Oxford Journals</ref>

[[Abductive logic programming]] is a computational framework that extends normal [[logic programming]] with abduction. It separates the theory <math>T</math> into two components, one of which is a normal logic program, used to generate <math>E</math> by means of [[backward reasoning]], the other of which is a set of integrity constraints, used to filter the set of candidate explanations.

===Set-cover abduction===
A different formalization of abduction is based on inverting the function that calculates the visible effects of the hypotheses. Formally, we are given a set of hypotheses <math>H</math> and a set of manifestations <math>M</math>; they are related by the domain knowledge, represented by a function <math>e</math> that takes as an argument a set of hypotheses and gives as a result the corresponding set of manifestations. In other words, for every subset of the hypotheses <math>H' \subseteq H</math>, their effects are known to be <math>e(H')</math>.

Abduction is performed by finding a set <math>H' \subseteq H</math> such that <math>M \subseteq e(H')</math>. In other words, abduction is performed by finding a set of hypotheses <math>H'</math> such that their effects <math>e(H')</math> include all observations <math>M</math>.

A common assumption is that the effects of the hypotheses are independent, that is, for every <math>H' \subseteq H</math>, it holds that <math>e(H') = \bigcup_{h \in H'} e(\{h\})</math>. If this condition is met, abduction can be seen as a form of [[set covering]].

===Abductive validation===
Abductive validation is the process of validating a given hypothesis through abductive reasoning. This can also be called reasoning through successive approximation.{{Citation needed|date=July 2020}} Under this principle, an explanation is valid if it is the best possible explanation of a set of known data. The best possible explanation is often defined in terms of simplicity and elegance (see [[Occam's razor]]). Abductive validation is common practice in hypothesis formation in [[science]]; moreover, Peirce claims that it is a ubiquitous aspect of thought:

{{blockquote|
Looking out my window this lovely spring morning, I see an azalea in full bloom. No, no! I don't see that; though that is the only way I can describe what I see. That is a proposition, a sentence, a fact; but what I perceive is not proposition, sentence, fact, but only an image, which I make intelligible in part by means of a statement of fact. This statement is abstract; but what I see is concrete. I perform an abduction when I so much as express in a sentence anything I see. The truth is that the whole fabric of our knowledge is one matted felt of pure hypothesis confirmed and refined by induction. Not the smallest advance can be made in knowledge beyond the stage of vacant staring, without making an abduction at every step.<ref>Peirce MS. 692, quoted in Sebeok, T. (1981) "[http://www.visual-memory.co.uk/b_resources/abduction.html You Know My Method]" in Sebeok, T., ''The Play of Musement'', Bloomington, IA: Indiana, page 24.</ref>
}}

It was Peirce's own maxim that "Facts cannot be explained by a hypothesis more extraordinary than these facts themselves; and of various hypotheses the least extraordinary must be adopted."<ref>Peirce MS. 696, quoted in Sebeok, T. (1981) "[http://www.visual-memory.co.uk/b_resources/abduction.html You Know My Method]" in Sebeok, T., ''The Play of Musement'', Bloomington, IA: Indiana, page 31.</ref> After obtaining possible hypotheses that may explain the facts, abductive validation is a method for identifying the most likely hypothesis that should be adopted.

===Subjective logic abduction===
[[Subjective logic]] generalises [[probabilistic logic]] by including degrees of epistemic [[Uncertainty quantification|uncertainty]] in the input arguments, i.e. instead of probabilities, the analyst can express arguments as [[Subjective logic|subjective opinions]]. Abduction in subjective logic is thus a generalization of probabilistic abduction described above.<ref name="Josang2016-SL" /> The input arguments in subjective logic are subjective opinions which can be binomial when the opinion applies to a binary variable or multinomial when it applies to an ''n''-ary variable. A subjective opinion thus applies to a state variable <math>X</math> which takes its values from a domain <math>\mathbf{X}</math> (i.e. a state space of exhaustive and mutually disjoint state values <math>x</math>), and is denoted by the tuple <math>\omega_{X}=(b_{X}, u_{X}, a_{X})\,\!</math>, where <math>b_{X}\,\!</math> is the belief mass distribution over <math>\mathbf{X}</math>, <math>u_{X}\,\!</math> is the epistemic uncertainty mass, and <math>a_{X}\,\!</math> is the [[base rate]] distribution over <math>\mathbf{X}</math>. These parameters satisfy <math>u_{X}+\sum b_{X}(x) = 1\,\!</math> and <math>\sum a_{X}(x) = 1\,\!</math> as well as <math>b_{X}(x),u_{X},a_{X}(x) \in [0,1]\,\!</math>.

Assume the domains <math>\mathbf{X}</math> and <math>\mathbf{Y}</math> with respective variables <math>X</math> and <math>Y</math>, the set of conditional opinions <math>\omega_{X\mid Y}</math> (i.e. one conditional opinion for each value <math>y</math>), and the base rate distribution <math>a_{Y}</math>. Based on these parameters, the subjective [[Bayes' theorem]] denoted with the operator <math>\;\widetilde{\phi}</math> produces the set of inverted conditionals <math>\omega_{Y\tilde{\mid} X}</math> (i.e. one inverted conditional for each value <math>x</math>) expressed by:

:<math>\omega_{Y\tilde{|}X}=\omega_{X|Y}\;\widetilde{\phi\,}\;a_{Y}</math>.

Using these inverted conditionals together with the opinion <math>\omega_{X}</math> subjective [[Deductive reasoning|deduction]] denoted by the operator <math>\circledcirc</math> can be used to abduce the marginal opinion <math>\omega_{Y\,\overline{\|}\,X}</math>. The equality between the different expressions for subjective abduction is given below:

:<math>\begin{align}
\omega_{Y\,\widetilde{\|}\,X} 
&=  \omega_{X\mid Y} \;\widetilde{\circledcirc}\; \omega_{X}\\
&= (\omega_{X\mid Y} \;\widetilde{\phi\,}\; a_{Y}) \;\circledcirc\;\omega_{X}\\
&= \omega_{Y\widetilde{|}X} \;\circledcirc\;\omega_{X}\;.
\end{align}</math>

The symbolic notation for subjective abduction is "<math>\widetilde{\|}</math>", and the operator itself is denoted as "<math>\widetilde{\circledcirc}</math>". The operator for the subjective Bayes' theorem is denoted "<math>\widetilde{\phi\,}</math>", and subjective deduction is denoted "<math>\circledcirc</math>".<ref name="Josang2016-SL">A. Jøsang. ''Subjective Logic: A Formalism for Reasoning Under Uncertainty'', Springer 2016, {{ISBN|978-3-319-42337-1}}</ref>

The advantage of using subjective logic abduction compared to probabilistic abduction is that both aleatoric and epistemic uncertainty about the input argument probabilities can be explicitly expressed and taken into account during the analysis. It is thus possible to perform abductive analysis in the presence of uncertain arguments, which naturally results in degrees of uncertainty in the output conclusions.