Tag Archives: 机器学习

支持向量机(Support Vector Machine)Part I

支持向量机用于解决分类问题。与感知器(PLA)相比,支持向量机不仅试图找到一个能够完美分割数据的高维平面(hyperplane),而且还希望这个平面能够尽量地胖,即平面与最近的数据点之间的距离尽可能地要大。

fatHyperPlane

给人的直观感觉是:分类平面离最近的数据点越远,越能容忍误差,因而鲁棒性越好。

1. 令w是分类平面的法向量
2. 分类器对每个数据点的所属类别的判断方法为:h(x)=sign(w^Tx+b)
3. 要完美地完成分类任务即等价于要:y_{n}(w^{T}x_{n}+b) data-recalc-dims=0" />
4. 每个数据点到分类平面的距离为:frac{1}{||w||}y_{n}(w^{T}x_{n}+b)

定义支持向量机问题如下:
underset{b,w}{max}qquad margin(b,w)
subject toqquad y_{n}(w^{T}x_{n}+b) data-recalc-dims=0" />
where qquad margin(b,w) = underset{n=1,dots ,N}{min}frac{1}{||w||}y_{n}(w^{T}x_{n}+b)
因为通过对b,w进行同等的放缩对限制条件并无影响,不妨令underset{n=1,dots ,N}{min}y_{n}(w^{T}x_{n}+b)=1
即可对上面问题进行简化:

underset{b,w}{max}qquad frac{1}{||w||}
subject to qquad underset{n=1,dots ,N}{min}y_{n}(w^{T}x_{n}+b)=1

依旧可以通过放缩对限制条件进行放松,同时将问题中的最大化专为最小化,获得了支持向量机的标准形式:

underset{b,w}{min}qquad frac{1}{2}w^Tw
subject to qquad y_{n}(w^{T}x_{n}+b)geq 1

这是一个二次规划问题,包含d+1个变量,N个限制条件

下面举个例子,在matlab中,利用cvx求解一个支持向量机,有四个数据点:
x_1=(0,0),y_1=-1
x_2=(2,2),y_1=-1
x_1=(2,0),y_1=1
x_1=(3,0),y_1=1
现要求解满足条件的支持向量机,代码如下:

求解后获得b = -1,w = [1;-1]

支持向量机的标准形式包含的是一个二次的目标函数和线性的限制条件,是一个二次规划问题,可以通过二次规划求解。

等价的二次规划问题形式如下:
underset{u}{min} qquad frac{1}{2}u^TQu+p^Tu
subject  to qquad a_m^Tugeq c_m
qquad for  m = 1,2,...,M

其中,目标中:
u = begin{bmatrix} bw end{bmatrix}
Q = begin{bmatrix} 0 quad 0^T_d �_d quad I_d end{bmatrix}
p = 0_{d+1}
限制条件为:
a^T_n = y_n[1quad x^T_n]
c_n = 1
M=N

下面仍然用cvx来求解上面例子中问题的二次规划形式,同时,我们对x进行一个非线性的变换:

求解得到:u = begin{bmatrix} -92� end{bmatrix}

即:b = -9, w =[2;0]

 

博主对于朗格朗日乘子和KKT条件不是懂,据说将上面的支持向量机标准形式转变为对应的对偶问题能够提高求解速度,支持向量机的对偶问题形式如下:

underset{alpha}{min}qquad frac{1}{2}sum_{n=1}^{N}sum_{m=1}^{N}{alpha}_n{alpha}_my_ny_mz_n^Tz_m-sum_{n=1}^{N}{alpha}_n

text{subject to}quad sum_{n=1}^{N}y_nalpha_n = 0;

qquad alpha_ngeq 0,quad text{for } n=1,2,3,dots ,N

对偶问题仍然是二次规划问题,有N个变量和N+?个限制条件,其中的alpha为拉格朗日乘数。

其解法为:

underset{alpha}{min}qquad frac{1}{2}alpha^TQ_Dalpha-1^Talpha

text{subject to} y^Talpha = 0;

qquad alpha_ngeq 0 text{for}  n=1,2,3,dots , N

Q_D矩阵中:q_{n,m}=y_ny_mz_n^Tz_m

CVX中代码示例:

求解出a为[0.0000;0.7037;0.7037;0.8889;0.2593;0.2593;0.0000],表示第2~第6个数据点为支持向量。相应的$b,w$求法如下:

w=sum_{SV}alpha_ny_nz_n

b=y_n-w^Tz_n,text{with any} SV(z_n,y_n)

Python中利用scikit-learn的SVM模块求解支持向量机方法如下,X,y以numpy.ndarray形式存储数据和标签:

本节中介绍的都是“硬”的支持向量机,Part II中会介绍“软”的支持向量机。

Learning From Data Lecture 8 偏倚和偏差的权衡

Segment 1 偏倚和偏差(Bias and Variances)

权衡的定量化:

由VC理论知:Eout<=Ein

Ein是Eout的一个近似,是针对训练数据拟合的h的样本内误差。

加上一般化误差Ω,这个式子告诉我们由样本内推广到样本外会如何。

偏倚和偏差分析是另一种途径,尝试将误差分解为两个部分,即:

  1. 假说集合H在多大程度上能近似目标函数f
    忽略样本,假设已知f和H,分析H中与f最接近的h与f之间的差距
  2. 能够从假说集合中找到这个h的可能性
    假设已知H中与f最近的f,根据已有的数据,有多大可能选择出这个h

下面的讨论中,将采用实值的目标函数,并用平方误差作为误差测量。

从Eout开始:

通过给定的训练数据集D,挑选出的最终假说g的样本外误差表达式为:

  • Eout(g(D))= EX[(g(D)(x)−f(x))2]

明显地,样本外误差的值依赖于所给定的训练数据集D。

假设现在只限定训练数据集D的样本数量为N,允许生成多个这样的训练数据集,则针对这些不同的训练数据集,可以获得不同的最终假说以及相应的样本外误差。

想要了解与某一给定训练数据集D无关的一般化的样本外误差,在等式两边都加上样本的期望:

  • ED[Eout(g(D))]=ED[EX[(g(D)(x)−f(x))2]]

根据期望迭代定律有:

  • ED[Eout(g(D))]=EX[ED[(g(D)(x)−f(x))2]]

下面主要讨论右边里面只与数据集D有关的这一项:

ED[(g(D)(x)−f(x))2]

平均假说(average hypothesis):

平均假说的定义:

对于一个特定的假说集合H,定义平均假说g(x)为:

g(x)=ED[(g(D)(x)]

g(D)(x)中x是一个给定的数据点,g(D)()是针对不同的训练数据集D挑选出的最终假说,g(D)(x)合起来是这些挑选而出的最终假说在这个给定的数据点X上的函数值ED[(g(D)(x)]是这些函数值的平均值。

如果训练数据集D的数量非常大,那么这个平均期望可能可以非常接近f。

QQ截图20131231153043

下面对ED[(g(D)(x)−f(x))2]进行展开:

ED[(g(D)(x)−f(x))2]=ED[(g(D)(x)−g(x)+g(x)-f(x))2]

=ED[(g(D)(x)−g(x))2+((g(x)-f(x))2+2(g(D)(x)−g(x))((g(x)-f(x))]

考虑到所求的是针对D的期望:

g(x)-f(x)为常数,交叉相乘项的关键在于ED[(g(D)(x)−g(x))]

由差的期望等于期望的差知:

  • ED[(g(D)(x)−g(x))]=ED[g(D)(x)]-ED[g(x)],其中ED[g(D)(x)]=g(x)为常数ED[g(x)]=g(x),两项消除为0

因此得到:

  • ED[(g(D)(x)−f(x))2]=ED[(g(D)(x)−g(x))2]+((g(x)-f(x))2

尝试理解这个式子:

ED[(g(D)(x)−f(x))2]告诉我们的是针对训练数据集D,我们从假说集合H中挑选出的最终假说g与目标函数f之间的差距

我们将其分解为两个部分:

  1. ED[(g(D)(x)−g(x))2]告诉我们的是,我们从假说集合H中挑选出的最终假说g与可能最好的平均假说g之间的差距
  2. ((g(x)-f(x))2是这个可能最佳的平均假说g与目标函数f之间的差距。

偏倚和偏差分别对应于这两者:

  1. 偏差为(var(X)):ED[(g(D)(x)−g(x))2]:是根据训练数据集D选出的最终假说g与平均假说g之间的距离,揭示的是给训练数据集D的影响
  2. 偏倚(bias(X))为:((g(x)-f(x))2: 是假说集合中最好的情况与目标函数之间针对某一个数据点的差距,揭示的是假说集合本身的影响

因此简化最一开始提出的样本外误差表达式:

Eout(g(D))= EX[(g(D)(x)−f(x))2]  = EX[bias(X)+var(X)]

偏差和偏倚权衡:

  • 偏倚:EX[bias(X)]=EX[((g(x)-f(x))2]
  • 偏差:EX[var(X)]=EX[ED[(g(D)(x)−g(x))2]]

以两张图来尝试说明偏倚和偏差之间的权衡

QQ截图20131231154811

上图代表假说集合H的复杂程度较低,假说集合中最好的情况离目标函数的距离可能较大,但是偏差可能较小。

QQ截图20131231154819

上图代表假说集合H的复杂程度较高,假说集合中最好的情况离目标函数的距离可能较小(甚至包含在其内),但是偏差可能较大。

告诉我们:

随着假说集合H的复杂度上升,偏倚减小,偏差增大。

举例说明:

假设目标函数是 f:[-1,+1] –> R, f(x)=sin(πx).

假设我们的训练数据集只含两个数据N=2, D={(x1,y1),(x2,y2)}

假设我们有两个假说集合:

H0为常数,h(x)=b

H1为线性一次函数,h(x)=ax+b

对于H0,挑选g(x)=(y1+y2)/2可以是Ein最小

QQ截图20131231155842

对于H1中挑选g(x)=(y1+y2)/(x1-x2)x+(x1y2-x2y1)/(x1-x2)可以使Ein最小

QQ截图20131231155852

现在要比较这两个假说集合的样本外误差Eout

就相当于是看获得的直线与目标函数对应的曲线之间区域的面积:

QQ截图20131231160801

下面考虑两个假说集合中平均假说分别是什么:

对于H0

下图左边表示的是反复抽取2个数据构成训练数据集D并拟合出的g()的分布情况,右边的绿色直线表示的是这些假说的平均,即g(x)。

g(x)是我们希望能选为最终假说的输出结果,但不一定能够选到它,这依赖于给定的数据集D。

下图右边的阴影部分是正负一个标准差的范围,因此:

蓝色曲线与绿色直线之间的差别代表偏倚,而阴影部分代表偏差。

QQ截图20131231212436

对于H1

下图左边表示的是反复抽取2个数据构成训练数据集D并拟合出的g()的分布情况,右边的红色直线表示的是这些假说的平均,即g(x)。

g(x)是我们希望能选为最终假说的输出结果,但不一定能够选到它,这依赖于给定的数据集D。

下图右边的阴影部分是正负一个标准差的范围,因此:

蓝色曲线与红色直线之间的差别代表偏倚,而阴影部分代表偏差。

QQ截图20131231213519

比较这两个假说集合,可以知道:

H0与H1相比,偏差较小,偏倚较大,下面是两者的具体数值。

QQ截图20131231213917

因此,在给定一个只含两个数据点的训练数据集D的情况下,赢家是H0

给我们的教训:

在机器学习问题中,我们是在模型复杂程度与训练数据集之间做匹配,而非在模型复杂程度与目标函数复杂程度之间做匹配。


Segment 2 学习曲线(Learning Curve)

学习曲线是在一张图表上同时绘制出样本内误差和样本外误差。

下图揭示的是简单模型和复杂模型的学习曲线。

QQ截图20131231214451

对于简单的模型,样本内外误差之间的差距较小,随着训练数据集样本量的增加,最终能达到的样本内误差不低,误差趋近于收敛的速度较快。

对于复杂的模型,样本内外误差之间的差距较大,随着训练数据集样本量的增加,最终能达到的样本内误差较低,误差趋近于收敛的速度较慢。

解读复杂模型的学习曲线:对于样本量较少的情况,复杂的模型是“记忆”住了样本,因此对样本外数据的误差大,只有在样本量足够大的时候,才能打破这个“偏见”而得以能够推广到样本外。

偏倚、偏差分析与VC分析告诉我们的结果是类似的。

QQ截图20131231215404

上图左边是基于VC理论的分析:

  • 蓝色区域代表样本内误差
  • 对于给定的N,做一条垂线,其在两条曲线上交点值之间的距离与一般化误差Ω成正比

上图右边是基于偏倚和偏差的分析:

  • 蓝色区域代表的是偏倚,即g(x)与f(X轴)之间的差距
  • 红色区域代表的是偏差

两种分析都考虑了样本内外误差,区别在于:

基于VC理论的分析中样本内外误差都随着样本量而改变

基于偏倚、偏差的分析中偏倚是常数,由假说集合决定,而偏差则由假说集合以及样本量共同决定

比较容易能理解为什么基于偏倚、偏差的分析的学习曲线的结构,下面举例解释基于VC理论的学习曲线结构。

最后以线性回归做示例:

假设我们尝试去学习的是一个有噪声的线性目标函数:y=wTX+noise

训练数据集为:D = {(x1,y1),…,(xn,yn)}

利用线性回归的正规方程解法,最终假说g中 w=(XTX)-1XTy

样本内误差Ein=Xw-y

对于同样的数据X,利用不同的noise生成y’用于估计样本外误差Eout=Xw-y’

QQ截图20131231221533

由此获得的学习曲线如上图所示。

其中:

  • σ2是样本外误差所能达到的最佳误差情况
  • 样本内误差的期望为:σ2(1-(d+1)/N)
  • 样本外误差的期望为:σ2(1+(d+1)/N)
  • 一般化误差的期望为:2σ2((d+1)/N)

d是假说集合的自由度。

一般化误差的期望值表达式也是上节中对曲线解读的来源。

课程地址:

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

Learning From Data Lecture 7 VC维度

Segment1 VC维度的定义

VC维度是针对假说集合H而定义的一个量,即给定一个假说集合,有一个数值称为VC维度。

给定假说集合H的VC维度记作:

  • dvc(H)

定义其数值等于假说集合H所能“打碎”的最大样本数据量。即:

  • 满足mH(N)=2N的N的最大值。

注意:

  • 并不是说任何N个数据的样本数据都能被假说集合H打碎,而是只要存在任何一个N个数据的样本能被假说集合H打碎,这个N就是我们要的。

假设已知一个假说集合H的VC维度dvc(H),

  • 如现有样本中数据量N<=dvc(H),则假说集合H有可能能打碎这N个数据点。
  • 如果有样本中数据量k>dvc(H),则假说集合H没有可能打碎这k个数据点。

dvc(H)这个值实际上等于转折点k的最小值-1,因此可以改写之前得出的成长函数上限:

由:

grwoth function bound in term of break point

改为:

grwoth function bound in term of vc dimension

下面举例说明VC维度:

  • 对于正射线假说集合,最小转折点为2,VC维度为1
  • 对于2维感知器假说集合,最小转折点为4,VC维度为3
  • 对于凸集合假说集,不存在转折点,VC维度为无穷大

下面看VC维度与机器学习之间的关系:

最重要的结论是:

  • 如果假说集合H的VC维度是有限的,在给定训练数据D的前提下,假说集合H中挑选出的最终假说g有非常高的概率可以一般化(g≈f)。

这个结论与学习算法A无关,与生成训练集数据的概率P无关,与目标函数f无关。

原因是:

  • 在得到VC维度的过程中,我们一直考虑的都是最糟糕情况时的上限,因此使得这个结论是可以一般化的。
    (无论Hoeffding 不等式还是成长函数都是考虑最糟糕的情况)

learning digram

因此在VC理论中关心的内容仅剩下:

  1. 希望得到的g≈f
  2. 假说集合H,VC维度的来源
  3. 训练数据D

segment 2 感知器假说集合的VC维度

考虑1维感知器假说集合实际上就相当于正射线假说集合,其VC维度是已知的2。

已知,2维感知器假说集合的VC维度为3。

考虑3维情况下的感知器,这时候的感知器将对应于3维空间内的一个2维平面。

很明显,2维空间中无法被直线模型所打碎的4个数据点的情况在3维空间中非常容易被2维平面所打碎。

3dpecptron

因此,3维感知器假说集合的VC维度至少为4。

猜想说对于d维感知器假说集合,其VC维度为d+1。

从两个方向上加以证明,即:

  1. dvc(H)<= d + 1
  2. dvc(H)>= d + 1

首先证明dvc(H)>= d + 1 :

为了证明dvc(H)>= d + 1,我们只要尝试在d维输入数据空间(Rd)中构建特定的N=d+1个数据点,并且使得这d+1个数据点能被d维感知器打碎即可。

用如下矩阵来构建这d+1个数据点。

trivial matrix

矩阵相当于是令单位矩阵的第1列全部都为1。

这个矩阵的行列式为1,因此是可逆的。

对于任意的

y

我们都需要找到一个向量w,使得sign(Xw) = y。

实际上,对于这样构建的输入数据X,我们完全可以可以使得Xw=y,只需要令w=X−1y即可(X可逆)。

接着证明dvc(H)<= d + 1 :

为了证明dvc(H)<= d + 1,我们需要证明对于d维输入数据空间(Rd)中的任意d+2个数据点,d维感知器均不能将其打碎。

对于任意d+2个数据点:x1,x2…xd+1,xd+2

数据点的数量超过空间的维度。如果我们有超过维度的向量数量,则其中必然存在线性相关,即至少存在一个xj和其余所有xi满足:

linear dependent 

ai为相应的系数,必然的ai不可全为0。

在上述结论的基础上,考虑如下二分法:

  • 对于所有ai非0的ai,令yi = sign(ai),并且令yj=-1。

这样的一个二分法是d维感知器假说所不能实现的。

原因如下,由线性相关性知:

signal coeff

由于wTXi = yi = sign(ai),sign(ai)×ai显然>0

因此上面右边的和必然为一正数,即知道wTXj = yj必然>0,不可能满足yj=-1。

综合两个结论,得证对于感知器假说集合其VC维度满足:dvc(H)= d + 1 。

对于感知器假说而言,这个d+1与假说中的参数(w0,w1,…,wd)数量相同。

将感知器假说的VC维度与其参数数量做比较,是为了在直观感受上,给你这样一种感觉:假说的参数越多,假说集合的VC维度越高。


segment 3 VC维度的解读

一种理解VC维度含义的方法是看自由度(degree of freedom)。

给定一个假说集合,区分这个假说集合中不同假说的是参数,拥有不同参数值的两个假说是不同的假说。

也就是说,参数给了我们创造不同具体假说的自由度。

将参数想象成旋钮。

switch

当给定假说集合的时候,就相当于扔给你一个带有固定数量旋钮的控制面板,你可以通过调整各个旋钮来产生不同的假说。

  • 参数的个数是“模拟”(analog)自由度(含义为:连续地,对任何一个旋钮进行任何调整都会产生新的假说)。
  • 而VC维度则是将上面的模拟自由度转变为二元(binary)自由度(含义为:二元地,对任何一个旋钮进行任何调整都只可能产生两种不同的假说)。

因此VC维度所做的是对低层的数学推导进行抽象,让人只关心假说集合的自由度(表达力)。

考虑几个老伙计:

正射线假说集合:

positive ray

区别不同地正射线假说的是参数a的取值,仅仅这一个参数。而正射线假说集合的VC维度也为1。

正区间假说集合:

postive interval

区别不同地正区间假说的是区间的两个端点的取值,是两个参数。而正区间假说集合的VC维度也为2。

  • 因此实践中,我们大致可以认为假说集合的参数数量近似于VC维度的值。

但并不总是如此。

考虑如下感知器:

perceptron

其输入为单个变量x,输出结果为+1或-1,该感知器的参数为w0,w1两个,VC维度为2。

但是这不是我们的完整假说集合,我们完整的假说集合是若干感知器的套用:

counter examples

每个感知器都有2个参数,完整的假说集合一共有8个参数,但是这些参数重叠严重,实际的自由度仍然只有2。

  • 因此,实际上VC维度告诉我们的是假说集合中有效参数的数量。

下面考虑在已知假说集合的VC维度情况下,我们如何知道所需要的训练数据量。

回顾VC不等式:

inequality

其中有两个我们希望能够非常小的量,即ε和不等式的整个右边部分。

已知mH(2N)=Ndvc(H)。 令δ=不等式的右边部分。

在给定dvc(H),ε和δ的情况下,我们可以求解N。

(例如,我希望我的2维感知器假说至多10%的情况下误差大于5%,则dvc(H)=3,ε=0.05,δ=0.1)

在求解之前,先来看简单一点的情况,看Nde-N的曲线集合中N与d对曲线的影响:

d=4时曲线如下:

4

先增后减,我们希望这个值要足够小,因此需要N足够大。

d=5时曲线如下:

5

变化的规律依然是先增后减,同样希望这个值足够小,需要N足够大。

并且可以看到,对于同样的小值,d更大时,需要的N更大。

3

考虑对于给定的Nde-N值,看d与N的关系:

下图中y值(即Nde-N值)是取log后的结果,从里到外分别为d=5,d=10,d=15,d=20,d=25,d=30时的曲线。

plot

如果用一条水平线来截这些曲线,发现两两曲线被截之处的值几乎是与d的取值成比例增长的。

直观上说明为:了达到同样的Nde-N值,随着d的增长,所需要的N值是成比例增长的。

直观的结论是VC维度越大,需要的训练数据量越大,而且所需数据量几乎与VC维度成正比。

经验结果是通常需要N>=10dvc(H)的数据量。

补充一个林老师课上的例子,通过理论计算出的量会远大于经验结果:

vc N

原因是,VC理论由始至终都考虑到是最糟情况。


segment4 一般化的上限

从δ的表达式中求解出ε的表达式:

solve for epsilon

我们称右边这个根号项为Ω。

明显地有:

  • 在所有其他量均不变的情况下,VC维度越大,ε越大。
  • 在所有其他量均不变的情况下,训练数据量N越大,ε越小。

对原先的VC不等式做一个转变:

我们有1-δ的概率,选定的假说h的一般化误差的上限小于Ω

  • P[|Ein(h)-Eout(h)|<=Ω(N,H,δ)] >=(1-δ)

这相当于我们最终的一般化的上限:

  • P[Eout(h)<=Ω(N,H,δ)+Ein(h)] >=(1-δ)

对于这个式子,我们可以看出:

如果假说集合H变得更加复杂,VC维度上升,则Ein(h)变小,假说能够更好地拟合样本内数据,但是Ω随着VC维度上升而上升,导致Eout(h)不是一定变小,而是要看前两者变化的综合结果。

这部分内容在以后归一化部分继续讨论。

课程地址:

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

Learning From Data Lecture 6 一般化的理论

segment 1 证明成长函数mH(N)是多项式

核心思想:

  • 如果要证明成长函数是mH(N)多项式,只需要证明成长函数mH(N)小于一个多项式。

关键的数量:

  • B(N,k),在转折点为k时,对于N个数据点的最大二分法数量。

回顾转折点k的定义:

  • 如果包含k个数据点的数据集均不能被假说集合H“打碎”,则称k是假说集合H的转折点。

在B(N,k)的定义中,假说集合被限定为二分法。

对二分法结果的矩阵而言,B(N,k)的值意味着:

  • 在N列的矩阵中,任意选择k列,要这k列中均不包含所有(2k)种可能的模式。B(N,k)是满足该条件的矩阵的行数。

例如,k=2,N=3,考虑下面二分法是否满足 B(N,k)的定义?

X1 X2 x3
+1 +1 +1
-1 -1 -1
+1 -1 +1
-1 +1 +1
-1 -1 +1

上述二分法是不符合 B(N,k)定义的,因为第1和第2个数据这2个数据点的及和被二分法打碎了(+1+1,-1-1,+1-1,-1+1均包含了2k = 22=4种模式)。

通过枚举法可知k=2,N=3时,二分法的最大可能性为4:

例如:

X1 X2 x3
+1 +1 +1
-1 +1 +1
+1 -1 +1
+1 +1 -1

接下来讨论一般情况,对于N个数据点,所有满足B(N,k)的二分法数量的上限是多少。

考虑一个满足B(N,K)的二分法矩阵,每一列分别对应一个数据点Xi。

考虑可以如何将矩阵进一步细分。

bnk-matrix

矩阵的第一部分称为S1,共有2α行。

S1中的每一列中的X1至XN-1的可能组合都出现正好2次,一次是伴随着XN=+1,一次是伴随着XN=-1。

根据XN=+1还是-1将其分为2个子部分S1+和S1-,两个子部分的行数相等均为α

矩阵的第2部分称为S2,共有β行。

其中每一列的X1至XN-1的可能情况都是与第一部分中X1至XN-1的情况互斥。

得出 B(N,k) = 2α+β

举一个例子N=4,k=3:

QQ截图20131218110408

有B(4,3) = 11

我们尝试通过递归的方法获得B(N,k)的上限。

首先尝试发现B(N,k)与B(N-1,k)之间的关系,由B(N,k)的二分法矩阵出发,尝试分析一下B(N-1,k)的二分法矩阵:

bn-1k-matrix

因为S1+和S1-这两个部分原先只有XN项不同,因此只可保留其一,而S2这部分的X1至XN-1均与S1中的情况互斥。

这样便构成了一个比B(N,k)小一些的矩阵。

在原先的B(N,k)矩阵中,任选k列,均不可能包含所有(2k)种模式。

因此可以知道,这个小矩阵中任选k列,也不可能会有包含所有(2k)种模式的情况。

因此知道:B(N-1,k) >=α+β

以上面B(4,3)为例,这样操作的结果是获得如下二分法矩阵:

QQ截图20131218110549

则知道B(3,3)>=3+4=7

如果尝试对B(3,3)进行枚举,结果可以发现B(3,3)确实为7,与这样构建的结果相同。

接下来观察原本B(N,k)二分法矩阵中的S1部分:

bnk-matrix3

因为S1+和S1-的前XN-1列完全是相同的,只随意选取其一来分析。

尝试说明这个被选出的部分的转折点为k-1。

原因是:对于S1+任意一行,S1-中均有一模一样的一行。

XN项的特殊性在于包含了其所有可能的情况,在加上XN项的情况下S1部分的突破点为k,在去掉XN后剩余的部分突破点应该为k-1。

即 α <= B(N-1,k-1)。

仍以之前B(4,3)的为例,抽取出来的S1+的前三列为:

QQ截图20131218110455

通过枚举亦可知B(3,2) = 4。

综合上面的结论B(N-1,k) >=α+β,α <= B(N-1,k-1),B(N,k) = 2α+β得到:

  • B(N,k)>=B(N-1,k)+B(N-1,k-1)

因此可以以此公式,在通过枚举法获得前几个情况的结果后,通过递归地f方式求出B(N,k)的上限表格:

  • 注意到B(N,1)的含义是,在N列的矩阵中任意取一列,该列中不能既有+1又有-1,其结果显而易见只能是1
  • 注意到B(1,k)的含义是,在1列的矩阵中任意取k列,该k列中不能包含所有可能的模式,因为实际上只有1列,因此B(1,k)=2

此后可用递归方法填满整张表格。

growth function matrix

这个表格实际上告诉我们B(N,k)的公式为:

theory

可以用归纳法证明:

proof

最后将此B(N,k)作为成长函数mH(N)的上限,这个值是多项式,因为最大项为NK-1,而N是训练集的数据数量,为常数。

gro fun

三个例子:

3 examples

  • 正射线假说集合的转折点为2,其成长函数上限为N+1
  • 正区间假说集合的转折点为3,其成长函数上限为1/2×N2+1/2×N+1
  • 2维感知器假说集合的转折点为4,其成长函数上限为1/6×N3+5/6×N+1

不论任何情况,我们都只需要知道假说集合的转折点这一个量,即可知道成长函数的多项式上限是多少。

segment 2 证明成长函数mH(N)可用于替代假说集中假说数量M

我们希望用上限为多项式形式的成长函数mH(N)来替代原本的假说集合中所有假说的数量M。

即从认为所有的假说均为互斥的,考虑最糟糕的情况:

1

到考虑到假说之间的互相包含关系,采取成长函数这个有限的上限:

2

尝试以图像的方式说明这样做的好处:

pictorial proof

假设上图中的黑框代表数据集的空间,黑框内的任意一个点都代表一个数据,黑框包含了所有可能的数据。

我们所使用的数据集是由某未知概率分布P从此数据集空间所生成的,整个黑框代表概率1,其中每一个点都有一定地概率被选进我们所看到的数据集。

  • 针对一个特定的假说h,我们将其运用到每一个数据(即黑框内的每一个点),如果发现|Ein(h)-Eout(h)|> ε则将这个代表这个数据的点着色,如(a)所示。
  • 采用联合上限就相当于,认为所有的h均互斥,因此对假说集合H中的所有h都进行上述操作,则获得(b)中情况。
  • 采用成长函数作为上限,考虑进h之间的互相包含关系,对假说集合H中的所有h都进行同样操作,获得(c)中情况,这个上限又称为VC上限。

关键的一个问题在于,成长函数能够在多大程度上捕捉假说之间的互相包容关系。

考虑容器-弹珠模型:

Eout_thumb.png

如果我们有很多容器(h),用一个概率分布取一个样本进行检验,则其中出现|Ein(h)-Eout(h)|> ε情况的概率随容器数量上升而上升。

Eout(h)是无限的,无法知道的,因此尝试将其替换掉。

方法是:与其只取一个样本,用同样的概率分布再取一个样本进行检验,E'in(h)和Ein(h)之间是微弱地相关的(Ein(h)和E'in(h)针对的是不同的两个样本)。

如果|Ein(h)-Eout(h)|> ε则很有可能|Ein(h)-E'in(h)|> ε。

原先的问题:容器越多,其中出现|Ein(h)-Eout(h)|> ε情况的概率就越高。

如果只考虑这些Ein(h),随着抽取的样本越多,出现|Ein(h)-E'in(h)|> ε情况的概率也就越高。

即:越来越多假说带来的问题,与反复抽样带来的问题实际上是一样的。

反复抽样的问题就是上面以图片形式加以说明的。

针对数据量N的样本检验Ein(h)-Eout(h)就相当于,针对数据量为2N的样本检验两个不同假说Ein(h)-E'in(h)。

因此我们用成长函数对M进行替换并不能获得:

2_thumb.png

而是:

VC in

这个式子被称为VC不等式(The Vapnik-Chervonenkis Inequality)

补充林老师课里详细一些的证明过程:

Ein,E'in和Eout之间关系如下图所示:

prob

因此有:

prof1

prof2

prof3

prof4

课程地址:

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

 

Learning From Data Lecture 5 训练与测试

segment 1: 从训练到测试

将机器学习与人类学习做个比喻:在参加期末考试之前,你通过做复习题来提高对相关知识的掌握,以期高期末考试成绩。

  • 脑中掌握的知识的相当于算法选择出的假说h
  • 复习题相当于输入空间X
  • 复习题的答案相当于y

训练的过程相当于:

  • 通过做复习题并对照答案,你知道自己没有掌握哪些内容,相当于机器学习中的Ein(h)。
  • 然后以此为基础调整自己对知识的掌握,即调整h。

测试的过程相当于:

  • 参加期末考试,获得一个针对期末考试的Ein(h),用以估计g与f的差距。

区别在于:

  • 期末考试结果(Ein)与知识掌握情况(Eout)之间的误差大于容忍程度ε的概率只受两个因素影响,即容忍程度ε和期末考试的问题数量N。
  • 练习题的结果(Ein)与知识掌握情况(Eout)之间的误差大于容忍程度ε的概率还额外受到M的影响(可以理解为知识的复杂程度)。

我们的目的是将这个可能无穷大的M转变为一个有限的量。这样学习就变得可行了。

回顾M的来由:

假说集合H由多个h构成。

我们知道针对每一个假说h,假说在样本内外的误差大于容忍值的概率都有一个上限。

hoffeding

如果这些假说都是独立的,且假说集合H中一共有M个假说h。

那么最糟糕的情况是将这些概率上限联合起来,便获得:

multibinhoffding

这里的一个重要假设前提是:这些假说是相互独立的。

如果我们称假说h1的|Ein(h1)-Eout(h1)|>ε为坏事件B1

如此类推,则上面假设前提的含义便是B1,B2...BM是互斥的。

然而,实际上,B1,B2...BM是可能相互有重叠的。

如下面韦恩图所示:

QQ截图20131214105849

以感知器假说集合为例:

假设我们尝试学习得到的目标函数f如下所示:

target function

假设我们目前获得的一个假说h为:

hypothesis1 function1

则该假说的样本外误差Eout(h)为下图绿色部分所示:

hypothesis1 function2

要计算Ein(h),我们需要看的到这个h的样本是怎样的。

假设图中的点是获得h时所依据的样本,则Ein(h)为红色点的数量除以点的总数量。

hypothesis1 function3

考虑两个2维感知器,将刚才的感知器同绿色的感知器比较。

直观感觉上,因为他们非常接近,两者之间的重叠非常大。

hypothesis1 function4

实际上,两个感知器假说的样本外误差Eout之间的差别ΔEout不大,为下图中黄色部分所示。

而Ein之间的差别ΔEin则是黄色区间内点的数量除以样本内所有点的数量,差别很可能也很小。

eoutbetweendifferenhypothesis.png

我们关心的实际上是:

cared about

两个假说的样本内外误差之间的差距并不大,即,两个假说之间有大量的重叠。

即得到一个好消息:我们可以替换掉通过联合获得的可能是无限大的M。

下面要介绍我们尝试用于替换掉M的量。

这个量将被用于表达任何你选用的假说集合的复杂程度。

之前,在我们考虑假说集合的时候,是从整个输入空间出发的。

仍然以感知器为例:

因为输入空间是连续且无限的,任何一个点上的区别都会导致出两个不同的感知器,因此假说集合中假说的数量M也是无穷的。

如果我们现在将注意力只专注于样本,只考虑样本中的数据点。

那么只要是对样本中的点分类的结果一致的多个感知器,对样本中的数据而言,实际上是一样的。

考虑对于给定的样本,可以构造多少个二分法(dichotomies),每一种二分法都决定了将样本内的哪些数据点分类为+1,哪些分类为-1。

思考这样的二分法的数量有多少?

假设我们输入空间如下所示,点代表样本内的N个数据点,蓝色的线代表目标函数f,蓝色区域内的数据点为+1,红色区域内的点为-1:

1

假设我们现在有一张不透明的纸,纸的大小同输入空间一样大,纸上只有在样本中数据点的位置上是透明的。

2

假设我们将这张不透明的纸放在输入空间上,透过这张纸上的洞来看输入空间,则为如下结果:

我们只能看到被标记为+1或-1的样本内数据点,却无法看见目标函数f。

3

我们可以构造出无限多个2维感知器,将样本内数据分类成上面的情况,这些感知器在对样本内数据的分类结果上都是一致的。

即,如果仍然是透过这张不透明的纸来看被这些不同感知器分类的输入空间,看到的结果都是一致的。

4

只有当感知器将样本内的N个数据点分类结果不一致时,我们才会观测到变化。

5

定义二分法为迷你假说(mini-hypotheses):迷你的含义是,这些假说之间的区别只是针对样本内的数据点而言,而非针对整个输入空间,因此数量可能会是有限个。

  • 一个假说为 h : X → {− 1,+1 }
    假说是一个函数,将输入空间中的数据点映射至二元值域{-1,+1}
  • 二分法为 h : {x1, x2, · · · , xN} → {−1,+1}
    即将样本空间中的数据点映射至二元值域{-1,+1}

假说集合H的大小M可以是无限的。

而二分法的数量则是有限的,最大值为2N(对于每个数据点,一个二分法可能将其分为+1,也可能分为-1,且一共有N个点)。

我们希望能用这个2N来替代M

下面引入一个成长函数(growth function)的概念:

定义成长函数为:

  • 对于一个给定的假说集合H,计算这个假说集合H应用于一个包含N个数据点的样本时,最大可能的二分法数量。

growth function

对于2维感知器而言,设想一个极端的例子,让样本内所有的数据点都拍成一条直线,则最多只有2N中可能的二分法数量,远小于2N

但是最糟糕的情况仍然是2N

成长函数返回的是这个最糟糕情况下的上限2N

由此定义,对于2维感知器的假说集合,必然有:

example

以2维感知器的成长函数:

  • N=3时,最糟糕的情况是存在2^3=8种不同的二分法。
  • N=4时,2^4=16,但是即便是最糟糕的情况下,也只能生成14种二分法。

segment2 例子

例1:

假说集合正射线(positive ray)h(x) = sign(x-a)。

假说集合中的假说以不同的a取值加以区别。

正射线假说接受的输入为单个变量x,假说采用一个阀值a,如果x>a则返回+1,否则返回-1。

positive ray

假设样本空间有N个数据点,可以知道最多只有N+1种可能的二分法,即mH(N)=N+1。

例2:

假说集合正区间(positive interval)。

在区间中的数据点被分为+1,区间外的被分为-1。

不同的区间对应不同的假说h

positiveinterval_thumb.png

假设样本空间有N个数据点,可以知道对应的成长函数为:

positiveintervalgrowthfunction_thumb.png

例3:

假说集合凸集合(convex sets),不在是1维的,而是2维的。

下图是一个凸集合的例子:

convex set

如果二维平面上的数据点落在凸集合中,则被标为+1,否则反之。

设想一种极端的情况,假设所有的点都被放在一个圆的圆周上。

对于任何一种可能的情况(数据点+1,-1的所有可能性),链接所有+1的数据点均可构成一个凸多边形,只令凸集合包含的范围略微大于此多边形即可。

convex set 2

因此2N种二分法总是可以找到的,即mH(N) = 2N

注意到在正射线和正区间这两种假说集合中,二分法的数量均小于样本数据的最大可能情况。

  • 如果我们发现,对于某个样本而言,如果我们的假说集合所对应的二分法数量与样本数据的最大可能情况相等,便称我们的假说集合“打碎”(shattered)了样本数据。

下图是三种假说集合的成长函数比较:

compare

如果我们能用成长函数mH(N)替代原先不等式中的M,如果mH(N)是二项式形式,则N足够大时,或者对ε的要求不是太严苛,学习便是可能的。


segment 3 转折点

转折点(break point)的定义为:

  • 如果包含k个数据点的数据集均不能被假说集合H“打碎”,则称k是假说集合H的转折点。

如果假说集合H确实存在一个转折点k, 则必有:

  • mH(k)<2k

对于2维感知器,根据之前的讨论知道k=4。

对于包含数据点>k个的数据集,必然也不能被假说集合H“打碎”。

  • 对于正射线假说集,其转折点为2
  • 对于正区间假说集,其转折点为3
  • 对于凸集合假说集,其转折点不存在。

下节将进一步讨论的重要结论:

  • 如果存在转折点,则mH(N)必然是N的多项式。
  • 如果不存在转折点,则mH(N)=2N

课程地址:

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