人工智能期末复习
6-7个简答题，每个题15-20分，搜索出一题，
搜索
井字棋，拼图等。
构建启发式函数
为什么需要启发：
- 没有精确解
- 约简搜索的状态空间
例：井字棋。以落子位置能够覆盖的路线数量作为启发函数。
- 在角上落子，覆盖三种路线；
- 在中间落子，覆盖四种路线；
- 在边上落子，覆盖两种路线。 优先对中间位置进行搜索。
例：8-Puzzle。$h(n)$定义为错位牌到正确位置需要移动的格子数目和。
博弈树、极小极大搜索
- 极大，MAX：代表我方玩家，要最大化收益
- 极小，MIN：代表对手，最小化我方收益
将评估值（启发值）自底向上传播。
- 如果父状态是MAX，将孩子节点中的最大值传给它
- 如果父状态是MIN，将孩子节点中的最小值传给它
MAX 3
____/ | \____
MIN 3 0 2
/ \ / \ / \
MAX 3 9 0 7 2 6
/ \ / \ | / \ / \ / \
MIN 2 3 5 9 0 7 4 2 1 5 6
固定层深的极小极大过程
在每次决策时，只搜索固定的层深。 例如，当固定层深为2时，搜索两层就停止，以子节点的子节点作为搜索树的叶子，叶节点用启发式函数估算价值。然后向上回溯，用MIN-MAX方法计算每一层的评估值。
α-β剪枝
Alpha表示一个MAX节点的估值，Beta表示一个MIN节点的估值。这两个值在搜索过程中不断更新。MAX节点的 Alpha会越来越大，MIN节点的Beta会越来越小。
- Alpha剪枝：任一MIN节点，如果其Beta值已经小于等于其祖先MAX节点的Alpha值，则停止搜索。
- Beta剪枝：任一MAX节点，如果其Alpha值已经大于等于其祖先MIN节点的Beta值，则停止搜索。
例：
MAX 3
____/ | \____
MIN 3 c e
/ \ / \ / \
MAX 3 a 0 d 2 f
/ \ / \ | / \ / \ / \
MIN 2 3 5 b 0 ? ? 2 1 ? ?
- 子树$b$的结果无论是多少，$a$的结果都不可能小于3，不会影响祖先的结果。用Alpha-Beta剪枝的术语描述，$a$是一个MAX节点，其Alpha值为5，祖先MIN节点的Beta值是3，Alpha值已经大于等于其祖先MIN节点的Beta值，则停止搜索。这是一次Alpha剪枝。
- 子树$d$的结果无论是多少，$c$的结果都不可能大于0，不会影响祖先的结果。用Alpha-Beta剪枝的术语描述，$c$是一个MIN节点，其Beta值为0，祖先MIN节点的Alpha值是3，Beta值已经小于等于其祖先MAX节点的Alpha值，则停止搜索。这是一次Beta剪枝。
- 子树$e$的结果无论是多少，$f$的结果都不可能大于2，不会影响祖先的结果。用Alpha-Beta剪枝的术语描述，$e$是一个MIN节点，其Beta值为2，祖先MIN节点的Alpha值是3，Beta值已经小于等于其祖先MAX节点的Alpha值，则停止搜索。这是一次Beta剪枝。
这种剪枝对子节点的排序非常敏感。
A*算法。
评估函数：
\[f(n) = g(n) + h(n)\]- $g(n)$是已知节点$n$距离起点的代价。
- $h(n)$是$n$距离终点的预计代价，这是一个启发函数。
- $f(n)$时综合优先级，在选择下一个要遍历的节点时，总会选取综合优先级$f(n)$最小的节点。
把最优评估函数记为：
\[f^*(n) = g^*(n) + h^*(n)\]- 由于还没有遍历完整张图，所以$g(n) \geq g^*(n)$。
- $h(n) \leq h^\ast(n)$时，一定能找到最短路径。此时称为$A\ast$算法。
自动推理
- 推理：从已知的判断（前提）推出一个新的判断（结论）的思维形式。
- 自动推理：主要指机器定理证明，其核心问题是寻找判定公式是否有效的(或者不一致的)通用程序。
命题演算
命题演算是命题逻辑的公理化，任务是使用演算手段来讨论命题逻辑。命题演算的形式系统包含：
- 代表命题的公式：由逻辑运算符（与或非，$\to$，=）、原子命题（PQRST……）构成。
- 形式证明规则：允许某些公式建构成定理。
语义
两个命题表达式在任何真值指派下都有相同的值，则称为是等价的。
推理
- 推理规则：代换、置换、分离。
- 推理策略：以宽度优先、目标驱动的方式将这些推理规则应用到要证明的定理中，用于尝试找到一系列操作，最终可以推导到公理或已知为真的定理。
子句
- 合取范式（CNF）：
- 析取范式（DNF）：
定理：对任意公式，都有与之等值的合取范式和析取范式。
一阶谓词逻辑
命题逻辑的缺陷
例：王平（主语）是大学生（谓语）
- 命题逻辑：$P$，不能把命题拆分成主语和谓语
- 谓词逻辑：$P(WangPing)$
语法
- 字母表
- 项：每一个变量和常数都是项，如果$u_1, \dots, u_n$是项，那么$f(u_1, \dots, u_n)$也是项，其中$f$是函词。函词与谓词不同，函词通常是个体到个体的映射，谓词是个体到${T, F}$的映射。
- 原子公式：如果$u_1, \dots, u_n$是项，那么$R(u_1, \dots, u_n)$是原子公式。
- 公式：每一个原子公式都是公式；如果$\phi$和$\psi$是公式，则$\neg\phi, (\phi),\forall x\phi, \exists x\phi, \phi\vee\psi, \phi\wedge\psi$也是。
推理规则
- 取式假言推理：如果已知语句P和$P\to Q$为真，那么$Q$为真。
- 拒式假言推理：如果已知$P\to Q$为真，且$Q$为假，那么$P$为假。
- 与消除：$P\wedge Q$为真，那么$P$、$Q$分别为真。
- 与引入：$P$和$Q$都为真， $P\wedge Q$为真。
- 全称例化：$\forall X P(X)$为真，且$a$为$X$定义域中一值，$P(a)$为真。
合一
合一算法：判断什么样的替换可以使两个谓词表达式匹配的算法。合一表明了：“两个或多个表达式在什么条件下可以称为等价的”。
例如，两个谓词表达式$man(X)$和$man(Y)$，合一的结果是不唯一的：
- ${Mike/X, Mike/Y}$，即用常元$Mike$替换$X$和$Y$。
- ${Male/X, Male/Y}$，即用变元$Male$替换$X$和$Y$。
这些结果都被称作“合一”。
替换
一个替换就是形如${t_1/x_1, t_2/x_2, \dots, t_n/x_n}$的有限集合，$x_1, \cdots, x_n$是互不相同的个体变元，$t_i$不同于$x_i$，$t_i/x_i$表示用$t_i$替换$x_i$。注意不能循环替换。两个例子：
- 例1：${a/x,g(y)/y, f(g(b))/z}$是一个替换
- 例2：${g(y)/x, f(x)/y}$则不是一个替换，因为$x$与$y$出现了循环替换。
斯柯伦标准化
去掉所有的存在量词。 例：
- $\exists Z (foo(Y, Z))$变成$foo(Y, k)$
如果谓词中含有多个参数，而$\exists$约束变元在$\forall$约束变元的约束范围内，则$\exists$约束变元必须是那些其他变元的函数。 例：
- $\forall X \exists Y (mother(X, Y))$变成$\forall X (mother(X, m(X)))$
组合
在合一过程中，如果先后产生$S$和$S’$的替换，那么将$S$中的某个元素应用$S’$，所产生的新的替换，称为组合。 例：
- 三个替换：${X/Y, W/Z}, {V/X}, {a/V, f(b)/W}$
- 观察前两个替换，$Y$被替换为$X$后，再替换为$V$，因此可以组合得到${V/Y, W/Z}$
- 观察第一个和第三个替换，$Y$被替换为$X$后，再替换为$a$，$Z$被替换为$W$之后，再替换为$f(b)$，因此可以得到${a/Y, f(b)/Z}$。
最一般的合一式
最一般的合一式(MGU, MOST GENERALIZE UNIFY)：如果$g$是表达式$E$的最一般合一式，那么对于任何的其他合一式$s$，都存在另一个合一式$s’$，使$Es=Egs’$。其中$Es$和$Egs’$是应用到表达式$E$的合一式的组合。
合一算法
- 递归地对表达式的初始成分进行合一。如果成功，这次合一返回的任何代入式被用到两个表达式的剩下部分，然后以这两个表达式为参数。
- 当两个参数之一为一个符号(谓词名，函词名，变元，常元)，或两个表达式的每一元素都已匹配了，算法终止。
归结
以反证法为基本思想：为了证明一个命题$P$恒真，则证明其反命题$\neg P$恒假。即不存在使得$\neg P$为真的解释。
消解是一种应用于谓词演算中的定理证明技术，是人工智能问题求解的一个组成部分。消解描述了如何用最少的合一次数在一个子句数据库中发现矛盾的方法。具体方法为目标驱动。
- 将已知为真的公理（转换成子句形式）加入集合中。
- 将所要证的命题取反（转换成子句形式），加入公理集中。
- 尝试用消解推理规则推出矛盾。
转换子句
子句应当只包含两种运算符：$\neg$和$\vee$。一些转换的手段：
- 消去蕴含：$a \to b$转换成$\neg a \vee b$
- 将否定式降至原子式
- 消除存在量词：斯柯伦标准化
- ……
归结（消解）策略
- 宽度优先策略
- 支持策略
- 单子句优先策略
知识表示
产生式系统
产生式规则
产生式：一组产生式，互相配合/协调，其中一个产生式产生的结论可以作为另一个产生式的事实使用，以求解问题。
主要架构
产生式系统由数据库、规则库、控制系统构成。
- 数据库：存放问题求解过程中的各种信息的数据结构，包括初始状态、原始证据、中间结论、最终结论。其内容在推理过程中在动态、不断变化的。
- 规则库：有效表达领域内的过程性知识。对知识进行合理的组织与管理，提高问题求解效率。
- 控制系统：从规则库中选择规则，并与数据库中的已知事实进行匹配。发生冲突时调用相应策略进行消解。如果执行规则的右部是一个或多个结论，则将结论加入到数据库中。如果执行规则的右部是一个或多个的操作，则执行这些操作，并将操作产生的事实加入到数据库中。对不确定性的知识，要计算结论的不确定性。在适当时候终止系统运行。
构造、推理
本质：深度优先搜索。
不确定性推理
DS证据理论
- 原理：基于收集到的证据数量，将概率论中的单点赋值扩展为集合赋值，处理由“不知道”所引起的不确定性。
- 形式定义：考虑命题集，赋给区间值[belief, plausibility]，每个命题的可信度必须在这个区间内。
- 从相关问题的主观概念得到其可信度的思想
- 基于相互独立的证据时，合并可信度的规则
信任函数与似然函数
- 信任函数
其中$A\subseteq \Omega$。$Bel$为下限函数，$Bel(A)$表示对A的总信任度。
- 似然函数
其中$A\subseteq \Omega, \neg A = \Omega - A$。$Pl$为上限函数，$Bel(\neg A)$表示对$\neg A$的总信任度，即$A$为假的信任度，因此$Pl(A)$表示对$A$为非假的信任度。
$A$不为假，并不代表$A$一定为真（$A$为命题集合，当情况较少时，对它的信念存在“不知道”，即无法判断的可能），即有：$Pl(A)≥Bel(A)$。$Pl(A)-Bel(A)$就是“不知道”的情况。
称$Bel(A)$和$Pl(A)$为对$A$信任程度的下限和上限，记为：$A[Bel(A), Pl(A)]$。
证据合并
Dempster证据合并规则：对于$\forall A \subseteq \Omega$，$\Omega$上的两个函数$m_1$和$m_2$，其Dempster合成规则为：
\[m_1 \oplus m_2(A) = \frac{1}{K}\sum_{B\cap C=A}m_1(B) \times m_2(C)\] \[K=\sum_{B\cap C \neq \emptyset} m_1(B)\times m_2(C) = 1 - \sum_{B\cap C = \emptyset}m_1(B)\times m_2(C)\]$K$为冲突因子，反应证据的冲突程度。$\frac{1}{K}$为归一化因子，相当于在组合中将空集（冲突）等比例分配给各个集合。
前提：证据是相互独立的。
例：假设在2001年911事件前，布什总统分别接到中央情报局(CIA)和国家安全局(NSA)的密报，内容是中东地区某组织要对美国发动突然袭击。其证据如下表。请给出证据合成后的结果。
| CIA | NSA | Bush | |
|---|---|---|---|
| {本} | 0.4 | 0.2 | ? |
| {萨} | 0.3 | 0.2 | ? |
| {霍} | 0.1 | 0.05 | ? |
| {本,萨} | 0.1 | 0.5 | ? |
| {本,萨,霍} | 0.1 | 0.05 | ? |
- {本}
- {萨}
- {霍}
- {本,萨}
- {本,萨,霍}
贝叶斯网络
先验概率与后验概率
- 先验概率：在得到任何新证据之前，统计的事件概率。即非条件概率$P(c)$。
- 后验概率：给定新证据之后，统计的事件概率。即条件概率$P(c \mid x)$。
贝叶斯定理
帮助我们在知道结果的时候反推原因。当知道某件事的结果后，由结果推断这件事是由各个原因导致的概率为多少。
推导：
\[P(H \mid E) = \frac{P(HE)}{P(E)}\] \[P(E \mid H) = \frac{P(HE)}{P(H)}\]综合以上两个公式，可得
\[P(H \mid E) = \frac{P(E \mid H)P(H)}{P(E)}\]即贝叶斯定理。
考虑事件$H_1, H_2, \dots, H_n$，可以得到更一般的形式
\[P(H_i \mid E) = \frac{P(E \mid H_i)P(H_i)}{\sum_{k=1}^nP(E \mid H_k)P(H_k)}\]贝叶斯网络
- DAG+概率分布表
- DAG的节点代表随机变量
- 边代表节点间的因果关系，用条件概率表达关系的强弱
- 没有父节点的用先验概率表达信息
D-seperation（有向分离）
考虑变量$x,y$的独立性，条件是变量集合${z}$。
- 将有向图转变为无向图（称为道德图）
- V形结构的父节点相连
- 有向边变成无向边
- 剪枝，仅保留图中$x,y,z$及其祖先节点。
- 若$x$和$y$能被$z$分入两个联通分支，则有$x \perp y \mid z$。
构建贝叶斯网络
- 定义变量：在领域专家指导下选取合适变量，或从中选择重要的因子。
- 结构学习：构建有向无环图。能够很好的解释数据，反应变量间的依赖关系或者独立性。
- 参数学习：学习节点的分布参数，即每条边对应的条件概率分布。
选择一组刻画问题的随机变量，并且确定一个变量顺序$a=<X_1, X_2, \dots, X_n>$。 参数学习从一个空图出发，按照顺序$a$逐个将变量加入$\epsilon$中。 假设当前需要加入的是变量$X_i$，此时$\epsilon$中已包含变量$X_1，X_2，\dots，X_{i-1}$。
- 在$X_1，X_2，\dots，X_{i-1}$选择一个尽可能小的子集$\pi(X_i)$，使得假设“给定$\pi(X_i)$，$X_i$与$\epsilon$中的其他变量条件独立”合理。
- 从$\pi(X_i)$中的每一个节点添加一条指向$X_i$的有向边。
- 结构学习：利用训练样本集，尽可能结合先验知识，确定和训练样本集合匹配最好的贝叶斯网络结构。
- 评分函数：评估贝叶斯网与训练数据的契合程度。利用评分函数，寻找与训练样本匹配最好的贝叶斯网络结构。
推理
- 因果推理(自顶向下的推理)：由原因推出结论，即根据一定的原因，推理出在该原因情况下结果发生的概率。
- 诊断推理(自底向上的推理)：由结论推出原因，即根据产生的结果，利用贝叶斯网推理算法，得出导致该结果的原因的概率。
- 支持推理：对所发生的现象提供解释，目的是分析原因之间的相互影响。
自顶向下
已知网络中的祖先节点而计算后代节点的条件概率。
- 首先，对于所求的询问节点的条件概率,用所给证据节点和询问节点的所有因节点的联合概率进行重新表达。
- 然后，对所得表达式进行适当变形, 直到其中的所有概率值都可以从问题贝叶斯网络的CPT中得到。
- 最后，将相关概率值代入概率表达式进行计算即得所求询问节点的条件概率。
例：假设已知某人吸烟($S$), 计算他患气管炎($T$)的概率$P(T \mid S)$。$T$有两个因节点感冒$C$和吸烟$S$。
\[P(T \mid S) = P(T, C \mid S) + P(T, \neg C \mid S)\]- 第一项：
- 第二项同理。
自底向上
已知网络中的后代节点而计算祖先节点的条件概率。先利用贝叶斯公式将诊断推理问题转化为因果推理问题; 再用因果推理的结果, 导出诊断推理的结果。
假设已知某人患了气管炎($T$), 计算他吸烟($S$)的后验概率$P(S \mid T)$。
\[P(S \mid T) = \frac{P(T \mid S)P(S)}{P(T)}\]自顶向下计算出$P(T \mid S)$，然后可以使用贝叶斯定理逆推$P(T \mid S)$。
例：考虑以下的贝叶斯网络，其中布尔变量B代表是否触犯法律，I代表被起诉，M代表被检举，G代表被发现有罪，J代表进监狱。请回答下面的问题：
B --> I <-- M
\ /
\ /
-> G <-
|
v
J
| $P(B)$ |
|---|
| 0.9 |
| $P(M)$ |
|---|
| 0.1 |
| $B$ | $M$ | $P(I)$ |
|---|---|---|
| t | t | 0.9 |
| t | f | 0.5 |
| f | t | 0.5 |
| f | f | 0.1 |
| $B$ | $I$ | $M$ | $P(I)$ |
|---|---|---|---|
| t | t | t | 0.9 |
| t | t | f | 0.8 |
| t | f | t | 0.0 |
| t | f | f | 0.0 |
| f | t | t | 0.2 |
| f | t | f | 0.1 |
| f | f | t | 0.0 |
| f | f | f | 0.0 |
| $G$ | $P(J)$ |
|---|---|
| t | 0.9 |
| f | 0.0 |
- 网络结构能够断言下列哪些语句？
- $P(B, I, M) = P(B)P(I)P(M)$
- $P(J\mid G) = P(J\mid G, I)$
- $P(M\mid G, B, I) = P(M\mid G, B, I, J)$
2和3。
- 计算$P(b, i, \neg m, g, j)$的值。
- 计算某个人如果触犯了法律、被起诉、而且被人检举、他会进监狱的概率。
马尔可夫网络
基本定义
- 闭谓词：不包含变元的谓词。
- 一个可能世界(A Possible World)：为每个可能的闭谓词指定真值。
- 可满足：一个一阶公式是可满足的，当且仅当该公式至少在一个世界中为真。
- 一阶逻辑的推理：判断一个知识库中是否包含公式F，即F是否在所有满足知识库的世界中为真。
马尔可夫逻辑网
- 基本思想：将一阶逻辑的限制放松，即一个可能世界违反公式越多，其发生的概率越小，但未必为0。
- 公式权重：表示公式限制强度的大小。权值越大，满足该公式世界的发生概率与不满足该公式世界的发生概率之间的差越大。
- 定义：
- 马尔科夫逻辑网$L$：是$(F_i, w_i)$对的集合，其中$F_i$代表一阶逻辑规则，$w_i$是用一个实数表示权重；有限的常数集为$C = {c_1, c_2, \dots, c_n}$。
- 马尔科夫逻辑网$M_{L,C}$：
- $L$中的任意闭原子（ground atom）都对应了$M_{L,C}$中的一个二值节点。若此闭原子为真，则对应的二值节点取值为1；若为假，则取值为0。
- $L$中的任意闭规则（ground formula）都对应着一个特征值。若此闭规则为真，则对应的特征值为1；若为假，则特征值为0。并且这个特征值Fi的权重为二元项中该规则对应的权重wi。
独立性：
-
Pairwise Markov Property: 给定所有其他变量，任意两个不相邻变量条件独立。
\[X_u \perp\!\!\!\!\perp X_v \mid X_{V \backslash \{u, v\}} \quad \mathrm{if} \{u, v\} \notin E\] -
Local Markov Property：一个变量如果给定所有邻居变量后与所有其他变量条件独立。
\[X_v \perp\!\!\!\!\perp X_{V \backslash \mathrm{cl}(v)} \mid X_{\mathrm{ne}(v)}\] -
Global Markov Property：A、B两个子集间任何一条路径都经过子集S，则给定S后，A、B两个子集相互条件独立
\[X_A \perp\!\!\!\!\perp X_B \mid X_S\]
与贝叶斯网的比较
- 贝叶斯网络：有向图+概率分布
- 马尔可夫网络：无向图+概率分布
无法构造贝叶斯网络的例子
一个班上有四名同学，A、B、C、D，他们每次做作业都会与其他人讨论，但是由于某种不明的原因，A和C、B和D从不一起讨论。当老师上课讲错知识点时，每个学生有一定几率自己发现这个错误，当他发现错误时有可能将这个发现告诉自己讨论的对象。
- $A \perp C \mid {B, D}$
- $B \perp D \mid {A, C}$
推理
条件概率查询(Conditional Probability Query)
给定证据，其他变量的一组特定取值具有怎样的概率？
- 证据：$\vec{E}$ = $\vec{e}$
- 查询：变量子集$\vec{Y}$
- 计算：$P(\vec{Y} \mid \vec{E} = \vec{e})$
最大化后验(Maximum a Posterior, MAP)
给定证据，其他变量的哪组取值具有最大的概率？
- 证据： $\vec{E} = \vec{e}$
- 查询：所有其他变量$\vec{Y}(\vec{Y} = {X_1, X_2, \dots, X_n} - \vec{E})$
- 计算： $MAP(\vec{Y} \mid \vec{E}=\vec{e}) = \arg\max_{\vec{y}}P(\vec{Y}=\vec{y} \mid \vec{E} = \vec{e})$
变量消除
基本思想
为得到精确解，必须计算和积。通常一个变量不会出现在所有的因子中。
- 根据给定的证据，得出需要约简的因子集$\Phi$
- 对每一个非查询的变量$X$，将其从$\Phi$消除
- 连乘所有余下的因子
- 正则化……
应用场景
- 对BN和MN均有效
- BN中计算的是条件概率分布
- MN中计算的是势函数
- 任何一种消除次序都可以导致正确的结果
- 计算复杂性NP-hard
符号学习
决策树：基于树结构进行决策。
ID3算法
ID3(Examples, Attributes)
1. 创建树的Root结点
2. 如果Examples的目标属性均为正，那么返回label=‘+’的单结点树Root
3. 如果Examples的目标属性均为反，那么返回label=‘-’的单结点树Root
4. 如果Attributes为空，那么返回单结点树Root，label设置为Examples中最普遍的目标属性值
5. 否则
A<-Attributes中分类Examples能力最好的属性
Root的决策属性<-A
对于A的每个可能值vi
令Examplesvi为Examples中满足A属性值为vi的子集
如果Examplesvi为空
在这个分支下加一个叶子结点，结点的label设置为Examples中最普遍的目标属性值
否则，在这个分支下加一个子树ID3(Examplesvi, Attributes-{A})
6. 结束，返回树Root
信息熵、信息增益
信息熵是度量样本集合$S$的纯度。
\[Ent(S) = -\sum_{i=1}^{c}-p_i\log_2p_i\]其中$p_i$是第$i$类样本在$S$中所占的比例。约定$p=0$时$p\log_2p=0$。
使用属性$A$对样本集合$S$进行划分。根据信息熵公式计算出划分出的子集的信息熵，根据样本数量为子集赋予权重，获得信息增益：
\[Gain(S, A) = Ent(S) - \sum_{v \in Values(A)}\frac{ \mid S_v \mid }{ \mid S \mid }Ent(S_v)\]信息熵越大，带来的纯度提升越大。
神经网络
神经元
- 输入：$X = [x_1, x_2, \dots, x_n]$
- 权值：$W = [w_1, w_2, \dots, w_n]$
- 阈值：$\theta$
- 激励函数：$f(net)=f(\sum(x_iw_i - \theta))$
- Sigmoid函数：$f(x) = \frac{1}{1+e^{-\lambda x}}$
- Relu函数：$f(x) = \max(x, 0)$
反向传播算法
给定训练集$D={(X_1, Y_1), (X_2, Y_2), \dots, (X_m, Y_m)}$，$X_i\in \mathbb{R}^d$，$Y_i\in \mathbb{R}^l$。 那么，神经网络有
- $d$个输入，相应地有$d$个输入神经元；
- $l$个输出，相应地有$l$个输出神经元；
- 假设一个隐层，隐层中有$q$个神经元。
假设使用sigmoid激活函数。
反向传播（Back Propagation）算法的过程如下：
- 初始化：对网络中所有连接权、阈值随机赋值。
- 重复以下过程，直到达到停止条件
- 对于训练集中的每组数据
- 前向计算：按照当前的权值、阈值，计算输出
- 反向计算：
- 计算输出层神经元梯度
- 计算隐层神经元梯度
- 更新连接权值、阈值
前向传播
假设第$k$个训练例$(X_k, Y_k)$的前向传播计算结果是$\hat{Y}_k = (\hat{y}_1^k, \hat{y}_2^k, \dots, \hat{y}_l^k)$， 其中$\hat{y}_j^k = f(\beta_j - \theta_j)$。则网络在$(X_k, Y_k)$上的均方误差是：
\[E_k = \frac{1}{2}\sum_{j=1}^l (\hat{Y}_j^k - Y_j^k)^2\]反向传播
基于梯度下降策略，以目标的负梯度方向对参数进行调整。以$w_{hj}$为例。 对误差$E_k$，给定学习率$\eta$，有：
\[\Delta w_{hj} = -\eta\frac{\partial E_k}{\partial w_{hj}}\]注意到$w_{hj}$先影响到$\beta_j$，再影响到$\hat{Y}^k_j$，然后影响到$E_k$，因此要利用链式法则。
\[\frac{\partial E_k}{\partial w_{hj}} = \frac{\partial E_k}{\partial \hat{Y}^k_j} \cdot \frac{\partial \hat{Y}^k_j}{\partial \beta_j} \cdot \frac{\partial \beta_j}{\partial w_{hj}}\]其中
- $\frac{\partial E_k}{\partial \hat{Y}^k_j} = \hat{Y}^k_j - Y^k_j$
- $\frac{\partial \hat{Y}^k_j}{\partial \beta_j} = f’(\beta_j - \theta_j)$
- $\frac{\partial \beta_j}{\partial w_{hj}} = b_h$
为什么一层网络不能解决异或问题
单层的神经网络只能解决线性问题，即可以用一个线性超平面划分的问题。然而，异或问题不是线性的，因此需要多层神经网络才能解决。
遗传算法
基本操作算子，如交叉、变异等等
1. t:=0，初始化种群P(t);
2. 如果不满足终止条件
评估种群P(t)中每个染色体的的适应度
根据适应度函数选择部分染色体
根据所选择的染色体产生后代
根据P(t)中染色体的的适应度，选择被替换的染色体，以后代替换
t:=t+1
3. 终止
染色体的表示
二进制位串的编码。
适应度函数
就是估价函数。
染色体的选择
基于适应度函数进行选择
- 轮盘赌选择：与适应度成比例选择
- 锦标赛选择
- 按预定义概率$p$选择较大适应度的假设（利用）
- 按概率$1-p$选择其他假设（探索）
- 排序选择：根据序而不是适应度进行选择
遗传算子
- 交叉：选择两个候选个体，分解每一个个体，然后交换分量形成两个新的候选个体。
- 变异：选择一个候选个体，随机的选择一位，然后取反。
强化学习
MDP模型
MDP即Markov Decision Process（马尔科夫决策过程）。 机器处于环境$E$中，状态空间为$X$，动作空间$A$，转移函数$P: X \times A \times X \to \mathbb{R}$使得环境从当前状态按某种概率转移到另一个状态，在转移的同时，环境会根据潜在的奖赏函数$R: X \times X \to R$反馈给机器一个奖赏。 综合起来，强化学习任务对应了马尔科夫四元组$E=<X, A, P, R>$。
动态规划
假定马尔可夫决策过程四元组$E=<X, A, P, R>$已知，即“模型已知”。
- $V^{\pi}(s)$：从$s$状态出发，采用$\pi$策略，所获得的期望返回值。
- $Q^{\pi}(s, a)$：从$s$状态出发，采用$a$动作，继而采用$\pi$策略，所获得的期望返回值。
- 最优值函数$V^\ast(s)$和$Q^\ast(s, a)$：采用最优策略$\pi^*$所获得的期望返回值。
贝尔曼等式
下面用到的一些标记：
- $\pi(x, a)$表示策略$\pi$在状态$x$下选择$a$的概率。
- $x$状态下执行动作$a$，
- $P_{x \to x’}^a$表示转移到$x’$的概率。
- $R_{x \to x’}^a$表示转移到$x’$的奖赏。
状态值函数可以写成：
-
$T$步累积奖赏
\[V_T^{\pi}(x) = \sum_{a\in A}\pi(x, a)\sum_{x'\in X}P_{x\to x'}^a(\frac{1}{T}R_{x\to x'}^a + \frac{T-1}{T}V_{T-1}^\pi(x'))\] -
$\gamma$折扣奖赏
\[V_\gamma^{\pi}(x) = \sum_{a\in A}\pi(x, a)\sum_{x'\in X}P_{x\to x'}^a(R_{x\to x'}^a + \gamma V_\gamma^\pi(x'))\]
这样的递归等式称为贝尔曼等式。 由此，也可以计算出状态-动作值函数。
\[Q_T^\pi(x, a) = \sum_{x'\in X}P_{x\to x'}^a (\frac{1}{T} R_{x\to x'}^a + \frac{T-1}{T} V_{T-1}^\pi (x'))\] \[Q_\gamma^\pi(x, a) = \sum_{x'\in X}P_{x\to x'}^a (R_{x\to x'}^a + \gamma V_\gamma^\pi(x'))\]理想的策略应能最大化累积奖赏：
\[\pi^* = \arg\max_{\pi}\sum_{x\in X}V^\pi(x)\]最优策略对应的值函数称为最优值函数，即
\[\forall x\in X: V^*(x) = V^{\pi^*}(x)\]最优情况下，状态值函数：
-
$T$步累积奖赏
\[V_T^*(x) = \max_{a\in A}\sum_{x'\in X}P_{x\to x'}^a(\frac{1}{T}R_{x\to x'}^a + \frac{T-1}{T}V_{T-1}^*(x'))\] -
$\gamma$折扣奖赏
\[V_\gamma^*{\pi}*(x) = \max_{a\in A}\sum_{x'\in X}P_{x\to x'}^a(R_{x\to x'}^a + \gamma V_\gamma^*(x'))\]
即$V^\ast(x)=\max_{a\in A}Q^{\pi^\ast}(x, a)$。
最优控制
- 贪心策略
- 一直选择$\pi(s) = \arg\max_a Q^\pi(s, a)$
- $\epsilon$-贪心策略
- 以$1 - \epsilon$概率选择$\pi(s) = \arg\max_a Q^\pi(s, a)$
- 以$\epsilon$概率选择其他动作
博弈
帕累托优
- 若某资源配置下，存在一种调整可以使得所有人的境况都不变差的前提下，有至少一个人的境况变好，则该资源配置不是帕累托最优。
- 反之，若不存在这样的调整，则该配置可以被称作帕累托最优。
纳什均衡
给定其他博弈者策略不变，每一个博弈者都没有动机改变自己的策略，即使改变策略也不会提高自身的收益。此时各博弈者的策略组合称为纳什均衡。
例：囚徒困境
| 囚犯B坦白 | 囚犯B抗拒 | |
|---|---|---|
| 囚犯A坦白 | $(-5, -5)$ | $(0, -10)$ |
| 囚犯B抗拒 | $(-10, 0)$ | $(-1, -1)$ |
- 帕累托优：除了<坦白，坦白>以外的其他情况
- 纳什均衡：<坦白，坦白>
投票
投票机制的原则
- 帕累托最优：对于所有选民的投票，如果A都在B之前，那么最后的结果A一定在B之前。
- 无关因素独立性：两个人的相关顺序不变的话，其他参与者的相对位置发生了变化，那么这两个人的相对位置也不会发生变化。 投票问题中，假如有四个候选人，即A、B、C和D，如果大多数民众（即超过一半）一致认为A优于C，那么B和D的相对位置发生了变化，也不会影响大多数民众的偏好上A优于C。
- 非独裁：不存在这样的选民，使得他的选择一定为最终结果。