Batch normalization

Batch normalization (also known as batch norm) is a method used to make training of artificial neural networks faster and more stable through normalization of the layers' inputs by re-centering and re-scaling. It was proposed by Sergey Ioffe and Christian Szegedy in 2015.
While the effect of batch normalization is evident, the reasons behind its effectiveness remain under discussion. It was believed that it can mitigate the problem of "internal covariate shift", where parameter initialization and changes in the distribution of the inputs of each layer affect the learning rate of the network. Recently, some scholars have argued that batch normalization does not reduce internal covariate shift, but rather smooths the objective function, which in turn improves the performance. However, at initialization, batch normalization in fact induces severe gradient explosion in deep networks, which is only alleviated by skip connections in residual networks. Others maintain that batch normalization achieves length-direction decoupling, and thereby accelerates neural networks. More recently a normalize gradient clipping technique and smart hyperparameter tuning has been introduced in Normalizer-Free Nets, so called "NF-Nets" which mitigates the need for batch normalization.
Internal covariate shift.
Each layer of a neural network has inputs with a corresponding distribution, which is affected during the training process by the randomness in the parameter initialization and the randomness in the input data. The effect of these sources of randomness on the distribution of the inputs to internal layers during training is described as internal covariate shift. Although a clear-cut precise definition seems to be missing, the phenomenon observed in experiments is the change on means and variances of the inputs to internal layers during training.
Batch normalization was initially proposed to mitigate internal covariate shift. During the training stage of networks, as the parameters of the preceding layers change, the distribution of inputs to the current layer changes accordingly, such that the current layer needs to constantly readjust to new distributions. This problem is especially severe for deep networks, because small changes in shallower hidden layers will be amplified as they propagate within the network, resulting in significant shift in deeper hidden layers. Therefore, the method of batch normalization is proposed to reduce these unwanted shifts to speed up training and to produce more reliable models.
Besides reducing internal covariate shift, batch normalization is believed to introduce many other benefits. With this additional operation, the network can use higher learning rate without vanishing or exploding gradients. Furthermore, batch normalization seems to have a regularizing effect such that the network improves its generalization properties, and it is thus unnecessary to use dropout to mitigate overfitting. It has been observed also that with batch norm the network becomes more robust to different initialization schemes and learning rates.
Procedures.
Transformation.
In a neural network, batch normalization is achieved through a normalization step that fixes the means and variances of each layer's inputs. Ideally, the normalization would be conducted over the entire training set, but to use this step jointly with stochastic optimization methods, it is impractical to use the global information. Thus, normalization is restrained to each mini-batch in the training process.
Let us use "B" to denote a mini-batch of size "m" of the entire training set. The empirical mean and variance of "B" could thus be denoted as
formula_1, and formula_2.
For a layer of the network with "d-"dimensional input, formula_3, each dimension of its input is then normalized (i.e. re-centered and re-scaled) separately,
formula_4, where formula_5 and formula_6; formula_7 and formula_8 are the per-dimension mean and standard deviation, respectively.
formula_9 is added in the denominator for numerical stability and is an arbitrarily small constant. The resulting normalized activation formula_10have zero mean and unit variance, if formula_9 is not taken into account. To restore the representation power of the network, a transformation step then follows as
formula_12,
where the parameters formula_13 and formula_14 are subsequently learned in the optimization process.
Formally, the operation that implements batch normalization is a transform formula_15 called the Batch Normalizing transform. The output of the BN transform formula_16 is then passed to other network layers, while the normalized output formula_17 remains internal to the current layer.
Backpropagation.
The described BN transform is a differentiable operation, and the gradient of the loss "l" with respect to the different parameters can be computed directly with the chain rule.
Specifically, formula_18 depends on the choice of activation function, and the gradient against other parameters could be expressed as a function of formula_18:
formula_20,
formula_21, formula_22,formula_23, formula_24,
and formula_25.
Inference.
During the training stage, the normalization steps depend on the mini-batches to ensure efficient and reliable training. However, in the inference stage, this dependence is not useful any more. Instead, the normalization step in this stage is computed with the population statistics such that the output could depend on the input in a deterministic manner. The population mean, formula_26, and variance, formula_27, are computed as:
formula_28, and formula_29.
The population statistics thus is a complete representation of the mini-batches.
The BN transform in the inference step thus becomes
formula_30,
where formula_31 is passed on to future layers instead of formula_32. Since the parameters are fixed in this transformation, the batch normalization procedure is essentially applying a linear transform to the activation.
Theoretical Understanding.
Although batch normalization has become popular due to its strong empirical performance, the working mechanism of the method is not yet well-understood. The explanation made in the original paper was that batch norm works by reducing internal covariate shift, but this has been challenged by more recent work. One experiment trained a VGG-16 network under 3 different training regimes: standard (no batch norm), batch norm, and batch norm with noise added to each layer during training. In the third model, the noise has non-zero mean and non-unit variance, i.e. it explicitly introduces covariate shift. Despite this, it showed similar accuracy to the second model, and both performed better than the first, suggesting that covariate shift is not the reason that batch norm improves performance.
Smoothness.
One alternative explanation, is that the improvement with batch normalization is instead due to it producing a smoother parameter space and smoother gradients, as formalized by a smaller Lipschitz constant. 
Consider two identical networks, one contains batch normalization layers and the other doesn't, the behaviors of these two networks are then compared. Denote the loss functions as formula_33 and formula_34, respectively. Let the input to both networks be formula_35, and the output be formula_36, for which formula_37, where formula_38 is the layer weights. For the second network, formula_36 additionally goes through a batch normalization layer. Denote the normalized activation as formula_40, which has zero mean and unit variance. Let the transformed activation be formula_41, and suppose formula_42 and formula_43 are constants. Finally, denote the standard deviation over a mini-batch formula_44 as formula_45.
First, it can be shown that the gradient magnitude of a batch normalized network, formula_46, is bounded, with the bound expressed as
formula_47.
Since the gradient magnitude represents the Lipschitzness of the loss, this relationship indicates that a batch normalized network could achieve greater Lipschitzness comparatively. Notice that the bound gets tighter when the gradient formula_48 correlates with the activation formula_49, which is a common phenomena. The scaling of formula_50 is also significant, since the variance is often large.
Secondly, the quadratic form of the loss Hessian with respect to activation in the gradient direction can be bounded as
formula_51.
The scaling of formula_50 indicates that the loss Hessian is resilient to the mini-batch variance, whereas the second term on the right hand side suggests that it becomes smoother when the Hessian and the inner product are non-negative. If the loss is locally convex, then the Hessian is positive semi-definite, while the inner product is positive if formula_53 is in the direction towards the minimum of the loss. It could thus be concluded from this inequality that the gradient generally becomes more predictive with the batch normalization layer.
It then follows to translate the bounds related to the loss with respect to the normalized activation to a bound on the loss with respect to the network weights:
formula_54, where formula_55.
Since the parameters of each hidden unit converge linearly, the whole optimization problem has a linear rate of convergence.