本稿では時系列データから変化するモデル系列を推定する「動的モデル選択」の問題を考える．従来，データ列が一括に与えられたときに動的計画法を用いてモデル系列を求めるアルゴリズムが提案されていたが，本稿では逐次的にデータを読みこみながらモデル系列を逐次的に推定し計算量が線形となるアルゴリズムを考察する．人工データについて実験的評価を行い，本アルゴリズムは計算量を劇的に減らしつつ，一括型のアルゴリズムと同じモデル系列を9割以上得られることを示す．%This paper addresses the issue of dynamic model selection (DMS), in which the goal is to select an optimal model sequence from time series under the assumption that the probabilistic model may change over time. Conventionally it has been proposed a batch algorithm for DMS, which is designed using a dynamic programming (DP) technique and requires O(n2) computation time (n is data size). We propose a novel DMS algorithm that runs in time linearly in the data size and can also be applied to sequential learning environments. The key idea is to sequentially apply the DP technique over subsequences of length a fixed size to drastically reduce the size of model sequences to be searched. We empirically demonstrate its effectiveness through artificial data sets by showing that the proposed algorithm produces model sequences of almost the same performance as the conventional algorithm while drastically reducing the computational costs.
展开▼
