I'm trying to understand Dempster-Shafer, the part before the combination rule.

example

Say I have a hypothesis space $H = \{x, y, z\}$, which describes three things that might be true about the world. Then the power set $2^H = \{\emptyset, \{x\}, \{y\}, \{z\}, \{x,y\}, \{x,z\}, \{y,z\}, \{x,y,z\}\}$ gives a set of possible states the world might take (or does it? See my possible answer.)

Say $m:2^H \rightarrow [0,1] = 0, 1, 0, 0, 0, 0, 0, 0$ for the elements of the powerset above. This is the "mass" function that "expresses the proportion of all relevant and available evidence that supports the claim that the actual state belongs to $A$ but to no particular subset of $A$", so all my evidence points to $\{x\}$ as the true state of my world.

Since $belief(A) = \sum_{B|B \subseteq A} m(A)$, then $belief(\{x,y\}) = \sum_{B \in\{\emptyset, \{x\}, \{y\}, \{x,y\}\}} m(B) = 0 + 1 + 0 + 0 = 1$

$belief(A)$ is said to be a lower bound on the probability of $A$, so here $P(\{x,y\}) = 1$.

This makes no sense to me. Wikipedia is very clear that "The value of $m(A)$ pertains only to the set $A$ and makes no additional claims about any subsets of $A$, each of which have, by definition, their own mass."

question

So how, when all the evidence points to $\{x\}$ alone in my contrived example can the probability of $\{x, y\}$ be $1$?

possible answer

Are the key words here particular subset of $A$? So belief is a lower bound on the probability that the truth lies in the possibilities $A$ offers rather than the truth being $A$ itself?

I've seen elsewhere that the hypotheses are supposed to be mutually exclusive. If this is truly the case, then all the hypotheses in $A$ need not be true, and $P(A)$ need not be some kind of joint probability. If true, then my result makes sense, since $\{x\}$ is clearly a member of the set $\{x,y\}$.

reasoning on top of my speculative answer

Why, if that is the case, is it necessary to carry around an exponentially large mass function? Say some new evidence indicates that $x$ or $y$ are more likely compared with $z$. Can't I adapt some pmf over the possibilities themselves rather than adjusting the masses of all the entries of the power set?

  • Maybe I'm just a Bayesian at heart: "A Bayesian would model the color of a car as a probability distribution over (red, green, blue), assigning one number to each color. Dempster–Shafer would assign numbers to each of (red, green, blue, (red or green), (red or blue), (green or blue), (red or green or blue)) which do not have to cohere, for example Bel(red)+Bel(green) != Bel(red or green)." – pvlkmrv Sep 10 at 20:49
  • "This may be computationally more efficient if a witness reports "I saw that the car was either blue or green" in which case the belief can be assigned in a single step rather than breaking down into values for two separate colors." Can you just assign in a single step, though? Wouldn't you have to renormalize the mass function before you used it anywhere? And doesn't that involve an exponential instead of a linear number of options now? I don't buy this efficiency argument at all. – pvlkmrv Sep 10 at 20:50
up vote 0 down vote accepted

I've done some further study. I was able to answer some more general questions I asked prior to these, and for a fuller explanation of my journey, D-S, message passing, how this relates to Bayesian Networks, and why we care at all I recommend going over there to read that.

Specifically for these questions:

  • How, when all the evidence points to $\{x\}$ alone in my contrived example can the probability of $\{x,y\}$ be $1$? Are the key words here particular subset of $A$ [and mutual exclusivity]? So belief is a lower bound on the probability that the truth lies in the possibilities $A$ offers rather than the truth being $A$ itself?

$\qquad$Yes, my speculative answer is correct: $belief(A)$ is a lower bound on the "probability" that the answer lives among the options in $A$, which are mutually exclusive possible outcomes for my output, which in my example may take values $x$, $y$, or $z$.
$\qquad$Caveat: I put "probability" in quotes because, although $belief$ and $plausibility$ do reflect upper and lower bounds of some kind of range of uncertainty, the way D-S reasons with uncertainty is really strange and has been thoroughly criticized. In fact, in the course of my search I uncovered a flame war between AI researchers in the 80s, specifically this hilariously scathing paper by a man with an equally hilarious name:

...The same cannot be said for those who invent new theories for reasoning under uncertainty, such as "Certainty Factors", "Schafer/Dempster Theory", "Confirmation Theory", "Fuzzy Logic", "Endorsements" etc.

These theories will be shown below to be at best unnecessary and at worst misleading (not to mention confusing to the poor novice faced with so many possibilities). Each one is an attempt to circumvent some perceived difficulty of probability theory, but as shown below these difficulties exist only in the minds of their inventors.

An analogy can be drawn between the situation in AI in the late 1970s, where Pat Hayes, in a paper entitled "In Defence of Logic"[10], found it necessary to take a broadside at the proliferation of new representation languages (with associated inference procedures) that purported to solve difficulties with the logical approach. He showed that far from being "nonlogical" it is possible to cast such languages into an equivalent logical form, and by doing so provide a clear semantics. In addition, he pointed out the obvious but unpopular fact that logic has been around for a long time and has a considerable body of research and experience that no new theory can match. Similarly today we have a set of new theories for dealing with uncertainty, despite the fact that probability theory has been around for three centuries and, as shown below, is sufficient for the task.

So basically, I've been confused because this is confusing. The representation of belief itself in D-S is funky.

  • Why is it necessary to carry around an exponentially large mass function?

$\qquad$Caveat. It actually isn't always necessary to carry around the whole mass function to reason with D-S. For example, the mass function $m$ in my example above could be fully defined with $m(\{x\}) = 1$.
$\qquad$ The figure below from this paper gives a really good example of how reasoning through belief combination is done in D-S: It's all based on set intersections. As a consequence, you really may not need to define the exponentially large function all the time. combination in D-S

  • Can't I adapt some pmf over the possibilities themselves rather than adjusting the masses of [a D-S belief function]?

$\qquad$Yes, and, as alluded to already, history and modern academics seem to be strongly preferring the pmf representation, so this is what people tend to do most of the time.
$\qquad$The authors of that IEEE paper claim the D-S representation is better or more flexible, because if, for example, I think with 50% probability the answer is $x$ and with 50% probability the answer is simply in the set of $x$ or $y$ without giving preference to either, then I can represent this without modification in only two expressions as $m(\{x\}) = 0.5$, $m(\{x, y\}) = 0.5$, and I don't have to do the work of putting those beliefs in to a pmf over all possibilities.
$\qquad$However, I can put this belief, say over the domain $\{x, y, z\}$, in to form of a pmf through the "pignistic transform" to get $p(x) = 0.75$, $p(y) = 0.25$, $p(z) = 0$. And in fact, somewhat amusingly given their fetishization of D-S, the authors do just this to generate decisionable output probabilities.

  • ...Can you just assign in a single step, though? Wouldn't you have to renormalize the mass function before you used it anywhere? And doesn't that involve an exponential instead of a linear number of options now? I don't buy this efficiency argument at all.

$\qquad$No, you really can't assign in a single step, because Yes, you do have to renormalize if you still want the sum of weights in $m$ to be $1$. Caveat about exponentiality: The authors of the IEEE paper were, thankfully, concerned about it too.

Since the belief function representation is on the power set ($2^\Theta$) of the frame, and the size of the joint frame of a set of variables is equal to the product of the frame size of all the variable frames, it is easy to understand that the computation complexity of such a brute-force approach will become very unrealistic quickly as the number of variable increases. This is especially a problem when one is only interested in the true states of only a few of the many variables in a system.

They go on to give an example of finding a belief by basically elevating all belief functions up to the highest-dimension domain, combining them there, and then marginalizing to get the things they care about. But then they point out there is a clever trick where you don't necessarily have to elevate things up in to that domain; you can use "local frames" instead to minimize the number of computations.
$\qquad$They go on to claim their Valuation-Based System can effectively exploit these shortcuts and run efficiently. All the things happening under the hood to make this work are not given, but they do have earlier publications specifically about this system.
$\qquad$The trouble is that in the general case using only local relationships to compute partial solutions might not be possible: If everything is related to everything, then you still have to elevate to the largest frame. And if your belief functions aren't sparse, you're going to be doing an exponential number of multiplications to find your combined belief.
$\qquad$So I was right to be worried about this, but it appears with enough gymnastics, in certain limited applications, they could make it work. Again, reasoning with Bayes' Rule on pmfs avoids many of these problems, which is probably why today people prefer it and exclusively teach that method.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.