引用本文

孙新, 严西敏, 尚煜茗, 欧阳童, 董阔. 一种基于共享度模型的改进Rete算法. 自动化学报, 2017, 43(9): 1571-1579. doi: 10.16383/j.aas.2017.c160674

SUN Xin, YAN Xi-Min, SHANG Yu-Ming, OUYANG Tong, DONG Kuo. An Improved Rete Algorithm Using Shared Degree Model. ACTA AUTOMATICA SINICA, 2017, 43(9): 1571-1579. doi: 10.16383/j.aas.2017.c160674

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160674

关键词

专家系统，Rete算法，有穷自动机，推理机 

摘要

专家系统是人工智能领域的重要分支，其中知识表示和知识推理是专家系统的重要组成部分.Rete算法是一种高效的模式匹配算法，能够解决专家系统中推理效率的问题，但是Rete算法在构建Rete网络和推理过程中存在空间和性能方面问题.本文采取有穷自动机理论的思想，阐述了Rete算法中的模式共享度和节点共享度模型，提出了一种Rete网络构建和推理算法来降低Rete网络的复杂度，提升Rete网络推理的速度.最后实验结果表明，本算法能够降低网络复杂度，提升推理速度.

文章导读

专家系统(Expert system)是一种运用专家提供的领域知识进行推理和判断, 求解那些需要专家才能解决的复杂问题的智能计算机程序[1].专家系统在人工智能领域应用广泛.在很多领域, 专家系统发挥了很大作用, 例如智能医疗和决策规划等[2].

专家系统是推理机和知识库的结合[3], 知识库用来保存专门的知识, 推理机使用知识库里的知识来解决问题.一直以来, 专家系统面临两个核心问题[4]:知识表示和知识推理.其中, 知识推理是专家系统中的关键技术, 也是近些年来优化专家系统的主要方向.

Rete算法是Forgy针对专家系统中推理问题提出的一种解决方法[5], 作为一种前向链形推理算法, 其核心思想是采用增量匹配的概念, 根据内容动态构造匹配树, 以达到显著降低计算量的效果.目前大部分规则推理引擎都使用Rete算法作为核心推理算法.但Rete算法也存在诸如推理网络构造复杂、推理速度过低等问题.在生成推理网络的时候, Rete算法没有考虑规则中节点的分布情况, 生成的规则网络可能过于复杂, 导致存储Rete网络的代价过大, 影响Rete网络的推理速度.

针对Rete算法推理过程中存在的问题, 本文提出了一种基于节点共享度模型的高共享性Rete网络构建算法(Rete algorithm based on the shared degree model, ReteSDM), 结合自动机理论优化推理系统中Rete网的构建过程.实验结果显示, 该算法有效提高Rete网络的节点共享性能, 减少冗余节点, 提升推理效率.

图 1  Alpha网络节点共享模型图

图 2  Beta网络节点共享模型

图 3  变换顺序后Beta网络节点共享模型

近年来, 人工智能在各方面都取得了良好的应用[16-18], 专家系统在人工智能领域扮演了很重要的角色.在专家系统中, 推理机是一个重要的组成部分.但是专家系统在推理过程上存在不足, 例如规则保存和推理速度等. Rete算法是专家系统中的经典算法, 但是传统的Rete算法也存在空间和性能方面问题.

本文根据节点共享度模型和模式共享度模型, 提出了一种新型Rete网络构造算法, 在Rete网络的构建中, 将规则中条件按照共享度进行排序, 构建出高共享性的Rete网络.并且在此基础上, 使用索引的方法对其进行推理优化.实验结果表明, 使用本算法创建Rete网络之后, 能够降低Rete网络的复杂度, 提升节点的共享度, 进而加快推理速度.

作者简介

严西敏

北京理工大学硕士研究生.2015年获得北京理工大学计算机学院学士学位.主要研究方向为人工智能, 机器学习. E-mail: yanximin@foxmail.com

尚煜茗 

北京理工大学硕士研究生.主要研究方向为大数据, 人工智能.E-mail:yumshang@126.com

欧阳童 

北京理工大学硕士研究生.主要研究方向为机器学习, 人工智能.E-mail:ouyangtong714@163.com

董阔 

北京理工大学硕士研究生.主要研究方向为智能医疗, 机器学习.E-mail:dongkuo@163.com

孙新 

北京理工大学计算机学院副教授.主要研究方向为人工智能, 机器学习, 智能决策.本文通信作者.E-mail: sunxin@bit.edu.cn