(57)【要約】【課題】観測情報が有する階層構造を考慮して観測情報の潜在構造を抽出するための確率モデルを生成する。【解決手段】初期モデル生成部３１が、階層構造を有する観測情報と階層構造を表現する順序木とを入力として、モデルパラメータと構造パラメータとを含む確率モデルを、複数生成して、初期モデル候補集合とする。モデルスコア計算部３２が、生成された初期モデル候補集合又は前回生成されたモデル候補集合に含まれる確率モデルの各々について、モデルスコアを算する。確率モデル候補生成部３４が、モデルスコアが上位ｗ個の確率モデルを抽出し、構造パラメータの何れか１つの階層の依存関係を変化させた確率モデルを生成して、モデル候補集合を生成する。反復判定部３３が、反復終了条件を満たすまで、確率モデル候補生成部３４及びモデルスコア計算部３２を繰り返し、モデルスコアが最も高い確率モデルを出力する。【選択図】図１
2015207197.tif 000002
【特許請求の範囲】
【請求項１】
階層構造を有する観測情報と前記観測情報の階層構造を表現する順序木とを入力として、前記入力された順序木の各節点に対応する、観測変数及び潜在変数を決定するためのモデルパラメータと、各階層について、前記階層の節点に対応する前記潜在変数の、親節点及び兄節点のそれぞれに対応する潜在変数との依存関係を調整するための構造パラメータと、を含む確率モデルを、前記構造パラメータの初期値を用いて、予め定められた方法により複数生成して、初期モデル候補集合とする初期モデル生成部と、
前記生成された初期モデル候補集合又は前回生成されたモデル候補集合に含まれる確率モデルの各々について、前記確率モデルが、前記入力された観測情報と合致する度合いを示すモデルスコアを算出して、スコア集合を生成するモデルスコア計算部と、
前記生成されたスコア集合に基づいて、前記生成された初期モデル候補集合又は前回生成されたモデル候補集合から、前記モデルスコアが上位ｗ個の確率モデルを抽出し、前記抽出された上位ｗ個の確率モデルの各々に対して、前記確率モデルの前記構造パラメータの何れか１つの階層の依存関係を変化させた確率モデルを生成して、モデル候補集合を生成する確率モデル候補生成部と、
前記モデルスコアに関して予め定められた反復終了条件を満たすまで、前記確率モデル候補生成部による前記モデル候補集合の生成、及び前記モデルスコア計算部による前記スコア集合の生成を繰り返し、繰り返しを終了したときに、前記モデルスコアが最も高い確率モデルを出力する反復判定部と、
を含む確率モデル生成装置。
【請求項２】
前記モデルスコアは、対数周辺尤度の下限値である変分自由エネルギーであって、
前記モデルスコア計算部は、
各節点ｎについて、前記順序木の頂点の節点から順番に、前記潜在変数の値ｋ毎に、前記節点ｎの潜在変数ｚnの値がｋであるときの、前記節点ｎの子孫の節点の集合Ｉ（ｎ）の観測変数ｘI(n)の確率Ｉn[ｋ]を計算すると共に、前記潜在変数の値ｋ、親節点の潜在変数の値ｉ、及び兄節点の潜在変数の値ｊの組み合わせ毎に、前記節点ｎの潜在変数ｚnの値、前記節点ｎの親節点ｌの潜在変数ｚlの値、及び兄節点ｍの潜在変数ｚmの値が、前記組み合わせであるときの、前記節点ｎの弟節点の集合に含まれる各節点の子孫の節点の和集合Ｂ（ｎ）の観測変数ｘB(n)の確率Bn[i,j,ｋ]を計算し、
各節点ｎについて、前記順序木の葉の節点から順番に、前記潜在変数の値ｋ、及び親節点の潜在変数の値ｉの組み合わせ毎に、前記節点ｎの確率Ｉn[ｋ]に基づいて、節点ｎの潜在変数ｚnの値、及び親節点ｌの潜在変数ｚlの値が前記組み合わせであるときの、前記節点ｎの兄節点の集合に含まれる各節点の子孫の節点の和集合F（ｎ）の観測変数ｘF(n)の確率Fn[i,ｋ]を計算すると共に、前記潜在変数の値ｋ、親節点の潜在変数の値ｉ、及び兄節点の潜在変数の値ｊの組み合わせ毎に、前記節点ｎの弟節点ｔの確率Bt[i,j,ｋ]に基づいて、前記節点ｎの潜在変数ｚnの値、前記節点ｎの親節点ｌの潜在変数ｚlの値、及び兄節点ｍの潜在変数ｚmの値が、前記組み合わせであるときの、前記節点ｎの子孫の節点を除いた節点の集合Ｏ（ｎ）の観測変数ｘO(n)の確率On[i,j,ｋ]を計算し、
各節点ｎについて、前記潜在変数の値ｋ、親節点の潜在変数の値ｉ、及び兄節点の潜在変数の値ｊの組み合わせ毎に、前記節点ｎの親節点ｐの確率On[i,j,ｋ]、前記節点ｎの兄節点ｓの確率Fn[i,ｋ]、及び前記節点ｎの確率Bn[i,j,ｋ]に基づいて、前記節点ｎの潜在変数の値、親節点ｌの潜在変数zlの値、及び兄節点ｍの潜在変数ｚmの値が前記組み合わせとなる確率ｐn,i,j,kを算出し、
各階層ｄについて、前記潜在変数の値ｋ、親節点の潜在変数の値ｉ、及び兄節点の潜在変数の値ｊの組み合わせ毎に、潜在変数ｚの集合の近似分布ｑ（ｚ）における、前記組み合わせの出現頻度の期待値Ｅq(z)[ｃd,i,j,k（ｚ）]を算出し、
各階層ｄについて、潜在変数の値ｋ、及び観測変数の値ｖの組み合わせ毎に、潜在変数ｚの集合の近似分布ｑ（ｚ）における、前記組み合わせの出現頻度の期待値Ｅq(z)[ｃd,k,v（ｚ）]を算出し、
各階層ｄについて、潜在変数の値ｋ、親節点の潜在変数の値ｉ、及び兄節点の潜在変数の値ｊの組み合わせ毎に、前記組み合わせに対する期待値Ｅq(z)[ｃd,i,j,k（ｚ）]及びモデルパラメータαd,kに基づいて、前記組み合わせに対する近似分布のパラメータａd,i,j,kを更新し、
各階層ｄについて、潜在変数の値ｋ、及び観測変数の値ｖの組み合わせ毎に、前記組み合わせに対する期待値Ｅq(z)[ｃd,k,v（ｚ）]及びモデルパラメータβd,vに基づいて、前記組み合わせに対する近似分布のパラメータｂd,k,vを更新し、
前記更新された近似分布のパラメータａd,i,j,k、ｂd,k,vに基づいて、前記モデルパラメータαd,k、βd,vを更新することを、前記近似分布のパラメータａd,i,j,k、ｂd,k,vが収束するまで繰り返す学習部と、
前記学習部によって最終的に更新された近似分布のパラメータａd,i,j,k、ｂd,k,vに基づいて、前記モデルパラメータαd,k、βd,vに基づいて、変分自由エネルギーであるモデルスコアを計算する計算部と、
を含む請求項１記載の確率モデル生成装置。
【請求項３】
初期モデル生成部が、階層構造を有する観測情報と前記観測情報の階層構造を表現する順序木とを入力として、前記入力された順序木の各節点に対応する、観測変数及び潜在変数を決定するためのモデルパラメータと、各階層について、前記階層の節点に対応する前記潜在変数の、親節点及び兄節点のそれぞれに対応する潜在変数との依存関係を調整するための構造パラメータと、を含む確率モデルを、前記構造パラメータの初期値を用いて、予め定められた方法により複数生成して、初期モデル候補集合とし、
モデルスコア計算部が、前記生成された初期モデル候補集合又は前回生成されたモデル候補集合に含まれる確率モデルの各々について、前記確率モデルが、前記入力された観測情報と合致する度合いを示すモデルスコアを算出して、スコア集合を生成し、
確率モデル候補生成部が、前記生成されたスコア集合に基づいて、前記生成された初期モデル候補集合又は前回生成されたモデル候補集合から、前記モデルスコアが上位ｗ個の確率モデルを抽出し、前記抽出された上位ｗ個の確率モデルの各々に対して、前記確率モデルの前記構造パラメータの何れか１つの階層の依存関係を変化させた確率モデルを生成して、モデル候補集合を生成し、
反復判定部が、前記モデルスコアに関して予め定められた反復終了条件を満たすまで、前記確率モデル候補生成部による前記モデル候補集合の生成、及び前記モデルスコア計算部による前記スコア集合の生成を繰り返し、繰り返しを終了したときに、前記モデルスコアが最も高い確率モデルを出力する
確率モデル生成方法。
【請求項４】
請求項１又は２に記載の確率モデル生成装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、確率モデル生成装置、方法、及びプログラムに係り、特に、階層構造を有する観測情報の潜在構造を抽出するための確率モデルを生成する確率モデル生成装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
大量のデータが与えられたとき、これらを分析する方法として、しばし潜在変数モデルが利用される。潜在変数モデルは観測データを表現する観測変数とは別に、データの持つ潜在的な構造を表現する潜在変数を含むモデルである。潜在変数モデルを用いてデータの潜在構造を抽出することはデータを分析するために非常に重要である。例えば文書データが大量に与えられたとき、これらをいくつかの類似した文書グループに分けることはデータの特徴を掴むために有用である。このタスクはクラスタリングと呼ばれ、潜在変数は各文書が所属するグループを表現する。また各文書を特徴付けるため、特徴的な文の構成パターンを潜在構造として取り出すことも可能である。
【０００３】
潜在変数モデルによる潜在構造の抽出は、モデルの持つパラメータを与えられたデータに合うようにフィッティング（学習）することで達成される。得られる潜在構造は用意したモデルに強く依存するが、与えられたデータを解析するために適したモデルを構築することは容易ではない。なぜならどのような潜在変数を用意し、それらの間にどのような依存関係を仮定するかは自明ではない。またモデルを設計しても、それを効率的に学習できなければ、データの分析は行えない。そのため、モデルの設計はデータに関するドメイン知識とモデル学習に関する専門知識の双方を必要とする困難な作業といえる。
【０００４】
このモデルの設計作業を自動化するため、データからのモデルの自動生成法が提案されている（例えば、非特許文献１）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｒｏｇｅｒ  Ｇｒｏｓｓｅ  ａｎｄ  ＲＲ  Ｓａｌａｋｈｕｔｄｉｎｏｖ．  “Ｅｘｐｌｏｉｔｉｎｇ  ｃｏｍｐｏｓｉｔｉｏｎａｌｉｔｙ  ｔｏ  ｅｘｐｌｏｒｅ  ａ  ｌａｒｇｅ  ｓｐａｃｅ  ｏｆ  ｍｏｄｅｌ  ｓｔｒｕｃｔｕｒｅｓ．”  Ｉｎ  ＵＡＩ，  ２０１２．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記非特許文献１などの既存の方法は、データの持つ階層情報を利用できていない。例えば、文書データは、章、節、文、単語のように複数の異なる粒度のデータの集合である。また、購買データは、複数のユーザの購買履歴の集合であり、ユーザの購買履歴は複数の購買イベントの系列、購買イベントは商品の集合、各商品は値段や量などの特徴の集合で表現される。これ以外にも音声、動画、ライフログなどのデータも階層情報を持つ。階層情報はデータの重要な性質であり、これを利用することでよりデータを解析するのに適したモデルが生成できると期待される。
【０００７】
本発明は、上記の事情を鑑みてなされたもので、観測情報が有する階層構造を考慮して観測情報の潜在構造を抽出するための確率モデルを生成することができる確率モデル生成装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の目的を達成するために本発明に係る確率モデル生成装置は、階層構造を有する観測情報と前記観測情報の階層構造を表現する順序木とを入力として、前記入力された順序木の各節点に対応する、観測変数及び潜在変数を決定するためのモデルパラメータと、各階層について、前記階層の節点に対応する前記潜在変数の、親節点及び兄節点のそれぞれに対応する潜在変数との依存関係を調整するための構造パラメータと、を含む確率モデルを、前記構造パラメータの初期値を用いて、予め定められた方法により複数生成して、初期モデル候補集合とする初期モデル生成部と、前記生成された初期モデル候補集合又は前回生成されたモデル候補集合に含まれる確率モデルの各々について、前記確率モデルが、前記入力された観測情報と合致する度合いを示すモデルスコアを算出して、スコア集合を生成するモデルスコア計算部と、前記生成されたスコア集合に基づいて、前記生成された初期モデル候補集合又は前回生成されたモデル候補集合から、前記モデルスコアが上位ｗ個の確率モデルを抽出し、前記抽出された上位ｗ個の確率モデルの各々に対して、前記確率モデルの前記構造パラメータの何れか１つの階層の依存関係を変化させた確率モデルを生成して、モデル候補集合を生成する確率モデル候補生成部と、前記モデルスコアに関して予め定められた反復終了条件を満たすまで、前記確率モデル候補生成部による前記モデル候補集合の生成、及び前記モデルスコア計算部による前記スコア集合の生成を繰り返し、繰り返しを終了したときに、前記モデルスコアが最も高い確率モデルを出力する反復判定部と、を含んで構成されている。
【０００９】
本発明に係る確率モデル生成方法は、初期モデル生成部が、階層構造を有する観測情報と前記観測情報の階層構造を表現する順序木とを入力として、前記入力された順序木の各節点に対応する、観測変数及び潜在変数を決定するためのモデルパラメータと、各階層について、前記階層の節点に対応する前記潜在変数の、親節点及び兄節点のそれぞれに対応する潜在変数との依存関係を調整するための構造パラメータと、を含む確率モデルを、前記構造パラメータの初期値を用いて、予め定められた方法により複数生成して、初期モデル候補集合とし、モデルスコア計算部が、前記生成された初期モデル候補集合又は前回生成されたモデル候補集合に含まれる確率モデルの各々について、前記確率モデルが、前記入力された観測情報と合致する度合いを示すモデルスコアを算出して、スコア集合を生成し、確率モデル候補生成部が、前記生成されたスコア集合に基づいて、前記生成された初期モデル候補集合又は前回生成されたモデル候補集合から、前記モデルスコアが上位ｗ個の確率モデルを抽出し、前記抽出された上位ｗ個の確率モデルの各々に対して、前記確率モデルの前記構造パラメータの何れか１つの階層の依存関係を変化させた確率モデルを生成して、モデル候補集合を生成し、反復判定部が、前記モデルスコアに関して予め定められた反復終了条件を満たすまで、前記確率モデル候補生成部による前記モデル候補集合の生成、及び前記モデルスコア計算部による前記スコア集合の生成を繰り返し、繰り返しを終了したときに、前記モデルスコアが最も高い確率モデルを出力する。
【００１０】
本発明に係るプログラムは、上記の確率モデル生成装置の各部としてコンピュータを機能させるためのプログラムである。
【発明の効果】
【００１１】
以上説明したように、本発明の確率モデル生成装置、方法、及びプログラムによれば、観測情報の階層構造を表現する順序木の各節点に対応する、観測変数及び潜在変数を決定するためのモデルパラメータと、各階層について、親節点及び兄節点のそれぞれに対応する潜在変数との依存関係を調整するための構造パラメータと、を含む確率モデルの各々について、モデルスコアを算出してスコア集合を生成し、スコア集合に基づいて、確率モデルのモデル候補集合を生成することを繰り返すことにより、観測情報が有する階層構造を考慮して観測情報の潜在構造を抽出するための確率モデルを生成することができる、という効果が得られる。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施の形態に係る確率モデル生成装置の構成を示す概略図である。
【図２】構造パラメータを説明するための図である。
【図３】本発明の実施の形態に係る確率モデル生成装置のモデル候補生成部の構成を示す概略図である。
【図４】本発明の実施の形態に係る確率モデル生成装置のモデルスコア計算部の構成を示す概略図である。
【図５】モデルスコアを計算するアルゴリズムを示す図である。
【図６】本発明の実施の形態に係る確率モデル生成装置における確率モデル生成処理ルーチンの内容を示すフローチャートである。
【図７】本発明の実施の形態に係る確率モデル生成装置におけるモデルスコア計算処理ルーチンの内容を示すフローチャートである。
【図８】本発明の実施の形態に係る確率モデル生成装置におけるモデル候補生成処理ルーチンの内容を示すフローチャートである。
【図９】実験のデータセットを示す図である。
【図１０】実験結果を示す図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１４】
＜概要＞
まず、本発明の実施の形態の概要について説明する。
【００１５】
本発明の実施の形態では、階層情報を有する観測情報からのモデルの自動生成を実現する。これにより本来専門知識を必要とするモデルの設計を簡易化し、データの解析をより容易にする。本発明の実施の形態の特徴として階層情報を利用することが挙げられる。階層情報を利用することは以下の（１）〜（３）の利点を持つ。
【００１６】
（１）モデルの生成および潜在構造の抽出に利用できる情報が増加し、よりデータに適したモデルの生成、解析が可能になる。
【００１７】
（２）モデル中の潜在変数とデータの階層情報を結びつけることができるため、モデルやモデルより得られた潜在構造を解釈しやすい。
【００１８】
（３）階層情報として解析者が期待する構造を埋め込むことで、解析用途に適したモデルを生成できる。
【００１９】
しかし、階層情報を導入することで，生成されるモデルが複雑化し、それらを利用する際に効率的に学習ができなくなるという懸念がある。そこで本発明の実施の形態では、効率的な学習法を伴うモデルの自動生成を実現する。
【００２０】
＜システム構成＞
次に、階層構造を有する観測情報を解析して、観測情報の潜在構造を抽出するための確率モデルを生成する確率モデル生成装置に、本発明を適用した場合を例にして、本発明の実施の形態を説明する。
【００２１】
図１に示すように、本発明の実施の形態に係る確率モデル生成装置は、ＣＰＵと、ＲＡＭと、後述する確率モデル生成処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。
【００２２】
図１に示すように、確率モデル生成装置１００は、入力部１、記憶部２、演算部３、及び出力部４を備えている。演算部３は、初期モデル生成部３１、モデルスコア計算部３２、反復判定部３３、及びモデル候補生成部３４を備えている。
【００２３】
入力部１は、階層構造を有する観測情報の入力を受け付ける。出力部４は、観測情報の潜在構造を抽出するための確率モデルを出力する。
【００２４】
演算部３は、まず、入力データとして観測情報と階層情報を読み込む。
【００２５】
次に、演算部３は、以下の手順を、反復終了条件を満たすまで繰り返す。まず、モデル候補生成部３４において、入力情報と現在時点でのモデル候補集合およびスコア集合を元に新たな確率モデルの候補集合を生成する。次に、生成されたモデル候補集合を入力とし、モデルスコア計算部３２において、各モデル候補がどれだけ入力された観測情報に合っているかを示すモデルスコアを計算する。反復判定部３３は、反復終了条件として、モデルスコアが改善されたか否かを判定し、モデルスコアが改善されれば、モデル候補生成部３４に戻り、新たなモデル候補を生成する。モデルスコアの改善がなくなれば、最もモデルスコアの高いモデル候補を最終モデルとして出力部４により出力する。このモデルスコアの計算はデータにモデルをフィットさせることで計算される。つまりモデルスコアを効率的に計算するためには、モデルの学習を効率的に行う必要がある。
【００２６】
既存の確率モデルの自動生成装置も同様の構造を持つ場合があるが、本発明の実施の形態では、入力として、観測情報の持つ階層構造を受け取り、これを活用し確率モデルを生成する点が異なる。以下に具体的に階層情報がどのように利用されるかを述べる。
【００２７】
入力部１で受け付ける入力は、観測列である観測情報ｘ＝｛ｘ１，．．．，ｘＮ｝と階層構造を表現した順序木Ｔとする。観測変数ｘｎは順序木Ｔ中の節点ｎに対応付けられているため、順序木Ｔの構造が観測情報ｘの持つ階層構造を表す。ここでは説明のため、順序木Ｔを３つ組（Ｎ；ｐａｒ；ｓｉｂ）で定義する。Ｎ＝｛０，．．．，Ｎ｝はＴ中の節点集合であり、写像ｐａｒ：Ｎ→Ｎとｓｉｂ：Ｎ→ＮはそれぞれＴ中の親子関係および順序関係を表す。つまりｐａｒ（ｎ）はｎの親であり、ｓｉｂ（ｎ）はｎの兄である。ＤとＤｎをそれぞれＴの深さ、節点ｎの深さとする。またＮｄ（１≦ｄ≦Ｄ）をｄｎ＝ｄなる節点ｎの集合とする。以後説明のため、ｘｎ（ｎ∈ｄｎ）は離散値１，．．．，Ｖｄを取るとする。
【００２８】
出力部４の出力は、確率モデルＭである。確率モデルは確率変数間の依存関係を定めたものであり、本実施の形態で扱うモデルは観測変数ｘとは別に、潜在変数ｚ＝（ｚｎ）Ｎｎ＝１を持つとする。つまり、ある具体的なモデルＭはｘとｚ間の依存関係を定めたものである。ここでは説明のため、モデルＭは順序木Ｔ、構造パラメータＡ，モデルパラメータα＝（αｄ）ｄ＝１Ｄ，β（βｄ）ｄ＝１Ｄによって定義されるとする。順序木Ｔ中の各節点ｎ∈Ｎｄ（１≦ｄ≦Ｄ）は離散潜在変数ｚｎ∈｛１，．．．Ｋ｝を持ち、各観測変数ｘｎは対応する潜在変数ｚｎにのみ依存し、ｚｎはその親節点の潜在変数ｚｐａｒ（ｎ）と兄節点の潜在変数ｚｓｉｂ（ｎ）に依存する。以後、簡単のためｌ＝ｐａｒ（ｎ）、ｍ＝ｓｉｂ（ｎ）とする。ただし、この親節点及び兄節点の潜在変数との間の依存関係は構造パラメータＡ≡（Ａｄ）Ｄｄ＝１により調整可能であるとする。Ａの各要素Ａｄを仮説変数と呼び、図２に仮説変数Ａｄが表す依存関係を示す。Ｉ−ｄｅｔはｚｎが値ｎを決定的にとることを意味し、Ｐ−ｄｅｔはｚｎが親の値ｚｌを決定的に取ることを意味する。Ｎ−ｄｅｐはｚｎが他の潜在変数と独立である事を意味する。Ｐ−ｄｅｐ，Ｓ−ｄｅｐ，Ｂ−ｄｅｐはそれぞれ、ｚｎが親ｚｌ，兄ｚｍそしてその両方に依存することを意味する。なお節点ｎが親節点や兄節点を持たないとき、これをｌ＝０、ｍ＝０と表す。また、ｚ０＝０とする。この構造パラメータＡを調整することで、様々な潜在変数モデルを表現できる。例えば、クラスタリングに利用される混合モデル、文書データの解析に広く利用されている潜在ディリクレ配分（ＬＤＡ）モデル、系列データの解析に利用される隠れマルコフモデル、そしてそれらを組み合わせたモデルが表現できる。
【００２９】
モデルパラメータαｄ≡（αｄ、ｋ）Ｋｄｋ＝１とβｄ≡（βｄ，ｖ）Ｖｄｖ＝１をＤｉｒｉｃｈｌｅｔ分布のパラメータとし、θｄ，ｉ，ｊとφｄ，ｋはそれぞれカテゴリカル分布のパラメータとする。ここでθｄ，ｉ，ｊはｚｌ＝ｉかつｚｍ＝ｊのときにｚｎ（ｎ∈Ｎｄ）の値を決定するためのカテゴリカル分布のパラメータであり、φｄ，ｋはｚｎ＝ｋのときにｘｎの値を決定するためのカテゴリカル分布のパラメータである。そしてαｄとβｄはそれぞれθｄ，ｉ，ｊとφｄ，ｋを生成するためのディリクレ分布のパラメータとする。このとき潜在変数ｚ＝（ｚｎ）Ｎｎ＝１と観測変数ｘ＝（ｘｎ）Ｎｎ＝１の生成過程は、以下の１〜２で表わされる。
【００３０】
１．  Ｆｏｒ  ｅａｃｈ  ｄｅｐｔｈ  ｄ＝１，．．．，Ｄ
（ａ）  Ｄｒａｗ  ｔｏｐｉｃ  ｄｉｓｔｒｉｂｕｔｉｏｎｓ  θｄ，ｉ，ｊ〜Ｄｉｒ（αｄ）
（ｂ）  Ｄｒａｗ  ｓｙｍｂｏｌ  ｄｉｓｔｒｉｂｕｔｉｏｎｓ  φｄ，ｋ〜Ｄｉｒ（βｄ）
２．  Ｆｏｒ  ｅａｃｈ  ｄｅｐｔｈ  ｄ＝１，．．．,Ｄ，  ｆｏｒ  ｅａｃｈ  ｎｏｄｅ  ｎ∈Ｎｄ
（ａ）  Ｃｈｏｏｓｅ  ａ  ｔｏｐｉｃ  ｚｎ  ｂｙ
ｃａｓｅ  Ａｄ
ｗｈｅｎ  Ｉ−ｄｅｔ  ：  ｚｎ：＝ｎ
ｗｈｅｎ  Ｐ−ｄｅｔ  ：  ｚｎ：＝ｚｌ
ｗｈｅｎ  Ｎ−ｄｅｐ  ：  ｚｎ〜Ｃａｔ（θｄ，０，０）
ｗｈｅｎ  Ｐ−ｄｅｐ  ：  ｚｎ〜Ｃａｔ（θｄ，ｚｌ，０）
ｗｈｅｎ  Ｓ−ｄｅｐ  ：  ｚｎ〜Ｃａｔ（θｄ，０，ｚｍ）
ｗｈｅｎ  Ｂ−ｄｅｐ  ：  ｚｎ〜Ｃａｔ（θｄ，ｚｌ，ｚｍ）
（ｂ）  Ｄｒａｗ  ａ  ｓｙｍｂｏｌ  ｘｎ〜Ｃａｔ（φｄ，ｚｎ）
【００３１】
初期モデル生成部３１は、入力部１により入力された、観測情報の階層構造を表現する順序木Ｔに基づいて、入力された順序木の各節点に対応する、観測変数及び潜在変数を決定するためのモデルパラメータα、βと、各階層について、階層の節点に対応する潜在変数の、親節点及び兄節点のそれぞれに対応する潜在変数との依存関係を調整するための構造パラメータＡと、順序木Ｔとの４つ組（Ｔ，Ａ，α，β）で表現される確率モデルＭを、構造パラメータＡの初期値を用いて、予め定められた方法により複数生成して、初期モデル候補集合とする。例えば、初期のモデル候補の各々における構造パラメータＡの初期値をランダムに決定してもよいし、既存のよく知られたモデルを表現した構造パラメータＡを初期値として与えてもよい。
【００３２】
モデル候補生成部３４は、図３に示すように、モデル候補読込部３４１及び新モデル候補計算部３４２を備えている。モデル候補生成部３４の入力は、記憶部２に記憶されている現在のモデル候補集合Ｃと、モデル候補集合Ｃに対するスコア集合Ｓとであり、出力は新たなモデル候補集合Ｃ’である。
【００３３】
モデル候補読込部３４１は、記憶部２に記憶されているモデル候補集合Ｃと、モデル候補集合Ｃに対するスコア集合Ｓとを読み込む。
【００３４】
新モデル候補計算部３４２は、モデル候補読込部３４１によって読み込んだモデル候補集合Ｃ及びスコア集合Ｃに基づいて、モデル候補集合Ｃより、スコア集合Ｓ内でモデルスコアが上位ｗ個の確率モデルを抽出する。新モデル候補計算部３４２は、ｗ個の各確率モデルに対して、隣接モデルを計算する。新モデル候補計算部３４２は、計算されたすべての隣接モデルの集合を新たなモデル候補集合Ｃ’として、記憶部２に格納する。ここで、確率モデルＭの隣接モデルとは、確率モデルＭ内の構造パラメータＡの何れか１つの階層の依存関係を表す要素を変化させたものである。本実施の形態では、確率モデルＭが４つ組（Ｔ，Ａ，α，β）で表現されるため、隣接モデルは構造パラメータＡの要素を丁度１箇所変更させたものである。
【００３５】
モデルスコア計算部３２は、図４に示すように、モデル候補読込部３２１、学習部３２２、及び計算部３２３を備えている。モデルスコア計算部３２の入力は、初期モデル候補集合、又は記憶部２に記憶されているモデル候補集合Ｃであり、出力は、確率モデルＭが、入力された観測情報と合致する度合いを示すモデルスコアのスコア集合Ｓである。
【００３６】
モデル候補読込部３４１は、初期モデル候補集合、又は記憶部２に記憶されているモデル候補集合Ｃを読み込む。
【００３７】
以下に、モデル候補集合Ｃ中の各モデルＭに対してモデルスコアを計算する方法について説明する。
【００３８】
モデルスコアは、モデルＭが、入力された観測情報ｘにどれだけ合っているかを表すものであり、代表例として対数周辺尤度Ｌ［Ｍ］≡ｐ（ｘ｜M)などが挙げられる。モデルスコアはモデルを比較することができればどのようなものを選んでも良いが、本実施の形態では対数周辺尤度Ｌ［Ｍ］の下限値である変分自由エネルギーＦ［Ｍ］を利用する。なお、モデルパラメータαとβは、学習部３２２において観測情報ｘに合うように学習される。Ｊｅｎｓｅｎ’ｓ  ｉｎｅｑｕａｌｉｔｙを利用することで、以下の対数尤度Ｌ［Ｍ］の下限値を得る。
【００３９】
【数１】
2015207197.tif 000003
【００４０】
ここでｑはｑ（ｚ，θ，φ）＝ｑ（ｚ）ｑ（φ）ｑ（φ）を満たす近似分布であり、Ｈ［ｑ］はそのエントロピーである。Ｅｕｌｅｒ−Ｌａｇｒａｎｇｅ  ｅｑｕａｔｉｏｎより、以下のｑに関する更新式を得る。
【００４１】
【数２】
2015207197.tif 000004
【００４２】
この更新式を繰り返し適用することでＦ［ｑ，Ｍ］を極大化することができる。更にモデルパラメータαとβは不動点反復法により推定できる。極大化された値をＦ［Ｍ］と書き、変分自由エネルギーと呼ぶ。
【００４３】
次にＦ［Ｍ］を効率的に計算する方法を述べる。ｑ（θ）とｑ（φ）に対して以下を仮定する。
【００４４】
【数３】
2015207197.tif 000005
【００４５】
ここでａｄ，ｉ，ｊ＝（ａｄ，ｉ，ｊ，ｋ）Ｋｄｋ＝１とｂｄ，ｋ＝（ｂｄ，ｋ，ｖ）Ｖｄｖ＝１は近似分布ｑのパラメータであり、更新式は以下で与えられる。
【００４６】
【数４】
2015207197.tif 000006
【００４７】
ここでｑ（ｚ）は以下である。
【００４８】
【数５】
2015207197.tif 000007
【００４９】
ここでΨ（ｘ）はディガンマ関数である。ｑ（ｚ）＝ｐ（ｚ｜ｘ，θ＊，φ＊）が成り立つため、（７）式、（８）式中の期待値は以下のように計算できる。
【００５０】
【数６】
2015207197.tif 000008
【００５１】
つまり近似分布ｑのパラメータａ，ｂは、（１４）式、（１５）式の期待値計算と、（７）式、（８）式の更新式の計算とを繰り返すことで推定できる。実際に期待値を計算するにはｐｎ，ｉ，ｊ，ｋを計算する必要がある。確率ｐｎ，ｉ，ｊ，ｋは、ｒｎ，ｉ，ｊ，ｋ≡ｐ（ｚｌ＝ｉ，ｚｍ＝ｊ，ｚｎ＝ｋ，ｘ｜θ＊，φ＊）を計算することで、以下のように計算できる。
【００５２】
【数７】
2015207197.tif 000009
【００５３】
最後にｒｎ，ｉ，ｊ，ｋの計算法を述べる。概略を述べると、ｒｎ，ｉ，ｊ，ｋを計算する際に、順序木Ｔ中の全節点Ｎを今注目しているｎを中心にその上にある集合、下にある集合、前にある集合、後ろにある集合の４つに分け、各集合毎の確率を計算・統合することで、効率よくｒｎ，ｉ，ｊ，ｋが計算できる。
【００５４】
以後簡単のため、θとφを省略し、具体的な計算法を述べる。順序木Ｔにおける節点ｎの子孫の節点の集合をＤｅｃ（ｎ）とし、Ｓｉｂ−（ｎ）をｎの兄節点の集合、Ｓｉｂ＋（ｎ）をｎの弟節点の集合とする。このとき以下の４種の集合を導入する。
【００５５】
【数８】
2015207197.tif 000010
【００５６】
これらの集合を利用してＮ＝Ｏ（ｐ）∪Ｆ（ｓ）∪Ｂ（ｎ）と書ける。ある集合Ｃ⊆Ｎに対してｘＣ≡（ｘｎ）ｎ∈ＣかつｚＣ≡（ｚｎ）ｎ∈Ｃと定める。すると計算したい値ｒｎ，ｉ，ｊ，ｋは以下のように分解できる。
【００５７】
【数９】
2015207197.tif 000011
【００５８】
上記を計算するため、以下の４種類の確率を導入する。
【００５９】
【数１０】
2015207197.tif 000012
【００６０】
これらの確率は互いを用いて以下のような動的計画法で計算できる。
【００６１】
【数１１】
2015207197.tif 000013
【００６２】
ここでｃはｎの長子であり、ｔはｎの弟である。また、φd,k,xn、θd,i,j,kは、上記（１２）、（１３）式に従って計算される。上記の確率を用いれば、ｒｎ，ｉ，ｊ，ｋは以下のように計算できる。
【００６３】
【数１２】
2015207197.tif 000014
【００６４】
まとめると、確率モデルＭについてのモデルスコアＦ［Ｍ］は、図５に示すアルゴリズムにより計算される。
【００６５】
本実施の形態では、学習部３２２によって、モデル候補読込部３４１により読み込んだ、初期モデル候補集合、又は記憶部２に記憶されているモデル候補集合Ｃの確率モデルＭの各々について、以下に説明するように、モデルパラメータα、β及び近似分布のパラメータａ、ｂを学習する。
【００６６】
まず、学習部３２２は、確率モデルＭの順序木Ｔの各節点ｎについて、順序木の頂点の節点から順番に、潜在変数の値ｋ毎に、上記（２８）式に従って、当該節点ｎの潜在変数ｚnの値がｋであるときの、当該節点ｎの子孫の節点の集合Ｉ（ｎ）の観測変数ｘI(n)の確率Ｉn[ｋ]を計算すると共に、潜在変数の値ｋ、親節点の潜在変数の値ｉ、及び兄節点の潜在変数の値ｊの組み合わせ毎に、上記（３３）式に従って、当該節点ｎの潜在変数ｚnの値、当該節点ｎの親節点ｌの潜在変数ｚlの値、及び兄節点ｍの潜在変数ｚmの値が、当該組み合わせであるときの節点ｎの弟の節点の集合に含まれる各節点の子孫の節点の和集合Ｂ（ｎ）の観測変数ｘB(n)の確率Bn[i,j,ｋ]を計算する。
【００６７】
また、学習部３２２は、確率モデルＭの順序木Ｔの各節点ｎについて、順序木の葉の節点から順番に、潜在変数の値ｋ、及び親節点の潜在変数の値ｉの組み合わせ毎に、上記（３１）式に従って、当該節点ｎの確率Ｉn[ｋ]に基づいて、節点ｎの潜在変数ｚnの値、及び親節点ｌの潜在変数ｚlの値が当該組み合わせであるときの節点ｎの兄節点の集合に含まれる各節点の子孫の節点の和集合F（ｎ）の観測変数ｘF(n)の確率Fn[i,ｋ]を計算すると共に、潜在変数の値ｋ、親節点の潜在変数の値ｉ、及び兄節点の潜在変数の値ｊの組み合わせ毎に、上記（３０）式に従って、節点ｎの弟節点ｔの確率Bt[i,j,ｋ]に基づいて、節点ｎの潜在変数ｚnの値、節点ｎの親節点ｌの潜在変数ｚlの値、及び兄節点ｍの潜在変数ｚmの値が、当該組み合わせであるときの、節点ｎの子孫の節点を除いた節点の集合Ｏ（ｎ）の観測変数ｘO(n)の確率On[i,j,ｋ]を計算する。
【００６８】
また、学習部３２２は、確率モデルＭの順序木Ｔの各節点ｎについて、潜在変数の値ｋ、親節点の潜在変数の値ｉ、及び兄節点の潜在変数の値ｊの組み合わせ毎に、上記（３４）式に従って、節点ｎの親節点ｐの確率On[i,j,ｋ]、節点ｎの兄節点ｓの確率Fn[i,ｋ]、及び節点ｎの確率Bn[i,j,ｋ]に基づいて、当該組み合わせに対するｒn,i,j,kを算出する。
【００６９】
また、学習部３２２は、確率モデルＭの順序木Ｔの各節点ｎについて、潜在変数の値ｋ、潜在変数の値ｋ、親節点の潜在変数の値ｉ、及び兄節点の潜在変数の値ｊの組み合わせ毎に、上記（１７）式、（１８）式に従って、算出された各ｒn,i,j,kに基づいて、節点ｎの潜在変数の値、親節点ｌの潜在変数zlの値、及び兄節点ｍの潜在変数ｚmの値が当該組み合わせとなる確率ｐn,i,j,kを算出する。
【００７０】
また、学習部３２２は、確率モデルＭの順序木Ｔの各階層ｄについて、上記（１４）式に従って、潜在変数の値ｋ、親節点の潜在変数の値ｉ、及び兄節点の潜在変数の値ｊの組み合わせ毎に、潜在変数ｚの集合の近似分布ｑ（ｚ）における、当該組み合わせの出現頻度の期待値Ｅq(z)[ｃd,i,j,k（ｚ）]を算出する。学習部３２２は、確率モデルＭの順序木Ｔの各階層ｄについて、潜在変数の値ｋ、及び観測変数の値ｖの組み合わせ毎に、上記（１５）式に従って、潜在変数ｚの集合の近似分布ｑ（ｚ）における、当該組み合わせの出現頻度の期待値Ｅq(z)[ｃd,k,v（ｚ）]を算出する。
【００７１】
また、学習部３２２は、確率モデルＭの順序木Ｔの各階層ｄについて、上記（７）式に従って、潜在変数の値ｋ、親節点の潜在変数の値ｉ、及び兄節点の潜在変数の値ｊの組み合わせ毎に、当該組み合わせに対する期待値Ｅq(z)[ｃd,i,j,k（ｚ）]及びモデルパラメータαd,kに基づいて、当該組み合わせに対する近似分布のパラメータａd,i,j,kを更新する。
【００７２】
また、学習部３２２は、確率モデルＭの順序木Ｔの各階層ｄについて、上記（８）式に従って、潜在変数の値ｋ、及び観測変数の値ｖの組み合わせ毎に、当該組み合わせに対する期待値Ｅq(z)[ｃd,k,v（ｚ）]及びモデルパラメータβd,vに基づいて、当該組み合わせに対する近似分布のパラメータｂd,k,vを更新する。
【００７３】
また、学習部３２２は、確率モデルＭの順序木Ｔの各階層ｄについて、更新された近似分布の各パラメータａd,i,j,k、ｂd,k,vに基づいて、潜在変数の値ｋ、親節点の潜在変数の値ｉ、及び兄節点の潜在変数の値ｊの組み合わせ毎のモデルパラメータαd,k、並びに潜在変数の値ｋ、及び観測変数の値ｖの組み合わせ毎のβd,vを更新する。
【００７４】
学習部３２２は、確率モデルＭについて、近似分布の各パラメータａd,i,j,k、ｂd,k,vが収束するまで、上記の処理を繰り返す。
【００７５】
計算部３２３は、モデル候補読込部３４１により読み込んだ、初期モデル候補集合、又は記憶部２に記憶されているモデル候補集合Ｃの確率モデルＭの各々について、上記（１）式に従って、学習部３２２によって最終的に更新された近似分布の各パラメータａd,i,j,k、ｂd,k,v、及び各モデルパラメータαd,k、βd,vに基づいて、変分自由エネルギーであるモデルスコアを計算し、スコア集合を生成して、記憶部２に格納する。
【００７６】
反復判定部３３は、モデルスコアに関して予め定められた反復終了条件を満たすまで、モデル候補生成部３４によるモデル候補集合の生成、及びモデルスコア計算部３２によるスコア集合の生成を繰り返し、繰り返しを終了したときに、モデルスコアが最も高い確率モデルを、出力部４により出力する。本実施の形態では、反復終了条件として、モデルスコアの改善がなくなったことを用いる。
【００７７】
＜確率モデル生成装置の作用＞
次に、本実施の形態に係る確率モデル生成装置１００の作用について説明する。階層構造を有する観測情報と、観測情報の階層構造を表す順序木とが、確率モデル生成装置１００に入力されると、図６に示す確率モデル生成処理ルーチンが実行される。
【００７８】
まず、ステップＳ１００において、入力された観測情報及び順序木を読み込む。ステップＳ１０２において、上記ステップＳ１００で読み込んだ順序木に基づいて、複数の確率モデルを生成し、初期モデル候補集合とする。
【００７９】
次のステップＳ１０４では、上記ステップＳ１０２で生成された初期モデル候補集合、又は後述するステップＳ１０８で前回生成されたモデル候補集合に対して、モデルスコアを計算して、スコア集合を生成する。
【００８０】
ステップＳ１０６では、上記ステップＳ１０４で生成されたスコア集合に基づいて、モデルスコアに関する反復終了条件を満たすか否かを判定する。反復終了条件を満たさない場合には、ステップＳ１０８へ移行する。
【００８１】
ステップＳ１０８では、上記ステップＳ１０２で生成された初期モデル候補集合、又はステップＳ１０８で前回生成されたモデル候補集合と、上記ステップ１０４で生成されたスコア集合に基づいて、新たなモデル候補集合を生成し、上記ステップＳ１０４へ戻る。
【００８２】
上記ステップＳ１０６において、反復終了条件を満たすと判定された場合には、ステップＳ１１０へ移行し、上記ステップＳ１０８で生成されたモデル候補集合のうち、モデルスコアが最も高い確率モデルを、出力部４により出力して、確率モデル生成処理ルーチンを終了する。
【００８３】
上記ステップＳ１０４は、図７に示すモデルスコア計算処理ルーチンにより実現される。
【００８４】
ステップＳ１２０において、上記ステップＳ１０２で生成された初期モデル候補集合、又はステップＳ１０８で前回生成されたモデル候補集合を読み込む。
【００８５】
次のステップＳ１２２では、上記ステップ１２０で読み込んだ初期モデル候補集合又はモデル候補集合に含まれる確率モデルの各々について、モデルパラメータα、β、及び近似分布のパラメータａ、ｂを学習する。
【００８６】
そして、ステップＳ１２４において、上記ステップ１２０で読み込んだ初期モデル候補集合又はモデル候補集合に含まれる確率モデルの各々について、上記ステップＳ１２２で学習された当該確率モデルのモデルパラメータα、β、及び近似分布のパラメータａ、ｂに基づいて、モデルスコアを計算し、計算されたモデルスコアの集合を、スコア集合として、記憶部２に格納して、モデルスコア計算処理ルーチンを終了する。
【００８７】
上記ステップＳ１０８は、図８に示すモデル候補生成処理ルーチンにより実現される。
【００８８】
ステップＳ１３０において、上記ステップＳ１０２で生成された初期モデル候補集合、又はステップＳ１０８で前回生成されたモデル候補集合と、上記ステップＳ１０４で生成されたスコア集合とを読み込む。
【００８９】
そして、ステップＳ１３２において、初期モデル候補集合又はモデル候補集合から、モデルスコアが上位ｗ個の確率モデルを抽出する。
【００９０】
ステップＳ１３４では、上記ステップＳ１３２で抽出されたｗ個の確率モデルの各々について、隣接モデルを計算する。
【００９１】
そして、ステップＳ１３６において、上記ステップＳ１３４で計算された全ての隣接モデルを、新たなモデル候補集合として、記憶部２に格納して、モデル候補生成処理ルーチンを終了する。
【００９２】
＜実験＞
本発明の実施の形態で説明した手法を評価するために、１２のデータセットを用いて実験を行った。各データセットは、図９に示される１２個のモデルから生成されたものであり、各データセットはＬ文書、各文書はＬ文、各文はＬ単語から成る。つまりデータセットは３層の階層情報を持つＬ３の単語からなる。上記図９においてＭＭはＭｕｌｔｉｎｏｍｉａｌ  ｍｉｘｔｕｒｅ、ＬＤＡはＬａｔｅｎｔ  ｄｉｒｉｃｈｌｅｔ  ａｌｌｏｃａｔｉｏｎ、ＨＭＭはｈｉｄｅｎ  Ｍａｒｋｏｖ  ｍｏｄｅｌの略であり、ｄ、ｓ、ｗはそれぞれ文書レベル、文レベル、単語レベルを意味する。各データセットは順序木で与えられる。順序木中で、各単語は自身が所属する文を親として持ち、各文は所属する文書を親として持つ。本発明の実施の形態ではこれを入力とし、確率モデルの自動生成を行う。本実験では、初期モデル候補ＭとしてＡ＝（Ｐ−ｄｅｔ，Ｐ−ｄｅｔ，Ｐ−ｄｅｔ）なるモデルを与えた。モデルスコア計算部３２においてモデル候補集合の確率モデルＭのモデルスコアを計算し、モデル候補生成部３４において得られたモデルスコアを元に新たなモデル候補集合を生成した。これをモデルスコアが改善されなくなるまで反復した。図１０に本実験により生成されたＡを示す。なおデータサイズＬとモデル候補生成部３４の探索幅ｗをそれぞれＬ＝１０，３０，５０、ｗ＝１，３と変化させた。上記図１０中の矩形で囲まれた部分は、正解モデルと異なる仮説が生成された事を意味する。上記図１０よりＬとｗを増加させるとより正しい確率モデルを生成され、最終的には全データセットに対して正しい確率モデルを生成できたことが分かる。
【００９３】
以上説明したように、本発明の実施の形態に係る確率モデル生成装置によれば、観測情報の階層構造を表現する順序木の各節点に対応する、観測変数及び潜在変数を決定するためのモデルパラメータα、βと、各階層について、親節点及び兄節点のそれぞれに対応する潜在変数との依存関係を調整するための構造パラメータＡと、を含む確率モデルＭの各々について、モデルスコアを算出してスコア集合を生成し、スコア集合に基づいて、確率モデルのモデル候補集合を生成することを繰り返すことにより、観測情報が有する階層構造を考慮して観測情報の潜在構造を抽出するための確率モデルを生成することができる。
【００９４】
また、解析対象の観測情報が持つ階層情報を有効利用した潜在変数モデルの自動生成が可能となる。階層構造を利用することにより、確率モデルに含まれる潜在変数がどの階層に対応するかが分かるため、モデルや得られた潜在構造を解釈しやすい。また生成されたモデルを用いて潜在構造を抽出するにはモデルを学習する必要があるが、この学習を、モデルスコア計算部に内蔵される手法により効率的に行うことができる。
【００９５】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００９６】
例えば、上述の確率モデル生成装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【００９７】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００９８】
１     入力部
２     記憶部
３     演算部
４     出力部
３１   初期モデル生成部
３２   モデルスコア計算部
３３   反復判定部
３４   モデル候補生成部
１００ 確率モデル生成装置
３２１ モデル候補読込部
３２２ 学習部
３２３ 計算部
３４１ モデル候補読込部
３４２ 新モデル候補計算部
【図１】
2015207197.tif 000015
【図３】
2015207197.tif 000016
【図４】
2015207197.tif 000017
【図６】
2015207197.tif 000018
【図７】
2015207197.tif 000019
【図８】
2015207197.tif 000020
【図１０】
2015207197.tif 000021
【図２】
2015207197.tif 000022
【図５】
2015207197.tif 000023
【図９】
2015207197.tif 000024