高级人工智能复习 中科大

参考：

中科大2023春季【高级人工智能】试题回顾
中国科学技术大学《高级人工智能》课程 重要知识点提纲
高级人工智能复习提纲

1.搜索

1.1 搜索问题的概念

搜索问题的五个要素：状态空间、后继函数、初始状态、目标测试和路径耗散。

用状态图描述搜索问题：
每个节点表示一个状态，弧及两端点表示后继函数。状态图可能包括多个不连通的分量，状态图上标有初态和终态。

搜索问题无解：状态图中初始节点和终态节点在不连通的两个分量中。

1.1.1 搜索问题举例

华容道：

• 状态空间：期盼任意一种布局
• 后继函数：合法移动棋子得到另一种布局
• 初态：任意初始布局 终态：曹操跑出来
• 路径耗散： 每移动一个棋子，路径耗散为1
• 目标测试：解–从初态到终态的移动序列；最优解–路径耗散最少的序列

数码游戏/8皇后问题/数独建模类似

1.1.2 五要素

状态
对事物可能的抽象表示，构建好的状态空间可以减少空间的大小从而降低搜索难度。

好的状态空间：

• 尽量覆盖所有合法状态，并尽可能让所有状态是可达，可行合法的
• 状态数目越少越好
• 方便设计后继函数和搜索算法

例子：
对于8皇后，设置状态为任何0~8个皇后在棋盘上的布局表示一个状态，总状态数为$P_{64}^8$。
如果设置为0~8个皇后在棋盘左侧且不互相攻击代表一个状态，则状态数目骤减为2057个。

后继函数
后继函数即为状态图的边，通常后继函数会返回若干个后继状态的集合。

路径耗散
标记在状态图的边上，表示执行后继函数的代价。一般都是正的（有时也被认为是一种reward）。
例如对数码问题，每移动依次，代价为1；n皇后问题，每放置/撤回一个皇后，代价为1，从一个状态转移到下一个状态花费代价为$\le 2n$。

初态和终态
初态和终态都可以是：

• 某个精确的特定状态
• 满足某些条件的某个状态
• 满足厚些条件的状态集合

问题的解
可能有唯一解，无解或多个解，有多个解时路径耗散最小的成为最优解。

1.1.3 路径规划问题形式化

• 网格化
• 扫描线法
• 障碍物边界法

1.1.4 搜索

基准算法：对状态图的宽度优先遍历。
其他算法：
相同点：与基准算法 基本框架一致、所有可达和不可达的状态子图一致；
不同点：从状态图中选择和处理的状态子集不一样、状态子集构成的状态子图不一样、后继函数不一样。

搜索树：将状态图中算法的搜索过程涉及到的状态和搜索顺序抽取出来就得到了对应的搜索树。
状态图中的状态可能被重复访问，体现在状态图上的同一节点会变为搜索树上的不同节点。

节点扩展：节点扩展是生成搜索树的关键操作。直观理解就是把一个节点用它的后继节点（集合替换）。
扩展包括：评估节点的后继函数（考虑路径耗散），然后对后继函数返回的所有后继状态，在搜索树上分别产生一个子节点与之对应。注意节点扩展$\ne$节点产生，对节点扩展也可能不产生新的节点。修改节点集合的优先性质就是在改变搜索的扩展策略。

评估算法：考虑三个性质 完备性、最优性和复杂性。
完备性：有解时，能保证返回一个解；无解时，能保证返回failue
最优性：能否找到最优解
复杂性：搜索树的大小；时间复杂度；空间复杂度
’
一个搜索树的大小由初态、后继函数和搜索策略决定，影响因素是分支因子、最浅目标状态的深度和路径的最大长度。
时间复杂度：访问过的节点数目； 空间复杂度：同时保存在内存中节点数目的最大值。

边界：搜索树的边界（FRINGE）是指那些已访问过但未扩展状态的节点集合。搜索树上的叶节点不一定是搜索树的边界节点。
搜索策略：FRINGE中节点的优先次序

1.2 盲搜索（bsearch）

从搜索树的边界FRINGE这个角度看：
无信息搜索、盲搜索的特点是边界是无序的；有信息搜索、启发式搜索的特点是将更有希望的节点放在边界的最前面。

基准算法属于盲搜索算法，它单纯将新的节点插入FRINGE的末尾.
基准算法的两个重要参数是:

• 分子因子$b$（后继函数返回的最大状态数目）
• 从初态到目标状态的最小深度$d$；搜索树上离根最近的目标节点的深度

基准算法是

• 完备的；
• 在每条边路径耗散相同的情况下是最优的；
• 访问节点数是$O(b^d)$。
  当问题无解时，如果状态空间无限大或者任意状态可以任意次重复访问，则基准算法不会停止。

1.2.1 盲搜索的改进

双向搜索算法

分别从初态和终态启动两个搜索算法。维护两个边界集合，当集合相交时算法结束。
双向搜索的两个搜索算法可以不一样。
双向搜索的评价：

• 完备的；
• 路径耗散相同时保证最优性；
• 时空复杂度（假设两个方向的分子因子相同）是$O(b^{d/2})$。

此算法没有带来根本性的变化，且在某些状态下不便于定义终态的“前驱函数”（例如象棋的目标状态）。但是提供了一种搜索算法改进的框架，并获得极大的优化，同时完备性和最优性和基准算法一致。

深度优先算法

节点扩展时，新节点总是插入到边界集合的队头。
深度优先的评价：

• 若搜索树有限则完备；
• 不一定最优；
• 时间复杂度（最坏情况，假设$m$是叶节点的最大深度）是$O(b^m)$，空间复杂度$O(bm)$。

回溯法

节点扩展时，只插入一个新节点到边界集合的队头,同时最多保存$O(m)$个节点。
评价：

• 若搜索树有限则完备；
• 不一定最优；
• 时间复杂度（最坏情形，假设$m$是叶节点的最大深度）$O(b^m)，空间复杂度$O(m)$。

深度受限的深度优先搜索

设置扩展节点的深度阈值$k$，当节点深度大于阈值时不再扩展。
返回结果：解；无解failure;深度阈值k内无解
评价：

• 若搜索树有限则完备；
• 不一定最优，
• 时间复杂度$O(b^k)$，空间复杂度$O(bk)$。

迭代深入搜索（IDS）

使用不同的受限深度参数$k=0,1,\mathrm{2...}$ 重复执行深度受限搜索。
结合BFS和DFS的长处，但要重复搜索节点。
评价：

• 当$k=d$时，完备；
• 单步路径耗散相同时最优，否则不一定；
• 访问节点数（最坏情况）$O(b^d)$，空间复杂度$O(bd)$。

代价一致搜索

每次在边界中选择让目前获得的路径耗散最小的节点扩展，当单步路径耗散相同时等价于基准算法。
要求单步耗散有下界$x_i\ge \epsilon >0$
评价：

• 当搜索树有限且单步耗散有下界时完备；
• 最优；
• 时空复杂度为$O(b^{[C^{\ast }/\epsilon ]})$，一般比基准算法大

总结

1.2.2 避免状态重复访问

重复访问状态产生的原因是可逆的行动。

• 设置一个标识数组记录已经访问过的节点，若扩展终点得到的后继状态在标识数组中则直接丢弃。
  这一方法需要的内存比较大，而且如果要保证最优性需要使用宽度优先搜索算法，

• 用Open/Closed表，closed表存储所有访问过的状态，未拓展的状态用Open来表示，若当前待扩展的转台在CLosed中，将其丢弃，否则扩展。

1.2.3 树搜索和图搜索

我们将采用Open/Closed表的算法框架称为图搜索：
例如在代价一致搜索中：
closed表保存每个状态的最优路径耗散（从初态出发），若s在closed表中，则检查s的代价（从初始状态到s的路径耗散），并和当前路径+s的总路径耗散进行比较，取较小的路径耗散，更新状态s的路径耗散；若s不在closed表中，则放入closed中，并开始扩展。

树搜索中不同节点可能代表的是相同的状态，分别代表从初态出发到达同一状态的不同路径；而图搜索中不同的节点代表不同的状态，相同状态都合并到同一节点上。

若状态空间无限，或者有限但允许状态被任意复杂重复访问，则搜索一般是不完备的；若状态空间有限且访问时重复状态被抛弃则搜索是完备的但一般不是最优的。

1.3 启发式搜索（heuristic）

和基准算法不同：启发式算法在拓展并插入新状态节点进入FRINGE时，会增加一个在FRINGE中给待拓展状态空间按一定优先级排序的过程

启发式搜索通过设计一个评估函数$f$ ，将搜索树的节点$N$映射到一个非负实数$f(N)$，表示从初始状态到达某个节点的路径耗散（越小越好）。

最佳优先搜索：每次从FRINGE中选择最佳节点进行拓展，这里的最佳是局部贪婪，并不一定是全局最佳。

设计函数$f$的两种方法：

• 设计$f(N)=g(N)+h(N)$对应${\text{A}}^{\ast }$算法
• $f(N)=h(N)$对应贪婪算法。
  $N$:待评价的节点，$g(N)$从初始节点到$N$的路径耗散，$h(N)$从$N$到目标节点的路径耗散，这就是所谓的启发式函数

1.3.1 启发式函数的设计要求

基本要求： $h(N)\ge 0,h(Goal)=0$；离目标越近$h(N)$越小。
可采纳性： $0\le h(N)\le h^{\ast }(N)$，其中$h^{\ast }(N)$ 是到目标的实际最优路径。这代表启发式函数必须乐观的估计将来的耗散。通常可以用一个松弛问题设计可采纳的启发式函数。
一致性/单调性 $h(N)\le c(N,N^{\prime })+h(N^{\prime })$，其中$N^{\prime }$是$N$的后继，$c(N,N^{\prime })$为两点之间的单步耗散。注意一致的启发式函数都是可以采纳的。这带来$h(N)\le h^{\ast }(N)\le c(N,N^{\prime })+h(N^{\prime })$。

举例1：
机器人导航问题，在一个网格中有的格子是路径有的是障碍物，从初态格子导航到终态格子。
$f(N)=h(N)=Manhattandistance$ 启发式函数为从当前点到终点的曼哈顿距离。

举例2：
数码问题（一个九宫格中每个格子分别填有1~8）或是空格，数字可以移动到邻接的空格中去，给定初始数字分布和目标数字分布求移动方式。
三种启发式函数设计：

• 错误放置的格子数（可采纳，一致的）
• 所有的数字到其正确位置的曼哈顿距离之和（可采纳一致的）
• 逆序数之和

举例3：
路径规划问题
启发式函数可以为：

• 欧式距离（可采纳的，一致的）
• 曼哈顿距离（若不允许沿网格对角线移动，则是可采纳的一致的；否则是不可采纳的不一致）

1.3.2 A*

$f(N)=g(N)+h(N)$对应${\text{A}}^{\ast }$算法
$g(N)$是初始节点到N的路径耗散，$h(N)$是从N到目标节点的路径耗散，可采纳的启发式函数

问题有解时：具有完备性、最优性，且对一致的$h$，A*算法拓展一个状态节点时到该状态的路径一定是最优的。（证明见PPT29）

无解情况：
1.状态空间无限/ 允许重复访问，A*算法的搜索不会停止
2.求解实际问题时通常给一个停止时间，到达时间时自动停止

再议图搜索和树搜索：
图搜索允许状态重复访问–>保证获得最优解–>无解时可能永远停不下来
树搜索避免状态重复访问–>状态有限时完备–>不保证最优

A*算法状态重复访问改进：当且仅当该节点的新路径的耗散$g(N)$比以前访问该状态的路径耗散更大时，丢弃重复访问的这个状态节点。

A算法中一致的启发式函数：
特殊的一致启发函数$h=0$，等价单步路径耗散相同，A 退化为宽度优先搜索，代价一致搜索。
设计启发函数时，对于两个可采纳的启发式函数$h_1,h_2$，若对任意节点，$h_1\le h_2$则称$h_2$比$h_1$准确。更准确的启发式函数拓展的节点会更少一些，而不精确的启发式函数会访问更多的节点。

1.3.3 IDA*

设置$f$的阈值，超过阈值的节点不再扩展；迭代执行以降低$A\ast$对内存的需求。
步骤：
1.初始化f的阈值t为$f(N0)$
2.Loop:
- 执行深度优先搜索，扩展$f(N)\le t$的节点
- 重新设置t为未拓展节点中$f$的最小值

优点：
- 完备+最优
- 内存要求比A*少
- 避免了未拓展节点集合的排序开销
不足：
- 无法充分利用内存，两次迭代之键只保留阈值t
- 无法避免重复访问不在路径上的点

改进：IDA*–> SMA*
将内存用光直至不能保存节点了，丢掉保存的一个高耗散，最旧的节点，再插入新的节点。

1.4 优化问题

优化问题是指 $\text{min}f(x)s.t.h(x)\le 0$，其中 $f(x)$是目标函数，$h(x)$是约束条件。

可以分为数值优化和组合优化两类问题。
将优化问题建模为搜素问题，其解法分为两种：

1.4.1 梯度下降法

对终止准则$T$、步长序列$\lambda$ 和初态 $X_0$,迭代更新
$$X_{t+1}=X_t-{\lambda }_t{\nabla }_{X}g\left(X_s\right),\text{ where }{\nabla }_{X}g=\left(\frac{\partial g}{\partial x_1},\frac{\partial g}{\partial x_2},\cdots ,\frac{\partial g}{\partial x_n}\right)$$
$g(x)$是n元实函数

• 第一步，设置超参数学习率（步长）
• 第二步，初始化初态
• 第三部，循环迭代

缺点：不能保证获得全局最优，且停止条件和学习率需要人工经验。

改进：不知道步长就多试几个步长来尝试；随机梯度下降，每一步都更新参数，而不是处理完整个训练集后更新

直线搜索
在一个预定的测试步长几何{…,-2c,-c,2c,…}中每轮选择其中使函数下降最快的那一个$\lambda \ast =ar{g}_{\lambda }mi{n}_g(X-\lambda {\nabla }_{x}g)$

随机梯度下降
每次迭代的梯度信息都随机地挑选一条训练数据计算，降低时间开销。

1.4.2 牛顿法

通过求解函数一阶导数$g^{\prime }(x)$的零点来找到函数极值对应的$X$。即每轮找$g^{\prime }(x)$在$X_n$的切线，以其与轴的交点作为新点$X_{n+1}$。
相当于寻找$g(X)$的根$X^{\ast }$使得$g(X^{\ast })=0$
离散的组合优化问题可用分支定界法解决。

1.4.3 爬山法

在每一个当前点，通过邻居算子$N(.)$向有限个邻接点算目标函数，并按照策略s向邻居点移动。
常见的策略$s$有：

• best-found 选择目标函数最小的邻点
• first-found 随机选择一个（比当前点）更好的邻点
• Random Walk 随机选择一个邻点（即使其目标函数大于当前点）

爬山法和梯度下降对应起来：

• best-found 离散版本的梯度下降
• first-found 离散版本的梯度下降

改进：

• 用不同随机初始值重启算法
• 在局部最优点增加扰动调整邻居算子
• 模拟退火（爬山+随机行走）

LBS/局部剪枝搜索
爬山法的并行改进，在初始时准备k个初态，迭代中可能有两种策略：
1.假设每个解有$l$个后继，每步都在所有$lk$个后继中选择最优的$k$作为当前的$k$个解
2.所有的$lk$个后继对应一个被选择的概率分布

1.4.4 模拟退火

通过一定概率接受“坏”移动来避免陷入局部最优，分类上介于全局搜索和局部搜索之间
超参数$p$决定了移动到坏解的概率，$p=e^{-\Delta g/T}$，$\Delta g$是解和它邻居的目标函数之差
$T$是温度，在整个搜索过程中温度会不断下降，理论可以证明,$T$下降的足够慢，那么算法找到最优解的概率逼近1.

1.4.5 Tabu搜索/禁忌搜索

不是原子算法，可以添加到其他局部搜素算法中。
核心：
1.维护一个长度有限（设为$k$）的最近历史解队列$Tab{u}_k$
2.搜索过程中，发现新解出现在$Tab{u}_k$中，直接放弃
3.$Tab{u}_k$能够在一定长度下防止陷入局部最优

1.4.6 (1+1)-EA

爬山法 的推广，此时邻居算子有一定概率能够将任何其他一个解算成邻居，该算子称为全局邻居算子。
不同解的跳转概率不一样，一般会系统地设置一个概率分布

类似爬山–>LBS 局部剪枝，也可以引入并行化，$\lambda$个(1+1)-EA并行执行。

EA算法的后继函数可以：
1.从当前解集的一个解产生后继，类似无线繁殖
2.从当前解集的两个或多个解产生后继，类似于有性繁殖

一些EA算法例子：
1.在当前k个解中，随机选择两个产生孩子，这称为交叉算子，这也是一般的进化算法
2.在当前k个解中，选择3个计算后继为$x=a+\zeta (b-c)$,得到差分演化算法
3.在当前k个解中，全部选择，用来估计一个分布，以用来描述整个解集。解集获得的过程我们成为从该模型中进行采样，这就是估计分布算法 EDA
4.在当前k各解中寻找后继时，考虑k个解的搜索历史，找到每个解历史最佳解和k个历史最佳解，以这些解为基础，设计速度函数，获得k个解的后继，即粒子群算法
5.在当前k个解中，每个解的后继都是以该解为初始解，执行局部搜索（例如使用爬山法），得到局部极值，然后以此局部极值为后继，即memetic算法
6.在状态空间的设计/编码上引入交叉/变异/选择算子，即遗传算法

1.4.7 蚁群算法

一种构造性算法（解的各个部分被逐步构造出来）
用分布式的策略来估计，让n只蚂蚁在有限状态机上爬行，并留下信息素，来标记爬行历史；
在评价好的状态转移边上，会有更多的蚂蚁在上面爬行并留下信息素

1.5 CSP约束满足问题

一般我们可以把CSP问题建模为搜索问题而不是优化问题

一个CSP问题是一个三元组$(X,D,C)$，其中$X$是一组变量；$D$是值域；$C$是一个约束组，包含了$m$个约束$X$分量间取值关系的计算公式。
$X_i$从$D_i$中取值，所有变量都给一个取值，形成一个赋值$v=(x_1,x_2,...,x_3)$可以参与约束$C$的计算，判断约束是否被满足

例子1:3-SAT
这里3表示每个约束是少于等于3个变量的析取式，我们需要求一个真值指派，使得每个析取式都为真。

例子2：地图着色
每个变量值域相同都是颜色种类例如(red,green,blue)，约束条件为任意两个相邻的变量色彩不一致

例子3:八皇后问题
8个变量，约束条件分为两类：1.每行一个皇后2.每个对角线一个皇后

分类：
有限和无线CSP:解的数目是否是有限（只要有一个变量的取值范围无限，则CSP问题无限，否则有限）

形式化为搜索：
有效赋值：对n个变量一个个赋值，不妨设前k个赋值完成，此时的赋值会使前k个变量相关的约束条件都满足
完全赋值：$k=n$，也就是n个变量都被赋值，使得所有约束条件都得到满足

五要素：
状态：有效赋值
初始状态：{},k=0
后继函数：在未赋值变量中挑选一个为第k+1个变量并对第k+1个变量赋值
目标测试：k=n
路径耗散：假设单步耗散为1

CSP问题的特性在于可交换性
变量赋值的次序和完全赋值的可达性无关，因此，CSP问题在解决时有以下便利：
1.扩展节点时可以任意选择一个未赋值的变量来扩展节点
2.不需要存储到达当前节点的路径，因此可以用回溯算法

改进：
1.前向检验：提前检测出冲突，以八皇后为例，一旦赋值了某个变量，那么按照约束就可以吧其他变量的某些取值从值域中去掉
2.启发式的选择下一个赋值的变量，选择约束最强/残留值域最小的变量，使得分支因子最小，后继最少
3.给残存的值域排序，对不同的v做前向检验
4.约束传播（课后了解）

2. 机器学习

定义：对于现实世界的一个过程/机制/方法的抽象$f$，我们从训练数据中归纳出一个学习器，该学习器实现了函数$f$的一个近似$h$，这就是我们的模型/假设。

建模过程分为两步：选择模型和训练

评价$h$的优劣时有以下指标：

• 准确性 即$h,g$之间的近似度
• 复杂性 $h$的描述长度，应保证在合理有效范围内以得到可满足的时空代价
• 完备性 $h$是否对$f$的每个输入都定义了一个响应

3. 线性回归

用简单的线性函数$h(x)=Wx+b$来近似$f$.
这里我们将输入变量做一次变换，转换为n维向量（例如把在$x$向量中加入一个1以消除常数项$b,x\to \varphi (x)$），那么我们讨论线性$h$的标准式就是$h(x)=W\varphi (x)$

损失函数：
绝对损失：$|f(x)-h(x)|$
平方损失：$(f(x)-h(x){)}^2$
计数损失：$1\ast (f(x)\ne h(x))$

将训练集上所有x的损失加起来，得到代价(cost)函数
训练集损失之和-训练误差
测试机损失之和-经验风险

最小损失函数：

• 采用平方损失函数：近似寻找均值，综合所有样本影响
• 采用绝对损失函数：近似寻找中值，抵抗离群点影响

方法：

• 平方损失函数时可以用最小二乘法
• 梯度下降法

4.线性分类

依然使用$h(x)=W\varphi (x)$，这是可以将分数离散化为分类，例如$h(x)\ge 0$分为正，$\le 0$分为负。

几何意义，对于输入存在的空间，找到一个超平面，使其能够将不同类的输入数据点隔开。

4.1 间隔

平面外（数据）点P到平面距离的$|W|$倍：
$$dist(P,\alpha )=(P.W+b)/\Vert W\Vert$$
间隔为负表示分类错误，越小表示错得越厉害

基于间隔定义损失函数
符号函数硬判决 没有梯度信息，无法应用梯度下降法
软判决 采用logistic损失函数，$log(1+e^{-W\varphi (x)y}),得到\ast \ast logistic回归\ast \ast$
关键部分梯度变为非0 使用hinge损失函数$max(1-W\varphi (x)y,0)$，要注意到我们在间隔在(0,1)时定义了非0的损失，这迫使我们在优化的时候要考虑间隔大于等于1，即正确的分类判断哟啊足够有说服力。

4.2 SVM

从hubfe损失函数出发，我们也可以替换梯度下降法，从而导出SVM算法。

首先定义代数间隔：
$$\alpha -margin\triangleq W\varphi (x)y$$
几何间隔：
$$g-margin\triangleq \frac{W\varphi (x)y}{\Vert W\Vert }$$
我们定义损失函数，要让代数间隔$\ge$1，并使得hinge损失最小
那么将其用于优化问题的语言描述：

• 约束条件：找到一个分类面$h(x)$，它能够分开所有的训练数据，并是任意一个数据点到分类面的距离（几何间隔）大于等于$\frac{1}{|W|}$，优化目标$\frac{1}{|W|}$越大越好
• 这里优化问题来自对分类问题的几何意义的理解和形式化，该问题追求“结构风险最小化”，这不同于我们之前定义的训练误差最小化和经验风险最小化

当超平面（决策边界）确定后，我们可以发现有些店很重要，他们是距离超平面最近的点，这些点被称为支持向量。下面我们介绍支持向量算法SVM。

线性SVM，该方法适用于线性可分的数据集：
$$min\Vert W\Vert s.t.1-(Wz+b)y\le 0$$
求解时，我们利用拉格朗日乘子法，将约束转化为目标函数中的参数。
我们对每个训练样本，对应一个非负乘子${\alpha }_i\ge 0$，代入约束：
$$[1-(W{x}_i+b)y_i]{\alpha }_i=0$$
意义：离超平面最近的数据，因为$1-(W{x}_i+b)y_i=0$ 所以${\alpha }_i$可以随意取值，非最近的数值，则令其${\alpha }_i$为0.

将所有的约束条件加起来，得到
$$\sum _i[1-(W{x}_i+b)y_i]\le \sum _i[1-(W{x}_i+b)y_i]{\alpha }_i=0$$
将其加到目标函数上：
$$L(W,b,a)\triangleq \Vert W\Vert +\sum _i[1-(W{x}_i+b)y_i]{\alpha }_i$$

4.3 SMO算法

序惯最小化算法
假设数据集有m个样本/ 训练数据

• 每次固定m-2个乘法因子${\alpha }_i$ 让其他两个任意变化，寻找两个任意变化乘法因子的最佳值；
• 循环迭代调整固定不同的m-2个乘子因子$\alpha$，直到收敛
• 局部搜索去寻找自由变量${\alpha }_i$就是对应的支持向量及其非零的${\alpha }_i$
• 训练过程中，尽量避免每次循环迭代都扫描一遍训练数据（因此不适用海量数据/样本的学习问题）

5.非线性处理

5.1 非线性SVM

当数据线性不可分时，线性SVM不可用，需要使用核函数

核函数并不把数据x映射到高维特征空间，他是高维特征空间的内积计算公式

5.2 KNN

训练样本数目越多，分类精度越高
训练就是将所有样本存储，预测时计算新数据的K个最近（训练样本的）邻居，以K个邻居占多数的类标号作为新数据类标号。

过拟合：训练误差小而测试风险大
泛化能力：给定训练集误差，在测试集上降低误差的能力

5.3 决策树

决策树的树形结构，每个节点是一个简单的决策器。
训练和构造：

• 初始时刻构建树根，拥有所有的训练数据
• 对每个节点，选择数据的某属性来分裂剩余数据集
• 当某节点的所有训练数据都属于同一类时，划分结束，生成叶节点

关键在于如何选择分割的属性
利用信息熵：$H(N)=-{\sum }_i{p}_i\log (p_i)$
$p_i$是节点N中拥有数据集D中属于第i类数据在D中占比。

5.3.1 ID3算法

在给定节点对所有属性的不同取值，计数其分裂出子节点数据集$D_i$
对所有自己点计算$H(N_i)$
然后计算信息增益$IG(N|A_i)=H(N)-\sum \frac{|N_I|}{N}H(N_i)$
选择信息增益大的属性来分裂

5.3.2 C.5算法

信息增益率：避免信息增益倾向选择值多的属性：
$$\frac{IG(N|A_t)}{H(N|A_t)}=\frac{H(N)-H(N|A_t)}{H(N|A_t)}$$
信息增益率+对连续属性的处理 就是C4.5算法

5.3.3 CART算法

Gini指数
$$i(N)=\sum _{i\ne j}{p}_i{p}_j=1-\sum _i{p}_i^2$$
本质上还是找到一个属性使得分割数据集后，剩下的Gini指数最小
这里是要将节点不停二分，所以对于多值域属性，需要一个“值域二分”的过程来划分数据集。
值域二分的过程的时间复杂度是值域大小的指数函数。

这就是CART算法。

6. 神经网络

6.1 特征提取函数

设计特征提取函数的通用方法：

• 定义输入x的各个单项式构成的向量为特征$\varphi (x)$
• 存在问题：单项式的最高次数难以确定（高了过拟合/低了欠拟合）

处理非线性：

• $W,\varphi (x)$ 都是值向量，它们做内积运算得到分数score，是线性运算
• 非线性部分，可以用非线性函数获得

6.2 激活函数

是一种对score做的非线性映射，常见的激活函数有Sigmod/ Tanh /Relu

ReLu的优点：

• 稀疏激活性：只激活少量神经元
• 单侧抑制和相对宽阔的兴奋边界：降低梯度消失的影响

神经网络的问题：训练代价大，收敛速度慢

基本概念：
输入层、隐层、输出层、权值、单元、激活函数、训练样本、隐层输出、数据特征

构建好网络结构后，下面最重要的就是如何去学习权值：
一般我们使用反向传播来倒推权值的更新量。

偏导数计算图

6.3 CNN

CNN特点：对连接方式做了约简处理，引入卷积核来做特征提取，起到权值共享

CNN池化作用：聚合特征，降维，减少计算量

6.4 RNN

RNN公式：$s_t=f(U{x}_t+W{s}_{t-1})$

6.5 LSTM

遗忘门+输入门 --> 确定信息如何删除和增加
输出门—> 什么信息需要被输出

$f_t=\sigma (W_f\cdot [h_{t-1},x_t]+b_f)$
$i_t=\sigma (W_i\cdot [h_{t-1},x_t]+b_i)$
${\tilde{C}}_t=\sigma (W_C\cdot [h_{t-1},x_t]+b_C)$
$C_t=f_t\ast C_{t-1}+i_t\ast {\tilde{C}}_t$
$o_t=\sigma (W_o\cdot [h_{t-1},x_t]+b_0)$
$h_t=o_t\ast tanh(C_t)$

7 贝叶斯网络

贝叶斯网络可以看做约简了的联合概率质量函数（PMF）。
换言之，通过贝叶斯网络，我们利用网络结构声明的随机变量的独立性和贝叶斯公式，可以得到网络中节点的PMF的乘积表达式。

在贝叶斯的网络结构图中，不直接相连的节点之间条件独立。
$$p(A)=\frac{p(AB)}{p(B)}$$

两类特殊的贝叶斯网络：

7.1 朴素贝叶斯

在朴素贝叶斯中，除了最终的结果（类标签$X_1$），其他随机变量均互相独立，而所有其他随机变量都有一条连接到类标签上。
$$p(X_1,X_2,...,X_n)=p(X_1)p(X_2|X_1)...p(X_n|X_1)$$

7.2 隐马尔可夫模型

设置$H=(H_1,...,H_n),E=(E_1,...,E_n)$，其中H是隐层变量，E是可观测的变量，$E_i$直接由$H_i$决定，而$H_i$由$H(i-1)$决定。
$$p(H=h,E=e)=p(h_1)\prod _{i=2}^{n}p(h_i|h_{i-1})\prod _{i=11}^{n}p(e_i|h_i)$$

确定网络结构的方法：

• 专家建模
• 从数据集中自动学习
• 二者结合

7.3 求解概率质量函数

给定数据集，网络结构，求个边缘/条件概率质量函数
方法：利用蒙特卡洛逼近，将数据集视为粒子集，然后计算网络结构需要的各种边缘/条件概率质量函数/表

例子1：
两变量 $p(t,r)=p(t)p(r|t)$
数据集 $D=(c,4),(c,4),(c,5),(s,1),(s,5)$
随机向量 $X=T,R$，其中 T ∈ { c , s } T \in \{c,s\} T∈{c,s} 表示餐馆类型 ,$R=1,2,3,4,5$ 表示对一个餐馆的评价，

统计频率到边缘概率$p(T)=(0.6,0.4)$
令$T=c,s$ 时分别统计各个打分的频率得到条件概率
$p(R|T)=((0,0,0,0.67,0.33),(0.5,0,0,0,0.5))$

如果数据量较少，那么有的随机变量的值域的某些值可能不会被覆盖，也就导致条件概率函数中会出现大量的0，这时我们可以采用拉普拉斯平滑来解决这个问题。

简单的说，我们在统计每个值出现的次数时，将计数器的初始值设定为非0即可。
以上面的例子为例，假设平滑前数据集为$D=\{(c,4),(c,4),(c,5),(s,1),(s,5)\}$，可以看到类型为c的餐馆缺少评分为1,2,3的数据，s的缺少2,3,4。那么我们可以设计计数器初始值为1，即覆盖了所有类型*评分，然后再开始真实的统计。

例子2：
含 隐变量的例子
这里我们设一个隐变量$H=G$和两个显变量$E=R_1,R_2$，由于我们观测不到隐变量，因此数据集类似这样:
$$D=\{(?,4,5),(?,4,4),(?,5,3),(?,1,2),(?,5,4)\}$$

这里的基本思想是：将条件概率质量函数视为参数，在这些参数的取值中找到一组最好的参数，使得出现观测到输出变量（已知数据集）的概率最大。

7.4 EM算法

EM算法是一种常见的隐变量学习的算法，这里我们将隐变量和PMF都作为未知变量，并轮流更新它们。

• E-step
• 对H所有的可能取值$h$，计算PMF，并挑选能够使得$p=(E=e|h,cp{t}_i)$最大的$h\ast$来更新$H$（极大似然估计）
• M-step
• 利用上一步E-step得到的$H$来更新PMF

EM 两部分循环迭代直到收敛
例子：k-means聚类，贝叶斯网络推理

7.5 编码实现概率推理

给定完整的PMF（表格），用程序代码描述某个特定概率值的计算。
需要计算的概率值分为两类：边缘概率/条件概率

• 对于边缘概率$p(B)$直接查询边缘概率PMF表格
• p(B|XXX)连接表中满足XXX条件的那些行，并归一化

形式化庙湖，我们令$Q$为查询,$E$为证据（数据集）,$M$为无关因素
随机向量$X=E\bigsqcup Q\bigsqcup M$

• 首先在表中将$E=e$的行留下
• 然后将无关因素$M$去掉，如果有些行的$M$值不一致，可以将这些行概率求和来合并（减小时间代价，不一定必需）

伪代码描述：

c1,c2=0,0 # 置初始计数为0
for i in data:if i satisfy (E=e):	# 满足条件E=ec1 += p(X_i)if i satisfy (Q=q):	# 满足查询c2 += p(X_i)
return c1/c2 # 返回概率

8 马尔可夫决策过程 MDP

马尔可夫决策过程和经典搜索不同

经典搜索	MDP
行动是确定地让搜索沿一条边前进	行动随机地让搜索沿多条边前进
解是一条路径或是状态序列	解不是路径而是策略：一组从状态到行动的映射关系

• $S:$状态空间
• 初态：$s_0$
• 行动：Action(s)，给定$s\in S$的合法行动几何
• 状态转移概率：$T(s,a,s^{\prime })$，从状态$s$出发，采用行动$\alpha$，导致结果状态$s^{\prime }$的概率
• 奖励：$Reward(s,a,s^{\prime })$，状态$(s,a,s^{\prime })$得到的收益
• 目标测试：$isEnd(s)$

与经典搜索中五要素对比：

• 行动+状态转移概率=后继函数
• 奖励=路径耗散
• 马尔科夫性：行动的确定只和当前的状态$s$有关

以随机数游戏为例：
该游戏为回合制，每个回合开始时有两种选择：继续游戏或者退出游戏；
选择退出游戏则可以得到￥15，游戏结束
继续游戏会得到￥4，并产生一个0~9的随机数，若随机数为0,1,2 则游戏结束，否则继续下回合
目标是获得更多的钱

• S={游戏中，结束}
• s_0=游戏中
• 行动：Action(s)={继续，退出}
• 态度转移T(s,继续,s’)=（1,0;0.3,0.7）和T(s,退出,s’)=(1,0;1,0)
• 奖励Reward(s,继续,s’)=（0,0;4,4）,Reward(s,退出,s’)=
  (0,0;15,0)
• 目标测试isEnd(s) s==结束

8.1 MDP的解

• MDP的解被称为策略，映射表
• 通常会造成许多从初态到终态的随机路径
• 路径数目是状态数目的指数函数

行动收益：定义为改行动导致状态转移带来的奖励$Reward=U(s,a,s^{\prime })$，收益获得的概率是$T(s,a,s^{\prime })$，则期望收益$\sum U(s,a,s^{\prime })T(s,a,s^{\prime })$
路径收益：一条路径上所有行动带来的收益之和
策略收益：一个策略可能会造成多条不同出现概率的路径，所有路径的期望收益即策略收益

如何计算策略收益：

• 枚举：枚举每个随机路径并计算收益和概率并加权求和。时空要求大，无法解决无限长路径问题

• 递推：找到递推公式后解之$V\pi (s)={\sum }_{s^{\prime }\in S}T(s,a,s^{\prime })[U(s,a,s^{\prime })+V_{\pi }(s^{\prime })]$，过程：

  • 初始化策略收益$V_{\pi }(s)=0$
  • 重复T次
  • • 对每个状态$s\in S$，执行：
  • • • 利用递推方程循环更新 $V\pi (s)={\sum }_{s^{\prime }\in S}T(s,a,s^{\prime })[U(s,a,s^{\prime })+V_{\pi }(s^{\prime })]$
  • 当相邻两次更新之间差值足够小时停止算法

8.2 找到最优策略 Q-value

为了找到最优策略，这里我们引入一个Q-value
Q-value:$Q_{\pi }(s,a)$ 定义为从状态$s$出发，采用行动$\alpha$后继续采用策略$\pi$的价值/收益；

和$V_{\pi }$的区别：在状态s时，采用了不同的行动，故$V_{\pi }(s)$ 仅仅是$\pi ,s$的函数，而$Q_{\pi }(s,a)$是$\pi ,s,a$ 的函数

策略改进算法：
1.输入策略$\pi$，得到一个更好的策略${\pi }_{new}$，充分利用马尔科夫性
2.对任意状态s，执行下述操作：
2.1 对不同行动$a\in Action(s)$,计算$Q_{\pi }(s,a)$
2.2 更新${\pi }_{new}=\arg ma{x}_{a\in Action(s)Q_{\pi }(s,a)}$

类似爬山法，把状态s所有可能行动都尝试一遍

结合策略评估和策略改进，我们得到值迭代算法来计算最优测了：
1.对所有状态s初始化$V_{opt}^0(s)\leftarrow 0$;
2.for $t=1,2,...,T_0$次：
2.1 对每个状态s,执行：
$$V_{opt}^t(s)\leftarrow \underset{a\in \mathrm{Action}(s)}{\max }\sum _{s^{\prime }}T\left(s,a,s^{\prime }\right)\left[\mathrm{Reward}\left(s,a,s^{\prime }\right)+V_{opt}^{t-1}\left(s^{\prime }\right)\right]$$

折扣因子：
我们在计算路径收益时，对未经历的路径的收益乘一个折扣因子$\lambda$ ，离现在越远，收益打折越大。
那么递推方程改为：
$$V_{\pi }=\sum _{s^{\prime }}T\left(s,a,s^{\prime }\right)\left[\mathrm{Reward}\left(s,a,s^{\prime }\right)+V_{\pi }\left(s^{\prime }\right)\right]$$

总结

9 强化学习

在现实生活中，我们通常不知道状态转移概率和奖励的细节，因此MDP有很大的局限性，强化学习由此而生。

MDP	强化学习
转移概率和奖励情况已知，离线	无人知道转移概率和奖励，在线
决策判断都可以仿真	需要花费代价去搜索未知（转移概率和奖励）
$f$已知	$f$未知

强化学习算法框架：

• for t = 1,2,…
• • 选择行动$a_t=\pi (s_{t-1})$
• • 收集反馈奖励$r_t$，获得新状态 $s_t$
• • 更新参数

已知：$s_0,a_1,r_1,s_1,a{2}_{r}2,...,a_n,r_n,s_n$
求参数：$T(s,a,s^{\prime })$ 和 $U(s,a,s^{\prime })$

9.1 蒙特卡洛方法

• 从已知数据的任何状态开始$(s,a,r,s^{\prime })$被视为一组数据，原数据序列被分割为n段
• 计数，并计算$\hat{T}(s,a,s^{\prime })=\frac{M(s,a,s^{\prime })}{M(s,a)},\hat{U}(s,a,s^{\prime })=\frac{{\sum }_r(s,a,r,s^{\prime })}{M(s,a,s^{\prime })}$
• 用$\hat{T}$近似$T$,$\hat{U}$近似$U$

这类方法被称为基于模型的蒙特卡洛算法。它们对于数据量要求大，还要求样本数据满足独立性假设。

9.2 模型无关方法

即不去揣摩状态转移函数和奖励，直接评估策略

定义引入折扣因子的时刻t的收益:$u_t=r_t+\lambda r_{t+1}+{\lambda }^2{r}_{t+2}+...$
用$u_t$的均值估计当成$Q_{\pi }(s,a)$:即将$u_t$按$(s,a)$不同取值分组，然后求组内均值。

算法描述：

• 对任意时刻t,对应数据段$(s,a,r)$;
• • 计算出$(s,a,u_t)$
• • 令$\xi$=1/(更新次数+1)
• • 更新$Q_{\pi }(s,a)=(1-\xi )Q_{\pi }(s,a)+\xi u_t$

求最优策略时第一种方法类似于MDP，第二种方法就是Q学习

10 博弈和对抗性搜索

博弈的基本要素：

• 参与者：大于等于2
• 策略集：可采取的行动集合
• 收益：$P_i(a_1{j}_1,...,a_n{j}_n)$表示参与者在所有人策略为$(a_1{j}_1,...,a_n{j}_n)$时的收益

10.1 静态博弈

完美信息：每个参与者对博弈信息完美了解
静态博弈：所有参与者同时选择策略并行动
理性：所有人都追求自己利益最大化
独立：参与者之间不协商
占优策略：对其他参与者的所有策略组合而言的最佳应对（可以取等号即可能有多个策略达到最佳，不取等号时仅有一个策略到达最佳，称严格占优策略）

博弈问题的求解可以如下（对于两名理性参与者）：
1.若两人都有严格占优策略，那么两人均会采取该策略
2.若只有一个人有严格占优策略，那么此人采用该策略，另一个人采用此策略的最佳应对
3.两人都没有严格占优策略，寻找纳什均衡

若无纳什均衡，比如下面的情况：
零和博弈：参与者收益之和为零，即若参与者收益增加，那么一定有其他参与者收益减少
此时引入混合策略：预测对方采用策略的概率并据此确定自己的策略，同时避免让对方了解自己采用不同策略的概率

10.2 动态博弈

参与者行动不是同时的（例如下棋）
MDP可以看作完美信息下的动态博弈：每个参与者知道所有公共信息，将对手视为MDP建模中无法观测和了解的位置因素。

下棋（非完美信息下动态博弈）可以看作是强化学习：不知道转移概率和每一步的奖励，需要逐步了解和学习。

博弈问题也可以建模为搜索问题：

• 状态：参与者的行动/策略及其各自对应的收益；
• 后继函数：参与者可能的各种新策略；
• 初态：随机或某个给定初态；
• 终态：均衡态（不管任何一个参与者如何调整策略/行动，各自的收益不再增加）；
• 路径耗散：单步路径耗散为常数c