模式分类笔记 -- 共轭梯度下降(2)

上节里的最速下降算法有个最明显的特征就是迭代，迭代所带来的特征便是经常反复应用矩阵A。在线性代数里面，矩阵的特征向量的特征便是在矩阵乘法运算的时候不改变方向(除了反向)。

 

我们用符号B 来代表这个不断被应用的矩阵。

 

一个矩阵的特征向量不是唯一的，因为可以任意缩放它们，但是对应的特征值却是不变的唯一的。好像看不出来与上一篇的联系哈，但是线性代数的一大特征就是任意向量可以看作是线性无关向量的组合 。

 

当反复的应用B在特征向量上时，如果特征值|v| < 1,那么特征向量就意味着缩短，反之就是延长 。当一个特征向量不断收缩的时候，就可以意味着收敛，哪怕另外的向量是向外延展的。想想向量加法就知道了。

 

记得上一节里求梯度的时候，对于正定对称A，得到f'(x) = Ax - b么，通过Ax = b这个式子，我们想着往x成为一个特征向量上靠，最好是能从这个式子里弄出个x迭代的关系，迭代的关系里还有矩阵与x的反复应用。我们可以通过这样变形，

 

(D + E)x = b，这里D只拥有A的对角元素，E拥有其它元素。再进一步的变形

 

Dx = -Ex + b       =>  (这样做是因为对角阵很好求逆)

 

x = -D''Ex + D''b  => (''再次用来表示求逆)

 

x = Bx + z           =>(B和z只是记号)

 

x(i+1) = Bx(i) + z 

 

(这样就满足要求了，x再变成特征向量线性组合的形式， 很好很强大)想法是好，但是有一点不得不说明，就是B经常不是对称的，甚至在确定性上也保证不了（就算A是对称的），这就决定了此方法好归好，但不一定收敛 哦。

 

详细的就不讲了，特征向量在线性代数里真的用处太多了，可惜就是上学那会儿不知道有这么多神奇。

上面是引子， 下边才是本篇的重点。

 

最速下降有一个问题，就是迭代总在几个早期的的方向上进行 ，左边的图上就可见一斑。

 

如此变产生这样一个想法，要是我们能够在 那几个正交方向上每次只 进行一步 ，一步完成那方向上应该移动的贴近解x的距离，那该有多好（直接由x【最优点】往那些方向上引垂线）。想法是绝妙，但是是空想，要是你知道了x，那问题不就直接解决了是吧。所以问题需要变通，转换成A正交。所谓A正交，是指d(i)'Ad(j) = 0,就称向量d(i)和d(j)是A正交的，也就是共轭。

 

我们利用共轭其实是利用这样一个特点，A * x 这种形式可以看作是对x进行线性变换（变形 ），x'Ax对应的形式正是椭圆（椭球）。我们讲x'Ax=0，如果A是单位对角矩阵，那么x'与x是正交的。说到底，d(i)'与d(j)是共轭的，正是因为他们在未变形的空间是正交的 。我们也是利用这样一个特点，来达到每次方向上只走一次，且一次便是该方向上的最优点。我盘算了一下，如果简单上一张图在这里也会显得比较突兀，文档里的图太大，还要缩小画布，mspaint又做不了此事，还是免了。

 

在此之前，可能要插上一点内容，当我们在最速下降过程中应用特征向量时，定义能量模（energe norm）||e||(A) = (e'Ae)1/2.这里的1/2是开平方的意思。我们用特征向量来表示e(i),详细的也不列了，贴图不方便，这里面又表示式子很困难。 最小化这个模和最小化f(x)是等价的。因为f(x+e) = f(x) + 1/2 * e'Ae.  （x+p）是函数上任意一点。看待这个能量模的时候同样可以用空间变形的角度，能量模相等的同心圆在变形后成为同心椭圆线 ，这些都是函数映射的等值线。A正交的向量正是未变形空间切线与半径的关系。

 

到此，我们的需求 也就变成了e(i+1)和d(i)是A正交 ，这样的变化同样可达到一个方向只走一次的特性。因为切线点已经是距离圆心最近的点了。这样的话，需求就变成了找到这些共轭方向 。我们有一个计算共轭方向的Gram-Schmidt Conjugation方法，原理和Gram-Schmidt正交化如出一辙，是 利用投影原理 在已有共轭基的基础上构造一个新的共轭基。但这种方法有个重大的问题是需要保存所有计算过的共轭方向在内存中以用来计算新的共轭方向。这个劣势使得它基本获得不了青睐，直到共轭方向展现除了一些让人轻松的特性。

 

详细讲很痛苦，必不可少列出些代数式式子变化和一些trick，其实最根本，自认为最有益的东西已经在上面讲出来了，再讲下去只是生成共轭梯度方向上的一些让人欣慰的变化，就此打住。

 

共轭梯度下降法在神经网络中加快训练速度有些帮助，假设误差曲面是二次型的。