监督学习

单变量线性回归

课程介绍

机器学习的两种主要类型是监督学习(Supervised Learning)无监督学习(Unsupervised Learning)。其中监督学习是实际运用最多的,也是进步最快和创新最多的算法。

本课程本课程主要讲解前面这两种学习方法。或许你也听说过强化学习(Reinforcement Learning),但不那么常用,本课程不讲。

监督学习介绍

监督学习是指学习输入到输出映射的算法。它的主要特点是,你给你的学习算法提供正确的例子去学习,最终使得算法可以在只给输入的条件下得到合理准确的预测。

常见的应用有:

举两个个具体的例子,比如想根据房子的大小来预测房价,就需要收集数据,绘制成图像,用直线或曲线拟合,然后预测出在某一点处的房价。(如下图)

预测房价的例子介绍

这属于监督学习的一种主要类型——回归(Regression),回归指从无限多个可能的数中预测出一个数。

再比如根据肿瘤的大小判断肿瘤是良性的还是恶性的,甚至还可以预测肿瘤的种类。你也可以把可能的因素也加进来作为输入,比如病人的年龄等。(如下图)

预测肿瘤的例子介绍

这属于监督学习的另一种主要类型——分类(classification)。分类和回归的区别在于,分类只有一个有限的输出。

无监督学习介绍

无监督学习中,我们只给输入,然后在数据中发掘一些内在的联系。

无监督学习的主要类型有:

线性回归模型

线性回归(Linear Regression)模型,指通过一条直线来拟合数据。

房价预测的例子

在房价预测的例子中,我们习惯把收集到的数据画成表,图中的每一个叉都对应着表中的一行数据。

符号约定

图片中用直线去拟合数据,此时可以写成:

其中是模型的参数(parameter),在机器学习中,模型的参数就是在训练的过程中可以调整的变量,用于改进模型,它们有时也叫做系数(coefficient)权重(weight)

像这样输入只是单个变量的线性回归叫做一元线性回归(Linear Regression with One Variable)或者单变量线性回归(Univariate Linear Regression)

代价函数

代价函数(Cost Function)是评价模型的一个指标,有助于我们优化模型。

在一元线性回归中,根据参数的不同,可以得到不同的直线,这些不同的直线对数据的吻合度不同,这时就需要通过代价函数来评估吻合度了。

我们常用平方误差代价函数,其中除以2是为了让后面的计算更简洁:

我们的目标是寻找合适的来使代价函数的值最小,用数学语言来表示就是.

若令,改变,那么对于某一组数据,代价函数的图像如下:

代价函数的直观理解1

如果同时改变,那么代价函数的图像如下图左,我们更习惯用等高线表示,如下图右,对于不同的三组,在某个点处可以是相同的。

代价函数的直观理解2

梯度下降

梯度下降的介绍

梯度下降(Gradient Descent)是一个用来求函数最小值的算法,我们将使用梯度下降算法来求出代价函数的最小值。

梯度下降的思想是,首先把都随机初始化成某个值,比如0,然后不断地改变这些参数,使得代价函数达到或接近最小值。

梯度下降的局部最小值

如上图(图中没有用平方误差代价函数,而是考虑任意的代价函数),起始位置的不同,可能会导致梯度下降的方向不一样,最终达到不同的最小值,这些不同的最小值叫做局部最小值(local minima),而这里面最小的那个值就叫做全局最小值(global minima)。因为我们并没有尝试完所有的参数组合,所以不能确定我们得到的局部最小值是否便是全局最小值,选择不同的初始参数组合,可能会找到不同的局部最小值。

而使用平方误差代价函数(凸函数)的一个好处是,它只有一个局部最小值,即全局最小值。

不同的书对函数凹凸性的定义不同,有时是相反的,这里我们说像碗状的这种函数是凸函数。

梯度下降的公式

使用梯度下降更新单变量线性回归的参数的公式如下:

这种梯度下降叫做批梯度下降(batch gradient descent),每一步梯度下降都会考虑到所有的样本。我们后面还会学习其他的梯度下降。

其中学习率(learning rate),它决定了向下走的每一步的步幅。学习率越小,梯度下降越慢,需要多次梯度下降才能达到代价函数最小值,学习率越大,梯度下降越快,但容易跨过最小值,出现过拟合现象。可采用逐渐减小的学习率。

我们不断地使用这两条公式同时更新参数,直至算法收敛。收敛指达到局部最小值的点。

这里面有个细节,更新完后,更新用的是还没有更新的那个,这就是所谓的“同时更新”。后面说更新参数的时候,都默认使用这种“同时更新”。

其中的计算过程如下:

同理,.

梯度下降的直观理解

为了理解梯度下降为什么能使函数达到最小值,下面画图来解释,为了简化图像,我们把代价函数的暂时去掉:

梯度下降的直观理解

如上图左,导数就是切线的斜率,图中的点处曲线是向上的,因此是正数,而也就会使减小,这时就会往左边走,也就更接近最小值了。如上图右,图中的点处曲线是向下的,因此更新后会增大,这时会往右边走,也会更接近最小值。而如果恰好落在了最小值处,那么等于0,就不会再更新了。

多元线性回归

多元线性回归模型

之前预测房价的例子中,我们只考虑了用房子的大小来预测房价,如果我们想把房子的其他加进来,比如房间数、楼层数、房龄等,我们可以用来表示这些特征。

符号约定

此时线性回归模型的函数可以写成:

不同的特征对房价的影响不同,因此它们有不同的系数。

其中有时也写成,这样的表示方法叫做向量化(vectorization),向量化后计算机可以并行计算,加快运算速度;对应地,我们也会把写成一个向量,,有时也写成;而和之前一样,是一个数字而不是向量。因此,也可以写成:

这样的线性回归叫做多元线性回归(Multiple Linear Regression)

多元线性回归的梯度下降

类似地,参照单变量线性回归的梯度下降,我们可以写出多元线性回归梯度下降的计算公式:

使用向量化后可以写成:

随着批梯度下降的迭代次数增加,代价函数的值应该是不断减小的。如果增大或者不断变大变小,可能是学习率太大导致跨过了最小值,或者是算法出了问题;如果几乎不变,可能是算法已经收敛了。实际应用中判断算法是否已经收敛,可以设置一个很小的值,比如,如果在一次迭代过后减小的量小于这个数,就可以说它收敛了。

特征缩放

对于房价预测的例子,房子的尺寸可能300-2000平方英尺之间,而房间数可能在0-5之间,一般来说,参数越大对应的就越小,这就导致了不同特征对应的可能会不在同一个数量级上,有些特征的变化几乎不会改变代价函数的值,而有些特征的微小变化却对代价函数的值影响很大。

要保证不同的特征都具有相近的尺度,可以尝试将特征缩放到-1到1之间。

一种做法是将特征除以它的最大值。比如对于一个取值范围在300-2000的特征,可以让它除以2000,这样它的取值范围就变成了0.15-1.

另一种做法是均值归一化(mean normalization),先找出该特征的均值,然后将减去后再除以它的取值范围之差。比如对于一个取值范围在300-2000的特征,.

还有一种做法是z-score标准化(z-score normalization),先计算特征的均值和标准差,然后.

当特征的取值在-1或者1附近的时候(比如-2、0.5、3等),一般不需要缩放,只有当特征取值过大或过小才需要缩放。

学习率的选择

学习率一般尝试几个不同的数,并且从小往大开始试验,比如0.001、0.003、0.01、0.03、0.1、0.3、1、…。也可以使用逐渐减小的学习率。

通过观察代价函数的值随迭代次数变化的曲线判断是否收敛以及收敛速度如何,选择大小合适的学习率。

特征的选择

特征的选择对学习算法的性能有很大的影响。比如预测房价的例子,我们会选择房子的面积作为一个参数,而不是房子的长和宽作为两个参数,这样可以让算法通过更简单的模型作出更准确的预测。因此要对研究的项目进行深入的了解,判断选择哪些特征作为模型的影响因素。

多项式回归

前面只用了直线进行拟合,我们也可以通过多项式回归(Polynomial Regression)来用曲线进行拟合。

上面是一个特征时的情况。多个特征时,不同的特征可以有不同的最高幂数。

多项式回归

由于使用了特征的高次幂,这时特征缩放就显得尤为重要了。

(补充)正规方程

到目前为止,我们都在使用梯度下降算法,但是对于某些线性回归问题,正规方程方法是更好的解决方案。

对于多元线性回归,若约定,那么可以写成,向量化后可以写成,相应地,代价函数可以写成.

我们的目标是寻找使代价函数最小的一组参数,即找代价函数的最低点,而最低点则意味着此时函数的导数为0,因此只需对求偏导即可:

上述方程的解是:

其中上标表示转置,上标表示矩阵的逆。

推导过程:

,其中的矩阵(为样本数,为特征数,即是由各样本的行向竖向堆叠而成的),的矩阵,的矩阵。把平方展开写就是:

接下来对求偏导,其中矩阵偏导的法则是

若令,则

对于不可逆的矩阵,正规方程法是不能用的。矩阵不可逆通常是特征之间不独立导致的,可以适当删除特征,或者使用正交化,也可以使用伪逆矩阵替代。

与梯度下降相比,正规方程的优点在于:1. 不需要设置学习率;2. 可以一次性算出无需迭代。而它的缺点是:1. 当数据量较大时(比如超过10,000时)运算代价较大;2. 只适用于线性模型,其他模型不能用(比如后面的逻辑回归)。

逻辑回归

线性回归的预测结果是任意的数字,而分类问题的预测结果只有几个可能的取值,这时就需要使用逻辑回归(Logistic Regression)

逻辑回归

对于只有两种可能的分类问题,称为二分类问题(Binary Classification)。比如对于垃圾邮件过滤器,我们只需判断一封邮件“是”或“不是”垃圾邮件。计算机中一般用0表示“错误”,用1表示“正确”,因此我们也习惯用0和1来表示模型的两种预测结果,分别称为负样本(Negative Class)正样本(Positive Class),比如0表示“不是垃圾邮件”(负样本),而1表示“是垃圾邮件”(正样本),这些符号的表示是人为定义的,你也可以反过来。

要使用逻辑回归,首先要了解Sigmoid函数,有时也叫做逻辑函数:

其中是自然常数,约等于2.7。它的图像如下:

Sigmoid函数

可见,它的输出总是在0到1之间的。

逻辑回归首先用一个函数计算出,比如线性回归函数,然后将传递给Sigmoid函数得到一个0到1之间的值,这个值就是输出的标签为1的概率,即,而输出标签为0的概率就是用1减去这个概率:

我们一般会设置一个阈值,当输出的概率高于该阈值时,当输出的概率低于该阈值时。我们常把这个阈值设置为0.5。

决策边界

根据逻辑回归的公式可知,当时,输出的概率大于0.5,也即认为模型的预测为1;相反的,当时,预测为0。因此我们称这条线为决策边界。

决策边界

比如,对于上图的数据,假设计算出来函数是,即,则它的决策边界是,即图中紫色的线,在这条线的左边,逻辑回归会预测,而在这条线的右边,会预测

逻辑回归中也可以用多项式回归函数来计算,这时得到的决策边界就可以是一条曲线甚至是圆等其他形状。

逻辑回归的代价函数

对于逻辑回归来说,平方误差不是一个好的代价函数,它的图像是非凸(non-convexfunction)的,有很多个局部最小值,如下图。

使用平方误差时的逻辑回归代价函数

逻辑回归通常使用交叉熵损失函数(Loss Function),它可以使逻辑回归的代价函数变成凸函数,从而只有一个局部最小值:

逻辑回归的代价函数分析

如果算法预测的概率接近1,而真实标签是1,那么计算出的损失就会很小(是一个小于1且很接近1的正数);而如果算法预测的概率接近0,而真实标签是1,那么计算出的损失就会很大(是一个很大的正数);也就是说,只有当预测的概率接近真实标签1时,损失才是最低的。

的值接近0而真实标签是0时,计算出的损失就会很小(是一个大于0且很接近0的正数);当的值接近1而真实标签是0时,计算出的损失就会很大(是一个很大的正数);也就是说,只有当预测的概率接近真实标签0时,损失才是最低的。

它可以简化为:

损失函数是在单个训练样本上考虑的,用表示;而代价函数是在整个训练集上考虑的,用表示:

逻辑回归的梯度下降

梯度下降的方法还是和之前一样的:

虽然这个公式看起来和线性回归的一样,但是其实里面的是不同的。

和线性回归类似,这里的参数也是同时更新的,即更新时用的参数都是还没有更新时的参数,全部更新完之后再把参数替换成新的。

和线性回归一样,随着批梯度下降的迭代次数增加,代价函数的值应该是不断减小的。可以画出代价函数的值随迭代次数变化的图像来观察是否收敛。

同样,线性回归中的特征缩放、学习率选择等也在逻辑回归中适用。

(补充)多类别分类

对于有多种类别的分类问题,可以创建一个“伪”训练集,让其中一个类别标记为正样本,其他类别标记为负样本,然后训练得到一个逻辑回归函数;类似地我们选择另一个类别标记为正样本,再将其他类别标记为负样本,依此类推可以得到若干个不同的函数,记作,其中。在预测时,将所有的分类函数都计算一遍,选择概率最高的类别输出。

用逻辑回归实现多类别分类

(补充)高级优化建议

有一些比梯度下降更复杂但是更快的算法,比如共轭梯度法BFGS(变尺度法)L-BFGS(限制变尺度法),这些算法的具体细节超出了本门课程的范畴,建议直接调用机器学习框架中的对应函数。

正则化

过拟合与欠拟合问题

在房价预测的例子中,假设房价的分布如下图所示:

欠拟合刚好以及过拟合

这些问题在分类问题中同样存在。

过拟合的解决办法:

当我们不想要某个特征的时候,可以在原有模型的基础上,把该特征对应的参数设置为0。而正则化更温和一点,它的思路把这些不需要的参数缩小到一个很小的值。由于不知道哪些参数需要缩小,正则化会尽可能地让算法缩小所有参数的值,这样就可以保留所有的特征,并防止权重过大。

线性回归的正则化

正则化的做法是,把特征对应的参数加入到代价函数中,让算法尽可能地减小参数的大小。以线性回归的代价函数为例:

其中是正则化参数,和学习率类似,你也需要为选择一个合适的数字。的大小体现了在最小化代价函数时,公式的前后两部分的优化是如何取舍的。如果过大会导致所有的都非常接近0,就会欠拟合;如果过小就和没有正则化时一样容易过拟合。

通常我们只需要正则化就行了,一般不需要进行正则化,它是否正则化对模型来说没有太大差别。

由于代价函数改变了,那么使用梯度下降进行参数更新的公式也会相应地改变:

推导过程:

如果将的更新公式重新排列一下,得到,可以看出是一个略小于1的数,也就是说除了原来的梯度下降更新的部分,每次还会乘以一个略小于1的数,因此正则化可以使得特征对应的这些参数减小。

逻辑回归的正则化

使用了正则化的逻辑回归的代价函数变为:

使用梯度下降进行参数更新的公式也需相应改变:

神经网络

(这部分内容已经在深度学习的笔记中写过了,知识点基本上已经涵盖了。这里只把一些公式写出来用作查阅。)

激活函数

多分类问题使用Softmax回归做输出层:

,其中

且满足

机器学习实践建议

模型的选择

模型评估:比如把训练数据的70%用于训练模型,剩下的用于验证模型在这个测试集中的表现。分别计算测试集和训练集上的代价函数(不含正则化项),就可以知道算法学习得怎么样了。对于分类问题,可以不计算代价函数,而是改为计算错误率。

模型选择

像多项式回归,我们想知道多项式的次(幂)数为多少合适,一种直观的做法是把训练数据分为训练集和测试集两部分,然后分别设计不同幂数的多项式去拟合训练集的数据,再选取在测试集中代价函数(不含正则化项)最小的那个模型。但是这样其实只是选取了一个适合测试集的模型,该模型在其他数据集中的泛化能力是不知道的。

我们可以把训练数据分为三部分,分别是训练集(training set)、交叉验证集(cross-validation set,有时也叫development set)、测试集(test set),比如比例分别是60% / 20% / 20%,在训练集中训练模型,然后在交叉验证集计算各个模型的代价函数并选取代价函数最小的那个模型,然后在测试集中计算该模型的代价函数以此来观察该模型的泛化能力。

我们也可以把不含正则化项的代价函数的值叫做错误率。

方差偏差分析

方差偏差分析:引入前面的几个的集合后,我们分析过拟合欠拟合问题就不单单在训练集上分析了,而是在训练集和交叉验证集上一起分析:

如下图,一般来说,使用越低次幂的多项式进行拟合,在训练集中的错误率就越大(欠拟合);使用越高次幂的多项式进行拟合,在训练集中的错误率就越小,但在交叉验证集中的错误率就越大(过拟合)。因此我们需要选择幂数适中的多项式,幂数可以通过观察随多项式的幂数变化的图像选出(一般都是指不含正则项的代价函数):

方差偏差分析

同理,正则化参数也可以这样找出合适的值,如下图:

方差偏差分析

有时像语音识别,可能由于有噪音,导致算法无法准确识别,因此单看误差率无法得知误差是高还是低。判断训练误差的高低时,可以和人类水平相比,或者和别人的已经实现了的算法比,又或者基于经验。

学习曲线(Learning curves)可以用来判断某一个学习算法是否存在偏差、方差问题:

学习曲线

如上图,模型在训练样本数量较少的时候很容易拟合,因此也小,但是在其他数据集(比如交叉验证集)中很容易欠拟合,因此会很大,随着样本数量的增加,会越来越接近。高偏差时,虽然接近,但和人类水平相比仍有很大差距;高方差时,远高于,且通常会低于人类水平(即过拟合)。

高偏差和高方差的应对方法

存在高偏差:

存在高方差:

神经网络如果在训练集上的表现不好(高偏差),就扩大网络规模;如果在训练集上表现良好但在交叉验证集上表现不好(高方差),就使用更多的训练数据再进行训练。

误差分析

误差分析过程(error analysis process)是指人工找出算法错误的预测,一般是从交叉验证集中找到一组算法错误分类的样本,并按照共有的主题/属性/特征等将它们分组,找出最有可能导致错误的类型,然后按需决定要做什么。比如,在训练集中加入更多这种类型的数据,再进行训练;或者在模型中加入一些新的特征,让模型能识别出这些错误分类的特点。

如果某种错误非常罕见,就不值得花那么多时间去修复了。

扩充数据集

有一种增加数据集的方法叫做数据增强(Data Augmentation),它是用已有的训练样本来创建一个新的训练样本。比如对于文字识别,有一张手写字的图片,我们可以将它通过旋转、缩放、镜像、改变对比度、扭曲等方式变成一个新的图片,但仍能看出是原来的字,这样就得到了一个新的训练样本。对于语言识别,也可以用类似的方法,比如增加不同的背景音或者音效等。

你也可以通过数据合成(Data Synthesis),从空白开始创造全新的例子。比如对文字应用不同的字体样式以及不同的颜色等,再进行截图,得到文字识别训练用的图片。

迁移学习

迁移学习(Transfer Learning)指将已训练好的神经网络模型的一部分网络结构以及参数应用到自己的模型中,只把输出层改成需要的形式,然后用自己的训练集来训练输出层的参数,而在训练的过程中其他层的参数有两种选择:一是不再更新,这种方法通常用于小训练集;二是使用训练好的模型的参数作为初始化值,更新所有参数,这种方法通常用于大训练集。

这种做法的直观理解是,对于相似类型的任务,比如都是图像识别,原来的模型前面的部分网络结构已经学习到了图像处理的一些合理的参数了,换到新的任务上,只需让模型再学习一点就可以了。

像这种先在大型数据集上进行训练,然后在较小的数据集上进一步参数调优(叫做微调,fine tuning),叫做监督预训练(supervised pretraining)

误差指标

对于一些没法和人类水平对比而且训练样本较少的数据,比如罕见病识别,我们无法得知哪个算法最好,因为有时误差小的算法可能过拟合了。这时我们就需要有不同的误差指标,一个常见误差指标是精确度(Precision)召回率(Recall)

当精确度和召回率都比较高时,算法就是有用的。

在预测罕见病的例子中,如果患病的后果不那么严重,有时为了避免误判,会在非常确信的情况下才会认为是患病,比如用逻辑回归来预测,正常情况下输出的概率大于0.5会预测为1,假设1代表患病,那么可以将设定的阈值提高,比如0.7,那么只有当输出的概率大于0.7才会预测1,这样模型的精确度就会增加,但是召回率会下降。而有时不想漏掉太多病例,可以把阈值降低,比如0.3,这样当一定程度上怀疑患病就预测1,只有当非常确定疾病不存在时才预测0,这样模型的精确度就会下降,但是召回率会增加。

我们会用F1评分(F1 score)来获得精确度和召回率的最佳权衡,它也叫P和R的调和平均数(Harmonic Mean)

其中P指精确度,R指召回率。为了强调P和R中较小的那个,先让它们分别取倒数,然后取平均,最后再倒回来。

决策树

决策树模型

如果我们知道动物的几个特征,比如耳朵形状、脸形、是否有胡子,这些特征都是一些离散的值(暂时假设只有两种可能的取值),要判断这是不是一直猫。那么我们可以画出一个类似二叉树的结构,先判断某个特征成不成立,然后再根据结果决定下一项要判断哪个特征,依此类推,最终就可以得知这是不是一只猫。

决策树模型

像上图右边这样的结构就是决策树模型(Decision Tree Model)。其中最顶端的叫做根节点(root node),中间的椭圆形框叫做决策节点(decision node),底部的矩形框叫做叶节点(leaf node)

决策树更适合处理结构化的数据(比如表格),而神经网络结构化与非结构化的数据(比如图像、视频、音频、文本等)都适用。和神经网络相比,决策树的优点在于运行速度更快,并且对于小型的决策树,里面的逻辑可能可以被人类所理解;而神经网络的优点在于,可以使用迁移学习,且容易构建大型机器学习系统,以及容易同时训练多个神经网络。

我们可以根据同样的特征画出各种不同的决策树模型模型,决策树算法的要做的是在所有可能的决策树模型中找出最好的那个。决策树算法是一种基本的分类与回归方法,其主要包括特征选择、决策树的生成、决策树的修剪。

决策树算法选择的特征要能够尽量地提高决策树的纯度(purity),纯度是指得到的分支应尽可能地都是同一类东西(比如都是猫,或者都不是猫)。

关于决策树算法何时停止,有几个选择:①当节点100%分类成功时;②当决策树模型达到允许的最大深度(深度从0开始算);③当节点的纯度的提升低于某个阈值;④当一个节点的样本数低于某个阈值。

特征选择

选择的特征要能够尽量地提高决策树的纯度,而纯度的一种测量方式是计算熵(entropy)

熵的公式为:

指分支中第类的比例,是总的种类数。这里我们定义.

我们把定义为标签为1的那一类的比例,比如在识别猫的例子中,如果将猫的标签设置为1,那么不是猫的比例。这时熵的公式为:

01分类时熵的图像

如图,当分支都是猫或者都不是猫时,熵是最小的;当分支猫和不是猫各占一半时,熵是最大的。

这里用是因为要使峰值是1,实际上用的效果也是一样的,只是峰值不一样。

我们要做的是,尝试用每个特征进行决策,找出使熵最小的那个特征。由于每个特征都会有两个分支,要综合考虑左右分支的熵,可以用它们的加权平均值。又由于决策树停止分裂的标准之一就是熵的减少量低于某个阈值,因此实际应用中,一般是和没有划分的时候比,计算熵的减少量。

对于只有两个分支的节点,公式为(正样本指“是猫”):.

熵的减少量又叫信息增益(information gain)

比如:

熵的计算举例1

对于识别猫的例子,要选择根节点,那么在全部的数据中,共有10只动物,其中5只是猫,根节点的熵为;如果用耳朵形状来这个特征作为根节点,那么左分支分出来有5个,其中4个是猫,右分支分出来有5个,其中1个是猫,因此熵的减少量是,其他的依此类推。

由于根据耳朵形状来分类信息增益最大,所以在这个例子中会选择耳朵形状作为根节点。

选好根节点的特征后,再分别选择两个子节点的特征,重复前面的过程,依此类推,直至达到指定的终止条件:

熵的计算举例2

决策树的生成

前面的思路就是ID3算法,它的完整过程如下:

  1. 从根节点开始,对节点计算所有可能的特征的信息增益,选择信息增益最大的特征作为节点的特征;
  2. 由该特征的不同取值建立子节点,再对子节点递归地调用以上方法,构建决策树;
  3. 直至达到指定的终止条件才停止递归,终止条件可以是一个或多个,比如100%分类成功 / 达到最大深度 / 特征的信息增益小于某个阈值 / 节点的样本数低于某个阈值;
  4. 最后得到一个决策树。

深度越大,决策树模型就越大,过拟合的风险也就越大,这有点像使用多项式回归。

(补充)如果最后的分类结果中仍包含多种类别,那叶子节点输出的类别按数量最多的那个类别算。

(补充)我们也可以使用其他算法:

(补充)决策树算法很容易过拟合,剪枝算法就是用来防止决策树过拟合、提高泛化性能的方法。剪枝分为预剪枝后剪枝

其他情况的特征和预测值

多种离散取值的特征

前面的特征都只有两种可能的取值,如果多种可能的取值,可以使用多叉树结构,也可以用独热编码(one-hot encoding)

独热编码的思路是,如果一个特征有多个不同的取值,那就给每个可能的取值都定义一个新的特征,这些新的特征的取值只有两种:“是”与“否”,分别对应标签1和标签0,显然,对于一个数据,同一个原特征的这些新特征只有一个为1,其他全是0。

这样就可以继续使用二叉树来构建决策树模型了。

独热编码

连续取值的特征

前面的特征都是离散值,如果是连续取值的特征,我们可以设定一个值,把小于等于这个值的归为一类,把大于这个值的归为另一类,这样就可以按照离散的情况来处理了。这个设定的值可以多尝试几个,选出信息增益最大的那个。

比如,在识别猫的例子中,把体重考虑进来,它是连续值:

连续取值的特征1

我们可以把体重的分布画出来,用不同的线去分割,分别计算每种分割方式的信息增益:

连续取值的特征2

如图,绿色的线信息增益最大,因此我们以9磅为基准把体重分为两类。

连续取值的预测值

如果要预测一个连续的值,可以使用回归树(Regression Tree)。回归树的思路是,通过比较分支中样本的对应属性的方差减少量来构建决策树,然后计算叶节点的每个样本对应属性的均值,作为预测值。

比如,我们要根据动物的耳朵形状、脸型、有无胡子,来预测它的体重。

回归树1

这时我们构建决策树的时候就不再计算信息增益了,而是改为计算分支中的样本的方差减少量。方差减少量的计算公式和信息增益类似,只不过把熵替换成方差。

回归树2

如上图,由于根据耳朵形状来分类方差减少量最大,因此会选择耳朵形状作为根节点。然后用同样的方式,分别选择两个子节点的特征,依此类推。

最后可以得到一个决策树模型,然后计算每个叶节点中样本体重的均值,作为输出的预测值。

回归树3

集成学习

集成树

决策树对数据的微小变化非常敏感,有时只改变训练集的一个数据,就可能会得到完全不同的一个决策树模型。让算法变得不那么敏感、更稳健的一个解决方案是,同时使用多个决策树,然后选取较多数的那个结果(分类任务)或取平均值(回归任务),我们称之为集成树(Tree Ensemble)

集成树的一种构建方式是,训练集使用放回抽样的方式得到一个和原来样本数量一致的新集合,这个集合中可以有重复的元素,且不一定包含所有的原始训练样本,然后用这个新集合训练一颗决策树;重复上述过程,就得到若干个不同的决策树。这种创建集成树的方式又叫做袋装决策树(Bagged Decision Tree)

事实证明,使用更多的决策树虽然不会显著地影响性能,但是在过了某个点后,收益会递减。

随机森林

使用随机森林(Random Forest)构建的集成树比袋装决策树更好。

即使抽样放回可以得到不同的决策,但是这样仍会有很多的决策树使用相同的根节点。随机森林的思路是,进一步尝试随机每一个节点的特征选择,让每颗决策树学习不同的特征。通常的做法是,假设共有个可用的特征,每个节点上都选取一个可用特征的子集,该子集的大小是(即),然后在这个特征随机选择一个作为节点的特征。其中的典型选择是

随机森林对具有大量特征的问题比较有效。

XGBoost

XGBoost(eXtreme Gradient Boosting)是一种增强决策树(Boosted Decision Tree)算法。XGBoost也是在袋装决策树的基础上进行修改的,它不再是等概率的放回抽样,而是改为之前错误分类的样本有更高的概率被抽到。生成第一颗决策树的时候,使用的集合是等概率的抽样放回得到的,而从生成第二颗决策树开始,对之前的所有决策树错误分类的样本就都有更高的概率被抽到了。

实际上XGBoost要比以上描述的复杂,建议直接调用机器学习框架函数而不是自己实现。

(补充)支持向量机

优化目标

支持向量机(Support Vector Machine,简称SVM)是从逻辑回归一点一点修改得到的。

前面在正规方程一节中我们了解到可以把回归模型中的写成,对于逻辑回归也可以这样做,因此有,相应地,代价函数也可以用向量化的形式给出

分别画出时的损失函数的图像,然后用分段函数去近似,我们把这两个分段函数分别定义为,如下图(图中):

cost函数

这时我们的优化目标就变成了

对于要优化的变量来说,上式中的是一个常数,可以去掉;前面说过,是用于权衡前后两个优化目标如何取舍,因此我们可以换个表述方式,比如把变成,这里的可以看作是,效果是一样的。最后,可以得到SVM的优化目标:

和逻辑回归不同的是,SVM不输出概率,而是直接输出1或0:

大间距的直观理解

人们有时将支持向量机看作是大间距分类器。

如果画出的图像,会发现其实当才是0,当才是0;而根据前面的公式,想预测出1只需,想预测出0只需即可。也就是说SVM对数据有更高的要求,它相当于构建了一个安全间距。

大边界的直观理解1

如下图,要分割这两组数据,其他算法可能会得到图中绿色或者洋红色的线,虽然也能正确分割,但是并不是很好;而SVM会让这条线到两组数据之间留有一定的间距,即图中黑色的线。这也是“大间距分类器”的由来。

大边界的直观理解2

大间距分类器背后的数学原理

先了解向量内积的含义:

向量内积的含义

如上图,假设都是二维向量,那么相当于投影在方向上的向量的长度乘以的范数,即,这其实和是相同的。其中,要说明的是,可以是负的,当的夹角大于90度时它就是负的。

监督学习-支持向量机-大间距分类器背后的数学原理

如上图,为了简化计算,假设,特征数。只考虑正则化部分,优化目标就变成了。根据前面向量内积的含义,就相当于的方向上作投影得到,然后用的长度乘以的范数,即

图中的决策边界(绿色线)其实是与(蓝色线)垂直的,其中由于我们令,所以过原点。根据前面的分析,要使才会预测出1,因此如果某个数据在上的投影的长度特别小,就会要求特别大;即使为负数(即预测出0时)也是如此。而我们的优化目标是,因此算法会让的长度尽可能大,而的长度正是到决策边界的距离。

核函数

前面说会根据来得到输出,其中可以是一个多项式,我们可以用一组新的特征来替换原来的特征,比如令,那么就变成

有一种更好的选择特征的方式,在原来的各个特征中随机地选取地标(landmarks),然后用特征与地标的近似程度来选取新的特征,如下图(为了表示方便这里假设只有两个特征):

核函数的地标

比如,令。其中,是样本中所有特征与地标之间的距离之和。类似地,可以令,…

这个就叫做核函数(Kernel),记作,而这里用的是高斯核函数(Gaussian Kernel)

时,;当很远时,。假设我们的训练样本有两个特征,选定地标后,改变的值,可以得到不同的图像(如下图),容易看出只有当重合时才有最大值。

核函数的图像

下面举例说明核函数是怎样作出预测的:

核函数是怎样作出预测的

如图,对于,假设,如果我们要预测图中的洋红色点,那么由于离地标比较近,所以,而,代入公式中就会计算得到0.5,由于,所以预测出1。而如果要预测一个远离地标的点(图中蓝色的点),那么就会预测出0。

在SVM中使用核函数

从前面的例子可知,决策边界在地标附近一定范围内。因此我们一般会把地标放在样本的位置上(即使是负样本也可以用作地标):

地标的选择

一般来说,如果训练集有个样本,那么就会设置个地标,并且,相应地,会有,特别地,我们定义,则:

其中.

现在我们修改支持向量机的算法为:

优化目标是:

其中优化目标的正则项还要作改动,要从改为,其中是根据我们选择核函数不同的该改变的一个矩阵,这样做是可以简化计算。

理论上讲,我们也可以在逻辑回归中使用核函数,但是上面使用来简化计算的方法不适用与逻辑回归,因此计算将非常耗费时间。

另外,支持向量机也可以不使用核函数,不使用核函数又称为线性核函数(linear kernel),当我们不采用非常复杂的函数,或者我们的训练集特征非常多而样本非常少的时候,可以采用这种不带核函数的支持向量机。

这里总结一下这两个参数对公式的影响,由前面的分析可知,故:

  1. 较大时,容易导致过拟合,即高方差;
  2. 较小时,容易导致欠拟合,即高偏差;
  3. 较大时,容易导致低方差、高偏差;
  4. 较小时,容易导致低偏差、高方差。

而核函数的选择除了前面的高斯核函数、线性核函数以外,还可以有:

这些核函数的目标也都是根据训练集和地标之间的距离来构建新特征,这些核函数需要满足Mercer’s定理,才能被支持向量机的优化软件正确处理。

关于何时使用逻辑回归,何时使用支持向量机:

  1. 如果相较于而言,要大许多,即训练集数据量不够支持我们训练一个复杂的非线性模型,就应选用逻辑回归模型或者不带核函数的支持向量机;
  2. 如果较小,而大小中等,例如在1-1000之间,而在10-10000之间,使用高斯核函数的支持向量机。
  3. 如果较小,而较大,例如在1-1000之间,而大于50000,则使用支持向量机会非常慢,这时可以创造、增加更多的特征,然后使用逻辑回归或不带核函数的支持向量机。

值得一提的是,神经网络在以上三种情况下都可能会有较好的表现,但是训练神经网络可能非常慢,选择支持向量机的原因主要在于它的代价函数是凸函数,不存在局部最小值。

无监督学习

K-means

K-means介绍

聚类算法(Clustering Algorithm)是一种无监督学习方法,它把数据分成若干个簇(cluser),有点像之前的分类,只不过它接受的是一个未标记的数据集(即只有,没有)。

K-means算法是一种常用的聚类算法,假设我们想要将数据聚类成个组,它的流程如下:

  1. 先随机选择个随机的点,这些点被称为簇质心(cluster centroids,又叫聚类中心)
  2. 然后对于数据集中的每一个数据,按照与个中心点的距离,将其与距离最近的簇质心关联起来,与同一个簇质心关联的所有点聚成一类;特别地,如果有一个簇质心没有被分配到训练样本时,习惯上一般会消除该簇,当然,你也可以重新初始化该簇质心;
  3. 计算每一个组的平均位置(即该组的坐标向量的平均值),将该组所关联的簇质心移动到平均位置;
  4. 重复上述步骤,直至中心点不再变化。
K-means算法演示

优化目标

尽管K-means不需要用梯度下降,但实际上K-means一直在优化一个特定的代价函数。假设我们有个簇质心,这些簇质心用表示,用表示离最近的那个簇质心的下标(),那么我们的优化目标就是最小化所有的数据点与其所关联的簇质心之间的距离之和,这个“距离”我们一般用L2范数计算。即代价函数为:

其中是样本数量,表示L2范数。这个K-means的代价函数又叫畸变函数(distortion function)。每次将簇质心移动到平均位置的过程,都会使这个代价函数减小。

随机初始化

选择簇质心数量的时候,使用太多的簇质心是没有意义的,应保证.

实际上,簇质心的初始位置也不是完全随意选择的。一般来说,我们会在训练样本中随机选择个,并让个簇质心的位置分别落在这个随机选择的训练样本的位置上。

K-means的一个问题在于,它有可能会停留在一个局部最小值处,而这取决于初始化的情况。

K-means的局部最小值

为了解决这个问题,我们通常需要多次运行算法,每一次都重新进行随机初始化,最后再比较多次运行的结果,选择代价函数最小的结果。这种方法在较小的时候是可行的,但是如果较大,这么做可能也不会有明显地改善。

簇数K的选择

没有最好的选择方法,通常是需要根据不同的问题,人工进行选择的,或者也可以用“肘部法则”(elbow method)作为参考。

“肘部法则”的思路是,不断改变的值来运行K-means,得到代价函数关于的值变化的图像,然后选择有明显弯曲的位置对应的值(如下图左);但不是所有情况都有明显弯曲的,有时曲线只是平滑地下降,就没法使用这个方法(如下图右)。

肘部法则

需要说明的是,选择使代价函数最小的是行不通的,因为几乎总是会随着的增加而变小。

肘部法则其实并不建议使用。选择的簇数应尽量服务于我们的问题,比如要根据客户的身高体重来确定服饰的尺码应该分为哪几种,通常更多的尺码意味着更高的成本,可以尝试常见的3个()以及5个()尺码的方案,运行K-means,然后分析成本和合身要如何权衡。

异常检测

密度估计算法

异常检测(Anomaly Detection)算法通过观察正常事件的未标记数据集,从而学会在数据与平常有较大区别时发出危险信号。

进行异常检测的一种常见方法是密度估计(Density Estimation),它的思路在有个正常样本的数据集中建立一个概率模型,然后对于测试样本,如果它的概率低于某个阈值,就认为可能出现了异常。

密度估计算法的具体做法是,对每个特征都计算均值和方差,即对于第个特征,有,然后对于一个新的数据,每个特征都根据高斯分布做出预测,然后全部乘起来,具体模型如下:

其中是样本数,是特征数。当时判断为异常。

高斯分布(Gaussian Distribution,又叫正态分布):如果一个变量符合高斯分布,就写做,其概率密度函数为:

其中分别是均值和方差:.

其实密度估计算法是在用已有数据的均值和方差来预测总体的均值和方差,并认为每个特征都是独立的,用联合概率做判断。

实数评估

关于密度估计算法中的,可以通过实数评估得到。

假设有一组带有标记的数据,里面既有正常的数据(用表示),又有异常的数据(用表示),并且异常数据要比正常数据少得多。我们用无标注的正常数据作为训练集(实际上如果有少量异常数据混进训练集中也是可以的),用剩下的正常和异常混合的有标注数据构成交叉检验集和测试集,然后使用实数评估,步骤如下:

  1. 根据训练集数据来得到密度估计模型
  2. 在交叉验证集中运行模型,选择合适的,使得算法能够可靠地分出我们放进交叉验证集中的异常数据,而不会把太多的数据标记为异常(可以用前面学的精确度、召回率、F1 score等来评估);单调整不行的话,也可以调整模型的特征,得到新的模型后再尝试选出
  3. 在测试集上对模型进行评估。

如果你收集到的异常数据较少,也可以不用测试集,只执行步骤一和步骤二即可。

特征的选择

对于监督学习,可以通过正则化等方法自动调整特征的权重,但是对于异常检测,就需要我们仔细地选择特征了。

特征的处理

异常检测假设了特征符合高斯分布,如果数据的分布不是高斯分布,虽然异常检测算法也能工作,但是最好还是将数据转换成高斯分布。(Python中可以用plt.hist查看数据的直方图,而高斯分布一般是钟形)

常用的把数据转成高斯分布的方法有:

把特征转换成高斯分布

特征的调整

如果异常检测算法在交叉验证集上表现不佳,比如,一些异常数据可能也会有较大的,这时通常会分析这些较大的异常数据样本,看看有没有新的特征能够将这些异常数据与正常数据区分开来,如果没有的话,可以尝试将一些相关的特征进行组合,来获得一些新的更好的特征,让异常数据的这些新特征能够与正常数据有较大区别。

异常检测与监督学习对比

异常检测 监督学习
需要大量的正常数据和非常少的异常数据。 需要同时有大量的正常数据和异常数据。
未来遇到的异常数据可以与已掌握的非常不同。 未来遇到的异常数据只能与训练集中的异常数据非常近似。
应用场景:欺诈行为检测、不及格产品检测、数据中心的计算机运行状况监测等。 应用场景:邮件过滤器、常见产品缺陷检测、天气预报、疾病分类。

(补充)多元高斯分布

假使我们有两个相关的特征,而且这两个特征的值域范围比较宽,这种情况下,一般的高斯分布模型可能不能很好地识别异常数据。其原因在于,一般的高斯分布模型尝试的是去同时抓住两个特征的偏差,因此会创造出一个比较大的判定边界。

如下图,有两个相关的特征,一般的高斯分布会均匀地划定判断边界(即图中的圆,可根据的大小调整范围),而有时异常数据(图中绿色的X)的会落到里面去。这时用多元高斯分布是一个更好的选择,它可以更好地捕捉特征间的相关性。

一般的高斯分布模型的缺陷

多元高斯分布的公式如下(这里用向量化的形式给出):

其中是均值的向量形式,是协方差矩阵,,注意和求和符号区分。指定矩阵,的逆。这里用向量化的方式给出了公式,需要说明的是,向量中的每个元素都对应的各个特征的均值。

不同的协方差矩阵可以有不一样的图像:

多元高斯分布演示

(图1是一般的高斯分布,图2令特征1有较小偏差,图3令特征2有较大的偏差,图4在不改变特征原有偏差的基础上增加了两者的正相关性,图5在不改变特征原有偏差的基础上增加了两者的负相关性)

原高斯分布模型和多元高斯分布模型的比较:

原高斯分布模型 多元高斯分布模型
不能捕捉特征之间的相关性,但可以通过将特征进行组合的方法来解决 自动捕捉特征之间的相关性
计算代价低,能适应大规模的特征 计算代价较高,即使训练集较小也是
必须要有 ,不然的话协方差矩阵不可逆的,通常需要 另外特征冗余也会导致协方差矩阵不可逆

原高斯分布模型被广泛使用着,如果特征之间在某种程度上存在相互关联的情况,我们可以通过构造新新特征的方法来捕捉这些相关性。

如果训练集不是太大,并且没有太多的特征,我们可以使用多元高斯分布模型。

(补充)降维

什么是降维

有时一些高维度的数据无法直观地画出图像,这就需要使用降维(Dimensionality Reduction)算法将它们降到二维或者三维,然后才能可视化。降维在其他地方也很实用,比如视频压缩,我们希望在画质损失尽可能小的情况下节省磁盘空间。下图是一个将一组二维的数据降到一维的例子。

二维数据降到一维举例

主成分分析

主成分分析(PCA)是最常见的降维算法,它的思路是找到一个方向向量(Vector direction),使得当我们把所有的数据都投射到该向量上时,投射误差(Projected Error)能尽可能地小。

投射误差

如上图,投射误差是指数据点到方向向量(可以看作是一条直线)的距离,总的投射误差一般用平均均方误差来计算。

假设要将维数据降到维,需要找出个方向,主成分分析算法的步骤如下:

  1. 均值标准化(又叫去中心化):先找出维数据的均值,然后;如果不同的特征之间取值范围差别很大,可以适当地进行特征缩放;
  2. 计算协方差矩阵(covariance matrix)
  3. 计算协方差矩阵的特征向量(eigenvectors):通常用奇异值分解(singular value decomposition)来计算,[U, S, V]= svd(Σ)
  4. 对于一个的矩阵,得到的是一个具有与数据之间最小投射误差的方向向量构成的矩阵。如果我们希望将数据从维降到维,只需要从中选取前列(一般会按对应特征值的大小从小到大排列),得到一个一个的矩阵,记为
  5. 计算投影,得到一个的向量,其中就是我们要的投影向量。

注,我们不对方差特征进行处理。

投射维数k的选择

我们希望在投射误差与训练集方差(,由于进行了去中心化,所以均值是0)的比例尽可能小的情况下选择尽可能小的值。

如果我们希望这个比例小于1%,就意味着原本数据的偏差有99%都保留下来了,一般来说选择保留95%的偏差便能非常显著地降低模型中特征的维度了。我们可以先令,然后运行主成分分析,获得,然后计算比例是否小于1%。如果不是的话再令,依此类推,直到找到可以使得比例小于1%的最小值(原因是各个特征之间通常情况存在某种相关性)。

还有一些更好的方式来选择,比如在计算奇异值分解时会得到三个矩阵[U, S, V]= svd(Σ),其中是一个的对角阵,只有对角线上有值,其它位置都是0,我们可以使用这个矩阵来计算平均均方误差与训练集方差的比例:

在压缩过数据后,我们可以采用如下方法来近似地重建原始数据:,其中.

推荐系统

基于内容的推荐系统

假设我们要构建一个算法,根据用户给看过的电影的评分,来预测用户可能会给他们没看过的电影打多少分,并以此作为推荐的依据。用户的评分规则如下图,从0到5,对于用户没有看过的电影,用?表示。

基于内容的推荐系统

符号约定

在这个例子中,只有爱情片、动作片两种电影,我们为每部电影增加两个特征,分别是浪漫程度、动作程度,并用表示添加的特征数量,这里

对于某个用户,可以使用类似线性回归的方法预测他对第部电影的评分,只不过每个用户都有一个不同的线性回归模型:

比如要预测第一个用户Alice对第三部电影的评分,假设,而就是第三部电影的两个特征,根据图中的表格,,那么

对于某个用户,损失函数为:

其中第一个求和符号下面的意思是只会对的那些求和。公式中的是一个常数,可以去掉。我们要做的是根据已有的用户评分来训练,使得代价函数最小。

而对所有的用户,代价函数可以写成:

前面我们对每一部电影,都假设掌握了对应的特征,并用它来计算用户的参数。相反地,如果我们掌握了用户的参数,也可以训练电影的特征

而对所有的电影,代价函数可以写成:

但是如果我们既没有用户的参数,也没有电影的特征,这两种方法就都不可行了。

协同过滤

协同过滤算法

如果你仔细观察前面的,你会发现它们的第一部分是完全相同的,因为的项的数量是一样的,对求和还是对求和不影响最后的结果。

协同过滤(Collaborative Filtering)算法通过把前面的两个代价函数整合到一起,可以同时学习电影特征和用户参数:

可以用梯度下降来优化上述代价函数:

如果用户对电影的评分较高,那么我们可以根据特征向量之间的的大小,推荐其他相似的电影,比如要推荐10部,那就选差距最小的前10部电影。

你也可以使用其他衡量相似度的算法,比如余弦相似度:.

二值标签

数据不一定是0到5星的评分,有时可能是喜欢或不喜欢这种只有两种可能的值,有时甚至可以根据用户行为来标注数据,比如完整地看完了电影或看了一部分就关掉,再比如是否点击、是否购买等。我们可以根据这些二值标签来预测用户对其他电影/商品的行为。

二值标签

我们可以在前面模型的基础上,加上一个激活函数,比如,让预测值变成0或1:

此外,把损失函数改成二元交叉熵损失函数(binary cross entropy loss function),让它更适合二值标签:

而二值标签协同过滤的代价函数为:

改进:均值归一化

如下图,回到电影评分的例子,如果我们有一位还没有对任何电影进行评分新用户,按照原来的算法,没法对这位新用户做出预测。使用均值归一化(mean normalization)后,可以根据全体用户对电影的平均分来给这位新用户做预测。

为什么要均值归一化

可以把上图的数据放到一个矩阵里,计算全体用户对各电影评分的平均值,然后用减去

然后用这个新的去训练模型。用新模型算出来的预测分,需要加回平均分,即,这样做也能避免出现负分。

对于一个新用户,由于正则化项会让尽可能变小,因此无论随机初始化成什么,该新用户对应的最后训练出来都会几乎等于零(虽然没有正则化,但所有参数都会随机初始化成一个很小的数),因此我们的新模型会认为他给每部电影的评分都是该电影的平均分。

除了将行归一化外,其实还有另一种选择,可以将列归一化成均值为0,在这个例子中,就可以预测出一个还没有人评分的电影的预测分,但这样做意义不大。

由上面的例子,可见协同过滤有一些限制:

以上的这些问题叫做冷启动问题(cold start problem),对于几乎没人评分的电影或者评分很少的用户,协同过滤的结果可能不是很准确,而且协同过滤不能提供一种自然的方式来使用附带信息或者有关项目或用户的附加信息,比如我们可能知道电影的类型、演员、工作室等,或者对于用户,我们可能知道他们的年龄、性别、位置等。

内容过滤

基于内容过滤算法(content-based filtering algorithm)会根据用户和物品的特征,尝试决定哪些物品和用户可能彼此匹配。

基于内容过滤算法仍需要用户对某些物品的评分,这里的符号约定和前面一样。用户特征可能有年龄、性别、国家、看过的电影、给每种类型电影的平均评分等,其中像性别、国家这种特征可以用one-hot向量表示,然后用这些特征组成一个特征向量;电影的特征可能有上映时间、电影类型、评论、平均评分,然后用这些特征组成一个特征向量。这些特征也可以组合起来变成一个新特征,比如每个国家/地区的平均分等。

值得注意的是,的大小(维度)可以不一样,因此需要经过处理才能运算。

基于内容过滤算法也是使用类似线性回归的方法来预测,实际上,把去掉并不会影响结果,因此可以用来进行预测。由前面可知,是用户的特征,是电影的特征;这里用户特征经过处理后,用表示(对应原来的),电影特征经过处理后,用表示(对应原来的),于是可以得到:

比如中的每个元素表示该用户对每种类型电影的喜爱程度,而中的每个元素可以表示该电影属于每种类型的程度,这样两者的大小就对应起来了。

得到,以及由得到的过程,可以分别使用两个有相同输出数量的神经网络:

使用神经网络构建内容过滤的参数

要训练上述模型,可以定义代价函数如下,然后用梯度下降不断优化:

类似协同过滤,如果需要输出0或1就加一个Sigmoid激活函数

类似协同过滤,要推荐其他相似的电影,可以找使较小的那些电影。

如何进行推荐

许多推荐系统的实现都分为两个步骤,分别被称为数据检索和排名:

  1. 检索:生成一堆候选项目列表,试图涵盖像用户推荐的种种可能,即使包含用户可能不太喜欢的项目也是可以的;
  2. 排名:微调,并选择最好的项目推荐给用户。

比如,在检索步骤中,对用户最近观看的10部电影,每部都找10部相似的电影,这个相似的电影可以预先计算,通过查表获得,然后再为用户观看次数最多的3种类型的电影,找出榜单的前10,以及用户所在地区榜单的前10等,尽可能涵盖所有可能,然后也一并添加到添加到候选列表里,最后删除候重复项,删除用户已经看过的电影等;在排名步骤中,把检索到的电影输入到学习好的模型中,用学习好的模型对它们进行预测评分,并根据预测的评分进行排名,然后选取评分最高的几部电影进行推荐。

对于大规模的数据,可以预先计算所有电影的,这样在检索时就可以查表获得,提高效率。

由于检索过程得到的项目越多,算法就会越慢,为了分析/优化对检索项目数量的取舍,可以用不同的数量进行离线实验,来看看检索额外的项目会产生多少更相关的推荐。

强化学习

强化学习模型

强化学习(Reinforcement Learning)是基于环境的反馈而行动的,通过不断地与环境的交互、试错,最终完成特定目标或使得整体收益最大化。它的特点是,每一步行动都需要环境给予的反馈。

比如,想让程序控制火星车执行设定的指令,可以每秒获取若干次各个传感器的数据,然后通过强化学习来决定怎么做。我们把火星车的位置、方向、速度等统称为状态,任务是找到一个函数,将火星车的状态映射到状态。传统监督学习很难找到一个从状态到状态的动作集,而强化学习通过输入奖励或者说奖励函数,告诉火星车什么时候做得好,什么时候做得不好,来实现这个过程。

每次状态变换都要考虑当前状态(state)、奖励/奖励函数(reward function)动作(action)下一个状态,并且如果达到了终止状态(terminal state)就停止。

折扣因子

如上图,只有达成一个目标才能获得奖励(图中是找到不同的地形),如果不作限制,火星车可以在状态之间来回跳动(比如)。为了让程序尽可能快地拿到奖励,可以设置一个折扣因子(discount factor),让越往后面的动作获得的奖励就越少,这样也能让机器在更远的目标更高的奖励以及更近的目标更少的奖励之间做出权衡。如果使用了负的奖励,该算法就会让这些负的奖励尽可能地推迟到未来。回报(return)被定义为奖励的总和,公式是(其中是奖励):

而强化学习中的动作,可以通过策略(policy,有时也叫控制器,controller)体现出来,比如总是去最近的奖励,或者总是往左/右,或者总是朝着更大/更小的奖励前进等。有了总回报的公式,就可以倒推出在当前状态下往不同方向走能获得的回报,并以此作为依据,根据不同的策略作出判断(倒推的数只用作判断,计算时还是用奖励算):

策略

我们的可以定义一个策略函数,输入任意的状态,然后映射到我们希望采取的某个动作.

这种形式的强化学习应用有一个名字,叫马尔可夫决策(Markov Decision Process,简称MDP),它指未来仅取决于当前的状态,而不取决于在到达当前状态之前可能发生的任何事情。

MDP

状态-动作价值函数

状态-动作价值函数(state action value function)是关于可能所处的状态和做出的动作的函数,通常用字母表示,因此又叫Q函数(Q-function)的值表示尝试在状态采取动作一次,之后再按策略走,所能带来的回报。

虽然前面定义了策略,但是这个策略并不一定是最好的策略,要找到最佳策略,可以尝试从当前状态往不同的方向走一步,之后再按原策略走,计算出不同方向的并进行对比,最大的方向就是最好的方向,依此类推,通过对原策略的不断优化,就能找到最佳策略了。

动作价值函数的计算

如上图,比如要计算,那就是从状态2先往右走一步到状态3,然后再按照策略,从状态3往左走到状态2再往左走到状态1,这样得到的回报是,因此。而在终止状态中用的就是该终止状态对应的奖励。易知可能的最大回报就是.

贝尔曼方程

贝尔曼方程(Bellman equation)提供了一种计算Q函数的方法。为了表示这个方程,我们用表示当前状态,用表示当前状态的奖励,用表示当前动作,用表示从状态执行了动作后达到的新状态,用表示可能会在状态是采取的新动作。贝尔曼方程如下:

对于在终止状态,贝尔曼方程简化为

举例验证一下这条方程,如下图:

举例说明贝尔曼方程

贝尔曼方程说明了分为两部分,第一部分是马上获得的奖励,叫做即时奖励,第二部分是在状态下采取最佳动作后获得的最佳回报,因此可以从另一个角度看这条方程:.

随机环境

在某些应用中,当你采取行动时,结果并不总是可靠的,比如让火星车往左走,可能会遇到岩石滑坡,或者打滑,就会走错方向。因此要模拟随机的环境(random/stochastic environment),将发生意外的情况考虑进去。这种随机的强化学习应用叫随机马尔可夫决策(Stochastic Markov Decision Process,简称SMDP)

在随机强化学习中,我们感兴趣的不是最大回报,因为那是一个随机数,我们感兴趣的是最大化回报的平均值:

这里的平均值指的是期望回报(expected return),即运行若干次算法,可能会得到很多不同的回报值,然后取这些回报值的平均值。

这时的贝尔曼方程改为:

比如我们从状态2往左走,成功的概率是0.9,而有0.1的概率会变成往右走,这时.

连续状态空间

介绍

前面的状态都是离散的值,而实际上状态可能是连续的,连续状态的强化学习问题,叫做连续状态马尔可夫决策(Continuous State Markov Decision Process)。下面通过一个案例来说明。

月球登录器

上图是一个简化版的登月器,它的状态有坐标、水平移动速度、垂直移动速度、左倾斜角度、右倾斜角度、左脚是否着地、右脚是否着地,其中都是数字,是连续的,而只有0或1两种取值:

它有左推进器、主推进器(即底部引擎)、右推进器可以控制,比如打开左推进器就会使登月器向右移动。这里定义动作nothing表示什么也不做,left表示启动左推进器、main表示启动底部引擎、right表示启动右推进器。

奖励函数定义如下:

目标是学习一个策略,当给定一个状态时,采取动作,以最大化回报。一般情况下会用很接近1的折扣因子,这里

学习Q函数

这里的使用神经网络来训练,我们把状态和动作组合成在一起作为输入到神经网络中,其中使用one-hot编码,而就是神经网络的输出

使用神经网络训练Q函数

这样如果能够训练出合适的神经网络参数,就可以把全部都输入到神经网络中,然后找出最高的那个动作。

训练这个神经网络的步骤如下(叫做DQN算法):

  1. 先随机初始化神经网络的参数;

  2. 然后可以在登月模拟器中对登月器使用随机的方式得到若干组,令,而可以通过贝尔曼方程计算得到,这样就得到了一个包含大量样本对的训练集;

    对于一个状态,需要计算所有可能的动作,才能得到.

    其中是通过我们的神经网络计算得到的,虽然一开始我们是随机初始化的,但是随着一次次迭代,就能得到准确的

  3. 通过训练集的数据训练神经网络得到,再用替换原来的,重复步骤2、3。

    神经网络的代价函数可以使用平方误差代价函数。

算法的改进

改进1:神经网络的结构

前面的神经网络只输出,那么对于一个状态,需要计算所有可能的动作才能得知哪个是最佳的。我们可以让神经网络同时输出所有动作的值,以减少计算量:

神经网络结构的改进

这样在计算时也可以一次性完成。

改进2:ε-Greedy

我们可以使用ε贪婪策略(ε-Greedy policy),这样在还没计算出准确的时也能有一个很好的估计。它的思路如下:在比如说0.95的概率下选取使最大化的动作,在0.05的概率下选取随机动作。这个采取随机动作的概率是可以设置的超参数,用表示。

这样做的原因是,完全随机的策略(即神经网络初始化时完全随机)通常会得到一些不好的判断,比如认为启动主推进器是一个不好的选择,因此总是很低,由于每次只会选取使最大的动作,所以总是不会尝试启动主推进器,神经网络就无法得知启动主推进器是否是一个更好的选择。而如果使用ε贪婪策略,每一步都有小概率尝试不同的动作,使得计算出来的最大值带有一定的随机性,这样神经网络就能克服先入为主的印象。

这种随机选取动作的想法有时被称为探索(Exploration)。通常一开始会将设置得很大,这样一开始就有很大概率采取随机动作,然后随着迭代次数的增加,逐渐把减少。

改进3:mini-batch

mini-batch的思路是,对一个很大的数据集,每次更新数据的时候,不需要全部数据同时运算,而是每次选取其中一小部分进行运算,分多次完成计算。

下图是算法的mini-batch版本:

用mini-batch改进算法

改进4:soft updates

在神经网络迭代完成后会用替换原来的,但是算出来的可能会比原来的差,使用软更新(soft updates)可以避免这种情况。

假设原来的中神经网络的参数为在神经网络的参数为,那么软更新的思路就是在更新参数时,比如令,也就是只用1%的新值,用99%的旧值,每次只更新一点点。这个百分比是可以设置的超参数。

结果表明,使用软更新可以使强化学习更可靠地收敛,可以降低强化学习算法振荡或不收敛或具有其他不良性质的可能性。