机器学习(二十三) —— 大数据机器学习(随机梯度下降与map reduce)

机器学习(二十三)——大数据机器学习(随机梯度下降与map reduce)

(原创内容,转载请注明来源,谢谢)

一、概述

1、存在问题

当样本集非常大的时候,例如m=1亿,此时如果使用原来的梯度下降算法(也成为批量梯度下降算法(batch gradient descent),下同),则速度会非常慢,因为其每次遍历整个数据集,才完成1次的梯度下降的优化。即计算机执行1亿次的计算,仅仅完成1次的优化,因此速度非常慢。

2、数据量考虑

在使用全量数据,而不是摘取一部分数据来做机器学习,首先需要考虑的是算法的学习曲线,如果学习曲线中训练代价函数和cv代价函数差距很大,未收敛,则可以考虑加大样本容量的使用。否则应该先考虑优化算法,加大数据量未必一定有用。

下图左边是可以加大数据量解决的问题,右边是加大数据量也无法解决的问题。

3、说明

本文下面用到的方法,都是在当数据量非常大(如1亿以上)的时候,才会考虑的方法,当数据量不大时,使用批量梯度下降最好,用下面的方法反而会有问题。

二、随机梯度下降

为了解决批量梯度下降收敛速度慢的问题,有了随机梯度下降算法(stochastic gradient descent)。

1、公式

随机梯度下降,本质上就是把批量梯度下降中,不是把整个数据集都计算完取平均值后,再调整对应的θ,而是对于每个样本,计算完该样本后,就直接更新θ。

如下图所示:

这里的重复次数,实际上数据量很大的时候,1次遍历整个数据集即可。如果想要多次优化,理论上1~10次即可,不需要太多次。

另外,随机梯度下降算法,使用之前,要打散整个数据集,这样效果更好。

2、原理

对于每个样本,计算出来的θ,实际上是一个小范围内的最优梯度。所以用这个来更新,不会直接逼近最优值,而是逼近区域的最优值,因此可能会非常的波动,蜿蜒曲折的靠近最优值,就像上图的粉色的线那样。如上图粉色的线。

而批量梯度下降,由于每次都是用整个样本最优值的均值,因此确保了样本能够直接朝着全局最优值的范围优化。如上图红色的线。

三、随机梯度下降的优化

随机梯度下降,也需要考虑到α,以及考虑算法是否正确执行。随机梯度算法正确的衡量,通常是每1000次优化,取一次误差的均值,进而画出均值-优化次数图,通过图像是否往0方向收敛,来判断算法是否正确。

之前学过,α越小,其相当于往梯度迈进的步子越小,即优化的更精确,但是收敛速度会比较慢,如下面的左上方的图。

由于随机梯度,每次的优化是局部的优化,因而会有抖动,如果把1000换成5000,图像会更平缓,但是这样算法的改变在图上表现的也不那么明显,因为是5000次的均值。如下面右上方的图。

如果发现图像一直上下波动,没有收敛也没有发散,可能是因为均值的基数太小,此时用5000来做均值,有可能会解决此问题。但是也有可能本身算法问题,或者数据等的问题导致的,这样的就无法解决。如下图左下角的图。

另外,如果α取的太大,图像发散,需要减小α,如下图右下角的图。

动态α:

为了保证抖动更少,还可以通过动态取α的值来做到,令α=C/(D+迭代次数),C、D是两个常数。这样随着迭代的深入,α越来越小,则会越来越精确,而尽量避免越过最低值导致波动的现象。

但是,这样带来的问题,就是原来需要一个α作为参数,现在需要C、D两个参数,这样需要设置的参数更多,算法更加复杂。

四、微型批量梯度下降

有一种梯度下降,介于批量梯度下降和随机梯度下降之间,叫做微型梯度下降(Mini batch gradient descent),其做法是,既不像批量梯度下降那样要遍历整个样本才做一次优化更新,也不像随机梯度下降那样每个样本更新一次,而是设定一个参数b,每遍历b个样本做一次优化更新。b通常取2~100。如下图所示:

五、在线学习

1、过程

当无法一次性获取整个数据集,或者需要不断的优化时,则要用到在线学习(online learning)技术。

在线学习,实际上就是拥有无限输入的随机梯度下降。随机梯度下降是遍历整个数据集,对于每个样本进行一次计算和优化;而在线学习没有指定的样本集,是每次来一个新的样本,就做一次优化。

这里输入的是样本的特征,并将是否被用户选择作为输出,可以用logistic回归的方式来进行学习。

如下:

2、主要业务场景

例如新闻网站,需要根据用户的点击,在用户下次登陆时展示不同的信息。这样就可以将展示出来的新闻作为样本,用户点击的话则判断为1,不点击则判断为0。对于被判断为1的新闻,拥有这种类型的特征的新闻,下次展示的概率都会更大。

六、Map-reduce

当数据量非常大,而且有多台电脑,或者计算机集群时,可以并行的来解决问题,运用map-reduce的思想来处理。

map-reduce,实际上是将一个庞大的数据集,根据当前情况进行分片,把不同的片分给不同的处理器处理,每片再把处理结果都传给同一个中央处理器,进行汇总计算。

例如现在有400个数据(这里为了举例说明,实际上400个数据用不到map-reduce,而4亿的数据则可以考虑用map-reduce),4台计算机,要进行线性回归的机器学习,采用批量梯度下降的方式进行优化。

批量梯度下降每次优化,需要累加所有的样本的求偏导的计算结果,则可以把400个数据分成4个100个的数据集,同时给4台机器处理。每台机器处理完,都将结果传给一个中央处理器。中央处理器在把这些结果求和,求均值,乘以α,做减法,触发下一次的优化。

这样,当不考虑网络延迟等问题时,可以达到原来速度的4倍。

如下图所示:

机器如下图所示:

另外,现在的很多计算机是多核的,如果一个计算机有四核,则也可以进行map-reduce,而且这样还省去了网络延时,效果更好。

另外,有的函数库,会自动的去调用计算机的多核来处理,则就不需要考虑map-reduce了。

七、总结

这一章主要提到大数据情况下的处理方式,数据量非常大时,很多平时很好用的算法会慢慢无法适应,这也是上面提到的一些改版的梯度下降的起源。对于数据量小时,如果使用随机梯度下降或者微型梯度下降,反而无法很好的收敛,因为数据量不足会导致训练次数不够。

另外,对于map-reduce,实际上是用到并行的思想来处理问题,要使用这个,首先要确定数据量足够大,有必要使用;此外,也要保证对应的机器学习算法,里面的优化过程(或部分子过程)可以拆成几个部分给各个机器同时处理,而且是耗时的部分进行拆解处理,这样才能最大的提示计算机是效用。

——written by linhxx 2018.01.26

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2018-01-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏后端之路

LinkedList源码解读

List中除了ArrayList我们最常用的就是LinkedList了。 LInkedList与ArrayList的最大区别在于元素的插入效率和随机访问效率 ...

19510
来自专栏MelonTeam专栏

ArrayList源码完全分析

导语: 这里分析的ArrayList是使用的JDK1.8里面的类,AndroidSDK里面的ArrayList基本和这个一样。 分析的方式是逐个API进行解析 ...

4489
来自专栏项勇

笔记68 | 切换fragmengt的replace和add方法笔记

1444
来自专栏alexqdjay

HashMap 多线程下死循环分析及JDK8修复

1K4
来自专栏赵俊的Java专栏

从源码上分析 ArrayList

1171
来自专栏聊聊技术

原 初学图论-Kahn拓扑排序算法(Kah

2878
来自专栏Java Edge

AbstractList源码解析1 实现的方法2 两种内部迭代器3 两种内部类3 SubList 源码分析4 RandomAccessSubList 源码:AbstractList 作为 Lis

它实现了 List 的一些位置相关操作(比如 get,set,add,remove),是第一个实现随机访问方法的集合类,但不支持添加和替换

422
来自专栏ml

朴素贝叶斯分类器(离散型)算法实现(一)

1. 贝叶斯定理:        (1)   P(A^B) = P(A|B)P(B) = P(B|A)P(A)   由(1)得    P(A|B) = P(B|...

3437
来自专栏学海无涯

Android开发之奇怪的Fragment

说起Android中的Fragment,在使用的时候稍加注意,就会发现存在以下两种: v4包中的兼容Fragment,android.support.v4.ap...

3155
来自专栏java闲聊

JDK1.8 ArrayList 源码解析

当运行 ArrayList<Integer> list = new ArrayList<>() ; ,因为它没有指定初始容量,所以它调用的是它的无参构造

1192

扫码关注云+社区