A brief detour into singular integrals.

Before defining the RLCT, we will take a brief detour into Bayesian statistics and Watanabe's theory of singular integrals. This will conveniently give us the opportunity to shore up necessary background in information theory and Bayesian statistics – and establish some prerequisites for exploring the fundamental theorems of singular learning theory in the future. We will seek to answer the following questions.

1. In Bayesian inference, we output a distribution on the weights. How can we quantify how well the model and the prior predicted the observed dataset?
2. How do KL divergence and Watanabe's singular integral show up when computing the model evidence?

Going forward, it will be essential to have some information theory basics. For that, I will default to 3b1b's excellent two-part series (Part 1: Reinventing Entropy and Part 2: But what is cross-entropy?). A central object of study in The Gray Book is the singular integral of general form:

where $K_n(w)$ is a function on $\RR^d$ and $\phi(w)$ is a probability density function. First, we will show that, when we set $K_n(w)$ to the empirical KL divergence, $Z(n)$ is exactly computing the normalized model evidence.

Empirical Cross Entropy

For the remainder of this post, let $\mathcal{X}$ be the input space, and let $\mathcal{Y}$ denote the space of possible outputs. Perhaps think about every $x \in \cX$ as a token sequence of fixed context length and every $y \in \cY$ as a possible next token with $|\cY| = |\textrm{vocabulary}|.$ Then let $q(y \mid x)$ denote the underlying true conditional distribution (that we are trying to model), and define a joint probability distribution on $\cX \times \cY$:

Similarly, let $p(y \mid x, w)$ denote the conditional distribution predicted by our model with parameters $w,$ and extend this to a distribution to $\cX \times \cY$ by letting

Recall that, for two probability distributions $q$ and $p$ on a discrete sample space $\mathcal Y$, the population KL divergence is defined by

Specializing to $\cX \times \cY,$ we compute that

In the case where $|\cX|$ is finite and $q(x)$ is a uniform distribution on $\cX$, this is the average of the conditional KL divergences over the inputs. The general issue with the population KL divergence, however, is that $q(x,y)$ may be unknown or difficult to compute in practice. (For modeling natural language, it is arguably unknown). Therefore, we need a good empirical substitute which will converge to the population KL divergence as the number of samples goes to infinity.

Let $D_n = \{(x_1,y_1),\ldots,(x_n,y_n)\} \subseteq \cX \times \cY$ be a dataset with $n$ examples, sampled independently according to

For future use, let $\mathcal{D}$ be the space of all datasets with any finite number of examples. Then

and

We define the empirical KL divergence to be

It is also a common convention to flip numerator and denominator, writing:

By the law of large numbers, for each fixed $w,$ it follows that

In the expression that we saw earlier for $Z(n),$ this will precisely be our choice of function $K_n.$

Now I should note that this actually does not fix the issue of being unable to compute $K_n(w)$ due to $q(x,y)$ being unknown. However, we can at least minimize the empirical KL divergence by remarking that minimizing $K_n(w)$ is equivalent to minimizing the empirical cross entropy, which is given by:

The fact that this quantity does not depend on $q$ makes $L_n(w)$ highly useful for training machine learning algorithms. Unfortunately though, explicitly computing $K_n(w)$ is still generally not possible. However, it will be useful to consider it abstractly as an input to a singular integral.

Bayesian Posterior

Given a dataset $D$ and a set of model parameters $\mathcal{W}$, we define the posterior distribution with respect to some $w \in \mathcal{W}$ to be:

for some prior distribution $p(\mathcal{W}).$ There are a few ways to think about the posterior distribution. First off, it is immediately apparent that

Thus, $p(w \mid D)$ is similar to the likelihood – except it is weighted by some prior, $p(w).$ Then we normalize by $p(D)$ to ensure that $p(\mathcal{W} \mid D)$ is a probability distribution. It is also important to remember that – under the hood – we are assuming the existence of the sample space $\mathcal{W} \times \mathcal{D}$, where the probability measure is a joint distribution constructed in two stages. First we sample from the parameters:

and then we sample from $\mathcal{D}$:

From this generative point of view, $p(w\mid D)$ becomes more concrete. In the discrete case, it is the probability that the hidden parameter setting sampled in the first stage was $w$, conditional on observing the dataset $D$ in the second stage. Remember unlike the likelihood, a large posterior (say .99) does not automatically mean that $w$ is highly predictive – only that its likelihood, weighted by the prior, is much larger than the rest of $\mathcal{W}.$ ¹ The process of Bayesian inference (repeatedly updating your new prior to be the posterior, computed with new observations) will output a distribution of parameters. The likelihood tells us how predictive a single parameter setting is. But what if we wanted to average the likelihood over the prior to get a feel for the entire distribution?

In general, this is hard. But SLT to the rescue! Let's see how the singular integral $Z(n)$ that Watanabe and others have developed techniques to analyze asymptotically is actually doing something very similar in disguise.

Model evidence

Letting $K_n(w)$ be the empirical KL divergence, we can simplify:

Plugging this into $Z(n)$ and taking $\phi(w) = p(w)$, we obtain:

It is extremely tempting to claim that this integrand is just $p(w \mid D_n)$, but this is incorrect precisely because $p(D_n) \neq q(D_n)$ (in general). Instead, we note that

We often call $p(D_n)$ the model evidence, and this ratio tells us roughly how well the distribution $p(\mathcal{W})$ predicted $D_n$, normalized by the true dataset probability. One might also remark that the evidence $p(D_n)$ is exactly the likelihood $p(D_n \mid w)$ averaged over $p(\mathcal{W})$, so this is a very natural thing to want to compute.

This explains Watanabe's interest in singular integrals to some extent. But this isn't all. Remember that the end goal is to produce a more precise measure of “effective dimension”. Next time, we will finally define the RLCT and relate it to $\frac{p(D_n)}{q(D_n)}$ via the free energy equation. Eventually we will also develop techniques for estimating $Z(n)$ using a Laplace approximation to the posterior distribution.