Tractability in univariate Bayesian inference
Claim of Luca: Bayes' formula "gives you the only rational method to update belief on the world after you experience a sensation"
Goal: get some knowledge of a state of the world that is not directly accessible.
What's implicit in the typical Bayes' formula is that it relies on a model (that is usually not written out).
The likelihood $p(measure|world)$ relies on some assumption about how the world affects the measure.
This is why $p(measurement)$ is also called the model evidence, because it marginalizes out all model parameters (the 'world states' for which the model makes an assumption).
$$p(measurements) = sum_{world\ states} p(measurements|world)p(world)$$
In most models, this model evidence is an intractable problem. For M N-valued variables, the state space of a model is $N^M$.
"Unfortunately, the number of possible states of almost all machine learning models you will use in your career have enough states to make the number of atoms in the universe into an irrelevant rounding error." (1)
Usually the size of the state space is the cause of intractability. But in practice there are models with an extremely large state space that are still not intractable because they have a structure that allows tractable inference.
Exact Univariate Bayesian Inference
Today we'll discuss the relatively simple univariate Bayesian models. Sometimes these models are tractable even though they are not solved in closed form.
Analytically tractable: we can express the posterior "as a finite algebraic combination of elementary functions such as powers, exponential, trigonometric functions" (2) that is then said to be in closed form.
A subset of tractable models can be solved in closed form.
As a rule of thumb, e.g. likelihoods with integrals or infinite sums will not have a closed form solution. But why is an exponential okay (e.g. using Gaussians)?
Exponential function or a sinusoid is also very complicated in a way, but it's considered elementary (which is a cultural thing as well) so when we are able to get an analytical solution reducing to these type of functions, we are satisfied and say to have a closed form solution.
Discrete univariate inference
In discrete problems the prior is a vector of probabilities over M discrete states:
$$p_{prior} = ( p(x=1), ..., p(x=M) )$$
Similarly, likelihood:
$$l = ( p(D|x=1), ..., p(D|x=M) )$$
The model evidence is a simple sum of entry-wise products between these vectors, i.e. a dot product:
$$p(D) = \sum_m p(D|x=m)p(x=m) = \mathbf{l} \dot p_{prior}$$
This means that the posterior can be easily written as the pairwise product of likelihood and prior divided by their dot product:
$$p_{post} = \frac{ l \odot p_{prior} }{ l \cdot p_{prior} }$$
When M is small enough, we have tractable posterior inference!
Concentrated probabilities
But even when M is large, we may still have tractability if probabilities are concentrated in a dense region.
For example, sometimes only a fraction of states has a likelihood or prior that is non-zero, which means that the intractable sum will be reduced to a sum over a limited set.
$$p(D) = \sum_{m \in A} p(D|x=m)p(x=m) + \sum_{m \notin A} 0$$
This computation is tractable when the intersection of the likelihood and prior's non-zero entries is tractably small.
But this is not in itself enough for tractability! Why? Well, because we have to find the concentration probability set and this is itself an intractable problem over an exponential search space! This means that from any world state there should be enough information to point towards the concentration probability set, e.g. to compute a gradient towards a global optimum where MAP is maximized. This is extremely rare.
Example: Medical testing
- Test with false positive and false negative rate of 1%
- Quite low prior of 0.001 on being infected on the general population.
- Given positive test, what's the chance the patient was infected?
- Due to the prior, the posterior probability is still quite low ($\approx 0.1$) despite testing positive and having reliable test
But... using this prior assumes a randomized test (i.e. on a random individual from the general population). But in clinical practice, a patient is usually only tested for a rare disease if they have very specific conditions associated with this rare condition (so not someone with just a headache). So the relevant prior here would be much much higher than the prior on the general population, i.e. we need to use P(I|symptoms).
Note that this new prior has the same shape as the old posterior!
Information theory
How much information is encoded in an event coming from a stochastic source? How can information be processed through a noisy channel?
Basic assumption of probability theory: the information of an event is determined by its rarity.
$$i_m = log 1/p_m = - log p_m$$
This implies that more information is conveyed by rare events than common events. This also shows that by definition information is always positive as $p$ cannot be larger than 1.
Weird consequence: even though ".asdf70987asdf" is meaningless, it contains more information than "Good morning, Joe" (let's assume the strings are equal length; I didn't bother) according to this definition of information.
This paradox can be explained by realizing that a information is always defined against the background of a set of meaningfully distinguishable events. We human do not distinguish different random strings and will typically see these all as a single event "random string", which is actually very very common if you have a stochastic source randomly producing strings. So all is well in the end: random strings indeed do not convey much information.
Information is a property of an event coming from a stochastic source. Entropy instead is a property of a source which can for example be represented as a vector of probabilities, i.e. a (discrete) probability distribution.
More entropy means we can encode more messages in a probability distribution.
Entropy is the average information content i.e. the expected information over all possible messages $m$ under probability distribution $p$:
$$\mathbb{H} [ p ] = \mathbb{E}_p [i_m]$$ $$= - \sum_m p_m log p_m$$ $$p \cdot log p$$
Where we define $0\ log\ 0 = 0$.
Imagine a delta distribution $\delta_k$ with $p_i=0$ for all states except when $i=k$. Then for all states we either have $0\ log\ 0 = 0$ or $1\ log\ 1 = 0$.
So entropy shows that there is no uncertainty in this distribution - which makes sense because it's deterministic - and that as a result we cannot convey any information with it! I.e. we cannot produce different messages; we can only send a single message and because of this the expected information content of a message is 0. So entropy is minimized with a deterministic distribution.
The uniform distribution instead maximizes the entropy. For M states, each state has probability $\frac{1}{M}$. So the entropy is:
$$\mathbb{H}[uniform] = - \sum_m \frac{1}{M} log \frac{1}{M} = log M$$
What this tells us is that if we have a binary system with M discernible states (so we use log with base 2), we can encode a maximum of $log_2 M$ bits of information.
See entropy.
Jensen inequality
- Def. of convex function
- If you interpret $a$ as probability $p$ of $x_1$, then the Jensen equality states that the function over the weighted average (=expectation) of $x_1$ and $x_2$ is smaller or equal to the expectation over the function
- So Jensen inequality is a generalization convex functions with probabilities
Exercise: Proof Jensen Inequality; apparently easy but not sure.
You can use Jensen inequality to show that the entropy of the uniform distribution is higher than the entropy of any other distribution.
Use A >= B = C >= D -> A >= D
Eq. 34: Is entropy of p bigger or equal to cross-entropy of p with q. Eq. 35-37 -> it is always higher.
Dynamic of sequential inference
Entropy after a Bayesian update is lower.
This is funny, because this is kind of the inverse of thermodynamics where we expect the entropy to always increase.
This is because we assume the environment is constant. If instead we environment is dynamic and we are not constantly observing, the entropy will increase in the Bayesian framework as well.
With infinite updates, you'll approximate a delta function.
In reality, we do not have perfect observations, so this will not happen.
General univariate continuous inference
In the integral of model evidence P(D) we usually do not write range [a,b] i.e. the support of the distribution.
- Analytical solution
- Inference quantization
If a prior doesn't change to fast, we can also approximate it reasonably well by constant values for bins.
See 1.4.3. three sources of intractability.
But these sources are quite rare in real world univariate inference problems. E.g. we usually don't have many modes in the posterior, In the continuous univariate case, we can often quite precisely approximate the posterior by simple inference quantization.
Difficult case where quantization does not work: integration of sin(1/x), because the frequency here is very high and becomes higher over time, so we cannot pick a bin size that's small enough.
But in practice this is not likely to happen. Usually the likelihood is actually smooth.
Information theory for continuous variable
- Quantize the probability distribution
- Now we can evaluate the entropy
- Take the limit of the bin size to 0, hope that this results in a finite limit that we can interpret as the continuous entropy.
We end up with a differential entropy, but we also get a term that goes to infinity.
So entropy is actually infinite for continuous distributions! For any sample from a continuous distribution, we get a number with infinitely many decimals for which we need infinite many bits to encode it exactly; so it has "infinite" information.
But the problematic part is only dependent on the bin size and not on the distribution. Whereas the term that depends everything that depends on the distribution converges on a nice integral.
We can end up with this integral by substracting positive infinity (which acts basically as a constant shift). Strictly speaking this messes a bit with our definition of information and becomes hand-waivy.
Also notice that the differential entropy may be negative!
H = DH + S
If you take the variance of a Gaussian to zero, at the limit you end up with a deterministic distribution which as zero entropy.
This means that we have 0 = DH + infinity, meaning that we can deduce that the differential entropy should be minus infinity!
Repeat with KL-divergence
When we repeat the same procedure we end up with a super clean integral. So KL-divergence for continuous distributions can be interpreted exactly the same as for discrete variables!
Formalization Conjugate priors
Why do conjugate priors lead to tractability?
The posterior will have the same form as the prior but with updated parameters. This means that Bayesian inference can be recasted in terms of a simple parameter update rule.
This also means that if the likelihood has a closed form expression, we'll also have a closed form expression for the posterior.
Conjugacy and data compression
In an iterative Bayesian updating schema, the posterior depends on all previous observations. But if we have conjugacy, the posterior of the i-th iteration can be summarized only through the parameters without any loss of information.
General technique, example of Beta-Binomial inference
Multinomial likelihood: p of k heads given n tosses of the coin.
B(a,b) is in fact an integral, which is very weird because normally we avoid those integrals as closed form without bothering to further work out this integral! But this integral is considered so useful we define it as B(a,b) and accept this solution as "closed form". So this is clearly a mathematical "cultural" thing.
General Technique:
- We want to find the posterior up to any proportionality not dependent on our stochastic variable x
- Model evidence does not depend on x, so for now we do not care about it; it's going to be some constant
- In this case: that our posterior is proportional with some constant to a non-normalized beta distribution
- But we already now how to normalize the result! Namely by the beta distribution with the updated parameters!
- We know this because the result after multiplying with the prior will have the same form as likelihood
- So we don't have to bother solving the integrals to get to the posterior in the inference procedure!
In assignment two we are asked to compare to the "real" model evidence. We can find this by doing likelihood x prior and then deducing with above strategy what the normalizing constant would be (which is the model evidence).
What we do in practice is compute the posterior via the "parameter update". Once we have the posterior, we can compute the model evidence by:
$P(D) = P(D|X)P(X) / P(X|D)$
Handy link? https://www.cs.ubc.ca/~murphyk/Papers/bayesGauss.pdf
Gaussian inference of the mean
n independent datapoints, modeled each by a univariate Gaussian likelihood with mean as our latent x. Then we have a Gaussian prior over x.
From eq. 85: Use the same strategy as before.
Eq. 89 Collect expression such that we have x seperately. Parts in brackets are called the natural parameterization, which is an alternative parameterization than mean and sigma.
Eq. 90-91: Completing the square -> rewrite the natural parameterization in terms of the familiar shape with mean and sigma.
The new form is really easy to interpret! The new mean is a trade-off between the sample average and prior contribution! (with "trade-off parameter" lambda determined by prior and likelihood variance and the amount of datapoints N)
Generalization to linear observation model
Problem: normally you measure the latent variable you care about. So we do not have latent z ( that goes into the Gaussian) directly, but instead have a measure that sometimes has a linear relation with that latent.
Mean of outcome of measuring device is function of the latent. (So we replace mean with (z=ax+b)).
We can incorporate this in the prior as well by shifting the mean and variance.
So idea is: map this problem to the simple Gaussian inference update we did before by shifting, then compute the posterior, and shift back again.
Non-linear observation model
Often the relation between measure and latent is not linear, but in this case we cannot apply above trick without losing conjugacy!
Extra: General theory of Bayesian conjugacy and exponential family
Only for likelihoods from the exponential family can we find conjugate priors. Posterior expressions are easy to find when we reduce the likelihood to the natural parameterization.
$$p(y| \eta ) = exp{ -\eta^T \Phi(y) + F(\eta)}$$
with $\eta$ natural parameters, $\Phi(y)$ a vector of sufficient statistics, and $F(\eta)$ free energy.
$$F(\eta) = -log \int exp{ -\eta^T \Phi(y)} dy$$
The joint distribution of this expression only depends on the average of the sufficient statistics.
Didn't continue notes. Mostly exercises to do and examples to follow here.