成果

プロジュクト1年目では PRISMのプロトタイプを設計・実装し、実 際にベイズネット、 隠れマルコフモデルなど既存の記号的確率モデ ルの記述実験により、PRISM プログラムの記述力と学習能力を確かめ た。プロジュクト２年目の本年度は、最初の実装を見直し、 処理系の強化を行ない、また GUIの付加など便利性を高める為の改良 を行なった。

• 組み込み確率的述語 の bsw から msw への拡張：

  PRISMの確率的スイッチを表現する基本組み込み述語 bsw(sw_1,P,S) は S=1, S=0 の2つの値を持つ。我々 は bsw を拡張し、 S に3つ以上の値（任意の基底項を許す） をとることができる msw を実装した。また、この拡張に伴って EM学習アルゴリズムの修正を行なった。

  msw を用いることでユーザの記述する統計モデルがより簡潔な 形になるだけでなく、学習時間も短縮される。それは n (n 2) 個の排反な事象を表現するには bsw が n-1 個必要にな るのに対し、 msw を用いれば1つだけで済むからである。繰り 返しアルゴリズムであるEMアルゴリズムの 1ステップの計算時間は出 現するスイッチの値の個数（ bsw は 2）の総計に比例するので、 学習時間の大幅な削減が期待できる。 下に 血液型遺伝プログラ ムの bsw バージョンと msw バージョンを示す。

  • bsw バージョン：

    bloodtype(X) は血液型が X であること、 genotype(X,Y) は遺伝子型が XY であること、 gene(P,G) はどちらかの親 P から遺伝子 G を もらうことを表す。

    	bloodtype(a) :- genotype(a,a); genotype(a,o); genotype(o,a).
    	bloodtype(b) :- genotype(b,b); genotype(b,o); genotype(o,b).
    	bloodtype(o) :- genotype(o,o).
    	bloodtype(ab):- genotype(a,b); genotype(b,a).
    
    	genotype(X,Y) :- gene(father,X), gene(mother,Y).
    
    	gene(P,G) :-
            ( bsw(1,P,1), G=a
            ; bsw(1,P,0),( bsw(2,P,1), G=b
                         ; bsw(2,P,0), G=o ) ).
    

    gene(P,G) の確率分布を定めるのに bsw(1,_,_) と bsw(2,_,_) という2つのスイッチを2分木の形で組み合わせる 必要がある。
  • msw バージョン：

    bloodtype(X), genotype(X,Y) の定義節は上と同じであるが、 gene(P,G) は1つのスイッチを使って

    	gene(P,G) :- msw(1,P,G).
    

    と書くだけで済む。ただし msw(1,_,_) が値 a, b, o をとることについて別に宣言する 必要がある。

• EMルーチンのCへの書き換え：

  学習では第1 段階である Prolog 上の全解探索の結果を元にEMアルゴ リズムを動作させる。EMアルゴリズムの入力には記号的情報は出現し ないので、 より高速な動作が期待できるC言語への移植を行なった。 具体的には SICStus Prolog 3 のforeign language interface を 用いている。EMアルゴリズムは確率スイッチのパラメータの更新を繰 り返して尤度の local maximum を探索するため、 良い解を得るには 数千回の繰り返しを必要とする場合も少なくない。従ってEMアルゴリ ズムをC言語で実装することで学習時間が大幅に減少する。例えば我々 は 3 状態、 2 出力記号をもつ HMM のプログラムにおいては約 180 倍の速度向上を確認している。

• trie 構造の採用：

  学習の第 1段階では :- bloodtype(b). を成功させるようなス イッチの組み合わせ(連言)を全解探索により求める。その探索結果は スイッチの連言の選言、すなわちDNFである。この DNFを compile し たもの(EM表と呼ぶ)をEMアルゴリズムの入力に与え、EMアルゴリズム を動作させる。EM表自体はコンパクトであるが、スイッチの組み合わ せが10,000 を越えるような大きな問題では DNFを求める段階でDNFサ イズの爆発によるメモリ不足に陥ってしまう。これを回避するために DNFの格納方式として trie 構造を採用した。trie 構造は全解探索時 の計算パスを反映しており、効率的なデータ圧縮が期待できる。

  例えば図 1 は血液型遺伝子プログラム （ bsw バージョン）において :- bloodtype(b) を成功 させるようなスイッチのDNFを trie 構造で格納したものである。 構造体1個が bsw に対応している（ f, m は father, mother の略）。 この場合はおよそ 8/12 にデータ圧縮できている． より大規模なプログラムでは圧縮効果はより顕著になる．

    
  図 1: 血液型遺伝子プログラムのDNFの trie 構造
  

• GUIの作成：

  ユーザが端末からマウスのクリックで簡便に PRISMのファイル を操作したり、また学習の様子を グラフにより参照したり出来るよう、 GUI機能を PRISMに付加した。

• 組み込み述語の追加：

  現在、学習用／実行用／その他合わせて30程の機能の各々に 組み込み述語を設け、ユーザの多様なプログラミングを支援 するようにした。それに伴い、50ページ程のユーザマニュアル （プログラミングガイドを含む）を新たに書き直した。