第1章 プロダクションシステムとOPS5

参考

SmallOPS を発展させた Toy Open Production SystemSourceForge.jp にて公開しています。

また、本コンテンツを書くに辺り、以下の参考書を参考にしています。

1. 1. プロダクションシステムとは?

プロダクションシステム(production system)とは、 if-then形式のルールを用いて問題解決を行うシステムのことである。 if-then形式のルールとは「もし〜ならば〜を行う」という判断を行うための基本形式のことで、 プロダクションシステムではこれを「条件-行動」という情報として表現しており、 これをプロダクションルール(production rule)という。 プロダクションシステムは、 このプロダクションルールと外部から与えられた事実を元に推論を行うシステムのことで 以下の図に示すような基本構成を持つ。



図1: プロダクションシステムの基本構成

外部世界もしくは推論によって得られた事実(fact)を蓄積しておく場所のことを ワーキングメモリ(working memory)、 プロダクションルールを蓄積しておく場所のことをルールベース(rule base)という。 また、実際に既知の事実とプロダクションルールから推論を行う機構のことをルールインタプリタ(rule interpreter)という。

プロダクションシステムは、与えられた事実から プロダクションルールを使って新しい事実の推論を行うが、 プロダクションルールの使い方によって前向き推論型と後向き推論型に大別できる。

1. 1. 1. 前向き推論型プロダクションシステム

前向き推論型のプロダクションシステムは、 既知の事実から出発して新しい事実を導出する推論方式で、 「条件 → 行動」という方向でプロダクションルールを用いた推論である。 既知の事実をプロダクションルールの条件と突合せ、 全ての条件が満たされたプロダクションルールの行動を実行する。 プロダクションルールの行動を実行することを、 特にそのプロダクションルールが発火する(fire)という。 これは原因から結果を導き出す推論であり、トップダウン的な処理であると言える。 例えば以下のようなルールがあり、

Aという事実がわかったとする。すると、 A ⇒ BというルールからBが導かれる。

  1. A ⇒ Bというルールによって、Bが導かれる。
  2. B ⇒ Cというルールによって、Cが導かれる。

従ってA,B,Cという3つの事実が導かれる。 前向き推論型のプロダクションシステムは、 目的に関係なくプロダクションルールを用いて既知の事実から導かれる全ての知識を導く。

1. 1. 2. 後向き推論型プロダクションシステム

後向き推論型のプロダクションシステムは、 結論の候補である仮説から出発してその仮説が妥当であるかどうかを立証する推論方式で、 「行動 → 条件」という方向でプロダクションルールを用いた推論である。 後向き推論型のプロダクションシステムは、 仮説として立てた事実を結論に持つプロダクションルールを探し、 そのプロダクションルールの条件が全て満たされるかどうかを再帰的に探索していくことで推論が行われる。 これは結論から原因を導き出す推論であり、ボトムアップ的な処理であると言える。 例えば以下のようなルールがあり、

Aという事実がわかっていて、Cであることを立証したいとする。すると、

  1. Cを帰結とするルールとしてB ⇒ Cが選択される。Bはまだ証明されていないのでさらに探索を続ける。
  2. Bを帰結とするA ⇒ Bが選択される。Aは既にわかっているのでCが導かれる。

従ってCが立証される。 後向き推論は仮説を立証することが目的であり、仮説を立証するのに関係のない事実は原則的に導かれない。


1. 2. 前向き推論型プロダクションシステム OPS5

OPS5(Official Production System 5)は、代表的な前向き推論型のプロダクションシステムである。 次章では、 以降教材として扱うSmallOPSというOPS5に真似て作った単純なプロダクションシステムを紹介するが、 その前にこの節ではOPS5の概要について説明する。

1. 2. 1. 文法

OPS5は、事実とプロダクションルールに関して以下のような文法を持っている。



図2: OPS5の基本文法

事実は、システムによって自動的に付けられる時刻タグという番号と オブジェクト名とそのオブジェクトの性質を表す属性の列からなる。 時刻タグはシステムによって付けられるため、ユーザは実際には記述しない。 事実はオブジェクト(object)・ 属性(attribute)・属性値(value)という 三種類のデータで構成されることからこれを特にOAV形式という。 以下に例を挙げる。

豊の父は、究である
(human ^name yutaka ^father kiwamu)

約束は12時30分である
(appointment ^hour 12 ^minute 30)

プロダクションルールは、大きく条件部と行動部に分けて考えることができる。 条件は、事実と同じOAV形式の文法を持つ。 条件は、ルールインタプリタによってワーキングメモリの事実とのマッチングが取られる。 マッチングが成功した場合のことを条件が満たされたという。 ただし、条件の前にマイナス記号が付いている場合は否定の意味になる。 その場合ルールインタプリタは、 その条件とマッチングする事実がワーキングメモリに無かった場合に限り条件が満たされたと判定する。

行動にはいくつかの種類があるが、make, modify, removeの3つが代表的である。 これらの行動はそれぞれ以下のような効果をワーキングメモリに起こす。

以下に例を挙げる。

childの父がfatherであり、fatherの父がgrand_fatherであるなら、childの祖父はgrand_fatherである
(P grand_father
 (human ^name <child> ^father <father>)(human ^name <father> ^father <grand_father>)
 ->
 (make (human ^name <child> ^grand_father <grand_father>))
)

事実およびプロダクションルールは、それぞれワーキングメモリとルールベースに蓄積される。 また事実に付けられる時刻タグおよびプロダクションルールのルール名はシステムにおいて一意であることから、 それぞれを特定するための情報として使用される。

1. 2. 2. 競合解消

OPS5は前向き推論型のプロダクションシステムであるため ルールインタプリタがプロダクションルールの条件部と事実とのマッチングを取っていき、 条件部の全ての条件がマッチングされたときその行動部が実行される。

プロダクションシステムには、新しい事実を追加するmakeだけでなく 既知の事実の修正を行うmodifyや既知の事実を削除するremoveなどの行動があるため、 どのような順番でプロダクションルールが発火するかは最終的な結果に大きな影響を及ぼす。 OPS5は、一度のフェーズで全てのプロダクションルールの発火可能性を判断する。 一度のフェーズで発火可能と判断された 全てのプロダクションルールのことを競合集合(conflict set)といい、 また、そのプロダクションルールの条件部を満足した事実の集合を例化(instantiation)という。 ルールインタプリタは、この競合集合のなかのどれを発火させるかを決定しなければならない。 このことを競合解消(conflict resolution)といい、 競合解消を行う方法のことを戦略(strategy)という。 OPS5は以下のような競合解消戦略を採用している。

  1. refraction
  2. 一度実行した例化を二度以上実行しない。

  3. recency
  4. 条件部を満足した事実の時刻タグが一番小さい例化を実行する。

  5. specificity
  6. もっとも詳細な条件部を持つプロダクションルールにマッチングした例化を実行する。

  7. abbitrary choise
  8. 最後はランダムに選択する。

これ以外にもいくつかの競合解消戦略が存在する。


次へ:SmallOPSの概要