前言
本文的主体是机器学习中所用到的数值计算知识，因此奉行Lazy evaluation，对这些知识更深层次的探究只在绝对必要时完成。
Source of errors
Overflow and Underflow
计算机的内存是有限的，而有限的内存上无法实现无限精度的数值计算，因此数值计算是有误差的。
接近零的非零数值因为舍入变为0称为Underflow。
超出表示范围的wrap-around称为Overflow
- positive-overflow 指超过范围的正数被截断为负数
- negative-overflow 指超过范围的负数被截断为正数
Poor Conditioning
Condition指输入的微小变化引起函数值变化的剧烈程度。计算机中的数字是有表示范围的，因此Condition大的函数会遇到很多问题。
对于
$$f(\mathbf{x})=A_{-1}\mathbf{x},A \in \mathbb{R}^{nxn}$$如果A可以做特征值分解，那么f的condition number定义为
$$\max{i,j}\left|\frac{\lambda_i}{\lambda_j}\right|$$Optimization
解出使函数f(x)取得最大值/最小值的x的过程称为优化(optimization)。求f(x)最大值可以用求-f(x)的最小值实现，因此主要讨论求最小值。
naive gradient descent
梯度(gradient)给出了函数增长最快的方向，那么沿着梯度的反方向就可以将函数值减少。梯度下降法(gradient descent)就是采用这个思路一种方法:
$$ x^{i+1} = x^{i} - \epsilon \nabla_xf(x) $$其中ε是学习率(learning rate)。一般来说ε有两种取法
- 设为一个固定的很小的常量
- 取多个ε，选其中让f(x-ε∇f(x))最小的那个ε。这种方法又称为line search
Beyond the Gradient: Jacobian and Hessian Matrices
对于一个输入和输出都是向量的函数f，含有它的所有偏微分的矩阵称为雅可比矩阵(Jacobian matrix)
$$f:\mathbb{R^m} \to \mathbb{R^n}$$$$J_{i,j}=\frac{\partial}{\partial x_j}f(x)_i 其中J \in \mathbb{R^{n\times m}}$$同样的，含有f的所有二阶偏微分的矩阵称为海希矩阵(Hessian matrix)
$$\mathbf{}{H}(f)(x)_{i,j}=\frac{\partial ^2}{\partial x_i \partial x_j}f(x) $$海希矩阵就是梯度的雅可比矩阵。
当二阶偏微分连续时，微分运算符具有交换律，即
$$H_{i,j}=H_{j,i}$$机器学习中大部分函数f都具有连续的二阶偏微分，因此海希矩阵是实对称矩阵，因而可以做特征值分解，并且U是正交矩阵。
f对某个单位向量u方向u的二阶偏微分由
$$u^{\top} Hu$$给出。
在x0处对f做二阶泰勒展开
$$f(x)\approx f(x^0)+(x-x^0)^{\top}g+\frac{1}{2}(x-x^0)^\top H(x-x^0)$$H为海希矩阵，g为梯度。当采用学习率ε时，梯度下降的新坐标是x0-εg，带入泰勒展开，有
$$f(x^0-\epsilon g) \approx f(x^0) - \epsilon g^{\top}g+\frac{1}{2}\epsilon^2g^{\top}Hg$$当最后一项小于等于零时，ε可以任选。当最后一项大于零时，有
$$\epsilon^*=\frac{g^{\top}g}{g^{\top}Hg}$$时下降最快。最坏情况下，g与H重合，因此学习率的数量级由
$$\frac{1}{\lambda_{\max}}$$决定。
学习率设的过大或过小都会造成问题，这可以由海希矩阵解决。其中最简单的就是牛顿法
牛顿法的步骤基本思路是，在x点做二阶泰勒展开。
$$f(x)\approx f(x^0)+(x-x^0)^{\top}g+\frac{1}{2}(x-x^0)^\top H(x-x^0)$$解出函数的critical point
$$x^*=x^0-H(f)(x^0)^{-1}\nabla_xf(x^0)$$f是正定二次函数时，一次就找到了最低点。当f不是二次函数但是可以用二次函数局部近似时，多次迭代x*即可。
牛顿法只适用于解最小值，而梯度下降没有这个限制。
只用到梯度的优化算法，如梯度下降，叫做一阶优化算法。使用海希矩阵的算法，如牛顿法，叫做二阶优化算法。
Constrained optimization
有时我们希望在某集合S上而不是R^n上找出函数的最大/最小值，这叫做constrainted optimization(受限优化)。落在s中的点称为feasible point(可行点)
KKT方法是一个受限优化问题的通用方法。使用KKT方法，首先定义广义拉格朗日函数。
为了定义广义拉格朗日函数，首先需要将S定义为函数的集合
$$\mathbb{S}=\{x| \forall i,g^{(i)}(x)=0 \text{ and } \forall j,h^{(j)}(x) \le0 \}$$含有g(i)的方程称为equality constraints，含有h(j)的方程称为inequality constraints。
对于每个函数，定义λi和αj。他们叫做KKT乘数。
现在定义广义拉格朗日函数
$$L(x,\lambda,\alpha)=f(x)+\sum_i \lambda_i g^{(i)}(x)+\sum_j \alpha_jh^{(j)}(x)$$接下来在广义拉格朗日函数上使用非受限优化算法，就可以解决受限优化算法了。