Probability as Minimal Map

post by johnswentworth · 2019-09-01T19:19:56.696Z · LW · GW · 10 comments

Contents

  Probability-Computing Circuits
  The Data Processing Inequality
  Why Is This Interesting?
None
10 comments

What’s the difference between a map and the raw data used to generate that map?

Suppose, for example, that google sends a bunch of cars out driving around New York City, snapping photos every few feet, then uses the photos to reconstruct a streetmap. In an informational sense, what’s the difference between the giant database full of photos and the streetmap?

Obvious answer: the map throws away a huge amount of information which we don’t care about, at least for the map’s use-case.

Let’s try to formalize this intuition a little. We want the ability to run queries against the map - e.g. things like “How far apart are Times Square and the Met?” or questions about street network topology. Let’s call the whole class of queries we want to support $Q$. We also have some input data $X$ - e.g. the database full of images from the streets of NYC. The goal of the map-synthesizing process is to throw out as much information as possible from $X$, while still keeping any and all information relevant to queries in $Q$.

Natural next question: given the query class $Q$ and some data-generating process, can we characterize “optimal” map-making processes which maximize the amount of information “thrown out” (measured in an information-theoretic sense) while still keeping all information relevant to $Q$?

For the very simplest query classes, we can answer this question quite neatly.

Suppose that our query class contains only a single query $q$, and the query is a true/false question. For instance, maybe the only query we care about at all is $q$ = “Is the distance between Times Square and the Met greater than one mile?”, and we want to throw out as much information as possible without losing any info relevant to the query.

Claim: any solution to this problem is isomorphic to the probability $P\left[q|X\right]$. In other words, $P\left[q|X\right]$ is itself a minimal “lossless” map (where by “lossless” we mean it does not throw out any info from $X$ relevant to the query, not that it perfectly predicts $q$), and any other minimal “lossless” map is a reversible transformation of $P\left[q|X\right]$.

Let’s prove it.

We’ll formalize our claim in terms of mutual information $I$. We have two pieces:

1. $P\left[q|X\right]$ throws away no information relevant to $q$: $I(q;X)=I(q;P[q|X\left]\right)$
2. For any function $g\left(X\right)$, if $g$ throws away no information relevant to $q$, then $P\left[q|X\right]$ can be computed from $g\left(X\right)$: $I(q;X)=I(q;g(X\left)\right)$ implies $P\left[q|X\right]=f\left(g\right(X\left)\right)$ for some $f$.

One important note: our notation $P\left[q|X\right]$ is really shorthand for $P[q=True|X]$, so $P\left[q|X\right]$ is not a function of the “outcome” of $q$ - it’s only a function of $X$. Also note that the second condition implies that the entropy of $g\left(X\right)$ is at least as high as $P\left[q|X\right]$, so $P\left[q|X\right]$ is indeed minimal in terms of information content.

In the next two sections, we’ll separately prove our two pieces.

Probability-Computing Circuits

We want to show that $P\left[q|X\right]$ throws away no information relevant to $q$: $I(q;X)=I(q;P[q|X\left]\right)$.

We’ll start with a short side-quest to prove a lemma: $P\left[q|P\right[q|X]=p]=p$. Here’s an interpretation: suppose you work late trying to calculate the probability of $q$ based on some giant pile of data $X$. You finally compute the result: $P\left[q|X\right]=p$. You go to bed feeling victorious, but wake up to find that your computer has died and your giant pile of data is lost. However, you still remember the final result $p$ - even though you don’t know $X$, you do know that $P\left[q|X\right]=p$. Based on this information, what probability should you assign to $q$? Presumably the answer should be $p$.

We can directly prove this in a few lines:

$P\left[q|P\right[q|X]=p]=\left(P\right[P\left[q|X\right]=p\left]{)}^{-1}P\right[q,P\left[q|X\right]=p]=({\sum }_{x}I\left[P\right[q|X=x]=p]P[X=x]{)}^{-1}{\sum }_{x}I\left[P\right[q|X=x]=p]P[q|X=x]P[X=x]$

Note that the indicator function $I[.]$ in the main sum is zero whenever $P[q|X=x]$ is not $p$, so we can replace $P[q|X=x]$ with $p$ in that sum: $=\left({\sum }_{x}I\right[P[q|X=x]=p\left]P\right[X=x\left]{)}^{-1}{\sum }_{x}I\right[P[q|X=x]=p\left]pP\right[X=x]=p$

We can also write this in the more compact form $P\left[q|P\right[q|X\left]\right]=P\left[q|X\right]$, which we’ll use later.

To build a bit more intuition, let’s expand on this result a bit. Imagine a circuit (aka deterministic causal diagram or computational DAG) which takes in data $X$ and outputs $P\left[q|X\right]$. We’ll think about some arbitrary cross-section of that circuit - some set of internal nodes $\left\{g_i\right\}$ which cut the circuit in two, so that $g$ mediates the interaction between $X$ and $P\left[q|X\right]$. We can write this as $P\left[q|X\right]=f\left(g\right(X\left)\right)$ for some function $f$.

Claim: for any cross-section $g$, $P\left[q|g\right(X\left)\right]=P\left[q|X\right]$. Intuitively, we can imagine that we’re partway through calculating $P\left[q|X\right]$, we’ve calculated all the $g$’s but haven’t finished the full computation yet, when suddenly our computer dies and we lose all the original data $X$. As long as we still have the $g$’s around, we’re good - we just shrug and continue the calculation, since the $g$’s were all we needed to finish up anyway.

I won’t write out the proof for this one, but it works exactly like the previous proof.

Notice that our cross-section theorem has two interesting corner cases: all of $X$ is a cross-section, and $P\left[q|X\right]$ by itself is a cross-section. The former yields the trivial statement $P\left[q|X\right]=P\left[q|X\right]$, while the latter yields our lemma from earlier: $P\left[q|P\right[q|X]=p]=p$.

Armed with our lemma, let’s return to the main problem: show that $P\left[q|X\right]$ throws away no information relevant to $q$, formalized as $I(q;X)=I(q;P[q|X\left]\right)$.

We’ll start by applying an identity from information theory:

• $I(q,X)=H\left(q\right)-H\left(q|X\right)$
• $I(q,P[q|X\left]\right)=H\left(q\right)-H\left(q|P\right[q|X\left]\right)$

… where $H$ is the Shannon entropy. So to show that $I(q,X)=I(q,P[q|X\left]\right)$, we can show $H\left(q|X\right)=H\left(q|P\right[q|X\left]\right)$. Our lemma makes this trivial:

$H\left(q|P\right[q|X\left]\right)=-{\sum }_{q}P\left[q|P\right[q|X\left]\right]lnP\left[q|P\right[q|X\left]\right]=-{\sum }_{q}P\left[q|X\right]lnP\left[q|X\right]=H\left(q|X\right)$ … so $P\left[q|X\right]$ contains all the information in $X$ relevant to $Q$.

The Data Processing Inequality

Next, we’d like to show that $P\left[q|X\right]$ is a minimal representation of the information in $X$ relevant to $Q$. Formally, for any $g\left(X\right)$, if $g$ throws away no information relevant to $q$, then $P\left[q|X\right]$ is a function of $g\left(X\right)$: $I(q;X)=I(q;g(X\left)\right)$ implies $P\left[q|X\right]=f\left(g\right(X\left)\right)$ for some $f$.

In particular, we’ll show that $P\left[q|g\right(X\left)\right]=P\left[q|X\right]$, so we can choose $f(g\ast )=P\left[q|g\right(X)=g\ast ]$. Intuitively, this says that if $g\left(X\right)$ throws out no information from $X$ relevant to $q$, then it yields the same probability for $q$.

To prove this, we’ll use a theorem from information theory called the data processing inequality (DPI). Intuitively, the DPI says that if we start with the data $X$, we cannot gain any new information about $q$ just by processing $X$. Formally, for any function $g$:

$I(q;X)\ge I(q;g(X\left)\right)$

… with equality iff $q$ and $X$ are independent conditional on $g\left(X\right)$ (so that $X$ tells us nothing else about $q$ once we know $g\left(X\right)$). The proof and a bit more discussion can be found in Cover & Thomas’ textbook on page 34.

We’re interested in the equality case $I(q;X)=I(q;g(X\left)\right)$, so the DPI tells us that $q$ and $X$ are independent conditioned on $g\left(X\right)$:

$P[q,X|g(X\left)\right]=P\left[q|g\right(X\left)\right]P\left[X|g\right(X\left)\right]$

But we can always just expand via the chain rule instead:

$P[q,X|g(X\left)\right]=P[q|X,g(X\left)\right]P\left[X|g\right(X\left)\right]=P\left[q|X\right]P\left[X|g\right(X\left)\right]$

Equate these two expressions for $P[q,X|g(X\left)\right]$, and we find

$P\left[q|g\right(X\left)\right]=P\left[q|X\right]$

… which is what we wanted.

Why Is This Interesting?

We’ve shown that the probability $P\left[q|X\right]$ summarizes all the information in $X$ relevant to $q$, and throws out as much irrelevant information as possible. Why does this matter?

First, hopefully this provides some intuition for interpreting a probability $P\left[q|X\right]$ as a representation of the information in $X$ relevant to $q$. In short: probabilities directly represent information. This interpretation makes sense even in the absence of “agents” with “beliefs”, or “independent experiments” repeated infinitely many times. It directly talks about maps matching territories, and the role probability plays, without invoking any of the machinery of frequentist or subjectivist interpretations. That means we can potentially apply it in a broader variety of situations - we can talk about simple mechanical processes which produce “maps” of the world, and the probabilistic calculations embedded in those processes.

Second, this is a natural first step in characterizing [LW · GW] map-making processes [LW · GW]. The data processing inequality also suggests a natural next step: sufficient statistics, which serve as minimal “lossless” maps when our data are independent samples from a distribution, and our queries can ask anything at all about the parameters of the distribution. From there, we could further generalize to approximate sufficient statistics - maps which throw out a small amount of information relevant to the queries, in cases where there is no “lossless” map smaller than $X$.

That said, this still only talks about half of the full map-making process: the data-processing half. There’s still the data-collection half to address - the process which generates $X$ in the first place, and somehow ties it to the territory. And of course, when map-making processes are embedded in the real world [LW · GW], there might not be a clean separation between data-collection and data-processing, so we need to deal with that somehow.

Third, the interpretation of probabilities as a minimal map - or a representation of information - suggests possible avenues to relax traditional probability to deal with things which are time-like separated from us [LW · GW], e.g. for handling self-reference and advanced decision-theoretic problems [? · GW]. In particular, it suggests strategically throwing away information to deal with self-referential tomfoolery - but continuing to use probabilities to represent the reduced information remaining.

10 comments

Comments sorted by top scores.