考试大纲¶
第 2 章¶
归纳学习：FOIL 算法¶
- 把目标谓词作为所学习推理规则的结论。
- 把其他的谓词逐一作为前提约束加入推理规则，计算 FOIL 的信息增益值。把增益值最大的一个加入原来的推理规则，并把不符合规则的样例去掉。
- 重复上一步直到没有反例为止。
\(FOIL\_Gain = \hat{m_+} \times (\log_2 \frac{\hat{m_+}}{\hat{m_+} + \hat{m_-}} - \log_2 \frac{m_+}{m_+ - m_-})\)
贝叶斯网络¶
一个 DAG，用有向边表示节点和节点的单项概率依赖。
它满足局部马尔可夫性：给定一个节点的父节点的情况下，该父亲节点有条件地独立于它的非后代节点。
马尔可夫网络¶
一个无向图，无向边表示节点和节点之间相互的概率依赖。
\(P(X = x) = \frac{1}{Z} \exp (\sum_i w_i n_i(x))\)
辛普森悖论：虚假关联¶
- 因果关联：T -> Y
- 混淆偏差：X -> T, X -> Y
- 选择偏差：T -> S, Y -> S
do 算子：\(do(X)\) 相当于在概率图里面把指向 X 的边都移除。
因果模型的层次化¶
- 可观测问题
- 决策行动问题
- 反事实问题（事情已经发生，则在相同环境中，这个事情不发生 / 发生不一样的事情会带来什么新结果）
第 3 章¶
贪婪最佳优先搜索算法¶
评价函数 f(n)：从当前节点 n 出发，判断该选择哪个后续节点的函数。
启发函数 h(n)：从节点 n 到目标节点之间的最小代价值。
对于贪婪算法：f(n) = h(n)，从终点开始跑。
时间复杂度：\(O(b^m)\)，b 是分支数，m 是最大深度。
空间复杂度：\(O(b^m)\)。
A* 搜索算法¶
f(n) = g(n) + h(n)，g(n) = 起始节点到节点 n 代价，h(n) = 节点 n 到目标节点的最小代价估计值。
可容性：h(n) 总小于真实代价 h*(n)。
一致性：h(n) <= c(n, a, n') + h(n')，称为启发函数的一致性。满足一致性的启发函数一定满足可容性。
如果启发函数是可容的，那么 A* 算法满足最优性。
Minimax 搜索 / 对抗搜索 / 博弈搜索，alpha-beta 剪枝¶
ADS 内容
蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）¶
要素：状态、动作、状态转移、奖励、悔值函数
悔值函数 \(\rho_T = T\mu^* - \sum_{i=1}^{T}\hat{r}_t\)，即最优策略下的得分减去实际得分。
\(\epsilon\)-贪心算法：有 \(\epsilon\) 的概率随机选择。
上限置信区间（UCB1）¶
为每个动作的奖励期望计算一个估计范围，优先选择估计范围更大的动作。
设 \(\bar{x}_{i, T_{(i, t-1)}}\) 是对动作 \(a_i\) 探索了 \(T_{(i, t-1)}\) 次所得到的收益均值。那么第 \(t\) 次选择 \(l_t = \argmax_i (\bar{x}_{i, T_{(i, t-1)}} + C \sqrt{\frac{2 \ln t}{T_{(i, t-1)}}})\)。
利用蒙特卡洛采样方法在搜索树上采样来估计每个节点这样的价值，就是蒙特卡洛树搜索算法。
步骤：选择、扩展、模拟（直到终止节点，计算价值）、反向传播。
第 4 章¶
监督学习通过带有标签的训练集，学习一个从输入到输出的映射函数 f。
无监督学习的数据没有标签，半监督学习的数据有些有标签而有些没有。
训练集、验证集、测试集：练习册、小测、期末考。
在训练集上的性能和在测试集上一样，说明模型具有泛化能力。
损失函数¶
损失函数是预测值和真实值之间的差异。
映射函数在训练集上产生的损失为经验风险（不等于用所有数据中计算出来的期望风险）。
结构风险是在模型变得复杂的时候产生的风险，通过把最小化函数添加 \(\lambda J(f)\) 来控制，其中 \(J(f)\) 叫正则化因子或者惩罚因子。
模型度量方法¶
TP、TN：判断对了的正例、判断对了的反例。
FP、FN：判断错成正例（应该是反例）、判断成反例（应该是正例）。
准确率：ACC = (TP + TN) / 所有
错误率：errorRate = (FP + FN) / 所有
精确率：precision = TP / (TP + FP)
召回率：recall = TP / (TP + FN)
综合分类率 F1-score = \(2 / (\frac{1}{precision} + \frac{1}{recall})\)
决策树¶
假设有 K 个信息，组成了集合样本 D。第 \(k\) 个信息发生的概率是 \(p_k\)，概率加起来等于 1。定义信息熵：
\(E(D) = - \sum_{k=1}^K (p_k \log_2 p_k)\)
熵越小说明 D 包含的信息越稳定，也称 D 的纯度越高。
K 均值聚类¶
把某些数据划分成 K 个簇，满足簇内方差最小（最小化类内距离），并且最大化类间距离。找到的是局部最优解。
线性判别分析 LDA¶
把高维数据投影到低维，使类内方差最小，并且最大化类间距离。
- 计算数据样本集里面每个类型的均值
- 计算类内散度矩阵 \(\mathbf{S}_w\) 和类间散度矩阵 \(\mathbf{S}_b\)
- 根据 \(\mathbf{S}_w^{-1} \mathbf{S}_b \mathbf{W} = \lambda \mathbf{W}\) 求解 \(\mathbf{S}_w^{-1} \mathbf{S}_b\) 前 r 个最大特征值所对应的特征向量以构成矩阵 \(\mathbf{W}\)
- 通过 \(\mathbf{W}\) 进行数据降维
主成分分析¶
主成分分析会找到数据特征的主要成分，并且用它们替代原始数据。主成分分析要求最大限度保持原始高维数据的总体方差结构。
其将原始数据向这些数据方差最大的方向进行投影，然后是第二大的，等等。
- 把样本去中心化。
- 计算其协方差矩阵。
- 对协方差矩阵进行特征值分解。
- 取前几个最大的特征根所对应的特征向量作为映射矩阵。
演化算法¶
通过突变重组和自然选择两种机制模拟自然演化过程。
- 初始化若干群体
- 计算每个染色体的适应值
- 使用轮盘赌算法对群体中染色体进行选择，产生同样规模的种群
- 种群之间交叉产生染色体
- 变异
- 计算适应值
- 重复直到达到要求
第 5 章¶
Sigmoid 函数 \(f(x) = \frac{1}{1 + e^{-x}}\)；\(f'(x) = f(x) (1 - f(x))\)
ReLU 函数 \(f(x) = x\ if\ x \geq 0\ else\ 0\)
Softmax 函数相当于一个归一化过程：\(softmax(x_i) = e^{x_i} / \sum_{j=1}^{k} e^{x_j}\)
神经网络的损失函数¶
均方误差损失函数 \(MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2\)
交叉熵损失函数 \(H(y_i, \hat{y}_i) = - y_i \times \log \hat{y}_i\)
梯度下降法¶
在多元函数中，梯度是对每一个变量所求导数组成的向量。梯度的反方向就是函数值下降最快的方向。给损失函数求梯度就可以获得参数需要变动的方向。
- 批量梯度下降：在整个训练集上计算损失误差。内存消耗量大。
- 随机梯度下降：使用每个样本分别更新参数。收敛速度慢，随机性大，更有可能跳出局部最优解。
- 小批量梯度下降：选取样本里的一小批计算损失误差。最常用。
误差反向传播¶
使用链式求导法则，从损失函数开始求导，找到损失函数对于每个参数的偏导。
卷积神经网络¶
填充：超过边界的位置填充 0。
步长：卷积核每次移动的像素数量。
池化¶
最大池化：选择值最大的像素点。
平均池化：选择像素点的均值。
k-max 池化：选择前 k 大的像素点。
循环神经网络¶
在接收当前输入数据 \(x_t\) 的时候，还会接收上一时刻的隐式编码结果 \(h_{i-1}\)，生成当前的隐式编码结果 \(h_t\)。
长短时记忆模型 LSTM¶
存在输入门、遗忘门和输出门三种结构。可以避免梯度消失问题。
注意力机制¶
对所有单词向量 \(w_i\)，训练三个映射矩阵，得到查询向量 \(q_i = W^q \times w_i\)、键向量 \(k_i = W^k \times w_i\) 和值向量 \(v_i = W^v \times w_i\)。
- 计算某个单词的查询向量和键向量的点积：\(a_{i, j} = q_i \cdot k_j\)，并且归一化得到 \(a'_{i, j}\)
- 拿它乘每个单词对应的值向量 \(a'_{i, j} \times v_j\) 并求和。结果为单词 \(w_i\) 注意到与其他单词的关联程度。
神经网路正则化¶
- Dropout：每次迭代的时候随机屏蔽每一层的若干神经元。
- 批归一化：把输入值映射到标准正态分布。
词向量生成¶
One-hot：对某个单词生成一个向量，根据在文档中指定位置有没有出现取值 0 或者 1。
词向量（Word2Vec）：单词向量在向量空间所计算的结果可以用来衡量两个单词之间的相似度。
Word2Vec¶
现在有 V 个不同的单词。在有 V 个元素的输入层和输出层之间放一个有 N 个元素的隐藏层。
输入层通过 \(W_{V \times N}\) 变换到隐藏层（\(W_{V \times N}^T \times X\)），再通过 \(W'_{N \times V}\) 变换到输出层。对于第 k 个词，损失函数是 \(-y^*_k + \log (\sum_{j=1}^{V} e_{y_j})\)。这样就可以训练 \(W_{V \times N}\) 和 \(W'_{N \times V}\)。\(W_{V \times N}\) 里面放的就是 V 个单词的 N 维词向量。
CBoW¶
现在有一个包含 c 个单词的句子，对于第 k 个单词，把除了它之外所有单词的词向量加起来训练，要求输出层的 k 对应的位置最大。
Skip-gram¶
相当于 CBoW 反过来，用某个词去预测它的背景词。
第 6 章¶
强化学习的学习依据基于评估，数据在时序交互中产生。
离散马尔可夫链¶
当前时刻的状态之和前一个时刻的状态相关。
回报：反应某个状态的未来几个时刻能获得的回报：\(G_t = R_{t + 1} + \gamma R_{t + 2} + \gamma ^ 2 R_{t + 3} + \cdots\)，其中 \(\gamma \in [0, 1]\) 是折扣因子。
马尔可夫决策过程 MDP¶
\(MDP = (S, A, P, R, \gamma)\)，分别是状态集合、动作集合、状态转移概率、奖励函数和折扣因子。
状态序列叫做轨迹。如果包含终止状态则是分段问题，否则是持续问题。一个从初始状态到终止状态的完整轨迹称为一个片段。
- 策略函数 \(\pi(s, a)\)：智能体在 s 状态下采取动作 a 的概率。
- 价值函数 \(V_\pi (s)\)：智能体处于 s 状态时按照策略 \(\pi\) 采取行动的时候所获回报的期望。
- 动作-价值函数 \(q_\pi (s, a)\)：智能体处于 s 状态时先选取动作 a，之后再按照策略 \(\pi\) 采取行动的时候所获回报的期望。
现在需要学习一个最优策略 \(\pi\)。
贝尔曼方程 / 动态规划方程¶
\(V_\pi (s) = E_\pi [R_{t + 1} + \gamma R_{t + 2} + \gamma ^ 2 R_{t + 3} + \cdots | S_t = s]\)
\(= E_{a \sim \pi(s, \cdot)} [E_\pi [R_{t + 1} + \gamma R_{t + 2} + \gamma ^ 2 R_{t + 3} + \cdots | S_t = s, A_t = a]]\)
\(= \sum_{a \in A} \pi (s, a) q_\pi (s, a)\)
\(= E_{a \sim \pi(s, \cdot)} E_{s' \sim P(\cdot | s, a)} [R(s, a, s') + \gamma V_\pi (s')]\)
当前状态价值函数等于瞬时奖励的期望加上后续状态的（折扣）价值函数的期望。
\(q_\pi (s, a) = E_\pi [R_{t + 1} + \gamma R_{t + 2} + \gamma ^ 2 R_{t + 3} + \cdots | S_t = s, A_t = a]\)
\(= \sum_{s' \in S} P(s' | s, a) (R(s, a, s') + \gamma V_\pi (s'))\)
\(= E_{s' \sim P(\cdot | s, a)} [R(s, a, s') + \gamma E_{a' \sim \pi (s', \cdot)} [q_\pi (s', a')]]\)
动作-价值函数等于瞬时奖励的期望加上后续状态的（折扣）动作-价值函数的期望。
策略优化¶
策略优化定理：如果两个策略 \(\pi, \pi'\) 满足 \(q_\pi (s, \pi' (s)) \geq q_\pi (s, \pi (s))\)，那么 \(V_{\pi'}(s) \geq V_{\pi}(s)\)，即策略 \(\pi'\) 不比 \(\pi\) 差。
策略评估¶
动态规划¶
迭代求解贝尔曼方程组，即每次枚举状态来更新它的价值函数。
蒙特卡洛采样¶
- 选择不同的起始状态，按照当前策略 \(\pi\) 采样若干轨迹，设它们的集合为 D
- 对于所有的状态 s，用它在 D 中出现的时候对应的值更新价值函数
时序差分¶
直到价值函数收敛，一直重复从初始状态走到终止状态的过程。在这个过程中更新价值函数。
\(V_\pi (s) = (1 - \alpha) V_\pi (s) + \alpha (R(s, a, s') + \gamma V_\pi (s'))\)
基于价值的强化学习算法¶
在策略评估动态规划法的基础上，每次迭代只对一个状态进行策略评估和策略优化，就可以得到价值迭代算法。
Q 学习算法¶
Q 学习算法更新的是动作-价值函数而不是价值函数，因为不知道转移概率的情况下靠价值函数求不出来动作-价值函数。
探索与利用¶
引入 \(\epsilon\) 贪心策略，每次有 \(\epsilon\) 的概率随机选择动作。
深度 Q 网络 DQN¶
使用经验重现方法：把算法探索的片段 \((s, a, R, s')\) 四元组存在一张表里面；更新参数 \(\theta\) 的时候随机一批样本用于计算损失函数。
损失函数 \(L(\theta) = \frac{1}{2} (R + \gamma \max_{a'} q_\pi (s', a'; \theta ^-) - q_\pi (s, a; \theta))^2\)，其中以较低的频率更新 \(\theta ^- \leftarrow \theta\)。
策略梯度定理，基于蒙特卡洛采样法的策略梯度算法，REINFORCE 算法¶
如果能够计算或者估计策略函数的梯度，那么就可以直接对策略函数进行优化。
\(\nabla_\theta J(\theta) \propto E_{s, a \sim \pi} [q_{\pi_\theta} (s, a) \nabla _\theta \ln \pi _\theta (s, a)]\)
基于时序差分的策略梯度算法，Actor-Critic 算法¶
使用下一时刻状态的价值函数来估计当前状态的价值函数，而不是使用整个片段的反馈值。
第 7 章¶
虚拟遗憾最小化算法¶
最优反应策略 \(\sigma _i^*\) 满足 \(u_i(\sigma_i^*, \sigma_{-i}) \geq \max u_i(\sigma_i, \sigma_{-i})\)。如果每个玩家的策略相对于其他玩家的策略而言都是最佳反应策略，那么策略组合就是一个纳什均衡。在有限对手、有限策略情况下，纳什均衡一定存在。
累加遗憾值：\(Regret_i^T (\sigma_i) = \sum_{t=1}^T (u_i (\sigma_i, \sigma_{-i}^t) - u_i(\sigma^t))\)
有效遗憾值：\(Regret_i^{T, +} (\sigma_i) = \max (Regret_i^T, 0)\)
在第 T 轮后，如果 \(\sum_{\sigma_i' \in \Sigma_i} Regret_i^{T, +} (\sigma_i') > 0\)，那么第 T + 1 轮选择策略 \(\sigma_i\) 的概率为：\(P(\sigma_i^{T + 1}) = Regret_i^{T, +} (\sigma_i) / \sum_{\sigma_i' \in \Sigma_i} Regret_i^{T, +} (\sigma_i')\)，否则就平均选。
虚拟价值¶
对于所有玩家的策略组合 \(\sigma\)，行为序列 h 出现的概率是 \(\pi^\sigma (h)\)。从根节点到达当前节点的信息集合为 I，则 \(\pi^\sigma (I) = \sum_{h \in I} \pi^\sigma (h)\)。
对于终结局势 \(z \in Z\)，玩家 i 在这个局势下的收益记作 \(u_i (z)\)。给定行动序列 h，依照策略组合 \(\sigma\) 最终到达终结局势 z 的概率为 \(\pi^\sigma (h, z)\)。
在策略组合 \(\sigma\) 下，对于玩家 i 而言，从根节点到当前节点的行动序列 h 的价值为：
\(v_i(\sigma, h) = \sum_{z \in Z} \pi_{-i}^\sigma (h) \times \pi^\sigma (h, z) \times u_i(z)\)
即先不考虑 i 的策略（每次都选择路径 h 相应的动作），然后再计算走到某个叶子节点的概率和相应的收益。
定义行动 a 的遗憾值：\(r_i (h, a) = v_i (\sigma _{I \to a}, h) - v_i (a, h)\)。
对于信息集 I：\(r_i (I, a) = \sum_{h \in I} r_i (h, a)\)。
虚拟遗憾最小化的遗憾值是 T 轮重复博弈后的累加：\(Regret^T_i(I, a) = \sum _{t=1}^{T} r_i^t (I, a)\)；类似地定义有效遗憾值和用遗憾值选择的概率。
安全子博弈¶
从当前已经完成的部分博弈出发，将接下来的博弈过程视作一个单独子博弈以减少计算量。