前向和后向链接

Question

我正在尝试了解在我正在编写的程序的人工智能编程中向后和向前链接的最佳用途。有人能够解释向后和向前链接的最理想用途吗？另外，您能举个例子吗？

Answer 1

我对目前对“前向链接”和“后向链接”的理解做了一些研究。这带来了很多材料。这里是 ar\xc3\xa9sum\xc3\xa9。

\n

首先是一张图表，部分基于：

\n

\n
• 关于逻辑、规则和逻辑编程之间关系的悲伤状态(Robert Kowalski)
\n

\n

LHS代表规则的“左侧”，RHS代表规则的“右侧”。

\n

让我们将“基于规则的系统”（即基于规则进行本地计算的系统）分为以下三组：

\n

\n
• 产生式规则系统，包括老式的专家系统外壳，它们不是建立在逻辑原则上的，即“没有指导模型”。
\n
• 逻辑规则系统，即基于逻辑形式主义的系统（通常是一阶逻辑的片段，经典的或直觉的）。这包括 Prolog。
\n
• 重写规则系统，基于LHS => RHS重写规则重写一些工作记忆的系统。
\n

\n

可能还有其他人。一组的特征可以在另一组中找到。一个组的系统可以部分或全部由另一组的系统实现。重叠不仅是可能的，而且是肯定的。

\n

（遗憾的是，imgur 在 2020 年不接受 .svg，所以它是 .png）

\n

\n

\n
• 绿色：正向链接
\n
• 橙色：向后链接
\n
• 黄色：序言
\n

\n

RuleML（一个组织）尝试将现有的各种规则集 XML 化。他们将规则分类如下：

\n

\n

以上内容出现在Adrian Paschke 的《RuleML Perspective on Reaction Rule Standards》中。

\n

因此，他们对“审议规则”和“反应规则”进行了区分，这是合适的。

\n

第一个框：“生产规则系统”

\n

“产生式规则系统”（PRS）的总体思路

\n

\n
• 有“LHS->RHS规则”和元规则，后者控制第一个规则的应用。规则可以是“逻辑的”（类似于 Prolog Horn 子句），但不一定如此！
\n
• PRS有一个“工作记忆”，只要应用规则，它就会发生破坏性的改变：工作记忆中的元素或事实可以被删除、添加或替换。
\n
• PRS 仅具有“操作语义”（它们由其所做的事情定义）。
\n
• PRS 没有“声明性语义”，这意味着没有正确的方法来推理规则集本身：它计算什么，它的固定点是什么（如果有的话），它的不变量是什么，它是否终止等等。
\n
• 更多功能：\n
  \n
  • 使用本地可计算函数（即不是概率计算）对不确定性进行临时处理，如MYCIN中那样，使用模糊规则、Dempster-Shaefer 理论等。
  \n
  • 强否定可以以特别的方式表达。
  \n
  • 一般情况下，不会执行僵局回溯，必须明确执行。
  \n
  \n
\n
• PRS 可以直接连接到其他系统：调用神经网络、调用优化器或 SAT 求解器、调用传感器、调用 Prolog 等。
\n
• 对解释和调试的特殊支持可能存在也可能不存在。
\n

\n

示例实现

\n

\n
• 古代:\n
  \n
  • 老派的“专家系统 shell”，通常用 LISP 编写。
  \n
  • 1971 年的Planner，这是具有基本（？）前向和后向链接的语言。该语言的实现从未完成。
  \n
  • 最初的 OPSx 系列，特别是 OPS5，其上运行的是R1/XCON （具有 2500 条规则的 VAX 系统配置器）。这实际上是一个前向链接的实现。
  \n
  \n
\n
• 最近：\n
  \n
  • CLIPS（用 C 语言编写）：http://www.clipsrules.net/
  \n
  • Jess（用 Java 编写）： https: //jess.sandia.gov/
  \n
  • Drools（用“企业”Java 编写）： https: //www.drools.org/
  \n
  \n
\n

\n

Drools 支持“向后链接”（具体如何），但我不确定其他任何人是否支持，如果支持，它看起来是什么样子）

\n

PRS 中的“前向链接”

\n

前向链接是 PRS“循环”的原始方法，也称为“识别-行动”循环或“数据驱动循环”，它表明了它的用途。事件-条件-动作架构是另一种常用的描述。

\n

内部工作很简单：

\n

\n
1. 规则LHS与工作记忆进行匹配（由于RETE 算法，每次工作记忆更新时都会发生）。
\n
2. 根据某些标准（例如优先级）选择匹配规则之一并RHS执行它。这一直持续到不再有LHS匹配为止。
\n

\n

这个循环可以被视为命令式基于状态的语言的更高层次的方法。

\n

Robert Kowalski 指出，“前向链接”规则实际上是两种不同用途的合并：

\n

前向链逻辑规则

\n

这些规则将“前取式”反复应用于工作记忆并添加推论事实。

\n

例子：

\n

\n

“如果 X 是一个人，那么 X 就是凡人”

\n

\n

用途：

\n

\n
• 审议、完善表述。
\n
• 状态空间的探索。
\n
• 如果您想要更多的控制或空间，那么规划是非常重要的（R1/XCON 是一个前向链接系统，我觉得这很令人惊讶。这显然是由于希望将资源使用保持在范围内）。
\n

\n

Fahiem Bacchus在《使前向链接相关》 （1998）中写道：

\n

\n

正向链接规划器有两个特别有用的属性。首先，他们维护有关潜在计划生成的中间状态的完整信息。这些信息可用于提供高效的搜索控制、域独立启发式控制以及甚至更有效的域相关控制……前向链接规划器的第二个优点是它们可以支持丰富的规划语言。例如，TL​​Plan 系统支持完整的 ADL 语言，包括函数和数值计算。数字和函数对于对实际规划领域的许多特征（尤其是资源和资源消耗）进行建模至关重要。

\n

\n

上述内容在多大程度上真正适用是有争议的。您始终可以编写向后链接规划器以保留更多信息或通过搜索策略选择模块开放配置。

\n

前向链接“反应规则”又名“刺激响应规则”

\n

例子：

\n

\n

“如果你饿了就吃点东西”

\n

\n

刺激是“饥饿”（可以从传感器读取）。反应是“吃点东西”（这可能意味着控制效应器）。有一个未明确的目标，即“减少饥饿”，这是通过饮食来实现的，但没有任何深思熟虑的阶段来明确该目标。

\n

用途：

\n

\n
• 立即、非故意的代理控制：LHS可以是传感器输入，RHS可以是效应器输出。
\n

\n

PRS 中的“反向链接”

\n

向后链接，也称为“目标导向搜索”，应用“目标缩减规则”并运行“假设驱动循环”，这表明了它的用途。

\n

例子：

\n

\n
• BDI代理商
\n
• 霉素
\n

\n

在以下情况下使用此功能：

\n

\n
• 您的问题看起来像是一个“目标”，可以分解为“子目标”，可以单独解决。根据问题的不同，这可能是不可能的。子目标相互依赖性太多或结构太少。
\n
• 您需要按需“提取更多数据”。例如，您询问用户Y/N问题，直到您对对象进行了正确分类，或者同等地，直到获得诊断。
\n
• 当您需要计划、搜索或构建目标证明时。
\n

\n

作为一种编程练习，我们可以将后向链接规则也编码为前向链接规则。然而，人们应该选择最适合自己问题的表示形式和计算方法。这就是向后链接存在的原因。

\n

第二个框：“逻辑规则系统”（LRS）

\n

这些是基于某些底层逻辑的系统。系统的行为可以（至少一般来说）独立于其实现进行研究。

\n

请参阅此概述：斯坦福哲学百科全书：自动推理。

\n

我区分了“逻辑问题建模”系统和“逻辑编程”系统。两者在 Prolog 教科书中被合并。简单的“逻辑问题”可以直接在Prolog中建模（即使用逻辑\n编程），因为该语言“足够好”并且不存在不匹配的情况。然而，在某些时候，您需要专用系统来完成您的任务，而这些系统可能与 Prolog 有很大不同。有关示例，请参见Isabelle或Coq 。

\n

将我们自己限制在用于“逻辑编程”的 Prolog 系列系统中：

\n

LRS 中的“前向链接”

\n

Prolog 系统本身不支持前向链接。

\n

前向链逻辑规则

\n

如果您想要前向链接逻辑规则，您可以“在 Prolog 之上”编写自己的解释器。这是可能的，因为 Prolog 是通用编程语言。

\n

这是逻辑规则前向链接的一个非常愚蠢的示例。最好定义一种特定于领域的语言和适当的数据结构：

\n

add_but_fail_if_exists(Fact,KB,[Fact|KB]) :- \\+member(Fact,KB).\n   \nfwd_chain(KB,KBFinal,"forall x: man(x) -> mortal(x)") :-\n   member(man(X),KB),\n   add_but_fail_if_exists(mortal(X),KB,KB2),\n   !,\n   fwd_chain(KB2,KBFinal,_).\n\nfwd_chain(KB,KBFinal,"forall x: man(x),woman(y),(married(x,y);married(y,x)) -> needles(y,x)") :-\n   member(man(X),KB),\n   member(woman(Y),KB),\n   (member(married(X,Y),KB);member(married(Y,X),KB)),\n   add_but_fail_if_exists(needles(Y,X),KB,KB2),\n   !,   \n   fwd_chain(KB2,KBFinal,_).\n      \nfwd_chain(KB,KB,"nothing to deduce anymore").\n\nrt(KBin,KBout) :- fwd_chain(KBin,KBout,_).\n

\n

尝试一下：

\n

?- rt([man(socrates),man(plato),woman(xanthippe),married(socrates,xanthippe)],KB).\nKB = [needles(xanthippe, socrates), mortal(plato),\n      mortal(socrates), man(socrates), man(plato), \n      woman(xanthippe), married(socrates, xanthippe)].\n

\n

人们已经研究了向 Prolog 添加高效前向链接的扩展，但它们似乎都已被放弃。我发现：

\n

\n
• 1989：向 Prolog 添加前向链接和真值维护(PDF)（Tom_Finin、Rich Fritzson、Dave Matuszek）\n
  \n
  • GitHub 上有一个积极的实现： Pfc - Prolog 中的前向链接，以及SWI-Prolog 包，另请参阅此讨论。
  \n
  \n
\n
• 1997：Prolog 中对反应式规则的有效支持(PDF) (Mauro Gaspari) ...作者谈到了“反应式规则”，但显然意味着“前向链式审议规则”。
\n
• 1998：关于主动演绎数据库：状态日志方法（Georg Lausen、Bertram Lud\xc3\xa4scher、Wolfgang May）。
\n

\n

科瓦尔斯基写道：

\n

\n

“Zaniolo（LDL++？）和 Statelog 使用类似情境演算的表示形式和框架公理，并将产生式规则和事件-条件-动作规则简化为逻辑程序。两者都受到框架问题的困扰。”

\n

\n

前向链式反应规则

\n

Prolog 并不是真正为“反应式规则”而设计的。已经做了一些尝试：

\n

\n
• LUPS：一种用于更新逻辑程序的语言（1999）（Moniz Pereira、Halina Przymusinska、Teodor C. Przymusinski C）
\n

\n

“基于逻辑的生产系统”（LPS）是最近出现的并且相当有趣：

\n

\n
• 在溯因逻辑编程代理中集成逻辑编程和产生式系统（Robert Kowalski、Fariba Sadri）
\n
• RR2009 上的演讲：在溯因逻辑编程代理中集成逻辑编程和生产系统
\n
• LPS网站
\n

\n

它定义了一种新的语言，其中观察导致前向链接，后向链接导致行为。两个“孤岛”都通过溯因逻辑编程中的完整性约束连接起来。

\n

所以你可以替换这样的反应规则：

\n

\n

通过类似这样的逻辑解释：

\n

\n

第三个框：“重写规则系统”（前向链接）

\n

另请参阅：重写。

\n

这里我就简单提一下CHR。它是一种前向链接系统，根据匹配工作存储器元素的规则连续重写工作存储器中的元素，验证逻辑保护条件，并且如果逻辑保护条件成功则移除/添加工作存储器元素。

\n

CHR可以理解为线性逻辑片段的应用（参见Hariolf Betz的“A Unified Analytical Foundation for Constraint Handling Rules”）。

\n

SWI Prolog 存在 CHR实现。它为 CHR 规则提供回溯功能，并且可以像任何其他 Prolog 目标一样调用 CHR 目标。

\n

CHR 的用法：

\n

\n
• 通用计算模型（例如图灵机等）
\n
• 自底向上解析。
\n
• 类型检查。
\n
• 约束逻辑编程中的约束传播。
\n
• 任何您宁愿前向链（自下而上的过程）\n而不是后向链（自上而下的过程）的东西。
\n

\n