講演抄録/キーワード |
講演名 |
2012-06-20 14:50
多次元パラメータを有する区間定常無記憶情報源に対してのMDL原理に基づく変化検出アルゴリズム ○金澤宏紀・山西健司(東大) IBISML2012-9 |
抄録 |
(和) |
非定常情報源の変化検出は,応用対象が幅広い重要な研究分野である.Kleinberg はテキストマイニングの分野で,時系列テキストデータから特定の単語が頻出する時期―バースト区間―を推定するアルゴリズムを構成した. Kanazawa and Yamanishi は Kleinberg のアルゴリズムをMDL原理に基づいて拡張し,1次元パラメータ区間定常無記憶情報源(PSMS)に対しての変化検出アルゴリズムを提案した.Kanazawa and Yamanishi は同時に,そのアルゴリズムの期待冗長度が Merhav の示す下限に漸近的に一致することを示した.アルゴリズムの核となるアイディアは 1) パラメータ空間をFisher情報量に基づき離散化する 2) 総記述長が最小となるようなパラメータ列を動的計画法(DP)により求める の2点である.
本論文では Kanazawa and Yamanishi の変化検出アルゴリズムを紹介するとともに,パラメータ空間の離散化法を多次元パラメータ空間に拡張する手法を提案する.さらに提案するアルゴリズムの記述長の期待値が Merhav の示す下限に漸近的に一致することを示す. |
(英) |
Kleinberg has proposed an algorithm for detecting bursts from a data sequence, which has turned out to be effective in the scenario of data mining, such as topic detection, change-detection, etc. Kanazawa and Yamanishi extended Kleinberg's algorithm in an information-theoretic fashion to obtain a new class of algorithms and applied it into learning of piecewise stationary memoryless sources (PSMSs) with 1-dimensional parameter. In this paper we introduce Kanazawa and Yamanishi's change-detection algorithm, and extend their algorithm into PSMSs with multi-dimensional parameter. We prove that an upper bound on the total code-length for the proposed algorithm asymptotically matches Merhav's lower bound. |
キーワード |
(和) |
MDL 原理 / 変化検知 / 区間定常無記憶情報源 / パラメータ離散化 / / / / |
(英) |
minimum description length principle / change-detection / piecewise stationary memoryless source / parameter discretization / / / / |
文献情報 |
信学技報, vol. 112, no. 83, IBISML2012-9, pp. 57-64, 2012年6月. |
資料番号 |
IBISML2012-9 |
発行日 |
2012-06-12 (IBISML) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
査読に ついて |
本技術報告は査読を経ていない技術報告であり,推敲を加えられていずれかの場に発表されることがあります. |
PDFダウンロード |
IBISML2012-9 |