最近在读“花书”《Deep learning》，然而第一部分“应用数学与机器学习基础”就异常吃力。一方面高数等基础我大三开始就不再应用，另一方面这部分写得着实简陋，数学公式的证明充斥着大量的“不难得出，可以看到，因此可证…”。让我一个高考数学 145 的人常常怀疑自己的智商。
梯度负方向下降最快
每一篇介绍梯度下降的文章，几乎都会告诉你“梯度负方向下降最快”，但却不告诉你为什么。 而当你谷歌时，中文互联网上的资料大都是这两篇文章复制粘贴：
然而，就在《Deep Learning》这本书的 4.3 章节，用短短 10 行向读者敷衍得证明了下为什么。敷衍到我为了看懂查了一天资料…
先列一些定义:
- 偏导数 \(\frac{\partial}{\partial x_i}f(x)\) 衡量点 \(x\) 处对 \(x_i\) 的变化率。
- 梯度是相对一个向量求导的导数， \(f\) 的导数是包含所有偏导数的向量，记为 \(\nabla_xf(x)\)。
- 下降方向中的方向定义为 \(u\) (单位向量)。
- \(u\) 方向的下降速度为 \(\frac{\partial}{\partial a}f(x+au)\) 在 a=0 时的值。
下面通过雅可比矩阵链式法则求导(向量求导不能直接应用链式法则): \[\frac{\partial{\boldsymbol{f(x+au)}}}{\partial{a}} = \frac{\partial \boldsymbol{f(x+au)}}{\partial{\boldsymbol{(x+au)}}}\frac{\partial{\boldsymbol{(x+au)}}}{\partial a} \]
注意这里是 \(\frac{\partial{\boldsymbol{f(x+au)}}}{\partial{a}}\) 而非 \(\frac{\partial{f(x+au)}}{\partial{a}}\)，等号左侧是粗体。
\(\frac{\partial{\boldsymbol{f}}}{\partial{\boldsymbol{x}}}, \frac{\partial{f}}{\partial{\boldsymbol{x}}}\) 是否相等需要结合分子分母的形态具体分析，以本题为例:
\(\frac{\partial{\boldsymbol{f(x+au)}}}{\partial{a}}\) 雅可比矩阵结果是 \(1 \times 1\)，而 \(\frac{\partial{f(x+au)}}{\partial{a}}\) 结果同样为 \(1\times 1\)，所以:
\[\frac{\partial{\boldsymbol{f(x+au)}}}{\partial{a}}=\frac{\partial{f(x+au)}}{\partial{a}}\]
假设 \(x \in R^n\), \(\frac{\partial \boldsymbol{f(x+au)}}{\partial{\boldsymbol{(x+au)}}}\) 雅可比矩阵结果是 \(1 \times n\)，而 \(\nabla_xf(x)a\) 通常记为 \(n \times 1\)，所以 \[\frac{\partial \boldsymbol{f(x+au)}}{\partial{\boldsymbol{(x+au)}}} ={\frac{\partial f(x+au)}{\partial{\boldsymbol{(x+au)}}}}^\intercal\]
同理\[\frac{\partial{\boldsymbol{(x+au)}}}{\partial a}={\frac{\partial (x+au)}{\partial a}}^\intercal\]
所以\[\frac{\partial}{\partial a}f(x+au)={\nabla_(x+au)f(x+au)}^\intercal u\]
当 \(a = 0\) 时，
\[\frac{\partial}{\partial a}f(x+au)={\nabla_xf(x)}^\intercal u =\left\|\nabla_xf(x)\right\|_2\left\|u\right\|_2\cos\theta \]
所以，梯度负方向下降最快。
KKT方法
Karush-Kuhn-Tucker(KKT) 是解决约束优化问题的通用解决方案，简单而言，当存在约束
\[S = \{x| \forall i, g^i(x)=0 \text{ and } \forall j, h^j \leq 0\}\]
如何求函数 \(f(x)\) 的最小值。
此时可以构造函数: \[L(x, \lambda, a)=f(x) + \sum_i\lambda_ig^i(x) + \sum_ja_jh^j(x)\]
当存在可行点，而且 \(f(x)\) 不允许取 \(\infty\) 时，
\[\min\limits_{x}\max\limits_{\lambda}\max\limits_{a, a \geq 0}L(x, \lambda, a) = \min\limits_{x \in S}f(x)\]
因为: \[\max\limits_{\lambda}\max\limits_{a, a \geq 0}L(x, \lambda, a)= \begin{cases} f(x), \quad x \in S \\ \infty, \quad x \notin S \end{cases}\]
所以 \(\min\limits_{x}\max\limits_{\lambda}\max\limits_{a, a \geq 0}L(x, \lambda, a)\) 的解一定满足 \(x \in S\)，而此时 \(\max\limits_{\lambda}\max\limits_{a, a \geq 0}L(x, \lambda, a) = f(x)\)。
由此可得 KKT 条件
- 广义 Lagrangian 的梯度为0
- 所有关于 \(x\) 和 KKT 乘子的约束都满足
- 不等式约束显示的“互补松弛性”: \(a \odot h(x) = 0\)
其中 1, 2 显然得，关于互补松弛性:
假设 \(h(x)<0\)，为满足 \(\max\limits_{a, a \geq 0}L(x, \lambda, a)\)，此时 \(a=0 => a \odot h(x) = 0\)。而当 \(h(x)=0\) 时，\(a \odot h(x) = 0\)
充分必要性证明，略。