相关数学理论

这篇文章会叙述之前没有解决的纯数学问题，会涉及到相当庞杂的数学概念与思想，其中一些推导的难度相对而言可能会比较大

梯度下降法

前文已经相当充分地说明了梯度下降的直观，本节则打算用较严谨的数学语言来重新叙述一遍这个方法

首先说明其地位：梯度下降法（又称最速下降法）是求解无约束最优化问题的最常用的手段之一，同时由于现有的深度学习框架（比如 Tensorflow）基本都会含有自动求导并更新参数的功能、所以梯度下降法的实现往往会简单且高效

其次说明一下梯度下降法的大致步骤。正如前文所说、梯度下降法的核心在于在于函数的“求导”，而由于一般来说样本都是高维的样本（亦即$x \in \mathbb{R}^{n}$、$n \geq 2$）、所以此时我们要求的其实是函数的梯度。由于梯度是微积分里面的基础知识、这里就不“追本溯源”般地讲解梯度的定义之类的了，如果确实不甚了解且不满足于前文给出的直观解释的话、可以参见维基百科中的详细定义（中文版和英文版都有，个人建议尽量看英文版）

不管怎么说、函数梯度的这一点性质需要谨记：它是使函数值上升最快的方向，这就同时意味着负梯度是使函数值下降最快的“更新方向”。利用该性质，梯度下降法认为在每一步迭代中、都应该以梯度为更新方向“迈进”一步；在机器学习中、我们通常把这时迈进的“步长”称作“学习速率”：

1. 输入：想要最小化的目标函数$f(x)$、迭代次数 M、学习速率$\eta$、计算精度$\epsilon$，其中$x \in \mathbb{R}^{n}$
2. 过程：
   1. 求出$f(x)$的梯度函数： $$g(x) \triangleq \nabla f(x)$$
   2. 取一个初始估计值$x^{\left( 0 \right)} \in \mathbb{R}^{n}$
   3. 对$j = 1,\ldots,M$：
      1. 计算负梯度——$g_{j} = - g(x^{\left( j \right)})$，若$\left\| g_{j} \right\| < \epsilon$则退出循环、令最终解$x^{*} = x^{\left( j \right)}$
      2. 否则、向更新方向$g_{j}$迈进步长为$\eta$的一步： $$x^{\left( j + 1 \right)} = x^{\left( j \right)} + \eta g_{j}$$
      3. 若$\left\| f\left( x^{\left( j + 1 \right)} \right) - f(x^{\left( j \right)}) \right\| < \epsilon$或$\left\| x^{\left( j + 1 \right)} - x^{\left( j \right)} \right\| < \epsilon$则退出循环、令最终解$x^{*} = x^{\left( j + 1 \right)}$
3. 输出：最终解$x^{*}$

上述算法是一个最为朴素的梯度下降法框架，通过在其基础上结合具体的模型进行改进、拓展能够衍生出一系列著名的算法。具体而言、这些拓展算法通常会针对如下两个部分进行改进：

• 不是单纯地把梯度作为更新方向、而是利用更多的属性来定出更新方向
• 不把学习速率设成常量、而设法让其能够“适应算法”并根据具体情况进行调整

有关梯度下降的拓展算法会在下一个系列的文章中进行比较详细的叙述，这里我们仅针对第二点来举一个非常直观的改进例子（仅写出与上述算法中不同的部分）：

• 算法 2.3.2 步
  对$j = 1,\ldots,M$：
  • 否则求出$\eta_{j}$、使得： $$f\left( x^{\left( j \right)} + {\eta_{j}g}_{j} \right) = \min_{\eta>0}{f(x^{\left( j \right)} + \eta g_{j})}$$ 然后根据$\eta_{j}$来更新估计值： $$x^{\left( j + 1 \right)} = x^{\left( j \right)} + \eta_{j}g_{j}$$ 这种算法又可以称作精确线性搜索准则。当优化问题为凸优化、亦即函数为凸函数时，可以证明若迭代次数 M 足够大、精确线性搜索必定能够收敛到全局最优解

考虑到对于具体的机器学习模型而言、其训练时一般会同时用到许多的样本，此时进行梯度下降法的话就不免会遇到一个问题：计算梯度时，是应该同时对多个样本进行求解然后将结果整合、还是对样本逐个进行求解？对该问题的不同解答对应着不同的算法、前文也已经有所提及。具体而言：

• 对于随机梯度下降（SGD）、其求梯度的公式为： $$g_{j} = - \nabla f\left( x_{i} \right)$$ 其中 i 是一个合适的下标。SGD 的优缺点都比较直观：虽然（在同样的迭代次数下）它的训练速度很快、但它搜索解空间的过程会显得比较盲目（就有种东走一下西走一下的感觉），这直接导致其收敛速度反而可能会更慢。同时如果考虑实际应用的话，由于 SGD 难以并行实现、所以其效率往往会比较低
• 对于小批量梯度下降（MBGD）、其求梯度的公式为： $$g_{j} = - \frac{1}{m}\left( \nabla f\left( x_{S_{1}} \right) + \ldots + \nabla f\left( x_{S_{m}} \right) \right)$$ 其中 m 是一个合适的、小于总样本数 N 的数，$S_1,...,S_m$则是 m 个合适的下标；通常我们会称$\left\{ x_{S_1},...,x_{S_m}\right\}$为一个 batch。MBGD 可谓是应用得最广泛的梯度下降法，它在单步迭代中会比 SGD 慢、但它对解空间的搜索会显得“可控”很多、从而收敛速度一般反而会比 SGD 要快
• 对于批量梯度下降（BGD）、其求梯度的公式为： $$g_{j} = - \frac{1}{N}\sum_{i = 1}^{N}{\nabla f\left( x_{i} \right)}$$ BGD 会有一种“过犹不及”的感觉，由于它单步迭代中会用到所有样本，所以当训练集很大的时候、无论是时间开销还是空间开销都会变得难以忍受

以上我们就大概综述了一遍梯度下降法的框架，更为细致的具体算法则会在下一个系列中介绍神经网络时进行部分说明

拉格朗日对偶性

如果按照最一般性的定义来讲的话，拉格朗日对偶性会显得太过“纯粹”、或说可以算是数学家的游戏。因此本小节拟打算通过推导如何将软间隔最大化 SVM 的原始最优化问题转化为对偶问题、来间接说明拉格朗日对偶性的一般性步骤

注意到原始问题为：

$$\min_{w,b}{L\left( w,b,x,y \right) =}\frac{1}{2}\left\| w \right\|^{2} + C\sum_{i = 1}^{N}\xi_{i}$$

使得：

$$y_{i}\left( w \cdot x_{i} + b \right) \geq 1 - \xi_{i}\ (i = 1,\ldots,N)$$

其中

$$\xi_{i} \geq 0\ (i = 1,\ldots,N)$$

那么原始问题的拉格朗日函数即为：

$$L\left( w,b,\xi,\alpha,\beta \right) = \frac{1}{2}\left\| w \right\|^{2} + C\sum_{i = 1}^{N}\xi_{i} - \sum_{i = 1}^{N}{\alpha_{i}\left\lbrack y_{i}\left( w \cdot x_{i} + b \right) - 1 + \xi_{i} \right\rbrack} - \sum_{i = 1}^{N}{\beta_{i}\xi_{i}}$$

为求解$L$的极小、我们需要对$w$、$b$和$\xi$求偏导并令偏导为 0。易知：

$$\begin{align} \nabla_{w}L &= w - \sum_{i = 1}^{N}{\alpha_{i}y_{i}x_{i}} = 0 \\ \nabla_{b}L &= \sum_{i = 1}^{N}{\alpha_{i}y_{i}} = 0 \\ \nabla_{\xi_{i}}L &= C - \alpha_{i} - \beta_{i} = 0 \end{align}$$

解得

$$w = \sum_{i = 1}^{N}{\alpha_{i}y_{i}x_{i}}$$ $$\sum_{i = 1}^{N}{\alpha_{i}y_{i}} = 0$$

以及对$i = 1,\ldots,N$、都有

$$\alpha_{i} + \beta_{i} = C$$

将它们带入$L\left( w,b,\xi,\alpha,\beta \right)$、得

$$L\left( w,b,\xi,\alpha,\beta \right) = - \frac{1}{2}\sum_{i = 1}^{N}{\sum_{j = 1}^{N}{\alpha_{i}\alpha_{j}y_{i}y_{j}\left( x_{i} \cdot x_{j} \right)}} + \sum_{i = 1}^{N}\alpha_{i}$$

从而原始问题的对偶问题即为求上式的极大值、亦即

$$\max_{\alpha}{- \frac{1}{2}\sum_{i = 1}^{N}{\sum_{j = 1}^{N}{\alpha_{i}\alpha_{j}y_{i}y_{j}\left( x_{i} \cdot x_{j} \right)}} + \sum_{i = 1}^{N}\alpha_{i}}$$

其中约束条件为：

$$\sum_{i = 1}^{N}{\alpha_{i}y_{i}} = 0$$

以及对$i = 1,\ldots,N$、都有

$$\alpha_{i} \geq 0,\ \ \beta_{i} \geq 0$$ $$\alpha_{i} + \beta_{i} = C\ (i = 1,\ldots,N)$$

易知上述约束可以简化为对$i = 1,\ldots,N$、都有

$$0 \leq \alpha_{i} \leq C$$

综上所述即得前文叙述过的软间隔最大化的对偶形式。注意到原始问题是凸二次规划、从而对偶形式的解$w^{*}$、$b^{*}$、$\xi^{*}$、$\alpha^{*}$和$\beta^{*}$满足 KKT 条件，亦即：

$$\nabla_{w}L(w^{*},b^{*},\xi^{*},\alpha^{*},\beta^{*}) = \nabla_{b}L(w^{*},b^{*},\xi^{*},\alpha^{*},\beta^{*}) = \nabla_{\xi}L(w^{*},b^{*},\xi^{*},\alpha^{*},\beta^{*}) = 0$$

以及对$i = 1,\ldots,N$、都有

$$\alpha_{i}^{*}\left\lbrack y_{i}\left( w^{*} \cdot x_{i} + b^{*} \right) - 1 + \xi^{*} \right\rbrack = 0$$ $$y_{i}\left( w^{*} \cdot x_{i} + b^{*} \right) - 1 + \xi^{*} \geq 0$$ $$\alpha^{*} \geq 0,\beta^{*} \geq 0,\xi^{*} \geq 0$$ $$\xi^{*}\beta^{*} = 0$$

由它们就可以推出前文说明过的、$w^{*}$和$b^{*}$关于$\alpha^{*}$的表达式了