人工智能复习材料.doc

时间：2021-02-08 00:19:22 来源：蒲公英阅读网 本文已影响人

相关热词搜索：人工智能 复习 材料

　一、绪 一、绪 1.21 世纪最具有发展前景和最具影响力的两大带头学科群：生命科学群与群体科学群 2.人工智能流派（符号智能——物理符号系统假设和有限合理性原理为基础，认为认知是一种符号处理的过程，人类思维过程也可用某种符号来描述，思维就是计算，认知就是计算；计算智能—— 认为人类认知活动主要基于大脑神经元的活动。

　核心：人工神经网络、进化计算；群体智能——智能可通过群体协同模拟，如多智能体系统，蚁群算法和生态平衡；）

　3.Minsky 总结了 AI 的两类任务：理论研究与技术研究； 4.Turing 测试（人与计算机分处在不同房间中; 相互对话;真实人不能判断对话方是人还是计算机;计算机就具有智能。) 二、 二、 概述 概述 1.人工智能主要研究用人工的方法和技术，模仿、延伸和扩展人的智能,实现机器智能。人工智能的长期目标是实现人类水平的人工智能。人工智能尚缺乏必要的理论。在一些关键技术方面,

　诸如机器学习、非单调推理、常识性知识表示、不确定推理等尚未取得突破性的进展。人工智能对全局性判断模糊信息处理、多粒度视觉信息的处理是极为困难的。人工智能还处于智能学科研究的早期阶段, 必须开展智能科学的研究。

　智能科学研究智能的基本理论和实现技术，是由脑科学、认知科学、人工智能等学科构成的交叉学科。

　2.认知是和情感、动机、意志等相对的理智或认识过程。认知科学是研究人类感知和思维信息处理过程的科学,

　包括从感觉的输入到复杂问题求解, 从人类个体到人类社会的智能活动,

　以及人类智能和机器智能的性质。

　3.人工智能的五个基本问题(1) 知识与概念化是否是人工智能的核心(2) 认知能力能否与载体分开来研究（3) 认知的轨迹是否可用类自然语言来描述(4) 学习能力能否与认知分开来研究？ (5) 所有的认知是否有一种统一的结构 4.思维是客观现实的反映过程，是具有意识的人脑对于客观现实的本质属性、内部规律性的自觉的、间接的和概括的反映。

　5.智能是个体认识客观事物和运用知识解决问题的能力。

　符号智能：以知识为基础，通过推理进行问题求解。也即所谓的传统人工智能。

　计算智能：以数据为基础，通过训练建立联系，进行问题求解。人工神经网络、遗传算法、模糊系统、进化程序设计、人工生命等都可以包括在计算智能。

　6.人工智能的研究方法：①逻辑学派以 Simon, Minsky 和 Newell 等为代表，从人的思维活动出发，利用计算机进行宏观功能模拟。②认知学派逻辑学派是以 McCarthy 和 Nilsson 等为代表，主张用逻辑来研究人工智能，即用形式化的方法描述客观世界 ③行为学派 Brooks 认为人工智能的研究应走出这种抽象过份简单的现实世界模型的象牙塔，而以复杂的现实世界为背景，让人工智能理论、技术先经受解决实际问题的考验，并在这种考验中成长。提出了无需知识表示的智能、无需推理的智能。

　7.推理：从一个或几个已知的判断(前提)逻辑地推论出一个新的判断(结论)的思维形式。

　 非单调推理：指的是一个正确的公理加到理论中,

　反而会使预先所得到的一些结论变得无效了。非单调推理过程：建立假设, 进行标准逻辑意义下的推理,

　若发现不一致, 进行回溯, 以便消除不一致, 再建立新的假设。定性推理：把物理系统或物理过程细分为子系统或子过程,

　对于每个子系统或子过程以及它们之间的相互作用或影响都建立起结构描述, 通过局部因果性的传播和行为合成获得实际物理系统的行为描述和功能描述。

　8.学习的基本机制是设法把在一种情况下是成功的表现行为转移到另一类似的新情况中去。学习是获取知识、积累经验、改进性能、发现规律、适应环境的过程。知识、知识表示及运用知识的推理算法是人工智能的核心,

　而机器学习则是关键问题。

　9.机器学习的研究四个阶段：

　无知识的学习：

　主要研究神经元模型和基于决策论方法的自适应和自组织系统。

　符号概念获取：给定某一类别的若干正例和反例，从中获得该类别的一般定义。

　实例学习：从实例学习结构描述。

　有知识的学习：把大量知识引入学习系统做为背景知识 机器学习的风范：

　归纳学习：研究一般性概念的描述和概念聚类；分析学习：在领域知识指导下进行实例学习,

　包括基于解释的学习、 知识块学习等。

　发现学习：根据实验数据或模型重新发现新的定律的方法。④遗传学习：模拟生物繁衍的变异和自然选择，把概念的各种变体当作物种的个体,

　根据客观功能测试概念的诱发变化和重组合并,

　决定哪种情况应在基因组合中予以保留。⑤连接学习是神经网络通过典型实例的训练, 识别输入模式的不同类别。

　10.分布式人工智能：研究在逻辑上或物理上分散的智能动作者如何协调其智能行为，即协调它们的知识、技能和规划, 求解单目标或多目标问题，为设计和建立大型复杂的智能系统或计算机支持协同工作提供有效途径。

　11.知识系统包括：专家系统、知识库系统、智能决策系统等。

　专家系统：专家系统是一种模拟人类专家解决领域问题的计算机程序系统。

　这类计算机程序包括两部分: 知识库, 它表示和存储由任务所指定领域知识的一组数据结构集合，包含有关领域的事实和专家水平的启发式知识。推理机, 它是构造推理路径的一组推理方法集合,

　以便导致问题求解、假设的形成、目标的满足等。由于推理采用的机理、概念不同，推理机形成多种范型的格局。知识库系统：把知识以一定的结构存入计算机, 进行知识的管理和问题求解, 实现知识的共享。决策支持系统是计算机科学（包括人工智能）、行为科学和系统科学相结合的产物，是以支持半结构化和非结构化决策过程为特征的一类计算机辅助决策系统，用于支持高级管理人员进行战略规划和宏观决策。其组成 ：数据库管理子系统、模型库管理子系统、方法库管理子系统、知识库管理子系统、会话子系统。

　 三、 三、问题表示及求解 问题表示及求解 1 1 问题表达及其变换 问题表达及其变换 1 同构同态变换 2 问题分解法 与图（树）描述问题分解。

　或图（树）描述同构同态变换 。

　2 2 问题的直接求解法状态空间求解法 问题的直接求解法状态空间求解法：1 用状态描述与问题相关的事实和事实间的关系 2 问题演绎法基本思想：分解原问题成若干个子问题。3 博弈问题求解法 属于对策性课题，表示若干个体开展竞争的过程。

　度量问题求解的性能 度量问题求解的性能问题求解算法的输出不是 Failure 就是解。完备性：当问题有解时，这个算法能否保证找到一个解最优性：算法是否能找到最优解？时间复杂度：找到一个解需要花费多长时间？空间复杂度：在执行算法的过程中需要多少内存？ 3 3 状态空间图搜索算法搜索（ 状态空间图搜索算法搜索（Search Search）， ），即寻找，设法在庞大状态空间图中找到目标。也可以把搜索看作是一种推理，它是人工智能问题求解的基本方法之一。主要分为两类性质的搜索：即基本搜索和智能搜索。基本搜索是一种没有任何经验和知识起作用的、由某种规则所确定的非智能性的搜索；启发式搜索（Heuristic Search）：其特点在于是一种有准备的、追求效率而有的放矢的智能搜索，它要求依据某种知识及信息的指导，通过逐一状态比较而找到符合规定条件的目标状态解。

　4 4 问题世界的全部信息空间划分为三类：

　问题世界的全部信息空间划分为三类：（1）全信息环境 Ee；已知与问题的解有关的全部信息，其搜索的目标和任务是：运用知识和经验，设法找到最佳路径，以便取得理想搜索效果。（2）部分已知信息环境 Ep；当只有部分信息已知，这时其目标和任务是：充分利用已知信息，把未知的信息不利影响设法降到最低程度，尽可能按照最佳搜索路径取得理想搜索效果。或者设法弥补信息损失，发挥已知信息作用，扬长避短，制定策略来克敌制胜。（3）未知信息环境 En 对于未知信息环境的问题求解，首先要设法变 En 为部分已知信息环境 Ep 来解决。

　5 5状态空间表示法 状态空间表示法 1状态：描述某一类事物在不同时刻所处于的信息状况。可用一组变量的有序组合来表示为如下形式：

　Sk=[ x0, x1, x2, x3, …]T 其中的每个元素 xi (i=0,1,2…)称为分量，相应的变量值域为[ai,bi]。给定每个分量的值，就得到了一个具体的状态。状态的维数可以任意，一般为有限值。2 操作：描述了状态之间的关系。它可以是一个行为步骤，也可以是一个改变过程、规则或操作数。使状态中的某些分量发生改变，就将使问题由一个具体状态变化到了另一个具体状态。问题的状态空间可用一个三元序组来表示：〈S，F，G〉S 是初始状态集；F 是操作的集合；而 G 为目标状态集。3 问题的求解就转化为从状态空间图的初始状态 S0 出发，搜索寻取目标状态 Sg 的路径问题。搜索过程所得到的操作序列就反映了问题的解路径。故搜索求解的过程可简洁地表示为：Sg=fn(…（f2(f1(S0))）…)式中，fi 表示对其右边的当前状态将进行第 i 个操作 6 6 搜索法求解问题的基本思想：

　搜索法求解问题的基本思想：

　1 将初始状态当作当前状态。

　2 选择适当的算符作用于当前状态得到后继状态。3 检查这组后继状态中是否有目标状态。

　7 7 问题的状态空间可用有向图来表达，又常称其为状态树 问题的状态空间可用有向图来表达，又常称其为状态树

　状态空间图在计算机中有两种存储方式：一种是图的显式存储，另一种是图的隐式存储。

　图的显式存储 图的显式存储: :（1）概念：所谓图的显式存储，即把问题的全部状态空间图直接都存于计算机中的方式。诸如一般计算机文件、程序文件和库文件的存储等，均为图的显式存储方式。

　（2）适用条件：通常图的显式存储方式需要占据计算机的大量存储空间和处理时间，故这种存储方式仅适用于状态空间十分有限以及较简单的问题求解。（3）特点：其优点是直观、明了，但缺点是占据存储空间大。图的隐式存储 图的隐式存储: :（1）概念：仅在计算机中存储关于要求解问题的相关各种知识，只在必要时再由相关的信息和知识逐步生成状态空间图的方式称为图的隐式存储。（2）适用条件：适用于一般问题求解，尤其适宜于状态空间庞大的情况。（3）特点：占据空间小，但不够直观，与图的显式存储刚好特点互补。

　8 8 隐式图的搜索过程 隐式图的搜索过程: :1.按照问题的已知条件，产生一个初始状态 S0 的有限描述，并依照一定的数据结构形式存于计算机中；2.用发生器函数 Q(x)作用于 S0 并扩展生成 S0 的子节点 Si , 逐一比较目标节点 Sg 是否在 Si 中出现，若出现则搜索成功。3.若没有出现 Sg，就用估计函数 f(x)对所有这些刚生成的子节点 Si 进行价值评估，在适当范围内选择最有希望的结点 Sk 替代S0，返回步 2 对 Sk 进行扩展生成。当所有可扩展的节点均已用 Q(x)生成，仍无 Sg 出现，则搜索失败。可逐层按照 f(x)选择子节点并返回步 2、步 3 反复进行扩展生成，比较目标，价值评估等操作，直到找到目标节点 Sg 为止。

　9 9 具体问题搜索求解可总结为如下的思路和步骤：

　具体问题搜索求解可总结为如下的思路和步骤：（1）设定状态变量及确定值域；（2）确定状态组，分别列出初始状态集和目标状态集；（3）定义并确定操作集； （4）估计全部状态空间数，并尽可能列出全部状态空间或予以描述之；（5）当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解。

　10 10 广度优先算法搜索原则：

　广度优先算法搜索原则：1 1 深度越小、越早生成结点的优先级越高。2 当最低层不止一个结点时，它选择最先生成的结点进行搜索。

　广度优先算法步骤：(1) 初始结点 S 加入到队列 OPEN 的尾部；(2) 若 OPEN 为空，则搜索失败，问题无解；(3) 取出 OPEN 队头的结点 n，并放入 CLOSE 队列中；(4) 若 n 是目标结点 D，则搜索成功，问题有解；(5) 若 n 是叶结点，则转(2)；(6) 扩展 n 结点(即找出它的所有直接后继)，并把它的诸子结点依次加入 OPEN 队尾，修改这些子结点的返回指针，使其指向结点 n。转(2)。

　11 11 深度优先搜索搜索原则：

　深度优先搜索搜索原则：1 深度越大、越晚产生结点的优先级越高。2 深度优先搜索是不完备的，属于非算法的搜索过程。深度优先算法步骤：(1) 初始结点 S 放入堆栈 OPEN 中； (2) 若 OPEN 为空，则搜索失败，问题无解； (3) 弹出 OPEN 表中最顶端结点放到 CLOSE 表中，并给出顺序编号 n； (4) 若 n 为目标结点 D，则搜索成功，问题有解； (5) 若 n 无子结点，转(2)；(6) 扩展 n 结点，将其所有子结点配上返回 n 的指针，并按次序压入 OPEN 堆栈，转(2) 。

　12 12 有界深度优先搜索 有界深度优先搜索特点：

　引入搜索深度限制值 d，使深度优先搜索过程具有完备性 。有界深度优先算法步骤：(1)初始结点 S 放入堆栈 OPEN 中；(2)若 OPEN 为空，则搜索失败，问题无解；(3)弹出 OPEN 中栈顶结点 n，放入 CLOSE 表中，并给出顺序编号 n；(4)若 n 为目标结点 D，则搜索成功，问题有解；(5)若 n 的深度 d(n)=d，则转(2) ；(6)若 n 无子结点，即不可扩展，转(2) ；(7)扩展结点 n，将其所有子结点配上返回 n 的指针，并压入 OPEN 堆栈，转(2)

　13 13 代价推进搜索特点：

　代价推进搜索特点：节点间有向边的代价不同 14 14 基本搜索的局限性及其特点为：

　基本搜索的局限性及其特点为：

　①基本搜索策略普遍适用于树状问题求解，控制性知识简单，容易编程在计算机上实现。但是，它表现出来的缺点也很突出：一般必须知道问题的全部状态空间，搜索效果差，求解能力弱，故常被称为弱方法。

　②它们都是依据某种固定规则运行的搜索，均属于非启发的强力搜索，没有表现出智能搜索的活跃性与灵活性。也就是说，问题搜索树的生成、扩展以及节点接受考察的次序等，都是由生硬死板的搜索方法决定的，而不由具体问题状态信息引导与经验分析来决定； ③由于基本搜索策略疏忽了对给定问题的特有知识的分析,没有充分考虑所要求解问题的自身发展规律和特性，搜索完全是按事先确定好的固定排序来进行的，这是一种穷尽遍历的大海捞针式的策略，没有任何启发式信息引导，往往使得实际搜索效率很低，故又被称为盲目搜索。

　 15 15 启发式搜索策略 启发式搜索策略利用与问题解有关的启发信息来作引导的搜索策略。特点是：由于充分考虑到问题求解所应用到的各种启发信息及知识，包括利用常识性推理和专家经验等信息与知识，启发式搜索能够动态地确定操作排序，优先调用较合适的操作规则，扩展、比较并选择最有希望的节点，使搜索尽可能以最快的速度，最短的距离，最小的代价，朝着最有利于达到目标节点的方向推进。即以智能思想调节搜索区，使尽量沿着最有希望找到解的路径方向上，纵向小范围地搜索前进。

　采用启发式搜索策略：

　采用启发式搜索策略：（1）使用了控制性知识中的启发信息，因而弥补了略去的部分状态空间所带来的有用信息丢失；（2）

　启发式搜索往往是深度优先搜索法的改进。只需知道问题的部分状态空间，就可以求解智能问题。（3）与基本搜索相比，启发式搜索最大特点就是搜索效率要高得多。搜索效率及其评价：

　搜索效率及其评价：P=L/T L 是从根节点到达目标节点的深度；T 是在整个搜索过程中产生节点总数(不计根节点)，因此，这里 P 反映的是朝着目标搜索时的搜索宽度。

　16 估价函数，是指从问题树根节点到达目标节点的搜索中，所要耗费全部代价的一种估计值，记为 f (n)。f(n)=g(n)+h(n) ① f (n)：表示从根节点 So 出发，经过当前节点 Sn，到达目标节点 Sg 已耗费及将要耗费代价总和的估计值。

　② g (n)：表示从根节点 So，在到达目标节点 Sg 的搜索路径上，已到达当前节点 Sn，g (n) 即表示从 So→Sn 已耗费的代价。

　③ h (n)：指从当前节点 Sn，，预测估计到达目标节点 Sg，将要耗费的可能代价。也就是说，h（n）表示了 Sn→Sg 这一路径搜索段上将要耗费代价的可能值。称之为启发函数。

　17 启发式搜索方法分为局部择优搜索和全局择优搜索两大类 启发式搜索方法分为局部择优搜索和全局择优搜索两大类。瞎子爬山局部择优搜索 过程：每搜索到达一个节点，其随后选择的下一节点不是按规则预定的或盲目选定的，而是按经验进行智能处理，使用估计函数 f(x)来搜索当前最优的节点。

　优点：方法简单，由于取消了 OPEN 表，要处理的数据量减少了，所以占用内存空间少、速度快。缺点：瞎子爬山法主要只在单因素，单极值的情况下使用，而在多极值情况下会遇到许多困难，导致找不到最佳解。

　18 瞎子爬山法进行人机交互搜索（智能搜索）的主要思路和步骤如下：

　瞎子爬山法进行人机交互搜索（智能搜索）的主要思路和步骤如下：（1）分析搜索的性质；（2）是否有许多可供选择的路径和方案，各种选择是否有优劣之分； （3）有哪些可供利用的启发信息；（4）启发信息可否编制成操作简便、易于判别、便于实现的规则；（5）编程完成使用规则的程序，用之进行择优搜索。

　19 全局择优搜索又称为有序搜索法 全局择优搜索又称为有序搜索法 搜索过程如下 搜索过程如下:(1) 把初始节点 So 放入 OPEN 表，计算 f(So)；(2) 如果 OPEN 表为空，则转到步(8)。

　(3 )把 OPEN 表中的第一个节点(记节点 n)从表中移出，放入 CLOSED 表；(4) 考察节点 n 是否为目标节点。若是，则成功得到问题的一个解，标记其解路径。并标记目标节点顺序，记为 Sgk,转步(2)，以便搜索下一个解。(5) 若节点 n 不可扩展,则转步(7)。(6) 扩展节点 n，用估价函数 f(n)计算每个子节点的估价值，并为每个子节点配置指向父节点的指针，把这些子节点都送人 OPEN 表中，然后对 OPEN 表中的全部节点按估价从小至大进行排序；(7) 转步(2)；(8) 分别计算每一个目标节点的代价值，按照代价值从小至大进行排序。则排在最前面的目标节点优于排在后面的目标节点。

　20A 搜索算法的基本特点是：

　搜索算法的基本特点是：①如何寻找并设计一个能够高效率求解问题的 h(n)，并构造出估价函数 f(n)；②使用 OPEN 表和CLOSED 表共同记载算法的搜索结果，并确保一旦找到问题解能够返回，同时得到该问题解的完整搜索路径；③A 搜索算法总是按照 f(n)的大小来排列待扩展状态的次序，每次总是在 f(n)值中选择最小代价者进行扩展。

　在 A 搜索算法中，若要求估价函数 f(n)的 h(n)满足 h(n)≤h*(n)条件时，则该算法称为 A*搜索算法。

　21 与 与/或树代价计算：具体约定为 或树代价计算：具体约定为 ① 通常可解的端节点 t 的代价值为 0，可表示为：h(t)=0；② 可解节点 n 的代价 h(n)为有限值，对可解节点 n 的代价需要具体加以计算；③ 不可解节点 x 的代价为无穷大或无定义，可表示为：h(x)=∞ 或无意义； ④ 如果节点 x 不可扩展，且又不是终止节点，则定义 h(x)=∞。代价计算策略 代价计算策略：设 C(x,y)表示节点 x 到节点 y 的代价,具体代价的计算方法如下：（1）或节点计算：若 x 是或节点，y1,y2, …,yn 是它的子节点，则 x 节点的代价计算式为：h(x)=min｛C(x,yi)+ h(yi)｝

　 (1≤i≤n)（2）与节点计算：

　① 和代价法：若 x 是与节点，通常按照和代价法计算 h(x)= ∑{C(x,yi)+ h(yi)}，其中，i 由 1 累加到 n.② 最大代价法计算：与节点的最大代价法计算式为 h(x)=max｛C(x,yi)+ h(yi)｝

　 (1≤i≤n) 22 对抗搜索 对抗搜索—博弈 博弈 博弈树：

　博弈树：在博弈过程中，按照博弈规则和步法状态过程分析，客观评判博弈双方在各自分枝节点上所获得的分数估计值，并依照其中任何一方的角度而依次生成具有得分值表示的与/或搜索树博弈原理：

　博弈原理：博弈的各方总是要挑选对自己最为有利而对对方最不利的那个行动方案。特点：（ 特点：（1）

　）博弈的初始格局总是要求从初始节点出发，为寻求某个确定的方向而选取行动方案；（ （2）

　）在博弈树中，由于双方轮流地扩展节点， 双方轮流地扩展节点，“或 或”节点和 节点和“与 与”节点逐层交替出现。

　节点逐层交替出现。如果自己一方扩展的节点之间是“或”关系，则对方扩展的节点之间是“与”关系。（ （3）

　）把本方获胜的终局定义为本原问题，相应最优搜索路径上的节点是可解节点，而所有使对方获胜的终局和属于对方最优搜索路径上的节点则是不可解节点。此外，所有其它的节点则是具有风险的中间节点。

　23 极小极大搜索法 极小极大搜索法

　 边生成边计算，从而直接剪除某些分枝的技术，称之为α α-β剪枝技术 β剪枝技术。α值和β值：对于一个“或”节点来说，为了剪除某些分枝，应该取其子节点中的最大倒推值，把它作为当前下界的参考，称此值为α值；对于一个“与”节点来说，应取其子节点中的最小倒推值，把它作为当前上界的参考，称此值为β值。

　α α-β剪枝技术的一般规律及其分析规则如下：

　β剪枝技术的一般规律及其分析规则如下：（1）任何“与”节点 x 的β值如果不能升高其父节点的α值，则对节点 x 以下的分枝可停止搜索，并实施剪枝，这种剪枝称为α剪枝；并把该组“与”节点中的极大值确定为其父节点的α值。（2）任何“或”节点x 的α值如果不能降低其父节点的β值，则对节点 x 以下的分枝可停止搜索，并实施剪枝，这种剪枝称为β剪枝；并把该组“或”节点中的极小值确定为其父节点的β值。（3）在实施α-β剪枝过程中，原则上仍然要先由某个端节点的估值开始，一方面自下而上地进行节点的估值计算，边搜索，边生成必要的博弈树节点；另一方面根据搜索中发现并得到的α值和β值，对不必要的节点及其后续的博弈树实施剪枝。

　。

　四、 四、机器学习 机器学习 在学习智能体中，对执行元件进行反馈并加以修正的元件是学习元件 学习元件 影响学习元件设计的主要因素：执行元件的哪个组成部分进行学习—谁要学习(who)组成部分从学习中得到什么反馈—怎么学习(how)组成部分是如何表示的—学习什么(what)决定智能体学习本质的最重要因素是学习中的反馈类型 学习的三种类型 学习的三种类型 1 有监督(有指导)学习—从其输入/输出的实例中学习一个函数 2 无监督(无指导)学习—在未提供明确的输出值情况下，学习输入的模式主要在概率推理系统的上下文中研究无监督学习 3 强化学习—从强化物中学习，而不是根据指导进行学习 如果一个计算机程序要完成某类任务 T，其完成任务的性能可以用 P 衡量，该程序根据经验 E 改进 P，则称该程序针对任务 T以性能 P 衡量从经验 E 中学习 学习 奥卡姆剃刀原则 奥卡姆剃刀原则—优先选择与数据一致的最简单假设 归纳 归纳学习 学习也可以称作归纳推理或简称归纳，其任务是：给定函数 f(未知)的实例集合，返回一个近似于 f 的函数 h—h 称为假设，所有 h 的集合称为假设空间归纳学习假设 归纳学习假设—任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数归纳偏置 归纳偏置—归纳学习需要某种形式的预先假定 决策树 决策树以事物的属性描述集合作为输入，输出通常是一个分类(离散的输出)—一般是二值分类(真或假) 决策树适合具有以下特征的学习 决策树适合具有以下特征的学习：1 实例是由“属性-值”对表示的—固定的属性+离散或连续的取值 2 目标函数具有离散的输出值 3 析取表达式 4 训练数据可以包含错误—决策树学习的鲁棒性好 5 训练数据可以包含缺少属性值的实例 决策树学习包括 决策树学习包括 2 个步骤 个步骤：1 从实例中归纳出决策树(建立决策树)2 利用决策树对新实例进行分类判断 如何建立决策树：

　如何建立决策树：如果存在一些正例和反例，选择划分它们的最佳属性如果剩下的都是正例或者反例，则分类已经完成，回答Yes 或 No 如果没有剩下实例，则返回一个缺省值如果没有剩下的属性但还有剩下的实例，则数据中含有噪声决策树算法 决策树算法(1) 如果 C 中全部实例为正例，则建立一个 YES 结点，并且停止。如果 C 中全部实例为反例，则建立一个 NO 结点，并且停止。否则选择一个属性 A, 根据它的值 v1, …, vn 建立决策树。

　(2) 根据值 V，将训练实例 C 划分为子集 C1, …, Cn。(3) 对每个集合Ci 递归地应用此算法。

　ID3 是一种自顶向下增长树的贪婪算法，在每个节点选取能最好的分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所有的属性都已被使用过。

　熵与不确定性信息 熵与不确定性信息论中用熵表示事物的不确定性，同时也是信息含量的表示—熵值越大，表示不确定性越大，同时信息量越多；反之则不确定性越小，信息量越小熵的单位 熵的单位=比特 比特 熵和决策树 熵和决策树 1 开始，决策树的树根对应于最大的不确定状态，表示在分类之前对被分类的对象一无所知 2 随着每个属性的不断判断，向树的叶子方向前进，即相当于选择了其中的一棵子树，其不确定状态就减小了 3 到达叶子节点，分类完成，此时不确定性为零要提高决策树的分类效率，就相当于要求熵值下降的更快 / 这样，ID3 算法的实质就是构造一棵熵值下降平均最快的决策树 分类的熵 分类的熵 1 算法的评价预先估计预测的质量 算法的评价预先估计预测的质量— —计算学习理论，回答为什么学习是可行的 计算学习理论，回答为什么学习是可行的(本课程只能提供一个简要说明 本课程只能提供一个简要说明)2 事后 事后考察预测的质量 考察预测的质量— —实验验证 实验验证(训练集 训练集/测试集 测试集) 测试方法对方法的性能的评估：

　测试方法对方法的性能的评估：(1)选取一个大的实例集合(规模常常意味着代价，一般对于统计方法来说越大越好)(2)将其分为不相交的两个子集—训练集和测试集(3)将学习算法应用于训练集，产生假设 h(4)测量测试集中用 h 分类正确的实例的百分比(开放测试)(5)对不同规模的实例集合以及每种规模的随机选择训练集重复进行(2)至(4)由此而得到相应的测试曲线 过拟合 过拟合：给定假设空间 H 和一个假设 如果存在其他假设 使得在训练样例上 h 的错误率比 h’小，但在整个实例分布上 h’错误率比 h 小，则称 h 过拟合训练样例 过拟合问题的解决解决方法：

　过拟合问题的解决解决方法：决策树剪枝— 剪枝 / 防止用不相关的属性来划分决策树 交叉验证—适用于任何学习算法 / 预留部分已知数据(将训练集中的一小部分留出来做测试集用)，利用其测试其余已知数据归纳出来的假设的性能 / k-交叉检验(每次预留 1/k 数据) 可能近似正确学习模型 可能近似正确学习模型 决策表学习的贪婪算法思想 决策表学习的贪婪算法思想：1 重复寻找一个与训练集的某个子集完全一致的测试 2 一旦找到这样的测试，就将其加入到决策表中，并删除相应的实例 3 然后用剩余实例构造决策表其他部分 4 重复上述过程直到没有剩余实例 集体学习 集体学习是从假设空间中选择一个作为整体的假设集合称为集体，将它们对新实例的分类预测进行合成，然后再输出结果 错误假设与实例的一致概率 错误假设与实例的一致概率设 hbHbad，其与前 N 个实例一致的概率可以如下计算：已知 error(hb)>，则该假设与一个给定实例一致的概率至多为 1- 所以 P(hb 与 N 个实例一致≤(1-)N

　 Hbad 中至少包含一个与 N 个实例一致的假设的概率为 P(Hbad)≤|Hbad|(1-)N≤|H|(1-)N 当然希望这个概率越小越好，即 |H|(1-)N≤ 实例数量的下限 实例数量的下限下面推导满足学习算法以较小误差和较大概率取得与实例相一致(即正确预测)的实例数量 N 由 |H|(1-)N≤ 得 ln|H|+Nln(1-)≤ln 此即 Nln(1- ≤ -ln|H| 由一个通用不等式(1-)≤e- ([0,1])令 Nln(1-)≤Nlne-≤ln-ln|H|此即-N≤ln-ln|H| AdaBoost 总结 总结 Adaboost 算法中不同的训练集是通过调整每个样本对应的权重来实现的。开始时，每个样本对应的权重是相同的，即 其中 n 为样本个数，在此样本分布下训练出一弱分类器 。对于分类错误的样本，加大其对应的权重；而对于分类正确的样本，降低其权重这样分错的样本就被突出出来，从而得到一个新的样本分布。在新的样本分布下，再次对分类器进行训练，得到弱分类器。依次类推，经过 T 次循环，得到 T 个弱分类器把这 T 个弱分类器按一定的权重叠加（boost）起来，得到最终想要的强分类器。

　。

　五、 五、逻辑、推理与知识 逻辑、推理与知识 逻辑 逻辑就是人们用以处理问题而抽象的一种思维规则或计算方法。

　把 GIANT(x)称为谓词 谓词，其中 GIANT ( )是谓词名；括号中的参量 x 叫做谓词的变元，又称之为项(item)。谓词中包含个体或变元的数目，称为谓词的元或谓词的目。

　谓词表达形式中所包容相叠加的含义层次数数目，称为谓词的阶。

　在谓词逻辑演算中，最重要的有三大类：

　即：命题逻辑演算、 一阶谓词逻辑演算和二阶谓词演算。

　Horn 子句 子句一个子句由两部分组成：头部和体。IF-THEN 规则的结论称为头部，前提部分称为体。

　Horn 子句是头部最多包含一个文字（命题或谓词）的子句。

　Horn 子句在 Prolog 中有三种表示形式：

　（1）

　无条件子句（事实）

　：A. （2）

　条件子句(规则)：A:-B1,…,Bn. （3）

　目标子句(问题)：?- B1,…,Bn.

　上述三种 Horn 子句均具有明显的非形式语义：

　（1）

　无条件子句 A：表示对变量的任何赋值，A 均为真。

　（2）

　条件子句 A:-B1,…,Bn：表示对变量的任何赋值，如果 B1,…,Bn 均为真，则 A 为真。

　（3）

　目标子句?- B1,…,Bn：其逻辑形式为 ∀x1…xn(¬B1∨…∨¬Bn)， 等价于¬∃x1…xn(B1∧…∧Bn)。它视作推理的目标。

　逻辑程序 逻辑程序就是由 Horn 子句构成的程序。在逻辑程序中，头部具有相同谓词符的那些子句称为该谓词的定义。

　单调逻辑 单调逻辑的推理规则是单调的。设 Γ表示推理规则集，则单调逻辑的语言 Th(Γ) = {A | Γ→ A}具有如下单调性：

　(1)

　Γ ∈ Th(Γ)

　(2)

　如果 Γ1 ⊆Γ2，则 Th(Γ1) ⊆ Th(Γ2) (3)

　Th(Th(Γ)) = Th(Γ)

　(幂等性) 其中 (3)又称为不动点 (fixed

　point)。单调推理规则的显著特性之一就是它的语言是封闭的最小不动点，亦即 Th(Γ1) = ∩{s |Γ1 → S 且 Th(S) = Γ2}。

　非单调推理 非单调推理推理系统的定理集合并不随推理过程的进行而单调地增大，新推出的定理很可能会否定、改变原来的一些定理，使得原来能够解释的某些现象变得不能解释了。非单调逻辑是处理不完全知识的工具。

　非单调推理三个主要流派 三个主要流派：McCarthy 提出的限制理论：当且仅当没有事实证明 S 在更大的范围成立时，S 只在指定的范围成立；Reiter 的缺省逻辑：

　“S 在缺省的条件下成立”是指 “当且仅当没有事实证明 S 不成立时 S 是成立的” ；Moore 的自认知逻辑：

　“如果我知道 S，并且我不知道有其他任何事实与 S 矛盾，则 S 是成立的”

　非单调逻辑：

　非单调逻辑：对逻辑进行扩展，将非单调推理形式化。

　。

　语言方面的扩充是指增强其表达能力；语义方面的扩充是指对真值的真假两种情况进行修正；一是对推理模式的扩展，这涉及非单调推理的过程化方面，称为非单调系统 非单调系统。

　非单调逻辑大致分为两类 非单调逻辑大致分为两类：一类基于最小化语义，称为最小化非单调逻辑；另一类基于定点定义，称为定点非单调逻辑。1 最小化非单调逻辑可以分为基于最小化模型和基于最小化知识模型 2 定点非单调逻辑可以分为缺省逻辑和自认知逻辑 封闭世 封闭世 界假设 界假设是一种对由一组基本信念集合 KB 定义的理论 T(KB)进行完备化的方法。一个理论 T(KB)是完备的，是说其包含（显式或隐含）了每一个基原子公式或该公式否定。

　基本思想是：如果无法证明 P，则就认为它是否定的。即：

　如果从知识库中无法证明 P 或者¬P，则就向 KB 中增加¬P。作 作用 用：是完备化数据库系统 CWA 对理论的完备化是仅仅通过向基本信念集合 KB 中增加基原子公式的取反来实现的。

　情景演算 情景演算是分析处理和研究涉及动作和进化问题的最常用的形式工具。

　多类逻辑（ 多类逻辑（ LR）：

　）：建立在对情景演算的直观理解的意义上，把情景演算的概念和方法在这种特殊的多类一阶逻辑的框架之内进行描述，以便为有关的研究提供一个坚实的系统的理论基础。把情景演算集成在一个多类逻辑框架里，这一做法的核心是：为了刻划一个动作，只需要描述动作发生的条件和动作发生以后对其环境所产生的效果这两件事。

　LR 被定义成一种多类逻辑，在其形式语言 被定义成一种多类逻辑，在其形式语言 ℒ ℒ 中引入了三种关于个体的类型，即状态类型 中引入了三种关于个体的类型，即状态类型 s、对象类型 、对象类型 o 和动作类型 和动作类型 a 一个类型为 s 的常量符号 S0 （表示起始状态）；一个类型为<a,s；s>的二元函数符号 do （描述一个动作的发生使得状态从一个变成另外一个）；一个类型为<a,s>的二元关系符号 Poss（表示一个动作在一个状态之下是可能发生的）；一个类型为<s,s>的二

　元关系符号<（表示状态之间的先后关系）

　。

　动态描述逻辑 动态描述逻辑 DDL 描述逻辑 描述逻辑是一种基于对象的知识表示的形式化，也叫概念表示语言或术语逻辑。它是一阶逻辑的一个可判定的子集，具有合适定义的语义，并且具有很强的表达能力。一个描述逻辑系统包含四个基本组成部分：表示概念和关系的构造集；TBox 包含断言；ABox 实例断言；TBox 和 ABox 上的推理机制。

　一个描述逻辑系统的表示能力和推理能力取决于对以上几个要素的选择以及不同的假设。

　描述逻辑中有两个基本元素：概念 概念解释为一个领域的子集关系 关系则表示在领域中个体之间所具有的相互关系，是在领域集合上的一种二元关系。动态描述逻辑 动态描述逻辑是在传统描述逻辑的基础上扩充得到的。

　约束推理 约束推理约束通常是指一个包含若干变量的关系表达式，用以表示这些变量所必须满足的条件。

　约束满足问题(Constraint Satisfaction Problem, 简称 CSP) 一组变量与一组变量间的约束。一般而言，变量表示领域参数，每个变量都有一个固定的值域。一个变量的值域可能是有限的，例如一个布尔变量的值域包含两个值；也可能是离散无限的，如整数域；也可能是连续的，如实数域。约束可用于描述领域对象的性质、相互关系、任务要求、目标等。约束满足问题的目标就是找到所有变量的一个（或多个）赋值，使所有约束都得到满足。约束满足问题在一般情形下是一个 NP 问题，所以必须使用各种策略与启发式信息。约束表示易于理解、编码及有效实现，它具有以下优点:

　(1) 约束表示允许以说明性的方式来表达领域知识，表达能力较强，应用程序只需指定问题的目标条件及数据间的相互关系。因而具有逻辑表示的类似性质。

　(2) 约束表示允许变量的域包含任意多个值，而不像命题只取真假二值。所以它保存了问题的一些结构信息，如变量域的大小、变量间的相关性等，从而为问题求解提供启发式信息。

　 (3) 易于并行实现。因为约束网络上的信息传播可以认为是同时的。

　(4) 适合于递增型系统。约束可以递增式地加入到约束网络。

　(5) 易于与领域相关的问题求解模型相衔接。各种数学规划技术，方程求解技术等, 都可以自然地嵌入约束系统。

　约束推理分为以下几种：

　约束推理分为以下几种：

　(1)

　关系推理：

　推理过程中推出的新的约束关系, 并将其加到约束网络中。

　(2) 标记推理：每个节点标注以可能值的集合，在传播过程中约束用于限制这些集合。

　(3) 值推理：节点标记以常量值。约束用已标记节点的值求出标记节点的值。

　(4) 表达式推理：是值推理的推广，其中节点可能标以关于其它节点的表达式。当一个节点标记以不同的表达式时, 应使其等同起来, 并求解结果方程。

　定性推理 定性推理是从物理系统、生命系统的结构描述出发,导出行为描述, 以便预测系统的行为并给出原因解释。定性推理采用系统部件间的局部结构规则来解释系统行为, 即部件状态的变化行为只与直接相邻的部件有关。定性推理方法 定性推理方法：1 定性模型方法 定性模型方法 2 定 定性进程方法 性进程方法 3 定性仿真法 定性仿真法 定性推理一般采用下列分析步骤：

　定性推理一般采用下列分析步骤：

　(1) 结构认识：将对象系统分解成部件的组合。

　(2) 因果分析：当输入值变化时，分析对象系统中怎样传播。

　(3) 行为推理：输入值随着时间变化，分析对象系统的内部状态怎样变化。

　(4) 功能说明：行为推理的结果表明对象系统的行为，由此可以说明对象系统的功能。

　基于范例的推理 基于范例的推理把当前所面临的问题或情况称为目标范例，而把记忆的问题或情况称为源范例。基于范例推理就是由目标范例的提示而获得记忆中的源范例，并由源范例来指导目标范例求解的一种策略。范例：

　范例：

　范例是一段带有上下文信息的知识，该知识表达了推理机在达到其目标的过程中能起关键作用的经验 基于范例推理有两种形式：

　基于范例推理有两种形式：问题求解型：利用范例以给出问题的解答解释型：把范例用作辩护的证据 知识的分类知识按问题 知识的分类知识按问题求解要求分为：

　求解要求分为：

　叙述型知识、过程型知识、控制型知识。

　叙述型知识、过程型知识、控制型知识。

　知识按其作用分为：描述性知识、判断性知识、过程性知识。

　知识按其作用分为：描述性知识、判断性知识、过程性知识。

　知识按其描述对象分为：对象级知识、元知识 知识按其描述对象分为：对象级知识、元知识 六 六、 、计算智能 计算智能 一般地，为研究某事物的规律性，总是先给定义目标集，它表达了问题的总范围，称为论域, 一般记为 U。下面在论域 U 上定义模糊集 定义 1.2.1

　设 A 是论域 U 到[0，1]的一个映射，即 A：U→[0，1]

　称 A 是 U 上的模糊集 模糊集，而函数 A （• ）称为模糊集 A 的隶属函数，A （x)称为 x 对模糊集 A 的隶属度 隶属度。

　 神经元也就分为阈值型、S 型和分段线性型三类.

　如果将多个神经元按某种的拓扑结构连接起来，就构成了神经网络。

　根据连接的拓扑结构不同，神经网络 神经网络可分为四大类：分层前向网络、反馈前向网络、互连前向网络、广泛互连网络。

　 进化计算 进化计算 建立在进化理论基础上的计算，它是仿照生物生命发展过程而建立起来的计算理论。进化计算研究内容：包括遗传算法；进化策略；进化规划和进化编程共四方面的内容。

　遗传算法原理：遗传算法基于达尔文进化论的观点，依照适者生存，优胜劣汰等自然进化法则，通过计算机来模拟生命进化的机制，进行智能优化计算和问题搜索求解。

　 GA 功能：在解决许多传统数学难题以及常规条件下明显失效的复杂问题时，遗传算法提供了一个行之有效的新途径。

　 遗传算法目的：一方面是通过它的研究来进一步解释自然界的适应过程；另一方面是为了将自然生物系统的重要机理运用到人工系统的设计中。

　 遗传算法实现：本质上，所谓遗传算法，就是一个通过基因因子选择、重组、复制、评价计算，从而再循环繁殖、继承而不断地进化以接近于最佳种群的过程。换言之，这是一个自适应地逐渐找到最优解的组织实现过程。

　实现 GA 过程:主要包括编码;确定种群;遗传操作;优胜劣汰等运算过程. ① 编码：把每一可能解,编码为向量,表示为二或十进制数字字符串,称其为染色体(chromosome)或个体,而把向量中的每个元素,称之为基因(genes); ② 确定种群：把所有的染色体组成集群(population)，按预定的目标函数，对每个染色体进行评鉴、计算其适应度值;

　根据其适应度值比较，对诸染色体进行遗传操作：

　③ 选择复制；

　④ 交换；

　⑤ 变异；

　⑥ 在进行遗传操作中，不断剔除适应度低的那些性能不佳的染色体，留下适应度高的并且性能优良的染色体，于是，就得到了性能较优的新种群。如此这样反复迭代，优胜劣汰，就使得该集群一代又一代向着更优群体的方向进化。

　算法过程:开始随机地产生一些染色体，称之为侯选解，组合为初始种群；随后对这些染色体进行向量编码，得到种群 P(t)；再对种群 P(t)进行适应度计算。选择适应度值大的染色体进行复制;再通过交换、变异等遗传操作,剔除适应度低的即性能不佳的染色体,留下适应度高的即性能优良的染色体，就得到了新种群 P(t+1)。由于新种群 P(t+1)成员是从上一代种群中挑选而得到适应度高的优秀者,它继承了上一代优良特性,总体性能将明显优于上一代。如此反复迭代,优胜劣汰,就使得该集群一代又一代向着更优群体的方向进化，直至集群品质达到某种预定的优化指标，即得到了问题的最优解。

　遗传算法知识表示和采用编码方式的几条指导原则：

　① 所选知识表达方式应以能自然地表示欲求解问题为原则；

　② 所选编码方式应尽可能使确定位数少、定义长度短的图式,并且与所求解的问题相关；

　③ 所选编码方式应具有最小的字符集。

　适应度函数的选择的原则是：

　① 应根据实际问题的具体特性来确定，一般要求适应度函数值是非负的；

　② 要求把待优化问题表达为最大化问题，即目标函数的优化方向对应于适应度函数的增大方向。

　高级遗传算法（1）精英保护法:为了保护每代种群中最优秀的个体，可以把种群中最优秀的个体挑选出来，直接复制到下一代中去，故这种方法又称为精英选择法。（2）自适应变异概率选择法:在进行交叉操作之前,首先以海明(Hamming)距离测定双亲基因码的差异,再根据测定值决定后代的变异概率 Pm. （3）移民算法:引入一定比例的外来个体，用以替换上一代中那些低适应度的个体。（4）分布式遗传算法:可将大的种群按基因图式结构分为若干小种群(又称子群), 由于它们各自遗传过程具有相对的独立性和封闭性,进化的方向也会略有差异.这样,在保证搜索充分性的同时,使收敛的结果趋于全局最优。（5）其它改进的选择算法:概率式确定选择法；部分个体的替换选择法；按排序函数的选择法等。

　进化策略:实质上是指进化计算的优化算法，即模仿自然进化原理，设法找到一种最优求解参数问题的方法 进化规划：为求解预测问题而提出的一种有限状态基进化模型。依此进化模型，机器的状态基的变异由均匀随机分布规律确定 遗传算法、进化策略、进化规划的比较：这三种算法又是从不完全相同的角度出发来模拟生物的进化过程的，分别是依据不同的生物进化背景、不同的生物进化机制而提出来的，所以三者之间也有一些差异。下表中总结、比较了这几种进化算法的主要特点。

　比较项目遗传算法（GA）进化策略（ES）进化规划（EP）

　个体表现形式离散值连续值连续值 参数调整方法无标准偏差、协方差方差 适应度评价方法变换目标函数值直接使用目标函数值变换目标函数值 个体变异算子辅助搜索方法主要搜索方法唯一搜索方法 个体重组算子主要搜索方法辅助搜索方法不使用 选择复制算子概率、保存确切的、不保存概率、不保存 复杂适应系统 主体的适应性, 是指它能够与环境以及其它主体进行交流，在交流的过程中 “学习” 或 “积累经验”，并且根据学到的经验改变自身的结构和行为方式。CAS 具有四个基本特点:

　 （1）首先, 主体是主动的、活的实体。（2）其次, 个体与环境(包括个体之间)之间的相互影响、相互作用是系统演变和进化的主要动力。（3）再次, 这种方法不像许多其他的方法那样, 把宏观和微观截然分开, 而是把它们有机地联系起来。（4）最后, 这种建模方法还引进了随机因素的作用, 使它具有更强的描述和表达能力。

　 人工生命(Artificial Life, AL)是用来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容: ① 如何利用计算技术研究生物现象② 如何利用生物技术研究计算问题。

　群智能定义：

　群智能定义：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。

　构建一个 SI 系统所应满足的五条基本原则:1． Proximity Principle: 群内个体具有能执行简单的时间或空间上的评估和计算的能力。2.Quality Principle: 群内个体能对环境(包括群内其它个体)的关键性因素的变化做出响应。3.Principle of Diver...