机器学习读书笔记

机器学习读书笔记〔一〕机器学习的根本概念和学习系统的设计最近在看机器学习的书和视频，我的感觉是机器学习是很用的东西，而且是很多学科交叉形成的领域。最相关的几个领域要属人工智能、概率统计、计算复杂性理论、计算智能。机器学习的定义《机器学习》ByM.Mitchell第一章中和斯坦福机器学习公开课第一课都提到了一个这样定义：对于某类任务T和性能度量P，如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善，那么我们称这个计算机程序从经验E中学习。并举了一个例子，西洋跳棋学习问题：任务T：下西洋跳棋性能标准P：比赛中击败对手的百分比训练经验E：和自己进行对弈这个例子很清楚的解释了上面的定义，后面会以这个例子来说明机器学习的根本设计方法。设计学习系统选择任务根据上面的定义，我们就选择任务是学习下西洋跳棋。选择性能标准在世界锦标赛中的获胜百分比训练经验选择相比上面两个，这个选择要考虑的东西要麻烦得多，因为给学习器提供的训练经验对它的成败有重大的影响。一个关键的选择准那么是训练经验必须要能对学习器的决策提供直接或间接的反应。以下西洋跳棋为例子,提供直接反应的训练样例，即各种棋盘状态和相应的正确走子。提供间接反应的训练样例，很多过去对弈序列和最终结局。对于这种情况，存在着一个信用分配的问题，也就是考虑每一次走子对最终结果的奉献程度。这个问题很难解决，以后再来谈。(为什么？只要你下过棋，你就应该明白，就算一开始的走子是最正确的，后面下的很差一盘棋也会输掉，反之，一开始走得不是最正确的，但是也有可能反败为胜)第二个重要的准那么是学习期多大程度上可以控制训练样例序列。我的理解是获得训练样例的自动程度还是以下西洋跳棋为例子,1.训练样例全是“手工”获得的，即学习器需要的训练样例是人工选取的棋盘状态和该棋盘状态下的一次正确走子。2.训练样例是“半自动”获得的，即学习器需要的训练样例是它本身自己选取的棋盘状态〔它对这些棋盘状态感到困惑〕，然后由人工指导它该如何正确走子。3.训练样例是“全自动”获得的，学习器跟自己对弈来进行学习。这种情况下，又有两种情形：(1)试验它还未考虑过的全新棋局；(2)在它目前发现的最有效的路线的微小变化上对弈，来磨砺它的技能。第三个重要的准那么是训练样例的分布能多好地表示实例分布，而最终系统的性能P是通过后者来衡量的。一般而言，当训练样例的分布和将来的测试样例的分布相似时，学习具有最大的可信度。比方，西洋跳棋学习中性能指标P是该系统在世界锦标赛上获胜的百分比。假设说世界锦标赛上的选手都是万里挑一的高手，如果你给的训练样例都是一些初学者下的棋局，那么可想而知，学习器最终会在世界锦标赛上败得很惨。不幸的是，通常情况下学习的样例与最终学习系统被评估时使用的样例有一定的差异，比方世界级的西洋跳棋冠军可能不会有有兴趣和一个程序下棋。然而，目前许多机器学习理论都依赖于训练样例与测试样例分布一致这一假设，但在实践中这个假设经常是不成立的。假设我们决定系统将通过和自己对弈来训练。这个好处是不需要人工干预，只要时间允许，可以让系统产生无限多的训练数据。学习系统的具体设计步骤上面我们确定了学习框架：任务T：下西洋跳棋性能标准P：比赛中击败对手的百分比训练经验E：和自己进行对弈现在，有三个具体的内容要确定：(1)要学习的知识确实切类型(2)对于这个目标知识的表示(3)一种学习机制选择目标函数在机器学习中，要学习的知识确实切类型通常是一个函数，我们把它称为目标函数(TargetFunction)。在学习西洋跳棋中，我们要给出一个函数，它对任何给定的器具能选出最好的走法，假设记这个函数为ChooseMove，那么它的形式如下：ChooseMove:B->M其中B是合法棋局集合中的某一棋盘状态，M是走子的方法。这样，我们可以把提高任务T的性能P的问题简化为学习像ChooseMove这样某个特定的目标函数的问题。所以目标函数的选择是关键性的问题。事实上，直接学习ChooseMove是非常困难的。所以一般情况下，我们把一个评估函数作为目标函数。令这个函数为V，并用V：B->R来表示把任何合法的棋局映射到某一个实数值(R表示实数集合)。我们让这个V给好的棋局赋予较高的评分。如果这个V被成功学习，那么系统就很容易找到当前棋局的最正确走法。方法是，先产生每一个合法走子对应的所有后继棋局，然后用V来选取分值最高的后继棋局，从而选择最正确走子。现在一个重要问题是，目标函数V的准确值是多少？我们可以如下定义V(b)：(1)如果b是一最终的胜局，V(b)=100(2)如果b是一最终的败局，V(b)=–100(3)如果b是以最终的和局，V(b)=0(4)如果b不是最终棋局，那么V(b)=V(b’)，其中b’是从b开始双发都采取最优对弈后可到达的终局。我们发现上面的定义虽然貌似很有道理，但有一个问题，就是(4)中包含递归，因此运算效率不高〔因为它要搜索从b开始到达终局的所有路线〕，算法复杂度到达了实际不可操作的地步。所以V是一个理想目标函数，我们必须找到一个V的可操作的描述，实际上就是一个近似地刻画V的函数。由于这个原因，学习目标函数的过程本质上是函数逼近的过程。选择目标函数的表示如上所述，我们得到了理想的目标函数，但我们实际上是要学习一个近似函数V’来描述〔或表示〕目标函数。《机器学习》ByM.Mitchell书上说这个描述包含一个重要的权衡过程，一方面，我们总希望选取一个非常有表征能力的描述，以最大可能地逼近理想的目标函数V。另一方面，越有表征能力的描述需要越多的训练数据，使程序能从它表示的多种假设中选择。这里刚好与GeorgeF.Luger的《人工智能：复杂问题求解的结构和策略》中的一句话不谋而合：“AI研究者所关心的两个最根本的问题是知识表示和搜索，而表现力〔特征抽取的结果〕和效率〔特征抽取算法的计算复杂度〕是评价知识表示语言的主要尺度”。在机器学习中，目标函数就是知识，近似函数就是知识表示，后来我们可以知道，学习机制〔函数逼近算法〕就是搜索策略。所以，我觉得人工智能和机器学习本质上其实是相同的东西，只不过前者在更理论的层面上〔讨论意识和物理世界的关系〕，而后者更注重实践〔解决实际问题，例如下西洋跳棋〕。题外话到此，为了简化讨论我们为目标函数选择一个简单的表示法：对于任何给定的棋盘状态，函数V’可以通过以下棋盘参数的线性组合来计算：x1:棋盘上黑子的数量x2:棋盘上白子的数量x3:棋盘上黑王的数量x4:棋盘上红王的数量x5:被红字威胁的黑子数量(即会在下一次被红子吃掉的黑子数量)x6:被黑子威胁的红子的数量于是学习程序把V’(b)表示为一个线性函数V’(b)=w0+w1x1+w2x2+w3x3+w4x4+w5x5+w6x6其中，w0到w6为数字系数，或叫权，由学习算法来选择。在决定某一个棋盘状态值，权w1到w6决定了不同的棋盘特征的相对重要性，而权w0为一个附加的棋盘状态值常量。好了，现在我们把学习西洋跳棋战略的问题转化为学习目标函数表示中系数w0到w6值的问题，也即选择函数逼近算法。选择函数逼近算法为了学习V’(b)，我们需要一系列训练样例，它的形式为<b,Vtrain(b)>其中，b是由x1-x6参数描述的棋盘状态，Vtrain(b)是b的训练值。举例来说，<<x1=3,x2=0,x3=1,x4=0,x5=0,x6=0>,+100>;描述了一个黑棋取胜的棋盘状态b，因为x2=0表示红旗已经没有子了。上面的训练样例表示仍然有一个问题：虽然对弈结束时最终状态的棋盘的评分Vtrain(b)很好确定，但是大量中间状态〔未分出胜负〕的棋盘如何评分呢？于是这里需要一个训练值估计法那么：Vtrain(b)<-V’(Successor(b))Successor(b)表示b之后再轮到程序走棋时的棋盘状态〔也就是程序走了一步和对手回应了一步以后的棋局〕。这个看起来有点难理解，我们用当前的V’来估计训练值，又用这一训练值来更新V’。当然，我们使用后续棋局Successor(b)的估计值来估计棋局b的值。直观地讲，越接近游戏结束的棋局的V’越趋向精确。事实上，可以证明这种基于对后继棋局进行估计的迭代估计训练值的方法，可以近乎完美地收敛到Vtrain估计值。接下来，我们面临的就是如何调整权值的问题。首先我们要定义如何最正确拟合训练数据，一种常用的方法是最小误差平方和E：有很多算法可以得到线性函数的权使此定义的E最小化，这里我们选择一个称为最小均方法(LeastMeanSquares)的算法，它对可能的假设〔权值〕空间进行随机地梯度下降搜索，以使误差平方和E最小化。LMS如下对wi进行更新：对于每一个训练样例<b,Vtrain(b)>使用当前的权计算V’(b)对于每一个权值wi进行如下更新这里就是一个小的常数〔比方0.1〕，用来调整向梯度方向移动的步长，之所以称为梯度下降法，因为可以证明(Vtrain(b)-V’(b))xi实际上就是〔这里如有疑问，看最后的补充局部〕。最终设计到此为止，我们的学习系统设计已经完成，我们可以模块化描述这个学习系统，下面这张图来自《机器学习》ByM.Mitchell由图可以知道，一个学习系统一般由四个模块组成，以上面下西洋跳棋的学习系统为例：执行系统：利用V’来做决策，决定下一步走法的策略鉴定器：以对弈的路线或历史记录作为输入，输出一系列训练样例泛化器：以训练样例为输入，产生一个输出假设，即目标函数的描述V’实验生成器：以当前的假设V’作为输入，输出一个新的问题供执行系统区探索。在下棋的例子中可以是给出一个初始棋局参考资料：机器学习ByM.Mitchell人工智能:复杂问题求解的结构和策略ByGeorgeF.Luger斯坦福公开课机器学习第一课补充：上面提到这个梯度下降迭代式时这里要声明一下，准确地说(Vtrain(b)-V’(b))xi是只有一个训练样例时E的偏导当有m个训练样例时:此时，上面这个式子称为批梯度下降(BatchGradientDescent)，它一定会收敛到局部极小值〔实际上，线性回归的平方函数通常是一个二次的碗状函数，只有一个全局最小值〕。但是，它存在一个问题，就是每次迭代要输入全部的数据，当训练样例集很大时〔想象一个有几百万条记录的数据库〕，这显然是不划算的。因此，上文中使用了这个式子，这个又称为随机梯度下降〔StochasticGradientDescent〕,或增量式梯度下降，每次输入一个训练样例。但是，它不一定会收敛到局部极小值，可能会在局部极小值附近徘徊。

机器学习读书笔记〔二〕概念学习和归纳偏置感觉概念学习现在提得很少，可能是因为在机器学习的实际应用中很少用到，但是从概念学习中很容易引出归纳偏置的概念，而归纳偏置是个很重要的概念，因此这次会简单讲讲概念学习，着重于归纳偏置。可以看到归纳偏置对于机器学习的重要性。概念学习给定一样例集合以及每个样例是否属于某一概念的标注，怎样自动推断出该概念的一般定义。这一问题被称为概念学习。一个更准确的定义：概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。注意，在前面一篇文章《机器学习的根本概念和学习系统的设计》中提到，机器学习中要学习的知识确实切类型通常是一个函数，在概念学习里面，这个函数被限定为是一个布尔函数，也就是它的输出只有{0,1}〔0代表false，1〔代表true〕〕，也就是说目标函数的形式如下：f:X->{0,1}根据上面的定义，很明显概念学习属于监督学习的分类问题。举一个《机器学习》Bymitchell书上的例子来更好的理解概念学习。目标概念：Aldo〔人名〕会去海边游泳的日子，注意，这里这样描述不太好，很容易理解成我们要得到的表示目标感念的函数输出的是一串日期，不符合前面所说的概念学习的目标是推断一个布尔函数，实际上，这里是给出一个日子，基于这一天的各种属性，推断Aldo是否会在这天去游泳。下面的表1描述了一系列日子的样例，每个样例表示为属性的集合。属性EnjoySport表示这一天Aldo是否乐于进行水上运动，也是需要预测的属性；Sky、AirTemp、Humidity、Wind、Water、Forcast是的属性，就是要基于这些属性来推断Aldo是否会在这天去海边游泳。表1目标概念EnjoySport的正例和反例ExampleSkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes接下来要确定假设〔目标函数〕的形式，可以先考虑一个较为简单的形式，即实例的各个属性的合取式。可令每个假设为6个约束的向量，这些约束指定了Sky、AirTemp、Humidity、Wind、Water、Forcast的值。每个属性可取值为：由“？”表示任意本属性可接受的值。明确指定的属性值〔如warm〕。由“∅”表示不接受任何值。如果某些实例x满足假设h的所有约束，那么h将x分类为正例(h(x)=1)。比方，为判定Aldo只在寒冷的和潮湿的日子里进行随上运动〔并与其他属性无关〕，这样的假设可以表示为下面的表达式：<?,Cold,High,?,?,?>也就是要表达：ifAirTemp=Cold∧Humidity=HighthenEnjoySport=Yes那么最一般的假设是每一天都是正例，可表示为：<?,?,?,?,?,?>而最特殊的假设即每一天都是反例，表示为：<∅,∅,∅,∅,∅,∅>这里有几点要注意：1.<∅,∅,∅,∅,∅,∅>和<∅,?,?,?,?,?>、<∅,∅,?,?,?,?>等等其实是一样的假设，也就是只要假设中有一个属性为“∅”，那么这个假设就表示每天都是反例。2.你很可能会疑心，这里假设的形式为什么一定是属性的合取，假设属性Humidity有3种取值：High、Normal和Low，那么就无法表达Aldo会在湿度Normal或High的时候去海边游泳，因为这是一个析取式:ifHumidity=Normal∨Humidity=HighthenEnjoySport=Yes后面会讲，断言假设的形式为属性的合取是一种归纳偏置，它使得我们的学习器是有偏的，如果学习器是无偏的，那么它根本上无法对未见实例进行分类，这一点很重要，后面会慢慢解释。现在做一些术语定义，方便后面的表述：(1)待学习的概念或函数称为目标概念，记作c。(2)概念定义在一个实例集合上，这个集合表示为X。学习目标概念时，必须提供一套训练样例〔训练集，记为D〕，训练集中的人每个样例为X中的一个实例x和它的目标概念值c(x)〔如上面的表1中的example〕。c(x)=1，x称为正例(positive)；c(x)=0，x称为反例(negative)。可以用序偶<x,c(x)>来描述训练样例。(3)给定目标概念c的训练样例集，学习器面临的问题就是假设或估计c。使用符号H来表示所有可能假设的集合，也称为假设空间，对于我们的问题来说假设空间就是所有各个属性的合取式。H中的每个假设h表示X上定义的布尔函数,即h:X->{0,1}。机器学习的目标就是寻找一个假设h，使对于X中的所有x，h(x)=c(x)。归纳学习假设机器学习的任务是在实例集合X上寻找一个与目标概念c相同的假设h，然而我们对于c仅有的信息只是它在训练结合上的值。因此，归纳学习算法最多只能保证输出的假设能与训练样例相拟合。如果没有更多的信息，我们只能假定，对于未见实例最好的假设就是与训练样例数据最正确拟合的假设。这是一个归纳学习的根本假定。下面给出一个准确的定义：归纳学习假设任一假设如果在足够大的训练样例集合中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。那么现在该讲讲如何逼近目标函数，也就是先前在《机器学习的根本概念和学习系统的设计》中提到的搜索策略，即如何搜索假设空间H获得与目标概念c一致的假设h。假设的一般到特殊序、变型空间和候选消除算法假设的一般到特殊序许多概念学习算法〔如这里要讲的候选消除算法〕，搜索假设空间的方法依赖于一种针对任意概念学习都很有效的结构：假设的一般到特殊序关系。考虑下面两个假设：h1=<Sunny,?,?,Strong,?,?>h2=<Sunny,?,?,?,?,?>很明显，被h1划分为正例的实例都会被h2划分为正例，因此，可以说h2比h1更一般，h1比h2更特殊。现在要定义“比……更一般”这种关系定义：令hj和hk为在X上定义的布尔函数。称hjmore_general_than_or_equal_tohk〔记作hj≥ghk〕，当且仅当如果hj≥ghk∧(hk≠ghj)，那么就说hj严格的more_general_thanhk〔写作hj>ghk〕，可以得出≥g的一些简单性质：(1)自反性，hj≥ghj(2)反对称，假设hj≥ghk，那么hk非≥ghj(3)传递性，假设hi≥ghj且hj≥ghk，那么hi≥ghk很明显，≥g是假设空间H上的一个偏序关系。≥g很重要，因为它在假设空间H上对任意概念学习问题提供了一种有效的结构，可以更加有效地搜索假设空间。变型空间为了更好的说明变型空间，先给出一个定义：一个假设h与训练样例集合D一致，当且仅当对D中每一个样例<x,c(x)>都有h(x)=c(x)。记为马上要提到的候选现出算法能够表示与训练样例一致的所有假设。在假设空间中的这一子集被称为关于假设空间H和训练样例D的变型空间，因为它包含了目标概念的所有合理的变型。定义：关于假设空间H和训练样例集D的变型空间，标记为VSH,D，是H中与训练样例D一致的所有假设构成的子集。使用上面介绍到的一般到特殊序的结构，可以用更简洁的形式表示变型空间。变型空间可以表示为它的极大一般的和极大特殊的成员。看下面一个假设〔怎么得到的先不管〕，h=<Sunny,Warm,?,Strong,?,?>这个h和表1中的4个训练样例一致，实际上，这只是与训练样例一致的所有6个假设之一。下面的图1给出了这个6假设：图1图1中的6个假设构成一个变型空间〔6个假设都与训练样例集一致〕，箭头表示实例间的more_general_than关系。其中S就是极大特殊假设的集合，而G就是极大一般假设的集合，图上很容易看出，如果给定G和S那么很容易通过一般到特殊偏序结构来生成S和G之间的所有假设，因此只需要给定极大特殊假设的集合和极大一般假设的集合，就能够完整地表示一个变型空间。下面给出准确的定义：一般边界：关于假设空间H和训练数据D的一般边界〔generalboundary〕G，是在H中与D相一致的极大一般成员的集合。特殊边界：关于假设空间H和训练数据D的特殊边界〔specificboundary〕S，是在H中与D相一致的极大特殊成员的集合。变型空间表示定理：令X为一任意的实例集合，H为X上定义的布尔假设的结合。令c:X->{0,1}为X上定义的任意目标概念，并令D为任一训练样例的集合{<x,c(x)>}。对所有的X,H,c,D以及良好定义的S和G：候选消除算法有了上面的一些预备知识，现在可以来说明候选消除算法。算法的思路如下：获得变型空间VSH,D，首先将G边界和S边界分别初始化为H中最一般的假设和最特殊的假设。即:G0<-{<?,?,?,?,?,?>}S0<-{<∅,∅,∅,∅,∅,∅>}然后处理每个训练样例，使得S被一般化，G被特殊化，从而逐步缩小变型空间，消去变型空间中与样例不一致的假设。伪代码描述如下：候选消除算法，输入训练样例D，输出由G和S表示的变型空间G<-{<?,?,?,?,?,?>}S<-{<∅,∅,∅,∅,∅,∅>}foreachdinD

{

if(d==positive)

{

foreachginG

{

if(g与d不一致)

{

从G中移去g;

}

}

foreachsinS

{

if(s与d不一致)

{

从S从移去s;

foreachs的极小一般化式h

{

if(h与d一致&&G的某个成员比h更一般)

{

将h参加到S中;

}

}

从S中移去所有这样的假设：它比S中另一假设更一般;

}

}

}

else

{

foreachsinS

{

if(s与d不一致)

{

从S中移去s;

}

}

foreachginG

{

if(g与d不一致)

{

从G中移去g;

foreachg的极小特殊化式h

{

if(h与d一致&&S的某个成员比h更特殊)

{

将h参加到G中;

}

}

从G中移去所有这样的假设：它比G中另一假设更特殊;

}

}

}

}简单总结一下上面的算法。正例使得变型空间的S边界逐渐一般化，而反例扮演的角色恰好使得G边界逐渐特殊化。每输入一个训练样例，S和G边界将继续单调移动并相互靠近，划分出越来越小的变型空间。对表1执行候选消除算法，便可以得到图1的结果。使用不完全学习概念进行分类假设只提供了表1中的4个训练样例，没有更多的训练样例，现在要对未见过的实例进行分类。图1表示的变型空间仍包含多个假设，即目标概念还未完全学习到，但是仍然有可能对新样例进行一定可信度的分类。为示范这一过程，给出表2列出待分类的新实例：表2待分类的新实例InstanceSkyAirTempHumidityWindWaterForecastEnjoySportASunnyWarmNormalStrongCoolChange?BRainyColdNormalLightWarmSame?CSunnyWarmNormalLightWarmSame?DSunnyColdNormalStrongWarmSame?先看A，图1所示的当前的变型空间中的每个假设都将A分类为正例。由于变型空间的所有假设一致同意实例A为正例，学习器将A划分为正例的可信度，与只有单个的目标概念一样〔当然前提是假设了目标概念一定在假设空间中，且训练样例没有错误〕。事实上，只要S中的每个成员将实例划分为正例，就可以断言变型空间中的每个假设将其划分正例，因为由more_general_than定义，如果新的实例满足S的所有成员，它一定也满足这些更一般的假设。同样，B被变型空间中的每个假设划分为反例，可以放心地把B划分为反例，即使概念学习是不完全的。只要实例不满足G中的所有成员，那么该实例就可以被断言为反例。碰到实例C就要注意了，变型空间中半数将C划分为正例，半数划分为反例。因此，学习器无法可信的分类地这一样例，除非提供更多的训练样例。实例D在变型空间中被两个假设分为正例，被其他划分为正例。这个例子的分类可信度比A和B要小，又比C要大。投票选取倾向于将其分类为反例，所以可以输出拥有最大票数的分类，还可附带一个可信度比例以说明投票的倾向程度。〔注意，如果假定H中所有假设有相等的先验概率，那么投票的方法能得到新实例的最可能的分类〕现在，可以讲讲一个非常重要的概念，归纳偏置。归纳偏置如前所述，如果训练样例没有错误，初始假设空间包含概念目标时，如果提供足够多的训练样例，候选消除算法可以收敛到目标概念。前面提到，断言假设的形式为属性的合取，事实上是为了缩小需要搜索的假设空间的范围。这样做的一个后果是，有可能目标概念不在这样一个初始的假设空间中。如果想要保证假设空间中包含目标概念，一个明显的方法是扩大假设空间，使每个可能的假设都被包含在内。再次以EnjoySport为例子，其中将假设空间限制为只包含属性值的合取。由于这一限制，假设空间不能够表示最简单的析取形式的目标如“Sky=Sunny或Sky=Cloudy”。所以问题在于，我们使学习器偏向于只考虑合取的假设。无偏学习的无用性好吧，居然这种偏向可能使得假设空间漏掉了目标概念，那我们就提供一个表达能力更强的空间，它能表达所有的可教授概念。换言之，它能够表达实例集X的所有可能的子集。一般我们把集合X的所有子集的集合称为X的幂集〔powerset〕。假设AirTemp、Humidity、Wind、Water、Forcast都只有两种可能取值，Sky有三种可能取值，那么实例空间X包含了3×2×2×2×2×2=96种不同的实例。根据集合的知识，在这一实例集合X的幂集的大小是2^|X|，其中|X|是X的元素数目。因此在这一实例空间上可以定义2^96，或大约10^28个不同的目标概念，我们称包含了2^|X|个假设的这样一个假设空间是一个无偏的假设空间。先前我们将假设空间限制为只包含属性值的合取，那么只能表示1+4×3×3×3×3×3=973个假设。哈，看来我们先前的空间实在是一个偏置很大的假设空间。从感觉上讲，无偏的假设空间虽然一定包含了目标概念，但是它包含的假设的数量太大，搜索这样一个空间必然会很费时。然而，你马上会发现，这里还存在一个根本的问题：如果使用无偏的假设空间，概念学习算法将无法从训练样例从泛化，要想得到单个目标概念，必须提供X中所有的实例作为训练样例。我们根本不能从这样一个学习器中，得到对未知实例的分类。现在来看看为什么这么说。假定我们给学习器提供了3个正例(x1,x2,x3)以及反例(x4,x5)。这时，变型空间的S边界包含的假设正好是三个正例的析取：S:{(x1∨x2∨x3)}因为这是能覆盖3个正例的最特殊假设。相似地，G边界将由那些刚好能排除掉的那些假设组成。G:{否认符号(x4∨x5)}问题来了，在这一非常具有表达力的假设表示方法中，S边界总是所有正例的析取式，G边界总是所有反例的析取的否认式。这样能够由S和G无歧义分类的，只有已见到的训练样例本身。要想获得单个目标概念，就必须提供提供X中所有的实例作为训练样例。好吧，为了防止这个问题，我们只使用不完全学习得到的变型空间，像前面使用成员投票的方式对未见实例进行分类。遗憾的是，你马上会发现投票对于那些未见过的实例不起作用，为什么？未见实例会被变形空间中刚好半数的假设划分为正例，而被另一半划分为反例，原因如下，假设H是X的幂集，而x是某个未出现的实例，那么对于变型空间中一覆盖x的假设h。必然存在另一假设h’，它与h几乎相等，只不过对x的分类不同。而且，如果h在变型空间中，那么h’也在，因为它对于已往训练样例的划分与h完全一样。以上讨论说明了归纳推理的一个根本属性：学习器如果不对目标概念的形式做预先的假定，它从根本上无法对未见实例进行分类。这便是无偏学习的无用性。我们原来的EnjoySport任务中，候选消除算法能够从训练样例中泛化，惟一的原因就是它是有偏的，隐含假定了目标概念可以由属性值的合取来表示。由于归纳学习需要某种形式的预先假定，或称为归纳偏置〔inductivebias〕，我们可以用归纳偏置来描述不同学习方法的特征。归纳偏置还有一个更术语化的定义，这里就不提了。简单的讲，归纳偏置就是一个附加的前提集合B，以后还会提到，这个前提集合B有两种情况，第一种是对假设空间进行限定，就像候选消除算法那样；第二种是假设空间是完整的假设空间，但是进行不彻底的搜索，很多贪心算法都是这样的，如以后会提到的决策树算法。前一种归纳偏置叫做限定偏置，后一种叫做优选偏置。在研究其他的归纳推理方法时，有必要牢记这种归纳偏置的存在及其强度。一种算法如果有偏性越强，那它的归纳能力越强，可以分类更多的未见实例。当然，分类的正确性也依赖于归纳偏置的正确性。参考资料：机器学习ByM.Mitchell机器学习读书笔记〔三〕决策树决策树可以说是用的非常广泛的学习算法，对噪声数据有很好的健壮性，而且表达能力也很强〔机器学习读书笔记〔二〕中的候选消除算法只能表示属性的合取，决策树可以表示属性的析取〕。虽然决策树不是最好的学习算法，但是目前最牛哄哄的几个学习算法，如boosting和随机森林〔RandomForest〕在内部都使用了决策树，因此很有必要深入了解一下决策树。--------------------------------------------------------------------------------简介及决策树表示法在《机器学习》ByMitchell书中讲到决策树是一种逼近离散值目标函数的方法，也就是说决策树适用于分类(classification)问题，事实上，决策树也可以用来做回归〔regression〕,例如有名的CART〔ClassficationandRegressionTree，分类与回归树〕系统〔由Friedman和Breiman两个大牛提出来的〕。这里还是主要讲如何使用决策树学习来解决分类问题。下面的图是一个通常的决策树表示：由于以树的形式表达，决策树的一个优点就是让人一目了然，也很符合人的思维习惯〔人在做某个决定时，总会将一系列需要考虑的”因素”按某种重要性准那么先排个序，然后优先考虑该因素〕。图上是一个根据天气情况分类“星期六上午是否适合打网球“的决策树，每一个非叶子节点都指定了对待分类实例的某个属性的测试(如Outlook表示测试天气预报的情况，即询问天气预报的情况是晴天Sunny，阴天Overcast，还是下雨Rain？)，并且该节点的每一个后继分支对应于该属性的一个可能值；每一个叶子节点即为实例所属的分类。分类实例的方法就是从树的根节点开始，测试这个节点指定的属性，然后按照给定实例的该属性值对应的树枝向下移动。然后这个过程在新节点为根的子树上重复，直到到达叶子节点。举一个例子，假设实例的表示形式为<Outlook,Temperature,Humidity,Wind,PlayTennis>，令某一个具体的实例为x=<Rain,Hot,High,Weak,?>，在根节点上测试属性Outlook，该样例的Outlook=“Rain”，那么就沿着标记“Rain”的树枝向下移动到达新的节点Wind，于是再测试实例的属性Wind=“Weak”，沿着”Weak”树枝移动到叶子节点，叶子节点把x分类为Yes，也即目标属性PlayTennis=Yes。这里要注意，上图中的树为一棵多叉树，节点的后继分支数由节点上测试属性取值的个数决定。然而在计算机中，多叉树比拟难于表示，而二叉树易于表示，且二叉树有很多优良的属性，因此在编写程序时，一般以二叉树的形式来表示决策树，称为二叉决策树，也就是上面提到的CART系统。本质上，决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。例如上图表示的决策树对应于以下表达式：(Outlook=Sunny∧Humidity=Normal)∨(Outlook=Overcast)∨(Outlook=Rain∧Wind=Weak)--------------------------------------------------------------------------------决策树学习的适用问题通常决策树学习最适合具有以下特征的问题：1.实例是由“属性-值”对表示的：实例是用一系列固定的属性和它们的值来描述的〔如上面的例子中的x〕。最简单的决策树学习中，每一个属性只取少数的离散的值〔例如，Temperature取Hot、Mild和Cold〕。然而，很容易扩展到也允许处理值域为实数〔连续值〕的属性。2.目标函数具有离散的输出值，也就是说要解决的问题是一个分类问题。实际上，如一开始讲述的，决策树也可以用来做回归问题。3.可能需要析取的描述。4.训练数据可以包含错误。决策树对于噪声有很好的健壮性。无论是目标值属性的错误〔即分类错误〕还是描述属性错误。5.训练样例可以包含缺少属性值的实例：决策树学习甚至可以在有未知属性值的训练样例中使用。这个问题后面会进行讨论理解决策树算法思路的关键是决策树的归纳偏置〔归纳偏置的概念参见机器学习读书笔记〔二〕，它是学习算法的一个重要特征〕，这个偏置被称为奥坎姆剃刀〔occam’srazor〕。--------------------------------------------------------------------------------根本的决策学习算法大多数已开发的决策树学习算法是一种核心算法的变体。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。这种方法是ID3算法〔Quinlan1986〕和后继的C4.5算法〔Quinlan1993〕的根底。下面给出经典的ID3算法的概要：///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////ID3(Examples,Target_attribute,Attributes)输入：Examples即训练样例集。Target_attribute是这棵树要预测的目标属性。Attributes是除目标属性外供学习到得决策树测试的属性列表。输出：返回一棵能正确分类给定Examples的决策树伪代码表示：{创立树的Root节点if(Examples都为正)//决策树增长终止条件返回label=+的单节点树Rootif(Examples都为反)//决策树增长终止条件返回label=-的单节点树Rootif(Attributes为空)//决策树增长终止条件那么返回单节点树Root,label=Examples中最普遍的Target_attributes值A<-Attributes中分类Examples能力最好的属性Root的决策属性<-Aforeach(ainA)//a为属性A的每个可能取值a{在Root下加一个新的分支对应测试A=a令Examples(a)为Examples中满足A属性值为a的子集在这个新分支下加一个子树ID3(Examples(a),Target_attribute,Attributes-{A})}返回Root}////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////算法的过程并不复杂，就是不断选取某个属性对样例集划分直到决策树增长终止条件满足为止。终止条件为：1.节点是一个纯节点，即从某一分支到达该节点上所有的样例〔这些样例满足分支上的属性测试的值〕属于同一个分类。2.所有属性都已经被作为测试属性使用过了。总之，上面的算法就是一种自顶向下增长树的贪婪算法，在每个节点选取最好地划分样例的属性。继续这个过程直到这棵树完美分类训练样例，或所有的属性都已被使用过。现在有一个重要的问题是：如何选择在树的每个节点要测试的属性？这里顶一个统计属性，称为信息增益，它用来来衡量给定的属性区分训练样例的能力。--------------------------------------------------------------------------------熵和信息增益什么样的属性才是最好地分类样例的属性？直觉上讲，如果训练样例集被某个属性A划分，得到的所有子样例集〔每个子样例集中的子样例满足A的某个取值a〕如果都是“纯洁”的，也就是说各个子样例集中的子样例〔根据目标属性的取值〕都属于同一个分类，那么这个属性A绝对是对能够最好的区分样例的属性〔因为只要用这个属性对样例测试，那么就可以得到分类的结果〕。也就是说，根据某个属性对样例集进行划分后，得到的子样例集越”纯洁“，那么这个属性对样例集的区分能力越强。注意，这里不是很严谨，上面一段话中前后两个“纯洁”并不是相同的含义。第一个”纯洁”是一个二值判断，如果样例集中的子样例都属于同一个分类，那么样例集就是纯洁的，反之那么是不纯洁的。上面一段话中第二个“纯洁”是一种程度的描述，把它称为样例集的纯度〔也就是说第一个“纯洁”是第二个“纯洁”的特例，或者说极端情况〕。这里把比拟两个属性对样例集的区分能力转化为比拟使用两个属性对样例集划分后得到的子样例的纯度。如何刻画样例集的纯度呢？这里引入信息论中广泛使用的一个度量标准，称为熵〔entropy〕。给定样例集S，目标属性有c个不同的值，那么S相对于这c个分类的熵定义为：在熵的计算中，我们定义0log0为0。上式中,pi是S中属于类别i的比例。举一个例子：假设S是一个关于某布尔概念〔目标属性的取值有2个，“+”和“-”表示正样本和负样本〕的有14个样例的集合，它包括9个正例和5个反例〔我们采用记号[9+，5-]来概括这样的数据样例〕。那么S相对于这个布尔分类的熵为：Entropy([9+,5])=–(9/14)log(9/14)–(5/14)log(5/14)=0.94注意，如果S的所有成员属于同一类，那么S的熵为0。如果S中的正反样例的数量相等时，熵为1。下面的图刻画了布尔分类的熵函数随着p+(正样例占总样例的比例)从0到1变化的曲线从上面的图可知道也就是说样例集越“纯”的时候〔对应途中横轴两边的情况〕，熵越小。这个结论可以由只有两个分类的情况推广到有多个分类的情况。(信息论中的熵可以解释为用二进制位0和1对某个信息〔如字串〕进行编码所需的二进制位的长度，样例集越纯的时候，其中包含的信息越少，因此要编码样例集的目标值的时候所需的二进制位越少，熵就越小。对于熵的更详细解释会在后面讲到贝叶斯学习时给出)有了这个结论之后，我们就可以衡量属性对于样例的区分能力了。用某个属性划分样例集后，每个样例子集越“纯洁”，那么该属性对于样例的区分能力就越高，这样每个子集的熵就越小，这些子集组成的整个样例集的期望熵也就越小，也就是期望熵相对于原样例集〔在未用该属性划分样例前〕的熵降低地越多。这个熵降低的大小就称为信息增益。因此，要求出信息增益，首先求出样例集S在划分前的熵Entropy(S)；然后，样例集S被某个属性A划分为多个子集，求出每个子集S(a)的熵Entropy(S(a))，并求出样例集S被属性A划分后熵的期望∑|S(a)|/|S|*Entropy(S(a))；最后用Entropy(S)-∑|S(a)|/|S|*Entropy(S(a))得到由于使用这个属性划分样例导致的期望熵降低，这个就是一个属性A相对于集合S的信息增益Gain(S,A)。下面给出精确定义：注意，等式右边第二项描述的期望熵就是每个子集的熵的加权和，权值为属于S(a)的样例占原始样例S的比例。再次强调，信息增益Gain(S,A)是由于知道属性A而导致的期望熵的减少。换句话讲，就是给定属性A，得到的关于目标函数〔如何分类样例〕的信息量，或者说是知道属性A的值后对S的任意一个成员的目标值进行编码时，可以节省的二进制位数。--------------------------------------------------------------------------------决策树学习中的假设空间搜索机器学习读书笔记〔一〕中提到过，任何一个归纳学习算法可以被描述为从一个假设空间〔称为知识的表示〕中搜索〔称为搜索策略〕一个拟合训练样例的假设。上面提到的ID3算法搜索的假设空间就是可能的决策树的集合。ID3算法一种从简单到复杂的爬山算法遍历这个假设空间，引导这种爬山搜索的评估函数是信息增益度量。通过观察ID3算法的搜索空间和搜索策略，可以深入认识这个算法的优势和缺乏。ID3算法中的假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间。因为每个有限离散值函数可被表示为某个决策树，所以ID3算法防止了搜索不完整假设空间的一个主要风险：假设空间不包含目标函数。当遍历决策树空间时，ID3仅维护单一的当前假设。因为仅考虑单一的假设，ID3算法失去了表示所有一致假设所带来的优势〔这个与机器学习读书笔记〔二〕中变型空间的候选消除算法不同，候选消除算法维护了与当前的训练样例一致的所有假设的集合〕它不能判断有多少个其他决策树也是与现有的训练数据一致的。根本的ID3算法在搜索中不进行回溯。每当在树的某一层次选择了一个属性进行测试，它不会再回溯重新考虑这个选择。所以，它易受无回溯的爬山搜索中的常见风险影响：收敛到局部最优的答案，而不是全局最优的。后面会讨论一个扩展，增加一种形式的回溯〔后修剪决策树〕ID3算法在搜索的每一步都使用当前的所有训练样例，以统计为根底决定怎样精化当前的假设。使用所有样例的统计属性〔例如信息增益〕大大降低了对个别训练样例错误的敏感性。因此，通过修改ID3算法的终止准那么以接受不完全拟合训练数据的假设，他可以被很容易地扩展到处理含有噪声的训练数据。--------------------------------------------------------------------------------决策树学习的归纳偏置回忆机器学习读书笔记〔二〕中提到的，归纳偏置是一系列前提，这些前提与训练数据一起演绎论证未来实例的分类。要描述ID3算法的归纳偏置，应找到它从所有一致的假设中选择一个的根据。ID3选择在使用简单到复杂的爬山算法遍历可能的树空间时遇到的第一个可接受的树。从上面的描述可知道，ID3的搜索策略为:(a)优先选择较短的树而不是较长的。〔由简单到复杂的自顶向下的贪心算法决定〕(b)选择那些信息增益高的属性里根节点较近的树。〔由信息增益的属性选择度量决定〕上面的两点决定了ID3算法的归纳偏置，注意，它们并没有先后顺序，而是存在一种微妙的相互作用的关系，也就是说，虽然较短的树优先与较长的树，但ID3算法并不是总是选择最短的树，而又倾向于那些信息增益高的属性更靠近根节点的树，因此准确刻画ID3归纳偏置是很难的。下面给出一个近似的刻画。ID3归纳偏置的近似：较短的树比拟长的树优先。那些信息增益高的属性更靠近根节点的树优先。ID3算法的和第二章中讨论的候选消除算法显示出的归纳偏置之间有一个有趣的差异。1.ID3算法的假设空间是一个完整的假设空间，从ID3的归纳偏置可知，它不彻底搜索这个空间，而是从简单的假设到复杂的假设，直到遇到终止条件。因此ID3的归纳偏置完全是搜索策略排序假设的结果。2.变型空间的候选消除算法的搜索范围是不完整的假设空间〔只搜索由属性的合取表示的假设〕，但它彻底搜索这个空间，查找所有与训练样例一致的假设。它的归纳偏置完全是假设表示的表达能力的结果。总结一下，ID3算法的归纳偏置来自它的搜索策略，该策略假定某种假设胜过其他假设〔较短的假设比拟长的更优〕，因此称这种归纳偏置为优选偏置〔preferencebias〕或搜索偏置(searchbias)。相反，候选消除算法的偏置是对待考虑假设的一种限定。这种形式的偏置通常称为限定偏置(restrictionbias)或语言偏置(language)。通常，优先偏置比限定偏置更符合需要，因为它保证了位置的目标函数被包含在学习器工作的假设空间中〔要不然很可能白忙活一场〕。但在实际中，综合使用两者的学习系统是很常见的〔例如使用最小均方差〔优选偏