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,前三层递归:
-
证 Q:结论是 Q 的规则只有 R1(P ⇒ Q),问题变成证 P。
-
证 P:结论是 P 的规则只有 R2(L ∧ M ⇒ P),要同时证 L 和 M。
-
证 M:结论是 M 的只有 R3(B ∧ L ⇒ M),要证 B 和 L。
怎么算
每一层只问两件事:这个目标是不是已知事实;如果不是,哪些规则的结论是它。
意思是:后向链接每碰一条规则,都是因为它的结论正好是眼下要证的目标。和目标无关的规则一条都不会被碰到,这是它比前向链接省事的原因。
前向链接像宽度式铺开,从已知往外一圈圈推;后向链接是深度优先递归,沿着一条分支一路往下钻到底,再回来处理下一条。
常见误解
以为 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 开始:
-
证 L:R4 需要 P,P 已在路径上,不选;改选 R5,要证 A 和 B。
-
A、B 都是 KB 里的事实(R6、R7),命中基准情形,触底。
-
一路返回:A、B 成立,所以 L 成立(R5);B、L 成立,所以 M 成立(R3);L、M 成立,所以 P 成立(R2);P 成立,所以 Q 成立(R1)。
怎么判断
选规则前多问一句:这条规则的前提里,有没有当前路径上的目标?有就跳过。
意思是:后向链接唯一需要额外记的东西,就是这条路径。前向链接没有这个问题,它只往 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 上两个方向差在哪。
逐项对照:
- 先比驱动方式和起点。
- 再比结构:前向是迭代加 Agenda,后向是递归加回溯。
- 再比开销:最坏都线性,实际开销后向通常更小。
- 最后比特殊机制和共同限制。
| 前向链接 | 后向链接 | |
|---|---|---|
| 驱动方式 | 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;最后默写前向和后向的对照表。
必背
- 后向链接递归四步:Q 已知则得证;选一条结论为 Q 的规则;递归证它的每个前提;不行就换规则
- R1–R7 的后向推导:Q ← P(R1)← L、M(R2)← A、B(R5、R3)← 事实
- p.32 不能选 R4,因为 P 已在当前递归路径上,选它会循环;后向链接必须记录已访问目标
- 前向链接数据驱动,后向链接目标驱动;两者最坏都是 KB 规模线性、都完备、都要求 Horn 子句
- 后向链接实际开销通常远小于 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 是否为真。
约定:记录当前递归路径;选规则时,前提出现在路径上的规则跳过。
解法:
- 证 Q。Q 不是事实。结论为 Q 的只有 R1,改证 P。路径:Q。
- 证 P。结论为 P 的只有 R2,要同时证 L 和 M。路径:Q → P。
- 证 M。结论为 M 的只有 R3,要证 B 和 L。路径:Q → P → M。
- 证 B。B 是事实(R7),触底。
- 证 L。可选 R4、R5。R4 需要 P,P 已在路径上,跳过;选 R5,要证 A 和 B。
- 证 A、B。都是事实(R6、R7),触底,Done。
- 返回。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。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。