Imprecise beliefs: a tiny introduction

davidad

Richard Ngo challenged me to set a time box and write down as many of the most important features of my formal epistemology as I can in one sitting. Here goes.

Motivation: Where probability distributions fail...

...to express beliefs

There is no probability distribution over that says “”. That is a support condition about probability distributions, namely, $⨾ ⨾$ . Some s satisfy this condition and some do not; but there is no that expresses the range belief itself.
There is no probability distribution over that says “ and are independent”. This is an equation condition about probability distributions, namely, . Some s satisfy this equation and some do not; there is no that expresses the independence belief itself.
There is no probability distribution over that can express a conditional probability distribution , even though this is just as essential a part of a Bayesian reasoner's epistemic state as her prior. A conditional probability distribution is a family of probability distributions indexed by the condition variable, not a probability distribution. There is no single distribution that expresses it.

...to make safety tradeoffs

Suppose there is an unfair coin, which you know to be unfair (but not exactly how much or in which direction), and you must choose between three options: bet on Heads, bet on Tails, or bet instead on a fair d20 coming up at least 12. Exercise for the reader: Every probability distribution you could possibly believe makes choosing the d20 irrational.
- The situation doesn't even need to involve Omega for the d20 to be a permissible choice; if the coin is chosen by Omega (who adversarially determines which way the unfair coin is unfair by predicting your betting choice), the d20 is the uniquely rational choice, making the orthodox Bayesian view (that beliefs are probability distributions) clearly wrong.
- Maximum entropy does not save you! In fact, if you follow Jaynes’ principle of maximum entropy (take the maximum entropy probability distribution consistent with your beliefs to be your belief), then the bet on Heads and the bet on Tails both strictly dominate the bet on the d20.

Beliefs, according to davidad

Definition 1. Given a state space , we define probability space as the space of all conceivable probability distributions on .

Definition 2. A belief about () is a functional

which is lower semicontinuous (meaning that ).

Following Richardson, we interpret as the level of inconsistency between the conceivable probability distribution and one's belief .

Following Lawvere, we order by (“backwards”), and pointwise, so that all conceivable beliefs about form a (thin) category of beliefs . Morphisms in can be interpreted as implications . is a commutative semicartesian monoidal category with .

Slogan: When one has multiple beliefs at the same time, one's overall belief is simply the sum of its parts.

All other known notions of belief are full subcategories

Bayesian beliefs

Definition 3. If one has a prior (big if), then one's prior belief is

Bayesian updating

Definition 4. If one has a belief over a hypothesis space, and the total state space of the situation is the product of hypothesis space and data space , then one's prior belief about is the inverse-image functor

Definition 5. An observation is a closed subset .

Example 6. If one observes that , this is the subset .

Definition 7. The belief that corresponds to an observation is

Definition 8. If one has a conditional distribution , then one's conditional belief is

Example 9. If one has a likelihood function , then the previous definition applies with and :

Definition 10. A Bayesian reasoner with prior and likelihood function has belief state

Theorem 11. The two components of a Bayesian reasoner's initial belief state, only one of which is a probability distribution, simply sum when lifted into the belief space, forming the joint belief:

However, this would be meaningless unless we could recover the Bayesian update by also summing the observations in the belief space.

Theorem 12. Whenever the Bayesian posterior is well-defined, then

with a constant denoting the level of incompatibility of the observation with the Bayesian reasoner's initial belief state, namely the prior predictive surprisal, .

Notice that the orthodox Bayesian update's “normalization” to a full-mass posterior distribution silently subtracts away the constant — the amount of incompatibility between the observed data and the statistical model as a whole — which is Deborah Mayo's criticism of Bayesian epistemology in a nutshell.

Bayesian beliefs have fully trivial categorical structure (no Bayesian belief implies any other Bayesian belief except itself), so Bayesian beliefs about are a full subcategory of , but the content of this is just that is injective (its post-inverse is ).

Infra-Bayesian beliefs (Kosoy and Appel)

Definition 13 (Kosoy and Appel). A homogenous ultracontribution is a nonempty topologically-closed convex down-closed subset of subprobability space, .

Theorem 14. Homogenous ultracontributions (ordered by ) form a full subcategory of . Specifically, given , the corresponding belief is

and given a belief , the corresponding subset of subprobability space is

and . Furthermore, is a member of iff is convex in probability space, which every satisfies.

Definition 15 (Kosoy and Appel). A homogenous ultradistribution is a homogenous ultracontribution whose intersection with the full-mass face is nonempty ().

Of course, is also a full subcategory of , since is a full subcategory of .

MWER (Halpern and Leung)

Theorem 16. Homogenous ultradistributions are exactly isomorphic to the belief states of Halpern and Leung's MWER framework (Minimax Weighted Expected Regret), via

Theorem 17. The updating process of simply adding , which is equivalent to that of Theorem 12, is also equivalent to Halpern and Leung's prescribed belief-updating procedure on the domain of their belief states.

Note: via the transform, this updating process is also consonant with the famous Multiplicative Weight Update family of algorithms (although I am not yet confident about whether e.g. AdaBoost is literally a special case of it).

Probabilistic dependency graphs (Richardson and Halpern)

Richardson and Halpern's PDGs, a common generalization of Bayes nets and factor graphs, take their semantics in functionals , and these functionals are always lower semicontinuous (though Richardson does not explicitly prove this), so therefore every PDG denotes a belief in my sense. Furthermore, the combination of PDGs with overlapping variables denotes exactly the sum of their beliefs, so the semantics of PDGs is a monoidal functor from PDGs into beliefs.

For a wide parameter regime of PDGs ( on every edge, or equivalently ) — assumed by some but not all PDG theorems [correction due to Richardson himself in the comments] — the beliefs they denote are convex, and thus immediately satisfy the exp-convexity criterion to be transformed into homogenous ultracontributions. However, even these PDGs do not typically denote homogenous ultradistributions, unless their semantics are “normalized” (by subtracting ).

PDGs can also express independence beliefs, which are non-convex while remaining lower semicontinuous.

Credal sets (Cozman)

Definition 18 (Cozman). A credal set is a nonempty closed convex set of probability distributions, .

Theorem 19. Credal sets about (ordered by ) form a full subcategory of . Specifically, given , the corresponding belief is

and given a belief , the corresponding credal set is

which is topologically closed by lower semicontinuity of .

Previsions (Goubault-Larrecq)

Definition 20 (Goubault-Larrecq). A gamble about is a Borel function . A prevision about is a functional such that and . An upper prevision is a prevision which is sub-additive: . A continuous upper prevision is an upper prevision which is Scott-continuous (for every directed family with least upper bound , ).

Definition 21. A coherent continuous upper prevision is a continuous upper prevision satisfying .

Theorem 22. Coherent continuous upper previsions about form a full subcategory of . Specifically, given the coherent continuous upper prevision , the corresponding belief is

and given a belief , the corresponding upper prevision is

The monad (Mio, Sarkis, and Vignudelli)

Definition 23 (Mio, Sarkis, and Vignudelli). The monad is defined on sets as the set of non-empty finitely-generated down-closed convex sets of subprobability distributions .

Mio, Sarkis, and Vignudelli prove that this monad is presented by the equational theory of semilattices equipped with finite probabilistic choice and , making in a strong sense the smallest semantic universe that can simultaneously interpret finite nondeterminism, finite probability, and partiality (and partiality is, in turn, needed to interpret either inconsistent beliefs or nonterminating probabilistic programs).

Theorem 24. ordered by inclusion is a full subcategory of , assuming is a Polish space. Specifically, this condition implies that finitely-generated convex sets are topologically closed, which makes a full subcategory of .

Thanks for putting this together! Permit me to promote PDGs a bit, which I think are under-sold here :)

First: motivating a "degree of inconsistency" scoring-function semantics, valued in and additive, was a primary innovation of the original PDG paper, which I think deserves some credit for this high-level picture of beliefs. Furthermore, my sense is that PDGs already capture the important elements of these other formalisms (many of them actually embed as nice sub-classes of PDGs), and the extra structure of the PDG formalism yields significant benefits (e.g., a visual calculus that yields insight into key facts of information theory and algorithms in machine learning). Further generalization is definitely possible (c.f., Ch3 of Halpern's Reasoning about Uncertainty), but, in practice, I see little reason to generalize further than PDGs.

Why not simply declare that everything of import is a set/category/TM? In tension with generality is the desire to expose minimal knobs and buttons to the modeler. A common complaint about probability is that it's too difficult for an agent to maintain a joint probability distribution about all variables of interest---and the burden of selecting a lower semi-continuous function on distributions (over which variables?) is WAY higher, since there are far more choices to make, and less standard guidance on how to make them. PDG semantics are arguably the natural way to answer these questions and produce a belief starting from probabilistic information and confidences.

A challenge for @davidad: can you motivate a scenario that really requires stepping outside of the sub-class of beliefs generated by PDGs, and is clearly better-modeled by a different lower semi-continuous function?

Finally, a couple of quick technical points/corrections:

PDG semantics are convex for many parameter values of interest, but they can also be non-convex, e.g., when qualitative/structural beliefs are strong (the PDG that simply claims that variables X and Y are independent, for example, has a non-convex set of optima), or when some confidences become negative, as occurs when we model distrust. In these extended parameter regimes, technically there are also cases when the PDG scoring function can be negative---and, while we can avoid these regimes or clip the score to zero to fit into this picture, I think something (related to the principle of maximum entropy) would be lost.
Lower semi-continuity was conceptually key in proving some of the theorems, but indeed it's not explicit.
I have been working on a categorical picture of PDGs for some time. While I endorse the characterization of PDGs as forming a monoidal category, some details still need to be worked out. Furthermore, I strongly suspect there's a beautiful theory lurking here that interacts with Baez and Fritz's characterization of relative entropy and Leinster's information loss. If there are any readers interested helping to develop this theory, please don't hesitate to get in touch!

A second, different kind of answer to your challenge is a stochastic PDE. The PDG formalism is finitary (finite node set and finite edge set , with semantics a sum of -indexed data), but a random field needs a node per point of spacetime (uncountably many). The natural belief functional over field configurations is the action functional (Freidlin-Wentzell), which is lsc on (via the weak topology), but is not the semantics of any PDG.

As a concrete example, for the SPDE , its semantics as a belief is

Thanks for your thoughtful engagement!

On syntax vs semantics, I fully agree that your work is the state of the art of how to produce a belief .

On convexity, I was going off of Lemma A.1 of "Probabilistic Dependency Graphs", but now I see that this is guaranteed of the full semantics only under the condition . (This is a condition that many, but not all, PDG theorems assume; a collegial technical observation back at you: Proposition 3.2 is stated in the main body with the premise , but its proof in the appendix actually strengthens the theorem by only using the premise , which is equivalent to .) I also overinterpreted the shading of the "non-convex region" in Figure 1 of "Loss as the Inconsistency of a PDG" as suggesting that you considered the non-convex region to be "out of bounds" in terms of what counts as valid choices of , but in fact that's exactly the "distrust" regime you're now floating as live and relevant to MaxEnt (interesting).

My current view is that negative inconsistency/incompatibility is an anti-pattern, because it means we no longer have the property that the "expected value" of is . If you want to model "whatever Bob said, he's probably wrong", I would pose this as something like (for some radius , and assuming metrized), which is non-convex but still non-negative and lower semi-continuous. I would also put this forward as an initial answer to your challenge, as I'm pretty sure no finite PDG realizes this belief as its semantics.

Re: d20

If you use Bayesianism + CDT, and the coin has already landed: Yes, you never take the d20 bet.

Why CDT is well-motivated for Bayesianism by default: Because CDT motivates taking bets according to one's subjective probabilities. Without CDT (or something close), non-Bayesian agents can choose to decline bets that would naively be good according to their subjective probabilities. This makes it harder to apply Dutch book arguments to them (to argue they should be Bayesian). See my recent post, "Simple Dutch books versus Sleeping Beauty halfers".

As my post suggests, it is worth considering EDT+FNC as a quasi-Bayesian anthropic decision theory, as the main alternative to CDT+SIA. Here's how EDT+FNC reasons on the d20:

"I have no information other than the problem setup; there is no FNC update to make so far. Evidentially on my choosing Heads, Omega has made it Tails, meaning I lose. Similarly, I lose evidentially on choosing Tails. Evidentially on the d20 bet, I'm not guaranteed to lose. Therefore I should pick the d20 bet."

So they pick the d20 bet despite assigning at least 50% subjective probability to at least one of Heads and Tails.

Since FNC is not even Bayesian (dynamic inconsistency as pointed out by Stuart Armstrong), Bayesianism does not combine well with EDT. See Stuart Armstrong's Anthropics: Full Non-indexical Conditioning (FNC) is inconsistent.

I think one route towards finding alternatives to Bayesianism is to consider decision theories with Dutch book resistance and/or ex ante optimality, and think of what probabilities/beliefs go well with them.

I really appreciate this comment, because I must admit I was not even previously aware of FNC, and I think FNC+EDT solves my problem of completing the corresponding decision theory for my notion of beliefs.

I already was favorable to Halpern’s MWER as a decision rule, but MWER leaves the question, as well as (implicitly) the anthropic update question, open as free parameters. I think filling these in with FNC’s “simply add ” and EDT’s “simply add ” completes the picture in a way that might very well be satisfying to me.