講演抄録/キーワード |
講演名 |
2010-06-15 16:45
逐次的動的モデル選択の線形時間アルゴリズム ○櫻井瑛一・山西健司(東大) IBISML2010-25 |
抄録 |
(和) |
本稿では時系列データから変化するモデル系列を推定する「動的モデル選択」の問題を考える.従来,データ列が一括に与えられたときに動的計画法を用いてモデル系列を求めるアルゴリズムが提案されていたが,本稿では逐次的にデータを読みこみながらモデル系列を逐次的に推定し計算量が線形となるアルゴリズムを考察する.人工データについて実験的評価を行い,本アルゴリズムは計算量を劇的に減らしつつ,一括型のアルゴリズムと同じモデル系列を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 isdesigned using a dynamic programming (DP) technique and requires $O(n^{2})$computation time ($n$ is data size).
We propose a novel DMS algorithm that runs in time linearly in the data sizeand can also be applied to sequential learning environments. The key idea isto 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. |
キーワード |
(和) |
MDL / 動的モデル選択 / 動的計画法 / / / / / |
(英) |
MDL principle / dynamic model selection / dynamic programming / / / / / |
文献情報 |
信学技報, vol. 110, no. 76, IBISML2010-25, pp. 175-180, 2010年6月. |
資料番号 |
IBISML2010-25 |
発行日 |
2010-06-07 (IBISML) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IBISML2010-25 |