Possibility theory


Possibility theory

Possibility theory is a mathematical theory for dealing with certain types of uncertainty and is an alternative to probability theory. Professor Lotfi Zadeh first introduced possibility theory in 1978 as an extension of his theory of fuzzy sets and fuzzy logic. D. Dubois and H. Prade further contributed to its development. Earlier in the 50s, economist G.L.S. Shackle proposed the min/max algebra to describe degrees of potential surprise.

Formalization of possibility

For simplicity, assume that the universe of discourse Ω is a finite set, and assume that all subsets are measurable. A distribution of possibility is a function operatorname{pos} from Ω to [0, 1] such that:

:Axiom 1: operatorname{pos}(varnothing) = 0

:Axiom 2: operatorname{pos}(Omega) = 1

:Axiom 3: operatorname{pos}(U cup V) = max left( operatorname{pos}(U), operatorname{pos}(V) ight) for any disjoint subsets U and V.

It follows that, like probability, the possibility measure on finite set is determined by its behavior on singletons:

:operatorname{pos}(U) = max_{omega in U} operatorname{pos}({omega})

provided "U" is finite or countably infinite.

Axiom 1 can be interpreted as the assumption that Ω is an exhaustive description of future states of the world, because it means that no belief weight is given to elements outside Ω.

Axiom 2 could be interpreted as the assumption that the evidence from which operatorname{pos} was constructed is free of any contradiction. Technically, it implies that there is at least one element in Ω with possibility 1.

Axiom 3 corresponds to the additivity axiom in probabilities. However there is an important practical difference. Possibility theory is computationally more convenient because Axioms 1-3 imply that:

:operatorname{pos}(U cup V) = max left( operatorname{pos}(U), operatorname{pos}(V) ight) for "any" subsets U and V.

Because one can know the possibility of the union from the possibility of each component, it can be said that possibility is "compositional" with respect to the union operator. Note however that it is not compositional with respect to the intersection operator. Generally:

:operatorname{pos}(U cap V) leq min left( operatorname{pos}(U), operatorname{pos}(V) ight)

Remark for the mathematicians:

When Ω is not finite Axiom 3 can be replaced by:

:For all index sets I, if the subsets U_{i,, i in I} are pairwise disjoint, operatorname{pos}left(cup_{i in I} U_i ight) = sup_{i in I}operatorname{pos}(U_i)

Necessity

Whereas probability theory uses a single number, the probability, to describe how likely an event is to occur, possibility theory uses two concepts, the "possibility" and the "necessity "of the event. For any set U, the necessity measure is defined by

:operatorname{nec}(U) = 1 - operatorname{pos}(overline U)

In the above formula, overline U denotes the complement of U, that is the elements of Omega that do not belong to U. It is straightforward to show that:

:operatorname{nec}(U) leq operatorname{pos}(U) for any U

and that:

:operatorname{nec}(U cap V) = min ( operatorname{nec}(U), operatorname{nec}(V))

Note that contrary to probability theory, possibility is not self-dual. That is, for any event U, we only have the inequality:

:operatorname{pos}(U) + operatorname{pos}(overline U) geq 1

However, the following duality rule holds:

:For any event U, either operatorname{pos}(U) = 1, or operatorname{nec}(U) = 0

Accordingly, beliefs about an event can be represented by a number and a bit.

Interpretation

There are four cases that can be interpreted as follows:

operatorname{nec}(U) = 1 means that U is necessary. U is certainly true. It implies that operatorname{pos}(U) = 1.

operatorname{pos}(U) = 0 means that U is impossible. U is certainly false. It implies that operatorname{nec}(U) = 0.

operatorname{pos}(U) = 1 means that U is possible. I would not be surprised at all if U occurs. It leaves operatorname{nec}(U) unconstrained.

operatorname{nec}(U) = 0 means that U is unnecessary. I would not be surprised at all if U does not occur. It leaves operatorname{pos}(U) unconstrained.

The intersection of the last two cases is operatorname{nec}(U) = 0 and operatorname{pos}(U) = 1 meaning that I believe nothing at all about U. Because it allows for indeterminacy like this, possibility theory relates to the graduation of a many-valued logic, such as intuitionistic logic, rather than the classical two-valued logic.

Note that unlike possibility, fuzzy logic is compositional with respect to both the union and the intersection operator. The relationship with fuzzy theory can be explained with the following classical example.

* Fuzzy logic: When a bottle is half full, it can be said that the level of truth of the proposition "The bottle is full" is 0.5. The word "full" is seen as a fuzzy predicate describing the amount of liquid in the bottle.

* Possibility theory: There is one bottle, either completely full or totally empty. The proposition "the possibility level that the bottle is full is 0.5" describes a degree of belief. One way to interpret 0.5 in that proposition is to define its meaning as: I am ready to bet that it's empty as long as the odds are even (1:1) or better, and I would not bet at any rate that it's full.

Possibility theory as an imprecise probability theory

There is an extensive formal correspondence between probability and possibility theories, where the addition operator corresponds to the maximum operator.

A possibility measure can be seen as a consonant plausibility measure in Dempster–Shafer theory of evidence. The operators of possibility theory can be seen as a hyper-cautious version of the operators of the transferable belief model, a modern development of the theory of evidence.

Possibility can be seen as an upper probability: any possibility distribution defines a unique set of admissible probability distributions by

::left{, p: forall S p(S)leq operatorname{pos}(S), ight}.

This allows one to study possibility theory using the tools of imprecise probabilities.

Necessity logic

We call "generalized possibility" every function satisfying Axiom 1 and Axiom 3. We call "generalized necessity" the dual of a generalized possibility. The generalized necessities are related with a very simple and interesting fuzzy logic we call "necessity logic". In the deduction apparatus of necessity logic the logical axioms are the usual classical tautologies. Also, there is only a fuzzy inference rule extending the usual Modus Ponens. Such a rule says that if α and α → β are proved at degree λ and μ, respectively, then we can assert β at degree min{λ,μ}. It is easy to see that the theories of such a logic are the generalized necessities and that the completely consistent theories coincide with the necessities (see for example Gerla 2001).

References

* Dubois, Didier and Prade, Henri, "Possibility Theory, Probability Theory and Multiple-valued Logics: A Clarification", "Annals of Mathematics and Artificial Intelligence" 32:35-66, 2001.

* Gerla Giangiacomo, Fuzzy logic: Mathematical Tools for Approximate Reasoning, Kluwer Academic Publishers, Dordrecht 2001.

* Zadeh, Lotfi, "Fuzzy Sets as the Basis for a Theory of Possibility", "Fuzzy Sets and Systems" 1:3-28, 1978. (Reprinted in "Fuzzy Sets and Systems" 100 (Supplement): 9-34, 1999.)

ee also

* Logical possibility
* Probability theory
* Fuzzy measure theory
* Upper and lower probabilities
* Transferable belief model

*
*


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Possibility — is the condition or fact of being possible. The Latin origins of the word hint at ability. Possibility also refers to something that could happen , that is not precluded by the facts, but usually not probable. Impossible denotes that something is …   Wikipedia

  • Theory of mind — is the ability to attribute mental states beliefs, intents, desires, pretending, knowledge, etc. to oneself and others and to understand that others have beliefs, desires and intentions that are different from one s own.[1] Though there are… …   Wikipedia

  • Theory of International Politics — is a 1979 international relations theory book, written by Kenneth Waltz that elaborated a new theory, the neorealist thory of international relations, and surpassed the cognitive limitations of the past. Taking into account the influence of… …   Wikipedia

  • Theory of justification — is a part of epistemology that attempts to understand the justification of propositions and beliefs. Epistemologists are concerned with various epistemic features of belief, which include the ideas of justification, warrant, rationality, and… …   Wikipedia

  • Theory of everything — A theory of everything (TOE) is a putative theory of theoretical physics that fully explains and links together all known physical phenomena. Initially, the term was used with an ironic connotation to refer to various overgeneralized theories.… …   Wikipedia

  • Theory of conjoint measurement — The theory of conjoint measurement (also known as conjoint measurement or additive conjoint measurement) is a general, formal theory of continuous quantity. It was independently discovered by the French economist Gerard Debreu (1960) and by the… …   Wikipedia

  • Theory of computation — In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into three major branches: automata… …   Wikipedia

  • Theory of planned behavior — In psychology, the theory of planned behavior is a theory about the link between attitudes and behavior. It was proposed by Icek Ajzen (last name sometimes spelled Aizen ) as an extension of the theory of reasoned action. It is one of the most… …   Wikipedia

  • Theory of impetus — The theory of impetus was an antiquated auxiliary or secondary theory of Aristotelian dynamics, put forth initially to explain projectile motion against gravity. It was first introduced by Hipparchus in antiquity, and subsequently further… …   Wikipedia

  • possibility of issue extinct — A contingency affecting the character of an estate as vested or contingent, as continuing or as terminated. 28 Am J2d Est § 319. A concept to be denied, both American and English authorities being in accord upon the proposition that, for the… …   Ballentine's law dictionary


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.