最近读了一篇文章，关于Binary Multidimensional Scaling的。原文见下面的链接：

http://tedlab.mit.edu/~dr/Papers/bmds.jou.pdf

其中4.4部分讲到了关于learning rate的设置的一个经验方法，觉得讲得很好。以下谈谈自己的理解。

------------------------------------------------------------------

处理的问题，是一个无约束的优化问题。也就是说，我们希望去找到一个\(\mathbf{x}\)能够最小化\(f(\mathbf{x})\)。这里的\(\mathbf{x}\)是一个向量，如果是\(1\times1\)，就是一个标量。如果我们处理的未知数是一个矩阵，那么把这个矩阵中得未知数排成一列之后，也是一个未知的向量。

接下来考虑如何得到这样的\(\mathbf{x}\)。其中一个经常用到的方法是梯度下降法。也就是这样的一种迭代算法

\[\mathbf{x}_{t + 1} = \mathbf{x}_t - s  \nabla{f(\mathbf{x}_t)}\]

这里的\(\mathbf{x}_t\)指的是第\(t\)次迭代时，\(\mathbf{x}\)的值。$s$是步长，$\nabla{f(\mathbf{x}_t)}$是函数在$\mathbf{x}_t$的梯度值。在梯度的相反方向上，可以期望能够找到一个新的$\mathbf{x}_{t + 1}$使得目标函数值，尽可能的小。这里的问题来了，

如何确定这个步长$s$?

对这个问题的研究很多。这里我们只讨论一种经验性的简单做法。首先令$s = \alpha {\|\mathbf{x}_t\|}/{\|\nabla{f(\mathbf{x}_t)}\|}$。这是因为一般情况下，我们很难确定这个梯度值的取值范围。比如说$\mathbf{x}$的取值范围是在0到1之间，而它的梯度值有可能是在100左右的位置，也可能是在0.01左右的样子。那么这是时候，直接确定$s$，比较困难。在这个时候，我们在$\nabla{f(\mathbf{x}_t)}$前面乘以一个标量${\|\mathbf{x}_t\|}/{\|\nabla{f(\mathbf{x}_t)}\|}$，起到了一个矫正的作用。我们就可以确定，如果当前的$\mathbf{x}_t$是1，那么这个矫正之后梯度方向的模也是1。接下来就考虑$\alpha$应该如何确定。

总的来说，是首先给定一个初始值$\alpha = 0.2$。然后根据情况，对这个$\alpha$做一定的修改。

初始值$0.2$是文章中的原话，在最近做的一个项目中，用的是$0.1$，实验进行的很好。

接下来，我们定义，或者说在实验的过程中，维护两个变量。一个是progress，一个事instability。其中progress的定义为

\[progress = \frac{S_{t} - S_{t + 1}}{|S_{t}|}\]

其中$S_{t}=f(\mathbf{x}_t)$。可以看到，如果progress小于0的话，代表$S_{t + 1}$比$S_{t}$小，目标函数值减小了，正是我们所期望的事情。如果很不幸的，progress大于0的话，说明了函数值没有减小，反而变大。这个时候，我们就需要减小一个步长$\alpha$了。按照文章中的参数，$\alpha$变为原来的0.75。根据新的$\alpha$，可以算出来新的$\mathbf{x}_{t + 1}$，从而可以得到新的$S_{t + 1}$。如果比$S_{t}$变小了，也就是这个时候progress小于0了，就进入下一个循环。否则的话，继续减小$\alpha$，直到progress小于0，或者达到了循环停止的条件。

另一个参数是instability,其定义如下

 \[instability = I_{t + 1} = 0.5 (I_{t} + \frac{|P_{t - 1} - P_{t}|}{|P_{t - 1}|})|\]

可以想象，如果我们的目标函数值能够稳定的下降的话，那么$P_{t}$将会是一个常数，代表了目标函数值下降的程度。这个时候instability就会趋近于0。也就是说，instability越小，越是我们希望的事情。它的初值设置成10，同时，我们约定，每一次$\alpha$发生变动的时候，$I_{t}$都被重置成10。接下来，在考虑，如果这个instability比较大的话，说明不是很稳定，也就是说，目标函数值下降的时快时慢，有可能函数的曲线就是这样子的，很凹凸不平。也有可能是在最优值附近，在最优值附近不停地摆动。但不管怎么说，目标函数值是下降到的，所以尽管instability很大，我们依然不去做任何事情。唯一需要做的是这样的一种情况，instability很小，说明很稳定，但是呢,progress也很小。也就是说我们的目标函数值减小的速度很慢，就像蚂蚁一样。这是情况，说明了步长$\alpha$比较小，我们需要增大这个数值。具体来说，在$progress < 0.02$并且$instability<0.2$的时候，将$\alpha$乘以1.2。

循环停止的条件，在这里的设置是progress小于0.01，在连续的10个循环过程中。

计划，这个博客写一些技术相关的博客。领域主要限定在机器学习和计算机视觉，也会有一些跟编程有关的内容。

以读后感，原创为主。督促自己多读书，读好书。不断进取。