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

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

Contents

概述

题面见此处

基本要求就是实现一个简单的 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() 其实都只须进行 wb 数组对于 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),当然我自己也没学过就是(逃)

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

 

点赞 9

Comments: 4

  1. miaom说道:

    ReLU这么没牌面的吗

Add your comment