Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

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

Contents [hide]

概述

题面见此处

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

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

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

(当然这个算不算算法另论)

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

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

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

本题中,每一层我们都限定其为线性层,换而言之,对于一个输入向量 inputn×1,我们通过一个转移矩阵 wm×n 和一个偏差向量 bm×1 得到:
outputm×1=wm×n×inputn×1+bm×1


但是通过上述仿射变换,得到的输出可能在一个比较大的范围内波动,我们希望将其限制在 (0,1) 中,则需要引入一个激活函数

比如 Sigmoid 函数
S(x)=11+ex


类似的也比如 tanhx 函数等。

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

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

设有 n 个数 x1,,xn,则:
yi=softmax(xi)=exink=1exk=exicnk=1exkc


显然有:
ni=1yi=1,yi>0

通过上面的定义我们会发现,此函数对于给定的样本只有相对意义,也就是说样本的整体平移并不会影响函数的结果

而为了防止指数函数的过大导致溢出,我们可以让所有的 xi 都减去 nmaxk=1xk,来保证数值运算的可靠性。

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

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

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

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

考虑这么一个问题,对于给定一个初始估计的参数分布 X(x;t1,t2,,tn),其中参数 t1,,tn 给定,我们已知在 x=x0 点,其实际值为 z0X 分布的估计值为 y0

那么这意味着在此点,此估计在 x=x0 点的误差为 δ=z0y0,那么在 x=x0 固定的情况下,我们会希望对应的 t1,,tnδ 的反方向移动。

具体来说,给定一个比例值(学习率)η,我们可以期待(对于分布整体而言,就是向梯度方向下降误差的一定比例):
ti=ti+ηδXti


这样得到的新参数 t1,,tn 对应的 X(x;t1,,tn) 相比初始的参数分布,可能有更好的拟合效果。

这也就是一般的梯度下降

对于(某种意义下)随机选取的样本 x,也就是这道题中的随机梯度下降

在此题中,对于单层(包括隐藏层与输出层)而言,我们的参数就是 w 矩阵和 b 偏差向量,而分布就是:
X(inputn×1;wm×n,bm×1)=S(wm×n×inputn×1+bm×1)


其中 S 为激活函数,这里我们假设为 Sigmoid 函数或者 Softmax 函数。

那么就可以根据求导的链式法则得到,对于 wi,j
wi,jwi,j=ηδiinputjdS(x)dx


对于 bi
bibi=ηδidS(x)dx

这时你就会发现,此处表示与题面中的提示基本一致了。

而此处单个节点的误差 δi,则容易想到通过其后继节点的误差表示。

具体来说,假设其有 m 个后继节点,我们有:
δi=mj=1wj,iδj

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

算法分析:损失函数

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

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

具体来说,我们假设实际分布为:
P(X=xi)=ˆyi(0,1)iˆyi=1


而对于训练结果有:
P(X=xi)=yi(0,1)iyi=1

则交叉熵定义为:
C=iˆyilnyi

可以证明,在 ˆyi 固定时,这个函数的最小值将在 i,yi=ˆyi 时取到(我们会发现将其求 exp 后就是一个多项分布的最大似然估计问题),这也符合损失函数的要求,也就是 C 变小的过程,就是训练结果变好的过程。

而对于本题而言,单个数据显然有确定的 ˆyk=1,其余均为 0(这是由于单个训练样本的标签是确定的),因此 C 的最小值就是 0,这也是十分利于我们的计算。

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

首先是一些全局变量

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

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

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

float learningRate; 即为学习率 η,本题由于时间较紧,可以设置的大一些,在 101 数量级。

(然后我没看见这个变量,自己写了个 const int eta

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

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

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

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

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

(经过测试大概两层逐渐变小的 2030510 比较好)

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

对于隐藏层和输出层

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

double* output_data; 表示本层输出的向量,即上面的 outputm

delta* delta; 表示本层的误差,即 δi

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

double** weight;double* bias; 表示转移矩阵 wm×n 和偏差向量 bn×1

对于神经网络类

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

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

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

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

首先是一些全局函数

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

通过一些配合均匀分布的推导,我们可以得出:
Wj+1U[6nj+nj+1,6nj+nj+1]


这样的分布是较为合适的,其中 njnj+1 分别是上层节点数和本层节点数。

具体可以参见这里

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

(当然由于我们隐藏层的数量极少,所以不是特别重要)

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

makeOneHot() 其实就是构造一个 ˆyi 分布(见损失函数部分)的过程,用于计算交叉熵和损失函数。

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]));
C++

输出层则已经实现了 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);
C++

分别含义是,下一层的 δi,下一层的转移矩阵,下一层的输入输出节点数。

之后只须按部就班计算即可,其中需要推导一下激活函数的导数,这里以 Sigmoid 函数为例:
S(x)=11+exdS(x)dx=ex(1+ex)2=11+exex1+ex=S(x)(1S(x))


因此我们对每个节点 i,只须在求出下一层误差的线性组合后,乘上 output_data[i] * (1 - output_data[i]) 即可(具体见上面的误差公式)。

而输出层采用的 Softmax 函数,也可以同理:
S(xi)=exink=1exkdS(xi)dxi=exi(nk=1exkexi)(nk=1exk)2=exink=1exknk=1exkexink=1exk=S(xi)(1S(xi))


因此对应的 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);
C++

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

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

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

最后是 main() 部分

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

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

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

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

代码分析:卡时技巧

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

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

假设我们的隐藏层数量为 k,每层节点数量为 bi,则我们单次运算的数量级大约为:
s=282×b1+k1i=1bibi+1+bkl


当多次训练总计次数达到 109 左右,我们可以选择强制停止训练。

换而言之,我们可以设置最大训练次数为 109s 左右(当然具体常数可以自己尝试)。

总结

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

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

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

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

 

点赞 9

Comments: 4

  1. miaom说道:

    ReLU这么没牌面的吗

Add your comment