人工智能导论学习笔记
老师提到要考的知识点和课后习题
知识点
第一章 基本概念
人工智能
它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。
或者
一门研究如何构造智能机器（智能计算机）或智能系统，使它能模拟、延伸、扩展人类智能的学科。
智能的特征
- 具有感知能力
- 具有记忆能力与思维能力
- 具有学习能力
- 具有行为能力
人工智能研究的基本内容
- 知识表示：将人类知识形式化或者模型化。
- 机器感知：使机器（计算机）具有类似于人的感知能力。以机器视觉(machine vision)与机器听觉为主。
- 机器思维：对通过感知得来的外部信息及机器内部的各种工作信息进行有目的的处理。
- 机器学习：研究如何使计算机具有类似于人的学习能力，使它能通过学习自动地获取知识。
- 机器行为：计算机的表达能力，即“说”、“写”、“画”等能力。
人工智能三大学派
- 符号主义(symbolicism)，又称为逻辑主义(logicism)、心理学派(psychologism)或计算机学派(computerism)，其原理主要为物理符号系统(即符号操作系统)假设和有限合理性原理。
- 连接主义(connectionism)，又称为仿生学派(bionicsism)或生理学派(physiologism)，其主要原理为神经网络及神经网络间的连接机制与学习算法。
- 行为主义(actionism)，又称为进化主义(evolutionism)或控制论学派(cyberneticsism)，其原理为控制论及感知-动作型控制系统。
知识表示
将人类知识形式化或者模型化。表示方法：符号表示法、连接机制表示法。
人工智能目标
用机器实现人类的部分智能。近期：实现机器智能，远期：制造智能机器。
第二章 知识表示
知识
把相关信息关联在一起所形成的信息结构。
在长期的生活及社会实践中、在科学研究及实验中积累起来的对客观世界的认识与经验。
知识的特性
- 相对正确性
- 不确定性，包括：由随机性引起的不确定性、由模糊性引起的不确定性、由经验引起的不确定性、由不完全性引起的不确定性
- 可表示性与可利用性
知识的表示
知识表示就是将人类知识形式化或者模型化。
命题
命题是一个非真即假的陈述句。一个命题能同时即为真又为假，但可以在一种条件下为真，在另一种条件下为假。
谓词
用来描述或判断客体性质、特征或客体之间关系的词项。用于刻画个体的性质、状态或个体间的关系的概念。
一阶谓词
在谓词P (x1, x2,…, xn)中，若xi都是个体常量、变元或函数，称它为一阶谓词，即个体都是常量、变元或函数的谓词是一阶谓词。
特点：优点：自然性、精确性、严密性、容易实现；局限性：不能表示不确定的知识、组合爆炸、效率低
产生式
一个产生式系统由规则库、控制系统（推理机）、综合数据库三部分组成。
产生式通常用于表示事实、规则以及它们的不确定性度量，适合于表示事实性知识和规则性知识。
形式：确定性规则知识P→Q、不确定性规则知识P→Q(置信度)、确定性事实性知识：（对象，属性，值）、不确定性事实性知识：（对象，属性，值，置信度）
产生式表示法的特点
优点：自然性、模块性、有效性、清晰性
缺点：效率不高、不能表达具有结构性的知识
框架
一种描述所论对象（一个事物、事件或概念）属性的数据结构。
特点：结构性、继承性、自然性
第三章 确定性推理方法
推理
从已知事实出发，按某种策略不断运用知识库中的已知知识，逐步推出结论的过程。
方式：演绎推理（一般→个别）、归纳推理（个别→一般）、默认推理（缺省推理）
推理方向：正向推理、逆向推理、混合推理、双向推理
冲突消解
按一定的策略从匹配成功的多个知识中挑出一个知识用于当前的推理过程。
自然演绎推理
从一组已知为真的事实出发，运用经典逻辑的推理规则推出结论的过程。
谓词公式化为子句集步骤
- 消去谓词公式中的→和←→符号
- 把否定符号 ¬ 移到紧靠谓词的位置上
- 变量标准化（每个辖域变量不同）
- 消去存在量词(常量、函数)
- 化为前束形（量词提前）
- 化为Skolem标准形（合取式）
- 略去全称量词
- 消去合取词，母式用子句集表示
- 子句变量标准化，即使每个子句的变量符号不同
鲁宾逊归结原理
消解原理，又称不可满足性原理
基本思想：检查子句集S中是否包含空子句，若包含，则S不可满足。若不包含，在S中选择合适的子句进行归结，一旦归结出空子句，就说明S是不可满足的。
第四章 不确定性推理方法
推理
从已知事实（证据）出发，通过运用相关知识逐步推出结论或者证明某个假设成立或不成立的思维过程。
不确定性推理
从不确定性的初始证据出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性但却是合理或者近乎合理的结论的思维过程。
知识的不确定性表示
在专家系统中知识的不确定性一般是由领域专家给出的，通常是一个数值——知识的静态强度
可信度方法
是在确定性理论的基础上，结合概率论等提出的一种不确定性推理方法。
优点：比较直观、简单、效果比较好。
可信度：根据经验对一个事物或者想象为真的相信程度。
C－F模型
基于可信度表示的不确定性推理的基本方法。
知识不确定性的表示
C-F模型中，知识是用产生式规则表示，一般形式
IF E THEN H （CF（H，E））
CF（H，E）是该条件知识的可信度，称为可信度因子，反映前提条件E与结论H的联系强度。CF > 0 支持H为真，CF < 0 支持H为假，CF = 0证据与结论无关。知识的静态强度（当 E 所对应的证据为真时对 H 的影响程度。）
证据的不确定性表示
在C-F模型中，证据的不确定性也是用可信度因子表示。CF（E），证据的动态强度
组合证据不确定性的算法
组合证据E是多个单一证据（E1、E2）合取时，CF（E）为多个单一证据中可信度最小值。（CF（E）= min{CF（E1），CF（E2）}）
组合证据E是多个单一证据（E1、E2）析取时，CF（E）为多个单一证据中可信度最大值。（CF（E）= max{CF（E1），CF（E2）}）
不确定性的传递算法
结论H的可信度计算：CF（H）= CF（H，E）× max{0，CF（E）}
结论不确定性的合成算法
IF E1 THEN H （CF（H，E1））
IF E2 THEN H （CF（H，E2））
CF1（H）= CF（H，E1）× max{0，CF（E1）}
CF2（H）= CF（H，E2）× max{0，CF（E2）}
CF1,2（H）=
若CF1（H）≥ 0，CF2（H）≥ 0
CF1（H）+ CF2（H）- CF1（H）×CF2（H）
若CF1（H）< 0，CF2（H）< 0
CF1（H）+ CF2（H）+ CF1（H）×CF2（H）
若CF1（H）CF2（H）< 0
CF1（H）+ CF2（H）/ 1 – min{|CF1（H）|，|CF2（H）|}
模糊集合
论域：所讨论的全体对象
元素：论域中的每个对象
集合：论域中具有某种相同属性的确定的、可以彼此区别的元素的全体
隶属度：模糊逻辑给集合中每一个元素赋予一个介于0和1之间的实数，描述其属于一个集合的强度，该实数称为元素属于一个集合的隶属度
隶属函数：集合中所有元素的隶属度全体构成集合的隶属函数
模糊集合的表示方法
- Zadeh表示法
- 序偶表示法
- 向量表示法
模糊集合运算
包含、相等、并补交（取大取小运算）、代数运算
模糊关系合成
模糊关系Q与模糊关系R的合成S是模糊矩阵的叉乘S = Q ° R
常用计算方法：最大-最小合成（最大最小运算）、最大-代数合成（求和最大运算）
模糊决策
(“模糊判决”、“解模糊”或“清晰化”）：由模糊推理得到的结论或者操作是一个模糊向量，转化为确定值的过程。
模糊决策方法：最大隶属度法（取最大隶属度量作为推理结构）、加权平均判决法、中位数法
第五章 搜索求解策略
问题求解基本方法
搜索法、归约法、归结法、推理法及产生式等。
搜索中需要解决的基本问题
（1）是否一定能找到一个解。
（2）找到的解是否是最佳解。
（3）时间与空间复杂性如何。
（4）是否终止运行或是否会陷入一个死循环。
搜索的主要过程
(1) 从初始或目的状态出发，并将它作为当前状态。
(2) 扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向其父结点的指针 。
(3) 检查所生成的新状态是否满足结束状态，如果满足，则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第(2)步再进行搜索
搜索策略
数据驱动：从初始状态出发的正向搜索。正向搜索：从问题给出的条件出发。
目的驱动：从目的状态出发的逆向搜索。逆向搜索：从想达到的目的入手，看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件。
双向搜索：从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合为止
启发式搜索和盲目搜索
盲目搜索：在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索。
启发式搜索：考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态。
盲目的图搜索策略
回溯策略、宽度（广度）优先搜索策略、深度优先搜索策略
回溯搜索的算法用三张表来保存状态空间
- PS（path states路径状态）表：保存当前搜索路径上的状态。如果找到了目的，PS就是解路径上的状态有序集。
- NPS（new path states新的路径状态）表：它包含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展 。
- NSS（no solvable states不可解状态）表：列出了找不到解题路径的状态。如果在搜索中扩展出的状态是它的元素，则可立即将之排除，不必沿该状态继续搜索。
CS（当前正在被检测的状态），最近加入PS中的状态
回溯思想：
- 用未处理状态表（NPS）使算法能返回（回溯）到其中任一状态。
- 用一张“死胡同”状态表（NSS）来避免算法重新搜索无解的路径。
- 在PS 表中记录当前搜索路径的状态，当满足目的时可以将它作为结果返回。
- 为避免陷入死循环必须对新生成的子状态进行检查，看它是否在该三张表中 。
宽度优先搜索
同一层拓展完再进入下一层
为了保存状态空间搜索的轨迹，用到了两个表：open表和closed表。
Open表与回溯算法中NPS表类似，包含了已经生成出来但其子状态未被搜索的状态。
Open表的排序次序就是搜索的次序。（队列，先进先出）
Closed表记录了已被生成拓展过的状态，它相当于回溯算法的PS表和NSS表的合并。
深度优先搜索：
沿一个方向一直扩展下去，直到达到一定的深度。未找到目的状态或无法再拓展时，回溯另一条路径。
Open表是个堆栈，先进后出；open表与closed表用途与广度一致；适用解题路径长、搜索有大量分支；易迷失方向
并不能保证第一次找到的路径是最短路径、后裔状态先于兄弟状态
估价函数f（n）
从初始结点经过n结点到达目的结点的路径的最小代价估计值，其一般形式是：f（n）= g（n）+ h（n）
其中，g（n）是从初始状态点到n结点的实际代价，h（n）是从n结点到目的结点的最佳路径的估计代价（已经付出代价和即将付出代价）
A搜索算法
基于估价函数的一种加权启发式图搜索算法（根据启发信息来排序open表，每次选择估计函数最小值进行拓展；每个状态保留父状态信息）
A*搜索算法（最佳图搜索算法）
1 | 定义：h*(n)为状态n到目的状态的最优路径的代价，则当A搜索算法的启发函数h(n)小于等于h*(n)，即h(n)≤h*(n)，对于全部结点n时，称为A*搜索算法。（有解时一定能找到最优解） |
第六章 智能计算及其应用
遗传算法（genetic algorithms，GA）
一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。
三种基本遗传算子：选择算子、交叉算子和变异算子
- 两种数据转换操作：
- 编码：表现型到基因型的转换，将搜索空间的参数或解转换成遗传空间中的染色体 或个体
- 解码：基因型到表现型的转换，个体转换成搜索空间的参数
遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。
遗传算法的基本思想
在求解问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生新的解。
遗传算法五个基本要素
参数编码、初始群体的设定、适应度函数设计、遗传操作设计、控制参数设定
适应度函数
是用来区分群体中的个体好坏的标准，是算法演化过程的驱动力，是进行自然选择的唯一依据。
遗传算法特点
- 对结构对象直接操作
- 有方向的随机搜索
- 采用群体搜索策略
- 应用适应度函数值来评估个体
适应度函数是用来区分群体中的个体好坏的标准，是算法演化过程的驱动力，是进行自然选择的唯一依据
第七章 专家系统与机器学习
专家系统：一类包含知识和推理的智能计算机程序。专家系统是一种智能的计算机程序，它运用知识和推理来解决只有专家才能解决的复杂问题。
专家系统知识三个层次：数据级、知识库级、控制级
专家系统的特点：
- 专业性（具有专家水平的专业知识）
- 推理性（能进行有效推理）
- 启发性（做出假设，使推理进行）
- 灵活性（知识库与推理机相互联系又相互独立）
- 透明性（解释推理过程）
- 交互性（与专家、工程师进行对话获取知识；从用户获得所需已知事实）
专家组成：完整的专家系统一般应包括人机接口、推理机、知识库、数据库、知识获取机构和解释机构
第8章 人工神经网络及其应用
- BP算法的基本思想：将输出误差以某种形式通过隐层向输入层逐层反转。
- BP 网络结构：输入层、隐层、输出层
- 输入层：输入与输出线性函数关系
- 隐层：输入与输出非线性函数关系
- 工作过程：
第一阶段或网络训练阶段：对网络的连接权进行学习和调整，以使该网络实现给定样本的输入输出映射关系。
第二阶段或称工作阶段：把实验数据或实际数据输入到网络，网络在误差范围内预测计算出结果。 - 学习算法：
正向传播：输入信息由输入层传至隐层，最终在输出层输出。
反向传播：修改各层神经元的权值，使误差信号最小。 - BP网络的主要优缺点
- 优点：
- 很好的逼近特性。
- 具有较强的泛化能力。
- 具有较好的容错性。
- 缺点：
- 收敛速度慢。
- 局部极值。
- 难以确定隐层和隐层结点的数目。
- 优点：