您的位置: 首页  >  文章  >  数学基础（一）：无约束优化问题

数学基础（一）：无约束优化问题

分类: 文章 • 2024-03-13 18:06:51

数学基础系列博客是自己在学习了稀牛学院&网易云课堂联合举办的《人工智能数学基础》微专业后的课程笔记总结。怀着对授课讲师Jason博士无限的敬佩与感激之情，我在完整听了两遍课程之后，对这门进行了笔记整理。Jason博士用深入浅出的方式把数学知识真的是讲透彻了，我的笔记显然无法完整传达Jason博士的精彩授课内容，在此非常推荐每一个打算进入或了解AI的同学去学习这门课程！

一：问题引入：线性回归问题

现在，我有如下一组关于病人收缩压的数据，包括患者姓名，性别，年龄，体重等信息，每一种信息为表中的一列。数据其中第6列为病人的收缩压。根据已有的这些数据记录，我需要对新的病例进行预测，那么怎么办呢？按照机器学习的方法，是首先对已有的数据进行训练，得到一个模型，然后利用该模型对新的未知病例进行预测。

数学基础（一）：无约束优化问题

符号说明：

1.{(x(i),y(i))}\left\{\left(x^{(i)}, y^{(i)}\right)\right\}是一个训练样本，其中上角标ii表示样本的编号；

2.{(x(i),y(i));i=1,⋯ ,N}\left\{\left(x^{(i)}, y^{(i)}\right) ; i=1, \cdots, N\right\}是训练样本集，共有NN个样本；

3.{(x1(i),x2(i),y(i))}→{(x(i),y(i))},x(i)=[x1(i)x2(i)]\left\{\left(x_{1}^{(i)}, x_{2}^{(i)}, y^{(i)}\right)\right\} \rightarrow\left\{\left(\mathbf{x}^{(i)}, y^{(i)}\right)\right\}, \mathbf{x}^{(i)}=\left[ \begin{array}{c}{x_{1}^{(i)}} \\ {x_{2}^{(i)}}\end{array}\right] ，将多个影响因素组合成一个向量表示。其中x(i)\mathbf{x}^{(i)}表示特征，y(i)y^{(i)}表示预测值（标签值）。

数学基础（一）：无约束优化问题

上图便是我们熟悉的线性回归模型，只不过是一维情况下的示意图。在实际的机器学习过程中，影响yy的因素肯定不只有一个，就拿上述收缩压的例子来讲，影响收缩压的因素就有性别，年龄等诸多因素。因此，一维情形下的线性回归模型肯定不能够满足要求。这就引出了多维情形下的线性回归模型。

以下对一维和多维情形下的线性回归问题进行对比观察：

  • 对于一维的线性回归，试图学习：f(x)=wx+bf(x)=w x+b，使得f(x(i))≈y(i)f\left(x^{(i)}\right) \approx y^{(i)}

  • 对于多维的线性回归，试图学习：f(x)=wTx+bf(\mathrm{x})=w^{T} \mathrm{x}+b，使得f(x(i))≈y(i)f\left(\mathrm{x}^{(i)}\right) \approx y^{(i)}，其中输入为向量，输出是标量。wTxw^{T}\mathrm{x}代表向量内积（或者称为向量点乘），最终的结果是一个具体的数字（标量）。在线性代数中，向量默认是列向量。

接下来，核心的问题就在于怎么学到ww和bb?

二：无约束优化梯度分析法

2.1 定义无约束优化问题

自变量为标量的函数ff: R→RR\rightarrow R:
min⁡f(x)x∈R \min f(x) \quad x \in {R}
自变量为向量的函数ff: Rn→RR^{n}\rightarrow R:
minf(x)x∈Rn minf(\mathrm{x}) \quad \mathrm{x} \in R^{n}
通过将一维和多维情形下的优化函数进行对比，我们可以清楚的明白，优化问题的目的是求一个函数的最小值。在一维情况下，自变量为标量，而在多元情况下，自变量变成向量，但是最优的函数值依旧是标量。在实际应用中，一元的情况很少见，最常见到的就是多元的情况，而且自变量x\mathrm{x}的维度有可能非常高。

优化问题可能的极值点情况：

数学基础（一）：无约束优化问题]

第一个图有极小值，第二个图有极大值，第三个图有鞍点(saddle point)，可以类比（y=x3x=0y = x^{3} \quad x = 0）的情况。第四张图中，既有极大值也有极小值，而且有局部极大（小）值。在实际的应用中，最常出现的是最后一种图，当维度很高时，我们有时候根本就不可能知道函数到底是什么样子的，也无法可视化。而且我们往往只能找到函数的局部极值，很难找到函数的全局最值（客观条件所限）。但是能够找到函数的局部极值也是非常有意义的。

2.2 梯度和Hessian矩阵

同样采用一阶和二阶对照的角度来理解

一阶导数和梯度：f′(x);g(x)=∇f(x)=∂f(x)∂x=[∂f(x)∂x1⋮∂f(x)∂xn]f'(x) ; \quad \mathbf{g}(\mathbf{x})=\nabla f(\mathbf{x})=\frac{\partial f(\mathbf{x})}{\partial \mathbf{x}}=\left[ \begin{array}{c}{\frac{\partial f(\mathbf{x})}{\partial x_{1}}} \\ {\vdots} \\ {\frac{\partial f(\mathbf{x})}{\partial x_{n}}}\end{array}\right]

注解：

  1. 导数的大小代表了函数在某个方向上变化的快慢；梯度的方向为函数值增加最快的方向。梯度本身是一个n维向量。

  2. 一阶导数为对x（标量）求导，二阶导数为对x\mathbf{x}(n维的向量）求导，结果为ff对向量中的每一个xx单独求导，然后组成一个向量（列向量）。

二阶导数和Hessian矩阵：
f′′(x);H(x)=∇2f(x)=[∂2f(x)∂x12∂2f(x)∂x1∂x2⋯∂2f(x)∂x1∂xn⋯∂2f(x)∂x2∂x1∂2f(x)∂x22∂2f(x)∂xn∂x1∂2f(x)∂xn∂x2⋯∂2f(x)∂xn2]=∇(∇f(x))T f^{\prime\prime}(x) ; \quad \mathbf{H}(\mathbf{x})=\nabla^{2} f(\mathbf{x})=\left[ \begin{array}{ccc}\begin{array}{ll}{\frac{\partial^{2} f(\mathbf{x})}{\partial x_{1}^{2}}} & {\frac{\partial^{2} f(\mathbf{x})}{\partial x_{1} \partial x_{2}}} & {\cdots} & {\frac{\partial^{2} f(\mathbf{x})}{\partial x_{1} \partial x_{n}} \cdots} \\ {\frac{\partial^{2} f(\mathbf{x})}{\partial x_{2} \partial x_{1}}} & {\frac{\partial^{2} f(\mathbf{x})}{\partial x_{2}^{2}}} \\ {\frac{\partial^{2} f(\mathbf{x})}{\partial x_{n} \partial x_{1}}} & {\frac{\partial^{2} f(\mathbf{x})}{\partial x_{n} \partial x_{2}}} & {\cdots} & {\frac{\partial^{2} f(\mathbf{x})}{\partial x_{n}^{2}}}\end{array}\end{array}\right]=\nabla(\nabla f(\mathbf{x}))^{T}

注解：

  1. 在多维情况下，二阶导数即为Hessian矩阵，在梯度的基础上再求一次导。是一个n∗*n的矩阵。
  2. Hessian矩阵其实是一个实对称矩阵，对角元相等。

2.3 二次型

2.3.1 定义

给定矩阵A∈Rn×n\mathbf{A} \in \mathbb{R}^{n \times n}，函数
xTAx=∑i=1nxi(Ax)i=∑i=1nxi(∑j=1naijxj)=∑i=1n∑j=1nxixjaij \mathbf{x}^{T} \mathbf{A} \mathbf{x}=\sum_{i=1}^{n} x_{i}(\mathbf{A} \mathbf{x})_{i}=\sum_{i=1}^{n} x_{i}\left(\sum_{j=1}^{n} a_{i j} x_{j}\right)=\sum_{i=1}^{n} \sum_{j=1}^{n} x_{i} x_{j} a_{i j}
被称为二次型。

  • 给定对称矩阵A∈Rn×n\mathbf{A} \in \mathbb{R}^{n \times n}，如果对于所有的x∈Rn\mathbf{x}\in{R }^n,有XTAx≥0\mathbf{X}^{T} \mathbf{A} \mathbf{x} \geq 0 ，则为半正定矩阵，此时特征值λ(A)≥0\lambda(\mathbf{A}) \geq 0.
  • 如果对于所有的x∈Rn,x≠0\mathbf{x} \in \mathbb{R}^n,\mathbf{x}\neq0，有XTAx>0\mathbf{X}^{T} \mathbf{A} \mathbf{x} > 0 ，则为正定矩阵。反之，如果小于0，则为负定矩阵，否则为不定矩阵。

上式注解：

1.A是一个实对称矩阵。

2.Ax\mathbf{A} \mathbf{x}的乘积可以看作是一个列向量，然后与xT\mathbf{x}^{T}相乘。这样其实就是两个列向量做点乘，结果是一个具体的数（标量）。

3.可以类比x∗2∗x>0x*2*x >0,此时对于任意的x(x不为0)，函数值均大于0，此时2为正数。

2.3.2 具体计算

  • 向量a\mathbf{a}与x\mathbf{x}无关，则∇(aTx)=a,∇2(aTx)=0\nabla\left(\mathbf{a}^{T} \mathbf{x}\right)=\mathbf{a}, \nabla^{2}\left(\mathbf{a}^{T} \mathbf{x}\right)=\mathbf{0}

  • 对称矩阵A\mathbf{A}与x\mathbf{x}无关，则∇(xTAx)=2Ax,∇2(xTAx)=2A\nabla\left(\mathbf{x}^{T} \mathbf{A} \mathbf{x}\right)=\mathbf{2} \mathbf{A} \mathbf{x}, \nabla^{2}\left(\mathbf{x}^{T} \mathbf{A} \mathbf{x}\right)=2 \mathbf{A} （可类比(ax2)′=2ax;(ax2)′′=2a(ax^2)'=2ax;(ax^2)''=2a.

  • 最小二乘：
    f(x)=∥Ax−b∥22=(Ax−b)T(Ax−b)=xTATAx−xTATb−bTAx+bTb=xTATAx−2bTAx+bTb∇f(x)=2ATAx−2ATb f(\mathrm{x})=\|\mathbf{Ax}-\mathbf{b}\|_{2}^{2}\\=(\mathbf{Ax}-\mathbf{b})^{T}(\mathbf{Ax}-\mathbf{b})\\ =\mathbf{x}^{T} \mathbf{A}^{T} \mathbf{A} \mathbf{x}- \mathbf{x}^{T}\mathbf{A}^{T}\mathbf{b} - \mathbf{b}^{T} \mathbf{A} \mathbf{x}+\mathbf{b}^{T} \mathbf{b}\\=\mathbf{x}^{T} \mathbf{A}^{T} \mathbf{A} \mathbf{x}-2 \mathbf{b}^{T} \mathbf{A} \mathbf{x}+\mathbf{b}^{T} \mathbf{b}\\\nabla f(\mathbf{x})=2 \mathbf{A}^{T} \mathbf{Ax}-2 \mathbf{A}^{T} \mathbf{b}

2.4 泰勒级数

2.4.1 泰勒级数展开（标量和向量）

  • 输入为标量的泰勒级数展开
    f(xk+δ)≈f(xk)+f′(xk)δ+12f′′(xk)δ2+⋯+1k!fk(xk)δk+⋯ f\left(x_{k}+\delta\right) \approx f\left(x_{k}\right)+f^{\prime}\left(x_{k}\right) \delta+\frac{1}{2} f^{\prime \prime}\left(x_{k}\right) \delta^{2}+\cdots+\frac{1}{k !} f^{k}\left(x_{k}\right) \delta^{k}+\cdots

  • 输入为向量的泰勒级数展开
    f(xk+δ)≈f(xk)+gT(xk)δ+12δTH(xk)δ f\left(\mathbf{x}_{k}+\boldsymbol{\delta}\right) \approx f\left(\mathbf{x}_{k}\right)+\mathbf{g}^{T}\left(\mathbf{x}_{k}\right) \boldsymbol{\delta}+\frac{1}{2} \boldsymbol{\delta}^{T} \mathbf{H}\left(\mathbf{x}_{k}\right) \boldsymbol{\delta}

注解

  1. 理解向量情况时，与标量情况进行对照理解。

  2. gT(xk)\mathbf{g}^{T}\left(\mathbf{x}_{k}\right)为梯度的转置（由列向量转变为行向量），相当于求一阶导数。H(xk)\mathbf{H}\left(\mathbf{x}_{k}\right)为Hessian矩阵，相当于求二阶导数。因为后边的高阶项数值太小，因此只保留到二阶项。

  3. δ\boldsymbol{\delta}可正可负，代表x周边很小的一个值。

2.4.2 泰勒级数和极值

标量情况

  • 输入为标量的泰勒级数展开：（保留到二阶项）
    f(xk+δ)≈f(xk)+f′(xk)δ+12f′′(xk)δ2 f\left(x_{k}+\delta\right) \approx f\left(x_{k}\right)+f^{\prime}\left(x_{k}\right) \delta+\frac{1}{2} f^{\prime \prime}\left(x_{k}\right) \delta^{2}
  • 严格的局部极小点是指：f(xk+δ)>f(xk)f\left(x_{k}+\delta\right)>f\left(x_{k}\right)
  • 称满足f′(x)=0f'(x)=0的点为平稳点（候选点）
  • 函数在xkx_k由严格局部极小值的条件为f′(x)=0f'(x)=0且f′′(x)>0f''(x)>0.

向量情况（一定对照标量情况理解）

  • 输入为向量的泰勒级数展开：（保留到二阶项）
    f(xk+δ)≈f(xk)+gT(xk)δ+12δTH(xk)δ f\left(\mathbf{x}_{k}+\boldsymbol{\delta}\right) \approx f\left(\mathbf{x}_{k}\right)+\mathbf{g}^{T}\left(\mathbf{x}_{k}\right) \boldsymbol{\delta}+\frac{1}{2} \boldsymbol{\delta}^{T} \mathbf{H}\left(\mathbf{x}_{k}\right) \boldsymbol{\delta}

  • 称满足g(xk)=0g(\mathbf{x_k})=0的点为平稳点（候选点），此时如果H(xk)\mathbf{H(x_k)}为正定矩阵，则xk\mathbf{x_k}为一严格局部极小点；如果为负定矩阵，则为严格局部极大点；如果为不定矩阵，则为鞍点（saddle point）。

通过2.4.1和2.4.2的分析，我们可以发现，当我们想要求函数的极小值时，首先需要找到一阶导数为0的点，然后再判断这些点处二阶导数的情况。但是实际中，当求解梯度为0时存在一些局限性。比如：

计算f(x)=x4+sin⁡(x2)−ln⁡(x)ex+7f(x)=x^{4}+\sin \left(x^{2}\right)-\ln (x) e^{x}+7的导数。
f′(x)=4x(4−1)+d(x2)dxcos⁡(x2)−d(ln⁡x)dxex−ln⁡(x)d(ex)dx+0=4x3+2xcos⁡(x2)−1xex−ln⁡(x)ex \begin{aligned} f'(x) &=4 x^{(4-1)}+\frac{d\left(x^{2}\right)}{d x} \cos \left(x^{2}\right)-\frac{d(\ln x)}{d x} e^{x}-\ln (x) \frac{d\left(e^{x}\right)}{d x}+0 \\ &=4 x^{3}+2 x \cos \left(x^{2}\right)-\frac{1}{x} e^{x}-\ln (x) e^{x} \end{aligned}
从上面的结果中可以看出，当f′(x)=0f'(x)=0时，很难通过直接求导等于0的方法求出显式解。此时，我们就需要采用另外的方法来解决这个问题，此时，无约束优化迭代法应运而生。

三：无约束优化迭代法

3.1 迭代法的基本结构（最小化f(x)f(x))

  1. 选择一个初始点，设置一个收敛容忍度ϵ\epsilon，计数k=0k=0
  2. 决定搜索方向dk\mathbf{d_k}，使得函数下降。（核心步骤）算法与算法最本质的区别就在于搜索方向的不同
  3. 决定步长αk\alpha_k，使得f(xk+αkdk)f(\mathbf{x_k+\alpha_kd_k})对于αk≥0\mathbf{\alpha_k\geq0}最小化，构建xk+1=xk+αkdk\mathbf{x_{k+1}=x_k+\alpha_kd_k}
  4. 如果∣∣dk∣∣2<ϵ||\mathbf{d_k}||_2<\epsilon,则停止迭代（说明梯度已经非常小了，这时已经非常接近极值点了）；否则继续迭代

αk\alpha_k太大，则容易在最低值处震荡，甚至冲过最低点导致不收敛。如果太小，则收敛速度会很慢，在实际应用中，这个值就是需要调的参数。

数学基础（一）：无约束优化问题]

3.2 梯度下降法

  • 方向选取： dk=−g(xk)\mathbf{d_k=-g(x_k)}(最重要)

原因分析：

我们展开泰勒级数，只保留一阶项，则f(xk+dk)≈f(xk)+gT(xk)dk\mathbf {f(x_k+d_k)\approx f(x_k)+g^{T}(x_k)d_k },既然要使得函数值下降，则必须要使得f(xk+dk)<f(xk)\mathbf {f(x_k+d_k)< f(x_k)}，也即是要求gT(xk)dk<0\mathbf{g^{T}(x_k)d_k}<0，这就说明是两个向量的内积小于0，相当于两个向量的夹角大于90度（−1≤cos(θ)≤1-1\leq cos(\theta)\leq1）。 当夹角为180度时，两个向量的内积最小（绝对值最大），此时dk=−g(xk)\mathbf{d_k=-g(x_k)}，f(xk+dk)\mathbf {f(x_k+d_k)}下降最多。

注释

  1. 两个向量的内积a⋅b=aTb=∣∣a∣∣∣∣b∣∣cos(θ)\mathbf{a\cdot b = a^Tb=||a|| ||b|| cos(\theta)}
    数学基础（一）：无约束优化问题

  2. 在保留一阶项的时候，梯度下降法是最优的方法，所选取的负梯度方向为最优的方向；但是这并不代表负梯度方向就是全局最优的方向，因为我们把二阶项给舍弃了。

3.3 牛顿法

3.3.1 牛顿法介绍

方向：dk=−H−1(xk)g(xk)\mathbf{d_k=-H^{-1}(x_k)g(x_k)}

方向选取的依据：
f(xk+dk)=f(xk)+gT(xk)dk+12dkTH(xk)dk f\left(\mathbf{x}_{k}+\mathbf{d}_{k}\right)=f\left(\mathbf{x}_{k}\right)+\mathbf{g}^{T}\left(\mathbf{x}_{k}\right) \mathbf{d}_{k}+\frac{1}{2} \mathbf{d}_{k}^{T} \mathbf{H}\left(\mathbf{x}_{k}\right) \mathbf{d}_{k}
在上面这个式子中，xk\mathbf{x_k}是已知的，dk\mathbf{d_k}是未知的。我们的目的是找到一个dk\mathbf{d_k}使得f(xk+dk)\mathbf{f({x}_{k}+\mathbf{d}_{k})}最小，因此我们对dk\mathbf{d_k}求导，得到：
∂f(xk+dk)∂dk=0⇒g(xk)+H(xk)dk=0 \frac{\partial f\left(\mathbf{x}_{k}+\mathbf{d}_{k}\right)}{\partial \mathrm{d}_{k}}=\mathbf{0} \Rightarrow \mathbf{g}\left(\mathbf{x}_{k}\right)+\mathbf{H}\left(\mathbf{x}_{k}\right) \mathbf{d}_{k}=\mathbf{0}
如果Hessian正定，则有dk=−H−1(xk)g(xk)\mathbf{d}_{k}=-\mathbf{H}^{-1}\left(\mathbf{x}_{k}\right) \mathbf{g}\left(\mathbf{x}_{k}\right)。

**注：**需要强制要求Hessian矩阵正定。原因如下：

（1）把dk\mathbf{d_k}的结果表达式代入，可得：f(xk+dk)=f(xk)−1/2gT(xk)H−1(xk)g(xk)f(\mathbf{x_k+d_k})=f\mathbf{(x_k)-1/2g^T(x_k)H^{-1}(x_k)g(x_k)},只有当H−1(xk)\mathbf{H^{-1}(x_k)}正定，也就是H(xk)\mathbf{H(x_k)}正定时，才能保证f(xk+dk)<f(xk)f(\mathbf{x_k+d_k}) <f\mathbf{(x_k)},即函数值下降。

（2）只有当H正定时，才能保证H可逆，才能求得dk\mathbf{d_k}。

3.3.2 应用牛顿法的困难点

  1. 在实际工程中，Hessian矩阵H\mathbf{H}很难求，而H−1\mathbf{H^{-1}}更加难求。而且H\mathbf{H}本身可能就不是正定矩阵。
  2. 解决办法：
    • 修正牛顿法：当Hessian矩阵不是正定矩阵时，可以对Hessian矩阵进行修正：H(xk)+E\mathbf{H(x_k)+E}，典型方法E=δI，δ>0\mathbf{E=\delta I}，\delta>0很小。这样做的目的是：通过添加一个单位阵，让E\mathbf{E}中最小的特征值也大于0，这就就可以保证修正后的Hessian矩阵是正定的，然后再求逆矩阵。
    • 拟牛顿法

3.4 拟牛顿法

3.4.1 核心思想

  • 统一看待梯度下降法和牛顿法：

dk=−Skgk \mathbf{d_k=-S_kg_k}

​ 其中：Sk={I steepest Hk−1 Newton \mathbf{S}_{k}=\left\{\begin{array}{ll}{\mathbf{I}} & {\text { steepest }} \\ {\mathbf{H}_{k}^{-1}} & {\text { Newton }}\end{array}\right.

  • 由于牛顿法的困难之处在于H−1\mathbf{H^{-1}}很难求，那么我们可以尝试这样的思路，不直接求Hk−1\mathbf{H^{-1}_k},而是尝试用一个正定矩阵去逼近Hk−1\mathbf{H^{-1}_k}。

  • 定义δk=xk+1−xk,γk=gk+1−gk\mathbf{\delta_k = x_{k+1}-x_k,\gamma_k = g_{k+1}-g_k}

  • 用于近似Hk−1\mathbf{H^{-1}_k}的矩阵应满足这样的条件：Sk+1γk=δk\mathbf{S_{k+1}\gamma_k=\delta_k}

    • 理解方式：gk+1−gkxk+1−xk=Hk\mathbf{\frac{g_{k+1}-g_k}{x_{k+1}-x_k}=H_k},因此，就可以得到Sk+1:=δkγk=Hk−1\mathbf{S_{k+1}:=\frac{\delta_k}{\gamma_k}=H^{-1}_k}，当满足Sk+1γk=δk\mathbf{S_{k+1}\gamma_k=\delta_k}时，Sk+1\mathbf{S_{k+1}}可用来近似H−1\mathbf{H^{-1}}

    • 注意：关于Sk+1\mathbf{S_{k+1}}的推导是不严谨的，仅仅通过上述方法用于理解思想。（即一阶导数再求导，便可以得到二阶导数）

  • 只有δk\mathbf{\delta_k}和γk\mathbf{\gamma_k}是不可能计算出Sk+1\mathbf{S_{k+1}}的(因为δk\mathbf{\delta_k}和γk\mathbf{\gamma_k}都是向量，不能直接做除法)，因此，我们继续考虑使用迭代的方法。

3.4.2 DFP法

  • 给定初始S0=I\mathbf{S_0=I}

  • Sk+1=Sk+ΔSk,k=0,1,⋯\begin{array}{l}{\mathbf{S}_{k+1}=\mathbf{S}_{k}+\Delta \mathbf{S}_{k}, k=0,1, \cdots}\end{array}

  • ΔSk=αuuT+βvvT,{\Delta \mathbf{S}_{k}=\alpha \mathbf{u} \mathbf{u}^{T}+\beta \mathbf{v} \mathbf{v}^{T}, }因此
    Sk+1=Sk+αuuT+βvvT \mathbf{S}_{k+1}=\mathbf{S}_{k}+\alpha \mathbf{u} \mathbf{u}^{T}+\beta \mathbf{v} \mathbf{v}^{T}

  • 两边同时乘γk\mathbf{\gamma_k},有δk=Skγk+(αuTγk)⎵1u+(βvTγk)⎵−1v=Skγk+u−v\delta_{k}=\mathbf{S}_{k} \gamma_{k}+\underbrace{\left(\alpha \mathbf{u}^{T} \gamma_{k}\right)}_{1} \mathbf{u}+\underbrace{\left(\beta \mathbf{v}^{T} \gamma_{k}\right)}_{-1} \mathbf{v}=\mathbf{S}_{k} \gamma_{k}+\mathbf{u}-\mathbf{v}，令αuTγk=1,βvTγk=−1\alpha \mathbf{u}^{T} \gamma_{k}=1,\beta \mathbf{v}^{T} \gamma_{k}=-1（类似待定系数法）

  • 解得：α=1uTγk,β=−1vTγk\alpha=\frac{1}{\mathbf{u}^{T} \gamma_{k}}, \beta=-\frac{1}{\mathbf{v}^{T} \gamma_{k}}且u−v=δk−Skγk\mathbf{u}-\mathbf{v}=\boldsymbol{\delta}_{k}-\mathbf{S}_{k} \gamma_{k}，可得u=δk；v=Skγk\mathbf{u}=\boldsymbol{\delta}_{k}；\mathbf{v}=\mathbf{S}_{k} \gamma_{k}，从而最终解得DFP更新公式：
    Sk+1=Sk+δkδkTδkTγk−SkγkγkTSkγkTSkγk \mathbf{S}_{k+1}=\mathbf{S}_{k}+\frac{\delta_{k} \boldsymbol{\delta}_{k}^{T}}{\delta_{k}^{T} \gamma_{k}}-\frac{\mathbf{S}_{k} \gamma_{k} \gamma_{k}^{T} \mathbf{S}_{k}}{\gamma_{k}^{T} \mathbf{S}_{k} \gamma_{k}}
    注意：Sk\mathbf{S_k}是对称矩阵，其转置和自身相等。

3.4.3 BFGS法

思想与DFP方法一致，区别在于ΔSk\Delta\mathbf{S_k}的选取不一致。一般来讲，BFGS法在数值上更稳定一些。

更新公式：
 Broyden-Fletcher-Goldfarb-Shanno (BFGS): S0=ISk+1=Sk+(1+γkTSkγkδkTγk)δkδkTδkTγk−δkγkTSk+SkγkδkTδkTγk \begin{array}{c}{\text { Broyden-Fletcher-Goldfarb-Shanno (BFGS): } \mathbf{S}_{0}=\mathbf{I}} \\ {\mathbf{S}_{k+1}=\mathbf{S}_{k}+\left(1+\frac{\gamma_{k}^{T} \mathbf{S}_{k} \gamma_{k}}{\delta_{k}^{T} \gamma_{k}}\right) \frac{\delta_{k} \boldsymbol{\delta}_{k}^{T}}{\delta_{k}^{T} \gamma_{k}}-\frac{\delta_{k} \gamma_{k}^{T} \mathbf{S}_{k}+\mathbf{S}_{k} \gamma_{k} \boldsymbol{\delta}_{k}^{T}}{\delta_{k}^{T} \gamma_{k}}}\end{array}

3.5 步长选取问题

第一种方法：每次迭代选择固定的步长。这种方法在实际中最常用，例如αk=α=0.1\alpha_{k}=\alpha=0.1。

第二种方法：每次选取最优步长。例如，对于二次型问题：f(x)=xTAx+2bTx+cf\mathbf{(x)}=\mathbf{x^TAx+2b^Tx}+c,

需要解：min⁡α≥0f(x+αd)\mathop {\min }\limits_{\alpha \ge0} f(\mathbf{x}+\alpha\mathbf{d}),令h(α)=f(x+αd)h(\alpha)=f(\mathbf{x}+\alpha\mathbf{d})，则∂h(α)∂α=0⇒α=−dT∇f(x)2dTAd\frac{\partial h(\alpha)}{\partial \alpha}=0 \Rightarrow \alpha=-\frac{\mathbf{d}^{T} \nabla f(\mathbf{x})}{2 \mathbf{d}^{T} \mathbf{A} \mathbf{d}}。该α\alpha即为每次迭代时的最优步长。

推导计算
h(α)=(x+αd)TA(x+αd)+2bT(x+αd)+c=(xTA+αdTA)(x+αd)+2bT(x+αd)+c=xTAx+αdTAx+αxTAd+α2dTAd+2bTx+2αbTd+c∂h(α)∂α=dTAx+xTAd+2αdTAd+2bTd=02xTAd+2αdTAd+2bTd=0α=xTAd+bTd−dTAd=dTAx+dTb−dTAd=dT(2Ax+2b)−2dTAd=dT∇f(x)−2dTAd h(\alpha)=(\mathbf{x}+\alpha\mathbf{d})^T\mathbf{A}(\mathbf{x}+\alpha\mathbf{d})+2\mathbf{b^T(\mathbf{x}+\alpha\mathbf{d})}+c\\ =(\mathbf{x^T}\mathbf{A}+\alpha\mathbf{d^T}\mathbf{A})(\mathbf{x}+\alpha\mathbf{d})+2\mathbf{b^T(\mathbf{x}+\alpha\mathbf{d})}+c\\ =\mathbf{x^TAx}+\alpha\mathbf{d^TAx}+\alpha\mathbf{x^TAd}+\alpha^2\mathbf{d^TAd}+2\mathbf{b^Tx}+2\alpha\mathbf{b^Td}+c\\ \frac{\partial h(\alpha)}{\partial \alpha}=\mathbf{d^TAx}+\mathbf{x^TAd}+2\alpha\mathbf{d^TAd}+2\mathbf{b^Td}=0\\2\mathbf{x^TAd}+2\alpha\mathbf{d^TAd}+2\mathbf{b^Td}=0\\\alpha=\frac{\mathbf{x^TAd}+\mathbf{b^Td}}{-\mathbf{d^TAd}}=\frac{\mathbf{d^TAx}+\mathbf{d^Tb}}{-\mathbf{d^TAd}}=\frac{\mathbf{d^T}(2\mathbf{Ax}+2\mathbf{b})}{-2\mathbf{d^TAd}}=\frac{\mathbf{d^T}\nabla f(\mathbf{x})}{-2\mathbf{d^TAd}}
注：当采用梯度下降法时，d=−g=−∇f(x)\mathbf{d=-g}=-\nabla f(\mathbf{x}),α=∣∣∇f((x)∣∣222dTAd\alpha=\frac{||\nabla f(\mathbf(x)||^2_2}{2\mathbf{d^TAd}}；当采用牛顿法或者拟牛顿法时，d=−Sg\mathbf{d=-Sg}.

通过以上求解，可以得到每次迭代时的最优步长。

四：线性回归求解

4.1 利用梯度等于0直接求解

对于一个线性回归问题，我们试图学习到这样一个模型 ：f(x)=wTx+bf(\mathbf{x})=\mathbf{w^Tx}+b，使得f(x(i))≈y(i)f(\mathbf{x}^{(i)}) \approx y^{(i)}。关键在于如何学习得到w\mathbf{w}和bb。

  • 令w‾=[wb]\overline{\mathbf{w}}=\left[ \begin{array}{l}{\mathbf{w}} \\ {b}\end{array}\right],X=[x(1)T1⋮⋮x(N)T1]N×(d+1)\mathbf{X}=\left[ \begin{array}{cc}{\mathbf{x}^{(1) T}} & {1} \\ {\vdots} & {\vdots} \\ {\mathbf{x}^{(N) T}} & {1}\end{array}\right]_{N \times(d+1)},则有y≈Xw‾\mathbf{y} \approx \mathbf{X} \overline{\mathbf{w}}。

  • 损失函数：∥y−Xw‾∥22\|\mathbf{y}-\mathbf{X} \overline{\mathbf{w}}\|_{2}^{2}，我们的目标在于求解使得损失函数最小的w‾\overline{\mathbf{w}}和bb。即：
    min⁡W‾,b∥y−Xw‾∥22 \mathop {\min }\limits_{\overline{\mathbf{W}},b}\|\mathbf{y}-\mathbf{X} \overline{\mathbf{w}}\|_{2}^{2}

  • 损失函数对w‾\overline{\mathbf{w}}求导，令导函数为0可得：
    g(w‾)=0⇒2XT(Xw‾−y)=0⇒w‾∗=(XTX)−1XTy g(\overline{\mathbf{w}})=0 \Rightarrow 2 \mathbf{X}^{T}(\mathbf{X} \overline{\mathbf{w}}-\mathbf{y})=0 \Rightarrow \overline{\mathbf{w}}^{*}=\left(\mathbf{X}^{T} \mathbf{X}\right)^{-1} \mathbf{X}^{T} \mathbf{y}

这样便可以直接求得最优参数，但是我们也观察到结果中存在求逆的步骤。求逆的运算量特别大，在实际工程中一般都会避免，并且，也不一定在任何情形下均可以求逆。因此，我们可以采用梯度下降法来进行迭代。

4.2 梯度下降法求解

  • 梯度下降法

g(w‾)=2XT(Xw‾−y)=2∑i=1NX(i)(w‾TX(i)−y(i))w‾←w‾−αg(w‾) \begin{aligned} \mathbf{g}(\overline{\mathbf{w}}) &=2 \mathbf{X}^{T}(\mathbf{X} \overline{\mathbf{w}}-\mathbf{y}) \\=& 2 \sum_{i=1}^{N} \mathbf{X}^{(i)}\left(\mathbf{\overline{\mathbf{w}}}^{T} \mathbf{X}^{(i)}-y^{(i)}\right) \\ & \overline{\mathbf{w}} \leftarrow \overline{\mathbf{w}}-\alpha \mathbf{g}(\overline{\mathbf{w}}) \end{aligned}

注意：其中X(i)=[x(i)T,1]T\mathbf{X}^{(i)}=[\mathbf{x}^{(i)T},1]^T.是一个列向量。

  • 随机梯度下降法(SGD),在实际中很常用。其实就是把梯度下降法中的求和运算去掉，每次更新时，只选择一个样本进行计算。
    {i=1:N,2X(i)(w‾TX(i)−y(i))} \left\{i=1 : N, 2 \mathbf{X}^{(i)}\left(\mathbf{\overline{w}}^{T} \mathbf{X}^{(i)}-y^{(i)}\right)\right\}

  • 当∣∣g(w‾)∣∣2<ϵ||\mathbf{g}(\overline{\mathbf{w}})||_2<\epsilon时，停止迭代。

相关推荐