人工智能引论：概念与公式速查
推理方法的目标
| 方法 | 已知信息 | 求什么 | 结论的性质 |
|---|---|---|---|
| 演绎（Deduction） | 事实、规则 | 逻辑后果 | 前提真且推理有效时必真 |
| 归纳（Induction） | 正负样本、背景知识 | 可推广的规则 | 有限样本支持，可能反例推翻 |
| 概率推理（Probabilistic Reasoning） | 概率模型、证据 | 条件概率 | 给定模型下的不确定性 |
| 因果推理（Causal Inference） | 因果结构、数据或实验 | 干预效果、反事实 | 依赖识别与机制假设 |
| 搜索（Search） | 初始状态、动作、目标、代价 | 合法或最优动作序列 | 取决于算法与资源条件 |
逻辑符号
| 符号 | 含义 | 易错点 |
|---|---|---|
| \(\neg,\land,\lor\) | 非、且、或 | 析取允许两者同时真 |
| \(p\to q\) | 实质蕴涵 | 只有 \(p\) 真、\(q\) 假时为假；不是因果关系 |
| \(p\leftrightarrow q\) | 双条件 | 两者真值相同 |
| \(\forall x,\exists x\) | 所有对象、至少一个对象 | 量词顺序不可任意交换 |
| \(\Gamma\models\varphi\) | 语义蕴涵 | 检查所有满足前提的模型 |
| \(\Gamma\vdash\varphi\) | 形式可证明 | 指定公理与推理规则 |
| \(\alpha\equiv\beta\) | 逻辑等价 | 所有解释下真值相同 |
| \(\square\) | 空子句 | 不可满足，表示归结矛盾 |
\[
\begin{aligned}
p\to q&\equiv\neg p\lor q,\\
\neg(p\land q)&\equiv\neg p\lor\neg q,\\
\neg\forall xP(x)&\equiv\exists x\neg P(x),\\
\neg\exists xP(x)&\equiv\forall x\neg P(x).
\end{aligned}
\]
全称类属关系常用 \(\forall x(A(x)\to B(x))\)；存在对象具有两种属性常用 \(\exists x(A(x)\land B(x))\)。
四种图的语义
| 图 | 节点 | 边 | 典型计算 |
|---|---|---|---|
| 知识图谱 | 实体 | 有类型的关系 | 补全 Father 等事实 |
| 贝叶斯网络 | 随机变量 | 有向依赖，组成 DAG | 分解联合分布并条件化 |
| 因果图 | 因果变量 | 直接作用机制 | 删入边、求干预分布 |
| 状态图 | 问题状态 | 动作转移 | 求到目标的路径 |
核心公式及条件
| 公式 | 用途与条件 |
|---|---|
| \(\mathrm{Gain}=t[\log_2\frac{p_1}{p_1+n_1}-\log_2\frac{p_0}{p_0+n_0}]\) | FOIL 文字选择；计数对象为绑定，\(t\) 是保留的原正绑定数 |
| \(P(\mathbf x)=\prod_iP(x_i\mid\mathrm{Pa}(X_i))\) | 贝叶斯网络的 DAG 因子分解 |
| \(P(\mathbf x)=Z^{-1}\exp(\sum_iw_in_i(\mathbf x))\) | MLN 世界概率；需要配分函数与落地公式计数 |
| \(P(Y\mid X)=P(X,Y)/P(X)\) | 观察条件概率，要求 \(P(X)>0\) |
| \(P(Y\mid\mathrm{do}(X=x))=\sum_zP(Y\mid X=x,Z=z)P(Z=z)\) | 仅在 \(Z\) 满足因果调整条件时成立 |
| \(\mathrm{ATE}=\mathbb E[Y(1)-Y(0)]\) | 比较同一总体的两种潜在结果 |
| \(f(n)=g(n)+h(n)\) | A* 排序；最优性还需启发式与重复处理条件 |
不应混淆的概念
- 无解与不可计算：数学上没有解，不代表不存在判断其无解的算法。
- 可计算与高效：存在算法不代表实际资源足够。
- 语义完备与理论完全：证明所有逻辑后果，不等于某个算术理论能决定每个句子。
- 存在见证与任意对象：证明某个对象有性质，不能全称概括到所有对象。
- 缺失与负例：开放世界中的未记录关系通常只是未知。
- 概率依赖与因果关系：贝叶斯网络的箭头需要额外因果解释，才能用于干预。
- 软约束与硬约束：有限 MLN 权重允许违规世界有非零概率。
- 观察与干预：自然选择人群的组别比例可能与目标总体不同。
- 效应与显著性：5 个百分点是大小，不是显著性检验结果。
- 状态与搜索节点：同一状态可以有不同到达路径和代价。
- 搜索完备与最优：能找到解，不等于保证最便宜的解。
自检问题
- 为什么 \(p\to q\) 与 \(q\) 不能推出 \(p\)？给出一个真值赋值。
- 为什么“有人同时满足 \(P,Q\)”不能只由“有人满足 \(P\)，有人满足 \(Q\)”推出？
- FOIL 加入 Couple 后为何仍覆盖一个负例？下一文字消去了谁？
- 计算 \(P(W=1\mid C=0,R=1)\) 时，为何要对 \(S\) 求和？
- MLN 查询“在室外”为什么要合并两个世界？
- 辛普森数据中，两种处理总体采用了什么不同权重？
- \(\mathrm{do}(X=x)\) 固定了什么，哪些变量还可能变化？
- 最先生成的目标为什么不一定是最便宜的目标？
对应解释见 命题逻辑、一阶逻辑、知识图谱、概率推理、因果推理与搜索框架。
课程来源与公式校订见 资料对照与校订依据。
第四节课：搜索方法对照
| 方法 | 评价／递归 | 目的 | 关键条件 |
|---|---|---|---|
| 贪婪最佳优先 | \(f=h\) | 优先看起来靠近目标的候选 | 有限图正确去重可完备，一般不最优 |
| A* | \(f=g+h\) | 求最小代价路径 | 可采纳启发式；图搜索须一致或允许重新打开 |
| Minimax | Max 取最大、Min 取最小 | 应对理性对手 | 固定收益视角，有限或截断树 |
| Alpha–Beta | Max 更新 \(\alpha\)，Min 更新 \(\beta\) | 保持 Minimax 值并减少扩展 | 继承窗口，\(\alpha\ge\beta\) 时可剪 |
| UCB1 | \(\bar X_i+C\sqrt{2\ln T/N_i}\) | 平衡探索与利用 | 先处理未采样动作；标准保证要求有界平稳奖励及相应系数 |
| UCT / MCTS | 选择、扩展、模拟、回传 | 在预算内估计动作价值 | 统一奖励视角；对手不能最大化己方收益 |
一致性：
\[
h(n)\le c(n,a,n')+h(n')
\quad\Longrightarrow\quad
h(n)\le h^*(n),\qquad f(n')\ge f(n).
\]
推论使用目标 \(h=0\)，第二项针对沿该转移生成的路径节点。可采纳性不能反向保证一致性。
MCTS 回传（统一根视角）：\(N\leftarrow N+1\)、\(W\leftarrow W+r\)；胜／平／负 \(r=1,0.5,0\)，对手选择时最大化 \(1-Q+\mathrm{Bonus}\)。回传不是梯度计算，最终落子也不必用探索指标。
交通图：贪婪 \(A\to E\to H\to J\to K\) 代价 20；A* \(A\to E\to G\to K\) 代价 14。Alpha–Beta 完整树：根值 3，左至右剪枝只访问 5 个叶子。黑白棋：单方无动作则 Pass，双方无动作才终止；必须保存行动方并保护原棋盘。