《人工智能原理及应用》由会员分享，可在线阅读，更多相关《人工智能原理及应用（111页珍藏版）》请在金锄头文库上搜索。
1、浙江大学远程教育学院浙江大学远程教育学院人工智能人工智能讲座讲座徐从富徐从富(Congfu Xu) PhD, Associate Professor Email: Institute of Artificial Intelligence, College of Computer Science, Zhejiang University, Hangzhou 310027, P.R. ChinaDecember 4, 2006第二讲 人工智能原理及应用(Lecture 2 Principles & Applications of AI)提纲提纲n知识表示知识表示n专家系统专家系统n人工神经网络人工
2、神经网络n不确定性推理不确定性推理 n机器学习机器学习n数据挖掘数据挖掘nAI的若干研究前沿的若干研究前沿22.1 知识表示 知识是智能的基础知识是智能的基础n 获得知识n 运用知识 符合计算机要求的知识模式符合计算机要求的知识模式n 计算机能存储、处理的知识表示模式n 数据结构（List, Table, Tree, Graph, etc.）2.1.1 知识表示的重要性知识表示的重要性3 数据数据 (Data)n信息的载体和表示n用一组符号及其组合表示信息 信息信息 (Information)n数据的语义n数据在特定场合下的具体含义 知识知识 (Knowledge)n信息关联后所形成的信息结构
3、：事实 & 规则n经加工、整理、解释、挑选、改造后的信息2.1.2 数据、信息与知识数据、信息与知识42.1.3 知识的特性知识的特性n相对正确性相对正确性n一定条件下n某种环境中n.n不确定性不确定性n存在“中间状态”n“真”（“假”）程度n随机性n模糊性n经验性n不完全性n.n可表示性可表示性 & 可利用性可利用性n语言n文字n图形n图像n视频n音频n神经网络n概率图模型n.52.1.4 知识的分类知识的分类n常识性知识、领域性知识常识性知识、领域性知识（作用范围）n事实性知识、过程性知识、控制知识事实性知识、过程性知识、控制知识（作用及表示）n确定性知识、不确定性知识确定性知识、不确定性
4、知识（确定性）n逻辑性知识、形象性知识逻辑性知识、形象性知识（结构及表现形式）n零级知识、一级知识、二级知识零级知识、一级知识、二级知识（抽象程度）62.1.5 常用的知识表示方法常用的知识表示方法n一阶谓词一阶谓词（First Order Predicate）n产生式产生式（Production）n框架框架（Framework）n语义网络语义网络（Semantic Network）n剧本剧本（Script）n过程过程（Procedure）n面向对象面向对象（Object-Oriented）nPetri网网（Petri Network）n信念网信念网（Belief Network）n本体论本体
5、论（Ontology）n72.1.6 如何选择合适的知识表示方法？如何选择合适的知识表示方法？n充分表示领域知识领域知识n有利于对知识的利用对知识的利用n便于理解和实现理解和实现n便于对知识的组织、管理与维护对知识的组织、管理与维护82.1.7 一阶谓词表示法一阶谓词表示法1. 何谓一阶谓词？何谓一阶谓词？n定义n谓词：就是带参数的命题。谓词：就是带参数的命题。n谓词公式：用连词谓词公式：用连词（ , , 等）等）把原子谓词公式组成把原子谓词公式组成的合适公式。的合适公式。n举例nCITY(X), HUMAN(X), INROOM(ROBOT, R1), etc.nHUMAN(X) LAWED
6、(X)，表示：人人都受法律管制nHUMAN(X) LAWED(X) COMMIT(X) PUNISHED(X)，表示：如果由于某个X是人而受到法律管制，则这个人犯了罪就一定要受到惩罚。9Syntax itemUsually usedOthers取反取反：Negation (not)P, PP（加上划线）合取合取：Conjunction(and)P QP&Q PQ PQ P,Q析取析取：Disjunction(or)P QP|Q P;Q P+Q蕴涵蕴涵：Implication(if)PQ PQP Q等价等价：Equivalence(iff)PQ PQPQ全称量词全称量词：Universal (a
7、ll)(x) P(x)x P(x) x P(x) 存在量词存在量词：Existential(exists)(x) P(x)x P(x) x P(x)关系关系：RelationR(x, y)(R x y) Rxy xRy2. 常用的谓词公式表示方法对照表常用的谓词公式表示方法对照表103. 谓词公式的表达方法举例谓词公式的表达方法举例n实例1n试用谓词演算表示如下英文句子：“For every set x, there is a set y, such that the cardinality of y is greater than the cardinality of x.”n对应的谓词公式
8、： ( x) SET(x) ( y) ( u) ( v) SET(y) CARD(y, u) CARD(x, v) G(u,v)n实例2n“世上决没有无缘无故的爱，也没有无缘无故的恨。世上决没有无缘无故的爱，也没有无缘无故的恨。”n对应的谓词公式： x爱爱(x) y 缘故缘故 (x, y) t恨恨(t) s 缘故缘故 (t, s)114. 一阶谓词表示法的优、缺点一阶谓词表示法的优、缺点(1) 优点优点n自然性n接近自然语言，容易接受n精确性n用于表示精确知识n严密性n有严格的形式定义和推理规则n易实现性n易于转换为计算机内部形式12一阶谓词表示法的优、缺点（续）一阶谓词表示法的优、缺点（续）
9、(2) 缺点缺点n无法表示不确定性知识n所能表示的知识范围太狭窄n难以表示启发性知识及元知识n未能充分利用与问题本身特性有关的知识n组合爆炸n经常出现事实、规则等的组合爆炸n效率低n推理与知识的语义完全割裂132.1.8 产生式表示法产生式表示法n1943年E. Post第一次提出n称为“Post机”的计算模型n一种描述形式语言的语法nAI中应用最多的知识表示方法之一nFeigenbaum研制的化学分子结构专家系统DENDRALnShortliffe研制的的诊断感染性疾病的专家系统MYCINn14P Q CF = 0, 1或 IF P THEN Q CF = 0, 1其中，P是产生式的前提前提
10、，Q是一组结论结论或操作操作，CF(Certainty Factor)为确定性因子确定性因子，也称置信度置信度。 【说明】：谓词逻辑中的蕴涵式蕴涵式与产生式产生式的基本形式相似，事实上，蕴涵式只是产生式的一种特殊情况。1. 产生式的基本形式产生式的基本形式15 2. 产生式系统的优、缺点产生式系统的优、缺点 (1) (1) 产生式系统的优点产生式系统的优点 a a）自然性）自然性：由于产生式系统采用了人类常用的表达因果关系因果关系的知识表示形式，既直观、自然，又便于进行推理。 b b）模块性）模块性：产生式是规则库中的最基本的知识单元，形式相同，易于模块化管理。 c c）有效性）有效性：能表示
11、确定性知识、不确定性知识、启发性知识、过程性知识等。 d d）清晰性）清晰性：产生式有固定的格式，既便于规则设计，又易于对规则库中的知识进行一致性、完整性检测。16（2）产生式系统的缺点）产生式系统的缺点 a a）效率不高）效率不高 产生式系统求解问题的过程是一个反复进行“匹配匹配冲突消解冲突消解执行执行”的过程。由于规则库一般都比较庞大，而匹配又是一件十分费时的工作，因此，其工作效率不高。此外，在求解复杂问题时容易引起组合爆炸容易引起组合爆炸。 b b）不能表达具有结构性的知识）不能表达具有结构性的知识 产生式系统对具有结构关系的知识无能为力，它不能不能把具有结构关系的事物间的区别与联系表示
12、出来把具有结构关系的事物间的区别与联系表示出来，因此，人们经常将它与其它知识表示方法（如框架表示法、语义网络表示法）相结合。173. 产生式系统的适用领域产生式系统的适用领域 （1）由许多相对独立的知识元组成的领域知识，彼此之间关系不密切，不存在结构关系。如：化学反应化学反应方面的知识。 （2）具有经验性及不确定性的知识，而且相关领域中对这些知识没有严格、统一的理论。如：医疗诊断、故障医疗诊断、故障诊断诊断等方面的知识。 （3）领域问题的求解过程可被表示为一系列相对独立的操作，而且每个操作可被表示为一条或多条产生式规则。182.1.9 框架表示法框架表示法 1. 框架理论框架理论 1975年美
13、国著名AI学者Minsky在其论文“A framework for representing knowledge”中提出了框架理论，并把它作为理解视觉、自然语言对话及其它复杂行为的基作为理解视觉、自然语言对话及其它复杂行为的基础础。 框架理论的基本思想框架理论的基本思想：认为人们对现实世界中各种事物的认识都是以一种类似于框架的结构存储在记忆中的，当面临一个新事物时，就从记忆中找出一个合适的框架，并根据实际情况对其细节加以修改、补充，从而形成对当前事物的认识。19 2. 2. 框架的一般表示形式框架的一般表示形式槽名1：侧面名1值1，值2，.，值p1侧面名2值1，值2，.，值p2侧面名m1值1，
14、值2，.，值pm1槽名n：侧面名1值1，值2，.，值r1约束： 约束条件1约束条件n203. 3. 框架及其实例框架及其实例框架名：tx 未遂杀人案犯罪意图：x犯罪结果：杀人被杀者：y杀人动机：x 未遂被 y 发现知情人： zi | i I罪犯： t条件一：若 x 为强奸，则 t 必须是男性条件二：有某个 zi 指控 t条件三：t 招认 在聊斋志异中有个胭脂的故事，开始时邑宰判错了案，就是因为他头脑里有个破案的框架：21 框架实例：鄂秋準鄂秋準 强奸强奸 未遂杀人案犯罪意图：强奸强奸犯罪结果：杀人被杀者：卞牛医卞牛医杀人动机：强奸强奸 未遂被 卞牛医卞牛医 发现知情人：卞妻，胭脂卞妻，胭脂罪犯
15、： 鄂秋準鄂秋準 条件一：鄂秋準鄂秋準 为男性，成立条件二：胭脂胭脂 指控 鄂秋準鄂秋準 ，成立条件三：鄂秋準鄂秋準 招认，成立 邑宰用上述框架去套胭脂一案，结果得到了该框架的一个实例：22 4. 框架表示法的优、缺点框架表示法的优、缺点 （1 1）优点）优点 a）结构性 b）继承性 c）自然性 （2 2）缺点）缺点 不善于表达过程性的知识不善于表达过程性的知识，经常与产生式表示法产生式表示法结合起来使用，以取得互补的效果。232.1.10 语义网络表示法语义网络表示法 1. 语义网络的提出及基本思想语义网络的提出及基本思想 1968年J.R.Quillian在其博士论文中最先提出语义网络，把
16、它作为人类联想记忆的一个显式心理学模型人类联想记忆的一个显式心理学模型，并在他设计的可教式语言理解器TLC (Teachable Language Comprehenden)中用作知识表示方法。 语义网络的基本思想语义网络的基本思想：在这种网络中，用“节点节点”代替概念，用节点间的“连接弧”(称为联想弧联想弧)代替概念之间的关系，因此，语义网络又称联想网络联想网络。它在形式上是一个带标识的有向图。由于所有的概念节点均通过联想弧彼此相连，Quillian希望他的语义网络能用于知识推导。242. 语义网络举例语义网络举例 与歌曲军港之夜中的歌词“海浪把战舰轻轻地海浪把战舰轻轻地摇摇”对应的语义网络
17、：全域全域行为行为事物事物方式方式海浪海浪战舰战舰摇动摇动轻轻轻轻某港海浪某港海浪某港战舰某港战舰子集子集子集子集子集子集子集子集子集子集个体个体个体个体子集子集个体个体动作对象动作对象动作方式动作方式动作主体动作主体25 3. 语义网络表示法的优、缺点语义网络表示法的优、缺点 （1 1）语义网络表示法的优点）语义网络表示法的优点 a）结构性结构性：因为语义网络是一种结构化的知识表示方法，它能把事物的属性以及事物间的各种语义联想显式地表示出来。 b）联想性联想性：它最初是作为人类联想记忆模型提出来的。 c）自然性自然性：直观地把事物的属性及其语义联系表示出来，便于理解，自然语言与语义网络的转换
18、比较容易实现，故语义网络表示法在自然语言理解系统中的应用最为广泛语义网络表示法在自然语言理解系统中的应用最为广泛。26 （2）语义网络表示法的缺点语义网络表示法的缺点 a a）非严格性）非严格性：与一阶谓词逻辑相比，语义网络没有公认的形式表示体系。一个给定的语义网络所表达的含义完全依赖于处理程序如何对它进行解释。通过推理网络而实现的推理不能保证其正确性。此外，目前采用的表示量词（包括全称量词和存在量词）的语义网络表示法在逻辑上是不充分的，不能保证不存在二义性。 b b）处理上的复杂性）处理上的复杂性：语义网络表示知识的手段多种多样，虽然灵活性很高，但同时也由于表示形式的不一致使得对其处理的复杂
19、性提高，对知识的检索也就相对复杂，要求对网络的搜索要有强有力的组织原则。27 2.1.11 剧本（脚本）表示法剧本（脚本）表示法 剧本表示法是1975年R.C. Schank依据他的概念依赖理论概念依赖理论而提出的一种知识表示方法。脚本与框架类似，由一组槽组成，用来表示特定领域内一些事件的发生序列。 1. 概念依赖理论概念依赖理论 【难点难点】在人类的各种知识中，常识性知识常识性知识是数量最多、涉及面最宽、关系最复杂的知识，很难把它们形式化地表示出来交给计算机处理。 概念依赖理论的基本思想基本思想：把人类生活中各类故事情节的基本概念抽取出来，构成一组原子概念，确定这些原子概念间的相互依赖关系，
20、然后把所有故事情节都用这组原子概原子概念念及其依赖关系依赖关系表示出来。28 2. 剧本（脚本）的构成剧本（脚本）的构成 1 1、剧本、剧本：描述特定范围内原型事件的结构。 2 2、剧本的组成、剧本的组成 （1）进入条件进入条件：指出剧本所描述的事件可能发生的先决条件，即事件发生的前提条件前提条件。 （2）角色角色：描述事件中可能出现的人物。 （3）道具道具：描述事件中可能出现的有关物体。 （4）场景场景：描述事件序列，可以有多个场景。 （5）结局结局：给出剧本所描述的事件发生以后必须满足的条件。29 广义的知识表示语言广义的知识表示语言n任何程序设计语言n例如：C, C+, Java, XM
21、L, etc. 狭义的人工智能语言狭义的人工智能语言n把知识和智能传授给计算机的表示语言n专门用于编程求解AI问题n典型代表：LISP语言、PROLOG语言n2.1.12 知识表示语言知识表示语言301. LISP语言概况语言概况n提出提出：1960年，美国AI之父McCarthy首次给出n含义含义：LISP是LISt Processer（表处理器）之意n目的目的：为处理AI中的符号编程问题而设计n理论基础理论基础：符号集上的递归函数论n地位地位：AI历史上第一个，且使用范围最广泛的符号处理语言，为AI的发展做出重大贡献【说明】: 详细语法可参见陆汝钤的人工智能（下册）312. PROLOG语
22、言概况语言概况n提出提出：1973年，马赛大学的Colmerauer首次给出n含义含义：是PROgramming in LOGic之意n目的目的：专门用于处理AI中的逻辑推理问题n理论基础理论基础：一阶谓词演算的归结(Resolution)原理n作用作用：给一阶谓词演算中的说明性命题以过程性解释【说明】: 详细语法可参见陆汝钤的人工智能（下册）321. 概述概述 定义定义n专家系统专家系统（Expert Expert Systems,ESSystems,ES）是一种以知识为基础、能对某一专门领域的问题提供“专家级”解答的计算机程序。 发展简况发展简况n1968年Stanford大学Feigen
23、baum开发成功世界上第一个专家系统DENDRALn1977年Feigenbaum在IJCAI77上提出“知识工程”n 2.2 专家系统专家系统332. 专家系统的成功范例专家系统的成功范例(以农业为例)n美国的农业专家系统美国的农业专家系统n1986年开发的COMAX/GOSSYM系统n加州大学Davis分校开发的CALEX系统n农业专家系统开发工具：LEVEL5, VP-EXPERT, INSIGHT, etc. nn中国的农业专家系统中国的农业专家系统n中科院智能机械所开发的施肥专家系统施肥专家系统n中国农科院作物研究所开发的品种选育专家系统品种选育专家系统n华中理工大学开发的园艺专家系
24、统园艺专家系统n浙江大学与中国农科院联合开发的蚕育种专家系统、蚕育种专家系统、饲料配方专家系统饲料配方专家系统n343. 专家系统的基本结构专家系统的基本结构解释器解释器知识库知识库知识库管知识库管理理推理机推理机知识获取知识获取界界面面网网络络35关于专家系统的基本结构的说明关于专家系统的基本结构的说明n推理机、知识库：推理机、知识库：是专家系统中最核心部分n知识库管理知识库管理：检查知识的内容是否有问题n知识获取：知识获取：是知识工程的瓶颈n解释器解释器：解释推理的结果及在推理过程中发生的一切n界面：界面：是让专家系统“接近群众”的重要手段n网络接口：网络接口：网上多个专家系统可构成分布式
25、专家系统364. 专家系统的生命周期专家系统的生命周期n第一阶段：需求分析需求分析（REQ）n第二阶段：系统设计系统设计（DES）n第三阶段：知识获取知识获取（ACQ）n第四阶段：原型测试原型测试（PRT）n第五阶段：知识求精知识求精（REF）n第六阶段：系统包装系统包装（PCK）n第七阶段：系统集成系统集成（ITG）【说明】：第七阶段并非最后阶段，后面阶段可返回到前面阶段。系统维护，特别是知识维护就体现在这种循环中。372.3 人工神经网络人工神经网络 n生理神经元的结构n人工神经网络的组成n人工神经网络的数学描述n典型的人工神经网络nBP网简介【注】：关于人工神经网络的详细原理及应用可参见
26、： Martin T. Hagan 等著, 戴葵 等译.神经网络设计, 机械工业出版社, 2002.382.3.1 神经元的组成部分示意图神经元的组成部分示意图392.3.2 生理神经元的结构说明生理神经元的结构说明n神经元由两部分组成 n细胞体细胞体(cell body或soma)n突突(process)：实现神经元间的信息传递n轴突轴突(axon)：长度可达1m，把本神经元的输出发送至其它相连接的神经元 n树突树突(dendrite)：一般较短，且分枝很多，与其它神经元的轴突相连，以接收来自其它神经元的生物信号 n突触突触(synapse)：是轴突的末端与树突进行信号传递的界面，通过突触向
27、其它神经元发送信息。n对某些突触的刺激促使神经元触发触发(fire)。只有神经元所有输入的总效应达到阈值电平，它才能开始工作。 n402.3.3 人工神经网络（人工神经网络（ANN）的组成）的组成n人工神经网络人工神经网络（Artificial Neural Nets, ANN）：一种由模拟神经元组成的，以处理单元PE (processing element)为节点，用加权有向弧(链)相互连接而成的有向图。n处理单元：处理单元：对生理神经元的模拟；n有向弧：有向弧：轴突-突触-树突对的模拟，有向弧的权值表示两处理单元间相互作用的强弱。 41ANN的组成示意图的组成示意图422.3.4 ANN的
28、数学描述的数学描述n令来自其它处理单元（神经元）i的信息为xi，它们与本处理单元的互相作用强度为wi，i = 0,1,，n-1，处理单元的内部阈值为。那么本神经元的输入为n处理单元的输出为43常用的激发函数（作用函数）常用的激发函数（作用函数）n上述f()称为激发函数激发函数（作用函数作用函数）n常用的激发函数阈值型 分段线性饱和型 S型函数442.3.5 典型的典型的ANNn常见的ANNn感知器(Perceptron) n反向传播反向传播(BP)(BP)网网 n自适应共振(ART) n双向联想存储器(BAM) nBSB模型，也称盒中脑模型nCPN(Counter Propagation Ne
29、twork)，也称对流网nHopfield网 nMadaLine n认知机(Neocognitron) n452.3.6 BP网简介网简介n反向传播反向传播(back-propagation, BP)算法算法：是一种计算单个权值变化引起网络性能变化值的较为简单的方法。n1986年, Rumelhart & Mclelland首次提出n至今应用最广的人工神经网络 n由于BP算法过程包含从输出节点开始，反向地向第一隐含层(即最接近输入层的隐含层)传播由总误差引起的权值修正，所以称为“反向传播反向传播”。 46BP网的基本结构网的基本结构nBP网的三个层次n输入层n隐含层n输出层n特点：相邻层神经元
30、间全互连，通层神经元无连接47BP网的基本思路网的基本思路n正向传播过程正向传播过程：当给BP网提供一个输入模式时，该模式由输入层传到隐含层，经隐含层神经元作用函数处理后传送到输出层，再经由输出层神经元作用函数处理后产生一个输出模式。n反向传播过程反向传播过程：若输出模式与期望的输出模式有误差，就从输出层反向将误差逐层传送到输入层，把误差“分摊”给各神经元并修改连接权，使BP网实现从输入模式到输出模式的正确映射。n对于一组训练模式，可逐个用训练模式作为输入，反复进行误差检测和反向传播过程，直到不出现误差为止。48BP网的简单实例解决网的简单实例解决XOR问题问题n作用函数f(ai)为阈值型，即
31、110.50.5-11输入层隐含层输出层49利用利用BP网解决网解决XOR问题（续）问题（续）n上部隐含层上部隐含层完成一个线性分类n输入模式(0, 0)为一类，输出0n(0, 1), (1, 0), (1, 1)为另一类，输出1n下部隐含层下部隐含层完成另一个线性分类n(0, 0), (0, 1), (1, 0) 为一类，输出0n(1, 1)为另一类，输出1n两个隐含神经元已对输入空间进行了初步划分，这种预处理实际上完成了对输入空间的特征抽象，从而为实现复杂的模式分类奠定了基础。n输出层输出层基于隐含层的输出，完成最终的分类：n(0, 0)和(1, 1)为一类，输出为0n(0, 1)和(1,
32、 0)为一类，输出为1502.4 不确定性推理不确定性推理n精确推理的局限性n不确定性推理的定义及意义n不确定性推理中的基本问题n不确定性推理的分类n关于不确定性推理方法的说明51 推理推理n依据已知事实（证据）、相关知识（规则）n证明某个假设成立 or 不成立 精确推理及其不足精确推理及其不足n将原本为不确定性的关系“硬性”转化为精确关系n将原本不存在明确界限的事物“人为”划定界限n歪曲了现实情况的本来面目n舍弃了事物的某些重要属性n失去了真实性n2.4.1 精确推理的局限性精确推理的局限性522.4.2 不确定性推理的定义及意义不确定性推理的定义及意义1. 定义定义n也称“不精确性推理”n
33、从不确定性的初始证据（即已知事实）出发n运用不确定性的知识（或规则）n推出具有一定程度的不确定性但却是合理或近乎合理的结论2. 意义意义n使计算机对人类思维的模拟更接近于人类的真实思维过程532.4.3 不确定性推理中的基本问题不确定性推理中的基本问题n不确定性的表示与度量不确定性的表示与度量n不确定性匹配不确定性匹配n不确定性的传递算法不确定性的传递算法n不确定性的合成不确定性的合成542.4.4 不确定性推理方法的分类不确定性推理方法的分类1. 不确定性推理的两条研究路线不确定性推理的两条研究路线n模型方法模型方法n在推理一级上扩展确定性推理n不确定证据和知识与某种度量标准对应n给出更新结
34、论不确定性的算法n构成相应的不确定性推理模型n控制方法控制方法n在控制策略一级上处理不确定性n无统一的不确定性处理模型，其效果依赖于控制策略552. 2. 不确定性推理方法的分类不确定性推理方法的分类不确定性推理模型方法控制方法数值方法非数值方法概率统计方法模糊推理方法粗糙集方法绝对概率方法贝叶斯方法证据理论方法HMM方法发生率计算相关性制导回溯、机缘控制、启发式搜索等可信度方法562.4.5 关于不确定性推理方法的说明关于不确定性推理方法的说明n数值方法数值方法n对不确定性的一种定量表示和处理方法n其研究及应用较多，已形成多种应用模型n非数值方法非数值方法n除数值方法外的其它处理不确定性的模
35、型方法n典型代表：“发生率计算方法”，它采用集合来描述和处理不确定性，且满足概率推理的性质57关于不确定性推理方法的说明（续关于不确定性推理方法的说明（续1）n概率统计方法概率统计方法n有完整、严密的数学理论n为不确定性的合成与传递提供了现成的数学公式n最早、最广泛地用于不确定性知识的表示与处理n已成为不确定性推理的重要手段n证据理论方法证据理论方法n1967年Dempster首次提出，1976年Shafer完善n可表示并处理“不知道”等不确定性信息58关于不确定性推理方法的说明（续关于不确定性推理方法的说明（续2）n模糊推理方法模糊推理方法n可表示并处理由模糊性引起的不确定性n已广泛应用于不
36、确定性推理n粗糙集理论方法粗糙集理论方法n1981年Z. Pawlak首次提出n一种新的可表示并处理“含糊”等不确定性的数学方法n可用于不确定性推理、数据挖掘等领域592.5 机器学习机器学习n机器学习的定义n机器学习的地位和作用n机器学习的发展历程n机器学习中的五个挑战性问题n机器学习中的主要理论问题n机器学习的发展趋势60 2.5.1 机器学习的定义机器学习的定义n何谓机器学习机器学习（Machine Learning）？nTom M. Mitchell认为：机器学习是计算机利用经验改计算机利用经验改善系统自身性能的行为善系统自身性能的行为。 n其它定义：“令W是给定世界的有限或无限的所有
37、观测对象的集合，由于我们观察能力的限制，只能能获得这个世界的一个有限的子集Q(为W的子集)，称为样本集。机器学习就是根据这个样本集，推算根据这个样本集，推算这个世界的模型，使它对这个世界（尽可能地）为这个世界的模型，使它对这个世界（尽可能地）为真。真。”n机器学习是“神经科学（含认知科学）数学计神经科学（含认知科学）数学计算算”的有机结合612.5.2 机器学习的地位和作用机器学习的地位和作用n机器学习是AI的核心研究内容n已成为整个计算机领域中最活跃、应用潜力最明最活跃、应用潜力最明显显的领域之一 n美国航空航天局JPL实验室的科学家们在2001年9月出版的Science上撰文指出：“机器学
38、习对科学研究机器学习对科学研究的整个过程正起到越来越大的支持作用，的整个过程正起到越来越大的支持作用，该领，该领域在今后的若干年内将取得稳定而快速的发展。域在今后的若干年内将取得稳定而快速的发展。” n机器学习研究的热门程度还可以从该领域的国际权威期刊Journal of Machine Learning Research的影响因子看出，据美国科学引文检索公司（ISI）统计，2004年年该学报的影响因子已达到该学报的影响因子已达到5.952，是整个计算机领域影，是整个计算机领域影响因子最高的期刊之一响因子最高的期刊之一。62机器学习的地位和作用（续）机器学习的地位和作用（续）n主要应用领域主要
39、应用领域n数据挖掘n语音识别n图像识别n机器人n车辆自动驾驶n生物信息学n信息安全n遥感信息处理n计算金融学n工业过程控制 nn涉及的主要学科涉及的主要学科n人工智能n模式识别n概率统计n神经生物学n认知科学n信息论n控制论n计算复杂性理论n哲学 n63n19世纪末，James发现了神经元是相互连接的现象 n20世纪30年代，McCulloch和Pitts发现了神经元的“兴奋”和“抑制”机制n20世纪中叶，Hebb发现了“学习律” n机器学习的发展大致可分为两条重要主线两条重要主线2.5.3 机器学习的发展历程机器学习的发展历程64n主线一主线一：以以Barlow提出的功能单细胞假设为依据提出
40、的功能单细胞假设为依据 n1956年，Rosenblatt提出了感知器n随后近30年，Samuel等人提出的“符号机器学习”方法一直处于主导地位 n1969年，Minsky开始研究线性不可分问题 n1986年，Rumelhart提出了著名的后向传播（BP）神经网络 n20世纪90年代，Vapnik等人提出了针对有限样本的统计学习理论（SLT）和支持向量机（SVM） 机器学习的发展主线一机器学习的发展主线一65n主线二主线二：以以Hebb提出的神经集合体假设为依据提出的神经集合体假设为依据 n1960年，Widrow提出了Madline以解决平凡解问题 n1984年，Valiant提出了PAC
41、n1990年，Schapire提出了弱学习定理 n1995年，Freund和Schapire提出了AdaBoost算法 n在上述研究成果的基础上，逐渐形成了泛化理论 n1967年，哥德尔从数学上证明了符号机器学习是不可能完全实现的 n机器学习的发展主线二机器学习的发展主线二66n泛化能力泛化能力（Generalization）n越准越好：永远追求的目标之一n支持向量机(SVM)、集成学习(Ensemble learning)n速度速度n越快越好：永远追求的目标之一n训练速度、测试速度 n可理解性可理解性n现实中需要向用户解释Why？n如：医疗诊断中需向用户解释“为何做出这个诊断？”n目前功能强
42、大的机器学习方法（NN, SVM 等）绝大多数是“黑盒子”2.5.4 机器学习中的五个挑战性问题机器学习中的五个挑战性问题67n数据利用能力数据利用能力 n如何处理现实中绝大多数“未标记”数据？n如何处理含噪声、属性缺失、不一致的“坏”数据？n如何处理大量分布“不平衡”数据？n代价敏感代价敏感（Cost-sensitive）n不同应用领域所能容忍的错误代价不一样n同一应用领域中不同判断所对应的代价也不一样 n期望以较小的代价达到“趣利避害”的目的n典型评价方法：ROC (Receiver Operating Characteristics)机器学习中的五个挑战性问题（续）机器学习中的五个挑战性
43、问题（续）682.5.5 机器学习中的主要理论问题机器学习中的主要理论问题n统计类机器学习需要满足独立同分布条件，该要求太过苛刻 n没有一般的指导原则来寻找问题线性表示的空间 n没有好的方法来支持信息向符号的映射 n机器学习没有一劳永逸的解决方案 n领域知识与数据分析不可避免 692.5.6 机器学习的发展趋势机器学习的发展趋势n主方向的改变n不再单独做“会学习的机器（人）”n越来越朝着“智能数据分析”的方向发展n已成为智能数据分析的支撑技术 n侧重点的改变n传统ML强调“学习本身是目的”n当前ML强调“学习本身是手段” n新的机器学习方法不断涌现n流形学习、增强学习、多示例学习、半监督学习、
44、Ranking学习、数据流学习 70 2.6 几种重要的机器学习方法几种重要的机器学习方法n统计学习理论与支持向量机统计学习理论与支持向量机n统计学习理论（SLT）n支持向量机（SVM）n隐马尔可夫模型（隐马尔可夫模型（HMM）n贝叶斯网络（贝叶斯网络（Bayesian Network）n712.6.1 统计学习理论与支持向量机统计学习理论与支持向量机nSLT&SVM的地位与作用nSLT&SVM所坚持的“基本信念”n统计学习理论（SLT）的核心内容n结构风险最小化原理n支持向量机（SVM）概述72SLT&SVM的地位与作用的地位与作用n是统计学习方法的优秀代表n有严密的数学依据，得到了严格的数
45、学证明n有力反驳 “复杂的理论是没有用的，有用的是简单的算法”等错误观点n充分表明 “没有什么比一个好的理论更实没有什么比一个好的理论更实用了用了”等基本的科学原则73SLT&SVM所坚持的所坚持的“基本信念基本信念”n传统的估计高维函数依赖关系的方法认为n实际问题中总存在较少数目的一些“强特征强特征”，用它们的简单函数（如线性组合）就能较好地逼近未知函数。因此，需要仔细地选择一个低维的特征空间仔细地选择一个低维的特征空间，在这个空间中用常规的统计技术来求解一个逼近。nSLT&SVM所坚持的基本信念n实际问题中存在较大数目的一些“弱特征弱特征”，它们“巧妙的”线性组合可较好地逼近未知的依赖关系
46、。因此，采用什么样的“弱特征”并不十分重要，而形成“巧妙的”线性组合更为重要。74统计学习理论（统计学习理论（SLT）的核心内容）的核心内容nSLT被公认为是目前针对有限样本统计估计和预测学习的最佳理论，它从理论上系统地研究了：n经验风险最小化原则成立的条件n有限样本下经验风险与期望风险的关系n如何利用这些理论找到新的学习原则和方法nnSLT的主要内容n基于经验风险原则的统计学习过程的一致性理论n学习过程收敛速度的非渐进理论n控制学习过程的推广能力的理论n构造学习算法的理论75结构风险最小化原理结构风险最小化原理n传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此，
47、需要同时最小化经验风险和置信范围。n统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。这种思想称作结构风险最小化(Structural Risk Minimization)，即SRM准则。76结构风险最小化示意图结构风险最小化示意图77 支持向量机（支持向量机（SVM）的基本思想）的基本思想nSVM从线性可分情况下的最优分类面发展而来。n最优分类面就是要求分类线不但能将两类正确分开(训练错误率为0),且使分类间隔最大。nSVM考虑寻找一个满足分类要求的超平面,并
48、且使训练集中的点距离分类面尽可能的远,也就是寻找一个分类面使它两侧的空白区域(margin)最大。n过两类样本中离分类面最近的点且平行于最优分类面的超平面上H1,H2的训练样本就叫做支持向量。78支持向量（支持向量（SV）示意图）示意图79广义最优分类面示意图广义最优分类面示意图80支持向量机（支持向量机（SVM）的基本原理）的基本原理n很多情况下，训练数据集是线性不可分的，Vapnik等人提出了用广义分类面来解决这一问题。n对于非线性问题通过非线性变换将它转化为某个高维空间中的线性问题，在这个高维空间中寻找最优分类面。n分类函数只涉及到训练样本之间的内积运算(xixj),因此,在高维空间中只
49、需进行内积运算,这种内积运算可通过定义在原空间中的函数来实现, 甚至不必知道变换的形式。81支持向量机支持向量机(SVM)的数学表示的数学表示n在最优分类面中采用适当的内积函数就可以实现某一非线性变换后的线性分类,而计算复杂度却没有增加。82支持向量机支持向量机(SVM)示意图示意图83SVM与神经网络（与神经网络（NN）的对比的对比SVM的理论基础比NN更坚实，更像一门严谨的“科学科学”（三要素：问题的表示、问题的解决、证明）SVM 严格的数学推理NN 强烈依赖于工程技巧推广能力推广能力取决于“经验风险值”和“置信范围值”，NN不能控制两者中的任何一个NN设计者需要用高超的工程技巧弥补了数学
50、上的缺陷84 SVM的的主要应用领域主要应用领域n手写数字识别n语音识别n人脸识别n文本分类n852.6.2 隐马尔可夫模型隐马尔可夫模型(HMM)n马尔可夫模型的由来n马尔可夫过程n一个实验球缸模型nHMM的基本原理nHMM的形式化描述nHMM的三个基本问题nHMM的三个主要算法86马尔可夫模型（马尔可夫模型（MM）的由来）的由来 n1870年，俄国有机化学家Vladimir V. Markovnikov第一次提出Markov Model（MM）nMM本质上是一种随机过程nHMM是一个二二重重Markov随随机机过过程程，包括具有状态转移概率的Markov链和输出观测值的随机过程nHMM的状
51、态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来n最成功的应用领域之一语音识别语音识别87 Markov过程过程n过程或系统在时刻T0所处状态为已知的条件下，过程在时刻TT0所处状态的条件分布与过程在时刻t0之前所处的状态无关。n通俗的说，就是在已经知道过程“现在”的条件下，其“将来”不依赖于“过去”。88一个实验一个实验球缸模型球缸模型n设有N个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下n根据某个初始概率分布，随机选择N个缸中的一个，例如第I个缸。n根据这个缸中彩球颜色的概率分布，随机选择一个球，记下球的颜色，记为O1，再把球放回缸中。n根据描述缸的转
52、移的概率分布，随机选择下一口缸，重复步骤1。n最后我们可以得到一个描述球的颜色的序列O1,O2,，称为观察值序列。 89Observed Ball SequenceUrn 3Urn 1Urn 2Veil球缸模型示意图球缸模型示意图90关于球缸模型的说明关于球缸模型的说明n缸之间的转移不能被直接观察到n从缸中所选取的球的颜色和缸并不是 一一对应的n每次选取哪个缸由一组转移概率决定91HMM中状态与观测的对应关系示意图中状态与观测的对应关系示意图92HMM的基本原理的基本原理nHMM概念的提出在实际问题中，观察到的事件与状态并非一一对应，而是通过一组概率分布相联系。nHMM是一个双重随机过程，两个
53、组成部分：n 马尔可夫链马尔可夫链：描述状态的转移，用转移概率转移概率描述。n 一般随机过程一般随机过程：描述状态与观察序列间的关系， 用观察值概率观察值概率描述。93Markov链链（ , A）随机过程随机过程（B）状态序列状态序列观察值序列观察值序列q1, q2, ., qTo1, o2, ., oTHMM的组成HMM的组成示意图的组成示意图94HMM的形式化描述的形式化描述nN是可能的状态空间nM是给定的一个观测值空间nA称作时间无关状态转移概率分布nB 是在给定状态下观察值概率分布条件n是在初始时刻状态空间的概率分布n模型(N, M, , A, B) 用来描述HMM 其中，N, M,
54、, B, A称为HMM的五元组 可简写为： （, A, B）95HMM中的三个基本问题中的三个基本问题n问题1：给定观察序列O=O1,O2,OT,以及模型（, A, B） , 如何计算P(O|)？n问题2：给定观察序列O=O1,O2,OT以及模型,如何选择一个对应的状态序列 Q = q1,q2,qT，使得Q能够最为合理的解释观察序列O？n问题3：如何调整模型参数（, A, B）, 使得P(O|)最大？ 96HMM的三个基本算法的三个基本算法n前向后向算法前向后向算法（解决问题1）n这个算法是用来计算给定一个观测值序列O以及一个模型时，由模型产生出观测值序列O的概率 。nViterbi算法算法（
55、解决问题2）n这个算法解决了给定一个观测值序列O和一个模型 ，在最佳意义上确定一个状态序列Q的问题。nBaum-Welch算法算法（解决问题3）n这个算法实际上是解决HMM训练，即HMM参数估计问题，或者说，给定一个观察值序列O，该算法能确定一个模型 ，使P(O| )最大。 97HMM的典型应用的典型应用语音识别语音识别982.7 数据挖掘数据挖掘n数据挖掘的由来n数据挖掘的创立n数据挖掘的主要应用n数据挖掘 vs. 知识发现n数据挖掘的基本过程n数据挖掘系统的基本结构n数据挖掘的基本问题n数据挖掘的发展趋势99n人类已进入一个崭新的信息时代 n数据库中存储的数据量急剧膨胀，但知识相对贫乏 n
56、需要从海量数据库和大量繁杂信息中提取有价值的知识，进一步提高信息的利用率n产生了一个新的研究方向：基于数据库的知识发现（Knowledge Discovery in Database），以及相应的数据挖掘（Data Mining）理论和技术的研究 数据挖掘的由来数据挖掘的由来100KDD的创立的创立n基于数据库的知识发现（KDD）一词首次出现在1989年举行的第11届AAAI学术会议上n1995年在加拿大蒙特利尔召开了第1届KDD国际学术会议（KDD95）n由Kluwers Publishers出版，1997年创刊的“Knowledge Discovery and Data Mining”是该
57、领域中的第一本学术刊物 101数据挖掘数据库技术概率统计高性能计算人工智能机器学习可视化数据挖掘是多学科交叉的产物数据挖掘是多学科交叉的产物102KDD已经成为已经成为AI的研究热点的研究热点n目前，关于KDD的研究工作已经被众多领域所关注，如信息管理、商业、医疗、金融、过程控制等领域。n作为大规模数据库中先进的数据分析工具，KDD的研究已经成为数据库及人工智能领域研究的一个热点。1031.数据挖掘的主要应用数据挖掘的主要应用n电信 ：客户流失原因分析n银行：聚类（细分）, 交叉销售n百货公司/超市：购物篮分析 （关联规则）n保险：细分、交叉销售、流失（原因分析）n信用卡： 欺诈探测、细分n电
58、子商务： 网站日志分析n税务部门：偷漏税行为探测n警察机关：犯罪行为分析n医学： 医疗保健n104数据挖掘数据挖掘 vs. 知识发现知识发现n数据挖掘数据挖掘（Data Mining）：从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。n知识发现知识发现（Knowledge Discovery in Database）：是用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后隐藏的知识，也称数据库中的知识发现。1051.数据挖掘的基本过程数据挖掘的基本过程1061.数据挖掘系统的基本结构数据挖掘系
59、统的基本结构数据仓库数据仓库数据清洗和集成数据清洗和集成过滤过滤数据库数据库数据库或数据仓库服务器数据挖掘引擎模式评价图形用户接口知识库知识库1071. 数据挖掘的主要问题数据挖掘的主要问题n数据挖掘结果的表示和显示n处理噪声和不完全数据n模式评估 兴趣度问题n数据挖掘算法的有效性和可伸缩性n并行、分布式和增量挖掘算法n异种数据库和全球信息系统挖掘信息n1081.数据挖掘的发展趋势数据挖掘的发展趋势n视频和音频数据挖掘n科学和统计数据挖掘n数据挖掘的应用探索n可伸缩的数据挖掘方法n数据挖掘与数据库系统、数据仓库和Web数据库系统的集成n数据挖掘语言的标准化n可视化数据挖掘n复杂数据类型挖掘的方
60、法nWeb挖掘、数据流（Data streams）挖掘n数据挖掘中的隐私保护与信息安全n1092.8 AI的未来展望的未来展望n在未来的10年之内，整个AI领域仍将以“基于概率统计的机器学习方法”为最主流的研究及应用方向。n以神经信息学、脑机工程（BME）等为代表的新一代AI技术将取得重大突破，并将成为未来AI中新的研究热点。n通过巧妙地将AI技术“嵌入”现有的各种软硬件系统等方式，使得AI技术及智能系统将更广泛、更深入地应用于其它领域，AI必将成为一种强大的共性支撑技术。n110THANKS FOR YOUR PRESENCE!“We are a scientific society dev
61、oted to the study of artificial intelligence. Our incorporating charter, with the characteristic precision of legal documents goes no further than to record the words artificial intelligence as an indicator of our proper object of concern. Of the semantics behind these terms, by its silence, it leaves it to us, the society, to determine.” by Allen Newell, “AAAI Presidents Message” (1980)111
