概念学习和一般到特殊序.ppt

2003.12.18*归纳偏置（3）无偏的学习器为了保证目标概念在假设空间中，需要提供一个假设空间，它能表达所有的可教授概念。换言之，它能表达实例集X的所有子集。问题：为什么2.3节中合取假设空间只能表示973个假设？第30页,共36页，星期六，2024年，5月2003.12.18*归纳偏置（4）EnjoySport的无偏形式带来的问题：概念学习算法无法从训练样例中泛化。要想获得单个目标概念，就必须提供X中所有实例作为训练样例使用2.6.3节讨论的部分学习的无效第31页,共36页，星期六，2024年，5月2003.12.18*归纳偏置（5）无偏学习的无用性归纳学习的一个基本属性：学习器如果不对目标概念的形式做预先的假定，它从根本上无法对未见实例进行分类归纳学习需要的预先假定，称为归纳偏置第32页,共36页，星期六，2024年，5月2003.12.18*归纳偏置（6）归纳偏置的精确定义(Dc?xi)?L(xi,Dc)需要在Dc?xi上附加怎样的前提，以使L(xi,Dc)能够演绎派生。L的归纳偏置定义为前提集合B，使所有的新实例满足： (B?Dc?xi)?L(xi,Dc)考虑对于实例集合X的概念学习算法L。令c为X上定义的任一概念，并令Dc为c的任意训练样例集合，L(xi,Dc)表示经过Dc训练后L赋予实例xi的分类。L的归纳偏置是最小断言集合B，它使任意目标概念c和相应的训练样例Dc满足： ?xi?X[(B?Dc?xi)?L(xi,Dc)]第33页,共36页，星期六，2024年，5月2003.12.18*归纳偏置（6）候选消除算法的归纳偏置{c?H}3个有偏程度不同的归纳学习算法机械式候选消除算法Find-S一种算法的有偏性越强，它的归纳能力越强，可以分类更多的未见实例。某些归纳偏置隐含在学习器中，有些表示为断言集合，可由学习器操作。第34页,共36页，星期六，2024年，5月2003.12.18*小结主要内容概念学习可看作有哪些信誉好的足球投注网站预定义潜在假设空间的过程假设的一般到特殊偏序结构可以定义在任何概念学习问题中，这种结构便于假设空间的有哪些信誉好的足球投注网站Find-S算法使用一般到特殊序，在偏序结构的一个分支上执行一般到特殊有哪些信誉好的足球投注网站，寻找一个与样例一致的最特殊假设候选消除算法利用一般到特殊序，通过渐进地计算极大特殊假设集合和极大一般假设集合发现变型空间候选消除算法缺少健壮性，第10章描述了几种基于一般到特殊序关系的概念学习算法，它们能够处理有噪声的数据和目标概念无法在假设空间中表示的情况归纳学习算法隐含了归纳偏置，候选消除算法的偏置是：目标概念可以在假设空间中找到。输出的假设和对新实例的分类可由归纳偏置和训练样例演绎推出第35页,共36页，星期六，2024年，5月2003.12.18*补充读物Bruneretal.1957和HuntHovland1963研究了概念学习以及一般到特殊的偏序Winston1970的博士论文将概念学习看作是包含泛化和特殊化操作的有哪些信誉好的足球投注网站过程SimonLea1973将学习的过程看作是在假设空间中有哪些信誉好的足球投注网站的过程Mitchell1977,1982提出变型空间和候选消除算法Haussler1988证明，一般边界的大小随训练样例的数目成指数增长Mitchell1979扩展了候选消除算法，以处理可预见的有限数量的误分类样例Sebag1994,1996展示了一种被称为析取变型空间的方法来从有噪声数据中学习析取概念...第36页,共36页，星期六，2024年，5月概念学习和一般到特殊序2003.12.18*2003.12.18*提纲概念学习给定某一类别的若干正例和反例，从中获得该类别的一般定义。有哪些信誉好的足球投注网站的观点在预定义的假设空间中有哪些信誉好的足球投注网站假设，使其与训练样例有最佳的拟合。利用假设空间的偏序结构算法收敛到正确假设的条件归纳学习的本质，从训练数据中泛化的理由第2页,共36页，星期六，2024年，5月2003.12.18*简介许多机器学习涉及到从特殊训练样例中得到一般概念。概念，可被看作一个对象或事件集合，它是从更大的集合中选取的子集，或在这个较大集合中定义的布尔函数。概念学习问题的定义给定一个样例集合以及每个样例是否属于某个概念的标注，怎样推断出该概念的一般定义。又称从样例中逼近布尔函数。概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。第3页,共36页，星期六，2024年，5月2003.12.18*概念学习任务一个例子目标概念，Aldo进行水上运动的日子，表示为布尔函数EnjoySport任务目的，基于某天的各属性，预测EnjoySpo