Embedded Naive Bayes

[johnswentworth]

Suppose we have a bunch of earthquake sensors spread over an area. They are not perfectly reliable (in terms of either false positives or false negatives), but some are more reliable than others. How can we aggregate the sensor data to detect earthquakes?

A “naive” seismologist without any statistics background might try assigning different numerical scores to each sensor, roughly indicating how reliable their positive and negative results are, just based on the seismologist’s intuition. Sensor i gets a score $s_i^{+}$ when it’s going off, and $s_i^{-}$ when it’s not. Then, the seismologist can add up the $s_i^{+}$ scores for all sensors going off at a given time, plus the $s_i^{-}$ scores for sensors not going off, to get an aggregate “earthquake score”. Assuming the seismologist has decent intuitions for the sensors, this will probably work just fine.

It turns out that this procedure is equivalent to a Naive Bayes model.

Naive Bayes is a causal model in which there is some parameter $\theta$ in the environment which we want to know about—i.e. whether or not there’s an earthquake happening. We can’t observe $\theta$ directly, but we can measure it indirectly via some data $\left\{x_i\right\}$ - i.e. outputs from the earthquake sensors. The measurements may not be perfectly accurate, but their failures are at least independent—one sensor isn’t any more or less likely to be wrong when another sensor is wrong.

We can represent this picture with a causal diagram:

From the diagram, we can read off the model’s equation: $P[\theta ,\{x_i\left\}\right]=P\left[\theta \right]{\prod }_{i}P\left[x_i|\theta \right]$. We’re interested mainly in the posterior probability $P\left[\theta |\right\{x_i\left\}\right]=\frac{1}{Z}P\left[\theta \right]{\prod }_{i}P\left[x_i|\theta \right]$ or, in log odds form,

$L\left[\theta |\right\{x_i\left\}\right]=ln\frac{P\left[\theta \right]}{P[\sim \theta ]}+{\sum }_{i}ln\frac{P\left[x_i|\theta \right]}{P[x_i|\sim \theta ]}$

Stare at that equation, and it’s not hard to see how the seismologist’s procedure turns into a Naive Bayes model: the seismologist’s intuitive scores for each sensor correspond to the “evidence” from the sensor $ln\frac{P\left[x_i|\theta \right]}{P[x_i|\sim \theta ]}$. The “earthquake score” then corresponds to the posterior log odds of an earthquake. The seismologist has unwittingly adopted a statistical model. Note that this is still true regardless of whether the scores used are well-calibrated or whether the assumptions of the model hold—the seismologist is implicitly using this model, and whether the model is correct is an entirely separate question.

The Embedded Naive Bayes Equation

Let’s formalize this a bit.

We have some system which takes in data $x$, computes some stuff, and spits out some $f\left(x\right)$. We want to know whether a Naive Bayes model is embedded in $f\left(x\right)$. Conceptually, we imagine that $f\left(x\right)$ parameterizes a probability distribution over some unobserved parameter $\theta$ - we’ll write $P[\theta ;f(x\left)\right]$, where the “;” is read as “parameterized by”. For instance, we could imagine a normal distribution over $\theta$, in which case $f\left(x\right)$ might be the mean and variance (or any encoding thereof) computed from our input data. In our earthquake example, $\theta$ is a binary variable, so $f\left(x\right)$ is just some encoding of the probability that $\theta =True$.

Now let’s write the actual equation defining an embedded Naive Bayes model. We assert that $P[\theta ;f(x\left)\right]$ is the same as $P\left[\theta |x\right]$ under the model, i.e.

$P[\theta ;f(x\left)\right]=P\left[\theta |x\right]=\frac{1}{Z}P\left[\theta \right]{\prod }_{i}P\left[x_i|\theta \right]$

We can transform to log odds form to get rid of the Z:

$L[\theta ;f(x\left)\right]=ln\frac{P\left[\theta \right]}{P[\sim \theta ]}+{\sum }_{i}ln\frac{P\left[x_i|\theta \right]}{P[x_i|\sim \theta ]}$

Let’s pause for a moment and go through that equation. We know the function $f\left(x\right)$, and we want the equation to hold for all values of $x$. $\theta$ is some hypothetical thing out in the environment—we don’t know what it corresponds to, we just hypothesize that the system is modelling something it can’t directly observe. As with $x$, we want the equation to hold for all values of $\theta$. The unknowns in the equation are the probability functions $P[\theta ;f(x\left)\right]$, $P\left[\theta \right]$ and $P\left[x_i|\theta \right]$. To make it clear what’s going on, let’s remove the probability notation for a moment, and just use functions $G$ and $\left\{g_i\right\}$, with $\theta$ written as a subscript:

$\forall \theta ,x:G_{\theta }\left(f\right(x\left)\right)=c_{\theta }+{\sum }_i{g}_{\theta i}\left(x_i\right)$

This is a functional equation: for each value of $\theta$, we want to find functions $G$, $\left\{g_i\right\}$, and a constant $c$ such that the equation holds for all possible $x$ values. The solutions $G$ and $\left\{g_i\right\}$ can then be decoded to give our probability functions $P[\theta ;f(x\left)\right]$ and $P\left[x_i|\theta \right]$, while $c$ can be decoded to give our prior $P\left[\theta \right]$. Each possible $\theta$-value corresponds to a different set of solutions $G_{\theta }$, $\left\{g_{\theta i}\right\}$, $c_{\theta }$.

This particular functional equation is a variant of Pexider’s equation; you can read all about it in Aczel’s Functional Equations and Their Applications, chapter 3. For our purposes, the most important point is: depending on the function $f$, the equation may or may not have a solution. In other words, there is a meaningful sense in which some functions $f\left(x\right)$ do embed a Naive Bayes model, and others do not. Our seismologist’s procedure does embed a Naive Bayes model: let $G$ be the identity function, $c$ be zero, and $g_i\left(x_i\right)=s_i^{x_i}$, and we have a solution to the embedding equation with $f\left(x\right)$ given by our seismologist’s add-all-the-scores calculation (although this is not the only solution). On the other hand, a procedure computing $f\left(x\right)=x_1^{x_2^{x_3}}$ for real-valued inputs $x_1$, $x_2$, $x_3$ would not embed a Naive Bayes model: with this $f\left(x\right)$, the embedding equation would not have any solutions.

[Vanessa Kosoy]

This seems interesting, but I think there are some assumptions that have been left out? What prevents us from taking $G$ and $g$ to be constants, which would give solutions for any $f$?

[johnswentworth]

I am indeed leaving out some assumptions, mainly because I am not yet convinced of which assumptions are “right”. The simplest assumption—used by Aczel—is that $G$ and $g$ are monotonic. But that’s usually chosen more for mathematical convenience than for any principled reason, as far as I can tell. We certainly want some assumptions which rule out the trivial solution, but I’m not sure what they should be.

[Rohin Shah]

What do you mean by embedded here? It seems you are asking the question “does a particular input-output behavior /​ computation correspond to some Naive Bayes model”, which is not what I would intuitively think of as “embedded Naive Bayes”.

[johnswentworth]

Here’s the use case I have in mind. We have some neural network or biological cell or something performing computation. It’s been optimized via gradient descent/​evolution, and we have some outside-view arguments saying that optimal reasoning should approximate Bayesian inference. We also know that the “true” behavior of the environment is causal—so optimal reasoning for our system should approximate Bayesian reasoning on some causal model of the environment.

The problem, then, is to go check whether the system actually is approximating Bayesian reasoning over some causal model, and what that causal model is. In other words, we want to check whether the system has a particular causal model (e.g. a Naive Bayes model) of its input data embedded within it.

What do you imagine “embedded” to mean?

[Rohin Shah]

I usually imagine the problems of embedded agency (at least when I’m reading LW/​AF), where the central issue is that the agent is a part of its environment (in contrast to the Cartesian model, where there is a clear, bright line dividing the agent and the environment). Afaict, “embedded Naive Bayes” is something that makes sense in a Cartesian model, which I wasn’t expecting.

It’s not that big a deal, but if you want to avoid that confusion, you might want to change the word “embedded”. I kind of want to say “The Intentional Stance towards Naive Bayes”, but that’s not right either.

[johnswentworth]

Ok, that’s what I was figuring. My general position is that the problems of agents embedded in their environment reduce to problems of abstraction, i.e. world-models embedded in computations which do not themselves obviously resemble world-models. At some point I’ll probably write that up in more detail, although the argument remains informal for now.

The immediately important point is that, while the OP makes sense in a Cartesian model, it also makes sense without a Cartesian model. We can just have some big computation, and pick a little chunk of it at random, and say “does this part here embed a Naive Bayes model?” In other words, it’s the sort of thing you could use to detect agenty subsystems, without having a Cartesian boundary drawn in advance.