Subjective logic

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Subjective_logic 

Subjective logic is a type of probabilistic logic that explicitly takes epistemic uncertainty and source trust into account. In general, subjective logic is suitable for modeling and analysing situations involving uncertainty and relatively unreliable sources. For example, it can be used for modeling and analysing trust networks and Bayesian networks.

Arguments in subjective logic are subjective opinions about state variables which can take values from a domain (aka state space), where a state value can be thought of as a proposition which can be true or false. A binomial opinion applies to a binary state variable, and can be represented as a Beta PDF (Probability Density Function). A multinomial opinion applies to a state variable of multiple possible values, and can be represented as a Dirichlet PDF (Probability Density Function). Through the correspondence between opinions and Beta/Dirichlet distributions, subjective logic provides an algebra for these functions. Opinions are also related to the belief representation in Dempster–Shafer belief theory.

A fundamental aspect of the human condition is that nobody can ever determine with absolute certainty whether a proposition about the world is true or false. In addition, whenever the truth of a proposition is expressed, it is always done by an individual, and it can never be considered to represent a general and objective belief. These philosophical ideas are directly reflected in the mathematical formalism of subjective logic.

Subjective opinions

Subjective opinions express subjective beliefs about the truth of state values/propositions with degrees of epistemic uncertainty, and can explicitly indicate the source of belief whenever required. An opinion is usually denoted as ${\displaystyle {\omega }_X^A}$ where ${\displaystyle A}$ is the source of the opinion, and ${\displaystyle X}$ is the state variable to which the opinion applies. The variable ${\displaystyle X}$ can take values from a domain (also called state space) e.g. denoted as ${\displaystyle \mathbb{X}}$. The values of a domain are assumed to be exhaustive and mutually disjoint, and sources are assumed to have a common semantic interpretation of a domain. The source and variable are attributes of an opinion. Indication of the source can be omitted whenever irrelevant.

Binomial opinions

Let ${\displaystyle x}$ be a state value in a binary domain. A binomial opinion about the truth of state value ${\displaystyle x}$ is the ordered quadruple ${\displaystyle {\omega }_x=(b_x,d_x,u_x,a_x)}$ where:

${\displaystyle b_x}$: belief mass	is the belief that ${\displaystyle x}$ is true.
${\displaystyle d_x}$: disbelief mass	is the belief that ${\displaystyle x}$ is false.
${\displaystyle u_x}$: uncertainty mass	is the amount of uncommitted belief, also interpreted as epistemic uncertainty.
${\displaystyle a_x}$: base rate	is the prior probability in the absence of belief or disbelief.

These components satisfy ${\displaystyle b_x+d_x+u_x=1}$ and ${\displaystyle b_x,d_x,u_x,a_x\in [0,1]}$. The characteristics of various opinion classes are listed below.

An opinion	where ${\displaystyle b_x=1}$	is an absolute opinion which is equivalent to Boolean TRUE,
	where ${\displaystyle d_x=1}$	is an absolute opinion which is equivalent to Boolean FALSE,
	where ${\displaystyle b_x+d_x=1}$	is a dogmatic opinion which is equivalent to a traditional probability,
	where ${\displaystyle b_x+d_x<1}$	is an uncertain opinion which expresses degrees of epistemic uncertainty, and
	where ${\displaystyle b_x+d_x=0}$	is a vacuous opinion which expresses total epistemic uncertainty or total vacuity of belief.

The projected probability of a binomial opinion is defined as ${\displaystyle {\mathrm{P}}_x=b_x+a_x{u}_x}$.

Binomial opinions can be represented on an equilateral triangle as shown below. A point inside the triangle represents a ${\displaystyle (b_x,d_x,u_x)}$ triple. The b,d,u-axes run from one edge to the opposite vertex indicated by the Belief, Disbelief or Uncertainty label. For example, a strong positive opinion is represented by a point towards the bottom right Belief vertex. The base rate, also called the prior probability, is shown as a red pointer along the base line, and the projected probability, ${\displaystyle {\mathrm{P}}_x}$, is formed by projecting the opinion onto the base, parallel to the base rate projector line. Opinions about three values/propositions X, Y and Z are visualized on the triangle to the left, and their equivalent Beta PDFs (Probability Density Functions) are visualized on the plots to the right. The numerical values and verbal qualitative descriptions of each opinion are also shown. 

The Beta PDF is normally denoted as ${\displaystyle \mathrm{B}\mathrm{e}\mathrm{t}\mathrm{a}(p(x);\alpha ,\beta )}$ where ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ are its two strength parameters. The Beta PDF of a binomial opinion ${\displaystyle {\omega }_x=(b_x,d_x,u_x,a_x)}$ is the function ${\displaystyle \mathrm{B}\mathrm{e}\mathrm{t}\mathrm{a}(p(x);\alpha ,\beta )\text{ where }\{\begin{array}{ll}\alpha & =\frac{W{b}_x}{u_x}+W{a}_x\\ \beta & =\frac{W{d}_x}{u_x}+W(1-a_x)\end{array}}$ where ${\displaystyle W}$ is the non-informative prior weight, also called a unit of evidence, normally set to ${\displaystyle W=2}$.

Multinomial opinions

Let ${\displaystyle X}$ be a state variable which can take state values ${\displaystyle x\in \mathbb{X}}$. A multinomial opinion over ${\displaystyle X}$ is the composite tuple ${\displaystyle {\omega }_X=(b_X,u_X,a_X)}$, where ${\displaystyle b_X}$ is a belief mass distribution over the possible state values of ${\displaystyle X}$, ${\displaystyle u_X}$ is the uncertainty mass, and ${\displaystyle a_X}$ is the prior (base rate) probability distribution over the possible state values of ${\displaystyle X}$. These parameters satisfy ${\displaystyle u_X+\sum b_X(x)=1}$ and ${\displaystyle \sum a_X(x)=1}$ as well as ${\displaystyle b_X(x),u_X,a_X(x)\in [0,1]}$.

Trinomial opinions can be simply visualised as points inside a tetrahedron, but opinions with dimensions larger than trinomial do not lend themselves to simple visualisation.

Dirichlet PDFs are normally denoted as ${\displaystyle \mathrm{D}\mathrm{i}\mathrm{r}(p_X;{\alpha }_X)}$ where ${\displaystyle p_X}$ is a probability distribution over the state values of ${\displaystyle X}$, and ${\displaystyle {\alpha }_X}$ are the strength parameters. The Dirichlet PDF of a multinomial opinion ${\displaystyle {\omega }_X=(b_X,u_X,a_X)}$ is the function ${\displaystyle \mathrm{D}\mathrm{i}\mathrm{r}(p_X;{\alpha }_X)}$ where the strength parameters are given by ${\displaystyle {\alpha }_X(x)=\frac{W{b}_X(x)}{u_X}+W{a}_X(x)}$, where ${\displaystyle W}$ is the non-informative prior weight, also called a unit of evidence, normally set to the number of classes.

Operators

Most operators in the table below are generalisations of binary logic and probability operators. For example addition is simply a generalisation of addition of probabilities. Some operators are only meaningful for combining binomial opinions, and some also apply to multinomial opinion. Most operators are binary, but complement is unary, and abduction is ternary. See the referenced publications for mathematical details of each operator.

Subjective logic operators, notations, and corresponding propositional/binary logic operators

Subjective logic operator	Operator notation	Propositional/binary logic operator
Addition	${\displaystyle {\omega }_{x\cup y}^A={\omega }_x^A+{\omega }_y^A}$	Union
Subtraction	${\displaystyle {\omega }_{x\mathrm{\setminus }y}^A={\omega }_x^A-{\omega }_y^A}$	Difference
Multiplication	${\displaystyle {\omega }_{x\wedge y}^A={\omega }_x^A\cdot {\omega }_y^A}$	Conjunction / AND
Division	${\displaystyle {\omega }_{x\overline{\wedge }y}^A={\omega }_x^A/{\omega }_y^A}$	Unconjunction / UN-AND
Comultiplication	${\displaystyle {\omega }_{x\vee y}^A={\omega }_x^A\bigsqcup {\omega }_y^A}$	Disjunction / OR
Codivision	${\displaystyle {\omega }_{x\overline{\vee }y}^A={\omega }_x^A\overline{\bigsqcup }{\omega }_y^A}$	Undisjunction / UN-OR
Complement	${\displaystyle {\omega }_{\overline{x}}^A=\mathrm{\neg }{\omega }_x^A}$	NOT
Deduction	${\displaystyle {\omega }_{Y\Vert X}^A={\omega }_{Y|X}^A⊚{\omega }_X^A}$	Modus ponens
Subjective Bayes' theorem	${\displaystyle {\omega }_{X\widetilde{|}Y}^A={\omega }_{Y|X}^A\tilde{\varphi }{a}_X}$	Contraposition
Abduction	${\displaystyle {\omega }_{X\tilde{\Vert }Y}^A={\omega }_{Y|X}^A\widetilde{⊚}(a_X,{\omega }_Y^A)}$	Modus tollens
Transitivity / discounting	${\displaystyle {\omega }_X^{A;B}={\omega }_B^A\otimes {\omega }_X^B}$	n.a.
Cumulative fusion	${\displaystyle {\omega }_X^{A\diamond B}={\omega }_X^A\oplus {\omega }_X^B}$	n.a.
Constraint fusion	${\displaystyle {\omega }_X^{A\mathrm{\&}B}={\omega }_X^A\odot {\omega }_X^B}$	n.a.

Transitive source combination can be denoted in a compact or expanded form. For example, the transitive trust path from analyst/source ${\displaystyle A}$ via source ${\displaystyle B}$ to the variable ${\displaystyle X}$ can be denoted as ${\displaystyle [A;B,X]}$ in compact form, or as ${\displaystyle [A;B]:[B,X]}$ in expanded form. Here, ${\displaystyle [A;B]}$ expresses that ${\displaystyle A}$ has some trust/distrust in source ${\displaystyle B}$, whereas ${\displaystyle [B,X]}$ expresses that ${\displaystyle B}$ has an opinion about the state of variable ${\displaystyle X}$ which is given as an advice to ${\displaystyle A}$. The expanded form is the most general, and corresponds directly to the way subjective logic expressions are formed with operators.

Properties

In case the argument opinions are equivalent to Boolean TRUE or FALSE, the result of any subjective logic operator is always equal to that of the corresponding propositional/binary logic operator. Similarly, when the argument opinions are equivalent to traditional probabilities, the result of any subjective logic operator is always equal to that of the corresponding probability operator (when it exists).

In case the argument opinions contain degrees of uncertainty, the operators involving multiplication and division (including deduction, abduction and Bayes' theorem) will produce derived opinions that always have correct projected probability but possibly with approximate variance when seen as Beta/Dirichlet PDFs. All other operators produce opinions where the projected probabilities and the variance are always analytically correct.

Different logic formulas that traditionally are equivalent in propositional logic do not necessarily have equal opinions. For example ${\displaystyle {\omega }_{x\wedge (y\vee z)}\ne {\omega }_{(x\wedge y)\vee (x\wedge z)}}$ in general although the distributivity of conjunction over disjunction, expressed as ${\displaystyle x\wedge (y\vee z)\iff (x\wedge y)\vee (x\wedge z)}$, holds in binary propositional logic. This is no surprise as the corresponding probability operators are also non-distributive. However, multiplication is distributive over addition, as expressed by ${\displaystyle {\omega }_{x\wedge (y\cup z)}={\omega }_{(x\wedge y)\cup (x\wedge z)}}$. De Morgan's laws are also satisfied as e.g. expressed by ${\displaystyle {\omega }_{\overline{x\wedge y}}={\omega }_{\overline{x}\vee \overline{y}}}$.

Subjective logic allows very efficient computation of mathematically complex models. This is possible by approximation of the analytically correct functions. While it is relatively simple to analytically multiply two Beta PDFs in the form of a joint Beta PDF, anything more complex than that quickly becomes intractable. When combining two Beta PDFs with some operator/connective, the analytical result is not always a Beta PDF and can involve hypergeometric series. In such cases, subjective logic always approximates the result as an opinion that is equivalent to a Beta PDF.

Applications

Subjective logic is applicable when the situation to be analysed is characterised by considerable epistemic uncertainty due to incomplete knowledge. In this way, subjective logic becomes a probabilistic logic for epistemic-uncertain probabilities. The advantage is that uncertainty is preserved throughout the analysis and is made explicit in the results so that it is possible to distinguish between certain and uncertain conclusions.

The modelling of trust networks and Bayesian networks are typical applications of subjective logic.

Subjective trust networks

Subjective trust networks can be modelled with a combination of the transitivity and fusion operators. Let ${\displaystyle [A;B]}$ express the referral trust edge from ${\displaystyle A}$ to ${\displaystyle B}$, and let ${\displaystyle [B,X]}$ express the belief edge from ${\displaystyle B}$ to ${\displaystyle X}$. A subjective trust network can for example be expressed as ${\displaystyle ([A;B]:[B,X])\diamond ([A;C]:[C,X])}$ as illustrated in the figure below.

The indices 1, 2 and 3 indicate the chronological order in which the trust edges and advice are formed. Thus, given the set of trust edges with index 1, the origin trustor ${\displaystyle A}$ receives advice from ${\displaystyle B}$ and ${\displaystyle C}$, and is thereby able to derive belief in variable ${\displaystyle X}$. By expressing each trust edge and belief edge as an opinion, it is possible for ${\displaystyle A}$ to derive belief in ${\displaystyle X}$ expressed as ${\displaystyle {\omega }_X^A={\omega }_X^{[A;B]\diamond [A;C]}=({\omega }_B^A\otimes {\omega }_X^B)\oplus ({\omega }_C^A\otimes {\omega }_X^C)}$.

Trust networks can express the reliability of information sources, and can be used to determine subjective opinions about variables that the sources provide information about.

Evidence-based subjective logic (EBSL) describes an alternative trust-network computation, where the transitivity of opinions (discounting) is handled by applying weights to the evidence underlying the opinions.

Subjective Bayesian networks

In the Bayesian network below, ${\displaystyle X}$ and ${\displaystyle Y}$ are parent variables and ${\displaystyle Z}$ is the child variable. The analyst must learn the set of joint conditional opinions ${\displaystyle {\omega }_{Z|XY}}$ in order to apply the deduction operator and derive the marginal opinion ${\displaystyle {\omega }_{Z\Vert XY}}$ on the variable ${\displaystyle Z}$. The conditional opinions express a conditional relationship between the parent variables and the child variable.

The deduced opinion is computed as ${\displaystyle {\omega }_{Z\Vert XY}={\omega }_{Z|XY}⊚{\omega }_{XY}}$. The joint evidence opinion ${\displaystyle {\omega }_{XY}}$ can be computed as the product of independent evidence opinions on ${\displaystyle X}$ and ${\displaystyle Y}$, or as the joint product of partially dependent evidence opinions.

Subjective networks

The combination of a subjective trust network and a subjective Bayesian network is a subjective network. The subjective trust network can be used to obtain from various sources the opinions to be used as input opinions to the subjective Bayesian network, as illustrated in the figure below.

Traditional Bayesian network typically do not take into account the reliability of the sources. In subjective networks, the trust in sources is explicitly taken into account.

If and only if

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/If_and_only_if

↔⇔≡⟺
Logical symbols representing iff  

In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is biconditional (a statement of material equivalence), and can be likened to the standard material conditional ("only if", equal to "if ... then") combined with its reverse ("if"); hence the name. The result is that the truth of either one of the connected statements requires the truth of the other (i.e. either both statements are true, or both are false), though it is controversial whether the connective thus defined is properly rendered by the English "if and only if"—with its pre-existing meaning. For example, P if and only if Q means that P is true whenever Q is true, and the only case in which P is true is if Q is also true, whereas in the case of P if Q, there could be other scenarios where P is true and Q is false.

In writing, phrases commonly used as alternatives to P "if and only if" Q include: Q is necessary and sufficient for P, for P it is necessary and sufficient that Q, P is equivalent (or materially equivalent) to Q (compare with material implication), P precisely if Q, P precisely (or exactly) when Q, P exactly in case Q, and P just in case Q. Some authors regard "iff" as unsuitable in formal writing; others consider it a "borderline case" and tolerate its use. In logical formulae, logical symbols, such as ${\displaystyle \leftrightarrow }$ and ${\displaystyle \iff }$, are used instead of these phrases; see § Notation below.

Definition

The truth table of P ${\displaystyle \iff }$ Q is as follows:

Truth table

P	Q	P ${\displaystyle \Rightarrow }$ Q	P ${\displaystyle \Leftarrow }$ Q	P ${\displaystyle \iff }$ Q
T	T	T	T	T
T	F	F	T	F
F	T	T	F	F
F	F	T	T	T

It is equivalent to that produced by the XNOR gate, and opposite to that produced by the XOR gate.

Usage

Notation

The corresponding logical symbols are "${\displaystyle \leftrightarrow }$", "${\displaystyle \iff }$", and ${\displaystyle \equiv }$, and sometimes "iff". These are usually treated as equivalent. However, some texts of mathematical logic (particularly those on first-order logic, rather than propositional logic) make a distinction between these, in which the first, ↔, is used as a symbol in logic formulas, while ⇔ is used in reasoning about those logic formulas (e.g., in metalogic). In Łukasiewicz's Polish notation, it is the prefix symbol ${\displaystyle E}$.

Another term for the logical connective, i.e., the symbol in logic formulas, is exclusive nor.

In TeX, "if and only if" is shown as a long double arrow: ${\displaystyle ⟺}$ via command \iff or \Longleftrightarrow.

Proofs

In most logical systems, one proves a statement of the form "P iff Q" by proving either "if P, then Q" and "if Q, then P", or "if P, then Q" and "if not-P, then not-Q". Proving these pairs of statements sometimes leads to a more natural proof, since there are not obvious conditions in which one would infer a biconditional directly. An alternative is to prove the disjunction "(P and Q) or (not-P and not-Q)", which itself can be inferred directly from either of its disjuncts—that is, because "iff" is truth-functional, "P iff Q" follows if P and Q have been shown to be both true, or both false.

Origin of iff and pronunciation

Usage of the abbreviation "iff" first appeared in print in John L. Kelley's 1955 book General Topology. Its invention is often credited to Paul Halmos, who wrote "I invented 'iff,' for 'if and only if'—but I could never believe I was really its first inventor."

It is somewhat unclear how "iff" was meant to be pronounced. In current practice, the single 'word' "iff" is almost always read as the four words "if and only if". However, in the preface of General Topology, Kelley suggests that it should be read differently: "In some cases where mathematical content requires 'if and only if' and euphony demands something less I use Halmos' 'iff'". The authors of one discrete mathematics textbook suggest: "Should you need to pronounce iff, really hang on to the 'ff' so that people hear the difference from 'if'", implying that "iff" could be pronounced as [ɪfː].

Usage in definitions

Technically, definitions are "if and only if" statements; some texts — such as Kelley's General Topology — follow the strict demands of logic, and use "if and only if" or iff in definitions of new terms. However, this logically correct usage of "if and only if" is relatively uncommon and overlooks the linguistic fact that the "if" of a definition is interpreted as meaning "if and only if". The majority of textbooks, research papers and articles (including English Wikipedia articles) follow the linguistic convention to interpret "if" as "if and only if" whenever a mathematical definition is involved (as in "a topological space is compact if every open cover has a finite subcover").

Distinction from "if" and "only if"

• "Madison will eat the fruit if it is an apple." (equivalent to "Only if Madison will eat the fruit, can it be an apple" or "Madison will eat the fruit ← the fruit is an apple")

  This states that Madison will eat fruits that are apples. It does not, however, exclude the possibility that Madison might also eat bananas or other types of fruit. All that is known for certain is that she will eat any and all apples that she happens upon. That the fruit is an apple is a sufficient condition for Madison to eat the fruit.

• "Madison will eat the fruit only if it is an apple." (equivalent to "If Madison will eat the fruit, then it is an apple" or "Madison will eat the fruit → the fruit is an apple")

  This states that the only fruit Madison will eat is an apple. It does not, however, exclude the possibility that Madison will refuse an apple if it is made available, in contrast with (1), which requires Madison to eat any available apple. In this case, that a given fruit is an apple is a necessary condition for Madison to be eating it. It is not a sufficient condition since Madison might not eat all the apples she is given.

• "Madison will eat the fruit if and only if it is an apple." (equivalent to "Madison will eat the fruit ↔ the fruit is an apple")

  This statement makes it clear that Madison will eat all and only those fruits that are apples. She will not leave any apple uneaten, and she will not eat any other type of fruit. That a given fruit is an apple is both a necessary and a sufficient condition for Madison to eat the fruit.

Sufficiency is the converse of necessity. That is to say, given P→Q (i.e. if P then Q), P would be a sufficient condition for Q, and Q would be a necessary condition for P. Also, given P→Q, it is true that ¬Q→¬P (where ¬ is the negation operator, i.e. "not"). This means that the relationship between P and Q, established by P→Q, can be expressed in the following, all equivalent, ways:

P is sufficient for Q

Q is necessary for P

¬Q is sufficient for ¬P

¬P is necessary for ¬Q

As an example, take the first example above, which states P→Q, where P is "the fruit in question is an apple" and Q is "Madison will eat the fruit in question". The following are four equivalent ways of expressing this very relationship:

If the fruit in question is an apple, then Madison will eat it.

Only if Madison will eat the fruit in question, is it an apple.

If Madison will not eat the fruit in question, then it is not an apple.

Only if the fruit in question is not an apple, will Madison not eat it.

Here, the second example can be restated in the form of if...then as "If Madison will eat the fruit in question, then it is an apple"; taking this in conjunction with the first example, we find that the third example can be stated as "If the fruit in question is an apple, then Madison will eat it; and if Madison will eat the fruit, then it is an apple".

In terms of Euler diagrams

• 

  A is a proper subset of B. A number is in A only if it is in B; a number is in B if it is in A.

• 

  C is a subset but not a proper subset of B. A number is in B if and only if it is in C, and a number is in C if and only if it is in B.

Euler diagrams show logical relationships among events, properties, and so forth. "P only if Q", "if P then Q", and "P→Q" all mean that P is a subset, either proper or improper, of Q. "P if Q", "if Q then P", and Q→P all mean that Q is a proper or improper subset of P. "P if and only if Q" and "Q if and only if P" both mean that the sets P and Q are identical to each other.

More general usage

Iff is used outside the field of logic as well. Wherever logic is applied, especially in mathematical discussions, it has the same meaning as above: it is an abbreviation for if and only if, indicating that one statement is both necessary and sufficient for the other. This is an example of mathematical jargon (although, as noted above, if is more often used than iff in statements of definition).

The elements of X are all and only the elements of Y means: "For any z in the domain of discourse, z is in X if and only if z is in Y."