数值优化
数值优化
无论是机器学习还是深度学习，本质上都是求解一个输入到输出的最好的映射，那么这里的“最好”的定义根据不同场景，任务目标也会有所不同。给出“最好”的定义之后，那么就需要去求解最优的映射，这个求解的过程，就是数值优化。本篇博客主要是介绍数值优化的一些基础概率和基本算法，更为高深的数值算法，这里不在赘述。
上溢和下溢
严格来说，在计算机里所有的数都是离散的，并且是有限的，其离散化的精度和所表示数的范围，都是有限的。举个例子来说，用64个比特位来表示整数，其能表示的整数范围为[-9223372036854775808, 9223372036854775807]，虽然这个范围很大，但并不是无穷的。同理如果用64个个比特位来表示浮点数，那么所能表示的浮点数个数也是有限的，所以这里就存在舍入误差。
为了更直观的看到舍入误差，这里举一个例子，以4个比特位为例子，前两个表示浮点数的整数部分，后两个比特位来表示浮点数的小数部分。比如1.2就可以用0110来表示，其中01是整数部分1的二进制表示，而后面的10则是小数部分2的二进制表示。但是这样的4个比特位，其表示的浮点数的能力非常有限。因为我们很容易就可以看到，它只能表示小数部分为0,1,2,3的小数，其余的表示不了，比如1.5，1.21。这里表示值和真实的浮点数之间的误差，可以称之为舍入误差。所以无论是用多少个比特位来表示浮点数，只要比特位个数有限，就总会存在误差。
当然这里的舍入误差一般不会很大，毕竟64个比特位已经能满足日常计算的需求。不过遗憾的是，舍入误差会导致一些问题，特别是当许多操作复合时，即使是理论上可行的算法，如果在设计时没有考虑最小化舍入误差的累积，在实践时也可能会导致算法失效。
一种比较麻烦的舍入误差是下溢（underflow），当接近零的数被四舍五入为
零时发生下溢。许多函数在其变量为0和很小的正数是所表现出的性质完全不同，比如在做除法时，分母不能0。除零之后会是一个“无穷大的数”，这时一些软件会抛出异常，或者返回一个非数字 (not-a-number, NaN) 的占位符。这样进一步的计算就无法进行了。
另一个极具破坏力的数值错误形式是上溢（overflow）。当大量级的数被近似为∞ 或 −∞ 时发生上溢。进一步的运算通常会导致这些无限值变为非数字。
上溢和下溢都会造成数值问题，这里举一个例子来更好的理解。在神经网络中，尤其是分类问题，softmax函数经常使用。softmax函数的定义为
$$
softmax(x)i = \frac{\exp(x_i)}{\sum{j=1}^n\exp(x_j)} \tag{1}
$$
如果$x$的所有分量都是一个常数$c$，那么softmax函数的值应该是一个$1/n$
然而，实际上当常数$c$比较大时，softmax函数的分子分母都是一个很大数（指数爆炸），这样的数早就超出了计算机的表示范围，于是出现了上溢，那么计算机便无法计算出此时softmax的函数值。同理如果此时c是一个比较小的负数，那么此时分子分母又会很接近0，此时又容易出现下溢，那么这个结果也是未定义的。这两个困难可以通过一个简单的变换来解决，我们放弃计算$softmax(x)$转为计算$softmax(z)$，其中$z = x - max_i x_i$。这样的变换可以保证，即使$x_i$ 很大，$z$最大值也只是0，而且分母总是保证有一个分量为1。
在大多数情况下，我们没有明确地对本书描述的各种算法所涉及的数值考虑进行详细说明。底层库的开发者在实现深度学习算法时应该牢记数值问题。本书的大多数读者可以简单地依赖保证数值稳定的底层库。在某些情况下，我们有可能在实现一个新的算法时自动保持数值稳定。Theano (Bergstra et al., 2010a; Bastien et al.,2012a) 就是这样软件包的一个例子，它能自动检测并稳定深度学习中许多常见的数值不稳定的表达式。
病态条件
无论是深度学习还是机器学习，我们在求解最优解的时候，常常会涉及到矩阵运算，而且这其中就包括矩阵求逆运算。一个$n\times n$的矩阵求逆运算的时间复杂度是$\mathcal{O}(n^3)$。然后矩阵求逆不仅仅是复杂度高，还会受矩阵病态的影响，导致求逆运算对很小的误差或者噪声非常敏感。举个例子来说。
现在有一个线性方程$Ax = b$,
$$
\begin{bmatrix}
400 & -201 \
-800 & 401
\end{bmatrix} \begin{bmatrix}
x_1 \
x_2
\end{bmatrix} = \begin{bmatrix}
200 \
-200
\end{bmatrix} \tag{2}
$$
上述方程的解为$x_1 = -100$, $x_2 = -200$，但是如果现在出现了一点扰动，导致矩阵$A$的第一个元素从400变为401，即,
$$
\begin{bmatrix}
401 & -201 \
-800 & 401
\end{bmatrix} \begin{bmatrix}
x_1 \
x_2
\end{bmatrix} = \begin{bmatrix}
200 \
-200
\end{bmatrix} \tag{3}
$$
此时方程的解会变为$x_1 = 40000$, $x_2 = 79800$。矩阵$A$一个小小的变化，会导致方程的解发生巨大变化。说明了此时方程的解对参数非常敏感，而这个矩阵也称为病态的（ill conditioned）。
矩阵病态是一个很难避免的问题，因为在实际工程应用中，求解线性方程组$Ax=b$问题时，其系数矩阵或初值矩阵 一般由实验数据构成，如果矩阵$A$或$b$中的元素存在观测误差、仪器的测量误差或计算机本身的误差等，则会导致求得解偏离真实值很多。
那么如何去衡量一个矩阵是否是病态的呢，数学根据条件数，给出了如下结论：考虑函数$f(x) = A^{-1}x$，其中$A\in \mathbb{R}^{n\times n}$的特征值为$\lambda_i, i=1, \dots, n$，其条件数为
$$
\kappa(A) = \max_{i,j} \mid\frac{\lambda_i}{\lambda_j}\mid \tag{4}
$$
这是最大和最小特征值的模之比，当该数很大时，矩阵求逆对输入的误差特别敏感。当该数很大时，矩阵求逆对输入的误差特别敏感。
这种敏感性是矩阵本身的固有特性，而不是矩阵求逆期间舍入误差的结果。也就是说即使我们乘以完全正确的矩阵逆，病态条件的矩阵也会放大预先存在的误差。在实践中，该错误将与求逆过程本身的数值误差进一步复合。
基于梯度的优化方法
之前的章节已经提到了，绝大多数深度学习或者机器学习目标都是求解一个最优的映射，这其中都涉及到优化某一个目标函数，即，$\min_{x} f(x)$，其中$x$是自变量，$f(x)$是目标函数（objective function），或者称为准则（criterion），因为这里是采用最小化$f(x)$，所以根据场景也常常称为损失函数（loss function），误差函数（error function），代价函数（cost function）。这里求解出的最优解往往用$x^*$表示，即，$x^* = \arg\min_x f(x)$。下面的内容需要一些微积分的基础知识。
对于一个函数$y = f(x)$，$x,y \in \mathbb{R}$都是实数，导数是提供函数变化确实最直接的线索。函数的导数定义为$f^{\prime}(x) = \frac{\partial f(x)}{\partial x}$，导数$f^{\prime}(x)$的方向是函数在该点增加最快的方向，$-f^{\prime}(x)$函数减小最快的方向。一个直观的函数优化方法就是，沿着导数的反方向去寻找更优的$x$，这种方法被称为梯度下降法（gradient descent）。这里需要提一句，在$x$是单变量的场景下，梯度和导数没有区别，如果是多变量，比如$x = (x_1, x_2)^T$，此时的导数$\frac{\partial{f(x)}}{\partial{x}} = \left(\frac{\partial{f(x_1)}}{\partial{x_1}}, \frac{\partial{f(x_2)}}{\partial{x_2}}\right)^T$，这个也称为梯度。
