机器学习初等指南(3)

这是基于吴恩达机器学习》课程的笔记的第三部分,主要记录无监督学习相关内容。

第一部分(监督学习1)传送门:Here

第二部分(监督学习2)传送门:Here

References

机器学习周志华) “西瓜书”,教材

机器学习实战 基于Python的编程练习册

统计学习方法李航) 算法的数理分析

机器学习训练秘籍吴恩达) 面向工程应用的指南

机器学习笔记1吴晓军)重点参考笔记

机器学习笔记2 面向软件的介绍手册

机器学习训练营

机器学习的一些资料

神经网络与深度学习

《动手学深度学习》 深度学习进阶

AiLearning

機器學習基石机器学习技法林轩田) 进阶教学视频

K-Means

无监督学习!

从本节开始,将正式进入到无监督学习(Unsupervised Learning)部分。
无监督学习,顾名思义,就是不受监督的学习,一种自由的学习方式。
该学习方式不需要先验知识进行指导,而是不断地自我认知,自我巩固,最后进行自我归纳。
在机器学习中,无监督学习可以被简单理解为不为训练集提供对应的类别标识(label),其与有监督学习的对比如下:

  • 有监督学习(Supervised Learning)下的训练集:$(x^{(1)}, y^{(1)}), (x^{(2)}, y^{2})$。
  • 无监督学习(Unsupervised Learning)下的训练集:$(x^{(1)}), (x^{(2)}), (x^{(3)})$。

聚类

在有监督学习中,我们把对样本进行分类的过程称之为分类(Classification).
无监督学习中,我们将物体被划分到不同集合的过程称之为聚类(Clustering)

在聚类中,我们把物体所在的集合称之为簇(cluster)

K-Means算法

那么,K-Means 这个算法是如何完成聚类过程的呢?其实算法名称中对此已有体现:

  • K: 描述了的数量,也就是应当聚合成的类数。
  • Means均值求解会是该算法的核心。

下面具体看到该算法的步骤:

(1)根据设定的聚类数 K,随机地选择 K 个聚类中心(Cluster Centroid),这就好比古代乱世,天下诸侯并起而逐鹿。

(2)评估各个样本到聚类中心的距离,如果样本距离第 i 个聚类中心更近,则认为其属于第 i 簇,这可以看做四方义士纷纷投奔诸侯,形成不同的势力。

(3)计算每个簇中样本的平均(Mean)位置,将聚类中心移动至该位置,该过程可以被认为是诸侯调整战略根据地以达到最强的控制力和凝聚力。

重复以上步骤直至各个聚类中心的位置不再发生改变。

综上,K-Means 的算法步骤能够简单概括为:

  1. 分配:样本分配到簇。
  2. 移动:移动聚类中心到簇中样本的平均位置。

Source:File

注意:有时某些聚类中心可能没有被分配到样本,这样的聚类中心就会被淘汰(意味着最终的类数可能会减少)。

More:Hard & Soft Clustering(动态演示)。

代价函数

和其他机器学习算法一样,K-Means 也要评估并且最小化聚类代价,在引入 K-Means 的代价函数之前,先引入如下定义:

引入代价函数:(所有点到其对应中心的距离均方之和)

$J$也被称为失真代价函数(Distortion Cost Function)

实际上,K-Means 的两步已经完成了最小化代价函数的过程:

  • 样本分配时

    • 我们固定住了 (μ1,μ2,…,μk),而关于 $(c^{(1)},c^{(2)},…,c^{(m)}) $ 最小化了 J。
  • 中心移动时

    • 同理,我们再关于$(\mu_1,\mu_2,…,\mu_k)$最小化了 J代价函数。

由于 K-Means 每次迭代过程都在最小化$ J$,所以下面的代价函数变化曲线不会出现

随机初始化

通常,我们会随机选取 K 个样本作为 K 个聚类中心(K同的初始化有可能引起不同的聚类结果</u>,能达到全局最优(global optimal)固然是好的,但是,往往得到的是局部最优(local optimal)。

目前,想要提前避免不好的聚类结果仍是困难的,我们只能尝试不同的初始化

for i=1 to 100:

  1. 随机初始化,执行 K-Means,得到每个所属的簇 c(i),以及各聚类的中心位置 μ:

  2. 计算失真函数$ J$

选择这 100 次中,$J $最小的作为最终的聚类结果。

显然,该方法计算量较大,所以只适用于 K 值较小的场景。

选择聚类数量

实际上,一开始是很难确定聚类数的,下图的两种聚类数似乎都是可行的:

但是,也存在一种称之为肘部法则(Elbow Method)的方法来选定适当的K值:

上图曲线类似于人的手肘,“肘关节”部分对应的 K 值就是最恰当的 K 值,但是并不是所有代价函数曲线都存在明显的“肘关节”,例如下面的曲线:

一般来说,K-Means 得到的聚类结果应服务于我们的后续目的(如通过聚类进行市场分析),所以不能脱离实际而单纯以数学方法来选择 K 值。在下面这个例子中,假定我们的衣服想要是分为 S,M,L 三个尺码,就设定 K=3,如果我们想要 XS、S、M、L、XL 5 个衣服的尺码,就设定 K=5:

这实际反映了点集的相似特征是具有尺度的。之前的肘部原则就是因为给定的点集缺少微观特征。(相似总是对应着某种度量上的接近)
不同尺度下可能分成不同数量的类,甚至同一个尺度下可能有多种特征。
(BUT,如何通过特征尺度的需要来自动化地选取初始聚类数?加入噪声!在微观尺度上进行平滑化处理,增加一些桥梁点)

K-Means虽然表面上是无监督的,却是有隐性的监督和隐特征——K平均本身就是点集将具有的一个特征(这些被分成的类中元素将在度量和尺度上接近)。这说明,即使不人为从高层输入特征信号,一个良好的学习算法仍然能够从底层自生成“自然”的特征(这时初始值就尤为重要,因为微观特征将被首先生成)。

More:二分K-Means算法。该算法从顶层开始逐步贪心地划分,能确保最优解,但算法效率低。

降维

投影

我们很希望有足够多的特征(知识)来保准学习模型的训练效果,尤其在图像处理这类的任务中,高维特征是在所难免的,但是,高维的特征也有几个如下不好的地方:

  1. 学习性能下降,知识越多,吸收知识(输入),并且精通知识(学习)的速度就越慢。
  2. 过多的特征难于分辨,你很难第一时间认识某个特征代表的意义。
  3. 特征冗余,如下图所示,厘米和英尺就是一对冗余特征,他们本身代表的意义是一样的,并且能够相互转换。

我们使用现在使用了一条绿色直线,将各个样本投影到该直线,那么,原来二维的特征 厘米,英尺x=(厘米,英尺)就被降低为了一维 直线上的相对位置

是不是很像线性回归?(稍微有点区别)

但是,线性回归的误差度量的是平行于y轴方向的。这个的误差度量则垂直与给定的优化直线。

并且推广以后,线性回归中优化的对象只有y变量。而在PCA中所有的变量被同等对待

而在下面的例子中,点云在一个二维平面周围富集。
我们又将三维特征投影到二维平面,从而将三维特征降到了二维:

综上,不难发现,特征降维的一般手段就是将高维特征投影到低维空间

PCA(主成分分析)

PCA(Principle Component Analysis),即主成分分析法,是特征降维的最常用手段。顾名思义,PCA 能从冗余特征中提取主要成分,在不太损失模型质量的情况下,提升了模型训练速度

降低特征维度不只能加速模型的训练速度,还能帮我们在低维空间分析数据,例如,一个在三维空间完成的聚类问题,我们可以通过 PCA 将特征降低到二维平面进行可视化分析。

例如下表中,我们有将近几十个特征来描述国家的经济水平,但是你仔细观察发现,我们很难直观的看出各个国家的经济差异。

通过降维,我们将特征降低到了二维,并在二维空间进行观察,很清楚的就能发现美国和新加坡具有很高的经济水平:(x-国家总GDP和y-人均GDP)


如下图所示,我们将样本到红色向量的距离称作是投影误差(Projection Error)。以二维投影到一维为例,PCA 就是要找寻一条直线,使得各个特征的投影误差足够小,这样才能尽可能的保留原特征具有的信息

这条直线可以用一个向量来表示。事实上,一个n维超平面总可以用n个向量表示(相当于坐标基)。

假设我们要将特征从 n 维度降到 k 维:PCA 首先找寻 k 个 n 维向量,然后将特征投影到这些向量构成的 k维空间,并保证投影误差足够小。
下图中,为了将特征维度从三维降低到二维,PCA 就会先找寻两个三维向量 $u^{(1)},u^{(2)}$。二者构成了一个二维平面,然后将原来的三维特征投影到该二维平面上:

算法

对于PCA方法有效性的证明可以参考:Here

假定我们需要将特征维度从 n 维降到 k 维。则 PCA 的执行流程如下:

  1. 特征标准化,平衡各个特征尺度:

  2. 计算协方差矩阵 Σ:(左边是矩阵符,右边是求和符)

  3. 通过奇异值分解(SVD),求取 Σ特征向量(eigenvectors):

    在协方差矩阵中,求Eigen value是数值稳定的(正定)。(通常eig()则不稳定)

  4. 从 U 中取出前 k 个左奇异向量(即前k列),构成一个被降维矩阵 $U_{reduce}$:

  5. 计算新的特征向量z^{(i)}:

主成分数量选择

从 PCA 的执行流程中,我们知道,需要为 PCA 指定目的维度 k。如果降维不多,则性能提升不大;如果目标维度太小,则又丢失了许多信息。
通常,使用如下的流程的来评估 k 值选取优异

  1. 求各样本的投影均方误差: $\min\frac{1}{m}\sum\limits{j=1}^{m}||x^{(i)}-x{approx}^{(i)}||^2$

  2. 求数据的总变差(variation):$\cfrac{1}{m}\sum\limits_{j=1}^{m}||x^{(i)}||^2$

  3. 评估下式是否成立:

其中,ϵ 的取值可以为 0.01,0.05,0.10,⋯0.01,0.05,0.10,⋯,假设 ϵ=0.01,我们就说“特征间 99% 的差异性(variance)得到保留”。

事实上,利用之前算法的奇异值分解:$(U,{\color{red}{S} },V^T) = {\color{blue}{\text{svd} } }(\Sigma)$。我们有更简单的办法计算上式:

释放/升维

因为PCA仅保留了特征的主成分,所以PCA是一种有损的压缩方式,假定我们获得新特征向量为:

那么,还原后的特征 $x_{approx}$ 为:

Tips

PCA能降低数据存储消耗,加速学习算法,还可以做可视化($k\le 3$)。

由于 PCA 减小了特征维度,因而也有可能帮助解决过拟合(Bad!可能表现挺好,但还是推荐正则化)。

PCA 不是必须的,在机器学习中,一定谨记不要提前优化,只有当算法运行效率不尽如人意时,再考虑使用 PCA 或者其他特征降维手段来提升训练速度。

异常检测

异常检测(Anomaly Detection)是机器学习里面的一个常见应用,机器通过训练,将知道什么样的样本是正常样本,从而具备识别异常样本的能力。

尽管异常检测常被认为是无监督学习,但它跟有监督学习又有着千丝万缕的联系。

飞机制造商在飞机引擎从生产线上流入市场前,会考虑进行异常检测,以防止不合格引擎造成恶劣结果。而为了进行异常检测,通常就需要采集一些引擎特征,如:

上标是样本指针,下标是特征指针。

假定现在有引擎的数据集:${x^{(1)},x^{(2)},\cdots,x^{(m)} }$,这些数据都是正常样本,我们将其绘制到二维平面上:

现在,新来了一个引擎样本(以绿色标志),它落到了正常样本中间,亦即,它表现了和正常样本类似的特征,所以,我们希望,新来的样本也会被当做是正常样本,从而让它顺利流入市场:

与此同时,又来了一个引擎,由于它偏离正常样本汇集的位置过远,其理所当然被认为是异常样本,从而被回炉重造:

综上我们知道,我们需要根据已有数据集构建一个概率模型 p(x),如果某一样本被认为是正常样本的概率足够小,它就该被当做是异常:(发生概率)


Anomaly detection example:

  • Fraud detection
  • Manufacturing
  • Monitoring computers in a data center

高斯分布模型

异常检测的核心就在于找到一个概率模型——帮助我们知道一个样本落入正常样本中的概率,从而帮助我们区分正常和异常样本。高斯分布(Gaussian Distribution)模型就是异常检测算法最常使用的概率分布模型。

我们称 $X∼N(μ,δ^2)$ 为: X 服从均值为 μ,方差为 δ^2 的高斯分布(也称正态分布)。高斯分布的概率密度函数为:

同时,概率模型可以表述为

均值 μ 决定了高斯分布概率密度函数的对称轴位置
方差 $δ^2$ 衡量了各样本与平均位置的差异,决定了概率密度函数的宽窄。δ^2 越大,各个样本的差异越大(各个样本偏离均值位置很远),即样本取 μ 附近位置的概率越低,亦即,概率 P(μ−ϵ<x<μ+ϵ) 很小,此时,概率密度函数很
下图展示了几组不同参数取值下的高斯分布的概率密度函数:

参数估计

高斯分布的参数估计:给定一个数据集,估算出μ和$δ^2$的值

假定第 j 个特征 $x_j$ 分布如下:

我们发现,该分布中间稠密,越向两边越稀疏,我们就认为数据服从高斯分布,即:$x_j \sim N(\mu_j,\delta_j^2)$。
但该分布的 μj 和 δj 参数未知。
可以根据这有限个样本进行(关于特征 j 的) μ 和 $δ^2$ 的参数估计:

如果学过概率论,这里对参数 μ 和参数 $δ^2$ 的估计就是二者的极大似然估计

当然,在数学上对于$δ^2$也有除以m-1的,但在实际使用中几乎没有什么区别。

算法

假定我们有数据集:${x^{(1)},x^{(2)},\cdots,x^{(m)} }, x \in R^n$。并且,各个特征服从于高斯分布。
完成了对于各个特征分布的参数估计后,可以得到:

有了前面的知识,我们可以得到,采用了高斯分布异常检测算法流程如下:

  1. 选择一些能够反映异常样本的特征 $x_j$。

  2. 对各个特征进行参数估计

  3. 当新的样本 x 到来时,计算 p(x)

    如果 $p(x)<{\color{purple}{\epsilon} }$,则认为样本 x 是异常样本。


:假定我们有两个特征 $x_1、x_2$,它们都服从于高斯分布,并且通过参数估计,我们知道了分布参数:

则模型 $p(x)$ 能由如下的热力图反映,热力图越热的地方,是正常样本的概率越高。

参数 $\color{purple}{ϵ}$ 描述了一个截断高度(截断概率),当概率落到了截断高度以下(下图紫色区域所示),则为异常样本:

将 p(x) 投影到特征所在平面,下图紫色曲线就反映了 $\color{purple}{ϵ}$ 的投影,它是一条截断曲线,落在截断曲线以外的样本,都会被认为是异常样本:

数据集划分

假定我们的引擎数据集被标注了是否为异常样本:(类似有监督)

并且,含有正常样本 10000 个,异常样本 20 个。那么,我们可以这样划分数据集:

  • 训练集含 6000 个正常样本。
  • 交叉验证集含 2000 个正常样本,10 个异常样本。
  • 测试集含 2000 个正常样本,10 个异常样本。

Evaluation

由于异常样本通常是非常少的,所以整个数据集是非常偏斜的,我们不能单纯的用预测准确率来评估算法优劣,因此,可以考虑使用我们在优化设计-偏斜类一节中提过的评价手段:

  • 真阳性、假阳性、真阴性、假阴性
  • 查准率(Precision)与 召回率(Recall)
  • $F_1Score$
  • 还可以利用交叉验证集来优化参数 $\color{purple}{ϵ}$(模型选择)

很多人会认为异常检测非常类似于有监督学习,尤其是逻辑回归。
这里用一张表格来描述有监督学习与异常检测的区别

有监督学习 异常检测
数据分布均匀 数据非常偏斜,异常样本数目远小于正常样本数目
可以根据对正样本的拟合来知道正样本的形态,从而预测新来的样本是否是正样本 异常的类型不一,很难根据对现有的异常样本(即正样本)的拟合来判断出异常样本的形态

下面的表格则展示了二者的一些应用场景对比:

有监督学习 异常检测
垃圾邮件检测 故障检测
天气预测(预测雨天、晴天、或是多云天气) 某数据中心对于机器设备的监控
癌症的分类 制造业判断一个零部件是否异常
…… ……

特征选择

转化为高斯分布

为了构建异常检测模型,我们就希望特征能服从高斯分布:(尽管不这样做算法也可能运行良好,但这样做可能会更好)

我们一开始拿到的特征的分布可能是这样的:

我们可以同过对数转换($log(x+c)$)或者其他操作(低指数次方)将他转化为高斯分布
例如,上面的特征经对数转换后形成的分布就非常接近于高斯分布:

实际上,$\text{log}x和x^\epsilon$在量级较小时是接近的。相当于将数值较低的部分拉伸。

误差分析

我们希望p(x)能尽量有更大的区分度,对正常样本尽量高,对异常尽量低。

但是有时会出现:正常、异常样本的概率都比较大。有时需要深入考察异常样本,从而看看是否能找出新的特征来帮助算法区别。

构建新特征

我们知道,在异常检测中,样本特征要尽可能区分正常样本和异常样本
例如,为了监测机房中的服务器异常状况,我们选定了如下特征:

当异常发生时,这些值都会非常大。但是,我们遇到一个新的异常:

  • 程序执行时进入了某个死循环,此时 CPU负载 很高,而网络流量很低(业务全部卡死在服务器,而没有和客户端通信),亦即,一个特征过大,而一个特征过小,要去识别这样一种情况,我们考虑创建新的特征:

当上述异常发生时,该特征将会变得相当大,有助于标识出异常发生。

这个例子说明,我们可以通过组合现有特征,来产生标识度更明显的特征。

多元高斯

在服务器运转监控的问题中,我们获得一个服务器样本 x,并且,计算了 $p(x_1;μ_1,δ_1^2) 及 p(x_2;μ_2,δ_2^2) $,认为该服务器的 CPU 负载和内存使用都在正常范围内,也就认为该服务器运转正常:

但是,截断边界却将该样本截在了正常样本之外,认为服务器发生异常:(一个倾斜的数据集

可以看到,出现错误截端的原因在于,我们的高斯分布模型形成的截断边界太固定(相当于多个边缘分布)。
试想,如果我们原有的决策边界能经放缩,旋转等操作,变换到下图的紫色边界位置,该服务器就不会被错分为异常了:

为此,引入了多元高斯分布模型。

理论上通过坐标转换也能解决这个问题,但寻找合适的坐标是困难的。

定义

多元高斯不再对$p(x_1),p(x_2),…,p(x_n)$分别建模,而是一次性地建立模型

多元高斯分布模型被定义为:

其中,μ 表示样本均值,$Σ_{n\times n}$ 表示样本协方差矩阵

多元高斯分布模型的热力图如下:

调参

  • 改变 Σ 主对角线的数值可以进行不同方向的宽度拉伸

    $\longrightarrow$比例拉伸:(同时改变)

    $\longrightarrow$非比例拉伸:(改变一些项)

  • 改变 Σ 次对角线的数值可以斜拉伸/旋转分布图像。

    $\longrightarrow$斜拉伸:(同时正改变)

    $\longrightarrow$斜拉伸:(同时负改变)

  • 改变 μ 可以对分布图像进行位移

参数估计

多元高斯分布模型的参数估计如下:

算法流程

采用了多元高斯分布的异常检测算法流程如下:

  1. 选择一些足够反映异常样本的特征 $x_j$。

  2. 对各个样本进行参数估计:

  3. 当新的样本 x 到来时,计算 p(x):

    如果 p(x)<ϵ,则认为样本 x 是异常样本。

与一般高斯分布模型的差异

实际上,一般的高斯分布模型只是多元高斯分布模型的一个约束,它将多元高斯分布的等高线约束到了如下所示同轴分布:(协方差矩阵 Σ 是对角阵)

一般高斯模型 多元高斯模型
需要手动创建一些特征来描述某些特征的相关性 利用协方差矩阵 Σ 自动获得了各个特征相关性
计算复杂度低,适用于高维特征 计算复杂
在样本数目 m 较小时也工作良好 需要 Σ 可逆,亦即需要 m>n(实际要远大于,比如一个数量级),且各个特征不能线性相关

由此可以看出,基于多元高斯分布模型的异常检测应用十分有限。

实际上完全可以在少数几个特征上(异常预测失败的特征)使用多元高斯,然后继续使用分步高斯。

推荐系统

推荐系统是机器学习最重要的应用之一(尽管在学术上被讨论地较少),你所知道的淘宝、亚马逊、facebook、豆瓣这些网站都把推荐系统作为了核心。

之前已经提到过,有一些算法可以自动地生成特征(而不需要手动去选择),推荐系统就是其中之一。

在某个电影资讯的网站,有那么一份用户对于电影的打分(0 - 5 分),? 代表用户没有评价过该电影:

Movie/User Alice(1) Bob(2) Carol(3) Dave(4)
Love at last 5 5 0 0
Romance for ever 5 ? ? 0
Cute puppies of love ? 4 0 ?
Nonstop car chases 0 0 5 4
Swords vs. karate 0 0 5 ?

推荐系统就是自动地填满这些缺失值(?),然后预测什么是用户会感兴趣的内容。

基于内容的推荐算法

该网站根据电影的内容,对每部电影都给出了两个评价指数,构成了基于电影内容的二维特征向量 x:

Movie/User Alice($\theta^{(1)}$) Bob($\theta^{(2)}$) Carol($\theta^{(3)}$) Dave($\theta^{(4)}$) $x_1$ $x_2$
Love at last 5 5 0 0 0.9 0
Romance for ever 5 ? ? 0 1.0 0.01
Cute puppies of love ? 4 0 ? 0.99 0
Nonstop car chases 0 0 5 4 0.1 1.0
Swords vs. karate 0 0 5 ? 0 0.9

假设用户 i 对于每个指数的偏好程度由向量 $θ^{(i)}$ 所衡量,则我们估计该用户对电影 j 的打分为:(线性回归

默认设定:$x_0^{(j)}=1$。

比如,对于Alice预测她对Cute puppies of love的喜好程度:(假设我们已经得到了用户参数$\theta^{(1)}$)

这就是基于内容的推荐系统,我们根据商品内容来判断用户可能对某个商品的偏好程度,本例中,商品内容就是电影具有的一些指数。我们也知道了,推荐系统中两个重要的维度:

代价函数

引入 $r(i,j)$ 表示第 i 个用户是否对第 j 部电影进行了打分:

为了对用户 j 打分状况作出最精确的预测,我们需要:(约去了$m^{(j)}$项,不影响极值)

那么对于所用用户 1,2,…,$n_u$,我们就需要:

代价函数$J(\theta^{(1)}, \theta^{(2)}, …, \theta^{(n_u)})$就为:

梯度下降法更新参数:

协同过滤

这一节将介绍具有特征学习(Feature learning)——自行学习所要使用的特征能力的算法。

回到上一节的问题,每部电影,我们都有评价其内容的特征向量 x。但是,在现实中,不会有任何网站,任何人有精力,有能力去评估每部电影所具有的一些指数。


假定我们先有了各个用户对电影的偏爱评估 $θ^{(j)}$:

并且,不知道电影内容特征的指数 $x^{(i)}$:

Movie/User Alice(1) Bob(2) Carol(3) Dave(4) x1 x2
Love at last 5 5 0 0 ? ?
Romance for ever 5 ? ? 0 ? ?
Cute puppies of love ? 4 0 ? ? ?
Nonstop car chases 0 0 5 4 ? ?
Swords vs. karate 0 0 5 ? ? ?

现在,我们通过 $\theta^{(1)}, …, \theta^{(n_u)}$ 来学习电影指数 x(i):(求和指数变化,正则项变化)

则对于所有的电影指数$x^{(1)},…,x^{(n_m)}$:


现在,我们拥有了评价用户的 θ 和评价商品的 x,并且:

  • 给定 θ 及用户对商品的评价,我们能估计 x。
  • 给定 x,我们又能估计 θ。

有点像“鸡生蛋,蛋生鸡”。

因此,就构成了 $θ\longrightarrow x\longrightarrow θ\longrightarrow x$… 的优化序列,这便是协同过滤算法(Collaborative Filtering)

进一步,可以同时(simultaneously)优化商品和用户具有的参数:

  1. 推测用户喜好:给定x,估计 θ

  2. 推测商品内容:给定θ,估计 x

  3. 协同过滤同时优化θ和x

    即(红色的3个公式其实是相等的)

    $\sum_{(i,j):r(i,j)=1}$反映了用户和商品所有有效配对。


使用了协同过滤的推荐算法流程为:

  1. 随机初始化$x^{(i)},…,x^{(n_m)} ; \theta^{(1)}, …, \theta^{(n_u)}$为一些较小值,与神经网络的参数初始化类似,为避免系统陷入僵死状态,不使用 0 值初始化。

  2. 使用梯度下降法来最小化$J(x^{(i)},…,x^{(n_m)};\theta^{(1)}, …, \theta^{(n_u)})$
    对于 j=1,2,..,n_u,i=1,2,…,n_m,参数的更新式为:

  3. 如果用户的偏好向量为 θ,而商品的特征向量为 x,则可以预测用户评价为 $θ^Tx$。

因为协同过滤算法 θ 和 x 相互影响,二者都没必要使用偏置θ_0和x_0,即,$x∈R^n、θ∈R^n$。

矢量化: 低秩矩阵分解

我们将用户对电影的评分表格:

Movie/User Alice(1) Bob(2) Carol(3) Dave(4)
Love at last 5 5 0 0
Romance for ever 5 ? ? 0
Cute puppies of love ? 4 0 ?
Nonstop car chases 0 0 5 4
Swords vs. karate 0 0 5 ?

用矩阵表示:

我们发现,由于用户不会对所有电影都进行打分,所以该矩阵通常是十分稀疏的。
如果我们用预测来描述这个矩阵:

令:

即矩阵 X 的每一行描述了一部电影的内容,矩阵$Θ^T$ 的每一列描述了一位用户对于电影内容偏好程度。
亦即,我们将原来稀疏的矩阵分解为了 X 和 Θ。现在预测可以写为:

用这个方法求取 X 和 Θ,获得推荐系统需要的参数,称之为低秩矩阵分解(Low Rank Matrix Factorization),该方法不仅能在编程时直接通过向量化的手法获得参数,还通过矩阵分解节省了内存空间。

当我们获得了电影 i 的特征向量后,我们就可以通过计算 $||x^{(j)}-x^{(i)}||$ 来比较电影 j 与电影 i 的相似度。那么,给予了电影 j 足够好评的用户,也会被推荐到类似的电影。(又可以聚类了

均值标准化

假定我们现在新注册了一个用户 Eve(5),他还没有对任何电影作出评价:1

Movie/User Alice(1) Bob(2) Carol(3) Dave(4) Eve(5)
Love at last 5 5 0 0 ?
Romance for ever 5 ? ? 0 ?
Cute puppies of love ? 4 0 ? ?
Nonstop car chases 0 0 5 4 ?
Swords vs. karate 0 0 5 ? ?

Eve(5) 对于电影内容的偏好应当被参数 $θ^{(5)}$ 所评估,注意到我们的最小化代价函数过程:

由于该用户没有对任何电影作出评价,$θ^{(5)}$能影响上式的项只有:

为了最小化该式,则显然会得到 $\theta^{(5)} = \begin{pmatrix} 0 \ 0 \end{pmatrix}$,从而,Eve(5) 对任何电影的评价将会被预测为:

显然,这就是一种“not useful”的预测了,系统会因此认为 Eve 对任何电影都不感冒,那么,Eve 就是吃饱了撑的来注册这个网站。

为了这个解决这个问题,我们会先求取各个电影的平均得分 μ:

并求取 Y−μ,对 Y 进行均值标准化(Mean normalization):(即,使得每一行元素和=0

对于用户 j,他对电影 i 的评分就为:$y(i, j) = (\theta^{(i)})^T x^{(j)} + {\color{red}{\mu_i} }$。

那么 Eve 对电影的评分就为:$y(i, 5) = (\theta^{(5)})^T x^{(i)} + \mu_i ={\color{red}{\mu_i} }$。

即,系统在用户未给出评价时,默认该用户对电影的评价与其他用户的平均评价一致。貌似利用均值标准化让用户的初始评价预测客观了些,但这也是盲目的,不准确的。实际环境中,如果一个电影确实没人被评价过,那么他没有任何理由被推荐给用户。

大数据

之前已经提到——在机器学习界流传着这样一句话:

It’s not who has the best algorithm that wins. It’s who has the most data.

在识别易混淆词汇一例中,我们分别使用了四种算法:(1)Perceptron;(2)Naive Bayes;(3)Winnow;(4)Memory-Based。通过下图可以看到,这四种算法都随着数据规模的增长获得了更高的精度

所以,在机器学习中,除了构建算法模型(低偏差),为模型提供足够大,足够多的数据也成为了关键。同时,我们也需要做好准备,以更快速的方式处理、消化大数据。拥有了大数据,也就意味着在算法模型中,我们面临着一个很大的 m 值。

梯度下降

BGD(批量梯度下降法)

拥有了大数据,就意味着,我们的算法模型中得面临一个很大的 m 值。回顾到我们的批量梯度下降法:

可以看到,每更新一个参数 $θ_j$,我们都不得不遍历一遍样本集,在 m 很大时,该算法就显得比较低效(尤其是计算机内存不够,需要反复读取数据)。

但是,批量梯度下降法能找到全局最优解:

梯度下降

SGD(随机梯度下降法)

针对大数据集,又引入了随机梯度下降法(Stochastic gradient descent),该算法的执行过程为:

在执行前通常要将数据集/样本做乱序随机处理。使得遍历样本的过程更加分散。

相较于批量梯度下降法,随机梯度下降法每次更新 $θ_j$ 只会用当前遍历的样本。虽然外层循环仍需要遍历所有样本,但是,往往我们能在样本尚未遍历完时就已经收敛(一般最多遍历1-10遍数据集),因此,面临大数据集时,随机梯度下降法性能卓越

上图反映了随机梯度下降法找寻最优解的过程,相较于批量梯度下降法,随机梯度下降法的曲线就显得不是那么平滑,而是很曲折了,其也倾向于找到局部最优解而不是全局最优解。

因此,我们通常需要绘制学习曲线来监控随机梯度的工作过程是否正确。

例如,假定误差定义为$cost(\theta, (x^{(i)}, y^{(i)})) = \frac{1}{2}(h_\theta(x^{(i)})-y^{(i)})^2$,则每完成 1000 次迭代,即遍历了 1000 个样本,我们求取平均误差并进行绘制,得到误差随迭代次数的变化曲线:

另外,遇到下面的曲线也不用担心,其并不意味着我们的学习率出了问题,有可能是我们的平均间隔取的太小:(导致你看不出来代价函数实际是在慢慢减少)

如果,我们每进行 5000 次迭代才进行绘制,那么曲线将更加平滑:

如果我们面临明显上升态势的曲线,就要考虑降低学习率 α 了:

另外,学习率 α 还可以随着迭代次数进行优化:$\alpha = \cfrac{const.1} {\text{iterationNumber} + const.2}$。

这样,随着迭代次数的增多,步长就会放缓,避免出现抖动:

MBGD(Mini批量梯度下降法)

Mini Batch梯度下降法是批量梯度下降法和随机梯度下降法的折中,通过参数 b 指明了每次迭代时,用于更新 θ 的样本数。
假定 b=10,m=1000,Mini 批量梯度下降法的工作过程如下:

一般只有向量化做得好,才能让MBGD的优势体现出来(使用并行机制)。

在线学习

:(快递报价)

用户登录了某提供货运服务的网站,输入了货运的发件地址和收件地址,该网站给出了货运报价,用户决定是购买该服务(y=1)或者是放弃购买该服务(y=0)。

特征向量 x 包括了收发地址,报价信息,我们想要学习 $p(y=1|x;θ) $来优化报价:

这就是在线学习(Online learning,与前面章节提到的机器学习过程不同,在线学习并不需要一个固定的样本集进行学习,而是不断接收样本,不断通过接收到的样本进行学习。

因此,在线学习的前提是:我们面临着流动的数据。(数据流

在线学习还可以适应变化的用户偏好。

Map-Reduce

前面,我们提到了 Mini 批量梯度下降法,假定 b=400,m=400,000,000,我们对 θ 的优化就为:

假定我们有 4 个机器(Machine),我们首先通过 Map (映射)过程来并行计算式中的求和项,每个机器被分配到 100 个样本进行计算:(矩阵相乘的本质是求和,而求和可以分开求

最后,通过 Reduce(规约)操作进行求和:

我们可以使用多台机器进行 MapReduce,此时,Map 任务被分配到多个机器完成:

也可以使用单机多核心进行 MapReduce,此时,Map 任务被分配到多个 CPU 核心完成:

能实现MapReduce的软件:Hadoop等。

案例-光学字符识别

先放一张非字符识别的动态识别图。Source:here


假定我们有下面一张图片,光学字符识别要解决的问题就是识别图片中的所有字符:

光学字符识别的工作流程为:

  • 文本检测:获得包含了文本的文本框。

  • 字符分割:从文本框中分割出各个字符。

  • 字符分类(识别):字符分割中得到的只是一个个字符图形,在字符分类阶段,才能真正知道该字符类别。

之前曾有一个手写识别的教学视频,原理是相似的。

有些监测系统可能更复杂,比如拥有进一步的修正识别结果的功能。

滑动窗口

Source:here


:(行人识别)

由于行人的识别矩形框的长宽比是近似固定的,可能稍微比文字识别简单一点

选用一个82X36像素的矩形框,并确定一些正、负例:

然后就可以Sliding window了。把每一个window分别喂给分类器进行检测就可以了。

文本检测

滑动窗口(Sliding window)是检测图像中目标对象的最常用手段,在文本检测阶段,我们首先定义正、负样本,正样本图像描述了含有文本的图像,负样本描述了不含文本的图像:

通过在原图像沿行、列滑动我们定义好的窗口,并让窗口内图像与正负样本进行比较:

当窗口遍历过整幅图像后,获得原图像对应的掩膜,高亮度的区域都为疑似文本框的区域:(亮度反映了分类器的判断)

掩膜中的文本框可能是断断续续的,因此还考虑使用形态学膨胀操作(放大算子,expansion operator)来让文本框更加完整:(瘦高的文本框可以丢弃)

字符分割

在文本检测阶段,我们的滑动窗口是分别沿着行、列进行扫描的,因此是 2 维的扫描过程。而在字符分割过程中,同样将使用到滑动窗口技术,只是这次我们将窗口的高度设置为与文本框等高,只进行 1 维的行扫描

我们同样需要定义正负样本,来让窗口知道哪些是字符,哪些包含了字符的分界:

人工数据合成

人工数据合成(Artifical data synthesis),应用于特定问题时经常需要深入了解和创新改进。

  • 创造数据集
  • 以某种方式扩充数据集

字符识别阶段,为了更好的完成分类识别任务,我们就需要给系统提供尽可能多的训练图像,如果我们手头上拥有的图像不多,就需要人工合成更多的数据。例如,我们可以收集不同的字体,并为每种字体的每个字符加上随机背景,这样就可以人工扩展大量的字符图像:

另外,也可以通过扭曲字符形状来合成新数据,这也会帮助机器更好地处理发生过形态变化的图像:

加上合理的失真(distortion)可以帮助扩充数据集。
但是,为数据加上完全随机、无意义的噪声一般不会提升模型训练质量:(效果不明显)

在getting more data之前,你最好确保:

  • 有一个低偏差、高方差的分类器
  • Brainstorm!:为了得到10倍的数据量需要付出多少成本?
    • 一般10倍的数据量,算法的性能就能通过某种方式提高
    • 人工合成数据
    • 自行收集数据(需要多少时间?)
    • 众包(Crowd source),获得标记数据集

流水线/上限分析

Warning: 时间宝贵!

光学字符识别并不是一个单一的过程,而是由若干过程构成的流水线(pipeline)。我们知道,字符识别作为该流水线的出口, 其将是衡量光学字符识别准确率的依据。工程浩瀚,我们不可能在流水线的每一步都花费巨额的精力来作出改善,因此,我们需要一种手段来知道去改善哪一步是最值得的,
上限分析(Ceiling analysis)就是手段之一。

所谓上限分析,就是我们假定某个组件及其前面组件的精度都达到了 100%,即该组件完美地完成了任务,达到了上限,那么此时整个系统的精度能提升多少
例如,假定整个系统的精度是 72%,我们令文本检测的精度是 100%(比如人工利用 PS 来定位图片中的文本框),此时,整个系统的精度能提升到 89%。

即,如果我们付出足够多的精力来优化文本检测,那么理想情况下,能将系统的精度提升 17%。

重复该步骤:

组件 流水线精度 精度提升
整个系统 72%
文本检测 89% 17%
字符分割 90% 1%
字符识别 100% 10%

完成上限分析后,我们得到上面的表格,可以看出,最值得花费精力的步骤是文本检测,最不值得花费精力的是字符分割,即便我们完成了 100% 的分割,最多也就对系统提升 1%

:(Face recognition)

组件 流水线精度 精度提升
整个系统 85%
Prepocess(remove background) 85.1% 0.1%
Face recognition 91% 5.9%
Eyes segmentation 95% 4%
Nose segmentation 96% 1%
Mouthse gmentation 97% 1%
Logistic regression 100% 3%

事实上曾经有一个研究团队花了18个月在Prepocess(remove background)方面做性能提升。

Anyway, 不要过于trust自己的直觉。

Summary

Machine Learning


"Thank you, too!"

——Vel

0%