JP7268752B2 - パラメタ推定装置、パラメタ推定方法、及びパラメタ推定プログラム - Google Patents

Description

開示の技術は、パラメタ推定装置、パラメタ推定方法、及びパラメタ推定プログラムに関する。

マルコフ過程は多様な動的システムを表現できる汎用性の高いモデルであり、都市の人や交通の流れの分析、及びチケット販売窓口の待ち行列の分析など様々な用途で用いられている。

例えば、従来技術として、状態の集合における状態間の完全な遷移データである完全遷移データのみからマルコフ連鎖のパラメタを推定する手法が示されている（非特許文献１参照）。

Patrick Billingsley. Statistical methods in markov chains. The Annals of Mathematical Statistics, pp. 12-40, 1961.

しかしながら、既存の推定手法では、完全遷移データと、観測可能な状態の集合に関する部分的な遷移データであるセンサ遷移データの両方のデータとを用いて、元のマルコフ連鎖のパラメタの推定はできない、という課題がある。

開示の技術は、上記の点に鑑みてなされた技術であり、部分的に観測されたデータを用いて、マルコフ連鎖のパラメタを精度よく推定できるパラメタ推定装置、パラメタ推定方法、及びパラメタ推定プログラムを提供することを目的とする。

本開示の第１態様は、パラメタ推定装置であって、状態の集合と、観測可能な状態の集合と、前記観測可能な状態の集合に関するセンサ遷移データと、前記状態の集合における状態間の完全な遷移データである完全遷移データとを入力データとし、前記完全遷移データへの当てはまり度合いを表す、前記状態の集合から定義される既定のマルコフ連鎖の遷移確率の一致度を表す項と、前記センサ遷移データへの当てはまり度合いを表す、前記観測可能な状態の集合から定義されるセンサマルコフ連鎖の遷移確率の一致度を表す項とを含む目的関数を最適化するように、前記既定のマルコフ連鎖及び前記センサマルコフ連鎖のそれぞれの遷移確率に係るパラメタを推定する推定部、を含む。

本開示の第２態様は、パラメタ推定方法であって、状態の集合と、観測可能な状態の集合と、前記観測可能な状態の集合に関するセンサ遷移データと、前記状態の集合における状態間の完全な遷移データである完全遷移データとを入力データとし、前記完全遷移データへの当てはまり度合いを表す、前記状態の集合から定義される既定のマルコフ連鎖の遷移確率の一致度を表す項と、前記センサ遷移データへの当てはまり度合いを表す、前記観測可能な状態の集合から定義されるセンサマルコフ連鎖の遷移確率の一致度を表す項とを含む目的関数を最適化するように、前記既定のマルコフ連鎖及び前記センサマルコフ連鎖のそれぞれの遷移確率に係るパラメタを推定する、ことを含む処理をコンピュータが実行することを特徴とする。

本開示の第３態様は、パラメタ推定プログラムであって、状態の集合と、観測可能な状態の集合と、前記観測可能な状態の集合に関するセンサ遷移データと、前記状態の集合における状態間の完全な遷移データである完全遷移データとを入力データとし、前記完全遷移データへの当てはまり度合いを表す、前記状態の集合から定義される既定のマルコフ連鎖の遷移確率の一致度を表す項と、前記センサ遷移データへの当てはまり度合いを表す、前記観測可能な状態の集合から定義されるセンサマルコフ連鎖の遷移確率の一致度を表す項とを含む目的関数を最適化するように、前記既定のマルコフ連鎖及び前記センサマルコフ連鎖のそれぞれの遷移確率に係るパラメタを推定する、ことをコンピュータに実行させる。

開示の技術によれば、部分的に観測されたデータを用いて、マルコフ連鎖のパラメタを精度よく推定することができる。

完全遷移データの一例を示す図である。 センサ遷移データの一例を示す図である。 本開示の手法の全体像のイメージを示す概略図である。 本実施形態のパラメタ推定装置の構成を示すブロック図である。 パラメタ推定装置のハードウェア構成を示すブロック図である。 パラメタ推定装置によるパラメタ推定処理の流れを示すフローチャートである。

以下、開示の技術の実施形態の一例を、図面を参照しつつ説明する。なお、各図面において同一又は等価な構成要素及び部分には同一の参照符号を付与している。また、図面の寸法比率は、説明の都合上誇張されており、実際の比率とは異なる場合がある。

以下において、まず、本開示に関する背景及び概要について説明した上で、本開示に係る原理及び最適化手法について説明する。

背景について、マルコフ過程の性質に関する事項を説明する。マルコフ過程のもつパラメタである遷移確率と初期状態確率とは一般に既知ではないことから、観測データから推定を行う必要がある。各状態間の遷移を観測した理想的な遷移データ、すなわち完全遷移データが利用できれば、状態間の遷移の回数をもとに容易に推定ができる（非参考文献１参照）。しかし、現実環境で収集されるデータの中には観測不可能な状態が存在するために、観測が一部打ち切られた遷移データ、すなわちセンサ遷移データとして表現される場合がある。センサ遷移データは、観測可能な状態の集合に関する部分的な遷移データである。

例えば、観光地における交通機関の移動履歴データを分析する状況を考える。この場合、実際に被験者を集めて移動を行ってもらい収集したデータは、被験者の人数に限定されるためにデータの量は少ないが、バス、タクシー、及び電車などの移動手段によらず移動の履歴が記録された完全遷移データとなる。完全遷移データは、状態の集合における状態間の完全な遷移データである。図１は、完全遷移データの一例を示す図である。一方、同地域におけるたとえば鉄道会社から提供されるデータは、これまでの全乗客に関するデータとなるためデータの量は多いが、鉄道駅間の移動履歴のみしかわからない。そのため、例えばバス停など鉄道駅と対応しない状態の訪問は記録されないセンサ遷移データとなる。図２は、センサ遷移データの一例を示す図である。本開示の手法は、センサマルコフ連鎖の理論と半教師付き学習に類似する手法の定式化とを用いて、上記２種類のデータの両方を利用してマルコフ連鎖のパラメタをセンサ遷移データから推定する手法である。この手法によりどちらか一方のデータしか利用できない場合と比較して、より精度のよいパラメタの推定が可能となる。センサマルコフ連鎖については、観測可能な状態の集合から定義されるマルコフ連鎖であり、詳細については後述する。

既存手法は、課題について述べたように、完全遷移データと、センサ遷移データとの両方のデータとを用いて、元のマルコフ連鎖（以下、既定のマルコフ連鎖と表記する）のパラメタの推定はできない。そこで本開示の手法では、完全遷移データとセンサ遷移データとの両方のデータを用いて、既定のマルコフ連鎖のパラメタを推定する手法を構築した。本開示のポイントとなるのは、センサマルコフ連鎖と半教師付き学習の定式化の利用である。以下で、マルコフ連鎖、及びセンサマルコフ連鎖についての原理を述べた後に、本開示の構成及び作用を説明する。

［準備］
状態の集合を以下で表す。以下の説明では単に状態の集合Ｘとも表記する。

状態の集合Ｘ上の離散時間のマルコフ連鎖は次の（１）式に示すマルコフ性をもつ確率過程｛Ｘ_ｔ；ｔ＝０，１，２，・・・｝として定義される。

・・・（１）

マルコフ連鎖は｛Ｘ，Ｐ，ｑ｝の３つ組で定義ができる。状態の集合Ｘに関する確率として、Ｐ：Ｘ×Ｘ→［０，１］は遷移確率、ｑ：Ｘ→［０，１］は初期状態確率であり、以下（２）式のように定義される。

・・・（２）
以後マルコフ連鎖は既約（ｉｒｒｅｄｕｃｉｂｌｅ）なマルコフ連鎖であると考える。

更にセンサマルコフ連鎖（ｃｅｎｓｏｒｅｄ Ｍａｒｋｏｖ ｃｈａｉｎ）の定義を与える。センサマルコフ連鎖は、Ｃｅｎｓｏｒｅｄ ｐｒｏｃｅｓｓ，ｗａｔｃｈｅｄ Ｍａｒｋｏｖ ｃｈａｉｎ，ｉｎｄｕｃｅｄ ｃｈａｉｎ等と呼ばれる場合もある（参考文献１、参考文献２、及び参考文献３参照）
［参考文献１］John G Kemeny, J Laurie Snell, and AnthonyW Knapp. Denumerable Markov chains, Vol.40. Springer-Verlag New York, 1976.
［参考文献２］DavidA Levin and Yuval Peres. Markov chains and mixing times, Vol.
107.American Mathematical Soc., 2017.
［参考文献３］YQuennel Zhao and Danielle Liu. The censored markov chain and the best augmentation. Journal of Applied Probability, Vol.33, No.3, pp. 623-629,1996.

Ｏを状態の集合Ｘの部分集合、Ｏ∈Ｘであるとする。Ｏは観測可能な状態の集合を表す。同様に観測不可能な状態の集合をＵと表す。センサマルコフ連鎖｛Ｘ_ｔ ^ｃ；ｔ＝０，１，２，・・・｝は、時刻ｔの状態Ｘ_ｔ ^ｃが、既定のマルコフ連鎖｛Ｘ_ｔ′；ｔ′＝０，１，２，・・・｝で観測不可能な状態は無視してｔ番目に現れた観測可能な状態を表すように定義する。既定のマルコフ連鎖で観測可能な状態が現れた時刻をそれぞれσ_０，σ_１，・・・，σ_ｔ，・・・などと書けば、センサマルコフ連鎖は以下のように定義できる。

なお、上記の右辺を以下ではＸσ_ｔとも表記する。直感的には、センサマルコフ連鎖は、既定のマルコフ連鎖から観測可能な状態のみを抜き出しているといえる。センサマルコフ連鎖の厳密な定義は以下の通りである。

［定義１］
Ｘ_ｔ∈Ｏとなる時刻を表す点列｛σ_ｔ；ｔ＝０，１，２，・・・｝を、σ_０＝０（ｉｆ
Ｘ_０∈Ｏ），σ_０＝ｉｎｆ｛ｍ≧１：Ｘ_ｍ∈Ｏ｝（ｏｔｈｅｒｗｉｓｅ），σ_ｔ＝ｉｎｆ｛ｍ＞σ_ｔ－１：Ｘ_ｍ∈Ｏ｝と定義する。系列σ_ｔでＸ_ｔを観測して得られる系列Ｘ_ｔ ^ｃ：＝Ｘσ_ｔをセンサマルコフ連鎖と呼ぶ。

以後、一般性を失うことなく状態は並び替えられて、マルコフ連鎖の遷移確率の行列表現Ｐ，（Ｐ）ｘｘ′＝Ｐ（ｘ′｜ｘ）と初期状態確率のベクトル表現ｑ：（ｑ）_ｘ＝ｑ（ｘ）が以下（３）式で与えられるとする。

・・・（３）

Ｐ_ｏｏ，Ｐ_ｏｕ，Ｐ_ｕｏ，Ｐ_ｕｕはそれぞれサイズが｜Ｏ｜×｜Ｏ｜，｜Ｏ｜×｜Ｕ｜，｜Ｕ｜×｜Ｏ｜，｜Ｕ｜×｜Ｕ｜の行列である。また、センサマルコフ連鎖について次の結果が定理１及び定理２として示されている。

［定理１］
センサマルコフ連鎖は以下の遷移確率行列に従うマルコフ連鎖である。

上記の定理１とほぼ同様の証明で初期状態確率について以下の定理２が導かれる。
［定理２］
センサマルコフ連鎖の初期状態確率は以下のｓで定義される。

定理１及び定理２により、既定のマルコフ連鎖｛Ｘ，Ｐ，ｑ｝と観測可能状態の集合Ｏとから作られるセンサマルコフ連鎖が、マルコフ連鎖｛Ｏ，Ｒ，ｓ｝の３つ組で定義ができる。

以上の原理を踏まえて、次に本開示の目的関数及び最適化手法について述べる。本開示の手法は、完全遷移データとセンサ遷移データとの両方を用いて既定のマルコフ連鎖のパラメタを推定する手法である。図３は、本開示の手法の全体像のイメージを示す概略図である。本手法の入力となるデータと入力モデル（目的関数）との詳細は次の通りである。

入力データは、（１）既定のマルコフ連鎖の状態の集合Ｘ、（２）観測可能な状態の集合Ｏ、（３）センサ遷移データＤ_ｃｅｎ、（４）完全遷移データＤ_ｐｅｒである。センサ遷移データＤ_ｃｅｎは、Ｄ_ｃｅｎ＝｛Ｎ_ｉｊ｝_ｉｊ∈Ｏ∪｛Ｎ_ｋ ^ｉｎｉ｝_ｋ∈Ｏである。Ｎ_ｉｊは観測可能な状態ｉ∈Ｏから観測可能な状態ｊ∈Ｏへの遷移の回数である。Ｎ_ｋ ^{ｉ ｎｉ}は観測可能な状態ｋ∈Ｏが初期状態として観測された回数を表す。完全遷移データＤ_ｐｅｒは、Ｄ_ｐｅｒ＝｛Ｎ_ｉｊ｝_ｉｊ∈Ｘ∪｛Ｍ_ｋ ^ｉｎｉ｝_ｋ∈Ｏである。Ｍ_ｉｊは状態ｉ∈Ｘから状態ｊ∈Ｘへの遷移の回数である。Ｍ_ｋ ^ｉｎｉは状態ｋ∈Ｘが初期状態として観測された回数を表す。また、以後ではセンサ遷移データ及び完全遷移データをまとめてＤ＝｛Ｄ_ｃｅｎ，Ｄ_ｐｅｒ｝と表す。

入力モデルには、既定のマルコフ連鎖の遷移確率と初期状態とを表現する任意のモデルを利用できる。目的関数に含まれる、入力モデルのパラメタをθ＝（η，λ）、遷移確率と初期状態との入力モデルをＰ^η，ｑ^λと表す。目的関数及び入力モデルの具体例は後ほど示す。この目的関数を用いたときの既定のマルコフ連鎖の遷移確率と初期状態確率とを以下（４）式で表す。

・・・（４）

（３）式と同様、一般性を失うことなく状態が並び替えられていて、目的関数を用いた遷移確率と初期状態確率との行列、及びベクトル表現が以下（５）式で与えられているとする。

・・・（５）

以上の入力データ及び入力モデルから得られる本開示の手法の出力は、目的関数のパラメタの推定結果θ＝（η，λ）である。よって既定のマルコフ連鎖の遷移確率Ｐ^ηと初期状態確率ｑ^λとが得られる。

次に目的関数の詳細について説明する。手法におけるパラメタ推定は目的関数の最適化により行う。目的関数には、カルバックライブラーダイバージェンス（Ｋｕｌｌｂａｃｋ－Ｌｅｉｂｌｅｒダイバージェンス。以下、ＫＬダイバージェンスと表記する）などのデータを生成する真の分布とモデルの確率分布とが近くなるとき値が小さくなる任意の関数が利用できる。以下、本開示ではＫＬダイバージェンスを利用する場合を考える。

入力データである完全遷移データは、既定のマルコフ連鎖｛Ｘ，Ｐ^＊，ｑ^＊｝から得られており、センサ遷移データは、センサマルコフ連鎖｛Ｏ，Ｒ^＊，ｓ^＊｝から得られていると考えられる。Ｐ^＊，ｑ^＊は既定のマルコフ連鎖の未知の真のパラメタであり、Ｒ^＊，ｓ^＊はマルコフ連鎖｛Ｘ，Ｐ^＊，ｑ^＊｝と観測可能状態Ｏとから作られるセンサマルコフ連鎖の遷移確率である。

定理１及び定理２より、入力モデルＰ^η，ｑ^λと観測可能状態Ｏとから作られるセンサマルコフ連鎖の遷移確率と初期状態確率とは下記（６）式のＲ^η，ｓ^η，λで与えられる。

・・・（６）

また、既定のマルコフ連鎖の遷移確率と初期状態確率とはＰ^ηとｑ^λとであることを（４）式ですでに示した。よって、ここでは、半教師付き学習の定式化にならう。ここで、ならう、と表しているのは、本開示の手法は、半教師付き学習に類似する手法だからである。半教師付き学習とは、厳密には、回帰又は識別などの入出力の関係を学習する教師付き学習の問題において、入出力両方が与えられたデータ、すなわち教師付きデータと入力のみが与えられたデータ、すなわち教師なしデータの両方を用いて、入出力関係を学習する設定を指す。本開示の内容は状態遷移確率を推定する設定であり、厳密な意味での半教師付き学習ではないが、入力モデルのパラメタを種類の異なる両方のデータに対する当てはめ度合いを考慮して推定しているという意味で半教師付き学習と非常に類似した設定であるため、このような言い方をしている。

目的関数としては、次の各項の線形和を利用できる。第１の項は、完全遷移データへの当てはまり度合いを表すＰ^ηとＲ^＊とのＫＬダイバージェンスの項である。第２の項は、ｑ^η，λとｑ^＊とのＫＬダイバージェンスの項である。第３の項は、センサ遷移データへの当てはまり度合いを表すＲ^ηとＲ^＊とのＫＬダイバージェンスの項である。第４の項は、ｓ^η，λとｓ^＊とのＫＬダイバージェンスの項である。第５の項は、推定対象のパラメタの発散を防ぐ正則化項である。パラメタに依存しない項を除けば、目的関数は以下（７－１）、（７－２）式で定義できる。

・・・（７－１）

・・・（７－２）
（７－１）式は第１項及び第２項、（７－２）式は第３項～第５項に関する。なお、初期状態確率のパラメタλを推定対象にしない場合には、第２項及び第４項を除いて第１項及び第３項を含む目的関数とすればよい。ただし、Ω（θ）はパラメタの正則化項であり、α＝（α_ｃｅｎ，α_ｃｅｎ ^ｉｎｉ）とは各項の目的関数への寄与度合いを定めるハイパーパラメタである。正則化項には、Ｌ_２ノルムなどの任意の正則化項を利用してよい。

次に最適化手法について述べる。目的関数の最適化には、勾配法又はニュートン法などの任意の最適化手法が適用できる。勾配法を利用する場合、ｋ回目の最適化ステップで、下記（８）式に従ってパラメタの更新を繰り返せばよい。

・・・（８）
ただし、γ_ｋは学習率パラメタである。目的関数の勾配∇_θＬ（θ）は計算して導出した関数を利用してもよいし、数値的に計算する方法を用いてもよい。

ここで目的関数に含まれる入力モデルＰ^η，ｑ^λの例を示す。遷移確率に関するモデルＰ^ηには、パラメタη＝｛ｖ^ｂａｓｅ，ｖ^ｆｔｒ｝をもつ下記（９）式のモデルを用いる。

・・・（９）
ただし、ｇ（ｉ，ｊ，η）はｇ（ｉ，ｊ，η）＝ｖ_ｉｊ ^ｂａｓｅ＋φ（ｉ，ｊ）^Ｔｖ^{ｆ ｔｒ}で定義されるスコア関数であり、φ（ｉ，ｊ）は特徴ベクトルである。特徴ベクトルφ（ｉ，ｊ）は、状態ｉとｊとに関する任意の属性情報をもつベクトルであり、例えば状態間の地理的な距離などを表す各要素をベクトルとしてもつ。また、ｖ^ｂａｓｅは、状態遷移に関するパラメタであり、ｖ^ｆｔｒは、特徴ベクトルに関するパラメタである。同様に初期状態確率に関するモデルｑ^λには、パラメタλ＝｛ｗ^ｂａｓｅ，ｗ^ｆｔｒ｝をもつ下記（１０）式のモデルが考えられる。

・・・（１０）
ただし、ｈ（ｉ，λ）はｈ（ｉ，ｊ，λ）＝ｗ_ｉ ^ｂａｓｅ＋Φ（ｉ）^Ｔｗ^ｆｔｒで定義されるスコア関数であり、Φ（ｉ）は特徴ベクトルである。特徴ベクトルはΦ（ｉ）は状態ｉに関する任意の属性情報をもつベクトルであり、例えばその状態が商業地域か否かなどを表す各要素をベクトルとしてもつ。

以上の目的関数及び最適化手法を用いて、本開示のパラメタ推定装置は、パラメタの最適化を行う。

以下、本実施形態の構成について説明する。

図４は、本実施形態のパラメタ推定装置の構成を示すブロック図である。

図４に示すように、パラメタ推定装置１００は、データ処理部１１０と、パラメタ記録部１２０と、推定部１３０と、パラメタ処理部１４０と、記録部１５０と、入出力部１６０とを含んで構成されている。また、パラメタ推定装置１００は、ネットワーク（図示省略）により外部装置１０２と接続されており、入出力部１６０により各種データを送受信する。

図５は、パラメタ推定装置１００のハードウェア構成を示すブロック図である。

図５に示すように、パラメタ推定装置１００は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）１１、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）１２、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）１３、ストレージ１４、入力部１５、表示部１６及び通信インタフェース（Ｉ／Ｆ）１７を有する。各構成は、バス１９を介して相互に通信可能に接続されている。

ＣＰＵ１１は、中央演算処理ユニットであり、各種プログラムを実行したり、各部を制御したりする。すなわち、ＣＰＵ１１は、ＲＯＭ１２又はストレージ１４からプログラムを読み出し、ＲＡＭ１３を作業領域としてプログラムを実行する。ＣＰＵ１１は、ＲＯＭ１２又はストレージ１４に記憶されているプログラムに従って、上記各構成の制御及び各種の演算処理を行う。本実施形態では、ＲＯＭ１２又はストレージ１４には、パラメタ推定プログラムが格納されている。

ＲＯＭ１２は、各種プログラム及び各種データを格納する。ＲＡＭ１３は、作業領域として一時的にプログラム又はデータを記憶する。ストレージ１４は、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）又はＳＳＤ（Ｓｏｌｉｄ Ｓｔａｔｅ Ｄｒｉｖｅ）等の記憶装置により構成され、オペレーティングシステムを含む各種プログラム、及び各種データを格納する。

入力部１５は、マウス等のポインティングデバイス、及びキーボードを含み、各種の入力を行うために使用される。

表示部１６は、例えば、液晶ディスプレイであり、各種の情報を表示する。表示部１６は、タッチパネル方式を採用して、入力部１５として機能してもよい。

通信インタフェース１７は、端末等の他の機器と通信するためのインタフェースであり、例えば、イーサネット（登録商標）、ＦＤＤＩ、Ｗｉ－Ｆｉ（登録商標）等の規格が用いられる。

次に、パラメタ推定装置１００の各機能構成について説明する。各機能構成は、ＣＰＵ１１がＲＯＭ１２又はストレージ１４に記憶されたパラメタ推定プログラムを読み出し、ＲＡＭ１３に展開して実行することにより実現される。

入出力部１６０は、外部装置１０２から入力データ、及び目的関数の設定パラメタを受け付ける。

データ処理部１１０は、入出力部１６０で受け付けた入力データを、記録部１５０の入力データ記録部１５１に記録する。入力データは、状態の集合Ｘ、観測可能な状態の集合Ｏ、センサ遷移データＤ_ｃｅｎ、及び完全遷移データＤ_ｐｅｒである。

パラメタ記録部１２０は、入出力部１６０で受け付けた設定パラメタを、記録部１５０の設定パラメタ記録部１５２に記録する。設定パラメタは、目的関数のハイパーパラメタα，β、及び最適化の際に用いる学習率パラメタγ_ｋなどである。

推定部１３０は、入力データ記録部１５１に記録されている入力データ、及び設定パラメタ記録部１５２に記録されている設定パラメタを読み込んで、パラメタ推定処理を実行し、推定されたパラメタθ＝（η，λ）をモデルパラメタ記録部１５３に記録する。
推定部１３０は、処理として、上記（７－１）、（７－２）式で表される目的関数を最適化するように、パラメタθ＝（η，λ）を推定する。ηは、既定のマルコフ連鎖及びセンサマルコフ連鎖のそれぞれの遷移確率Ｐ^η，Ｒ^ηに係るパラメタである。λは、既定のマルコフ連鎖及びセンサマルコフ連鎖のそれぞれの初期状態確率ｑ^η，λ，ｓ^η，λに係るパラメタである。推定のための最適化手法は、上記（８）式に従ってパラメタθを推定する処理を、所定の条件を満たすまで繰り返し行う。所定の条件には、例えば、繰り返しの最大数を定めておけばよい。

パラメタ処理部１４０は、モデルパラメタ記録部１５３に記録されているパラメタθを、入出力部１６０を介して外部装置１０２に送信する。

次に、パラメタ推定装置１００の作用について説明する。

図６は、パラメタ推定装置１００によるパラメタ推定処理の流れを示すフローチャートである。ＣＰＵ１１がＲＯＭ１２又はストレージ１４からパラメタ推定プログラムを読み出して、ＲＡＭ１３に展開して実行することにより、パラメタ推定処理が行なわれる。

ステップＳ１００において、ＣＰＵ１１は、入力として、上述したように、入力データ及び設定パラメタを受け付けて記録部１５０の各記録部に記録する。入力データとしては、状態の集合Ｘ、観測可能な状態の集合Ｏ、センサ遷移データＤ_ｃｅｎ、及び完全遷移データＤ_ｐｅｒを受け付けて入力データ記録部１５１に記録する。設定データとしては、目的関数のハイパーパラメタα，β、及び最適化の際に用いる学習率パラメタγ_ｋなどを受け付けて設定パラメタ記録部１５２に記録する。

ステップＳ１０２において、ＣＰＵ１１は、入力データ記録部１５１から入力データを読み出し、設定パラメタ記録部１５２から設定パラメタを読み出して、例えば（７－１）、（７－２）式に示すような目的関数を定義する。

ステップＳ１０４において、ＣＰＵ１１は、パラメタθを初期化するとともに、繰り返し回数ｋをｋ＝０とし、繰り返しの最大数Ｋを設定する。

ステップＳ１０６において、ＣＰＵ１１は、ステップＳ１０２で定義した目的関数を最適化するように、上記（８）式に従って、パラメタθを更新し、推定する。

ステップＳ１０８において、繰り返し回数ｋを１加算して更新する。

ステップＳ１１０において、繰り返し回数ｋが最大数Ｋを超えたか否かを判定する。最大数Ｋを超えた場合には、パラメタθの推定結果をモデルパラメタ記録部１５３に記録して処理を終了し、最大数Ｋを超えていない場合には、ステップＳ１０６に戻って処理を繰り返す。

以上説明したように本実施形態のパラメタ推定装置１００によれば、部分的に観測されたデータを用いて、マルコフ連鎖のパラメタを精度よく推定できる。

また、上記の実施形態では、最適化の際に勾配法を用いる例を示しているが、ニュートン法など任意の手法が利用できる。同様に状態遷移確率と初期状態確率とのモデルにも任意のモデルが利用できる。同様に、目的関数の正則化項にも任意の正則化項が利用できる。また、上記の実施形態の図４に示すパラメタ推定装置は、各構成要素の動作をプログラムとして構築し、パラメタ推定装置として利用されるコンピュータにインストールして実行させる、又はネットワークを介した流通形態が可能である。本開示は上記の形態に限定されることなく、種々の変更及び応用が可能である。

なお、上記各実施形態でＣＰＵがソフトウェア（プログラム）を読み込んで実行したパラメタ推定処理を、ＣＰＵ以外の各種のプロセッサが実行してもよい。この場合のプロセッサとしては、ＦＰＧＡ（Ｆｉｅｌｄ－Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）等の製造後に回路構成を変更可能なＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ
Ｄｅｖｉｃｅ）、及びＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）等の特定の処理を実行させるために専用に設計された回路構成を有するプロセッサである専用電気回路等が例示される。また、パラメタ推定処理を、これらの各種のプロセッサのうちの１つで実行してもよいし、同種又は異種の２つ以上のプロセッサの組み合わせ（例えば、複数のＦＰＧＡ、及びＣＰＵとＦＰＧＡとの組み合わせ等）で実行してもよい。また、これらの各種のプロセッサのハードウェア的な構造は、より具体的には、半導体素子等の回路素子を組み合わせた電気回路である。

また、上記各実施形態では、パラメタ推定プログラムがストレージ１４に予め記憶（インストール）されている態様を説明したが、これに限定されない。プログラムは、ＣＤ－ＲＯＭ（Ｃｏｍｐａｃｔ Ｄｉｓｋ Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＤＶＤ－ＲＯＭ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、及びＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）メモリ等の非一時的（ｎｏｎ－ｔｒａｎｓｉｔｏｒｙ）記憶媒体に記憶された形態で提供されてもよい。また、プログラムは、ネットワークを介して外部装置からダウンロードされる形態としてもよい。

以上の実施形態に関し、更に以下の付記を開示する。

（付記項１）
メモリと、
前記メモリに接続された少なくとも１つのプロセッサと、
を含み、
前記プロセッサは、
状態の集合と、観測可能な状態の集合と、前記観測可能な状態の集合に関するセンサ遷移データと、前記状態の集合における状態間の完全な遷移データである完全遷移データとを入力データとし、前記完全遷移データへの当てはまり度合いを表す、前記状態の集合から定義される既定のマルコフ連鎖の遷移確率の一致度を表す項と、前記センサ遷移データへの当てはまり度合いを表す、前記観測可能な状態の集合から定義されるセンサマルコフ連鎖の遷移確率の一致度を表す項とを含む目的関数を最適化するように、前記既定のマルコフ連鎖及び前記センサマルコフ連鎖のそれぞれの遷移確率に係るパラメタを推定する、
ように構成されているパラメタ推定装置。

（付記項２）
状態の集合と、観測可能な状態の集合と、前記観測可能な状態の集合に関するセンサ遷移データと、前記状態の集合における状態間の完全な遷移データである完全遷移データとを入力データとし、前記完全遷移データへの当てはまり度合いを表す、前記状態の集合から定義される既定のマルコフ連鎖の遷移確率の一致度を表す項と、前記センサ遷移データへの当てはまり度合いを表す、前記観測可能な状態の集合から定義されるセンサマルコフ連鎖の遷移確率の一致度を表す項とを含む目的関数を最適化するように、前記既定のマルコフ連鎖及び前記センサマルコフ連鎖のそれぞれの遷移確率に係るパラメタを推定する、
ことをコンピュータに実行させるパラメタ推定プログラムを記憶した非一時的記憶媒体。

１００ パラメタ推定装置
１０２ 外部装置
１１０ データ処理部
１２０ パラメタ記録部
１３０ 推定部
１４０ パラメタ処理部
１５０ 記録部
１５１ 入力データ記録部
１５２ 設定パラメタ記録部
１５３ モデルパラメタ記録部
１６０ 入出力部

Claims (7)

1. 状態の集合と、観測可能な状態の集合と、前記観測可能な状態の集合に関するセンサ遷移データと、前記状態の集合における状態間の完全な遷移データである完全遷移データとを入力データとし、前記完全遷移データへの当てはまり度合いを表す、前記状態の集合から定義される既定のマルコフ連鎖の遷移確率の一致度を表す項と、前記センサ遷移データへの当てはまり度合いを表す、前記観測可能な状態の集合から定義されるセンサマルコフ連鎖の遷移確率の一致度を表す項とを含む目的関数を最適化するように、前記既定のマルコフ連鎖及び前記センサマルコフ連鎖のそれぞれの遷移確率に係るパラメタを推定する推定部、
   を含むパラメタ推定装置。
2. 前記目的関数は、前記既定のマルコフ連鎖の初期状態確率の一致度を表す項と、前記センサマルコフ連鎖の初期状態確率の一致度を表す項と、前記パラメタの発散を防ぐ正規化項とを更に含み、
   前記推定部は、前記目的関数を最適化するように、前記遷移確率に係るパラメタと、前記既定のマルコフ連鎖及び前記センサマルコフ連鎖のそれぞれの初期状態確率に係るパラメタとを推定する請求項１に記載のパラメタ推定装置。
3. 前記目的関数において、カルバックライブラーダイバージェンスを適用し、前記既定のマルコフ連鎖の遷移確率の一致度を表す項には、前記完全遷移データの状態間の遷移の回数を用い、前記センサマルコフ連鎖の遷移確率の一致度を表す項には、前記センサ遷移データの観測可能な状態間の遷移の回数を用いる請求項１又は請求項２に記載のパラメタ推定装置。
4. 状態の集合と、観測可能な状態の集合と、前記観測可能な状態の集合に関するセンサ遷移データと、前記状態の集合における状態間の完全な遷移データである完全遷移データとを入力データとし、前記完全遷移データへの当てはまり度合いを表す、前記状態の集合から定義される既定のマルコフ連鎖の遷移確率の一致度を表す項と、前記センサ遷移データへの当てはまり度合いを表す、前記観測可能な状態の集合から定義されるセンサマルコフ連鎖の遷移確率の一致度を表す項とを含む目的関数を最適化するように、前記既定のマルコフ連鎖及び前記センサマルコフ連鎖のそれぞれの遷移確率に係るパラメタを推定する、
   ことを含む処理をコンピュータが実行することを特徴とするパラメタ推定方法。
5. 前記目的関数は、前記既定のマルコフ連鎖の初期状態確率の一致度を表す項と、前記センサマルコフ連鎖の初期状態確率の一致度を表す項と、前記パラメタの発散を防ぐ正規化項とを更に含み、
   前記推定において、前記目的関数を最適化するように、前記遷移確率に係るパラメタと、前記既定のマルコフ連鎖及び前記センサマルコフ連鎖の初期状態確率に係るパラメタとを推定する請求項４に記載のパラメタ推定方法。
6. 前記目的関数において、カルバックライブラーダイバージェンスを適用し、前記既定のマルコフ連鎖の遷移確率の一致度を表す項には、前記完全遷移データの状態間の遷移の回数を用い、前記センサマルコフ連鎖の遷移確率の一致度を表す項には、前記センサ遷移データの観測可能な状態間の遷移の回数を用いる請求項４又は請求項５に記載のパラメタ推定方法。
7. 状態の集合と、観測可能な状態の集合と、前記観測可能な状態の集合に関するセンサ遷移データと、前記状態の集合における状態間の完全な遷移データである完全遷移データとを入力データとし、前記完全遷移データへの当てはまり度合いを表す、前記状態の集合から定義される既定のマルコフ連鎖の遷移確率の一致度を表す項と、前記センサ遷移データへの当てはまり度合いを表す、前記観測可能な状態の集合から定義されるセンサマルコフ連鎖の遷移確率の一致度を表す項とを含む目的関数を最適化するように、前記既定のマルコフ連鎖及び前記センサマルコフ連鎖のそれぞれの遷移確率に係るパラメタを推定する、
   ことをコンピュータに実行させるパラメタ推定プログラム。

Images