Learning From Data Lecture 1 笔记 学习问题

学习问题 Learning Problem

内容:

  1. 机器学习举例
  2. 学习的组成
  3. 一个简单的模型:感知器
  4. 学习的类型
  5. 一个学习谜题

1 机器学习举例:

Netflix希望能够提高他们的推荐系统预测10%的准确度,为此愿意支付1百万给首先能够达成这个目标的人。

预测观众对电影的评分是一个典型的机器学习例子,其中体现出了机器学习的本质,即:

  1. 存在一个模式(A pattern exists)
  2. 该模式无法用数学的方法确定(We cannot pin it down mathematically)
  3. 拥有对该问题的数据(We have data on it)

首先,观众对电影的评价的背后存在一个模式,即:一个人如何评价一部电影与他如何评价其他电影之间存在关联性。如果不存在这样一个模式,所有用户对于电影的评价都是随机的,那么便没有可以追寻的东西。

其次,这个模式是无法单纯地用数学方法来确定的,我们无法手动为每一个用户写出一个高次方的多项式来捕捉他们是如何评价电影的,这是我们选择机器学习的主要原因。

最后,我们需要依靠数据来帮助确定这个模式,如果没有数据,那么一切都是空谈。

下面是一个预测电影评分的解决方案:

用向量来表示观众,每个维度都代表一个因素,如:

viewer as a vector

其中第一个因素为喜剧,第二个因素为动作,第三个因素是大片,可能的因素还有是否小众,或是主演是否是某个演员,如最后的汤姆·克鲁斯。对于一个观众而言,其中的值代表他是否喜欢喜剧,是否喜欢动作片,是否喜欢大片,等等。

对于电影,也用一个向量表示:

movie as a vector

其中的值代表该电影是否有喜剧内容,是否有动作内容,是否由汤姆·克鲁斯主演,等等。

如果我们将两个向量进行匹配比较,便可根据比较的结果预测观众是否可能会喜欢这部电影。

match vectors and predict

可惜的是,这样的解决方案并不是机器学习。为了进行这样的预测,需要观看一部电影并且分析该电影的内容,还需要对观众进行调查,确定观众的喜好,最后才能预测评分。

机器学习的思想是,你不需要做这些事,而是让机器自动生成这些向量。

下面是一个机器学习的解决方案:

机器学习的方法是对上述解决方案的一个逆向工程,从一个评分出发,试图找出哪些因素与该评分是一致的。

首先将所有电影和所有观众向量随机初始化,然后针对一个真实的评分,微调这些向量中的因素,使得两个向量的内积能向这个评分靠近。

如果一遍一遍地对上千万个评分进行这样的过程,便能使得这些因素对于评分有意义。这时,如果选择一个观众和一部他从未看过的电影,对经上面过程得出的两个向量求内积,得出的结果与观众对该电影的实际评分是一致的。

这是一个现实可行的解决方案,也是Netflix获奖方案采用的方法。

2 学习的组成

下面,以信贷审批为隐喻,分析学习问题的组成:

用户申请信用卡,银行需要决定是否批准。对于银行而言,赚钱是唯一标准。

与电影评分问题类似,银行没有一个用于判断是否批准申请的神奇公式。

银行需根据过往的用户记录,对用户的信息以及他们之后的信用表现进行反向工程,将获得的系统用于对新用户的信贷审批。

这个问题中的第一个组成是申请者的信息,年龄、性别、收入等各种与信用表现有关的因素,其中任一个因素都不唯一地决定一个人的信用表现。

银行要用这样的模式进行信用审批,给定输入为申请信息,需要判断是否批准申请。

将这个问题进行形式化:

  • 输入:X
    为申请信息,D维向量
  • 输出:y
    是否批准申请,+1为批准,-1为拒绝
  • 目标函数: f: χ → y
    定义域χ为D维向量的集合,值域y是一个包含+1和-1的集合
    该目标函数是理想中的信用审批公式,是我们未知的
  • 数据:(X1,y1),(X2,y2), ... ,(XN,yN
    为过往申请的记录,Xi为申请者的信息,yi为申请者的最终表现
    其后的思想在于,认为大量的历史记录能够捕获目标函数的本质
  • 假说:g:  χ → y
    是我们获得的公式,是对目标函数的近似,f未知,g是对f的近似
    使得g尽可能好地近似f是学习的目标

将这些组成放入一张图表中来帮助理解:

diagram01

我们无法直接看到目标函数,我们只能通过训练集间接地看到它,我们希望能最终获得一个近似f的假说g。

将训练集和最终假说连接起来的是学习算法A,学习算法接受训练集,产生最终假说:

diagram02

学习算法从一个预设的假说集合(候选公式集合)H中选取一个假说h,作为最后的g:

diagram03

需要有这样的一个假说集合H来限制算法的原因是:引入假说集合不仅没有坏处,还有好处。

  • 从实践角度来说,不论采用神经网络还是支持向量机,实际上都是选择了一个特定的假说集合。
  • 如果不用假说集合对学习算法进行限制,也可以理解成采用了一个由全部可能假说所构成的集合。
  • 假说集合在学习理论中扮演了支点作用,告诉我们是否能学习,能学习多少。

对于假说集合H={h},显然有g∈H。

目标函数,训练集是给定的,最终假说是要求的,学习算法和假说集合是我们可以选择的。

学习算法和假说集合合起来称为学习模型,选择一个学习模型意味着同时选择了一个假说集合(例如神经网络)和一个学习算法(例如反向传播)。

3 一个简单的模型:感知器

输入: X = (x1,...xd) d维向量,表示一个客户的各种属性,如年龄,收入等

假说集合:感知器模型

感知器模型的原理:给每个属性一个权重wi,对属性值和权重的乘积进行求和(可以将这个和看作是“信用分数”),将这个分数和一个阀值进行比较,用于信贷审批。

perceptron

感知器模型中的wi和阀值都是未知的,但是限定了假说公式的形式。

具体假说h可以写成如下形式:

perceptron hyposis

 

输出结果+1代表同意,-1代表拒绝。

确定一个具体的感知器假说h所需确定的参数为wi和阀值,不同的假说h之间通过不同的参数值加以区分。

输入数据和结果变量都是数据集所给定的,我们要做的便是通过学习算法来确定所需的参数wi和阀值。

假设数据集是线性可分割的,如下图的中共有9个数据,+代表批准的申请者,-代表拒绝的申请者。

linear separable data

任一种wi和阀值的组合对应于图中洋红色线的位置和浅蓝色的区域边的一种可能情况。

用感知器模型来正确地分割这些申请者,希望感知器能够是图中右边情况。

假设这种简单的线性模式是存在的并且被找到了,那么对于新的申请者,可以根据其落在线的哪一边来判断是否批准申请。

我们随机地对所有的权重以及阀值进行初始化,可能得到任何直线以及蓝色区域,如上图中左边情况。

学习算法所做的便是不断地调整wi和阀值,从图中左边的情况逐渐地转为图中右边的情况。

对模型公式简化:

如果将阀值改写为权重w0,令w0为阀值乘以负1。

threshold to weight

引入一个人工的常数x0=1,则可以将公式简化为:

simplified peceptron fomula

写成向量形式为:

vector form peceptron fomula

 

看完了假说集合后,来看看与之相对应的学习算法。

假说集合为学习算法提供了可选假说的来源,学习算法将根据训练集数据,在假说集合中寻找一个最适合的假说作为输出。

感知器学习算法的工作是根据训练数据(X1,y1),(X2,y2), ... ,(XN,yN),尝试找出最合适的W。

对于任何一个错误分类的点,即学习算法将当前的W应用于某一个数Xn,yn时,如发现:

misclassified

 

学习算法需更新权重向量W,改变假说h使之更加适合这个特定的点。更新公式为:

weight update fomula

注意到权重向量W和训练数据向量X之间的内积,在两个向量之间的夹角在0~90度之间时,为正值;夹角在90~180度之间时,为负值。

更新公式中,更行W为旧的W加上yn与Xn的积。因为yn的取值只能是+1或-1,所以更新公式要么是加上向量Xn,要么是减去该向量。

由下图可知,这么做将使得更新后的假说公式能将之前错误分类的点正确分类。

W X inner product sign

当y=+1时,如果假说将该点错误分类,则W必然与X之间的夹角大于90度,W+yX等于W+X,而W+X与X之间的夹角小于90度,内积必然为正。对y=-1时,也有类似的结果。

以学习算法的一次迭代为例:

iteration

图中被圈起来的数据点为错误分类的点,经过该次迭代,对权重W进行更新,图中洋红色的线将沿着箭头所示的方向移动,将错误分类的点纳入浅蓝色的范围内。

问题在于,随着权重的更新,可能会导致之前正确分类的点被更新后的感知器错误分类。

解决方法在于:多次迭代。每一次迭代都选择一个错误分类的点,对这个点运用学习算法。如果数据确实是线性可分割的,那么多次迭代后必然会得到正确的结果,即一个能够正确分类所有点的假说。(可证明)

感知器是最简单的学习模型,其中假说集合是一个线性模型,学习算法是迭代地根据错误分类的点更新权重。

思考:训练感知器过程是与历史记录匹配的过程,在得出假说g后,是否意味着该假说可以应用于新的数据上?如果不能,则一切都是枉然。

4 学习的类型

任何学习问题都有一个共同的基础前提即:

使用一系列的观察来揭示一个潜在的过程(using a set of observations to uncover an underlying process)

这个前提非常宽泛的,对不同的领域内的不同问题都适用。对于统计学而言,这个潜在的过程可能是一个概率分布,观察是由该概率分布生成的样本。

在机器学习中,这个潜在的过程便是目标函数。

学习的类型:

  1. 监督学习
  2. 非监督学习
  3. 强化学习

监督学习:给定的数据集中包含了输入数据和正确的结果变量(如:同时包含用户信息和用户的信用表现)。

”监督“可以理解为:有结果变量的帮助。

以自动售货机硬币识别为例:

为了区分不同硬币,对硬币的物理属性进行度量,为了简化问题,只考虑硬币的尺寸和质量。

有4种不同硬币,10分,1分,5分和25分,训练数据如下图所示:

coin reconition

因为误差,4种不同硬币呈现分散分布的状态,不同的硬币用不同的颜色表示。

这是个监督学习问题,因为对于任意一个硬币,其面值是已知的。

使用这个训练集,如果我们采用线性模型,可能会得到如图所示的分割线:

coin separater

得到这些分割线后,可根据这些分割线对新的硬币进行分类。

非监督学习:给定的数据集中只包含输入数据(如只用户信息),不包含结果变量。

同样以硬币识别为例,如果结果变量未知,即不知道每一个硬币面值是多少,训练数据如图所示:

coin unsup

虽然我们不知道到底有几种硬币,以及每种硬币分别是多少面值的,但是能够对上面的数据进行聚类:

coin unsup sep

可以看出未标记的数据(只有输入数据,没有结果变量)也是可以利用的。

得出了上面的聚类结果,只要去观察每个类分别是什么硬币,便可以了。

另一个非监督学习的例子:如果你知道一个月后将被派去葡萄牙学习葡萄牙语,在去葡萄牙之前,你不断地听葡萄牙语电台,你的脑中开始逐渐形成一个葡萄牙语的模型,到葡萄牙正式地学习葡萄牙语时,将发现这个听电台的过程是有益的。

可以将非监督学习理解成:获得对输入数据的更高层次表示的过程。

例如:忽略具体的物理属性,聚焦于四种不同的聚类。

强化学习:给定的数据集中包含输入数据,部分结果变量,并且提供对于结果变量的评分。

强化学习的有趣之处在于,它与我们人类自己的学习经历类似。

例如:一个小孩面前有一杯热咖啡。每次小孩伸手去触摸咖啡杯,会感觉到温度,如果温度较高,小孩被烫到并收手,久而久之,小孩学会如何判断一杯咖啡是否已经不烫了,并且在咖啡还烫着的时候不再伸手去触碰。

强化学习的重要应用之一是博弈,例如:让机器不断地对某种情况下走某一步棋的后果进行学习,从而学会如何下棋。

机器学习是懒人的生活之道。对于一个问题,懒人不需要研究数学,不需要写代码和调试代码,而是坐下喝着茶,让学习算法产生结果。

当然,这一切的前提是:学习是可行的。

5 一个学习谜题

下面是一个监督学习的谜题,给定输入数据和结果变量,求一个特定新输入的结果。

puzzle

不同的人可能会得出不同的假说,因此+1或-1都有可能。

不同的假说可能在这6个点上的结果是一样的,但是对其他未知点,可能会得出不同的结果。

这是否意味着学习是在劫难逃的?且听下回分解。

课程地址:

http://work.caltech.edu/telecourse.html

Leave a Reply

Your email address will not be published. Required fields are marked *