← COMP5511 全部讲次
L03b-4 · 第 3 周

L03b-4 后向链接:从目标倒着找,走过的路要记住

从零讲目标驱动的后向链接:递归四步、为什么 p.32 不能选 R4、怎么从事实一路返回,再和前向链接逐项对照。

一句话版

后向链接从要证的目标出发:找一条结论是它的规则,把证明任务换成证这条规则的全部前提,一层层往下递归,直到碰到已知事实。

递归时要记住当前路径上已经在证的目标,否则会绕圈。上一页 L03b-3 用同一个 R1–R7 知识库做了前向链接,这一页把方向倒过来。

先认识这几个词

词 全称 / 读法 一句人话
目标驱动 goal driven 从要证的东西出发,只看和它有关的规则
数据驱动 data driven 从已有事实出发,能推什么推什么
递归 recursion 函数在执行过程中调用自己去解一个更小的同类问题
基准情形 base case 递归停下来的条件,这里是「目标已经是已知事实」
回溯 backtracking 选的规则走不通,退回来换一条
递归路径 当前正在证的目标链 从最初目标到眼下这个目标,一路经过的那些符号

一个类比:倒着查菜谱,从想吃的菜往回找原料

上一页的厨师有料就开火。这一次换个做法:你先决定要吃哪道菜,然后翻菜谱,找能做出这道菜的那一页,看它要哪些原料。

原料台面上有,就打勾;台面上没有,就再去翻能做出这样原料的那一页。一直翻到所有原料都能从台面上现成的东西做出来,这道菜就做得成。

这样只翻和这道菜有关的菜谱,其余菜谱一页都不碰,所以叫目标驱动。有一个陷阱:如果做 A 要用 B,做 B 又要用 A,你会在两页菜谱之间来回翻个没完。所以要在手边记一张单子,写着「我正在为哪些东西找做法」,翻到单子上已有的东西就换一页。

类比在哪里失效:

  • 真实厨房里你可以先把 A 做一半,逻辑里一个符号要么证出来了,要么没有。
  • 厨师记不住可以凭经验跳过,算法只能靠那张路径单子判断。

从零讲起

1. 后向链接的递归:要证 Q,先证它的前提

它解决什么问题

前向链接不看目标,可能把一堆无关结论都推出来。如果只关心一个目标 Q,更省事的做法是从 Q 出发,只去碰能推出 Q 的规则。

从哪来(补充)

后向链接是目标驱动的推理方式,和数据驱动的前向链接相对。逻辑编程语言 Prolog 用的就是它,按深度优先的顺序搜索;不少专家系统也用它来回答「这个结论成立吗」这类问题。

出处:Wikipedia: Backward chaining

直觉

课件给的是一个递归函数:

BackwardChaining(Q):
  ① 若 Q 已在 KB 中已知 → Q 得证
  ② 选一条结论为 Q 的规则:(P1 ∧ P2 ∧ … ∧ Pn) ⇒ Q
  ③ 递归调用 BackwardChaining(P1), …, BackwardChaining(Pn)
  ④ 重复 ②③,直到 Q 得证或没有规则可选

第 1 步是基准情形,目标已经是事实就直接返回。第 3 步是 AND 分支:一条规则的前提必须全部证出来,少一个都不行。第 4 步是回溯:这条规则走不通,就换另一条结论也是 Q 的规则。

一步一步看

目标:从目标 Q 出发往回找结论是它的规则,看证 Q 怎样一层层变成证 P、L、M。

用 R1–R7 知识库证 Q,前三层递归:

  1. 证 Q:结论是 Q 的规则只有 R1(P ⇒ Q),问题变成证 P。

    后向链接第 1 步:R1 到 R7 规则表,结论是 Q 的只有 R1,底部当前递归路径只有 Q,接着要证 P

  2. 证 P:结论是 P 的规则只有 R2(L ∧ M ⇒ P),要同时证 L 和 M。

    后向链接第 2 步:结论是 P 的只有 R2,要同时证 L 和 M,当前递归路径变成 Q → P

  3. 证 M:结论是 M 的只有 R3(B ∧ L ⇒ M),要证 B 和 L。

    后向链接第 3 步:结论是 M 的只有 R3,要证 B 和 L,当前递归路径是 Q → P → M

怎么算

每一层只问两件事:这个目标是不是已知事实;如果不是,哪些规则的结论是它。

意思是:后向链接每碰一条规则,都是因为它的结论正好是眼下要证的目标。和目标无关的规则一条都不会被碰到,这是它比前向链接省事的原因。

前向链接像宽度式铺开,从已知往外一圈圈推;后向链接是深度优先递归,沿着一条分支一路往下钻到底,再回来处理下一条。

常见误解

以为 AND 分支证出一个前提就够

R2 是 L ∧ M ⇒ P,要证 P 就必须把 L 和 M 都证出来。只证出 L,P 仍然没有着落。

以为可以省掉第 1 步

第 1 步是递归的出口。没有「目标已知就返回」,递归会一直找规则往下钻,永远停不下来。

试一下

用后向链接证 P,第一步会找哪条规则?要接着证什么?

结论是 P 的只有 R2(L ∧ M ⇒ P),接着要同时证 L 和 M。R1 的结论是 Q,和 P 无关,不会被碰。

2. 走过的路要记住:为什么不能选 R4

它解决什么问题

一个目标可能有好几条规则可选。如果选中的规则绕回到路径上已经在证的目标,递归就会无限循环。需要一个机制把这种规则排除掉。

直觉

证 L 时有两条规则可选:R4(A ∧ P ⇒ L)和 R5(A ∧ B ⇒ L)。

看当前路径:Q → P → M → L。如果选 R4,要证 L 就得先证 P;可 P 正在路径上等着 L 被证出来。等于「证 L 要先证 P,证 P 又要先证 L」,绕成一个圈。课件在这一页专门写了一句:R4 shouldn’t be selected because we visited P before。

解决办法很简单:记录当前递归路径上的目标,选规则时发现前提在路径上,就跳过这条规则,换下一条。

一步一步看

目标:接着证 L,看为什么要跳过绕回路径的 R4,以及触底后各层结论怎样一路返回到 Q。

接着上一节,从证 L 开始:

  1. 证 L:R4 需要 P,P 已在路径上,不选;改选 R5,要证 A 和 B。

    后向链接第 4 步:证 L 时 R4 被划掉,旁注 R4 要先证 P 但 P 已在路径上会绕圈,改选 R5 证 A、B;当前递归路径 Q → P → M → L

  2. A、B 都是 KB 里的事实(R6、R7),命中基准情形,触底。

  3. 一路返回:A、B 成立,所以 L 成立(R5);B、L 成立,所以 M 成立(R3);L、M 成立,所以 P 成立(R2);P 成立,所以 Q 成立(R1)。

    后向链接第 5 步:A、B 是事实触底,规则表旁依次注明 L、M、P、Q 成立,底部写出返回顺序 A、B、L、M、P、Q,目标 Q 得证并用青绿标出

怎么判断

选规则前多问一句:这条规则的前提里,有没有当前路径上的目标?有就跳过。

意思是:后向链接唯一需要额外记的东西,就是这条路径。前向链接没有这个问题,它只往 Agenda 里加事实,Agenda 只会变大,天然不会绕圈。

整条后向推理链是 R1 → R2 → {R5, R3} → 事实 A、B,正好是前向那条链倒过来走。R4 被跳过,这就是目标驱动省下来的功。

常见误解

以为选了 R4 只是慢一点,最后也能证出来

不记录路径的话,选 R4 会让「证 L」和「证 P」互相调用,递归永远不返回。记录路径之后,R4 会被直接跳过,改走 R5。

以为 R4 被跳过是因为它的结论没用

前向链接里 R4 没被触发,是因为它的结论 L 早就有了。后向链接里 R4 被跳过,是因为它的前提 P 在当前路径上。两个原因不一样。

试一下

如果证 L 时先试 R4、发现循环再回溯,最后用的是哪条规则?

回溯到 R5,改证 A 和 B。A、B 都是事实,L 得证。先试 R4 只是多走一步弯路,记录路径保证了这一步弯路会被及时发现。

3. 前向和后向对照:什么时候用哪个

它解决什么问题

两种方法用的是同一个 KB、同一种推理(前提为真则结论为真),差别在方向。考试常让你逐项对比,实践中也要根据问题选方向。

直觉

前向链接适合「手上有一批新事实,想知道能推出什么」。后向链接适合「想知道某个具体结论成不成立」。

课件对后向链接给了和前向对称的性质:完备;最坏情况下每条规则都会被触发;线性时间,每条规则最多触发一次。还多了一句:实践中开销远小于 KB 规模,更接近为了证 Q 真正要用到的那些规则的个数。

一步一步看

目标:把前向和后向链接按驱动方式、结构、开销和机制逐项对照,看同一个 KB 上两个方向差在哪。

逐项对照:

  1. 先比驱动方式和起点。
  2. 再比结构:前向是迭代加 Agenda,后向是递归加回溯。
  3. 再比开销:最坏都线性,实际开销后向通常更小。
  4. 最后比特殊机制和共同限制。
前向链接 后向链接
驱动方式 Data Driven(数据驱动) Goal Driven(目标驱动)
起点 KB 中的已知事实 要证的目标 Q
结构 迭代 + Agenda 工作内存 递归(深度优先 + 回溯)
最坏复杂度 KB 规模线性 KB 规模线性
实际开销 可能推出大量无关结论 通常远小于 KB 规模,只碰相关规则
特殊机制 无 需记录已访问目标以防循环
共同限制 要求 KB 是 Horn 子句的合取 同左

怎么判断

问题里有明确的单个目标,选后向;问题是「这些事实能推出什么」,选前向。

意思是:两种方法能证出的东西完全一样,都是 KB 里可证的原子命题。选方向只影响碰多少无关规则。

常见误解

以为后向链接在任何写法下都保证线性

线性界要求每条规则最多处理一次。朴素的递归写法如果反复去证同一个子目标,并不自动有线性界,需要配上查重和缓存。

以为后向链接能处理 a ∨ b 这种句子

两种链接法都要求 KB 是 Horn 子句的合取,a ∨ b 有两个正文字,都处理不了。

试一下

一个系统每天收到一批新的传感器读数,想把能推出的报警全部列出来。该用哪种?

前向链接。问题没有单个目标,是「新事实能推出什么」,数据驱动正合适。

把它们串起来

前向链接从事实往外铺,后向链接从目标往回钻,用的推理一样,差的只是方向。

后向链接的骨架是一个四步递归:目标已知就返回;否则选一条结论是它的规则,把前提一个个递归证出来;走不通就换规则。R1–R7 的例子里,Q 要 P,P 要 L 和 M,M 要 B 和 L,L 选 R5 触底到 A 和 B。

递归比迭代多一个风险:绕圈。证 L 时 R4 需要 P,而 P 正在路径上等 L,所以 R4 必须跳过。记住当前路径,是后向链接唯一需要额外维护的东西。

方向带来的差别体现在开销上。两者最坏都是线性、都完备,但后向链接只碰和目标相关的规则,前向链接可能把无关结论都推出来。

两种方法有同一个短板:只能处理 Horn 子句。下一页的归结法去掉这个限制,代价是要把所有句子先转成 CNF。

课件里的坑

  • [原文漏词] 课件写「much less linear in the size of KB」,漏了 than,应读作 much less than linear,意思是远低于 KB 规模的线性(p.34)
  • [易漏] R4 不能选的原因是 P 已在递归路径上,答题要写出「会循环」,只写「R4 没用」不给分(p.32)
  • [课件没画] 返回过程课件只写了 Done,答题时要把 A、B → L、M → P → Q 的返回顺序写出来(p.33)
  • [适用条件] 线性界依赖每条规则最多处理一次,朴素递归反复证同一子目标时需要查重和缓存(p.34)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写后向链接的四步伪代码;再从 Q 开始画递归树,每一层写出当前路径和接着要证的目标,在证 L 那一层写清为什么跳过 R4;最后默写前向和后向的对照表。

必背

  1. 后向链接递归四步:Q 已知则得证;选一条结论为 Q 的规则;递归证它的每个前提;不行就换规则
  2. R1–R7 的后向推导:Q ← P(R1)← L、M(R2)← A、B(R5、R3)← 事实
  3. p.32 不能选 R4,因为 P 已在当前递归路径上,选它会循环;后向链接必须记录已访问目标
  4. 前向链接数据驱动,后向链接目标驱动;两者最坏都是 KB 规模线性、都完备、都要求 Horn 子句
  5. 后向链接实际开销通常远小于 KB 规模,只碰和目标相关的规则;前向链接可能推出大量无关结论

课件例题

例 1(课件 p.29–33):用后向链接判断 Q 是否为真

见下方完整例题。

例 2(课件 p.32):证 L 时为什么不能选 R4?

题面:当前递归路径是 Q → P → M → L,L 有 R4、R5 两条规则可选,说明选择理由。

提示

看 R4 的前提里有没有路径上的符号。

解答

R4 是 A ∧ P ⇒ L,要证 L 就得先证 P。P 已在当前路径上,而证 P 正在等 L 被证出来,选 R4 会形成循环。所以跳过 R4,选 R5(A ∧ B ⇒ L),改证 A 和 B,二者都是事实。

例 3(课件 p.28、p.34):比较前向链接和后向链接

题面:从驱动方式、复杂度、实际开销三方面比较。

提示

两者最坏情况一样,差在实际开销。

解答

前向链接数据驱动,后向链接目标驱动。两者最坏都是 KB 规模线性,每条规则最多触发一次,且都完备。实际开销上,前向链接可能推出大量无关结论;后向链接只碰和目标相关的规则,通常远小于 KB 规模。

完整例题

题面(课件 p.29–33):KB 为 R1:P ⇒ Q,R2:L ∧ M ⇒ P,R3:B ∧ L ⇒ M,R4:A ∧ P ⇒ L,R5:A ∧ B ⇒ L,R6:A,R7:B。用后向链接判断 Q 是否为真。

约定:记录当前递归路径;选规则时,前提出现在路径上的规则跳过。

解法:

  1. 证 Q。Q 不是事实。结论为 Q 的只有 R1,改证 P。路径:Q。
  2. 证 P。结论为 P 的只有 R2,要同时证 L 和 M。路径:Q → P。
  3. 证 M。结论为 M 的只有 R3,要证 B 和 L。路径:Q → P → M。
  4. 证 B。B 是事实(R7),触底。
  5. 证 L。可选 R4、R5。R4 需要 P,P 已在路径上,跳过;选 R5,要证 A 和 B。
  6. 证 A、B。都是事实(R6、R7),触底,Done。
  7. 返回。A、B 成立 ⟹ L 成立(R5);B、L 成立 ⟹ M 成立(R3);L、M 成立 ⟹ P 成立(R2);P 成立 ⟹ Q 成立(R1)。
层 要证 选用规则 接着要证 当前路径
1 Q R1 P Q
2 P R2 L、M Q → P
3 M R3 B、L Q → P → M
4 L R5(R4 跳过) A、B Q → P → M → L
5 A、B 事实 R6、R7 无 触底

要点:AND 分支要全部证出;R4 因循环被跳过;返回顺序是前向那条链倒过来。

答题格式:按层写「要证什么、选哪条规则、为什么、接着证什么」,在 L 那一层单独写出跳过 R4 的理由,最后写返回过程和结论 Q 为真。

变式题(先自己做)

(1) 改编自课件 p.29–33:同一个 KB,用后向链接证 M。写出递归过程,并指出哪些规则从未被访问。 (2) 改编自课件 p.32:如果算法不记录路径,证 Q 时在 L 那一层先选 R4,会发生什么? (3) 改编自课件 p.34:一个 KB 有很多条规则,但和目标 Q 相关的只有其中几条。前向和后向哪个更省事?为什么?

提示

(1) 从 M 出发,路径从 M 开始记。(2) 跟着 R4 往下走一层看看要证什么。(3) 想想谁会碰无关规则。

判分点与答案(非官方评分标准)

判分点:① (1) 写出路径并说明 L 那一层的选择;② (1) 列出未访问的规则;③ (2) 写出循环的具体形式;④ (3) 点出目标驱动只碰相关规则。

(1) 证 M:用 R3,证 B、L,路径 M。B 是事实。证 L,路径 M → L:R4 需要 A 和 P,P 不在路径上,可以试;证 P 要用 R2,需要 L 和 M,两者都在路径上,走不通,回溯。改选 R5,A、B 都是事实,L 得证,M 得证。若直接选 R5,R1、R2、R4 都没被访问;若先试 R4,R1 始终未被访问。

(2) 选 R4 要证 P,证 P 用 R2 又要证 L,证 L 再选 R4 又要证 P,无限循环,算法不返回。

(3) 后向链接。它从 Q 出发,只碰结论和 Q 相关的规则;前向链接不看目标,可能把无关规则都触发一遍。

闪卡自测

1. 后向链接的递归四步是什么?

Q 已知则得证;选一条结论为 Q 的规则;递归证它的全部前提;重复直到得证或无规则可选(p.29)。

2. 后向链接为什么叫目标驱动?

它从要证的目标出发,只碰结论和当前目标相关的规则(p.29)。

3. R1–R7 的后向推导链是什么?

R1 → R2 → {R5, R3} → 事实 A、B,正好是前向那条链倒过来走(p.30–33)。

4. p.32 为什么不能选 R4?

R4 需要先证 P,而 P 已在当前递归路径上,选它会循环(p.32)。

5. 为什么前向链接不需要记录访问历史?

前向链接只往 Agenda 里加事实,Agenda 只增不减,不会绕圈(p.32)。

6. 后向链接的实际开销为什么通常远小于 KB 规模?

它只碰为证明目标真正需要的那些规则,和目标无关的规则一条都不会被碰到(p.34)。

下一讲

两种链接法都装不下 p ∨ q 这种句子,下一页讲只有一条规则、但适用于任何命题句子的归结法。见 L03b-5。

下一讲 →
L03b-5 L03b-5 归结法:只有一条规则,先转 CNF,再推出矛盾

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