PAC学習と計算論的学習理論(Computatinonal Learning Theory)の文献まとめ

　PAC学習 (Probability Approximately Correct learning) とは、イギリスの理論計算機科学者 Leslie Valiant が1984年に以下の論文で初めて提唱した概念で、計算機科学の分野でそれまで研究されていた一般的な計算アルゴリズムの効率性・複雑性に対して、学習アルゴリズムに関しても同様の議論を行うために定義されたものです。

"A theory of the learnable"
Valiant, L. G. (1984). Communications of the ACM 1984 pp1134-1142.

　Valiant は、統計学の分野である「パターン認識(Pattern recognition)」や「決定理論(Decision theory)」の諸問題を、理論計算機科学の分野である計算複雑性理論(Computational Complexity Theory, CCT)と結びつけることで、学習アルゴリズムの持つ「複雑性」を定義しています。具体的に言うと、計算複雑性理論における「多項式時間で計算可能な解法が存在する問題(クラスP)」の定義と近しい形で、「実現可能な学習アルゴリズム」のクラスを定義しました。やがて、Valiantにより創始された学習アルゴリズムに関する一連の研究分野は計算論的学習理論(Computational Learning Theory, CLT)と呼ばれるようになり、今日に至ります。PAC学習の研究成果としては、例えば機械学習モデルの持つ汎化性能についての上界を与えるものなどがあり、近年ではソフトマージンSVMやDeep Learningの汎化誤差に関して、計算論的学習理論の研究者から、たくさんの関連論文が出ています。

　2019年2月現在、機械学習の隆盛下においても、計算論的学習理論やPAC学習に関する日本語の解説はあまりありませんが、「PAC learning」でGoogle検索すると、Introduction, Tutorioal, Surveyといった名前のつく英語の解説文献がそこそこ見つかります。個人的には、以下の文献がわかりやすかったです。

"Overview of the Probably Approximately Correct (PAC) Learning Framework" (David Haussler, UC Santa Cruz, July 2010)

"PAC Learnability" (Karl Stratos, TTIC, September 2016)

　このポストでは、Valiantが導入した計算論的学習理論における重要な2つの概念"true error(generalization error)", "PAC learnability"の定義を紹介し、参考論文を備忘として留めておきます。

定義1（true error or generalization error）
　学習したい"概念"クラス $\mathcal{C}$ とそれに対応づけられた確率変数の集合 $\mathcal{X}$ に対して、学習アルゴリズム $\mathcal{A}: X \in \mathcal{X} \mapsto c(X) \in \mathcal{C}$ を考える。ただし、 $\mathcal{X}$ に対して定義される確率分布を $\mathcal{D}$ とおく。確率分布 $\mathcal{D}$ に対して独立同分布となる $m$ コのサンプル $\left\{ x_1, \dots, x_m \right\}$ と、それに対応する"概念" $\left\{ c(x_1), \dots, c(x_m) \right\}$ のペアからなる訓練集合 $S := { \bigl\{ x_i, c(x_i) \bigr\} }_{i=1}^{m}$ によって学習を行い仮説 $h_{S}: \mathcal{X} \to C$ を立てる。このとき、仮説 $h_{S}$ の真の誤差(true error)あるいは汎化誤差(generalization error)を次式で定義する。

$$ error(h) := \underset{x ~ \sim~ \mathcal{D}}{Pr} \bigl( h_{S}(x) \neq c(x) \bigr) $$

定義2（PAC learnable）
　"概念"クラス $C$ がPAC学習可能であるとは、以下の条件を満たす学習アルゴリズム $\mathcal{A}$ が存在し、かつ学習に必要な訓練集合の大きさ $m:=|S|$ の下限に対して $m \geq poly(1/\varepsilon, 1/\delta, dim(\mathcal{X}), size(c))$ という関係を満たす多項式 $poly(\cdot)$ が存在することである。

$$ \forall \varepsilon, \delta \in [0, 1], ~~ \forall m \in \mathbb{N}, ~~ \forall c \in C, ~~ \forall \mathcal{D} ~on~ \mathcal{X}, \\ \underset{S ~ \sim~ \mathcal{D}^{m} \times C^{m}}{Pr} \Bigl( \underset{x ~ \sim~ \mathcal{D}}{Pr} \bigl( h_{S}(x) \neq c \bigr) \leq \varepsilon \Bigr) \geq 1 - \delta $$

※ PAC学習では、ある訓練集合 $S$ に対して、高い確率で「高い予測精度のモデル」を作ることができる学習アルゴリズム $\mathcal{A}$ を考える。"PAC Learnable"の定義は抽象的だが、確率分布によって定まる汎化誤差(true error)を念頭においており、PAC学習の分野の成果は、実際に使われている多くの確率モデル・学習アルゴリズムに対する誤差理論へ適用できる。

※ ある訓練集合 $S$ に対して仮説と学習アルゴリズムの関係は $h_{S} \gets \mathcal{A}(S)$ で与えられることに注意。

訓練集合 $S$ ：学習アルゴリズムを構成するためのデータ
仮説 $h$ ：学習アルゴリズム $\mathcal{A}$ の出力結果
概念 $c$ ：学習アルゴリズム $\mathcal{A}$ で出力されるもの
仮説集合 $\mathcal{H}$ ：仮説 $h$ の集合
概念集合 $\mathcal{C}$ ：概念 $c$ の集合

　ところで、「学習アルゴリズム $A$ 」という表現は、計算機科学・計算理論の色が根強く反映されていると思います。すなわち、数理統計学(確率＆解析学)のお気持ちとしては、学習は、「確率変数の集合間の写像(関数)を、有限集合から近似する計算操作」として解釈されますが、ここでは近似すべき関数の方が強調されているように感じます。