2021SPR《人工智能》课程复习笔记

第一章 总论

现代人工智能（Artificial Intelligence，简称AI），一般认为起源于美国1956年的一次夏季讨论（达特茅斯会议），在这次会议上，第一次提出了“Artificial Intelligence”这个词。

AI是一门新兴的边缘学科，是自然科学与社会科学的交叉学科。
AI的交叉包括：逻辑、思维、生理、心理、计算机、电子、语言、自动化、光、声等。
AI的核心是思维与智能，构成了自己独特的学科体系。
AI的基础学科包括：数学（离散、模糊）、思维科学（认知心理、逻辑思维学、形象思维学）和计算机（硬件、软件）等。

第二章 一般图搜索

图搜索是搜索过程可以用图结构的形式呈现的一类搜索算法。图可以更加形象与清晰地描述搜索过程。

扩展节点

生成某一节点的所有后继节点，并给出他们之间的耗散值。

图搜索要素

问题状态：问题求解过程中的一个状态，对应于图G_i=(E,V)
初始状态：问题求解之前的状态，对应于图G_0=(E,V)=S
目标状态：包含求解目标的状态，对应于图G_n=(E,v)=T
问题的解：从T到S的反推
状态空间：问题求解过程中所有可能状态的集合

图搜索基本思想

• 从给定的初始节点出发
• 迭代地选择节点扩展，得到新的状态
• 扩展到目标状态停止，或者没有节点可扩展为止
• 从目标状态反推到初始节点，得到问题的解

需要使用的数据结构

OPEN表：存储还未扩展的节点
CLOSED表：存储已经扩展过的节点
状态图G：已扩展出的节点呈现出的状态

节点类型

• 已扩展过的节点，Closed表
• 新扩展的节点，不在两个表内
• 待扩展的节点，Open表

补充说明

一般图搜索是一类无信息搜索，盲目扩展所有节点，与问题本身无关。
一般图搜索算法是很多算法的基础，通常通过在搜索前：

• 根据条件降低搜索规模
• 根据问题的约束条件进行剪枝
• 利用搜索过程中的中间解，避免重复计算
• 利用问题启发式信息，减少搜索空间

第三章 启发式搜索

利用启发式信息引导算法搜索，达到减少搜索范围，降低问题复杂度的目的。

启发信息的使用

强：降低搜索工作量，但可能导致找不到最优解
弱：导致工作量加大，极限情况下变盲目搜索，但可能可以找到最优解
关键点：如何利用启发式信息，尽可能有效地找到问题的近似最优解
人：有关问题的求解经验+算法设计

启发式图搜索基本思想

基于一般图搜索算法，定义一个评价函数f，对当前的搜索状态进行评估，从Open表中找出一个最有希望的节点来扩展。

评价函数

f^*(n) = g^*(n) + h^*(n)
g^*(n) 从根节点到当前节点的最短路径长
h^*(n) 从当前节点到目标节点的最短路径长

因为在运行中，我们无法得知真正的最短路径，所以采用估计值来代替。

爬山法

只考虑与目标之间的差距，即g(n) = 0

最佳图搜索A*算法

如果在上述算法中，恒有h(n) \leqslant h^*(n)，那么算法变为A*算法。
在A*算法运行过程中，有：
f^*(S) = f^*(T) = h^*(S) = g^*(T) = f^*(n)
其中n是最佳路径S→T上的节点。

A*定理和推论

定理1：对于有限图，A*算法一定终止。
算法每次循环从OPEN表里去掉一个节点，而有限图的OPEN表内只有有限个节点加入。所以无论算法是否找到解都会正常停止。
定理2：若算法不终止，则OPEN表上的点的f值将越来越大。
定理3：A*结束前，Open表中必存在f(n)≤f^*(S)。
定理4：若问题有解，算法终止时一定找到最优解，即可纳。
定理5：OPEN表上任一具有f(n)≤f^*(s)的节点n，最终都将被算法选作扩展的节点。
定理6：A*选作扩展的任一节点n，有f(n)≤f^*(s)。
定理7：设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h_2(n) > h_1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。

算法改进

因A算法第6步对m_1类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。

解决的途径:

• 对h加以限制：对h增加适当的限制，使得第一次扩展一个节点时，就找到了从S到该节点的最短路径。
• 对算法加以改进：对算法加以改进，避免或减少节点的多次扩展。

改进的条件:

• 可采纳性不变
• 不多扩展节点
• 不增加算法的复杂性

算法描述

* 初始化open_set和close_set；
* 将起点加入open_set中，并设置优先级为0（优先级最高）；
* 如果open_set不为空，则从open_set中选取优先级最高的节点n：
    * 如果节点n为终点，则：
        * 从终点开始逐步追踪parent节点，一直达到起点；
        * 返回找到的结果路径，算法结束；
    * 如果节点n不是终点，则：
        * 将节点n从open_set中删除，并加入close_set中；
        * 遍历节点n所有的邻近节点：
            * 如果邻近节点m在close_set中，则：
                * 跳过，选取下一个邻近节点
            * 如果邻近节点m也不在open_set中，则：
                * 设置节点m的parent为节点n
                * 计算节点m的优先级
                * 将节点m加入open_set中

与或图搜索

超图：定义它的边（这里叫超边，hyperedge）可以和任意个数的顶点连接。
k-均匀超图：超图的每个边连接的顶点个数都是相同的，即为个数k。
能解节点：

• 终节点是能解节点
• 若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解
• 若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解

不能解节点

• 没有后裔的非终节点是不能解节点。
• 若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解
• 若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解

第四章 不确定性搜索

局部搜索算法

通常考察一个算法的性能通常用局部搜索能力和全局收敛能力这两个指标。局部搜索是指能够无穷接近最优解的能力，而全局收敛能力是指找到全局最优解所在大致位置的能力。
局部搜索是解决最优化问题的一种启发式算法。对于某些计算起来非常复杂的最优化问题，比如各种NP完全问题，要找到最优解需要的时间随问题规模呈指数增长，因此诞生了各种启发式算法来退而求其次寻找次优解，是一种近似算法（Approximate algorithms），以时间换精度的思想。局部搜索就是其中的一种方法。

伪代码描述

LOCAL-SEARCH
    随机选择一个可能的初始解x
    扩展x的邻域P(x)
    如果满足结束条件，停止循环：
        选择P(x)中的一个子集P'(x)
        评估其中的最优解y
        如果f(x)>f(y)
            x := y
            P(x) := P(y)
        否则
            P(x) := P(x) - P'(x)
    输出结果

存在的问题和改进

陷入局部最优而非全局最优

• 每次并不一定选择邻域内最优的点，而是依据一定的概率，从邻域内选择一个点，指标函数优的点，被选中的概率比较大，而指标函数差的点，被选中的概率比较小。
• 变更步长
• 随机生成初始点，取最佳

第五章 博弈搜索

博弈问题的基本假设：

• 两个棋手交替地走棋
• 比赛的最终结果，是赢、输和平局中的一种
• 可用图搜索技术进行，但效率很低
• 博弈的过程，是寻找置对手于必败态的过程
• 双方都无法干预对方的选择

基本思想：

• 下棋的双方是对立的
• 一方为“正方”，这类节点称为“MAX”节点
• 另一方为“反方”，这类节点称为“MIN”节点
• 正方从所有子节点中，选取具有最大评估值的节点
• 反方从其所有子节点中，选取具有最小评估值的节点
• 反复进行这种选取，就可以得到双方各个节点的评估值。这种确定棋步的方法，称为极小极大搜索法。

对各个局面进行评估
评估的目的：对后面的状态提前进行考虑，并且以各种状态的评估值为基础作出最好的走棋选择。
评估的方法：用评价函数对棋局进行评估。赢的评估值设为+∞，输的评估值设为-∞，平局的评估值设为0。
评估的标准：由于下棋的双方是对立的，只能选择其中一方为评估的标准方。

a-b剪枝法

MAX节点的评估下限值a
作为正方出现的MAX节点，当它的第一个MIN子节点的评估值为a时，对于其它的子节点，如果有高过a的，就取那最高的值作为该MAX节点的评估值；如果没有，则该MAX节点的评估值为a。

MIN节点的评估上限值b
作为反方出现的MIN节点，当它的第一个MAX子节点的评估值为b时，则对于其它子节点，如果有低于b的，就取那个低于的值作为该MIN节点的评估值；如果没有，则该MIN节点的评估值取b。

a剪支法
设MAX节点的下限为a，则其所有的MIN子节点中，其评估值的a上限小于等于a的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了a剪支。

b剪支法
设MIN节点的上限为b，则其所有的MAX子节点中，其评估值的b下限大于等于b的节点，其以下部分的搜索都可以停止了，即对这部分节点进行了b剪支。

蒙特卡洛树搜索

根据模拟的输出结果，按照节点构造树。每个节点必须包含两个重要信息：

• 根据模拟结果估计的值
• 该节点被访问的次数

第六章 约束满足问题

地图着色问题

地图着色是指分配地图的每一个面一种颜色，使得相邻的面(指有公共边界边)具有不同的颜色。

定义：

• 考虑图形中全部节点（N个）
• 变量取值范围集合S
• 将S中的元素赋值给V_i \in {V}
• 约束：如果E(i,j)存在，那么V_i \neq V_j

特点：没有优化目标

一般图搜索策略

DFS改进策略
基本思想：尽可能剪枝
只评估那些赋值，它们不违反任何与目前赋值想关的约束
不搜索那些明显不可能通往解的分支
预测合法的赋值
控制变量与值的排序

向前查看策略

对于未赋值的变量，跟踪余下的合法值
当变量无合法值时，回溯

约束传播策略

Propagate(node, color)
    从node的所有近邻的值域中去掉color
    对每个近邻n
        if 第1步后，D(n)中只剩一种颜色，即D(n)={c}
            Propagate(n, c)

变量与值的启发式算法

变量排序
1.最多约束变量(MCV)
选择一个贡献最多约束数的变量，会对其它变量有极大的影响，因此有希望裁剪掉大部分搜索
要求：在约束图中找到与最多变量相连的变量

2.最少余下值(MRV)
选择一个侯选值最少的变量，由此极可能导致一个早期的失败(失败优先启发式策略)

值排序
1.最少值约束(LCV)
选择使相邻变量可用值减少最少的值
优先选用最有可能的值（也即为随后的变量赋值提供最大的灵活性）来获得一个解

搜索算法总结

偏算法

一般图搜索算法：最基础的搜索算法，与问题无关，效率低，但是书写简洁。
启发式搜索算法：利用问题信息，提高算法搜索效率。
不确定性搜索算法：初始化一个解，逐步改进；引入不确定因素，求近似最优解。

偏问题

博弈搜索：针对二人博弈问题，剪枝和评估函数值估计是关键。
约束满足：寻找满足所有约束的解，剪枝是关键。

两大类基本搜索算法

构造法：从零开始逐渐构造一个最优解
逼近法：从一个差的解开始逐渐逼近最优解

搜索算法设计的本质

在给定的硬件条件下，更快更好地解决问题
更快：降低搜索空间大小 + 问题相关启发式信息指导+硬件加速
更好：有限时间内获得更好的近似最优解或局部最优解

问题+算法+硬件

问题与算法无法分割，脱离问题的算法效率过低（穷举法等）
算法在具体的硬件上执行，需考虑执行环境（研究相对较少）
问题分类-》寻找同类问题共有的启发式信息-》设计或改进求解算法
将人的认识融入到计算机自动执行的算法之中

第七章 机器学习基础

根据样本数据的标记（label）特性，可将机器学习任务分为：
监督学习：样本特征x均有对应的样本标记y
无监督学习：样本特征x均没有对应的样本标记y
半监督学习：样本特征x（大）部分没有对应的样本标记y
强化学习：可近似理解为具有延迟标记信息

评估

误差：真实输出与预测输出之间的差异
泛化误差：训练集+测试集之外的数据的误差

回归问题使用均方误差。
分类问题使用
错误率：错误分类的样本占总样本数的比例
准确率：1-错误率

精密度：真正/(真正+假正)
召回率：真正/(真正+假负)

精密度=召回率的点可以度量在PR图上有交叉的分类器的性能高低。

交叉验证

分层采样划分为k个（一般取10或5）大小相似的互斥子集。
每次选择k-1个子集作为训练集，剩余的作为测试集。
上述过程迭代k次，返回每次测试结果的均值。

第八章 监督学习

监督学习类型

当标记为离散值时：分类
当标记为连续值时：回归

学到的模型能够良好的适用于未来的测试样本（泛化能力），而不仅仅是在已有的训练样本上表现良好

线性回归

y = f(x_1, x_2, ..., x_d)+\epsilon
\epsilon为随机误差项，表示由于人们的认识以及其它客观原因的局限而没有考虑的各种偶然因素。

优势：简单、易于训练和测试、数学上易于优化、可解释性好、是复杂非线性模型的基础。

决策树

决策树（decision tree）：基于树结构进行决策
树的每个内部结点对应某个特征/属性上的判定
每个分支对应上述判定的一种可能结果（该属性的某个取值）
每个叶结点对应一个预测结果

基于信息增益选择划分属性的缺点：
偏向于选择可取值数目较多的属性（比如会将样本编号作为一个划分属性来选择，这明显不合理）

第九章 聚类算法

k-Means算法

算法流程（迭代优化）：
初始化每个簇的均值向量
repeat

1. （更新）簇划分；
2. 计算每个簇的均值向量
   until 当前均值向量均未更新

密度聚类DBSCAN

第十章 神经网络

前馈神经网络（全连接神经网络、多层感知器）

各神经元分别属于不同的层，层内无连接。
相邻两层之间的神经元全部两两连接。
整个网络中无反馈，信号从输入层向输出层单向传播，可用一个有向无环图表示。

激活函数

理想激活函数是阶跃函数, 0表示抑制神经元而1表示激活神经元
阶跃函数具有不连续、不光滑等不好的性质, 常用的是 Sigmoid函数

性质：
• 连续并可导（允许少数点上不可导）的非线性函数。
可导的激活函数可以直接利用数值优化的方法来学习网络参数。
• 激活函数及其导函数要尽可能的简单
有利于提高网络计算效率。
• 激活函数的导函数的值域要在一个合适的区间内
不能太大也不能太小，否则会影响训练的效率和稳定性。
• 单调递增

反向传播算法

https://zhuanlan.zhihu.com/p/32819991?ivk_sa=1024320u

缓解过拟合
主要策略：
早停 (early stopping)
• 若训练误差连续 a 轮的变化小于 b, 则停止训练
• 使用验证集：若训练误差降低、验证误差升高 , 则停止训练
正则化 (regularization)
• 在误差目标函数中增加一项描述网络复杂度

第十一章 深度学习

图像识别特点

• 在一张图片中，某些模式只需要利用图中很小的一部分就可以判断出来（神经网络无需对整张图片做判断而得到结果）
• 同一个模式可能存在图片的不同位置
• 下采样像素不会改变图片中的对象(通过下采样使得图片变得更小，利用更少的参数处理图片识别)

CNN流程

卷积运算

将卷积算子对准原矩阵的一个值，将重叠的数字相乘后，加总得到的数字替换原矩阵的这个被对准的值。
一般会取均值。

假设原矩阵是p·p·q，卷积算子规模为k，一共n组。那么每组卷积算子有q个，输出的矩阵为(p-\lfloor k/2 \rfloor)^2·n。

然后使用激活函数修改矩阵。

池化

Max-Pooling，用一块区域内部最大的数值代替整个区域。
Avg-Pooling，用一块区域的均值代替整个区域。
池化是为了降维。

Flatten

把多维的输入一维化，常用在从卷积层到全连接层的过渡。

第十二章 知识表示

评价知识表示的两个重要因素：

• 表达能力（expressiveness）：一个知识表示应该具有足够强的表达能
  力，以充分完整地表达特定领域或者问题所需的知识。
• 计算效率(efficiency)：基于这一知识表示的计算求解过程也应有着足够
  高效的执行效率。

符号知识表示

谓词逻辑（Predicate Logic）
产生式规则（Production Rule）
框架（Frame）
树形知识表示
概率图模型 (Probabilistic Graphical Model)
语义网络 (Semantic Newtork)
知识图谱（Knowledge Graph）

数值知识表示

知识图谱的表示学习旨在将知识图谱中的元素(包括实体、属性、概念等)表示为低维稠密实值向量
知识图谱的两种表示各有其适用场景

• 向量化表示是面向机器处理的
• 符号化表示是面向人的理解的。
• 相对于向量化表示，符号知识易于理解，可以实现符号推理。

基于翻译的TransE模型不适用与自反，一对多，多对一型关系

第十三章 知识图谱（上）

知识图谱(Knowledge Graph)本质上是一种大规模语义网络（semantic network）
富含实体(entity)、概念(concepts)及其之间的各种语义关系(semantic relationships)

知识图谱是一种以图形化的(Graphic)形式通过点和边表达知识的方式，其基本组成元素是点和边。

KG优势

• 大规模，实体和概念的覆盖度高
• 语义丰富，在语义关系上覆盖度高
• 质量高，多源数据交叉验证
• 结构化程度高

KG劣势

• 高质量模式缺失，知识图谱在设计模式时通常会采取一种“经济、务实”的做法：也就是允许模式（Schema）定义不完善，甚至缺失

• CWA 是假定数据库或知识库中不存在（或未观察到）的事实即为不成立的事实，KG中CWA不成立。很难保证知识图谱中关于柏拉图的信息完整，很可能会缺失柏拉图父母的信息。但常识告诉我们柏拉图一定有父母。

• 大规模自动化知识获取成为前提

词汇和实体挖掘

领域词汇挖掘指的是从给定的领域语料中自动挖掘属于该领域的高质量词汇的过程。

高质量短语
高频率：一个 N-Gram 在给定的文档集合中要出现得足够频繁才能被视作高质量短语。
一致性：N-Gram 中不同单词的搭配是否合理或者是否常见。
信息量:一个高质量短语应该传达一定的信息，表达一定的主题或者概念。比如，“机器学习”与“这篇论文”
完整性:一个高质量短语还必须在特定的上下文中是一个完整的语义单元。

基于规则的

无监督
通过预定义的词性标签（POS Tag）规则来识别文档中的高质量名词短语。
缺陷：规则一般是针对特定领域手工设计的，难以适用于其他领域。人工定义规则代价高昂，难以穷举所有的规则，因此召回率存在一定的局限性。

有监督
利用标注好词性的语料来自动学习规则
缺陷：依赖于领域的语言规则以及昂贵的人工标记，不适用于新兴的大型语料。另外词性标注不能做到百分百的准确，这会在一定程度上影响后续规则学习的准确率。

基于统计学习

无监督
通过计算候选短语的统计指标特征从而给词汇打分、排序来进行领域词汇挖掘。

有监督
根据人工或自动标注的高质量短语，建立高质量短语分类模型。
使用wiki中存在的词条做自动标注。

统计指标

TF-IDF：一个词的重要程度与其tf 正相关，idf反相关。
如果某个短语在领域语料中频繁出现但是在外部文档中很少出现，则该短语很可能是该领域的高质量短语。

C-Value：词频与长度决定候选短语质量。
• 父短语的重复统计会带来频次估计的偏差。
• “支持向量机”是个高质量短语，那么“向量机”和“支持向量”的词频就不应该重复计数。
一般而言，在很多专业领域（比如医学领域）越长的短语越有可能是专有名词, 从而极可能是高质量短语。

NC-Value：在C-value的基础上利用短语丰富的上下文信息。

PMI点互信息：PMI 值刻画了短语组成部分之间的一致性（Concordance）程度。
如果两部分联合出现的概率远大于两者在独立情况下随机共现的概率，说明这两个部分的共现是一个有意义的搭配，预示着两者应该组成一个有意义的短语而非纯粹偶然共现。

左（右）邻字熵:描述词汇的自由搭配程度，也就是用来衡量一个词的左(右)邻字集合的丰富程度。
一个词汇的左（右）邻熵越大，左（右）搭配越丰富，则该词汇越有可能是个好的词汇。

第十四章 知识图谱（下）

关系抽取

自动化模式获取:自举法

Motivation：自动发现更多的模式，提升基于模式方法的recall
基本过程：模式提取+实例抽取 相互迭代
是一种半监督的思路：用当前已经习得的模型（模式）自动标注新样本，基于新补充的样本逐步提升模型

基于中文例子的迭代过程:
Step1：给定关系“出生于”、种子实体对<周杰伦，台湾>和<林丹，福建>
Step2：抽取出句子集合：{“周杰伦，出生于台湾省新”，“周杰伦在台湾…”，“林丹小时候在福建学球”}
Step3：得到关系“出生于”的描述Pattern{“X出生于Y”，“X在Y”，“X小时候在Y”}
Step4：基于该模式，抽得句子“林俊杰，出生于新加坡的一个音乐世家”，从而得到实体对<林俊杰，新加坡>

语义漂移问题

迭代过程中得到的新Pattern不再能表达种子关系。
迭代会引入噪音实例和噪音模板。

比如：纽约位于美国的东海岸，提取（纽约，美国），但不能表达纽约是美国的首都。从这个pattern得到的后续的pattern都是错的。

Bootstrapping-语义漂移解决方案
Mutual exclusive Bootstrapping ：同时扩展多个互斥类别，一个实体对只能属于一个类别；
Coupled training：建模不同抽取关系之间的约束，寻找最大化满足约束的抽取结果；
Co-Bootstrapping ：引入负实例来限制语义漂移；

第十五章 贝叶斯网络

贝叶斯网络由网络结构和条件概率表组成

• 网络结构是一个有向无环图
• 每个结点代表一个事件或者随机变量
• 结点的取值是完备互斥的

贝叶斯网络预测

• 贝叶斯网络的预测是指从起因推测一个结果的推理，也称为由顶向下的推理
• 原因推导出结果，求出由原因导致的结果发生的概率

贝叶斯网络诊断

• 贝叶斯网络的诊断是指从结果推测一个起因的推理，也称为由底至上的推理
• 已知发生了某些结果，根据贝叶斯网络推理计算造成该结果发生的原因和发生的概率

贝叶斯网络学习

• 贝叶斯网络学习是指由先验的贝叶斯网络得到后验的贝叶斯网络的过程
• 贝叶斯网络学习的实质是用现有数据对先验知识的修正
• 贝叶斯网络可以持续迭代修正
• 上次学习得到的后验贝叶斯网络变成下一次学习的先验贝叶斯网络
• 结构学习：确定最合适的贝叶斯网络模型结构
• 参数学习：在给定结构下，确定贝叶斯网络模型的参数，即每个结点上的条件概率分布表（CPT表）。

第十六章 归结原理

归结的过程
写出谓词关系公式
用反演法写出谓词表达式
SKOLEM标准形
子句集S
对S中可归结的子句做归结
归结式仍放入S中，反复归结过程
得到空子句
得证