[ML]PAC Learning: Probably Approximately Correct learning

少し必要だったので昔の記憶を思い出して書いてみようと思うんだよ.

前提その1



学習対象は関数族 f:X\rightarrow \{0,1\}とする.
例としてXをΣ上の文字列の集合Σ*とすると,fは言語を表す.
Xを\{0,1\}^nとすると,fは論理関数を表す.

\{a\in X\mid f(a)=1\}と考えると,関数fはXを制限する特徴関数として見ることができる.
Xの部分集合をconceptと呼ぶ.ある特徴を持ったfの集合を概念のクラスと呼ぶ.
私達は例などから概念のクラス\mathcal{F}を学びたい.

概念のクラスを表現するために木や文法や論理式を利用する.
関数を表現するためのアルファベットΓが与えられるとき,Γを利用して
表現することができる表現の種類,表現のクラス(\mathcal{R}\subseteq \Gamma ^*)を表現クラスと呼ぶ.
関数C: \mathcal{R}\rightarrow \mathcal{F}を考えてR中の各表現rが表す関数をC(r)と書く.

前提その2



まず定義域X上に確率分布Dを仮定し,私達(学習アルゴリズム)は関数EX()を利用できる.
EX()を呼ぶと分布Dに従った要素a\in Xが独立に取得され,
未知の関数f_*の例(a,f_*(a))が取得できる.

近似度のパラメータεと信頼度のパラメータδを定義する.
このとき関数fとgの間のDに関する誤差はd(f.g)=\sum_{a\in f\Delta g}Pr_D(a)で定められる.
fΔgは関数fとgの対象差.

定義



学習アルゴリズムがFPAC学習するとは…

X上の任意の確率分布Dと\mathcal{F}中の任意の未知の関数f_*\in \mathcal{F}
任意のパラメータ0<\delta <1, 0<\varepsilon <1[/latex]についてアルゴリズムが常に停止して<br /> <br /> [latex]Pr(d(g, f_*)\leq\varepsilon) \geq 1-\delta

の条件を満たす関数gの表現r\in \mathcal{R}を出力すること.
つまり1-δで保証される高い確率で,ε程度しか違わない答えを発見できるということ.
こうして作られた出力は強仮説と呼ばれるよ.

弱PAC学習とブースティング



パラメータεとδが任意だとあれなので,ある固定されたパラメータε0とδ0を考える.
そしてPr(d(g,f_*)\leq\varepsilon_0)\geq 1-\delta_0
という条件を考える.こうして学習される仮説は弱仮説と呼ばれる.
ただしε0は1/2未満であること.

もしPr(d(g,f_*)) = 1/2であれば,ランダムな予測gとなる.
つまりgがfに当たる確率が1/2になるので,コインを投げているのと変わらないってこと.
こうしてランダムな仮説よりも少しいい仮説(ε0<1/2)を学ぶことを弱PAC学習する,という.
弱PAC学習で生成された弱仮説を使ってより優れた仮説を生成する手法がブースティングと呼ばれる.
例えばAdaBoostとかですね.

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です