読者です 読者をやめる 読者になる 読者になる

【アーキテクチャパターン】POSA Vol.1のBlackboard(ブラックボード)

Pattern-Oriented Software Architecture Vol.1に載っているアーキテクチャパターンの1つ,Blackboardをまとめる.

Blackboardアーキテクチャパターンは,決定論的な解決戦略が分かっていない課題に対して有効である.複数のサブシステムが持つそれぞれの知見を組み合わせることによって,部分的,もしくは近似的に妥当な解を得ることができる.

前提

解答にいたる確実なアプローチが存在しないか,あるいは存在するとしても現実的ではないような,いまだ成熟していないドメイン.

課題

Blackboardパターンのシステムは,「黒板システム」と呼ばれる.

以下のフォースが,この課題に対する解答に影響を与える

  • 解空間に対する全探索は,時間がかかるため現実的でない
  • ドメインが未成熟なので,同一サブタスクに対して異なるアルゴリズムを試す必要があるかもしれない
  • 異なる種のアルゴリズムが存在し,それぞれが部分問題を解く.
  • 入力,中間結果,最終形がそれぞれ異なる表現形式を持つ.
  • 1つのアルゴリズムは,通常,他のアルゴリズムの結果を使用する.
  • 不確かなデータと近似解が含まれる
  • アルゴリズムが独立しているため潜在的に並列実行できる.

解決策

独立したプログラムが共通のデータ構造上で協調的に作業を行い,そのようなものが集まってシステムを構成する. タスク全体に対して,各プログラムは特定の部分のみを担う. 各プログラムは独立しており,互いに呼び出すこともない.順序もない. むしろ現在の進行状態に基づいて,システムの方向付けがなされる. このデータ主導の制御方法は日和見問題解決(opportunistic problem solving)と呼ばれる.

静的側面

システムは下記3つのコンポーネントからなる.

Blackboard(黒板コンポーネント

中核となるデータ書庫. 解空間の要素と制御データはここに格納される. 語彙という言葉を,黒板上に現れる,ある時点におけるデータ要素集合を指して用いる. すべての知識源に対し,黒板は自身への書き込みと読み出しを行うインターフェースを提供する.

解空間に存在するすべての要素は,黒板上に現れることが可能である. 問題解決の処理中にさくさ製され,そして黒板上に置かれた解のことを「仮説」(hypothesis),あるいは「黒板エントリ」と表すことにする. 1個の仮説は属性を複数もつ.たとえば抽象レベルという属性があり,これは「入力情報からの概念的な距離」を表す. この抽象レベル属性の値が低ければ,その仮説が表現している内容はいまだ入力情報のレベルから隔たってないことを示す.

Knowledge Source(知識源コンポーネント

問題全体に対して,各々特定の側面からその解決に努める,個々に独立したサブシステムである. これら知識源コンポーネントが一体となって,問題ドメイン全体のモデルを構築する. 単体ではなく,複数の知識源の結果を統合することによって,はじめて最終的な解を構築することができる.

知識源コンポーネント同士が直接,連絡をとりあうことはない. 黒板を介し,そこから読み出し,そこへの書き込みを行うのみである. したがって知識源コンポーネントは黒板上に現れる語彙を理解できなくてはならない.

それぞれの語彙は,いつ,どのような条件のもとであれば貢献できるのか,それを明らかにする義務がある. したがって,知識源は条件節と実行説にわけられる.

  • 条件節
    • 黒板上にかかれている現在の解の進行状況を評価
    • 自身が解の追求に貢献できるかどうかを判定
  • 実行節
    • 黒板の内容に影響を及ぼすことになる結果を提供する

Control(制御コンポーネント

黒板上の変化をモニタし,次にどのようなアクションを起こすかを決定することを繰り返す. また知識源の評価と活性化を,知識適用戦略に従ってスケジューリングする. この戦略の源は,黒板上の情報である. 得る.

以下にBlackboardにおける3コンポーネント間の関係を示す. 知識源は,黒板上のinspectを呼び出し,現在の解を調べる. そして,黒板上のデータを変更するためにupdateを用いる. 制御コンポーネントは黒板の変化を監視し,次にとるべきアクションを決定するという繰り返しを行う.

f:id:yusuke_ujitoko:20161117205113p:plain

動的側面

  • 制御担当コンポーネントがループ開始
  • 制御担当コンポーネントが次に適用する知識源を選択するためにnextSource()を実行
  • nextSourceは,最初に黒板の観察を行い,どの知識源を利用するかを決める.
  • nextSourceは,各知識源の条件節を起動する.
  • 知識源の実行説が仮説に対して適用される.

f:id:yusuke_ujitoko:20161117205917p:plain

実装

  1. 対象となる問題を定義する
    • 問題が属するドメイン,解を見つけるための知識領域をそれぞれ明らかにする
    • システムへの入力を調べる
    • システムの出力を定義する
    • ユーザとのやり取りを詳細化する
  2. その問題に対応した解空間を定義する
    • 中間的な解とトップレベルの解を区別し,部分的な解と完備した解を区分する.
  3. 問題解決のプロセスを手段へと展開する
  4. 特定のサブタスクに対応させて,それに特化した知識源へと知識を分割する
  5. 黒板に現れる語彙を定義する
  6. どのようにシステムが制御されるのかを明らかにする
  7. 知識源を実装する

バリエーション

プロダクションシステム

サブルーチンが条件-結果ルールとして表される. データは作業メモリに存在し,大局的に利用できる. 条件-結果ルールは,条件の指示を行う左辺部と結果を支持する右辺部から構成される. 右辺部の結果は,左辺部の条件が満たされ,そのルールが選択された場合のみ実行される.

リポジトリ

中核となるデータ構造がリポジトリと呼ばれる. Blackboardアーキテクチャでは,現在のデータ構造の状態が,制御担当コンポーネントと結びつき,最終的に知識源が活性化される. それとは対象的に,リポジトリでは内部に制御機構をもたない. ユーザ入力や外部プログラムによって制御される. 例えばDBをリポジトリとみなせる.

適用例

HEARSAY-Ⅱ

最初の黒板システムはHEARSAY-Ⅱ音声認識システム

HASP/SIAP

CRYSALIS

TRICERO

汎用化

SUS

結論

Blackboardパターンの利点

  • 試行による接近
  • 変更容易性と保守性の支援
  • 再利用可能な知識源 フォールトトレランスと頑強性の支援

Blackboardパターンの欠点

  • 結果に再現性が伴わないため,テストが困難
  • 解の妥当性が保証されない
  • 優れた制御戦略を確立するのが困難である
  • 低い効率性
  • 開発労力が多大である
  • 並列性を支援しない

yusuke-ujitoko.hatenablog.com