机器学习基石笔记1

机器学习基石笔记

2016年08月

版本记录

版本更新日期更新内容修改人

建立文档，台大机器学习基石课程笔记整

V1.02016.8.29蔡少阳

理。

目录

版本记录...............................................................II

第一讲、TheLearningProblem...........................................................................................1

1.1什么是机器学习？.................................................1

1.2机器学习与数据挖掘、人工智能、统计学的关系......................2

第二讲、LearningtoAnswerYes/No...................................................................................3

2.1Perceptron.................................................................................................................3

2.2PerceptronLearningAlgorithm(PLA)....................................................................3

2.3PLA算法是否能正常终止..........................................4

2.4数据线性不可分：PocketAlgorithm......................................................................5

第三讲'机器学习的分类学...............................................7

3.1根据输出空间来分类..............................................7

3.2根据数据标签(label)情况来分类.....................................7

3.3根据不同的协议来分类.............................................7

3.4通过输入空间来分类...............................................8

第四讲'学习的可行性分析...............................................9

4.1第一条准则：没有免费的午餐！(nofreelunch!)................................................9

4.2关于罐子里选小球的推论(概论&统计).............................9

4.3罐子理论与学习问题的联系........................................10

4.4RealLearning..........................................................................................................10

第五讲、学习的可行性分析(一些概念和思想)............................12

5.1回顾：学习的可行性？............................................12

5.2假设空间H大小：M...........................................................................................12

第六讲'归纳理论......................................................14

6.1TheoryofGeneralization........................................................................................14

第七讲、VC维理论.....................................................16

7.1VC维的定义....................................................16

7.2感知机的VC维..................................................16

7.3VC维的物理意义................................................18

7.4VC维的解释....................................................18

第八讲'噪音和错误....................................................20

8.1噪音和非确定性目标..............................................20

8.2错误的测量(errormeasure).................................................................................20

8.3衡量方法的选择.................................................20

8.4带权重的分类...................................................21

第九讲'线性回归......................................................23

9.1线性回归问题...................................................23

9.2线性回归算法...................................................23

9.3线性回归是一个“学习算法”吗？.................................24

9.4线性回归与线性分类器...........................................25

第十讲'逻辑斯谛回归..................................................27

10.1逻辑斯蒂回归问题..............................................27

10.2逻辑斯蒂回归的优化方法........................................27

10.3LRError的梯度................................................29

10.4梯度下降法....................................................29

第十一讲、线性分类模型................................................32

11.1三个模型的比较................................................32

11.2随机梯度下降(StochasticGradientDescent)...................................................33

11.3多类别分类(multiclassclassification)..............................................................34

11.4另一种多值分类方法............................................35

第十二讲、非线性转换..................................................36

12.1二次假设......................................................36

12.2非线性转换....................................................37

12.3非线性转换的代价..............................................37

12.4假设集........................................................38

第十三讲、过拟合-Overfitting..........................................................................................39

13.1什么是过拟合(overfitting).................................................................................39

13.2噪音与数据规模................................................39

13.3随机噪音与确定性噪音(DeterministicNoise)................................................40

13.4解决过拟合问题................................................41

第十四讲、正规化-Regularization.....................................................................................42

14.1正规化：Regularization.....................................................................................42

14.2WeightDecayRegularization..............................................................................42

14.3正规化与VC理论..............................................43

14.4泛化的正规项(GeneralRegularizers)..............................................................43

第十五讲、Validation.........................................................................................................45

15.1ModelSelectionProblem(模型选择问题)..........................45

15.2Validation.....................................................................................................................46

15.3Leave-One-OutCrossValidation（留一法交叉验证）.................49

15.4V-FoldCrossValidation（K-折交叉验证）..........................51

第十六讲、ThreeLearningPrinciples.......................................................................................53

16.1Occam'sRazor（奥卡姆剃刀定律）................................53

16.2SamplingBias（抽样偏差）......................................53

16.3DataSnooping（数据窥探）......................................54

16.4PowerofThree............................................................................................................54

参考资料..............................................................57

机器学习基石笔记

第一讲、TheLearningProblem

1.1什么是机器学习？

使用MachineLearning方法的关键：

①存在有待学习的“隐含模式”

②该模式不容易准确定义（直接通过程序实现）

③存在关于该模式的足够数据

(setofcandidateformula)

•assumegw"={hk},i.e.approvingif

•hi:annualsalary>NTD800,000

•h2：debt>NTD100,000(really?)

•/)3：yearinjob<2(really?)

・hypothesissetH:

•cancontaingoodorbadhypotheses

•uptoAtopickthe'best'oneasg

learningmodel=AandH

这里的f表示理想的方案，g表示我们求解的用来预测的假设。H是假设空间。

通过算法A,在假设空间中选择最好的假设作为g。选择标准是g近似于fo

unknowntargetfunction

f.x^y

(idea!creditapprovalformula)

(setofcandidateformula)

上图增加/"unknowntargetfunctionf:x->y”,表示我们认为训练数据D潜在

地是由理想方案f生成的。

第1页

机器学习基石笔记

机器学习就是通过DATA来求解近似于f的假设g。

1.2机器学习与数据挖掘、人工智能'统计学的关系

（1）MachineLearningvs.DataMining

数据挖掘是利用（大量的）数据来发现有趣的性质。

①如果这里的“有趣的性质”刚好和我们要求解的假设相同，那么ML=DM。

②如果“有趣的性质”和我们要求的假设相关，那么数据挖掘能够帮助机器学

习的任务，反过来，机器学习也有可能帮助挖掘（不一定）。

③传统的数据挖掘关注如果在大规模数据（数据库）上的运算效率。

目前来看，机器学习和数据挖掘重叠越来越多，通常难以分开。

（2）MachineLearningvs.ArtificialIntelligence（AI）

人工智能是解决（运算）一些展现人的智能行为的任务。

①机器学习通常能帮助实现AI。

②AI不一定通过ML实现。

例如电脑下棋，可以通过传统的gametree实现AI程序；也可以通过机器学习

方法（从大量历史下棋数据中学习）来实现。

（2）MachineLearningvs.Statistics

统计学：利用数据来做一些未知过程的推断（推理）。

①统计学可以帮助实现ML。

②传统统计学更多关注数学假设的证明，不那么关心运算。

统计学为ML提供很多方法/工具（tools）o

第2页

机器学习基石笔记

第二讲、LearningtoAnswerYes/No

2.1Perceptron

x=(xl,x2,xd)——features

w=(wl,w2,•・.,wd)—未知(待求解)的权重

对于银行是否发送信用卡问题：

approvecreditif“均>threshold

denycreditif上」“为<threshold

perceptron假设：

wx

/)(x)=signITii)一threshold|

sign是取符号函数,sign(x)=1ifx>0,-1otherwise

向量表示：

#X)

感知机(perceptron)是一个线性分类器(linearclassifiers)。线性分类器的几何表

示：直线、平面、超平面。

2.2PerceptronLearningAlgorithm(PLA)

感知机求解(假设空间为无穷多个感知机；注意区分下面的普通乘法和向量内

积，内积是省略了向量转置的表示)

初始w=0(零向量)。

第一步：找一个分错的数据(xi,yi),sign(w*xi)!=yi；

第二步：调整w的偏差，w=w+yi*xi；

循环第一、二步，直到没有任何分类错误，返回最后得到的w。

实际操作时，寻找下一个错误数据可以按照简单的循环顺序进行(xl,x2,xn)；

第3页

机器学习基石笔记

如果遍历了所有数据没有找到任何一个错误，则算法终止。注：也可以预先计算(如

随机)一个数据序列作为循环顺序。

以上为最简单的PLA算法。没有解决的一个基本问题是：该算法不一定能停止!

2.3PLA算法是否能正常终止

分两种情况讨论：数据线性可分；数据线性不可分。

(linearseparable)(notlinearseparable)(notlinearseparable)

注意PLA停止的条件是，对任何数据分类都正确，显然数据线性不可分时PLA

无法停止，这个稍后研究。

(1)我们先讨论线性可分的情况。

数据线性可分时，一定存在完美的w(记为wf),使得所有的(xi,yi),yi=

sign(wf*xi)o

可知：

力⑴>minynw^xn>0

下面证明在数据线性可分时，简单的感知机算法会收敛。

第4页

机器学习基石笔记

另t表示向量w的更新次数，初始时W°=0.每次遇见错误的数据才会更新+，

sign（w[x项））丰力⑺o力⑴w/x碇）<0

T；欠更新之后：~

nyw7=wf（wt+y^i）>uyv*]+m恤（为年"）之…

>wfw0+T*mi-rin{ynWfXn）

=T*miT^^WfX^

2

||Wf+i『=||wr+yn（f）xn（f）||

=||Wf/+2%⑺W/X"«）+B碌）X”⑴

W||Wf『+0+||%⑺x〃⑴

22

<||wr||+max||>xn||

22

Ikrll<IMTIF+maxn\\xn^^

<IIWoII2+T*maXnllXnll2p

2

<T*maxn\\xn\\"

所以产

Wfwr>r*Tnin7t（ywwn）>7*mg10nw—n）=.

www

IRfllllrll—ll/llllrll—||w^||Vr*maxn||xn||'

mirin（ywx）

71*7j--n-M-f---n-----------

||uy||*maxn\\xn\\

a*普是一个常数，所以可以得出结论：。

随着T增大，uy和卬丁的夹角越来越小，即w越来越靠近完美（理想）向量。。

而且量向量夹角余弦值不会大于1,可知T的值有限。由此，我们证明了简单

的PLA算法可以收敛。

2.4数据线性不可分：PocketAlgorithm

当数据线性不可分时（存在噪音），简单的PLA算法显然无法收敛。我们要讨

论的是如何得到近似的结果。

我们希望尽可能将所有结果做对，即：

N

T

wg—argmin£*sign(wxn)

Wn=1

第5页

机器学习基石笔记

寻找wg是■•个NP-hard问题！只能找到近似解。

PocketAlgorithm

initializepocketweightsw

Forf=0.1,•••

Ofinda（random）mistakeofwrcalled（xn（f）.yn（r））|

❷（tryto）correctthemistakeby

Wf+i_Wt+y.M.t）

❸ifwZ41makesfewermistakesthanw,replacewbywHT

...untilenoughiterations

returnw（calledWP0CKET）asg

与简单PLA的区别：迭代有限次数（提前设定）；随机地寻找分错的数据（而不是循环遍历）；只有当

新得到的w比之前得到的最好的wg还要好时，才更新wg（这里的好指的是分出来的错误更少）。由于计算

w后要和之前的wg比较错误率来决定是否更新wg,所以pocketalgorithm比简单的PLA方法要低效。

最后我们可以得到还不错的结果：wg

第6页

机器学习基石笔记

第三讲、机器学习的分类学

机器学习方法的分类学，通过不同的分类标准来讨论。

3.1根据输出空间来分类

(1)分类(classification)

①二值分类(binaryclassification)：输出为{+1,-1}□

②多值分类(multiclassclassification)：输出为有限个类别，{1,2,3,...,K}

(2)回归(regression)

输出空间：实数集R,或区间[lower,upper]

(3)结构学习(structuredlearning)：典型的有序列化标注问题

输出是一个结构(如句子中每个单词的词性)，可以成为hyperclass,通常难以

显示地定义该类。

需要重点研究的是二值分类和回归。

3.2根据数据标签(label)情况来分类

(1)有监督学习(supervisedlearning)：训练数据中每个xi对应一个标签yi。

应用：分类。

(2)无监督学习(unsupervisedlearning)：没有指明每个xi对应的是什么，即对

x没有labelo

应用：聚类，密度估计(densityestimation),异常检测。

(3)半监督学习(semi-supervisedlearning)：只有少量标注数据，利用未标注数

据。

应用：人脸识别；医药效果检测。

(4)增强学习(reinforcementlearning)：通过隐含信息学习，通常无法直接表示

什么是正确的，但是可以通过“惩罚”不好的结果，“奖励”好的结果来优化学习效

果。

应用：广告系统，扑克、棋类游戏。

总结：有监督学习有所有的yi；无监督学习没有yi；半监督学习有少量的yi；

增强学习有隐式的yi。

3.3根据不同的协议来分类

(1)批量学习-Batchlearning

利用所有已知训练数据来学习。

(2)在线学习-onlinelearning

通过序列化地接收数据来学习，逐渐提高性能。

第7页

机器学习基石笔记

应用：垃圾邮件，增强学习。

(3)主动学习-activelearning

learningbyasking：开始只有少量label,通过有策略地"问问题”来提高性能。

比如遇到xi,不确定输出是否正确，则主动去确认yi是什么，依次来提高性能。

3.4通过输入空间来分类

(1)具体特征-concretefeatures

特征中通常包含了人类的智慧。例如对硬币分类需要的特征是(大小，重量)；

对信用分级需要的特征是客户的基本信息。这些特征中已经蕴含了人的思考。

(2)原始特征-rawfeatures

这些特征对于学习算法来说更加困难，通常需要人或机器(深度学习，deep

learning)将这些特征转化为具体(concrete)特征。(de印learning的一个核心是，由

机器来完成特征工程。)

例如，数字识别中，原始特征是图片的像素矩阵；声音识别中的声波信号；机

器翻译中的每个单词。

(3)抽象特征-abstractfeatures

抽象特征通常没有任何真实意义，更需要人为地进行特征转化、抽取和再组织。

例如，预测某用户对电影的评分，原始数据是(userid,itemid,rating),rating是

训练数据的标签，相当于y。这里的(userid,itemid)本身对学习任务是没有任何帮助

的，我们必须对数据所进一步处理、提炼、再组织。

总结：具体特征具有丰富的自然含义；原始特征有简单的自然含义；抽象特征

没有自然含义。

原始特征、抽象特征都需要再处理，此过程称为特征工程(featureengineering),

是机器学习、数据挖掘中极其重要的一步。具体特征一般只需要简单选取就够了。

Lecture3:TypesofLearning

®LearningwithDifferentOutputSpacey

[classification],[regression],structured

•LearningwithDifferentDataLabelyn

[supervised],un/semi-supervised,reinforcement

•LearningwithDifferentProtocolf=>(xn.yn)

[batch],online,active

®LearningwithDifferentInputSpaceX

[concrete],raw,abstract

第8页

机器学习基石笔记

第四讲、学习的可行性分析

4.1第一条准则：没有免费的午餐！（nofreelunch!）

给一堆数据D,如果任何未知的f（即建立在数据D上的规则）都是有可能的,

那么从这里做出有意义的推理是不可能的！！doomed!!

如下面这个问题无解（或者勉强说没有唯一解）：

下面这题也是如此:

X„Yn—f(X〃)

000o

001X

010X

011o

100X

•X-{0.1}3,y={o,x）,canenumerateallcandidatefasH

再来看个"大神“的例子：

己矢口（5,3,2）=>151022,求（7,2,5）=>?

鬼才知道！！即使给你更多已知数据也白搭！因为有多种自造的规则可以解释

已知数据。

如何解决上述存在的问题？答：做出合理的假设。

4.2关于罐子里选小球的推论（概论&统计）

这里主要去看原课件吧。

比较重要的一个霍夫丁不等式（Hoeffding'sInequality）。

第9页

机器学习基石笔记

•inbigsample(Nlarge),visprobablycloseto〃(within

P[|z7-//1><2exp

•called'：gsInequality,formarbles,coin,polling,...

thestatement'//="'is

probablyapproximatelycorrect(PAC)

这里v是样本概率；u是总体概率。

霍夫丁不等式的直观解释是，当抽样数据量N足够大时，样本和总体的分布是

接近的(probablyapproximatelycorrect,PAC)。

4.3罐子理论与学习问题的联系

foranyfixedh,inbig'data(Nlarge),

in-sampleerrorEin(h)isprobablycloseto

out-of-sampleerror旦5(力)(withinF)

叫匠S)-Eout(/7)|>(]<2exp(-2时

sameasthe'bin'analogy...

•validforallNande

f

•doesnotdependon旦川力)，noneedto*knowEoui(h)

一fandPcanstayunknown

•七n(h)=Eout(h)'isprobablyapproximatelycorrect(PAC)

1

if*Ein(/7)-Eout(^)and,E^h)small

Eout(^)small=>h弋fwithrespecttoP

对于一个固定的假设h,我们需要验证它的错误率。根据霍夫丁不等式，当样本

数据N足够大时，样本错误概率和总体错误概率是接近的(PAC)。

4.4RealLearning

(1)baddataforoneh

霍夫丁不等式说，当只有一个h的情况下，baddata的概率很小。(baddata,即

对该h,训练数据和真实数据的分布不一致。导致，训练错误率和测试错误率相差

第10页

机器学习基石笔记

很远。)

BADDataforOneh

Eou[(h)andEin(h)faraway:

e.g.,Eou\big(farfromf),butEinsmall(correctonmostexamples)

DiD2。112605678Hoeffding

hBADBADPD[BADPfor/)]<...

Hoeffding:small

勘

[BADT>]=£P(P)■[BAD

allpossible。

(2)baddataformanyh

面对多个h做选择时，容易出现问题。比如，某个不好的h刚好出现”准确“的

假象。随着h的增加，出现这种假象的概率会增加。发生这种现象的原因是训练数

据质量太差。即对某个h,训练数据和真实数据的分布不一致。

BADDataforManyh

BADdataformanyh

<==>no'freedomofchoice,byA

<=>thereexistssomehsuchthatEOut(^)andEjn(/))faraway

A02。112605678Hoeffding

hiBADBADPpBADPfor/7i]<...

h2BADPDBADVforZ)2]<...

饱BADBADBADPpBADPfor/h]<...

BADBADPp[BADDfor

hM

all—

forMhypotheses,boundof「"BADP]?

对于某个假设h,当训练数据对于h是BADsample时，就可能出现问题。因

此，我们希望对于我们面对的假设空间，训练数据对于其中的任何假设h都不是

BADsampleo

Pp[BADV]

=P©[BADT)fororBADT>forh2or...orBADT>forhM]

<Pp[BADT)forh^]+PpfBADPforh2]+...+Pp[BADT>for。血

(unionbound)

<2exp+2exp(—2f2/v)+…+2exp(-23N)

=2Mexp(-2FN)

所以，当假设空间有限时(大小为M)时，当N足够大，发生BADsample的

概率非常小。此时学习是有效的。当假设空间无穷大时(例如感知机空间)，我们下

一次继续讨论。(提示：不同假设遇到BADsample的情况会有重叠)

第11页

机器学习基石笔记

第五讲、学习的可行性分析(一些概念和思想)

5.1回顾：学习的可行性？

最重要的是公式：

叫向n(g)-Eout(g)|>6]<2.M-exp(-2e2/v)

①假设空间H有限(M),且训练数据足够大，则可以保证测试错误率Eout约

等于训练错误率Ein；②如果能得到Ein接近于零，根据①，Eout趋向于零。以

上两条保证的学习的可能性。

可知，假设空间H的大小M至关重要，我们接下来会力求找一个H大小的

上界。

M存在重要的trade-off思想：

①当M很小，那么坏数据出现的概率非常小(从上面的公式可以看出)，学

习是有效的；但是由于假设空间过小，我们不一定能找到一个方案，可以使训练误

差接近零；②反之，若M很大，坏数据出现的概率会变大。

若假设空间无限大(比如感知机)，学习一定是无效的吗？这将在下面试图回答

这个问题。

5.2假设空间H大小：M

根据上面的公式，当M无限大时是无法有效学习的；主要是我们在计算M是

通过UNIONBOUND的方式，这样得到的上界太宽松了；实际上，由于不同假设

下发生坏事情是有很多重叠的，其实我们可以得到比M小得多的上界。

我们希望将这么多的假设进行分组，根据组数来考虑假设空间大小。

后面的讨论都是针对批量的二值分类问题。

这个思想的关键是，我们从有限个输入数据的角度来看待假设的种类。

①最简单的情形，只有一个输入数据时，我们最多只有两种假设：hl(x)=+lor

h2(x)=-1o

②输入数据增加到两个，最多可以有四种假设：

hl(xl)=l,hl(x2)=l;

h2(xl)=-l,h2(x2)=l;

h3(xl)=l,h3(x2)=-l;

h4(xl)=-l,h4(x2)=-l.

依次类推，对于k个输入数据，最多有2”种假设。

上面阐述的是理想、极端情况，实际上，在实际学习中我们得不到如此之多的

假设。例如，对于2维感知机(输入为平面上的点)，输入数据为3个时，下面这种

假设是不存在的：

第12页

机器学习基石笔记

(圆圈和叉代表两种不同分类，这种情形也就是线性不可分)

我们尝试猜测，当k很大时，有效假设的数量远小于24?

定义"dichotomy”:hypothesis'limited'totheeyesifxl,x2,xn

也就是相当于我们前面描述的，从输入数据的角度看，有效假设的种类。

输入规模为N时，dichotomies的一个宽的上界是2AN.

定义关于数据规模N的生长函数(growthfunction)：数据规模为N时，可能的

dichotomy的数量，记为m(N)»

下面列举几种生长函数：

①positiveraysoX=R(一维实数空间)，h(x)=sign(x-a),a是参数。

它的生长函数：m(N)=N+1；当N>1时，m(N)<2AN

②positiveintervalsoX=R,h(x)=1ifx>=aorx<b,-1otherwise.有两个参数a,b.

它的生长函数：m(N)=0.5NA2+0.5N+1；当N>2时，m(N)<2AN

③convexsetsoX=RA2(二维实数空间)，h是一个任意凸多边形，多边形内部

的为1,外部的为-1。

它的生长函数：m(N)=2AN

我们引入一个重要概念：突破点(breakpoint)：对于某种假设空间H,如果

m(k)<2Ak,则k是它的突破点。(也就是说，对于H,任意的k个点，无法被打散。)

对于上面提到的三个例子，①的突破点是2,3,4…②的突破点是3,4,...③没有突

破点。注意：如果k是突破点，那么k+l,k+2,...都是突破点。

对于感知机(2Dperceptons),我们不知道它的生长函数，但是我们知道它的第

一个突破点是4,m(4)=14<16

对于后面的证明，突破点是一个很重要的概念。

第13页

机器学习基石笔记

第六讲、归纳理论

上一讲重点是一些分析机器学习可行性的重要思想和概念，尤其是生长函数

(growthfunction)和突破点(breakpoint)的理解。

6.1TheoryofGeneralization

这一讲开篇再介绍一个界函数(boundingfunction)的概念：是指当(最小)突

破点为k时，生长函数m(N)可能的最大值，记为B(N,k)。

显然，当k=l时，B(N,1)=1;当k>N时，B(N,k)=2AN;当k=N时，

B(N,k)=2AN-1.

于是很容易得到Boundingfunctiontable:

k

B(N.k)123456...

1122222...

2134444...

3147888...

N41151616...

513132...

6163...

•

需要重点考虑k<N的情况。

我们考虑B(4,3),对应的数据量是4(xl,x2,x3,x4),从这四个数据的角度看应

该有B(4,3)个有效的dichotomieso

如果我们遮住其中一个数据(比如x4),余下的dichotomies去重后，不超过

B(3,3)个。(否则就违背了突破点在3)。显然，B(4,3)<=2*B(3,3)。

也就是说，当扩展为(xl,x2,x3,x4)时，(xl,x2,x3)上的dichotomies只有部分被重

复复制了(最多一次)。

于是可以设被复制的dichotomies数量为a,未被复制的数量为b。(0<=a,b<=

B(3,3))

可以知道,B(3,3)=a+b;B(4,3)=2*a+b.

我们假设a>B(3,2),这样，当扩展到(xl,x2,x3,x4)时,有大于B(3,2)的(xl,x2,x3)

上的dichotomies被复制。此时在(xl,x2,x3)中一定能够找到两个点被打散(shatter)

而且被复制了，由于被复制，对于这些dichotomies,x4可以取两个不同类别的值，

因此在(xl,x2,x3,x4)中一定能找到3个点被打散了。这与"3"是突破点相违背。假设

不成立，所以a<=B(3,2)。

所以，我们得到：B(4,3)=2*a+b<=B(3,3)+B(3,2).

对于任意N>k,利用上述思路，可以证明B(N,k)<=B(N-1,k)+B(N-l,k-l).

有了递推不等式，通过数学归纳法，我们证明下面的BoundingFunction(N>k):

第14页

机器学习基石笔记

/=0\/

、V/

highesttermNk-]

这个式子显然是多项式的，最高次事是k-lo

所以我们得到结论：如果突破点存在(有限的正整数)，生长函数m(N)是多项

式的。

既然得到了m(N)的多项式上界，我们希望对之前的不等式(如下图)中M进

行替换。

叫En(g)-E°ut(g)|>e]w2.M.exp(―2叫

然而直接替换是存在问题的，具体解释和替换方法这里不多说了，可以去看林

老师的课程。主要问题就是Eout(h),out的空间是无穷大的，通过将Eout替换为

验证集(verificationset)的Ein,来解决这个问题。最后我们得到下面的VCbound:

Vapnik-Chervonenkis(VC)bound:

P2/7€HS.t.|Ein(^)-Eout(^)|>

(4

VC界是机器学习中很重要的理论基础，我们在后面还会对VC维有详细解释。

到了这里，我们可以说，2维感知机的学习是可行的！

第15页

机器学习基石笔记

第七讲、VC维理论

上一讲的最后得到了VCbound,这一讲对VC维理论进行理解，这是机器学习

(最)重要的理论基础。

我们先对前面得到的生长函数和VCbound做一点小的修改。

provab：&loosely,forA/>2.k>3,

mH(N)

Foranyg=€and,statisticarlargeD,一・・■一

Pp[|Ein(g)-E0Ut(g)|>f]

Pp[3/7e7/s.t.

<4m(2N)exp(-蒙M)

ifkexists

<4exp

7.1VC维的定义

VCDemension:对于假设空间H,满足生长函数m(N)=2^N的最大的N,记

为dvc(H).

可知，dvc(