番外篇(1)——最速下降法
由ypyu创建，最终由ypyu 被浏览 6 用户
番外篇正式开始，我们主要利用番外篇的时间聊一些机器学习中的黑盒部分——没错，就是优化算法。之前接受过前辈的教诲，一个机器学习的套路可以分解成三个部分——模型，目标和优化方法。模型用来定义待解决的问题，目标（一般也会被称作损失函数）用来明确评价模型质量的方法，而优化算法则是具体解决求解过程的问题。有了这三个部分，我们可以说在学术的角度上我们基本上就搞定了一个机器学习问题。之所以在前面加上了学术这两个字，是因为在工业界一个机器学习的问题就不止这三部了。
好了回到正题，我们回到前面的三个部分，一般来说第一部分是最灵活的，第二部分也算灵活，但还是有一定的约束的，然而第三部分——一般来说都是非常确定的，而且一般也是以一个黑盒的状态出现的。
于是乎大家一般对第一部分和第二部分更为关注，而对第三部分相对忽视一些。于是乎我们这里就反其道而行，作死地选择和大家聊聊第三部分——优化。实际上在前面的正文中我们已经花了很大的篇幅去聊一些优化算法，下面我们继续聊一些经典的算法。
最速下降法
友情提示，下面我们要聊的内容主要用于凸函数。关于凸函数的性质这里就不多说了，大家不懂的去查查资料就好。前面我们提到了梯度下降法，也提到了梯度下降法中那个让人头疼的learning rate，那么我们有没有其他的办法不去计算这个learning rate，又能让剃度下降的每一步尽可能地走好呢？
于是有大神们发明了下面这个方法——最速下降法。所谓的最速下降法，就是在确定下降方向后，从下降方向中找到下降程度最大的一点进行下降。我们可以用形式化的方式来明确表述下：
如果说我们前面的梯度下降法是先求出梯度，再根据预先设定的learning rate完成下降，那么就完成了一轮的优化；
而最速下降法在求出梯度之后，要进行另外一个小优化问题的求解过程，那就是选择最合适的learning rate，使得函数值最小，如果待求的函数为f(x)，当前的迭代轮数为t，那么当前函数的优化的参数解是
$x_t$
，这一点的梯度为
$-g_t$
，于是我们小优化问题就变成了：
$\alpha_t=argmin_{\alpha_t}f(x_t-\alpha_t*g)$
$x_{t+1}=x_t-\alpha_t*g$
好了，下面就该求解这个问题了。实际上我们同样可以采用求梯度并令梯度值为0的方式求出，但是那种方法并不是很容易推导出一个通用的公式，所以我们可以采用另外的方法求出一个公式来。
梯度正交
最速下降法的优化方向有一个特点，那就是相邻两轮迭代的梯度相互正交。这个特点对于推导最终的算法十分重要，我们首先来证明一下。
证明这个问题的最好方法是反证法。我们假设迭代轮数分别为t和t+1的梯度分别为
$g_t$
和
$g_{t+1}$
，如果两个梯度不正交，那么我们就可以把
$g_{t+1}$
分解成两个部分——
-
与
$g_t$
共线的部分
$g_{t+1}^t$
-
与
$g_t$
正交的部分
$g_{t+1}'$
那么问题来了——对于被第t轮更新后
$x_{t+1}$
来说，在
$g_t$
这个方向上应该是最小的了，换句话说在这个点上，关于
$g_t$
的方向梯度应该为0，那么
$g_{t+1}$
就不应该有
$g_t$
方向的分量。如果有就说明上一轮迭代并没有做到最优，和我们的假设矛盾，所以假设不成立，我们最终可以认定，
$g_t$
和
$g_{t+1}$
是正交的。
知道了正交的特点，我们就可以用这个性质来进行计算了。我们的经典问题是一个二阶优化问题：
$f(X)=\frac{1}{2}X^TAX$
首先为了保证这个问题是凸函数，我们需要对上面的一些内容做约束，具体来说就是A是对称正定的，这样，我们就能保证函数的凸性质了。
于是乎，我们可以得到第一个公式：
$g=AX$
然后是第二个公式，也就是我们刚才推倒了半天得到的结论：
$g_t^Tg_{t+1}=0$
最后是第三个公式，也是大家喜闻乐见的参数更新公式：
$x_{t+1}=x_t-\alpha_tg_t$
好了，有这三个公式就足够了，我们开始推导：
$g_t^Tg_{t+1}=0$
$g_t^T(AX_{t+1})=0$
$g_t^T(A(X_t-\alpha_t g_t))=0$
$g_t^T(AX_t-A\alpha_t g_t)=0$
$g_t^T(g_t-A\alpha_t g_t)=0$
$\alpha_t=\frac{g_t^Tg_t}{g_t^TAg_t}$
好了，到此我们就把步长的公式求解出来了，下回我们来看看一些细节问题。
\