[Learning-from-data]有限假设空间的可学性论述

作者: 七八音 | 来源:发表于2018-12-12 21:03 被阅读7次

明白机器学习中的通用理论,然后在细化到数学推导,之后再明白局限性以及改进;辅助以代码.
笔记.防止看得太过于枯燥.
主要论述有限假设空间上的可学性问题.

-What is learning?

-Can a machine learn?

-How to do it?

-How to do it well?

-Take-home lessons.

"学习"

我们人类的学习过程,有时候并不是直接从定义学习,更像是实例学习,比如说小孩学习"树",并不能给出一个真正的定义,而是从实例的树来学习这个定义,也就是说"learning from data".

Learning from data: 因为不能给出一个明确的解析解,但是可以从大量的数据中构建一个经验解决方法.换句话说,就是我们不能给出明确的定义,但是可以从大量的数据中归纳出一种解决方法. 一种归纳推理:从特殊到一般. learning from data.

Learning from data is used in situations where we don't have an analytic solution, but we do have data that we can use to construct an empirical solution.

什么是学习?给出与"学习"相关的各种概念,目前为止出现的各种学习方法.

学习问题

这种学习方法learning from data 是 machine 尝试以自己的角度从数据中学习,机器"自己"理解的角度/方法,当然这种方法对人类而言,可能是"天书",but it works, it's enough! 不需要人类理解.

学习的"成分"

数据记录x
记录标签y
数据集X
标签Y
目标函数f: 理想函数
学习函数g: 学习到的函数
假设空间H
理想情况下 g = f, 我们学到的g函数和理想函数f完全相同; 一般情况下,就是用训练学习到的函数g去逼近ideal target function理想函数f.

函数g的选择依据是:在训练数据集上g已经非常逼近期望函数f了,而且我们也希望在unseen data/新数据上也能逼近函数f,也就是说在新数据上也能"完美运行/不出错[判断出错]",没有误差. 但这个期望能否实现需要继续判断.

[图片上传失败...(image-e4a838-1544619781471)]

图中定义了"学习"过程中的各个"成分".

There is a target to be learned, but it's unknown to us. We have a set of examples generated by the target. The learning algorithm uses these examples to look for a hypothesis that approximates the target.

一个简单的学习模型

对于一个实际的学习问题来说, 期望的目标函数f和数据集X能通过待求解的问题得到,是已知的[尽管目标函数并不是真正的已知],但是学习算法以及函数假设/假设函数是未知的,但是存在很多种选择需要我们自己选定. 假设函数集/函数空间和学习算法可以理解为"算法模型".

对于垃圾邮件分类器,如果数据集线性可分,那么我们能找到一个完美的模型:正确划分所有训练数据. 对于2-d维度来说,感知机模型的分类边界是一条直线.

假设空间H:

$H = {h|Y=h_{\theta}(X), \theta \in R^n}$

假设空间由 $\theta$ 参数定义的一个函数族[实现确定了选定那种类型的算法].

感知机模型:

$h(x) = sign(w^Tx)$

分类结果是{+1, -1}.从式子中可以看出,分类结果是由两个向量内积决定,图像化来说就是两个向量的夹角决定,如果夹角大于90度,分为负类;夹角小于90度,分为正类.

PLA(perceptron learning algorithm):基于数据对感知机模型参数w进行学习.具体来说:
假设数据集线性可分,那么一定能找到一个超平面[参数向量w决定]将所有训练数据集中记录正确划分,也就是说,对于训练集中所有数据有h(xn)=yn.

PLA是一个简单的迭代算法:最终的分类效果是对训练数据集"完美划分".既然是一个迭代过程,刚开始划分效果并不好,需要进行优化,但是如何优化呢?或者说优化方法是什么?PLA给出了具体的方法.

在每次迭代t,t=0,1,...,当前迭代的权重向量为w(t). 训练集 $(x_1,y_1),(x_2,y_2),...,(x_N,y_N)$ .
在训练集D中找一个误分样本点(x(t), y(t)),使用这个误分样本点对当前的权重向量w(t)进行更新.既然是误分,可以知道 $y(t) \neq sign(w^T(t)x(t))$ . 更新规则:
$w(t+1) = w(t) + y(t)x(t)$ .

因为是误分样本,所以有上面的不等关系,在具体来说,就是正类样本分成负类,负类分成正类;

对于第一种情况来说,y(t)=1,但是感知机h(x)分成负类,因此 $w^Tx$ 两个向量内积应该是负的,本来夹角应该是小于90度的,但由于当前权重向量不准确,导致夹角大于90度了,对于这种情况需要两个向量之间的夹角变到90度里,所以让 $w(t+1) = w(t) + x(t)$ ,两个起点相同的钝角向量相加,结果[w(t+1)]和原来的向量x(t)之间的夹角变到90度里,因此更新后的超平面能对这个样本点正确分类了;

对于情况二,y(t)=-1,但是h(x)分成正类,从图象上来说,本来两个钝角向量,变成了锐角向量,我们需要做的就是让锐角变到钝角去,从上面的例子中得到启发,两个起点相同的锐角向量[相减],$w(t+1) = w(t) - x(t)结果为更新后的权重向量w(t+1),此时两个向量的夹角成了钝角,也就是说超平面能对这个样本点(x(t),y(t))正确分类了.

两种情况合二为一,更新规则变成:

$w(t+1) = w(t) + y(t)x(t)$ .

符合两种误分情况的更新方法.同时从上面的更新方法来看,每次更新只选择一个误分样本点.但最终一定会得到一个"完美"的模型.并且这个结果和我们如何初始化w,如何选择误分样本无关.因为一定有一个"最优解".

这种学习算法在无限的解空间里通过有限步的迭代最终找到了最优解,求解过程并不是无限次的使用每种可能进行尝试,而是有目的性的优化.找准优化方向是根本,只有方向正确,最终一定能找到.

BUT,关于这个学习模型还存在一定的疑问?

数据集D上学到的模型g对于unseen data是否适用?[学习理论的关键问题--模型的泛化评估]
如果数据集D上的样本点不是线性可分呢?应该怎么办?

为什么一定能算法收敛?一定能找到一个最优解,证明PLA算法的更新规则是正确的.

http://www.cnblogs.com/HappyAngel/p/3456762.html#top

如果数据线性不可分怎么办?能否通过PLA变形,完成问题求解.

http://www.cnblogs.com/HappyAngel/p/3456762.html#top

Learning VS. Design

Learning是基于数据进行学习的, design更像是专门设计的,由专家定义设计,有大量的专业知识[先验知识].design方法并不需要数据,不需要从数据中获取信息.

"学习"的可行性

How could a limited data set reveal enough information to pin down the entire target function?
有限的训练数据集为什么能从中学到整个数据集上的通用信息???或者说为什么有限集上学到的模型能在未知数据上应用?难道不会出错吗?

[图片上传失败...(image-5f31b1-1544619781471)]

从上面的例子可以看出,对于6个样本的数据集来说,学到的模型并不一致,但是在数据集里,模型能完美运行,数据集之外unseen data上,不同的模型有不同的预测结果.但是我们并不能判断到底哪个结果是正确的[缺少额外信息]? 这个例子从一定程度上表明了判断"学习可行性"的难度.

Outside the Data Set

当我们在训练数据集D上进行训练时,表现良好,但在数据集之外unseen data上一无所知,这并不是学习,这属于单纯的记忆.我们关心的是模型在数据集之外的unseen data上的表现如何?

Does the data set D tell us anything Outside of D that we didn't know before? If the answer is YES, then we have learned something. If the answer is NO, we can conclude that learning is not feasible.
训练数据集D,能够揭示数据集D之外的我们不知道的整个数据空间X上的信息?如果可以,那么机器学习就可行,能在有限集D上学到的知识是全局的,具有普世性[迁移性];如果不能揭示全局信息,机器学习就没有意义.

The performance outside D is all that matters in learning.

如何证明D上学到的f能够和全局h相互接近,这样,就可以用f来代替h,来进行应用.

Probability to the Rescue

We will show that we can indeed infer something outside D using only D, but in a probabilistic way.虽然推断的函数和全局target函数f相比可能并不完全相同,但关键是我们使用一种方法能预测数据集D之外unseen data上的表现如何.一旦确定了这种方法,我们就可以扩展到一般性的学习问题上,并能确定什么是可以学习的,什么是不能学习的?

举一个简单的例子,一个有红色和绿色石头的无限大瓶子[不能穷举石头个数],瓶子中红色石头和绿色石头的比例,如果在瓶子中随机选择一块石头,红色石头的概率是 $\mu$ ,绿色石头的概率 $1-\mu$ . 我们假定 $\mu$ 对于我们来说是未知的.

我们随机从瓶子中选择包含N个石头的随机样本,观察在样本中红色石头的概率 $v$ . 这个概率 $v$ 和概率 $\mu$ 之间有什么关系呢?What does the value of $v$ tell us about the value of $\mu$ ?

一个答案是无论N个样本的颜色是什么,对于那些没有被选择的石头,我们一无所知.我们可以在大多数是红色石头的瓶子中选出大多数是绿色石头的样本.对于参数 $\mu$ 来说,随机变量 $\nu$ 的概率分布,当取样样本数N非常大时, $\nu$ 趋向于 $\mu$ .

为了量化 $v$ 和 $\mu$ 之间的关系,使用Hoeffding Inequality不等式.对于任意样本大小N,

$P[|\nu-\mu|>\epsilon] \leq 2e^{-2\epsilon^2 N}$ for any $\epsilon$ > 0.

P[\cdot]代表一个事件的概率.上面的不等式的意思是说,随着样本大小N逐渐变大, $\nu$ 和 $\mu$ 差值大于 $\epsilon$ 概率会指数级减小[两个概率之间相差很大的概率非常小],也就是说N越大, $\nu$ 和 $\mu$ 之间越相似.不等式中的 $\nu$ 仅依赖于随机样本,与 $\mu$ 无关, $\mu$ 是大小未知.利用hoeffding不等式,可以用 $\nu$ 来推断 $\mu$ .因为 $\nu$ 倾向于接近 $\mu$ ,所以 $\mu$ 也越来越接近 $\nu$ .

尽管 $P[|\nu - \mu| > \epsilon]$ 依赖于 $\mu$ ,但是利用不等式可以断定它的一个不依赖 $\mu$ 的上界 $2e^{-2\epsilon^2 N}$ .可以看出取样样本大小N决定上界的大小,而不是输入空间X的大小.输入空间可大可小,有限或无限,当我们使用相同大小的取样样本时,都不影响不等式的上界阈值.

我们能断定 $\mu$ 接近于 $\nu$ 的依据是样本是随机选择的.如果样本依据某种选择方式选择,那么这个不等式就不再成立.

瓶子模型问题对应于学习问题来说,未知的 $\mu$ 对应于学习问题中未知函数 $f:X \to Y.$ 对于任意假设 $h \in H$ , $x \in X$ ,如果 $h(x) = f(x)$ ,对应于x点是绿色的;如果 $h(x) \neq f(x)$ ,对应于石头是红色的.每个石头是什么颜色是未知的,因为f是未知的.但是如果我们依据某种概率分布P在输入空间X上随机选样本点x,假设x是红色的概率为 $\mu$ ,绿色概率为 $1-\mu$ .输入空间X对应于下图中的瓶子:

[图片上传失败...(image-abcbe5-1544619781471)]

训练样本对应于瓶子中的样本点.如果训练集D中 $x_1,..., x_N$ 是依据P独立地选出来,那一个随机样本可能是红色( $h(x)=f(x)$ ),也可能是绿色( $h(x) \neq f(x)$ ).红色概率为 $\mu$ .在D中每个点的颜色是已知的,因为对于N的点来说, $h(x_N)$ 和 $f(x_N)$ 是已知的(h是假设函数, $f(x_N)=y_N$ ).这样学习问题就和瓶子模型对应上了,D中样本点是依据概率分布P在空间X中独立随机选择,这个概率分布P决定了 $\mu$ 大小,因为 $\mu$ 是未知的,因此随机选择分布P也是未知的.

[图片上传失败...(image-56c310-1544619781471)]

类比以后,不等式可以用在学习问题上,从而保证我们可以估计D之外的数据.依据 $\nu$ 来估计 $\mu$ 可以帮助我们了解target function f,尽管不知道f的具体形式. $\mu$ 可以知道假设函数h在估计f时的错误率;如果 $\nu$ 接近于0,我们可以预测假设h函数将在整个输入空间X上无限接近于f[应用Hoeffding不等式].

$\nu$ 的大小依赖于特定的假设函数h.在实际学习问题中,在整个假设空间H上,选择一些错误率小的 $h \in H$ .如果只有一个假设,这并不是一个学习过程,而是在"验证"这个假设的好坏.将瓶子扩展到多个,也就是多个假设函数,从而变成真正的学习问题.

先定义几个概念,瓶子模型的 $\nu$ 对应于训练集上的错误率in-sample error:

$E_{in}(h)=(fraction of D where f and h disagree) = \frac1{N}\sum_{n=1}^{N}[h(x_n) \neq f(x_n)]$

$E_{in}$ 完全依赖于特定的假设h.定义out-of-sample error:

$E_{out}(h)=P[h(x) \neq f(x)]$ ,

对应于瓶子模型的 $\mu$ ,这个概率的大小依赖于从输入空间X选择样本x时的概率分布.

[图片上传失败...(image-e794f0-1544619781471)]

不等式变成:

$P[|E_{in}(h) - E_{out}(h)|>\epsilon] \leq 2e^{-2\epsilon^2 N}$ for any $\epsilon > 0$ .

我们考虑多个假设的假设空间H,设定H的有限的:

$H={h_1,h_2,...,h_M}$ .

对应于上面图中的M个瓶子.Hoeffding不等式应用于每个单独的瓶子,或者说一个具体的假设函数,而不是多个瓶子.如果同时考虑所有的瓶子,情况就比较复杂.

$P[|E_{in}(h) - E_{out}(h)|>\epsilon] \leq 2e^{-2\epsilon^2 N}$ for any $\epsilon > 0$ .

其中,h是在数据集生成之前就已经确定好了 h is fixed.对于有多个假设的H,学习算法基于数据集D选择最终的假设函数g. 在数据集生成之后,
$P[|E_{in}(g) - E_{out}(g)|>\epsilon] is small for the final hypothesis g$ .

但是g在生成数据之前并不确定,因为g是依据假设函数在数据D上的表现进行选择的.g是在M个h中间进行选择,因此不能直接把g带入到不等式当中.

$P[|E_{in}(h) - E_{out}(h)|>\epsilon]$ 要保证无论学习算法选择假设空间里的哪个假设作为最终g都成立.因为g是假设空间h中的一个具体的假设,所以:

[图片上传失败...(image-26e7a5-1544619781471)]

左边成立,右边一定成立.再利用事件的联合概率,可以得到:

[图片上传失败...(image-57d9ec-1544619781471)]

同时考虑M个模型,可以得到:

$P[|E_{in}(g) - E_{out}(g)|>\epsilon] \leq 2Me^{-2\epsilon^2 N}$

右边界是希望M个模型 $E_{in}(h_m)$ 同时逼近对应的 $E_{out}(h_m)$ .这样无论g选择哪一个模型最终都会满足这个不等式,逼近于对应的全局值.

这种联合式的估计比单个模型上界更大,而且只有在假设空间H有限时才有意义,也就是说M的有限的.

Feasibility of Learning学习的可行性

上面两小节依次介绍了两个观点:依据数据集D学到的内容并不能用来判断数据集之外的数据记录.并没有学习到数据集之外的数据信息;之后又说我们可以学习something outside of D.这两个观点看起来是矛盾的.如何统一起来?

1.通过对数据集D的学习能否学到一些数据集之外unseen data的信息呢?确定的说,"NO";如果可以接受一种概率性的答案,数据集D能告诉我们一些数据集之外unseen data上f的一些信息,"YES".
通过概率性的角度,可以得到一个理想的答案.存在的前提条件是数据集D中的数据记录是独立选择/生成的.同时在用数据评估g和f的接近程度时,数据必须也是同样的方式独立随机选择的,否则Hoeffding不等式失效.
2.学习可行性的含义是什么? 学会产生一个假设函数g去估计(接近/逼近)未知的目标函数f.如果学习是有效的,成功的,那么g应该接近于f,也就是说 $E_{out}(g) \approx 0$ . 然后从概率学中不能直接得到.Hoeffding不等式告诉我们, $E_{out}(g) \approx E_{in}(g)$ . 为了确保 $E_{out}(g) \approx 0$ 必须先让 $E_{in}(g) \approx 0$ .

我们并不能保证一定会找到一个假设函数g能达到 $E_{in}(g) \approx 0$ , 但至少如果能找到的话,我们一定会知道. $E_{out}(g)$ 是未知的,因为f是未知的,但是 $E_{in}(g)$ 是可以度量的.我们可以通过调整 $E_{in}(g) \approx 0$ 让 $E_{out}(g) \approx 0$ . 理论依据是:

$P[|E_{in}(g) - E_{out}(g)| > \epsilon] \leq 2Me^{-2\epsilon^2 N}$

这个不等式能保证 $E_{out}(g) \approx E_{in}(g)$ ,所以可以用 $E_{in}(g)$ 来近似替代 $E_{out}(g)$ .需要注意的是我们并不严格要求 $E_{in}(g) \approx 0$ ,因为有时候并不能实现.

学习的可行性可以划分为两个问题:
[图片上传失败...(image-f48365-1544619781471)]

保证 $E_{in}(g) \approx E_{out}(g)$ ;
保证 $E_{in}(g)$ 足够小.

Hoeffding不等式可以解决第一个问题.第二个问题需要在在真实数据上我们运行学习算法之后,确定 $E_{in}$ 的大小来确定.

将学习的可行性划分为两个问题能帮助我们明白学习问题中不同成分所扮演的角色.

我们先确定一些学习问题各个成分的复杂度如何?

假设空间H的复杂度.如果假设空间假设函数个数M增加,那么 $E_{in}(g)$ 是 $E_{out}(g)$ 的一个poor estimator,因为不等式的上界变大,两个之间的差距也变大,犯错概率增加.因此M可以看做是度量假设空间H的一个指标.对于上面两个问题,第一个问题,为了保证两者之间的接近,应该确保M不会过大,否则上界就会变大,但是这样并不能保证E_{in}(g)足够小,有可能会很大,因为选择不多;第二个问题,为了保证 $E_{in}(g)$ 足够小,M应该足够大,这样就可以选择一个更好的假设g能更好地拟合数据,表现更好,更复杂的假设空间H可以保证选择的范围扩大,可选项增多,要知道林子大了什么鸟都有!所有M需要在两者之间权衡.

目标函数f的复杂度.直觉上复杂函数比简单函数更难学.我们看看能否从上面的两个问题中得到答案.从Hoeffding不等式中可以知道,目标函数f的复杂度并不影响 $E_{in}(g)$ 和E_{out}(g)的接近程度.对于确定的数据集D和假设空间H,无论f复杂还是简单,都不影响不等式的上界,这只是可学性的第一个问题;如果目标函数过于复杂,那么第二个问题就会陷入困境.因为复杂模型的拟合(学习)比简单模型的学习更加复杂,难度更高,这就导致 $E_{in}(g)$ 并不会很小.如果想模型复杂同时能确保 $E_{in}(g)$ 足够小,那么第一个问题就会出错,两者之间差距变大.无论怎样,复杂模型比简单模型要更难学.极端情况下,对于一个极其复杂的模型f,我们可能不能学习.

实际问题中,大多数目标函数都不是过于复杂,我们可以在一个合理假设空间H中,通过合理的数据集D来学习.这两个定语"合理/reasonable"是经验性的,而不是数学严格给定.有时候尽管不能学习到理想的函数f,但是我们至少能判定不能学习. 只要能保证H的复杂度能给定一个良好的Hoeffding上界,那么对于训练数据的拟合程度可以断定f的学习是否成功.

通过将学习可学性划分成两个问题,可以判断某个具体问题是否可学.我们的目标是unseen data上的表现,也就是 $E_{out}(g)$ ,我们想让它足够小,但是不能直接保证,使用Hoeffding不等式可以做一个桥梁,用数据集之间D上 $E_{in}(g)$ 的表现作为unseen data(全局) $E_{out}(g)$ 的一个估计;之后的目光就集中在 $E_{in}(g)$ 上,通过学习算法确保 $E_{in}(g)$ 足够小,进而保证 $E_{out}(g)$ 在数据集之外上也表现良好----是可以学习的!Cool!

Error and Noise误差和噪音

介绍两个概念:一个是函数"近似",当我们讨论两个函数之间近似时是什么意思?第二个是关于目标函数的一个性质.在实际情况中,存在一些噪音使得目标函数f的输出并不是完全依赖于输入数据.有噪声的数据之后,学习问题有什么变化呢?

Error Measures 误差计算

学习并不是对目标函数f的完美复制(也不可能实现).最终的假设函数g仅仅是目标函数f的一个近似(估计).所以,为了度量g对f估计的有多好,两者之间多相似,我们需要定义一个误差计算方法,量化两者之间的差距.

不同的误差计算方法会影响学习过程.不同的误差计算方法产生的最终假设函数g也各不相同,尽管目标函数f和数据是一样的,不同的误差计算值之间可能相差很大.因此我们使用的错误计算方法会对我们学到的东西产生影响.误差计算方法怎么选择,需要进一步讨论.

误差计算方法能量化模型每个假设函数h与目标函数f之间的差距:

$Error = E(h, f)$

E(h,f)是基于整个h和f,是由每个单独的输入点x上的误差来决定.所以我们可以逐个点的进行计算 $e(h(x),f(x))$ ,全局误差计算逐个点之和的平均值.对于分类问题的误差,在逐个点上计算 $e(h(x),f(x))=[h(x) \neq f(x)]$ .
在实际应用中,E(h,f)需要用户指定.相同的学习问题不同的内容会有不同的误差计算方法.

Noisy Targets 噪音

在实际情况中,用来学习的数据并不是由一个决定性的目标函数生成的.相反,它们是以一种有噪音的方式生成的,也就是说输出并不是只由输入决定.
在有噪音的情况下,可以用相同的方法进行建模.将输出y看做一个受输入x影响的随机变量,而不是一个决定性的量.因此,可以得到一个目标分布P(y|x),而不是目标函数y=f(x).一个数据点(x,y)是由联合概率生成P(x,y)=P(x)P(y|x).
可以将带噪音的目标函数看做是决定性函数加上噪音.对于输出y,其输入x决定性的输出是f(x),而y-f(x)看做是加在f上的噪音.
而之前决定性的函数可以看做带噪音的目标函数的特殊情况:噪音为0.同时任意的目标函数f,可以看做分布P(y|x)的特殊情况,保证除了y=f(x)之外,其他y对应的概率都设为0.因此,无论目标是个分布还是函数,都不影响其普遍性.

[图片上传失败...(image-2cce38-1544619781471)]

之前的可学性分析方法也可以用在带噪音的一般目标函数上.因为Hoeffding不等式可以用在任意的未知目标函数上.但是这并不意味着带噪音的目标函数和决定性函数学习难易程度相同.可学性的两个问题,相同的学习模型,在噪音环境下 $E_{out}$ 可以接近 $E_{in}$ ,但是 $E_{in}$ 在噪音环境下更难学习,因为噪音环境下数据不好拟合.

[Learning-from-data]有限假设空间的可学性论述

"学习"

学习问题

学习的"成分"

一个简单的学习模型

Learning VS. Design

"学习"的可行性

Outside the Data Set

Probability to the Rescue

Feasibility of Learning学习的可行性

Error and Noise误差和噪音

Error Measures 误差计算

Noisy Targets 噪音

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

大数据，机器学习，人工智能

机器学习与数据挖掘