2023台大机器学习笔记.docx

台大机器学习笔记NTUMLl.学习问题机器学习的概念我们可以从人类的学习思维入手。人类的学习过程，是从观察出发，经过大脑内化以后，变成有用的技巧。机器学习,类似地，是我们希望能让电脑模拟类似的过程。这时，电脑的观察到的东西被称作是数据，而思考过程实际上是计尊过程，技巧则是增强某一方面的表现。因此，机器学习的过程是从数据出发，经过计算过程以后，最终获得某种表现上的增进那么为什么需要机器学习呢？想象如下的例子，给定一张照片，判断照片里的物体是不是一棵(大自然中的)树.如果我们不使用机器学习算法，就需要对“什么是树”做一个回答，给出树的定义，并且动手将这个定义实现为程序.传统的做法是按照规则进行判断，而将规则表述出来是很难的。然而，我们认识树的方法其实也是通过观察，经过经验的积累判断这个是树或者不是，并不是教条地从长辈那里学习判断规则。类似地，我们也可以编写代码，让机器自己从数据中学习树的判断方法.因此，机器学习是构建复杂系统的另一种方法机器学习在以下情况下尤其适用 当我们不敏前想好各种情况，手工编码规则时。例如要让机器人在火星上导航，而我们不可能提前想到它在火星上会遇见什么样的情况 当我们无法容易地定义问题的解决方案时。例如要做语音识别/视觉识别，而我们无法对音频信号做出准确定义 当人们需要做出快速决策时。例如高频交易 当要让机器服务于海量使用者时.例如糊艮务个性化定制因此,我们可以从三个关键点进行判断，看是否适合使用机器学习1 .问题应该是“可以学习的"，即存在一些潜在的模式，以及目标2 .这些规则难以清晰定义3 .手里掌握了对应的数据机器学习的应用机器学习目前在衣食住行四个方面都得到了广泛应用 衣：AbU-MoStafa201芬IJ用销售数据和对用户的调研结果构建推荐系统给用户推荐穿搭 食：Sadileketal.2013利用机器学习，以推特上的文本和地理位置信息为数据，判断餐厅的卫生状况 住：TsanasandXifara2012利用已有房间的特点和耗能，预测房屋的能源消耗 行：Stallkampetal.2012利用交通标志照片和对应的意义，来提升认识交通标志的准确率此外还有两个领域：教戴口娱乐 教育：系统根据学生的答题状况，有针对地提供题目让学生练习其薄的部分，同时将太难的题推后给出。即，给定一名学生的答题历史和一个题目，预测学生是否能作对这道题(KDDCup2010) 娱乐：系统根据用户的历史打分，预测用户对新电影的打分(KDDCup2011)机器学习的过程问题背景以银行信用卡发卡这一问题为例。假设银行收集了一些用户的基本信息,例如下表项目值年龄23岁项目值so女年薪20万人民币在所在地居住年数1工龄0.5负债额4万人民币银行要解决的问题是，对于这样的客户，是否应该给她发放信用卡问题的形式化描述为了更加形式化地描述这个问题，我们需要定义一些符号： 输入：X£X,例如上面的这些基本信息 输出：yY,是我们期望得到的答案。例如在上面的问题中就是“发"期不发” 目标函数：f：X一丫，朝划门期望学到，但是目前不知道的东西。是题隅的公式 数据：D=(x,y),仅2,丫2),，yn),是之前积累的记录 假设：g：X-Y,是机器从数据中学到的函数。我们通常都希望g的表现足够好，即gf注意这里g不一定等于f(事实上，我们永远也不知道真正的f是什么样子，只知道由f产生的数据D) 机器学习算法：A,是由D产生g的算法，可以理解为A会从各种不同假设hk(这里hk有好有坏)构成的集合H中拟题出来一个最好的g,使得gf»即A以D和H为输入，以g为输出。我们所讲的机器学习模型，指的就是A和H在有了这些记号以后，我们可以重新给机器学习下一个定义机器学习是使用幡计算假设g以逼近目标函数f的过程机器学习与其它名词机器学习与数据挖掘数据挖掘的f简单定义是使用海量数据中以找出一些有趣的现象或性质。这里，如果“有用的性质”就是“能够逼近目标函数的假设”，那么数据挖掘和机器学习是没有区别的。假如这两个概念只是有关联，那么这两者是相辅相成的关系传统上的数据挖掘还关注如何在大的数据库中进行有效计算.不过现在已经很难将机器学习和数据挖掘这两个概念分开了机器学习与人工智能人工智能要求计算机呈现出一些智能的行为。由于机器学习逼近目标函数的过程就展现了一些智能，因此我们可以说，机器学习是实现人工智能的一种手段.机器学习与统计学统计学是要使用数据做出推论，推测一些我们本来不知道的事实。考虑到假设g是推论结果，f是不知道的事情，那么可以说统计是实现机器学习的一种方法。但是传统统计学从数学出发,很多工具是为数学假设提供证明和推论。而机器学习看重的是如何算出结果。总而言之，统计学为机器学习提供了很多有力的工具NTUML2.学习判断是与非 本文作者:TingxunShi 本文链接:http:/txshi- 版权声明:本博客所有文章除特别声明外，均采用CCBY-NC-SA3.0许可协议.转载请注明出处！感知机假设集合上回说到机器学习的核心就是，使用算法A接收数据D,从假设集合（所有可能性）H中选出一个g,希望gf那么我们现在最关心就是，H应该是什么样的。以之前提到的银行审核发放信用卡的场景为例，假设我们把每个使用者定义为向量X,包含d个维度，例如Xl代表年龄，X2代表年薪，等等.我们可以将这些维度（因素）综合起来给使用者一个整体分数。如果这个分数超过了某个标准，那就给ta发放；否则拒绝发放.这样，我们需要给每个Xi,i1,.,CI）来赋一个系数Wi,如果特征对最后的影响是正面的，那么就给Wi正值，否则给负值。如果我们再规定一个阈值threshold,那么我们的决策方法就可以写为，如果cji=WiXi>threshold,就批准信用卡申请，否则就拒绝。Sign函数来求出y的值，具体地说，假设集合H中的每个元?h（x）= sign我们可以进一步地规定输出空间丫-l,+1,其中y=-1时表示拒绝，V=1时表示许可.这样做的好处是我们可以直接使用都有)下形式)fcZWiXi-thresholdi=l其中Sign函数的定义为Sign(X)=I+1if×>01-1ifX<0即对用户的所有属性做一个加权打分，看它是否超过阈值。如果超过，则批准；否则就拒绝（如果正好等于阈值，这种情况很少发生，甚至可以随机决定y是1还是1）.这里我们说H是一个集合的原因是，不同的W和threshold都对应了不同的h,所有这些可能性对应的所有h构成了最后的假设集合H.h这样的函数类型称为感知机（PerCePtrOn）,其中W称为权重。进一步地，假设我们把ThreQhOld看做是(-threshold)(+1),然后把+1 看作是o h(×)= sign么前面的j式形式可以作）"步的简化即WiXi-threshold11=sign=sign3J+(-threshold)(+1)WiXii=0=Si卯(WTX)这里W和X都看作是列向量，即维度为（d+1）1我们可以来看一个图例来加强理解。假如我们顾客的特征数（也就是前面说的属性维度）为2,那么我们可以把任意输入X画在一个平面R2±（类似的，如果特征数为d,那么每个输入X都可以在Rd空间表示，只是会对我们的可视化造成困难），每个输入对应平面上的一个点。这样，r2上的h都有如下形式：h（x）=sign（wo÷w×+w22）可以看出，每个h其实都对应了r2上的一条直线。感知机规定位于直线某一侧的样本都被判定为正例，另一侧的样本都被判定为负例。不同的权重会产生不同的直线，从而对顾客有不同的分类方式。假设我们用蓝色的圈。表示正例，红色的叉X表示负例，下图给出了两个不同感知机的图晒机的例子可以看出右边的感知机在训练集上效果更好，因为它对所有例子做出了正确分类。而左侧的敬机在训练集上表现稍逊(一个正例被误判为负，两个负例被误判为正)由于蝴机都对应于一个超平面，因此它也被称为是线性分类器(R2的超平面是一条直线，r'的超平面是一个平面，以此类推).感知机学习算法在我们知道了hH的形态以后，接下来的问题是设计算法A来选出最优的g来逼近理想的L尽管我们不知道f具体应该是什么，但是我们知道数据D是由f生成。因此我们有理由相信，好的g满足对所有我们已经收集到的数据，其输出与f的输出尽可能接近，即g(×n)=f(×n)=y11因此，我们可以先找一个超平面，至少能够对训练集中的数据正确分类。然而难度在于，H的大小通常都是无限的.一种解决方案是,我们可以先初始化一个超平面go(为了简单起见，将其以其权重WO代表，称为初始权重)我们允许这个超平面犯错，但是我们要设计算法，让超平面遇到D中的错分样本以后可以修正自己.通常我们可以将WO初始化为零向量0.然后，在每一步t,找到一个使Wt错分的样本(Xn(t),yn)。即有sign(wx)ytn(t)n(t)接下来我们试着修正Wl可以看到错分有两种情况：y本来应该是+1,但是横型判断出来是负值(I也就是说此时W与X之间的角度太大,因此需要把W往靠近X的方向旋转使它们的角度变小.可以通过让Wt+1-Wt+yn(t)Xn达到这个目的y本来应该是,但是模型判断出来是正值.也就是说此时W与X之间的角度太小，因此需要把W往远离X的方向旋转使它们的角度变大。考虑到符号，其实也可以通过让Wt+1-Wi+yn(t)Xn(t)达到这个目的因此，在第t+1时刻，我们总可以通过下式来修正WL即wt+l-Wt+yn(t)×n(t)下图给出了这两种情况的示例感知机学习算法(PerceptronLearningAlgorithm,PLA)就是重复上面的过程，直到没有错误发生为止。算法将最后得到的权重W(记做WPLA)返回为g.完整的写法如下感知机学习算法对t=0,1,1)找到一个使Wt错分的样本(Xn(t),yn(t).即有Si卯(WTX)ytn(t)n(t)2).以如下方法修正Wt：Wt+1-Wt+yn(t)×n(t)直到遍历了所有样本一遍以后都没有找到错误为止.注意这里“遍历一遍”不一定非得顺序遍历,只要遍历过样本的一个全排列即可。例如假如样本中有4条数据，可以按照诸如23,4.1或者3,2,1,4这样的顺序遍历讲到这里，我们可能会有以下问题：算法真的会停止吗？能否确定算法返回的gf?我“能下来会讨论这些问题。不过我在这里想首先对FUntime中的题目做一个详细解答。为了方便起见，简记y=y11(t),×=×11(t),W=Wt,代入Wt+1-wt+y“t)xn(t),有ywX=y(w+y×)×=(yw+y(y×)×=ywx+yxyx=yw×+yy××(.yisascalar)=ywx÷y2X22>ywx感知机的有效性与确定终止性回顾PLA算法的停止条件，它是在没有找到错误的时候才停止，这要求我们的数据可以用一条线将正例样本和负例样本分割开来(如果不存在这条线，PLA肯定是不可能停止的).这种条件叫做线性可分条件.接下来，我们需要证明：如果数据集的确是线性可分的，感知机是否总能找到一个超平面把数据恰好分开.假设数据集D线性可分，我们先证明存在一个超平面W使得对任意il,.,n,y=Sig11(w×这意味着对每个X,它与超fifii平面都有一定距离，即minywx>Onrfn其中WTX是点X到W的带符号的距离。如果它被放在了相对于超平面的正确一侧，那么这个值与其标签的乘积应该是正数，否则为fnnf负数.则在训练过程中遇到的所有错分点(Xn(t),y11(t)(假设在时刻t遇到)，肯定有yw×minywx>011(t)fn(t)nnfn我们可以先证明，Wl被(Xn(t),yn(t)纠正以后更加接近Wf.我们可以通过两个向量的内积来判断它们是否接近：两个向量越接近，内积越大(可以理解为两向量U和V越接近，其夹角越小，那么COSe越大，所以两者的内积Uv=uvCoS礴大)，则wfwt+=Wr(Wt+y1t)×n(t)WW+m11yWtXftnrnfn>wwt+0=rWt但是这里有一个漏洞，即内积变大不一定说明两个向量接近，因为向量长度变大也会导致内积变大。因此接下来我们要证明,修正黑窿fs碉麟要再弩生椽韵这艘到或嘱强霸产5三j颗鹏霸饕聋碱如果磨剪吗感，也tn(t)nn(t)tn(t)n(t)n(t)tn(t)是标量，因此wt+I2=wt+yn(t)×11(t)I2简记y=y11(),×=x(t),W=Wt,则IWt+iI2=(w+y×)(w+y×)=WW+2yW×+XtXw2+x2(.yw×<0)IwI2+max×11I2n即权重经过修正以后，其长度最多增加maxnIXnI2经由上面两个部分，假设权重的初始向量为O,我们可以求出经过T步更新最后得到的权重WT与Wf之间的夹角余弦值的下界.为了求这个值，只需求两个权重归一化以后内积的下界即可，即先看分子.由于初始Wo=0,因此由之前第一个证明的中间步骤，我们可以写出第一次更新、第二次更新后分子的下界,即WWIW10+minyW×ffn.nfnWTW2wWi+minyw×w0+2minyw×ffnf11fn11f11wwminywxfTnnfn类似地，对分母有wI2maxx112n因此，w；.wTmicywfIWflwIWfNTmaXnlXrJ2minyw'x,nnn=T*/-wtIvmaxn×n2按照FUnTime中的记法，记R 2=maXn x2 , P = minWTr>-Xn,则W：WTTWfIWIR由于向量除以其长度得到的是单位向量，长度为1,在这种情况下，两者内积越大一定意味着两者的夹角越小，距离越近。但是这里需要注意的是，两者的距离不会无限接近，到CoS=1时就会停止换f角度看，因为两个单位向量的内积最大值为1,因此从上面的不等式可推出L1>上Rp2即算法至多更新W步后一定会停止感知机在线性不可分数据上的应用由上面的证明，假设数据集是线性可分的，那么PLA算法最后肯定会停止，而且（对训练集）给出正确的分类。该算法非常容易实现，而且结束很快，适用于任意Rd空间.但是这个算法最大的问题是，它要提前假设训练集是训练可分的，而且我们不知道算法什么时候会终止（因为上面给出的上限中用到了Wf,而我们不知道它是多少一甚至不知道是否存在！（在线性不可分的时候该向量不存在）刃陷我们来考虑一个最坏的情况，即数据若的确是线性不可分的话，应该如何应对。由于数据产生的过程中可能会混入噪声，这使得原本线性可分的数据也可能因为噪声的存在而不可分。但是，一般情况下，噪声应该是一小部分，即我们可以退而求其次，不去寻找一个完美的超平面，而是去寻找一个犯错误最少的超平面，即NWg-argminynsign（w×n）Wn=l然而，求解这个问题被证明是NP难的，只能采用近似算法求解。例如，我们可以保存一个最好的权重，该权重到目前为止错分的数量最少.该算法称为“口袋法”，其完整细节如下设定初始权重W对时刻t=0,1,1 .随机寻找一个Wt错分的样本(Xn(t),y11(t)2 .试图通过如下方法修正Wtwt+1-W+yn(t)×n(t)3 .如果Wt+1犯的错误比W少,那么将W替换为Wt+1直到足够多次迭代完成.我们将W(称为WPOCket)返回为g注意在线性可分集合上也可以使用口袋法，算法也可以返回一个无训练误差的解。但是由于每次更新权重以后,都要在所有数据上使用新旧权重各跑一遍,来计算错分数量，因此口袋法的执行时间通常比原始PLA的计算时间长很多NTUML3.机器学习的类型 本文作者：TingxunShi 本文链接：http7xshi20170805NTUML-3-Types-of-Learning 版权声明：本博客所有文章除特别声明外，均采用CCBY-NC-SA3.0许可协议.转载请注明出处！根据输出空间Y分类二元分类问题重新回顾一下“是非题”的形式。为了解决这个问题，需要我们提供一批训练数据D,其中我们要指出对哪些用户发放信用卡，哪些不发.像这样答案只有两种可能性(“要”或“不要”)的问题称为二元分类问题，其输出空间丫通常用集合-1,+1表示，类似于“判断题这种问题类型的例子有很多，包括 要不要发信用卡 电子邮件是不是垃圾邮件 病人有没有生病 广告是否会赚钱等等。二元分类问题是机器学习中最基本也是最核心的问题，很多理论推导和算法模型设计都是从这一类问题出发。多元分类问题二元分类问题很容易进行扩展，即如果答案有多个离散的可能性，那么问题演变为多元分类问题.假设目标类别有K种，那么Y=1,2,一个典型的例子是对硬币进行分类，看投入的是1角、5角还是1元.这种问题类似于“选择题”。这种问题类型的例子包括 识别手写数字是0到9这十个数字中的哪一种 识别图片中的水果是哪一种水果 邮件的进一步分类,例如是垃圾邮件、社交网络邮件、重要邮件还是促销活动邮件等等回归问题如果将医疗领域中的问题对应到上述问题中,那么这两种问题可以对应如下： 二元分类问题：给定病人特征，判断病人是否患病 多元分类问题：给定病人特征，判断病人患的是哪种癌症但是还有一类问题，例如判断病人手术后多少天可以出院0这种问题的输出是整个实数集，或者实数集中的一个连续区间。这种问题通常被称为回归分析。此时丫R或丫=lower,uppercr.这种问题类型的例子包括 根据公司的状况，预测其次日股票价格 根据大气状况，预测明日气温回归问题是一种历史悠久的统计问题，也是机器学习领域里非常核心的问题结构化分析在自然语言处理（NLP）这个领域里，有一项任务是对于输入句子中的每个词标注其词性（PartofSpeech,POS）.例如输入“IloveML”，程序应该可以将tT标记为代词，“love”标记为动词，“ML”标记为名词.这种彳镑可以看作是一种多元分类问题，但是如果输入是以句子为单位，由于句子中有结构性，因此输出也是一个结构.这样的问题可以看做是一个巨大的多类别分类问题，各个类别是隐藏的，看不到，而且不同类别之间有联系，使得穷举所有可能性变得不可能。但是我们知道输出存在一定的结构性，并希望程序能够正确给出判定.这种问勉称为结构化分析，此时丫是一种结构.这种问题类型的例子包括 给定蛋白质数据，判断蛋白质的结构 给定语言文本，给出语法树根据数据标签yn分类有监督学习考虑在第一节中的硬币分类问题。我们可以将所有硬币的特征收集起来，设成Xn,同时可以将硬币的面额给出，称为yn这两部分可以一起给到机器学习的算法A里，得到g。这种每个特征组Xn都有对应的yn的学习问题称作有监督学习。这里“监督”的意义在于，对每个特征都可以给出对应的标签，是一种“完整”的教学。无监督学习如果对所有数据，都没有标签给出，机器也可以通过类似“自学”或者“自己研究”的方式将其归类。这种学习问题称作无监督学习”.注意这种自动分类（称为聚类）的方法并不一定能得到正确的类数，而且如何判断聚类结果的好坏也是一个难题。这种问题类型的例子包括 将文章按照主题归类 将用户聚合称为用户群当然，无监督学习不止聚类这一种方向，还包括了 密度估计，即给定X=×1,.,×n,判断哪里稠密哪里稀疏。例如给定一些带有地点的交通事故资料，判断哪里是事故多发区（有点像回归分析） 奇异点检测，即给定X=×1,.,×nf判断哪些是异常点。例如给定网络日志，判断哪些是爬取日志（有点像极端情况下的二元分类）无监督学习的目标比较分散，难以衡量算法的好坏半监督学习介于有监督学习和无监督学习之间，只有少量数据有标签，大部分标签都没有，使用算法判断健的类别。这类问题的特点是标记数据很贵（标签获取不容易）。强化学习类似于训练宠物的方法：当人们训练宠物时，无法直接告诉它给定讯号Xn以后期望的yn,但是可以在它做了错误的回应以后施加惩罚，通过这种方式告诉它这种做法是错的（当然也可以在它做了的正确的或者你不排斥的回应以后施加奖励）.即此时系统的输入包括了数据X,系统的行为y和奖惩函数goodness。这种问题类型的例子包括 广告系统：X为用户特征，y为给出的广告，goodness是该广告的收入.这样系统可以学到对给定用户应该给出什么广告 德州扑克：X为牌型和底池，y为叫牌策略，goodness是牌局结束后的收益。这样系统可以学到对给定局面的叫牌策略强化学习实际上是从一些隐含的数据中学习，这些数据通常是J顺序的根据学习方式f=（Xn,yn）分类批处理学习读进所有的数据,训练出来模型g,使用g来处理未知数据。批处理学习是最常见的一种学习方法在线学习每看到一个样本就做出预测，然后根据正确的标签对模型做出更新，让模型的效果越来越好。在线学习是一种循序渐进的学习方式。PLA就很容易被改写为在线学习方法，因为它看到一个错分样本就会更新权重.另外，强化学习通常都是在线学习，因为每次我们只能得到部分数据。主动学习批处理学习有点像填鸭式教育，在线学习有点像老师课堂讲授，但是这两种方式其实都是机器被动学习。近几年一种新提出的研究方式类似于让机器来主动提问，即对输入Xn来提问对应的yn由于机器提问可以有技巧，因此我们希望这种学习可以加速学习过程，同时减少对标签的需求。当标注样本匕阐昂贵的情况下，主动学习比较有用根据输入空间X分类具体特征这种情况下，输入XRd中的每个分量（称为特征）都有具体且复杂的物理意义。这些特征都包含了人类的智慧，称为“领域知识”，是机器学习能处理的最简单的输入原始特征假设要处理的是手写数字识别问题，我们可以懈入做一些分析，提取出具体特征，包括数字是否对称，笔画是否有弯折等等。但是，也可以直接将原始的每个像素的灰度值组合成一个256维向量（假设图片是16x16的）这个输入比具体特征要抽象一些，求解也更困难，不过这些数据里仍然包含了一些简单的物理意义。原始特征通常需要机器或者人来转换为具体特征，这个转换的过程称为特征工程抽象特征以之前提到的预测用户对电影评分的比赛为例，对于这个问题，输入XGNXN实际上是用户编号和电影编号组成的二元组,而这些编号对机器来讲没有任何物理意义，因此更加需要特征转换本系列课程主要关注二元分类问题或回归问题，有监督，使用批处理方式处理，数据都有具体特征NTUML4.机器学习的可行性本文作者：TingxunShi本文链接：http:/txshi-版权声明：本博客所有文章除特别声明外，均采用CCBY-NC-SA3.0许可协议.转载请注明出处！不可能学习的情况Vn = +1g()=?一个学习谜题可以说g(x)=+1,因为所有已知y11=+1的图形都是对称的。也可以说g(x)=-1,因为所有已知y11=1的图形左上角都是黑的。甚至可以找出更加复杂的规则，让g(x)取得+1或可以说，这是一道公说公有理，婆说婆有理的问题，无论怎么样都可以说得到的答案是错误的.即，这个问题不可学习.接下来看一个更加数学一些的例子：假设输入空间X=0,13,Y=o,×,已知的数据集D如下表所示Xny=f(×n)0000001X010X0110100X由于输入情况b匕较简单，可以列举所有可能的h,也就是H是一个有限集。我们能否学习到一个gH,使得gf?答案是，我们只能保证g在D中跟f一样.但是对于那些在D外的数据，类似于上面黑白格的例子，总可以找到一个f使其与g给出的答案不尽相同(甚至完全不同).但是，机器学习的目的就是要看算法在未知数据上的表现情况。因此可以说，如果f可以取任何形式，那么从D中学习模型以对D外的元素做判断，这件事是注定要失败的概率成为救世主事已至此,需要开动脑筋，想一想是否有工具可以帮助我们从已知推断未知。这里再看一个例子：假设有一个很大的罐子，里面装了不计其数的橙球和绿球，则是否有可能知道橙球的比例？由于无法一颗一颗地数，因此求这个问题很难，但是可以通过随机取样的方法来推断这个比例。例如假设从里面抓了10颗球出来，里面有3颗是橙色的，那么橙球的比例就可以估计为30%.推而广之，假设罐子中橙球的比例为P,绿球的比例为1一,这里是一个未知数。通过某种随机独立程序取样后观测到橙球的比例为V,绿球的比例为1-V,这里V是一个已知数，刃陷和V有没有联系？这时，无;去确定的说V就是IJ,因为也许罐子里只有5颗绿球，却有几百颗橙球，而这次随机抽样只拿到了这5颗绿球这种情况是可能发生的。但是可以退而求其次地说，和V在大部分情况下非常接近。准确地说，两者之间的关系可以用Hoeffding不等式来描述.即假设采样大小为N,为一个比较小的数，那么有pv->e2exp(-22N)即"v="这个结论"大概差不多是对的"(probablyapproximatelycorrect,PAC)HOeffding不等式对任何11和£都成立，而且不需要知道真实的值。抽样样本越多(即N越大)，或者界限越松(即越大)，则V的概率越大Funtime中，已知=0.4,取样数N=10,求取样后V0.1的概率上界.这时可以把设为0.3,代入Hoeffding不等式右侧可知上界为2exp(-2×0.32XIO)Fo.3306。m三如果实刷甑氏脸个概率应该为0.6°+IoXO£9x.40.046360即HOeffding不等式只能提供一个上界，并不能对概率做出准确预估概率与机器学习的联系我们可以把“罐中取球”的问题与机器学习问题建立联系，即 未知的橙球比例对应于学习问题中未知的目标函数f(x),或者也可以对应于,对给定新样本(测试数据)×,假设函数值h(x)是否等于目标函数值f(x) 罐中的所有球对应于学习问题中的数据点XX 取出橙球对应于h判断错误，即h(x)f(x)注意，这里h是给定的，对下一条也如此取 出绿球对应于h判断正确，即h(x)=f(×) 从罐中做大小为N的取样对应于学习问题中从数据集D=(×11,yn学习f(×n)因此，同样的道理，如果N足够大而且Xn满足独立同分布假设(iid),那么根据已知的错分情况h(xn)y11,就可以推断假设函数h在整个数据集上的错分概率h(x)f(×)如果记h对已知数据的错分情况(样本内错误率)为Ein,全集上的错分情况(样本外错误率)为EOUt,就会有Ein(h)=:h(×11)y11=Eout(h)=Ex-Ph(×)f(×)同理套用Hoeffding不等式，在N足够大的情况下,Ein(h)和EOUt(h)之间相差超过£的概率为PEin(h)-E0Ut(h)I><2×p(-2e2N)即也可以说h的样本内错误率“大概差不多"相当于其样本外错误率，Ein(h)EOUt(h)。因此，如果h的样本内错误率很小，其样本外错误率也不会很大。在X全都是通过分布P产生的前提下，可以说hfo那么，如果算法A能够从H中选择到了Ein足够小的h,其返回为g,那么我们能否说gf?如果对给定的hfEin足够小，而且A真的把h当做g返回，那么g=f是PAC的。但是如果A被写死了，无论给定什么数据集都要返回h作为g,那么Ein(h)其实往往并不是最小的，此时gf反而是PAC的.这意味着真正的学习不是让A返回固定的h,而是要让A在解空间H中搜索.不过这提供了一个验证的思路，即可以选出一些未在训练过程中使用的历史数据送给某个候选模型h,在这之上观测其表现如何.概率与真正学习的联系真正的学习过程中，我们不会只有一个h来验证，而是要在H=hi,.,*中做出选择。假设找到了一个h在训练集上表现完全正确，是否应该把它选择为g?先不考虑这个问题。假设有150个人，每个人掷同一枚硬币5次，如果有一个人能连续扔出5个正面，那么这是否意味着这枚硬币不是均匀的？答案是不可能.因为假设硬币均匀，由150人每人掷5次，至少有f人扔出连续5个正面的概率是1一(斗>50>99.那么返回刚才的例子，这意味着h即便在训练集上全对，也不能确定它就比其它的h'好(可能大家都是瞎猜)。假设将造成Ein和EoUt相差比较大的取样称为“不好的采样”，可以看到当存在选择的时候，选择会恶化不好的采样(即让你选到错误h的概率变得很大).同样的道理,也可以把Ein(h)和EOUt(h)差得特别K的数据称为“不好的数据”.注意HOeffding不等式只能保证h遇到“不好的数据”的概率不是很大。事实上，每个h都会有对应的一些数据D,成为“不好的数据"，例如下表DlD2D1126D5678hiBADBADh2BADh3BADBADBADBADBAD从上表可以看到，给出的这四条数据里，只有第1126条是“好的”数据，其余的都会给不同的h带来麻烦。接下来的问题是，如果对某条数据Di,只要存在H使得Di是hJ不好的唾”，那就称该数据为“不好的数据”，那么对所有D,如果算法A能够自由选择数据，则算法遇上“不好的数据”的概率有没有上界答案是有的。使用事件的并的概率的不等式，假设IHl=M,可以做如下推导pdBADd=pdBADdforhorBADDforh2or.orBADDforhMpdBADdforhi÷pdBADDfOrh2+pdBADdforhM2exp(-22N)+2exp(-262N)+.+2e×p(-262N)=2mexp(-22N)即在假设集H为有限集，数据量足够的情况下，每个h都是安全的，即无论A如何选，其返回的g都会有Ein(g)=EOUt(g)是PAC的.所以，最理性的A会选择Ein(hm)的那个假设由数返回为g但是当M无限大时，如何证明机器学习是可行的？这个问题留在接下来的课程中解决到此为止，台大机器学习课的第一个部分已全部结束。这一部分解决的是机器何时能够学习的问题NTUML5.训练vs.测试本文作者：TingxunShi 本文链接:http7txshi-20170814NTUML-5-Training-versus-Testing 版权声明：本博客所有文章除特别声明外,均采用CCBY-NC-SA3.0许可协议.转载请注明出处！再谈Ein与EOUt上回提到，如果有足够多的根据统计方法生成的数据，而且H是有限集，那么问题是可学习的。即如果假设集H的基数是有限的，记为M,而且有样本量N足够大,那么对任意算法A选出来的g,都会有EOUt(g)Ein(g)同样的道理，如果A找到的g满足了Ein(g)0,那么有PAC地EOUt(g)0,也就是说此时学习是可能的。需要注意的是,要想单纯地通过训练让Em(g)0是很容易的，只需要把每条数据对应的标签记住就好.但是研究机器学习算法的目的是在于要让模型在未知的数据上一样表现良好，因此才需要有测试的过程来验证是否有EinEouu这里再回顾一下之前几讲讲过的东西： 第一讲主要是强调，我们希望机器学习能够找到一个g使彳短接近目标函数f.这个目标可以改写为EOUt(g)Oe 第二讲讲的是，如何寻找一Tg,使得Ein(g)0 第三讲施加了f前提条件,即主要讨论批处理、有监督的二元分类问题 第四讲则证明在假设集有限、样本量足够的情况下，有EOUt(g)Ein(g)这样第二讲做的工作可以联结到第T井提出的目标实际上核心是两个问题 到底EOUt(g)和Ein(g)会不会接近.如果答案是否定的，那么第T井和第二讲的内容就无法连接 能否让Em(g)尽可能小那么IHl=M跟这两个问题有什么关系呢？可以分两个情况讨论： M比较小的时候，第一个问题能够满足，因为“坏事情”发生的概率(即Em和EOUt不接近的概率)有上界2mexp(-22N)M小意味着上界小，即Ein和EOUt大部分情况下会接近。但是此时算法的选择有限，很难找SI一个让Ein接近0的5 匕较大的时候，由于有足够的选择，因此可以找到g让Ein尽量小，但是“坏事情”发生的概率会大大增加，对两者接近的把握变弱如果就这么看，那么M=8是不是T牛特别不好的事？感知机会不会并不可用？回顾之前Ein和EOUt不接近这一事件概率的上界，有PEin(g)-Eout(g)l><2Me×p(-22N)这里可以先把无穷大的数M替换为一个有穷的数RlH看看，即pin(g)-Eout(g)l>e72mHe×p(-22N)如果换完以后之前的性质仍然成立，那么就可以用有穷的mH来替换无穷的M。这样就可以证明在无限假设集上学习的可行性，并为之后决定如何选择正确的假设集提供支持有效线性分类器的数量重新回顾一下对假设hm所谓”坏事情“这一定义的概念。如果对分类器hm有Ein(hm)-Eout(hm)>,瓣K为坏事件Brn会发生。由于假设集合比较大，为了让算法A能自由选择,需要计算任一坏事件发生的概率，即求出PBlorB2or.orBhJ的上界。在最坏的情况下，每个Bm都不互相交叠，所以由事件并的概率上界定理，有pbiorB2or.orbm<PbJ+PB2+.÷Pbm当M=8时，由于是无限多个概率连加，因此这个上界有可能也是无限大的值，至少会是一个很大的值，会大于1,所以这个上界就没有实际意义了.问题出在哪J晚？回顾上界定理中取到上界的条件，是所有子事件互不交会。但是这个现象在当前讨论的问题中很难出现。相反地，对于相似的假设hih2,其EOUt是相似的，而对大部分D甚至其Ein是相等的。可以通过考虑之前提到的感知机的例子来理解这个结论.对于一个已知的感知机，如果将其稍微旋转或平移一点，就会得到一个新的战机。这两个感知机只会对那些处于旋转或平移经过的区域中的点给出不同的分类结果