人工智能的三大学派

人工智能主要学派分为符号主义、连接主义、行为主义。

• 符号主义（Symbolicism）学派：认为人工智能源于数理逻辑。该学派将数学严格公理化，从公理出发，由逻辑推理得到引理，定理，推论。

• 连接主义（Connectionism）学派：认为人工智能源于仿生学，特别是对人脑模型的研究。

• 行为主义（Actionism）学派：来源于控制论及“感知—动作”型控制系统。该学派认为智能取决于感知和行动，人工智能可以像人类智能一样逐步进化，以及智能行为只能在现实世界中与周围环境交互作用而表现出来。

  $$\begin{array}{|c|c|c|} \hline \text { 学习模式 } & \text { 优势 } & \text { 不足 } \\ \hline \text { 用规则教 } & \begin{array}{c} \text { 与人类逻辑推理相似, 解 } \\ \text { 释性强 } \end{array} & \begin{array}{c} \text { 难以构建完备的知识规则 } \\ \text { 库 } \end{array} \\ \hline \text { 用数据学 } & \text { 直接从数据中学 } & \begin{array}{c} \text { 以深度学习为例: 依赖于 } \\ \text { 数据、解释性不强 } \end{array} \\ \hline \text { 用问题引导 } & \begin{array}{c} \text { 从经验中进行能力的持续 } \\ \text { 学习 } \end{array} & \begin{array}{c} \text { 非穷举式搜索而需更好策 } \\ \text { 略 } \end{array} \\ \hline \end{array}$$

数据

智能之根：数据

• 人工智能的本质是从数据中挖掘知识，实现机器智能化的过程。
• 样例学习是智能体的基本学习方式之一。

数据的认识

• 数据概念：数据对象及其属性的集合。
• 属性（变量、特征）：对象的属性或特性。
• 属性值：属性分配的数字或符号。属性值不一定反映出属性
• 数据类型：类别属性、顺序属性、区间属性、比率属性。

数据集的类型

• 记录型数据（Record Data）：包含固定属性集的记录集合。
• 图/网络数据（Graph Data）：如社交网络、分子结构等。
• 有序数据（Ordered Data）：序列数据、时间序列数据、时空数据等。

数据质量

数据的质量决定了算法的上限

• 数据质量问题：噪声、异常值、缺失值、重复数据。
• 数据预处理：聚合、采样、降维、离散化、属性转换、特征创建、特征子集选择。

数据预处理技术

• 聚合（Aggregation）：将多个属性或对象合并为单一属性或对象。
• 采样（Sampling）：数据选择的主要技术，用于初步调研和最终分析。

• 降维（Dimensionality Reduction）：减少数据集的维度，避免“维度的诅咒”。

  • 数据的维度越高，数据分散的就越分散。很多机器学习的方法都是基于距离的，在高维的表现不好，所以要将维度下降下来。常用的有PCA，T-SNE，SVD。

T-SNE（t-Distributed Stochastic Neighbor Embedding）是一种非线性降维技术，通常用于高维数据的可视化。它是由Laurens van der Maaten和Geoffrey Hinton在2008年提出的。T-SNE的主要目的是将高维空间中的数据点映射到低维空间（通常是2维或3维），同时保持原始数据中的相似性结构。
T-SNE的特点包括但不限于：

1. 非线性降维：与传统的线性降维技术（如PCA）不同，T-SNE能够捕捉数据中的非线性结构。
2. 相似性保持：T-SNE尝试在低维空间中保持高维空间中数据点之间的相似性。这意味着在高维空间中相似的数据点在低维空间中仍然相似，而不相似的数据点在低维空间中则被拉开。

• 离散化（Discretization）：将连续属性转换为分类属性。
• 属性转换（Attribute Transformation）：对属性值集映射到新的替代值集。
• 特征创建（Feature Creation）：从原始数据创建新特征，以更有效地捕捉重要信息。
• 特征子集选择（Feature Subset Selection）：减少数据维度，剔除冗余和不相关特征。

从数据到智能的不同理解方式

• 符号主义（Symbolism）：使用符号系统和规则来理解数据。
• 连接主义（Connectionism）：使用网络和学习算法来理解数据。
• 行为主义（Behaviorism）：使用环境和反馈来理解数据。

知识的表示与推理

人工智能的本质是知识的表示

• 人工智能的成功与否取决于其知识表示的清晰度。

知识与数据、信息的区别：

• 数据：单独的事实、信号、符号，是信息的载体。
• 信息：由符号组成，如文字和数字，赋予符号一定的意义。
• 知识：在信息的基础上增加上下文信息，提供更多意义。

知识表示：将知识符号化并输入到计算机的过程和方法。

知识表示的两种基本观点：

• 陈述性知识表示：知识表示与应用分开处理。
• 过程性知识表示：知识表示与应用结合，知识与程序融合。

现代逻辑学

命题逻辑

命题：具有真假意义的陈述句。

命题逻辑的组成：

• 原子命题：最基本的命题。
• 复合命题：由联结词、标点符号和原子命题复合构成。

具体的公式参考离散数学以及人工智能课件

归结推理

1. 子句

在归结推理中，子句是一个关键概念。一个子句是逻辑公式的一个特殊形式，可以表示为：

其中，每个 $ L_i $ 都是一个文字（literal），文字可以是原子公式或其否定。子句也可以是空的，表示为 $\square$ 或 $\bot$，这在逻辑中代表矛盾或“假”。

特点

• 子句可以包含任意数量的文字。
• 子句中的文字可以是正的（原子公式）或负的（原子公式的否定）。
• 空子句表示逻辑矛盾。

  2. 谓词公式转子句集

要将下列谓词公式化为子句集：

1. 消去蕴涵符号
   将原公式中的蕴涵符号（$\rightarrow$）转换为或（$\vee$）与非（$\wedge$）的组合：

   $$\forall x\{\neg[\neg P(x) \vee \neg Q(x)] \vee \exists y[S(x, y) \wedge Q(x)]\} \wedge \forall x[P(x) \vee B(x)]$$

2. 移动否定符号
   将否定符号（$\neg$）移到每个谓词前：

   $$\forall x\{[P(x) \wedge Q(x)] \vee \exists y[S(x, y) \wedge Q(x)]\} \wedge \forall x[P(x) \vee B(x)]$$

3. 变量标准化
   为了避免变量冲突，对变量进行标准化处理：

   $$\forall x\{[P(x) \wedge Q(x)] \vee \exists y[S(x, y) \wedge Q(x)]\} \wedge \forall w[P(w) \vee B(w)]$$

4. 消去存在量词
   设 $y$ 的Skolem函数是 $f(x)$，则：

   $$\forall x\{[P(x) \wedge Q(x)] \vee[S(x, f(x)) \wedge Q(x)]\} \wedge \forall w[P(w) \vee B(w)]$$

5. 化为前束型
   将公式化为前束型，即将量词移至公式最前面：

   $$\forall x \forall w\{\{[P(x) \wedge Q(x)] \vee[S(x, f(x)) \wedge Q(x)]\} \wedge[P(w) \vee B(w)]\}$$

6. 化为标准形
   将公式化为标准形，包括整理合取与析取：

   $$\begin{array}{l} \forall x \forall w\{\{[Q(x) \wedge P(x)] \vee[Q(x) \wedge S(x, f(x))]\} \wedge[P(w) \vee B(w)]\} \\ \forall x \forall w\{Q(x) \wedge[P(x) \vee S(x, f(x))] \wedge[P(w) \vee B(w)]\} \end{array}$$

7. 略去全称量词
   在这一步中，我们去掉全称量词：

   $$Q(x) \wedge[P(x) \vee S(x, f(x))] \wedge[P(w) \vee B(w)]$$

8. 消去合取词
   将公式分解为子句集，每个合取词对应一个子句：

   $$\{Q(x),(P(x), S(x, f(x))),(P(w), B(w))\}$$

9. 子句变量标准化
   对子句中的变量进行标准化处理：

   $$\{Q(x),(P(y), S(y, f(y))),(P(w), B(w))\}$$

3. 归结式

归结式（Resolution Inference Rule）是归结推理的核心。它是一个推导规则，用于从两个子句推导出一个新的子句。归结式的应用基于以下原则：

• 选择两个子句，它们至少有一个共同的文字，且在一个子句中为正，在另一个中为反。
• 删除这两个子句中的共同文字及其否定。
• 合并剩余的文字形成一个新的子句。

  归结式的表示

  如果 $ C_1 $ 和 $ C_2 $ 是两个子句，并且它们有一个共同的文字 $ L $ 和它的否定 $ \neg L $，则归结式可以表示为： $$C_1, C_2 \rightarrow C_1 \cup C_2 - \{L, \neg L\}$$ 其中 $ C_1 \cup C_2 $ 表示两个子句文字的并集，$ -\{L, \neg L\} $ 表示去除共同的文字和它的否定。

假设有两个子句：

• $ C_1: A \vee B \vee \neg C $
• $ C_2: \neg A \vee D $
  它们可以通过归结式来推导出一个新的子句：
• 共同文字：$ A $ 和 $ \neg A $
• 应用归结式：删除 $ A $ 和 $ \neg A $，得到新的子句 $ B \vee \neg C \vee D $

4. 归结推导

命题逻辑

1. 前提转换：将所有前提转换为子句的合取范式。
2. 归结：应用归结规则，选择两个子句进行归结，生成新的子句。
3. 重复归结：使用新生成的子句重复归结步骤。
4. 检查结果：检查是否生成了空子句。如果生成了空子句，则推导成功（说明之前的亲本子句也是假的，一直向前传递）；如果没有生成空子句且无法继续归结，则推导失败。

谓词逻辑

谓词逻辑在归结的时候还可能需要进行置换和合一。

置换和合一

置换：可以用$t_1 /v_1$或$v_1=t_1$来表示用$t_1$置换$v_1$​

• $t_i$不允许包含与$v_i$有关的项
• 不允许$v_i$循环出现在另一个$t_i$​中作置换

合一：存在置换$\lambda$使得$\mathrm{F}_{1} \lambda=\mathrm{F}_{2} \lambda$，则$\lambda$称为一个合一。（不唯一）

最一般合一：定义设 $\sigma$ 是公式集$F$的一个合一，如果对任一个合一 $\theta$ 都存在一个置换 $\lambda$ , 使得 $\theta=\sigma\circ \lambda$ 则称 $\sigma$​​ 是一个最一般合一（MGU）。（唯一）

最一般合一算法

1. 令 $k=0$, $F_k=F$, $\sigma_k=\varepsilon$。其中 $\varepsilon$ 是空置换。

2. 若 $F_k$ 只含一个表达式，则算法停止，$\sigma_k$ 就是最一般合一。

3. 找出 $F_k$ 的差异集 $D_k$。

4. 若 $D_k$ 中存在元素 $x_k$ 和 $t_k$，其中 $x_k$ 是变元，$t_k$ 是项，且 $x_k$ 不在 $t_k$ 中出现，则置：

   $$\begin{align*} F_{k+1} & = F_k \{ t_k / x_k \} \\ \sigma_{k+1} & = \sigma_k \{ t_k / x_k \} \\ k & = k + 1 \end{align*}$$

   然后转 (2)。若不存在这样的 $x_k$ 和 $t_k$ 则算法停止。

5. 算法终止，$F$​的最一般合一不存在。

5. 归结实例

设A、B、C三人中有人从不说真话，也有人从不说假话。某人向这三人分别提出同一个问题：谁是说谎者？以下是他们的回答：

• A答：“B和C都是说谎者”；
• B答：“A和C都是说谎者”；
• C答：“A和B中至少有一个是说谎者”。

求谁是老实人，谁是说谎者？

先写出公式：

然后，我们把上述回答公式化成子句集S：

1. ¬T(A) ∨ ¬T(B) （如果A不是老实人，则B不是老实人）
2. ¬T(A) ∨ ¬T(C) （如果A不是老实人，则C不是老实人）
3. T(C) ∨ T(A) ∨ T(B) （C、A、B中至少有一个是老实人）
4. ¬T(B) ∨ ¬T(C) （如果B不是老实人，则C不是老实人）
5. ¬T(C) ∨ ¬T(A) ∨ ¬T(B) （C、A、B中至少有一个不是老实人）
6. T(A) ∨ T(C) （A或C是老实人）
7. T(B) ∨ T(C) （B或C是老实人）

下面先求谁是老实人。把¬T(x) ∨ Answer(x)并入$S$得到$S_1$。即多一个子句：

1. ¬T(x) ∨ Answer(x) （如果x不是老实人，则x是答案）

应用归结原理对$S_1$进行归结：

1. ¬T(A) ∨ T(C) （子句1和子句7归结）
2. T(C) （子句6和子句9归结）
3. Answer(C) （子句8和子句10归结）

所以C是老实人，即C从不说假话。

6. 归结策略

宽度优先、支持集策略、线性输入策略（不完备）、单文字策略（不完备）、祖先过滤策略。

删除策略：纯文字删除法、重言式删除法、包孕删除法。

知识图谱

知识图谱是由一些相互连接的实体及其属性构成的

三元组是知识图谱的一种通用表示方式：

• (实体1-关系-实体2)：中国-首都-北京
• (实体-属性-属性值)：北京-人口-2069万

知识库推理包括基于符号的推理和基于统计的推理。

知识图谱推理：FOIL算法

1. 初始化：选择一个目标谓词（例如，Father(X, Y)），这是我们想要学习推理规则的谓词。

2. 前提约束谓词的选择：从知识图谱中选择可能作为目标谓词前提约束的谓词（例如，Mother(X, Y), Sibling(X, Y) 等）。

3. 正例和反例的构造：根据知识图谱中的信息，构造出目标谓词的正例和反例。正例是已知满足目标谓词的实体对，而反例是不满足目标谓词的实体对。

4. 信息增益计算：对于每个候选的前提约束谓词，计算其加入推理规则后的信息增益值。

   $$\text {增益值 }=\widehat{m_{+}} \cdot\left(\log _{2} \frac{\widehat{m_{+}}}{\widehat{m_{+}}+\widehat{m_{-}}}-\log _{2} \frac{m_{+}}{m_{+}+m_{-}}\right)$$

5. 选择最佳前提：基于信息增益值，选择最佳的前提约束谓词加入到推理规则中。

6. 推理规则的构建：将选定的前提约束谓词与目标谓词结合，形成新的推理规则（例如，Couple(X, Z) -> Father(X, Y)）。将训练样例中与该推理规则不符的样例（正例和反例）去掉。

7. 规则评估：评估新构建的推理规则是否满足所有正例并且不覆盖任何反例。如果满足，规则学习完成，得到最终的推理规则；如果不满足，返回步骤5，选择另一个前提约束谓词并重复过程。

搜索技术

盲目搜索

盲目搜索有三个特点：

• 这些策略都采用固定的规则来选择下一需要被扩展的状态
• 这些规则不会随着要搜索解决的问题的变化而变化
• 这些策略不考虑任何与要解决的问题领域相关的信息

搜索算法的重要特征：

• 完备性（Completeness）: 搜索算法是否总能在问题存在解的情况下找到解
• 最优性（Optimality）: 当问题中的动作是需要成本时，搜索算法是否总能找到成本最小的解
• 时间复杂度（Time complexity）: 搜索算法最多需要探索/生成多少个节点来找到解
• 空间复杂度（Space complexity）: 搜索算法最多需要将多少个节点储存在内存中

常用的方法

• 深度优先：把当前要扩展的状态的后继状态放在边界的最前面
  • 时间复杂度为$O(b^m),m是遍历过程中最长路径的长度$​
  • 空间复杂度为$O(bm)$，线性复杂度
  • 不具有完备性和最优性
• 宽度优先：把当前要扩展的状态的后继状态放在边界的最后
  • 时间复杂度为$O(b^{d+1}),d=最短解的个数$
  • 空间复杂度高
  • 具有完备性和最优性
• 一致代价：边界中，按路径的成本升序排列；总是扩展成本最低的那条路径
  • 只是将宽度优先算法的队列换成了优先队列
  • 如果最优解为$C$，则时间和空间复杂度为 $O\left(b^{C / s+1}\right)$
• 深度受限：深度优先搜索，但是预先限制了搜索的深度 $L$​
  • 不具有完备性和最优性
  • 时间复杂度$O(b^L)$，空间复杂度$O(bL)$

• 迭代加深搜索：一开始设置深度限制为$L = 0$，迭代地增加深度限制，对于每个深度限制都进行深度受限搜索

  • 具有完备性和最优性
  • 时间复杂度为$O(b^{d}),d=最短解的个数$​
  • 空间复杂度$O(bd)$

• 双向搜索：同时进行从初始状态向前的搜索和从目标节点向后搜索，在

  两个搜索在中间相遇时停止搜索

  • 难点：如何向后搜索

总结

路径检测

路径检测：当扩展节点$n$来获得子节点$c$时，确保节点$c$不等于到达节点$c$的路径上的任何祖先节点。

环检测：记录下在之前的搜索过程中扩展过的所有节点，当扩展节点 $n_k$ 获得子节点$c$​时，确保节点c不等于之前任何扩展过的节点

• 对于一致代价搜索，使用环检测后仍能找到最优的解

• 对于启发式搜索，这个性质不一定会成立

启发搜索

常见的启发函数$h(n)$：欧氏距离、曼哈顿距离

欧氏距离：$\sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 + … + (x_n - y_n)^2}$​

曼哈顿距离：$| x_1 - y_1 | + | x_2 - y_2 | + … + | x_n - y_n |$

贪心最佳优先搜索：只考虑启发式函数$h(n)$​来对边界上的节点进行排序

• 但是，这种做法忽略了从初始状态到达节点𝑛的成本
• 其是不完备的

A搜索

盲目搜索只考虑了前半部分，能计算出从初始节点走到当前节点的优劣。启发函数则只“估计”了当前节点到最终节点的优劣。

两者相结合，就是启发式搜索策略，典型的代表是A算法。

其定义了评价函数$𝑓 (𝑛)$，利用节点对应的$𝑓 (𝑛)$值来对边界上的节点进行排序，并总扩展边界中具有最小$𝑓$​ 值的节点。$g(n)$是到$n$点的实际开销，$h(n)$是$n$点到终点的估计距离。

算法步骤：

1. 将初始节点的加入优先队列中。
2. 取优先队列中$f(n)$最小的结点。
3. 如果这个结点不是目标结点，则计算其相邻的结点的$f(n)$值，并将这些节点加入优先队列中。转2。
4. 算法终止。

启发函数的要求

• 如果启发函数的值太大，超出了实际的cost，就无法找到最优解
• 如果启发函数的值太小，A搜索就变为了一致代价搜索

A*搜索

在A算法中，如果代价函数 $f(n)=g(n)+h(n)$ 始终满足 $h(n) \leqq h^{}(n)$ 那么该算法就是 $\mathbf{A}^{}$​ 算法。

一个好的$h(n)$​要满足的条件有两个：

$ h(n)=0 时，对于任何 \mathrm{n} 这个启发式函数都是单调的。 \mathrm{A} * 搜索会退化成一致代价搜索$

• 可采纳性：

可采纳的启发式函数低估了当前节点到达目标节点的成本，使得实际成本最小的最优路径能够被选上。

可采纳性意味着最优性：$\text { 最优解一定会在所有成本大于 } C^{*} \text { 的路径之前被扩展到 }$

• 单调性（一致性）：

  $$对于任意节点 n_{1} 和 n_{2} , 若，h\left(n_{1}\right) \leq c\left(n_{1} \rightarrow n_{2}\right)+h\left(n_{2}\right)，则 h(n) 具有单调性$$

  如果是大于号，代表过大估计了cost。

  如果具有单调性，则具有下面以下性质：

  1. 满足一致性的启发式函数也一定满足可采纳性

  2. 在进行环检测之后仍然保持最优性

  3. 一条路径上的节点的 $f$​ 函数值应该是非递减的
  4. 如果节点 $n_2$ 在节点 $n_1$ 之后被扩展, 则有$f(n_1) \leq f(n_2)$
  5. 在遍历节点$n$时，所有$𝑓$值小于$𝑓(𝑛)$​​的节点都已经被遍历过了
  6. A*搜索第一次扩展到某个状态，其已经找到到达该状态的最小成本路径

  拓展指的是将该节点相邻的结点加入边界，遍历指的是探索这个结点

如果$h(n)$只满足可采纳性但是不满足单调性：

1. 虽然确实可以找到最优路径，但是搜索过程可能会更久。
2. 如果启发式函数只有可采纳性，则不一定能在使用了环检测之后仍保持最优性。若出现到达已遍历过节点但成本更低的路径，则需重新扩展而不能剪枝。

IDA*算法

A∗搜索 和宽度优先搜索（BFS）或一致代价搜索（UCS）一样存在潜在的空间复杂度过大的问题。 IDA∗ （迭代加深的A∗搜索）与迭代加深搜索一样用于解决空间复杂度的问题。

但用于划定界限的不是深度，而是使用 $f$ 值$\left(g+h\right)$​

当启发函数h为可采纳时， IDA* 是最优的。

松弛问题

可以通过放宽原始问题中的一些约束条件来简化问题，从而使得问题更容易解决。

例如，在8数码问题中，原始问题要求将一些乱序的数字块通过滑动操作（只能移动到相邻的空格）恢复到正确的顺序。为了构建启发式函数，我们可以设计一个松弛问题，其中允许我们在任何时候都将一个数字块移动到目标位置，而不需要考虑是否相邻或空位的限制。这样的松弛问题简化了原始问题，因为它忽略了移动的约束条件，从而更容易计算出解决方案的成本。

在松弛问题中，到达某个节点的最优成本可作为原始问题中到达该节点的可采纳的启发式函数值。

对抗性搜索

上述的两个搜索算法都假设智能体对环境有完全的控制。

对抗搜索（博弈）的主要特点：超过两个以上玩家且均可以改变状态。难点在于对方会如何行动。博弈有确定的和随机的、完全的信息和不完全的信息等不同的特征.

经典的博弈问题就是双人博弈的问题，主要关注扩展形式的博弈：

• 两个玩家：游戏的状态或决策可以映射为离散的值，游戏的状态或可以采取的行动的种类是有限的。
• 零和博弈：游戏的一方赢了，则另一方输掉了同等的数量
• 确定性：没有不确定的因素
• 完整的信息：任何层面的状态都是可观察的

MinMax策略

对这种扩展式的双人博弈，采用MINMAX搜索。搜索的步骤如下：

• 构建完整的博弈树（每个叶子节点都表示终止状态）
• 反向传播效益值$U(n)$：
  • 叶子节点的$U(n)$是提前定义的
  • 如果结点$n$是一个$Min$节点：$U(n)=min\{U(c):c是n的子节点\}$
  • 如果结点$n$是一个$Max$节点：$U(n)=Max\{U(c):c是n的子节点\}$

为了解决博弈树太大的问题，需要使用深度优先搜索算法来实现MinMax。

Alpha-Beta剪枝

为了进一步提高MinMax执行效率，可以对没有必要探索的分支进行剪枝。

Alpha-Beta剪枝的算法如下：（考试要求写的Alpha-Beta算法）

1. 初始化根节点的$\alpha$值为$-\infty$，$\beta$值为$+\infty$​
2. 以后序遍历遍历整棵博弈树。
   1. 每一个子节点都继承父节点的$\alpha$值和$\beta$值
   2. 每当一个子节点的被遍历完或$\alpha \geq \beta$时，停止遍历其并将结点值返回父节点并更新其父节点的结点值和$\alpha$值或$\beta$值。
   3. MAX结点更新$\alpha$值，MIN结点更新$\beta$值

具体而言，如果一个节点是MIN结点，其的$\alpha$值是继承父节点MAX结点的，$\beta$值是自己更新的。当$\alpha \geq \beta$的时候，因为MIN结点的取值只会越来越小，而父节点（MAX结点）能取到的值已经大于该子节点的值了，所以已经不需要继续遍历了，可以直接返回。

如果一个节点是MAX结点，其的$\beta$值是继承父节点MIN节点的,$\alpha$值是自己更新的。当$\alpha \geq \beta$​的时候，因为MAX结点的取值只会越来越大，而父节点（MIN结点）能取到的值已经小于该子节点的值了，所以已经不需要继续遍历了，可以直接返回。

算法的伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def SearchGameTree(alpha,beta,root,level):
  #叶节点则返回节点的值
  if IsLeaf(root):
    return root.value
  
  value=infinity if level=="Min" else -infinity
  #其他结点则返回alpha或beta值
  for child in childsOf(root):
    #每有一个子节点更新，则更新结点的值，并
    if(level=="Max"):
    	value=max(value,SearchGameTree(alpha,beta,child,"Min"))
      alpha=max(alpha,value)
    else:
    	value=min(value,SearchGameTree(alpha,beta,child,"Max"))
      beta=min(beta,value)
      
    if(alpha>=beta):
      return value
    
  return value

一种优化的Alpha-Beta剪枝的算法如下：

1. 初始化根节点的$\alpha$值为$-\infty$，$\beta$值为$+\infty$​
2. 以后序遍历遍历整棵博弈树。
   1. 每一个子节点都继承父节点的$\alpha$值和$\beta$值
   2. 每当一个节点遍历完或其的$\alpha \geq \beta$，如果其是MAX结点返回$\alpha$值，MIN结点返回$\beta$值
   3. MIN结点只更新$\beta$值，MAX结点只更新$\alpha$​值

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

def SearchGameTree(alpha,beta,root,level): #叶节点则返回节点的值 if IsLeaf(root): return root.value #其他结点则返回alpha或beta值 for child in childsOf(root): #每有一个子节点更新，则更新结点的alpha-beta值 if(level=="Max"): alpha=max(alpha,SearchGameTree(alpha,beta,child,"Min")) else: beta=min(beta,SearchGameTree(alpha,beta,child,"Max")) if(alpha>=beta): return alpha if level=="Max" else beta return alpha if level=="Max" else beta

高级搜索

如果目标路径与问题解不相关，将考虑各种根本不关心路径（耗散）的算法，其中占据重要地位的就是局部搜索算法。

局部搜索算法: 局部搜索算法从单独的一个当前状态出发，通常只移动到与之相邻的状态

爬山算法

爬山搜索算法是一种局部搜索算法。当它达到一个峰值，没有邻居有更高的值时，它将终止。

伪代码如下：

1
2
3
4
5
6
7

def Hill_Climbing(problem):
  current=problem
  while True:
    neighbor=highest_valued_neighbor(neighbors_of(current));
    if neighbor.value<=current.value:
      return current
    current=neighbor

爬山算法存在以下问题：

• 局部极大值：当前状态的邻居状态值都低于当前状态，导致搜索停止。
• 高原或山肩：多个局部极大值连成一片，搜索可能无法找到最优解。

所以爬山法搜索成功与否在很大程度上取决于状态空间地形图的形状

模拟退火算法

模拟退火算法（Simulated Annealing, SA）是一种模拟物理退火过程的优化算法，用于解决NP难题和避免陷入局部最优。

基本要素

三函数两准则一初温：

• 三函数
  • 状态产生函数
  • 状态接受函数：常使用$min(1,e^{-\frac{\Delta C}{t}})$（会以一定几率接受劣解）
  • 温度更新函数：常使用$t_{k+1}=\alpha t_k$
• 两准则
  • 内循环终止准则
  • 外循环终止准则
• 初始温度

基本流程

计算接受概率$P(t_k)=e^{-[\frac{f(j)-f(i)}{t_k}]}$

遗传算法

基本流程

遗传算法（Genetic Algorithms, GA）是一类借鉴生物进化机制的随机搜索算法，适用于解决复杂和非线性优化问题。

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

procedure Simple_GA(input GA_parameters):
    # 输入：遗传算法参数
    # 输出：最佳解决方案
    generation = 0  # 代数
    Population = initialize_population(GA_parameters)  # 种群
    Population.evaluate_fitness()  # 评估种群的适应度
    
    # 主循环，直到满足终止条件
    while not termination_condition(t, GA_parameters):
        Children = crossover(P_t, GA_parameters)  # Children：交叉后产生的后代
        Children = mutate(Children, GA_parameters)  # 变异Children
        Children.evaluate_fitness()  # 评估Children的适应度
        Population = select_next_generation(Population, Children, GA_parameters)  # 选择下一代的种群
        generation = generation + 1  # 增加代数
    
    # 输出最佳解决方案
    best_solution = get_best_solution(Population)
    return best_solution

编码方式

为了交叉（crossover）和变异（mutate），需要对问题状态进行编码，常用编码方式有：

• 二进制编码
• 格雷编码
• 实数编码
• 多参数映射编码（把每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体）

适应度计算方式

若目标函数为最大化问题，则$Fitness(f(x))=f(x)$。若目标函数为最小化问题，则$Fitness(f(x))=\frac 1 {f(x)}$。

在遗传算法中，将所有妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题统称为欺骗问题。常见的有过早收敛、停滞现象等。

解决方法有：

• 缩小这些个体的适应度，以降低这些超级个体的竞争力；
• 或改变原始适应值对应的比例关系，以提高个体之间的竞争力；
• 或对适应度函数值域的某种映射变换。

选择子代方式

常见的选择子代方式有；

• 适应度比例方法：各个个体被选择的概率和其适应度值成比例。个体$i$被选择的概率为：$\quad p_{s i}=\frac{f_{i}}{\sum_{i=1}^{M} f_{i}}$​
• 排序方法：排序选择进入下一代的个体
• 赌盘轮转法：按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例。产生一个随机数，它落入转盘的哪个区域就选择相应的个体。
• 锦标赛选择方法：从群体中随机选择个个体，将其中适应度最高的个体保存到下一代。

交叉方式

常见的交叉方式有；

• 一点交叉：在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新的个体。
• 两点交叉：随机设置两个交叉点，将两个交叉点之间的码串相互交换。

贝叶斯分类器

贝叶斯定理

其中：

• $P(C|A)$ 是后验概率，即在已知特征A的情况下，样本属于类别C的概率。
• $P(A|C)$ 是似然概率，即在已知类别C的情况下，观察到特征A的概率。
• $P(C)$ 是先验概率，即在没有观察到任何特征之前，样本属于类别C的概率。
• $P(A)$ 是边缘概率，即样本具有特征A的概率。

朴素贝叶斯分类器

朴素贝叶斯分类器是贝叶斯分类器的一种，它假设所有特征在给定类别的条件下都是相互独立的。

朴素贝叶斯分类器通过以下方式从数据中估计概率：

• 对于离散属性，使用类别下具有特定属性的样本数除以该类别的总样本数。
• 对于连续属性，可以离散化，也可以假设属性服从正态分布，并使用数据的均值和方差来估计分布的参数，然后利用这些参数来估计条件概率。

Laplace 平滑

为了避免在计算概率时出现零概率的问题，可以使用Laplace平滑（也称为加一平滑）。

其中，$N_c$ 是类别c的样本数量，$N$ 是所有样本的总数，$K$ 是类别总数。通过添加1，可以避免计算得到的概率为零的情况。

对于条件概率，Laplace平滑也可以应用于特征值和类别组合的计数：

其中，$N_{xc}$ 是在类别c下特征x取某个值的样本数量，$V$ 是特征x的所有可能值的数量。同样地，通过添加1，可以避免在训练集中没有出现过的特征值-类别组合导致概率为零的情况。

分类过程

给定一个新的样本，贝叶斯分类器通过计算其属于每个类别的后验概率$\frac{P(A|C)P(C)}{P(A)}$，然后选择具有最大后验概率的类别作为预测结果。

贝叶斯网络

朴素贝叶斯的局限性在于它要求所有特征在给定类别的条件下都是相互独立的。而贝叶斯网络则考虑了不同特特征之间的依赖关系。

贝叶斯网络由以下两个部分组成：

• 一个有向无环图
• 多个条件概率表

一个贝叶斯网络如下：

  flowchart LR
a((A))-->b((B))-->c((C))-->d((D))-->e((E))
  

为了计算$P(A,B,C,D,E)$，就需要计算$P(E|A,B,C,D)P(D|A,B,C)P(C|A,B)P(B|A)P(A)$。计算这个式子比较复杂。

而又观察到，在B发生的情况下，A和C是条件独立的（A发不发生都不影响C，因为A只能通过影响B发生的概率影响C，而B已经发生）。所以可以化简$P(C|A,B)$为$P(C|B)$。

所以将原来的式子化简，可以得到$P(A,B,C,D,E)=P(E|D)P(D|C)P(C|B)P(B|A)P(A)$​，这样就简化了计算。

[!NOTE]

基于因果关系的变量序列可以获得更加自然紧致的贝叶斯网络结构

三类条件独立

所以如果能找到条件独立的变量，就能进行化简。条件独立的变量有三类。

传递

  flowchart LR
a((A))-->b((B))-->c((C))
  

在B发生的条件下，A和C条件独立。

共因

  %%{init:{'flowchart':{'curve':'basis'}}}%%
flowchart TB
a((A))-->b((B)) & c((C))
  

当A发生的条件下，B和C条件独立。

反过来说，如果A还不知道发不发生，B发生了。说明A很有可能发生，进而C有可能发生，因此不独立。

共果

  %%{init:{'flowchart':{'curve':'basis'}}}%%
flowchart TB
a((A)) & b((B)) --> c((C))-->d((D))
  

A和B相互独立。但在C（或者其子节点D）发生的条件下，它们没有条件独立。

如果C（或D）发生了，说明可能是A或B发生了。如果此时A没发生，那说明很可能是B发生了。

判断有向无环图中在特定条件下两个变量是否条件独立，可以看两个变量之间是否有连通的路（这里的路是无方向的）。连通不独立，独立不联通。

• 传递链路上的事件发生，会阻塞路
• 共因的因发生，会阻塞路
• 共果的果发生，会连通路

举一个例子：

  %%{init:{'flowchart':{'curve':'basis'}}}%%
flowchart LR
a((A))-->b((B))-->c((C))-->d((D))
e((E))-->a & c
b & g((G))-->f((F))
  

当C发生的时候，C阻塞了传递链路，因此E和D独立

  %%{init:{'flowchart':{'curve':'basis'}}}%%
flowchart LR
classDef red fill:#f96;
a((A))-.->b((B))-.->c((C))-->d((D))
e((E))-.->a & c
b & g((G))-->f((F))
class c red;
  

当E和B发生的时候，E和B产生阻塞，因此A和D独立

  %%{init:{'flowchart':{'curve':'basis'}}}%%
flowchart LR
classDef red fill:#f96;
a((A))-.->b((B))-->c((C))-->d((D))
e((E))-.->a
e((E))-->c
b & g((G))-->f((F))
class b red;
class e red;
  

当F发生的时候，F是一个通路，因此B和G不独立

  %%{init:{'flowchart':{'curve':'basis'}}}%%
flowchart LR
classDef green fill:#90ee90;
a((A))-->b((B))-->c((C))-->d((D))
e((E))-->a
e((E))-->c
b & g((G))==>f((F))
class f green;
  

分类过程

给定一个新的样本，贝叶斯网络也是通过计算其属于每个类别的后验概率$\frac{P(A|C)P(C)}{P(A)}$，然后选择具有最大后验概率的类别作为预测结果。只不过此时$P(A)$和$P(A|C)$​​在展开的时候用的不是相互独立而是条件独立去计算。

比如，在下面这个贝叶斯网络。计算$P(+b,+j,+m)$的时候就用条件独立代替了相互独立。

变量消除

如果直接枚举所有的情况，变量还是太多。这时候，就可以消除一些变量。

合并因子

比如果知道了$P(R)$和$P(T|R)$的概率表，就可以将其变为$P(R,T)$的概率表。

如果$P(R)*P(T|R)$在一串式子中，那么两个乘积就可以变为一个乘积。

消除因子

如果知道$R$不会以$-R$或$+R$的形式出现在表达式当中。就可以将这个因子消除。将$P(R,T)$的概率表变为$P(T)$的概率表。

已知取值变量

如果一个变量的取值已知，那它也可以被消除。

机器学习

机器学习基础

机器学习基本类别有两种：

• 回归：函数的输出是一个数值
• 分类：函数的输出是一个类别

这两类的目的都是找到一个最优的函数，而寻找函数的三个步骤是：

1. 确定候选函数的集合（Model）
2. 确定「评价函数好坏」的标准（Loss）
3. 找出最好的函数（最优化Optimization）

根据学习模式对机器学习进行分类，机器学习可以分为：

• 监督学习
• 无监督学习
• 半监督学习
• 强化学习

聚类算法

聚类算法目的是找到几个组，使组内相似度较高，而组间相似度较少。

聚类（clustering）是由一系列集群（clusters）组成的集合。其的类别有：

• 分割式聚类：将数据对象划分为不重叠的子集(簇) ，这样每个数据对象都恰好在一个子集中。

  

• 阶层式聚类：一组嵌套的集群，组织成一个层次树。

  

K-means算法

算法流程：

1. 选择K个点作为初始的聚类中心
2. 计算所有点到K个初始聚类中心的距离，每个点被划分到距离最近的聚类中心的那个簇。
3. 重新计算每个簇的聚类中心（求坐标的平均值）
4. 如果聚类中心没有变化，则算法结束，否则转2

初始的聚类中心通常是随机选择的。也是因为随机选择，所以可能聚类效果并不好。

算法评价方法

可以用SSE（Sum of Squared Errors误差平方和）来评估聚类的质量。SSE 越小，表示数据点在聚类内部越紧密，聚类效果越好。

其中，K 是聚类的数量，$C_i$ 是第 $i$ 个聚类，$m_i$ 是第 $i$ 个聚类的中心点，$x$ 是聚类 $C_i$ 中的一个数据点，$d(m_i, x)$ 是点 $x$ 到中心点 $m_i$ 的距离。

K-means算法的改进

K-means++

改进了初始选择聚类中心的方法：

1. 第一个聚类中心随机选取
2. 以每个点分别为$\frac{D\left(x^{\prime}\right)^{2}}{\sum_{x \in \mathcal{X}} D(x)^{2}}$的概率选择下一个聚类中心。$D(x)$是数据点$x$到已经选择的最近的聚类中心的距离，也就是会选尽量与已选择的聚类中心较远的点作为聚类中心。
3. 如果没选择到K个聚类中心则转2。

但其也有缺点：每次选择聚类中心都需要遍历一次剩下的点，一共K次遍历。

K-means||

K-means||也叫稳定的K-means。

主要思路在于改变每次遍历时的取样策略，并非按照 kmeans++ 那样每次遍历只取样一个样本，而是每次遍历取样 $O(k)$ 个样本，重复该取样过程大约 $O(logn)$ 次，共得到 $O(klogn)$ 个样本点组成的集合。然后再聚类这 $O(klogn)$ 个点成 $k$ 个点，最后将这 $k$ 个点作为初始聚类中心。

DBSCAN

DBSCAN是一个基于密度的算法。（密度：指定半径内的点数）

给定$Eps$作为半径、$MinPts$作为最小的点的数量，其将点分为三类：

• 核心点（core point）：在$Eps$（半径范围内）就有超过指定数量（$MinPts$）的点。

• 边界点（border point）：在$Eps$内少于$MinPts$个点，但它位于一个核心点的邻域内

• 噪声点（noise point）：其他点。

算法流程：

1. 对所有点进行标记，核心点、边界点或噪声点
2. 消除所有的噪声点。
3. 对于所有核心点，如果在$Eps$范围内，则它们之间添加一条边。
4. 将相连的核心点组成不同的簇
5. 将每个边界点分配到它相关的核心点的某个簇中

但其对$Eps$和$MinPts$的选择有要求。

评价方法

1. 相似度矩阵
2. SSE（凝聚度）和SSB（分离度）两者之和是定值（TSS）
   • $SSE = \sum_{i=1}^{k} \sum_{x \in C_i} | x - m_i |^2$
   • $SSB = \sum_{i=1}^{k} n_i | m_i - m |^2$。其中，$k$ 是聚类的数量，$n_i$ 是第 $i$个聚类中的点的数量，$m_i$ 是第 $i$个聚类的中心点，$m$是所有数据点的中心点（通常是所有点的均值）。

谱聚类

参考文章

谱聚类(Spectral Clustering)要求比K-means少，结果比K-means好，复杂度比K-means小。

图的一些概念

• $|A|$：图中顶点的个数

• $vol(A)$：图的所有顶点的度数之和

• 相似度矩阵：

  • $A(i, j)=0。如果i,j不相邻$
  • $A(i, j)=s(i, j)。如果i,j相邻$

• 度矩阵：

  • $D(i, j)=0。如果i\neq j$

  • $D(i,j)=d(v_i)。如果i=j相邻$​

    对角线上是每个节点自己的度

• 拉普拉斯矩阵：$L=D-W$​，其有如下性质：

  D是度矩阵，W是邻接矩阵

  • 对称性：由于D和W都是对称的，L也是对称的。

  • 半正定性：拉普拉斯矩阵的所有 eigenvalues（特征值）都是非负的，这意味着对于所有的向量$x，x^T L x ≥ 0$。

  • 最小特征值：拉普拉斯矩阵的最小特征值是0，对应的特征向量是所有元素都是1的常数向量。

  • 特征值排序：拉普拉斯矩阵的特征值可以按照非递减的顺序排列：$0 = λ_1 ≤ λ_2 ≤ … ≤ λ_N$。

  • 特征值之间的差距：最小非零特征值$λ_2$被称为谱隙（spectral gap），它度量了图结构的扩展性。

  • 特征向量的正交性：拉普拉斯矩阵有一组完整的正交特征向量。

  • 对于任意的向量有

    $$f^{T} L f=\frac{1}{2} \sum_{i, j=1}^{n} w_{i j}\left(f_{i}-f_{j}\right)^{2}$$

图分割

图分割要求把一个图分割为几个子图，并使得那些被切断的边的权值之和最小。

无向图切图

Cut

对于任意两个子图点的集合 $A, B \subset V$，其中 $A \cap B=\emptyset$，定义 $A$ 和 $B$ 之间的切图权重为：

其中 $w_{ij}$ 表示点 $i$ 和点 $j$ 之间的权重。

对于 $k$ 个子图点的集合 $A_{1}, A_{2}, \ldots A_{k}$，定义切图Cut为：

这里，$\bar{A}_{i}$ 表示 $A_{i}$ 的补集，即除 $A_{i}$ 子集外其他 $V$ 的子集的并集。

一个好的切图，要让切图Cut最小

但是仅使用这个Cut定义，会得到不够好的切图：

RatioCut

RatioCut切图对每个切图，不光考虑最小化$\operatorname{cut}(A_{1}, A_{2}, \ldots A_{k})$ ，它还同时考虑最大化每个子图点的个数：

而要最小化RatioCut，需要引入指示向量：$h_{j} \in\left\{h_{1}, h_{2}, . . h_{k}\right\} ,j=1,2, \ldots k$，它是一个$n$维向量。$h_{ij}$定义为：

意思是如果点$v_i$属于$A_j$集合，则$h_{ij}=\frac{1}{\sqrt{\left|A_{j}\right|}}$。

有了指示向量后，RatioCut就可以化简为：

要最小化RatioCut，需要优化每一个$h_{i}^{T} L h_{i}$。其中 $h$ 是单位正交基， $L$ 为对称矩阵，此时 $h^T L h$ 的最大值为 $L$ 的最大特征值，最小值是 $L$ 的最小特征值。

所以通过找到$L$的最小的$k$个特征值，可以得到对应的$k$个特征向量，这$k$个特征向量组成一个$n\cdot k$维度的矩阵，即为$H$​。

由于在使用维度规约的时候损失了少量信息，导致得到的优化后的指示向量$h$对应的$H$现在不能完全指示各样本的归属。

如果没有损失信息，$h_{ij}=\frac{1}{\sqrt{\left|A_{j}\right|}}$代表点$v_i$属于$A_j$集合。

因此一般在得到$n\cdot k$维度的矩阵$H$后还需要对每一行进行一次传统的聚类，比如使用K-Means聚类。

NCut

Ncut切图和RatioCut切图很类似，但是把RatioCut的分母 $|A_i|$ 换成 $\text{vol}(A_i)$：

同样选取指示向量：

将优化目标转换为：

此时$H$中的指示向量$h$并不是标准正交基，而是$H^{T} D H=I$，所以在RatioCut里面的降维思想不能直接用。

令$H=D^{-1 / 2} F$,则$H^{T} L H=F^{T} D^{-1 / 2} L D^{-1 / 2} F$。此时$H^{T} D H=F^{T} F=I$。可以继续按照RatioCut的方法降维，求出 $D^{-1/2} L D^{-1/2}$ 的最小的前$k$个特征值，然后求出对应的特征向量，并标准化，得到最后的特征矩阵 $F$，最后对 $F$ 进行一次传统的聚类（比如K-Means）即可。

算法步骤

构建图

用于构建图的方法有：

• 全连接图
• $r$-邻接图（结点与以其为圆心，$r$为半径内的其他结点相连）
• $k$-最近邻图（结点与最近的$k$个邻居相连）

构建拉普拉斯矩阵

根据相似矩阵$S$构建邻接矩阵$W$，构建度矩阵$D$。然后计算拉普拉斯矩阵$L=D-W$​。

根据切图方法计算特征值

以下$k_1$为降维后的维度

• RatioCut计算 $L$ 的最小的前$k_1$个特征值
• NCut计算$D^{-1/2} L D^{-1/2}$ 的最小的前$k_1$​​个特征值

计算特征矩阵

将各自对应的特征向量$f$组成的矩阵按行标准化，最终组成$n\cdot k_1$维的特征矩阵$F$​。

对特征矩阵聚类

对$F$中的每一行作为一个$k_1$维的样本，共$n$个样本，用输入的聚类方法（比如K-means）进行聚类，聚类维数为$k_2$（划分为$k_2$个簇）。

最后得到簇划分 $C(c_1, c_2, \ldots, c_{k})$。

SVM(不考)

参考文章，这篇博客写的非常透彻，强推。

SVM（Support Vector Machine）也称支持向量机，是一个将数据单元表示在多维空间中，然后对这个空间做划分的算法。而支持向量指的是支撑平面上把两类类别划分开来的超平面的向量点。

SVM在解决小样本、非线性、及高维模式识别中有很多优势。

基础概念

结构风险

结构风险 = 经验风险 + 置信风险。

• 经验风险：在给定样本上的误差。
• 置信风险：在多大程度上可以信任分类器在未知样本上分类的结果。

SVM 的目标是最小化结构风险，而不再只是优化经验风险，否则会过拟合。

几何间隔

几何间隔，指的是点到超平面距离（不同于点到平面的距离）：

其中，超平面为$y=\omega^T x+b$。$\hat y$是函数间隔。

SVM目标函数

原问题

对一个数据点进行分类，当超平面离数据点的“间隔”越大，分类的效果就越好。所以对所有点来说，应该使得平面恰好夹在两类点的中间。

所以就需要使最靠近分界线的点离分界线的几何间隔最大。所以目标函数定义为：

如果令函数间隔 $\hat{\gamma}$​ 等于1（方便推导和优化，且这样做对目标函数的优化没有影响）。则目标问题变为：

由于求 $\frac{1}{|w|}$ 的最大值相当于求 $\frac{1}{2}|w|^{2}$ 的最小值，所以可以将目标函数转换为：

因为原问题的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题，有全局的最优解。

对偶问题

拉格朗日变换

由于原问题的特殊结构，还可以通过拉格朗日对偶性变换为对对偶问题的求解。

通过给每一个约束条件加上一个拉格朗日乘子$\alpha$，可以将约束条件融合到目标函数里去，从而将约束优化问题转换为无约束优化问题：

并令：

而当所有约束条件都满足时，则最优值为$\theta(w)=\frac{1}{2}|w|^{2}$。因此，在要求约束条件得到满足的情况下最小化 $\frac{1}{2}|w|^{2}$，实际上等价于直接最小化 $\theta(w)$。

用$p^*$​表示问题的最优值，则目标函数变为：

这个问题的求解较为困难（因为有参数$w、b$，并且$a_i$​​还受到不等式约束）。所以把最小和最大的位置交换一下，得到原问题的对偶问题：

$d^{}$是新问题的最优解，并且有$d^{}\leq p^{}$。并且因为Slater 条件成立，所以$d^{}\leq p^{*}$​可以取等号。

求解对偶问题

首先固定 $\alpha$ ，要让 $\mathcal{L}$ 关于 $w$ 和 $b$ 最小化 我们分别对 $w, b$ 求偏导数，即令 $\partial \mathcal{L} / \partial w$ 和 $\partial \mathcal{L} / \partial b$ 等于零。 可以得到：

将以上结果代入之前的$\mathcal{L}$，化简后得到：

此时的拉格朗日函数只包含了一个变量$\alpha_i$。然后就可以根据下式求解出$\alpha_i$：

然后就可以根据$w=\sum_{i=1}^{m} \alpha_{i} y^{(i)} x^{(i)}$，求解出$\omega$；根据$b^{}=-\frac{\max _{i: y^{(i)}=-1} w^{ T} x^{(i)}+\min _{i: y^{(i)}=1} w^{* T} x^{(i)}}{2}$求解出$b$​。最终得出分离超平面和分类决策函数。

核函数

SVM分类过程

对于一个数据点 $x$ 进行分类, 实际上是通过把 $x$ 带入到 $f(x)=w^{T} x+b$ 算出结果然后根据其正负号来进行类别划分的。

而$w=\sum_{i=1}^{m} \alpha_{i} y^{(i)} x^{(i)}$，所以分类函数为：

那么，对于新点$x$​的预测，只需要计算它与训练数据点的内积即可。

事实上，所有非支持向量所对应的系数$\alpha$​都是等于零的，因此对于新点的内积计算实际上只要针对少量的“支持向量”，而不是所有的训练数据。

核函数的作用

对于非线性的情况，SVM 的处理方法是选择一个核函数 $κ(⋅,⋅)$​ ，通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。

而在核函数之前，如果用原始的方法，在用线性学习器学习一个非线性关系时，需要选择一个非线性特征集，并且将数据写成新的表达形式，这等价于应用一个固定的非线性映射，将数据映射到特征空间，在特征空间中使用线性学习器。

如果将原来的分类函数

直接找一个映射 $\phi(\cdot)$，把原来的数据映射到新空间中, 再做线性SVM。就会有维度爆炸的问题。

所以相比映射到高维空间中，然后再根据内积的公式进行计算。核函数选择另一个方式：直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果。

核函数的定义

核函数是一个函数 $\kappa$，对所有 $x, z \in X$，满足 $\kappa(\mathbf{x}, \mathbf{z}) = \langle\phi(\mathbf{x}) \cdot \phi(\mathbf{z})\rangle$，这里 $\phi$ 是从 $X$ 到内积特征空间 $F$ 的映射。

计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数。它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就避免了直接在高维空间中的复杂计算。

常见的核函数

常见的核函数有：

• 多项式核：$\kappa(x, y)=\left(\alpha x^{T} y+c\right)^{d}$
• 高斯核：$\kappa(x, y)=\exp \left(-\gamma|x-y|^{2}\right)$
• 线性核 ：$\kappa\left(x, y\right)=\left\langle x, y\right\rangle$

松弛变量处理离群点

虽然通过映射 $\phi(\cdot)$ 将原始数据映射到高维空间之后，能够线性分隔的概率大大增加，但是对于某些情况还是很难处理。

例如一些离群点（偏离正常位置很远的数据点），会对SVM模型造成很大影响。

因为超平面本身就是只有少数几个支持向量组成的，如果这些支持向量里又存在离群点的话，其影响就很大了

通过向约束条件中加入松弛变量$\xi_{i}$：

允许数据点离超平面更近。并且向目标函数中加入惩罚项，限制这种松弛：

再进行上面的一系列操作（拉格朗日对偶、核函数），就可以得到一个完整的、可以处理线性和非线性、并能容忍噪音和离群点的支持向量机。

人工神经网络

发展史

MP模型

最初提出的神经网络模型是MP（McCulloch-Pitts ）模型，其的权重是预先设置的：

感知机

之后发展出了感知机，也被称为单层神经网络，其的权重是通过训练得到的，训练法则为：

其$f$神经元中执行的是线性运算$\mathbf{z}=g(\boldsymbol{W} \times \boldsymbol{a})$，所以只能执行线性分类。

也是因为神经元执行的是线性运算，所以感知机只能做简单的线性分类任务，无法解决XOR（异或）问题。

多层感知机

之后就发展出了多层感知机（多层的神经网络）

并且其不再使用sgn函数做激活函数，而是使用sigmoid函数

关键在于: 从输入层到隐藏层时，数据在激活函数作用下发生了空间变换

其通过前向传播和反向传播来进行训练，前向传播为了计算当前参数下的误差，反向传播是为了根据误差调整参数。反向传播常用的算法是梯度下降。

神经网络基础

神经网络的一个神经元的基础操作是对输入$x$执行：

1. 线性运算：$z=W x+b$​
2. 通过激活函数：$y=\sigma(z)$

从功能角度讲，神经网络就是多层的特征提取加上线性分类。

卷积神经网络

卷积操作

人观测图片的特点： ① 局部特征影响大 ② 重要位置常变化 ③ 采样压缩也没差

根据前两个特点特点，设计卷积神经网络，就设计出了可以移动的卷积核。

卷积过程中的步长（stride）指的是卷积核在输入图像上每次移动的像素数量；卷积操作前的填充（padding）操作，指的是在输入图像的边界周围添加额外的像素。

卷积维度公式

假设图片尺寸为 $n_{h} \times n_{w} \times n_{c}$，卷积核为 $f \times f \times n_{c}$，步长 $s$，填充 $p$​。其中：

• $n_{h}$ 是高度，$n_{w}$ 是宽度，$n_{c}$ 是深度（通道数）

• $f$ 是卷积核的尺寸，$n_{c}$​ 是卷积核的深度（与输入图片的深度相同）

那么特征图（卷积层输出）维度公式：

池化

池化操作将特征图划分为若干个子区域，并对每个子区域进行统计汇总。

池化操作的方式可以有很多种，比如最大池化、平均池化等。

• 最大池化：选取每个子区域内的最大值作为输出
• 平均池化：计算每个子区域内的平均值作为输出

循环神经网络

循环神经网络要解决的槽填充问题：

I would like to arrive Guangzhou on May.

CNN和普通的神经网络都没有记忆功能，而RNN可以记忆。

长短期记忆网络（LSTM）

RNN网络没有遗忘的功能，所以以往的所有输入都会影响输出，而LSTM加入了遗忘功能。它用特殊的神经元代替了普通神经网络中的神经元。

这个特殊的神经网络有三个门：

• 输出门：控制是否输出
• 遗忘门：选择是否遗忘
• 输入门：控制是否输入

一份输入要充当这三个门的信号和神经元的输入。

缺点是参数量大了，训练和计算时间也长了。

强化学习

强化学习是通过与环境进行交互、试错，从而学会做出一系列好的决策。

  %%{init:{'flowchart':{'curve':'basis'}}}%%
flowchart TD
a[Agent]--Action-->e[Environment]
e--Reward-->a
e--state-->a
  

强化学习的特殊之处在于：

• 环境刚开始是未知的

• 智能体要与环境互动

基本概念

随机性的两个来源

随机性的来源有两个：

• 给定状态，智能体的行为具有随机性，由策略来决定。

  $$A \sim \pi(\cdot \mid s)$$

  其中$\pi$是策略，$\pi(a_1|s)$代表的是在状态$s$下选择行为$a_1$的概率。

• 状态的转移也具有随机性，由状态转移函数来决定。

  $$S^{\prime} \sim p(\cdot \mid s, a)$$

  其中$S’$是次态，$p(\cdot \mid s, a)$指的是在状态$s$和行为$a$下转移到次态$S’$的概率。

AI玩游戏

可以将AI玩游戏的过程看成一个由状态（$s$）、行为（$a$）和奖励（$r$）组成的序列。

一个完整的交互序列（episode），就是从初始状态开始到最终状态结束。一个好的策略能让最后积累的奖励最大。

回报

回报（Return）即累计未来奖励。假设$R_t$是$t$时刻的奖励，那么回报$U_t$的定义为：

因为在$t$时刻，未来的奖励具有随机性，所以$U_t$也具有随机性。并且因为奖励的越早，奖励越具有吸引力。所以随着获得奖励所需的时间越久，其的价值也越低，在公式中以衰减因子$\gamma$表示。

价值函数

行为价值函数

行为价值函数$Q_\pi(s,a)$是针对策略$\pi$而言的。其的定义如下：

$Q_{\pi}\left(s_{t}, a_{t}\right)$代表的是，在$\pi$策略下，在$s_t$的状态下、选择行动$a_t$，获得回报的期望。

可以定义最优行为价值函数为：

其代表着在$s_t$的状态下、选择行动$a_t$，在所有策略中，能获得的最大的回报的期望。

状态价值函数

状态价值函数$V_\pi(s_t)$的定义如下：

$V_\pi(s_t)$代表的是，在$\pi$策略下，在$s_t$的状态下，获得回报的期望。

状态价值函数和行为无关。

可以用$\mathbb{E}_{S}\left[V_{\pi}(S)\right]$来衡量策略$\pi$有多棒。

进行强化学习

单智能体强化学习问题可以形式化定义为马尔可夫决策过程（MDP）六元组：

其中：

• $S$ 表示状态空间，
• $\boldsymbol{A}$ 表示动作空间，
• $R=R(S, \boldsymbol{a})$ 表示奖励函数，
• $T: S \times \boldsymbol{A} \times S \rightarrow [\mathbf{0}, \mathbf{1}]$ 表示状态转移函数，
• $\boldsymbol{P}_{0}$ 表示初始状态分布，
• $\gamma$ 是折扣因子。

强化学习的学习目标: 找到能最大化累计奖励的策略$\pi$​。

有这几种学习方式：

• 基于价值（Value-based learning）：它的目标是学习出一个价值函数，这个价值函数能够评估给定状态下采取某个动作的期望回报。
• 基于策略（Policy-based learning）：它直接学习策略函数，这个策略函数能够根据当前状态直接输出一个动作分布或确定性的动作。
• Actor-critic方法：它结合了Value-based learning和Policy-based learning两种方法的优点。

基于价值学习

基于价值学习需要近似$Q^{\star}\left(s_{t}, a_{t}\right)$，那么就可以知道每一个行动$a_t$能带来多大的价值。近似所用的方法是DQN（Deep Q-Network），即深度Q网络。

但在训练DQN的时候，和训练任何一个神经网络一样，需要给出标签值，也就是$a_t$实际的价值是多少，然后与预测出来的$a_t$的价值去求损失。但直接求实际价值又太慢了（需要完整的完成一个迭代），所以就有了TD学习（Temporal Difference (TD) Learning）。

TD学习将实际价值近似为「当前奖励+下一步预测值」，只关注时间差分，即当前时间步的预测值和下一时间步的预测值之间的差异。数学的表达形式为：

右边就是「当前奖励+下一步预测值」（还乘了损失因子），用其来近似实际价值。然后就可以用这个近似的实际价值当做神经网络的标签，去进行训练。

基于策略学习

基于策略学习和基于价值学习的方法类似，它也是用神经网络去近似策略函数$\pi(a|s)$。

它的目的是优化${\theta}$使得$J({\theta})=\mathbb{E}_{S}[V(S ; {\theta})]$​最大。也就是让所有状态下采取给定策略得到的回报期望最大。这个回报期望可以通过跑完全程得到，也可以通过训练一个神经网络去预测这个回报。

在优化的过程中，梯度为让$V(s;\theta)$上升最快的方向。神经网络中是减去梯度，来梯度下降，这里是加上梯度来梯度上升。

Actor-Critic方法

Actor-Critic方法结合了基于价值学习和基于策略学习两者，它有一个actor作为策略网络，有一个critic作为价值网络：

• actor：用神经网络$\pi(a|s ; \theta)$去近似$\pi(a|s)$。
• critic：用神经网络$q(s,a;\omega)$去近似$Q_\pi(s,a)$

在训练过程中两者是一起训练的，训练的过程如下：

1. 观察到状态$s_t$
2. actor根据自己的$\pi(a|s ; \theta)$网络给出的概率，（按概率）随机选一个动作执行。
3. 观察到下一个状态$s_{t+1}$并得到奖励$r_t$
4. 用TD学习更新critic网络中的参数$\omega$
5. 用策略梯度（需要critic预测回报），更新critic网络中的$\theta$

在训练全部完成后，以后做出决策就只需要策略网络（actor），而不需要critic。

AlphaGo

AlphaGo的训练有三步：

1. 通过behavior cloning初始化策略网络
2. 通过策略梯度训练策略网络。
3. 训练完策略网络后，用策略网络去训练一个价值网络。

最后通过蒙特卡洛树搜索的方法使用策略网络和价值网络。

训练过程

behavior cloning

因为如果直接进行强化学习，速度太慢。所以首先根据人类已有的棋局资料，去训练策略网络。

训练策略网络

因为仅仅用behavior cloning还会有很多状况考虑不到。所以还需要训练策略网络。在训练策略网络的过程中，通过跑完全程得到回报期望。即如果最终赢了，这局所有的行为的分数都+1；如果平局则这句行为的分数不变；如果最终输了，这局所有行为的分数都-1。

训练价值网络

仅用策略网络，有可能出现在某一步走错之后步步错。所以还需要用策略网络训练一个价值网络（与之前不同，这里是拟合状态价值函数）。之后就可以结合策略网络和价值网络进行决策。

运行过程

运行的过程用到了蒙特卡洛树搜索的方法。其有四步：

• Selection：

  • 设当前状态为$s_t$

  • 对所有有效的行为$a$，计算行为$a$的得分：

    $$\operatorname{score}(a)=Q(a)+\eta * \frac{\pi\left(a | s_{t} ; \theta\right)}{1+N(a)}$$

    其中$Q(a)$是蒙特卡洛树计算的行为得分，$\pi\left(a | s_{t}\right)$是策略网络给出的行为概率，$N(a)$是到目前为止一共选择了行为$a$​多少次。

  • 选择具有最大$\operatorname{score}(a)$的行为$a_t$​。

    

• Expansion：

  • 选择了$a_t$行为，所以到达了$s_{t+1}$的状态。

  • 然后通过策略网络，不断自我博弈，直到走到游戏结束

    

• Evaluation：

  • 计算： $$V(s_{t+1})=\frac{1}{2} v\left(s_{t+1} ; w\right)+\frac{1}{2} r_{T}$$ 其中$v\left(s_{\mathrm{t}+1} ; {w}\right)$是价值网络的评分；如果赢了，则$r_T=1$，如果输了，则$r_T=-1$。

• Backup：

  • 重复上面三步，每一个$a_t$都会记录一系列的$V_i$​值

    

  • 更新

    $$\left.Q\left(a_{\mathrm{t}}\right)=\text { mean(the recorded } V^{\prime} s\right)$$

最后，选择被蒙特卡洛树搜索选择最多次的$a_t$作为下一个行为。

数据降维

大多数机器学习和数据挖掘技术可能对高维数据无效。并且高维的数据会比较稀疏，有可能导致数据“过于”可分，导致过拟合。而且高维度中用距离来衡量样本相似性的方法会渐渐失效。

数据降维不仅可以帮助可视化，还可以进行数据压缩和噪声过滤。

数据降维的方法主要有特征选择与特征降维。它们的区别如下：

1. 特征选择：减少特征的数量，只使用选中的特征。
2. 特征降维：所有原始特征都用于计算，但最终模型使用的是这些原始特征的线性或非线性组合，以降低数据的维度

特征降维的方法有：

• 无监督学习：
  • 截断奇异值分解（Truncated Singular Value Decomposition, SVD）
  • 独立成分分析（Independent Component Analysis, ICA）
  • 主成分分析（Principal Component Analysis, PCA）
  • 局部线性嵌入（Locally Linear Embedding, LLE）
  • 拉普拉斯特征映射（Laplacian Eigenmaps, LE）
• 有监督学习：
  • 线性判别分析（Linear Discriminant Analysis, LDA）
  • 典型相关分析（Canonical Correlation Analysis, CCA）

PCA主成分分析

主成分分析（PCA）是一种常用于降维的数据分析技术，通过将原始高维数据投影到新的低维空间来保留数据中的主要信息。以下是PCA的算法流程：

1. 数据标准化：将数据标准化为均值为0，方差为1的形式。这一步是为了消除不同特征之间量纲不一致的影响。

   $$\text{Standardized data} = \frac{X - \mu}{\sigma}$$

2. 计算协方差矩阵：计算标准化数据的协方差矩阵，以了解特征之间的相关性。

   $$\mathbf{C} = \frac{1}{n-1} \mathbf{X}^T \mathbf{X}$$

   其中，$\mathbf{X}$ 是标准化后的数据矩阵， $n$​是样本数量。

   如果两个变量的协方差为正，则表示一个变量的增加通常与另一个变量的增加相联系；如果协方差为负，则表示一个变量的增加通常与另一个变量的减少相联系。

3. 特征值分解：对协方差矩阵进行特征值分解，得到特征值和特征向量。

   $$\mathbf{C} \mathbf{v} = \lambda \mathbf{v}$$

   其中，$\lambda$ 为特征值，$\mathbf{v}$ 为对应的特征向量。

4. 选择主成分：根据特征值的大小选择前k个最大的特征值对应的特征向量，作为主成分。

5. 转换数据：将原始数据投影到选定的特征向量空间，得到降维后的数据。

   $$\mathbf{X}_{\text{new}} = \mathbf{X} \mathbf{W}$$

   其中， $\mathbf{W}$ 是由选定的特征向量构成的矩阵。

示例：应用PCA进行降维

假设我们有一个三维数据集如下：

1. 数据标准化

将每个特征标准化，标准化后的数据：

2. 计算协方差矩阵

计算标准化数据的协方差矩阵：

3. 特征值分解

对协方差矩阵进行特征值分解，得到特征值和特征向量。

特征值：

特征向量：

4. 选择主成分

选择前两个最大的特征值对应的特征向量作为主成分，则选择的特征向量：

5. 转换数据

将原始数据投影到选定的特征向量空间，转换后的数据：

这样，我们将原始的三维数据降维成了二维数据，同时保留了数据中的主要信息。

SVD（奇异值分解）

SVD是另一种数据降维的技术。算法流程如下：

1. 构建矩阵：构建一个数据矩阵 $A$，其中包含要处理的所有数据。

2. 奇异值分解：对矩阵 $A$ 进行奇异值分解，得到三个矩阵 $U$、$\Sigma$ 和 $V^T$。

   $$A = U \Sigma V^T$$

   其中，$ U $是$ m \times m $的正交矩阵，$ \Sigma $是$ m \times n $的对角矩阵，$ V^T $是$ n \times n $​ 的正交矩阵。

3. 选择主成分：根据奇异值的大小选择前k个最大的奇异值，构建低秩近似。

4. 重构矩阵：利用选择的奇异值和对应的左右奇异向量重构原始矩阵的低秩近似。

   $$A_k = U_k \Sigma_k V_k^T$$

   其中，$ U_k $和$ V_k $分别是$ U $和$ V $的前 k 列，$ \Sigma_k $是$ \Sigma $ 的前 k 个奇异值构成的对角矩阵。

给定一个向量$q$，可以通过$qV$得到它属于哪一个类。

示例：Latent Semantic Indexing（潜在语义索引）

假设有这样的一个数据集，其中第一列是文档类型（CS代表计算机，MED代表医学）。可以看到data、information、retrieval这些词只在计算机类的文档中出现；而brain、lung只在医学类的文档中出现。

1. 构建矩阵

构建文档-词项矩阵 $A$ ：

2. 奇异值分解

对矩阵$A$进行奇异值分解，可以得到三个矩阵为：

在这里其实就可以发现矩阵$U$前三行第一列不为0的刚好对应的是CS类的。而第二列不为0的刚好对应的是MED类的。而$V$也同理。

3. 选择主成分

这里可以看到为9.64的奇异值较大，所以就选择其。

4. 重构矩阵

然后将$\Sigma$矩阵中的没有选择的奇异值改为0。也就是：

然后再重新计算$A_k$。

得到低秩近似$A_k$：

LDA（线性判别法）

LDA的原理是，将带上标签的数据（点），通过投影的方法，投影到维度更低的空间中，使得投影后的点，会形成按类别区分，一簇一簇的情况，相同类别的点，将会在投影后的空间中更接近。

参考文章：https://www.cnblogs.com/LeftNotEasy/archive/2011/01/08/lda-and-pca-machine-learning.html

LLE（局部线性嵌入）

LLE(Locally Linear Embedding)优势在于降维时保持样本局部的线性特征。它广泛的用于图像图像识别，高维数据可视化等领域。

算法原理

LLE首先假设数据在较小的局部是线性的。即某一个数据可以由它邻域中的几个样本来线性表示。

比如有一个样本 $x_1$，在它的原始高维邻域里用K-近邻思想找到和它最近的三个样本 $x_2, x_3, x_4$。然后假设 $x_1$ 可以由 $x_2, x_3, x_4$ 线性表示，即：

其中，$w_{12}, w_{13}, w_{14}$ 为权重系数。在通过LLE降维后，希望 $x_1$ 在低维空间对应的投影 $x’_1$ 和 $x_2, x_3, x_4$ 对应的投影 $x’_2, x’_3, x’_4$ 也尽量保持同样的线性关系，即

也就是说，投影前后线性关系的权重系数 $w_{12}, w_{13}, w_{14}$ 是尽量不变或者最小改变的。

从上面可以看出，线性关系只在样本的附近起作用，离样本远的样本对局部的线性关系没有影响，因此降维的复杂度降低了很多。

参考文章：https://www.cnblogs.com/pinard/p/6266408.html