决策引擎核心算法—Rete算法起源篇

如果你对规则引擎这个领域有一定的了解，你可能会知道，Rete是主流的算法。实际上有两个流派：推崇推理模式的，以及不推崇的。Rete是在推理模式下执行规则的核心算法。在之前的文章中，我讨论过在商用BRMS中使用的各种算法的区别和重要性。当然，在使用这些技术时您并不需要知道它们是如何工作的——就像您开车并不需要理解力学一样。话虽这么说，我知道有好奇心的人会希望了解引擎之下隐藏的是什么？在这篇文章中，我将聚焦在Rete 算法的起源上。

第一次接触

Charles L. Forgy博士[1] 在七十年代后期开发出了这个著名的算法，但是直到业务规则技术出现后一段时间，Rete算法才变得广为流行起来。我不记得在我攻读计算机科学硕士学位的时候，曾经被教授过Rete算法，尽管我们学习了相当多的人工智能知识。当我还是一个年轻的顾问时，我的专家系统经常让我手忙脚乱，直到我被介绍给ILOG Rules。我一加入公司，就成为了这个技术的大粉丝，最终的发布产品叫JRules。我记得当柯长海（音）亲自到美国教我们Rete算法的时候，我终于学到了这个伟大的技术的内部结构。当然，ILOG，Blaze和大多数推理引擎提供商都对该算法进行了略微修改或添加功能，以提高其速度。

最令我惊讶的是，虽然过去了很多年，算法本身实际上并没有什么文献。当我加入Blaze Software时，我很震惊，只有极少数人知道它是如何工作的。最后我终于接受了“使用者不必知道其内在机制”的理念，但我认为，作为供应商我们有责任知道其内在机制。十多年前，我还是个年轻的纯粹主义者。

关于Rete

Rete是Charles在卡内基梅隆大学工作的成果。虽然该算法已经从原始工作文件改进到博士论文，但我们经常参考1982年发表的最终论文。该方法的天才之处是将独立条件的评估“状态”保存在内存中，并消除了重复的计算。因此，按照密集的定义模式-匹配的规则项目可以比使用一般的方法更快地评估，特别是当新事实需要被不断加入时。

“推理”项目是这种方法的理想用例，因为它们存在相关的决策，例如规则1（高消费）意味着规则2（VIP客户），进一步意味着规则3（免费送货）等等。事实上，在我们看起来，这将是乏味的不断重新计算。在这个例子中，退货这样一个新事实可能会影响最初的决定，最终导致需要在发票上加上运费。这是一个简单的例子，因为我们通常在结帐服务之前就能获得所有的事实。推论项目的大多数学术实例用商业术语描述更复杂，因为它们包含诸如猴子试图通过跳上桌子或椅子拿香蕉，或客人只是基于兴趣来选择坐在谁身边等等。

我所见的在商业环境中，Rete网络的最佳使用可能是报警关联和监控。这意味着随着时间的推移，当发生某些情况时，警报将会收到一种“有状态的”执行指令。考虑到实际中的电信网络是由成千上万的设备组成来“基础”和处理报警的，因此Rete的表现优于暴力法毫不奇怪。当一个路由器上发出一个警报时，Rete网络不必重新处理所有过去的事件，来判断到我们达到了同一台设备上的5个主要警报的阈值，来触发适当的处理，从而最终提供一个可能的诊断。处理时间在网络管理系统中变成了几秒钟。这是不可思议的。    

尽管如此，并不是所有的商业规则项目都需要推断。当所有的数据放在面前，规则之间也没有什么来回，那么串行执行可能和Rete一样快，甚至更快。还有些需要推论，但毫无疑问和Rete没什么关系的情况，比如当法国人讲“y a pas photo”时，根据字面意思推断他是“不需要图片”的。

名字的起源

我听到过算法名称起源的很多不同说法。它们都指的是在内存中创建的结构，Rete网络，它看起来像一个由节点和链接组成的复杂的网。我将在下一篇文章中发表，Charles给我个人关于算法起源的真实答复！

从技术上来说，Rete并不是首字母缩略词，所以不应该全部大写。所以我应该纠正一下，并且以后都用‘Rete’来指代它。过去一些我做的已经好多了，不过我还是喜欢全部大写。

Rete的发展

原始的Rete算法多年一直在进化。

大多数BRMS供应商开发了自己的算法，在圈内被称为XRete或uni-rete，其主要涉及性能改进和内置的对一些特定功能的支持。

Rete2是Charles在自己的引擎“OPS/J”中开发的版本。性能改进打破了传说中的“Rete墙”，它指的是当工作内存中的对象数量增加时，会导致剧烈的性能下降。

Rete3是为RulePower开发的Rete2的进化版，随后集成在BlazeAdvisor中。当然，我不能随意地告诉你相关的商业秘密。为了避免来自FICO的麻烦，我什么也不会说。

最新的发展

我们在之前的博客中宣布“Charles已经提出了Rete算法的另一个变体”，这个变体比它前身的表现更为优越。你可能会想知道为什么他没有遵循既定的命名方案，称之为Rete4...

是为了致敬Windows-NT也破坏了以前建立的数字序列么？

这次我不会卖关子！Rete4是一个意大利私人电视频道的名称，使用它最坏情况会侵犯版权，最好的情况也会导致混淆。有一段时间，Charles把这个算法称作TECH，在确定这个名字没法google之后，决定重新把它命名为Rete-NT。目前Rete-NT算法，在明策引擎上独家使用，明策引擎隶属于上海信数金服。

[1]：Charles L.Forgy博士，Sparkling Logic投资人与战略顾问，Rete算法及决策引擎发明人著名的计算机科学家。曾创立Rules Power公司并担任首席科学家，后被FICO收购。2010年离开FICO，以投资人和战略咨询顾问的角色加入Sparkling Logic公司，为其提供强有的技术保障和战略支持。