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

1. 梯度下降

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

• 迭代公式：
  x k + 1 = x k − s k ∇ f ( x k )
  xk+1=xk−sk∇f(xk)" role="presentation">xk+1=xk−sk∇f(xk)$$x_{k+1}=x_k-s_k\mathrm{\nabla }f(x_k)$$
  xk+1​=xk​−sk​∇f(xk​)​​
• 步长：$s_k$，也叫学习率
• 方向：$-\nabla f(x_k)$负梯度方向

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

详细推导请点击链接

• 迭代公式：
  x k + 1 = x k − [ H j k ] − 1 ∇ f ( x )
  xk+1=xk−[Hjk]−1∇f(x)" role="presentation">xk+1=xk−[Hjk]−1∇f(x)$$x_{k+1}=x_k-[H_{jk}{]}^{-1}\mathrm{\nabla }f(x)$$
  xk+1​=xk​−[Hjk​]−1∇f(x)​​
• 步长：$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 )

S= ​10​0b​ ​,f(x)=21​xTSx=21​(x2+by2)​​

• 矩阵S的特征值,条件数$\kappa (S)$分别表示如下,假设$b<1$：
  λ max ⁡ = 1 , λ min ⁡ = b , κ ( S ) = 1 b
  λmax=1,λmin=b,κ(S)=1b" role="presentation">λmax=1,λmin=b,κ(S)=1b$${\lambda }_{max}=1,{\lambda }_{min}=b,\kappa (S)=\frac{1}{b}$$
  λmax​=1,λmin​=b,κ(S)=b1​​​
• 通过$f(x)$函数可以明显看出最小值点为(0,0)
  arg min ⁡ x ∗ = 0 f ( x ) = 0
  \begin{equation} \argmin \limits_{x^*=0}f(x)=0 \end{equation}" role="presentation">\begin{equation} \argmin \limits_{x^*=0}f(x)=0 \end{equation}$$\text{begin{equation} argmin limits\_{x^*=0}f(x)=0 end{equation}}$$
  x∗=0argmin​f(x)=0​​
• 函数一阶导数如下：
  d f ( x , y ) d X = d 1 2 X T S X d X = S X = [ 1 0 0 b ] [ x y ] = [ x b y ]
  df(x,y)dX=d12XTSXdX=SX=[100b][xy]=[xby]" role="presentation">df(x,y)dX=d12XTSXdX=SX=⎡⎣⎢100b⎤⎦⎥⎡⎣⎢xy⎤⎦⎥=⎡⎣⎢xby⎤⎦⎥$$\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]$$
  dXdf(x,y)​=dXd21​XTSX​=SX= ​10​0b​ ​ ​xy​ ​= ​xby​ ​​​
• 函数二阶导数如下：
  d 2 f ( x , y ) d X 2 = S = [ 1 0 0 b ]
  d2f(x,y)dX2=S=[100b]" role="presentation">d2f(x,y)dX2=S=⎡⎣⎢100b⎤⎦⎥$$\frac{{\mathrm{d}}^{2}f(x,y)}{\mathrm{d}{X}^2}=S=\left[\begin{array}{cc}1& 0\\ \\ 0& b\end{array}\right]$$
  dX2d2f(x,y)​=S= ​10​0b​ ​​​

2.2. 线性函数求导

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

f(x,y)=2x+5y=[2​5​] ​xy​ ​=ATX,A= ​25​ ​​​

• 函数的一次导数如下：
  d f ( x , y ) d X = d A T X d X = A = [ 2 5 ]
  df(x,y)dX=dATXdX=A=[25]" role="presentation">df(x,y)dX=dATXdX=A=⎡⎣⎢25⎤⎦⎥$$\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]$$
  dXdf(x,y)​=dXdATX​=A= ​25​ ​​​
• 函数的二阶偏导 hessian matrix 如下：[向量对向量求导，XY拉伸术]
  H j k = [ 0 0 0 0 ]
  Hjk=[0000]" role="presentation">Hjk=⎡⎣⎢0000⎤⎦⎥$$H_{jk}=\left[\begin{array}{cc}0& 0\\ \\ 0& 0\end{array}\right]$$
  Hjk​= ​00​00​ ​​​
• 对于函数$f(x)=2x+5y$来说，依据线搜索方法，其负梯度方向为最佳迭代方向。

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

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

f(x)=21​xTSx−aTx−b​​

• $f(x)$导数如下：
  d f ( x ) d x = S x − a ; d 2 f ( x ) d x 2 = H j k = S
  df(x)dx=Sx−a;d2f(x)dx2=Hjk=S" role="presentation">df(x)dx=Sx−a;d2f(x)dx2=Hjk=S$$\frac{\mathrm{d}f(x)}{\mathrm{d}x}=Sx-a;\frac{{\mathrm{d}}^{2}f(x)}{\mathrm{d}{x}^2}=H_{jk}=S$$
  dxdf(x)​=Sx−a;dx2d2f(x)​=Hjk​=S​​
• 函数$f(x)$的最小值满足其一次导数为零，即表示如下：
  f ′ ( x ∗ ) = 0 , S x ∗ − a = 0 → x ∗ = S − 1 a
  f′(x∗)=0,Sx∗−a=0→x∗=S−1a" role="presentation">f′(x∗)=0,Sx∗−a=0→x∗=S−1a$$f^{\prime }(x^{\ast })=0,S{x}^{\ast }-a=0\to x^{\ast }=S^{-1}a$$
  f′(x∗)=0,Sx∗−a=0→x∗=S−1a​​
• 整理可得：
  f min ⁡ ( x ) = min ⁡ x = x ∗ = S − 1 a f ( x ) = − 1 2 a T S − 1 a − b
  fmin(x)=minx=x∗=S−1af(x)=−12aTS−1a−b" role="presentation">fmin(x)=minx=x∗=S−1af(x)=−12aTS−1a−b$$f_{min}(x)=\underset{x=x^{\ast }=S^{-1}a}{min}f(x)=-\frac{1}{2}{a}^T{S}^{-1}a-b$$
  fmin​(x)=x=x∗=S−1amin​f(x)=−21​aTS−1a−b​​
  arg min ⁡ x = x ∗ f ( x ) = S − 1 a
  \begin{equation} \argmin\limits_{x=x^*}f(x)=S^{-1}a \end{equation}" role="presentation">\begin{equation} \argmin\limits_{x=x^*}f(x)=S^{-1}a \end{equation}$$\text{begin{equation} argminlimits\_{x=x^*}f(x)=S^{-1}a end{equation}}$$
  x=x∗argmin​f(x)=S−1a​​

4. 正则化

4.1 定义

• Log-determinant regularization
  Log-determinant regularization 通过在损失函数中加入一个负对数行列式项来约束矩阵X的结构。具体形式为
  P e n a l t y = − log ⁡ ( det ⁡ ( X ) )
  Penalty=−log⁡(det(X))" role="presentation">Penalty=−log(det(X))$$Penalty=-\log (det(X))$$
  Penalty=−log(det(X))​​
• 其中X通常是一个正定矩阵， 这一正则化项有利于确保X的特征值远离零，从而避免数值不稳定性和病态矩阵的出现

4.2 性质

• 凸性： $-\log (\det (X))$是一个凸函数，这意味着优化问题中，局部最小值也是全局最小值
• 梯度： $\nabla f(x)=-X^{-1}$
  f ( x ) = − log ⁡ ( det ⁡ ( X ) ) → d f ( x ) d x = 1 det ⁡ ( X ) ⋅ [ det ⁡ ( X ) ⋅ ( X − 1 ) T ] = X − 1
  f(x)=−log⁡(det(X))→df(x)dx=1det(X)⋅[det(X)⋅(X−1)T]=X−1" role="presentation">f(x)=−log(det(X))→df(x)dx=1det(X)⋅[det(X)⋅(X−1)T]=X−1$$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}$$
  f(x)=−log(det(X))→dxdf(x)​=det(X)1​⋅[det(X)⋅(X−1)T]=X−1​​
• hessian matrix：
  H j k = X − 1 H X − 1 ， H 是一个对称矩阵
  Hjk=X−1HX−1，H是一个对称矩阵" role="presentation">Hjk=X−1HX−1，H是一个对称矩阵$$H_{jk}=X^{-1}H{X}^{-1}，H是一个对称矩阵$$
  Hjk​=X−1HX−1，H是一个对称矩阵​​

5. 回溯线性搜索法

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

• 迭代公式：
  x k + 1 = x k − s k ∇ f ( x k )
  xk+1=xk−sk∇f(xk)" role="presentation">xk+1=xk−sk∇f(xk)$$x_{k+1}=x_k-s_k\mathrm{\nabla }f(x_k)$$
  xk+1​=xk​−sk​∇f(xk​)​​
• 步长： $s_k$
• 方向： 负梯度方向 $-\nabla f(x_k)$

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

sk∗​=sk​argmin​f(xk+1​)​​

• 步骤：先固定步长$s_k=s_0$，再取半步长$s_k=\frac{1}{2}{s}_0$,再取半步长$s_k=\frac{1}{4}{s}_0$,
• 假设我们有如下一个损失函数如下：
  S = [ 1 0 0 b ] , f ( x ) = x T S x = x 2 + b y 2
  S=[100b],f(x)=xTSx=x2+by2" role="presentation">S=⎡⎣⎢100b⎤⎦⎥,f(x)=xTSx=x2+by2$$S=\left[\begin{array}{cc}1& 0\\ \\ 0& b\end{array}\right],f(x)=x^{T}Sx=x^2+b{y}^2$$
  S= ​10​0b​ ​,f(x)=xTSx=x2+by2​​
• 迭代公式如下：
  x k + 1 = x k − s k ∇ f ( x k ) , ∇ f ( x k ) = 2 S x
  xk+1=xk−sk∇f(xk),∇f(xk)=2Sx" role="presentation">xk+1=xk−sk∇f(xk),∇f(xk)=2Sx$$x_{k+1}=x_k-s_k\mathrm{\nabla }f(x_k),\mathrm{\nabla }f(x_k)=2Sx$$
  xk+1​=xk​−sk​∇f(xk​),∇f(xk​)=2Sx​​
• 向量化如下 :$x=[x,y{]}^T$
  [ x y ] k + 1 = [ x y ] k − s k [ 2 x 2 b y ] k
  [xy]k+1=[xy]k−sk[2x2by]k" role="presentation">⎡⎣⎢xy⎤⎦⎥k+1=⎡⎣⎢xy⎤⎦⎥k−sk⎡⎣⎢2x2by⎤⎦⎥k$${\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$$
  ​xy​ ​k+1​= ​xy​ ​k​−sk​ ​2x2by​ ​k​​​
• 假设我们定义初始点 $p_0=(x_0,y_0)=(b,1)$
• 步长$s_k=\frac{1}{x_0+y_0}=\frac{1}{b+1}$这里没弄懂，后续再研究，反推出来的
  x k = b ( b − 1 b + 1 ) k , y k = ( 1 − b 1 + b ) k , f k = ( 1 − b 1 + b ) k f 0
  xk=b(b−1b+1)k,yk=(1−b1+b)k,fk=(1−b1+b)kf0" role="presentation">xk=b(b−1b+1)k,yk=(1−b1+b)k,fk=(1−b1+b)kf0$$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$$
  xk​=b(b+1b−1​)k,yk​=(1+b1−b​)k,fk​=(1+b1−b​)kf0​​​
• 函数$f(x)=x^2+b{y}^2=c$是一个椭圆形图像，随着c的变化不断变化,也就是做函数的最小值是之字型不断地趋近于最小，就像不同的椭圆进行等比缩小，最终求得最小值。