线性代数|机器学习-P23梯度下降

1. 梯度下降

1.1 线搜索方法，运用一阶导数信息[线搜索方法]

• 迭代公式：
  $$\begin{array}{c}{x}_{k+1}=x_k-s_k\nabla f(x_k)\end{array}$$
• 步长：$s_k$，也叫学习率
• 方向：$-\nabla f(x_k)$负梯度方向

1.2 经典牛顿方法，运用二阶导数信息

详细推导请点击链接

• 迭代公式：
  $$\begin{array}{c}{x}_{k+1}=x_k-[H_{jk}{]}^{-1}\nabla f(x)\end{array}$$
• 步长：$s_k=1$，把步长和方向结合起来放到方向里面去了。
• 方向： hessian matrix 可逆时$[H_{jk}{]}^{-1}\nabla f(x)$

2. hessian矩阵和凸函数

• 如果hessian matrix$H_{jk}$是半正定矩阵[positive semi-definite]或正定矩阵[positive definite]可得为函数是一般凸函数
• 如果hessian matrix$H_{jk}$是正定矩阵[positive definite]可得为函数是强凸函数

2.1 实对称矩阵函数求导

假设我们有一个实对称矩阵S和二次型函数表示如下：
S = [ 1 0 0 b ] , f ( x ) = 1 2 x T S x = 1 2 ( x 2 + b y 2 )

$$\begin{equation} S=\begin{bmatrix}1&0\\\\0&b\end{bmatrix},f(x)=\frac{1}{2}x^TSx=\frac{1}{2}(x^2+by^2) \end{equation}$$ S= ​10​0b​ ​,f(x)=21​xTSx=21​(x2+by2)​​

• 矩阵S的特征值,条件数$\kappa (S)$分别表示如下,假设$b<1$：
  $$\begin{array}{c}{\lambda }_{\max }=1,{\lambda }_{\min }=b,\kappa (S)=\frac{1}{b}\end{array}$$
• 通过$f(x)$函数可以明显看出最小值点为(0,0)
  $$\begin{array}{c}\underset{x^{\ast }=0}{\mathrm{argmin}}f(x)=0\end{array}$$
• 函数一阶导数如下：
  $$\begin{array}{c}\frac{\mathrm{d}f(x,y)}{\mathrm{d}X}=\frac{\mathrm{d}\frac{1}{2}{X}^{T}SX}{\mathrm{d}X}=SX=\left[\begin{array}{cc}1& 0\\ & \\ 0& b\end{array}\right]\left[\begin{array}{c}x\\ \\ y\end{array}\right]=\left[\begin{array}{c}x\\ \\ by\end{array}\right]\end{array}$$
• 函数二阶导数如下：
  $$\begin{array}{c}\frac{{\mathrm{d}}^{2}f(x,y)}{\mathrm{d}{X}^2}=S=\left[\begin{array}{cc}1& 0\\ & \\ 0& b\end{array}\right]\end{array}$$

2.2. 线性函数求导

假设我们有如下函数：
f ( x , y ) = 2 x + 5 y = [ 2 5 ] [ x y ] = A T X , A = [ 2 5 ]

$$\begin{equation} f(x,y)=2x+5y=\begin{bmatrix}2&5\end{bmatrix}\begin{bmatrix}x\\\\y\end{bmatrix}=A^TX,A=\begin{bmatrix}2\\\\5\end{bmatrix} \end{equation}$$ f(x,y)=2x+5y=[2​5​] ​xy​ ​=ATX,A= ​25​ ​​​

• 函数的一次导数如下：
  $$\begin{array}{c}\frac{\mathrm{d}f(x,y)}{\mathrm{d}X}=\frac{\mathrm{d}{A}^{T}X}{\mathrm{d}X}=A=\left[\begin{array}{c}2\\ \\ 5\end{array}\right]\end{array}$$
• 函数的二阶偏导 hessian matrix 如下：[向量对向量求导，XY拉伸术]
  $$\begin{array}{c}{H}_{jk}=\left[\begin{array}{cc}0& 0\\ & \\ 0& 0\end{array}\right]\end{array}$$
• 对于函数$f(x)=2x+5y$来说，依据线搜索方法，其负梯度方向为最佳迭代方向。

3. 无约束条件下的最值问题

假设我们有一个函数表示如下：
f ( x ) = 1 2 x T S x − a T x − b

$$\begin{equation} f(x)=\frac{1}{2}x^TSx-a^Tx-b \end{equation}$$ f(x)=21​xTSx−aTx−b​​

• $f(x)$导数如下：
  $$\begin{array}{c}\frac{\mathrm{d}f(x)}{\mathrm{d}x}=Sx-a;\frac{{\mathrm{d}}^{2}f(x)}{\mathrm{d}{x}^2}=H_{jk}=S\end{array}$$
• 函数$f(x)$的最小值满足其一次导数为零，即表示如下：
  $$\begin{array}{c}{f}^{\prime }(x^{\ast })=0,S{x}^{\ast }-a=0\to x^{\ast }=S^{-1}a\end{array}$$
• 整理可得：
  $$\begin{array}{c}{f}_{\min }(x)=\underset{x=x^{\ast }=S^{-1}a}{\min }f(x)=-\frac{1}{2}{a}^T{S}^{-1}a-b\end{array}$$
  $$\begin{array}{c}\underset{x=x^{\ast }}{\mathrm{argmin}}f(x)=S^{-1}a\end{array}$$

4. 正则化

4.1 定义

• Log-determinant regularization
  Log-determinant regularization 通过在损失函数中加入一个负对数行列式项来约束矩阵X的结构。具体形式为
  $$\begin{array}{c}Penalty=-\log (\det (X))\end{array}$$
• 其中X通常是一个正定矩阵， 这一正则化项有利于确保X的特征值远离零，从而避免数值不稳定性和病态矩阵的出现

4.2 性质

• 凸性： $-\log (\det (X))$是一个凸函数，这意味着优化问题中，局部最小值也是全局最小值
• 梯度： $\nabla f(x)=-X^{-1}$
  $$\begin{array}{c}f(x)=-\log (\det (X))\to \frac{\mathrm{d}f(x)}{\mathrm{d}x}=\frac{1}{\det (X)}\cdot [\det (X)\cdot (X^{-1}{)}^T]=X^{-1}\end{array}$$
• hessian matrix：
  $$\begin{array}{c}{H}_{jk}=X^{-1}H{X}^{-1}，H是一个对称矩阵\end{array}$$

5. 回溯线性搜索法

对于线搜索方法来说，迭代公式如下，但是对于步长的选择来说，我们如果选择步长$s_k$太大，那么就很容易越过极值点，在极值点不断跳跃和震荡，如果步长$s_k$太小，那么迭代太慢，没有效果

• 迭代公式：
  $$\begin{array}{c}{x}_{k+1}=x_k-s_k\nabla f(x_k)\end{array}$$
• 步长： $s_k$
• 方向： 负梯度方向 $-\nabla f(x_k)$

那么我们希望找到一个步长 $s_k$使得在搜索方向上使得$f(x_{k+1})$最小，这样就不是固定步长了，相当于动态步长
s k ∗ = arg min ⁡ s k f ( x k + 1 )

$$\begin{equation} s_k^*= \argmin\limits_{s_k} f(x_{k+1}) \end{equation}$$ sk∗​=sk​argmin​f(xk+1​)​​

• 步骤：先固定步长$s_k=s_0$，再取半步长$s_k=\frac{1}{2}{s}_0$,再取半步长$s_k=\frac{1}{4}{s}_0$,
• 假设我们有如下一个损失函数如下：
  $$\begin{array}{c}S=\left[\begin{array}{cc}1& 0\\ & \\ 0& b\end{array}\right],f(x)=x^{T}Sx=x^2+b{y}^2\end{array}$$
• 迭代公式如下：
  $$\begin{array}{c}{x}_{k+1}=x_k-s_k\nabla f(x_k),\nabla f(x_k)=2Sx\end{array}$$
• 向量化如下 :$x=[x,y{]}^T$
  $$\begin{array}{c}{\left[\begin{array}{c}x\\ \\ y\end{array}\right]}_{k+1}={\left[\begin{array}{c}x\\ \\ y\end{array}\right]}_k-s_k{\left[\begin{array}{c}2x\\ \\ 2by\end{array}\right]}_k\end{array}$$
• 假设我们定义初始点 $p_0=(x_0,y_0)=(b,1)$
• 步长$s_k=\frac{1}{x_0+y_0}=\frac{1}{b+1}$这里没弄懂，后续再研究，反推出来的
  $$\begin{array}{c}{x}_k=b(\frac{b-1}{b+1}{)}^k,y_k=(\frac{1-b}{1+b}{)}^k,f_k=(\frac{1-b}{1+b}{)}^k{f}_0\end{array}$$
• 函数$f(x)=x^2+b{y}^2=c$是一个椭圆形图像，随着c的变化不断变化,也就是做函数的最小值是之字型不断地趋近于最小，就像不同的椭圆进行等比缩小，最终求得最小值。