机器什么时候能够学习?

本系列是台湾大学资讯工程系林軒田(Hsuan-Tien Lin)教授开设的《机器学习基石课程的梳理。重在梳理,而非详细的笔记,因此可能会略去一些细节。

该课程共16讲,分为4个部分:

  1. 机器什么时候能够学习?(When Can Machines Learn?)
  2. 机器为什么能够学习?(Why Can Machines Learn?)
  3. 机器怎样学习?(How Can Machines Learn?)
  4. 机器怎样可以学得更好?(How Can Machines Learn Better?)

本文是第1部分,对应原课程中的1-3讲。虽然第4讲在原课程中也放入了第1部分,但我认为它与后面第2部分的连贯性更强,因此移到后面。

本部分的主要内容:

  • 介绍机器学习的概念与流程,并将它和其他几个相似的领域进行比较;
  • 介绍感知机模型,说明普通的感知机学习算法PLA在什么条件下可以停下,如果不满足条件该怎么办;
  • 列举机器学习的类别。

1 机器学习的概念

1.1 定义

机器学习的定义:improving some performance measure with experience computed from data

什么时候可以用机器学习?有几个关键的地方:

  • 确实存在一些需要学习的“潜在模式”,如预测下一次丢骰子的点数,就不能用机器学习;
  • 没有简单的可编程的定义,如判断一张图像中是否包含了圆,就可以直接通过编程解决,不需要使用机器学习;
  • 有一些关于要学习的模式的数据,如预测未来核能的滥用是否会导致地球毁灭,就不能用机器学习,因为没有历史数据。

1.2 组成部分

机器学习的实用定义如下图(灰字是以信用卡审批为例):

机器什么时候能够学习?插图

可以看到,机器学习有以下几个要素:

  • 未知的目标函数(f: mathcal Xrightarrowmathcal{Y}),在例中为理想的信用卡审批规则;
  • 训练样本(mathcal{D}),在例中为银行中信用卡审批的历史记录;
  • 假设集(mathcal{H}),在例中为一系列的候选规则;
  • 学习算法(mathcal{A})
  • 最终挑选出的假设(g),满足(gapprox f),在例中为最终“学习”出的规则。

机器学习的实用定义:使用数据计算出最接近于目标函数(f)假设(g)

1.3 和其他领域的关系

1.3.1 数据挖掘(DM)

数据挖掘:用(大)数据寻找感兴趣的性质。

  • 如果这里所说的“感兴趣的性质”就是“接近目标函数的假设”,那么机器学习就等同于数据挖掘;
  • 如果“感兴趣的性质”与“接近目标函数的假设”是相关的,那么数据挖掘可用来帮助机器学习,反之亦然;
  • 传统的数据挖掘还关注在大数据库中的有效计算。

在现实中,很难区分ML和DM。

1.3.2 人工智能(AI)

人工智能:计算一些的有智能行为的东西。

如果(gapprox f)就是那个有智能行为的东西,那么ML可用于实现AI。

如下棋,传统AI的做法是做博弈树,而ML的做法是从大量数据中进行学习。因此,机器学习是实现人工智能的一种途径。

1.3.3 统计学(Statistics)

统计学:使用数据对未知过程进行推断。

  • 如果推断的结果就是(g)(f)是未知的,那么统计学就可以就用来实现机器学习;
  • 传统的统计学聚焦于在数学假设下可证明的结果,而不太关注计算。

统计学为机器学习提供了很多有用的工具。

2 分类学习之感知机模型

2.1 PLA

这里介绍一个简单的分类模型:感知机(Perceptron)。

回顾上一节,在假设集(mathcal{H})中,我们可以使用哪些假设?

在分类问题中,要预测的变量是正/负,或表示成(+1)/(-1)。我们可以对自变量做线性加权求和,然后设定一个阈值,若高于阈值,则分类为正,若低于阈值,则分类为负。若将“阈值”也看作在自变量中补入的常数项((mathbb{w})中补入对应的常数1),则这个模型可以写作(h(x)=text{sign}(mathbf{w}^Tmathbf{x}))

每一个(mathbb{w}),都对应了一个假设。

那么,要如何从假设集(mathcal{H})中找出最接近于目标函数的(g)呢?也就是如何找出最好的(mathbb{w})

可以这样做,先任意设一个初始的(mathbf{w}_0)(比如(mathbf{0})),然后:

  1. 从该点开始,寻找错误分类的样本点,即找到满足(text{sign}(mathbf{w}^T_t mathbf{x}_{n(t)})ne y_{n(t)})的点((mathbf{x}_{n(t)}, y_{n(t)}))
  2. 利用找到的错误分类点对(mathbf{w})进行更新,更新规则是:(mathbf{w}_{t+1}leftarrowmathbf{w}_t +y_{n(t)}mathbf{x}_{n(t)})
  3. 不断重复上述过程,直到找不出错误分类的点为止,最终得到要找的(mathbf{w}_{PLA}),把它作为(g)

这就是感知机学习算法PLA(Perceptron Learning Algorithm)。更新规则的图示如下:

机器什么时候能够学习?插图(1)

但是,以上算法仍然有不少问题:

  • 该如何遍历所有的样本点?
  • 它最终会停下来吗?需要满足什么条件?
  • 停下来说明在样本(mathcal{D})内已经没有错误了,(gapprox f),那么在样本(mathcal{D})外有用吗?
  • 如果不满足使它能停下的条件怎么办?

2.2 PLA会停下吗?

PLA能停下来的必要条件是,存在一些(mathbf{w})可以在(mathcal{D})内不会犯错。这叫线性可分(linear separable)条件。那么,线性可分是PLA能停下来的充分条件吗?

答案是肯定的。证明的思路是,既然数据集线性可分,则一定存在某个(mathbf{w})将样本完美分开,记为(mathbf{w}_f),只需证明在经过有限次的迭代后的(mathbf{w})(mathbf{w}_f)的夹角的余弦的下限会超过1即可(因为余弦无法超过1,如果在经过特定次数的迭代后余弦的下限超过了1,说明在上一次迭代之后必定已经完成了完美的分类,无法找出错误分类的点进行迭代了),而余弦可以从分子(两个向量的内积)和分母(两个向量模的乘积)分别突破。具体证明如下:

因为(mathbf{w}_f)能完美分开数据集中的样本,即满足

[y_{n(t)}mathbf{w}_f^T mathbf{x}_{n(t)}ge min_n y_n mathbf{w}_f^T mathbf{x}_n gt 0
]

可令(min_limits{n} y_n dfrac{mathbf{w}_f^T}{Vert mathbf{w}_fVert} mathbf{x}_n=rho),则有

[begin{aligned}
mathbf{w}_f^Tmathbf{w}_t &= mathbf{w}_f^T(mathbf{w}_{t-1}+y_{n(t-1)}mathbf{x}_{n(t-1)})
&ge mathbf{w}_f^Tmathbf{w}_{t-1}+rhoVertmathbf{w}_fVert
&ge trhoVertmathbf{w}_fVert
end{aligned}]

而更新一定是在犯错的点处,所以触发第t次更新的样本一定满足(y_{n(t-1)}mathbf{w}^T_{t-1} mathbf{x}_{n(t-1)}le 0)。令(R^2=max_limits{n} Vert x_nVert^2)(R>0)),则有

[begin{aligned}
Vertmathbf{w}_tVert^2 &= Vertmathbf{w}_{t-1}+y_{n(t-1)}mathbf{x}_{n(t-1)}Vert^2
&= Vertmathbf{w}_{t-1}Vert^2+2y_{n(t-1)}mathbf{w}^T_{t-1} mathbf{x}_{n(t-1)}+Vertmathbf{x}_{n(t-1)}Vert^2
&le Vertmathbf{w}_{t-1}Vert^2+Vertmathbf{x}_{n(t-1)}Vert^2
&le Vertmathbf{w}_{t-1}Vert^2 + R^2
&le t R^2
end{aligned}]

接下来就看一看在经过(T)次迭代后得到的(mathbf{w}_{T}),它和(mathbf{w}_f)的夹角的余弦:

[begin{aligned}
&dfrac{mathbf{w}_f^Tmathbf{w}_{T}}{Vertmathbf{w}_fVertVertmathbf{w}_{T}Vert} ge dfrac{TrhoVertmathbf{w}_fVert}{Vertmathbf{w}_fVert sqrt{T R^2}}=sqrt{T}dfrac{rho}{R}
end{aligned}]

而余弦必定小于1,因此必有迭代次数(Tle dfrac{R^2}{rho^2})证明完毕

从直觉上理解,PLA算法通过不断迭代,可以使得(mathbf{w})越来越接近于(mathbf{w}_f)

PLA算法的优点是简单、快、对任意维度的数据都可用,但缺点在于,一方面我们假设了数据集(mathcal{D})是线性可分的,而现实中我们不知道是否真的如此,另一方面我们不知道它到底多久会停下,尽管在实践中算法往往很快停下。

2.3 Pocket算法

如果数据中有噪声,导致数据集不是线性可分的,怎么办?

机器什么时候能够学习?插图(2)

当然,可以直接取(mathop{argmin}limits_{w}sumlimits_{n=1}^{N}{mathbf{1}_{[y_nne text{sign}(mathbf{w}^Tmathbf{x}_n)]}})作为(mathbf{w}_g),但由于要一一遍历所有样本,这是个NP-hard问题。

那怎么办呢?可以对PLA做一些修改:

  • 把当下找到的最佳(hat{mathbf{w}})先存起来,就好比放在口袋里;
  • 在找到一个使(mathbf{w}_t)分类错误的样本之后,进行和PLA一样的更新,即(mathbf{w}_{t+1}leftarrowmathbf{w}_t +y_{n(t)}mathbf{x}_{n(t)})
  • 比较(mathbf{w}_{t+1})(hat{mathbf{w}})在整个数据集上谁犯的错误较少,若前者少,则将前者放入口袋,反之仍保留(hat{mathbf{w}})在口袋中;
  • 不断循环,在经过一定次数的迭代后,停止上述过程,最终在口袋中的(hat{mathbf{w}})就取为(g)

由于始终有一个(hat{mathbf{w}})在口袋中,因此这种算法被称为Pocket算法。

3. 学习的分类

依据输出空间(mathcal{Y})的不同来分:

  • 二分类问题:(mathcal{Y})(+1)(-1)
  • 多分类问题:(mathcal{Y})有更多的类别;
  • 回归:(mathcal{Y}=mathbb{R})(mathcal{Y}=[text{lower}, text{upper}]subsetmathbb{R})
  • 结构学习(Structured Learning):(mathcal{Y})是某种结构,如学习出句子的结构等。

依据数据标签(y_n)的不同来分:

  • 监督(Supervised)学习:每个(mathbf{x}_n)都有对应的(y_n)
  • 无监督(Unsupervised)学习,没有标签(y_n),如聚类、密度估计、离群点检测等;
  • 半监督(Semi-supervised)学习:只有一小部分数据有标签,需要充分利用无标签数据,避免代价昂贵的手动打标签;
  • 强化学习(Reinforcement Learning):(y_n)被隐含在goodness((tilde{y}_n))中。

依据(fRightarrow (mathbf{x}_n, y_n))的不同来分:

  • Batch:所有的数据都是已知的;
  • Online:被动获取的序列数据;
  • Active Learning:通过策略不断主动询问某个(mathbf{x}_n)(y_n)是什么,来获得序列数据。

依据输入空间(mathcal{X})的不同来分:

  • 具体的(Concrete)特征:(mathcal{X}subseteq mathbb{R}^d)的每个维度都有复杂的物理意义。
  • 原始的(Raw)特征:只有简单的物理意义,如手写数字识别,特征是每个像素点的灰度,往往需要人或机器将它转换为具体的特征。
  • 抽象的特征:没有或几乎没有物理意义,如打分预测系统,(mathcal{X})是用户id,(mathcal{Y})是对某部电影的评分,也需要做特征转换/抽取/构造。
本站资源均源自网络,若涉及您的版权、知识产权或其他利益,请附上版权证明邮件告知。收到您的邮件后,我们将在72小时内删除。
若下载资源地址错误或链接跳转错误请联系站长。站长q:770044133。

» 机器什么时候能够学习?

发表评论

免登录下载网,提供全网最优质的资源集合!