花书第一谈之数值计算

花书第一谈之数值计算

0.导语

今天开刷花书第四章：数值计算。

这一章主要讲的是：机器学习的一些问题，有一部分可以通过数学推导的方式直接得到用公式表达的解析解，但对绝大多数的问题来说，解析解是不存在的，需要使用迭代更新的方法求数值解。然而实数的精度是无限的，而计算机能够表达的精度是有限的，这就涉及到许多数值计算方法的问题。因此机器学习中需要大量的数值运算，通常指的是迭代更新求解数学问题。常见的操作包括优化算法和线性方程组的求解。

1.上溢和下溢

• 上溢

当大数量级的数被近似为+∞或−∞时，进一步的运算容易导致这些无限值为非数字。

• 下溢

由于计算机进行数值计算时精度有限，下溢是在四舍五入为零时发生。例如：当零做除数时，会返回非数值，对零取对数则会得到−∞。

对上溢和下溢需要进行数值稳定。例如softnax函数：

若xi是都是很小的负数，exp(xi)会发生下溢，分母会变为0，则softmax函数值变为0。当xi是很大的正数，exp(xi)会发生上溢，同样会导致结果未定义。这两种情况都可以通过

来解决。这样子解决保证了分子exp最大参数时为0，避免了上溢，，同样分母至少有一个值为1的项，排除了下溢。

但是还有一个小问题：分子中的下溢仍然可以导致整体表达式被计算为零，比如计算log(softmax(x))，若传递的softmax(x)下溢为0，则log后则被错误的得到−∞。因此必须实现一个单独的函数，并以数值稳定的方式计算log softmax。

2.病态条件

条件数用于表征当输入发生微小变化时，函数变化的快慢程度。

考虑函数：

具有特征分解时，条件数为：

条件数较大时，求逆对于输入误差特别敏感。

这是矩阵本身的特性，与计算机精度无关。

3.基于梯度的优化方法

3.1 基本概念

优化是指通过改变x来最大化或最小化函数f(x)。

在深度学习中，通常都是用最小化函数拉进行优化，对于最大化任务则可以通过最小化−f(x)来完成。 表示为：

而f(x)称为目标函数，或者准则，或者损失函数，再或者代价函数，或误差函数。

3.2 梯度下降算法

对于函数 y=f(x) ，我们通常用 f'(x) 或

来表示其导数。导数代表了f(x)在x处的斜率，即假如我们将x改变一个小量

则

通过上述我们知道，导数告诉我们如何更改x来微调地改善y。

梯度下降算法：我们想要寻找f(x)的最小值，假设我们初始位置是 x ，那我们下一次想要找的新的x的位置为

比如对于一个简单的二次函数

其导数为 f'(x)=x , 在x>0时，f'(x)也大于零，所以新的位置应往左边走，使f(x)更小，对于x<0时，f'(x)小于零，因此新的位置应往右边走，最终我们会得到在x=0时有最小值f(x)=0。

我们发现f(x')与f(x)的值相同，这个点称作临界点(critical point)，它可能是局域最大点(local maximum)如果f(x)比其它周围的值都高，也可能是局域最小点(local minimum)如果f(x)比其他周围的值都低，也可能是鞍点(saddle point)即既不是局域极大点也不是极小点。

矢量导数，称作梯度(gradient)。假设我们有函数

为f(x)在矢量x所在点相对于xi坐标的f(x)的变化率，我们可以用一个矢量来表示相对于所有坐标的导数，标记为

。而梯度下降算法的公式就可以表示为

，其中 是学习率(learning rate)，表示了每次步进的幅度。通常我们将其选为一个较小的常数，但直观上讲，当初始时我们可能离极值点比较远，我们可以用比较大的学习率，而接近于极值点时我们需要较小的学习率否则f(x)就可能来回波动而收敛很慢。

3.3 梯度之上：雅可比和海森矩阵

什么是雅克比矩阵？

有的时候我们的映射函数可能输入和输出均是矢量，即

，这时候为表示所有输出与输入各坐标的偏导数，我们就需要雅可比矩阵(Jacobian matrix)，

,定义为：

什么是海森矩阵？

有的时候我们可能还需要求某一个函数的二阶导数，对于

，其对于xj求偏导后再对xi求偏导可以表示为

,对于所有的i,j的偏导数的组合，我们可以用海森矩阵(Hessian matrix)H(f)(x)表示，其中

我们可以将其看做梯度的雅可比矩阵。

二阶导数代表了什么意义呢？

它可以看做是曲线斜率随输入的变化，是一种对曲线曲率的测量。

（1）二阶导数可以告诉我们梯度下降算法的效果。

（2）二阶导数也可以用来判断一个临界点是否是极小值点，极大值点或是鞍点.

什么是牛顿法？

对于多维空间，我们也可以看出一阶梯度下降算法的局限性，如果不同方向上的曲率不同，则某些方向上导数改变很快，而另一些方向上导数改变很小，由于梯度下降算法并没有考虑二阶梯度，它并不知道该选取哪个方向才能更快的到达极值点。同样的，如果不同方向的曲率不同，我们如何选取合适的学习率也成了一个难题，某些方向上曲率大，就会产生在曲线的两个山坡上来回振动而不能一直趋近山坳的现象，限制了我们只能选取很小的学习率，如下图所示：

为了解决这一缺陷，我们需要利用二阶导数，这就是牛顿方法。多维情况下的二阶泰勒展开为

使f(x)相对于x的导数为零，可得更新公式

牛顿方法会比梯度下降算法更快的到达极值点。

4.约束优化

约束极值如何处理？

有的时候，我们不仅仅是要在全域里求某个函数的极值点，而是要在某条件的集合中求条件极值。

这时候我们可以利用KKT算法将有限制条件的极值问题转化为无限制条件的极值问题，然后我们就可以用之前处理无限制条件的极值问题的方法来解决这个问题。

KKT算法可以看做是是拉格朗日乘子法的一种推广形式。

实例

假设我们要求f(x)的极值，其限制条件为

，其中

为等式限制条件，

为不等式限制条件。

对于每一个限制条件，我们可以引入新的KKT乘子

和

，这些变量被称为KTT乘子。广义拉格朗日式子：

我们通过优化无约束的广义拉格朗日解决约束最小化问题，即求出

与如下函数有相同的最优目标函数值和最优集x

这是因为当约束满足时，即

而违反任意约束时， 最大值为零

而违反任意约束时，

由此我们也可以得出拉格朗日式子取极值的必要条件：

• 广义Lagrangian的梯度为零。
• 所有关于x和KKT乘子的约束都满足。
• 不等式约束显示的”互补松弛性”：

一个应用KKT的实例是对于线性最小二乘问题(linear least square),我们想要求在限制条件为

时

的极小值。我们可以将其转化为拉格朗日式子

而转化为解决

的问题。具体细节，参见书实例部分。