Skip to content

Files

Latest commit

cc0230c · Aug 26, 2020

History

History
162 lines (103 loc) · 9.92 KB

LM算法.md

File metadata and controls

162 lines (103 loc) · 9.92 KB

介绍

想写好这部分不容易,详情请看参考文献,这里只是做一个导读,秋招结束后再回来补。

最优化方法分为 Line SearchTrust Region 两类。Line Search 方法先固定下降方向,再在该方向上搜索步长,典型的有 最速下降法高斯牛顿法 ; Trust Region 方法先固定搜索区域,再在该区域内找最优的点,典型的有 LM算法

考虑最小二乘问题: $$ \underset{x}{min}\frac{1}{2}||f(x)||^2_2 $$ 其中,这整个式子称为目标函数,自变量x有n维,f是任意非线性函数,它有m维。

最速下降法

参考:《计算机视觉中的数学方法》13.3.1 最速下降法

又叫一阶梯度法。让x加一个增量 Δ x ,让x朝着梯度下降的方向走,使得 m i n x 1 2 | | f ( x + Δ x ) | | 2 2 变小。问题是走多远呢?将目标函数在x附近进行一阶泰勒展开,得到目标函数的近似函数,一般取 Δ x = J T ( x ) 。其中 J ( x ) 也叫作雅克比矩阵,是向量 向量f(x)关于向量x 的一阶梯度。

但这样有2个问题,

问题一:直接取 Δ x = J T ( x ) (注意:这里 J ( x ) | | f ( x ) | | 2 2 关于向量x的导数,但是也叫雅克比矩阵)只能保证目标函数下降,并不能保证下降最快。为了更快的下降,有时候我们取 Δ x = λ J T ( x ) ,选择一个合适的 λ ,令目标函数(注意不是它的近似函数,这里指的就是目标函数本身)在 Δ x 的方向上取得最小值(只是在这个方向上取得最小值)。那么这个 λ 取值怎么确定呢?这又是一个最优化问题,这次可以对 λ 做二阶泰勒展开,用牛顿法搜索到最好的 λ (注意,前面是对向量x泰勒展开,这次是对 λ 进行泰勒展开)。这个确定 λ 的方法叫做线性搜索(在《计算机视觉中的数学方法》中好像叫一维搜索)。

问题二:最速下降法每次迭代,求出 λ Δ x 是为了让目标函数在 Δ x 方向下降最大,$\Delta x$ 方向只是目标函数在x处的梯度,走远了以后目标函数的梯度肯定发生改变,所以让目标函数在 Δ x 方向下降最大不一定目标函数就下降最大,这种方法过于贪心,容易走出锯齿路线,反而增加迭代次数。

注意:这里做一阶展开,一阶展开是个线性函数,在低维度来说就是一条直线,根本没有最小值一说,所以这种方法的近似函数只能确定个方向,要想确定步长,还得挨个把 λ Δ x 代入原目标函数,看看值是增大还是变小了,这样才能找得到在这个方向上目标函数的最小值,以此确定步长。这就是线性搜索。

牛顿法

又叫二阶梯度法。最速下降法只使用一阶泰勒展开,对目标函数近似不够,可能导致下降缓慢甚至失败。牛顿法与最速下降法类似,只不过在求近似函数时,是采用二阶泰勒展开。对近似函数求关于 Δ x 的导数,另导数为0可以得到近似函数的极值点,可以得到 H Δ x = J T ,其中H矩阵是向量f(x)关于向量x的二阶梯度,也叫作海森矩阵,如果海森矩阵有逆矩阵或者伪逆的话,则增量 Δ x = H + J T

但这种这种方法存在1个问题:

问题一:当问题规模非常大时,海森矩阵的求解非常困难(我的理解是求解速度很慢?),我们通常避免去计算海森矩阵,而用其他矩阵去近似海森矩阵。

注意:这里 J ( x ) | | f ( x ) | | 2 2 关于向量x的导数,但是也叫雅克比矩阵

高斯-牛顿法

牛顿法中需要计算海森矩阵,对于大规模问题这是很困难的,因此高斯-牛顿法用 J T ( x ) J ( x ) 替代海森矩阵H,避免了海森矩阵的求解。

f ( x ) 在向量x附近进行一阶泰勒展开(注意,不是对目标函数 1 2 | | f ( x ) | | 2 2 进行泰勒展开),得到 f ( x ) 的近似函数。用近似函数去替换目标函数里的 f ( x ) ,得到近似的目标函数,同理,依旧是对目标函数求导,令导数为0,求得目标函数的极值点。令导数为0,可以得到方程组 J ( x ) T J ( x ) Δ x = J ( x ) T f ( x ) ,令 H = J ( x ) T J ( x ) , g = J ( x ) T f ( x ) ,则可以得到与牛顿法近似的式子 H Δ x = g ,所以我们才说高斯-牛顿法用 J T ( x ) J ( x ) 替代海森矩阵H,避免了海森矩阵的求解。

与牛顿法一样,求解这个方程组,可以得到 Δ x

这个方法同样有一些问题:

问题一:$H=J(x)^TJ(x)$ 可能为奇异矩阵或者病态(illcondition)的情况,此时求解出来的 稳 Δ x 定性较差。

问题二:就算 H = J ( x ) T J ( x ) 非奇异也非病态,求出来的 Δ x 的模值也可能太大,会导致我们的近似不准确,甚至无法保证目标函数下降。这种情况,可以使用线性搜索的方法,在确定了下降方向 Δ x 后,再确定一个步长 λ ,采用 λ Δ x 作为下降的增量,这个 λ 保证了近似目标函数在这一步迭代中达到最小(但不保证目标函数达到最小) 。

注意:这里 $J(x)是f(x)关于向量x的导数,但是也叫雅克比矩阵。

LM算法

又叫阻尼牛顿法(Damped Newton Method)。由于高斯牛顿法中采用二阶泰勒展开去近似函数 f ( x ) ,只能在站开点附近有比较好的近似效果,那么我们可以加一个约束,约束求出的 Δ x 在某个信赖区域内(Trust Region),在信赖区域内我们认为近似是有效的,在信赖区域外,近似可能会出问题。LM算法就是这么一种信赖区域的方法。

怎么确定信赖区域的范围?我们可以用 ρ = f ( x + Δ x ) f ( x ) J ( x ) Δ x 去评价近似得好不好,其中 ρ 的分子表示实际函数的下降值,分母表示泰勒一阶展开的近似函数的下降值。如果 ρ 接近1,则近似是好的,如果 ρ 很小,则说明实际减小的值要远少于近似减小的值,则认为近似比较差,需要缩小近似范围;如果 ρ 很大,则说明实际下降的值比预计的大,我们可以放大近似范围。(TODO:这里不太清楚 ρ 很大有没有包括其大于1的情况,还有就是为什么很大就可以放大近似范围?

注意:这里 $J(x)是f(x)关于向量x的导数,但是也叫雅克比矩阵。

附录

泰勒展开

f ( x ) = i = 0 n f ( i ) ( x 0 ) i ! ( x x 0 ) i = f ( x 0 ) + f ( x 0 ) ( x x 0 ) + . . . f ( x + Δ x ) = i = 0 n f ( i ) ( x ) i ! ( Δ x ) i = f ( x ) + f ( x ) Δ x + . . .

正定与半正定矩阵

正定矩阵

(1)广义定义:设M是n阶方阵,如果对任何非零向量x,都有 x T M x > 0 ,就称M为正定矩阵。

(2)狭义定义:设M是n阶实对称方阵,当且仅当对任何非零实系数向量x,都有 x T M x > 0 ,就称M为正定矩阵。

半正定矩阵

(1)广义定义:设M是n阶方阵,如果对任何非零向量x,都有 x T M x 0 ,就称M为半正定矩阵。

(2)狭义定义:设M是n阶实对称方阵,当且仅当对任何非零实系数向量x,都有 x T M x 0 ,就称M为半正定矩阵。

判定定理

判定定理1:对称矩阵A为正定的充分必要条件是:A的特征值全为正。(而对角阵的特征值正好等于对角线上的那些元素。)

判定定理2:对称矩阵A为正定的充分必要条件是:A的各阶(顺序)主子式都为正。注意:负定的充分必要条件是:奇数阶(顺序)主子式为负,偶数阶(顺序)主子式为正。

判定定理3:任意阵A为正定的充分必要条件是:A合同于单位阵。

主子式和顺序主子式

参考:百度百科-主子式

主子式定义:在n 阶行列式中,取出的k行k列得到的新行列式,称为n阶行列式的k阶主子式。(注意:取得行号和列号要相同,如1,3,7行和1,3,7列)

特殊的,由前 [ 1 , k ] 行和前 [ 1 , k ] 列所确定的主子式即为n阶行列式的k阶顺序主子式

举例

设矩阵M $$ M = \begin{bmatrix} m_{11} & m_{12} & m_{13} \ m_{21} & m_{22} & m_{23} \ m_{31} & m_{32} & m_{33} \end{bmatrix} $$ 那么其1阶、2阶、3阶顺序主子式分别为 $$ 一阶: m_{11} \ 二阶:\begin{vmatrix} m_{11} & m_{12} \ m_{21} & m_{22} \ \end{vmatrix} \ 三阶:\begin{vmatrix} m_{11} & m_{12} & m_{13} \ m_{21} & m_{22} & m_{23} \ m_{31} & m_{32} & m_{33} \end{vmatrix} $$

举例说明

x T M x 的表达式列出来可能有助于理解: $$ \begin{array}{l} \boldsymbol{x} = [x_1 \quad x_2 \quad x_3]^T \ M = \begin{bmatrix} m_{11} & m_{12} & m_{13} \ m_{21} & m_{22} & m_{23} \ m_{31} & m_{32} & m_{33} \end{bmatrix} \ \boldsymbol{x}^TM\boldsymbol{x} = \ = [m_{11}x_1+m_{21}x_2+m_{31}x_3 \quad m_{12}x_1+m_{22}x_2+m_{32}x_3 \quad m_{13}x_1+m_{23}x_2+m_{33}x_3] \begin{bmatrix} x_1 \ x_2 \ x_3 \end{bmatrix} \ = m_{11}x_1^2 + (m_{12}+m_{21})x_1x_2 + (m_{13}+m_{31})x_1x_3 + m_{22}x_2^2 + (m_{23}+m_{32})x_2x_3 + m_{33}x_3^2 \end{array} $$

牛顿法和高斯-牛顿法的区别

高斯牛顿法是牛顿法在最小二乘问题上的特例,但又不是完全套用牛顿法,而是在套用的过程中做了简化。

参考:https://zhuanlan.zhihu.com/p/103724149

也可以参考《视觉SLAM十四讲》,一个对目标函数 1 2 | | f ( x ) | | 2 2 求导,一个对f(x)求导

参考文献

  • 《视觉SLAM十四讲》第一版 - 高翔

  • 《计算机视觉的数学方法》| 注意:本书把f(x)看做目标函数,而《视觉SLAM十四讲》中把 1 2 | | f ( x ) | | 2 2 看做目标函数,所以一些结论对比,要注意一下。

  • 《计算机视觉中的多视图几何》第一版