How it works · 05 / 05

Training

Differentiable, so trained by gradient descent: a modulated version of Adam minimising a cross-entropy loss.

For dummiesPlain-language view: everyday words, no equations. The full version is one click away.

In plain words

Training is nudging. Start with random numbers inside the formula and the vortices. Measure how wrong the current predictions are, using a standard score called cross-entropy. Adjust every number a little in the direction that reduces the score. Repeat, 32 examples at a time, until the training set is classified perfectly.

The nudging is done by Adam, the same optimiser that trains most neural networks, which the replicant can use because its formula is differentiable. The paper adds one tweak: each step is capped so that a single unusually large gradient cannot throw the model off course.

Why gradient descent

It is not possible in general to identify a minimiser of a discontinuous function. The logic replicant is differentiable (its derivative is discontinuous at the fold points of the absolute values, but continuous elsewhere), so quasi-Newton or gradient methods apply and converge towards a good local or global optimum. Gradient descent is also efficient and scalable in high-dimensional parameter spaces, and differentiable models lend themselves to sensitivity analysis. Grid search or evolutionary strategies would be computationally impractical here.

Adam

The chosen optimiser is the adaptive moment estimation variant of stochastic gradient descent. For every coefficient \(\alpha\) of the model it keeps exponentially forgetting estimates of the first and second moments of the gradient:

\[m_\alpha^{(t+1)}=\beta_1 m_\alpha^{(t)}+(1-\beta_1)\nabla_\alpha H^{(t)},\qquad v_\alpha^{(t+1)}=\beta_2 v_\alpha^{(t)}+(1-\beta_2)\left(\nabla_\alpha H^{(t)}\right)^2\](25, 26)

\[\hat m_\alpha=\frac{m_\alpha^{(t+1)}}{1-\beta_1^t},\qquad \hat v_\alpha=\frac{v_\alpha^{(t+1)}}{1-\beta_2^t},\qquad \alpha^{(t+1)}=\alpha^{(t)}-\eta\frac{\hat m_\alpha}{\sqrt{\hat v_\alpha}+\epsilon}\](27–29)

where \(\nabla_\alpha H^{(t)}\) is the partial derivative of the cross-entropy at iteration \(t\) and the forgetting factors are fixed at \(\beta_1=0.9\), \(\beta_2=0.99\).

Loss

The loss is the cross-entropy between predictions \(\boldsymbol{Y}=(y_{ij})\) and targets \(\boldsymbol{T}=(t_{ij})\), both \(N\times|C|\) matrices for \(N\) instances and \(|C|\) classes:

\[H(\boldsymbol{Y},\boldsymbol{T})=-\sum_{i=1}^{N}\sum_{j=1}^{|C|} t_{ij}\log\big(\sigma_j(\boldsymbol{u}_i)\big)+(1-t_{ij})\log\big(1-\sigma_j(\boldsymbol{u}_i)\big)\](30)

\[\sigma_j(\boldsymbol{u}_i)=\frac{e^{u_{ij}}}{\sum_{j'=1}^{|C|}e^{u_{ij'}}}\](31)

Here \(u_{ij}=U_j(L(\boldsymbol{x}_i))\) is the scalar field of class \(j\) evaluated at instance \(i\), \(\boldsymbol{u}_i\) collects the \(|C|\) class fields, and \(\sigma\) is the softmax over them.

Modulated moments

To converge faster and avoid extreme gradient values, the moment updates are modulated by dividing the gradient by a value \(a\):

\[m_\alpha^{(t+1)}=\beta_1 m_\alpha^{(t)}+(1-\beta_1)\frac{\nabla_\alpha H^{(t)}}{a},\qquad v_\alpha^{(t+1)}=\beta_2 v_\alpha^{(t)}+(1-\beta_2)\left(\frac{\nabla_\alpha H^{(t)}}{a}\right)^2\](32, 33)

with \(a=\max\big(1,|\nabla_{\alpha_1}H^{(t)}|,|\nabla_{\alpha_2}H^{(t)}|,\dots\big)\) taken over all parameters at iteration \(t\). This guarantees that the increments of \(m\) and \(v\) in every iteration are not greater than \(1-\beta_1\) and \(1-\beta_2\), and symmetrically not more negative than \((\beta_1-1)\) and \((\beta_2-1)\).

Settings used in the paper

Batch size \(N=32\). Training stops when the cross-entropy of the whole dataset is 0. Parameters are initialised at random, which is a source of run-to-run variability, most noticeable for small configurations such as the 32-parameter parity replicant.