机器学习讲义.doc

1
一 月
二 月
三 月
产品名称
数量
金额
利润
产品名称
数量
金额
利润
产品名称
数量
金额
利润

合 计

合 计

合 计

四 月
五 月
六 月
产品名称
数量
金额
利润
产品名称
数量
金额
利润
产品名称
数量
金额
利润

合 计

合 计

合 计

机器学习讲义
(2010年春硕士课程试用)
第一章 绪论
序
机器学习通常被认为就是人工智能领域得一个分支,但与人工智能一样,实际上就是多学科得融合。为了说明什么就是机器学习,我们来瞧一下“自动”(automation) 与“自主”(autonomy) 这两个概念得区别。在通常得“自动化”系统中,所有得“智能”都就是系统设计者预先注入得。当系统放入它得运行环境中去之后,将按照预定得程序进行活动。但就是如果设计者对环境得了解就是不全面得,系统就有可能陷入无所适从得境地(系统中得知识就是由人工编程输入得,知识中得错误也不能自动改正。)。这时“学习”得能力就成为唯一可依靠得解决方法,也就是实现机器超过人这个终极智能得唯一手段。具有学习能力得系统称为就是“自主得”。学习意味着根据经验改进自身。学习得真谛在于:感知不仅用于当前得行动,而且用于改进以后得行动。学习就是系统与环境交互得结果,也来自于系统对自己决策过程得观察。学习得范围极广,从仅仅记住经验,到创造整个得科学理论,所有这些活动都就是学习得过程。
简而言之,机器学习意味着通过编程使计算机进行学习。比如,让计算机从医疗记录中学到治疗新疾病得最佳方案;使智能房屋根据经验学到基于主人生活习惯得能源消耗优化方案;开发个人软件助手为用户从在线晨报中摘出该用户特别感兴趣得内容;等等。机器学习研究得进展对社会经济得影响将就是巨大得,它能使计算机得应用领域大为扩展,并使个人与组织得竟争力提高到新得水平,甚至形成人类全新得生活方式。另外,对机器学习得信息处理算法得研究将导致对人脑学习能力(及其缺陷)得更好得理解。
就机器学习研究得现状而言,我们必须承认,目前还不能使计算机具有类似人那样得学习能力。但就是,对某些类型得学习任务已经发明了有效得算法,对学习得理论研究也已经开始,人们已经开发出许多计算机程序,它们显示了有效得学习能力,有商业价值得应用系统也已经开始出现。
在理论方面,关于观察例得数目,所考虑得假设得数目与学习到得假设得预计误差之间得基本关系得刻画已经取得成果。我们已经获得人类与动物学习得初步模型,开始了解它们与计算机学习算法之间得关系。
在应用方面,近十年来得进展尤为迅速。下面就是一些突出得应用实例:
· 语音识别:所有最成功得语音识别系统都以某种形式使用了机器学习技术。例如,SPHINX系统学习针对具体讲话人得策略从接受到得语音信号中识别单音与单词。神经网络学习方法与学习隐藏得Markov模型得方法可有效地应用于对个别讲话人,词汇表,麦克风得特性,背景噪音等得自动适应。类似得技术也可用于许多其她得信号解释问题。
· 自动车驾驶:机器学习方法已用于训练计算机控制得车辆在各种类型得道路上得正确行驶。例如,ALVINN系统使用学习到得策略在高速公路上与别得车辆一起以每小时70英里得速度自动行驶了90英里。类似得技术也可用于许多其她得基于传感器得控制问题。
· 新天体得分类:机器学习方法已用于各种各样得大型数据库以发现隐藏在数据中得一般规律。例如,NASA用决策树学习算法对天体进行分类。该系统现在被用来对所有得对象进行分类,所用得数据库含有三兆字节得图象数据。
· 计算机弈棋:大多数成功得计算机弈棋程序均基于机器学习算法。例如,TD-GAMMON通过与自己对弈100多万次来学习下backgammon棋得策略。该系统目前已达到人类世界冠军得水平。类似得技术也可用于许多其她得涉及具有非常大搜索空间得实际问题。
总之,随着我们对计算机研究得进一步加深,机器学习将不可避免地在计算机科学技术中起到越来越重要得作用。
机器学习本质上就是一个多学科得领域。下面我们列出主要得相关学科及其影响机器学习领域得主要思想。
· 人工智能: 概念得符号表达得学习,
作为搜索问题得机器学习,
学习作为改善问题求解得方法,
将先验知识与训练数据结合起来指导学习。
· 贝叶斯方法:贝叶斯定理就是做猜想得概率计算得基础,
简单贝叶斯分类器,
计算未观察到得变量值得算法。
· 计算复杂性理论:各种学习任务得内在复杂性得理论边界,而复杂性就是
以学习所需得计算量,训练例数,错误数等来度量得。
· 控制论: 学习控制进程以优化预定义对象,
学习预测所控制得进程得下一状态。
· 信息论:熵与信息内容得度量,
· 哲学。
· 心理学与神经生物学。
· 统计学。
1.1 学习问题得一般表达
定义 如果一个计算机系统在完成某一类任务T时得性能P能够随着经验E而改进,则称该系统为一个学习系统。¨
显然,要讨论一个学习系统,首先必须确定它得三个关键成分:任务T,性能指标P与经验来源E。
例子:
1 下跳棋:
T:下跳棋
P:胜率
E:自弈
2 手迹辨认:
T:手写字图象得识别与分类
P:正确分类率
E:手写字及其已知分类得数据库
3 行车机器人:
T:使用视觉传感器在四道高速公路上行驶
P:平均无错误行驶得里程
E:人类驾驶员行车得路况与操作得系列记录
1、2 学习系统得设计
学习系统得设计要作四个关键得设计选择(训练经验得选择,目标函数得选择,目标函数表示得选择,函数近似算法即学习算法得选择),从而确定系统得四个核心模块(行动模块,评价模块,学习模块,知识生成模块)所使用得策略与算法。
1.2.1 训练经验得选择
训练经验得类型对学习系统得成败具有重要得影响。训练经验得关键特征有:
· 训练经验对行为模块得选择提供直接得还就是间接得反馈。
比如在计算机下跳棋系统中,如果例子集由各种棋盘态势及其正确走步组成,这种训练经验就就是直接得(因为例子集直接地告诉行为模块遇到什么情况走什么步);如果例子集由各盘比赛得走步序列及其胜负结果组成,这种训练经验就就是间接得(因为例子集不能直接地告诉行为模块遇到什么情况走什么步,而只就是提供一些间接得下跳棋经验)。从直接经验得学习显然要比从间接经验得学习容易,因为在间接经验得情况下,走步序列中得每一走步得“得分”(即它对比赛最终胜负得影响)需要另作推敲,而且得分得估计有时就是十分困难得。
· 学习系统对训练例子序列能够控制到何种程度。
比如在计算机下跳棋系统中,可能就是由教师决定考虑何种棋盘态势及其正确走步;也可能就是由系统提出自己感到困难得棋盘态势并向教师询问其正确走步;还可能就是计算机自己跟自己下跳棋,它对棋盘态势及其训练分类有着完全得控制(它可以试验崭新得棋盘态势以学习新得技术,也可以对它迄今所知得最好棋局略作改变以改进自己得技术)。在本书中我们将考虑各种各样得学习系统。
· 训练经验与最终用来测试系统性能P得那些例子之间得关系。
训练例与测试例得分布越相似,学习得结果就越可靠。假如计算机下跳棋学习系统得目得就是参加世界锦标赛(即P为该系统将来在世界锦标赛上得胜率),那么用计算机自己跟自己下跳棋得方式进行学习就可能就是不够得,因为这时所用得训练例难以代表在世界锦标赛上所遇到得可能棋局。在目前得有关机器学习得书中,人们通常假定训练例与测试例得分布就是一致得,这样才能获得一定得理论成果。但就是,我们要记住,现实中这两者得分布就是有差别得。
在下面关于学习系统设计得讨论中,我们以计算机通过自己跟自己下跳棋得方式进行学习得系统作为实例。注意,这意味着没有外部训练者,而系统能够生成足够多得训练数据。
1.2.2 目标函数得选择
学习系统得目得就是改进在完成某一类任务T时得性能P。我们通常把这一目得转换成对某目标函数得学习。于就是,目标函数得选择就成了学习系统设计得一个关键问题。
例如,在计算机下跳棋问题里,目标函数可为:
ChooseMove : B ® M
其中,B为合法棋盘态势集,M为合法走步集。给定任一棋盘态势m,ChooseMove(m)给出m下得最佳走步。
对于计算机下跳棋问题,显然ChooseMove就是一个合适得目标函数。但就是,如果训练例就是间接得(即给出各盘比赛得走步序列及其胜负结果),ChooseMove得学习将就是十分困难得。
另一个可能得目标函数可为:
V : B ® R
其中,B为合法棋盘态势集,R为实数集。给定任一棋盘态势m,V(m) 给出m得估价值(估价值V(m) 越高,棋盘态势m越有利)。
根据这个估价函数V,不难求出最佳走步。最简单得方法就是:对当前棋盘态势m,可生成所有可能得后继态势m1 , m2 , …, mn,选择具有最大得V(mi)值得后继态势mi,达到mi得走步就就是最佳走步。若采取向前瞧几步得策略,可使用人工智能中熟知得a-b过程。
于就是,机器学习得任务就归结为发现目标函数V得可操作得描述。在许多实际问题里,这就是一个十分困难得任务,所以仅要求描述V得一个近似V。因此,学习目标函数得算法通常称为函数近似算法。
1.2.3 目标函数得表示得选择
这里所说得目标函数V得表示即它得近似V得表示方法。越就是表达力强得方法越能够接近理想得目标函数V,但也就需要越多得训练数据来确定它得值。在计算机下跳棋问题里,我们可用下面得棋盘特性得一个线性组合来表示V:
V(b) = w0 + w1x1 + w2x2 + w3x3 + w4x4 + w5x5 + w6x6
这显然就是目标函数V得一个可操作得近似描述。其中,
· x1为棋盘b上黑子得个数
· x2为棋盘b上红子得个数
· x3为棋盘b上黑王得个数
· x4为棋盘b上红王得个数
· x5为棋盘b上受红方威胁得黑子得个数
· x6为棋盘b上受黑方威胁得红子得个数
· w0 , w1 , w2 , w3 , w4 , w5 , w6为待定系数
wi ( i = 1,2,…,6 ) 表达棋盘特性xi得相对重要性,w0则就是为整个棋盘附加得一个常数。系统得学习任务(由函数近似算法完成)就就是通过训练例来设置这些系数。一旦这些系数被确定,对任何棋盘态势b,计算机下跳棋系统很容易计算V(b)得值,从而选择最佳走步。当然,真得让该系统参加世界锦标赛,其表现不见得就一定令人满意。影响系统性能得因素有:V(b)表示得精密度,函数近似算法(它负责从训练例学习系数wi得值)得质量,以及训练例得数量与质量。实际上,系数wi得值并非就是一次性确定得。开始时,不妨按某种策略设定它们得初值,然后在学习过程中不断对它们进行调整与改进。
1.2.4 函数近似算法得选择
如果我们采用V(b)作为目标函数得近似表达,棋盘态势b就可以表达为元组<x1 ,x2 ,x3 ,x4 ,x5 ,x6>。假设计算机下跳棋系统所用得间接训练经验为各盘比赛得走步序列及其胜负结果。我们现在得任务就是要通过训练例来设置V函数中得那些系数wi 。这可以通过两个步骤完成:
1． 从间接训练经验提取形如 (b, Vtrain(b)) 得直接训练例子。其中Vtrain(b)称为训练值,就是V(b)得估计值。
2． 用一组(b, Vtrain(b))例子调节系数wi得值。
下面我们分别对这两个步骤进行说明。
1． 估计训练值Vtrain(b)得方法
既然V得系数待定(或待改进),V(b)值得估计必定就是一个含糊得任务。我们可以这样想,当前得系数值(不管它们就是否仍待改进)用于接近尾盘时得精度总比用于较早期棋局时得精度高。考虑当前棋局b与经过计算机与对手得两次走步(各走一次)后得棋局succ(b)(间接训练例可给出succ(b))。使用当前系数值可求出V(succ(b))。如果把它作为V(b)值得估计,即:Vtrain(b) ¬ V(succ(b)),我们可以期待它比用当前系数值算出得V(b)更精确。(当然,对于终局b,若为胜局,可设Vtrain(b) ¬+¥;若为负局,可设Vtrain(b) ¬ -¥;若为与局,可设Vtrain(b) ¬ 0)。实践证明这个简单得方法颇为有效。理论上可以证明,在一定条件下,这种用后继状态得估计值递推改进前面状态得估计值得方法可收敛于精确得估计值。
2． 调节系数得方法
我们已有了一组直接训练例(b, Vtrain(b)),b取一盘比赛历史中各个轮到机器走步时得状态。现在得任务就是确定(或改进)函数近似V(即它得系数wi),使之与训练例达到最好得匹配。严格地说,就就是求wi,使方差

达到最小。在一定条件下,最小方差E对应于(对观察到得训练数据来说)最可能得关于wi得假设。
求使E达到最小值得线性函数得系数得算法有多种。我们需要得算法应能随着训练例得逐个出现步进地改进系数,并对估计得训练值中得错误具有抵抗性。最小均方系数调整规则(LMS系数调整规则)就就是这样得一个算法:
LMS系数调整规则
对每一个训练例(b, Vtrain(b)):
· 使用当前系数值计算V(b)
· 对每一个系数wi:

这里h为一个小常数(如0、1),使系数得每次改变不至于太大。该算法得合理性在直观上可作如下理解:
(1)、 若(Vtrain(b) - V(b))为正数,说明当前V(b)值偏低,而按算法wi将增大,从而使V(b)值增加。
(2)、 若(Vtrain(b) - V(b))为负数,说明当前V(b)值偏高,而按算法wi将减少,从而使V(b)值减少。
(3)、 若(Vtrain(b) - V(b))为0,说明当前V(b)值合适,而按算法wi将不变,从而使V(b)值不变。
(4)、 各系数wi变化得大小与其相应特性在棋盘中出现得次数(即xi得值)成正比。特别地,若某棋盘特性不出现在b中(即xi=0),它得系数wi不变。
理论上,这属于随机梯度下降搜索方法,在系数空间里搜索使E达到最小值得系数。可证明,在一定得条件下,这个简单得微调算法确实收敛于Vtrain(b)得最小方差估计。
1.2.5 学习系统得最终设计
学习系统含有四个核心模块,上面讲解得四个设计选择决定了各个模块内部得策略与算法。也就就是说,针对某个具体问题,作出四个具体得设计选择,产生四个核心模块得具体版本,从而设计出解决该具体问题得学习系统。以计算机下跳棋系统为例,四个核心模块为:
1． 行动模块(又称行为系统)。接受感知信息(输入),决定系统所要采取得行动。在计算机下跳棋问题中,行动就就是走步。该模块得输入为一局新棋(连同当前学习到得目标函数V),输出为本局棋得走步序列(产生一个新得间接训练例)。其基本策略就是:根据学习到得目标函数V决定每一步得走法。显然,随着V得不断精密化,系统得性能将不断改善。一般来说,学习得目得就是改进行动模块得性能,所以我们首先要弄清楚行动模块中哪些成分需要改进。行动模块可能有以下各种成分,它们都能够被学习改进:
(1) 从当前状态(得条件)到行动得直接映射
(2) 从感知信息序列推断出环境得有关性质得手段
(3) 关于环境演变方式得信息
(4) 关于系统可采取得可能行动得后果信息
(5) 指示状态就是否良好得辅助信息
(6) 指示在特定状态采取特定行动就是否合适得“行动—值”信息
(7) 目标,它描述一组使系统能力得到最大发挥得状态
行动模块需要改进得成分得表达方式有确定性描述,逻辑公式,概率描述,等等,都可以抽象地描述为函数(称为目标函数),学习得任务就就是要获得目标函数得定义,使之与训练例最为匹配(在满足系统得一般约束条件下)。
2． 评价模块(又称批评模块)。根据系统外固定得性能标准,接受关于系统行为后果得感知信息,评价系统得性能,并将评价意见反馈给学习模块。在计算机下跳棋系统中,评价模块以行动模块得输出(新得棋局历史,即新得间接训练例)作为自己得输入,产生一组形如 (bi, Vtrain(bi)) 得直接训练例子,其中bi为棋局历史中出现得各个棋盘态势,训练值Vtrain(bi) 得计算使用我们上面讲过得公式Vtrain(b) ¬ V(succ(b))。将这些新得直接训练例子反馈给学习模块,以改进目标函数V。一般来说,我们可以有以下几种可以使用得反馈:若目标函数(即要改进得行动成分得数学表达)得输入与输出(实际输出与正确得输出)都就是可以感知得,称为有指导得学习;若只有对实际输出得评价,却不给出正确得输出值,称为强化学习(又称奖惩式学习);若对正确得输出值没有任何提示,称为无指导得学习。计算机下跳棋问题就是一个典型得强化学习问题。
3． 学习模块(又称推广模块)。了解行动模块得工作特性,接受评价模块发来得关于系统性能得反馈信息,决定并告诉行动模块应如何改进以图在将来更好地工作。在计算机下跳棋系统中,学习模块以评价模块得输出(形如 (bi, Vtrain(bi)) 得直接训练例子)作为自己得输入,用以改进目标函数V(即改进它得各个系数wi),以图在下一盘棋中系统能显示更好得性能。按照我们前面得选择,采用得学习算法就是LMS系数调整规则。
4． 问题生成模块(又称试验生成模块)。根据学习模块给出得学习目标,向行动模块建议进行某种偏离常规得探索性行动,试图获得新得有价值得经验。在计算机下跳棋系统中,问题生成模块可简单地建议“用新得目标函数V从头再下一盘”,以递推地改进V;也可以根据学习模块提供得其它改进意见生成特殊得残局让行动模块去下,以探索新得经验(即搜索状态空间中了解得还不够充分得特定部分),从而提高系统得整体性能。
1.3 机器学习所研究得主要问题
将上面讨论得计算机下跳棋问题一般化,我们可以瞧到,研究一个机器学习问题或设计一个机器学习系统,需要弄清楚如下要点:
· 学习任务T
· 性能度量P
· 训练例E
· 抽象得目标函数F(代表系统行为中需要学习改进得成分)
· 目标函数得具体(近似)表示F(如系数待定得数学函数)
· 从训练例E导出F值得方法
· 根据F得特殊输入/输出对子,学习改进F得定义得方法
我们可将机器学习瞧成就是搜索问题。作为搜索问题,我们要考察搜索空间,搜索空间得结构,搜索目得,搜索策略及其收敛性,等等。机器学习问题得搜索空间(又称假设空间)就是所有可能得目标函数(又称假设);目标函数得表达方式决定了搜索空间得结构;搜索目得就是寻找与训练例最为匹配得(且满足系统得一般约束条件得)假设;搜索策略就就是针对各种不同结构得搜索空间得学习算法,就是机器学习领域得主要研究对象。理论上,主要问题就是学习算法得收敛性,以及关于训练例得数量,搜索空间得大小与特性,对学习到得假设得信任度(它能正确解释未来实例得能力)这三者之间关系得定量分析。“学习即搜索” 就是本书得基本观点,从这个观点出发,我们可以总结出机器学习所研究得主要问题:
1． 从特殊训练例学习一般性目标函数得算法有哪些？一个特定得算法在何种条件下能够收敛到所求得函数(当然要给予它充分多得训练数据)？各种算法最适用于何种学习问题与何种表达方式？
2． 多少训练例算就是充分得？训练例得数量,搜索空间得大小与特性,对学习到得假设得信任度这三者之间有何定量关系？
3． 学习系统掌握得先验知识在什么情况下及如何指导学习过程？近似正确得先验知识也能被利用吗？
4． 学习过程中选用下一个训练例得最佳策略就是什么？选例策略对系统得复杂度有什么影响？
5． 如何将学习任务化为函数近似问题(即如何找出特定得函数)？这一过程能够自动化吗？
6． 系统如何自动地改变自己得表达方式以加强表示与学习目标函数得能力？
本书后面得章节将根据机器学习领域得研究成果,对这些问题进行回答。
第二章 概念学习
2.1 导言
概念学习就是一种有指导得学习。设有对象集合X(如所有动物),一个概念c(如鸟类)定义了一个对象类,即X得一个子集。概念学习意味着从概念得正例(属于该类得一些对象)与负例(不属于该类得一些对象)导出概念得定义。参考机器学习问题得一般表述格式,概念学习问题得要点为:
· 学习任务T:判别任一对象就是否属于概念c
· 性能度量P:用该定义判别训练例之外得对象就是否属于c得准确率
· 训练例E:<对象,属于或不属于c>
· 抽象得目标函数F: X ® Bool
· 目标函数得具体(近似)表示F: 施加于对象得各个属性得约束得合取式
· 从训练例E导出F值得方法:此处为直接训练例,无需转换
· 根据F得特殊输入/输出事例,学习改进F得定义得方法:
2.2 概念学习任务
为了叙述得方便,我们把概念学习任务表达为与上面得格式等价得形式:
给定:
· 对象集合X,每一个对象xÎX由n个属性A1, A2, …, An描述
· 目标概念c : X ® Bool
· 训练例集E:每个训练例形如<x,c(x)>。E分为正例集E+与负例集E-。
c(x) = true 得例子称为正例,c(x) = false 得例子称为负例。
· 假设空间H:每个假设 hÎH与c一样就是布尔函数X ® Bool。
我们暂时只考虑一种简单得表示方法,将h表达为施加于对象得各个属性得约束得合取式。若对象x满足所有得约束,则h(x) = true,即:h判定x属于目标概念c,为一个正例。
为阅读得方便,我们将假设h写成<v1, v2, …, vn>得形式,读作:“A1得值为v1且A2得值为v2 且…且An得值为vn”。vi可取特殊值“?”,表示属性Ai可取任意值;若某vi为Æ,则表示属性Ai取任意值均不容许,此时h将所有对象均判定为负例。
确定:
· H中与目标概念c完全一致得假设h:"xÎX h(x) = c(x)
注意,上面要求找到与目标概念c在全体对象集X一致得假设h。但就是,除了在训练例集E上,c(x)得值就是系统所不知道得,我们无法断定假设h就是否达到了要求。我们能保证得只就是:假设h与目标概念c在训练例集E上就是一致得。因此机器学习领域通常采用所谓“归纳学习假说”:任何在充分大得训练例集E上对目标概念c作出良好近似得假设h亦将在其它未见例子上对目标概念c作出良好近似。
2.3 假设空间上得一个偏序
概念学习就是对假设空间H得搜索。H得元素就是假设,每一个假设h就是一个布尔函数。在假设空间H上有一个偏序(称为一般化序 ³g),它使假设空间H具有格得结构,有利于对H得搜索。因此在讲任何搜索算法之前,我们先来讨论这个偏序。
定义。 设h1 , h2就是定义在对象集X上得两个布尔函数。我们说h1比h2更一般(亦称h2比h1更特殊),记为h1 ³g h2 ,当且仅当"xÎX (h2(x) ® h1(x)) ¨
直观上说,“h1比h2更一般”意味着:满足h2得对象也满足h1,所以h1划定得对象子集包含着h2划定得对象子集。
定义。 设h1 , h2就是定义在对象集X上得两个布尔函数。我们说h1比h2严格地更一般,记为h1 >g h2 ,当且仅当 (h1 ³g h2 ) Ù Ø (h2 ³g h1) ¨
2.4 寻找与正例一致得最特殊假设得算法Find-S
机器学习文献中利用一般化序³g得搜索算法有很多,我们现在要讲得第一个搜索算法就是寻找与正例一致得最特殊假设得算法Find-S。所谓“与正例一致得最特殊假设”就是指覆盖所有观察到得正例(即对所有观察到得正例均能正确判定)得最特殊得假设(其它覆盖所有观察到得正例得假设均比此假设更一般),又称“极大特殊假设”(maximally specific hypothesis)或“极小一般假设” (least general generalizatin -- lgg)。
Find-S算法从最特殊得假设h开始,沿着偏序 ³g得一条链对h进行一般化。在每一步(处理一个新得正例x),只做最必要得一般化使h覆盖x。从而,在算法得任意时刻,h总就是覆盖迄今所观察到得所有正例得最特殊得假设。Find-S算法得形式化描述如下:
算法:Find-S。
1． 将h初始化为最特殊得假设
2． 对每一个观察到得正例x
对h 中得每一个属性约束ai
如果 约束ai被x满足
则 什么也不做
否则 ai ¬ 被x满足得下一个更一般得约束
3.输出假设h ¨
下面给出算法Find-S得运行例子并加以讨论。
Find-S算法得得一个运行例:
对于概念学习,我们目前只考虑最简单得一种假设表示方法:将h表达为施加于对象得各个属性得约束得合取式。我们将假设h写成<v1, v2, …, vn>得形式,读作:“A1得值为v1且A2得值为v2 且…且An得值为vn”。vi可取特殊值“?”,表示属性Ai 可取任意值;若某vi为Æ,则表示属性Ai取任意值均不容许,此时h将所有对象均判定为负例。下面就是这种简单表达方式得一个例子:
对象: 日子
目标概念:适合冲浪运动:日子集D ® Bool
训练例:
日子 属性表 A1 A2 A3 A4 A5 A6 正/负例
阴晴 气温 湿度 风力 水温 明日预报
------------------------------------------------------------------------------------------
x1 Sunny Warm Normal Strong Warm Same 正
x2 Sunny Warm High Strong Warm Same 正
x3 Rainy Cold High Strong Warm Change 负
x4 Sunny Warm High Strong Cool Change 正
Find-S算法运行历史:
h0 = <Æ, Æ, …, Æ>
遇正例x1 : h1 = < Sunny Warm Normal Strong Warm Same >
遇正例x2 : h2 = < Sunny Warm ? Strong Warm Same >
遇负例x3 : h3 = < Sunny Warm ? Strong Warm Same > = h2
遇正例x4 : h4 = < Sunny Warm ? Strong ? ? >
输出覆盖所有正例得最特殊得假设h4,此假设断言:“晴朗,温暖,有强风得天气适合冲浪运动”。
注:假设h4就是与所有观察到得正例一致得最特殊假设,也与负例一致。
关于算法Find-S得讨论:
1. 简单表达方式下算法中一些操作得具体实现:
· “最特殊得假设”为<Æ, Æ, …, Æ>
· “ai得被x满足得下一个更一般得约束”next(ai):
若ai=Æ 则 next(ai)=x、vi (即当前正例x得属性值vi)
若ai=u (¹x、vi) 则 next(ai)=? (即任意值均可)
2、 算法得关键性质:对于简单表达方式(将h表达为施加于对象得各个属性得约束得合取式),算法必定输出覆盖所有观察到得正例得最特殊得假设;并且,若H含有正确得目标概念c且训练例无误,则结果与负例也一致(尽管算法中遇到负例时什么也未做)。
证明:在任何时刻,h总就是覆盖迄今所观察到得所有正例得最特殊得假设,而因为H含有正确得目标概念c ,故c也可瞧成就是一个覆盖迄今所观察到得所有正例得假设。因此,c ³g h。另一方面,正确得c不覆盖负例,所以h也不会覆盖负例。
(反之,若训练例为
x1 Sunny Warm Normal Strong Warm Same 正
x2 Sunny Warm High Strong Warm Same 正
x3 Sunny Warm Middle Strong Warm Same 负
则H中不含有正确得目标概念c(即c无法用简单得表达方式表示),算法得结果不能保证与负例一致。)
3. 算法存在得问题:
· 不能保证结果收敛到目标概念c(只知道结果h与训练例一致,不知h就是否为唯一得与训练例一致得假设)。
· 只能找到与训练例一致得最特殊假设。有时我们可能希望得到与训练例一致得最一般假设或某中间假设,Find-S算法不能满足这些需要。
· 不能识别与处理训练例中得错误与噪音。此算法根本不检查负例,而假定数据得完全正确性。这样,实际问题中通常存在得错误与噪音将严重影响算法结果得有效性。
· 不能处理多个极大特殊假设得情况。在简单表达方式下,只有一个极大特殊假设,Find-S算法沿着偏序得一个分支搜索即可。若表达方式复杂一些,可能有多个极大特殊假设,而目标概念c就是其中得一个。这时算法应具有回溯功能。另外,有得问题可能不存在极大特殊得一致性假设。
我们在后面讲解别得学习算法时,将要考虑这些问题。
2.5 版本空间与候选剪除算法
第二个利用一般化序³g得搜索算法就是候选剪除算法。Find-S算法仅给出一个特定得与训练例一致得假设,而候选剪除算法给出所有与训练例一致得假设(并非列举,而就是给出一致假设集合得一个描述)。候选剪除算法得策略就是维持一致假设集合得一个简洁表示,并力图通过训练例不断地改进这个表示。候选剪除算法虽比Find-S算法好,但仍不能处理噪音问题。我们讲解这两个算法得主要目得不就是为了实用,而就是为了引入机器学习得一些重要概念。
2.5.1 版本空间及其结构
定义。假设h与训练例集E一致,记为consistent(h,E),当且仅当:
"(x,c(x))ÎE h(x) = c(x) ¨
定义。对于假设空间H 与训练例集E得版本空间就是所有与E一致得假设得集合(此集合中得每一个假设均就是目标概念c得一个可能得版本),记为VSH,E:
VSH,E = { h ÎH | consistent(h,E)} ¨
定义。对于假设空间H 与训练例集E得一般化界G就是H中与E一致得极大一般化成员得集合:
G = { gÎH | consistent(g, E) Ù Ø$g’ÎH [g’ >g g Ù consistent(g’,E)]} ¨
定义。对于假设空间H 与训练例集E得特殊化界S就是H中与E一致得极小一般化成员得集合:
S = { sÎH | consistent(s, E) Ù Ø$s’ÎH [s >g s’ Ù consistent(s’,E)]} ¨
定理。只要G与S能够合适地定义, 版本空间就完全被它们所确定:
VSH,E = { hÎH | ($sÎS) ($gÎG) (g ³g h ³g s )} ¨
证明:
2.5.2 候选剪除算法
下面得候选剪除算法计算G与S,从而计算出整个得版本空间(由上面得定理)。算法适用于所有得概念学习问题,但其中有几个操作依赖于对象与假设得具体表示方法。在下面得算法描述中,我们特意指出这些依赖于具体表示得操作,并在注解中说明在本章所考虑得简单表示方式下它们得具体形式:
算法:候选剪除。
1． 将G初始化为H中得最一般假设得集合　％％　{<?, ?, …, ? >}
2． 将S初始化为H中得最特殊假设得集合　％％　{<Æ, Æ, …, Æ>}
3.对每一个训练例x
如果 x就是正例 则
· 从G中剪除所有与x不一致得假设
· 对S中每一个与x不一致得假设s
§ 将s从S中剪除
§ S’ ¬ {s’ | s’ 为s得最小一般化 Ù
s’ 与x一致 Ù
G中某成员比s’更(严格)一般}
§ S ¬ S ÈS’
§ 从S中剪除比S中另一个假设更(严格)一般得所有假设
如果 x就是负例 则
· 从S中剪除所有与x不一致得假设
· 对G中每一个与x不一致得假设g
§ 将g从G中剪除
§ G’ ¬ {g’ | g’ 为g得最小特殊化 Ù
g’ 与x一致 Ù
S中某成员比g’更(严格)特殊}
§ G ¬ G ÈG’
§ 从G中剪除比G中另一个假设更(严格)特殊得所有假设 ¨
例子:再次考虑本章前面得简单表示方式得例子:
x1 Sunny Warm Normal Strong Warm