オッカム学習

計算学習理論において、オッカム学習は、学習者の目的が受信したトレーニング データの簡潔な表現を出力することであるアルゴリズム学習のモデルです。これは、学習者がテスト セットの予測力に基づいて評価される、 おそらくほぼ正しい (PAC) 学習と密接に関連しています。

オッカムの学習可能性は PAC 学習を意味し、さまざまな概念クラスではその逆も当てはまります。つまり、PAC 学習可能性はオッカムの学習可能性を意味します。

オッカム学習はオッカムの剃刀にちなんで名付けられました。オッカムの剃刀とは、他のすべての条件が同じであれば、観察されたデータに対する短い説明の方が長い説明よりも優先されるべきであるという原理です。オッカム学習の理論は、この原理を形式的かつ数学的に正当化するものです。オッカム学習は計算学習理論における学習の標準モデルであるPAC学習を意味することが、Blumerら^[1]によって初めて示されました。言い換えれば、（出力仮説の）簡素化は予測力を意味します。

概念クラスの概念の簡潔さは、で表現できる最短のビット文字列の長さで表現できます。オッカム学習は、学習アルゴリズムの出力の簡潔さと、目に見えないデータに対する予測力を結び付けます。 ${\displaystyle c}$ ${\displaystyle {\mathcal {C}}}$${\displaystyle size(c)}$${\displaystyle c}$${\displaystyle {\mathcal {C}}}$

とをそれぞれ対象概念と仮説を含む概念クラスとする。定数とに対して、学習アルゴリズムはを使用する-Occamアルゴリズムであり、かつ、概念 に従ってラベル付けされたサンプルの集合が与えられた場合に限り、次のような 仮説を出力する。${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle \alpha \geq 0}$${\displaystyle 0\leq \beta <1}$${\displaystyle L}$${\displaystyle (\alpha ,\beta )}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle S=\{x_{1},\dots ,x_{m}\}}$${\displaystyle m}$${\displaystyle c\in {\mathcal {C}}}$${\displaystyle L}$${\displaystyle h\in {\mathcal {H}}}$

• ${\displaystyle h}$は（つまり）と整合しており、${\displaystyle c}$${\displaystyle S}$${\displaystyle h(x)=c(x),\forall x\in S}$
• ${\displaystyle size(h)\leq (n\cdot size(c))^{\alpha }m^{\beta }}$ ^{[2] [1]}

ここで、は任意のサンプルの最大長である。オッカムアルゴリズムは、、、およびにおいて多項式時間で実行される場合、効率的であると言われる。概念クラスが仮説クラスに関してオッカム学習可能であるのは、それを使用する効率的なオッカムアルゴリズムが存在する場合である。 ${\displaystyle n}$${\displaystyle x\in S}$${\displaystyle n}$${\displaystyle m}$${\displaystyle size(c).}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {H}}.}$

オッカムの学習可能性はPACの学習可能性を意味し、Blumerら^[2]の次の定理がそれを示しています。

を使用するための効率的な -Occam アルゴリズムをとします。このとき、 および の任意の分布 に対して、 から抽出され、それぞれ長さ ビットの概念に従ってラベル付けされたサンプルが与えられた場合、アルゴリズム は少なくともの確率で となる仮説を出力します 。${\displaystyle L}$${\displaystyle (\alpha ,\beta )}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {H}}}$${\displaystyle a>0}$${\displaystyle 0<\epsilon ,\delta <1}$${\displaystyle {\mathcal {D}}}$${\displaystyle m\geq a\left({\frac {1}{\epsilon }}\log {\frac {1}{\delta }}+\left({\frac {(n\cdot size(c))^{\alpha })}{\epsilon }}\right)^{\frac {1}{1-\beta }}\right)}$${\displaystyle {\mathcal {D}}}$${\displaystyle c\in {\mathcal {C}}}$${\displaystyle n}$${\displaystyle L}$${\displaystyle h\in {\mathcal {H}}}$${\displaystyle error(h)\leq \epsilon }$${\displaystyle 1-\delta }$

ここで、は概念と分布に関してです。これは、アルゴリズムが仮説クラス を使用する概念クラスの PAC 学習器でもあることを意味します。もう少し一般的な定式化は次のとおりです。 ${\displaystyle error(h)}$${\displaystyle c}$${\displaystyle {\mathcal {D}}}$${\displaystyle L}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {H}}}$

とします。は、固定されているが未知の分布から抽出され、それぞれの長さビットの概念に従ってラベル付けされたサンプルが与えられた場合、ラベル付けされたサンプルと一致する仮説を出力するアルゴリズムとします。すると、 の場合、 は少なくとも の確率で仮説 を出力することが保証される定数が存在します。${\displaystyle 0<\epsilon ,\delta <1}$${\displaystyle L}$${\displaystyle m}$${\displaystyle {\mathcal {D}}}$${\displaystyle c\in {\mathcal {C}}}$${\displaystyle n}$${\displaystyle h\in {\mathcal {H}}_{n,m}}$${\displaystyle b}$${\displaystyle \log |{\mathcal {H}}_{n,m}|\leq b\epsilon m-\log {\frac {1}{\delta }}}$${\displaystyle L}$${\displaystyle h\in {\mathcal {H}}_{n,m}}$${\displaystyle error(h)\leq \epsilon }$${\displaystyle 1-\delta }$

上記の定理は、オッカム学習がPAC学習に十分であることを示していますが、必要性については何も述べていません。BoardとPittは、さまざまな概念クラスについて、オッカム学習が実際にPAC学習に必要であることを示しています。^{[3]彼らは、}例外リストの下で多項式的に閉じている概念クラスの場合、 PAC学習可能性はその概念クラスに対するオッカムアルゴリズムの存在を意味することを証明しました。例外リストの下で多項式的に閉じている概念クラスには、ブール式、回路、決定論的有限オートマトン、決定リスト、決定木、およびその他の幾何学的に定義された概念クラスが含まれます。

概念の表現と例外の有限リストが与えられたときに、概念とが集合を除いて一致するような概念の表現を出力する多項式時間アルゴリズムが存在する場合、概念クラスは例外リストの下で多項式的に閉じています。 ${\displaystyle {\mathcal {C}}}$${\displaystyle A}$${\displaystyle c\in {\mathcal {C}}}$${\displaystyle E}$${\displaystyle c'\in {\mathcal {C}}}$${\displaystyle c}$${\displaystyle c'}$${\displaystyle E}$

まず、基数バージョンを証明します。の場合、仮説は悪いと呼ばれます。ここで、 は真の概念と基礎となる分布に関して再びです。サンプルの独立性により、サンプル セットがと一致する確率は最大で です。和集合により、 に悪い仮説が存在する確率は最大で であり、の場合よりも小さくなります。これで、上記の 2 番目の定理の証明は終了です。 ${\displaystyle h\in {\mathcal {H}}}$ ${\displaystyle error(h)\geq \epsilon }$${\displaystyle error(h)}$${\displaystyle c}$${\displaystyle {\mathcal {D}}}$${\displaystyle S}$${\displaystyle h}$${\displaystyle (1-\epsilon )^{m}}$${\displaystyle {\mathcal {H}}_{n,m}}$${\displaystyle |{\mathcal {H}}_{n,m}|(1-\epsilon )^{m}}$${\displaystyle \delta }$${\displaystyle \log |{\mathcal {H}}_{n,m}|\leq O(\epsilon m)-\log {\frac {1}{\delta }}}$

2 番目の定理を使用すると、最初の定理を証明できます。 -Occam アルゴリズムがあるため、 が出力する仮説は最大 ビットで表現できるため、 となります。これは、 を何らかの定数 に設定した場合よりも小さくなります。したがって、基数バージョンの定理により、は少なくとも の確率で一貫した仮説を出力します。これで、上記の最初の定理の証明は終了です。 ${\displaystyle (\alpha ,\beta )}$${\displaystyle L}$${\displaystyle (n\cdot size(c))^{\alpha }m^{\beta }}$${\displaystyle \log |{\mathcal {H}}_{n,m}|\leq (n\cdot size(c))^{\alpha }m^{\beta }}$${\displaystyle O(\epsilon m)-\log {\frac {1}{\delta }}}$${\displaystyle m\geq a\left({\frac {1}{\epsilon }}\log {\frac {1}{\delta }}+\left({\frac {(n\cdot size(c))^{\alpha })}{\epsilon }}\right)^{\frac {1}{1-\beta }}\right)}$${\displaystyle a>0}$${\displaystyle L}$${\displaystyle h}$${\displaystyle 1-\delta }$

^{オッカムとPACの学習可能性は同等ですが、オッカムのフレームワークは、接続詞[2]、}関連する変数が少ない接続詞^{[4] 、決定リスト[5]}などの古典的な問題のサンプル複雑性に対してより厳しい境界を生成するために使用できます。

^{オッカムアルゴリズムは、エラーが存在する場合のPAC学習、 [6] [7]}確率的概念、^[8]関数学習^[9]およびマルコフ非独立例^[10]でも成功することが示されています。

• 構造リスクの最小化
• 計算学習理論

• Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, MK「学習可能性とVapnik-Chervonenkis次元」Journal of the ACM, 36(4):929–865, 1989.