人工智能7机器学习方法.ppt

第10章机器学习方法 一 常见学习方法分类 依据学习策略划分二 常见学习方法分类 依据获取知识的类型划分三 两种归纳学习方法 概念学习法 决策树学习法 第10章机器学习方法 一 常见学习方法分类 根据学习策略 1机械式学习 死记式学习 能够直接体现它的特点 这是一种最简单的 最原始的学习方法 也是机器的强项 人的弱项 2指导式学习 这种学习方式是由外部环境向系统提供一般性的指示或建议 系统把它们具体地转化为细节知识并送入知识库中 在学习过程中要反复对知识进行评价 使其不断完善 机器学习方法 3类比学习 类比也就是通过对相似事物进行比较所进行的一种学习 它的基础是类比推理 也就是把新事物和记忆中的老事物进行比较 如果发现它们之间有些属性 过程 是相同的 那么可以 假定地 推断出它们的另外一些属性 过程 也是相同的 例如 桥bridge 概念建立 狗 与 狼 概念的建立等 已知 偶数 偶数 偶数 用类比的方法求证 奇数 奇数 奇数 4解释学习 它不是通过归纳或类比进行学习 而是通过运用相关的领域知识及一个训练实例来对某一目标概念进行学习 并最终生成这个目标概念的一般描述 这个一般描述是一个可形式化表示的一般性知识 机器学习方法 二 常见学习方法 获取知识的类型 1归纳学习 概念学习 决策树 2基于范例的学习3人工神经网络4统计学习 支持向量机 5遗传算法 马尔柯夫模型 高级人工智能 1归纳学习方法 归纳学习是一种符号学习 在已知正例 反例的基础上归纳出一个通用的概念 归纳学习能得到新的概念 创立新的规则 发现新的理论 归纳学习并不 保真 是 保假 的 是从特殊到一般 而演绎是保真的 如 麻雀会飞 燕子会飞 等归纳 鸟会飞 鸵鸟不会飞 归纳学习依赖于经验数据 因此又称为经验学习 归纳学习的基本操作 泛化 例化 泛化 扩展一假设的语义信息 使其能包含更多的正例 应用于更多的情况 例化 用于限制概念描述的应用范围 归纳学习方法 概念学习给定某一类别的若干正例和反例 从中获得该类别的一般定义 概念 搜索的观点在预定义的假设空间中搜索假设 使其与训练样例有最佳的拟合 例如 云计算cloudcomputing 物联网theinternetofthings 社会计算socialcomputing 码农codingfarmer s 等 单概念 多概念学习 1 1概念学习 概念学习 许多机器学习涉及到从特殊训练样例中得到一般概念 概念 可被看作一个对象或事件集合 它是从更大的集合中选取的子集 或在这个较大集合中定义的布尔函数 概念学习问题的定义给定一个样例集合以及每个样例是否属于某个概念的标注 怎样推断出该概念的一般定义 又称从样例中逼近布尔函数 概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数 概念学习 目标概念 运动员进行水上运动项目的日子 表示为布尔函数enjoysport任务目的 基于某天的有关属性 预测enjoysport函数的值任务的学习空间 样例集 每个样例表示为属性的集合 概念学习例子 术语定义 目标概念c训练样例x训练样例集d x1 x2 xn 正例 yes 目标概念成员反例 no 非目标概念成员假设h假设集h h1 h2 hn 机器学习的目标就是寻找一个假设h 使得对所有的训练样例x 都有h x c x 假设与概念一致 概念学习任务 2 目标概念enjoysport的训练样例 d day1 day2 dayn 每个训练样例x有六个属性 概念学习任务 3 表示假设的形式一个简单的形式 具体实例的各属性约束的合取式令每个假设为6个约束 或变量 的向量 每个约束对应一个属性可取值范围 可以为 任意本属性可接收的值明确指定的属性值 如cold high 不接受任何值假设的例子 气温冷 湿度偏高 所有的样例都是正例 没有指定任何条件 所有的样例都是反例 任何条件都满足不了 概念学习任务 4 enjoysport概念学习的任务已知实例x每个实例x由6个属性描述 每个属性的取值范围已确定假设集h每个假设h描述为6个属性的取值约束的合取目标概念c布尔函数 变量为实例训练样例集d目标函数 或目标概念 的正例和反例求解h中的任一假设h 使对于任意实例x h x c x 归纳学习过程 归纳学习从特殊的训练样例中得到普遍的规律归纳保证输出的假设能与训练样例相拟合归纳假设的一个基本假定对于未见实例最好的假设就是与训练数据最佳拟合的假设归纳学习假设任一假设如果在足够大的训练样例集中很好地逼近目标函数 它也能在未见实例中很好地逼近目标函数 假设从一般到特殊的转化 假设的一般到特殊考虑下面两个假设h1 h2 任何被h1划分为正例的实例都会被h2划分为正例 因此h2比h1更一般 h1比h2更特殊 利用这个关系 无需列举所有假设 就能在无限的假设空间中进行彻底的搜索 假设从一般到特殊的转化 2 关系 更一般 的精确定义任给实例x和假设h x满足h 当且仅当h x 1令hj和hk是在x上定义的布尔函数 称hj比hk更一般 当且仅当 x x hk x 1 hj x 1 记为hjmore general than or equal tohk 或hj ghk显然 g 是一种关系中的一类 偏序关系 自反 反对称 可传递 在某一集合上可能存在四类八种特殊元素 假设从一般到特殊的转化 3 更一般 的严格情形hj ghk 当且仅当 hj ghk hk ghj 反对称性 更特殊 关系的定义hj ghk 当且仅当 hk ghj以enjoysport为例说明上面的定义hk hj hj ghkhj 更一般 hkhk ghjhk 更特殊 hj 概念学习的方法find s算法 寻找极大特殊假设 1 使用more general than偏序的搜索算法从h中最特殊假设开始 然后在假设覆盖正例失败时将其一般化find s算法将h初始化为h中最特殊假设对每个正例x对h的每个属性约束ai如果x满足ai 那么不做任何处理否则将h中ai替换为x满足的另一个更一般约束输出假设h find s 寻找极大特殊假设 2 find s算法在例子enjoysport上的应用h h h 遇到反例 h不变 因为h已经能够正确地识别反例 h 极大特殊假设 find s 寻找极大特殊假设 3 find s算法演示了一种利用more general than偏序来搜索假设空间的方法 沿着偏序链 从较特殊的假设逐渐转移到较一般的假设 因此 每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设 find s的重要特点 对以属性约束的合取式描述的假设空间h 保证输出为h中与正例一致的最特殊的假设 存在的问题是否收敛到了正确的目标概念 为什么要用最特殊的假设 训练样例是否相互一致 学习方法的健壮性如果有多个极大特殊假设怎么办 多概念下的学习 概念学习的方法 变型空间和候选消除算法 候选消除算法概述概念学习的另一种方法 候选消除算法 candidate elimination find s算法的不足 输出的假设只是h中能够拟合训练样例的多个假设中的一个 候选消除算法输出与训练样例一致的所有假设的集合 候选消除算法在描述这一集合时不需要明确列举所有成员 利用more general than偏序结构 可以维护一个一致假设集合表示 候选消除算法可用于启发式搜索控制规则来表示 候选消除算法的缺点 容错性能差 变型空间和候选消除算法 2 一致 的定义一个假设h与训练样例集合d一致 当且仅当对d中每一个样例都有h x c x 即 consistent h d d h x c x 一致 与 满足 的关系 变型 版本 空间vs versionspace 与训练样例一致的所有假设组成的集合表示了目标概念的所有合理的变型 版本 关于h和d的变型空间 记为vsh d 是h中与训练样例d一致的所有假设构成的子集 vsh d h h consistent h d 变型空间和候选消除算法 3 先列表后消除法能表示变型空间的一种方法是列出其所有成员 变型空间vs 包含h中所有假设的列表 对每个训练样例 从变型空间中移除所有h x c x 的假设 输出vs中的假设列表 优点保证得到所有与训练数据一致的假设 缺点非常繁琐地列出h中的所有假设 大多数实际的假设空间无法做到 变型空间和候选消除算法 4 变型空间的更简洁表示变型空间被表示为它的极大一般g和极大特殊s的成员 这些成员形成了一般和特殊边界的集合 这些边界在整个偏序结构中划分出变型空间 g s vsh d 变型空间versionspace 变型空间方法的初始g集是最上面的一个点 最一般的概念 初始s集是最下面的直线上的点 训练正例 初始h集是整个规则空间 在搜索过程中 g集逐步下移 进行特例化 s集逐步上移 进行泛化 h逐步缩小 最后h收敛为只含一个要求的概念 变型空间方法以整个规则空间为初始的假设规则集合h h 依据训练例子中的信息 它对集合h进行泛化或特化处理 逐步缩小集合h 最后使h收敛为只含有要求的规则 由于被搜索的空间h逐步缩小 故称为变型空间 vsh d vsh d 初始变型空间 例化 泛化 g s 第一个训练实例 smcir 第二个训练实例 lg tri 第三个训练实例 lg cir 消除候选算法 1 正规的初始h集是整个规则空间 这时s包含所有可能的训练正例 最特殊的概念 这时s集规模太大 实际算法的初始s集只包含第一个训练正例 这种h就不是全空间了 2 接收一个新的训练例子 如果是正例 则首先由g中去掉不覆盖新正例的概念 然后修改s为由新正例和s原有元素共同归纳出的最特殊的结果 这就是尽量少修改s 但要求s覆盖新正例 如果这是反例 则首先由s中去掉覆盖该反例的概念 然后修改g为由新反例和g原有元素共同作特殊化的最一般的结果 这就是尽量少修改g 但要求g不覆盖新反例 变型空间和候选消除算法 5 形式化定义极大一般 更一般中的极大者 元 下确界极大特殊 更特殊中的极小者 元 上确界关于假设空间h和训练数据d的一般边界g 是在h中与d相一致的极大一般成员的集合关于假设空间h和训练数据d的特殊边界s 是在h中与d相一致的极大特殊成员的集合 变型空间和候选消除算法 6 变型空间定理 令x为一任意的实例集合 h为x上定义的布尔假设的集合 令c x 0 1 为x上定义的任一目标概念 并令d为任一训练样例集合 对所有的x h c d以及定义的s和g vsh d h h s s g g g gh gs 变型空间中的任意假设h一定更一般特殊边界s而更特殊一般边界g 变型空间和候选消除算法 7 候选消除算法 candidate elimination 初始化g和s如果d是一个正例从g中移去所有与d不一致的假设对s中每个与d不一致的假设s从s中移去s把s的所有的极小泛化式h加入到s中 其中h满足h与d一致 而且g的某个成员比h更一般如果d是一个反例从s中移去所有与d不一致的假设对g中每个与d不一致的假设g从g中移去g把g的所有的极小特殊化式h加入到g中 其中h满足h与d一致 而且s的某个成员比h更特殊从g中移去所有这样的假设 它比g中另一个假设更特殊 变型空间和候选消除的说明 候选消除算法收敛到正确的假设训练样例中没有错误h中包含描述目标概念的正确假设如果样例中存在错误如果给定足够的训练数据 s和g边界收敛得到一个空的变型空间如果目标概念不能由假设表示方式所描述相似情况出现 变型空间和候选消除的说明 2 下一步需要什么样的训练样例一般来说 概念学习的最优查询策略 是产生实例以满足当前变型空间中大约半数的假设 这样 变型空间的大小可以在遇到每个新样例时减半 正确的目标概念就可在只用log2 vs 次实验后得到 变型空间和候选消除的说明 3 怎样使用不完全学习概念即便变型空间中包含多个假设 即目标概念还未学习到 但是仍然有可能对新样例进行一定可信度的分类 归纳偏置 有关候选消除算法的几个问题如果目标概念不在假设空间中怎么办 是否可设计一个包含所有假设的空间来解决这一困难 假设空间的大小对于算法推广到未见实例的能力有什么影响 假设空间的大小对所需训练样例的数量有什么影响 归纳学习需要的预先假定 称为归纳偏置 归纳偏置 2 一个有偏的假设空间在enjoysport这个例子中 假设空间限制为只包含属性值的合取 肯定有偏 因为这一限制 导致假设空间不能够表示最简单的析取形式的目标概念 归纳偏置 3 无偏的学习器为了保证目标概念在假设空间中 需要提供一个假设空间 它能表达所有的可教授概念 换言之 它能表达实例集x的所有子集 enjoysport的无偏形式带来的问题 概念学习算法无法从训练样例中泛化 要想获得单个目标概念 就必须提供x中所有实例作为训练样例 归纳偏置 4 无偏学习的无用性归纳学习的一个基本属性 学习器如果不对目标概念的形式做预先的假定 它从根本上无法对未见实例进行分类 小结 概念学习可看作搜索预定义潜在假设空间的过程 假设的一般到特殊偏序结构可以定义在任何概念学习问题中 这种结构便于假设空间的搜索 find s算法使用一般到特殊序关系 在偏序结构的一个分支上执行一般到特殊搜索 寻找一个与样例一致的最特殊假设 候选消除算法利用一般到特殊的过程 通过渐进地计算极大特殊假设集合s和极大一般假设集合g发现变型空间 候选消除算法缺少健壮性 归纳学习算法隐含了归纳偏置 候选消除算法的偏置是 目标概念可以在假设空间中找到 所以又称限定偏置 输出的假设和对新实例的分类可由归纳偏置和训练样例演绎推出 二决策树学习 概论 决策树学习是应用最广的归纳学习 推理 算法之一是一种逼近离散值函数的方法很好的健壮性能够学习析取表达式id3 是著名的学习算法搜索一个完整表示的假设空间归纳偏置是优先选择较小的树决策树表示了多个if then规则 决策树表示法 决策树通过把实例从根节点排列到某个叶子节点来分类实例 叶子节点即为实例所属的分类树上每个节点说明了对实例的某个属性的测试节点的每个后继分支对应于该属性的一个可能值决策树代表实例属性值约束的合取的析取式 从树根到树叶的每一条路径对应一组属性测试的合取 树本身对应这些合取的析取 决策树举例 能否打羽毛球 看天气情况 r1 ifoutlook sunny humidity highthennor2 ifoutlook sunny humidity normalthenyesr1 r2 决策树 outlook humidity no yes 分支对应属性值 sunny overcast rainy high normal 决策树学习的适用问题 适用问题的特征实例由 属性 值 对表示目标函数具有离散的输出值可能需要析取的描述训练数据可以包含错误训练数据也可以包含缺少属性值的实例问题举例根据疾病分类患者根据起因分类设备故障根据拖欠支付的可能性分类贷款申请根据年龄 收入等分类银行信用卡的等级分类问题核心任务是把样例分类到各可能的离散值对应的类别 决策树学习的适用问题 客户的购买记录 确定下列商品是否可能购买 决策树学习案例 一个模拟淘宝的简单示例 sellers sid wid wprice wsold wscore customers cid cname ctype cscore wdivide wid wname wtype 1 wtype 2 wtype 3 shopcart cid sid wid datetime amount 用表cookie来模拟用户上网浏览产生的数据 cookie sid wid 数据库视图 1 数据库中的表customers 2 购物车shopcarts 数据表设计 3 商家店铺 根据网页用户浏览产生的cookie来推荐给用户商品 cookie中信息 推荐其他的 适合用户的 迫切需求的 代码设计 declare type 1nchar 12 type 2nchar 12 type 3nchar 12 namevarchar 16 sidchar 10 widchar 10 select sid cookie sid wid cookie wid name wname type 1 wtype 1 type 2 wtype 2 type 3 wtype 3fromwdivide cookiewherewdivide wid cookie wid select name 您正在浏览的物品 sid 商家编号 type 1 种类 type 2 性质 type 3 品牌 selectwname 您可能喜欢的物品 sid 商家编号 wtype 1 种类 wtype 2 性质 wtype 3 品牌 fromwdivide sellerswherewtype 1 type 1andwtype 2 type 2andwdivide wid sellers widandsellers wid wid 根据购物车来推荐商品 按最简单的分类方式 决策树方法 种类 性质 这里选取了购物车中的一条记录进行了模拟 而现实生活中肯定会有大量的数据存在 所以真实的淘宝因其成千上万的数据要显示给用户 其界面会显得让人眼花缭乱 分类 推荐商品 作者 孙志刚指导老师 赵合计教授 基本的决策树学习算法 大多数决策树学习算法是一种核心算法的变体采用自顶向下的贪婪搜索遍历可能的决策树空间id3 identification辨认 是这种算法的代表 基本的决策树学习算法 2 id3的思想自顶向下构造决策树从 哪一个属性将在树的根节点被测试 开始使用统计测试来确定每一个实例属性单独分类训练样例的能力id3的过程分类能力最好的属性被选作树的根节点 如长相 收入 天气等 根节点的每个可能值产生一个分支训练样例排列到适当的分支重复上面的过程 id3算法 1 随机选择训练实例的子集构成训练窗口2 重复执行下列步骤 1 对窗口内的实例集构造其决策树 2 寻找决策树的一个反例 3 如果反例存在 将其加入到训练窗口中 并转 1 否则返回得到的决策树 id3检查所有的候选属性 选择增益最大的属性a作为根结点 形成树 然后 对子树c1 c2 cm以同样处理 递归地形成决策树 id3算法 最佳分类属性 1 实例集中实例的属性的重要性是不同的 如何评价属性所得到信息量的多少 引入信息增益 gain的概念刻画 信息增益用来衡量给定的属性区分训练样例的能力id3算法在增长树的每一步使用信息增益从候选属性中选择属性用熵 entropy 度量样例的均一性熵刻画了任意样例集的纯度给定包含关于某个目标概念的正反样例的样例集s 那么s相对这个布尔型分类的熵为例如 26个字母 每个字母的熵 log2 1 26 4 72500个汉字每个汉字的熵 log2 1 2500 11 29entropy s pos log2pos neg log2neg 最佳分类属性 2 entropy s pos log2pos neg log2negpos neg分别表示s中正负实例的比例 如3个正实例 6个负实例 entropy 3 6 3 9 log2 3 9 6 9 log2 6 9 1 3 1 585 1 3 0 585 0 9182entropy 1 6 1 7 log2 1 7 6 7 log2 6 7 0 5617 最佳分类属性 2 entropy 6 6 6 12 log2 6 12 6 12 log2 6 12 1entropy 0 6 0 6 log2 0 6 6 6 log2 6 6 0entropy 6 0 6 6 log2 6 6 0 6 log2 0 6 0如果所有的实例都为正或都为负 则熵为0 如pos neg 1 2 最均匀 平均 有则熵为1熵的取值是 0 1 曲线如下 更一般地 如果目标属性具有c个不同的值 那么s相对于c个状态的分类的熵定义为entropy s 其中pi表示第i个输出所占训练窗口中总的输出数量的比例 最佳分类属性 为了检测每个属性的重要性 可以通过每个属性的信息增益gain来评估其重要性 对于属性a 假设其域值为 v1 v2 vn 则训练实例中属性的信息增益定义如下 其中si表示s中属性a的值为vi的子集 si 表示集合的势 通过计算各属性的信息增益 可以选择信息量最大的属性作为决策树的根节点属性 最佳分类属性 信息增益计算举例 首先计算熵entropy s 然后计算每个属性a的增益gain id3应用举例 其中9个yes正例 5个no反例 计算信息增益选择最佳分类属性 humidity high normal 3 4 6 1 s 9 5 e 0 940 gain s humidity entropy s 7 14 entropy 3 4 7 14 entropy 6 1 0 940 7 14 0 985 7 14 0 592 0 151 e 0 985 e 0 592 entropy 9 5 9 14log29 14 5 14log25 14 0 940其中属性humidity high样例有7个 3个正例 4个反例entropy 3 4 3 7log23 7 4 7log24 7 0 985humidity normal样例有7个 6个正例 1个反例entropy 6 1 6 7log26 7 1 7log21 7 0 592 计算信息增益选择最佳分类属性 wind weak strong 6 2 3 3 s 9 5 e 0 940 e 0 811 e 1 0 gain s wind entropy s 8 14 entropy 6 2 6 14 entropy 3 3 0 940 8 14 0 811 6 14 1 0 0 048 entropy 6 2 6 8log26 8 2 8log22 8 0 811entropy 3 3 3 6log23 6 3 6log23 6 1 0 选择下一个分类属性 outlook sunny rainy 2 3 3 2 s 9 5 e 0 940 gain s outlook 0 940 5 14 0 971 4 14 0 0 5 14 0 0971 0 247 e 0 971 e 0 971 overcast 4 0 e 0 0 gain s outlook 0 247gain s humidity 0 151gain s wind 0 048 id3算法 outlook sunny overcast rainy yes d1 d2 d14 9 5 ssunny d1 d2 d8 d9 d11 2 3 d3 d7 d12 d13 4 0 d4 d5 d6 d10 d14 3 2 gain ssunny humidity 0 970 3 5 0 0 2 5 0 0 0 970gain ssunny temp 0 970 2 5 0 0 2 5 1 0 1 5 0 0 0 570gain ssunny wind 0 970 2 5 1 0 3 5 0 918 0 019 id3算法 outlook sunny overcast rainy humidity high normal wind strong weak no yes yes yes no d3 d7 d12 d13 d8 d9 d11 d6 d14 d1 d2 d4 d5 d10 决策树中的规则 outlook sunny overcast rain humidity high normal wind strong weak no yes yes yes no r1 if outlook sunny humidity high thenplaytennis nor2 if outlook sunny humidity normal thenplaytennis yesr3 if outlook overcast thenplaytennis yesr4 if outlook rain wind strong thenplaytennis nor5 if outlook rain wind weak thenplaytennis yes 决策树学习中的假设空间搜索 观察id3的搜索空间和搜索策略 认识到这个算法的优势和不足假设空间包含所有的决策树 它是关于现有属性的有限离散值函数的一个完整空间维护单一的当前假设 不同于变型空间候选消除算法 不进行回溯 可能收敛到局部最优每一步使用所有的训练样例 不同于基于单独的训练样例递增作出决定 容错性增强 决策树学习的归纳偏置 id3的搜索策略优先选择较短的树优先选择那些信息增益值大 高 的属性作为离根节点较近的节点近似的id3的归纳偏置较短的树比较长的树优先近似在于id3得到局部最优 而不一定是全局最优更贴切近似的归纳偏置较短的树比较长的树优先 信息增益高的属性更靠近根节点的树优先 id3和候选消除算法的比较 id3和候选消除算法的比较id3的搜索范围是一个完整的假设空间 但不彻底地搜索这个空间候选消除算法的搜索范围是不完整的假设空间 但彻底地搜索这个空间id3的归纳偏置完全是搜索策略排序假设的结果 来自搜索策略候选消除算法完全是假设表示的表达能力的结果 来自对搜索空间的定义 限定偏置和优选偏置 优选偏置id3的归纳偏置是对某种假设胜过其他假设的一种优选 对最终可列举的假设没有硬性限制限定偏置候选消除算法的偏置是对待考虑假设的一种限定通常优选偏置比限定偏置更符合归纳学习的需要优选偏置和限定偏置的结合 决策树学习的常见问题 决策树学习的实际问题确定决策树增长的深度处理连续值的属性选择一个适当的属性筛选度量标准处理属性值不完整的训练数据处理不同代价的属性提高计算效率决策树的知识表示没有规则不易于理解 两棵决策树比较是否等价问题是子图匹配问题不能处理未知属性的情况 决策树学习算法的发展 发现概念描述空间一种特别有效的方法是形成决策树 hunt marin 和stone于1966年研制了一个概念学习系统cls 可以学习单个概念 并用此学到的概念分类新的实例 quinlan于1983年研制了id3 1983 schlimmer和fisher于1986年构造了id4算法 允许递增式地构造决策树 utgoff于1988年提出id5算法 它允许通过修改决策树来增加新的训练实例 而无需重建决策树 决策树id4 1986 schlimmer和fisher设计了id4学习算法 是一种递增式学习算法 他们修改id3算法 在每个可能的决策树结点创建一系列表 每个表由全部未检测属性值和每个值的正例和反例数组成 当处理一个新例时 每个属性值的正例或反例递增计量 决策树id4 输入 决策树 一个实例输出 决策树 1 若该实例是正例 正例数加1 否则 反例数加1 2 如果实例全部为正例或反例 则返回决策树 3 否则 a 计算期望信息分数 b 实例中出现的每个属性 每个值 使之递增正例数或者反