Distances, Divergences, Dirichlet distributions

by benmoran

Probability distributions and distances

There’s an interesting correspondence between unimodal p.d.f.’s on a metric space (like the reals $\mathbb{R}^{N}$ ), and distance functions. I will dig through this for amusement below, with some R code to generate the pictures.

Squared Euclidean distance and Gaussians

For example, in one dimension the normal p.d.f. is

$f(x;\mu,\sigma^2) = \frac{1}{\sigma\sqrt{2\pi}} e^{-\frac{1}{2}\left(\frac{x-\mu}{\sigma}\right)^2 }$

so the log likelihood for a single $x$ and fixed $\sigma$ is proportional to the squared distance from the mean: $\log\mathcal{L}(\mu) = \frac{(x-\mu)^{2}}{2\sigma^{2}}$ . Here’s the log likelihood for unit variance with $\mu=\frac{1}{2}$ :

mu <- 0.5;
par(mfrow=c(2,1));
curve(dnorm(x, mean=mu, sd=1, log=T),-4,5,xlab="x",ylab=expression(log(phi*("x"))));
abline(v=mu);
curve(dnorm(x, mean=mu, sd=1, log=F),-4,5,xlab="x",ylab=expression(phi*("x")));
abline(v=mu);
text(mu,0,expression(mu=="0.5"));

This is basic stuff at the core of classical statistical techniques: least squares models are computationally straightforward to fit, but they also happen to imply Gaussian errors, which is a reasonable first approximation for a lot of real life data.

Of course we could look at it the other way. If I want to measure the Euclidean distance from a point $a$ to a point $b$ , I can back this out from the log likelihood of $a$ under a unit variance Gaussian centred at $b$ .

Putting $\sigma=1$ :

$\displaystyle f(x;\mu) = \frac{1}{\sqrt{2\pi}} e^{-\frac{1}{2} \left(x-\mu\right)^2 }$

$\displaystyle \log f(x;\mu) = - \frac{1}{2}\log(2\pi) -\frac{1}{2}\left(x-\mu \right)^2$

$\displaystyle \left(x-\mu \right)^2 = - 2\log f(x;\mu) - \log(2\pi)$

$\displaystyle \left(x-\mu \right) = \sqrt{-2\log f(x;\mu) - \log(2\pi)}$

a <- 2;
b <- 4;
sqrt(-2*dnorm(b, mean=a, sd=1, log=T)  - log(2*pi));

This is rather a roundabout way of measuring distances. Would you ever want to do this? Well, in the multivariate case, if the covariance matrix isn’t spherical you get a distance measure that depends on direction; something a bit like the Mahalanobis distance.

L-1 distance and Laplace distribution

For our next trick, we can try measure distances with other norms than $L_{2}$ , the good old squared Euclidean distance. For instance if we minimize the absolute error instead of the squared error (e.g. for Quantile Regression) we’re still measuring distances but now they’re in the achingly fashionable $L_{1}$ norm. We’ve implicitly assumed the errors follow the Laplace or “double exponential” distribution so the log likelihood looks like this:

mu <- 0.5;
b <- 1;
par(mfrow=c(2,1));
curve(log(exp(-abs(x-mu)/b)/2*b),-4,5,xlab="x",ylab=expression(log(f(x))));
abline(v=mu);
curve(exp(-abs(x-mu)/b)/2*b,-4,5,xlab="x",ylab=expression(f(x)));
abline(v=mu);
text(mu,0,expression(mu==0.5));

KL divergence and Dirichlet distributions

What if we go a bit further off-piste: let’s consider the Kullback-Leibler divergence between two arbitrary N-dimensional probability distributions $\mathbf{p}$ and $\mathbf{q}$ :

$\displaystyle D_{KL}(\mathbf{p} \Vert \mathbf{q}) = \sum_{i} p_{i} \log \frac{p_{i}}{q_{i}}$

This is a bit different than the examples above, where the log-probability depends on metric distances between points in $\mathbb{R}^{N}$ , Firstly: the KL divergence isn’t a proper metric (it’s not symmetric and doesn’t obey the triangle inequality). However, it is does act as a distance in the sense that $D_{KL}(p,q) \geq 0$ with equality only when $\mathbf{p}=\mathbf{q}$ , which is good enough for our purposes (it’s a “premetric”).

Secondly, we’re now confining ourselves to points that live on probability simplex $\mathbb{P}^{N}$ , instead of anywhere in $\mathbb{R}^{N}$ . That means our distributions $\mathbf{p}$ have to satisfy $\sum_{i} p_{i}=1$ , and $p_{i}>0$ .

A widely used distribution on the simplex is the Dirichlet distribution:

$\displaystyle f(\mathbf{p} ; \mathbf{\alpha}) \propto \prod_{i=1}^K p_i^{\alpha_i - 1}$

which is also called the beta distributionin the case when $N=2$ . Then we have a single degree of freedom $p$ :

$\displaystyle f(p ; \alpha,\beta) \propto p^{\alpha-1}(1-p)^{\beta-1}$

Now; is it too much to hope for that the log-likelihood for the beta distribution follows the same form as the Gaussian and Laplace distributions above, but with the KL divergence replacing the metric distance? (SPOILERS: yes, but not by much, and let’s see where…)

Concentration and mean parameters

Firstly, the other distributions had two parameters: a mean or location ( $\mathbf{\mu}$ ) and a scale or dispersion parameter ( $\sigma$ or $b$ ). Here we seem to have just an unnormalized $N$ -dimensional parameter vector of pseudo-counts $\mathbf{\alpha}$ . But as David Mackay will tell you in ITILA, you can factor this into a positive real concentration parameter and a normalized mean vector which lives on the simplex: $\mathbf{\alpha} = c\mathbf{\mu}$ .

Let’s write out the log-likelihood in this form, lumping all the messy gamma functions at the front into a normalizing factor $Z$ .

$\displaystyle \log f(\mathbf{p} ; c, \mathbf{\mu}) = \sum_{i=1}^K (c\mu_i - 1) \log p_i - \log Z$

$\displaystyle = c\sum_{i=1}^K \mu_i \log p_i - \sum_{i=1}^K \log p_i - \log Z$

Recall that the KL divergence from the mean $\mathbf{\mu}$ to $\mathbf{p}$ is

$\displaystyle D_{KL}(\mathbf{\mu} \Vert \mathbf{p}) = \sum_{i} \mu_{i} \log \frac{\mu_{i}}{p_{i}} = \sum_{i} \mu_{i} \log \mu_{i} - \sum_{i} \mu_{i} \log p_{i} = -H(\mu) - \sum_{i} \mu_{i} \log p_{i}$

where $H(\mathbf{\mu})$ is the entropy of the mean distribution $\mathbf{\mu}$ . Then our log likelihood is:

$\displaystyle \log f(\mathbf{p} ; c, \mathbf{\mu}) = -c D_{KL}(\mathbf{\mu} \Vert \mathbf{p}) - c H(\mathbf{\mu}) - \sum_{i=1}^K \log p_i - \log Z$

which is looking promising, especially because the $H(\mathbf{\mu})$ doesn’t depend on $p$ so will just become part of the normalizing constant $Z$ . But what about the other term?

That’s a more awkward customer, but we can still look at it in terms of KL divergence; not from our mean $\mathbf{\mu}$ but from the uniform distribution $\mathbf{u}$ with $u_{i}=\frac{1}{N}$ .

If we substitute in

$\displaystyle D_{KL}(\mathbf{u} \Vert \mathbf{p}) = \sum_{i} u_{i} \log \frac{u_{i}}{p_{i}} = -H( \mathbf{u} ) - \frac{1}{N} \sum_{i} \log p_{i}$

and pull out the constants we end up with this:

$\displaystyle = -c D_{KL}(\mathbf{\mu} \Vert \mathbf{p}) + N D_{KL}(\mathbf{u} \Vert \mathbf{p}) - \log Z$

Curiouser and curiouser!

How does it behave?

Our Dirichlet log likelihood doesn’t depend solely on the “distance” from the mean like other two examples, but:

It does depend on the KL divergence from the mean, and asymptotically solely on that as we make $c \gg N$ .
We can also see that it does so exactly when $\mathbf{\mu} = \mathbf{u}$ , with an effective concentration of $c-N$ .

So the contours of the Dirichlet distribution with uniform mean are balls of constant $D_{KL}$ , which is pleasing. (Someone has made nice 3d prints of these and other related “Bregman balls” here.)

dirichlet.logZ <- function(c, m) {
 sum(lgamma(c*m)) - lgamma(sum(c*m));
}
logddirichlet <- function(p, c, m) {
  (c*m-1) %*% log(p) - dirichlet.logZ(c,m);
}

m <- c(1,1,1)/3.;
c <- 25.;

x <- 1:99/100.;
y <- 1:99/100.;
z <- matrix(nrow=99,ncol=99)
for (xx in 1:99) { 
  for (yy in 1:99) { 
    p <- c(x[xx],y[yy],1-x[xx]-y[yy]);
    z[yy,xx] <- logddirichlet(p, c, m);
  }
}
filled.contour(x,y,exp(z));

There’s also a repulsive dependence on the divergence from the uniform p.d.f. $\mathbf{u}$ , which is easiest to see in the univariate (beta distribution) case.

This accounts for the skewness of the distributions when $p \neq \frac{1}{2}$ , and it also explains why the distribution becomes multimodal with peaks at the boundaries when $c$ is small: then the “centrifugal” term pushing away from $\mathbf{u}$ dominates over the “centripetal” term which pulls us toward $\mathbf{m}$ .

par(mfrow=c(2,1));
curve(dbeta(x, 25, 5));
curve(dbeta(x, 0.8, 0.8));

Connections

I’ve got some more questions about this interpretation of the beta/Dirichlet distributions as depending on divergences, please comment if you know the answers!

Why does this unexpected “centrifugal” term appear in the Dirichlet? It’s to do with the pesky $-1$ ‘s in the exponents… why are they there?

Sometimes people want to approximate beta distributions by Gaussians. John D.Cook points out that this works reasonably well when the parameters are “large and approximately equal” (exactly the circumstances under which the distribution depends more on $D_{KL}$ from the mean). This paper of David MacKay and Andrew Gelman’s blog both suggest that if you need to approximate Dirichlet distributions with Gaussians, this is best done with a change of coordinates to the softmax basis.

It feels to me like there is already a similarity between $D_{KL}$ and squared Euclidean distance, and so between the Dirichlet and the Gaussian. Maybe it can be made more precise with a better understanding of information geometry; and maybe this might help to come up with or reinterpret a generalization of the Dirichlet with a more general precision/concentration structure for $N>2$ .

2 Comments to “Distances, Divergences, Dirichlet distributions”

Items of some interest: | Notional Slurry says:

July 12, 2012 at 2:04 pm

[…] Distances, Divergences, Dirichlet distributions « Ben Moran […]

Turning Distances in Distributions says:

September 19, 2016 at 11:59 pm

[…] Much of the material for this note is canonical, although I’m less familiar with the focus on relating metrics to distributions. One thing that got me interested in the topic long ago was this blog post by Ben Moran. […]

Ben Moran