专家系统/Rete 算法
Rete 算法是一种用于实现产生式规则系统的有效模式匹配算法。Rete 算法由 卡内基梅隆大学的 查尔斯·L·福吉 博士设计,首次在 1974 年 的工作论文中发表,并在其 1979 年 的博士论文和 1982 年 的论文中进行了详细阐述(见参考文献)。Rete 已成为许多流行专家系统的基础,包括CLIPS、Jess、JBoss Rules 和 Soar。
对专家系统的一种朴素实现可能会检查每个规则与 知识库中已知的 事实是否匹配,并在必要时触发该规则,然后继续处理下一条规则(并在处理完所有规则后循环回第一条规则)。对于规则和事实数量中等规模的知识库,这种朴素方法执行速度过慢。
Rete 算法(通常读作“REET”、“REE-tee”或在欧洲读作“re-tay”,来自拉丁语“rete”的网状结构,或网络)为专家系统的更高效实现提供了基础。基于 Rete 的专家系统构建了一个节点网络,其中每个节点(根节点除外)对应于规则左侧出现的模式。从根节点到叶节点的路径定义了完整规则的左侧。每个节点都存储了满足该模式的事实的记忆。这种结构本质上是广义的Trie。
当断言或修改新事实时,它们会沿着网络传播,导致节点在事实匹配该模式时被标记。当事实或事实组合导致给定规则的所有模式都得到满足时,会到达叶节点,并触发相应的规则。
Rete 算法旨在牺牲内存以提高速度。在大多数情况下,与朴素实现相比,速度提升了几个数量级(因为 Rete 性能在理论上独立于系统中规则的数量)。但是,在非常大的专家系统中,原始 Rete 算法往往会遇到内存消耗问题。此后,已经设计了其他算法,包括新算法和基于 Rete 的算法,这些算法需要更少的内存。
Rete 算法提供了一种通用的逻辑描述,用于实现功能,该功能负责在模式匹配产生式系统(一种规则引擎类别)中,将数据元组(“事实”)与产生式(“规则”)进行匹配。一个产生式包含一个或多个条件和一组操作,这些操作可以针对匹配这些条件的每一组完整事实进行。条件测试事实属性,包括事实类型说明符/标识符。Rete 算法具有以下主要特征
- 它通过使用节点共享来减少或消除某些类型的冗余。
- 它在执行不同事实类型之间的连接时存储部分匹配项。这反过来又允许产生式系统在对产生式系统的活动内存进行更改时,避免对所有事实进行完全重新评估。相反,产生式系统只需要评估活动内存的更改(增量)。
- 它允许在从活动内存中撤回事实时有效地删除内存元素。
Rete 算法被广泛用于实现模式匹配引擎中的匹配功能,这些引擎利用匹配-解决-操作循环来支持正向链接和推理。
Rete 是有向无环图,表示更高级别的规则集。它们通常在运行时使用内存中对象的网络来表示。这些网络将规则条件(模式)与事实(关系数据元组)进行匹配。Rete 网络充当一种关系查询处理器,有条件地对任意数量的数据元组执行投影、选择和连接。
产生式(规则)通常由分析师和开发人员使用某种高级规则语言来捕获和定义。它们被收集到规则集中,然后在运行时(通常在运行时)被翻译成可执行的 Rete。
当事实被“断言”到活动内存时,引擎会为每个事实创建“活动内存元素”(WME)。事实是n 元组,因此可能包含任意数量的数据项。每个 WME 可能会保存整个n 元组,或者,每个事实也可以由一组 WME 来表示,其中每个 WME 都包含一个固定长度的元组。在这种情况下,元组通常是三元组 (3 元组)。
每个 WME 都会在单个根节点进入 Rete 网络。根节点将每个 WME 传递给它的子节点,每个 WME 可能会在网络中传播,可能存储在中间内存中,直到它到达终端节点。
节点图的“左侧”(alpha)形成一个判别网络,负责根据简单的条件测试来选择单个 WME,这些条件测试将 WME 属性与常数值进行匹配。判别网络中的节点也可以执行比较同一个 WME 的两个或多个属性的测试。如果一个 WME 成功地与一个节点所代表的条件匹配,它将被传递到下一个节点。在大多数引擎中,根节点的直接子节点用于测试每个 WME 的实体标识符或事实类型。因此,所有代表相同实体类型的 WME 通常会遍历判别网络中给定分支的节点。
在判别网络中,每个 alpha 节点分支(也称为 1 输入节点)都终止于一个名为“alpha”内存的内存。这些内存存储与给定节点分支中每个节点的每个条件匹配的 WME 集合。未能与分支中的至少一个条件匹配的 WME 不会在相应的 alpha 内存中物化。alpha 节点分支可以分叉,以最大程度地减少条件冗余。
一种可能的变体是在判别网络中的每个中间节点引入额外的内存。这会增加 Rete 的开销,但在规则动态添加到或从 Rete 中删除的情况下可能具有优势,从而更容易动态地改变判别网络的拓扑结构。
Doorenbos 描述了另一种实现。在这种情况下,判别网络被一组内存和一个索引代替。该索引可以使用哈希表实现。每个内存都保存与单个条件模式匹配的 WME,而该索引用于通过其模式引用内存。这种方法仅在 WME 代表固定长度的元组,并且每个元组的长度很短(例如,3 元组)时才实用。此外,这种方法仅适用于执行相等性测试以匹配常量值的条件模式。当 WME 进入 Rete 时,该索引用于定位一组其条件模式与 WME属性匹配的内存,然后 WME 直接添加到这些内存中的每一个。本身,这种实现不包含任何 1 输入节点。但是,为了实现非相等性测试,Rete 可能包含额外的 1 输入节点网络,WME 在放置到内存中之前会通过这些网络。或者,可以在下面描述的 beta 网络中执行非相等性测试。
Beta 网络
[edit | edit source]图的“右侧”(beta)主要执行不同 WME 之间的连接。它是可选的,仅在需要时才包含。它由 2 输入节点组成,每个节点都有一个“左侧”和一个“右侧”输入。每个 beta 节点将其输出发送到一个“beta”内存。
Beta 节点处理标记。标记是内存内的存储单元,也是内存和节点之间交换的单元。在许多实现中,标记是在 alpha 内存中引入的,在那里它们用于保存单个 WME。然后,这些标记被传递到 beta 网络。
每个 beta 节点都执行其工作,并且作为结果,可能会创建新的标记来保存代表部分匹配的 WME 列表。然后,这些扩展的标记存储在 beta 内存中,并传递到后续的 beta 节点。在这种情况下,beta 节点通常通过从每个接收到的标记中复制现有的 WME 列表到新的标记中,然后通过执行连接或其他操作将更多 WME 添加到列表中,从而将 WME 列表传递到 beta 网络中。然后,新标记存储在输出内存中。
一个常见的变体是构建链表,其中每个标记保存一个单个 WME。在这种情况下,部分匹配的 WME 列表由标记的链表表示。这种方法可能更优化,因为它消除了从一个标记复制 WME 列表到另一个标记的需要。相反,beta 节点只需要创建一个新的标记来保存它希望与部分匹配列表连接的 WME,然后将新标记链接到存储在输入 beta 内存中的父标记。新标记现在形成了标记列表的头部,并存储在输出 beta 内存中。
在 Rete 的描述中,通常会提到 beta 网络中的标记传递。但是,在本文中,我们将根据 WME 列表而不是标记来描述数据传播,以认识到不同的实现选项以及标记的根本目的和用途。当任何一个 WME 列表通过 beta 网络时,可能会向其中添加新的 WME,并且该列表可能会存储在 beta 内存中。beta 内存中的 WME 列表表示对给定产生式中条件的部分匹配。
到达 beta 节点分支末端的 WME 列表表示对单个产生式的完全匹配,并将传递到终端节点。这些节点有时称为“p 节点”,其中“p”代表“产生式”。每个终端节点都代表单个产生式,并且到达终端节点的每个 WME 列表都代表对该产生式中条件的完全匹配的 WME 集。对于它接收到的每个 WME 列表,产生式节点都会在“议程”上“激活”一个新的产生式实例。议程通常以优先队列的形式实现。
Beta 节点通常执行存储在 beta 内存中的 WME 列表与存储在 alpha 内存中的单个 WME 之间的连接。每个 beta 节点都与两个输入内存相关联。alpha 内存保存 WME,并在每次存储新的 WME 时对 beta 节点执行“右侧”激活。beta 内存保存 WME 列表,并在每次存储新的 WME 列表时对 beta 节点执行“左侧”激活。当连接节点被右侧激活时,它会将输入 alpha 内存中新存储的 WME 的一个或多个属性与输入 beta 内存中包含的每个 WME 列表中特定 WME 的给定属性进行比较。当连接节点被左侧激活时,它会遍历 beta 内存中新存储的单个 WME 列表,检索给定 WME 的特定属性值。它将这些值与 alpha 内存中每个 WME 的属性值进行比较。
每个 beta 节点都输出 WME 列表,这些列表要么存储在 beta 内存中,要么直接发送到终端节点。只要引擎将在后续 beta 节点上执行额外的左侧激活,WME 列表就会存储在 beta 内存中。
从逻辑上讲,beta 节点分支头部的一个 beta 节点是一个特殊情况,因为它不会从网络中任何更高层的 beta 内存接收输入。不同的引擎以不同的方式处理这个问题。一些引擎使用专门的适配器节点将 alpha 内存连接到 beta 节点的左侧输入。其他引擎允许 beta 节点直接从两个 alpha 内存接收输入,将其中一个视为“左侧”输入,另一个视为“右侧”输入。在这两种情况下,“头部”beta 节点都从两个 alpha 内存接收输入。
为了消除节点冗余,任何一个 alpha 或 beta 内存都可以用于对多个 beta 节点执行激活。除了连接节点之外,beta 网络还可以包含其他节点类型,其中一些节点类型将在下面描述。如果 Rete 不包含 beta 网络,则 alpha 节点会将每个包含单个 WME 的标记直接馈送到 p 节点。在这种情况下,可能不需要将 WME 存储在 alpha 内存中。
冲突解决
[edit | edit source]在任何一个匹配-解析-动作循环期间,引擎都会找到当前断言到工作内存中的所有事实的所有可能匹配。一旦找到了所有当前匹配,并且相应的产生式实例在议程上被激活,引擎就会确定产生式实例可以“触发”的顺序。这被称为“冲突解决”,并且激活的产生式实例列表被称为“冲突集”。该顺序可以基于规则优先级(突出显示)、规则顺序、将每个实例中包含的事实断言到工作内存的时间、每个产生式的复杂性或其他一些标准。许多引擎允许规则开发人员在不同的冲突解决策略之间进行选择,或者将多个策略的选择链接起来。
冲突解决不是作为 Rete 算法的一部分定义的,而是与算法一起使用。一些专门的产生式系统不执行冲突解决。
产生式执行
[edit | edit source]在执行了冲突解决之后,引擎现在“触发”第一个产生式实例,执行与该产生式相关联的动作列表。这些动作作用于产生式实例的 WME 列表所代表的数据。
默认情况下,引擎将按顺序继续触发每个生产实例,直到所有生产实例都被触发。在任何一次匹配-解析-执行周期中,每个生产实例最多只触发一次。这种特性被称为“折射”。但是,在工作内存进行更改的任何阶段,生产实例触发的顺序都可能被打断。规则操作可以包含从引擎的“工作内存”中断言或撤回 WME 的指令。每次任何单个生产实例执行一个或多个此类更改时,引擎都会立即进入新的匹配-解析-执行周期。这包括对当前在工作内存中的 WME 的“更新”。更新通过撤回然后重新断言 WME 来表示。引擎对更改后的数据进行匹配,这反过来可能会导致议程中生产实例列表的更改。因此,在任何一个特定生产实例的操作执行完毕后,以前激活的实例可能已被停用并从议程中删除,而新的实例可能已被激活。
作为新匹配-解析-执行周期的一部分,引擎对议程进行冲突解决,然后执行当前的第一个实例。引擎继续触发生产实例并进入新的匹配-解析-执行周期,直到议程中不再存在生产实例。此时,规则引擎被认为已完成其工作并停止。
一些引擎支持高级折射策略,其中在先前周期中执行的某些生产实例不会在新的周期中重新执行,即使它们可能仍然存在于议程中。
引擎有可能进入无限循环,其中议程永远不会到达空状态。出于这个原因,大多数引擎支持可以在生产操作列表中调用的显式“停止”动词。它们还可以提供自动循环检测,其中无限循环在给定次数的迭代后自动停止。一些引擎支持这样一种模型,在这种模型中,引擎不会在议程为空时停止,而是进入等待状态,直到新的事实从外部断言。
至于冲突解决,激活生产实例的触发不是 Rete 算法的特性。但是,它是使用 Rete 网络的引擎的核心特性。Rete 网络提供的一些优化仅在引擎执行多个匹配-解析-执行周期的情况下才有用。
存在量词和全称量词
[edit | edit source]条件测试最常用于对单个元组执行选择和连接。但是,通过实现其他 β 节点类型,Rete 网络可以执行量化。存在量化涉及测试工作内存中是否存在至少一组匹配的 WME。全称量化涉及测试工作内存中的一整组 WME 是否满足给定条件。全称量化的变体可能会测试从一组 WME 中提取的给定数量的 WME 是否满足给定条件。这可能是根据测试确切数量或最小数量的匹配。
量化并非在所有 Rete 引擎中都得到普遍实现,并且在支持量化的引擎中,存在多种变体。存在量化的一种变体,称为“否定”,在很大程度上(但并非普遍)得到支持,并在开创性文件中进行了描述。存在量化否定条件和连接涉及使用专门的 β 节点,这些节点测试是否存在匹配的 WME 或 WME 集。这些节点仅在找不到匹配项时才传播 WME 列表。否定的具体实现方式各不相同。在一种方法中,节点在它从左侧输入接收的每个 WME 列表上维护一个简单的计数。该计数指定从右侧输入接收的 WME 中找到的匹配项数量。节点仅传播计数为零的 WME 列表。在另一种方法中,节点在从左侧输入接收的每个 WME 列表上维护一个额外的内存。这些内存是 β 内存的一种形式,并且存储从右侧输入接收的每个匹配的 WME 列表。如果 WME 列表在其内存中没有 WME 列表,则它将向下传播到网络中。在这种方法中,否定节点通常直接激活其他 β 节点,而不是将其输出存储在额外的 β 内存中。否定节点提供了一种形式的 '否定为失败'。
当对工作内存进行更改时,以前与任何 WME 不匹配的 WME 列表现在可能与新断言的 WME 匹配。在这种情况下,传播的 WME 列表及其所有扩展副本都需要从网络中更下层的 β 内存中撤回。上面描述的第二种方法通常用于支持有效地移除 WME 列表的机制。当移除 WME 列表时,任何相应的生产实例都会被停用并从议程中移除。
存在量化可以通过组合两个否定 β 节点来执行。这表示双重否定的语义(例如,“如果 NOT NOT 任何匹配的 WME,那么...”)。这是几种生产系统采用的常见方法。
内存索引
[edit | edit source]Rete 算法没有强制要求任何特定的工作内存索引方法。但是,大多数现代生产系统提供索引机制。在某些情况下,只有 β 内存被索引,而在其他情况下,索引被用于 α 内存和 β 内存。良好的索引策略是决定生产系统整体性能的主要因素,尤其是在执行导致高度组合模式匹配(即大量使用 β 连接节点)的规则集时,或者,对于某些引擎,在执行在多个匹配-解析-执行周期中执行大量 WME 撤回的规则集时。内存通常使用哈希表的组合来实现,并且哈希值用于对 WME 列表和 WME 的子集执行条件连接,而不是对内存的全部内容进行连接。这反过来通常会显著减少 Rete 网络执行的评估次数。
移除 WME 和 WME 列表
[edit | edit source]当从工作内存中撤回 WME 时,必须将其从存储它的每个 α 内存中移除。此外,包含 WME 的 WME 列表必须从 β 内存中移除,并且这些 WME 列表的激活生产实例必须被停用并从议程中移除。存在几种实现变体,包括基于树的移除和基于重新匹配的移除。在某些情况下,可以使用内存索引来优化移除。
处理 OR’ed 条件
[edit | edit source]在定义规则集中的生产时,通常允许使用“OR”连接词对条件进行分组。在许多生产系统中,这是通过将包含多个 OR’ed 模式的一个生产解释为多个生产的等价物来处理的。生成的 Rete 网络包含一组终端节点,这些节点共同代表单个生产。这种方法不允许对 OR’ed 条件进行任何形式的短路。它还可以,在某些情况下,导致议程中激活重复的生产实例,其中相同的 WME 集匹配多个内部生产。一些引擎提供议程去重以处理此问题。
其他注意事项
[edit | edit source]虽然 Rete 算法没有定义,但一些引擎提供了扩展功能来支持对真值维护的更多控制。例如,当为一个产生式找到匹配项时,这可能会导致断言新的 WME,而这些 WME 反过来又与另一个产生式的条件相匹配。如果工作内存的后续更改导致第一个匹配变得无效,则可能意味着第二个匹配也无效。Rete算法没有定义任何机制来自动定义和处理这些逻辑真值依赖项。但是,一些引擎支持附加功能,其中可以自动维护真值依赖项。在这种情况下,一个 WME 的撤回可能会导致自动撤回其他 WME 以维护逻辑真值断言。
Rete算法没有定义任何理由方法。理由是指在专家和决策系统中通常需要的机制,最简单地说,系统会报告为得出最终结论所使用的每个内部决策。例如,一个专家系统可能会通过报告动物很大、灰色、有很大的耳朵、鼻子和象牙来证明动物是大象的结论。一些引擎在其对 Rete算法的实现中提供内置的理由系统。
本文没有提供对 Rete 算法所有可能的变化或扩展的详尽描述。其他考虑因素和创新也存在。例如,引擎可以在 Rete 网络中提供专门支持,以将模式匹配规则处理应用于特定数据类型和来源,例如程序对象、XML 数据或关系数据表。另一个例子是许多引擎为每个进入 Rete 网络的 WME 提供的附加时间戳功能,以及在冲突解决策略中使用这些时间戳。引擎在允许以编程方式访问引擎及其工作内存的方式上表现出显著差异,并且可能会扩展基本 Rete 模型以支持并行和分布式处理形式。
优化和性能
[edit | edit source]已经确定并在学术文献中描述了 Rete 的一些优化。然而,其中一些仅适用于非常特定的场景,因此在通用规则引擎中通常几乎没有或根本没有应用。此外,已经制定了 TREAT 和 LEAPS 等替代算法,它们可以提供额外的性能改进。目前,很少有支持这些替代算法的商业或开源产生式系统。
Rete算法面向从现有事实中计算新事实,或过滤和丢弃事实以得出某个结论的前向链接和“推理”场景。它也被用作一种相当有效的机制,用于执行事实的高度组合评估,其中必须在事实元组之间执行大量联接。其他执行规则评估的方法,例如使用决策树,或实现顺序引擎,可能更适合简单的场景,应该考虑作为可能的替代方案。
下图说明了基本的 Rete 地形,并显示了不同节点类型和内存之间的关联。
- 大多数实现使用类型节点在 n 元组工作内存元素上执行第一级选择。类型节点可以被视为专门的选择节点。它们区分不同的元组关系类型。
- 该图没有说明专门节点类型(例如否定连接节点)的使用。一些引擎实现了几种不同的节点专门化,以扩展功能并最大限度地优化。
- 该图提供了 Rete 的逻辑视图。实现可能在物理细节方面有所不同。特别是,该图显示了在 beta 节点分支头部提供正确激活的“虚拟”输入。引擎可能会实现其他方法,例如允许 alpha 内存直接执行正确激活的适配器。
- 该图没有说明所有节点共享可能性。
有关 Rete 算法的更详细和完整的描述,请参阅 Robert Doorenbos 编著的《大型学习系统生产匹配》第 2 章(见下方链接)。
Rete II
[edit | edit source]在 1980 年代,Charles L. Forgy 开发了 Rete 算法的后继者,名为Rete II[1]。与原始 Rete(它是公共领域的)不同,该算法没有公开。Rete II 声称对于更复杂的问题具有更好的性能(甚至数量级)。
参考文献
[edit | edit source]- Charles Forgy,“生产系统的网络匹配例程”。工作论文,1974 年。
- Charles Forgy,“关于生产系统的高效实现”。卡内基梅隆大学博士论文,1979 年。
- Charles Forgy,“Rete:一种针对多模式/多对象模式匹配问题的快速算法”,人工智能,19,第 17-37 页,1982 年
外部链接
[edit | edit source]- 大型学习系统生产匹配 - R Doorenbos 对 Rete 的详细和易懂的描述,还描述了针对大型系统优化的名为 Rete/UL 的变体(PDF)
- 根据规则(来自cut-the-knot的简短介绍)