ベイズ統計学に基づくOn-line学習モデルと学習可能性

概要

論文の詳細を見る
計算論的学習理論のパラダイムの1つであるOn-line 学習モデルでは, 重みを用いた学習アルゴリズムについて多くの研究がなされてきた。WINNOWはその代表的なアルゴリズムの1つであり, プール関数のクラスにおいてリテラルや節などに対応する重みを用いて学習を行なう。一方Wighted Majority Algorithm (WMA)は重みを個々の概念に対応させて学習するアルゴリズムである。これらのアルゴリズムの長所として, 概念クラスから任意の1つの仮説を選択して予測するアルゴリズムよりも優れた性能を持っことが, ヒューリスティックな方法で示されている。この性質はベイズ統計学の枠組を用いることにより, 厳密に証明することができる。D.Hausslerらは計算論的学習理論の立場からベイズ的学習モデルを研究し, ベイズアルゴリズムのsample complexityについての解析を行なっている。また情報理論の考え方を取り入れた解析結果も明らかにしている。このベイズアルゴリズムはベイズ統計学に立脚した最適性を保証するという優れた性能を持っているが, 問題の領域が大きくなると事後確率の更新や平均損失を最小にする決定を探索する計算量が膨大になるという問題点もある。計算量の問題は, もう1つの学習パラダイムであるProbably Approximately Correct (PAC)学習モデルでは, 多くのクラスについての学習可能性が明らかにされているが, On-line学習モデルの予測可能性についての議論は不十分である。またPAC学習モデルにおいても, 従来の学習可能性の議論のみではネガティブな結果しか得られず, 現実問題との乖離が大きい。本稿はこれらの点を考慮し, ベイズアルゴリズムを考える場合にsample complexityだけでなくtime complexityも考えた学習モデルの枠組を提案する。このモデルではベイズ統計学と計算量理論の両方の視点からモデル化を行ない, PAC学習モデルだけでなくOn-line学習モデルについても同様に扱うモデルであることを明らかにする。さらにベイズ予測可能性という新しい概念を提案し, 典型的な概念クラスについて予測可能性を明らかにし, その性質についても述べる。なお, 本文ではブール関数を対象とするが, q元, q>2, の事例空間, 概念表現空間のクラスへの拡張は可能である。
1997-09-24

ベイズ統計学に基づくOn-line学習モデルと学習可能性

スポンサーリンク

概要

著者

関連論文

スポンサーリンク