豆丁微信公众号
君，已阅读到文档的结尾了呢~~
1 机器学习与人工智能此项研究受到国家重大基础研究项目(“973”计划人工智能,机器学习
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
1 机器学习与人工智能此项研究受到国家重大基础研究项目(“973”计划
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口AI、机器学习和深度学习之间的区别是什么？_网易科技
AI、机器学习和深度学习之间的区别是什么？
用微信扫码二维码
分享至好友和朋友圈
（原标题：人工智能、机器学习和深度学习之间的区别和联系）
有人说，人工智能（AI）是未来，人工智能是科幻，人工智能也是我们日常生活中的一部分。这些评价可以说都是正确的，就看你指的是哪一种人工智能。今年早些时候，Google DeepMind的AlphaGo打败了韩国的围棋大师李世乭九段。在媒体描述DeepMind胜利的时候，将人工智能（AI）、机器学习（machine learning）和深度学习（deep learning）都用上了。这三者在AlphaGo击败李世乭的过程中都起了作用，但它们说的并不是一回事。今天我们就用最简单的方法——同心圆，可视化地展现出它们三者的关系和应用。如上图，人工智能是最早出现的，也是最大、最外侧的同心圆；其次是机器学习，稍晚一点；最内侧，是深度学习，当今人工智能大爆炸的核心驱动。五十年代，人工智能曾一度被极为看好。之后，人工智能的一些较小的子集发展了起来。先是机器学习，然后是深度学习。深度学习又是机器学习的子集。深度学习造成了前所未有的巨大的影响。|&从概念的提出到走向繁荣1956年，几个计算机科学家相聚在达特茅斯会议（Dartmouth Conferences），提出了“人工智能”的概念。其后，人工智能就一直萦绕于人们的脑海之中，并在科研实验室中慢慢孵化。之后的几十年，人工智能一直在两极反转，或被称作人类文明耀眼未来的预言；或者被当成技术疯子的狂想扔到垃圾堆里。坦白说，直到2012年之前，这两种声音还在同时存在。过去几年，尤其是2015年以来，人工智能开始大爆发。很大一部分是由于GPU的广泛应用，使得并行计算变得更快、更便宜、更有效。当然，无限拓展的存储能力和骤然爆发的数据洪流（大数据）的组合拳，也使得图像数据、文本数据、交易数据、映射数据全面海量爆发。让我们慢慢梳理一下计算机科学家们是如何将人工智能从最早的一点点苗头，发展到能够支撑那些每天被数亿用户使用的应用的。|&人工智能（Artificial Intelligence）——为机器赋予人的智能早在1956年夏天那次会议，人工智能的先驱们就梦想着用当时刚刚出现的计算机来构造复杂的、拥有与人类智慧同样本质特性的机器。这就是我们现在所说的“强人工智能”（General AI）。这个无所不能的机器，它有着我们所有的感知（甚至比人更多），我们所有的理性，可以像我们一样思考。人们在电影里也总是看到这样的机器：友好的，像星球大战中的C-3PO；邪恶的，如终结者。强人工智能现在还只存在于电影和科幻小说中，原因不难理解，我们还没法实现它们，至少目前还不行。我们目前能实现的，一般被称为“弱人工智能”（Narrow AI）。弱人工智能是能够与人一样，甚至比人更好地执行特定任务的技术。例如，Pinterest上的图像分类；或者Facebook的人脸识别。这些是弱人工智能在实践中的例子。这些技术实现的是人类智能的一些具体的局部。但它们是如何实现的？这种智能是从何而来？这就带我们来到同心圆的里面一层，机器学习。|&机器学习—— 一种实现人工智能的方法机器学习最基本的做法，是使用算法来解析数据、从中学习，然后对真实世界中的事件做出决策和预测。与传统的为解决特定任务、硬编码的软件程序不同，机器学习是用大量的数据来“训练”，通过各种算法从数据中学习如何完成任务。机器学习直接来源于早期的人工智能领域。传统算法包括决策树学习、推导逻辑规划、聚类、强化学习和贝叶斯网络等等。众所周知，我们还没有实现强人工智能。早期机器学习方法甚至都无法实现弱人工智能。机器学习最成功的应用领域是计算机视觉，虽然也还是需要大量的手工编码来完成工作。人们需要手工编写分类器、边缘检测滤波器，以便让程序能识别物体从哪里开始，到哪里结束；写形状检测程序来判断检测对象是不是有八条边；写分类器来识别字母“ST-O-P”。使用以上这些手工编写的分类器，人们总算可以开发算法来感知图像，判断图像是不是一个停止标志牌。这个结果还算不错，但并不是那种能让人为之一振的成功。特别是遇到云雾天，标志牌变得不是那么清晰可见，又或者被树遮挡一部分，算法就难以成功了。这就是为什么前一段时间，计算机视觉的性能一直无法接近到人的能力。它太僵化，太容易受环境条件的干扰。随着时间的推进，学习算法的发展改变了一切。|&深度学习——一种实现机器学习的技术人工神经网络（Artificial Neural Networks）是早期机器学习中的一个重要的算法，历经数十年风风雨雨。神经网络的原理是受我们大脑的生理结构——互相交叉相连的神经元启发。但与大脑中一个神经元可以连接一定距离内的任意神经元不同，人工神经网络具有离散的层、连接和数据传播的方向。例如，我们可以把一幅图像切分成图像块，输入到神经网络的第一层。在第一层的每一个神经元都把数据传递到第二层。第二层的神经元也是完成类似的工作，把数据传递到第三层，以此类推，直到最后一层，然后生成结果。每一个神经元都为它的输入分配权重，这个权重的正确与否与其执行的任务直接相关。最终的输出由这些权重加总来决定。我们仍以停止（Stop）标志牌为例。将一个停止标志牌图像的所有元素都打碎，然后用神经元进行“检查”：八边形的外形、救火车般的红颜色、鲜明突出的字母、交通标志的典型尺寸和静止不动运动特性等等。神经网络的任务就是给出结论，它到底是不是一个停止标志牌。神经网络会根据所有权重，给出一个经过深思熟虑的猜测——“概率向量”。这个例子里，系统可能会给出这样的结果：86%可能是一个停止标志牌；7%的可能是一个限速标志牌；5%的可能是一个风筝挂在树上等等。然后网络结构告知神经网络，它的结论是否正确。即使是这个例子，也算是比较超前了。直到前不久，神经网络也还是为人工智能圈所淡忘。其实在人工智能出现的早期，神经网络就已经存在了，但神经网络对于“智能”的贡献微乎其微。主要问题是，即使是最基本的神经网络，也需要大量的运算。神经网络算法的运算需求难以得到满足。不过，还是有一些虔诚的研究团队，以多伦多大学的Geoffrey Hinton为代表，坚持研究，实现了以超算为目标的并行算法的运行与概念证明。但也直到GPU得到广泛应用，这些努力才见到成效。我们回过头来看这个停止标志识别的例子。神经网络是调制、训练出来的，时不时还是很容易出错的。它最需要的，就是训练。需要成百上千甚至几百万张图像来训练，直到神经元的输入的权值都被调制得十分精确，无论是否有雾，晴天还是雨天，每次都能得到正确的结果。只有这个时候，我们才可以说神经网络成功地自学习到一个停止标志的样子；或者在Facebook的应用里，神经网络自学习了你妈妈的脸；又或者是2012年吴恩达（Andrew Ng）教授在Google实现了神经网络学习到猫的样子等等。吴教授的突破在于，把这些神经网络从基础上显著地增大了。层数非常多，神经元也非常多，然后给系统输入海量的数据，来训练网络。在吴教授这里，数据是一千万YouTube视频中的图像。吴教授为深度学习（deep learning）加入了“深度”（deep）。这里的“深度”就是说神经网络中众多的层。现在，经过深度学习训练的图像识别，在一些场景中甚至可以比人做得更好：从识别猫，到辨别血液中癌症的早期成分，到识别核磁共振成像中的肿瘤。Google的AlphaGo先是学会了如何下围棋，然后与它自己下棋训练。它训练自己神经网络的方法，就是不断地与自己下棋，反复地下，永不停歇。|&深度学习，给人工智能以璀璨的未来
深度学习使得机器学习能够实现众多的应用，并拓展了人工智能的领域范围。深度学习摧枯拉朽般地实现了各种任务，使得似乎所有的机器辅助功能都变为可能。无人驾驶汽车，预防性医疗保健，甚至是更好的电影推荐，都近在眼前，或者即将实现。人工智能就在现在，就在明天。有了深度学习，人工智能甚至可以达到我们畅想的科幻小说一般。你的C-3PO我拿走了，你有你的终结者就好了。注：本文原文来自NVIDIA官网，作者Michael Copeland，Long-time Tech记者。
本文来源：雷锋网
责任编辑：丁广胜_NT1941
用微信扫码二维码
分享至好友和朋友圈
加载更多新闻
热门产品:　　　
:　　　　　　　　
:　　　　　　　　　
热门影院：
阅读下一篇
用微信扫描二维码
分享至好友和朋友圈人工智能、机器学习、深度学习，终于弄懂了……人工智能、机器学习、深度学习，终于弄懂了……方水泉百家号Google DeepMind的AlphaGo打败了韩国的围棋大师李世乭九段。在媒体描述DeepMind胜利的时候，将人工智能（AI）、机器学习（machine learning）和深度学习（deep learning）都用上了。这三者在AlphaGo击败李世乭的过程中都起了作用，但它们说的并不是一回事。本文讲解了 AI 、机器学习、深度学习是怎么回事，他们之间的关系，常见的 AI 算法等知识。当有人问你这些概念的时候，你可以通熟易懂地讲解。人工智能（AI）、机器学习（ML）、深度学习（DL）的关系如下，DL ML
AI。人工智能比喻成的孩子大脑，而机器学习就是让孩子去掌握认知能力的过程，而深度学习是这过程中很有效率的一种教学体系。人工智能是目的，是结果；深度学习、机器学习是方法，是工具。人工智能的概念是在 1955 年提出的；机器学习概念是 1990 年提出的；深度学习概念是 2010 年提出的。深度学习曾经是以机器学习中的「神经网络算法」的身份存在的，随着大数据的爆发，深度学习被单拿出来，成为一种学习思想。从亚马逊、Facebook、谷歌、微软这些顶级科技公司能都看出，世界上最具影响力的技术公司的领导者都在强调他们对人工智能（AI）的关注。什么是人工智能？人工智能的定义是让机器实现原来只有人类才能完成的任务，其核心是算法。例如下图所示就是让机器模拟人各种能力的人工智能领域示意图：人工智能为什么很重要？人工智能一直是计算机科学的前沿和热点领域，受关注度因技术的发展几起几落，自上个世纪50年代提出后受到热捧，到70年代因算法处理非线性问题的效果不理想而淡出公众视野，80年代末期又因“专家系统”的兴起再次引起众多世界500强企业青睐，21世纪后随着神经网络、遗传算法等新算法的成熟，以及“深度学习”领域核心问题的突破，人工智能的热潮再次来临。人工智能技术 将极大地提升和扩展人类的能力边界，对促进技术创新、提升国家竞争优势，乃至推动人类社会发展产生深远影响。而当前，人工智能技术的发展已经迎来拐点。机器学习：推理 - 知识 - 学习机器学习（ML）是 AI 的一个子集。所有机器学习是 AI，但不是所有的 AI 是机器学习。「AI」的兴趣在今天表现于人们对「机器学习」的热情，进展迅速且明显。机器学习让我们通过算法来解决一些复杂的问题。正如人工智能先驱 Arthur Samuel 在 1959 中写道的那样，机器学习是需要研究的领域，它给计算机学习的能力而不是明确地编程能力。大多数机器学习的目标是为特定场景开发预测引擎。一个算法将接收到一个域的信息（例如，一个人过去观看过的电影），权衡输入做出一个有用的预测（未来想看的不同电影的概率）。通过计算机学习的能力，通过优化任务衡量变量的可用数据，做出算法，来对未来做出准确的预测。机器通过训练学习。算法最初接收其输出是已知的示例，此时要注意其预测和正确输出之间的差异，并且调谐输入的权重以提高其预测的准确性，直到它们被优化。因此，机器学习算法的定义特征是，它们的预测的质量随着经验而改进。深度学习——一种实现机器学习的技术人工神经网络（Artificial Neural Networks）是早期机器学习中的一个重要的算法，历经数十年风风雨雨。神经网络的原理是受我们大脑的生理结构——互相交叉相连的神经元启发。但与大脑中一个神经元可以连接一定距离内的任意神经元不同，人工神经网络具有离散的层、连接和数据传播的方向。现在，经过深度学习训练的图像识别，在一些场景中甚至可以比人做得更好：从识别猫，到辨别血液中癌症的早期成分，到识别核磁共振成像中的肿瘤。Google的AlphaGo先是学会了如何下围棋，然后与它自己下棋训练。它训练自己神经网络的方法，就是不断地与自己下棋，反复地下，永不停歇。深度学习使得机器学习能够实现众多的应用，并拓展了人工智能的领域范围。深度学习摧枯拉朽般地实现了各种任务，使得似乎所有的机器辅助功能都变为可能。无人驾驶汽车，预防性医疗保健，甚至是更好的电影推荐，都近在眼前，或者即将实现。本文由百家号作者上传并发布，百家号仅提供信息发布平台。文章仅代表作者个人观点，不代表百度立场。未经作者许可，不得转载。方水泉百家号最近更新：简介:分享生活百事，感受人间温暖。作者最新文章相关文章苹果/安卓/wp
积分 986, 距离下一级还需 389 积分
权限: 自定义头衔, 签名中使用图片, 隐身
道具: 涂鸦板, 彩虹炫, 雷达卡, 热点灯, 显身卡, 匿名卡, 金钱卡, 抢沙发下一级可获得
权限: 设置帖子权限道具: 变色卡, 提升卡
购买后可立即获得
权限: 隐身
道具: 金钱卡, 变色卡, 彩虹炫, 雷达卡, 热点灯, 涂鸦板
开心签到天数: 901 天连续签到: 281 天[LV.10]以坛为家III
本帖最后由 fengxingliulizi 于
17:24 编辑
从别处下载的，不全，从第2章到第10.1。
17:19:55 上传
17:19:54 上传
17:19:52 上传
售价: 2 个论坛币
支持一下！
好好好 谢谢楼主！
谢谢楼主！
谢谢楼主！
翻译原地址： http://download.csdn.net/detail/shuxiangjianqi
翻译下载地址 ： &&我是雷锋
好好好 谢谢楼主！
您需要登录后才可以回帖
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
如有投资本站或合作意向，请联系（010-）；
邮箱：service@pinggu.org
投诉或不良信息处理：（010-）
论坛法律顾问：王进律师当前位置： >>
机器学习的研究与应用新进展
第 10 章机器学习研究与应用新进展徐从富 李石坚 王金龙 310027）（浙江大学人工智能研究所，杭州2005 年 10 月 7 日第一稿 2006 年 10 月 16 日第二稿10.1机器学习研究与应用综述10.1.1 机器学习的发展概况机器学习（Machine Learning）不仅是人工智能的一个核心研究领域，而且 已成为整个计算机领域中最活跃、应用潜力最明显的领域之一，它扮演着日益重 要的角色。近年来，欧美各国都投入了大量人财物进行机器学习的研究和应用， Intel、IBM、波音、微软、通用电器等大型公司也积极开展该领域的研究和开发， 而且已有不少研究成果进入产品。 美国航空航天局 JPL 实验室的科学家们在 2001 年 9 月出版的《Science》上撰文指出： “机器学习对科学研究的整个过程正起到 越来越大的支持作用，……，该领域在今后的若干年内将取得稳定而快速的发 展。 ”此外，机器学习研究的热门程度还可以从该领域的国际权威期刊《机器学 习研究学报》 （Journal of Machine Learning Research，简称 JMLR）的影响因子 （Impact factor）看出，据美国科学引文检索公司（ISI）统计，2004 年该学报的 影响因子已达到 5.952，这是除了《ACM 计算综述》 （ACM Computing Survey） 以外影响因子最高的计算机类期刊。需要特别说明的是， 《ACM 计算综述》每年 只发表 12 篇世界级权威计算机专家关于某个研究方向最新研究进展的综述文 章，一般并不发表研究论文，2004 年其影响因子为 10.037。 1997 年 Tom M. Mitchell 在“Machine Learning”一书中给出了机器学习的经 典定义――“计算机利用经验改善系统自身性能的行为。 ”还有人认为，机器学 习是“神经科学（含认知科学）＋数学＋计算”的有机结合，数学则填补了神经 科学与计算之间的鸿沟。与很多新兴学科一样，机器学习也是一个多学科交叉的 产物，它吸取了人工智能、概率统计、神经生物学、认知科学、信息论、控制论、 计算复杂性理论、哲学等学科的成果。实践证明，机器学习在很多应用领域发挥 了重要的实用价值，特别是在数据挖掘、语音识别、图像识别、机器人、车辆自 动驾驶、生物信息学、信息安全、遥感信息处理、计算金融学、工业过程控制等 1领域取得了令人瞩目的成果。 一般来说，机器学习的研究起点最早可追溯到 19 世纪末的神经科学，特别 是 James 发现了神经元是相互连接的现象。 随后， 在 20 世纪 30 年代， McCulloch 和 Pitts 发现了神经元的“兴奋”和“抑制”机制，20 世纪中叶，Hebb 发现了“学 习律” ，等等。在上述神经生物学研究成果的基础上，机器学习的发展大致可分 为两条重要主线。一条主线是：以 Barlow 提出的功能单细胞假设为依据， Rosenblatt 于 1956 年提出了感知器，在随后的近 30 年时间里，Samuel 等人提出 的“符号机器学习”方法一直处于主导地位，1969 年 Minsky 开始研究线性不可 分问题，1986 年 Rumelhart 提出了著名的后向传播（BP）神经网络，20 世纪 90 年代 Vapnik 等人提出了针对有限样本的统计学习理论和支持向量机（SVM） ，等 等。另一条主线是：以 Hebb 提出的神经集合体假设为依据，1960 年 Widrow 提 出了 Madline 以解决平凡解问题，1984 年 Valiant 提出了 PAC，1990 年 Schapire 提出了弱学习定理， 1995 年 Freund 和 Schapire 提出了 AdaBoost 算法， 在上述研 究成果的基础上，逐渐形成了泛化理论。需要说明的是，在符号机器学习方面， 1959 年 Solomonoff 关于文法归纳的研究应该是最早的符号机器学习，Samuel 将 学习限制在结构化数据，由此学习演变为约简算法，这是现代符号机器学习的基 础。如果将每条规则理解为一个分类器，符号机器学习是也可算作是 Hebb 路线 的产物。此外，1967 年哥德尔从数学上证明了符号机器学习是不可能完全实现 的。10.1.2 机器学习的研究内容一般来说，一个典型的机器学习系统（如图 10.1 所示）都包括下面 4 个程 序模块： （1） 执行系统（Performance System） 。其主要功能是用学会的目标函数来 解决给定的任务。 （2） 鉴定器（Critic） 。它以解答路线或历史记录作为输入，输出目标函数 的一系列训练样本。 （3） 泛化器（Generalizer） 。它以训练样本作为输入，产生一个输出假设， 作为它对目标函数的估计。它从特定的训练样本中泛化，猜测一个一 般函数，使其能够覆盖这些样本以及样本之外的情形。 （4） 实验生成器（Experiment Generator） 。它以当前的假设（即当前学到 的目标函数）作为输入，输出一个新的问题供执行系统去探索。 设计一个机器学习系统通常要解决如下几方面的问题： （1）选择训练经验。 它包括：如何选择训练经验的类型，如何控制训练样本序列，以及如何使训练样 本的分布与未来测试样本的分布相似等子问题。 （ 2 ）选择目标函数（ Target function） 。不难发现，所有的机器学习问题几乎都可简化为学习某个特定的目标 函数的问题，而且这样的简化对解决实际问题是非常有益的，因此，目标函数的 2学习、设计和选择是机器学习领域的关键问题。 （3）选择目标函数的表示。对于 一个特定的应用问题，在确定了理想的目标函数后，接下来的任务是必须从很多 （甚至是无数）种表示方法中选择一种最优或近似最优的表示方法。实验生成器 新问题 执行系统 解答路线 鉴定器 假设泛化器训练样本图 10.1一个典型的机器学习的基本组成模块Tom M. Mitchell 认为，机器学习致力于解决的主要问题有： （1） 存在什么样的算法能从特定的训练样本中学习一般的目标函数？如 果提供了充足的训练样本，在什么条件下会使特定的算法收敛到期 望的函数？哪个算法对哪些问题的性能最好？ （2） 多少训练样本是充足的？怎样找到假设的置信度与训练样本的数量 及提供给学习器的假设空间特性之间的一般关系？ （3） 学习器拥有的先验知识是怎样引导从样本进行泛化的过程的？当先 验知识仅仅是近似正确的，它们会有帮助吗？ （4） 关于选择有效的后续训练经验，什么样的策略最好？这个策略的选 择将如何影响学习问题的复杂性？ （5） 怎样把学习任务简化为一个或多个函数逼近问题？也就是说，系统 试图学习哪些函数？这个过程本身能否自动化？ （6） 学习器怎样自动地改变表示法来提高表示和学习目标函数的能力？10.1.3 研究现状与发展趋势显然，任何一个没有学习能力的系统都很难被认为是一个真正的智能系统， 但随着机器学习研究及应用的不断发展，尽管“学习机制”还是研究动力之一， 然而， “烦恼的网络”危机使得更为重要的推动力来自“有效利用”信息。当前， 很多传统领域借用机器学习来提高研究水平，应用驱动的机器学习方法层出不 穷，特别是基于机器学习的数据分析方法已成为解决复杂问题的关键技术之一， 因此，当前机器学习的角色也逐渐发生了转变，已发展到一个新阶段。主要体现 3在： （1）主方向的改变。当前机器学习领域的主流不再是单纯地做“会学习的 机器（人） ” ，而是越来越朝着智能数据分析的方向发展，并已成为智能数据分析 技术的一个重要源泉。目前，机器学习主要用于智能数据分析的典型任务――预 测，例如，天气预报、网络入侵检测、生物信息学中的基因组和蛋白质组的结构 分析等。 （2）侧重点的改变。传统的机器学习强调“学习本身是目的” ，上一阶段的 研究几乎完全局限于人工智能这一领域本身， 主要关注人工智能对人类学习能力 的追求；而当前的机器学习更强调“学习本身是手段” ，它已经开始广泛进入计 算机科学的不同领域，甚至其它学科，并已成为一种支持技术和服务技术。 （3）应用面的改变。近年来，文本与图像占信息的绝大数，在文本分析与 自然语言理解上，数据资源建设逐渐完善，人们关注的焦点是机器学习及其在这 些数据资源上的深层次应用。当前，针对信息的复杂多样性，涌现出很多新的机 器学习方法。比如：可用于特征抽取的流形机器学习，即稀疏数据的非线性处理 方法；改善机器人适应环境变化性能的增强学习；可用于药物设计的多实例学习 和半监督学习；广泛用于搜索引擎的 Ranking 学习；能够快速过滤海量数据的数 据流（Data stream）学习；等等。虽然这些新的机器学习方法仍处于探索和实验 观察阶段，但是，它们已充分表明基于机器学习的数据分析方法越来越成为解决 复杂问题的关键。 因此，现阶段机器学习研究不应再过多地强调模拟人的学习能力，应该把机 器学习真正当成一种支持技术（也就是说，它是一种重要手段而非目的） ，考虑 不同领域甚至不同学科对机器学习的需求，找出其中迫切需要解决的共性问题， 并进行深入研究， 有人把这种视角下的机器学习称为 “普适机器学习” （Pervasive Machine Learning，简称 PML） 。 中科院自动化研究所模式识别国家重点实验室的王珏教授等人认为， 目前机 器学习领域存在的主要理论问题有： z 统计类机器学习需要满足独立同分布条件，这样的要求太过苛刻。 z 没有一般的指导原则来寻找问题线性表示的空间。 z 没有好的方法来支持信息向符号的映射。 z 机器学习没有一劳永逸的解决方案。 z 领域知识与数据分析不可避免。 南京大学计算机软件新技术国家重点实验室的周志华教授等人认为，今后 10 年间机器学习领域存在 5 个挑战性问题： （1）泛化能力。这是一个共性问题，几乎所有的领域都希望越准越好，提 高泛化能力是机器学习领域永远追求的目标。目前泛化能力最强的技术有：支持 向量机（SVM） ，其产生途径是从理论（特别是统计学）到实践；集成学习 （Ensemble learning） ，其产生途径则是从实践到理论。4（2）速度。这也是一个共性问题，几乎所有的领域都希望越快越好，加快 速度也是机器学习领域永远追求的目标。目前，机器学习领域最关心的一个问题 是“训练速度”与“测试速度”之间的关系，以及如何使这两者之间不发生矛盾。 例如，k 近邻方法的训练速度快，但其测试速度往往比较慢；而神经网络恰恰相 反；等等。 （3）可理解性。绝大多数领域都希望有“可理解性” ，例如，在医疗诊断中 需要向病人解释“为什么做出这样的诊断” ，信用卡盗用检测时需要向保安或公 安部门解释“为什么这是正被盗用的卡” ，等等。而目前功能强大的机器学习技 术几乎都是（或基本上是） “黑盒子” ，如神经网络、支持向量机、集成学习等。 最近，Tom M. Mitchell 在他的著作“Machine Learning”新增一章可理解的 Na?ve Bayes（朴素贝叶斯）方法和 Logistic Regression（回归）模型是有重要意义的。 （4）数据利用能力。传统的机器学习技术都是对有“标记”的数据（是指 带有事件所对应的结果的数据）进行学习，然而，随着 Internet 的出现和数据收 集能力的不断提高，绝大多数领域都将面临大量未标记的数据，如医学图像、垃 圾邮件等；同样地，大多数领域也都会遇到“坏”数据（是指那些含有大量噪音、 属性缺失、不一致的数据） ；此外，还有一类“不平衡”数据也经常碰到，比如， 乳腺癌诊断中的 “健康人” 样本就远多于 “病人” 样本， 信用卡盗用检测中的 “正 常使用”样本就远多于“盗用”样本。这就提出了一个新的问题，即如何充分利 用这些没有标记的数据、 “坏”数据和不平衡数据？ （5）代价敏感。目前的机器学习技术都在极力追求低错误率，然而，不同 领域所容忍的错误代价并不一样， 即使同一领域中不同的判断所对应的代价也不 同。比如，在乳腺癌诊断中， “将病人误诊为健康人的代价”与“将健康人误诊 为病人的代价”是不同的；同样地，在信用卡盗用检测中， “将盗用误认为正常 使用的代价”与“将正常使用误认为盗用的代价”也是不同的。而传统的机器学 习技术基本上只考虑同一代价， 如何处理代价敏感性？这就带来了一个很大的挑 战，机器学习技术能否以较小的代价达到“趋利避害”的目的，即在达到用户容 忍的总错误率的基础上，如何“趋利” ，又如何“避害”？最近两年，不少知名 学者将信号理论、医学诊断中的 ROC（Receiver Operating Characteristic）分析方 法引入机器学习领域，有望在这方面取得突破。 关于机器学习研究的方法论，有人认为： （1）特殊性比普适性更重要，即一 类问题的深入研究比普适的研究更重要。比如，就本体论方法而言，一个领域本 体的深入研究比广泛地构造本体更重要。 （2）应该向其它相关领域学习，机器学 习的进展需要依赖其它学科的进展，特别是神经科学与认知科学，以及从数学工 具那里寻找结果。同时，还应该向非线性等领域学习。需要特别强调的是，自从 20 世纪 90 年代以来，基于概率统计的机器学习技术已成为当今机器学习领域中 最重要的主流研究方向。 当前，机器学习研究与应用中最常用的关键技术有：集成学习（含 Boosting, Bagging 等算法） 、贝叶斯网络、决策树、统计学习理论与支持向量机、隐马尔 5可夫模型、神经网络、k 近邻方法、序列分析、聚类、集成学习、粗糙集理论、 回归模型等。因篇幅所限，本章着重介绍贝叶斯网络、隐马尔可夫模型、统计学 习理论与支持向量机、数据挖掘与知识发现。610.2贝叶斯网络10.2.1 概述在机器学习过程中，如何通过一种自然和有效的方式来捕捉、表示和推理不 确定性知识显得十分重要。 贝叶斯方法就是一种非常有代表性的不确定性知识表 示和推理方法，在机器学习领域具有十分重要的地位和作用。贝叶斯方法的主要 特点有： （1）使用概率去表示所有形式的不确定性知识，学习和推理过程都用概 率规则来实现，学习或推理结果表示为随机变量的概率分布，可理解为人们对不 同可能性的信任程度； （2）观察到的每个训练样本可以增量地降低或升高某假设 的估计概率； （3）先验知识可以与观察数据一起决定假设的最终概率； （4）贝叶 斯方法可允许对假设做出不确定性的预测； （5）新的实例分类可由多个假设一起 做出预测， 用它们的概率来加权； （6） 可作为最优决策标准衡量其它方法的优劣。 在实际应用中，若能正确估计概率密度函数假设，就可使用少量样本数据， 进行少量计算得到较满意的结果。这在样本难得的情形下特别有用，这也是贝叶 斯方法优于其它方法之处。 在贝叶斯方法中，由于全联合概率公式假设所有变量之间都具有条件依赖 性， 其计算复杂性十分巨大， 而且为每个原子事件指定概率既不自然也相当困难， 所以，在实际应用中一般都采用其简化形式。朴素贝叶斯（Na?ve Bayes）分类器 就是经常使用的一种简化方法。然而，由于朴素贝叶斯分类器假设所有变量之间 都是条件独立的，该假设太过简单和武断，与实际情况并不相符。因此，如何在 全联合概率计算公式和朴素贝叶斯分类器之间取得均衡， 就成为贝叶斯方法的重 要研究课题。贝叶斯网络（Bayesian Network）就是一种很好的折衷方法，它充 分利用了变量之间的独立性和条件独立性关系， 从而大大减少了为定义全联合概 率分布所需指定的概率数目，同时，它又避免了朴素贝叶斯分类器要求所有变量 都是条件独立的不足。 简单地说，贝叶斯网络是一种用以表示变量之间依赖关系的概率图模型 （Directed Probabilistic Graphical Model） ，它提供了一种自然而又有效的 因果关系表达和推理方法，以发现数据间存在的相关性和依赖关系。贝叶斯网络 用图的方法来描述数据间的因果关系，语义清晰，可理解性强，这有助于人们利 用数据间的因果关系来进行推理和预测。 贝叶斯方法以其独特的不确定性知识表 达形式、丰富的概率表达能力、综合先验知识的增量学习特性等，已成为当前机 器学习、人工智能、数据挖掘等领域中众多方法中最受关注的研究热点之一。710.2.2 贝叶斯网络的定义及语义1. 贝叶斯网络的定义概括地说，贝叶斯网络是用于表示变量之间依赖关系，并为任何全联合概率 分布（Joint Probability Distribution）提供自然、有效的简明规范的一种有 向无环图（DAG）结构，其中每个节点都标注了定量概率信息。 具体地说，贝叶斯网络是一种有向图，其拓扑结构满足如下特性： （1） 一个随机变量集组成网络节点，变量可以是离散或连续的。 （2） 一个连接节点对的有向边集合。若存在从节点 X 到节点 Y 的有向边， 则称 X 是 Y 的一个父节点。 量化其父节点对 （3） 每个节点Xi都有一个条件概率分布P(Xi | Parents(Xi))， 该节点的影响。 （4） 图中不存在有向环，因此是贝叶斯网络是一种有向无环图（DAG） 。 贝叶斯网络借助于节点和有向边的集合， 用一种精确而又简结的方式描述了 在全域中成立的条件独立性（conditional independence）关系。在一个正确构造 的贝叶斯网络中，有向边的直观含义通常表示父节点 X 对子节点 Y 有直接的影 响。事实上，贝叶斯网络的拓扑结构和条件概率的有机结合足以显式或隐式指定 所有变量的全联合概率分布。 贝叶斯网络还有很多其它名称，主要有： z 信念网（Belief Network） z 概率网络（Probability Network） z 因果网络（Causal Network） z 知识图（Knowledge Map） z 决策网络（Decision Network） z 影响图（Influence Diagram）2. 贝叶斯网络示例一个表示防盗报警器（Alarm）与盗贼闯入（Burglary） 、地震（Earthquake） 、 John 来电告知（JohnCalls） 、Mary 来电告知（MaryCalls）之间的条件依赖关系 的贝叶斯网络，如图 10.2 所示。该贝叶斯网络的拓扑结构表明，盗贼闯入和地 震直接影响到警报的概率，但是，John 或者 Mary 是否打电话只取决于警报声。 因此，该网络隐式地表明一些假设：John 和 Mary 不直接感知盗贼闯入，也不会 注意到轻微的地震，并且他们在打电话之前并不会交换意见，也就是说，在给定 警报 Alarm 后，JohnCalls 和 MaryCalls 是条件独立的。 图中每个节点都有一个条件概率表 CPT（Conditional probability table） 。CPT 中的每一行包含了每个节点对于一个条件事件（Conditioning case，即所有父节 点的取值的一个可能组合）的条件概率，且每一行的概率总和必须为 1。对于布 尔变量，一旦知道了它为真的概率为 p，那么它为假的概率就是 1-p，因此，在 图中经常省略第二个概率值。特别地，对于没有父节点的节点而言，其概率分布 表只有一行，表示该变量可能取值的先验概率。8图 10.2贝叶斯网络示例3. 贝叶斯网络的语义一般地，可通过两种方式来理解贝叶斯网络的语义。第一种是将贝叶斯网络 视为对联合概率分布的表示；第二种则将其视为对条件依赖性语句集合的编码。 这两种观点是等价的，但前者有助于理解如何构造贝叶斯网络，而后者则能够帮 助人们设计推理过程。 贝叶斯网络的语义可形式化地表示为如下计算公式：P( x1 ,..., xn ) = ∏ P( xi | parents( xi ))i =1n其中， P(x1 ,...,xn ) 表示对每个变量赋予一个特定值的情况下的联合概率，它是P( X1 = x1 ∧ ... ∧ X n = xn ) 的简化表示。下面通过一个例子来说明贝叶斯网络的语义公式的计算过程。 在上述图 10.2 中，已知报警器响了，但既没有盗贼闯入，也没有发生地震， 试计算 John 和 Mary 两人都同时给安装了此报警器的房子主人打电话的概率。【解】 ：9根据贝叶斯网络的语义计算公式可知要计算如下概率：P ( Burglary = False ∧ Earthquake = False ∧ Alarm = True ∧ JohnCalls = True ∧ MaryCalls = True )为简便起见，下面采用英文单词的第一个字母的小写来表示变量名，即P ( Burglary = False ∧ Earthquake = False ∧ Alarm = True ∧ JohnCalls = True ∧ MaryCalls = True ) = P ( ? b ∧ ? e ∧ a ∧ j ∧ m ) = P ( ? b , ? e , a , j , m )然后，再结合这个关于警报器的特定贝叶斯网络的拓扑结构和条件概率表，可得P(?b, ?e, a, j , m) = P(?b) P(?e) P(a | parents(a)) P( j | parents( j )) P(m | parents(m)) = P(?b) P(?e) P(a | ?b ∧ ?e) P( j | a) P(m | a) = 0.999 × 0.998 × 0.001 × 0.90 × 0.70 = 0.00062 = 0.062%10.2.3 贝叶斯网络的特性及构造原则1. 贝叶斯网络的特性z 作为对域的一种完备而无冗余的表示，贝叶斯网络比全联合概率分布紧 凑得多，正是因为这个特性使得对包含许多变量的域进行处理成为可 行。 贝叶斯网络的紧凑性是局部结构化(Locally structured, 也称稀疏, Sparse)系统一个非常普遍特性的实例。在一个局部结构化系统中，每 个组成部分只与数量有限的其它部分发生直接的相互作用，而不考虑组 成部分的总数量，因此，这种结构的复杂度通常是线性增长而不是指数 增长。 在贝叶斯网络中，假设大多数域中每个随机变量受到至多k个其它随机 变量的影响是合理的，其中，k是某个常数。假设有n个布尔变量，那么 k 指定每个条件概率表CPT所需信息量至多为 2 个数据，则整个贝叶斯网 络可由不超过n2k个数据完全描述。与之相反，全联合概率分布将包含 2n个数据。例如，节点数n=30，每节点有最多有 5 个父节点，则贝叶斯 网络需要的数据个数不超过 30×25=960， 而全联合概率分布则需要 230=10 亿个。zz2. 贝叶斯网络的构造原则贝叶斯网络的构造原则如下： z 首先，添加“根本原因”节点； z 然后，加入受它们直接影响的变量；依次类推，直到叶节点，即对其它 10z变量没有直接因果影响的节点为止。 两节点间的有向边的取舍原则：权衡更高精度概率的重要性与指定额外 信息的代价，即在两者之间取得较好的折衷。3. 贝叶斯网络中的条件独立关系在贝叶斯网络中，存在如下 2 种十分重要的条件独立性关系： （1）给定父节点，一个节点与它的非后代节点是条件独立的。 （2）给定一个节点的父节点、子节点以及子节点的父节点――也就是说， 给定一个节点的马尔可夫覆盖(Markov blanket)，这个节点和网络中的所有其它 节点是条件独立的 （注意： 节点 X 与 X 子节点的父节点是 Marginal Independence， 而非 Conditional Independence） 。 上述 2 种条件独立性关系如图 10.3 中的(a)和(b)所示。在图 10.3(a)中， 给定父节点（灰色区域中所示的各Ui） ，节点X与它的非后代节点（即各Zij）是条 件独立的；在图 10.3(b)中，给定马尔可夫覆盖（灰色区域） ，节点X和网络中的 所有其它节点都是条件独立的。事实上，马尔可夫覆盖将在贝叶斯网络的推理中 发挥十分重要的作用。(a) 给定父节点，节点 X 与其非后代节点条 件独立(b) 马尔可夫覆盖图 10.3贝叶斯网络中的条件独立性关系10.2.3 贝叶斯网络中 CPT 的有效表达1. 无连续变量的贝叶斯网络下面以一个例子来说明不含连续变量的贝叶斯网络的条件概率的表示方法。 11例如：已知 P(~fever | cold, ~flu, ~malaria) = 0.6 P(~fever | ~cold, flu, ~malaria) = 0.2 P(~fever | ~cold, ~flu, malaria) = 0.1， 要求给出完整的条件概率表。【解】 ：可利用“噪声或” （Noisy-OR，是逻辑“或”的推广）关系得到表 10.1： Cold F F F F T T T T Flu F F T T F F T T 表 10.1 Malaria F T F T F T F T 完整的条件概率表 P(Fever) P(?Fever) 0.0 1.0 0.9 0.1 0.8 0.2 0.98 0.02 = 0.2×0.1 0.4 0.6 0.06 = 0.6×0.1 0.94 0.12 = 0.6×0.2 0.88 0.012 = 0.6×0.2×0.1 0.988由上述实例可知， “噪声或”模型考虑到每个父节点引起子节点为真的能力 的不确定性――父节点与子节点之间的因果关系有可能被抑制，所以，病人可能 得了感冒却没有出现发烧的症状。事实上，对于其中一个变量依赖于k个父节点 的噪声逻辑关系，可以只用O(k)而不是O(2k)个参数来描述整个条件概率表。这 极大地简化了贝叶斯网络的表示、评价、学习与推理等操作。2. 含连续变量的贝叶斯网络――混合贝叶斯网络同时包含离散随机变量和连续随机变量的网络成为混合贝叶斯网络 （Hybrid Bayesian network） 。下面通过图 10.4 所示的例子来说明混合贝叶斯网络的 CPT 表达方法。图 10.4一个简单的混合贝叶斯网络示例 12图 10.4 所示的是一个同时包含离散随机变量（Subsidy，Buys）和连续随机 变量（Harvest，Cost）的混合贝叶斯网络。图中 4 个节点的 CPT 表达方法分别 如下： z Subsidy 是离散变量，且无父节点，故其概率可根据实际情况指定为 x。 z Harvest是连续变量，具有无限个可能的取值，故不可能显式地为每个取 值指定条件概率。有如下两种处理方式： （1）通过离散化，将所有可能 的取值划分到固定的区间集合中，但该方法有时会导致很大的精度损失 和巨大的CPT； （2）定义标准的概率密度函数族，通过有限个参数进行 指定。例如，高斯（即正态）分布N(?, σ2)以均值?和方差σ2为参数。 z Cost 是连续变量，其父节点既有离散变量（ Subsidy ）也有连续变量 （Harvest） 。 （1）对于离散父节点 Subsidy 可通过直接枚举方式来处理， 即分别指定 P(Cost | Harvest, Subsidy)和 P(Cost | Harvest, ?Subsidy)。 （2） 对于 Harvest， 可将 Cost 的连续取值 c 指定为 Harvest 的连续取值 h 的线 性高斯分布，即子节点 Cost 服从均值?随父节点 Harvest 的值线性变化， 而标准差σ保持不变的高斯分布。对于 Subsidy 和?Subsidy，需要分别定 义 2 个参数不同的线性高斯分布：P (c | h, subsidy ) = N(at h + bt , σt ) =21 σ t 2πe2 1 ? c ?( at h + bt ) ?? ? ?? ? σt 2 ?? ??P(c | h, ?subsidy ) = N(af h + bf , σf 2 ) =1 σf 2πe2 1 ? c ?( af h + bf )?? ? ?? ? 2 ?? σf ??对于这个例子， 连续变量Cost的条件分布可通过确定线性高斯分布以及提供 参数at, bt, σt, af, bf, σf来指定。 z Buys 是离散变量，而其父节点 Cost 则是连续变量。比较合理的分布情 况是：价格 Cost 较低时顾客会购买（Buys=True） ，而 Cost 较高时就很 少买（甚至不购买，即 Buys=False） ，并且 Buys 的概率在某个中间区域 平滑变化。对于这个例子，可采用 S 形函数（Sigmoid function，即“软” 的阈值函数）来生成 Buys 随 Cost 的值变化的条件概率分布，即P (buys | Cost = c ) =1 ?c+? 1 + e( ?2 )σ10.2.4 贝叶斯网络中的精确推理在给定某个已观察事件（一组证据变量）值的某个赋值后，任何概率推理系 统的基本任务都是要计算一组查询变量的后验概率分布。令X表示查询变量；E 表示证据变量集E1, E2, …, Em，e则表示一个观察到的特定事件；Y表示非证据变 Hidden variable） 。 从而得到全部变量的集合X={X} 量Y1, Y2, …, Y（ l 也称隐变量， 13∪ E ∪ Y。典型的查询是询问后验概率P(X | e)。 因篇幅所限，下面以上述“防盗网络”为例简要介绍贝叶斯网络的精确推理 方法――“枚举推理” 。 已知一个事件 e = {JohnCalls = true ∧ MaryCalls = true}，试问出现盗贼的概 率 P(Burglary | e)是多少？【解】 ：由于任何条件概率都可通过将全联合概率分布表中的某些项相加而计算得 到，有如下条件概率计算公式：P( X | e) = αP( X , e) = α ∑ P( X , e, y)y其中，X 为查询变量，e 为事件（即证据的一个观察值） ，y 为未观测变量（即隐 变量） ，α为归一化常数， α =1 。 P(e)根据贝叶斯网络的语义计算公式，可将上述联合概率分布中的项 P(x, e, y) 写成条件概率乘积的形式，因此，在贝叶斯网络中可通过计算条件概率的乘积并 求和来回答查询（即推理结果） 。 就本例而言，要求查询 P(Burglary | JohnCalls = True, MaryCalls = True)，该 查询的隐变量是 Earthquake 和 Alarm。为方便起见，下面采用英文首字母小写的 形式来表达变量。有P(B | j, m) = αP(B, j, m) = α ∑∑ P( B, e, a, j, m)e a下面分别计算 Burglary = True 和 Burglary = False 时的条件概率。 （1）当 Burglary = True 时，根据贝叶斯网络的语义计算公式可得：P(b | j, m) = α ∑∑ P(b) P(e) P(a | b, e) P( j | a) P(m | a)e a由于 P(b)是常数，P(e)与对 a 求和的项无关，故上式可改写为：P(b | j, m) = αP(b)∑ {P(e)∑[P(a | b, e)P( j | a)P(m | a)]}e a其计算过程如图 10.5 所示。故可得P (b | j , m ) = α × 0 .001 × {[ 0 .002 × ( 0 .95 × 0 .9 × 0 .7 + 0 .05 × 0 .05 × 0 .01)] + [ 0 .998 × ( 0 .94 × 0 .9 × 0 .7 + 0 .06 × 0 .05 × 0 .01)]} = α × 0 .同理，可得 P(?b |j, m) = α × 0.0014919α=1 0. + 0.0014919由于α是归一化常数，故有14因此，最后可得P(B | j, m) = α?0..0014919 ? ≈ ?0.284 ,0.716 ?也就是说， 在两个邻居 John 和 Mary 都给房主打电话的条件下， 出现盗贼的概率 大约是 28％。图 10.6直接枚举法计算过程中所得到的树型结构1510.2.5 贝叶斯网络中的近似推理在实际应用中，对于大规模多连通的贝叶斯网络而言，采用上述精确推理是 不可操作的，所以，考虑近似推理方法是非常必要的。因篇幅所限，下面通过一 个实例简要介绍基于随机采样的贝叶斯网络近似推理方法――马尔可夫链蒙特 卡罗（Markov Chain Monte Carlo，简称 MCMC）方法。 已知：一个简单的多连通贝叶斯网络（网络中两个节点之间可能存在不只一 条路径）如图 10.6 所示。 要求：查询（求解）(Rain | Sprinkler = True, WetGrass = True)的概率。图 10.6一个简单的多连通贝叶斯网络1.MCMC 的算法思想MCMC算法总是对前一个事件进行随机改变而生成每个事件样本，可以认 为贝叶斯网络处于为每一个变量指定了值的当前状态。 而下一个状态是通过对某 个非证据变量Xi进行采样来产生，取决于Xi的马尔可夫覆盖（由节点的父节点、 子节点，以及子节点的父节点组成）中的变量当前值。因此，MCMC方法可视为： 在状态空间（即所有可能的完整赋值空间）中的随机走动，每次改变一个非证据 变量，但证据变量的值固定不变。2.MCMC 算法的执行步骤对于图 10.6 所示的例子而言，可知： z 证据变量：Sprinkler 和 WetGrass 固定为它们的观察值（即 True） 。 16z z z隐变量：Cloudy 随机初始化，例如，Cloudy = True。 查询变量：Rain 随机初始化，例如，Rain = False。 初始状态：[C=true, S=true, R=false, W=true]反复执行如下步骤： （1）根据 Cloudy 的马尔可夫覆盖变量的当前值，对 Cloudy 采样，即根据 P(Cloudy|Sprinkler= True, Rain=False)（即转移概率）来采样。即P(C , S , ?R) P ( S , ?R ) P(C ) P( S | C ) P(?R | C ) = P(C ) P( S | C ) P(?R | C ) + P(?C ) P( S | ?C ) P(?R | ?C ) 0.5 × 0.1 × 0.2 = = 0. × 0.1 × 0.2 + 0.5 × 0.5 × 0.8 P(C | S , ?R) =再由计算机生成一个随机数 q∈[0,1]（可参照《概率统计》中的随机数生成 方法） 。 比较转移概率 P(C|S,?R)与随机数 q 的大小， 以决定是继续停留在原状态， 还是转移到下一个新的状态。判别方法如下： if q & P(C|S, ?R) then 转移到下一个新状态； otherwise 停留在原状态. 对 于 本 例 子 ， 假 设 生 成 的 随 机 数 q=0.0389 ， 可 知 ， 转 移 概 率 P(Cloudy|Sprinkler= True, Rain=False)= 0.04762 & q=0.0389， 所以， Cloudy 由 True 状态转移到新状态 Ffalse，即采样结果为：Cloudy = false。故新的当前状态为： [C=False, S=True, R=False, W=True]。 （2）根据 Rain 节点的马尔可夫覆盖变量的当前值，对 Rain 采样，即根据 P(Rain | Cloudy = False, Sprinkler = Ttrue, WetGrass = True)来采样。假设采样结果 为：Rain = True。故新的当前状态为： [C=False, S=True, R=True, W=True] 需要特别指出的是，上述过程中所访问的每一个状态都是一个样本，能对查 询变量 Rain 的估计有贡献。 （3）重复上述步骤，直到所要求的访问次数N。若为True, False的次数分别 为n1, n2，则查询解为：17Normalize(& n1 , n2 &) =&其中， n1 + n2n1 n2 , & N N== N 。若上述过程访问了 20 个 Rain=True 的状态和 60 个 RainFalse 的状态，则所求查询的解为&0.25, 0.75&。上述过程可用图 10.7 来表示。图 10.7MCMC 算法的执行过程示意图3.MCMC 算法描述function MCMC-Ask(X, e, bn, N) return P(X | e) local variables: N[X]，//关于查询变量 X 的向量计数，初值 0 Z， //bn 中的非证据变量集 x， // bn 的当前状态 利用 Z 中变量的随机值来初始化 x； for j = 1 to N do N(x) ? N(x) + 1; for each Zi in Z do //x 是当前状态 x 中的查询变量 X 的值18给出 Zi 的马尔可夫覆盖 MB(Zi)， 并根据 P(Zi |mb(Zi))采样的 Zi 值; return Normalize(N[X]) //对 N[X]进行归一化 最后需要特别指出的是，上述 MCMC 算法实际上是采用了 MCMC 方法中 最常用的一种简单变体――吉布斯采样器（Gibbs sampler） 。MCMC 是概率模型 计算中的一种强有力的方法，目前已发展出很多变形，包括模拟退火算法、随机 可满足性(Stochastic satisfiability)算法等。1910.3 隐马尔可夫模型隐马尔可夫模型（Hidden Markov Models，简称为 HMM） ，作为一种统计机器学习模型 （Statistical Machine Learning） ，今天正在语音识别、合成等领域获得广泛应用，已经为世界 各国从事语音处理等研究人员所了解和熟悉，是该领域公认的主要技术和研究热点。10.3.1 Markov 过程和 Markov 链HMM 是在 Markov 链的基础上发展起来的，这里我们将首先介绍 Markov 链和 Markov 过 程的一些基本概念。 马尔可夫过程（Markov Process） ：具有无后效性的随机过程。即 tm 时刻所处状态的概率 只和 tm?1 时刻的状态有关，而与 tm?1 时刻之前的状态无关。 马尔可夫链（Markov Chain） ：时间离散、状态离散的马尔可夫过程。它是马尔可夫过程 的特殊情况。从数学上，可以给出如下定义： 随机序列 Xn ，在任一时刻 n ，它可以处在状态 θ1,,θN ，且它在 m + k时刻所处的状态为 qm+k 的概率，只与它在 m 时刻的状态 qm 有关，而与 m 时刻以前它所处状态无关，即 有：P( X m + k = qm + k qm , X m ?1 = qm ?1 , = P( X m + k = qm + k X m = qm ) 其中， q1, q2 ,, X 1 = q1 ), qm, qm+k ∈(θ1,θ2 , ,θN )则称 Xn 为 Markov 链，并且称 P ij (m, m + k ) 为 k 步转移概率，当 P ij (m, m + k ) 与 m 无 关时，称这个 Markov 链为齐次 Markov 链。其中Pi j ( m, m + k ) = P (qm + k = θ j qm = θ i ) 1 ≤ i, j ≤ N , 其中m, k为正整数此时P ij (m, m + k ) = P ij (k )以后若无特别申明，Markov 链就是指齐次 Markov 链。当 k ＝1 时， Pij (1) 称为一步转 移概率，简称为转移概率，记为aij ，所有转移概率 aij ， 1 ≤ i, j ≤ N 可以构成一个转20移概率矩阵，即?a11 a1N ? ? A=? ? ? ? ?aN1 aNN ? ?且有0 ≤ aij ≤ 1，∑aj =1Nij=1由于 k 步转移概率 Pij ( k ) 可由转移概率aij 得到，因此，描述 Markov 链的最重要参数= θ1 的概率，这样，就是转移概率矩阵 A。 但 A 矩阵还决定不了初始分布． 即由 A 求不出 q1完全描述 Markov 链，除 A 矩阵之外，还必须引进初始概率矢量 ，其中πi = P(q1 =θ1),1≤ i ≤ N显然有0 ≤ πi ≤ 1∑πii=1实际中，Markov 链的每一状态可以对应于一个可观测到的物理事件．比如天气预测申的 雨、晴、雪等，那么，这时它可称之为天气预报的 Markov 链模型．根据这个模型，可以算 出各种天气（状态）在某一时刻出现的概率（这是一个离散的马尔可夫模型 Discrite Hidden Markov Model, DHMM） 。10.3.2 基本概念隐 Markov 模型作为数字信号的一种统计模型，今天正在各个领域中获得广泛的应用。有 关它的理论基础， 是在 1970 年前后由 Baum 等人建立起来的， 随后由 CMU 的 Baker 和 IBM 的 Jelinek 等人将其应用到语音识别之中。由于 Bell 实验室 Rabiner 等人在 80 年代中期对 HMM 的深入浅出的介绍，才逐渐使 HMM 为世界各国从事语音处理的研究人员所了解和熟 悉，进而成为公认的一个研究热点。 HMM 是在 Markov 链的基础之上发展起来的．由于实际问题比 Markov 链模型所描述的 更为复杂，观察到的事件并不是与状态―一对应，而是通过一组概率分布相联系，这样的模 型就称为 HMM。它是一个双重随机过程，其中之一是 Markov 链，这是基本随机过程，它 描述状态的转移．另一个随机过程描述状态和观察值之间的统计对应关系．这样，站在观察 者的角度，只能看到观察值，不像 Markov 链模型中的观察值和状态DD对应，因此，不能 直接看到状态， 而是通过一个随机过程去感知状态的存在及其特性。 因而称之为 “隐 Hidden” Markov 模型，即 HMM。现在来看一个著名的说明 HMM 概念的例子（DHMM）DD球和 缸（Ball and Urn）实验，如图 10.8 所示。21缸1 P(红)＝b11 P(蓝)＝b12 P(绿)＝b13 … P(黄)＝b1M缸2 P(红)＝b21 P(蓝)＝b22 P(绿)＝b23 … P(黄)＝b2M……缸N P(红)＝bN1 P(蓝)＝bN2 P(绿)＝bN3 … P(黄)＝bNM图 10.8 球缸实验示意图设有 N 个缸，每个缸中装有很多彩色的球，球的颜色由一组概率分布描述，如图所示。 实验是这样进行的，根据某个初始概率分布，随机地选择 N 个缸中的一个，例如第 i 个缸， 再根据这个缸中彩色球颜色地概率分布，随机地选择一个球，记下球的颜色，记为 O 1 ，再 把球放回缸中，又根据描述缸的转移的概率分布，随机选择下一缸，例如，第 j 个缸，再从 缸中随机选一个球，记下球的颜色，记为 O 2 ，一直进行下去。可以得到一个描述球的颜色 的序列（Sequence） ，由于这是观察到的事件，因而称之为观察值序列。但缸之间的转移以 及每次选取的缸被隐藏起来了，并不能直接观察到。而且，从每个缸中选取球的颜色并不是 与缸一一对应，而是由该缸中彩球颜色概率分布随机决定的。此外，每次选取哪个缸则由一 组转移概率所决定。10.3.3 HMM 的定义有了前面讨论的 Markov 链以及球和缸实验，就可以给出 HMM 的定义。或者说，一个 HMM 可以由下列参数描述： z N：模型中 Markov 链状态数目。记 N 个状态为 θ1, 处状态为 qt ，显然 qt z,θN ，记 t 时刻 Markov 链所∈ (θ1 ,,θ N ) 。在球与缸实验中的缸就相当于状态。 ,VM ，记 t 时刻观M：每个状态对应的可能的观察值数目。记 M 个观察值为 V 1, 察到的观察值为 O t ，其中 O t ∈(V 1, 是观察值。,VM ) 。在球与缸实验中所迷彩球的颜色，就zπ ：初始状态概率矢量， π = (π1, πN ) ，其中 π i 为在球与缸实验中指开始时选取某个缸的概率。 πi= P(q1 =θi ),1≤ i ≤ NzA：状态转移概率矩阵，其中aij 为在球与缸实验中指描述每次在当前选取的缸的条件下选取下一个缸的概率。aij = p(qt +1 = θ j qt = θi ),1 ≤ i, j ≤ Nz B：观察值概率矩阵， B = (bjk ) N×M ，其中 bjk 为在球与缸实验中，就是第 j 个缸中22球的颜色 k 出现的概率。bjk = P(Ot = Vk qt = θ j ),1 ≤ j ≤ N,1 ≤ k ≤ M这样，可以记一个 HMM 为λ = ( N , M , π , A, B )或简写为λ = (π , A , B )更形象地说，HMM 可分为两部分，一个是 Markov 链，由 π , A 描述，产生地输出为状态 序列，另一个是一个随机过程，由 B 描述，产生地输出为观察值序列，如图 10.9 所示。T 为观察值时间长度。 Markov 链 q1,q2,..., qN 状态序列 随机过程 （B ） O1,O2 ,..., OM 观察值序列(π , A)图 10.9 HMM 组成示意图10.3.4 HMM 基本算法 10.3.4.1 基本算法简介HMM的经典算法有三种，分别是：前向-后向算法（Forward-Backward Algorith,有的文献 、Viterbi算法和Baum-Welch算法。下面讨论各种算法的 中也将它们分开成为两种算法讨论 ） 应用： 1. 前向-后向算法1, OT 以及一个模型 λ = (π , A, B ) 这个算法是用来计算给定一个观察值序列 O = O 1, O 2 ,…时，由模型 λ 产生出的 O 概率 P ( O / λ ) 。算法的计算量在 O( N 2 T )数量级，是典型的格 型结构（Lattice） 。 2. Viterbi 算法, OT 和一个模型 λ = (π , A, B ) ，在最 这个算法解决了给定一个观察值序列 O = O 1, O 2 ,…佳意义上确定一个状态序列 Q* * * * = q1 , q2 ,…, qT 的问题。 “最佳”的意义有很多种，由不同的定义可以得到不同的结论。这里讨论的最佳意义上的状态序列 Q ，是指使 P ( Q , O / λ ) 最2*大时确定的状态序列 Q （Maximum Likelihood State Sequence） 。Viterbi算法也是一种格型结1 2*因为前向后向算法定义了各自的算子变量，但这里我们将之归为一种算法。 也可以记为 P (Q / O, λ )23构。它可以由前向-后向算法推倒而来。 3. Baum-Welch 算法 这个算法实际上是解决 HMM 训练，即 HMM 参数估计问题，或者说，给定一个观察值序, OT ，该算法能确定一个 λ = (π , A, B ) ，使 P (O / λ ) 最大。由前向-后向算 列O=O 1, O 2 ,…法知道，这将是一个泛函极值问题。但是，由于给定的训练序列有限，因而不存在一个最佳 算法来估计 λ 。在这种情况下，Baum-Welch 算法利用递归的思想，使 P ( O / λ ) 局部极大， 此外， 用梯度方法也可达到类似目的 （Hill Climing 算法） 。 最后得到模型参数 λ = (π , A , B ) 。10.3.4.2 前向－后向算法前向－后向 算法主要用 来计算 给定一个观 察值序列 O = O 1, O 2,, OT 以及一个模型λ = (π , A , B ) 时，由模型 λ 产生出 O 的概率 P ( O λ ) 。1. 前向算法定义前向变量为：αt (i) = P(O1, O2 , Ot , qt =θi λ) ， 1 ≤ t ≤ T那么，有 (1) 初始化：α1(i) = πibi (O1) ， 1 ≤ i ≤ NN(2)递归： αt +1 ( j) = [∑αt (i)aij ]bj (Ot +1 ) ， 1 ≤ t ≤ T ? 1 ， 1 ≤ j ≤ Ni =1，(3) 终结： P(Oλ ) = ∑αT (i)i =1N24t 时刻递归关系图 10.10 前向算法示意图2. 后向算法与前向算法类似，定义后向变量为βt (i) = P(Ot +1 , Ot + 2 ,其中， β T (i ) = 1 。 类似地，有OT qt = θi , λ ) ， 1 ≤ t ≤ T ? 1（1）初始化： β T (i ) = 1 ， 1 ≤ i ≤ N（2）递归： β t (i ) = ∑ α ij b j (Ot +1 ) β t +1 ( j ) ， t = T ? 1, T ? 2,j =1N,1 ， 1 ≤ i ≤ N（3）终结： P (O λ ) = ∑ β1 (i )i =1N后向算法的计算量大约在 N 2T 数量级，也是一种格型结构。10.3.4.3 Viterbi 算法这个算法决定了一个观察值序列 O = O1 , O2 ,… , OT 和一个模型 λ = (π , A, B ) ，在最佳的 意义上确定一个状态序列 q1 , q2 ,* * * , qT 的问题。25“最佳”的意义有很多种，由不同的定义可以得到不同的结论。这里讨论的最佳意义上的 状态序列 Q ，是指 P (Q, O / λ ) 最大时确定的状态序列 Q 。Viterbi 算法可以叙述如下：* *定义 δ t (i ) 为时刻 t 时沿一条路径 q1 , q2 , 最大概率，即有, qt ，且 qi = θi ，产生出 O1 , O2 ,Ot λ ), Ot 的δ t (i ) = max P(q1 , q2q1 , q2 qt ?1qt , qt = θ i , O1 , O2*那么，求取最佳状态序列 Q 的过程为 （1）初始化： δ (i ) = π i bi (O1 ),1 ≤ i ≤ N?1 (i ) = 0,1 ≤ i ≤ N（2）递归：δ (i ) = max[δ t ?1 (i )aij ]b j (Ot ) ， 2 ≤ t ≤ T ， 1 ≤ j ≤ N1≤ i ≤ N? (i) = arg max[δ t ?1 (i )aij ] ， 2 ≤ t ≤ T ,1 ≤ j ≤ N1≤ i ≤ N（3）终结：P* = max[δ T (i )]1≤i ≤ N * qT = arg max[δ T (i )] 1≤i ≤ N（4）状态序列求取：qt* = ?t +1 (qt*+1 ) ， t = T ? 1, T ? 2,,1上述的 Viterbi 算法是一种格型结构，而且类似于前向算法。同样，由后向算法的思想出 发，亦可推导出 Viterbi 算法的另一种实现方式。10.3.4.4 Baum-Welch 算法该算法主要是解决 HMM 训练，即 HMM 参数估计问题。或者说，给定一个观察值序列O = O1 , O2 ,, OT ，该算法能够确定一个模型 λ = (π , A, B ) ，使 P (O λ ) 最大。由在前向－后向算法中定义的前向和后向变量，有：P (O λ ) = ∑∑ α t (i )aij b j (Ot +1 ) β t +1 ( j )i =1 j =1 N N，1 ≤ t ≤ T ? 126Baum-Welch 算法利用递归的思想，使 P (O λ ) 局部极大，最后得到模型参数λ = (π , A, B) 。定义 ξt (i, j ) 为给定训练序列 O 和模型 λ 时， 时刻 t 时 Markov 链处于 θ i 状态和时刻t + 1 为 θ j 状态的概率，即ξt (i, j ) = P(O, qt = θ i , qt +1 = θ j λ )可以推导出：ξt (i, j ) = [α t (i)aij b j (Ot +1 ) β t +1 ( j )] P(O λ )那么，时刻 t 时 Markov 链处于 θ i 状态的概率为：ξt (i, j ) = P(O, qt = θ i λ ) = ∑ ξt (i, j )j =1N= α t (i ) β t (i ) P(O λ )因此， t =1∑ ξ (i)tT ?1表示从 θ i 状态转移出去的次数的期望值，而 t =1∑ ξ (i, j )tT ?1表示从 θ i 状态转移到 θ j 状态的次数的期望值。由此可以导出 Baum-Welch 算法中著名的重估 (reestimation)公式：π i = ξ1 (i )aij = ∑ ξt (i, j )t =1 T ?1∑ ξ (i)t =1 tT ?1b jk =t =1 且Ok =Vk∑Tξt ( j )∑ξ ( j)t =1 tT推导过程从略(读者可参考 Rabiner 的论文：A tutorial on Hidden Models and Selected Applications in Speech Recognition，这是一篇介绍 HMM 的经典文 献)。那么，HMM 参数 λ = (π , A, B) 的求取过程为，根据观察值序列 O 和选取的初 始模型 λ = (π , A, B) ，由重估公式求得一组新参数π ij，aij，b jk，这样，就得到了一个新的模型 λ = (π , A, B) 。可以证明， P (O λ ) & P (O λ ) ，即由重估公式得到 的 λ 比 λ 在表示观察序列 O 方面要好。那么，重复该过程，逐步改进模型参数， 直到 P (O λ ) 收敛，即不再明显增大，此时的 λ 即为所求之模型。27需要指出的是，HMM 训练或称参数估计问题，是 HMM 在语音处理中应用的关键问题， 与前面讨论的两个问题相比，这也是最困难的一个问题，Baum-Welch 算法只是得到广泛应 用的解决这一问题的经典方法，但并不是唯一的，也远不是最完善的方法。10.3.5 HMM 在语音识别领域的应用隐马尔可夫模型是 70 年代引入语音识别理论的，它的出现使得自然语音识别系统取得了 实质性的突破。HMM 方法现已成为语音识别的主流技术，目前大多数大词汇量、连续语音 的非特定人语音识别系统都是基于 HMM 模型的。 语音信号是通过声源经声道处理产生的， 是一种可观测的时变随机信号序列， 是由大脑根 据语法知识和言语需要(不可观测的状态) 发出的音素的参数流。我们的语音发音是有限的， 所以可认为声道的状态是有限的。我们将人的声道特性划分为有限个特性平稳的部分或状 态，每个状态对声音信号作用产生受该处的声道物理参量决定的短时信号。使用 HMM 时， 我们首先对语音信号的时间序列结构建立统计模型，将之看作一个数学上的双重随机过程： 其一是将声道特性的变化用 HMM 的状态转移概率来描述，用具有有限状态数的 Markov 链 来模拟语音信号统计特性变化的隐含的随机过程， 即状态序列； 其二是某一声道特性产生短 时语音信号观察值的概率分布用 HMM 的状态生成概率表征，从而得到与 Markov 链的每一 个状态相关联的观测序列的随机过程，即观察值序列。前者通过后者表现出来，但前者的具 体参数是不可测的。这样，声道特性的变化用 HMM 的状态转移概率来描述，某一声道特性 产生短时语音信号观察值的概率分布用 HMM 的状态生成概率来描述， HMM 很好地描述 了语音信号的整体非平稳性和局部平稳性，是较为理想的一种语音模型。 具体过程为： z 用前向后向算法 (Forward-Backward) 通过递推方法计算已知模型输出 O 及模型λ = (π , A, B) 时的产生输出序列的概率 P(O / λ ) 。z 用 Baum-Welch 算法， 基于最大似然准则(ML) 对模型参数 λ = (π , A, B ) 进行修正， 最优参数 λ 的求解可表示为 λ = arg max { P (O / λ )} 。**z用 Viterbi 算法解出产生输出序列的最佳状态转移序列 X。所谓最佳是以 X 的最大 条件后验概率为准则，即 X = arg max { P ( X / O, λ )} 。2810.4统计学习理论和支持向量机10.4.1 概述基于数据的机器学习是现代智能技术中的重要方面， 研究从观测数据 （样本） 出发寻找规律， 利用这些规律对未来数据或无法观测的数据进行预测。 迄今为止， 关于机器学习还没有一种被共同接受的理论框架， 关于其实现方法大致可以分为 三种： 第一种是经典的（参数）统计估计方法。统计学是现有机器学习方法（包括 HMM, Logistic Reression, GMM 等）共同的重要理论基础之一。参数方法正是基 于传统统计学的，在这种方法中，参数的相关形式是已知的，训练样本用来估计 参数的值。这种方法有很大的局限性，首先，它需要已知样本分布形式，这需要 花费很大代价，还有，传统统计学研究的是样本数目趋于无穷大时的渐近理论， 现有学习方法也多是基于此假设。 但在实际问题中， 样本数往往是有限的， 因此， 一些理论上很优秀的学习方法在实际中的表现却可能不尽人意。 第二种方法是经验非线性方法，如人工神经网络（ANN） 。这种方法利用已 知样本建立非线性模型，克服了传统参数估计方法的困难。但是，这种方法缺乏 一种统一的数学理论。 与传统统计学相比，统计学习理论（Statistical Learning Theory，简称 SLT） 是一种专门研究小样本情况下机器学习规律的理论。 该理论针对小样本统计问题 建立了一套新的理论体系， 在这种体系下的统计推理规则不仅考虑了对渐近性能 的要求，而且追求在有限信息的条件下得到最优结果。Vladimir N. Vapnik 等人 从 20 世纪 60 年代开始致力于统计学习理论的研究，到 20 世纪 90 年代中期，随 着该理论的不断发展和成熟， 也由于神经网络等学习方法在理论上缺乏实质性进 展，统计学习理论开始受到越来越广泛的重视。 统计学习理论的一个核心概念就是 VC 维(VC Dimension)概念，它是描述函 数集或学习机器的复杂性或者说是学习能力(Capacity of the machine)的一个重要 指标，在此概念基础上发展出了一系列关于统计学习的一致性(Consistency)、收 敛速度、推广性能(Generalization Performance)等的重要结论。 统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学习 问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望解决许多原来 难以解决的问题（比如神经网络结构选择问题、局部极小点问题等） ；同时，在 该理论基础上发展了一种新的通用学习方法──支持向量机（ Support Vector Machine，简称 SVM） ，已初步表现出很多优于已有方法的性能。一些学者认为， SLT 和 SVM 正在成为继神经网络研究之后新的研究热点，并将推动机器学习理 论和技术有重大的发展。 支持向量机方法是建立在统计学习理论的 VC 维理论和结构风险最小化29（Structural Risk Minimization，简称 SRM）原理基础上的，根据有限的样本信息 在模型的复杂性（即对特定训练样本的学习精度）和学习能力（即无误识别任意 样本的能力）之间寻求最佳折衷，以期获得最好的推广能力 (Generalization Ability)。支持向量机方法的几个主要优点有： z 专门针对有限样本情况，其目标是得到现有信息下的最优解而不仅仅是 样本数趋于无穷大时的最优值； z 算法最终将转化为一个二次规划（QP）问题，从理论上说，得到的将是 全局最优点，解决了在神经网络方法中无法避免的局部极值问题； z 算法将实际问题通过非线性变换转换到高维的特征空间(Feature Space)， 在高维空间中构造线性判别函数来实现原空间中的非线性判别函数，从 而保证学习机器有较好的推广能力，同时它巧妙地解决了维数问题（只 需计算原始空间的两个向量的内积） ，其算法复杂度与样本维数无关。 在 SVM 方法中，只要定义不同的内积函数，就可以实现多项式逼近、贝叶 斯分类器、径向基函数(Radial Basic Function，简称 RBF)方法、多层感知器网络 等许多现有学习算法。 统计学习理论从 20 世纪 60 年代末诞生， 到 20 世纪 90 年代之前都处在初级 研究和理论准备阶段，近几年才逐渐得到重视，其本身也趋向完善，并产生了支 持向量机这一将这种理论付诸实现的有效的机器学习方法。目前，SVM 算法在 模式识别、回归估计、概率密度函数估计等方面都有非常成功的应用。例如，在 模式识别方面， 对于手写数字识别、 语音识别、 人脸图像识别、 文本分类等问题， SVM 算法在精度上已经超过传统的学习算法或与之不相上下。 目前，国际上对 SLT 和 SVM 的研究和应用方兴未艾，我国学者从 20 世纪 90 年代末开始引进并翻译关注该理论的重要著作，并及时学习掌握有关理论， 同时开展了有效的研究和应用工作， 以期在这一有着重要意义的领域中能够尽快 赶上国际先进水平。由于 SLT 理论和 SVM 方法尚处在发展阶段，很多方面尚不 完善，比如：许多理论目前还只有理论上的意义，尚不能在实际算法中实现；而 有关 SVM 算法某些理论解释也并非完美（J. C. Burges 曾提到结构风险最小原理 并不能严格证明 SVM 为什么有好的推广能力） ；此外，对于一个实际的学习机 器的 VC 维的分析尚没有通用的方法；SVM 方法中如何根据具体问题选择适当 的核（内积）函数也没有理论依据。因此，在这方面可做的研究探索工作还有很 多。10.4.2 基本概念1. 统计方法统计方法的基本目的是从观测自然现象或者专门安排的实验所得到的数据 （样本）去推断该事务可能具有的规律性。302. 统计学习理论（SLT）统计学习理论是在研究小样本统计估计和预测的过程中发展起来的一种新 兴理论。需要特别指出的是，这里所说的小样本是相当于无穷样本而言的，只要 样本数不是无穷多，都可称为小样本。3. 支持向量机（SVM）支持向量机方法是一种建立在统计学习理论基础上， 根据有限样本信息在模 型的复杂性和学习能力之间寻求最佳折衷， 以期获得最好的推广能力的新的通用 机器学习方法。4. SLT&SVM 与传统机器学习方法的不同传统的机器学习方法认为，实际问题中总存在较少数目的一些“强特征” ， 用它们的简单函数（如线性组合）就能较好地逼近未知函数。因此，需要仔细地 选择一个低维的特征空间，在这个空间中用常规的统计技术来求解一个逼近。 而统计学习理论和支持向量机则认为，实际问题中存在较大数目的一些“弱 特征” ，它们“巧妙的”线性组合可较好地逼近未知的依赖关系。因此，采用什 么样的“弱特征”并不十分重要，而形成“巧妙的”线性组合更为重要。10.4.3 学习问题的表示1. 机器学习的基本问题根据样本学习的一个典型模型如图 10.11 所示。GXSyLM y图 10.11 一个典型的机器学习模型 在图 10.11 中，产生器 G 生成随机向量 x∈Rn ,它们是从固定但未知的概率 分布函数 P(x)中独立抽取的；训练器 S 对每个输入向量 x 返回一个输出值 y，产 生输出的根据是同样固定但未知的条件分布函数 P(y|x)； 学习机器 LM 能够实现 一定的函数集 f(x,α)，α∈ ，其中 是参数集合。31机器学习的问题就是从给定的函数集f(x, α)(α∈)中选择出能够最好地逼近训练器响应的函数。机器学习问题可形式化地表示为：根据n个独立同分布的 观测样本， (x1, y1), (x2, y2), …, (xn, yn)， 在一组函数{ f(x, α)}中求出一个最优函数f(x, α0)对训练器的响应进行估计，使期望风险最小，即R (α ) =∫L ( y , f ( x ,α ))d P ( x , y )P(x,y)是未知的概率分布函数， L(y, f(x, α))为损失函数 （Cost Function） ， 其中， 对于不同类型的机器学习问题有不同形式的损失函数。根据损失函数的不同，可 将机器学习问题分为 3 大类，分别是模式识别、回归函数估计和概率密度估计。2. 经验风险最小化原则（ERM）对于未知的概率分布 P(x,y),若要最小化风险函数 R(α),只有样本的信息可 以利用，这导致了定义的期望风险是无法直接计算和最小化的问题。根据概率论 中大数定理的思想,人们用算术平均代替数学期望,于是定义了经验风险泛函：Remp ( w) =1 n ∑ L( yi , f ( xi , w)) n i =1来逼近期望风险。使用对参数w求经验风险Remp(w)的最小值代替求期望风险R(w) 的最小值，就是所谓的经验风险最小化(Empirical Risk Minimization，简称ERM) 原则。遗憾的是，从期望风险最小化到经验风险最小化并没有可靠的理论依据， 这只是直观上合理的想当然。期望风险和经验风险都是 w 的函数，概率论中的 大数定理只说明了当样本趋于无穷多时经验风险将在概率意义上趋近于期望风 险，并没有保证两个风险的 w 是同一点，更不能保证经验风险能够趋近于期望 风险。即使有办法使这些条件在样本数无穷大时得到保证，也无法认定在这些前 提下得到的经验风险最小化方法在样本数有限时仍能得到好的结果。3. 复杂性与推广能力复杂性 在样本有限的情况下，经验风险最小并不一定意味着期望风 险最小，学习机器的复杂性不但与所研究的系统有关，而且要和有限的 学习样本相适应。 z 推广能力 学习机器对未来输出进行正确预测的能力称作推广能力。 在有限样本情况下，学习精度和推广性之间似乎是一对不可调和的矛盾，采 用复杂的学习机器虽然容易使得学习误差更小，却往往丧失推广性。在某些情况 下，训练误差过小反而导致推广能力的下降，这就是过学习问题(overfitting)。 事实上，神经网络的过学习问题就是经验风险最小化原则失败的一个典型例子。 z32因此，人们研究了很多解决办法，如采用正则化、模型选择、噪声干扰等方法以 控制学习机器的复杂度，但这些方法都缺乏完善的理论基础。10.4.4 统计学习理论的核心内容统计学习理论被认为是目前针对小样本统计估计和预测学习的最佳理论。 它 从理论上较为系统地研究了经验风险最小化原则成立的条件、 有限样本条件下经 验风险与期望风险的关系， 以及如何利用这些理论找到新的学习原则和方法等问 题。概括地说，统计学习理论的主要研究内容包括： z 基于经验风险原则的统计学习过程的一致性理论 z 学习过程收敛速度的非渐进理论 z 控制学习过程的推广能力的理论 z 构造学习算法的理论1. VC 维为了研究经验风险最小化函数集的学习一致收敛速度和推广性， 统计学习理 论 定 义 了 一 些 指 标 来 衡 量 函 数 集 的 性 能 ， 其 中 最 重 要 的 就 是 VC 维 (Vapnik-Chervonenkis Dimension)。对于一个指示函数（即只有 0 和 1 两种取值 的函数）集，如果存在h个样本能够被函数集里的函数按照所有可能的 2h种形式 分开，则称函数集能够把h个样本打散。函数集的VC维就是能够打散的最大样本 数目。 如果对任意的样本数， 总有函数能打散它们， 则函数集的VC维就是无穷大。 一般而言，VC 维越大，学习机器的学习能力越强，但学习机器也越复杂。 目前还没有通用的关于计算任意函数集的 VC 维的理论，只有对一些特殊函数集 的 VC 维可以准确知道。例如，N 维实数空间中线性分类器和线性实函数的 VC 维 是 n+1，Sin(ax)的 VC 维为无穷大。对于给定的学习函数集，如何用理论或实验 的方法计算其 VC 维是当前统计学习理论研究中有待解决的一个重要问题。2. 推广性的界统计学习理论系统地研究了经验风险和实际风险之间的关系， 也即推广性的 界。根据统计学习理论中关于函数集推广性的界的理论，对于指示函数集中所有 的函数，经验风险Remp(α)和实际风险R(α)之间至少以概率 1-η满足如下关系：R (α ) ≤ Remp (α ) +h(ln(2n / h) + 1) ? ln(η / 4) n其中，h 是函数集的 VC 维，n 为样本数。 学习机器的实 由上述经验风险Remp(α)和实际风险R(α)之间的关系公式可知， 际风险由两部分组成： （1）训练样本的经验风险； （2）置信范围(同置信水平 1-η 有关，且与学习机器的VC维和训练样本数有关)。即n R (α ) ≤ Remp (α ) + Φ ( ) 33 h在训练样本有限的情况下，学习机器的 VC 维越高，则置信范围就越大，导 致实际风险与经验风险之间可能的差就越大。在设计分类器时，不但要使经验风 险最小化，还要使 VC 维尽量小，从而缩小置信范围，使期望风险最小化。寻找 反映学习机器能力的更好参数从而得到更好的界是今后学习理论的重要研究方 向之一。3. 结构风险最小化（SRM）原则传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是 不合理的，因此，需要同时最小化经验风险和置信范围。统计学习理论提出了一 种新的策略，即把函数集构造为一个函数子集序列，使各个子集按照 VC 维的大 小排列；在每个子集中寻找最小经验风险，在子集间折衷考虑经验风险和置信范 围，取得实际风险的最小化，这种思想被称作结构风险最小化(Structural Risk Minimization)，即 SRM 原则。真实风险的界与经验风险、置信范围的关系如图 10.12 所示。图 10.12 真实风险的界与经验风险、置信范围的关系 实现 SRM 原则可以有两种思路： （1）在每个子集中求最小经验风险，然后选 择使最小经验风险和置信范围之和最小的子集。 （2）设计函数集的某种结构使每 个子集中都能取得最小的经验风险， 然后， 只需选择适当的子集使置信范围最小， 则这个子集中使经验风险最小的函数就是最优函数。 支持向量机方法实际上就是 第二种思路的实现。10.4.5 支持向量机（SVM）1963 年 Vapnik 在解决模式识别问题时提出了支持向量方法，这种方法从训 练集中选择一组特征子集，使得对特征子集的划分等价于对整个数据集的划分， 这组特征子集就被称为支持向量（Support Sector，简称 SV） 。1971 年 Kimeldorf 提出使用线性不等约束重新构造 SV 的核空间，解决了一部分线性不可分问题。 从 1990 年开始， Vapnik， Grace 和 Boser 等人开始对 SVM 进行研究， 1995 年 Vapnik 等人正式提出基于统计学习理论的支持向量机方法。341. SVM 的基本思想及理论SVM 是从线性可分情况下的最优分类面发展而来的， 基本思想可用图 10.13 所示的 2 维情况说明。图 10.13 最优分类面 图中，实心点和空心点分别代表两类样本，H为分类线，H1，H2分别为过各类中 离分类线最近的样本且平行于分类线的直线，它们之间的距离叫做分类间隔 （margin） 。所谓最优分类线就是要求分类线不但能将两类正确分开（训练错误 率为 0） ，而且使分类间隔最大。分类线方程为 x ? w + b = 0 ，可对其进行归一化， 使得对线性可分的样本集 ( xi , yi ) ， i = 1,..., n ， x ∈ R d ， y ∈ {+1,?1} ，满足yi [( w ? xi ) + b] ? 1 ≥ 0 , i = 1,,n2(10-1)2此时分类间隔等于 2/||w||， 使间隔最大等价于使||w|| 最小。 满足条件(1)且使 1 2 w最小的分类面就叫做最优分类面，H1，H2上的训练样本点就称作支持向量。 利用 Lagrange 优化方法可以把上述最优分类面问题转化为其对偶问题，即 在约束条件∑yαi =1 ini= 0,(10-2a) (10-2b)和 αi ≥ 0 下对αi求解下列函数的最大值：Q (α ) = ∑ α i ?i =1 ni=1，…n1 n ∑α iα j yi y j ( xi ? x j ) 2 i , j =1(10-3)αi为原问题中与每个约束条件（1）对应的Lagrange乘子。这是一个不等式约束下二次函数寻优的问题，存在唯一解。可以证明，解中将只有一部分（通常是少部 分）αi不为零，对应的样本就是支持向量。解上述问题后得到的最优分类函数是35?n ? f ( x ) = sgn{( w ? x ) + b} = sgn ?∑ α i* y i ( xi ? x ) + b* ? , ? i =1 ?(10-4)式中的求和实际上只对支持向量进行。 b*是分类阈值， 可以用任一个支持向量 （满 足(1)中的等号）求得，或通过两类中任意一对支持向量取中值求得。对非线性 问题，可以通过非线性变换转化为某个高维空间中的线性问题，在变换空间求最 优分类面。这种变换可能比较复杂，因此这种思路在一般情况下不易实现。但是 注意到，在上面的对偶问题中，不论是寻优目标函数(3)还是分类函数(4)都只涉 及训练样本之间的内积运算 ( xi ? x j ) 。设有非线性映射Φ：R → Η将输入空间的 样本映射到高维（可能是无穷维）的特征空间Η中。当在特征空间H中构造最优 超平面时，训练算法仅使用空间中的点积，即Φ(xi).Φ(xj)，而没有单独的Φ(xi) 出现。因此，如果能够找到一个函数K使得K( xi , xj )=Φ(xi).Φ(xj)，这样，在高 维空间实际上只需进行内积运算， 而这种内积运算是可以用原空间中的函数来实 现的，甚至没有必要知道变换Φ的形式。根据泛函的有关理论，只要一种核函数dK( xi，xj)满足Mercer条件，它就对应某一变换空间中的内积。 因此，在最优分类面中采用适当的内积函数K( xi，xj)就可以实现某一非线性 变换后的线性分类，而计算复杂度却没有增加，此时目标函数(3)变为：Q (α ) = ∑α i ?i =1 n1 n ∑ α iα j y i y j K ( x i , x j ) , 2 i , j =1(10-5)而相应的分类函数也变为f ( x ) = sgn(∑ α i* yi K ( xi , x ) + b* ) ，i =1n(10-6)这就是支持向量机。 这一特点提供了解决算法可能导致的“维数灾难”问题的有效方法，即在构 造判别函数时，不是对输入空间的样本作非线性变换，然后在特征空间中求解， 而是先在输入空间比较向量（例如，求点积或是某种距离） ，对结果再作非线性 变换。这样，大的工作量将在输入空间而不是在高维特征空间中完成。SVM 分 类函数形式上类似于一个神经网络，输出 y 是中间节点的线性组合，每个中间节 点对应一个支持向量，如图 10.14 所示。36图 10.14 支持向量机示意图 图中，输入向量 x = ( x1 , x 2 ,..., x d ) ，中间节点为基于 s 个支持向量 x1 , x2 ,..., xs 的非 线性变换（即向量内积） ，输出（决策规则）由如下指示函数计算而得：y = sgn(∑ α i yi K ( xi , x ) + b )i =1s其中， α i yi 为中间各节点所对应的权值。2. 均衡经验风险和推广能力的 SVM显然，上面的方法在保证训练样本全部被正确分类，即经验风险Remp为 0 的 前提下，通过最大化分类间隔来获得最好的推广性能。如果希望在经验风险和推 广性能之间求得某种均衡，可以通过引入正的松弛因子ξi来允许错分样本的存 在。这时，约束（1）变为yi [( w ? xi ) + b] ? 1 + ξ i ≥ 0 , i = 1,2n,n(10-7)而在目标最小化 1 w 中加入惩罚项 C ∑i =1 ξ i ，这样，Wolf 对偶问题可以写成： 2Maximize:Q (α ) = ∑ α i ?i =1n1 n ∑α iα j yi y j K ( xi , x j ) 2 i , j =1(10-8)s.t.∑yαi =1 ini=0(10-9a)0 ≤ αi ≤ C i=1，…n (10-9b) 这就是 SVM 方法的最一般的表述，接下来就是 QP 问题，可以用常用的优 化算法求解。373. 一个简单的实例已知 4 个样本及其分类情况如下：x1 =(0, 0)，y1 = +1；x2 =(1, 0)，y2 = +1；x3 =(2, 0)，y3 = -1；x4 =(0, 2)，y4 = -1。试求将上述两类样本分开的最优分类线。【解】 ：由上述公式（10-8）可得1 2 2 Q(α ) = (α1 + α 2 + α 3 + α 4 ) ? (α 2 ) ? 4α 2α 3 + 4α 32 + 4α 4 2利用上述公式（10-9a）可得α1 y1＋ α2 y2＋ α3 y3＋ α4 y4 = 0 将y1 = +1，y2 = +1，y3 = -1，y4 = -1 分别代入上式，得α1＋α2－α3－α4 = 0至此，调用 Matlab 二次规划程序，求得α1，α2，α3，α4的值，进而求得 w 和b的值。同时，支持向量是x2 =(1, 0), x3 =(2, 0), x4 =(0, 2)?α 1 ?α ? 2 ? ?α 3 ? ?α 4= 0 =1 = 3/4 = 1/4 1 2 1 2 ? ? ? ? ? ?? ?? 1 2 0 ? ? 3 ? ? 1 ? ? w = ? ? ? ? ? ? ? ? = ? ?0 ? 4 ?0 ? 4 ?2? ?? ? ? 1 ? 1 1 ? ?3 ? 3 b = ? ?? , ? ? ? ? = 2 ? 2 2 ? ?0 ? 4 g ( x ) = 3 ? 2 x1 ? 2 x 2 = 0从而，可知，g(x) = 3-2x1-2x2 = 0 即为所求的最优分类线方程，如图 10.15 所示。38g(x)x4x1x2x3图 10.15 样本分布及其最优分类线4. SVM 与神经网络的对比显然，SVM 的理论基础比神经网络（Neural Network，简称 NN）更坚实，更 像一门严谨的“科学” （科学的三要素是： 问题的表示、 问题的解决、 数学证明） 。 SVM 是经过严格的数学推理而得，而神经网络则强烈依赖于设计者的工程技巧。 理论证明推广能力取决于“经验风险值”和“置信范围值”的折衷，SVM 能够很 好地在这两者中求得均衡，然而，神经网络却不能控制两者中的任何一个。所幸 的是，神经网络的设计者用高超的工程技巧弥补了数学上的缺陷，通过设计特殊 的结构，并利用启发式算法，有时也能得到一些出人意料的好结果。10.4.6 SVM 算法研究进展1. SVM 算法存在的问题由于 SVM 方法有较好的理论基础及其在一些领域的应用中表现出来的优秀 的推广性能，近年来，许多关于 SVM 方法的研究，包括算法本身的改进及实际 应用，受到了广泛的关注。尽管 SVM 算法的性能在许多实际问题的应用中得到 了验证，但是该算法在计算上存在着一些问题，包括训练算法速度慢、算法复杂 而难以实现，以及检测阶段运算量大等。 传统的利用标准二次型优化技术解决对偶问题的方法可能是训练算法慢的 主要原因。首先，SVM 方法需要计}