机器学习3：使用梯度下降和退火算法得到全局最小值
机器学习笔记三
详细阐述使用Gradient descent梯度下降的方法，求得评价模型好坏的函数L(θ)的全局最小值。
基本步骤为：首先从一个初始点θ0 开始，计算在该点下的偏导数，然后向偏导数为负的方向移动，一直重复这个步骤，直到偏导数为零的点。
但是这里有对于每次移动的距离，我们需要精心的设定。因为如果每次移动的距离过大，可能会导致梯度下降跳过了最小值的点，如果每次移动的距离无限小，可能会导致计算的时间过长、消耗资源过多的问题。
在公式中，移动的距离使用偏导数乘以学习率η来表达的，针对设定不同的学习率η，我们做一个可视化一个图表：
其中蓝色、红色和绿色的曲线是缓慢下降的，这表明学习率的选取是比较合适的，但是黄色的曲线是随时间先下降后上升的，这表明学习率，或者说移动的距离太大，导致错过了最小值的点。
那么如何确定每一次移动的距离呢，我们可以通过平时的生活常识得到这样一个定量的道理：当距离目标很远的时候，我们可以每一次移动较大的距离；当距离目标点很近时，我们就需要迈很小的步子，进行"微调"。
为了定量的确定具体的距离，我们使用一个名叫Adagrad的算法：
其中g表示的是偏导数。通过这个随时间变化的公式，我们就可以保证刚开始时移动的距离较大，而随着时间的推移，移动的距离变小了。
为了使计算的时间更快，我们可以使用改进的算法： Stochastic Gradient Descent
这个算法改进的方面在于，它每次仅仅考虑训练集中的一部分，譬如仅仅考虑训练集中的一个元素：
在模型中设计多个特征变量时（feature），常见的情况是变量的取值范围是不一样的，譬如
Y = a x长度 + b x体重 + c
x长度 ：1.5，1.6，1.5，1.6，1.56
x体重 ：100，160，140，90
这样就会导致b对模型的影响比a的影响更大，为了解决这个问题，我们可以将数据进行适量的放大或缩小，使他们的取值范围是差不多的。
这个方法叫： Feature Scaling
现在我们的计算方法优化完成了，但其实并不是一定能得到最小值的，因为我们会发现：1.有可能初始点就在最小值点的附近，这个时候根据Adagrad 的算法，我们有可能会因为移动的距离过大而导致跳过了最小值的情况。2.因为根据偏导数为零的方法找到的最小值仅仅是局部的最小值，而无法得到全局的最小值，所以并不能保证一定能得到全局最小值。
为了解决这个问题，我们可以使用模拟退火算法来避免卡在局部最小值处。
模拟退火算法描述：
若J( Y(i+1) )>= J( Y(i) ) (即移动后得到更优解)，则总是接受该移动
若J( Y(i+1) )< J( Y(i) ) (即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）
这里的"一定的概率"的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。
根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为：
P(dE) = exp( dE/(kT) )
其中k是一个常数，exp表示自然指数，且dE<0。这条公式说白了就是：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于dE总是小于0（否则就不叫退火了），因此dE/kT < 0 ，所以P(dE)的函数取值范围是(0,1) 。
随着温度T的降低，P(dE)会逐渐降低。
我们将一次向较差解的移动看做一次温度跳变过程，我们以概率P(dE)来接受这样的移动。
-
while( T > T_min )
-
{
-
dE = J( Y(i+1) ) - J( Y(i) ) ;
-
-
if ( dE >=0 ) //表达移动后得到更优解，则总是接受移动
-
Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
-
else
-
{
-
// 函数exp( dE/T )的取值范围是(0,1) ，dE/T越大，则exp( dE/T )也
-
if ( exp( dE/T ) > random( 0 , 1 ) )
-
Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
-
}
-
T = r * T ; //降温退火 ，0<r<1 。r越大，降温越慢；r越小，降温越快
-
/*
-
* 若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值
-
*/
-
i ++ ;
-
}