泰勒展开到梯度下降和牛顿法,再到雅各比,海森矩阵

技术讨论 hello_uncle ⋅ 于 1个月前 ⋅ 123 阅读

作者丨CJ1019@知乎(已授权)
来源丨https://zhuanlan.zhihu.com/p/57625037
编辑丨极市平台

1.0 代价函数

在深度学习中,一个想要最大化或最小化的函数称为代价函数。优化目标通常是要找到使代价函数最大或最小的参数。记为:

$$
x^*=\mbox{argmin}f(x)\
$$

以最小化代价函数为例,优化的目标为了找到 $x^$ ,使得 $f(x^) = 0$ .

这里要注意,代价函数一般定义为“距离”,他的值域为 $\left( 0,\infty \right)$ 。

1.1 泰勒展开和牛顿法

一个可微函数 $f(x)$ ,$f(x)$ 在某点 $x_0$ 处的各阶导数已知,那么使用 $f(x_0),f^{'}(x_0),f^{''}(x_0),\cdots,f^{(n)}(x_0)$ 构成的多项式可以逼近$x_0$邻域内的任一点的函数值。

$$
f(x+\epsilon)=f(x)+\frac{f^{'}(x)}{1!}\epsilon+\frac{f^{''}(x)}{2!}\epsilon^2+\cdots+\frac{f^{n}(x)}{n!}\epsilon^n \
$$

1.1.1 求使 $f(x)=0$ 的参数(求函数的解)

使用1阶导数估计领域点的函数值时,设 $x_0$ 为已知点, $x$ 为$x_0$邻域内的未知点。那么可以有下列表达式:

$$
f(x) = f(x_0)+f^{'}(x_0)(x-x_0)\
$$

令: $f(x)=0$

有: $\begin{align} & f(x_0)+f^{'}(x_0)(x-x_0)=0 \ \Rightarrow & x=x_0-\frac{f(x_0)}{f^{'}(x_0)} \end{align} \$

如果一直迭代下去,即 $ x{n+1}=x{n}-\frac{f(x_n)}{f^{'}(x_n)}$ 。那么 $f(x_n)$ 就会越来越逼近 $f(x)=0$ 。

1.1.2 求使$f^{'}(x)=0$ 的参数(求函数的极值)

使用2阶导数估计领域点的函数值时,设 $x_0$ 为已知点, $x$ 为领域内未知点。那么可以有下列表达式:

$$
f(x) = f(x_0)+f^{'}(x_0)(x-x_0)+\frac{f^{''}(x_0)}{2!}(x-x_0)^2\
$$

当 $f(x)=f(x_0)$ 时, $f^{'}(x) = 0$ .

有:

$$
f^{'}(x_0)(x-x_0)+\frac{f^{''}(x_0)}{2!}(x-x_0)^2 = 0 \ \Rightarrow x = x_0 - \frac{2f^{'}(x_0)}{f^{''}(x_0)}
$$

如果一直迭代下去,即 $ x{n+1}=x{n}-\frac{2f^{'}(x_n)}{f^{''}(x_n)}$ 。那么 $f(x_n)$ 就会越接近 $f(x)$ 的极值(包括全局极值和局部极值)。

1.2 梯度下降法

1.2.0 梯度下降法

梯度下降法利用了函数的一阶泰勒展开,即 $f(x+\epsilon)=f(x)+\frac{f^{'}(x)}{1!}\epsilon$ 。其中 $f^{'}(x)$ 表明了当 $x$ 发生微小变动时, $f(x)$ 的变化情况。

比如,当 $f^{'}(x)>0$ 且 $\epsilon > 0$ 且足够小时, $f(x-\epsilon) $ 一定小于 $f(x)$ 。因为:

$$
f(x-\epsilon)=f(x)-\frac{f^{'}(x)}{1!}\epsilon \
$$

通式可以表示为:

$$
f(x-\epsilon~\mbox{sign}(f^{'}(x)))=f(x)-\frac{f^{'}(x)}{1!}\epsilon~\mbox{sign}(f^{'}(x)) \
$$

当沿着梯度的方向,以 $\epsilon$ 为步长,迭代计算 $f(x)$ 和$f^{'}(x)$可以得到 $f(x)$ 的极值(包括全局极值和局部极值)。

1.2.1 多变量情况时的梯度下降法

在深度学习中,常见的优化是优化一个具有多个输入的函数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ 。这里要注意,如果要使优化有意义,那么 $f(x)$ 的输出必须是标量。

为了使用梯度下降法优化函数,就必须要求 $f(x)$ 对各个自变量的导数,即 $\left[ \frac{\partial f(x)}{\partial x_1},\frac{\partial f(x)}{\partial x_2},\cdots,\frac{\partial f(x)}{\partial xn} \right]$ ,记为 $\bigtriangledown{x}f(x)$ 。方向导数是个标量.

在多变量情况时,函数的极值点为使各自变量导数都为 $0$ 的点。

$f(x)$ 在方向 $u$ 上的方向导数可以通过 $u^T\bigtriangledown_{x}f(x)$ 求解。

1.3 牛顿法和梯度下降法的不同

在寻找极值时,牛顿法和梯度下降法有一些区别

牛顿法可以通过较少的迭代找到极值,但是计算复杂(需要计算 $f^{''}(x)$ 并求他的逆)。

牛顿法包含了学习率的动态调节。

梯度下降法简单好实现,但迭代步骤较多。

梯度下降法是一阶优化算法。牛顿法是二阶优化算法。

1.4 雅可比矩阵和海森矩阵

1.4.1 雅可比矩阵(描述$f: \mathbb{R}^n \rightarrow \mathbb{R}^m$ 的一阶导数矩阵)

在向量微积分中,雅可比矩阵是向量函数 $f: \mathbb{R}^n \rightarrow \mathbb{R}^m$ 的一阶导数矩阵。向量函数的输入是 $\mathbb{R}^n$ 的向量,输出是 $\mathbb{R}^m$ 的向量。向量函数可以表示为:

$$
\begin{bmatrix} y_1 \ y_2 \ \vdots \ y_m \\end{bmatrix} = f(\begin{bmatrix} x_1 \ x_2 \ \vdots \x_n \\end{bmatrix}) = \begin{bmatrix} f_1(x_1, x_2, \cdots, x_n) \ f_2(x_1, x_2, \cdots, x_n) \ \vdots \f_m(x_1, x_2, \cdots, x_n) \\end{bmatrix} \
$$

雅各比矩阵是 $m \times n$ 的矩阵,坐标为 $(i,j)$ 元素表示为:

$J_{ij}=\frac{\partial f_i}{\partial x_j} \$ 雅各比矩阵的通式为:

$$
J_f(x_1,x_2, \cdots, x_n) = \begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} & \cdots & \frac{\partial f_1}{\partial x_n} \ \frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} & \cdots & \frac{\partial f_2}{\partial x_n} \ \vdots & \vdots & \cdots & \vdots \ \frac{\partial f_m}{\partial x_1} & \frac{\partial f_m}{\partial x_2} & \cdots & \frac{\partial f_m}{\partial x_n} \end{bmatrix} \
$$

例子:

向量函数 $f: \mathbb{R}^2 \rightarrow \mathbb{R}^2$ 为:

$$
f(\begin{bmatrix} x \ y \ \end{bmatrix}) = \begin{bmatrix} f_1(x,y) \ f_2(x,y) \ \end{bmatrix} = \begin{bmatrix} x^2y \ 5x+\mbox{sin}y \ \end{bmatrix} \
$$

他的雅各比矩阵 $Jf(x,y)$ 为:
$\mathbf {J}
{\mathbf {f} }(x,y)= {\begin{bmatrix} {\dfrac {\partial f{1}}{\partial x}} & {\dfrac {\partial f{1}}{\partial y}}\{\dfrac {\partial f{2}}{\partial x}} & {\dfrac {\partial f{2}}{\partial y}}\end{bmatrix}} = {\begin{bmatrix}2xy & x^{2}\5 & \cos y\end{bmatrix}} \$

例子:

向量函数 $f:\mathbb{R_3} \rightarrow \mathbb{R_4}$ 为:

$$
{\begin{aligned} y{1} & =x{1}\ y{2} & =5x{3}\ y{3} & =4x{2}^{2}-2x{3}\ y{4} & =x{3}\sin x{1} \end{aligned}} \
$$

他的雅各比矩阵 $J_f(x_1,x_2,x_3)$ 为:

$$
\mathbf {J} {\mathbf {f} }(x{1},x{2},x{3}) = {\begin{bmatrix}{\dfrac {\partial y{1}}{\partial x{1}}} & {\dfrac {\partial y{1}}{\partial x{2}}} & {\dfrac {\partial y{1}}{\partial x{3}}}\ {\dfrac {\partial y{2}}{\partial x{1}}} & {\dfrac {\partial y{2}}{\partial x{2}}} & {\dfrac {\partial y{2}}{\partial x{3}}}\ {\dfrac {\partial y{3}}{\partial x{1}}} & {\dfrac {\partial y{3}}{\partial x{2}}} & {\dfrac {\partial y{3}}{\partial x{3}}}\ {\dfrac {\partial y{4}}{\partial x{1}}} & {\dfrac {\partial y{4}}{\partial x{2}}} & {\dfrac {\partial y{4}}{\partial x{3}}}\end{bmatrix}}={\begin{bmatrix}1 & 0 & 0\ 0 & 0 & 5\ 0 & 8x{2} & -2\ x{3}\cos x{1} & 0 & \sin x{1}\end{bmatrix}} \
$$

1.4.2 海森矩阵(描述$f: \mathbb{R}^n \rightarrow \mathbb{R}$ 的二阶导数矩阵)

向量函数的输入是 $\mathbb{R}^n$ 的向量,输出是 $\mathbb{R}^1$ 的标量。向量函数可以表示为:

$$
y = f(\begin{bmatrix} x_1 \ x_2 \ \vdots \x_n \\end{bmatrix}) = f_1(x_1, x_2, \cdots, x_n) \
$$

他的雅各比为 $1 \times n$ 的矩阵:

$$
J_f(x_1,x_2, \cdots, x_n) = \begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} & \cdots & \frac{\partial f_1}{\partial x_n} \end{bmatrix} \
$$

将雅各比矩阵转置: $J_f(x_1,x_2, \cdots, x_n) = \begin{bmatrix} \frac{\partial f_1}{\partial x_1} \ \frac{\partial f_1}{\partial x_2} \ \cdots \ \frac{\partial f_1}{\partial x_n} \end{bmatrix} \$

求雅各比矩阵的雅各比矩阵(海森矩阵)

$$
H_f(x_1,x_2, \cdots, xn) = J{J_f}(x_1,x_2, \cdots, x_n) = \begin{bmatrix} \frac{\frac{\partial f_1}{\partial x_1}}{\partial x_1} & \frac{\frac{\partial f_1}{\partial x_1}}{\partial x_2} & \cdots & \frac{\frac{\partial f_1}{\partial x_1}}{\partial x_n} \ \frac{\frac{\partial f_1}{\partial x_2}}{\partial x_1} & \frac{\frac{\partial f_1}{\partial x_2}}{\partial x_2} & \cdots & \frac{\frac{\partial f_1}{\partial x_2}}{\partial x_n} \ \vdots \ \frac{\frac{\partial f_1}{\partial x_n}}{\partial x_1} & \frac{\frac{\partial f_1}{\partial x_n}}{\partial x_2} & \cdots & \frac{\frac{\partial f_1}{\partial x_n}}{\partial x_n} \end{bmatrix} = \begin{bmatrix} \frac{\partial^2 f_1}{\partial x_1 \partial x_1} & \frac{\partial^2 f_1}{\partial x_1 \partial x_2} & \cdots & \frac{\partial f_1}{\partial x_1 \partial x_n} \ \frac{\partial^2 f_1}{\partial x_2 \partial x_1} & \frac{\partial^2 f_1}{\partial x_2 \partial x_2} & \cdots & \frac{\partial f_1}{\partial x_2 \partial x_n} \ \vdots \ \frac{\partial^2 f_1}{\partial x_n \partial x_1} & \frac{\partial^2 f_1}{\partial x_n \partial x_2} & \cdots & \frac{\partial f_1}{\partial x_n \partial x_n} \ \end{bmatrix} \
$$

1.4.3 海森矩阵与梯度下降法(如何决定步长)

当对一个向量函数进行二阶泰勒展开时,可以得到了下列形式:

$$
f(x_0+x) = f(x_0)+x^Tf'(x_0)+\frac{1}{2}x^Tf''(x_0)x\
$$

$f(x)$ 的一阶导数为雅各比矩阵(这里为行向量)的转置,记为 $g$ 。二阶导数为海森矩阵,记为 $H$ 。 $x$ 是一个调节向量。当沿着一阶导数的方向进行调节时,调节步长向量可以表示为 $\varepsilon g$ 。此时的二阶展开可以变形为:

$$
f(x_0-\varepsilon g) = f(x_0)-\varepsilon g^Tg+\frac{\varepsilon^2}{2}g^THg\
$$

当使用上式用梯度下降法求解函数的时,分析 $\varepsilon$ 对调节的影响:

1,回忆梯度下降的目的:通过迭代使得 $f(x)$ 的值不断下降直到两个变化的差足够小。即 $f(x_0-\varepsilon g) < f(x_0)$ .

2,上式中 $g^Tg$ 是二次项一定大于 $0$ ,所以如果 $\frac{\varepsilon^2}{2}g^THg = 0$ ,那么 $f(x_0-\varepsilon g) < f(x_0)$ 一定成立。但是如果 $\frac{\varepsilon^2}{2}g^THg$ 是很大的正值,那么不等式可能就要变方向了,此时的调节不能使函数值减小,反而会使他增大。如果$\frac{\varepsilon^2}{2}g^THg$ 是很大的负值,那么 $f(x)$ 的值会一直减小。

3,如果要让梯度下降实现它该实现的功能,就需要满足一个条件:

$\varepsilon g^Tg > \frac{\varepsilon^2}{2}g^THg \$ 将上式变形,得 $\varepsilon$ 的表达式:

$$
\varepsilon < \frac{g^Tg}{g^THg} \
$$

4,海森矩阵是 $n \times n$ 的对称方阵。如果各元素都是实数的话,那么海森就是实对称矩阵,那么他就一定可以进行特征值分解为: $Q\Lambda Q^T$ .其中 $Q$ 是特征向量 $q_i$ 构成的矩阵, $\Lambda$ 为特征值构成的矩阵。一阶导数 $g$ 可以通过组合特征向量得到,即:

$$
g=Q\begin{bmatrix}\alpha_1 \ \alpha_2 \ \vdots \ \alpha_n \end{bmatrix}\
$$

可以得到 $g^Tg=(Q\alpha)^T(Q\alpha)=\alpha^TQ^TQ\alpha=\alpha^T\alpha$ 。

$$
\frac{g^Tg}{g^THg} = \frac{\alpha^T\alpha}{\alpha^TQ^THQ\alpha} = \frac{\alpha^T\alpha}{\alpha^TQ^TQ\Lambda Q^TQ\alpha}= \frac{\alpha^T\alpha}{\alpha^T\Lambda \alpha} \
$$

5,因为 $\alphai$ 的取值范围为 $[0,1]$ 且 $\alpha$ 为单位向量。所以当 $\alpha$ 的某一个分量为 $1$ 其余分量为 $0$ 时, $g^Tg$ 取到最大值 $1$ 。也就是当 $\alpha$ 与 $H$ 的一个特征向量同向时, $g^Tg$ 可以取到最大值。由此可以知道当 $\alpha$ 与 $H$ 的最大特征值对应的特征向量同向时,$\varepsilon$ 有最小值为 $\frac{1}{\lambda{max}}$ .

1.4.4 二阶导数测试与 海森矩阵的特征值

对于一维函数,如果 $f'(x)=0$ ,且 $f''(x)>0$ ,那么 $f(x)$ 是函数的(局部)极小值。

证明:因为 $f'(x)=0$ 且 $f''(x)>0$ ,那么可以得到 $f'(x-\varepsilon)<0$ 且 $f'(x-\varepsilon)>0$ .也就是函数先下降后上升。

同理可以得到,如果 $f'(x)=0$ ,且 $f''(x)<0$ ,那么 $f(x)$ 是函数的(局部)极大值。

但是$f'(x)=0$ ,且 $f''(x)=0$ ,是不能导出任何结论,因为此时 $f(x)$ 有可能是一块平坦的区域。

对于多维函数也有相似的结论。

如果$f'(x)=0$ ,且 $f''(x)$ 在各个方向上都大于 $0$ ,那么 $f(x)$ 是函数的(局部)极小值。

如果$f'(x)=0$ ,且 $f''(x)$ 在各个方向上都小于 $0$ ,那么 $f(x)$ 是函数的(局部)极大值。

如果$f'(x)=0$ ,且 $f''(x)$ 在各个方向上都小于 $0$ 或者大于 $0$ (不等于 $0$ ),那么 $f(x)$ 是函数的鞍点。

如果$f''(x)$ 在某个方向上等于 $0$时,二阶导数测试是不确定的。

海森矩阵的特征值可以描述,二阶导数的符号。如果在某个方向的特征值大于 $0$ ,那么在这个方向上的二阶导数就大于 $0$。特征值越大就说明,对应的二阶导数越大。

大叔

成为第一个点赞的人吧 :bowtie:
回复数量: 0
暂无回复~
您需要登陆以后才能留下评论!