計算学習理論

計算学習理論は、学習を計算とサンプル複雑性の問題として扱い、どの概念が例から効率的に学習できるかを研究する。

Definition

計算学習理論は、例から概念を学習するために必要なデータと計算のリソースを研究する分野である。おそらく近似的に正しい (PAC) モデルでは、アルゴリズムが多項式個のサンプルから多項式時間内に、高い確率で正確な仮説を出力できる場合、概念クラスは学習可能であるとされる。

Scope

このトピックでは、学習可能性の形式モデルについて扱う。すなわち、多項式個の例と計算から、高い確率で高い精度に概念を学習できるかを問う「おそらく近似的に正しい (PAC) モデル」、誤り回数モデルとオンライン学習モデル、弱い学習可能性と強い学習可能性、およびブースティング、そして計算複雑性との関連である。学習の統計的およびアルゴリズム的実現可能性の両方に取り組む。

Core questions

• どの概念クラスが例から効率的に学習できるか？
• 概念の学習にはどれくらいのデータと計算が必要か？
• 弱い学習可能性と強い学習可能性の関係は何か？
• 学習可能性は計算複雑性とどのように関連するか？

Key theories

おそらく近似的に正しい (PAC) 学習

Valiantのモデルは、効率的なアルゴリズムが多項式個の例から高い確率で低誤差の仮説を生成できる場合に概念クラスを学習可能と定義し、学習可能性を正確な計算問題とした。

弱い学習可能性とブースティング

中心的な結果として、偶然よりわずかに優れた学習が可能なクラスは、強く学習可能であるということが示され、これは弱い学習器を正確な学習器に増幅するブースティングアルゴリズムに直接つながった。

統計的および計算的限界

学習可能性は、容量尺度に関連するサンプル複雑性と、計算的困難性の両方によって制限されるため、一部のクラスは統計的には学習可能であるものの、計算的には扱いにくい。

Clinical relevance

計算学習理論は、学習アルゴリズムが何を達成でき、何を達成できないかについての形式的な基礎を提供し、実践的な手法、特にブースティングに直接的なインスピレーションを与えた。ブースティングは、弱い学習器を強い学習器に結合できるかという問いから生まれたものである。この理論は、学習を厳密な計算科学分野として位置づける。

History

Valiantは1984年に「おそらく近似的に正しい (PAC) モデル」を導入し、学習に正確な計算的定義を与え、この分野を創設した。その後の研究により、サンプル複雑性の特性評価、ブースティングの動機となった弱い学習可能性と強い学習可能性の等価性、および学習の計算限界を示す困難性の結果が確立された。

Key figures

• Leslie Valiant
• Michael Kearns
• Robert Schapire

Seminal works

• valiant1984
• kearns1994
• vapnik1995

Frequently asked questions

「おそらく近似的に正しい」とはどういう意味ですか？

これは、ランダムなサンプルに対する高い確率で、学習器が近似的に正しい、つまり将来のデータに対して小さな誤差を持つ仮説を出力することを意味する。学習可能性は、多項式的にのみ増加する数の例と計算量からこれを達成することを要求する。

学習理論はどのようにブースティングにつながったのですか？

研究者たちは、ランダムな推測よりわずかに優れた学習器を、非常に正確な学習器に変えることができるかを問いました。弱い学習可能性と強い学習可能性が等価であることの証明は構成的であり、その構成が実践で広く使用されるブースティングアルゴリズムとなりました。