(前回の続き)

ちなみに前回のケースは、条件部分に書かれている

契約(　$id_no : 証券番号,　基本保険金額 > 30000000)

は、制約条件が「基本保険金額 > 30000000」の一つですが、これにたとえば「○○特約付加==true」などという条件が加わると、ネットワーク上は、「基本保険金額 > 30000000」のαノードの次に、「○○特約付加==true」のαノードが直列に付け加わります。

さて次にβノードを用いた実例を見てみましょう。αノードは一つのファクトに対する制約条件でしたが、βノードは複数のファクトにまたがる制約条件を表すノードとなります。このノードは2つの入力(Left Input, Right Input)があり、左の入力はファクトの組、右の入力は、ファクトとなります。またこのそれぞれの入力は、部分的にマッチしたファクトの組やファクトの待機場所となるメモリを持ちます。

ここでは典型的なβノードであるJoinノードを例にとって見てみましょう。

先ほどのルールに加えて、もう一つルールを加えてみます。

新たに加えた、基本保険金額2のルールは、顧客タイプのファクトに対する条件を加えています。顧客が持っている保険契約(リスト)に基本保険金額が3000万を超えるものがあればメッセージを出力するというものです。

このルールファイルは以下の形のReteネットワークとなります。

まず、同じ条件の部分は、２つのルールでグラフのノードが共有されていることに注意ください。さらに新たな種類のノード(黄緑のノード)が表れています。これがβノードの一種であるJoin ノードになります。

• Joinノード
  LeftInputAdapterノードから入ってくるファクトの組(Left Input)と、Right Input
  からのファクトとを合わせて判断し、条件が満たされれば入力から新たなファクトの
  組をつくり、次に渡す。

では、上記のネットワークにファクトをinsertしてみましょう。以下のファクトを次々に加えていきます。

f-1．契約(証券番号=’10001′, 基本保険金額=40000000)
f-2．契約(証券番号=’10005′, 基本保険金額=20000000)
f-3．顧客(顧客番号=’10005′, 保険契約={f-1,f-2})

まずf-1をinsertします。契約→αノード(基本保険金額>3000万)を通過してLeftInputAdapterノードに入ります。ここでファクトの組(f-1)が生成され、2つの方向に伝播していきます。一方はTerminalノードに行き、ルール”基本保険金額1″と合わさって、実行候補のリストに付け加えられます。もう一方は、黄緑のJoinノードの左入力となります(上の図ではJoinノードの右になっていますが^^;)。

さて、Joinノードの左(上図では右)入力に(f-1)が入ってきました。Joinノードは片方の入力に値が入ってきたので、もう片方の入力のメモリを見に行きます。しかしまだメモリは空なので(f-1)はそのまま左入力のメモリに保存されます。

次にf-2をinsertしましょう。契約→αノード(基本保険金額>3000万)と行きますが、この時点でこのαノードを通過できません。

最後にf-3をinsertしましょう。顧客のファクトなので、顧客に進み、次のJoinノードの入力になります。Joinノードでは、片方の入力としてf-3が入ってきたので、f-3を右入力のメモリに保持すると同時に、左入力のメモリを見に行きます。左入力のメモリには(f-1)が入っていたので、f-3と、(f-1)を使って条件判断をします。f-3には、f-1の保険契約が含まれているので、条件が満たされ新たなファクトの組((f-1),f-3)を生成して次に渡します。最後にこのファクトの組はルール”基本保険金額2″と合わさって、実行候補のリストに加えられます。

以上、このようにしてファクトがinsertされていきます。ファクトが削除(retract)されるときは対象のファクトを入口から流して逆に削除していき、ファクトの更新の場合はretract&insertの動きになります。

以上がReteアルゴリズムの概略です。わかりにくい部分も多々あったかと思いますが、雰囲気はおおよそつかめていただけたのではないかと。

ルールベースのアプリケーションのパフォーマンス見積もりなどでは、簡単なのでついついルール数で概算見積もりをしてしまいます。しかし本来は、パフォーマンスとルール数自身とは直接の関係はありません。パフォーマンスに影響するのは、むしろルールの条件部分のバリエーションの数であるということがおわかりいただけたのではないかと思います。

あと、最近のルールエンジンの使い方から考えると、Reteアルゴリズムは少々オーバースペックなので、使い方に制限があるかわりに、より軽い Sequential アルゴリズムもよく使われますが、それはまたの機会に。

(参考文献)
Michal Bali,  Drools JBoss Rules 5.0 Developer’s Guide PACKT publishing.
Jérôme Boyer, Hafedh Mili, Agile Business Rule Development Process, Architecure, and JRules Examples Springer.

(前回の続き)

さて、Reteアルゴリズムは最初にルールをコンパイルしてネットワークの形に表現します。

(なお、ここではDroolsで用いられているReteOOというオリジナルReteの派生形を説明に用いますが、本質的な部分での違いはありません)。

たとえば本家サイトの方で例示しているルール(DroolsTest3.drl)をReteのネットワークにコンパイルすると、

となり、入口(○)が一つ、出口(●)がルール数だけある有向グラフができます。

(ちなみにDroolsのEclipseプラグインでルールファイル(.drlファイル)を表示するとReteTreeタグで上のようなReteネットワークを見ることができます)

Reteアルゴリズムは、ファクト(データ)を追加/変更/削除するたびにReteネットワークの入口から投入/チェックしていくのですが、まずはこのグラフについて最初に説明しましょう。ただ上記のルールそのままですと説明が複雑になるかと思いますので、最初にルール一つのケースから説明をします。

さて、以下のルールがあったとします。

このルールは以下の形のReteネットワークとなり、

それぞれのノードは

• Reteノード
  ファクトを追加する際の入り口となるノード
• EntryPointノード
  CEP(Drools Fusion)で複数のエントリーポイントを持つことができるが、今回はデフォルトのエントリーポイントのみを使用。
• ObjectTypeノード
  ファクトのオブジェクトタイプを識別して、フィルタとして働くノード。上記のルールでは「契約」タイプのオブジェクトを通す。
• αノード
  条件部での制約をチェックしてフィルタとして働くノード。条件部のひとつのオブジェクトに対する制約条件ひとつがひとつのノードになる。上記の例では、「基本保険金額>30000000」がこれにあたる。
• LeftInputAdapterノード
  βノード(後述)へのエントリーポイントとなるノード。ここまで関門をくぐり抜けてきたファクトからファクトの組(tuple)を生成する。
• Terminalノード
  if-thenルールのthen部分にあたるノード。ここまで到達したファクト(の組)がthen部分と合わさって実行候補のリストに登録される(前回の記事の１．で言う「マッチしたルールとデータのカップルを列挙」したリストに登録されるということ)

と呼ばれます。

以上がReteのネットワークの説明ですが、単にルールをネットワーク化しただけではルールの実行サイクルを効率化することには寄与しません。そこで着目するのが、前回書いたように

「ワーキングメモリの中身が変わらなければ、マッチするファクトとルールの組も変わらない。」
「1回のルール実行では、ワーキングメモリの中身はほとんど変わらない。」

という点です。ワーキングメモリにファクトが追加されたり、ワーキングメモリのファクトを変更/削除したりした都度、今作成したReteネットワークの入り口から投入し、ルールの条件にマッチするかしないかを判定します。ここで重要なことは、ファクトとルール条件との判定はルールの実行サイクルの判定のフェーズで行われるのではなく、すでにファクトをワーキングメモリに挿入したり、変更/削除したりするときに同時に判定されるということなのです。

では、上で作成したReteネットワークにファクトを挿入してみましょう。以下の3つのファクトがワーキングメモリにinsertされるとします。

f-1．契約(証券番号=’10001′, 基本保険金額=40000000)
f-2．契約(証券番号=’10005′, 基本保険金額=20000000)
f-3．顧客(顧客番号=’10005′)

この例では、ファクトf-1のみが、ルール基本保険金額1にマッチしますから、基本保険金額1(f-1)といったルールとファクトの組が、ルール実行候補のリストに追加されるはずです。

ではまず、ファクトf-1がinsertされたとしましょう。f-1は、Reteノード、EntryPointノードを通過し、Objectノードに入ります。このObjectノードはObjectの種類が契約であるというフィルタとなっていますがf-1は条件を満たすので、そのまま通過します。次のαノードは、基本保険金額 > 30000000という判定条件ですが、f-1はこれもまた満たすので通過します。次のLeftInputAdapterノードは、次に向かう準備としてf-1をファクトの組(tuple)に変換して、最後のTerminalノードに渡します。TerminalノードではLeftInputAdapterノードでできたファクトの組とルールとを組にして(基本保険金額1(f-1))、ルール実行候補リストに追加します。

次にf-2をinsertしてみましょう。f-2は、f-1と同様に、Reteノード、EntryPointノード、Objectノードは通過しますが、αノードは基本保険金額 > 30000000という判定条件を満たさないのでこれ以上は進めません。

最後にf-3をinsertしてみると、Reteノード、EntryPointノードは通過しますが、Objectノードは条件を満たさないのでこれ以上は進みません。

以上の状況を図にすると、

となります。

(つづく)

今日はルールエンジンの代表的なアルゴリズムReteアルゴリズムを。
ルールエンジンのアルゴリズムにも書いたように、ルールエンジンは、

１．ワーキングメモリ(短期記憶)に入ったデータ(ファクト)の集合に対して、たくさんあるルールの条件部分をひとつひとつファクトとマッチングさせて、マッチしたルールとデータのカップルを列挙しておく。
２．カップルの中からひとつを選んで実行する。
３．実行によってワーキングメモリ(短期記憶)のファクトが書き換えられる場合もあるので、再度１．のカップリングを行う。
４．１～３を繰り返してマッチするルールがなくなったところで実行が終了する。

(前回の続き)
もっとも、入力データのチェックなどは、ルールのパターンマッチの側面こそ利用していますが、一方でルールの実行中に入力データが変わっていくわけではないので、先に挙げたルールの実行サイクルを何度も回して結果を出すという特徴的なところはあまり利用していないとも言えます。

では、よりルールエンジンの動きの特徴が表れている例というとどんな例があげられるでしょうか。思うに、たとえば質問に対して答えていき最後に結果を出すといったコンサルティングというか、レコメンドというか…といったシステムの例はそのひとつではないでしょうか。

この動きをルールエンジンの実行サイクルに合わせて見てみましょう。まずは、

１．システムは利用者に対して最初の質問を投げます。
２．利用者は質問に対する回答を行いその回答はデータとして(短期)記憶領域に書かれます。
３．システムはこの回答に合ったルールを選び出し、次の質問を利用者に投げます。
４．利用者はさらに回答を行い結果は記憶領域に書かれます。
５．システムは今までに出した質問の結果と今回の質問の結果を合わせて条件に合うルールを選び出し、さらに質問を繰り返していきます…。
６．そして最後に十分に絞り込まれた結果が得られそれ以上尋ねる質問がなくなった(マッチするルールがなくなった)ところで利用者に結果を返します。

これだけではあまりに抽象的なので、もう少しかみくだいた例として、たとえば、料理に合うワインをおすすめするといった場合を考えてみましょう(この具体的な実装は、Clipsというツールの例としてあげられています)。

まず質問としては、

１．料理は肉、魚、鳥料理のうちのどれですか？
２．料理にはソースがかかっていますか？
３．ソースは、スパイシー、甘口、クリーム、トマトのうちのどれですか？
４．料理の味は、繊細、ふつう、強めのうちのどれですか？
５．ワインとしてお好きなのは赤と白とどちらですか？
……

といった感じ。これら質問をルールとして保持し、ルールの実行部分で質問の回答を記憶領域に書くようにしておきます。
さて、まず最初に１．の質問のルールが動き、質問に対して「肉」という回答をすると、(短期)記憶領域に

・「料理は肉」

と書かれます。次に２．の質問に、「ソースがかかっていない」という回答をすると、記憶領域に

・「料理にはソースがかかっていない」

という事実が追加されます。
次に３．の質問。これは本来、料理にソースがかかっていなければ意味のない質問です。したがって、３．の質問を行うルールの条件部分には「料理にはソースがかかっている」という前提条件を加えておきます。そうすると、現在の記憶領域の状態

・「料理は肉」
・「料理にはソースがかかっていない」

に３．の質問ルールはマッチしないので、ルールは実行されません。一方、２．でソースがかかっていると回答すると自然に３．のルールもマッチしてきます。

このように、質問を行う各ルールの前提条件をきちんと書いておけば、意味のない質問をすることもなく、効率的に結果を求めることができましょう。

さて、実は上の議論では少々ゴマカシがあるのですが、お気づきでしょうか。上の議論では、１．から順に実行することが前提となっているような書き方になっていますが、ルールエンジンの一般的な動きでは上から順に動くという保証はありません。順番に関して何も指定していない(*1)と、上記のルールのうち１．２．４．５．のどのルールが最初に動くかの保証は何もありません。
まあ、論理的には最初に１．２．４．５．のどの質問から聞いても結果は同じなのですが、ワインの好みに対して聞く４．５．の順番はともかく、１．２．は気持ちとしては、１．の次に２．を聞くのがふつうかと。こんなときには、
A.　２．の前提条件に料理の種類が決まっている条件。
具体的には、「料理は○○」という事実があるという条件を加える。
B.　ルールに優先度をつけて、１．が２．よりも先に動くようにする。
というような解決方法があります。まあ、ルールの一般的なお作法としては、A.のほうが推奨ですが、ケースバイケースで一概にどちらがいいというわけでもありません。
さらに質問のかたまり間で順番をつけたいという場合に、たとえば料理に関する質問のルール、ワインの好みに関する質問のルールといったかたまりの間での順番をつけたいというときには、ルールのかたまりとその順番を定義するという仕組みがたいていのルールエンジンに標準的に装備されています(Droolsでは、アジェンダグループとか、ルールフローとか)。

(*1)　実は、ルールが動く順番は全くのランダムというわけではなく、たいていの場合何らかの規則にしたがって、実行されるルールが選ばれます。この規則を競合解消戦略といって、考え方としては、「最新の情報を優先する」、「一般的な条件のルールと、より特殊な条件のルールと両方にマッチした場合は、特殊な条件のルールを優先する」などといった基準があります。

　久しぶりの更新になってしまいましたが、ここのところルールベースエンジン関連の話題が次々と出てきて・・・Droolsはいつのまにか5.3のFinalが出ていて、5.4のβまで出ているし、CorticonはProgressに買収されるし・・・ちなみに最近またDroolsの新しい本が出たようです。

　それはそうと、おかげさまで最近私もルールエンジンの仕事がだいぶ増えてきてうれしい限り。ただ、まだまだ人口に膾炙するといったところではないようで、ルールエンジンの動き等に関連していろいろ質問されることが多々あります。
たとえば
・ルールエンジンのプログラムって、if-Thenのルールが並んでいるけれども、上から順にやっていくの？？
・(上記に関連して)　通常のプログラムの(単体)テストだと全部のパスを通るようにテストするけれども、　ルールの場合のテストでは、全部のパスを通す…ってどのように考えればよい？
・ルールエンジンのメモリ使用量は何に依存してきまるのでしょうか？　ルール数？
・同じようにルールエンジンの処理速度は何できまる？
などなど。

　私もこのような質問をされるようになって、あらためてネットなどを調べてもみるのですが、ルールエンジンの動きとかアルゴリズムとか結構情報が少なくて、ルールエンジンの代表的なアルゴリズムであるはずのReteアルゴリズムの日本語の解説などは、ちょっと探してみたところネット上にはほとんど皆無状態でした。
　というわけで、これからぼちぼちルールエンジンの動きやアルゴリズムなど気が付いたときに書いていきたいと思います。
　さて、最初というわけでルールエンジンの動きから。以前、本宅の記事(プロダクションシステム(ルールベースシステム)とは)にルールエンジンの動きを書きましたが、もともとはこのルールエンジン、人工知能や認知心理学の研究をルーツとするもので
人間が長期記憶にあたる「ルール」を使って、認識した外界の状況(短期記憶に保持される)に合わせて判断を行うという行動がモデルとなっています。
　これをルールエンジンの動きとして翻訳してみると、
１．データの集合に対して、たくさんあるルールの条件部分をひとつひとつデータとマッチングさせて、マッチしたルールとデータのカップルを列挙しておく。
２．カップルの中からひとつを選んで実行する。
３．実行によってデータが書き換えられる場合もあるので、再度１．のカップリングを行う。
４．１～３を繰り返してマッチするルールがなくなったところで実行が終了する。
となります。
　この動きをみるとわかるように、ルールエンジンでは、すべてのデータに対して、すべてのルールの条件部のマッチングを試し、そののちにルールを実行します。したがってルールの実行順序は必ずしも上から順などといったことではなくて(実はそれなりの実行順の規則はあるのですが)、実行順に過度に依存するようなルールの書き方はむしろお作法に反するものという見方が強いです。
　特に最近ルールエンジンがよく使われている入力データのチェックなどは、(チェックそのものだけでいえば)別に順番などはどうでもよく、条件に合うか合わないかで正しくエラーが出ればそれでよいのであって、上記のようなルールエンジンの動きはこの「チェック」という作業に対して非常になじむもののように思います。