数值计算

上溢和下溢

数值分析概念，运算时考虑其影响即可。一般调库时不需要考虑。

病态条件

数值分析概念，考虑函数$f(\boldsymbol{x})=\boldsymbol{A}^{-1}\boldsymbol{x}$，当$A \in \mathbb{R}^{n \times n}$具有分解特征值时，条件数为$\max _{i,j} \left | \cfrac{\lambda_i}{\lambda_j} \right |$，越大，矩阵求逆对误差越敏感。

基于梯度的优化方法

把要最小化或最大化的函数称为目标函数
要对其进行最小化时，称为
- 代价函数cost function
- 损失函数loss function
- 误差函数error function
导数
梯度下降
局部最小，局部最大，全局最小，全局最大
偏导数
梯度
- 记为$\boldsymbol{\triangledown_{x}}f(\boldsymbol{x})$
- 多维情况下，临界点是梯度中所有元素都为0的点
在$\boldsymbol{u}$方向的方向导数是函数$f$在$\boldsymbol{u}$方向的斜率
- 是函数$\cfrac{\partial}{\partial{\alpha}}f(\boldsymbol{x} + \alpha \boldsymbol{u})$关于$\alpha$的导数
- 当$\alpha=0$时，$\cfrac{\partial}{\partial{\alpha}}f(\boldsymbol{x} + \alpha \boldsymbol{u}) = \boldsymbol{u}^T\boldsymbol{\triangledown_{x}}f(\boldsymbol{x})$
- 找到使$f$下降最快的方向，计算方向导数：
  $$\begin{gathered} \min _{\boldsymbol{u}, \boldsymbol{u}^{\top} \boldsymbol{u}=1} \boldsymbol{u}^{\top} \nabla_{\boldsymbol{x}} f(\boldsymbol{x}) \\ =\min _{\boldsymbol{u}, \boldsymbol{u}^{\top} \boldsymbol{u}=1}|\boldsymbol{u}|_2\left|\nabla_{\boldsymbol{x}} f(\boldsymbol{x})\right|_2 \cos \theta \end{gathered} $$
  - 其中$\theta$是$\boldsymbol{u}$与梯度的夹角
  - 将$|\boldsymbol{u}|_2=1$代入，忽略与$\boldsymbol{u}$无关的项，简化得$\min _{\boldsymbol{u}, \boldsymbol{u}^{\top} \boldsymbol{u}=1} \cos \theta$
  - 可见在负梯度方向上移动可以最快减小$f$
- 梯度下降建议更新为
  - $$\boldsymbol{x}^{\prime}=\boldsymbol{x}-\epsilon \nabla_x f(\boldsymbol{x})$$
  - 其中 $\epsilon$ 为学习率（learning rate）

梯度之上：Jacobian和Hessian

Jacobian矩阵：如果有一个函数$\boldsymbol{f}:\mathbb{R}^m \rightarrow \mathbb{R}^n$，则Jacobain矩阵定义为：
- $\boldsymbol{J} \in \mathbb{R}^{n \times m} \boldsymbol{J}_{i,j}=\cfrac{\partial}{\partial x_j}f(\boldsymbol{x})_i$
二阶导数是对函数曲率的衡量，影响基于梯度的预测值。
Hessian矩阵：函数具有多维输入时，二阶导数也有很多，将这些导数合并成一个矩阵就是Hessian矩阵，定义为：
- $\boldsymbol{H}(f)(\boldsymbol{x})_{i,j}=\cfrac{\partial^2}{\partial x_i \partial x_j}f(\boldsymbol{x})$
- 在深度学习中，大部分时候$H_{i,j}=H_{j,i}$，因此大部分其是实对称矩阵，可将其分解成一组实特征值和一组特征向量的正交基
- 在特定方向$\boldsymbol{d}$上的二阶导数可以写成 $\boldsymbol{d^THd}$
  - 当$\boldsymbol{d}$是$\boldsymbol{H}$的一个特征向量时，这个方向的二阶导数就是对应的特征值
  - 对于其他的方向$\boldsymbol{d}$，方向二阶导数是所有特征值的加权平均，权重在 0 和 1 之间，且与$\boldsymbol{d}$夹角越小的特征向量的权重越大。最大特征值确定最大二阶导数，最小特征值确定最小二阶导数
- 可以通过方向二阶导数预期一个梯度下降步骤能表现的多好
  - 用泰勒级数近似在点$\boldsymbol{x}^{(0)}$处作$f(\boldsymbol{x})$的近似二阶泰勒级数，梯度下降的学习率可代入并计算得：当$\boldsymbol{g^THg}$ (g是梯度，H是Hessian)为正时，最优步长为：
    - $\epsilon^*=\cfrac{\boldsymbol{g^Tg}}{g^THg}$
- 二阶导数还可以被用于确定一个临界点是否是局部极大点、局部极小点或鞍点（二阶导数测试）
仅使用梯度信息的优化算法被称为一阶优化算法，如梯度下降
使用 Hessian 矩阵的优化算法被称为二阶最优化算法，如牛顿法
深度学习中，限制函数满足 Lipschitz 连续或其导数Lipschitz连续可以保证优化算法的适用。Lipschitz 连续函数的变化速度以 Lipschitz常数$\mathcal{L}$为界：
- $\forall \boldsymbol{x},\forall \boldsymbol{y}, |f(\boldsymbol{x})-f(\boldsymbol{y})| \le \mathcal{L}|\boldsymbol{x-y}|_2$

约束优化

希望在$\boldsymbol{x}$的某些集合$\mathbb{S}$中找$f(\boldsymbol{x})$的最大值或最小值。这被称为约束优化
集合$\mathbb{S}$内的点$\boldsymbol{x}$被称为 可行点（feasible）
找到在某种意义上小的解的常见方法是强加一个范数约束
Karush–Kuhn–Tucker（KKT）方法是针对约束优化非常通用的解决方案

梯度下降法计算线性最小二乘

对式 $f(\boldsymbol{x})=\frac{1}{2}|\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b}|_2^2$ 找到最小化的$\boldsymbol{x}$的值
计算梯度：
$$\nabla_x f(\boldsymbol{x})=\boldsymbol{A}^{\top}(\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b})=\boldsymbol{A}^{\top} \boldsymbol{A} \boldsymbol{x}-\boldsymbol{A}^{\top} \boldsymbol{b}$$
使用梯度下降法：
$
\begin{aligned}
& \text { while }\left|\boldsymbol{A}^{\top} \boldsymbol{A} \boldsymbol{x}-\boldsymbol{A}^{\top} \boldsymbol{b}\right|_2>\delta \text { do } \\
& \qquad \boldsymbol{x} \leftarrow \boldsymbol{x}-\epsilon\left(\boldsymbol{A}^{\top} \boldsymbol{A} \boldsymbol{x}-\boldsymbol{A}^{\top} \boldsymbol{b}\right) \\
& \text { end while }
\end{aligned}
$