Deep Learning 0.3 数值计算

Deep Learning 0.3 数值计算

机器学习算法需要通过迭代过程更新解的估计值来解决数学问题,而不是通过解析过程推导出公式来提供正确解

上溢和下溢

计算机中我们需要通过有限数量的位模式来表示无限多的实数,因此总会引入一些近似误差。最小化舍入误差的累积可能会导致算法的失效

下溢指接近零的数被四舍五入为零,而上溢指大量级的数被近似为无穷。必须对上溢和下溢进行数值稳定的一个例子是softmax函数,它经常用于预测与Multinoulli分布相关联的概率

softmax(x)i=exp(xi)j=1nexp(xi)

当所有的xi都等于某个常数c时,如果c是很小的负数,exp(c)就会下溢。这意味着softmax函数的分母会变成0,如果c是非常大的正数,exp(c)就会上溢,这两个困难能通过计算softmax(xmaxixi)

这样exp的最大参数为0,排除了上溢的可能性,同样分母中至少有一个值为1的项,排除了分母下溢的可能性。

病态条件

条件数是指函数相对于输入的微小变化而变化的快慢程度,输入被轻微扰动而迅速改变的函数可能会引发问题,因为舍入误差可能导致巨大的变化

考虑函数f(x)=A1x,当A具有特征值分解时,其条件数为maxi,j|λiλj|

当该数很大时,矩阵求逆对输入的误差特别敏感

基于梯度的优化方法

优化指的是改变x以最小化或最大化某个函数的任务

我们把要最小化或最大化多的函数称为目标函数(objective function)或准则(criterion)。当我们对其进行最小化时,也把它称为代价函数、损失函数或误差函数,这个输出量必须是一维的(标量)

导数对于最小化一个函数很有用,我们可以将函数向导数的反方向移动一小步来减小f(x)

f(x)=0时,称为临界点或驻点,包括极小值点、极大值点和鞍点

针对具有多维输入的函数,需要用到偏导数(partial derivative),衡量点x\mathbf{x}处只有xix_i增加时函数的值如何变化。梯度时相对一个向量求导的函数,函数的梯度时包含所有偏导数的向量,记为Δxf(x)。在多维情况下,临界点是梯度中所有元素为零的点

u方向的方向导数(directional derivative)是函数在u\mathbf{u}方向的斜率,方向导数是函数f(x+αu)关于α的导数,αf(x+αu)=uΔxf(x)

为了最小化f,我们希望找到使它下降最快的方向,计算方向 导数

minuΔxf(x)

这个值在u\mathbf{u}与梯度方向相反时取得最小,这被称为最速下降法(method of steepest descent)或梯度下降(gradient descent),最速下降建议新的点为

x=xϵΔxf(x)

其中ϵ称为学习率(learning rate),是一个确定步长大小的正标量,通常选择一个小常数。最速下降在梯度的每一个元素为零时收敛。

梯度下降的概念可以推广到离散空间,称为爬山算法

Jacobian和Hessian矩阵

有时需要计算输入和输出都为向量的函数的所有偏导数,包含所有这样偏导数的矩阵称为Jacobian矩阵。如果有一个函数f:RmRn,f的Jacobian矩阵JRn×m定义为Ji,j=xjf(x)i

有时我们也对二阶导数感兴趣,如果二阶导数是正的,函数将比梯度下降慢,如果二阶导数是正的,函数将比梯度下降快

当函数具有多维输入时,二阶导数也有很多,可以合并成一个矩阵,称为Hessian矩阵

H(f)(x)i,j=2xixjf(x)

Hessian矩阵是一个对称矩阵,因为在偏导连续的点微分算子可以交换,因此我们可以将其分解成一组实特征值和一组特征向量的正交基。在特定方向d上的二阶导数可以写成dHd。当d\mathbf{d}H的一个特征向量时,这个方向的二阶导数就是对应的特征值,对于其他的方向,方向二阶导数是所有特征值的加权平均,权重在0和1之间,与方向夹角越小的特征向量权重越大。最大特征值确定最大二阶导数,最小特征值确定最小二阶导数

我们可以通过一个二阶导数预期一个梯度下降步骤能表现地多好,我们在当前点处做函数的近似二阶泰勒级数

f(x)f(x(0))+(xx(0))g+12(xx(0))H(xx(0))

其中有三项,函数的原始值,函数斜率导致的预期改善和函数曲率导致的校正。当最后一项的值为零或负时,梯度下降将永远使函数值下降。通过计算可得,最优步长为

ϵ*=gggtHg

在多维情况下我们需要检测函数的所有二阶导数,利用Hessian的特征值分解,将二阶导数测试扩展到多维情况。在临界点处,当Hessian矩阵是正定的,则该临界点是局部极小值点,如果是负定的,则是局部极大值点,如果有正有负则是一个鞍点

Hessian额条件数衡量二阶导数的变化范围,当Hessian的条件数很差时,梯度下降法也会表现地很差,这是因为一个方向上的导数增加地很快,而另一个方向上增加地很慢,病态条件也限制了步长,因为防止在某个方向上冲过最小而向具有较强正曲率的方向上升。

我们可以使用Hessian矩阵的信息来知道搜索,其中最简单的方法时牛顿法(Newton’s method),牛顿法基于泰勒展开来近似某点附近的函数值

f(x)f(x0)+(xx0)tΔxf(x0)+12(xx0)tH(f)(x0)(xx0)

通过计算可以得到函数的临界点

x*=x0H(f)(x0)1Δxf(x0)

如果f是一个正定二次函数,牛顿法只要应用一次就可以直接跳到函数的最小点,但是牛顿法在鞍点附近时有害的,只有当附近的临界点时最小点时牛顿法才适用,而梯度下降不会被吸引到鞍点

仅使用梯度信息的优化算法称为一阶优化算法,如梯度下降,使用Hessian矩阵的优化算法称为二阶最优化算法,如牛顿法

在深度学习的背景下,限制函数满足Lipschitz连续,其变化速度以Lipschitz常数为界

x,y,|f(x)f(y)|xy2

这个属性导致输入的微小变化将使输出只产生微小的变化

约束优化

有时希望在自变量的某些集合中找到函数的最大值或最小值,这被称为约束优化(constrained optimization)

Karush-Kuhn_Tucker(KKT)方法使针对约束优化非常通用的解决方案,我们引入一个广义Lagrangian函数的新函数。我们希望通过m和函数和n个约束条件来描述可行域,其中g称为等式约束,h称为不等式约束

定义广义Lagrangian

L(x,λ,α)=f(x)+iλig(i)(x)+jαjh(j)(x)

那么可以通过优化无约束的广义Lagrangian解决约束最小化问题,只要存在至少一个可行点且函数值不允许无穷,那么

minxmaxλmaxα,α0L(x,λ,α)

minxSf(x)

是等价的,这是因为当约束满足时,前者的优化函数和原函数相等,约束不满足时,它等于无穷

Karush-Kuhn_Tucker条件是确定一个点是最优点的必要条件,但不一定是充分条件,这些条件是

  • 广义Lagrangian的梯度为零
  • 所有关于x\mathbf{x}和KKT乘子的约束都满足
  • 不等式约束显示的“互补松弛性”:αh(x)=0

线性最小二乘

假设我们希望找到最小化下式的x\mathbf{x}

f(x)=12Axb2

首先我们计算梯度

Δxf(x)=A(Axb)=AAxAb

然后我们可以设置很小的步长进行梯度下降

我们也可以用牛顿法解决这个问题,因为真实函数是二次的,牛顿法可以得到精确近似

现在假设我们希望最小化这个函数,但受xx1的约束,我们引入Lagrangian

L(x,λ)=f(x)+λ(xx1)

现在解决以下问题

minxmaxλ,λ0L(x,λ)

我们可以用Moore-Penrose伪逆,找到无约束最小二乘问题的最小范数解,如果这一点是可行的,那么也是约束问题的解,否则必须找到约束是活跃的解。对Lagrangian微分,得到

AAxAb+2λx=0

解为

x=(AA+2λI)1Ab

λ的选择必须使结果服从约束,我们可以关于λ进行梯度上升找到这个值,为了做到这一点

λL(x,λ)=xx1

x\mathbf{x}的范数超过1时,这个导数是正的,所以为了跟随导数上坡并相对λ增加Lagrangian,我们需要增加λ。这个过程将一直持续到x\mathbf{x}具有正确的范数,并且关于λ的导数是0

发表评论