| 講演名 | 2002/5/13 計算論的学習と情報圧縮に関する一考察 中澤 真, 松嶋 敏泰, 平澤 茂一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 情報源符号化における形式文法に基づく符号化法は,サンプルデータからオートマトンを導出する過程と考えることができる.これは情報圧縮の過程を機械学習の枠組みで捉えることができることを意味する.しかし,Chomsky階層に属する文法あるいは計算機モデルの中で,どのようなものを対象とするのが適切であるかは明らかにされていない.また,従来の文法に基づく符号化はいずれも決定性文脈自由文法を用いているが,この文法が必ずしも最適というわけではない.この点を明らかにするため,計算論的学習理論の枠組みから情報圧縮の過程を捉え,ベイズ学習アルゴリズムを用いて十分シンプルで記述長が短い仮説を出力できることを示す.さらにどのような計算機モデルを考えると現実的計算量で最適な仮説を出力ことが可能になるかを示し,これが事前分布の分布族の複雑さと仮説言語の複雑さの両方によって決まることを示す. |
| 抄録(英) | Recently, grammar based codes are researched in the area of lossless source coding. But, it is not clear which formal grammars is appropriate in Chomsky hierarchy for information compression. In this paper, we consider grammar based codes as the process of deriving automata based on machine learning and it is a purpose to clarify what influence the class of grammars or languages gives the encoding in the view of machine learning. I will show that Bayes algorithm outputs the shortest hypothesis in the class and some class has feasible complexity in order to ouput optimal hypothesis based on computational learning theory. |
| キーワード(和) | 形式文法 / 無歪み圧縮 / 計算論的学習 / ベイズアルゴリズム / タイムコンプレキシティ |
| キーワード(英) | formal grammars / lossless compression / computational learning / Bayes algorithm / time complexity |
| 資料番号 | IT2002-7 |
| 発行日 |
| 研究会情報 | |
| 研究会 | IT |
|---|---|
| 開催期間 | 2002/5/13(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Theory (IT) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 計算論的学習と情報圧縮に関する一考察 |
| サブタイトル（和） | |
| タイトル（英） | A Note on Computational Learning and Information Compression |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 形式文法 / formal grammars |
| キーワード(2)（和/英） | 無歪み圧縮 / lossless compression |
| キーワード(3)（和/英） | 計算論的学習 / computational learning |
| キーワード(4)（和/英） | ベイズアルゴリズム / Bayes algorithm |
| キーワード(5)（和/英） | タイムコンプレキシティ / time complexity |
| 第 1 著者 氏名（和/英） | 中澤 真 / Makoto NAKAZAWA |
| 第 1 著者 所属（和/英） | 早稲田大学メディアネヅトワークセンター Media Network Center, Waseda University |
| 第 2 著者 氏名（和/英） | 松嶋 敏泰 / Toshiyasu MATSUSHIMA |
| 第 2 著者 所属（和/英） | 早稲田大学理工学部経営システム工学科 School of Science and Engineering, Waseda University |
| 第 3 著者 氏名（和/英） | 平澤 茂一 / Shigeichi HIRASAWA |
| 第 3 著者 所属（和/英） | 早稲田大学理工学部経営システム工学科 School of Science and Engineering, Waseda University |
| 発表年月日 | 2002/5/13 |
| 資料番号 | IT2002-7 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 66 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |