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.
Thank you for your generous recognition and changes to the post.
To connect some dots, recall that is the condition under which certain PDGs (those with ) are equivalent to factor graphs. This is the boundary of the region , or equivalently where inference isknown to be fixed-treewidth tractable (on par with factor graphs and BNs, but the precise complexity is unknown with a gap of vs for PDGs of variables), and is solvable precisely because it can be compiled to a convex problem. In the original PDG paper, Joe insisted that we quarantine discussion of , so we assumed (in the definition of a PDG) that outside of §4.3; hence claim in §3.3. I apologize for the confusion that can easily result.
I sympathize with your suspicion of negative belief, and I advise anyone who isn’t 100% sure of their footing to assume and move on. I see other reasons to call it an anti-pattern; a negative KL term on its own creates problems, for example—perhaps because it is not lower semi-continuous (on its own). Similarly, while we have the training wheels on, it’s best to stick to confidences when we aggregate beliefs as . But notice that negative confidence does not necessarily lead to loss of convexity (or ) overall. In Fig 1 of “Loss as the Inconsistency of a PDG”, for example, the divergence construction has confidence on one arc and on the another, yet the problem remains within a broader convex region where the PDG inconsistency can be solved in closed form (although it lies outside the the “canonical” convex region ). The minimum value is negative in this case, but the semantics of this PDG are bounded below, so we can ensure with additional context. Negative confidences also play an intuitive role in modeling generative adversarial networks (GANs), in the LIR framework. Most importantly, the structural weights themselves can be regarded as negative confidences relative to the base measure! (optional: reflect again on the condition .) To summarize: negative confidences can be useful, don’t necessarily result in negative overall belief in context. Here is a general interpretation of possibly-negative beliefs : view them as “pseudo”-beliefs that are only valid in contexts in which they result in a proper posterior belief .
Finally: I like your answer to my challenge :) I think there might be a PDG angle, but I haven’t fully worked it out yet. Here are my thoughts so far:
To model “bob’s belief is probably wrong”, I think there are a lot of different different modeling choices we can make; my gut reaction with a PDG is just to assign to , which can work provided there’s enough context to stabilize—but I agree this can be problematic in isolation. Your definition of is definitely better-behaved on its own, but the distance metric and radius are not present in the gloss “bob’s belief is probably wrong”, so in my view this particular functional requires a more complex story to motivate. (I was hoping to get you to tell such a story so I could try to follow it using the PDG formalism.) Still, I am inclined to agree that your functional is worth expressing, and I also agree that seems impossible to capture the underlying exclusion exclusion ball with the semantics of a fixed finite PDG. That said, I strongly suspect it is expressible via a minimax game over PDGs, and would not be surprised if it can be expressed via local inconsistency resolution (LIR) on a PDG with two foci (which I’m tempted to call a “bi-focal” PDG) using negative confidence, like how we model GANs with PDGs. Another relevant fact: the (-regularized entropic) optimal transport distance is itself the (-)inconsistency of a PDG that has high-confidence marginal beliefs and together with a soft “cost” implemented by the belief . I will respond again if I finish working out the details in a way that yields deeper insight.
I’d like to add another point here regarding burden. The fact that davidad didn’t make this point is surprising to me, so I may be misunderstanding something here—please let me know if so!
I want to push back on your point that “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”—to do so I will draw an analogy. Consider a problem which asks the user for a function satisfying some properties on some space (e.g. a holomorphic function on the upper half-plane): in my view, if I were to instead ask the user to give me a function on just some subspace (e.g. a holomorphic function on the upper half-disk), this is less burden, not more. But of course the latter function space is larger[1] than the original function space . By increasing the freedom of choice, the burden is decreased, not increased. I view this as analogous to the case of belief functionals vs PDGs; asking for a belief functional is less burden than asking for a PDG, since any PDG yields a belief functional and thus the burden of a expressing a PDG is an upper bound on the burden of expressing a belief functional :)
This of course does not discount the utility of PDGs. As you note, their clearly interpretable presentation makes them a very natural[2] way to construct belief functionals, and since they are a more structured type there are probably theorems that will be easier to prove about PDGs than about belief functionals (especially since there should be things that are provable about PDGs but are not true or even expressible for general belief functionals). Furthermore, since PDGs carry more structure than belief functionals, it is more clear how to describe/understand the dynamics of the former (such as LIR) as opposed to the latter (is there a natural way to do something like LIR in this context?). But it does seem to me that belief functionals are in some sense more natural / more fundamental than PDGs (on account of being a broader/less-structured/less-artificial type), so I hope that the two can inform each other: PDGs are fertile ground for interesting belief dynamics, and the theoretical constraints of working at the belief functional level might help prune those dynamics down to the most essential ones!
More freedom does not necessarily mean less modeling burden (and certainly not less burden of choice). Making 300 decisions in sequence is a greater burden than making the first 10 and having the others automatically handled by context. Low-level programming languages are burdensome despite (or perhaps because of) the freedom that they expose to the modeler. And universal constructions are appealing in part because they allow you to specify important information arguably without making any (unjustified) choices at all (i.e., very little modeling burden)! As davidad points out, this burden is a matter of syntax, i.e., the interface for constructing valid objects. Do the constraints of that interface provide helpful, simplifying guidance? Or does working within the constraints impose (computational) difficulties on the modeler? My experience is that the structure of PDGs does both: it makes specifying “natural” beliefs easier and “unnatural” ones more difficult.
My understanding is that @davidad wants to sidestep syntax and focus on delivering an IR (intermediate representation) for beliefs: a simple common compilation target that retains some useful structure (in this case, additive combination). This effectively deflects my point about the modeler’s burden, since his aim is instead to reduce the burden of a compiler that targets the IR. This allows him to endorse PDGs as one particular (nice) language for articulating inconsistency functionals, casting PDG semantics as the way to compile them. This makes a lot of sense to me, and the mathematical simplicity is definitely an appealing advantage over PDGs for this purpose.
However, I’m not 100% convinced that this is a good idea. The class of PDGs is itself already a useful IR, since it unifies so much, and it intentionally occupies a different point in the design space. The structure can indeed create some burden for certain modelers (e.g., for one who wants to arrive at a certain preconceived belief functional, but now, annoyingly, has to figure out how to write it down in terms of local conditional probabilities and confidences), but this exercise also has nice side-effects (e.g., gives you justification for your loss function), often yielding significant interpretability benefits. As you point out, the map from PDGs to belief functionals is non-injective; in my view, that is because the mapping loses something that is worth tracking in a belief state. There’s technically a difference between specifying P(X) and P(Y|X) vs P(Y) and P(X|Y) (all with the same confidence), even though we all agree they are semantically equivalent. Making this distinction (and others in the same class) can be relevant for revising your beliefs (e.g., if you determine that your mechanism for forming conditional beliefs had a flaw). My concern is that direct specification of an inconsistency functional could short-circuit the modeling process that PDGs are designed to elicit.
FWIW, it’s not really clear to me how to map the IR/higher-language analogy into this situation, but when I try to it feels more like belief functionals are the higher-level language and PDGs are a particular lower-level implementation thereof (and from this perspective it doubly makes sense why the map isn’t injective, since there are a wide variety of ways to compile a given higher-level program into a given lower-level representation); I don’t really see how it could be the case that PDGs are less burdensome than belief functionals given that if you want to specify your belief functional with a PDG, you’re always free to do so, and given that you’re also free to do so with simpler techniques (e.g. all of the items under ”...to express beliefs” in the original post, which are IMO much simpler to express with belief functionals that aren’t PDGs).
Regardless, I do find your argument at the end (“in my view [...] had a flaw)”) quite compelling; I think we’re on the same page about belief-revision being an extremely important aspect of belief-modeling, and if there’s in fact not a clear way to do this sort of credit assignment for belief functionals then it does make them significantly less attractive than PDGs for understanding belief dynamics.
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
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
Thank you for your generous recognition and changes to the post.
To connect some dots, recall that§ §
I sympathize with your suspicion of negative belief, and I advise anyone who isn’t 100% sure of their footing to assume
Finally: I like your answer to my challenge :)
I think there might be a PDG angle, but I haven’t fully worked it out yet. Here are my thoughts so far:
To model “bob’s belief is probably wrong”, I think there are a lot of different different modeling choices we can make; my gut reaction with a PDG is just to assign
I’d like to add another point here regarding burden. The fact that davidad didn’t make this point is surprising to me, so I may be misunderstanding something here—please let me know if so!
I want to push back on your point that “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”—to do so I will draw an analogy. Consider a problem which asks the user for a function satisfying some properties on some space
This of course does not discount the utility of PDGs. As you note, their clearly interpretable presentation makes them a very natural[2] way to construct belief functionals, and since they are a more structured type there are probably theorems that will be easier to prove about PDGs than about belief functionals (especially since there should be things that are provable about PDGs but are not true or even expressible for general belief functionals). Furthermore, since PDGs carry more structure than belief functionals, it is more clear how to describe/understand the dynamics of the former (such as LIR) as opposed to the latter (is there a natural way to do something like LIR in this context?). But it does seem to me that belief functionals are in some sense more natural / more fundamental than PDGs (on account of being a broader/less-structured/less-artificial type), so I hope that the two can inform each other: PDGs are fertile ground for interesting belief dynamics, and the theoretical constraints of working at the belief functional level might help prune those dynamics down to the most essential ones!
In the sense that all functions on
I’m not sure about “the natural way” though, especially given that it looks like the map from PDGs to belief functionals is non-injective!
More freedom does not necessarily mean less modeling burden (and certainly not less burden of choice). Making 300 decisions in sequence is a greater burden than making the first 10 and having the others automatically handled by context. Low-level programming languages are burdensome despite (or perhaps because of) the freedom that they expose to the modeler. And universal constructions are appealing in part because they allow you to specify important information arguably without making any (unjustified) choices at all (i.e., very little modeling burden)! As davidad points out, this burden is a matter of syntax, i.e., the interface for constructing valid objects. Do the constraints of that interface provide helpful, simplifying guidance? Or does working within the constraints impose (computational) difficulties on the modeler? My experience is that the structure of PDGs does both: it makes specifying “natural” beliefs easier and “unnatural” ones more difficult.
My understanding is that @davidad wants to sidestep syntax and focus on delivering an IR (intermediate representation) for beliefs: a simple common compilation target that retains some useful structure (in this case, additive combination). This effectively deflects my point about the modeler’s burden, since his aim is instead to reduce the burden of a compiler that targets the IR. This allows him to endorse PDGs as one particular (nice) language for articulating inconsistency functionals, casting PDG semantics as the way to compile them. This makes a lot of sense to me, and the mathematical simplicity is definitely an appealing advantage over PDGs for this purpose.
However, I’m not 100% convinced that this is a good idea. The class of PDGs is itself already a useful IR, since it unifies so much, and it intentionally occupies a different point in the design space. The structure can indeed create some burden for certain modelers (e.g., for one who wants to arrive at a certain preconceived belief functional, but now, annoyingly, has to figure out how to write it down in terms of local conditional probabilities and confidences), but this exercise also has nice side-effects (e.g., gives you justification for your loss function), often yielding significant interpretability benefits. As you point out, the map from PDGs to belief functionals is non-injective; in my view, that is because the mapping loses something that is worth tracking in a belief state. There’s technically a difference between specifying P(X) and P(Y|X) vs P(Y) and P(X|Y) (all with the same confidence), even though we all agree they are semantically equivalent. Making this distinction (and others in the same class) can be relevant for revising your beliefs (e.g., if you determine that your mechanism for forming conditional beliefs had a flaw). My concern is that direct specification of an inconsistency functional could short-circuit the modeling process that PDGs are designed to elicit.
FWIW, it’s not really clear to me how to map the IR/higher-language analogy into this situation, but when I try to it feels more like belief functionals are the higher-level language and PDGs are a particular lower-level implementation thereof (and from this perspective it doubly makes sense why the map isn’t injective, since there are a wide variety of ways to compile a given higher-level program into a given lower-level representation); I don’t really see how it could be the case that PDGs are less burdensome than belief functionals given that if you want to specify your belief functional with a PDG, you’re always free to do so, and given that you’re also free to do so with simpler techniques (e.g. all of the items under ”...to express beliefs” in the original post, which are IMO much simpler to express with belief functionals that aren’t PDGs).
Regardless, I do find your argument at the end (“in my view [...] had a flaw)”) quite compelling; I think we’re on the same page about belief-revision being an extremely important aspect of belief-modeling, and if there’s in fact not a clear way to do this sort of credit assignment for belief functionals then it does make them significantly less attractive than PDGs for understanding belief dynamics.