人工智能基础

大二下学期人工智能基础的复习笔记，目前已完结。

一、搜索

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)$
笔记
#计算机 #大二下
人工智能基础
https://sqzr2319.github.io/26Spring/AI/
作者
sqzr2319
发布于
2026年1月19日
许可协议