修士論文 要旨

非定常データからの動的パラメータ推定とモデル選択に関する研究
数理情報学専攻 48096217
指導教員

櫻井瑛一
山西健司 教授(t)

1 はじめに
本研究では非定常なデータに対するモデル選択を考える．ここで非定常なデータとは時間区間ごとでは定常であるが，各時間区間での情報源は複雑度が異なる情報源から出力されていることを考える．近年，モデルの変化は起きるものと仮定し，変化するモデルの系列を推定するということが考えられるようになってきた．
本研究は変化するモデル系列を求めるという動的モデル選択（Dynamic Model Selection，以下 DMS と略す）の枠組み [5] を用いる．[5] では変化するモデル系列的なパラメータ推定値を θk とする．そして，モデルは遷移し，その確率は次のように定まるとする．

P (k1 ) = 1/K,
1−α, if kt+1 = kt , kt 6= 1orK,P (kt+1 |kt ) = 1 − α/2 , if kt+1 = kt , kt = 1orK,
α/2, if |kt+1 − kt | = 1.
そして，α の推定を変化の頻度で行う．モデルの系列

k T = {k1 , . . . , kT } の下での記述長とモデルの系列自体の記述長 `(k T ) を合わせた総記述長を `(xT , k T ) としたときに，MDL の二段階符号化による定義にならい，を予測的 MDL(Minimum Description Length) [2] に動的モデル選択規準を次のように定義する．

より，最適なモデル系列を選択する動的モデル選択規準

定義 1. モデル系列 k T の下で総記述長をを考え，その規準を満たすモデル系列を求める手法を確立した．
しかし，動的モデル選択では二つの問題が存在する．
一つは，モデルに付随するパラメータの変動があったと

T ³
X(t)
`(x , k ) =− log Pk (xt |θk )TT

t=1− log P (kt |k t−1 : α(k t−1 ))¢き，いかに追随し推定を行うかについて考えてこられなとする．この量を最小とするモデル系列 k T を選択するかったという問題である．他方は，モデルが変化する事ことを動的モデル選択と定義し，その選択の規準となるは過去を全て説明できるモデルが入れ替わるときであ

総記述長 `(xT , k T ) を動的モデル選択規準と定義する．

る (switching) としており，変化点を境に完全にモデルが切り替わる場合を扱えていないという問題である．

パラメータが過去データ全てに依るため，モデル遷移

本研究では二つの問題を解消するアルゴリズムの設は過去を含め今をより良く説明するモデルが現れた時計と解析を与えた．前者に対してはパラメータが区間点で発生する．それゆえ，switching 型動的モデル選的に変化しても，これに追従できる動的パラメータ推定択とよぶ．そして，最適なモデル系列を求めるアルゴリを提案し，従来の動的モデル選択と組み合わせて効果をズムが動的計画法により構成でき，次が成立する．

生み出す手法を与えた．後者に対しては直近の変化点

定 理 2. 定 義 1. の 規 準 を 最 小 化 す る モ デ ル 系 列 はからパラメータを初期化して推定しなおし，モデル系列

O(KT 2 ) で求まり，その総記述長は次で抑えられる:m tj+1³´X
X−1(t)
T
T−log P xt |θk(j)`(x , k ) ≤ min minm  t,kj=0 t=tjµ¶
m
1+(T − 1)H+ log(T − 1)
T −12
+(m + 1) log 2+log K .
を選択する resetting 型のアルゴリズムを提案した．

2 動的モデル選択
本研究での基礎となる動的モデル選択の定義を行う．
観測されたデータ列を xT = {x1 , . . . , xT } とし，それの生成源として，確率モデルクラスを考える．(Ck ={Pk (X|θ)}, Ck−1 ⊂ Ck , (1 ≤ k ≤ K)) を考える．ここでの，k はクラスの複雑さをあらわす指標であり，今後は k をモデルの次数と呼ぶ．そして，モデルクラス Ckに対する t − 1 までの出力から学習した時刻 t での逐次

ただし，t = {t0 , . . . , tm+1 } はモデルの変化時刻を表し，

k = {k(1), . . . , k(m)} で k(j) は時間区間 [tj , tj+1 − 1]の間でのモデルをあらわす．

非定常データからの動的パラメータ推定とモデル選択に関する研究 (櫻井瑛一)になった追従性に必要なエントロピーのコストだけ上

3 本研究での問題設定界が下がる．一方計算量は変化頻度と変化時点を記憶

本研究では特に，出力 yt を補助入力 xt から予測関するため O(KT 3 ) となる．そこで，データ圧縮におけ数 f (x, θ) を用いて予測を行う逐次予測問題を考える．

る研究 [3, 4] を援用し，変化点に依存する遷移確率推定

その予測損失を凸な関数 L(y, z) を用いてはかり，動的を用いる動的モデル選択アルゴリズムを提案した．こモデル選択を考える際には，その損失から確率を定めれにより計算すべき状態が減り，計算量は O(KT 2 ) とP (L) とする．その例として，論文では二乗ロスとガウなる．その上界は，[3] を用いれば次のように書ける．

ス分布を用いた AR モデルを考え数値実験を行った．

4 動的パラメータ推定(t)には真の構造変化に対しての追従性が必要になる．そこで，連続型集合型予測枠組みと [1] を組み合わせ，以下のようなアルゴリズムを構築した． この結果，次がAlgorithm 1 動的パラメータ推定
Initialization0<η≤ηnXπ(t − tc + 1)
1α̂(k ) =, π(t) = 1+² , Zn =π(j)Z∞ − Zt−tct
j=1t

Swithcing 型動的モデル選択のパラメータ推定法 θk∗

定理 4. [3] を応用した resetting 型 DMS は遷移確率をで推定し，求めた k T の下で上界は以下を満たす:

m tj+1
 X³´
X−1(tj ,t)TT`(x , k ) ≤ min min−log P xt |θk(j)m t,kj=0 t=tj, 0 < α < 1, π1s (θ) = π1 (θ),

R+ m logπ1 (θ)dθ = 1.

for t = 1 to T doRRŷt = πts (θ)/Πst f (xt , θ)dθ, Πst = πts (θ)dθ.
R mπ̃tm (θ) = πts (θ)e−ηL(yt ,f (xt ,θ)) ,Π̃mπ̃t (θ)dθ.
t =s(θ) = (1 − α)π̃tm (θ) + απ1s (θ)Π̃m
πt+1t .

TT+²(m+1) log
mm+1
²+(m+1) log(1+²)−m log +log K .
26 まとめend forSwitching 型動的モデル選択で構造変化への追従性成立する．

が要求されその手法を提案した．また，モデルの推移が定理 3. 累積予測損失の上界は次を満たす:
TX

ÃL(yt , ŷt ) ≤ min −Ã k1 X

限定されていたため，resetting 型を提案した．そして，

switching 型と動的パラメータ推定を組み合わせた場合
log Z[ti , ti+1 − 1]と resetting 型と逐次最尤推定を組み合わせた場合の情µ µµ¶¶¶¶mm ¯¯¯¯+(T − 1) H+Dα,¯¯T −1T −1Z
Pti+1 −1−ηL(yt0 ,f (xt0 ,θ))t0 =tidθ.
Z[ti , ti+1 − 1] = π1 (θ)e

報論的・計算論的限界を導いた．その結果，両者を計算

ただし，t = {t0 , . . . , tm , tm+1 }, (1 = t0 < t1 < · · · <[1] M. Herbster and M. K. Warmuth. Tracking the bestexpert. In Proceedings of the 12th International Conference on Machine Learning, pp. 286–294. MorganKaufmann, 1995.
[2] J. Rissanen. Universal coding, information, prediction, and estimation. IEEE Transaction on Information Theory, Vol. 30, pp. 629–636, 1984.
[3] G. I. Shamir and N. Merhav. Low complexity sequential lossless coding for piecewise stationary memoryless sources. IEEE Transactions on Information Theory, Vol. 45, pp. 1498–1519, 1999.
[4] F. M. J. Willems. Coding for a binary independentpiecewiseidentically-distributed source. IEEE Transactions on Information Theory, Vol. 42, pp. 2210–2217, 1996.
[5] K. Yamanishi and Y. Maruyama. Dynamic model
selection with its applications to novelty detection.
IEEE Transactions on Information Theory, Vol. 53,
pp. 2180–2189, 2007.

t=1t,mη¶i=0tm+1 = T + 1) であり，0 ≤ m ≤ T − 1 である．

5 動的モデル選択の拡張
前章での動的なパラメータ推定では過去の影響を受(t ,t)けていたが，直近の変化点 tc から推定しなおす θk c

場合を考える．このような推定を行う動的モデル選択を resetting 型動的モデル選択と定義する．これにより，switching 型とは違い，局所に最良なモデルを選択できる．
ここで，パラメータ推定として最尤推定量に漸近する推定を行うとする．その場合，switching 型と動的なパラメータ推定を組み合わせた場合と比べ，前章で明らか論的には同じにした場合，情報論的上界は前者 < 後者となり，後者の有意性を理論的に保証した．

参考文献