梯度下降算法说明及实现哈尔滨工业大学深圳研究生院生物计算研究中心1算法说明（1）目的假设我们有一个包含n个样本的集合D={x1，x2，…，xn}，一些标记为ω1，另一些标记为ω2，其中ω1，ω2记作y，作为样本的输出。我们希望用这些样本来确定一个判别函数gx=atx的权向量a。对于一个样本xi，如果有atxi>0就标记为ω1，如果atxi>0就标记为ω2。我们在寻找满足线性不等式组atxi>0的解时所采用的方法是：定义一个准则函数J(a)，当a是解向量时，J(a)最小。这样就将问题简化为一个标量函数的极小化问题——通常可用梯度下降法来解决。（2）原理首先从随意选择的一个权向量a(0)开始，计算梯度向量∇J(a(0))，下一个值a(1)由自a(0)向下降最陡的方向移一段距离而得到，即沿着梯度的负方向。通常a(i+1)由等式ak+1=ak-ηk∇J(a(k))计算，η是正的比例因子，或者说是用于设定步长的“学习率”，可以是较小的常数，一般手工设置，∇J(a(k))是ak的梯度。我们希望这样得到的一个权向量序列最终收敛到是J(a)极小化的解上。按照上面的梯度下降法迭代公式进行若干次迭代搜索，每次迭代的初始点取上次迭代的终点，即可使迭代点逐步逼近目标函数的极小点。其迭代的终止条件可采用点距准则或梯度准则，即当ak-ak+1<ε或||∇J(a(k))||<ε时终止。其中，∇Ja=[∂J∂a0,∂J∂a1,…,∂J∂a(n)]T。注意：∇Ja本身是一个向量，它的成员是J对每个a(i)的偏导数。我们可以从度量标准——训练误差：Ja=12x∈D(gx-y)2中得到组成这个梯度向量的分量∂J∂ai，其中g(x)是训练样例的目标输出，即预测值，每一个训练样本X都有m个属性值，Z是线性单元对训练样例的输出，即已知的训练样本的取值。则推导过程如下，假设只有一个训练样本：∂J(a)∂ai=∂∂ai12gx-y2=12∙2gx-y∂∂aigx-y=gx-y∂∂aigx-y=gx-y∂∂aia0x0+a1x1+…+amxm-yi=gx-yxi其中xi表示样本的第i个属性值。则有ai=ai-ηgx-yxi推广到有n个样本的集合时则有：ai=ai-ηj=1ngxj-yjxij（3）一些变量及规格X一个n行m列的矩阵y一个具有n列的行向量a一个具有m列的行向量xj表示第j个样本向量，是一个具有m个特征的行向量yj表示第j个样本向量的输出xij表示第j个样本的第i个特征值2算法实现步骤给定初始点a(0)∈Rn,迭代精度ε，学习率ηk。置0⟹k。计算迭代点a(k)的梯度∇J(a(k))=[∂J∂a0,∂J∂a1,…,∂J∂a(m)]T计算迭代新点ak=ak-ηk∇J(a(k))。检验是否满足迭代终止条件||ηk∇Jak||是否小于迭代精度，若小于，停止迭代，则返回最优解a，否则下一步。置k+1⟹k，返回步骤(3)进行下一次迭代计算。3算法伪代码Begininitializea,阈值ε，ηk，k0dokk+1aa-ηk∇J(a)until|ηk∇Jak|<εreturnaend4梯度下降算法应用简介训练样本集中一共有80张人脸样本，主要来自于两个不同的人，没人四是张。首先处理人脸图像数据，将其归一化，一方面一张图像累加为一行数据，灰度级处理为0-1之间，防止溢出。然后调用梯度下降算法，假设判别函数是线性的，找出最优的权向量。最后输入测试样本，同样对测试样本归一化处理，使用判别函数对人脸图像进行判别。实现步骤读入测试样本（80张人脸样本，灰度图像）。将这些图像做归一化处理，即将整个图像的数据归一化为一行，如x=123456789，归一化之后为：X=[123456789]。得到测试样本后，调用梯度下降算法，假设线性判定函数，获得最优权向量a。输入测试样本，同样做归一化处理。将测试样本带入假设的线性函数中，求出函数值。通过函数值判断测试样本的类别。输出图像。运行gradient.m文件，选择训练样本集。Figure1单击Ok键，得到测试结果，如下图所示：一共有10个测试样本，测得的值分别为：Figure2Figure3Figure4（1）徐勇教授个人主页：HYPERLINK"http://xyhomepage.web-108.com/default.html"http://xyhomepage.web-108.com/default.html（2）《模式分类》机械工业出版社、中信出版社，RichardO.Duda,PeterE.Hart,DavidG.Stork著，李宏东、姚天祥译，第五章，5.4.2梯度下降算法，183