大数据上的机器学习

2014-12-10 | 研究学术 | 机器学习应用大数据在线学习梯度下降法

本节的主要内容来自Andrew NG的机器学习课程[1]。

需要大数据么？

当机器学习面对大数据的时候，是否从大数据中抽取一个小的子集就可以了呢？这需要分析学习曲线，确定影响性能的关键问题是数据量、特征还是模型或其它问题。

图 1: 学习曲线 [PNG]

如果是上图左所示的High Variance情况，则采用大数据能提高模型效果。若从大数据中抽取$m=1000$个样本的训练，如上图右所示，这表明机器学习是High Bias，即使加入更多的数据对性能也没有大的提升，应先加入更多的新特征（若神经网络，则增加神经元），再考虑大数据上的训练是否有利。

如何减少学习时间提高学习效率，是大数据上的机器学习需要解决的重要问题。

随机梯度下降法

对于梯度下降法，参数更新的方法是 \begin{equation} \theta_j := \theta_j - \alpha\frac{1}{m}\sum_{i=1}^m\left(h_\boldsymbol\theta\left(\mathbf x^{(i)}\right)-y^{(i)}\right)x_j^{(i)}， \end{equation} 这种方法叫做批量（batch）梯度下降法，参数更新需在整个训练集上计算一次，当$m$特别大的时候，速度就会很慢。随机梯度下降法（stochastic gradient descent）的更新方式是每次只用一个数据点更新参数。

####随机梯度下降法

数据集随机化；

更新模型参数，
Repeat ¹ { // 通常是$1\sim 10$轮迭。
for $i := 1,\dots,m$ { \begin{equation} \theta_j := \theta_j - \alpha\left(h_\boldsymbol\theta\left(\mathbf x^{(i)}\right)-y^{(i)}\right)x_j^{(i)}~~(j=1,\ldots,n) \end{equation} } }。

如下图所示，批量梯度下降法通常会向着极小值逼近，随机梯度下降法逼近道路稍显曲折，最总结果通常在极小值的某个区域内徘徊。

图 2: 左：批量梯度下降法，右：随机梯度下降法 [PNG]

小批量梯度下降法

随机梯度法每次更新参数只需要一个数据点，批量梯度法每次更新参数只需要整个训练集参数。小批量（mini-batch）梯度下降法间于二者之间，每次更新参数利用训练集的一个小子集的$b$个数据点（通常$b=2,\ldots,100$）。小批量梯度下降法的参数更新规则为 \begin{equation} \theta_j := \theta_j - \frac{\alpha}{b}\sum_{i=k}^{k+b-1}\left(h_\boldsymbol\theta\left(\mathbf x^{(i)}\right)-y^{(i)}\right)x_j^{(i)}， \end{equation} 其中$k=1,b+1,2b+1,3b+1,\ldots$。

小批量梯度下降法可利用并行化，获得比随机梯度法更快的速度，但是又多了参数$b$需要调节。

收敛性判断

随机梯度下降法可利用代价函数曲线，判断迭代过程是否收敛。但是，随机梯度下降法不会像批量梯度下降法那样，在整个训练集上评估代价。

在利用$\left(\mathbf x^{(i)},y^{(i)}\right)$更新参数$\boldsymbol\theta_j$之前，计算该点的代价（误差） \begin{equation} \mbox{cost}\left(\boldsymbol\theta,\left(\mathbf x^{(i)},y^{(i)}\right)\right)= {1\over 2}\left(h_{\boldsymbol\theta}\left(\mathbf x^{(i)}\right)-y^{(i)}\right)^2， \end{equation}

可以通过代价函数的梯度检测，判断随机梯度法是否沿着梯度下降方向更新参数。

若是在参数更新之后再计算误差，不能真实反映迭代的误差。将最近多次（比如$1000$）迭代的误差平均，作为代价函数曲线上的一个点，下图就是随机梯度下降法的代价函数曲线。

图 3: 代价函数曲线 [PNG]

小的$\alpha$能否得到更好的结果呢？随机梯度下降法的性质表明其结果会在极小值附近区域震荡，很小的学习率$\alpha$可能得到的结果也只是好一点点而已。如上图左上所示，小的$\alpha$得到稍微光滑一点的曲线，但效果提升并不明显。

上图右下的代价函数曲线不降反升，是因为学习率$\alpha$过大，可以适当调小学习率。

选择最近多少个点平均作为代价函数曲线的点合适呢？

点的数目多，代价函数曲线更光滑，需要较长时间才展示参数更新结果，不能及时的反应参数更新的情况。上图右上所示，更多数目的点平均得到的曲线更光滑。
点的数目少，代价函数曲线噪声更大。上图左下所示，过少数目的点导致曲线震荡厉害，看不到变化趋势；过多的点又导致曲线过于平坦，也看不到变化趋势。

因此，选择点的数目需要综合考虑这些情况，便于观察判断迭代是否收敛。

为了随机梯度下降法能更好逼近极小值，可动态调整学习效率$\alpha=\frac{\mbox{constant1}}{\mbox{interationNumber + constant2}}$，学习过程中不断减小$\alpha$，越是靠近极小值的地方更新步长越短。但是，这又多出两个参数$\mbox{constant1}$和$\mbox{constant2}$需要调节了，该方法也不十分常用。

在线学习

在线学习通常不需要维护一个固定的训练集，思想上和随机梯度法类似，每次新数据来，学习更新模型，然后继续接收新数据，继续更新模型……在线学习适合用于数据集动态缓慢变化的情况，模型随可随数据变换动态演进。

对于购物网站来说，随着经济大环境的改变，用户对价格的敏感度也会变化，用户特性会随时变迁，在线学习及时通过新样本训练模型可适应这些变化。

预测CTR（click-through rate）是经典的在线学习例子。比如用户在网站搜索手机，返回用户最可能点击的10个结果。

图 4: 预测CTR [PNG]

如何计算用户点击的概率呢？将搜索匹配的单词等作为特征向量，利用logistic回归可以估计用户点击概率。推荐系统的协同过滤算法学习到的特征向量，也可作为logistic的输入特征。

每次用户搜索可以得到对这10个搜索结果的反馈（是否点击了），从而得到10组数据，这些数据又可以用来训练模型。

MapReduce

MapReduce可将学习任务分配到多台机器上（或者一台机器的多个CPU核上），然后将这些机器的学习结果汇总得到整个学习结果。

####基于MapReduce的批量梯度学习算法

整个任务：$\theta_j := \theta_j - \alpha\frac{1}{400}\sum_{i=1}^{400}\left(h_\boldsymbol\theta\left(\mathbf x^{(i)}\right)-y^{(i)}\right)x_j^{(i)}$。

分配任务：

Machine 1: $temp_j^{(1)}=\sum_{i=1}^{100}\left(h_\boldsymbol\theta\left(\mathbf x^{(i)}\right)-y^{(i)}\right)x_j^{(i)}$；

Machine 2: $temp_j^{(2)}=\sum_{i={101}}^{200}\left(h_\boldsymbol\theta\left(\mathbf x^{(i)}\right)-y^{(i)}\right)x_j^{(i)}$；

Machine 3: $temp_j^{(3)}=\sum_{i={201}}^{300}\left(h_\boldsymbol\theta\left(\mathbf x^{(i)}\right)-y^{(i)}\right)x_j^{(i)}$；

Machine 4: $temp_j^{(4)}=\sum_{i={301}}^{400}\left(h_\boldsymbol\theta\left(\mathbf x^{(i)}\right)-y^{(i)}\right)x_j^{(i)}$。

任务合并：$\theta_j := \theta_j - \alpha\frac{1}{400}\left(temp_j^{(1)}+temp_j^{(2)}+temp_j^{(3)}+temp_j^{(4)}\right)$。

随机梯度下降法每次只采用一个数据点，是一个串行过程，因此不适合用Mapreduce这样的并行化方法。