Batch Normalization 1D

题号：NC215118
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

提示：本题描述较长，但难度并不高，请耐心读题和写题。

Batch Normalization（简称BN），被提出在Google于2015年发表的《Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift》。

不少同学都知道，机器学习模型往往需要一个训练集，训练之后才会使用到测试集或者其他实用场合中，这里有一个基本假设就是，训练集和测试集的数据是独立同分布的。在概率论与统计学中，独立同分布（英语：Independent and identically distributed，缩写为IID）是指一组随机变量中每个变量的概率分布都相同，且这些随机变量互相独立。一组随机变量独立同分布并不意味着它们的样本空间中每个事件发生概率都相同。例如，投掷非均匀骰子得到的结果序列是独立同分布的，但掷出每个面朝上的概率并不相同。

在深度学习中，由于问题的复杂性，我们往往会使用较深层数的网络进行训练，而在深度网络前向传播的过程中，每一层的输入都是上一层的输出，而在相邻的两层之间由于各种原因，输出的数据也并不一定是IID的，这个现象称为“Internal Covariate Shift”，因此我们需要将每一层的输出也转换为IID，Normalize常被用来实现这个过程，例如Dropout，L1正则化、L2正则化等都可以视为是一种Normalize，此外，还有一种方式叫白化（Whiten），就是对输入数据分布变换到0均值，和单位方差的分布，即正态分布。但白化的计算成本很高，尽管它可能是效果最明显的方法。

白化的计算方式各位同学可以在赛后自行查阅。

此外，由于算力因素的制约，我们往往无法将训练集一次性全部输入深度网络来训练，因此有mini-batch方式将原数据集切分为n_batch个批次来依次训练，这也是深度学习之所以备受瞩目的原因（便于分布式训练）。并且白化很难扩展到mini-batch的情况，因此就有了Batch Normalization。

注意，我们仅考虑输入数据是一维的情况，即输入数据的shape为 $(n, c)$ ，有 $n$ 个长度为 $(1, c)$ 的数据。

BN层共有四个参数：moving_mean, moving_var, gamma, beta。

其中gamma和beta是在深度网络中接受反向传播优化，和传递梯度的参数，在本题中不考虑反向传播训练优化，始终使用给定的数值进行计算。（在BN理论中，gamma和beta是用来维持输入的分布信息的）

BN在模型训练时会使用滑动平均的方式积累计算每个batch的数据均值mean和方差var，滑动平均是一种通过创建整个数据集中不同子集的一系列平均数来分析数据点的计算方法，然后更新到已经积累的moving_mean和moving_var中。

在n_batch个批次的数据都经过训练之后积累的moving_mean和moving_var会被认为是整个数据集的mean和var的估计值。

然后使用当前批次输入数据的平均值mean和var来对当前输入数据进行Normalize，之后使用gamma和beta来做线性变换得到输出。

在模型推理阶段，BN不再计算moving_mean和moving_var，而是直接使用moving_mean和moving_var来对当前输入数据进行Normalize，之后使用gamma和beta来做线性变换得到输出。

论文里的算法描述为：

这里给出一个直接的计算模板（伪Python代码，即使没学过也不可能看不懂，使用Python的选手也不用寄希望于复制粘贴就能运行，也不支持使用numpy或者scipy等Python库）

函数定义：

def batch_norm(X, gamma, beta, moving_mean, moving_var, is_training=True, eps=1e-5, momentum=0.9,):

其中X是shape为 $(n, c)$ 的张量，gamma, beta, moving_mean, moving_vars是 $(1, c)$ 的张量，is_training表示是否是训练模式。

返回 out, moving_mean, moving_var，out是计算结果，moving_mean, moving_var是本轮更新后的moving_mean, moving_var。

这里注意，上面提到的张量的计算具有广播特性：

如果是一个 $(n, c)$ 的张量和一个标量数字运算，那么就是把张量的每一个元素都和这个数字做运算，比如shape为 $(2,4)$ 的 $A = \{ \{ 1,2,3,4 \}, \{ 5,6,7,8 \}\}$ ，标量数字 $B = 2$ ，
那么 $A – B = \{ \{ -1,0,1,2 \}, \{ 3,4,5,6 \}\}$ ，加减乘除同理，此时满足交换律。

如果是一个 $(n, c)$ 的张量和 $(1, c)$ 的张量运算，那么就是把前一个张量第0个维度上的每个 $(1, c)$ 的张量，都和后者做逐元素的运算，比如shape为 $(2, 4)$ 的 $A = \{ \{ 1,2,3,4 \}, \{ 5,6,7,8 \}\}$ ，shape为 $(1,4)$ 的 $B = \{ 1,2,1,2 \}$ ,
那么 $A + B = \{ \{ 2,4,4,6 \}, \{ 6,8,8,10\} \}$ ，加减乘除同理。

如果是一个 $(n, c)$ 的张量和 $(n, c)$ 的张量运算，那么直接做逐元素的运算，比如shape为 $(2, 4)$ 的 $A = \{ \{ 1,2,3,4 \}, \{ 5,6,7,8 \}\}$ ，shape为 $(2, 4)$ 的 $B = \{\{ 1,2,1,2 \},\{ 1,2,1,2 \} \}$ ,
那么 $A - B = \{ \{ 0,0,2,2 \}, \{ 4,4,6,6 \} \}$ ，加减乘除同理。

一个 $(n, c)$ 的张量的平均值mean运算，为第0维的每个张量的均值来组成的张量，例如 $A = \{ \{ 1,2,3,4 \}, \{ 5,6,7,8 \}\}$ ，那么 $mean(A) = \{ 3, 4, 5, 6\}$ ，第一个元素 $3 = (1+5) / 2$ 。； $A = \{ \{ 1,2,3,4 \},\{ 5,6,7,8 \}, \{ 9,10,11,12 \} \}$ ，那么 $mean(A) = \{ 5,6,7,8\}$ ，第一个元素 $5 = (1+5+9) / 3$ 。

一个 $(n, c)$ 的张量的平方运算square为逐元素平方的结果。例如 $A = \{ \{ 1,2,3,4 \}, \{ 5,6,7,8 \}\}$ ，那么 $square(A) = \{ \{ 1,4,9,16 \}, \{ 25,36,49,64 \} \}$

一个 $(n, c)$ 的张量的开方运算sqrt为逐元素开方的结果。例如 $A = \{ \{ 1,4,9,16 \}, \{ 25,36,49,64 \} \}$ ，那么 $sqrt(A) = \{ \{1,2,3,4 \}, \{5,6,7,8 \} \}$

上述伪代码的几个print而言，对于

X = {{1.2, 2.3, 3.4, 4.5},
{2.3, 3.4, 4.5, 5.6},
{3.4, 4.5, 5.6, 6.7},}

gamma = {1.0, 2.0, 3.0, 4.0};
beta = {2.0, 3.0, 4.0, 5.0}
moving_mean = {0.0,0.0,0.0,0.0}
moving_var = {1.0,1.0,1.0,1.0}
eps = 1e-5
momentum = 0.9

而言，

当为训练模式时，输出为：

{2.3000, 3.4000, 4.5000, 5.6000}

{0.8067, 0.8067, 0.8067, 0.8067}

{0.2300, 0.3400, 0.4500, 0.5600}

{0.9807, 0.9807, 0.9807, 0.9807}  

{{-1.2247, -1.2247, -1.2247, -1.2247},
{0,.0,0.0,0.0,0.0}
{1.2247, 1.2247, 1.2247, 1.2247}}

{{0.7753, 0.5505, 0.3258, 0.1011},
{2.0000, 3.0000, 4.0000, 5.0000],
{3.2247, 5.4495, 7.6742, 9.8989]}

当为推理模式时，输出为：

{2.3000, 3.4000, 4.5000, 5.6000}


{0.8067, 0.8067, 0.8067, 0.8067}


{{1.2000, 2.3000, 3.4000, 4.5000},
{2.3000, 3.4000, 4.5000, 5.6000},
{3.4000, 4.5000, 5.6000, 6.7000}}


{{ 3.2000,  7.6000, 14.1999, 22.9999},
{ 4.3000,  9.8000, 17.4999, 27.3999},
{ 5.4000, 12.0000, 20.7999, 31.7999}}

注意我们的提交里不需要输出上述函数定义里的print，示例的print仅用于方便理解。

如果你的结果和上述输出有不大于0.001的误差那么可以认为是正确的。

你的任务是，给定初始参数，完成这个过程：

for i in range(n_batch):
    out, moving_mean, moving_var = batch_norm(X, gamma, beta, moving_mean, moving_var, True, eps, momentum)
out, moving_mean, moving_var = batch_norm(X, gamma, beta, moving_mean, moving_var, False, eps, momentum)

或者C/C++的伪代码：

while(n_batch--){
    out, moving_mean, moving_var = batch_norm(X, gamma, beta, moving_mean, moving_var, true, eps, momentum);
}
out, moving_mean, moving_var = batch_norm(X, gamma, beta, moving_mean, moving_var, false, eps, momentum);
//C/C++当然是不能直接返回三个返回值的，这只是表示batch_norm这个函数会更新moving_mean和moving_var的值而已，

最后打印out的值。

注意不需要输出上述函数定义里的print，示例的print仅用于方便理解。输出结果与正确结果的每个元素的误差不超过0.001即视为正确。

输入描述:

第一行为三个整数和两个浮点数，分别为n, c, n_batch, eps, momentum。

接下来的 $n$ 行，每行有 $c$ 个浮点数，分别表示 $X$ 的各个元素

接下来的 $1$ 行有 $c$ 个浮点数，表示gamma的该元素初始值

接下来的 $1$ 行有 $c$ 个浮点数，表示beta的该元素初始值

接下来的 $1$ 行有 $c$ 个浮点数，表示moving_mean的该元素初始值

接下来的 $1$ 行有 $c$ 个浮点数，表示moving_var的该元素初始值

所有值的范围都在 $[-20.0,20.0]$ 。

输出描述:

结果out是一个的张量，请保留四位小数，输出行，第行为第个张量的个值，按一个空格分隔。

输出结果与正确结果的每个元素的误差不超过0.001即视为正确。

示例1

输入

复制

3 4 3 0.00005 0.9
1.2 2.3 3.4 4.5
2.3 3.4 4.5 5.6
3.4 4.5 5.6 6.7
1.0 2.0 3.0 4.0
2.0 3.0 4.0 5.0
0.0 0.0 0.0 0.0
1.0 1.0 1.0 1.0

输出

复制

2.5924 5.8323 10.7200 17.2550 
3.7224 8.0923 14.1100 21.7750 
4.8524 10.3520 17.5000 26.2940