| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 研究会情報 | |
| 研究会 | IBISML |
| 開催期間 | 2010-06-14 - 2010-06-15 |
| 開催地（和） | 東大武田ホール |
| 開催地（英） | Takeda Hall, Univ. Tokyo |
| テーマ（和） | 機械学習とその応用 |
| テーマ（英） | Machine learning, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IBISML |
| 会議コード | 2010-06-IBISML |
| 本文の言語 | 日本語 |
| タイトル（和） | 逐次的動的モデル選択の線形時間アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | A linear time algorithm for sequential dynamic model selection |
| サブタイトル（英） | |
| キーワード(1)（和/英） | MDL / MDL principle |
| キーワード(2)（和/英） | 動的モデル選択 / dynamic model selection |
| キーワード(3)（和/英） | 動的計画法 / dynamic programming |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 櫻井 瑛一 / Eiichi Sakurai / サクライ エイイチ |
| 第1著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： Univ. of Tokyo.) |
| 第2著者 氏名（和/英/ヨミ） | 山西 健司 / Kenji Yamanishi / ヤマニシ ケンジ |
| 第2著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： Univ. of Tokyo.) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2010-06-15 16:45:00 |
| 発表時間 | 15分 |
| 申込先研究会 | IBISML |
| 資料番号 | IBISML2010-25 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | no.76 |
| ページ範囲 | pp.175-180 |
| ページ数 | 6 |
| 発行日 | 2010-06-07 (IBISML) |
[研究会発表申込システムのトップページに戻る]