(57)【要約】【課題】系列データのクラスタリングを行う際に、クラスタ間の遷移における各クラスタの関係を同時に抽出する。【解決手段】パラメータ初期化部１２が、隠れマルコフモデルにおける状態間の遷移を、モンドリアン過程における領域分割で表した系列データの生成過程を示す生成モデルの事後確率分布を示す各パラメータであって、cost及び分割位置で構成されたモンドリアンΜ、モンドリアン過程の領域上における状態毎の位置Ｓ、及び隠れ状態の系列Ｚを含む各パラメータの初期値を設定し、サンプリング部１３が、入力された系列データ、及び各パラメータの初期値、または前回サンプリングした各パラメータの値を用いて、パラメータΜ、Ｓ、及びＺを含む各パラメータをサンプリングし、終了判定部１４が、予め定められた終了条件を満たすまで、各パラメータのサンプリングを反復させ、終了条件を満たした場合に、サンプリングされた各パラメータを出力する。【選択図】図１
2014002499.tif 000002
【特許請求の範囲】
【請求項１】
隠れマルコフモデルにおける状態間の遷移を、モンドリアン過程における領域分割で表した系列データの生成過程を示す生成モデルの事後確率分布を示す各パラメータであって、前記モンドリアン過程において発生するcost及び分割位置で構成されたモンドリアンを示すパラメータΜ、前記モンドリアン過程の領域上における前記状態毎の位置を示すパラメータＳ、及び前記系列データの各要素に対応した隠れ状態の系列を示すパラメータＺを含む各パラメータの初期値を設定するパラメータ初期化手段と、
入力された系列データ、及び前記パラメータ初期化手段により設定された各パラメータの初期値、または前回サンプリングした各パラメータの値を用いて、前記パラメータΜ、前記パラメータＳ、及び前記パラメータＺを含む各パラメータをサンプリングするサンプリング手段と、
予め定められた終了条件を満たすまで、前記サンプリング手段による各パラメータのサンプリングを反復させ、前記終了条件を満たした場合に、反復する毎にサンプリングされた各パラメータのうち、少なくとも前記パラメータΜ、前記パラメータＳ、及び前記パラメータＺを出力する終了条件判定手段と、
を含む系列データ解析装置。
【請求項２】
前記サンプリング手段は、リヴァーシブルマルコフ連鎖モンテカルロ法に基づいて、前記モンドリアン過程における領域に新たな分割を加えるか、または分割を取り除くかを示す提案分布を採択または棄却することにより、前記パラメータΜをサンプリングし、前記領域毎のbeta変数を用いた多項分布から選択された領域中の一様分布から前記パラメータＳをサンプリングし、状態間の遷移回数を用いた多項分布から前記パラメータＺをサンプリングする請求項１記載の系列データ解析装置。
【請求項３】
前記サンプリング手段は、前記状態間の遷移確率を与えるディリクレ過程の重みを示すパラメータβ、及び前記モンドリアン過程における領域内の各ブロックにおけるバイナリ変数を示すパラメータＲを含む前記各パラメータをサンプリングする請求項１または請求項２記載の系列データ解析装置。
【請求項４】
終了判定手段は、入力された系列データに対する前記生成モデルの事後確率が最大となるときの各パラメータを出力するか、または該事後確率が最大となるときの各パラメータのうち、前記パラメータΜ、前記パラメータＲ、及び前記パラメータＺを出力する請求項１〜請求項３のいずれか１項記載の系列データ解析装置。
【請求項５】
パラメータ初期化手段が、隠れマルコフモデルにおける状態間の遷移を、モンドリアン過程における領域分割で表した系列データの生成過程を示す生成モデルの事後確率分布を示す各パラメータであって、前記モンドリアン過程において発生するcost及び分割位置で構成されたモンドリアンを示すパラメータΜ、前記モンドリアン過程の領域上における前記状態毎の位置を示すパラメータＳ、及び前記系列データの各要素に対応した隠れ状態の系列を示すパラメータＺを含む各パラメータの初期値を設定し、
サンプリング手段が、入力された系列データ、及び前記パラメータ初期化手段により設定された各パラメータの初期値、または前回サンプリングした各パラメータの値を用いて、前記パラメータΜ、前記パラメータＳ、及び前記パラメータＺを含む各パラメータをサンプリングし、
終了判定手段が、予め定められた終了条件を満たすまで、前記サンプリング手段による各パラメータのサンプリングを反復させ、前記終了条件を満たした場合に、反復する毎にサンプリングされた各パラメータのうち、少なくとも前記パラメータΜ、前記パラメータＳ、及び前記パラメータＺを出力する
系列データ解析方法。
【請求項６】
コンピュータを、請求項１〜請求項４のいずれか１項記載の系列データ解析装置を構成する各手段として機能させるための系列データ解析プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、系列データ解析装置、方法、及びプログラムに係り、特に、系列データをクラスタリングする系列データ解析装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
従来、系列データをクラスタリングしていく手法の代表的なものとして隠れマルコフモデルが知られている。入力系列データＹ＾ｔ（ｔ＝１，...，Ｔ）が与えられたとき、隠れマルコフモデルは次のような生成モデルの逆問題を解くことでクラスタリングを行う。
【０００３】
【数１】
2014002499.tif 000003
【０００４】
ただし、Dirichlet(・)は・をパラメータとするディリクレ分布を表している。Ｚｔは系列データｔ番目の要素に割り当てられた隠れ状態、π＾ｋはｋ番目の状態から次の状態への遷移確率、θｋはｋ番目の状態が持つパラメータ、Ｈは隠れ状態が持つパラメータの事前分布、Ｋは隠れ状態の個数、α及びβ＾は遷移確率πｋの事前分布の超パラメータ（αは正の実数、β＾はＫ次元の正の実数によるベクトル）である。また、Ａ〜ＢはＡが確率分布Ｂから生成されたことを表す。なお、数式内のボールド表示の記号は行列、多次元配列、またはベクトルであることを表わしており、文中では該当の記号に「＾」を付して表している。
【０００５】
従来は、隠れ状態の個数Ｋを予め指定することが一般的であったが、近年このＫの値、すなわちモデルの複雑度も同時に推定する方法として、階層ディリクレプロセスを事前分布として設定する方法が知られている（例えば、非特許文献１参照）。
【０００６】
【数２】
2014002499.tif 000004
【０００７】
ただし、ＤＰ(ａ，Ｈ)は集中度ａ、基底測度Ｈのディリクレ過程、δ．はディラック測度を表している。
【０００８】
また、ポアソン過程の多次元への拡張としてモンドリアン過程とよばれるモデルが知られている（例えば、非特許文献２参照）。ここでは簡単のため２次元に限定して述べる。２次元の領域(ａ，Ａ)×(ｂ，Ｂ)上のモンドリアン過程Μ〜ΜＰ(λ，(ａ，Ａ)，(ｂ，Ｂ))は以下のような再帰的な手順でこの領域に対して確率的な分割を与える。はじめにbudgetと呼ばれる正の実数を予め指定する。各再帰の中で、costが生成されbudgetと比較を行う。もしcostがbudgetを超過した場合、再帰的な反復は終了し現在の分割を返す。もしcostがbudgetを超過しなかった場合は新しい分割を追加し領域が２つの領域に分割され、budgetからcostが引かれる。分割された２つは各々独立なモンドリアン過程が再帰的に適用されていく。領域(ａ，Ａ)×(ｂ，Ｂ)において発生するcostは平均を1/(Ａ-ａ+Ｂ-ｂ)とする指数分布により生成される。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】T.Stepleton, Z.Ghahramani, G.Gordon and T.S.Lee, "The Block Diagonal Infinite Hidden Markov Model," AISTATS, 2009.
【非特許文献２】D.Roy, Y.W.Teh, "The Mondrian Process," NIPS, 2009.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、従来技術により系列データをクラスタリングする際には、各クラスタの間にどのような関係があるかを抽出することができない、という問題があった。
【００１１】
例えば、あるテレビ放送の動画の編集を行っている状況を考えてみる。ドラマのような場合、動画はシーン１、シーン２のようにいくつかのシーンを経ながらその合間にＡ社のＣＭ、Ｂ社のＣＭなどいくつかコマーシャルを挟む。従来の系列データのクラスタリング手法は、各時刻のデータに対して、シーン１、シーン２、ＣＭ１、ＣＭ２、などのラベル付けしていくことを目的としている。隠れマルコフモデルは、シーン１から次にどのクラスタに遷移し易いのかの情報を抽出することができる。例えば、シーン１の終了後必ずＣＭを挟んで次のシーンに移ったのであればシーン１から別のシーンに移る確率は０であると抽出されることが期待される。
【００１２】
ここで、例えばドラマ自体に興味がある場合、シーン１と別のシーンとの間に挟まるＣＭはＡ社のものであってもＢ社のものであってもＣ社のものであっても構わないと考えることができる。すなわち「ＣＭ」という機能の意味においてはＡ社のＣＭもＢ社のＣＭも交換可能であるとみなすことができる。例えば、動画編集をしている場合においては、クラスタの遷移におけるクラスタ間の交換可能性は有用な情報となる。
【００１３】
しかし、このような各クラスタ間の遷移については従来から議論されてきたが、２つの状態間の遷移におけるシーン１、シーン２、ＣＭ１、ＣＭ２、などのクラスタ同士の関係についてはあまり議論されてこなかった。
【００１４】
本発明は、上記の事情を考慮してなされたもので、系列データのクラスタリングを行う際に、クラスタ間の遷移における各クラスタの関係を同時に抽出することができる系列データ解析装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
上記目的を達成するために、本発明の系列データ解析装置は、隠れマルコフモデルにおける状態間の遷移を、モンドリアン過程における領域分割で表した系列データの生成過程を示す生成モデルの事後確率分布を示す各パラメータであって、前記モンドリアン過程において発生するcost及び分割位置で構成されたモンドリアンを示すパラメータΜ、前記モンドリアン過程の領域上における前記状態毎の位置を示すパラメータＳ、及び前記系列データの各要素に対応した隠れ状態の系列を示すパラメータＺを含む各パラメータの初期値を設定するパラメータ初期化手段と、入力された系列データ、及び前記パラメータ初期化手段により設定された各パラメータの初期値、または前回サンプリングした各パラメータの値を用いて、前記パラメータΜ、前記パラメータＳ、及び前記パラメータＺを含む各パラメータをサンプリングするサンプリング手段と、予め定められた終了条件を満たすまで、前記サンプリング手段による各パラメータのサンプリングを反復させ、前記終了条件を満たした場合に、反復する毎にサンプリングされた各パラメータのうち、少なくとも前記パラメータΜ、前記パラメータＳ、及び前記パラメータＺを出力する終了条件判定手段と、を含んで構成されている。
【００１６】
本発明の系列データ解析装置によれば、隠れマルコフモデルにおける状態間の遷移を、モンドリアン過程における領域分割で表した系列データの生成過程を示す生成モデルを用いて、系列データのクラスタリングを行う。パラメータ初期化手段が、この生成モデルの事後確率分布を示す各パラメータであって、モンドリアン過程において発生するcost及び分割位置で構成されたモンドリアンを示すパラメータΜ、モンドリアン過程の領域上における状態毎の位置を示すパラメータＳ、及び系列データの各要素に対応した隠れ状態の系列を示すパラメータＺを含む各パラメータの初期値を設定する。次に、サンプリング手段が、入力された系列データ、及びパラメータ初期化手段により設定された各パラメータの初期値、または前回サンプリングした各パラメータの値を用いて、パラメータΜ、パラメータＳ、及びパラメータＺを含む各パラメータをサンプリングする。そして、終了判定手段が、予め定められた終了条件を満たすまで、サンプリング手段による各パラメータのサンプリングを反復させ、終了条件を満たした場合に、反復する毎にサンプリングされた各パラメータのうち、少なくともパラメータΜ、パラメータＳ、及びパラメータＺを出力する。
【００１７】
このように、隠れマルコフモデルにおける状態間の遷移をモンドリアン過程における領域分割に適用した生成モデルの事後確率分布を示すパラメータとして、少なくともモンドリアンΜ、状態の位置Ｓ、及び隠れ状態Ｚをサンプリングすることで、モンドリアンの領域における各状態の位置関係によって示される各状態に対応するクラスタ間の関係も得ることができるため、系列データのクラスタリングを行う際に、クラスタ間の遷移における各クラスタの関係を同時に抽出することができる。
【００１８】
また、前記サンプリング手段は、リヴァーシブルマルコフ連鎖モンテカルロ法に基づいて、前記モンドリアン過程における領域に新たな分割を加えるか、または分割を取り除くかを示す提案分布を採択または棄却することにより、前記パラメータΜをサンプリングし、前記領域毎のbeta変数を用いた多項分布から選択された領域中の一様分布から前記パラメータＳをサンプリングし、状態間の遷移回数を用いた多項分布から前記パラメータＺをサンプリングすることができる。これにより、サンプリングを反復するほど、生成モデルの事後確率を大きくする各パラメータをサンプリングすることができる。
【００１９】
また、前記サンプリング手段は、前記状態間の遷移確率を与えるディリクレ過程の重みを示すパラメータβ、及び前記モンドリアン過程における領域内の各ブロックにおけるバイナリ変数を示すパラメータＲを含む前記各パラメータをサンプリングすることができる。
【００２０】
また、終了判定手段は、入力された系列データに対する前記生成モデルの事後確率が最大となるときの各パラメータを出力するか、または該事後確率が最大となるときの各パラメータのうち、前記パラメータΜ、前記パラメータＲ、及び前記パラメータＺを出力することができる。これにより、最も適切なパラメータのみを得ることができる。
【００２１】
また、本発明の系列データ解析方法は、パラメータ初期化手段が、隠れマルコフモデルにおける状態間の遷移を、モンドリアン過程における領域分割で表した系列データの生成過程を示す生成モデルの事後確率分布を示す各パラメータであって、前記モンドリアン過程において発生するcost及び分割位置で構成されたモンドリアンを示すパラメータΜ、前記モンドリアン過程の領域上における前記状態毎の位置を示すパラメータＳ、及び前記系列データの各要素に対応した隠れ状態の系列を示すパラメータＺを含む各パラメータの初期値を設定し、サンプリング手段が、入力された系列データ、及び前記パラメータ初期化手段により設定された各パラメータの初期値、または前回サンプリングした各パラメータの値を用いて、前記パラメータΜ、前記パラメータＳ、及び前記パラメータＺを含む各パラメータをサンプリングし、終了判定手段が、予め定められた終了条件を満たすまで、前記サンプリング手段による各パラメータのサンプリングを反復して行い、前記終了条件を満たした場合に、反復する毎にサンプリングされた各パラメータのうち、少なくとも前記パラメータΜ、前記パラメータＳ、及び前記パラメータＺを出力する方法である。
【００２２】
また、本発明の系列データ解析プログラムは、コンピュータを、上記の系列データ解析装置を構成する各手段として機能させるためのプログラムである。
【発明の効果】
【００２３】
以上説明したように、本発明の系列データ解析装置、方法、及びプログラムによれば、隠れマルコフモデルにおける状態間の遷移をモンドリアン過程における領域分割に適用した生成モデルの事後確率分布を示すパラメータとして、少なくともモンドリアンΜ、状態の位置Ｓ、及び隠れ状態Ｚをサンプリングすることで、モンドリアンの領域における各状態の位置関係によって示される各状態に対応するクラスタ間の関係も得ることができるため、系列データのクラスタリングを行う際に、クラスタ間の遷移における各クラスタの関係を同時に抽出することができる、という効果が得られる。
【図面の簡単な説明】
【００２４】
【図１】本実施の形態に係る系列データ解析装置の構成を示す概略図である。
【図２】本実施の形態における系列データ解析処理ルーチンの内容を示すフローチャートである。
【図３】人工的に生成したクラスタ間の関係モデルを示す図である。
【図４】推定されたクラスタ間の関係モデルを示す図である。
【図５】サンプリングの反復に対する事後確率の発展を示す図である。
【発明を実施するための形態】
【００２５】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２６】
＜生成モデル＞
まず、本実施の形態で用いる生成モデルについて説明する。本実施の形態では、隠れマルコフモデルを拡張した以下のような生成モデルを用いる。
【００２７】
本生成モデルは、Ｄ個の系列データＹ＾ｄ（ｄ＝１，...，Ｄ）の生成過程をモデル化していることに相当する。まず、モンドリアン過程による［０，１］×［０，１］の領域とその領域の分割（モンドリアンΜ）が下記（１）式に示すように生成され、各隠れ状態の［０，１］上の位置Ｓｋ（ｋ＝１，...）が下記（２）式に示すように生成される。
【００２８】
【数３】
2014002499.tif 000005
【００２９】
ただし、Uniformは一様分布を表している。ｄ（ｄ＝１，...，Ｄ）番目の系列データは状態遷移行列π＾ｋを表現するための次のような関係モデルを利用する。
【００３０】
【数４】
2014002499.tif 000006
【００３１】
ただし、Beta及びBernoulliはそれぞれベータ分布及びベルヌーイ分布を表している。さらに、通常の隠れマルコフモデルと同様に、状態遷移行列の事前分布を構成するために次のような隠れ変数の重みβを用意する。
【００３２】
【数５】
2014002499.tif 000007
【００３３】
ただし、GEM(・)は集中度・のディリクレ過程の重みのみを生成する分布である。各状態遷移確率π＾ｄは以上から
【００３４】
【数６】
2014002499.tif 000008
【００３５】
と表される。上記状態遷移確率を用い、Ｄ個の系列データは次のような生成モデルで表現される。
【００３６】
【数７】
2014002499.tif 000009
【００３７】
このような生成モデルを用い、Ｙｄ（ｄ＝１，...，Ｄ）を入力とし、ａ０、ａ１、ξ、γ、及びαを事前に指定するパラメータとして、モンドリアンΜ、各状態の位置Ｓ＾、モンドリアンの各ブロックにおけるbeta変数φ＾、モンドリアンの各ブロックにおけるバイナリ変数Ｒ＾、ディリクレ過程の重みβ＾、及び隠れ状態の系列Ｚ＾を推定することで所望の目的が達成される。
【００３８】
この推論は、下記（３）式に示す事後確率分布をマルコフ連鎖モンテカルロ法により推定することで実現できる。（３）式において、右辺の各項は上述の各確率分布の密度関数を表している。マルコフ連鎖モンテカルロは、後述する各手順を反復的に行うことによって実現できる。
【００３９】
【数８】
2014002499.tif 000010
【００４０】
＜システム構成＞
本実施の形態に係る系列データ解析装置は、ＣＰＵと、ＲＡＭと、後述する系列データ解析処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成されている。このコンピュータは、機能的には、図１に示すように、パラメータ初期化部１２と、サンプリング部１３と、終了判定部１４とを含んだ構成で表すことができる。また、サンプリング部１３は、さらに、Ｚサンプリング部２１と、βサンプリング部２２と、Ｒサンプリング部２３と、Μサンプリング部２４と、Ｓサンプリング部２５とを含んだ構成で表すことができる。
【００４１】
パラメータ初期化部１２は、予め決めたパラメータａ０、ａ１、ξ、γ、及びαと、入力系列データＹ＾ｄ,ｔ（ｄ＝１，...，Ｄ、ｔ＝１，...，Ｔ）とからモンドリアンΜ、各状態の位置Ｓ＾、モンドリアンの各ブロックにおけるbeta変数φ＾、モンドリアンの各ブロックにおけるバイナリ変数Ｒ＾、ディリクレ過程の重みβ＾、及び隠れ状態の系列Ｚ＾の初期値を設定する。
【００４２】
Μの初期値は分割のない［０，１］×［０，１］とする。Ｓ＾の初期値は事前分布の［０，１］からの一様分布から乱数により生成する。φ＾の初期値は事前分布のベータ分布から乱数により生成する。Ｒ＾の初期値は事前分布のベルヌーイ分布から乱数により生成する。β＾の初期値は一様なディリクレ分布から乱数により生成する。Ｚ＾の初期値は一様な多項分布から乱数により生成する。
【００４３】
サンプリング部１３は、パラメータ初期化部１２で設定された各パラメータの初期値と入力系列データＹ＾ｄ,ｔとに基づいて、Ｚサンプリング部２１、βサンプリング部２２、Ｒサンプリング部２３、Μサンプリング部２４、及びＳサンプリング部２５の各部により各パラメータをサンプリングする。また、終了判定部１４で終了したと判定されるまで、一つ前の反復処理においてサンプリングされた各パラメータと入力系列データＹ＾ｄ,ｔとに基づいて、各部による各パラメータのサンプリング処理を反復して行う。以下では、一反復の実行におけるサンプリング部１３の各部の処理について説明をする。
【００４４】
Ｚサンプリング２１は、時刻毎に次の多項分布から逐次的に隠れ状態の系列Ｚ＾をサンプリングする。
【００４５】
【数９】
2014002499.tif 000011
【００４６】
ただし、ｎｄ,ｉ,ｊはｄ番目の系列データにおいて状態ｉからｊに遷移した回数、ｎｄ,ｉ,ｊ−ｔはｎｄ,ｉ,ｊのうち、時刻ｔ−１からｔ及び時刻ｔからｔ＋１に遷移したものを除いた回数である。また、Ｉ［ｘ＝ｙ］はｘ＝ｙのときだけ１をとりそれ以外は０をとることを表す。
【００４７】
βサンプリング部２２は、ある反復の際に状態の数がＫであるとして、下記（６）式に示す密度関数に従う補助変数（ｑｄ，ｉ，ｊ）Ｄ×Ｋ×Ｋを用いて、ディリクレ過程の重みβ＾を下記（７）式に示すディリクレ分布からサンプリングする。ガンマ分布から補助変数（ｇｊ）Ｋをサンプリングした後、ベクトルｇ＾のＬ１ノルムが１となるように正規化したものとしてディリクレ過程の重みβ＾をサンプリングする。
【００４８】
【数１０】
2014002499.tif 000012
【００４９】
なお、状態の数Ｋは、理論的には無限大であり、Ｋの値が大きいほど状態推定の精度を向上させることができる。ただし、Ｋの値を大きくするほど計算コストが大きくなるため、実際には１００程度の値を用いる。
【００５０】
Ｒサンプリング部２３は、モンドリアンの各ブロックにおける状態間の遷移のし易さに応じたバイナリ変数Ｒ＾を、下記（８）式に示すようなベルヌーイ分布からサンプリングする。
【００５１】
【数１１】
2014002499.tif 000013
【００５２】
Μサンプリング部２４は、リヴァーシブルマルコフ連鎖モンテカルロ法に基づいて、モンドリアンΜをサンプリングする。モンドリアンはcostＥｋと分割位置χｋとで構成されているため、costＥｋと分割位置χｋとを同時にサンプリングする。
【００５３】
具体的には、反復毎に一つの分割を加えるか、一つの分割を取り除くかをメトロポリスヘイスティングアルゴリズムの採択または棄却によってサンプリングする。今、ｋ番目のブロックがｋ’とｋ”とに分割されたとすると、モンドリアンに関係するパラメータζ＾は＜ζ＾，Ｅｋ，χｋ＞となるとみなすことができる。一方で、分割が取り除かれる場合は、Ｅｋ及びχｋが＜ζ＾，Ｅｋ，χｋ＞から取り除かれζ＾になる。リヴァーシブルマルコフ連鎖モンテカルロ法を適用するため、現在のパラメータと提案のパラメータとの次元をそろえる必要があるため、分割を加える場合はζ＾ｉと補助変数とを加えた＜ζ＾ｉ，ｕ１，ｕ２＞を用いζ＾ｉ＋１＝＜ζ＾ｉ，Ｅｋ，χｋ＞とする。このとき、提案分布Ｑ（Μｉ＋１；Μｉ）はχｋを一様分布から、Ｅｋを1/τｋを平均パラメータとする指数分布からサンプリングする。
【００５４】
ｋ番目のブロックから分割を取り除く場合は、Ｑ（Μｉ＋１；Μｉ）は新しいパラメータζ＾ｉ＋１を確定的に決めることができる。
【００５５】
採択または棄却は以下のように行うことができる。提案分布が分割を取り除こうとしているとき、ａをUniform（０，１）から生成し、下記（１０）式に示す条件を満たすときだけ採択する。
【００５６】
【数１２】
2014002499.tif 000014
【００５７】
一方、分割を加えようとしている場合は、下記（１１）式に示す条件を満たすときだけ採択する。
【００５８】
【数１３】
2014002499.tif 000015
【００５９】
ただし、ｗｋはｋ番目のブロックがbudgetを使い果たす確率であり、下記のように表せる。
【００６０】
【数１４】
2014002499.tif 000016
【００６１】
分割を加える場合は下記のように表せる。
【００６２】
【数１５】
2014002499.tif 000017
【００６３】
Ｓサンプリング部２５は、次の補助変数を定義する。ｘ(Ｒ)＝＜ｘｈ(Ｒ)｜ｈ∈｛０，...，ＬＲ，ＬＲ＋１｝＞、ただし、ｘ(Ｒ)＝０，ｘｈ(Ｒ)＜ｘｈ＋１(Ｒ)，ｘＬＲ＋１(Ｒ)と定義する。同様に、ｘ(Ｃ)＝＜ｘｇ(Ｃ)｜ｇ∈｛０，...，ＬＣ，ＬＣ＋１｝＞を定義し、さらに、ｘ＾＝（ｘ０，...，ｘＬ＋１）、ただし、ｘｊ＝∈｛ｘ(Ｒ)，ｘ(Ｃ)｝、ｘｊ＜ｘｊ＋１，ｘ０＝０、ｘＬ＋１＝１とする。ｒ番目の状態の位置は、下記（１８）式に示す多項分布から［０，１］の中の分割の一つを選び、その中で一様分布から状態の位置Ｓ＾をサンプリングする。
【００６４】
【数１６】
2014002499.tif 000018
【００６５】
終了判定部１４は、予め定められた終了条件を満たしたか否かを判定し、終了条件を満たしていない場合には、繰り返し回数を１つ増加させて、各パラメータのサンプリング処理を繰り返す。本実施の形態では、生成するサンプル（モンドリアンΜ、各状態の位置Ｓ＾、モンドリアンの各ブロックにおけるbeta変数φ＾、モンドリアンの各ブロックにおけるバイナリ変数Ｒ＾、ディリクレ過程の重みβ＾、及び隠れ状態の系列Ｚ＾の各パラメータの組）の個数の上限を予め指定しておき、当該サンプルの個数の上限を、繰り返し回数の上限として設定しておく。計算時間の許す限り、サンプルの個数の上限としてできるだけ大きな値を選ぶほど、サンプルは事後分布のより良い近似となるが、実用的には１００個や数千個を選ぶのが一般的である。生成されたサンプルが指定の個数に満たない場合は反復を繰り返す。
【００６６】
終了判定部１４は、終了条件を満たすと判定した場合に、各反復で抽出されたサンプルを全て出力する。なお、各サンプルを（３）式に適用して得られる事後確率が最大となるサンプルが最適なサンプルとなるため、終了判定部１４では、この事後確率が最大となるサンプルのみを出力するようにしてもよい。また、サンプルのうち、クラスタ間の遷移におけるクラスタ間の関係を示すパラメータとして、モンドリアンΜ、各状態の位置Ｓ＾、及び隠れ状態の系列Ｚ＾のパラメータの組を出力するようにしてもよい。さらに、（３）式の事後確率が最大となるサンプルのΜ、Ｓ＾、及びＺ＾のパラメータの組のみを出力するようにしてもよい。
【００６７】
上記のようなサンプリングを繰り返すことで、そこから生成されたサンプルは事後分布をよく近似したものとなる。
【００６８】
次に、本実施の形態に係る系列データ解析装置１０の作用について説明する。まず、解析対象の系列データＹ＾ｄ,ｔ（ｄ＝１，...，Ｄ、ｔ＝１，...，Ｔ）が入力されると、系列データ解析装置１０において、図２に示す系列データ解析処理ルーチンが実行される。
【００６９】
ステップ１００で、入力された系列データＹ＾ｄ,ｔを受け付ける。次に、ステップ１０２で、パラメータ初期化部１２が、予め決めたパラメータａ０、ａ１、ξ、γ、及びαと、入力系列データＹ＾ｄ,ｔとからモンドリアンΜ、各状態の位置Ｓ＾、モンドリアンの各ブロックにおけるbeta変数φ＾、モンドリアンの各ブロックにおけるバイナリ変数Ｒ＾、ディリクレ過程の重みβ＾、及び隠れ状態の系列Ｚ＾の初期値を設定する。
【００７０】
次に、ステップ１０４で、Ｚサンプリング部２１が、（４）及び（５）式に従って、時刻毎に逐次的に隠れ状態の系列Ｚ＾をサンプリングする。次に、ステップ１０６で、βサンプリング部２２が、状態の数をＫとして、（６）式に示す密度関数に従う補助変数（ｑｄ,ｉ,ｊ）Ｄ×Ｋ×Ｋを用いて、ディリクレ過程の重みβ＾を（７）式に示すディリクレ分布からサンプリングする。次に、ステップ１０８で、Ｒサンプリング部２３が、モンドリアンの各ブロックにおけるバイナリ変数Ｒ＾を、（８）式に示すようなベルヌーイ分布からサンプリングする。次に、ステップ１１０で、Μサンプリング部２４が、リヴァーシブルマルコフ連鎖モンテカルロ法に基づいて、モンドリアンΜを構成するcostＥｋと分割位置χｋとを同時にサンプリングする。次に、ステップ１１２で、Ｓサンプリング部２５が、補助変数ｘ(Ｒ)及びｘ(Ｃ)を上述のように定義し、ｒ番目の状態の位置を、（１８）式に示す多項分布から［０，１］の中の分割の一つを選び、その中で一様分布から状態の位置Ｓ＾をサンプリングする。
【００７１】
次に、ステップ１１４で、終了判定部１４が、生成したサンプルの個数が上限値に達したか否かを判定することにより、終了条件を満たしたか否かを判定する。終了条件を満たしていない場合には、繰り返し回数を１つ増加させて、ステップ１０４へ戻り、上記の処理でサンプリングされた各パラメータを用いて、ステップ１０４〜１１２の処理を繰り返す。終了条件を満たした場合には、ステップ１１６へ移行し、各反復で抽出されたサンプルを出力して、系列データ解析処理を終了する。
【００７２】
なお、上記ステップ１０４〜１１２の各処理の実行順序は問わない。例えば、ステップ１１２の状態の位置Ｓ＾のサンプリングを最初に行ってもよい。
【００７３】
＜実施例＞
次に、本実施の形態に係る系列データ解析装置の効果を示すため、人工的に作ったデータに対し、各クラスタの関係が推定できるか否かを確認した実施例を示す。
【００７４】
ｆ（・|・）を正規分布とし、人工データは状態数（クラスタ数）６、系列データ数を３０とした。６つの隠れ状態はランダムに生成した一つのモンドリアンからランダムに生成した３０通りの関係モデル（図３）を与え、Ｔ＝１００の系列データを人工的に生成した。
【００７５】
本実施の形態に係る系列データ解析装置により、上記の人工的に生成したデータを入力系列データとして、マルコフ連鎖モンテカルロ法により各パラメータを推定して関係モデルを抽出した（図４）。図３及び図４に示すように、正しく関係モデルを抽出できることが確認できた。なお、図３及び図４では、色が濃い部分ほどクラスタ間の関係が強いことを示す。また、サンプリングの反復に対するモンドリアンに関する事後確率の発展を図５に示す。
【００７６】
以上説明したように、本発明の実施の形態に係る系列データ装置によれば、隠れマルコフモデルにおける状態間の遷移をモンドリアン過程における領域分割に適用した生成モデルの事後確率分布を示すパラメータとして、少なくともモンドリアンΜ、状態の位置Ｓ、及び隠れ状態Ｚをサンプリングすることで、モンドリアンの領域における各状態の位置関係によって示される各状態（クラスタ）間の関係も得ることができるため、系列データのクラスタリングを行う際に、クラスタ間の遷移における各クラスタの関係を同時に抽出することができる。
【００７７】
また、このような解析によって、クラスタ間の交換可能性の手掛かりを得ることができ、系列データの編集や加工に生かすことができる。
【００７８】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００７９】
また、上述の系列データ解析装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【００８０】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００８１】
１０   系列データ解析装置
１２   パラメータ初期化部
１３   サンプリング部
１４   終了判定部
２１   Ｚサンプリング部
２２   βサンプリング部
２３   Ｒサンプリング部
２４   Μサンプリング部
２５   Ｓサンプリング部
【図１】
2014002499.tif 000019
【図２】
2014002499.tif 000020
【図３】
2014002499.tif 000021
【図４】
2014002499.tif 000022
【図５】
2014002499.tif 000023