Machine learning, by hand

Companion to the notes on Chapter 11 of Amari's Information Geometry and Its Applications. Back to the notes. Eight small experiments, one or two for each section of the chapter: the centre of a cluster and the shape of a decision boundary for a Bregman divergence, the Chernoff exponent of a classifier, the volume element of a kernel, the margin of a linear machine, belief propagation and two flavours of CCCP on a loop, AdaBoost round by round, and a Gaussian restricted Boltzmann machine. Every number is computed in your browser by the same formulas as in code/machine_learning.py, and the default readouts equal what that script prints.

1. The centre of a cluster is the mean, in one slot only

Six patterns in the positive quadrant and a Bregman divergence $D_\varphi$. The cost of putting the representative of the cluster at $c$ is the average divergence from the members. Theorem 11.1 says that with $c$ in the second slot, $\tfrac1k\sum_iD_\varphi[x_i:c]$, the cost is smallest at the arithmetic mean for every $\varphi$ (the orange cross). Switch to the first slot, $\tfrac1k\sum_iD_\varphi[c:x_i]$, and the minimum moves to the mean in the dual coordinates, $\theta=\nabla\varphi(c)$ (the green diamond); for the squared Euclidean distance the two coincide. Drag the trial centre and compare: in the table the smaller entry of each column is in bold.

2. Which curve is the boundary? Theorem 11.2, corrected

For two centres $\eta_1,\eta_2$ the boundary of their cells is $\{x:D_\varphi[x:\eta_1]=D_\varphi[x:\eta_2]\}$. Because $D_\varphi[x:\eta_1]-D_\varphi[x:\eta_2]=(\theta_2-\theta_1)\cdot x+\text{const}$, it is a straight line in the pattern coordinates (black, left) and meets orthogonally the geodesic that is straight in $\theta$ (blue, dashed) at the equidistant point $\eta_{12}$. The book draws it the other way round: a hyperplane in $\theta$ through the midpoint of the $\eta$-straight line (orange); that is the right statement for the exchanged divergence $D_\varphi[\eta_h:x]$, for which the cluster centre is no longer the mean. On the right, in $\theta=\log x$, the printed construction is a straight line, and the true boundary is the curve. Move the centres; the readout gives the divergence difference $D_1-D_2$ at four points of the printed hyperplane (it should be $0$ and is not) and at points of the corrected one.

3. The error exponent of a classifier is a divergence

Two Poisson laws with rates $\lambda_1,\lambda_2$ and $N$ observations. With the e-geodesic $\theta_t=(1-t)\theta_1+t\theta_2$ the divergences $\mathrm{KL}[\theta_t:\theta_1]$ and $\mathrm{KL}[\theta_t:\theta_2]$ cross at $t^*$, and the Chernoff information $C=-\min_t\log\sum p_1^{1-t}p_2^{t}$ equals both there (right panel). The exact Bayes error, computed by summing over the sufficient statistic, has $-\tfrac1N\log P_{\rm err}\to C$ for any prior (left panel), but only like $P_{\rm err}\approx0.49\,N^{-1/2}e^{-NC}$: (11.54) is an equality of exponents, not of probabilities. The printed (11.55) forgets the $-\log$, and the symbol $\lambda$ means $1-t$ in (11.52) and $t$ in (11.50); the readout shows both values.

4. A kernel's volume element, before and after the conformal change

The Gaussian kernel $K=e^{-|x-x'|^2/\sigma_w^2}$ induces the metric $g_{ij}=\partial_i\partial'_jK|_{x'=x}=\tfrac{2}{\sigma_w^2}\delta_{ij}$ (11.90): the same at every point. The modified kernel $\tilde K=\sigma(x)\sigma(x')K$ has $\tilde g=\sigma^2g+\nabla\sigma\nabla\sigma^{\mathsf T}$ (11.98), so with $\sigma$ large near the support vectors (11.93) the volume element (11.91) is enlarged there (orange) and shrunk far away (blue). The readout gives $\sigma$, $|\nabla\sigma|$ and the ratio $\sqrt{\det\tilde g}/\sqrt{\det g}$ at the yellow point. At a support vector the cone-shaped $\sigma$ has no gradient, which is a small gap in the construction; the page uses the symmetric value $0$ there.

5. The maximal margin is the best direction

Fourteen separable points. For a given direction of the normal, the best separating hyperplane with that direction sits halfway between the two projected classes, and its margin is half the gap between them; the support vectors are the points at exactly that distance. As you turn the normal the margin traces the curve on the right, which has one peak: the direction of $w=\sum_i\alpha_iy_ix_i$ from the dual problem (11.70)–(11.73), with margin $1/|w|$ (11.65). The scan finds the same number as the quadratic program, which is an independent route to (11.63)–(11.66).

6. Belief propagation, mean field and two CCCPs on a loop

Four $\pm1$ spins on a cycle, fields $h=(0.3,-0.2,0.1,0.25)$ and a common coupling $w$. The exact marginals need 16 terms; belief propagation (the e/m-projection algorithm (11.133)–(11.136), identical to message passing to $10^{-16}$) and the mean-field equation (11.125) approximate them, BP much better. The simplified CCCP (11.144)–(11.145) is claimed to converge; on this loop it does so only for weak coupling and otherwise flips sign at every step (left) while the Bethe free energy of its iterates goes up and down (right). Yuille's CCCP (11.148)–(11.149), with the inner equation solved exactly, lowers the free energy at every step. Change the coupling and the number of steps shown.

7. AdaBoost, one round at a time

Twenty points in the unit square, labelled by $\operatorname{sign}(x_1+x_2-1+\text{noise})$, and 76 decision stumps. At each round the stump with the smallest weighted error under the current weights $W_t$ is added with the weight $\alpha_t=\tfrac12\log\frac{1-\varepsilon_t}{\varepsilon_t}$ (11.174); the points it gets wrong are outlined and their weights grow in (11.175) until the same stump has error exactly $\tfrac12$ under the new weights. The product $\prod Z_s$ equals the mean exponential loss and bounds the training error. The orange curve is the weight that exact maximum likelihood of the normalised model (11.164) would give: twice AdaBoost's at round 1, because (11.169) is the projection onto an unnormalised family.

8. A Gaussian RBM learns the leading principal components

For a Gaussian restricted Boltzmann machine whose input has covariance with eigenvalues $\lambda_i$, the learning equation (11.229) (with the factor $W$ that the printed formula loses) drives the singular values of the weight matrix to $\sqrt{1-\sigma_v^2/\lambda_i}$ for the directions with $\lambda_i>\sigma_v^2$, as many as there are hidden units; the model covariance $\sigma_v^2(I-W^{\mathsf T}W)^{-1}$ then has the data variance in those directions and the floor $\sigma_v^2$ in all others (11.234). The book prints $1-1/\lambda_i$, which is right only for $\sigma_v=1$. Contrastive divergence $\mathrm{CD}_k$ (11.230) has the same equilibrium; its relaxation is slower. Change $\sigma_v^2$, the number of hidden units and the learning rule.