番外篇(4)——共轭梯度法入坑
由ypyu创建，最终由ypyu 被浏览 4 用户
前面我们已经把最速下降法的内容介绍的差不多了，下面我们要做的就是介绍这个真正的主角了——共轭梯度法。这个优化方法算是活跃在优化世界的一个经典算法了，它的计算速度还算不错，方法也算相对简单——真的是相对，因为比起梯度下降它还是复杂不少，但是和其他的一些方法比较，那就不算难了。
好了，我们直奔主题。在番外篇的开篇我们就提到了机器学习的三个部件。优化算法作为一个黑盒，一般来说是不为人所知的。所以我们的重点就是揭开它的面纱，尽可能清楚地阐述它的原理。
更高级的约束
前面在最速下降法中，我们提到了最速下降法的一个性质——那就是相邻两次的优化方向是正交的。乍一听上去，总感觉这个性质很酷，但是看过了一些实际案例，又不免让人心灰——走成"zig-zag"的形状，还好意思标榜这个性质？
于是乎，我们开始对优化方向有了更大的野心——能不能让我们的优化方向更加智能，我们每朝一个方向走，就把这个方向走到极致？所谓的极致，可以理解为在优化的过程中我们再也不需要朝这个方向走了。于是乎我们引出了另外一个变量，叫做误差：
$e_t=x^*-x_t$
这个误差表示了参数的最优点和当前点之间的距离。那么我们的目标就可以更在形式化了，我们希望每一步优化后，当前的误差和我们刚才优化的方向正交！注意，这里我们已经不再使用梯度这个词，而是使用优化方向，因为从现在开始，我们的优化方向不一定是梯度了。当然我们也要换一个变量名比较好，不然会引起误会：
$r_t$
还是写个公式出来比较靠谱：
$r_t^Te_{t+1}=0$
这样我们可以想象，如果我们的优化空间有d维，那么我们最多只需要迭代d轮就可以求解出来了。听上去蛮靠谱的。
好了，大饼画完了，下面就是填坑时间了。
坑
理想很丰满，但是现实很骨感。如果我能知道那个误差，我还优化干嘛？直接按误差更新不就完事了？但是想知道误差还是需要一步一步地求解啊？感觉我们掉入了"chicken-egg senario"里面。
但是别着急，我们还有数学武器在手，我们可以用线性代数的知识偷天换日，填满这个坑。于是乎，见证奇迹的时刻就要来临了。
共轭
偷天换日的关键就在这个共轭上了。其实一开始看到这个词的时候我是拒绝的，这是什么鬼？这词是啥意思？
一个按原意的解释——轭就是绑在两头牛身上的木头，它让两个本来独立的个体变成了一个整体，属于牵线搭桥之类的关键道具。
好了，我们再回到刚才的问题中，前面我们说了我们新的正交特性，那么放在共轭这个环境下是什么效果呢？我们希望现在的关系变为共轭正交，存在一个矩阵A（A就是轭），使得：
$r_t^TAe_{t+1}=0$
其实看到这里我依然是拒绝的……这又是什么鬼，三观都崩塌了好不好，这么乱搞有什么意义？
别着急，其实如果我们把上面的原始公式中间加一个东西，看上去就舒服很多了：
$r_t^TIe_{t+1}=0$
单位阵不改变结果，现在我们要加一个能改变结果的东东，仅此而已。那么这个矩阵是什么作用呢？
我们可以认为这个矩阵要完成线性变换的作用，将一个向量从一个线性空间转换到另一个空间。转换后的向量可以满足正交的性质，如果这个矩阵一直保持不变，听上去这个性质也是合理的啊。
那么有没有更加实际的例子呢？
比方说我们有两个向量：
$a=[1,1] , b=[1,0.5]^T$
很显然它们不是正交的，但是如果我们多了一个矩阵A：
$A=[[1,0][0, -2]]$
那么我们发现，b经过A转换后就与a正交了。
所以这个新的条件实际上只是多绕了一个弯，和前面的条件差距并不大。
一旦接受了这样的设定，下面的内容就好理解多了。
共轭梯度法的流程
好了，我们已经明确了共轭梯度法的目标和特点，那么我就要开始推导算法公式了。当然，共轭梯度法也属于line search的一种，我们的总体思路不变：
- 确定优化方向
- 确定优化步长
相对而言，确定优化方向比确定优化步长麻烦，我们放在后面说，现在先来捡个软柿子，那就是第2步，我们从上面提过的公式开始：
$r_t^TAe_{t+1}=0$
好了，开始推导：
$r_t^TAe_{t+1}=r_t^TA[e_{t}+X_t-X_{t+1}]=r_t^TA[e_{t}+\alpha_t r_t]$
$=r_t^TAe_{t}+\alpha_t r_t^TAr_t=0$
，于是
$\alpha_t=-\frac{r_t^TAe_{t}}{r_t^TAr_t}$
$\alpha_t=-\frac{r_t^TA(X^*-X_t)}{r_t^TAr_t}$
我们知道
$AX^*=0$
，
$g_t=AX_t$
,于是公式最终变为：
$\alpha_t=\frac{r_t^Tg_t}{r_t^TAr_t}$
好了，我们发现我们利用多出来的A把前面的误差e成功地消掉了，这下子步长可解了。让我们记住这个公式——不是背下来，而是大概记住这个形式，后面我们还会用到它。
下一回我们继续来看看后面的推导。