← COMP5511 全部讲次
R02

Midterm 复习资料|概率与逻辑

条件概率、贝叶斯、贝叶斯网络,以及命题逻辑的真值表、CNF、链接与归结。

手机上宽表格可左右滑动;自测答案默认收起,点击题目下方按钮查看。

使用边界:2026-11-04 课堂期中复习,非官方材料;考试安排按讲师通知整理,正式要求以讲师通知和课堂公告为准。主体覆盖 L01–L07、Tutorial 1–5 与 Assignment 1;通知列出的课件只到 Lecture 7,L08 放在第 08 节作范围存疑附节。练习题均为自拟,不是往年真题或预测卷。

复习资料:范围与搜索 · 概率与逻辑 · 机器学习与聚类 · 神经网络与 L08 附节

先做题再看解析:A 搜索 · B 概率 · C 逻辑 · D 机器学习 · E 聚类与神经网络 · F 论文与 PyTorch

02|不确定性与概率:从公理到贝叶斯网络

必须会算的

  • 📌 条件概率 P(E|F) = P(EF)/P(F),EF 表示交集;独立的判据是 P(EF) = P(E)P(F)(L03a p.8、p.12–13)。
  • 📌 贝叶斯公式带全概率展开:P(D|+) = P(+|D)P(D) / [P(+|D)P(D) + P(+|H)P(H)]。课件例题 P(D) = 0.001、P(+|D) = 0.99、P(+|H) = 0.05,结果 0.00099/0.05094 ≈ 0.0194(L03a p.15–17)。
  • 📌 链式法则:P(A,B,C) = P(C|A,B)P(B|A)P(A),再用题目给的独立或条件独立替换其中一项(L03a p.18;T04 p.5)。
  • 📌 贝叶斯网络联合概率 = 各节点在父节点下的条件概率连乘。课件例题 P(L,C,E,T) = 0.96×0.93×0.95×0.9 = 0.763344 ≈ 0.76(L03a p.24–25)。
  • 📌 因果推理与诊断推理:课件例题 P(C|T) ≈ 0.884、P(C|T^c) = 0.095、P(T|C) = 0.7956/0.8051 ≈ 0.988(L03a p.26–27)。
  • 📌 参数量对比:四个布尔变量的联合表 2⁴ = 16 项;同一网络用条件概率表只需 8 个数(L03a p.24)。
  • 📌 从联合分布表求条件概率:分子查表,分母把满足条件的行相加(T04 p.10)。
  • 📌 题目给出错概率和比例时:先把比例换成和为 1 的先验(2:1 → 2/3、1/3),再用 1 − 出错概率得到正确接收的似然;分母把「正确传来」和「错收过来」两条来源都加上(L03a p.15–17;A1 Q4)。
  • 📌 Monty Hall:先验各 1/3,主持人知情时开门的似然分别是 1/2、1、0,换门赢的概率 2/3;主持人不知情、碰巧开出山羊时换不换都是 1/2(T04 p.11–15)。

必须会用英文说清的

  • 📌 Mutually exclusive events cannot happen together, P(EF) = 0; independent events satisfy P(EF) = P(E)P(F). Two events with non-zero probabilities cannot be both.(L03a p.13)
  • 📌 Bayes’ rule updates a prior P(H) into a posterior P(H|E) using the likelihood P(E|H).(L03a p.15)
  • 📌 A Bayesian belief network is a directed acyclic graph; each node is conditionally independent of its non-descendants given its parents.(L03a p.21)
  • 📌 In a converging connection A → C ← B, A and B are independent when C is not observed; observing C can make them dependent (explaining away).(L03a p.23;T04 p.7)
  • 📌 Ignoring a very small prior when reading a positive test result is the base-rate fallacy.(L03a p.17)

成立条件和常见误区

  • 互斥与独立是两回事:两个概率都不为 0 的互斥事件一定不独立(L03a p.13)。
  • 条件独立 P(AB|C) = P(A|C)P(B|C) 与独立互不蕴含(L03a p.19;T04 补充节)。
  • 0.99 是灵敏度(sensitivity),不要读成准确率(L03a 补充节)。
  • 汇聚连接里两个父节点的独立只在子节点未被观测时成立;一旦观测到子节点,不能再把 P(E|·) 直接换成 P(E)(T04 补充节)。
  • 联合表的 16 项里只有 15 个自由参数,因为总和为 1(L03a 补充节)。课件说的 8 个数是每种父节点取值下记一个 P(X 为真|父节点)。
  • 课件 p.15 的页脚印刷页码有误,回查按 PDF 页序。
  • 「发出」和「收到」是不同事件,要用不同符号;题目问的是收到后反推发出,条件方向和题面给的出错概率相反(A1 Q4)。
  • Monty Hall 的概率树不能数叶子,各叶子的概率不相等;主持人知不知情改变的是似然(T04 p.11–15)。

03|知识表示与推理:命题逻辑

必须会算的

  • 📌 真值表:n 个命题符号共 2ⁿ 个解释;模型是使句子为真的解释。按列从内层子公式往外算(L03b p.13–14;T05 p.4)。
  • 📌 判定 satisfiable / unsatisfiable / valid:至少一个模型、没有模型、所有解释都是模型(L03b p.17)。课件练习「None of us…」有 3 个模型,「I’m a liar」没有模型(L03b p.16)。
  • 📌 转 CNF 四步:消 ⇔ → 消 ⇒ → 用 de Morgan 把 ¬ 推到文字上 → ∨ 对 ∧ 分配(L03b p.37–38;T05 p.6–7)。
  • 📌 前向链接:已知事实出发,前件全满足就加入结论,数据驱动;课件例题用到 R5→R3→R2→R1,R4 没用上(L03b p.22–28)。
  • 📌 后向链接:从目标出发换成子目标,已访问过的目标不再选,目标驱动(L03b p.29–34;T05 p.10)。
  • 📌 归结反证:S = KB ∪ {¬Q},反复归结,推出空子句即证明 KB 蕴含 Q(L03b p.35、p.39–43;T05 p.12)。
  • 📌 含 ⇔ 的句子转 CNF:先拆成两个方向的 ⇒,例如 P ⇔ (Q ∧ R) 得到 ¬P ∨ Q、¬P ∨ R、¬Q ∨ ¬R ∨ P 三个子句(T05 p.6–7)。
  • 📌 化 DNF:前三步与 CNF 相同,最后改用 ∧ 对 ∨ 分配,整理成若干合取式的析取;DNF 不唯一,写完用真值表逐行自检(L03b p.18、p.36–38;A1 Q5)。

必须会用英文说清的

  • 📌 Propositional logic is a special case of first-order logic; a logic has syntax, semantics and inference rules.(L03b p.3、p.8)
  • 📌 Operator precedence is ¬, ∧, ∨, ⇒, ⇔ (from highest to lowest).(L03b p.12)
  • 📌 P ⇒ Q is equivalent to ¬P ∨ Q; it is false only when P is true and Q is false.(L03b p.14、p.18;T05 p.4)
  • 📌 A Horn clause has at most one positive literal; forward and backward chaining work on Horn clauses.(L03b p.21;T05 补充节)
  • 📌 Forward chaining is data-driven; backward chaining is goal-driven and often costs much less than linear.(L03b p.28、p.34)
  • 📌 Resolution proves Q by refutation: add ¬Q to the knowledge base and derive the empty clause.(L03b p.39)

成立条件和常见误区

  • 推理规则要 sound,推出的结论才一定为真;真值表法的开销是 2ⁿ(L03b p.20)。
  • 前件为 ∨ 的规则(A ∨ B ⇒ C)转 CNF 后拆成两条 Horn 子句;前件为 ∧ 的不拆(T05 p.9)。
  • 子句里有两个正文字(如 P ∨ Q)就不是 Horn 子句,链接法用不上,归结和真值表仍可用(L03b 补充节;T05 补充节)。
  • 一个 ⇔ 要拆成两个方向,漏一个方向就漏子句(T05 p.7)。
  • 蕴含前件为假时整句为真(空真),真值表里最容易填错(L03b p.14)。
  • 归结每步只消一对互补文字,与目标无关的子句可以不用(T05 p.12)。
  • ¬ 的优先级最高,只作用在紧跟它的那个文字或括号上;先按括号把公式拆成「前件 ⇒ 后件」再动手(L03b p.12;A1 Q5)。
下一页 →
R03 Midterm 复习资料|机器学习与聚类

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。