Possibility Theory: Simplifying Uncertainty and Human Reasoning

[Auto-Didact]

Anyone familiar with possibility theory and possibilistic analysis? I came across it during my own research on expert human reasoning/decision making.

Here is a brief description of possibility theory from a recent article behind a paywall.

Possibility theory is the simplest uncertainty theory devoted to the modeling of incomplete information. It is characterized by the use of two basic dual set functions that respectively grade the possibility and the necessity of events. Possibility theory lies at the crossroads between fuzzy sets, probability and non‐monotonic reasoning. Possibility theory is closely related to fuzzy sets if one considers that a possibility distribution is a particular fuzzy set (of mutually exclusive) possible values. However fuzzy sets and fuzzy logic are primarily motivated by the representation of gradual properties while possibility theory handles the uncertainty of classical (or fuzzy) propositions. Possibility theory can be cast either in an ordinal or in a numerical setting. Qualitative possibility theory is closely related to belief revision theory, and common‐sense reasoning with exception‐tainted knowledge in Artificial Intelligence. It has been axiomatically justified in a decision‐theoretic framework in the style of Savage, thus providing a foundation for qualitative decision theory. Quantitative possibility theory is the simplest framework for statistical reasoning with imprecise probabilities. As such it has close connections with random set theory and confidence intervals, and can provide a tool for uncertainty propagation with limited statistical or subjective information.

Possibility theory is an uncertainty theory devoted to the handling of incomplete information. To a large extent, it is similar to probability theory because it is based on set‐functions. It differs from the latter by the use of a pair of dual set functions (possibility and necessity measures) instead of only one. Besides, it is not additive and makes sense on ordinal structures. The name “Theory of Possibility” was coined by Zadeh [1], who was inspired by a paper by Gaines and Kohout [2]. In Zadeh's view, possibility distributions were meant to provide a graded semantics to natural language statements. However, possibility and necessity measures can also be the basis of a full‐fledged representation of partial belief that parallels probability. It can be seen either as a coarse, non‐numerical version of probability theory, or a framework for reasoning with extreme probabilities, or yet a simple approach to reasoning with imprecise probabilities [3].

As I see it, possibility theory offers a novel way to deal with chances which have some particular form of 'vagueness' to them. This makes it an alternative to probability theory, the standard canonical mathematical theory of chances, which focuses on randomness instead of vagueness.

I'm not entirely sure if the two theories are exclusionary with respect to each other, or if they are in some sense just different ways of looking at the same thing, eg. like looking at classical mechanics from a Newtonian, Hamiltonian or Lagrangian perspective.

In any case, possibility theory seems to be a powerful, and more importantly, intuitive tool, which seems to be a lot simpler to learn than probability theory and seems to more closely or more naturally model human reasoning than probability theory does.

 

[jedishrfu]

It would help if you provided a peer reviewed reference for us to evaluate the quoted piece.

 

[Auto-Didact]

Quote was from here:
http://link.springer.com/referenceworkentry/10.1007/978-1-4614-1800-9_139

Foundational paper:
http://www.sciencedirect.com/science/article/pii/0165011478900295

Random other paper:
http://www.sciencedirect.com/science/article/pii/S0167947306001149

 

[jedishrfu]

Wikipedia has a summary of the theory:

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

One thing though, it doesn't seem to have generated too much traction in the math community as the Zadeh work is from 1978 and Didier's last paper is from 2006.

 

[fresh_42]

One thing though, it doesn't seem to have generated too much traction in the math community as the Zadeh work is from 1978 and Didier's last paper is from 2006.

Maybe @Demystifier knows something about it.

 

[Demystifier]

Maybe @Demystifier knows something about it.

Unfortunately, I don't.

 

[jedishrfu]

I found another article on it in 2011:

https://www.irit.fr/~Didier.Dubois/Papers1208/possibility-EUSFLAT-Mag.pdf

It has some history and speculates on its future uses.

And another in 2013 so I think it's still alive but not yet popular:

http://www.ccsenet.org/journal/index.php/ijsp/article/download/22906/15494

 

[Auto-Didact]

This isn't exactly applied mathematics, but Chapter 16.5.2 (pgs. 616-638) of this (logic & set theory heavy) book from 2015 should definitely count as an application:

Sadegh-Zadeh 2015, Handbook of Analytic Philosophy of Medicine

 

[stevendaryl]

Anyone familiar with possibility theory and possibilistic analysis? I came across it during my own research on expert human reasoning/decision making.

Years ago, I did computer security research using such a theory. The disadvantage is that there is no quantitative aspect; among the possibilities, there is no notion of one being more likely than another.

What my company used it for was a non-quantitative definition of information flow.

The quantitative definition of information flow is that there is a flow of information from Alice to Bob if the probability distribution on possible outcomes visible to Bob is affected by Alice's actions. Shannon's definition of information can then be used to quantify how many bits per second can be transmitted from Alice to Bob.

In lots of cases, though, there is no reliable estimate of the probabilities for various results. We were looking at the interaction of concurrent programs. It's easy enough (at least conceptually) to enumerate all possible execution sequences, but until the program is actually running on a real machine, there is no reliable way to give probabilities to the various possibilities. So we used a "possibilistic" definition of information flow: There is a potential information flow from Alice to Bob if Alice's actions affect the set of possible sequences of events visible to Bob.

 

[chiro]

Hey Auto-didact.

You should think about the constraints you have and use that to determine what is possible within those constraints.

This is one of the "basic" ideas of mathematics.

 

[Auto-Didact]

Years ago, I did computer security research using such a theory. The disadvantage is that there is no quantitative aspect; among the possibilities, there is no notion of one being more likely than another.

What my company used it for was a non-quantitative definition of information flow.

The quantitative definition of information flow is that there is a flow of information from Alice to Bob if the probability distribution on possible outcomes visible to Bob is affected by Alice's actions. Shannon's definition of information can then be used to quantify how many bits per second can be transmitted from Alice to Bob.

In lots of cases, though, there is no reliable estimate of the probabilities for various results. We were looking at the interaction of concurrent programs. It's easy enough (at least conceptually) to enumerate all possible execution sequences, but until the program is actually running on a real machine, there is no reliable way to give probabilities to the various possibilities. So we used a "possibilistic" definition of information flow: There is a potential information flow from Alice to Bob if Alice's actions affect the set of possible sequences of events visible to Bob.

The non-quantitative aspect that you are describing seems to be in line with the qualitative version of possibility theory, basically providing a basis for decision theory, as described by Didier & Dubois.

There are a few versions of a quantitative version of possibility theory, e.g. a recent version by Sadegh-Zadeh (see my earlier post), but these only seem utilizable given some inherent interpretative linguistic-like vagueness in the data, as occurs in human communication and reasoning.

I'm wondering therefore how vague, in the above sense, the communications or interactions are between programs. If they aren't very vague inherently i.e. if their vagueness is artificial, then I don't think the quantitative version of possibility theory is necessary, let alone preferable or rightly applicable.

Hey Auto-didact.

You should think about the constraints you have and use that to determine what is possible within those constraints.

This is one of the "basic" ideas of mathematics.

I'm not sure to which of my posts this is referring. If you're referring to my own research I alluded to, you have probably misunderstood me: I'm claiming possibility theory seems to be (part of) a mathematical model of the theory of human reasoning about possibilities and how we handle them naturally, as opposed to 'artificial' and learned human reasoning in the form of applied probability theory.

This seems to be true in the decision making of certain expert domains based on a fairly good match with experimental psychological data, where decision making based solely on standard probabilistic methods reliably lead to wrong decisions and therefore they have already been ruled out experimentally as candidate theories.

This doesn't mean that probability theory is false, it merely implies that it is a specific mathematical idealization, possibly even one of many, based on certain axioms; the same is true of possibility theory. Of course, mathematical probability theory was historically developed much earlier than mathematical possibility theory, causing it to be a much richer theory at the moment.

This historical precedence should however have no bearing on the scientific discussion of the ontology of chance, randomness and related concepts, nor grant probability theory a possibly unwarranted sole primacy on these concepts in domains such as psychology and artificial intelligence or even physics, as often is the case today.

 

[stevendaryl]

I'm wondering therefore how vague, in the above sense, the communications or interactions are between programs. If they aren't very vague inherently i.e. if their vagueness is artificial, then I don't think the quantitative version of possibility theory is necessary, let alone preferable or rightly applicable.

There is nothing vague about it. You can say precisely (well, given a model of the system as concurrent processes) what Bob learns by observing a sequence of outputs. It's just that the possibilistic semantics doesn't distinguish between something random (once in a million years) and something predictable (99 times out of 100). So by possibilistic reasoning, you can eliminate all information flows by just adding randomness to the system. Of course, that doesn't actually eliminate information flows: If you are on a noisy phone call, you can still communicate, just more slowly (that's what Shannon's theory of information tried to quantify).

 

[chiro]

Usually you assume that you have constraints on certain observations and then you try and reconcile these constraints for consistency to see what is implied.

The more information you have, the better the reliability of the estimate you use on the data.

 

[MarneMath]

Chiro, I too am rather confused what you are actually trying to convey. "Possibility Theory" is basically an extension/application of fuzzy logic that has sporadic development. It seems like you are trying to answer how to determine what's possible and are unaware of this rather obscure field. The odds that the OP finds an expert in this field in this forum are rather low since I figure there's probably like maybe 10 experts in the world? (I have no facts to back that up, but seriously possibility theory is obscure.).

 

[TeethWhitener]

In the interest of rescuing a potentially interesting thread from devolving into personal attacks...

How complicated is it to add modal operators to fuzzy logic? It sounds like this is roughly what Zadeh is doing. (I don't have access to the paywalled papers right now.) Alternatively, how complicated is it to turn the (Boolean) accessibility relation in Kripke semantics into a continuous "membership" function? (That could actually be an interesting question.) You might even be able to treat accessibility and truth values separately as continuous, though you might have to tweak the formalism of the model a bit.

I find it a little odd that none of the info I've found on a field called "possibility theory" even mentions in passing modal logic.

 

[TeethWhitener]

I'm not entirely sure if the two theories are exclusionary with respect to each other, or if they are in some sense just different ways of looking at the same thing, eg. like looking at classical mechanics from a Newtonian, Hamiltonian or Lagrangian perspective

From what I can tell from the Wikipedia article, they're not identical. Possibility theory is basically a variation on the notion of a probability measure where the additivy of disjoint sets:
$$prob(U\cup V) = prob(U) +prob(V)$$
is replaced by a maximum principle:
$$poss(U\cup V) = max(poss(U),poss(V))$$
The formalism allows the definition of necessity and possibility operators as dual, which is the same as in standard modal logic. Dempster-Shafer theory generalizes this further by considering any monotonic increasing function over disjoint sets as a valid "probability" measure.

I don't know anything about alethic modal logic, but standard modal logic treats much of this quantitatively. Maybe the innovation in possibility theory is a set theoretic notion of the accessibility relation in possible worlds semantics? But I wonder if you couldn't achieve the same end by defining a possibility measure as the fraction of possible worlds in which a proposition is true under a given accessibility relation. The advantage of modal logic is that your set of axioms determines your accessibility relation and vice versa, but the disadvantage is that the possible world semantics are a lot of extra baggage that might not strictly be necessary if you're not worried about broad properties of the overall model (e.g., completeness).

 

[Auto-Didact]

From what I can tell from the Wikipedia article, they're not identical. Possibility theory is basically a variation on the notion of a probability measure where the additivy of disjoint sets:
$$prob(U\cup V) = prob(U) +prob(V)$$
is replaced by a maximum principle:
$$poss(U\cup V) = max(poss(U),poss(V))$$
The formalism allows the definition of necessity and possibility operators as dual, which is the same as in standard modal logic. Dempster-Shafer theory generalizes this further by considering any monotonic increasing function over disjoint sets as a valid "probability" measure.

I don't know anything about alethic modal logic, but standard modal logic treats much of this quantitatively. Maybe the innovation in possibility theory is a set theoretic notion of the accessibility relation in possible worlds semantics? But I wonder if you couldn't achieve the same end by defining a possibility measure as the fraction of possible worlds in which a proposition is true under a given accessibility relation. The advantage of modal logic is that your set of axioms determines your accessibility relation and vice versa, but the disadvantage is that the possible world semantics are a lot of extra baggage that might not strictly be necessary if you're not worried about broad properties of the overall model (e.g., completeness).

You're right about the two theories definitely not being identical. A high degree of possibility does not imply a high degree of probability, or viceversa.

Alethic modal logic refers to modalities of truth, classically those of necessity and possibility; standard modal logic I believe can be much richer in its repertoire of modal operators than simply these two. The key point is that classical modal logic functions as a logic, involving premises, MP/MT, proofs, etc, i.e. it is a way of going from premises to sound/valid conclusions. (Please correct me, if I'm wrong on this!)

Possibility theory, on the other hand, functions quite analogous to probability theory: there are fuzzy sets signifying imprecise possibly partially overlapping concepts, degrees of possibility laying on the unit interval quantifying set membership for each element in a fuzzy set, and possibility distribution functions wherein the various possibilities do not sum up to 1. In order to draw conclusions in uncertainty and so make decisions, a maximum of the minimum joint possibility strategy is employed for each of the decisions under consideration, leading to a best decision, which is after all still a guess at best.

 

[Auto-Didact]

The odds that the OP finds an expert in this field in this forum are rather low since I figure there's probably like maybe 10 experts in the world? (I have no facts to back that up, but seriously possibility theory is obscure.).

During my further digging for applications of possibility theory, I just came across this book: Fuzzy Mathematics in Economics and Engineering.

And lo and behold, one of the first references I can find in it is to a book by @A. Neumaier on interval arithmetics, which, when extended, happens to be one of the ways of doing fuzzy arithmetics. Perhaps I'm in luck today!

 

[Dale]

Several heated posts have been removed. I am reopening the thread, but please keep things exceptionally civil from this point on.

 

[sysprog]

Multi-valued logic (>2 values) allows 1 or more values along the interval between 0 and 1. It's convenient to represent greater likelihood than neutrality with numbers greater than .5, and lesser likelihood with numbers lesser than .5, with .5 assigned to indifference. For some purposes, comparisons of continua are useful. In familiar classical logic we typically look at 0 and 1, but in electronics, it's not atypical to work with 5 values, which may be called low, low-mid, mid, mid-high, and high. Assigning those values discrete numbers, e.g. 0, .25, .5, .75, 1. (or 0, 1/4, 1/2, 3/4, 1), or obtaining sets of more exact measurements within the ranges, enables using the numbers as weights in calculations. Informally we might name the values false, improbable, neutral, probable, and true. The intervals and detents can be defined in various scales and sizes depending on the application.

 

[TeethWhitener]

I was finally able to access Zadeh's paper. It's interesting.

You're right about the two theories definitely not being identical. A high degree of possibility does not imply a high degree of probability, or viceversa.

According to the definitions above, the possibility measure is strictly EDIT: GREATER THAN (...whoops) or equal to the probability measure. This makes sense, in that an event with a low possibility measure shouldn't have a high probability measure.

Alethic modal logic refers to modalities of truth, classically those of necessity and possibility; standard modal logic I believe can be much richer in its repertoire of modal operators than simply these two. The key point is that classical modal logic functions as a logic, involving premises, MP/MT, proofs, etc, i.e. it is a way of going from premises to sound/valid conclusions. (Please correct me, if I'm wrong on this!)

Necessity and possibility are the standard modal operators, defined dual to one another. The modern way of handling necessity and possibility semantics is by using Kripke models (also called "possible worlds semantics"), where the truth or falsity of a (non-modal) proposition can vary from world to world, with possibility and necessity determined by an accessibility relation between worlds. So when we say "X is possible," that means that we can "see" a world in which X is true. In other words, there exists an accessibility relation between the actual world (where X may or may not be true) and a possible world (in which X is true). Typically this accessibility relation is Boolean: either world 1 can "see" world 2 or not (in more mathematical terms: $R$ is a relation between worlds $w_i$ such that either $(w_1,w_2) \in R$ or $(w_1,w_2) \not \in R$). My comment above was wondering what would happen if you made the accessibility relation fuzzy (or proportional), and what relation that would bear to possibility theory. I honestly don't know the answer to that. It might be an interesting research project.

There are "multimodal" logics, where more than one set of modal operators is defined. In practice, what that tends to mean is that you define multiple accessibility relations, one for each set of dual operators. But as far as I can tell, the accessibility relations are still Boolean. But I don't know very much about it.

 

[Auto-Didact]

I was finally able to access Zadeh's paper. It's interesting.According to the definitions above, the possibility measure is strictly EDIT: GREATER THAN (...whoops) or equal to the probability measure. This makes sense, in that an event with a low possibility measure shouldn't have a high probability measure.Necessity and possibility are the standard modal operators, defined dual to one another. The modern way of handling necessity and possibility semantics is by using Kripke models (also called "possible worlds semantics"), where the truth or falsity of a (non-modal) proposition can vary from world to world, with possibility and necessity determined by an accessibility relation between worlds. So when we say "X is possible," that means that we can "see" a world in which X is true. In other words, there exists an accessibility relation between the actual world (where X may or may not be true) and a possible world (in which X is true). Typically this accessibility relation is Boolean: either world 1 can "see" world 2 or not (in more mathematical terms: $R$ is a relation between worlds $w_i$ such that either $(w_1,w_2) \in R$ or $(w_1,w_2) \not \in R$). My comment above was wondering what would happen if you made the accessibility relation fuzzy (or proportional), and what relation that would bear to possibility theory. I honestly don't know the answer to that. It might be an interesting research project.

That indeed seems an interesting project and not obviously in direct relation to possibility theory. I guess such a logic would be called something akin to 'fuzzy modal logic'; a quick search gives among many others this paper.

There are "multimodal" logics, where more than one set of modal operators is defined. In practice, what that tends to mean is that you define multiple accessibility relations, one for each set of dual operators. But as far as I can tell, the accessibility relations are still Boolean. But I don't know very much about it.

Yeah, that's what I was referring to; alethic operators are simply the standard ones you are referring to. In any case, Zadeh in his foundational paper also refers to modal logic (second footnote on second page) making clear that the concept of possibility used there is different, saying:

$^2$The interpretation of the concept of possibility in the theory of possibility is quite different from that of modal logic [2] in which propositions of the form "It is possible that..." and "It is necessary that..." are considered.

 

[TeethWhitener]

That indeed seems an interesting project and not obviously in direct relation to possibility theory.

You could, in principle, define a function $f(w_1,R,p)$ which takes as its input a world, an accessibility relation, and a proposition, and spits out the fraction of worlds that are $R$-accessible from $w_1$ in which $p$ is true vs. the total number of worlds that are $R$-accessible from $w_1$. This would give a degree of possibility, in a sense. It might be interesting to ask if this bears any relation to the possibility measure defined by Zadeh.

I guess such a logic would be called something akin to 'fuzzy modal logic'; a quick search gives among many others this paper.

This was pretty much exactly what I was talking about in that post. Can't slip anything by those crafty logicians.

 

[TeethWhitener]

One more thing and then I'm done: It looks like my description in post 23:

You could, in principle, define a function f(w1,R,p)f(w1,R,p)f(w_1,R,p) which takes as its input a world, an accessibility relation, and a proposition, and spits out the fraction of worlds that are RRR-accessible from w1w1w_1 in which ppp is true vs. the total number of worlds that are RRR-accessible from w1w1w_1. This would give a degree of possibility, in a sense. It might be interesting to ask if this bears any relation to the possibility measure defined by Zadeh.

is basically equivalent to the possibility measure defined by Zadeh in his 1978 paper, leaving open the question for how to treat joint possibility distributions. This seems like pretty fertile ground to till in terms of research ideas, but I haven't really studied the state of the art in the field for many years, so I don't know how much of this has already been worked out.