梯度下降

一、基本思想

1.1 知识回顾

我们首先回顾逻辑回归模型的参数估计：

$\begin{aligned} &对于给定的数据集D=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\},x_i\in R^d,y_i\in\{0,1\}\\ &\hat{w}_{MLE}=\underset{w}{argmin}\sum_{i=1}^n\log(1+e^{-y_i(w^Tx_i+b)})\\ &\hat{w}_{MAP}=\underset{w}{argmin}\sum_{i=1}^n\log(1+e^{-y_i(w^Tx_i+b)})+\lambda w^Tw \end{aligned}$

由此我们得到两个估计过程的损失函数：

$\begin{aligned} &l(w)_{MLE}=\sum_{i=1}^n\log(1+e^{-y_i(w^Tx_i+b)})\\ &l(w)_{MAP}=\sum_{i=1}^n\log(1+e^{-y_i(w^Tx_i+b)})+\lambda w^Tw \end{aligned}$

我们的目标是最小化一个凸的、连续的、可微的损失函数$l(w)$。

凸函数定义为：

$对\forall t\in[0,1],若f(x)满足:f(tx_1+(1-t)x_2)\le tf(x_1)+(1-t)f(x_2),则称f(x)为凸函数$

①$l(w)$是凸函数：这使得我们找到的局部最小值也是全局最小值
②$l(w)$至少三次连续可微：我们将广泛得使用泰勒近似，这个假设大大简化了讨论
③在$w$上没有设置任何约束，添加约束会增加问题的复杂程度，我们在这里将不讨论

1.2 局部最小值

1.2.1 定义

定义：我们将$w^*$称为$l(w)$的一个局部最小值，如果有：

$\exist \epsilon>0,使得\forall w\in\{w:||w-w^*||_2<\epsilon\},都有l(w^*)\le l(w)$

$LP$范数：$||x||_p=(\sum_{i=1}^n |x_i|^p)^{\frac1p}$

因为我们之前有$l(w)$是凸函数的假设，所以找到的局部最小值$w^*$也是全局最小值，有：

$\forall w\in R^d,都有l(w^*)\le l(w)$

当满足如下条件时，我们称$w^*$为$l(w)$的一个严格的局部最小值：

$\exist \epsilon>0,使得\forall w\in\{w:||w-w^*||_2<\epsilon\},都有l(w^*)< l(w)$

注意不是所有的凸函数都有严格的局部最小值，比如$l(w)=1$

1.2.2 必要条件

一个点$w^*$成为局部最小值的必要条件为：

$\nabla l(w^*)=\overrightarrow0$

$\nabla为梯度算子，\nabla l(w)=[\frac{\partial l(w)}{\partial w_1},\frac{\partial l(w)}{\partial w_2},...,\frac{\partial l(w)}{\partial w_d}]^T$

如果点$w^*$满足上述必要条件，则该点成为严格的局部最小值的充分条件是$Hessian$矩阵为正定的：

$即：\nabla^2l(w^*)=H(w)=\left[ \begin{aligned} &\frac{\partial^2l(w)}{\partial w_1^2}~~\frac{\partial^2l(w)}{\partial w_1\partial w_2}~~...~~\frac{\partial^2l(w)}{\partial w_1\partial w_d}\\ &~~~~...~~~~~~~~~~...~~~~~~~~...~~~~~~~...\\ &\frac{\partial^2l(w)}{\partial w_d\partial w_1}~~\frac{\partial^2l(w)}{\partial w_d\partial w_2}~~...~~\frac{\partial^2l(w)}{\partial w_d^2}\\ \end{aligned} \right]是正定的。$

正定矩阵的定义为：

$设A是n阶方阵，即A\in R^{n\times n},如果对于任何非零向量X\in R^n都有：X^TA~X>0,那么A是正定的$

二、泰勒展开

为了理解更新过程中的损失函数变化，我们对损失函数进行泰勒展开：

2.1 一阶泰勒展开

$l(w+\Delta w)=l(w)+g(w)^T\Delta w\\ g(w)=\nabla l(w)=[\frac{\partial l(w)}{\partial w_1},\frac{\partial l(w)}{\partial w_2},...,\frac{\partial l(w)}{\partial w_d}]^T$

一阶泰勒展开对应于线性近似：

在$\Delta w$很小时，这些近似是合理可靠的，线性近似的误差为：

$O(||\Delta w||_2^2)=\sum_{i=1}^d\Delta w_i^2$

2.2 二阶泰勒展开

$l(w+\Delta w)=l(w)+g(w)^T\Delta w+\frac12\Delta w^TH(w)\Delta w\\ H(w)为Hessian矩阵，[H(w)]_{i,j}=\frac{\partial^2 l(w)}{\partial w_i\partial w_j}$

二阶泰勒展开对应于二次近似：

二次近似的误差为：

$O(||\Delta w||_2^3)=(\sum_{i=1}^n\Delta w_i^2)^\frac32$

三、搜索方向方法

我们求解问题的目标是：寻找$w^*$使得$l(w)$取得最小值，我们需要研究寻找$w^*$的方向。

3.1 核心思想

给定一个初始点$w^0$，寻找一个迭代序列：$w^0\rightarrow w^1\rightarrow...\rightarrow w^k$，$w^k$表示第$k$次迭代找到的$w$，我们希望：$k\rightarrow\infty,w^k\rightarrow w^*$

我们的目的就是寻找一个步长$s$用于对$w$进行更新，更新过程：

$w^{k+1}=w^k+s$

由此我们得到了一个梯度下降过程的伪代码：

根据上述算法，我们便需要解决以下两个问题：
①如何寻找一个合理的步长$s$
②如何确定我们找到了$w^*$以跳出循环

3.2 梯度下降

我们需要寻找到一个使得函数梯度下降最快的方向，并朝该方向迈出一步。

考虑一阶泰勒展开：

$l(w^k+s)=l(w^k)+g(w^k)^Ts$

那么下降最快的方向就是$-g(w^k)$，因此我们在梯度下降过程中所作的就是：

$s=-\alpha g(w^k),\alpha>0$

正确性验证：我们需要验证的是总有一些足够小的$α$使得：

$l\big(w^k-\alpha g(w^k)\big)<l(w^k)$

根据泰勒展开：

$\begin{aligned} &l\big(w^k-\alpha g(w^k)\big)=l(w^k)-\alpha g(w^k)^Tg(w^k)+O(\alpha^2)\\ &\because g(w^k)^Tg(w^k)>0,\alpha\rightarrow0 过程中\alpha^2\rightarrow0的速度大于\alpha\\ &\therefore 存在足够小的\alpha，使得：l\big(w^k-\alpha g(w^k)\big)<l(w^k) \end{aligned}$

$α$的设定需要合理，太小的话会导致收敛过慢，太大的话会导致发散。

3.3 Adagrad算法

对于$α$的一个选择是：设置$α$使得步长适合于所有的特征，Adagrad算法通过保持每个优化变量的平方梯度的运行平均值来实现这一点

Adagrad算法为具有大梯度的变量设置小学习率，并为具有小梯度的特征设置大学习率。

Adagrad算法的伪代码如下：

该算法的特点是：每一个维度都有不同的学习率，第$j$维的学习率维：

$\frac{\alpha}{\sqrt{z_j+\epsilon}}$

3.4 牛顿方法

牛顿方法处理梯度下降利用二阶泰勒展开：

$l(w^k+s)=l(w^k)+g(w^k)^Ts+\frac12s^TH(w^k)s$

$H(w)=\left[ \begin{aligned} &\frac{\partial^2l(w)}{\partial w_1^2}~~\frac{\partial^2l(w)}{\partial w_1\partial w_2}~~...~~\frac{\partial^2l(w)}{\partial w_1\partial w_d}\\ &~~~~...~~~~~~~~~~...~~~~~~~~...~~~~~~~...\\ &\frac{\partial^2l(w)}{\partial w_d\partial w_1}~~\frac{\partial^2l(w)}{\partial w_d\partial w_2}~~...~~\frac{\partial^2l(w)}{\partial w_d^2}\\ \end{aligned} \right]$

因为我们假设$l(w)$是凸函数，则$H(w)$对所有$w$都是半正定的，则有：

$s^TH(w^k)s\ge0$

事实上，牛顿方法在严格的局部极小值附近有很好的性质，一旦足够接近一个解，它就会迅速收敛，为了便于分析，我们假设$H(w)$是正定的，即：

$s^TH(w^k)s>0$

二次近似的梯度为：

$\frac{\partial l(w^k+s)}{\partial s}=g(w^k)+H(w^k)s$

这意味着我们要找到的$w^*$满足：

$g(w^*)+H(w^*)s=0$

所以我们可以得到步长$s$：

$s=H(w^k)^{-1}g(w^k)$

3.4.1 Example

这有一个简单的例子清楚地说明了利用二阶泰勒展开的牛顿方法的优势：

假设损失函数实际上是严格的凸二次函数，即：

$l(w)=\frac12w^TAw+b^Tw+c$

其中$A$为正定矩阵，$b$为任意向量，$c$为任意常数，在这种情况下，牛顿方法仅需一步即可收敛：

$l(w)在Aw+b=0时收敛$

我们不妨以二维向量为例：

$A=\left[ \begin{aligned} &a_{11}~~~~a_{12}\\ &a_{21}~~~~a_{22}\\ \end{aligned} \right],w=[w_1,w_2]^T,b=[b_1,b_2]^T$

则损失函数则变为：

$l(w_1,w_2)=\frac12\big(a_{11}w_1^2+(a_{12}+a_{21})w_1w_2+a_{22}w_2^2\big)+(b_1w_1+b_2w_2)+c$

$\begin{aligned} &g(w)=\nabla l(w)=[\frac{\partial l(w)}{\partial w_1},\frac{\partial l(w)}{\partial w_2}]=[a_{11}w_1+(a_{12}+a_{21})w_2+b_1,a_{22}w_2+(a_{12}+a_{21})w_1+b_2] \end{aligned}$

$H(w)=\left[ \begin{aligned} &\frac{\partial^2l(w)}{\partial w_1^2}~~~~\frac{\partial^2l(w)}{\partial w_1\partial w_2}\\ &\frac{\partial^2l(w)}{\partial w_2\partial w_1}~~~~\frac{\partial^2l(w)}{\partial w_2^2} \end{aligned} \right]=\left[ \begin{aligned} &~~~~a_{11}~~~~a_{12}+a_{21}\\ &a_{12}+a_{21}~~~~a_{22} \end{aligned} \right]$

$H(w)^{-1}=\left[ \begin{aligned} &\frac{a_{22}}{a_{11}a_{22}-(a_{12}+a_{21})^2}~~~~\frac{-(a_{12}+a_{21})}{a_{11}a_{22}-(a_{12}+a_{21})^2}\\ &\frac{-(a_{12}+a_{21})}{a_{11}a_{22}-(a_{12}+a_{21})^2}~~~~\frac{a_{11}}{a_{11}a_{22}-(a_{12}+a_{21})^2} \end{aligned} \right]=\beta\left[ \begin{aligned} &~~~~a_{22}~~~~-(a_{12}+a_{21})\\ &-(a_{12}+a_{21})~~~~a_{11} \end{aligned} \right],\beta=\frac1{a_{11}a_{22}-(a_{12}+a_{21})^2}$

$s=-H(w)^{-1}g(w)=-\beta\left[ \begin{aligned} &(a_{11}a_{22}-(a_{12}+a_{21})^2)w_1+a_{22}b_1-(a_{12}+a_{21})b_2\\ &(a_{11}a_{22}-(a_{12}+a_{21})^2)w_2+a_{11}b_2-(a_{12}+a_{21})b_1 \end{aligned} \right]\\ =\left[ \begin{aligned} &-w_1+\frac{(a_{12}+a_{21})b_2-a_{22}b_1}{a_{11}a_{22}-(a_{12}+a_{21})^2}\\ &-w_2+\frac{(a_{12}+a_{21})b_1-a_{11}b_2}{a_{11}a_{22}-(a_{12}+a_{21})^2} \end{aligned} \right]$

则更新$w$的过程为：

$w=w+s=\left[ \begin{aligned} &\frac{(a_{12}+a_{21})b_2-a_{22}b_1}{a_{11}a_{22}-(a_{12}+a_{21})^2}\\ &\frac{(a_{12}+a_{21})b_1-a_{11}b_2}{a_{11}a_{22}-(a_{12}+a_{21})^2} \end{aligned} \right]$

为了便于讨论，我们不妨使得$A=I$，则有$w=[-b_1,-b_2]^T=-b$，则有$Aw+b=0$，仅通过一次更新即实现了收敛。

注意：
①$H(w)$是一个$d\times d$的矩阵，它的构造代价很大，一个很好的近似方法是只计算其对角线条目
②本质上这是梯度下降法和牛顿方法的结合，为了避免牛顿法的发散，一个好的方法是从梯度下降（甚至随机梯度下降）开始，然后完成优化牛顿法。通常，牛顿法使用的二阶近似值更可能接近最佳值