机器学习笔记-20

处理大数据集的算法

1. 随机梯度下降
我们之前一直在学的梯度下降算法也叫Batch梯度下降算法，前面的笔记有提过一嘴。以线性回归为例子，随机梯度下降也适用于其他使用Batch梯度下降算法求参数的学习算法，随机梯度下降是对Batch梯度下降算法的改进，可以使其应用于大数据集。
Batch梯度下降算法：
在这里插入图片描述
但当m值很大时，每次都计算全部的偏导并求和所花费的代价就变大，所以需要随机梯度下降算法。随机梯度下降算法在每次迭代的过程中不需要递归全部的数据，仅仅需要一个训练样本。

随机梯度下降算法具体如下：
在这里插入图片描述
首先先进行数据预处理，将所有数据随机打乱。随后进行内循环，在内循环过程中，每一次都只拟合一个数据，选取更加拟合此数据的参数，到下一次内循环时如果有更好的参数就换，直到结束。

随机梯度下降算法和Batch梯度下降算法的最大区别就是，Batch梯度下降算法每一次内循环时都遍历所有的数据求和后才能拟合换参数，而随机梯度下降算法只遍历一个就可以换更加拟合的参数。如此减少了计算量降低了代价加速了收敛速度。
在Batch梯度下降算法中我们判断是否收敛的方法是画图，在随机梯度下降算法中我们则通过定义一个cost函数，在更新 $\theta$ 之前计算。每隔1000(或其他数值也可以)个样本计算一次平均值并将其绘图，以此检查出随机梯度下降算法是否收敛。
在这里插入图片描述

如果算法发散，减小学习率

如果想要随机梯度下降算法更好的收敛到全局最小，可以动态变化学习率让学习率的值随着时间逐渐减小：
在这里插入图片描述

const1、const2是算法外的两个常数，妥善选取
iterationNumber是迭代次数

2. Mini-Batch梯度下降
Mini-Batch梯度下降算法有时会比随机梯度下降算法还要优秀。Mini-Batch梯度下降算法每次内循环选取b个样本，通常来讲 $b \in (2, 100)$ ，具体流程如下图：
在这里插入图片描述

3. 在线学习机制
在线学习机制是随机梯度下降算法的一个变种，是一种新的、大规模的机器学习机制，可以模型化一些问题，就是想要用算法从连续的数据流中学习的这类问题。

一些大型网站上经常使用这个机制预测用户的行为从而得到更好的收益，因为不缺数据，所以在线学习没有固定的数据集，用完一个丢一个，也因此，在线学习机制可以适应变化的用户偏好。

4. 减小映射(Map Reduce)
可以使用Map Reduce处理随机梯度下降算法不能解决的更大规模的问题。
Map Reduce将训练集分成多个子集，有几台电脑运行就分成几个子集，分别在几台电脑上对其分配到的数据计算Batch梯度下降算法中的偏导求和项，计算完成后将各自的结果发送给同一个中心服务器，由中心服务器对结果进行整合处理(代入Batch梯度下降算法的参数更新的等式求值)、更新参数 $\theta_j$ 。我理解的这个过程其实就是分布式处理，但是不知道对不对，欢迎指正。
除了梯度下降算法外，任何一种只要可以通过“求和”表示的算法都可以通过Map Reduce加速。