Learning From Data Lecture 2 笔记 学习可行么?

Lecture 2 Is Learning Feasible?

学习可行么?

内容

  1. 概率上的救赎
  2. 与学习的联系
  3. 与真正学习的联系
  4. 困境和解决方案

Lecture1回顾:

1应用机器学习的三个前提:

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

在很多领域中,直觉来看第一条都是满足的。

第二条是选择机器学习的原因。

第三条是我们有表达了这个模式的数据。

实际上有两个前提是可以缺失的,一个是必须的。

首先,如果不存在模式,仍然可以尝试去学习,唯一的结果就是失败。介绍完机器学习理论后会知道,模式是否存在,是可以用机器学习的技术来判断的,我们可以衡量是否学会了。因此,即使模式不存在,尝试机器学习也不会有什么坏处。

其次,如果我们能够用数学的方法确定这个模式,这时,相对于完美解决该问题的程序而言,机器学习可能不是最佳的解决方案,但是机器学习任然是可行的方案。

最后,数据是唯一不可缺少的。机器学习是从数据中学习,没有数据就什么也做不了。

2监督学习:

目标函数式未知的,这是一个普遍性地假设。监督学习的训练集中包含输入数据和结果变量,因此尽管目标函数是未知的,但是至少它在给定的数据集内是已知的。

学习模型,包括学习算法和假说集合,学习算法从假说集合中选取最适合的假说g作为最终输出。

3感知器案例

4问题:是否真能学习?

我们是否真能学习一个未知的函数?答案似乎是否定的。 原因在于,数据集是有限的,我们不知道对数据集之外的数据而言这个未知函数应该是怎样的。对于数据集以外的数据而言,这个未知函数可以有任意输出结果。 看上去我们要对此做些什么,这便是本节的内容:学习是否可行。

2.1概率上的救赎

以一个实验作为学习问题的隐喻。假设如下情况:有一个容器,其中有红色或绿色的弹珠:

bin01

  • 从容器中取出一个红色弹珠的概率为μ(取出后放回)
  • 从容器中取出一个绿色弹珠的概率为1-μ(取出后放回)

pick marble from bin

可以认为这是一个只有两种结果的实验,容器和弹珠只是对这个抽象实验的可视化。

μ是未知的(隐喻目标函数)。

从容器中取N个弹珠作为样本(隐喻训练集数据),每次取弹珠都是相互独立的,观察样本中红色弹珠的占样本中弹珠总数的比例ν(隐喻假说)。

bin1

  • ν是样本中出现红弹珠的频率,是已知的
  • μ是容器中红色弹珠的频率,是未知的,是我们希望求解的

思考ν与μ的关系,ν是否能帮助我们知道μ?

  • 严格意义上,不能。样本中可以绿色的珠子多,而容器中实际上是红色的珠子多。因此ν不可以告诉我们μ。
  • 然而,如果样本越大,ν就越可能会接近μ。

两个答案之间的区别在于,可以(possible)和可能(probable)。

在一个大的样本中(N越大),ν越可能接近μ,两者间误差在ε以内。

假设ε是可以容忍的最大误差,希望ν与μ之间的误差不在ε以内的概率尽可能小。

for

这个概率不等式称为hoeffding不等式。它告诉我们

  • 好消息:对ε的需求不变时,增加样本的数量N,该概率减小的很快。
  • 坏消息:如果ε尽可能小,如10^-6,则该概率小于等于2e^-(2*10^-12*N),几乎不可能有足够大的N使得这个概率足够小。

hoeffding不等式是VC理论的基础,以后会介绍。

hoeffding不等式告诉我们,“μ=ν”是近似可能正确的。P.A.C(Probably Approximately Correct)

  • 可能的原因是e的指数可以很小,因此概率的上限可以很小
  • 近似的原因是ε始终不可能为0

对于hoeffding不等式,有几点认识:

  1. 不等式对于任何正整数N和任意正数ε均成立,该不等式属于大数定律家族中的一员
  2. 概率的实际取值是与μ,ν和ε有关的,但是这个概率的上限只与ε和N有关,μ的值不影响这个上限
    即,对于这个概率的真实值,虽然里面包含未知数μ我们无法求解,但是根据不等式可以确定其上限是多少
  3. 我们需要在N和ε之间做出权衡
  4. ν≈ μ => μ≈ν
    在进行实验时,常数μ是未知的,ν是唯一的随机量。不等式是尝试用ν来推出μ。
    然而实际上,是μ的值影响ν的值,即如果给定μ的值,我们可以推出ν的可能取值。
    然而这个不等式是对称的(绝对值)。
    因此,原本合乎逻辑的结论是μ是不变的常数,ν倾向于接近μ;我们现在可以说ν是已知的,μ倾向于接近ν。

2.2 与学习的联系

将这个实验与学习问题关联起来。

  • 在实验中,要求的未知数是μ。
  • 在学习问题中,要求的是未知函数  f: χ → y。

将容器想想成学习问题中的输入空间(input space)χ,每一个弹珠相当于输入数据中的一个x∈χ:

bin-g

比较目标函数和我们的假说,现在给弹珠“上色”:

  • 假设绿色的弹珠代表假说h(x)=f(x)的情况。
  • 假设红色的弹珠代表假说h(x)≠f(x)的情况。

color marble

这将给我们的学习问题增加一个之前没有包含的重要组成部分。

我们所看到的容器也是根据一个概率分布所产生的,在原先的学习问题陈述中,不存在这样一个概率。

原先的学习图表:

diagram03

现在对输入空间X引入一个概率分布,让输入空间内是依据分布P生成的。

显然这个概率P会影响我们获得怎样的假说h,但我们可以不去追究这个概率P是什么,因为由hoeffding不等式知,我们获得的假说h与目标函数f的误差上限是与这个概率P无关的。

prob in digram

2.3 与真正学习的联系

上面进行了在选出一个h后,该h在多大程度上能够用于近似f的讨论。

我们讨论的只是一种验证,而非真正意义上的学习。

学习需要能从假说集合中寻找最合适的h作为g输出。

因此,引入多个容器(M个)。

对于一个特定的容器,从容器内取出一个红色弹珠的概率μ,从对应样本中取出一个红色弹珠的概率为ν。

每个容器就对应于一个假说h。

取出红色的弹珠就相当于h(x)!=f(x)

取出绿色的弹珠就相当于h(x)=f(x)

即μ和ν均依赖于h。

为了能够学习,我们需要从多个容器中进行选择。

multiple bins

完美的情况(即h≈f)是所有的弹珠都是绿色的。v为样本内出现红色弹珠的概率,便是样本内误差。μ是容器内红色弹珠出现的概率,便是样本外误差。显然v和μ都是越接近0越好。

因为μ和ν均依赖于h,将两者表达成h的表达式。我们称:

  • ν为样本内(in sample)误差,用Ein(h)表示
  • μ为样本外(out of sample)误差,用Eout(h)表示

ein out

将hoeffding不等式改写为:

adj hoffeding

可以理解为,假说h在样本内和样本外表现的差距超过容忍值的概率小于一个值。

2.4 困境和解决方案

然而,此时我们陷入一个困境:hoeffding不等式对于多个容器并不适用。

用抛硬币做一个隐喻。如果我们反复扔一个公正的硬币10次,我们获得10次正面的概率大约是0.1%。如果进行1000次这样的实验,其中至少有一次试验中出现10次正面的概率是63%。

如果我们只进行了一次实验,获得了10次正面朝上的结果。这一次实验的结果,显然不能推广为所有扔10次硬币的结果。仅对一个样本进行分析得出的结论是无法推广到总体的。

将这个抛硬币的实验与之前的进行一个比较:

QQ截图20131012152909

每一个扔10次硬币的实验分别对应与一个包含一半绿色和一半红色弹珠的容器中取出10个弹珠的实验。

hoeffding不等式对于其中每一次实验都是成立的,但是对于多次实验的总体是不适用的。

硬币出现正面的概率为ν,而扔硬币本身的概率为μ。

我们寻找的完美情况是所有的弹珠都是绿色的,就相当于扔10次硬币全部都是正面朝上。但这并不能推广为扔硬币出现正面朝上的概率。

我们需要一个能够处理多个容器的方法。

从由多个分布所生成的样本中获得的多个假说h中,根据一定的标准,我们选取一个作为最终假说g输出。

因为现在是一个多容器的情况,hoeffding不等式不成立,我们需要为不等式找到一个上限

QQ截图20131012154030

注意,在上节中,我们知道假说g的来源是假说集合H,而假说集合H中的假说是有限个。

假设假说集合中的假说分别为h1,h2,...hm,则上面不等式的上限为假说集合H中至少有一个h在样本内核样本外的表现差大于这个容忍值的概率:

QQ截图20131012155645

假设对于每一个h,这个概率都是独立的(最糟糕的情况),则有:

QQ截图20131012155438

这个求和公式中的每一项,分别对应一个实验,hoeffding不等式是成立的,因此用hoeffding不等式的上限来替换每一项,得到:

QQ截图20131012155941

 即:

QQ截图20131012160020

这时不等式中引入了M,在ε个N不变的情况下,如果我们的假说空间H中只有10个假说h,那么不等式的上限可能还足够小;问题在于假说空间中假说的数量可能会非常大。

这告诉我们,采用越是复杂的模型(假说空间中的假说数量越大),样本内误差和样本内误差之间的差距便可能越大;即:假说可能能非常完美地适应样本内的数据,但是却无法很好地推广到样本外。

hoeffding不等式见: http://en.wikipedia.org/wiki/Hoeffding_inequality

P.A.C见 http://en.wikipedia.org/wiki/Probably_approximately_correct_learning

VC理论见: http://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_theory

大数定律见:http://en.wikipedia.org/wiki/Law_of_large_numbers

课程地址:

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

Leave a Reply

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