Drools 6 Documentation ナナメ読みその３

Drools

http://docs.jboss.org/drools/release/6.0.1.Final/drools-docs/html_single/index.html#d0e2752

III. Drools Runtime and Language

5. Hybrid Reasoning

5.1. Artificial Intelligence

AIの栄枯盛衰を語るでー

5.1.1. A Little History

1990年頃にAIは失墜したけど、2005年に "Spring comes to AI winter" が提唱される。実践的、商業的な領域でイケるレベル、状況に達した。

5.1.2. Knowledge Representation and Reasoning

これ "must read for anyone wanting to build strong foundations" だそうです。"Knowledge Representation and Reasoning" http://www.amazon.co.jp/gp/product/1558609326/

5.1.3. Rule Engines and Production Rule Systems (PRS)

Ontology = the representation model we use for our "things" (情報科学でのオントロジーは「概念体系」という訳が一般的なんですかね)
Rete の発音は REH-te or RAY-tay
when/then の2部構造ルールを Production Rule と呼ぶ
Drools5 -> ReteOO, Drools6 -> PHREAK

5.1.4. Hybrid Reasoning Systems (HRS)

forward chaining と backward chaining の比較。図が分かりやすい。

5.1.5. Expert Systems
5.1.6. Recommended Reading

これ "a must have, for anyone's bookshelf" だそうです。"Artificial Intelligence: A Modern Approach " http://www.amazon.co.jp/dp/0130803022/

5.2. Rete Algorithm

rete はラテン語で "net" or "network".
discrimination network ... データがネットワークを通ってフィルタされていく

  • RootNode
    • 入り口。すぐにObjectTypeNodeへつなぐ
  • ObjectTypeNode
    • Objectのタイプでまずフィルタする
    • Drools内部ではHashMapにObjectTypeNodeのリストを持って、instance of処理を短縮する
  • AlphaNode
  • BetaNode (JoinNode / NotNode)
    • two-input を持つ
      • left input はオブジェクトのリスト(= Tuple)
      • right input はひとつのオブジェクト
    • left input は Beta Memory と呼ばれ、全ての incoming tuples を憶えている。right input は Alpha Memory と呼ばれ、全ての incoming objects を憶えている。
    • Drools内部ではBetaNodeのインデックス化を行う（hashでlookupなど）
  • LeftInputAdapterNode
    • Object を受け取り、single Object Tuple に変換して BetaNode につなぐ
  • TerminalNode
    • 終端。あるひとつのルールが、条件に完全にマッチしたことを示す。

Droolsでは複数のルールがノードをシェアすることができる。結果的に、ひとつの複雑なネットワークが出来上がる。

5.3. ReteOO Algorithm

ReteOOはReteの拡張。以下のfeature

  • Node sharing
  • Alpha indexing
  • Beta indexing
    • ここまで、上記で説明済み
  • Tree based graphs
    • tree graph により、asymmetrical propagationを実現。 faster and less impact on the GC, and more robust
  • Modify-in-place
    • delete + insert を避ける
  • Property reactive
    • factのpropertyが変更された際の再評価のreactをfine grained にする。
  • Sub-networks
    • Not, Exists and Accumulate のネストされた条件は、Sub-networkを構成する
  • Backward Chaining
  • Lazy Truth Maintenance
  • Heap based agenda
    • Agenda は binary heap queue を使う
  • Dynamic Rules
    • ルールの動的追加、削除
5.4. PHREAK Algorithm

Drools 6 で導入。ReteOOの拡張だけど、すごく変わったのでもはや別の名前なんだ。

  • Three layers of contextual memory; Node, Segment and Rule memories.
  • Rule, segment and node based linking.
  • Lazy (delayed) rule evaluation.
  • Isolated rule evaluation.
  • Set oriented propagations.
  • Stack based evaluations, with pause and resume.

[理解が間違っていたらスマヌ。後日もっとちゃんと勉強します]

  • goal orientedなので、実行されることが期待されるルールのみ評価される。よって、insert/update/delete時より、fireAllRules時の処理が多くなる。
  • tuple oriented ではなく set oriented。評価されるひとつのルールに対して、insert/update/deleteんのsetがまとめて、ノードを通過していく
  • networkはセグメント化される。ビットマスクを各ノードに適用する。ビットがonだと、linkedであり、ゴールが生成される

以下、複数ルールからどのようにセグメントが構成され、ビットマスクが使われるかを図とともに解説。

  • PHREAK はひとつのルールの処理速度では RETE と変わらないだろう
  • しかし、非効率なルールに対して、PHREAK は RETE より、寛大だろう（ひどく性能が劣化したりしないだろう）
  • 大量、複雑なルールに対して、PHREAK は RETE より、性能の低下が緩やかになる
  • つまり、速くなるというよりは遅くなりにくい、ということ
  • PHREAK では AgendaGroup と salience が性能向上に有効になる。これらにより、不要なルール評価が減らせる。