Machine Learning (5) - Large Scale Machine Learning
Stochastic gradient descent
回忆线性回归的cost function：
 - Large Scale Machine Learning/SVGa2e9495bfc83fe763885a95044e1d45f)
Stochastic的意思就是每次只用一个sample，并不断进行迭代，从而达到和普通的gradient descent相同的效果。
- Randomly shuffle dataset
- Repeat
- for i = 1, …, m
- for j = 0, …, n
- for j = 0, …, n
- for i = 1, …, m
 - Large Scale Machine Learning/SVG2b97a81c8066d369bf5f1e9cc23abbdb)
 - Large Scale Machine Learning/SVGb481fe9f91dd321ef9de8883b4db6ca1)
 - Large Scale Machine Learning/SVGbbf00422994aa813e94ff378b4ff6f8d)
 - Large Scale Machine Learning/1498184027550.png)
Mini-batch gradient descent
改进版的stochastic gradient descent
Batch gradient descent: Use all m examples in each iteration
Stochastic gradient descent: Use1 example in each iteration
Mini-batch gradient descent: Use b examples in each iteration
Say b = 10, m = 1000
Repeat{
- for i = 1, 11, 21, 31,…,991{
- for j = 0,…, n
- }
- for j = 0,…, n
- }
 - Large Scale Machine Learning/SVG7c03b661b99f5fef129ebc7ac7e1648f)
在stochastic的图像中，我们可以看到，这种算法和batch算法比较，更多迂回婉转，难于收敛。所以在取 - Large Scale Machine Learning/SVGc745b9b57c145ec5577b82542b2df546)
Learning rate
to converge.
 - Large Scale Machine Learning/SVG25b5aa6f7590e45fe012040182e4665d)
Online learning
这其实是stochastic算法的一个应用。因为在每一次的迭代中，不需要所有的sample都参与，所以算法可以一边手机数据，一边进行迭代优化。
Map-reduce and data parallelism
 - Large Scale Machine Learning/1498184980549.png)