人工智能基础

大二下学期人工智能基础的复习笔记，目前已完结。含自学的状态空间模型和采样方法。

一、搜索

1. A* 算法

1. 可采纳性（Admissibility）：$0\leq h(n) \leq h^*(n)$，A* 树搜索保证最优性
2. 地标差分启发式：$h(n) = \max_{l\in L} |C^*(n,l)-C^*(l,T)|$，满足可采纳性（三角不等式）
3. 一致性（Consistency）：$h(n)-h(n^\prime) \leq c(n,n^\prime)$，A* 图搜索保证最优性，强于可采纳性
4. 性质证明：$h(n)\leq h^*(n)+C_1\Rightarrow g(T)\leq h^*(S)+C_1$；$h(n)\leq C_2\cdot h^*(n)\Rightarrow g(T)\leq C_2\cdot h^*(S)$

二、学习

1. 基本概念

1. 贝叶斯误差/最优误差 Bayes/Optimal Error：目标函数（最优分类器）在测试集上的误差
2. 精确率 Precision：$\frac{TP}{TP+FP}$
3. 召回率/灵敏度/真正率 Recall/Sensitivity/TPR：$\frac{TP}{TP+FN}$
4. 准确率 Accuracy：$\frac{TP+TN}{TP+FP+TN+FN}$
5. 假阳性率 FPR：$\frac{FP}{FP+TN}$
6. 特异度 Specificity：$1-\text{FPR}$
7. 误差 Error：$1- \text{Accuracy}$
8. F1-Score：$\frac{1}{F_1} = \frac{1}{2}\left(\frac{1}{\text{Precision}}+\frac{1}{\text{Recall}}\right)$
9. ROC 曲线：横轴 FPR，纵轴 TPR，对模型输出的分数 $f(x)$ 设置不同阈值时 (FPR, TPR) 的变化曲线，曲线下面积 AUC 越大越好

2. 决策树

1. $H(D)=-\sum_{i=1}^k \frac{|C_i|}{|D|} \log_2 \frac{|C_i|}{|D|}$，信息增益 Information Gain：$H(D)-\sum_{i=1}^k \frac{|D_i|}{|D|} H(D_i)$
2. 内在值 Intrinsic Value：$-\sum_{i=1}^k \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}$，增益率 Gain Ratio：$\frac{\text{Information Gain}}{\text{Intrinsic Value}}$
3. 代价 Cost：$\frac{(\text{Gain Ratio})^2}{\text{Cost}}$
4. 缺失值：用完整数据计算 GR 再乘以缺失率，再将缺失数据按比例分配到子节点
5. 连续值：选取切分点
6. 剪枝：预剪枝（每次分叉时检查验证集准确率是否提升）、后剪枝（从叶子开始）
7. 损失函数：$-\sum_{t=1}^{|T|} N_{t}\sum_{i=1}^k \frac{N_{ti}}{N_t} \log_2 \frac{N_{ti}}{N_t}+\alpha |T|$
8. 决策树本质：在高维空间中用超平面把数据分成不同的区域做独热编码
9. 随机森林：每棵树从全体 $n$ 个样本中有放回采样 $n$ 次；随机选取 $k$ 个特征（$k\approx \sqrt{d}$），多数投票
10. 偏差方差分解：$\text{Error} = \text{Bias}[h_D(x)|x]^2 + \text{Var}_D[h_D(x)|x] + \text{Var}(y|x)(\text{Noise,Irreducible Error})$

3. 深度学习

1. BatchNorm：$n$ 个样本 $n\times w\times h$ 做归一化（逐通道）
2. LayerNorm：同样本内部所有特征做归一化
3. 位置编码：$e_i(2j)=\sin(i/10000^{2j/d})$，$e_i(2j+1)=\cos(i/10000^{2j/d})$
4. 交叉注意力：$q$ 来自 Decoder，$k,v$ 来自 Encoder
5. 混合专家 MoE：FFN 门控
6. 感知机的收敛保证：

三、推理

1. 概率图模型

1. 贝叶斯网络 BN 转马尔可夫随机场 MRF：每个节点的父节点两两相连
2. D-分离：BN 头对头独立但观测到C或任意C后代则条件相关，其他相反；MRF 关于割集条件独立
3. 马尔可夫边界：观测后与外界条件独立，BN 父/子节点/子节点其他父节点，MRF 邻居集
4. 变量消除法：把所有含 $X_i$ 的因子相乘后边缘化 $X_i$ 得到新因子替换原因子
5. 信息传递：$m_{i\to j}(x_j) = \sum_{x_i} \psi_i(x_i) \psi_{ij}(x_i,x_j) \prod_{k\in N(i)\setminus j} m_{k\to i}(x_i)$，$P(X_i) = \psi_i(x_i) \prod_{k\in N(i)} m_{k\to i}(x_i)$，最大后验把 $\sum$ 换成 $\max$，图每次选一条边来回更新

2. 贝叶斯推断

1. 最大似然估计法：观测到数据 $D$，使用以 $\theta$ 为参数的模型让 $D$ 出现的概率尽可能大 $\hat{\theta}=\arg\max_\theta p(D|\theta)$
2. 最大后验估计法：假设模型参数 $\theta$ 服从先验分布，观测到数据 $D$ 后修正对 $\theta$ 的信念得到后验分布，选择后验概率最大的 $\hat{\theta}=\arg\max_\theta p(\theta|D)=\arg\max_\theta p(D|\theta)p(\theta)$
3. 贝叶斯模型平均法：不选择后验概率最大的 $\hat{\theta}$，而是对所有后验分布中的 $\theta$ 加权求和，$p(x|D) = \int p(x|\theta)p(\theta|D)d\theta$（假设给定 $\theta$ 后 $x$ 和 $D$ 独立）
4. 隐变量模型：$x$ 由 $z$ 决定，$\arg\max_\theta p(x|\theta)$ 难以计算，引入 ELBO $\log p(x|\theta) = \log\sum_z p(x,z|\theta) = \log\sum_z q(z)\frac{p(x,z|\theta)}{q(z)} \geq \sum_z q(z) \log\frac{p(x,z|\theta)}{q(z)}$
5. KL：ELBO $=\sum_z q(z) \log \frac{p(z|x,\theta)p(x|\theta)}{q(z)} = \sum_z q(z) \log \frac{p(z|x,\theta)}{q(z)} + \sum_z q(z) \log p(x|\theta)=-\text{KL}(q(z)||p(z|x,\theta)) + \log p(x|\theta)$
6. EM 算法：E 步 $q^*(z)=p(z|x,\theta)$，M 步 $\theta=\arg\max_\theta \sum_z q^*(z) \log \frac{p(x,z|\theta)}{q^*(z)}$
7. MAP：$\log p(\theta|x)=\log p(x|\theta)+\log p(\theta)-\log p(x)$，M 步 $\theta=\arg\max_\theta (\log p(x|\theta)+\log p(\theta))$
8. 变分推断：$q^*(z)=p(z|x,\theta)$ 难以计算，用 $q_\phi(z)\in\mathcal{Q}$ 近似取 $\phi=\arg\min_\phi \text{KL}(q_\phi(z)||p(z|x,\theta))$，使用优化方法求解 $q_\phi(z)$
9. 平均场理论：若 $q_\phi(z)=\prod_{i=1}^m q_{\phi_i}(z_i)$，则有 $q_{\phi_i}(z_i)=\mathbb{E}_{j\neq i}[\log p(x,z|\theta)]$

3. 概率主题模型

1. 朴素贝叶斯分类器、高斯判别分析、混合高斯模型
2. LDA：推理时隐变量取 $\arg\max_{z} q_\phi(z)$
3. 困惑度：$\exp\left(-\frac{\sum_{d=1}^{D_\text{test}} \log p(w_d|\alpha,\eta,\beta)}{\sum_{d=1}^{D_\text{test}} N_d}\right)$
4. VAE：用 $\theta$ 为参数的 Decoder 神经网络从先验为 $p(z)$ 的隐变量中生成 $x$，$\arg\max_\theta p_\theta(x)=\sum_z p_\theta(x|z)p(z)$ 不好计算，即 EM 所需的隐变量后验 $p_\theta(z|x)=\frac{p_\theta(x|z)p(z)}{p_\theta(x)}$ 分母不好计算，引入 Encoder 神经网络 $q_\phi(z|x)$ 近似隐变量后验
5. ELBO：$\sum_z q_\phi(z|x) \log\frac{p(x,z|\theta)}{q_\phi(z|x)}=\sum_z q_\phi(z|x) \log \frac{p(x|z,\theta)p(z)}{q_\phi(z|x)} = \sum_z q_\phi(z|x) \log \frac{p(z)}{q_\phi(z|x)} + \sum_z q_\phi(z|x) \log p(x|z,\theta)=-\text{KL}(q_\phi(z|x)||p(z)) + \mathbb{E}_{q_\phi(z|x)}[\log p(x|z,\theta)]$，对应 Encoder 不偏离先验、Decoder 能重构输入
6. 重参数化技巧：$z=\mu_\phi(x)+\sigma_\phi(x)\odot \epsilon,\epsilon\sim \mathcal{N}(0,I)$
7. HMM：Viterbi 算法最小化隐变量序列误差，Forward-Backward 算法最小化隐变量状态误差
8. 线性动态系统：连续化 HMM 的状态空间后隐变量分布 Forward 算法积分难计算，卡尔曼滤波假设高斯分布只变参数，粒子滤波用蒙特卡洛模拟分布（初始化 $\to$ 前向传播 $\to$ 观测赋权 $\to$ 重采样）
9. DDPM：训练 U-Net 接收加噪后的图像预测添加的噪声，推理时从纯噪声根据预测的噪声逐步去噪

4. 采样方法

1. 蒙特卡洛积分：$I=\int_{\Omega}f(x)\mathrm{d}x=|\Omega|\mathbb{E}[f(X)]\approx \frac{|\Omega|}{N}\sum_{i=1}^N f(x_i)$，$x_i\sim U(\Omega)$，有均方根误差 $\frac{|\Omega|\sigma}{\sqrt{N}}$，需要最小化 $\sigma$ 以降低误差
2. 重要性采样：$\int f(x)\mathrm{d}x=\int \frac{f(x)}{g(x)}g(x)\mathrm{d}x=\mathbb{E}g\left[\frac{f(X)}{g(X)}\right]\approx \frac{1}{N}\sum{i=1}^N \frac{f(x_i)}{g(x_i)}$，$x_i\sim g(x)$，有最优重要性密度 $g^*(x)=\frac{|f(x)|}{\int |f(x)|\mathrm{d}x}$，$g$ 与 $f$ 越相似方差越小
3. 控制变量法：辅助函数 $\mathbb{E}[h(X)]=c,Y=f(X)-\lambda (h(X)-c)$，有最优系数和对应方差 $\lambda^*=\frac{\text{Cov}(f(X),h(X))}{\text{Var}(h(X))},\text{Var}(Y)=\text{Var}(f(X))(1-\rho^2)$，$h$ 与 $f$ 越相关方差越小
4. 分层抽样：将 $\Omega$ 划分成 $K$ 个不相交子域，内部独立抽取样本，$N_k\propto \frac{|\Omega_k|}{|\Omega|}\sigma_k$ 时最小化方差
5. 对偶变量法：$U\sim U[0,1],I\approx \frac{1}{2N}\sum_{i=1}^N (f(U_i)+f(1-U_i))$，有方差 $\frac{\sigma^2+\text{Cov}(f(U),f(1-U))}{2N}$，越负相关方差越小
6. 拒绝采样：从密度 $f(x)$ 采样时选取包络密度 $g(x)$ 和 $c\ge 1$，$f(x)\le cg(x)$，先从 $g$ 采样，再独立产生 $U\sim U[0,1]$，若 $U\le \frac{f(x)}{cg(x)}$ 则接受，否则拒绝（在 $cg(x)$ 下方采样，保留 $f(x)$ 下方的点，接受概率 $\frac{1}{c}$）
7. 拟蒙特卡洛 QMC：用确定性低差异序列代替伪随机数，更均匀地填满高维空间
8. 马尔可夫链蒙特卡洛 MCMC Metropolis-Hastings 算法：为了从密度 $\pi(x)$ 采样，从状态 $x$ 出发按建议分布 $q(\cdot|x)$ 生成候选 $y$，以概率 $\alpha(x,y)=\min\left(1,\frac{\pi(y)q(x|y)}{\pi(x)q(y|x)}\right)$ 接受 $y$，否则保持 $x$，得到马尔可夫链 ${X_t}$，满足细致平衡 $\pi(x)p(x,y)=\pi(x)q(y|x)\alpha(x,y)=\pi(y)p(y,x)$，两边对 $x$ 积分得到平稳分布 $\int \pi(x)p(x,y)\mathrm{d}x=\pi(y)$