花书四数值计算

2019-03-03 本文已影响0人 link_start

上溢和下溢

计算机中在表示实数时候存在的误差。
一种近似误差是舍入误差。这种舍入误差指的是，指运算得到的近似值和精确值之间的差异。
如果忽略舍入误差，会导致某些理论可行的算法在实践中也可能会失效。

文中的两个舍入误差引起的例子，上溢和下溢。
当大量级的数被近似为∞ 或 −∞ 时发生上溢。
当接近零的数被四舍五入为零时发生下溢

例子： softmax 函数

softMax函数

softmax函数在深度学习中经常用到，必须对上溢和下溢进行数值稳定。

当所有的xi都等于某一常数C，如果C是很小的负数，在计算机中可能对其存在舍入误差直接取0。那么则会发生下溢，反之则会产生上溢。

病态条件

书中对病态条件的描述是

条件数表征函数对于输入的微小变化而变化的快慢。

1.病态系统

首先一个线性系统是否是病态的，需要看这个系统的解受系数矩阵微小变化的扰动情况[1]。
例如现有线性系统:
Ax = b，解方程

很容易得到解为： x1 = -100, x2 = -200. 如果在样本采集时存在一个微小的误差，比如，将 A 矩阵的系数 400 改变成 401：

则得到一个截然不同的解：

x1 = 40000, x2 = 79800.

当解集 x 对 A 和 b 的系数高度敏感，那么这样的方程组就是病态的 (ill-conditioned).

2.条件数

那么，如何评价一个方程组是病态还是非病态的呢？在此之前，需要了解矩阵和向量的 norm，这里具体是计算很简单的 infinity norm，即找行绝对值之和最大，举个例子：

矩阵范数：

1-范数：列和范数，即所有矩阵列向量绝对值之和的最大值

2-范数：谱范数，即A'A矩阵的最大特征值的开平方

∞-范数：行和范数，即所有矩阵行向量绝对值之和的最大值

F-范数：Frobenius范数，即矩阵元素绝对值的平方和再开平方

矩阵范数性质：
1.||A||>=0;
2.||A||=0 iff A=O （零矩阵）; （1和2可统称为正定性）

3.||aA||=|a| ||A||; （齐次性）
4.||A+B||<= ||A|| + ||B||. （三角不等式）
5.||AB||<=||A|| ||B||. （相容性）

理解了这些概念，下面讨论一下衡量方程组病态程度的条件数，首先假设向量 b 受到扰动，导致解集 x 产生偏差：

根据相容性可得

综合上面两个不等式

可得

如果是矩阵A产生的误差，同意可得

其中，条件数定义为：

书中对其条件数定义采用二姐矩阵范数形式：

所以当这个数很大的时候，矩阵其实是对输入误差特别敏感的，在实践中，该错误与求逆过程中的本身数值错误将会进一步复合。

基于梯度的优化方法

我们把需要最小化或者最大话的函数成为目标函数或准则。
当我们对其进行最小化时，我们也将其成为代价函数，损失函数，误差函数。

为了求解这个函数的最小值，我们引入当前点x的导数，导数表示了，如果缩放输入的小变化，才能在输出获得相应的变化。

因此我们可以通过根据导数来不断的往导数的反方向移动一小步来减少f(x)
这种技术被成为梯度下降。

当导数等于0的时候，这表示导数无法提供往哪个方向移动的信息。
这些点被成为临界点或驻点。
局部极小值点意味着f(x) 小于所有附近的点
局部极大值点意味着f(x)大于所有附近的点
有些临界点既不是最小值点，也不是最大值点，这些点被成为鞍点。

使得f(x)取得绝对的最小值点是全局最小值点。函数可能只有一个全局最小点或存在多个全局最小点，还可能存在不是全局最优的局部极小点。
我们通常寻找使 f 非常小的点，但这在任何形式意义下并不一定是最小

多维度输入

针对具有多维输入的函数，我们需要用到偏导数（partial derivative）的概念。
偏导数： ∂∂xif(x) 衡量点 x 处只有 xi 增加时 f(x) 如何变化。
梯度：本意是一个向量（矢量），是包含所有偏导数的向量，
是函数对每个因子求偏导得到的列向量，表示着函数的变化趋势，
表示某一函数在该点处的方向导数沿着该方向取得最大值。记为

Jacobin 矩阵：

Hessian矩阵：

梯度下降，最速下降法，牛顿法。

问题一：[2] 为什么沿着负梯度方向是下降最快的方向?

将目标函数 f(x) 在点 xk 处泰勒展开

由于我们定义了步长 α>0 ，因此，当 gTkdk<0 时， f(x)<f(xk) ，即函数值是下降的。此时 dk 就是一个下降方向。
但是 dk 具体等于什么的时候，可使目标函数值下降最快呢？
由Cauchy-Schwartz不等式（柯西-许瓦兹不等式）可得

当且仅当 dk=gk 时，等号成立， dTkgk 最大（>0）
所以 dk=−gk 时， dTkgk 最小（<0）， f(x) 下降量最大
所以 −gk 是最快速下降方向

问题二：梯度法的步长如何确定?

书中简单提供了三种方式:
1.简单的取一个小常数
2.选择使方向导数消失的步长
3.还有一种方法是根据几个 ϵ 计算 f(x − ϵ∇xf(x))，并选择其中能产生最小目标函数的 ϵ。这种策略被称为线搜索（line search）

line search

对每一个line search过程来说，搜索方向 $d_{k}$ 已经确定了，所以，在一个确定的 $d_{k}$ 上，要找到一个合适的 $\alpha_{k}$ 使得 $\phi(\alpha) = f(x_{k}+\alpha d_{k})$ 这个函数满足 $f(x_{k}+\alpha_{k} d_{k})<f(x_{k})$ ，这就是line search的目的。说白了，就是要找到 $\phi(\alpha_{k})$ 使 $\phi(\alpha)$ 的函数函数值变小。
不变小的话就会像上图那样，不会精确收敛。
但是，要小到什么程度呢？假设小到有可能的“最小”，即：