浙江大学远程教育学院人工智能讲座

浙江大学远程教育学院《人工智能》讲座徐从富(CongfuXu)

PhD,AssociateProfessorEmail:xucongfu@InstituteofArtificialIntelligence,CollegeofComputerScience,ZhejiangUniversity,Hangzhou310027,P.R.ChinaDecember4,2006第二讲人工智能原理及应用

(Lecture2Principles&ApplicationsofAI)1提纲知识表示专家系统人工神经网络不确定性推理机器学习数据挖掘AI的若干研究前沿22.1知识表示知识是智能的基础获得知识运用知识符合计算机要求的知识模式计算机能存储、处理的知识表示模式数据结构（List,Table,Tree,Graph,etc.）2.1.1知识表示的重要性3数据(Data)信息的载体和表示用一组符号及其组合表示信息信息(Information)数据的语义数据在特定场合下的具体含义知识

(Knowledge)信息关联后所形成的信息结构：事实&规则经加工、整理、解释、挑选、改造后的信息2.1.2数据、信息与知识42.1.3知识的特性相对正确性一定条件下某种环境中......不确定性存在“中间状态”“真”（“假”）程度随机性模糊性经验性不完全性......可表示性&可利用性语言文字图形图像视频音频神经网络概率图模型......52.1.4知识的分类常识性知识、领域性知识（作用范围）事实性知识、过程性知识、控制知识（作用及表示）确定性知识、不确定性知识（确定性）逻辑性知识、形象性知识（结构及表现形式）零级知识、一级知识、二级知识（抽象程度）62.1.5常用的知识表示方法一阶谓词（FirstOrderPredicate）产生式（Production）框架（Framework）语义网络（SemanticNetwork）剧本（Script）过程（Procedure）面向对象（Object-Oriented）Petri网（PetriNetwork）信念网（BeliefNetwork）本体论（Ontology）……72.1.6如何选择合适的知识表示方法？充分表示领域知识有利于对知识的利用便于理解和实现便于对知识的组织、管理与维护82.1.7一阶谓词表示法1.何谓一阶谓词？定义谓词：就是带参数的命题。谓词公式：用连词（,,等）把原子谓词公式组成的合适公式。举例CITY(X),~HUMAN(X),INROOM(ROBOT,R1),etc.HUMAN(X)LAWED(X)，表示：人人都受法律管制{[HUMAN(X)LAWED(X)][COMMIT(X)PUNISHED(X)]}，表示：如果由于某个X是人而受到法律管制，则这个人犯了罪就一定要受到惩罚。9SyntaxitemUsuallyusedOthers取反：Negation(not)~P,PP（加上划线）合取：Conjunction(and)PQP&QP·QPQP,Q析取：Disjunction(or)PQP|QP;QP+Q蕴涵：Implication(if)PQPQPQ等价：Equivalence(iff)PQPQPQ全称量词：Universal(all)(x)P(x)xP(x)xP(x)存在量词：Existential(exists)(x)P(x)xP(x)xP(x)关系：RelationR(x,y)(Rxy)RxyxRy2.常用的谓词公式表示方法对照表103.谓词公式的表达方法举例实例1试用谓词演算表示如下英文句子：“Foreverysetx,thereisasety,suchthatthecardinalityofyisgreaterthanthecardinalityofx.”对应的谓词公式：(x){SET(x)(y)(u)(v)[SET(y)CARD(y,u)CARD(x,v)G(u,v)]}实例2“世上决没有无缘无故的爱，也没有无缘无故的恨。”对应的谓词公式：x[爱(x)y缘故(x,y)]t[恨(t)s缘故(t,s)]114.一阶谓词表示法的优、缺点(1)优点自然性接近自然语言，容易接受精确性用于表示精确知识严密性有严格的形式定义和推理规则易实现性易于转换为计算机内部形式12一阶谓词表示法的优、缺点（续）(2)缺点无法表示不确定性知识所能表示的知识范围太狭窄难以表示启发性知识及元知识未能充分利用与问题本身特性有关的知识组合爆炸经常出现事实、规则等的组合爆炸效率低推理与知识的语义完全割裂132.1.8产生式表示法1943年E.Post第一次提出称为“Post机”的计算模型一种描述形式语言的语法AI中应用最多的知识表示方法之一Feigenbaum研制的化学分子结构专家系统DENDRALShortliffe研制的的诊断感染性疾病的专家系统MYCIN……14

PQ

CF=[0,1]或IFPTHENQCF=[0,1]其中，P是产生式的前提，Q是一组结论或操作，CF(CertaintyFactor)为确定性因子，也称置信度。

【说明】：谓词逻辑中的蕴涵式与产生式的基本形式相似，事实上，蕴涵式只是产生式的一种特殊情况。1.产生式的基本形式152.产生式系统的优、缺点(1)产生式系统的优点

a）自然性：由于产生式系统采用了人类常用的表达因果关系的知识表示形式，既直观、自然，又便于进行推理。

b）模块性：产生式是规则库中的最基本的知识单元，形式相同，易于模块化管理。

c）有效性：能表示确定性知识、不确定性知识、启发性知识、过程性知识等。

d）清晰性：产生式有固定的格式，既便于规则设计，又易于对规则库中的知识进行一致性、完整性检测。16（2）产生式系统的缺点

a）效率不高产生式系统求解问题的过程是一个反复进行“匹配—冲突消解—执行”的过程。由于规则库一般都比较庞大，而匹配又是一件十分费时的工作，因此，其工作效率不高。此外，在求解复杂问题时容易引起组合爆炸。

b）不能表达具有结构性的知识产生式系统对具有结构关系的知识无能为力，它不能把具有结构关系的事物间的区别与联系表示出来，因此，人们经常将它与其它知识表示方法（如框架表示法、语义网络表示法）相结合。173.产生式系统的适用领域

（1）由许多相对独立的知识元组成的领域知识，彼此之间关系不密切，不存在结构关系。如：化学反应方面的知识。（2）具有经验性及不确定性的知识，而且相关领域中对这些知识没有严格、统一的理论。如：医疗诊断、故障诊断等方面的知识。（3）领域问题的求解过程可被表示为一系列相对独立的操作，而且每个操作可被表示为一条或多条产生式规则。182.1.9框架表示法1.框架理论

1975年美国著名AI学者Minsky在其论文“Aframeworkforrepresentingknowledge”中提出了框架理论，并把它作为理解视觉、自然语言对话及其它复杂行为的基础。

框架理论的基本思想：认为人们对现实世界中各种事物的认识都是以一种类似于框架的结构存储在记忆中的，当面临一个新事物时，就从记忆中找出一个合适的框架，并根据实际情况对其细节加以修改、补充，从而形成对当前事物的认识。19

2.框架的一般表示形式<框架名>槽名1： 侧面名1 值1，值2，...，值p1 侧面名2 值1，值2，...，值p2 侧面名m1 值1，值2，...，值pm1槽名n： 侧面名1 值1，值2，...，值r1约束： 约束条件1 约束条件n203.框架及其实例框架名： tx未遂杀人案犯罪意图： x犯罪结果： 杀人被杀者： y杀人动机： x未遂被y发现知情人： {zi|iI}罪犯： t条件一： 若x为强奸，则t必须是男性条件二： 有某个zi指控t条件三： t招认

在《聊斋志异》中有个《胭脂》的故事，开始时邑宰判错了案，就是因为他头脑里有个破案的框架：21

框架实例： 鄂秋準强奸未遂杀人案犯罪意图： 强奸犯罪结果： 杀人被杀者： 卞牛医杀人动机： 强奸未遂被卞牛医发现知情人： 卞妻，胭脂罪犯： 鄂秋準

条件一： 鄂秋準为男性，成立条件二： 胭脂指控鄂秋準，成立条件三： 鄂秋準招认，成立

邑宰用上述框架去套胭脂一案，结果得到了该框架的一个实例：224.框架表示法的优、缺点（1）优点

a）结构性b）继承性c）自然性

（2）缺点不善于表达过程性的知识，经常与产生式表示法结合起来使用，以取得互补的效果。232.1.10语义网络表示法1.语义网络的提出及基本思想

1968年J.R.Quillian在其博士论文中最先提出语义网络，把它作为人类联想记忆的一个显式心理学模型，并在他设计的可教式语言理解器TLC(TeachableLanguageComprehenden)中用作知识表示方法。

语义网络的基本思想：在这种网络中，用“节点”代替概念，用节点间的“连接弧”(称为联想弧)代替概念之间的关系，因此，语义网络又称联想网络。它在形式上是一个带标识的有向图。由于所有的概念节点均通过联想弧彼此相连，Quillian希望他的语义网络能用于知识推导。242.语义网络举例

与歌曲《军港之夜》中的歌词“海浪把战舰轻轻地摇”对应的语义网络：全域行为事物方式海浪战舰摇动轻轻某港海浪某港战舰子集子集子集子集子集个体个体子集个体动作对象动作方式动作主体253.语义网络表示法的优、缺点

（1）语义网络表示法的优点

a）结构性：因为语义网络是一种结构化的知识表示方法，它能把事物的属性以及事物间的各种语义联想显式地表示出来。

b）联想性：它最初是作为人类联想记忆模型提出来的。

c）自然性：直观地把事物的属性及其语义联系表示出来，便于理解，自然语言与语义网络的转换比较容易实现，故语义网络表示法在自然语言理解系统中的应用最为广泛。26

（2）语义网络表示法的缺点

a）非严格性：与一阶谓词逻辑相比，语义网络没有公认的形式表示体系。一个给定的语义网络所表达的含义完全依赖于处理程序如何对它进行解释。通过推理网络而实现的推理不能保证其正确性。此外，目前采用的表示量词（包括全称量词和存在量词）的语义网络表示法在逻辑上是不充分的，不能保证不存在二义性。

b）处理上的复杂性：语义网络表示知识的手段多种多样，虽然灵活性很高，但同时也由于表示形式的不一致使得对其处理的复杂性提高，对知识的检索也就相对复杂，要求对网络的搜索要有强有力的组织原则。272.1.11剧本（脚本）表示法

剧本表示法是1975年R.C.Schank依据他的概念依赖理论而提出的一种知识表示方法。脚本与框架类似，由一组槽组成，用来表示特定领域内一些事件的发生序列。1.概念依赖理论

【难点】在人类的各种知识中，常识性知识是数量最多、涉及面最宽、关系最复杂的知识，很难把它们形式化地表示出来交给计算机处理。概念依赖理论的基本思想：把人类生活中各类故事情节的基本概念抽取出来，构成一组原子概念，确定这些原子概念间的相互依赖关系，然后把所有故事情节都用这组原子概念及其依赖关系表示出来。28

2.剧本（脚本）的构成

1、剧本：描述特定范围内原型事件的结构。

2、剧本的组成（1）进入条件：指出剧本所描述的事件可能发生的先决条件，即事件发生的前提条件。（2）角色：描述事件中可能出现的人物。（3）道具：描述事件中可能出现的有关物体。（4）场景：描述事件序列，可以有多个场景。（5）结局：给出剧本所描述的事件发生以后必须满足的条件。29广义的知识表示语言任何程序设计语言例如：C,C++,Java,XML,etc.狭义的人工智能语言把知识和智能传授给计算机的表示语言专门用于编程求解AI问题典型代表：LISP语言、PROLOG语言……2.1.12知识表示语言301.LISP语言概况提出：1960年，美国AI之父McCarthy首次给出含义：LISP是LIStProcesser（表处理器）之意目的：为处理AI中的符号编程问题而设计理论基础：符号集上的递归函数论地位：AI历史上第一个，且使用范围最广泛的符号处理语言，为AI的发展做出重大贡献【说明】:详细语法可参见陆汝钤的《人工智能》（下册）312.PROLOG语言概况提出：1973年，马赛大学的Colmerauer首次给出含义：是PROgramminginLOGic之意目的：专门用于处理AI中的逻辑推理问题理论基础：一阶谓词演算的归结(Resolution)原理作用：给一阶谓词演算中的说明性命题以过程性解释【说明】:详细语法可参见陆汝钤的《人工智能》（下册）321.概述定义专家系统（ExpertSystems,ES）是一种以知识为基础、能对某一专门领域的问题提供“专家级”解答的计算机程序。发展简况1968年Stanford大学Feigenbaum开发成功世界上第一个专家系统——DENDRAL1977年Feigenbaum在IJCAI’77上提出“知识工程”……2.2专家系统332.专家系统的成功范例(以农业为例)美国的农业专家系统1986年开发的COMAX/GOSSYM系统加州大学Davis分校开发的CALEX系统农业专家系统开发工具：LEVEL5,VP-EXPERT,INSIGHT,etc.……中国的农业专家系统中科院智能机械所开发的施肥专家系统中国农科院作物研究所开发的品种选育专家系统华中理工大学开发的园艺专家系统浙江大学与中国农科院联合开发的蚕育种专家系统、饲料配方专家系统……343.专家系统的基本结构解释器知识库知识库管理推理机知识获取界面网络35关于专家系统的基本结构的说明推理机、知识库：是专家系统中最核心部分知识库管理：检查知识的内容是否有问题知识获取：是知识工程的瓶颈解释器：解释推理的结果及在推理过程中发生的一切界面：是让专家系统“接近群众”的重要手段网络接口：网上多个专家系统可构成分布式专家系统364.专家系统的生命周期第一阶段：需求分析（REQ）第二阶段：系统设计（DES）第三阶段：知识获取（ACQ）第四阶段：原型测试（PRT）第五阶段：知识求精（REF）第六阶段：系统包装（PCK）第七阶段：系统集成（ITG）【说明】：第七阶段并非最后阶段，后面阶段可返回到前面阶段。系统维护，特别是知识维护就体现在这种循环中。372.3人工神经网络

生理神经元的结构人工神经网络的组成人工神经网络的数学描述典型的人工神经网络BP网简介【注】：关于人工神经网络的详细原理及应用可参见：MartinT.Hagan等著,戴葵等译.《神经网络设计》,机械工业出版社,2002.382.3.1神经元的组成部分示意图392.3.2生理神经元的结构说明神经元由两部分组成细胞体(cellbody或soma)突(process)：实现神经元间的信息传递轴突(axon)：长度可达1m，把本神经元的输出发送至其它相连接的神经元树突(dendrite)：一般较短，且分枝很多，与其它神经元的轴突相连，以接收来自其它神经元的生物信号

突触(synapse)：是轴突的末端与树突进行信号传递的界面，通过突触向其它神经元发送信息。对某些突触的刺激促使神经元触发(fire)。只有神经元所有输入的总效应达到阈值电平，它才能开始工作。……402.3.3人工神经网络（ANN）的组成人工神经网络（ArtificialNeuralNets,ANN）：一种由模拟神经元组成的，以处理单元PE(processingelement)为节点，用加权有向弧(链)相互连接而成的有向图。处理单元：对生理神经元的模拟；有向弧：轴突-突触-树突对的模拟，有向弧的权值表示两处理单元间相互作用的强弱。41ANN的组成示意图422.3.4ANN的数学描述令来自其它处理单元（神经元）i的信息为xi，它们与本处理单元的互相作用强度为wi，i=0,1,…，n-1，处理单元的内部阈值为θ。那么本神经元的输入为

处理单元的输出为43常用的激发函数（作用函数）上述f(·)称为激发函数（作用函数）常用的激发函数阈值型分段线性饱和型S型函数442.3.5典型的ANN常见的ANN感知器(Perceptron)反向传播(BP)网

自适应共振(ART)双向联想存储器(BAM)BSB模型，也称盒中脑模型CPN(CounterPropagationNetwork)，也称对流网Hopfield网MadaLine认知机(Neocognitron)……452.3.6BP网简介反向传播(back-propagation,BP)算法：是一种计算单个权值变化引起网络性能变化值的较为简单的方法。1986年,Rumelhart&Mclelland首次提出至今应用最广的人工神经网络由于BP算法过程包含从输出节点开始，反向地向第一隐含层(即最接近输入层的隐含层)传播由总误差引起的权值修正，所以称为“反向传播”。

46BP网的基本结构BP网的三个层次输入层隐含层输出层特点：相邻层神经元间全互连，通层神经元无连接47BP网的基本思路正向传播过程：当给BP网提供一个输入模式时，该模式由输入层传到隐含层，经隐含层神经元作用函数处理后传送到输出层，再经由输出层神经元作用函数处理后产生一个输出模式。反向传播过程：若输出模式与期望的输出模式有误差，就从输出层反向将误差逐层传送到输入层，把误差“分摊”给各神经元并修改连接权，使BP网实现从输入模式到输出模式的正确映射。对于一组训练模式，可逐个用训练模式作为输入，反复进行误差检测和反向传播过程，直到不出现误差为止。48BP网的简单实例－解决XOR问题作用函数f(ai)为阈值型，即110.50.5-11输入层隐含层输出层49利用BP网解决XOR问题（续）上部隐含层完成一个线性分类输入模式(0,0)为一类，输出0(0,1),(1,0),(1,1)为另一类，输出1下部隐含层完成另一个线性分类(0,0),(0,1),(1,0)为一类，输出0(1,1)为另一类，输出1两个隐含神经元已对输入空间进行了初步划分，这种预处理实际上完成了对输入空间的特征抽象，从而为实现复杂的模式分类奠定了基础。输出层基于隐含层的输出，完成最终的分类：(0,0)和(1,1)为一类，输出为0(0,1)和(1,0)为一类，输出为1502.4不确定性推理精确推理的局限性不确定性推理的定义及意义不确定性推理中的基本问题不确定性推理的分类关于不确定性推理方法的说明51推理依据已知事实（证据）、相关知识（规则）证明某个假设成立or不成立精确推理及其不足将原本为不确定性的关系“硬性”转化为精确关系将原本不存在明确界限的事物“人为”划定界限歪曲了现实情况的本来面目舍弃了事物的某些重要属性失去了真实性……2.4.1精确推理的局限性522.4.2不确定性推理的定义及意义1.定义也称“不精确性推理”从不确定性的初始证据（即已知事实）出发运用不确定性的知识（或规则）推出具有一定程度的不确定性但却是合理或近乎合理的结论2.意义使计算机对人类思维的模拟更接近于人类的真实思维过程532.4.3不确定性推理中的基本问题不确定性的表示与度量不确定性匹配不确定性的传递算法不确定性的合成542.4.4不确定性推理方法的分类1.不确定性推理的两条研究路线模型方法在推理一级上扩展确定性推理不确定证据和知识与某种度量标准对应给出更新结论不确定性的算法构成相应的不确定性推理模型控制方法在控制策略一级上处理不确定性无统一的不确定性处理模型，其效果依赖于控制策略552.不确定性推理方法的分类不确定性推理模型方法控制方法数值方法非数值方法概率统计方法模糊推理方法粗糙集方法绝对概率方法贝叶斯方法证据理论方法HMM方法发生率计算相关性制导回溯、机缘控制、启发式搜索等可信度方法562.4.5关于不确定性推理方法的说明数值方法对不确定性的一种定量表示和处理方法其研究及应用较多，已形成多种应用模型非数值方法除数值方法外的其它处理不确定性的模型方法典型代表：“发生率计算方法”，它采用集合来描述和处理不确定性，且满足概率推理的性质57关于不确定性推理方法的说明（续1）概率统计方法有完整、严密的数学理论为不确定性的合成与传递提供了现成的数学公式最早、最广泛地用于不确定性知识的表示与处理已成为不确定性推理的重要手段证据理论方法1967年Dempster首次提出，1976年Shafer完善可表示并处理“不知道”等不确定性信息58关于不确定性推理方法的说明（续2）模糊推理方法可表示并处理由模糊性引起的不确定性已广泛应用于不确定性推理粗糙集理论方法1981年Z.Pawlak首次提出一种新的可表示并处理“含糊”等不确定性的数学方法可用于不确定性推理、数据挖掘等领域592.5机器学习机器学习的定义机器学习的地位和作用机器学习的发展历程机器学习中的五个挑战性问题机器学习中的主要理论问题机器学习的发展趋势602.5.1机器学习的定义何谓机器学习（MachineLearning）？TomM.Mitchell认为：机器学习是计算机利用经验改善系统自身性能的行为。其它定义：“令W是给定世界的有限或无限的所有观测对象的集合，由于我们观察能力的限制，只能能获得这个世界的一个有限的子集Q(为W的子集)，称为样本集。机器学习就是根据这个样本集，推算这个世界的模型，使它对这个世界（尽可能地）为真。”机器学习是“神经科学（含认知科学）＋数学＋计算”的有机结合612.5.2机器学习的地位和作用机器学习是AI的核心研究内容已成为整个计算机领域中最活跃、应用潜力最明显的领域之一美国航空航天局JPL实验室的科学家们在2001年9月出版的《Science》上撰文指出：“机器学习对科学研究的整个过程正起到越来越大的支持作用，……，该领域在今后的若干年内将取得稳定而快速的发展。”

机器学习研究的热门程度还可以从该领域的国际权威期刊JournalofMachineLearningResearch的影响因子看出，据美国科学引文检索公司（ISI）统计，2004年该学报的影响因子已达到5.952，是整个计算机领域影响因子最高的期刊之一。62机器学习的地位和作用（续）主要应用领域数据挖掘语音识别图像识别机器人车辆自动驾驶生物信息学信息安全遥感信息处理计算金融学工业过程控制……涉及的主要学科人工智能模式识别概率统计神经生物学认知科学信息论控制论计算复杂性理论哲学……6319世纪末，James发现了神经元是相互连接的现象

20世纪30年代，McCulloch和Pitts发现了神经元的“兴奋”和“抑制”机制20世纪中叶，Hebb发现了“学习律”机器学习的发展大致可分为两条重要主线2.5.3机器学习的发展历程64主线一：以Barlow提出的功能单细胞假设为依据

1956年，Rosenblatt提出了感知器随后近30年，Samuel等人提出的“符号机器学习”方法一直处于主导地位

1969年，Minsky开始研究线性不可分问题1986年，Rumelhart提出了著名的后向传播（BP）神经网络20世纪90年代，Vapnik等人提出了针对有限样本的统计学习理论（SLT）和支持向量机（SVM）机器学习的发展主线一65主线二：以Hebb提出的神经集合体假设为依据1960年，Widrow提出了Madline以解决平凡解问题1984年，Valiant提出了PAC1990年，Schapire提出了弱学习定理1995年，Freund和Schapire提出了AdaBoost算法在上述研究成果的基础上，逐渐形成了泛化理论1967年，哥德尔从数学上证明了符号机器学习是不可能完全实现的……机器学习的发展主线二66泛化能力（Generalization）越准越好：永远追求的目标之一支持向量机(SVM)、集成学习(Ensemblelearning)速度越快越好：永远追求的目标之一训练速度、测试速度可理解性现实中需要向用户解释——Why？如：医疗诊断中需向用户解释“为何做出这个诊断？”目前功能强大的机器学习方法（NN,SVM等）绝大多数是“黑盒子”2.5.4机器学习中的五个挑战性问题67数据利用能力

如何处理现实中绝大多数“未标记”数据？如何处理含噪声、属性缺失、不一致的“坏”数据？如何处理大量分布“不平衡”数据？代价敏感（Cost-sensitive）不同应用领域所能容忍的错误代价不一样同一应用领域中不同判断所对应的代价也不一样期望以较小的代价达到“趣利避害”的目的典型评价方法：ROC(ReceiverOperatingCharacteristics)机器学习中的五个挑战性问题（续）682.5.5机器学习中的主要理论问题统计类机器学习需要满足独立同分布条件，该要求太过苛刻没有一般的指导原则来寻找问题线性表示的空间没有好的方法来支持信息向符号的映射机器学习没有一劳永逸的解决方案领域知识与数据分析不可避免692.5.6机器学习的发展趋势主方向的改变不再单独做“会学习的机器（人）”越来越朝着“智能数据分析”的方向发展已成为智能数据分析的支撑技术侧重点的改变传统ML强调“学习本身是目的”当前ML强调“学习本身是手段”新的机器学习方法不断涌现流形学习、增强学习、多示例学习、半监督学习、Ranking学习、数据流学习……

702.6几种重要的机器学习方法统计学习理论与支持向量机统计学习理论（SLT）支持向量机（SVM）隐马尔可夫模型（HMM）贝叶斯网络（BayesianNetwork）……712.6.1统计学习理论与支持向量机SLT&SVM的地位与作用SLT&SVM所坚持的“基本信念”统计学习理论（SLT）的核心内容结构风险最小化原理支持向量机（SVM）概述72SLT&SVM的地位与作用是统计学习方法的优秀代表有严密的数学依据，得到了严格的数学证明有力反驳——“复杂的理论是没有用的，有用的是简单的算法”等错误观点充分表明——“没有什么比一个好的理论更实用了”等基本的科学原则73SLT&SVM所坚持的“基本信念”传统的估计高维函数依赖关系的方法认为实际问题中总存在较少数目的一些“强特征”，用它们的简单函数（如线性组合）就能较好地逼近未知函数。因此，需要仔细地选择一个低维的特征空间，在这个空间中用常规的统计技术来求解一个逼近。SLT&SVM所坚持的基本信念实际问题中存在较大数目的一些“弱特征”，它们“巧妙的”线性组合可较好地逼近未知的依赖关系。因此，采用什么样的“弱特征”并不十分重要，而形成“巧妙的”线性组合更为重要。74统计学习理论（SLT）的核心内容SLT被公认为是目前针对有限样本统计估计和预测学习的最佳理论，它从理论上系统地研究了：经验风险最小化原则成立的条件有限样本下经验风险与期望风险的关系如何利用这些理论找到新的学习原则和方法……SLT的主要内容基于经验风险原则的统计学习过程的一致性理论学习过程收敛速度的非渐进理论控制学习过程的推广能力的理论构造学习算法的理论75结构风险最小化原理传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此，需要同时最小化经验风险和置信范围。统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。这种思想称作结构风险最小化(StructuralRiskMinimization)，即SRM准则。76结构风险最小化示意图77支持向量机（SVM）的基本思想SVM从线性可分情况下的最优分类面发展而来。最优分类面就是要求分类线不但能将两类正确分开(训练错误率为0),且使分类间隔最大。SVM考虑寻找一个满足分类要求的超平面,并且使训练集中的点距离分类面尽可能的远,也就是寻找一个分类面使它两侧的空白区域(margin)最大。过两类样本中离分类面最近的点且平行于最优分类面的超平面上H1,H2的训练样本就叫做支持向量。78支持向量（SV）示意图79广义最优分类面示意图80支持向量机（SVM）的基本原理很多情况下，训练数据集是线性不可分的，Vapnik等人提出了用广义分类面来解决这一问题。对于非线性问题——通过非线性变换将它转化为某个高维空间中的线性问题，在这个高维空间中寻找最优分类面。分类函数只涉及到训练样本之间的内积运算(xi·xj),因此,在高维空间中只需进行内积运算,这种内积运算可通过定义在原空间中的函数来实现,甚至不必知道变换的形式。81支持向量机(SVM)的数学表示在最优分类面中采用适当的内积函数就可以实现某一非线性变换后的线性分类,而计算复杂度却没有增加。82支持向量机(SVM)示意图83SVM与神经网络（NN）的对比SVM的理论基础比NN更坚实，更像一门严谨的“科学”（三要素：问题的表示、问题的解决、证明）SVM——严格的数学推理NN——强烈依赖于工程技巧推广能力取决于“经验风险值”和“置信范围值”，NN不能控制两者中的任何一个NN设计者需要用高超的工程技巧弥补了数学上的缺陷84

SVM的主要应用领域手写数字识别语音识别人脸识别文本分类……852.6.2隐马尔可夫模型(HMM)马尔可夫模型的由来马尔可夫过程一个实验——球缸模型HMM的基本原理HMM的形式化描述HMM的三个基本问题HMM的三个主要算法86马尔可夫模型（MM）的由来

1870年，俄国有机化学家VladimirV.Markovnikov第一次提出MarkovModel（MM）MM本质上是一种随机过程HMM是一个二重Markov随机过程，包括具有状态转移概率的Markov链和输出观测值的随机过程HMM的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来最成功的应用领域之一——语音识别87Markov过程过程或系统在时刻T0所处状态为已知的条件下，过程在时刻T>T0所处状态的条件分布与过程在时刻t0之前所处的状态无关。通俗的说，就是在已经知道过程“现在”的条件下，其“将来”不依赖于“过去”。88一个实验——球缸模型设有N个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下根据某个初始概率分布，随机选择N个缸中的一个，例如第I个缸。根据这个缸中彩球颜色的概率分布，随机选择一个球，记下球的颜色，记为O1，再把球放回缸中。根据描述缸的转移的概率分布，随机选择下一口缸，重复步骤1。最后我们可以得到一个描述球的颜色的序列O1,O2,…，称为观察值序列。89ObservedBallSequenceUrn3Urn1Urn2Veil球缸模型示意图90关于球缸模型的说明缸之间的转移不能被直接观察到从缸中所选取的球的颜色和缸并不是一一对应的每次选取哪个缸由一组转移概率决定91HMM中状态与观测的对应关系示意图92HMM的基本原理HMM概念的提出——在实际问题中，观察到的事件与状态并非一一对应，而是通过一组概率分布相联系。HMM是一个双重随机过程，两个组成部分：

马尔可夫链：描述状态的转移，用转移概率描述。

一般随机过程：描述状态与观察序列间的关系，用观察值概率描述。93Markov链（,A）随机过程（B）状态序列观察值序列q1,q2,...,qTo1,o2,...,oTHMM的组成HMM的组成示意图94HMM的形式化描述N是可能的状态空间M是给定的一个观测值空间A称作时间无关状态转移概率分布B是在给定状态下观察值概率分布条件π是在初始时刻状态空间的概率分布模型λ＝(N,M,π,A,B)用来描述HMM其中，N,M,π,B,A称为HMM的五元组可简写为：λ＝（π,A,B）95HMM中的三个基本问题问题1：给定观察序列O=O1,O2,…OT,以及模型λ＝（π,A,B）,如何计算P(O|λ)？问题2：给定观察序列O=O1,O2,…OT以及模型λ,如何选择一个对应的状态序列Q=q1,q2,…qT，使得Q能够最为合理的解释观察序列O？问题3：如何调整模型参数λ＝（π,A,B）,使得P(O|λ)最大？96HMM的三个基本算法前向－后向算法（解决问题1）这个算法是用来计算给定一个观测值序列O以及一个模型λ时，由模型λ产生出观测值序列O的概率。Viterbi算法（解决问题2）这个算法解决了给定一个观测值序列O和一个模型λ，在最佳意义上确定一个状态序列Q的问题。Baum-Welch算法（解决问题3）这个算法实际上是解决HMM训练，即HMM参数估计问题，或者说，给定一个观察值序列O，该算法能确定一个模型λ，使P(O|λ)最大。97HMM的典型应用——语音识别982.7数据挖掘数据挖掘的由来数据挖掘的创立数据挖掘的主要应用数据挖掘vs.知识发现数据挖掘的基本过程数据挖掘系统的基本结构数据挖掘的基本问题数据挖掘的发展趋势99人类已进入一个崭新的信息时代数据库中存储的数据量急剧膨胀，但知识相对贫乏需要从海量数据库和大量繁杂信息中提取有价值的知识，进一步提高信息的利用率产生了一个新的研究方向：基于数据库的知识发现（KnowledgeDiscoveryi