プロダクションシステムにおけるマッチング候補の概念を用いた高速パターンマッチングアルゴリズム

• Item type: Journal(1)
• 公開日: 1996-06-15
• タイトル: プロダクションシステムにおけるマッチング候補の概念を用いた高速パターンマッチングアルゴリズム
• タイトル / 言語: en
• タイトル: A Fast Pattern Matching Algorithm Using Matching Candidates for Production Systems
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 人工知能
• 著者所属: NTTコミュニケーション科学研究所
• 著者所属: 大阪大学基礎工学部システム工学科／現在，大阪府立大学総合科学部
• 著者所属: 大阪大学基礎工学部システム工学科
• 著者所属: 大阪大学基礎工学部システム工学科
• 著者所属(英): en
• 著者所属(英): NTT Communication Science Laboratories
• 著者所属(英): en
• 著者所属(英): Department of Systems Engineering, Faculty of Engineering Science, Osaka University/College of Integrated Arts and Sciences, Osaka Prefecture University
• 著者所属(英): en
• 著者所属(英): Department of Systems Engineering, Faculty of Engineering Science, Osaka University
• 著者所属(英): en
• 著者所属(英): Department of Systems Engineering, Faculty of Engineering Science, Osaka University
• 著者名: 松下, 光範; 馬野, 元秀; 鳩野逸生; 田村, 坦之
• 著者名(英): Mitsunori, Matsushita; Motohide, Umano; Itsuo, Hatono; Hiroyuki, Tamura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Reteアルゴリズムをはじめとする従来のプロダクション・システムの高速化手法では ルールの条件部をデータフローネットワークに展開し 作業記憶要素をトークンとして流している.これらの高速化手法は有効であるが 作業記憶の更新が頻繁に起こるような場合には そのネットワーク中の定数をテストするノードにおいてまだ無駄な処理を行っている.そこでこの無駄な処理を解消するために マッチング候補の概念を用いたデータフローネットワークによる高速推論アルゴリズムを提案する.このネットワークでは Reteネットワークでは定数をテストするノードとして同一に扱われているノードをパターン間テストノードとパターン内テストノードに分類して それらの間にマッチング候補メモリノードを持つことで 無駄な処理を行うことを従来手法に比べて少なくすることができる. また マッチする作業記憶要素と条件パターンの組を少ない比較回数で特定するために ID3決定木作成アルゴリズムの考え方を用いたパターン間テストノード作成アルゴリズムを提案する.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Some fast pattern matching algorithms have been proposed to improve the reasoning speed of production systems. In almost all of these methods, rule conditions are represented in a data-flow network and elements in a working memory flow through this network as tokens. These algorithms are effective, however, excessive constant testing still cannot be avoided for instances when the working memory must be frequently updated. This paper proposes a fast pattern matching algorithm for a production system. It uses an improved reasoning network employing matched candidates to circumvent such constant testing which is inherent in conventional networks. Using an example conventional network, the Rete network, we classify constant-test nodes into inter-pattern test nodes and intra-pattern test nodes. Then we introduce memory nodes for matching candidates between these test node classes. This is done in order to find unnecessary matching patterns more quickly. The ID3 algorithm is used to make an efficient inter-pattern test network which is capable of finding patterns in the rule conditions for the working memory element. This algorithm is implemented in Austin Kyoto Common Lisp (AKCL) and is applied to several rule bases with good results.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 37, 号 6, p. 988-997, 発行日 1996-06-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764