Spark Notes

Appearance

推理引擎与搜索 ​

推理引擎是符号 AI 系统的执行核心，负责在知识库上自动推导新结论。搜索算法则负责在庞大的可能性空间中高效地找到推理路径。两者结合，构成了符号系统从已知知识得出新知识的完整机制。

前向链推理 ​

前向链推理（Forward Chaining）是数据驱动的推理方式。从已知事实出发，不断匹配规则的条件部分，将匹配成功的规则的结论添加到事实集中，直到没有新事实产生或者目标被满足。这是一种自底向上的推理策略。

text
已知事实：
  parent(tom, bob)
  parent(bob, pat)

规则：
  R1: parent(X, Y) → ancestor(X, Y)
  R2: parent(X, Z) ∧ ancestor(Z, Y) → ancestor(X, Y)

推理过程：
  第1轮：匹配 R1，得到 ancestor(tom, bob), ancestor(bob, pat)
  第2轮：匹配 R2（X=tom, Z=bob, Y=pat），得到 ancestor(tom, pat)
  第3轮：无新事实产生，推理结束

前向链的优势在于能够推导出所有可以从已知事实得出的结论，适合"告诉我所有能知道的事情"这类场景。缺点是会产生大量与目标无关的中间结论，浪费计算资源。在专家系统中，当用户希望系统主动推送可能的诊断结论时，前向链是合适的选择。 RETE 算法是前向链推理的高效实现，由 Charles Forgy 在 1979 年提出。核心思想是构建一个规则网络，将所有规则的条件部分编译成一个有向无环图。当事实集中发生变化时，只需沿着网络传播变化的部分，就能增量地更新所有规则的匹配状态，避免了对每条规则重新扫描整个事实集。RETE 算法将规则匹配的时间复杂度从 O(R×F)（R 为规则数，F 为事实数）降低到接近 O(F)，使得大规模产生式系统成为可能。

后向链推理 ​

后向链推理（Backward Chaining）是目标驱动的推理方式。从目标假设出发，反向查找能够证明该目标的规则，然后递归地证明这些规则的条件部分，直到所有条件都被已知事实满足或者无路可走。Prolog 语言默认采用后向链策略。

text
目标：ancestor(tom, pat) 是否成立？

查找规则：
  R1: ancestor(X, Y) ← parent(X, Y)
  R2: ancestor(X, Y) ← parent(X, Z), ancestor(Z, Y)

尝试 R1: ancestor(tom, pat) ← parent(tom, pat)
  检查事实：parent(tom, pat) 不在事实集中 → R1 失败

尝试 R2: ancestor(tom, pat) ← parent(tom, Z), ancestor(Z, pat)
  匹配 parent(tom, Z) → Z = bob
  递归目标：ancestor(bob, pat)
    尝试 R1: ancestor(bob, pat) ← parent(bob, pat)
    检查事实：parent(bob, pat) 存在 → 成功！
  所有子目标满足 → ancestor(tom, pat) 成立

后向链的优势在于只搜索与目标相关的推理路径，避免了前向链中大量无关结论的计算。在用户提出明确问题的场景（如"这个病人的病因是什么？"），后向链效率更高。Prolog 的查询机制就是后向链的直接实现——用户输入查询，引擎自动进行反向推理和回溯搜索。 前向链和后向链可以组合使用。在复杂的推理系统中，先通过后向链确定相关的推理子目标，再对每个子目标进行局部的前向链推理，兼顾了方向性和完备性。

搜索算法 ​

推理过程本质上是在一个状态空间中的搜索问题。状态空间的每个节点代表推理过程中的一组事实或一个待证目标，边代表应用一条规则后的状态变化。搜索算法的目标是在这个空间中找到一条从初始状态到目标状态的路径。

无信息搜索 ​

深度优先搜索（DFS）沿着一条路径尽可能深入，走到死胡同后回溯到最近的分支点。DFS 的内存开销是 O(d)（d 为搜索深度），但可能陷入无限分支而无法找到解，即使在有限空间中也不保证找到最短路径。 广度优先搜索（BFS）逐层扩展所有节点，保证找到最短路径（如果存在），但内存开销是 O(bd)（b 为分支因子），在搜索空间大时会迅速耗尽内存。 迭代加深搜索（IDS）结合了 DFS 的低内存开销和 BFS的完备性。先以深度 1 进行 DFS，再以深度 2，逐步增加深度限制。虽然看似重复搜索了很多节点，但由于搜索树中每层的节点数远大于之前所有层之和，额外开销可以忽略。

启发式搜索 ​

A* 算法是启发式搜索的经典算法。它使用评估函数 f(n)=g(n)+h(n) 对每个节点进行排序，其中 g(n) 是从起点到节点 n 的实际代价，h(n) 是从 n 到目标的估计代价（启发式函数）。当启发式函数满足可容许性（不高估实际代价）时，A* 保证找到最优解。

text
A* 搜索示例（路径规划）

起点 S，终点 G，h 为到 G 的直线距离估计

        f=10(S)
       /        \
    f=5(A)     f=7(B)
    /    \        |
 f=6(C) f=8(D) f=4(G) ← 找到目标！

优先队列：[B(f=7), C(f=6), D(f=8)]
弹出 f 最小的 C，扩展...

启发式函数的设计是 A* 算法性能的关键。好的启发式函数能够大幅减少搜索节点数，差的启发式函数退化为广度优先搜索。在实际问题中，启发式函数通常基于问题的松弛版本计算——去掉某些约束后问题的最优解代价就是原问题的一个可容许估计。

对抗搜索 ​

在博弈场景中，搜索需要考虑对手的策略。极小极大算法（Minimax）假设对手总是做出最优应对，在博弈树上交替选择最大化己方收益和最小化己方收益的节点。Alpha-Beta 剪枝通过维护搜索窗口 [α,β] 剪掉不可能影响最终结果的分支，将搜索效率提升约一倍。 Deep Blue 在 1997 年击败国际象棋冠军 Kasparov，本质上就是大规模的对抗搜索加上精心设计的评估函数。它不"理解"棋局，只是在庞大的搜索树上高效地评估了数十亿个节点。这种暴力搜索的方法在围棋上失败了——围棋的搜索空间（10170）远超国际象棋（1047），AlphaGo 后来通过神经网络提供更精确的评估函数和策略指导才突破了这一障碍。

不确定性推理 ​

纯粹的逻辑推理要求所有前提都确切为真或为假，但现实世界充满了不确定性。病人可能只有 70% 的概率是细菌感染，传感器读数可能有噪声，用户表达的需求可能含糊不清。符号 AI 发展出多种处理不确定性的方法。

确定性因子 ​

MYCIN 系统使用确定性因子（Certainty Factor）处理医学诊断中的不确定性。每条规则关联一个 CF 值（-1 到 +1 之间），表示规则结论的可信程度。规则的 CF 值与前提的 CF 值相乘传播到结论，多条规则支持同一结论时通过组合函数合并 CF 值。 确定性因子的数学基础并不严格——CF 的组合公式是经验性的，不满足概率论的基本公理。但 MYCIN 在实际诊断中表现良好，这说明在工程实践中，简单但实用的近似方法有时优于理论严谨但复杂的方法。

贝叶斯推理 ​

贝叶斯网络（Bayesian Network）用有向无环图表示变量间的概率依赖关系，每个节点的条件概率分布只依赖于其父节点。推理过程就是利用贝叶斯定理计算后验概率：给定某些观察到的证据变量，计算查询变量的条件概率。 贝叶斯网络的理论基础比确定性因子严格得多，它满足概率论的所有公理，推理结果是数学意义上的最优。但在大规模网络上，精确推理的计算复杂度是 NP 困难的，实际系统通常使用近似推理算法（如变分推断、马尔可夫链蒙特卡罗采样）。

模糊逻辑 ​

模糊逻辑（Fuzzy Logic）由 Lotfi Zadeh 在 1965 年提出，打破了经典逻辑中"非此即彼"的二元划分。在模糊逻辑中，一个元素可以部分地属于一个集合，比如 30 岁的人属于"年轻"集合的隶属度可能是 0.6，属于"中年"集合的隶属度可能是 0.4。模糊逻辑在控制系统中有广泛应用——洗衣机根据衣物重量和脏污程度的模糊值自动选择洗涤模式，空调根据温度差和湿度的模糊值调整制冷功率。

从搜索到学习 ​

符号 AI 的搜索算法在特定领域取得了成功，但暴露了一个根本问题：搜索依赖手工设计的评估函数和启发式策略。国际象棋的评估函数是人类专家精心设计的，换一个领域就需要重新设计。AlphaGo 的突破在于用神经网络自动学习评估函数和策略，摆脱了对人类专家知识的依赖。这不是搜索算法本身的问题，而是知识获取的问题——当知识可以从数据中自动学习时，搜索的效率才能真正发挥出来。