Large scale machine learning

回想之前学过的所有机器学习算法,大致的步骤如下:
1.定义hypothesis 和 cost function
2.求gradient descent
3.minimize cost function得到parameters
4.将parameters应用与hypothesis中进行计算
对于机器学习算法来说,是否有好的性能大概率取决于你是否有足够的数据.
那么问题来了,如果我们有足够的数据,之前介绍过的算法是否能够有效率的计算这些数据?

以linear regression打比方,如下图所示是linear regression的gradient descent算法,每次更新我们需要将所有样本都遍历一遍, 假设样本超大(比如亿级别),那么算法的效率将非常糟糕,不仅如此,大量的训练样本将要一次性load到内存中,并不是所有机器都能做到的.做完这些以后,算法仅仅向global min推进了一小步,不知道还要执行这个过程多少次cost才能收敛.这种每次扫描所有样本的梯度下降算法被称为batch gradient descent.

linear regression

Stochastic gradient descent

Stochastic gradient descent是另一种梯度下降算法,适用于样本量非常大的情况,计算效率要比Batch gradient descent要高,对比如下:

Stochastic vs. Batch
Stochastic gradient descent的思想是是对于每一个样本去minimize cost function,所以在每一次gradient descent过程中只需要考虑当前的样本.具体步骤如下:
Stochastic gradient descent
在做Stochastic gradient descent之前有必要把样本数据先随机打乱,对于优化的过程可能需要做1～10次,但是这样也比Batch gradient descent好多了.
Stochastic gradient descent的缺点也很明显,因为对于每一次梯度下降只考虑当前样本,所以梯度下降的过程会十分曲折而且最终cost也不会收敛.所以这个过程多重复几次就显得很有必要了.

Mini-batch gradient descent

comparison between 3 gradient descent

Mini-batch gradient descent is somewhere in between Stochastic gradient descent and Batch gradient descent. 2~100 are the reasonable choices for b.

Mini-Batch gradient descent

Mini-Batch gradient descent can be even faster than Stochastic gradient descent if you use vectorization properly.

Stochastic gradient descent convergence

Checking for convergence cost

左上1:每1000次迭代打印前1000次平均代价
右上2:每5000次迭代打印前5000次平局代价(迭代次数越多越平滑)
左下1:learning rate较小,convergence的速度慢
右下2:learning rate较大,diversion

Choose learning rate

learning rate一般来说保持不变,但是也可以随着迭代慢慢减小,如果learning rate函数选择的合理可以得到更合适的parameter.

Online learning

Online learning

在有足够的持续incoming的数据的情况下,我们并不需要Training Set,我们只需要对每一条数据求gradient descent并更新parameter即可,这样做的好处是如果数据的特征在变化(比如用户的口味)那么你的hypothesis函数也会随之慢慢调整,就像在用一个一直在更新的Training Set不停的优化一样.

MapReduce and data parallelism

Training Set MapReduce
MapReduce with batch gradient descent
机器学习中使用mapreduce的场景比如上图,将拆分成4份,分发给worker执行,最后将结果合并到master上由master去做gradient descent最后的步骤.
当然没有多台机器,多线程也是可以做的.