Learning From Data Lecture 3 笔记 线性模型1

Lecture2回顾:

上一节讨论了学习是否可行,我们认识到学习确实是可行的,但是只在概率意义上可行。

我们用容器对这个概率意义进行建模, 一个容器代表一个假说h,具有相应样本外误差Eout(h)。

QQ截图20131022092635

为了知道Eout(h),我们观察样本内误差Ein(h),由hoeffding不等式知,样本内误差是可以近似Eout(h)的。

QQ截图20131022092732

该不等式告诉我们:Ein(h)与Eout(h)之间的差距在容忍值ε之外的概率小于一个很小的值,这个值随着样本数量N的增大而减小。

这个不等式关系是构建学习理论的一个基础构件,但是只适用于一个单一假说的情况。

考虑假说集合h1至h2,...,hM,hoeffding不等式对于其中任意一个单一假说均成立,但对于假说集,累积起来的概率上限可能会很大,意味着假说集合中选出Ein(h)与Eout(h)之间差距在容忍值ε之外的假说h的概率很大。

令g为最终选取的假说,则g必然是h1至h2,...,hM,中的一个,则如果|Ein(h)-Eout(h)|>ε则,必然有h1至h2,...,hM中有一个假说h使得|Ein(h)-Eout(h)|>ε。因此,获得上限:

即通过机器学习后,获得的假说与目标函数间误差超过容忍值的概率小于一个上限值。

这个不等式告诉我们,如果我们选择越是复杂的假说集合,则这个上限值越大,学习就开始变得无意义了。


Lecture 3 Linear Models I

学习可行么?

内容

  1. 输入表达(Input representation)
  2. 线性分类(Linear Classiation)
  3. 线性回归(Linear Regression)
  4. 非线性变换(Nonlinear Transformation)

3.1 输入表达

以一个真实的数据集做例子,数据集的来源是邮局收集的手写数字,每一个手写数字都是16×16像素灰度图片:

QQ截图20131022095324

我们需要做的是让机器来根据图片判断出图中的数字。我们将尝试使用第一节中介绍的感知器模型来解决这个问题,并在此基础上将模型进行推广。

第一个问题是:输入的表达。下图是一个输入的示例:

QQ截图20131022095828

16×16像素的灰度图片,共包含256个值,引入人工常量x0=1,用向量为:

QQ截图20131022102100

如果我们直接采用感知器模型,则模型中会有257个参数:

QQ截图20131022102434

无论是输入还是模型,都是高维度的。学习算法需要跟据数据来学习这257个参数的值。

输入表达的目的在于简化学习算法的生活。对于这个问题的输入,我们有一些知识,我们知道并不是每一个像素都等价地影响着结果变量,我们可以从中提取出一些特征,然后将这些特征交给学习算法。

特征是抽取出的有用信息。

在这个例子中,我们可以抽取一些用于描述图片的信息,如颜色的饱和度和图片的对称度。

例如:一般而言,1的颜色饱和度小于5的颜色饱和度小于8的颜色饱和度。如果我们将一个图片上所有像素的颜色值加起来,得到的这个综合可能不能唯一地决定这个图片所代表的数字,但是可能是紧密相关的。令这个特征为x1

图片的对称度也是类似的,8的对称度要大于5的对称度。我们可以将图片反转,然后比较反转前后的两张图片上像素的差异,将这个差异值作为特征。令这个特征为x2

这两个抽取出来的特征都是原始输入的高层抽象。

因此,将输入表达转化为:

QQ截图20131022103803

这个过程中,无可避免地会有信息的损失。但这个例子里同时损失了无关信息和有关信息,只保留了有关信息,同时将257维的输入数据降至3维。

相应的感知器模型也只有3个参数:

QQ截图20131022104046


3.2 线性分类

下面是抽取特征后对数字5个数字1的数据进行分类的一个可视化示例:

QQ截图20131022104151

其中每一个圈或叉都分别对应于一个输入数据,上图中的横坐标代表对称程度,纵坐标代表颜色饱和度。

从这个示例可以看出,数字5个数字1几乎是线性可分割的。

感知器学习算法的作用是:计算Ein与Eout之间的差距。

下图中横坐标代表学习算法的迭代次数,纵坐标代表Ein与Eout的值:

QQ截图20131022105058

其中绿色的折线代表Ein,蓝色的折线代表Eout(实际问题中是未知的),随着迭代次数的增加,Ein时而减少时而增加,因为为了适应某一个错误分类的数据而对模型进行的调整可能会导致对原先能正确分类的数据的错误分类。

从图中可以看出,随着Ein的减小,Eout也随之减小,随着Ein的增大,Eout也随之增大,表明采用这两个特征的感知器模型能够较好地推广。

因为这个数据并不能完美地用线性模型进行分类,感知器模型的表现可能会很糟糕,并且永远不会收敛。

我们可以做的事在第1000次迭代的时候令其停止,将此时所得的g作为最终假说输出。

此时获得的分割线如下所示:

QQ截图20131022105930

显然不是特别理想。在之前的图中明显能看出在250次迭代附近获得的假说要更加好。

下面对学习算法进行一个修正,称为口袋算法(pocket algorithm),令算法记录下目前为止最小的Ein所对应的假说g,并将这个g作为最终假说输出。

采用口袋版感知器学习算法所获得的分割线如下所示:

QQ截图20131022110427


3.3 线性回归

回归的含义是实值输出。线性回归在统计学和经济学中应用非常广泛。

以信用卡问题为例来区分回归问题和分类问题:

  • 分类问题为:信用审批,输出的值为二元值,批准或拒绝。
  • 回归问题为:信用额度,输出为实值,是具体的货币数量。

对于信用额度的问题,输入数据与之前一样为申请者的信息。线性回归模型输出的假说,形式如下:

QQ截图20131022113323

这与之前的感知器分类模型输出的假说形式非常相似:

vector form peceptron fomula

唯一的区别在于,之前我们只关心假说输出结果的符号,而线性回归问题中我们关心输出结果的具体值。

信用额度判断问题的输入数据也是银行的历史记录数据,但是与之前信用审批的判断问题的输入数据略有不同,结果变量y代表的是具体的数额:

QQ截图20131022142932

yn代表的是给申请者xn批准的的信用额度,yn是实值。

学习算法的任务是根据给定的输入数据,在线性回归模型中寻找最适合的模型,即要找到最合适的参数W。

不同的参数W确定了不同的假说,不同的假说与目标函数之间的差距不一,我们需要给学习算法提供一个判断标准,提供一个误差测量方法,帮助学习算法能够定量地判断假说与目标函数之间的差距大小,以选择最合适的参数。

在线性回归问题中,我们利用均方误差(squared error)来测量误差:

QQ截图20131022143706

均方误差是线性回归问题的标准误差测量方法,测量的是假说的预测值与目标函数的实际输出值之间的差距。

因此对于一个特定的假说,样本内误差为假说所估测的结果与真实值之间的差距平方和的均值,即:

QQ截图20131022143754

学习算法的任务便是要找到能够使得这个误差测量值最小的参数W。

下面以图为例进行说明:

CA___Lecture 03_ [ The Linear Model[14-45-26]

图中横坐标代表GPA,纵坐标代表十年后的年收入。线性回归模型尝试根据均方误差找到一条直线。

CA___Lecture 03_ [ The Linear Model[14-45-26]2

样本内误差即为各个数据点与模型预测值之间差值的平方的均值,即红色直线长度的平房和再除以数据点的数量。

QQ截图20131022144737

线性回归可以应用与高维数据,如下图所示:

QQ截图20131022145442

上图中每一个数据都是三维平面中的一个点,而假说则是蓝色所示的二维平面。

将样本内误差的表达式改写成矩阵形式,得到:

QQ截图20131022145728

其中:

QQ截图20131022145804

学习算法的目的是使得Ein(W)最小,就W进行求导:

QQ截图20131022150134

令上式为0求解出:

QQ截图20131022150337

因为不确定X是否可逆,继而求解出:

QQ截图20131022150611

其中QQ截图20131022150744为X的伪拟(pseudo-inverse)。

矩阵X的d+1行,代表d个特征和1个人工常量,矩阵X的N列,代表训练集中的N个训练数据,通常N远大于d+1。在实际问题中,通常不用担心是否可逆的问题。

X的转置矩阵和X的乘积将是一个的d+1×d+1的矩阵,对这个尺寸为d+1×d+1的矩阵求逆矩阵,将其结果再进一步乘上X的转置矩阵便可得到参数W:

QQ截图20131022151347

总结线性回归模型的学习算法如下:

QQ截图20131022151933

在构建输入数据矩阵和结果变量的向量后,只需一步计算即可得到假说。

线性回归模型经常被用来作为更加复杂问题的构件。

线性回归模型不仅可以用于预测实值,也可以用于解决分类问题。之前的感知器分类模型输出的结果为+1或-1,实际上也是实值,因此也可以用线性回归模型来解决这个问题。

我们可以用线性回归模型一步求解出一个参数向量W,然后将其作为初始参数提供给感知器模型,然后再运行口袋算法进一步优化参数W,这样做可以加快优化的过程。


3.4 非线性变换

线性模型是有局限的,例如下面一个二元分类问题:

QQ截图20131022153342

任何直线都无法很好地将数据进行分类,我们希望能获得如下假说:

QQ截图20131022153419

在线性回归模型中,模型的线性关系并不在于输入数据X是线性的,而是在于参数W是线性的。

因此,我们可以对输入数据X进行转换,然后再运用至线性回归模型中去。

如,对于上例,我们采取一个变换:

QQ截图20131022154306

将原先数据数据空间中的一个个数据点均转换为一个新的输入空间中的对应数据点:

QQ截图20131022154511

变换后的输入空间明显是线性可分割的。

你可以进行任何变换,使得变换后的问题是更加容易解决的。

课程地址:http://work.caltech.edu/telecourse.html

Leave a Reply

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