LambdaOJ：手写数字识别 解题报告

wzf2000
2020年12月9日

LambdaOJ：手写数字识别 解题报告

概述

题面见此处。

基本要求就是实现一个简单的 MLP，进而完成训练与验证的过程。

由于我是真没学过人工智能理论，所以概念性错误啥的是太正常了。

算法分析：模型与前向传播

（当然这个算不算算法另论）

我们需要完成一个多层感知机的搭建，其中第一层就是我们的输入层，具体到某幅图片也就是其 $28 \times 28$ 的像素值（这也就是输出层的节点数），而隐藏层则不确定数量、也不确定每层的点数，最后通过一个输出层，得出等于每个标签（也就是某个数字）的概率，因此输出层的节点数就是 $l$。

这里面最特别的就是这个隐藏层，我们可以简单的认为隐藏层就是一个提取输入数据特征的过程，比如图像面积占比、图像周长什么的，当然最后训练得出的模型中，这些特征应该是不那么容易表述的。

而最终通过一系列隐藏层，提取了一系列特征后，输出层将进行一次线性回归，进而得到最终的各数字概率分布。

本题中，每一层我们都限定其为线性层，换而言之，对于一个输入向量 $input_{n \times 1}$，我们通过一个转移矩阵 $w_{m \times n}$ 和一个偏差向量 $b_{m \times 1}$ 得到：
$$
output_{m \times 1} = w_{m \times n} \times input_{n \times 1} + b_{m \times 1}
$$
但是通过上述仿射变换，得到的输出可能在一个比较大的范围内波动，我们希望将其限制在 $(0, 1)$ 中，则需要引入一个激活函数。

比如 Sigmoid 函数：
$$
S(x) = \frac{1}{1 + e^{-x}}
$$
类似的也比如 $\tanh x$ 函数等。

我们会发现，这些函数都具有值域落在某个小区间内的特点。

通过这样若干层的放射变换以及激活函数的作用，我们最终会在输出层得到 $l$ 个 $(0, 1)$ 范围的结果，但这并不是我们想要的一个概率分布，所以我们可以通过 Softmax 函数。

设有 $n$ 个数 $x_1, \cdots, x_n$，则：
$$
y_i = \mathrm{softmax}(x_i) = \frac{e^{x_i}}{\sum\limits_{k = 1}^n e^{x_k}} = \frac{e^{x_i - c}}{\sum\limits_{k = 1}^n e^{x_k - c}}
$$
显然有：
$$
\sum_{i = 1}^n y_i = 1, y_i > 0
$$
通过上面的定义我们会发现，此函数对于给定的样本只有相对意义，也就是说样本的整体平移并不会影响函数的结果。

而为了防止指数函数的过大导致溢出，我们可以让所有的 $x_i$ 都减去 $\max\limits_{k = 1}^n x_k$，来保证数值运算的可靠性。

那么对输出层得出的 $l$ 个结果作此变换，我们即可得到一个可能较为合理的概率分布。

最后的验证时，我们也只需认为，概率最大值即为最终的识别结果（最大似然）。

到这里，我们完成了对整个模型的架构分析，但是我们仍没有给出构建或者说训练这套模型的方法。

算法分析：后向传播与梯度下降

考虑这么一个问题，对于给定一个初始估计的参数分布 $X(x;t_1, t_2, \cdots, t_n)$，其中参数 $t_1, \cdots, t_n$ 给定，我们已知在 $x = x_0$ 点，其实际值为 $z_0$，$X$ 分布的估计值为 $y_0$。

那么这意味着在此点，此估计在 $x = x_0$ 点的误差为 $\delta = z_0 - y_0$，那么在 $x = x_0$ 固定的情况下，我们会希望对应的 $t_1, \cdots, t_n$ 向 $\delta$ 的反方向移动。

具体来说，给定一个比例值（学习率）$\eta$，我们可以期待（对于分布整体而言，就是向梯度方向下降误差的一定比例）：
$$
t_i' = t_i + \eta \cdot \delta \frac{\partial X}{\partial t_i}
$$
这样得到的新参数 $t_1', \cdots, t_n'$ 对应的 $X(x; t_1', \cdots, t_n')$ 相比初始的参数分布，可能有更好的拟合效果。

这也就是一般的梯度下降。

对于（某种意义下）随机选取的样本 $x$，也就是这道题中的随机梯度下降。

在此题中，对于单层（包括隐藏层与输出层）而言，我们的参数就是 $w$ 矩阵和 $b$ 偏差向量，而分布就是：
$$
X(input_{n \times 1}; w_{m \times n}, b_{m \times 1}) = S(w_{m \times n} \times input_{n \times 1} + b_{m \times 1})
$$
其中 $S$ 为激活函数，这里我们假设为 Sigmoid 函数或者 Softmax 函数。

那么就可以根据求导的链式法则得到，对于 $w_{i, j}$：
$$
w_{i, j}' - w_{i, j} = \eta \cdot \delta_i \cdot input_j \frac{dS(x)}{dx}
$$
对于 $b_i$：
$$
b_i' - b_i = \eta \cdot \delta_i \frac{dS(x)}{dx}
$$
这时你就会发现，此处表示与题面中的提示基本一致了。

而此处单个节点的误差 $\delta_i$，则容易想到通过其后继节点的误差表示。

具体来说，假设其有 $m$ 个后继节点，我们有：
$$
\delta_i = \sum_{j = 1}^m w_{j, i} \cdot \delta_j'
$$

通过这样的分析我们就得到了反向传播的一个基本模型。

算法分析：损失函数

本题我们采用输出层 Softmax 函数激活加交叉熵的方式定义损失函数。

而交叉熵，主要是对于实际分布和训练结果分布定义的（此处考虑离散型分布）。

具体来说，我们假设实际分布为：
$$
P(X = x_i) = \hat{y}_i \in (0, 1) \\
\sum_i \hat{y}_i = 1
$$
而对于训练结果有：
$$
P(X = x_i) = y_i \in (0, 1) \\
\sum_i y_i = 1
$$
则交叉熵定义为：
$$
C = -\sum_i \hat{y}_i \ln y_i
$$
可以证明，在 $\hat{y}_i$ 固定时，这个函数的最小值将在 $\forall i, y_i = \hat{y}_i$ 时取到（我们会发现将其求 $\exp$ 后就是一个多项分布的最大似然估计问题），这也符合损失函数的要求，也就是 $C$ 变小的过程，就是训练结果变好的过程。

而对于本题而言，单个数据显然有确定的 $\hat{y}_k = 1$，其余均为 $0$（这是由于单个训练样本的标签是确定的），因此 $C$ 的最小值就是 $0$，这也是十分利于我们的计算。

代码分析：变量、参数含义与调参

首先是一些全局变量：

double pixel[][784]; 表示存储图像像素信息的数组，其同时用来存储训练集和验证集，因此大小应该为 $\max(n, m)$，即至少为 $6000$。

int label[]; 表示读入的各图像的标签信息，因此大小为 $n$，同上。

还需要一个 int labe_tag[6]; 数组用以存储每个编号的标签对应的标签值。

float learningRate; 即为学习率 $\eta$，本题由于时间较紧，可以设置的大一些，在 $10^{-1}$ 数量级。

（然后我没看见这个变量，自己写了个 const int eta）

int maxTrainTimes; 代表最大训练次数，这个根据后面的结构酌情设置，当然理论上至少需要达到 $n$ 数量级（不然 $n$ 个训练样本都没有全被用上）。

如果采用卡时技巧，那肯定是只需要尽量向大设置即可。

int num_hidden_layer; 和 int hidden_nodes[10]; 就是表示了隐藏层的结构。

本题中由于给出的信息和任务都比较简单，应该是不需要多的隐藏层，可以考虑 $1 \sim 3$ 层。

而每层的节点数也可以慢慢尝试，根据我个人的经验，大致在几十这个数量级可能比较有效，可以参考这里，虽然可能不太靠谱。

（经过测试大概两层逐渐变小的 $20 \sim 30$ 和 $5 \sim 10$ 比较好）

然后是封装的类中成员变量：

对于隐藏层和输出层：

实际上两者的成员含义基本一致。

double* output_data; 表示本层输出的向量，即上面的 $output_m$。

delta* delta; 表示本层的误差，即 $\delta_i$。

int in_channel, out_channel; 分别表示输入节点数和输出节点数，即上一层的节点数和本层的节点数，换而言之即为上面表示的 $n$ 和 $m$（与输入的 $n, m$ 不是一个东西）。

double** weight; 和 double* bias; 表示转移矩阵 $w_{m \times n}$ 和偏差向量 $b_{n \times 1}$。

对于神经网络类：

int in_channel, out_channel; 分别表示整个网络的输入节点和输出节点，实际上就是第一个隐藏层的输入节点数和输出层的输出节点数，分别为 $28 \times 28$ 和 $l$。

同时也存储了整个隐藏层的结构。

layers 存储了隐藏层对象指针，last_layer 存储了输出层对象指针。

代码分析：函数含义与实现思路

首先是一些全局函数：

xavier_uniform() 函数用于初始化神经网络中每个节点的参数权重，其基于的原则大致是，每层的方差应该基本相等。

通过一些配合均匀分布的推导，我们可以得出：
$$
W_{j + 1} \sim U\left[-\frac{\sqrt{6}}{\sqrt{n_j + n_{j + 1}}}, \frac{\sqrt{6}}{\sqrt{n_j + n_{j + 1}}} \right]
$$
这样的分布是较为合适的，其中 $n_j$ 和 $n_{j + 1}$ 分别是上层节点数和本层节点数。

具体可以参见这里。

因此 gain 的值定义在 $1$ 左右即可。

（当然由于我们隐藏层的数量极少，所以不是特别重要）

getMaxIndex() 函数可以看出，就是用于求取概率最大的那一维的下标（也就是用于验证集的输出）。

makeOneHot() 其实就是构造一个 $\hat{y}_i$ 分布（见损失函数部分）的过程，用于计算交叉熵和损失函数。

findIndex() 用于寻找对应标签值的标签下标，与 makeOneHot() 配合使用。

然后是封装的类中成员变量：

对于隐藏层和输出层：

构造函数就是根据参数来 new 出合适长度的数组，并且对于参数数组，调用 xavier_uniform() 进行合适的初始化。

析构函数略。

隐藏层的 activate_func() 函数就是对经过仿射变换的输出数据，调用激活函数，比如我们如果选用 Sigmoid 函数：

for (int i = 0; i < out_channel; ++i)
    x[i] = 1.0 / (1.0 + exp(-x[i]));

输出层则已经实现了 softmax() 函数用以激活。

而对于 activate_func_bp() 函数则是用于反向传播时计算误差。

根据上面的分析，对于隐藏层，我们会需要用到以下参数：

void HiddenLayer::activate_func_bp(double* next_layer_delta, double** next_layer_weight, int next_in_channel, int next_out_channel);

分别含义是，下一层的 $\delta_i'$，下一层的转移矩阵，下一层的输入输出节点数。

之后只须按部就班计算即可，其中需要推导一下激活函数的导数，这里以 Sigmoid 函数为例：
$$
S(x) = \frac{1}{1 + e^{-x}} \\
\frac{dS(x)}{dx} = \frac{e^{-x}}{(1 + e^{-x})^2} = \frac{1}{1 + e^{-x}} \cdot \frac{e^{-x}}{1 + e^{-x}} = S(x) (1 - S(x))
$$
因此我们对每个节点 $i$，只须在求出下一层误差的线性组合后，乘上 output_data[i] * (1 - output_data[i]) 即可（具体见上面的误差公式）。

而输出层采用的 Softmax 函数，也可以同理：
$$
S(x_i) = \frac{e^{x_i}}{\sum\limits_{k = 1}^n e^{x_k}} \\
\frac{dS(x_i)}{dx_i} = \frac{e^{x_i} \left(\sum\limits_{k = 1}^n e^{x_k} - e^{x_i}\right)}{\left(\sum\limits_{k = 1}^n e^{x_k}\right)^2} = \frac{e^{x_i}}{\sum\limits_{k = 1}^n e^{x_k}} \cdot \frac{\sum\limits_{k = 1}^n e^{x_k} - e^{x_i}}{\sum\limits_{k = 1}^n e^{x_k}} = S(x_i) (1 - S(x_i))
$$
因此对应的 softmax_bp() 函数，也只需求出 label[i] 与 output_data[i] 的差值后，乘上 output_data[i] * (1 - output_data[i]) 即可。

而两个层的 forward() 其实都只须进行 w 和 b 数组对于 intput_data 数组的作用即可（做一次仿射变换），将结果传入 output_data 数组，再对其调用激活函数（使得变换完全非线性），即可得到最终的前向传播输出。

而对于 backward()，我们先调用对应的 _bp() 函数获取其误差值，再代入后向传播中讲的梯度下降公式（见上）计算即可。

这里我们会发现，对于此处两个激活函数的求导都只与函数值相关，因此我们只需要 output_data 数组即可得到其导数，这也是 backward 的过程并没有传入本层的输入信息的原因。

再来看神经网络类：

train() 函数就是进行单次的随机梯度下降训练，而 eval() 则是对于整体的验证集得出训练结果。

其中 train() 需要特别修改函数的参数类型为：

double NeuralNetwork::train(double* train_data, int label, int* label_tag);

并将输出层的反向传播修改为：

double loss = last_layer->backward(layers[num_hidden_layer - 1]->output_data, makeOneHot(findIndex(label, label_tag)));

这里的返回值，也就是我们之前提到的交叉熵损失函数。

最后是 main() 部分：

主程序部分的输入我就不再赘述，需要注意的是，要将 srand() 的随机种子修改，如果为了更好的判断自己模型的准确性，应该修改为一个常数而不能与时间相关，这是为了防止随机数对于程序可能造成的影响。

理论上为了实行随机梯度下降，我们还应将输入的训练集随机打乱，可以考虑使用 random_shuffle() 函数完成这一点。

最后的输出需要注意，应该是 label_tag[result[i]] 而非直接使用 result 数组（输出的是标签值而非标签下标）。

（这里不得不吐槽一点，这个代码居然在先 new 的同时，还将其赋值为 eval() 函数中 new 来的新内存，这种恶意内存泄漏真是让我难以评价，希望同学们引（hào）以（zǐ）为（wěi）戒（zhī））

代码分析：卡时技巧

虽然 OJ 上禁用了 clock() 函数，但我们可以通过估计运算次数来近似模拟时间。

这里计算的是训练时的运算次数。

假设我们的隐藏层数量为 $k$，每层节点数量为 $b_i$，则我们单次运算的数量级大约为：
$$
s = 28^2 \times b_1 + \sum_{i = 1}^{k - 1} b_{i} b_{i + 1} + b_k l
$$
当多次训练总计次数达到 $10^{9}$ 左右，我们可以选择强制停止训练。

换而言之，我们可以设置最大训练次数为 $\dfrac{10^{9}}{s}$ 左右（当然具体常数可以自己尝试）。

总结

本题本质上就是个 $l$ 分类问题，跟数算没锤子关系，纯粹是人工智能基础的学习。

虽然自己认真写一遍可能对于多层感知机、深度学习等模型的理解上会有一定帮助，但出在数算课上还是一道屑题。

建议想认真学人工智能的同学，自己选《机器学习概论》、《人工智能导论》这些课（给老师打广告.jpg），当然我自己也没学过就是（逃）。

最后的最后，这次代码细节不贴了（实际上是没有细节），有实现和理解问题建议直接私聊我。

 AI 题解