首页 > 程序开发 > 综合编程 > 其他综合 >

《Deep Learning》(4)-数值计算

2016-09-16

机器学习算法常常需要大量的数学计算,尤其是一些需要迭代求解的算法。优化算法和解线性方程时,当这些函数涉及到实数操作时,就要在数值精度和内存两者之间做权衡了。

机器学习算法常常需要大量的数学计算,尤其是一些需要迭代求解的算法。

优化算法和解线性方程时,当这些函数涉及到实数操作时,就要在数值精度和内存两者之间做权衡了。

4.1 上溢出和下溢出(Overflow and Underflow)

使用数字计算机表示连续变量时,需要用有限的bit来表示无限的实数。这意味着,对于大部分的实数,有精度上的损失。这样的误差叫做舍入误差。舍入误差包括Underflow和Overflow。

Underflow:当数值接近0时,被舍入为0。
Overflow:当数值逼近正负无穷时,数值变为Not-A-Number(NAN)。

Softmax函数就一个要同时处理Unverflow和Overflow的函数

softmax(x)i=exp(xi)∑nj=1exp(xj)

假设xi为常数c,这时函数应该为1n。当c为负且很大时,这时会出现Underflow;当c为正且很大时,竟会出现Overflow。用线性代数处理一下z=x?max(xi),再求softmax(z)即可。

还有一个小的问题。分子的underflow可能会导致整个表达式为零。即,如果首先计算softmax函数,然后把结果传递给log函数,可能会得到?∞。可以使用同样方法避免这个问题。

在使用算法时,可能不会考虑溢出问题,因为一些底层库的作者常常已经处理好这个问题了。当时,要时刻意识到这个问题。

4.2 Poor Conditioning

Condition是指函数输入变化时,它的输出变化的快慢。输入微小变化就能引起输出很大波动的的函数,对于科学计算来说,有问题。因为数据可能存在噪声(或预处理存在噪声),噪声很大程度影响了输出。

例如函数f(x)=A?1x,其中A∈Rn×n,且有特征值,那么它的condition number 就是

maxi,jλiλj

这个比值就是幅度最大的特征值和幅度最小的特征值的比值。如果比值很大,那么矩阵的逆对输入就很敏感。

这种敏感是矩阵本身的特性,而不是求逆过程中的误差。这样的矩阵会放大预处理的误差。

4.3梯度下降最优化

大多数机器学习都会涉及到最优化;最优化是指最大化f(x)或最小化?f(x)。要最大化或最小化的函数叫做目标函数或准则;如果最小化它时,常常叫做代价函数、损失函数或误差函数。

最下滑函数,常常使用梯度下降法。但是在梯度为零的点,梯度没有为我们提供信息。梯度为零f′(x)的点,是关键点或驻点(critical points or stationary point)。梯度为零的点,可以是局部最小值,或者是局部最大值,也可能是鞍点(saddle point)。如下图:
deeplearnging04_01.jpeg

局部最小值可能不是全局最小值,全局最小才是最优。在深度学习中,优化的函数有许多局部最小值和鞍点;尤其是当优化目标函数为多维函数时。下图是一维情况的简单描述:
deeplearnging04_02.jpeg

我们优化的函数,输入可能是多维的,但输入是一维的:f:Rn&rarr;R。输入是多维时,对某一维变量求导就是偏导了??xif(x)。对函数就到得到的梯度就是一个向量了?xf(x),其中每一个元素都是偏导。<喎"https://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPtTaxLO49re9z/I8bm9icj51PC9ub2JyPqOoz/LBv6Opyc+1xLW8yv3Oqjxub2JyPj8/JmFscGhhO2YoeCsmYWxwaGE7dSk9dVQ/eGYoeCk8L25vYnI+oaM8L3A+DQo8cD7X7tChu688bm9icj5mPC9ub2JyPr7NysfV0rW90ru49re9z/KjrNTa1eK49re9z/LJz8/CvbXX7r/soaPKtbzKyc+jrMzdtsjKx8nPyf3X7r/stcS3vc/yo6zG5Le0t73P8r7NysfPwr211+6/7LXEt73P8qGj0djXxczdtsi3tLe9z/LPwr21tcS3vbeoo6y90Nf21+7L2c/CvbW3qKOoc3RlZXBlc3QgZGVzY2VudKOpu/LM3bbIz8K9taOoZ3JhZGllbnQgZGVzY2VudKOpoaM8L3A+DQo8cD7X7svZz8K9tbeoyrnTw8jnz8KjujwvcD4NCjxwPjxub2JyPngmcHJpbWU7PXg/Pz94Zih4KTwvbm9icj48L3A+DQo8cD7V4sDvPG5vYnI+Pzwvbm9icj690Nf20afPsMLKo6zL/Na4yr7U2s/CvbW5/bPM1tC1xLK9s6SjrL/J0tTJ6NbDsrvNrLXE1rWho9fuwffQ0LXE1/a3qMrHsNHL/Mno1sPOqrOjyv2ho9PQyrGjrLu508PNqLn9yejWw7K9s6SjrLfA1rnM3bbIz/vKp6Gju7nT0NK71tbJ6NbDsr2zpLXEt723qKOszai5/bzGy+Oyu82sPG5vYnI+Pzwvbm9icj7KsaOsxL+x6rqvyv08bm9icj5mKHg/Pz94Zih4KSk8L25vYnI+tcS089Cho6zAtNGh1PHX7tPFtcTRp8+wwsqju9Xi1tay38LUvdDX9s/f0NTL0cv3oaM8L3A+DQo8cD7M3bbIz8K9tda7xNzTw9TawazQ+L/VvOSho7WrysfG5Mu8z+ujus2ouf3Su7K9sr3Sxravo6zV0rW91+7TxbXjo6y/ydLU08O1vcDryaK/1bzkoaM8L3A+DQo8aDMgaWQ9"431-beyond-the-gradient雅克比矩阵和海森矩阵">4.3.1 Beyond the Gradient:雅克比矩阵和海森矩阵

对于输入和输出都是多维情况,这时求其偏导,可以得到雅克比矩阵(Jacobian Matrices)。函数f:Rm&rarr;Rn,那么雅克比矩阵J&isin;Rn&times;m,矩阵中的每个变量

Ji,j=??xjf(x)i

对于函数f:Rn&rarr;R,求它导数的导数,即二阶导数,可以得到海森矩阵。二阶导数告诉我们一阶导数随输入变量变化而变化的情况。二阶导数很重要,它可以告诉我们基于一阶导数梯度步长,将会引起多大提高。可以把二阶导数想象为衡量弯曲。例如,有一个二次函数,如果它二阶导数为零,那么它是一条直线,没有弯曲。假设梯度为1,如果二阶导数为负,那么其开口向下,函数f(x)下降幅度大于?;如果二阶导数为正,那么其下降小于步长。如下图:

deeplearning04_03.jpg

二阶导数定义的矩阵,叫做海森矩阵:

H(f)(f)i,j=?2?xi?xjf(x)

求导符合交换律,即:

H(f)(f)i,j=?2?xj?xif(x)

即海森矩阵是对称矩阵Hi,j=Hj,i。海森矩阵是对称的实数矩阵,可以分解为特征值和特征向量,且特征值为实数。二阶微分,在某一方向d表示为dTHd,其中dH的单位特征向量,在此方向上的值为特征向量对应的特征值。对于其他的方向,是单位特征向量的加权和。最大的特征值对应最大二阶导数,最小特征值对应最小二阶导数。

二阶导数的方向可以告诉我们梯度下降算法下降的幅度。用二阶泰勒级数在x(0)处展开目标函数可以得到:
f(x)&asymp;f(x(0))+(x?x(0))Tg+12(x?x(0))TH(x?x(0))(x?x(0))

这里g是梯度,H是海森矩阵。如果学习率为?是学习率用x(0)??g代替x,可以得到:

f(x(0)??g)&asymp;f(x(0))??gTg+12?2gTHg

使用梯度下降算法,步长为 ?时,下降大小为??gTg+12?2gTHg。当后面一项比较大时,目标函数可能没有变小;当gTHg为负数或为零时,学习率为任何值,都会下降。在使用泰勒级数时,如果?比较大时,二项展开精度可能就不高。如果gTHg为正数,那么最佳学习率为

??=gTggTHg

最坏情况下,当gH的最大特征值对应的特征向量平行时,最佳步长为1&lambda;max

二阶导数可以判断关键是是局部最小、局部最大、鞍点。关键点处f&prime;(x)=0;如果f&prime;&prime;(x)>0,意味着如果f&prime;(x)向右移动大于零,向左移动小于零,即f&prime;(x??)<0,f&prime;(x+?)>0f^{&lsquo;}(x-\epsilon)<0f^{&lsquo;}(x-\epsilon)<0f^{&lsquo;}(x-\epsilon)<0,可以得到此处为局部最小值。同理当f&prime;(x)=0,f&prime;&prime;(x)<0时,此处为局部最大值。当f&prime;(x)=0,f&prime;&prime;(x)=0,这时不能得到确切的结论,此时x可能为鞍点,或一段平坦区域。

对于多维情况,同一点不同方向导数不同。海森矩阵的condition number衡量二阶导数变化情况,如果海森矩阵的condition number是poor的,那么梯度下降性能不好。因为在某一点的一个方向,梯度可能下降很快,但是在另一个方向,梯度下降很慢;这时很难选择一个全局的学习率。如下图所示:

deeplearning04_04.jpg
在上图中,方向[1,1]上的弯曲率最大,方向[1,-1]上的弯曲率最小。红色的线是梯度下降时,行走的路线。可以看到,来回走动,浪费很多步。

可以使用从海森矩阵中得到的信息来指导搜索。最简单的方法是牛顿法。牛顿法是基于二阶导数的泰勒展开的:

f(x)&asymp;f(x(0))+(x?x(0))Tg+12(x?x(0))TH(x?x(0))(x?x(0))

对于关键点,求解函数,得到

x?=x(0)?H(f)(x(0))?1?xf(x(0))

当函数f是二次时,只需要一步即可跳到最优解。当函数不是正定的,但是可以近似为二次正定的,可以迭代使用上面公式,这样比梯度下降法要快。这在局部最小值附近时是个有用的特性,但是牛顿法只能在局部最小值附近来近似。

梯度下降是一阶导数的优化算法,牛顿法是二阶导数的最优化算法。这些最优化算法可以用到大多数的深度学习应用中,但是不确保一定有效。因为深度学习中,用到的函数十分复杂。有时需要给函数加上Lipschitz连续限制。Lipschitz连续函数为:

?x,?y,"f(x)?f(y)|&le;?||x?y||2

其中?是Lipschitz限制。这时一个很有用的特性,因为输入上的微小变量,将会引起输出上的微小变化。Lipschitz限制是一个弱限制,深度学习中的许多问题可以经过微小修改获取Lipschitz连续性。

在优化领域,最成功的领域是凸优化。凸优化通过许多强限制来加以保证。凸优化只能用来解决凸函数,海森矩阵为半正定的函数才是凸函数;这样的函数没有鞍点,局部最小值即为全局最小值。但是深度学习中,目标函数往往不是凸函数。凸函数优化只能用作深度学习的一个分支。

4.4 受限的优化问题

有时我们要在限制输入满足x一定条件情况来,来最小化目标函数。这就是受限的优化问题。

常常用的一种方法是把受限条件考虑到目标函数中,然后再来优化新的目标函数。

一种复杂的方法,是把受限问题转换为不受限的问题来解决。

Karush-Kuhn-Tucker(KKT)方法提供了解决受限问题的一种通用方法。这里介绍一种新的方法,拉格朗日乘子法或拉格朗日函数。

在定义拉格朗日函数前,先定义受限集合的描述,假设受限约束有m个等式和n个不等式描述。受限集合S={x|?i,g(i)=0and?j,h(j)&le;0}。为每个约束引入新的变量&lambda;i,&alpha;j,它们叫做KKT乘子,拉格朗日函数定义如下:

L(x,&lambda;,&alpha;)=f(x)+&sum;i&lambda;ig(i)(x)+&sum;j&alpha;jh(j)(x)

这样就可以用不受限的优化问题解决受限的优化问题。注意到只有存在可行点,那么f(x)就不能有无穷大值点,那么

minxmax&lambda;max&alpha;,&alpha;&ge;0L(x,&lambda;,&alpha;)

minx&isin;Sf(x)

有相同的优化目标和结果集。这时因为满足

max&lambda;max&alpha;,&alpha;&ge;0L(x,&lambda;,&alpha;)=f(x)

违反

max&lambda;max&alpha;,&alpha;&ge;0L(x,&lambda;,&alpha;)=&infin;

这条性质确保在可行性点不变情况下,非可行性点不会得到优化。

不等式的约束很有趣。如果h(i)(x?)=0,那么这个不等式就是激活的。否则,这个不等式就是没有激活的。如果一个约束没有激活,那么使用这个约束得到的解,至少是不使用这个约束时,问题的局部解。没有激活的约束也会排除一些解。例如一个凸优化问题,没有约束时,它的解的范围是全局任何点;也可以使用一些约束把它解的范围约束到一个集合范围内。但是在收敛处的点,不管约束有没有激活,它都是个stationary point。因为没有激活的约束h(i)是负值,那么对于变形后的目标函数minxmax&lambda;max&alpha;,&alpha;&ge;0L(x,&lambda;,&alpha;),将会有&alpha;i=0,因此可以得到&alpha;h(x)=0,即约束&alpha;i&ge;0h(i)(x)&le;0中,至少有一个是激活的。

泛化后的拉格朗日梯度为零,对于x约束和KKT乘数都必须满足,且&alpha;⊙h(x)=0,这些约束叫做KKT条件。

4.5例子:线性最小平方

要最小化下面目标函数
f(x)=12||Ax?b||22

第一步,求得梯度

?xf(x)=AT(Ax?b)=ATAx?ATb

使用梯度下降,按照以下步骤

1、设置步长和容忍方差&delta;
while||ATAx?ATb||2>&delta;do
x&larr;x??(ATAx?ATb)
end while

也可以使用牛顿法求解,因为函数是二次的,可以一步得到全局最优解。

如果给输入加上约束xTx&le;1,得到拉格朗日函数

L(x,&lambda;)=f(x)+&lambda;(xTx?1)

有约束问题变为无约束问题

minxmax&lambda;,&lambda;&ge;0L(x,&lambda;)

朗格朗日函数对x求导,得到

ATAx?ATb+2&lambda;x=0

得到的解的形式为:

x=(ATA+2&lambda;I)?1ATb

&lambda;幅度必须满足约束。对它求导

??&lambda;L(x,&lambda;)=xTx?1

x范数大于1时,上面导数为正;增大&lambda;拉格朗日函数值随之增大。因为xTx的系数增大,所以xTx将会变小(因为我们在最小化朗格朗日函数)。如此重复,直到&lambda;导数为零。

相关文章
最新文章
热点推荐