第4章 数值计算
数值问题
下溢：接近0的数被四舍五入为0；导致零除问题 上溢：大量级的数被近似为$\infty$
softmax函数：$softmax(x){i}=\frac{e^{x{i}}}{\sum\limits_{j=1}^{n}e^{x_{j}}}$ 当所有$x_i=c$且$c$为很小的负数，$e^{c}$会下溢；当$c$是非常大的正数，$e^c$会上溢 令$softmax(z)$，其中$z=x-max_{i}x_{i}$解决问题 指数的参数最大为0，排除上溢 分母中至少有一项值为1，排除下溢
Theano包自动检验并稳定深度学习中常见的数值不稳定表达式
条件数：函数相对于输入的微小变化而变化的快慢程度 病态条件：输入被轻微扰动而迅速改变的函数 $k(A)=||A||·||A^{-1}||$ 当$k(A)$较小时是良态矩阵，否则是病态矩阵
梯度优化
导数为0：局部最大、局部最小、鞍点 深度学习通常接受近似最小化的满意解
向量$f(x)$梯度$\bigtriangledown_{x}f(x)$：包含所有偏导数的向量 梯度第$i$个元素是$f$关于$x_{i}$的偏导数 多维临界点梯度中所有元素为0
一阶优化算法
最速下降法 单位向量$\mu$方向的方向导数：函数$f$在$\mu$方向的斜率 $\begin{aligned}&\mathop{\min}\limits_{\mu,\mu^{T}\mu=1}\mu^{T}\bigtriangledown_{x}f(x)\ = &\mathop{\min}\limits_{\mu,\mu^{T}\mu=1}||\mu||{2}||\bigtriangledown{x}f(x)||{2}cos\theta\ &代入||\mu||{2}=1,||\bigtriangledown_{x}f(x)||与\mu无关 \ = & \mathop{\min}\limits_{\mu}cos\theta\ &其中\theta是\mu与梯度的夹角\end{aligned}$ 即：当移动方向与梯度向量相反时最速下降
建议移动点$x^{‘}=x-\eta \bigtriangledown_{x}f(x)$
学习率$\eta$：
- 小常数
- 线搜索：计算多个学习率指出的移动点$x^{‘}$选择其中目标函数最小的
二阶优化算法
Jacobian矩阵：包含所有偏导数的矩阵 函数$f:\mathbb{R}^{m}\to \mathbb{R}^n$，Jacobian矩阵$J\in \mathbb{R}^{n\times m}$定义为$J_{i,j}=\frac{\partial}{\partial x_{j}}f(x)_{i}$
Hessian矩阵：二阶导数合并的矩阵；梯度的Jacobian矩阵 $H(f)(x){i,j}= \frac{\partial^{2}}{\partial x{i}\partial x_{j}}f(x)$ 微分算子在任何二阶偏导连续的点处可交换 Hessian矩阵是实对称矩阵
在特定方向$d$上的二阶导数可写成$d^{T}Hd$ 当$d$是$H$的一个特征向量时，这个方向的二阶导数就是对应的特征值 海森矩阵特征值越大凸性越强
当前点$x^{0}$做$f(x)$二阶泰勒展开 $f(x)\approx f(x^{0})+(x-x^{0})^{T}g+ \frac{1}{2} (x-x^{0})^{T}H(x-x^{0})$ $g:梯度；H:矩阵$
移动点$f(x^{0}-\eta g)\approx f(x^{0})-\eta g^{T}g+ \frac{1}{2}\eta^{2}g^{T}Hg$ 函数新值$\approx$函数原始值-斜率导致的预期改善+曲率导致的矫正
当$g^{T}Hg>0$，使近似泰勒级数下降最多的最优步长$\eta^{*}= \frac{g^{T}g}{g^{T}Hg}$ 最坏情况下，$g$与$H$最大特征值$\lambda_{max}$对应的特征向量对齐，最优步长为$\frac{1}{\lambda_{max}}$ $\therefore$Hessian矩阵的特征值决定了学习率的量级
在临界点处（梯度向量为0），通过检测Hessian的特征值判断该临界点是局部最大值、局部最小值还是鞍点 Hessian矩阵是正定的，局部极小点 Hessian矩阵是负定的，局部极大点 Hessian矩阵是半定的，不确定
Hessian矩阵条件数很差时，梯度下降算法表现也很差【步长过小】
牛顿法 对目标函数进行二阶泰勒展开 $f(x)\approx f(x^{0})+(x-x^{0})^{T}\bigtriangledown_{x}f(x^{0})+ \frac{1}{2}(x-x^{0})^{T}H(f)(x^{0})(x-x^{0})$ 最小化目标函数： $令\frac{\partial f(x)}{\partial x^{}}\approx \bigtriangledown_{x}f(x^{0})+x^{}H(f)(x^{0})-x^{0}H(f)(x^{0})=0$ $\therefore x^{*}=x^{0}-\frac{\bigtriangledown_{x}f(x^{0})}{H(f)(x^{0})}$ 当附近的临界点为最小点(Hessian矩阵所有特征值为正)牛顿法不会被吸引到鞍点 若f局部近似正定二次函数，牛顿法多次迭代后可快速接近局部极小点 牛顿法无法区分鞍点
Lipschitz连续：保证了函数连续且变化速度小于Lipschitz常数 $\forall x, \forall y, |f(x)-f(y)|\leq\mathcal{L}||x-y||_2$
凸优化：适用凸函数(Hessian矩阵处处半正定) 没有鞍点，局部极小值必为全局极小值
约束优化
简单处理：将无约束梯度下降计算结果投影至约束中筛选 复杂处理：转化为同解无约束问题
KKT方法
约束优化通用解决方案 拉格朗日乘子法的推广 广义Lagrangian函数 约束域$\mathbb{S}$由$i$个等式约束和$j$个不等式约束组成 $\mathbb{S}={x|\forall i,g^{i}(x)=0\ and\ \forall j,h^{j}(x)\leq 0}$ 为每个约束引入拉格朗日乘子$\lambda,\alpha$ $L(x,\lambda,\alpha)=f(x)+\sum\limits_{i}\lambda_{i}g^{i}(x)+\sum\limits_{j}\alpha_{j}h^{j}(x)$
若不等式约束$h^{j}(x^{*})=0$约束是活跃的 若约束不活跃，则该约束问题的解与去掉该约束问题的解至少存在一个相同的局部解 不活跃的约束$h^{i}$必有负值，$\mathop{\min}\limits_{x}\ \mathop{\max}\limits_{\lambda}\ \mathop{\max}\limits_{\alpha,\alpha\geq0}\ L(x,\lambda,\alpha)$中$\alpha_{i}=0$
KKT条件
- 广义Lagrangian梯度为0
- 所有关于$x$和KKT乘子的约束均满足
- 不等式约束显示的“互补松弛性”：$\alpha \odot h(x)=0$
实例：线性最小二乘
最小化目标函数$f(x)= \frac{1}{2}||Ax-b||{2}^{2}$ 最速下降法 从任意点$x$开始，使用最速下降法优化目标函数 将步长$\eta$和容差$\delta$ while $||A^{T}Ax-A^{T}b||{2}>\delta$ do $x \leftarrow x-\eta (A^{T}Ax-A^{T}b)$ end while
牛顿法 原问题为二次函数，一步到位
KKT方法 修改问题：添加不等式约束$x^{T}x\leq 1$ Lagrangian函数：$L(x,\lambda)=f(x)+\lambda(x^{T}x-1)$