The Training Example Lie Bracket

Summary

Training Examples are Vector Fields and their Lie Brackets can be Computed skip to results An ideal machine learning model would not care what order training examples appeared in its training process. From a Bayesian perspective, the training dataset is unordered data and all updates based on seeing one additional example should commute with each other. For neural nets trained by gradient descent, however, this is not the case. This webpage will explain how to compute the effects of swapping the order of two training examples on a per-parameter level, and show the results of computing these quantities for a simple convnet model. To get started, we just need to recognize one simple mathematical fact: Training Examples are Vector Fields If we are training a neural network with parameters $\theta \in \Theta = \mathbb{R}^\text{num params}$, then we can treat each training example as a vector field. In particular, if $x$ is a training example and $\mathcal{L}^{(x)}$ is the per-example loss for the training example $x$, then this vector field is: $$ v^{(x)}(\theta) = -\nabla_{\theta} \mathcal{L}^{(x)} $$ In other words, for a specific training example, the arrows of the resulting vector field point in the direction that the parameters should be updated. In this view, a gradient update basically looks like moving in the direction of the vector field by the learning rate $\epsilon$. $$ \theta' = \theta + \epsilon v^{(x)}(\theta). $$ The Training Example Lie Bracket One thing we can do with vector fields is to compute their Lie bracket. So if $x, y$ are training examples, we may compute: $$ [v^{(x)}, v^{(y)}] = (v^{(x)}\cdot \nabla_\theta) v^{(y)} - (v^{(y)}\cdot \nabla_\theta) v^{(x)} $$ We can compute the Lie bracket of any two vector fields on $\Theta$, and so we can certainly compute the Lie bracket of the vector fields arising from two training examples. The Lie bracket of two training examples tells us about the order dependence of training on those examples. The Lie b...