![](https://wzf2000.top/wp-content/uploads/二次元/17.png)
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+e−x
类似的也比如 tanhx 函数等。
我们会发现,这些函数都具有值域落在某个小区间内的特点。
通过这样若干层的放射变换以及激活函数的作用,我们最终会在输出层得到 l 个 (0,1) 范围的结果,但这并不是我们想要的一个概率分布,所以我们可以通过 Softmax 函数。
设有 n 个数 x1,⋯,xn,则:
yi=softmax(xi)=exin∑k=1exk=exi−cn∑k=1exk−c
显然有:
n∑i=1yi=1,yi>0
通过上面的定义我们会发现,此函数对于给定的样本只有相对意义,也就是说样本的整体平移并不会影响函数的结果。
而为了防止指数函数的过大导致溢出,我们可以让所有的 xi 都减去 nmaxk=1xk,来保证数值运算的可靠性。
那么对输出层得出的 l 个结果作此变换,我们即可得到一个可能较为合理的概率分布。
最后的验证时,我们也只需认为,概率最大值即为最终的识别结果(最大似然)。
到这里,我们完成了对整个模型的架构分析,但是我们仍没有给出构建或者说训练这套模型的方法。
算法分析:后向传播与梯度下降
考虑这么一个问题,对于给定一个初始估计的参数分布 X(x;t1,t2,⋯,tn),其中参数 t1,⋯,tn 给定,我们已知在 x=x0 点,其实际值为 z0,X 分布的估计值为 y0。
那么这意味着在此点,此估计在 x=x0 点的误差为 δ=z0−y0,那么在 x=x0 固定的情况下,我们会希望对应的 t1,⋯,tn 向 δ 的反方向移动。
具体来说,给定一个比例值(学习率)η,我们可以期待(对于分布整体而言,就是向梯度方向下降误差的一定比例):
t′i=ti+η⋅δ∂X∂ti
这样得到的新参数 t′1,⋯,t′n 对应的 X(x;t′1,⋯,t′n) 相比初始的参数分布,可能有更好的拟合效果。
这也就是一般的梯度下降。
对于(某种意义下)随机选取的样本 x,也就是这道题中的随机梯度下降。
在此题中,对于单层(包括隐藏层与输出层)而言,我们的参数就是 w 矩阵和 b 偏差向量,而分布就是:
X(inputn×1;wm×n,bm×1)=S(wm×n×inputn×1+bm×1)
其中 S 为激活函数,这里我们假设为 Sigmoid 函数或者 Softmax 函数。
那么就可以根据求导的链式法则得到,对于 wi,j:
w′i,j−wi,j=η⋅δi⋅inputjdS(x)dx
对于 bi:
b′i−bi=η⋅δidS(x)dx
这时你就会发现,此处表示与题面中的提示基本一致了。
而此处单个节点的误差 δi,则容易想到通过其后继节点的误差表示。
具体来说,假设其有 m 个后继节点,我们有:
δi=m∑j=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;
即为学习率 η,本题由于时间较紧,可以设置的大一些,在 10−1 数量级。
(然后我没看见这个变量,自己写了个 const int eta
)
int maxTrainTimes;
代表最大训练次数,这个根据后面的结构酌情设置,当然理论上至少需要达到 n 数量级(不然 n 个训练样本都没有全被用上)。
如果采用卡时技巧,那肯定是只需要尽量向大设置即可。
int num_hidden_layer;
和 int hidden_nodes[10];
就是表示了隐藏层的结构。
本题中由于给出的信息和任务都比较简单,应该是不需要多的隐藏层,可以考虑 1∼3 层。
而每层的节点数也可以慢慢尝试,根据我个人的经验,大致在几十这个数量级可能比较有效,可以参考这里,虽然可能不太靠谱。
(经过测试大概两层逐渐变小的 20∼30 和 5∼10 比较好)
然后是封装的类中成员变量:
对于隐藏层和输出层:
实际上两者的成员含义基本一致。
double* output_data;
表示本层输出的向量,即上面的 outputm。
delta* delta;
表示本层的误差,即 δi。
int in_channel, out_channel;
分别表示输入节点数和输出节点数,即上一层的节点数和本层的节点数,换而言之即为上面表示的 n 和 m(与输入的 n,m 不是一个东西)。
double** weight;
和 double* bias;
表示转移矩阵 wm×n 和偏差向量 bn×1。
对于神经网络类:
int in_channel, out_channel;
分别表示整个网络的输入节点和输出节点,实际上就是第一个隐藏层的输入节点数和输出层的输出节点数,分别为 28×28 和 l。
同时也存储了整个隐藏层的结构。
layers
存储了隐藏层对象指针,last_layer
存储了输出层对象指针。
代码分析:函数含义与实现思路
首先是一些全局函数:
xavier_uniform()
函数用于初始化神经网络中每个节点的参数权重,其基于的原则大致是,每层的方差应该基本相等。
通过一些配合均匀分布的推导,我们可以得出:
Wj+1∼U[−√6√nj+nj+1,√6√nj+nj+1]
这样的分布是较为合适的,其中 nj 和 nj+1 分别是上层节点数和本层节点数。
具体可以参见这里。
因此 gain
的值定义在 1 左右即可。
(当然由于我们隐藏层的数量极少,所以不是特别重要)
getMaxIndex()
函数可以看出,就是用于求取概率最大的那一维的下标(也就是用于验证集的输出)。
makeOneHot()
其实就是构造一个 ˆyi 分布(见损失函数部分)的过程,用于计算交叉熵和损失函数。
findIndex()
用于寻找对应标签值的标签下标,与 makeOneHot()
配合使用。
然后是封装的类中成员变量:
对于隐藏层和输出层:
构造函数就是根据参数来 new
出合适长度的数组,并且对于参数数组,调用 xavier_uniform()
进行合适的初始化。
析构函数略。
隐藏层的 activate_func()
函数就是对经过仿射变换的输出数据,调用激活函数,比如我们如果选用 Sigmoid 函数:
输出层则已经实现了 softmax()
函数用以激活。
而对于 activate_func_bp()
函数则是用于反向传播时计算误差。
根据上面的分析,对于隐藏层,我们会需要用到以下参数:
分别含义是,下一层的 δ′i,下一层的转移矩阵,下一层的输入输出节点数。
之后只须按部就班计算即可,其中需要推导一下激活函数的导数,这里以 Sigmoid 函数为例:
S(x)=11+e−xdS(x)dx=e−x(1+e−x)2=11+e−x⋅e−x1+e−x=S(x)(1−S(x))
因此我们对每个节点 i,只须在求出下一层误差的线性组合后,乘上
output_data[i] * (1 - output_data[i])
即可(具体见上面的误差公式)。而输出层采用的 Softmax 函数,也可以同理:
S(xi)=exin∑k=1exkdS(xi)dxi=exi(n∑k=1exk−exi)(n∑k=1exk)2=exin∑k=1exk⋅n∑k=1exk−exin∑k=1exk=S(xi)(1−S(xi))
因此对应的
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()
需要特别修改函数的参数类型为:
并将输出层的反向传播修改为:
这里的返回值,也就是我们之前提到的交叉熵损失函数。
最后是 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+k−1∑i=1bibi+1+bkl
当多次训练总计次数达到 109 左右,我们可以选择强制停止训练。
换而言之,我们可以设置最大训练次数为 109s 左右(当然具体常数可以自己尝试)。
总结
本题本质上就是个 l 分类问题,跟数算没锤子关系,纯粹是人工智能基础的学习。
虽然自己认真写一遍可能对于多层感知机、深度学习等模型的理解上会有一定帮助,但出在数算课上还是一道屑题。
建议想认真学人工智能的同学,自己选《机器学习概论》、《人工智能导论》这些课(给老师打广告.jpg),当然我自己也没学过就是(逃)。
最后的最后,这次代码细节不贴了(实际上是没有细节),有实现和理解问题建议直接私聊我。
Comments: 4
ReLU这么没牌面的吗
因为我确实没用过。^_^
说起来,其实这题的Xavier初始化不太适用于ReLU激活函数,虽然就一两层隐藏层不一定导致梯度爆炸、梯度消失,不过还是尽量Sigmoid和tanh比较好。
用ReLU 一层隐藏层不是爆炸就是消失TAT