Backward Chaining（后向链推理）

Backward Chaining

这张图介绍了 Backward Chaining（后向链推理） 的基本概念和步骤。

后向链推理的基本思路：

后向链推理的目标是从查询目标 ( q ) 开始，向后推导前提条件，验证该查询是否成立。

证明目标 ( q ) 的步骤：

检查 ( q ) 是否已知为真：如果 ( q ) 已经在已知事实中，证明完成。
通过后向链推理证明：如果 ( q ) 不是已知事实，寻找以 ( q ) 为结论的规则，并尝试证明所有前提条件为真。

避免循环：

在推理过程中，需要检查新产生的子目标是否已经在目标栈中，以避免重复推理和陷入无限循环。

避免重复工作：

检查新的子目标是否已经被证明为真，或者之前尝试证明该子目标时已经失败了。如果是其中任一情况，就不需要再次证明该子目标。

通过这些步骤，后向链推理能够逐步从目标向前推导出相应的前提条件，最终确定目标是否能够被证明。

这张图解释了 Backward Chaining（后向链推理） 其实本质上是 And-Or 搜索（与或搜索）。下面对图中的各要素进行详细解释：

Backward Chaining as And-Or Search

后向链推理可以看作是一种与或搜索，通过推理过程找到目标是否能够被证明。

Initial state (初始状态) = Query (查询)：推理的起点是我们想要验证的命题 ( q )，即查询。
Goal state (目标状态) = KB (知识库)：推理的最终目的是要找到 ( q ) 是否能通过知识库 ( KB ) 中的事实和规则推导出来。
Actions (动作) = Clauses (子句)：在推理过程中，动作相当于应用知识库中的子句（规则）来推导新的事实或结论。
States (状态) = Models of KB (知识库的模型)：每个状态都代表了知识库中的某种解释或模型，表示已知的事实。
If a plan exists (如果有一个推理计划)，( q ) is true (则 ( q ) 为真)：如果存在一条从查询 ( q ) 到达目标状态的推理路径（推理计划），那么 ( q ) 就是真的。这条路径中的每一步都包含了具体的推理步骤。

简而言之，后向链推理可以通过一种搜索方法从查询开始，依次应用规则直到达到目标，即证明查询是否能够从知识库中推导出来。

在这里插入图片描述

这张图展示了 AND-OR Graph Search 算法的伪代码，主要用于在解决问题时进行与或搜索。下面是对代码中每个部分的解释：

1. `And-Or-Graph-Search(problem)`

这个函数是整个算法的入口点。它调用了 Or-Search，开始从问题的初始状态（problem.Initial-State）进行搜索，并且传递一个空路径（[]），表示当前还没有走过任何路径。

2. `Or-Search(state, problem, path)`

输入： 当前状态（state）、问题（problem）以及当前已经走过的路径（path）。
Goal Test: 首先检查当前状态是否是目标状态（problem.Goal-Test(state)），如果是，则返回一个空计划（[]），表示已经到达目标，不需要再进一步规划。
环检测（Cycle Check）： 如果当前状态已经在路径中（意味着出现了环），返回失败（failure），防止陷入死循环。
动作循环： 对于每个可能的动作（action）：
- 使用 And-Search 对应用该动作后的结果状态进行递归搜索。
- 如果 And-Search 返回一个非失败的计划，则将该动作与返回的计划组合成一个新的计划并返回。
- 如果没有找到成功的计划，则返回失败。

3. `And-Search(states, problem, path)`

输入： 一组可能的状态（states）、问题（problem）、和路径（path）。
状态循环： 对于每个状态 s_i：
- 调用 Or-Search 来对这个状态进行搜索。
- 如果 Or-Search 返回失败，则 And-Search 也会返回失败。
成功计划构建： 如果所有的状态都成功找到计划，则返回一个组合的计划，形如 if s_1 then plan_1 else ... if s_n then plan_n。也就是说，对于每个状态都生成相应的计划。

总结

Or-Search 负责处理 OR 节点的情况，也就是只要有一个动作能成功，就可以返回成功。
And-Search 负责处理 AND 节点的情况，也就是所有状态都需要成功才能返回成功。
整个搜索算法通过递归方式，处理了复杂的与或图中的决策问题。

这段伪代码实现的是一个 递归的与或搜索算法，在人工智能问题求解中非常常见，特别是当问题包含多个并行的子问题时。

在这里插入图片描述
这张图展示了一个**Backward Chaining（逆向推理）**的示例，通过从目标开始，沿着规则链向后推导，直至找到已知的事实为止。

逻辑规则

左边的逻辑表达式描述了推理规则：

P ⇒ Q （如果 P 为真，那么 Q 为真）
L ∧ M ⇒ P （如果 L 和 M 都为真，那么 P 为真）
B ∧ L ⇒ M （如果 B 和 L 为真，那么 M 为真）
A ∧ P ⇒ L （如果 A 和 P 都为真，那么 L 为真）
A ∧ B ⇒ L （如果 A 和 B 为真，那么 L 为真）
A 和 B 是已知的事实（它们为真）。

图的解释

目标： 我们的目标是证明 Q 为真（标记为绿色的圆圈）。
推理过程：
1. 从 Q 开始，根据规则 P ⇒ Q ，我们需要 P 为真才能使 Q 为真。
2. 根据 L ∧ M ⇒ P ，我们需要 L 和 M 都为真才能使 P 为真。
3. 接着，根据 B ∧ L ⇒ M ，要证明 M ，我们需要 B 和 L 为真。
4. 现在，我们需要证明 L 。根据 A ∧ P ⇒ L 和 A ∧ B ⇒ L ，两条路径可以证明 L 。但我们知道 A 和 B 是已知的事实，因此 L 为真。

结论

根据上述推理链条：

A 和 B 都为真；
L 为真；
M 为真；
最终 P 为真，进而 Q 为真。

这个过程展示了如何通过逆向推理从目标 Q 出发，沿着逻辑规则的路径找到可以证明的已知事实，从而证明目标的真实性。这就是 Backward Chaining 的核心思想。

在这里插入图片描述
这张幻灯片讨论了前向推理（Forward Chaining, FC）和后向推理（Backward Chaining, BC），它们是人工智能中常用的两种推理技术，尤其是在基于规则的系统中。

前向推理 (FC)：
- 数据驱动方式：从已有的数据开始，应用推理规则以提取更多数据或得出结论，从事实逐步推向目标。这种过程类似于自动或无意识的处理，常见于物体识别或日常决策等任务中。
- 潜在缺点：可能效率较低，因为它可能会生成与目标无关的结果，无法提前知道具体目标。
后向推理 (BC)：
- 目标驱动方式：从目标开始，向后推理，检查哪些数据或事实可以实现该目标。适用于问题解决，例如“我的钥匙在哪里？”或者“如何进入博士项目？”
- 效率：BC通常更高效，因为它只探索与特定目标相关的路径。相对于知识库（KB）的大小，BC的复杂性可能远小于线性增长，这使得它在效率要求较高的系统中非常有用。

总的来说，FC 更为通用且数据驱动，但在针对性问题解决上可能效率较低，而 BC 以目标为导向，通常在解决特定问题时更加高效。

在这里插入图片描述
这张幻灯片介绍了命题逻辑Propositional Logic的几个关键特点：

命题逻辑是声明式的（declarative）：
- 命题逻辑的语法片段对应于事实。也就是说，命题逻辑通过使用声明性的语句来表达某些事物为真或假。
命题逻辑允许部分、析取（或）、否定的信息：
- 命题逻辑可以处理部分信息、带有“或”的不确定信息、以及否定信息。这是与大多数数据结构和数据库不同的特点，因为很多传统数据结构只处理确定的、正面的信息。
命题逻辑是组合性的：
- 命题逻辑的组合性意味着复合命题的意义来自于各个组成部分的意义。例如，命题 ( B_{1,1} \land P_{1,2} )（"与"的表达式）是由 ( B_{1,1} ) 和 ( P_{1,2} ) 各自的意义组合而来的。
命题逻辑的含义是上下文无关的：
- 与自然语言不同，命题逻辑中的意义与上下文无关。自然语言的意思往往依赖于上下文，而命题逻辑不需要上下文来理解句子的含义。
命题逻辑的表达能力非常有限：
- 与自然语言相比，命题逻辑的表达能力相对较弱。例如，在命题逻辑中，无法直接表达“坑洞会导致相邻方格出现微风”这样的复杂关系，必须为每个方格单独写一个句子来描述这种情况。