文章目录
- 1. 梯度下降[线搜索方法]
- 1.1 线搜索方法，运用一阶导数信息
- 1.2 经典牛顿方法，运用二阶导数信息
- 2. hessian矩阵和凸函数
- 2.1 实对称矩阵函数求导
- 2.2. 线性函数求导
- 3. 无约束条件下的最值问题
- 4. 正则化
- 4.1 定义
- 4.2 性质
- 5. 回溯线性搜索法
1. 梯度下降[线搜索方法]
我们之前经常用到的梯度下降，
1.1 线搜索方法，运用一阶导数信息
- 迭代公式：
x k + 1 = x k − s k ∇ f ( x k ) \begin{equation} x_{k+1}=x_k-s_k\nabla f(x_k) \end{equation} xk+1=xk−sk∇f(xk) - 步长： s k s_k sk，也叫学习率
- 方向： − ∇ f ( x k ) -\nabla f(x_k) −∇f(xk)负梯度方向
1.2 经典牛顿方法，运用二阶导数信息
详细推导请点击链接
- 迭代公式：
x k + 1 = x k − [ H j k ] − 1 ∇ f ( x ) \begin{equation} x_{k+1}=x_k-[H_{jk}]^{-1}\nabla f(x) \end{equation} xk+1=xk−[Hjk]−1∇f(x) - 步长： s k = 1 s_k=1 sk=1，把步长和方向结合起来放到方向里面去了。
- 方向：
hessian matrix 可逆时[ H j k ] − 1 ∇ f ( x ) [H_{jk}]^{-1}\nabla f(x) [Hjk]−1∇f(x)
2. hessian矩阵和凸函数
- 如果
hessian matrixH j k H_{jk} Hjk是半正定矩阵[positive semi-definite]或正定矩阵[positive definite]可得为函数是一般凸函数 - 如果
hessian matrixH j k H_{jk} Hjk是正定矩阵[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= 100b ,f(x)=21xTSx=21(x2+by2)
- 矩阵S的特征值,条件数 κ ( S ) \kappa(S) κ(S)分别表示如下,假设 b < 1 b<1 b<1：
λ max = 1 , λ min = b , κ ( S ) = 1 b \begin{equation} \lambda_{\max}=1,\lambda_{\min}=b,\kappa(S)=\frac{1}{b} \end{equation} λmax=1,λmin=b,κ(S)=b1 - 通过 f ( x ) f(x) f(x)函数可以明显看出最小值点为(0,0)
arg min x ∗ = 0 f ( x ) = 0 \begin{equation} \argmin \limits_{x^*=0}f(x)=0 \end{equation} x∗=0argminf(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 ] \begin{equation} \frac{\mathrm{d}f(x,y)}{\mathrm{d}X}=\frac{\mathrm{d}\frac{1}{2}X^TSX}{\mathrm{d}X}=SX=\begin{bmatrix}1&0\\\\0&b\end{bmatrix}\begin{bmatrix}x\\\\y\end{bmatrix}=\begin{bmatrix}x\\\\by\end{bmatrix} \end{equation} dXdf(x,y)=dXd21XTSX=SX= 100b xy = xby - 函数二阶导数如下：
d 2 f ( x , y ) d X 2 = S = [ 1 0 0 b ] \begin{equation} \frac{\mathrm{d}^2f(x,y)}{\mathrm{d}X^2}=S=\begin{bmatrix}1&0\\\\0&b\end{bmatrix} \end{equation} dX2d2f(x,y)=S= 100b
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=[25] xy =ATX,A= 25
- 函数的一次导数如下：
d f ( x , y ) d X = d A T X d X = A = [ 2 5 ] \begin{equation} \frac{\mathrm{d}f(x,y)}{\mathrm{d}X}=\frac{\mathrm{d}A^TX}{\mathrm{d}X}=A=\begin{bmatrix}2\\\\5\end{bmatrix} \end{equation} dXdf(x,y)=dXdATX=A= 25 - 函数的二阶偏导
hessian matrix如下：[向量对向量求导，XY拉伸术]
H j k = [ 0 0 0 0 ] \begin{equation} H_{jk}=\begin{bmatrix}0&0\\\\0&0\end{bmatrix} \end{equation} Hjk= 0000 - 对于函数 f ( x ) = 2 x + 5 y f(x)=2x+5y 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)=21xTSx−aTx−b
- f ( x ) f(x) f(x)导数如下：
d f ( x ) d x = S x − a ; d 2 f ( x ) d x 2 = H j k = S \begin{equation} \frac{\mathrm{d}f(x)}{\mathrm{d}x}=Sx-a;\frac{\mathrm{d}^2f(x)}{\mathrm{d}x^2}=H_{jk}=S \end{equation} dxdf(x)=Sx−a;dx2d2f(x)=Hjk=S - 函数 f ( x ) f(x) f(x)的最小值满足其一次导数为零，即表示如下：
f ′ ( x ∗ ) = 0 , S x ∗ − a = 0 → x ∗ = S − 1 a \begin{equation} f'(x^*)=0,Sx^*-a=0\rightarrow x^*=S^{-1}a \end{equation} 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 \begin{equation} f_{\min}(x)=\min\limits_{x=x^*=S^{-1}a}f(x)=-\frac{1}{2}a^TS^{-1}a-b \end{equation} fmin(x)=x=x∗=S−1aminf(x)=−21aTS−1a−b
arg min x = x ∗ f ( x ) = S − 1 a \begin{equation} \argmin\limits_{x=x^*}f(x)=S^{-1}a \end{equation} x=x∗argminf(x)=S−1a
4. 正则化
4.1 定义
- Log-determinant regularization
Log-determinant regularization 通过在损失函数中加入一个负对数行列式项来约束矩阵X的结构。具体形式为
P e n a l t y = − log ( det ( X ) ) \begin{equation} Penalty=-\log(\det(X)) \end{equation} Penalty=−log(det(X)) - 其中X通常是一个正定矩阵， 这一正则化项有利于确保X的特征值远离零，从而避免数值不稳定性和病态矩阵的出现
4.2 性质
- 凸性： − log ( det ( X ) ) -\log(\det(X)) −log(det(X))是一个凸函数，这意味着优化问题中，局部最小值也是全局最小值
- 梯度： ∇ f ( x ) = − X − 1 \nabla f(x)=-X^{-1} ∇f(x)=−X−1
f ( x ) = − log ( det ( X ) ) → d f ( x ) d x = 1 det ( X ) ⋅ [ det ( X ) ⋅ ( X − 1 ) T ] = X − 1 \begin{equation} f(x)=-\log(\det(X))\rightarrow \frac{\mathrm{d}f(x)}{\mathrm{d}x}=\frac{1}{\det(X)}\cdot [\det(X)\cdot (X^{-1})^T]=X^{-1} \end{equation} 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 是一个对称矩阵 \begin{equation} H_{jk}=X^{-1}HX^{-1}，H是一个对称矩阵 \end{equation} Hjk=X−1HX−1，H是一个对称矩阵
5. 回溯线性搜索法
对于线搜索方法来说，迭代公式如下，但是对于步长的选择来说，我们如果选择步长 s k s_k sk太大，那么就很容易越过极值点，在极值点不断跳跃和震荡，如果步长 s k s_k sk太小，那么迭代太慢，没有效果
- 迭代公式：
x k + 1 = x k − s k ∇ f ( x k ) \begin{equation} x_{k+1}=x_k-s_k\nabla f(x_k) \end{equation} xk+1=xk−sk∇f(xk) - 步长： s k s_k sk
- 方向： 负梯度方向 − ∇ f ( x k ) -\nabla f(x_k) −∇f(xk)
那么我们希望找到一个步长 s k s_k sk使得在搜索方向上使得 f ( x k + 1 ) f(x_{k+1}) f(xk+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∗=skargminf(xk+1)
- 步骤：先固定步长 s k = s 0 s_k=s_0 sk=s0，再取半步长 s k = 1 2 s 0 s_k=\frac{1}{2}s_0 sk=21s0,再取半步长 s k = 1 4 s 0 s_k=\frac{1}{4}s_0 sk=41s0,
- 假设我们有如下一个损失函数如下：
S = [ 1 0 0 b ] , f ( x ) = x T S x = x 2 + b y 2 \begin{equation} S=\begin{bmatrix}1&0\\\\0&b\end{bmatrix},f(x)=x^TSx=x^2+by^2 \end{equation} S= 100b ,f(x)=xTSx=x2+by2 - 迭代公式如下：
x k + 1 = x k − s k ∇ f ( x k ) , ∇ f ( x k ) = 2 S x \begin{equation} x_{k+1}=x_k-s_k\nabla f(x_k),\nabla f(x_k)=2Sx \end{equation} xk+1=xk−sk∇f(xk),∇f(xk)=2Sx - 向量化如下 : x = [ x , y ] T x\;=[x\;,y\;]^T x=[x,y]T
[ x y ] k + 1 = [ x y ] k − s k [ 2 x 2 b y ] k \begin{equation} \begin{bmatrix}x\\\\y\end{bmatrix}_{k+1}=\begin{bmatrix}x\\\\y\end{bmatrix}_{k}-s_k\begin{bmatrix}2x\\\\2by\end{bmatrix}_{k} \end{equation} xy k+1= xy k−sk 2x2by k - 假设我们定义初始点 p 0 = ( x 0 , y 0 ) = ( b , 1 ) p_0=(x_0,y_0)=(b,1) p0=(x0,y0)=(b,1)
- 步长 s k = 1 x 0 + y 0 = 1 b + 1 s_k=\frac{1}{x_0+y_0}=\frac{1}{b+1} sk=x0+y01=b+11
这里没弄懂，后续再研究，反推出来的
x k = b ( b − 1 b + 1 ) k , y k = ( 1 − b 1 + b ) k , f k = ( 1 − b 1 + b ) k f 0 \begin{equation} x_k=b(\frac{b-1}{b+1})^k,y_k=(\frac{1-b}{1+b})^k,f_k=(\frac{1-b}{1+b})^kf_0 \end{equation} xk=b(b+1b−1)k,yk=(1+b1−b)k,fk=(1+b1−b)kf0 - 函数 f ( x ) = x 2 + b y 2 = c f(x)=x^2+by^2=c f(x)=x2+by2=c是一个椭圆形图像，随着c的变化不断变化,也就是做函数的最小值是
之字型不断地趋近于最小，就像不同的椭圆进行等比缩小，最终求得最小值。
