本文笔记针对的是西安电子科技大学计算机科学与技术专业在大三下学期必修的课程《人工智能导论》
参考教材为 蔡自兴.人工智能及其应用[M].北京.清华大学出版社.2016.7.1，配图参考的是杨利英和王晓丽老师给的 PPT 或 PDF
第一章 绪论
1.1 智能与人工智能
人工智能(顾名思义)：就是用人工的方法在计算机上实现的智能。
人工智能(学科)：人工智能是一门研究如何构造智能机器或智能系统，使它能模拟、延伸、扩展人类智能的学科。
人工智能(能力)：智能机器所执行的通常与人类智能有关的智能行为，如判断、推理、证明、识别、感知、理解、设计、思考、规划、学习和问题求解等思维活动。
1.2 人工智能的起源与发展
图灵
第一阶段：孕育(1956年之前)
第二阶段：形成(1956~1969)
第三阶段：发展(1970年至今)
1.3 人工智能各学派的认知观
符号主义：认为人工智能起源于数理逻辑，人类认知（智能）的基本元素是符号，认知过程是符号表示上的一种运算。
连接主义：认为人工智能起源于仿生学，特别是人脑模型的研究。
行为主义：认为人工智能起源于控制论，提出智能取决于感知和行为，取决于对外界复杂环境的适应，而不是表示和推理。
1.4 人工智能的研究与应用领域
问题求解、机器学习、自然语言理解、专家系统、模式识别、计算机视觉、机器人学、博弈、计算智能、人工生命、自动定理证明、自动程序设计、智能控制、智能检索、智能调度与指挥、智能决策支持系统、人工神经网络、数据挖掘和知识发现
第二章 知识表示方法
2.1 基本概念
数据是信息的载体和表示；信息是数据的语义。
一般来说，把有关信息关联在一起所形成的信息结构称为知识。
知识表示：对知识的一种描述，一种计算机可以接受的用于描述知识的数据结构
2.2 状态空间法
简述：基于解答空间的问题表示和求解方法称为状态空间法，它是以状态和算符为基础来表示和求解问题的。
特点：由于状态空间法需要扩展过多的节点，容易出现“组合爆炸”，因而只适用于表示比较简单的问题。
状态：描述问题在求解过程中不同时刻的属性
算符：使问题从一个状态转变为另一个状态的操作
状态空间：由所有可能出现的状态及一切可用算符所构成的集合
产生式系统：描述搜索过程的方法；组成：综合数据库(存放信息)，产生式规则(知识)，控制系统(规则解释)
用状态空间法表示 BFS 或 DFS 的过程
2.3 问题归约法
简述：已知问题的描述，通过一系列变换把此问题变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。
特点：问题归约法能够比状态空间法更有效地表示问题。状态空间法是问题归约法的一个特例。
本原问题：不能再分解或变换且直接可解的子问题
梵塔难题
与/或树表示
2.4 谓词逻辑法
简述：谓词逻辑法采用谓词合式公式和一阶谓词演算把要解决的问题变成一个有待证明的问题，然后采用消解定理和消解反演来证明一个新语句是从已知的正确语句导出的，从而证明这个新语句也是正确的。
特点：谓词逻辑法常与其他表示方法混合使用，灵活方便，可以表示比较复杂的问题。
经典逻辑与非经典逻辑，经典逻辑的特点是二值
命题：可以判断真假的陈述句，一般用大写字母表示，如 P＝”老李是小李的父亲”
谓词：表示关系，谓词名用大写字母表示，个体用小写字母表示，如 LIKE(I,MUSIC) 表示我喜爱音乐 \(P→Q ⇔ \lnot P∨Q\\ \lnot(\exist x)P⇔(\forall x)(\lnot P)\\ \lnot(\forall x)P⇔(\exist x)(\lnot P)\\\) 将命题表示为谓词公式
2.5 语义网络法
简述：语义网络是一种结构化表示方法，它由节点和弧线或链线组成。节点用于表示实体、概念和状态，弧线用于表示节点间关系
特点：语义网络可用于表示多元关系，扩展后可以表示更复杂的问题。
用语义网络表示命题
- 节点可以带有属性
- 下层概念可以继承上层概念的属性
- 下层概念可以对上层概念进行细化、补充、与变异（重载）
第二章 搜索策略
2.1 基本概念
搜索：采用某种策略，在知识库中寻找可利用的知识，从而构造一条代价较小的推理路线，使问题得到解决的过程。
搜索分为盲目搜索和启发式搜索。
盲目搜索与启发式搜索的区别：
-
盲目搜索按规定的路线进行，不运用特别信息
-
启发式搜索运用启发信息指导搜索过程
2.2 状态空间的搜索策略
广度优先搜索
深度优先搜索
启发式搜索，估价函数 = 代价 + 启发函数
A* 算法
画图表示搜索过程
2.3 与/或树的搜索策略
第三章 经典逻辑推理
3.1 基本概念
推理就是按某种策略由已知判断推出另一个判断的思维过程
3.3 归结演绎推理
归结，也称消解
文字：原子谓词公式及其否定
子句：任何文字的析取式
合取范式
子句集
任何谓词公式 F 都可通过等价关系及推理规则化为相应的子句集 S
谓词公式转化为子句集，实质上是转化为合取范式
计算智能
进化算法
传统优化算法
- 给定一个初始点 $x_0$，令 $x_{k+1} = x_k + a_kd_k $，其中 $d_k$ 为 f(x) 在 $x_k$ 处的一个下降方向，$a_k$ 为搜索步长
- 取不同的 $d_k$ ，就会产生不同的算法。通常要用 f(x) 的梯度信息。
传统优化算法的局限性：
- 难以求出全局最优，往往只能求出局部最优
- 对于无法获得梯度信息的问题，无法求解
货郎担问题(TSP)
设有 n 个城市， 城市 i 和城市 j 之间的距离为 d(i,j)。TSP 问题是寻找最短的一条回路，要求该回路能够遍访每个城市且每个城市仅访问一次。
进化算法
为克服传统优化方法缺点而设计，是对传统优化算法的补充。
进化算法的特点：
-
进化算法的迭代形式不同传统优化算法那样，从一个点向另一个点移动，而是一群点通过进化算子移动到另一群点。
-
因为进化算法的迭代形式，所以进化算法是并行的搜索多个山谷，容易求解出全局最优点
-
进化算法不需要梯度信息，只需要适应度函数的信息(可由目标函数确定)
进化算法的分支：
- 遗传算法
- 进化策略
- 进化规划
- 遗传程序设计
进化算法的基本步骤：
- 产生初始种群
- 计算个体的适应度评价个体的优劣
- 用进化算子产生新种群
- 终止条件成立则结束，否则转到步骤二
遗传算法
遗传算法的基本步骤：
- 对问题进行编码，产生初始种群
- 对个体进行交叉、变异等遗传操作，产生新个体
- 根据优胜劣汰的原则对个体进行选择
- 根据上述过程迭代，最终产生合适的个体
编码：将问题的解用位串形式表示
种群初始化：使用计算机在0～1之间产生随机数 K，并按照数 K 的值初始化基因位，产生N个个体组成初始种群
适应度
交叉
- 单点交叉，交叉点前或后互换
- 两点交叉，交叉点间互换
- 多点交叉
- 部分匹配交叉
- 顺序交叉
变异
选择
-
轮盘赌选择
随机，但适应度高的个体被选择的概率大，体现自然选择，优胜劣汰
-
两两竞争法选择
-
锦标赛选择
-
精英保留
从实际问题理解遗传算法
上图给出了目标函数，取值范围，精度等信息。
神经网络
人工神经网络：模拟生物神经网络由简单的处理单元(神经元)组成的大规模并行分布式处理器。
M-P神经元模型
- 每个神经元都是一个“多输入”和“单输出”的信息处理单元
- 神经元具有空间整合特性
- 神经元具有阈值
- 神经元的输入分兴奋性输入和抑制性输入两种类型
激活函数，阶跃函数
单层感知器网络
- 输入层(感知层)
- 输出层(信息处理层)
单层感知器的局限性：只能解决线性可分问题
多层感知器网络(MLP)
-
输入层
- 隐藏层，多层计算节点
- 输出层
监督学习，将神经网络学习问题转化为输出误差最小化的优化问题
BP 算法(反向传播算法)
- 初始化网络权重
- 前向传播
- 计算误差
- 反向传播
- 判断结束
反向传播算法采用梯度下降法修正权值，因此要求激活函数可微
模糊逻辑
这节主要讲模糊逻辑，并且与命题逻辑对比。
命题逻辑与模糊逻辑，命题逻辑是确定的，要么是 0 ，要么是 1 ；模糊逻辑是模糊的，在 [0,1] 中
模糊集合
模糊集合把元素对集合隶属程度的取值范围从{0,1}推 广到[0,1]上
隶属函数，隶属度
| 集合的表示 | 模糊集合的表示 |
|---|---|
| 枚举法 | 扎德表示法 |
| 描述法 | 向量表示法 |
| 积分表示法 | |
| 序对表示法 |
模糊集合的运算
模糊关系
模糊关系的表示
- 枚举法
- 表格法
- 有向图法
- 矩阵法
模糊关系的性质
- 自反性
- 反自反性
- 对称性
- 传递性
模糊复合关系
矩阵法求模糊复合关系
模糊推理
非经典逻辑推理
可信度：是指人们根据以往经验对某个事物或现象为真的相信程度。
CF(H,E) 的取值为 [-1,1]
CF(E) 的取值为 [-1,1]
组合证据的不确定性计算：
- AND ，min
- OR ，max
CF(H)=CF(H,E)×max{0,CF(E)}
