Lecture1: Large scale machine learning
从大量的数据中学习
It’s not who has the best algorithm that wins. It’s who has the most data.
当算法处理过拟合状态，或者高方差时，更多的数据会有更好的学习效果。如果算法本身就处理高偏差的状态，那么大量的数据也不会有改善。
先选取较小的样本集合，画出学习曲线确认算法是处于哪种状态。
当数据量很大时，比如100000000时，根据\(\theta_j = \theta_j - \alpha \frac{1}{m} \sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x^{(i)}_j\)，每进行一步批量梯度下降，就要遍历所有的样本，显然计算量会特别大。
随机梯度下降(Stochastic Gradient Descent)
算法步骤
(1) 随机打乱样本数据顺序
(2) 重复执行以下循环
for i = 1 … m
\(\theta_j = \theta_j - \alpha (h_{\theta}(x^{(i)}) - y^{(i)}) \cdot x^{(i)}_j\)
算法每一次只会使用一个样本来学习参数\(\theta\)，这使得不用在每一次迭代都要遍历所有的样本，有效减少了计算量
随机梯度下降并不会收敛于全局最小值，而是会在全局最小值附近徘徊
以上算法中1到m的循环，一般会执行1-10次
小批量梯度下降（Mini-Batch Gradient Descent）
不同于批量梯度下降一次使用全部的样本，也不同于随机梯度下降每一次只使用一个样本，小批量梯度下降每一次会使用b个样本
一般b取值2-200
例如b = 10, m = 1000，则小批量梯度下降的算法可以表示为：
for i = 1,21,31,…,991
\(\theta_j := \theta_j - \alpha \dfrac{1}{10} \displaystyle \sum_{k=i}^{i+9} (h_\theta(x^{(k)}) - y^{(k)})x_j^{(k)}\)
当使用向量化运算时，小批量梯度下降有时候会比随机梯度下降效率高
随机梯度下降的收敛
收敛判断
对于批量梯度下降，我们画出\(J_{train}(\theta)\)与迭代次数的图像来判断是否正确收敛
对于随机梯度下降，有\(cost(\theta,(x^{(i)}, y^{(i)})) = \frac{1}{2}(h_\theta(x^{(i)}) - y^{(i)})^2\)
在使用\((x^{(i)}, y^{(i)})\)样本更新\(\theta\)之前，先算出\(cost(\theta,(x^{(i)}, y^{(i)}))\)
每进行1000次迭代，算出这1000次迭代过程中\(cost(\theta,(x^{(i)}, y^{(i)}))\)的平均值
画出cost与迭代次数的函数，判断是否正确收敛
当使用较小的\(\alpha\)时，算法会收敛较慢，最后在全局最小值附近振荡的幅度也更小
如果增大统计cost函数均值的迭代次数，比如从1000改到5000，那么学习曲线将更加光滑；当减少这个值时，曲线可能会变得严重地上下波动，影响判断
如果cost随着佚代次数增加而增加，那么应该考虑选择一个更小的\(\alpha\)值
为了让随机梯度下降算法尽可能的收敛于全局最小值，可以在每一次迭代之后，慢慢地减少\(\alpha\)的值
可以使用这个式子来计算\(\alpha = \frac{const1}{iterationNumber + const2}\)，但由于此式子需要确认两个常数，所以并不经常使用
在线学习
在一个持续获得学习样本的环境中，可以使用随机梯度下降的思想来解决在线学习的问题：
每当获取到一个样本\((x,y)\)，则使用此样本来学习，并更新\(\theta\)。
这样，在不断更新的数据同时，学习出来的参数也在不断地变化
MapReduce与并行计算
在批量梯度下降学习过程中，我们可以将样本分成n份，并分发到不同的学习节点（可以是独立的机器也可以是计算机中的某一个核），求得\(\displaystyle \sum_{i=p}^{q}(h_{\theta}(x^{(i)}) - y^{(i)}) \cdot x_j^{(i)}\)，然后再在一个节点合并，最终算出\(\Theta_j := \Theta_j - \alpha \dfrac{1}{z}(temp_j^{(1)} + temp_j^{(2)} + \cdots + temp_j^{(z)})\)