《人工智能导论》课件

《《人工智能导论》课件》由会员分享，可在线阅读，更多相关《《人工智能导论》课件（27页珍藏版）》请在金锄头文库上搜索。

1、人工智能导论,方若宇 ,2008年秋季汕头大学计算机系本科课程,学习,概述 决策树学习 神经网络学习,什么是机器学习？ Simon（1983）： 学习就是系统中的变化，这种变化使系统比以前更有效地去做同样的工作。 Minsky (1985)： 学习是在我们头脑中（心里内部）进行有用的变化。 学习是一种具有多侧面的现象。学习的过程有：获取新的陈述性知识、通过教育或实践发展机械技能和认知能力、将新知识组织成为通用化和有效的表达形式、借助观察和实验发现新的事实和新的理论。,机器学习的基本形式 知识获取和技能求精。 学习的本质就是获取新的知识。包括物理系统和行为的描述和建模，构造客观现实的表示。 知识

2、获取 通过实践逐渐改造机制和认知技能。 例：骑自行车。这些技能包括意识的或机制的协调。这种改进又是通过反复实践和从失败的行为中纠正偏差来进行的。 技能求精 知识获取的本质可能是一个自觉的过程，其结果是产生新的符号知识结构和智力模型。而技能求精则是下意识地借助于反复地实践来实现的。 本章只涉及学习的知识获取问题。,为什么要研究机器学习？ 人工智能主要是为了研究人的智能，模仿其机理将其应用于工程的科学。在这个过程中必然会问道：“人类怎样做才能获取这种特殊技能（或知识）？”。 当前人工智能研究的主要障碍和发展方向之一就是机器学习。包括学习的计算理论和构造学习系统。现在的人工智能系统还完全没有或仅有很

3、有限的学习能力。系统中的知识由人工编程送入系统，知识中的错误也不能自动改正。也就是说，现有的大多数人工智能是演绎的、没有归纳推理，因而不能自动获取和生成知识。 未来的计算机将有自动获取知识的能力，它们直接由书本学习，通过与人谈话学习，通过观察学习。它们通过实践自我完善，克服人的存储少、效率低、注意力分散、难以传送所获取的知识等局限性。一台计算机获取的知识很容易复制给任何其它机器。,机器学习研究目的与特点 希望得到通用的算法 研究了解学习知识的模型、认知模型 解决实际问题的知识库与系统，达到工程目标 不可预测性,机器学习模型,学习是建立理论、形成假设和进行归纳推理的过程。 整个过程包括：信息的存

4、储、知识的处理两部分,环境,学习环节,知识库,执行环节,机器学习的类型,按学习策略的不同机器学习可以分为以下几类： 机械式学习，直接输入新知识（记忆学习） 学习者不需要进行任何推理或知识转换，将知识直接装进机器中。 根据示教学习（传授学习、指点学习） 从老师或其它有结构的事物获取知识。要求学习者将输入语言的知识转换成它本身的内部表示形式。并把新的信息和它原有的知识有机地结合为一体。 通过类推学习（演绎学习） 学习者找出现有知识中所要产生的新概念或技能十分类似的部分。将它们转换或扩大成适合新情况的形式，从而取得新的事实或技能。 从例子中学习（归纳学习） 给学习者提供某一概念的一组正例和反例，学习

5、者归纳出一个总的概念描述，使它适合于所有的正例且排除所有的反例。（目前研究较多的一种方法） 类比学习 演绎学习与归纳学习的组合。匹配不同论域的描述、确定公共的结构。以此作为类比映射的基础。寻找公共子结构是归纳推理，而实现类比映射是演绎推理。,机器学习发展历史,神经系统模型和决策理论 50年代开始。其特点是对开始与无初始结构和面向作业知识的通用学习系统感兴趣。包括构造多种具有随机或部分随机的初始结构的基于神经模型的机器。这些系统一般称为神经网络或自组织系统。由于当时计算机技术状态，多停留在理论和硬件上。这些元件类似于神经元，他们实现简单的逻辑功能。 1965年左右，神经网络经验模式导致了模式识别

6、这一新学科以及机器学习的决策理论方法。这种方法中学习就是从给定的一组经过选择的例子中获得判断函数，有线性的、多项式的、或相关的形式。 当时，Samuel(1959-1963)的跳棋程序是最著名的成功的学习系统之一。达到了跳棋大师的水平。 符号概念获取 1975年左右提出的。这类学习过程通过分析一些概念的正例和反例构造出这些概念的符号表示。表示的形式一般是逻辑表达式、决策树、产生式规则或语义网络。代表有Winston的ARCH。 知识加强和论域专用学习 此方法是70年代中期开始，沿着符号主义路线进行的。在原有基础上逐步加强、重于专业的专用性。强调使用面向任务的知识和它对学习过程的引导作用。系统包

7、括预先确定的概念、知识结构、论域约束、启发式规则和论域有关的变换。系统在开始并不具有所有的属性或概念，在学习过程中系统应得到一些新的属性或概念。 没有绝对的学习方法。许多系统体现出上述途径的组合。 ,决策树学习,决策树学习,一种描述概念空间的有效的归纳推理办法。基于决策树的学习方法可以进行不相关的多概念学习，具有简单快捷的优势，已经在各个领域取得广泛应用。 决策树学习是以实例为基础的归纳学习。从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。,一个分类的任务,决策树学习,

8、决策树学习采用的是自顶向下的递归方法。 决策树的每一层节点依照某一属性值向下分为子节点，待分类的实例在每一节点处与该节点相关的属性值进行比较，根据不同的比较结果向相应的子节点扩展，这一过程在到达决策树的叶节点时结束，此时得到结论。 从根节点到叶节点的每一条路经都对应着一条合理的规则，规则间各个部分（各个层的条件）的关系是合取关系。整个决策树就对应着一组析取的规则。 决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练例子进行较好的标注，就能够进行学习。如果在应用中发现不符合规则的实例，程序会询问用户该实例的正确分类，从而生成新的分枝和叶子，并添加

9、到树中。,树是由节点和分枝组成的层次数据结构。节点用于存贮信息或知识，分枝用于连接各个节点。树是图的一个特例，图是更一般的数学结构，如贝叶斯网络。 决策树是描述分类过程的一种数据结构，从上端的根节点开始，各种分类原则被引用进来，并依这些分类原则将根节点的数据集划分为子集，这一划分过程直到某种约束条件满足而结束。,可以看到，一个决策树的内部结点包含学习的实例，每层分枝代表了实例的一个属性的可能取值，叶节点是最终划分成的类。如果判定是二元的，那么构造的将是一棵二叉树，在树中每回答一个问题就降到树的下一层，这类树一般称为CART（Classification And Regression Tree）

10、。 判定结构可以机械的转变成产生式规则。可以通过对结构进行广度优先搜索，并在每个节点生成“IFTHEN”规则来实现。如图6-13的决策树可以转换成下规则： IF “个子大” THEN IF “脖子短” THEN IF “鼻子长” THEN 可能是大象 形式化表示成,Shannon信息熵 自信息量 设信源X发出ai 的概率p(ai)，在收到符号ai之前，收信者对ai 的不确定性定义为ai的自信息量I(ai)。I(ai) = -log2 p(ai)。 信息熵 自信息量只能反映符号的不确定性，而信息熵用来度量整个信源整体的不确定性，定义为： 其中，r为信源X发出的所有可能的符号类型。信息熵反应了信源

11、每发出一个符号所提供的平均信息量。 条件熵 设信源为X，收信者收到信息Y，用条件熵H(X|Y)来描述收信者在收到Y后对X的不确定性估计。设X的符号ai，Y的符号bj，p(ai|bj)为当Y为bj时，X为ai的概率，则有： 平均互信息量 用平均互信息量来表示信号Y所能提供的关于X的信息量的大小，用I(X, Y)表示：,设学习的实例集为 其中Si为学习实例，T为实例集大小。对于有指导的学习，任一个Si具有明确标定的类别 ， 向量表示该实例的特性， 即 Si的信息为，如果一个观测值具有属性则应该划归为类 ，应该有下面的规则总结出来 式中Xi为事件所具有的第i个属性。这里的属性和类具有广泛的意义。,防

12、雹减灾决策的机器学习的实例,防雹部门在雹灾来临前需要采取不同的方案以减轻灾害可能造成的危害, 常用的方法是根据具体的自然条件使用防雹炮。 一般有3种决策: u1: 使用大口径防雹炮 u2: 使用小口径防雹炮 u3: 不能防雹炮 作出决策所依据的条件: x1(云层的性质): 雨云; 浓积云; 雨层云 x2(风速): 微风; 大风 x3(季节): 夏秋; 春冬 x4(地理条件): 向风坡; 背风坡 这是一个典型的依据知识和具体上下文进行决策的任务, 通常决策的任务是由具有一定专业能力的人士来作出的。 机器学习算法使计算机通过一个学习的过程能够获得这种专业能力。,学习的实例集为 S=s1,s2,sT

13、 , 其中Si为一个具体学习实例, T为实例集大小。 对于有指导的学习, 任一个si具有明确标定的类别u,并有一个属性向量表示该实例的特性,即 s=(a1, a1 , am; u) 实例s含有的信息即为,如果一个观测值具有属性(a1, a1 , am)则应该划归为类u 。 从学习的角度看, 应该有下面的规则总结出来 x1=a x2=a xm=a u (xi为事件所具有的第i个属性),决策树学习-ID3算法,ID3 算法将S视为一个离散信息系统, 并用信息墒表示该系统的信息量。S中的决策方案u为随机事件,而属性可以看作加入的信息源。在没有任何信息的时候,S的墒为 其中N为可选方案总数. 在上面的

14、例子中,计算S的墒为 其中 P(u1)=4/24, P(u2)=5/24, P(u3)=15/24,将S作为决策树的根结点, 引入各属性值, 依据某一属性xi 的各个取值,即可将根结点分裂成子结点。这一过程相当于引入分类信息,因而各子集的墒总量减少。 各个子集的总墒值可以认为是已知xi时S的条件墒, 即H(S| xi), 用各个子集的信息墒期望计算条件墒,可得 St为 xi=t的例子集, |S|为例子集S的大小。 如果取属性云层性质x1, 则St分别如下: S1=1,2,8 S1=9,10,16 S1=17,18,24 其中各训练例子用表中的序号表示,且有|S1|= |S2|= |S3|=8,

15、条件墒可以计算属性对训练例子集的墒贡献的大小, H(S|xi)越小,说明xi引入的信息越多,系统的墒下降得也越大。为了产生最有效的规则,ID3采用贪心策略,即每次选择信息量最大的属性进行决策树分裂,计算中表现为使训练例子集的墒下降最大。 在防雹例子中,以S1为例来计算属性x1的条件墒。 Ps1(u1)=2/8 Ps1(u2)=2/8 Ps1(u3)=4/8 有 同样求得 代入条件墒公式 同理求得其他属性的条件墒 选择x4作为第一次分裂的属性将使树的墒下降最大,分裂的结果得到2个子结点例子集合。用同样的方法对子集选择属性进行分裂,直到每个子集都属于同一类,此时所有叶子结点的总墒值为零,完整的决策

16、树生成。,图中非叶子结点上的数对(a,b)表示属性xa=b, 而叶子结点上的结构(a,b;c)表示属性xa=b时产生决策c。寻找所有从根结点出发到叶子结点的路径,每条路径将对应一条规则。 上述的图表达什么样的规则。,决策树的特点,证据由属性值对表示 证据由固定的的属性和其值表示，如属性（温度），值（热）最简单的学习情况时每个属性拥有少量的不相关的值。 目标函数有离散输出值 决策树分配一个二值的树，很容易扩展成为多于两个的输出值。 需要不相关的描述 决策树原则上是表述不相关的表示 容忍训练数据的错误 对训练样本和表述样本的属性值的错误都有较强的鲁棒性。 训练数据可以缺少值 可以采用缺少属性值的样本学习。（不是所有样本都有）,构造一棵决策树要解决四个问题 收集待分类的数据: 这些数据的所有属性应该是完全标注的。 设