西工大计算智能知识点整理（完整版）.doc

《西工大计算智能知识点整理（完整版）.doc》由会员分享，可在线阅读，更多相关《西工大计算智能知识点整理（完整版）.doc（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章 绪 论1. 图灵测试一组人类裁判以敲击键盘的形式与电脑“对话”。如果裁判认定电脑为人的比例超过30%，则电脑通过测试。2. 人类智能活动的能力是人类在认识世界和改造世界的活动中，由脑力劳动表现出来的能力。 认识和理解世界环境的能力 提出概念、建立方法、进行演绎和归纳推理、做出决策的能力 学习取得经验、积累知识的能力 自我适应的能力 联想、推理、判断、决策的能力 3. 智能的本质感知能力、记忆和思维能力、学习能力、自适应能力、行为能力4. 思维种类逻辑思维、形象思维、顿悟思维5. 人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑所从事的推理、学习、思考、规划等思维活动关于知

2、识的科学执行拟人的任务6. 没有计算机的出现，人工智能就无法得到应用7. 人类智能与人工智能本质区别: 物质载体、逻辑模拟、活动规律、目的性、能动性、适应性8. 研究方法符号主义、联结主义、行为主义9. 计算智能是人工智能的深化与发展人工智能是以知识库为基础、那么计算智能则是以模型为基础、以分步、并行、仿生计算为特征含数据、算法和实现的信息系统。前者强调规则的形式和表示，后者强调模型的建立和构成；前者依赖专家知识，后者强调系统的自组织、自学习和自适应。10. 计算智能的主要方法有人工神经网络、遗传算法、遗传程序、演化程序、局部搜索、模拟退火等等11. 计算智能的特征与应用智能性：包括算法的自适

3、应性，自组织性，算法不依赖于问题本身的特点，具有通用性并行性：算法基本上是群体协作的方式对问题进行优化求解，非常适合大规模并行处理鲁棒性: 算法具有很好的容错性，同时对初始条件不敏感，能在不同条件下寻找最优解12. 计算智能发展趋势分布式人工智能、Internet及数据库的挖掘、智能系统之间的交互与通信、智能系统之间的合作等13.第二章 知识表示一. 知识的基本概念1. 相关概念：数据：指为描述具体事物引入的数字、符号等信息：指不同数据组成的一种结构（如 “建国50岁”）数据与信息的关系：数据是信息的载体和表示，信息是数据的语义知识：对信息进行智能性加工后形成的对客观世界的规律性认识*。知识的

4、一般概念人类认识与经验的总和人们对客观事物的认识及解决问题的方法和策略以高度概括形式对客观事实及相互关系的整合知识的三个代表性定义：经过消减、塑造、选择和转换的信息；由特定领域的描述、关系和过程组成；知识=事实+信念+启发式。2. 人类对客观世界感知四个层面：4 智能（Intelligence）3 知识（Knowledge）2 信息（Information）1 数据（Data）3. 知识的特性相对正确性、可表示性、不确定性、关联性4. 知识的分类常识性知识、领域性知识（作用范围）确定性知识、不确定性知识（确定性）逻辑性知识、形象性知识（结构及表现形式）5. 知识的表示方法对知识的表示过程就是将

5、知识编码成某种数据结构的过程v 一阶谓词逻辑表示法（First Order Predicate）v 产生式表示法（Production）v 框架表示法（Framework）v 语义网络法（Semantic Network）v 脚本表示法（Script）6. 如何选择合适的表示方法？v 选择知识表示要根据所处理的具体领域和实际情况荀泽相应的知识表示方法 充分表示领域知识 有利于对知识的利用 便于理解和实现 便于对知识的组织、管理与维护7. 智能活动过程的模拟 知识表示 知识利用 知识获取二谓词逻辑表示1. 命题逻辑命题 是能够判断真或假的陈述句 通常用大写字母来表示，如A, B, P, Q等 命

6、题的真假值一般用 T 或 F 来表示 表示单一意义的命题，称之为 原子命题。原子命题通过 “连接词” 构成 复合命题。2. 连接词v “ ”表示“非” 复合命题 P为真，当且仅当P为假。v “ ”表示 “与（合取）”复合命题“PQ”为真，当且仅当P和Q都为真。v “”表示“或（析取）” 复合命题“PQ”为真，当且仅当P、Q两者之一为真。v “= （ ）”表示“蕴含” 复合命题“PQ”为假，当且仅当P为真且Q为假。 与自然语言不一样，蕴涵式的前件和后件可以没有内在联系 v “” 表示 “等价” 复合命题“PQ”为真，当且仅当P、Q同时为真、或者同时为假。 与自然语言不一样，等价式的2个命题可以没

7、有内在联系v 等价式具有下列性质：v 自反性：对于任意公式A，有A Av 对称性：对于任意公式A和B，若A B，则B A传递性：对于任意公式A，B和C，若A B，B C，则A C 3. 命题定律 双否律（ P） P 德摩根律（ P Q ） P Q （ P Q ） P Q 交换律 P Q Q P P Q Q P 结合律 P (Q R) ( P Q ) R P (Q R ) (P Q ) R 分配率 P (Q R ) (P Q ) (P R ) P (Q R ) (P Q ) (P R ) 等幂律P P PP P P 同一律P T * P P F * P 零律P F* F* P T * T * 互

8、补率P P F* P P T* 吸收率 P (Q R ) P P (Q R ) P4. 设A和B是两个公式，若A B为永真式，则称A蕴含B，记作A =B5. 主要的推理式假言推理PP Q- P (P Q) = QQ假言三段论或演绎P QQ R- (P Q) (Q R) = (P R)P R拒取式P QQ- (P Q) (Q) = (P)P简化式 PQ- (P Q) = P P析取三段论 P Q P- (P Q) ( P)= QQ二难推论 P R Q R- (P R) (Q R) = (P Q) R(P Q) R6. 谓词逻辑表示法的特点v 自然性：符合人类对问题的直觉理解；v 精确性：只有“真

9、与假”的值；v 严密性：谓词逻辑具有严格的形式定义以及推理规则；利用推理规则及有关定理证明技术，可以从已知事实推出新的事实，或证明作出的假设。 v 易实现：用谓词逻辑表示的知识可以比较容易地转换为计算机内部形式，易于模块化，便于对知识的增加、修改、删除。用其表达的知识也易于计算机上实现。7. 谓词逻辑局限性v 不能揭示不确定的知识：只能表示精确性知识，不能表示不确定的知识，表示的知识范围受到了局限。v 易形成组合爆炸：在推理过程中，其推理根据事实数目的增大及盲目使用推理规则，可能形成组合爆炸。v 效率低：将推理与知识语义割裂，降低推理效率。三产生式表示法1.事实的表示 事实通常是用三元组成四元

10、组来表示。 对确定性知识，一个事实可用一个三元组(对象,属性,值)或(关系,对象1,对象2)来表示。对不确定性知识,一个事实可用一个四元组(对象,属性,值,可信度因素) 来表示。2. 规则的表示 规则描述的是事实间的因果关系，规则的产生式表示形式称为产生式规则。其基本形式为: P Q 或者: IF P THEN Q 其中,P是产生式的前提,也称前件,由事实的逻辑组合来构成, Q是产生式的结论或操作,也称后件. 产生式的含义是:如果前提P满足,则可推出结论Q或执行Q规定的操作。3. 产生式系统的基本结构控制系统规则库综合数据库4.优点 自然性：接近人类对因果关系知识的思维判断形式 模块性：与推理

11、机构相互独立，利于增加、删除、修改和扩充 有效性：可表示不确定性知识、启发性知识 一致性：规则具有固定表示形式缺点 效率较低 存在组合爆炸：匹配-冲突消解-执行；不能表示结构性知识四语义网络1. 语义网络是一个有向图，其中节点表示个体，而弧表示两个体间的二元关系，弧上标记关系模型名称，单一个体就由一结点表示。2. 语义关联 类属关系：是一种、是一员、是一个 聚类关系：是一部分 属性关系：有、能 推论关系：推论出 时间、位置关系：在前、在后、在上、在下、接近、相似等3. 语义网络主要特点：n 结构性 把事物的属性以及事物间的各种语义联系显式地表示出来，是一种结构化的知识表示方法。在这种方法中，下

12、层结点可以继承、新增、变异上层结点的属性。n 联想性 本来是作为人类联想记忆模型提出来的，它着重强调事物间的语义联系，体现了人类的联想思维过程。n 自然性 这种带有标识的有向图，可比较直观地把知识表示出来，符合人们表达事物间关系的习惯，并且与自然语言语义网络之间的转换也比较容易实现。n 复杂性 语义网络表示知识的手段是多种多样的，这虽然对其表示带来了灵活性，但同时也由于表示形式的不一致，使得它的处理增加了复杂性。 五框架表示法1. 框架：是一种描述对象（事物、事件或概念等）属性的数据结构，在框架理论中，框架是知识表示的基本单位。2. 一个框架由若干个“槽”（Slot）结构组成，每个槽又可分为若

13、干个“侧面”。 一个槽：用于描述所论对象某一方面的属性； 一个侧面：用于描述相应数学的一个方面。槽和侧面所具有的属性值分别称为槽值和侧面值。第三章 基本推理原理一推理的基本概念1. 推理：按某种策略由已知判断推出另一判断的思维过程已知判断：包括已掌握的与求解问题有关的知识及关于问题的已知事实推理的结论： 由已知判断推出新判断推理机：推理由程序程序实现，称为推理机2. 推理的基本任务：从一种判断推出另一种判断推理的分类： 演绎推理、 归纳推理、 默认推理3. 演绎推理推理过程：从已知的一般性知识推出组合在这些已知知识中适合于某种个别情况结论的过程三段论式演绎推理： 大前提：已知的一般性知识或假设

14、小前提：关于所研究的具体情况或个别事实的判断 结论：由大前提推出的适合于小前提所示情况的新判断 个别经验: 无意发现一种药治病一般性认识：经验累积结论： 得出结论：这种药可以治这种病4. 归纳推理 从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到一般的推理完全归纳推理：在进行归纳时考察了相应事物的全部对象，并根据这些对象是否都具有某种属性，从而推出这个事物是否具有这个属性不完全归纳推理：只考察了相应事物的部分对象就得出了结论5. 默认推理又称缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理按所用知识的确定性分类：确定性推理、不确定性推理按推理过程的单调性分类：单调推

15、理、非单调推理二自然演绎推理 从一组已知的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程三归结反演推理应用归结原理证明定理的过程称为归结反演。1. 谓词公式转换成相应子句集的步骤（1）利用等价谓词关系消去谓词公式中的“”和“”（2）减少否定符号的辖域，将每个否定符号移到仅靠谓词的位置，使得每个否定符号最多作用于一个谓词。双重否定律德摩根律 量词转换律（3）对变元标准化。 在一个量词的辖域内，将谓词公式中受该量词约束的变元全部用另一个没有出现过的任意变元代替，使不同量词约束的变元有不同的名字。（4）消去存在量词若存在量词不出现在全称量词的辖域内（即左边没有全称量词），只用一个新的

16、个体常量（称为Skolem常量）替换受该存在量词约束的变元，即可消除该存在量词。若存在量词位于一个或多个全称量词的辖域内，则需要Skolem函数替换受该存在量词约束的变元，再消去该存在量词。量词消去原则：v 存在量词。将该量词约束的变量用任意常量（a，b等）或任意变量的函数（f(x)，g(y)等）代替。v 左边有任意量词的存在量词，消去时该变量改写成为任意量词的函数；如没有，改写成为常量。v 任意量词。简单地省略掉该量词。（5）化身前束范式 将所有量词都移到公式左边，并且不改变相对顺序。（6）化为Skolem标准型 其标准型一般形式为使用如下等价关系（7）消去全称量词由于母式中全部变元均受到全

17、称量词的约束，并且全称量词的次序已无关紧要，因此可省掉全称量词。（8）消去合取词在母式中消去所有合取词，将母式用子句集的形式表示出来，其中，子句集中的每一个元素都是一个子句。（9）更换变元名称对子句集中的某些变元重新命名，使得任意两个子句中不出现相同的变元名。（10）定理：设有谓词公式F，其标准形的子句集为S，则F不可满足的充要条件是S不可满足。要证明一个谓词公式是不可满足的，只要证明其相应的标准子句集是不可满足的2. 鲁宾逊归结原理 检查子句集S中是否包含空子句，若包含，则S不可满足；若不包含，就在子句集中选择合适的子句进行归结，一旦通过归结能推出空子句集，就说明子句集S是不可满足的。（1）

18、、命题逻辑中的归结原理（2）、谓词逻辑中的归结3. 使用归结原理证明问题4. 不确定推理建立在不确定性知识和证据基础上的推理。引起不确定性的因素：知识的不完备、不精确；原因的多样性；知识描述的模糊性；不一致性；随机性；解决问题的方案不唯一；第四章 搜索原理求解：推理和搜索。一搜索原理概述1.概念：依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。2. 搜索策略的任务确定如何选取规则的方式3. 搜索的分类盲目搜索：无信息引导的搜索策略启发式搜索：有信息引导的搜索4. 状态空间、搜索空间与解路径状态空间: 一个有向图，节点

19、可表示问题的各种状态（综合数据库），及节单之间的弧代表一些操作（产生式规则），可以把一种状态导向另一种状态。解路径: 在状态空间图中，从初始点到目标节点的一条路径称为解路径搜索空间：为找到解路径而搜索的空间称为搜索空间5. 搜索成本规则控制费用：即为决定选取可用规则而花费的费用规则应用费用：即使用规则所花费的费用6. 搜索结果 最优结果 次优结果 任意结果二、盲目搜索策略1. 一般图搜索算法v (1) 把初始节点S0放入Open表，并建立目前仅包含S0的图G；v (2) 检查Open表是否为空，若为空，则问题无解，失败推出；v (3) 把Open表的第一个节点取出放入Closed表，并记该节点

20、为节点n；v (4)考察节点n是否为目标节点。若是则得到了问题的解，成功退出；v (5) 扩展节点n，生成一组子节点。把这些子节点中不是节点n先辈的那部分子节点记入集合M，并把这些子节点作为节点n的子节点加入G中v (6) 针对M中子节点的不同情况，分别作如下处理：v 对那些没有在G中出现过的M成员设置一个指向其父节点（即节点n）的指针，并把它放入Open表。（新生成的）v 对那些原来已在G中出现过，但还没有被扩展的M成员，确定是否需要修改它指向父节点的指针。（原生成但未扩展的）v 对于那些先前已在G中出现过，并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。（原生成也扩展过的

21、）v (7) 按某种策略对Open表中的节点进行排序。(8) 转第(2)步。2. 深度优先搜索v 算法描述v (1) 把初始节点S0放入Open表中；v (2) 如果Open表为空，则问题无解 ，失败退出；v (3) 把Open表的第一个节点取出放入Closed表，并记该节点为n；v (4) 考察节点n是否为目标节点。若是，则得到问题的解，成功退出；v (5) 若节点n不可扩展，则转第(2)步； (6) 扩展节点n，将其子节点放入Open表的首部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。3. 有界深度优先搜索对深度优先搜索引入搜索深度的界限(设为dm)，当搜索深度达到了深度界限

22、，而尚未出现目标节点时，就换一个分支进行搜索。v 搜索算法：v (1)把初始节点S0放入Open表,置S0的深度d(S0)=0；v (2)如果Open表为空,则问题无解,退出；v (3)把Open表的第一个节点(记为节点n)取出,放入Closed表；v (4)考查节点n是否为目标节点.若是,则求得了问题的解,退出；v (5)如果节点n的深度d(节点n)=dm,则转第(2)步；v (6)若节点n不可扩展,则转第(2)步；v (7)扩展节点n,将其子节点放入Open表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步。4. 宽度优先搜索v 基本思想 ： 从初始节点S0开始逐层向下扩展，在

23、第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。Open表中的节点总是按进入的先后排序，先进入的节点排在前面，后进入的节点排在后面。v 搜索算法：v (1)把初始节点S0放入Open表中；v (2)如果Open表为空，则问题无解，失败退出；v (3)把Open表的第一个节点取出放入Closed表，并记该节点为n；v (4)考察节点n是否为目标节点。若是，则得到问题的解，成功退出；v (5)若节点n不可扩展，则转第(2)步；(6)扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。5. 深度优先搜索与宽度优先搜索唯一区别 宽度优先搜索是

24、将节点n的子节点放入Open表的尾部，而深度优先搜索是把节点n的子节点放入Open表的首部。仅此一点不同，就使得搜索的路径完全不一样。6. 等代价搜索v 代价图: 当搜索图中的节点之间的耗散不是单位耗散时，这样的图成为代价图。v 搜索算法:v (1)把起始节点S放到Open表中。如果此起始节点为一目标节点则求得一个解。否则令g(S)0。v (2)如果Open是个空表，则没有解而失败退出。v (3)从Open表中选择一个节点i，使其g(i)为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点i(要是有目标节点的话)，否则,就从中选一个作为节点。 把节点i从Open表移至扩展节点表Clo

25、sed中。v (4)如果节点i为目标节点，则求得一个解。v (5)扩展节点i。如果没有后继节点，则转向第(2)步。v (6)对于节点i的每个后继节点j，计算g(j)g(i)十c(i，j)，并把所有后继节点j放进Open表。提供回到节点i的指针。v (7)转向第(2)步。三 启发式搜索1.概念： 又称为有信息搜索，利用问题拥有的启发信息引导搜索，达到减少搜索范围，降低问题复杂度的目的。2. 三种基本启发式信息搜索策略：(1)节点选择：根据启发式信息决定要扩展的下一个节点（最有希望的节点）(2)操作选择：控制下层子节点产生，以避免盲目地同时生成所有可能的节点。(3)剪枝技术：在图搜索中对某些节点从

26、图中剪去。3. 评价函数 评价函数用来估计节点重要性的函数。评价函数f(n)被定义为从初始节点S0出发，约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。它的一般形式为： f(n)=g(n)+h(n)其中，g(n)是从初始节点S0到节点n的实际代价；h(n)是从节点n到目标节点Sg的最优路径的估计代价。 4. A算法A算法也被称为启发式搜索算法。可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为全局择优搜索算法和局部择优搜索算法。 全局择优： 从Open表的所有节点中选择一个评价函数值最小的一个进行扩展。 局部择优：仅从刚生成的子节点中选择一个评价函数值最小的一个进行扩展。

27、v 全局择优搜索A算法描述 (1)把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0)； (2)如果Open表为空，则问题无解 ，失败退出； (3)把Open表的第一个节点取出放入Closed表，并记该节点为n； (4)考察节点n是否为目标节点。若是，则找到了问题的解，成功退出； (5)若节点n不可扩展，则转第(2)步； (6)扩展节点n，生成其子节点ni(i=1, 2, )，计算每一个子节点的估价值f(ni)(i=1, 2, )，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入Open表中； (7)根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进

28、行排序； (8)转第(2)步。5. A*算法A*算法是对A算法的评价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法。第六章 神经网络一概述1.概念：人工神经网络（Artificial Neural Networks，简记作ANN），是反映人脑结构及功能的一种抽象数学模型，是由大量神经元节点互连而成的复杂网络，用以模拟人类进行知识的表示与存储以及利用知识进行推理的行为。简单地讲，它是一个数学模型，可以用电子线路来实现，也可以用计算机程序来模拟，是人工智能研究的一种方法。2. 人工神经网络力求从四个方面去模拟人脑的智能行为 物理结构 计算模拟 存储与操作 训练 3. 生物神

29、经元神经元结构包括四个部分： 胞体：神经细胞的本体，维持细胞生存功能 树突：接收来自其他神经元的信号（输入） 轴突：输出信号 突触：与另一个神经元相联系的特殊部位4. 一个神经元有两种状态：兴奋和抑制；5. 生物神经网络的六个基本特征： 1）神经元及其联接； 2）神经元之间的联接强度决定信号传递的强弱； 3）神经元之间的联接强度是可以随训练改变的； 4）信号可以是起刺激作用的，也可以是起抑制作用的； 5）一个神经元接受的信号的累积效果决定该神经元的状态； 6) 每个神经元可以有一个“阈值”6. MP 模型 是一种人工神经元的数学模型，它是由美国Mc Culloch和Pitts提出的最早神经元模

30、型之一。MP模型是大多数神经网络模型的基础。7. 神经元的输出y是对u的映射：8. 输出函数 线性函数 非线性斜面函数（Ramp Function） Sigmoid输出函数（S型函数）9. 联接模式 层（级）内联接 循环联接 层（级）间联接10. 人工神经网络典型结构v 人工神经网络连接的几种基本形式 前向网络(感知器) 从输出到输入有反馈的前向网络 用来存储某种模式序列 层内互连前向网络 限制层内同时动作的神经元；分类功能反馈型全互联网络 & 反馈型局部互联网络11. 神经网络学习v 神经网络基本学习算法分为： 有师学习（Supervised Learning ）有师学习算法主要有规则、BP

31、算法、LVQ算法等 无师学习（Unsupervised Learning） 强化学习（ Reinforcement Learning ）12. 神经网络的特点大规模并行处理与容错能力 信息的分布式存储与处理学习与自适应能力具有联想与记忆能力二人工神经网络1. 感知器v 感知器是一种早期的神经网络模型，由美国学者F. Rosenblatt 于1958年提出。2. 感知器模型v 单输出的感知器(M-P模型)v 多输出的感知器3. 感知器的学习是有师学习v 感知器的训练算法的基本原理来源于著名的Hebb学习律（1949年提出）基本思想：逐步地将样本集中的样本输入到网络中，根据输出结果和理想输出之间的

32、差别来调整网络中的权矩阵。4. Hebb学习规则Hebb学习规则调整wij的原则为：若第i个神经元ui和第j个神经元uj同时处于兴奋状态，则它们之间的连接wij应当加强5. BP网络和BP算法v BP：输入层、隐层、输出层v BP网络结构：多层感知器网络 输出函数：Sigmoid函数 6. 反向传播算法（BP算法）的思想：从后向前反向逐层传播输出层的误差，以间接计算隐层的误差。算法可以分为两个阶段： 前馈：从输入层经隐层逐层正向计算各单元的输出；学习：由输出误差逐层反向计算隐层各单元的误差，并用此误差修正前层的权值。7. BP算法的优缺点v 优点： 理论基础牢固 推导过程严谨 物理概念清晰 通

33、用性好 所以，它是目前用来训练多层前向网络（BP网络）较好的算法。v 缺点： BP算法的收敛速度一般来说比较慢； BP算法只能收敛于局部最优解，不能保证收敛于全局最优解；当隐层元的数量足够多时，网络对训练样本的识别率很高，但对测试样本的识别率有可能很差，即网络的推广能力有可能较差。第七章 进化计算进化计算是一类模拟生物进化过程求解问题的人工智能技术。是基于自然选择和自然遗传等生物进化机制的一种搜索算法。1. 基本遗传算法简单实例至下一代，适应度计算选择交叉变异，直至满足终止条件。2. 参数设置群体规模N、染色体长度L 、基因取值范围R 、交叉概率Pc、变异概率Pm、适应值评价、终止条件 第八章群体智能1. 粒子群优化算法v （Particle Swarm Optimization，PSO）是进化计算的一个分支，是一种模拟自然界的生物活动的随机搜索算法。v PSO模拟了自然界鸟群捕食和鱼群捕食的过程。通过群体中的协作寻找到问题的全局最优解。v 它是1995年由美国学者Eberhart和Kennedy提出的，现在已经广泛应用于各种工程领域的优化问题之中。