オッカム学習
計算学習理論では、 Occam学習はアルゴリズム学習のモデルであり、学習者の目的は受信したトレーニングデータの簡潔な表現を出力することです。これは、学習者がテストセットの予測力で評価される、おそらくほぼ正しい（PAC）学習と密接に関連しています。
Occamの学習可能性はPACの学習を意味し、さまざまな概念クラスについては、逆も成り立ちます。PACの学習可能性はOccamの学習可能性を意味します。
前書き
Occam LearningはOccamのカミソリにちなんで名付けられました。これは、他のすべての条件が同じであれば、より長い説明よりも観測データの短い説明の方が好ましいと述べた原則です。 Occam学習の理論は、この原則の形式的および数学的な正当化です。 Blumer等によって最初に示されました。 Occam学習はPAC学習を意味します。これは、計算学習理論における学習の標準モデルです。言い換えれば、（出力仮説の） 節約は予測力を意味します。
Occam学習の定義
コンセプトクラスC {\ displaystyle {\ mathcal {C}}}のコンセプトc {\ displaystyle c}の簡潔さは、次の最短ビット文字列の長さsize（c）{\ displaystyle size（c）}で表現できます。 C {\ displaystyle {\ mathcal {C}}}でc {\ displaystyle c}を表すことができます。 Occam学習は、学習アルゴリズムの出力の簡潔さを、見えないデータの予測力に結び付けます。
C {\ displaystyle {\ mathcal {C}}}およびH {\ displaystyle {\ mathcal {H}}}を、それぞれターゲットコンセプトと仮説を含むコンセプトクラスとします。次に、定数α≥0{\ displaystyle \ alpha \ geq 0}および0≤β1 {\ displaystyle 0 \ leq \ beta 1}の場合、学習アルゴリズムL {\ displaystyle L}は（α、β） {\ displaystyle（\ alpha、\ beta）}- H {\ displaystyle {\ mathcal {H}}}を使用したC {\ displaystyle {\ mathcal {C}}}のOccamアルゴリズム 、S = {x1、 …、xm} {\ displaystyle S = \ {x_ {1}、\ dots、x_ {m} \}}の概念に従ってラベル付けされたm {\ displaystyle m}サンプルc∈C{\ displaystyle c \ in {\ mathcal {C}}}、L {\ displaystyle L}は、仮説h∈H{\ displaystyle h \ in {\ mathcal {H}}}を出力します。
- h {\ displaystyle h}は、S {\ displaystyle S}のc {\ displaystyle c}（つまり、h（x）= c（x）、∀x∈S{\ displaystyle h（x）= c（ x）、\ forall x \ in S}）、および
- size（h）≤（n⋅size（c））αmβ{\ displaystyle size（h）\ leq（n \ cdot size（c））^ {\ alpha} m ^ {\ beta}}
ここで、n {\ displaystyle n}は、サンプルx∈S{\ displaystyle x \ in S}の最大長です。 Occamアルゴリズムは、n {\ displaystyle n}、m {\ displaystyle m}、およびsize（c）。{\ displaystyle size（c）の時間多項式で実行される場合、 効率的と呼ばれます。}概念クラスC {\ displaystyle {\ mathcal {C}}}は、C {\ displaystyle {\ mathcal {C}}}に効率的なOccamアルゴリズムが存在する場合、仮説クラスH {\ displaystyle {\ mathcal {H}}}に関して学習可能なOccamです。 H。{\ displaystyle {\ mathcal {H}}を使用します。}
OccamとPAC学習の関係
オッカムの学習可能性はPACの学習可能性を意味します。ショー：
定理（ Occam学習はPAC学習を意味します ）
L {\ displaystyle L}を効率的な（α、β）{\ displaystyle（\ alpha、\ beta）}にする -H {\ displaystyle {\ mathcalを使用したC {\ displaystyle {\ mathcal {C}}}のOccamアルゴリズム{H}}}。次に、定数a> 0 {\ displaystyle a> 0}が存在し、0 ϵ、δ1 {\ displaystyle 0 \ epsilon、\ delta 1}の場合、任意の分布D {\ displaystyle {\ mathcal {D}}}、m≥a（1ϵlog1δ +（（n⋅size（c））α）ϵ）11−β）{\ displaystyle m \ geq a \ left（{\ frac {1} {\イプシロン}} \ log {\ frac {1} {\ delta}} + \ left（{\ frac {（n \ cdot size（c））^ {\ alpha}）} {\ epsilon}} \ right）^ { \ frac {1} {1- \ beta}} \ right）} D {\ displaystyle {\ mathcal {D}}}から描画され、概念c∈C{\ displaystyle c \ in {\ mathcal {長さn {\ displaystyle n}ビットのC}}}、アルゴリズムL {\ displaystyle L}は、error（h）のような仮説h∈H{\ displaystyle h \ in {\ mathcal {H}}}を出力します≤ϵ {\ displaystyle error（h）\ leq \ epsilon}、少なくとも1-δ{\ displaystyle 1- \ delta}の確率。
ここで、error（h）{\ displaystyle error（h）}は、概念c {\ displaystyle c}および分布D {\ displaystyle {\ mathcal {D}}}に関するものです。これは、アルゴリズムL {\ displaystyle L}が、仮説クラスH {\ displaystyle {\ mathcal {H}}}を使用したコンセプトクラスC {\ displaystyle {\ mathcal {C}}}のPAC学習器であることを意味します。もう少し一般的な公式は次のとおりです。
定理（ Occam学習はPAC学習、カーディナリティバージョンを意味します ）
0 ϵ、δ1 {\ displaystyle 0 \ epsilon、\ delta 1}としましょう。 L {\ displaystyle L}を、固定されているが未知の分布D {\ displaystyle {\ mathcal {D}}}から引き出され、概念c∈C{各長さn {\ displaystyle n}ビットの\ displaystyle c \ in {\ mathcal {C}}}、仮説h∈Hn、m {\ displaystyle h \ in {\ mathcal {H}} _ {n、m }}ラベル付きサンプルと一致しています。次に、定数b {\ displaystyle b}が存在し、log| Hn、m | ≤bϵm-log1δ {\ displaystyle \ log | {\ mathcal {H}} _ {n、m} | \ leq b \ epsilon m- \ log {\ frac {1} {\ delta}}}の場合、L {\ displaystyle L}は仮説h∈Hn、m {\ displaystyle h \ in {\ mathcal {H} } _ {n、m}}、少なくとも1-δ{\ displaystyle 1- \ delta}の確率でerror（h）≤ϵ {\ displaystyle error（h）\ leq \ epsilon}となる。
上記の定理は、Occam学習がPAC学習に十分であることを示していますが、 必要性については何も述べていません。 BoardとPittは、さまざまなコンセプトクラスについて、Occam学習がPAC学習に実際に必要であることを示しています。彼らは、 例外リストの下で多項式的に閉じられている概念クラスについて、 PACの学習可能性はその概念クラスのOccamアルゴリズムの存在を意味することを証明しました。例外リストの下で多項式的に閉じられている概念クラスには、ブール式、回路、決定論的有限オートマトン、決定リスト、決定木、および他の幾何学的に定義された概念クラスが含まれます。
コンセプトクラスC {\ displaystyle {\ mathcal {C}}}は、コンセプトc∈C{\の表現が与えられるような多項式時間アルゴリズムA {\ displaystyle A}が存在する場合、例外リストの下で多項式的に閉じられます。 displaystyle c \ in {\ mathcal {C}}}および例外の有限リストE {\ displaystyle E}は、概念c'∈C{\ displaystyle c '\ in {\ mathcal {C}}}の表現を出力しますコンセプトc {\ displaystyle c}とc '{\ displaystyle c'}は、セットE {\ displaystyle E}を除いて一致します。
Occam学習がPAC学習を意味することの証明
まず、カーディナリティバージョンを証明します。仮説h∈H 悪い場合は、再度（H）エラーエラー（H）≥ε{\ displaystyle誤差（H）\ GEQ \イプシロン}、{\ displaystyle {{\ mathcal {H}}で\ displaystyleさh \}を呼び出しますerror（h）}は、真の概念c {\ displaystyle c}および基礎となる分布D {\ displaystyle {\ mathcal {D}}}に関するものです。サンプルのセットS {\ displaystyle S}がh {\ displaystyle h}と一致する確率は、次の独立性により、最大で（1ϵ）m {\ displaystyle（1- \ epsilon）^ {m}}です。サンプル。ユニオン境界により、Hn、m {\ displaystyle {\ mathcal {H}} _ {n、m}}に悪い仮説が存在する確率は最大で| Hn、m |（1−ϵ）m {\ displaystyle | {\ mathcal {H}} _ {n、m} |（1- \ epsilon）^ {m}}。log| Hn、m |≤O（の場合、δ{\ displaystyle \ delta}より小さいϵm）−log1δ {\ displaystyle \ log | {\ mathcal {H}} _ {n、m} | \ leq O（\ epsilon m）-\ log {\ frac {1} {\ delta}}}これで、上記の2番目の定理の証明は終わりです。
2番目の定理を使用して、1番目の定理を証明できます。 （α、β）{\ displaystyle（\ alpha、\ beta）}-Occamアルゴリズムがあるので、これは、L {\ displaystyle L}が出力する仮説は最大で（n⋅size（c） ）αmβ{\ displaystyle（n \ cdot size（c））^ {\ alpha} m ^ {\ beta}}ビット、したがってlog| Hn、m |≤（n⋅size（c））αmβ{\ displaystyle \ log | {\ mathcal {H}} _ {n、m} | \ leq（n \ cdot size（c））^ {\ alpha} m ^ {\ beta}}。これはO（ϵm）−log1δ {\ displaystyle O（\ epsilon m）-\ log {\ frac {1} {\ delta}}}未満です。m≥a（1ϵlog1δ +（（n ⋅size（c））α）ϵ）11−β）{\ 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）}定数a> 0 {\ displaystyle a> 0}。したがって、カーディナリティバージョンの定理により、L {\ displaystyle L}は、少なくとも1-δ{\ displaystyle 1- \ delta}の確率で一貫した仮説h {\ displaystyle h}を出力します。これで、上記の最初の定理の証明が終わりました。
一般的な問題のサンプルの複雑さを改善する
OccamとPACの学習可能性は同等ですが、Occamフレームワークを使用して、接続詞、関連する変数がほとんどない接続詞、決定リストなど、古典的な問題のサンプルの複雑さをより厳密に制限できます。
拡張機能
Occamアルゴリズムは、エラー、確率論的概念、関数学習、マルコフの非独立例がある場合のPAC学習にも成功することが示されています。
