Zephon Blog
0%

Part1-大规模机器学习

发表于 更新于 分类于
本文字数： 5.2k 阅读时长 ≈ 5 分钟

Part1-大规模机器学习

大数据集学习

机器学习和数据

“赢的不是最好的算法，而是有最多数据的算法”

大数据集学习

\(\theta_j:=\theta_j - \alpha \frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)})\)

假设\(m=100,000,000\)

在训练模型之前，我们应该自问一下，为什么不只用1000个样本？

如果绘图如上，则我们可以认为增加额外的训练用例能够提升效果

相反，如果绘制的学习曲线如上图，则可以增加额外的训练用例可能对于训练结果并没有太好的效果

随机梯度下降(Stochastic gradient descent,SGD)

梯度下降训练线性回归

\(h_\theta(x) = \sum_{j=1}^n \theta_j x_j\)

\(J_{train}(\theta)=\frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2\)

\(\theta_j:=\theta_j-\alpha \frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}\)

梯度下降过程大致可如图理解

这种梯度下降法也叫做批量梯度下降(Batch gradient descent)，批量(Batch)的指的是每次都要同时考虑所有的训练样本；当数据集非常大时，训练过程就会非常慢。

随机梯度下降

\(cost(\theta,(x^{(i)},y^{(i)}))=\frac{1}{2}(h_\theta(x^{(i)})-y^{(i)})^2\)

\(J_{train}(\theta)=\frac{1}{m} \sum_{i=1}^m cost(\theta, (x^{(i)},y^{(i)})\)

SGD:

  1. 随机打乱所有数据

  2. 循环：

    for i=1,\(\cdots\),m:

    ​ \(\theta_j := \theta_j - \alpha(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}\)(for j=0,\(\cdots\),n)

由于没有求和操作，所有面对大量数据时，就不需要将数据遍历一遍了(此处遍历是指当数据量大时，不用每次因为求和而将数据依次加载到内存，再从内存中替换的过程)

如图，如果使用SGD，可能训练过程就如图中紫红色线

Mini-batch 梯度下降

Mini-batch梯度下降

批量梯度下降(Batch gradient descent)：在每次迭代中使用所有的m个样本

随机梯度下降(Stochastic gradient descent)：在每次迭代中使用1个样本

Mini-batch梯度下降：在每次迭代中使用b个样本

b：Mini-batch的大小，通常会选择b=10，(2~100)

即：

每次获取b(=10)个样本\((x^{(i)},y^{(i)}),\cdots,(x^{(i+9)},y^{(i+9)})\)

​ 循环：

​ \(\theta_j := \theta_j - \alpha \frac{1}{10}\sum_{k=i}^{i+9}(h_\theta(x^{(k)})-y^{(k)})x_j^{(k)}\)(j=0,\(\cdots\),n)

​ \(i:=i+10\)

其比批量梯度下降更快，而与SGD相比，当有一个好的矢量化方式时，Mini-batch梯度下降的效果会更好。

而Mini-梯度下降算法的缺点之一是：有一个额外的参数b，需要确定Mini-batch的大小

随机梯度下降收敛

检查收敛

批量梯度下降：

​ 绘制关于迭代次数的代价函数\(J_{train}(\theta)\)变化

​ \(J_{train}(\theta)=\frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2\)

SGD：

​ \(cost(\theta,(x^{(i)},y^{(i)}))=\frac{1}{2}(h_\theta(x^{(i)})-y^{(i)})^2\)

​ 当SGD进行学习时，在我们对某个样本进行训练前，在随机梯度下降中，我们要关注样本\((x^{(i)},y^{(i)})\)，然后对样本进行小的更新，然后到下个样本

​ 所以，当这个算法刚好扫描到样本\((x^{(i)},y^{(i)})\)时，在更新参数前，我们可以计算出这个样本对应的cost函数。

​ 最后，为了检查算法是否收敛，我们可以在每1000次迭代后，就画出前一步中所计算出的cost函数，将之前这1000个cost函数值的均值画出

例：

如果如图上左图所示的结果，这个图有很多噪声，因为它只是对一小部分样本求均值，这是一个不错的下降过程，可以看出代价函数的值在下降，从某个点开始，图像变得平缓，表示算法已经收敛如果尝试用一个更小的学习率，结果可能如图中红色所示的结果

如果如图上右图所示的结果，看起来，算法大概已经收敛了，如果将计算1000个样本均值换成计算5000个样本均值，则会得到一条更平滑的曲线，如图中红色部分

如果如图上左图所示，看上去代价函数完全没有在减小，看起来算法没有进行学习，但如果增加计算均值的数量，来对更多样本进行求均值，则结果可能会观察到图中红色线对应的情况，能看出代价函数实际上是在下降的；而如果即使使用了更大数量的样本，曲线还是很平坦，如图中紫红色曲线，那就代表算法不知出于何种原因，没有进行学习，这里就需要调整学习速率或特征或算法等

如果如图上右图所示，这种情况就是算法发散的信号，这里就需要用一个更小的学习率\(\alpha\)

注意：

我们已经知道，在SGD运行过程中，算法会从某个值开始，然后曲折到达最小值，但它不会完全收敛，而是在最小值附近一起徘徊，因此最终得到的参数只是一个全局最小值的近似值，而不是真正的全局最小值。

在大多数SGD的典型应用中，学习率\(\alpha\)一般是一个不变的常数，如果想让SGD更好的收敛到全局最小值，可以让学习率\(\alpha\)随时间变化逐渐减小，一种典型的方法就是\(\alpha = \frac{常数1}{迭代次数+常数2}\)，但这样就又需要花费时间调整这两个常数参数的值。

由于调整两个参数需要更多额外的工作，并且通常情况得到的参数值它接近全局最小值的程度已经足够使我们满意了，因此我们很少采用这种逐渐减小\(\alpha\)的值的方法，而是让\(\alpha\)保持一个常数。

在线学习

假设我们需要提供运输服务，用户们来询问将包裹从A地运到B地的服务，同时假定有一个网站，用户们登录网站，提供包裹的寄出地址和目的地址，然后网站需要计算出服务价格，然后根据计算出的价格，用户可能会接受(y=1)，有时他们不会接受(y=0)。

假定我们想要一个学习算法来帮助我们优化我们想给用户开出的价格。具体来说：

假设我们获取了描述用户特点的特征\(x\)，如：寄出地址、目的地址等。我们想学习\(p(y=1|x;\theta)\)来优化价格。

考虑使用逻辑回归：

假定有一个连续运行的网站，则以下就是在线学习算法所做的：

循环：

​ 在某个时候，一个用户访问了这个网站，对应一个\((x,y)\)

​ 使用\((x,y)\)更新参数\(\theta\)：

​ \(\theta_j:=\theta_j - \alpha (h_\theta(x)-y)x_j\)(j=0,\(\cdots\),n)

如果真的有这样一个大型网站，网站有连续的用户流，那么，这种在线学习算法就非常适用；如果我们只有少量的用户，那么就最好不要用这种在线学习算法，而是将所有的数据保存在一个固定的数据集，然后对这个数据集使用某种算法，但是如果有连续的数据流，则在线学习算法会非常有效。

而这种在线学习算法会带来一个有趣的效果，就是它可以适应变化的用户偏好，如随着时间变化、经济环境变化，用户可能 对价格更加敏感或更加不敏感，则在线学习算法也会根据变化着的用户偏好进行调整。

其它在线学习例子

产品搜索(学习如何反馈给用户更好的搜索列表)：

如用户搜索："安卓手机 1080p摄像头"

假设商店中有100种手机，需要返回10部合适的手机，而学习算法就需要找到最合适的10部手机返回给用户。

\(x\)：手机的各种特征，它会体现用户的搜索与这部手机的类似程度有多高，还可能体现用户搜索词中有多个个词可以与这部手机相匹配等

\(y\)：如果用户点击了链接，则对应\(y=1\)，否则 \(y=0\)

学习\(p(y=1|x;\theta)\)

然后用来选择10个用户最可能点击的手机进行显示

这类学习问题，也被称作点击率预测学习问题，即CTR预测(predicted CTR(click through rate))

映射化简与数据并行

映射化简(Map-reduce)

为书写方便，这里假定m=400(实际上并不大)

批量梯度下降：\(\theta_j:=\theta_j-\alpha \frac{1}{400}\sum_{i=1}^{400}(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}\)

Map-reduce：

​ 将训练集分割成不同的子集，在这个例子中，有4台机器并行处理数据，则将训练集分成4份

​ 机器1：使用前四分之一训练集\((x^{(1)},y^{(1)}),\cdots,(x^{(100)},y^{(100)})\)

​ \(temp_j^{(1)}=\sum_{i=1}^{100}(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}\)

​ 机器2：使用\((x^{(101)},y^{(101)}),\cdots,(x^{(200)},y^{(200)})\)

​ \(temp_j^{(2)}=\sum_{i=101}^{200}(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}\)

​ 机器3：使用\((x^{(201)},y^{(201)}),\cdots,(x^{(300)},y^{(300)})\)

​ \(temp_j^{(3)}=\sum_{i=201}^{300}(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}\)

​ 机器4：使用\((x^{(301)},y^{(301)}),\cdots,(x^{(400)},y^{(400)})\)

​ \(temp_j^{(4)}=\sum_{i=301}^{400}(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}\)

​ 整合并行处理的结果：

​ \(\theta_j := \theta_j -\alpha \frac{1}{400}(temp_j^{(1)}+temp_j^{(2)}+temp_j^{(3)}+temp_j^{(4)})\)(j=0,\(\cdots\),n)

Map-reduce应用在学习算法上

需要考虑的一个问题是：学习算法是否可以表示成对训练集的一种求和，实际上，很多算法都可以表示成对训练集的函数求和，而在大数据集上运行，所消耗的计算量就在于需要对非常大的训练集进行求和，所以，只要学习算法可以表示对训练集的求和或算法的主要工作可以表示成对训练集的求和，就可以使用Map-reduce来将学习算法的适用范围扩展到非常非常大的数据集

例：对于一个逻辑回归的优化算法，需要：

\(J_{train}(\theta)=-\frac{1}{m}\sum_{i=1}^m y^{(i)}\log h_\theta(x^{(i)})-(1-y^{(i)})\log(1-h_\theta(x^{(i)}))\)

\(\frac{\partial}{\partial \theta_j}J_{train}(\theta)=\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}\)

就可以通过Map-reduce将求和的部分分别交给不同的机器进行并行计算，来并行化学习算法

多核机器

目前我们只讨论了运用Map-reduce算法在多台电脑上并行计算，可能是计算机集群中的多台电脑，或者是数据中心的多台电脑，但有时，也可以在单机上进行Map-Reduce计算，因为现在很多电脑可以有多个CPU，多个CPU又有多个核心。

同一台电脑运行Map-reduce也可以不用担心由于通信传输接发变量\(temp_j\)时的网络延迟问题。

取决于不同的实现，如果有一个多核机器，然后有某些线性代数的库，实际上，有些线性代数库可以自动在一台机器的不同核心上进行并行运算，如果用的是这样的线性代数库，且学习算法有很好的向量化表示，就可以直接以向量化的形式应用标准学习算法，而不用担心并行，因为线性代数库会处理好的，所以不用再应用Map-reduce