斯坦福机器学习课程 第十周 (2)高级主题

在线学习

视频地址

在本节,我将会讨论一种新的大规模的机器学习机制,叫做在线学习机制。在拥有连续一波数据或连续的数据流涌进来,而我们又需要一个算法来从中学习的时候来模型化问题时,我们就需要用到在线学习机制

今天许多大型网站,或者许多大型网络公司,都在使用不同版本的在线学习机制算法从大批的涌入又离开网站的用户身上进行学习。

特别要提及的是,如果你有一个由连续的用户流引发的连续的数据流,用户流进入你的网站,你能做的是使用一个在线学习机制,从数据流中学习用户的偏好,然后使用这些信息,来优化一些关于网站的决策。

在线学习机制举例

运输服务对于定价的预测

假如你有一个提供运输服务的网站,在网站上提供用户选择包裹邮寄的起始地址和目的地址,并显示运输价格。然和我们需要根据用户对给出邮费价格的选择接受或者走掉,来作为正样本($y=1$)和负样本($y=0$),通过这些样本来构建学习算法,来帮助我们找到用户的特点,从而给出一个合理的邮费价格预测。

我们使用这些优化后的价格,很有可能会提高我们的利润。

对于持续运行的网站来说,以下就是在线学习算法要做的:

  • 网站一直保持在线学习状态。
  • 当一个用户偶然访问网站时,我们会得到当前用户对应的数据$(x,y)$(特征$x$是指用户所指定的起始地与目的地以及我们这一次提供给客户的价格,而$y$的取值是0或1,具体值取决于用户最终是否选择了我们的运输服务)。
  • 通过该用户的数据$(x,y)$来更新$\theta$。
    • $\theta_j := \theta_j - \alpha(h_{\theta}(x)-y)x_j \ \ \ \ \ \ \ (j=0,…,n)$

与以往的学习过程不同的是,在线学习中,每次梯度下降使用的这个当前用户的样本数据$(x,y)$,我们使用一次之后就丢弃了,我们永远都不会再次使用它。这就是为什么我们在一个时间点只会处理一个样本的原因。

如果你真的运行一个大型网站,在这个网站里你有一个连续的用户流登陆网站,那么这种在线学习算法,是一种非常合理的算法。因为数据本质上是自由的,而且数据本质上是无限的,那么或许就真的没必要重复处理一个样本。当然,如果我们只有少量的用户,那么我们就不选择像这样的在线学习算法,这种情况下最好是要保存好所有的数据,然后对这个数据集使用某种算法。

我也必须要提到一个这种在线学习算法会带来的有趣的效果,那就是它可以对正在变化的用户偏好进行调适。

搜索中对于搜索结果的优化

在搜索引擎中,我们想使用一种学习机制来学习如何反馈给用户好的搜索列表。

举个具体的例子,假如你有一个在线卖手机的网站,你有一个可以提供搜索的用户界面。在你的网站中,有100部正在售卖的手机,用户每次搜索时会提供10部手机的搜索结果。那么当用户输入类似“安卓 手机 1080p 摄像头”这样的搜索词时,我们应该推荐哪十部手机给用户呢?

我们想要做的是拥有一个在线学习机制来帮助我们 找到在这100部手机中哪十部手机是我们真正应该反馈给用户的,而且这个返回的列表是对类似这样的用户搜索条目最佳的回应。

接下来要说的是一种解决问题的思路。

对于每一个手机以及一个给定的用户搜索命令,我们可以构建一个特征矢量$x$,那么这个特征矢量$x$可能会抓取手机的各种特点,它可能会抓取类似于用户搜索命令与这部电话的类似程度有多高这样的信息,我们获取类似于:这个用户搜索命令中有多少个词,可以与这部手机的名字相匹配;或者这个搜索命令中有多少词,与这部手机的描述相匹配。

$$
x=手机的特征,\\用户的搜索词中有多少个词与手机名称匹配,\\用户的搜索词中有多少个词与手机的描述匹配,\\等等
$$

所以特征矢量$x$获取手机的特点,并且它还会获取这部手机与搜索命令的结果在各个方面的匹配程度。我们想要做的就是估测一个概率,这个概率是指用户将会点进某一个特定的手机的链接的概率。因为我们想要给用户提供那些他们很可能在浏览器中点进去查看的手机,所以我定义$y=1$是指用户点击了手机的链接,而$y=0$是指用户没有点击链接。

$$
y=1 (如果用户点击了链接) \\
y=0 (用户没有点击链接)
$$

然后我们想要做的就是学习到用户将会点击某一个特定的手机的概率:

$$
p(y=1|x;\theta)
$$

你知道的,特征$x$获取了手机的特点以及搜索条目与手机的匹配程度。这类问题其实被称作预估点击率CTR,它仅仅代表这学习用户将点击某一个特定的、你提供给他们的链接的概率。所以CTR点击率(Click Through Rate)的简称。

如果你能够估计任意一个特定手机的点击率,我们可以做的就是利用这个来给用户展示十个他们最有可能点击的手机。因为从这一百个手机中,我们可以计算出每一部手机的可能的点击率,然后选择10部用户最有可能点击的手机,那么这就是一个非常合理的来决定要展示给用户的十个搜索结果的方法。

更明确地说,假定每次用户进行一次搜索,我们回馈给用户十个结果。在线学习算法会真正地提供给我们十个$(x,y)$数据对样本。每当一个用户来到 我们网站时就给了我们十个样本,因为对于这十部我们选择要展示给用户的手机的每一个我们会得到 一个特征矢量x,而且对于这10部手机中的任何一个手机,我们还会得到$y$的取值。这些取值是根据用户有没有点击那个网页链接来决定的。这样运行此类网站的一种方法就是连续给用户展示你的十个最佳猜测,这十个推荐是指用户可能会喜欢的其他的手机,那么每次一个用户访问,你将会得到十个$(x,y)$样本数据对,然后利用一个在线学习 算法来更新你的参数。更新过程中会对这十个样本利用10步梯度下降法,然后你可以丢弃你的数据了。

如果你真的拥有一个连续的用户流进入你的网站,这将会是一个非常合理的学习方法,来学习你的算法中的参数从而来给用户展示十部他们最有可能点击查看的手机。

总结

上面几个例子的原理,你应该也能懂得其他应用的原理。例如优惠券推荐、新闻推荐等。

而且实际上,如果你有一个协作过滤系统,你可以想象到一个协作过滤系统可以给你更多的特征,这些特征可以整合到逻辑回归的分类器,从而可以尝试着预测对于你可能推荐给用户的不同产品的点击率。

这就是在线学习机制,与随机梯度下降算法非常类似,唯一的区别的是我们不会使用一个固定的数据集,而是获取一个用户样本,从那个样本中学习,然后丢弃那个样本并继续下去。而且如果你对某一种应用有一个连续的数据流,这样的算法可能会非常值得考虑。

当然在线学习的一个优点,就是如果你有一个变化的用户群、又或者你在尝试预测的事情在缓慢变化,就像你的用户的品味在缓慢变化,这个在线学习算法可以慢慢地调试你所学习到的假设,将其调节更新到最新的用户行为。

Map Reduce 和数据并行

视频地址

在之前,我们讨论了随机梯度下降,以及梯度下降算法的其他一些变种,包括如何将其运用于在线学习。然而所有这些算法都只能在一台计算机上运行,但有的时候,机器学习的运算量巨大,以至于单台机器处理起来特别耗时,所以人们希望能在多台机器上同时执行运算来提高效率。

在本节中,我将介绍进行大规模机器学习的另一种方法,称为Map Reduce。尽管我们用了很多内容来讲解随机梯度下降算法,而对于Map Reduce的介绍比较少,但是请不要根据我们介绍内容的长短来判断哪一种技术更加重要。事实上 许多人认为Map Reduce与梯度梯度下降算法相比至少是同等重要的,还有人认为Map Reduce甚至比梯度下降方法更重要。

我们之所以在Map Reduce上花的时间比较少,只是因为它相对简单,容易解释。然而实际上相比于随机梯度下降方法,Map Reduce能够处理更大规模的问题。

举例说明

假设我们要拟合一个线性回归模型,或者逻辑回归模型,或者其他的什么模型。让我们再次从随机梯度下降算法开始:

假设我们有400个样本$m=400$(实际应用中会比这个数字大很多):

$$
(x^{(1)},y^{(1)}),…,
(x^{(400)},y^{(400)})
$$

根据Map Reduce的思想,一种解决方案是将训练集划分成几个不同的子集,然后分别放在多台机器上并行的处理我们的训练数据(这里我们把数据集划分成四份,并且放在4台机器上并行处理)。

每台机器内部都去计算对应的子集的求和运算:

最后,当这些计算机全都完成了各自的工作,我们将这些临时变量收集到一起,送到一个中心计算服务器,这台服务器会将这些临时变量合并起来:

图中右侧更新的公式如下:

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

其实这个公式计算的数值和原先的梯度下降公式计算的数值是完全一样的。

Map Reduce工作原理

这里值得说明的一点是Map Reduce基本思想来自于Jeffrey DeanSanjay Ghemawat这两位研究者。其中Jeffrey Dean是硅谷最为传奇的一位工程师,今天Google所有的服务所依赖的后台基础架构,有很大一部分是他创建的。

总结来说Map Reduce技术是这么工作的:

  • 将原始训练样本均分成4份
  • 将这4份训练样本的子集送给4台不同的计算机,每一台计算机对四分之一的训练数据进行求和运算
  • 最后这4个求和结果 被送到一台中心计算服务器负责对结果进行汇总。

通过Map Reduce技术,我们相较于之前的方式提升了4倍的速度。

特别的,如果没有网络延时也不考虑通过网络来回传输数据所消耗的时间,那么你可能可以得到4倍的加速。当然,在实际工作中,因为网络延时数据汇总额外消耗时间,以及其他的一些因素,你能得到的加速总是略小于4倍的。但是,不管怎么说,这Map Reduce算法确实让我们能够处理之前单台机器无法处理的大规模数据。

使用Map Reduce的条件

如果你打算将Map Reduce技术用于加速某个机器学习算法,也就是说你打算运用多台不同的计算机并行的进行计算,那么你需要问自己一个很关键的问题,那就是你的机器学习算法是否可以表示为训练样本的某种求和

事实证明,很多机器学习算法的确可以表示为关于训练样本的函数求和。而在处理大数据时,这些算法的主要运算量在于对大量训练数据求和。

Map Reduce处理逻辑回归

对于某些使用逻辑回归的优化算法(比如说LBFGS算法,或者共轭梯度算法等等),我们需要计算两个值:

计算优化目标代价函数

首先,我们需要提供一种方法用于计算优化目标的代价函数值。比如逻辑回归的代价函数计算如下:

如果你想在10台计算机上并行计算,那么你需要将训练样本分给这10台计算机,让每台计算机计算10份之一训练数据。

计算梯度下降的偏导数项

另外,高级优化算法还需要提供某种偏导数的计算方法。对于逻辑回归,这些偏导数可以表示为训练数据的求和:

因此,和之前的例子类似,你可以让每台计算机只计算部分训练数据上的求和。最后当这些求和计算完成之后,求和结果会被发送到一台中心计算服务器上,这台服务器将对结果进行再次求和。这等同于对临时变量$temp^{(i)}_j$进行求和。而这些临时标量是第$i$台计算机算出来的。

中心计算服务器对这些临时变量求和得到了总的代价函数值,以及总的偏导数值,然后你可以将这两个值传给高级优化函数。

因此更广义的来说,通过将机器学习算法表示为 求和的形式,或者是训练数据的函数求和形式,你就可以运用Map Reduce技术来将算法并行化,这样就可以处理大规模数据了。

单台设备运行Map Reduce

目前我们只讨论了在多台计算机上运用Map Reduce技术实现并行计算。但实际上有时即使我们只有一台计算机,我们也可以运用这种技术。

具体来说,现在的许多计算机都是多核的,你可以有多个CPU,而每个CPU又包括多个核。

如果你有一个很大的训练样本,那么你可以使用一台四核的计算机,然后将训练样本分成4份,让每一个核处理其中一份子样本:

这样,在单台计算机或者单个服务器上,你也可以实现利用Map Reduce技术来划分计算任务了。

相对于多台计算机,这样在单台计算机上使用Map Reduce技术的一个优势在于:你不需要担心网络延时问题,因为所有的通讯所有的来回数据传输都发生在一台计算机上。

一个细节问题

如果你的算法实现使用的是某种自动利用多核的线性代数运算库,那么你就没有必要去手动在单台机器上实现Map Reduce了。但并不是所有的库都会自动并行运算。

一个广告:Hadoop

今天,网上有许多优秀的开源Map Reduce实现。

实际上一个称为Hadoop的开源系统已经拥有了众多的用户。通过自己实现Map Reduce算法 或者使用别人的开源实现,你就可以利用Map Reduce技术来并行化机器学习算法。这样你的算法将能够处理单台计算机处理不了的大数据。

坚持原创技术分享,您的支持将鼓励我继续创作!