統計的学習理論１

PAC 学習

Foundation
Author

司馬博文

Published

1/10/2024

Modified

3/03/2024

概要
統計的機械学習には，「汎化」に価値を置く独特の決定理論的な枠組みが存在する．特に，第一義的には経験リスクを最小化すること，より正確には経験リスク最小化と正則化とをバランスよく目指す「構造的リスク最小化」が広く機械学習のモデリング指針として採用されている．

機械学習と統計学に別を設けるならば，いずれもデータから構造を発見することを目標とするとしても，前者は明示的なプログラムを伴わない「自動化」を念頭におくものであると言える．この人間による介入をなるべく少なくしたいという志向が「学習」の名前に表れている．

それ故，機械学習の理論としては，通常の統計的決定理論の枠組みよりも，汎化性能に力点を置いたものとなっている．これを，径数模型の教師あり学習の場合に関して述べる．

1 機械学習の形式化

1.1 記法と用語1

  • データサイズを \(n\in\mathbb{N}^+\) で表す．

  • 訓練データ (sample) の全体を \(S_n=\{z_i\}_{i=1}^n\subset\mathcal{X}\times\mathcal{Y}\) と表す．2 \(\mathcal{X}\) を入力空間，\(\mathcal{Y}\) を出力空間と呼ぶ．3

  • \(\mathcal{X},\mathcal{Y}\) はいずれも可測空間とし，可測関数 \(h\in\mathcal{L}(\mathcal{X},\mathcal{Y})\) を 推定量，部分集合 \(\mathcal{H}\subset\mathcal{L}(\mathcal{X};\mathcal{Y})\) を 仮説集合 (hypothesis set) という．4

  • \(l(\Delta_\mathcal{Y})=\{0\}\) を満たす関数 \(l:\mathcal{Y}^2\to\mathbb{R}_+\) を 損失関数 という．5

  • 写像 \(A:(\mathcal{X}\times\mathcal{Y})^n\to\mathcal{H}\) を（機械学習） アルゴリズム または学習者という．

以降，データはある真の分布 \(\mathbb{P}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})\) に従うものとし，\((X,Y)\sim\mathbb{P}\) と表す．サンプル \(S_n=\{z_i\}_{i=1}^n\) は \((X,Y)\sim\mathbb{P}\) の独立同分布な複製と仮定する．6

  • \(l:=1_{\Delta_\mathcal{Y}^\complement}\) は 0-1損失 と呼ばれ，主に分類問題で使われる．これについて，汎化誤差とは，7 \[ R(h)=\mathbb{E}[l(h(X),Y)]=\mathbb{P}[h(X)\ne Y] \]

  • \(\mathcal{Y}=\mathbb{R}^d\) とし，\(l(y_1,y_2)=\|y_1-y_2\|^2_2\) とした場合を 二乗損失 といい，主に回帰問題の最小二乗法などで用いられる．

1.2 汎化ギャップ

(generalization) error, training error8

定義 1 \(l:\mathcal{Y}^2\to\mathbb{R}_+\) を損失関数とする．

  1. 仮説 \(h\in\mathcal{H}\) の （汎化）誤差 または 危険 または 予測損失 とは， \[ R(h):=\mathbb{E}[l(h(X),Y)] \] をいう．

  2. 仮説 \(h\in\mathcal{H}\) のサンプル \(S_n=\{(x_i,y_i)\}_{i=1}^n\) に関する 訓練誤差 または 経験損失 とは， \[ \widehat{R}_n(h):=\frac{1}{n}\sum_{i=1}^n l(h(x_i),y_i) \] をいう．

  3. 差 \(\widehat{R}_n(h)-R(h)\) を 汎化ギャップ という．

アルゴリズム \(A\) にとって，汎化誤差は不可知であるが，訓練誤差は計算可能である．データが独立同分布に従うとする場合，経験損失は予測損失の不偏推定量であり，9 \(n\to\infty\) の漸近論もすでに準備が出来ている．

従って，不可知である予測損失の最小化の代わりに，経験損失を最小化する予測器 \[ \operatorname{ERM}_\mathcal{H}(S_n)\in\operatorname*{argmin}_{h\in\mathcal{H}}R_n(h) \] を構成すれば良い，という指針があり得る．この枠組みを 経験リスク最小化 (Empirical Risk Minimization) といい，PAC 学習は，この ERM の枠組みがどれほどの意味で正しいかの定量的な検証になっている．

1.3 経験リスク最小化の問題

ERM は一見，過学習の問題を孕んでいるように思える．

そこで，あらかじめ学習者 \(A\) の値域 \(\mathcal{H}\subset\mathcal{L}(\mathcal{X};\mathcal{Y})\) を制限することを考える．これを 帰納バイアス といい，正則化などの方法によって達成される．

しかし，この漸近論が提供してくれない消息は複数ある．

  1. 機械学習においては，仮説 \(h\) 自体がデータから決まる確率変数 \(h_{S_n}:\Omega\to\mathcal{H}\) である場合が多い．これを考慮した収束が欲しい．
  2. \(n\) が有限の場合に非漸近論的消息が欲しい．

そこで以降は，アルゴリズム \(A:(\mathcal{X}\times\mathcal{Y})^n\to\mathcal{H}\) を通じて，\(h_{S_n}:=A(S_n)\) と定まるとし，\(h_{S_n}\) を単に \(h\) ともかき，これをデータの関数とする．

この下で，\(\widehat{R}(h_{S_n})\) と \(R(h_{S_n})\) の関係を考える．

(金森敬文, 2015, p. 13) では，（決定論的な）仮説 \(h\in\mathcal{H}\) に関して，\(R(h)\) を損失，データから決まる仮説 \(h_{S_n}=A(S_n)\) に関して，\(\operatorname{E}[R(h_{S_n})]\) をリスクと呼び分けている．

損失のうち，特に 0-1損失 \[ l=1_{\Delta_\mathcal{Y}^\complement} \]

に関するものを誤差といい，この２語は殆ど交換可能な形で使う．その期待値をリスクと言う，という使い分けは一つ筋が通りそうである．

ただし，(Alquier, 2024), (Bousquet and Elisseeff, 2002), (Shalev-Shwartz and Ben-David, 2014) はいずれもリスクと誤差を交換可能な概念としている．

1.4 PAC 学習

機械学習を形式化する数理的枠組みのうち，PAC 学習 とは，

Probably Approximately Correct Learning

の略であり，(Valiant, 1984) によって提案されたものである．

機械学習における哲学的な問題として，「そもそも不可知なリスク \(R(h)\) を最小化できるのか？」「できるとしたら，どのような場合においてか？」というものがあった．10

agnostically PAC Learnable11

定義 2 集合 \(\mathcal{H}\subset\mathcal{L}(\mathcal{X};\mathcal{Y})\) が（不可知論的な意味で） PAC 学習可能 であるとは，ある関数 \[ m_\mathcal{H}:(0,1)^2\to\mathbb{N} \] とアルゴリズム \[ A:(\mathcal{X}\times\mathcal{Y})^{<\omega}\to\mathcal{H} \] が存在して，任意の \(\epsilon,\delta\in(0,1)\) と \(\mathbb{P}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})\) に対して，\(m_\mathcal{H}(\epsilon,\delta)\) よりも多くの i.i.d. サンプルが存在すれば，\(1-\delta\) 以上の確率で， \[ R(A(S_m))\le\min_{h\in\mathcal{H}}R(h)+\epsilon\quad(m\ge m_\mathcal{H}(\epsilon,\delta)) \] が成り立つことをいう．

PAC 学習とは，分布 \(\mathbb{P}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})\) に依らない真の誤差の評価を，確率論的に与えることを目的としており，Probably Approximately Correct の名前はその様子を端的に表現している．

(Valiant, 1984) による PAC 学習可能性の定義には，計算量と計算時間の制約も入っていた．12 (Haussler and Warmuth, 1993, p. 292) によれば，PAC 学習の枠組みにより，計算効率性の研究者が，機械学習のアルゴリズムにも目を向け，協業を始めるきっかけになったとしている．

agnostically PAC Learnable13

定理 1 仮説集合 \(\mathcal{H}\subset\mathcal{L}(\mathcal{X};\mathcal{Y})\) が有限ならば，（不可知論的な意味で）PAC 学習可能である．

1.5 定理 1 の証明

仮説集合 \(\mathcal{H}\) が 一様収束性 を持つことを示せば良い，というように議論する．

PAC 学習可能性（ 定義 2 ）は純粋に真の誤差の議論であるが，訓練誤差との関係に注目して示すのである．

\(\epsilon\)-representative, uniform convergence property14

定義 3  

  • 訓練データ \(S_n=\{x_i\}_{i=1}^n\) が \(\epsilon\)-代表的 であるとは，次を満たすことをいう： \[ \lvert\widehat{R}_n(h)-R(h)\rvert\le\epsilon\quad(h\in\mathcal{H}). \]
  • 仮説集合 \(\mathcal{H}\) が 一様収束性 を持つとは，任意の \(\epsilon,\delta\in(0,1)\) と \(\mathbb{P}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})\) について，十分大きな訓練データ \(S_m\) を取れば，\(1-\delta\) 以上の確率で \(S_m\) は \(\epsilon\)-代表的であることをいう．
  • このときのサンプル数の増加の速さを \(m_\mathcal{H}^{\mathrm{UC}}(\epsilon,\delta)\) と書く．

補題 1 訓練データ \(S_n\) が \(\epsilon/2\)-代表的ならば，任意の経験リスク最小化学習器 \[ h_{S_n}\in\operatorname*{argmin}_{h\in\mathcal{H}}\widehat{R}_n(h) \] は \[ R(h_{S_n})\le\min_{h\in\mathcal{H}}R(h)+\epsilon \] を満たす．

特に，\(m_\mathcal{H}^{\mathrm{UC}}(\epsilon,\delta)\) に関して一様収束性を持つならば，\(m_\mathcal{H}(\epsilon/2,\delta)\le m_\mathcal{H}^{\mathrm{UC}}(\epsilon,\delta)\) に関して（不可知論的な意味で）PAC 学習可能である．

\(h_{S_n}\) の最小性に注意して，

\[ \begin{align*} R(h_{S_n})&\le\widehat{R}_n(h_{S_n})+\frac{\epsilon}{2}\\ &\le\widehat{R}_n(h)+\frac{\epsilon}{2}\\ &\le R(h)+\epsilon. \end{align*} \]

こうして，PAC 学習の枠組みは，（今回のケースでは）ERM の枠組みを肯定する結果を導いている．

これは，一様収束性が成り立つ仮説集合 \(\mathcal{H}\) については，経験リスクは真のリスクに十分近いことを意味している．このような \(\mathcal{H}\) を Glivenko-Cantelli クラス (Glivenko, 1933), (Cantelli, 1933) ともいう．15

こうして，

1.6 PAC 学習の基本定理

実は，分類問題においては，一様収束性は，PAC 学習可能性を特徴付ける．

この証明は，VC 次元 (V. N. Vapnik and Chervonenkis, 1971) の概念による．

しかし，一般の学習問題においても同じ状況というわけではない (Shalev-Shwartz et al., 2010)．多クラス分類でさえ同値性は崩れる (Daniely et al., 2011)．

Fundamental Theorem of Statistical Machine Learning16

定理 2 分類問題 \(\mathcal{Y}=2\) を 0-1 損失 \(l=1_{\Delta_\mathcal{Y}^\complement}\) で考えるとする．仮説集合 \(\mathcal{H}\subset\mathcal{L}(\mathcal{X};\mathcal{Y})\) について，次は同値：

  1. \(\mathcal{H}\) は一様収束性を持つ．
  2. \(\mathcal{H}\) は（不可知論的な意味で）PAC 学習可能である．
  3. \(\mathcal{H}\) は有限な VC 次元を持つ．

1.7 Bayes ルール

Bayes error, Bayes rule17, excess risk / regret

定義 4 損失関数 \(l\) に対して， \[ \begin{align*} R^*&:=\inf_{h\in\mathcal{L}(\mathcal{X};\mathcal{Y})}R(h)\\ &=\inf_{h\in\mathcal{L}(\mathcal{X};\mathcal{Y})}\mathbb{E}[l(h(X),Y)] \end{align*} \] を Bayes 誤差 という．仮に右辺の下限が達成される \(h^*\in\mathcal{L}(\mathcal{X};\mathcal{Y})\) が存在するとき，これを Bayes 最適学習則 またはベイズルール という． \[ \mathcal{E}(h):=R(h)-R^* \] を 超過損失 という．

\(\mathcal{Y}=2\) の場合，任意の \(\mathbb{P}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})\) に対して， \[ h^*(x):=\begin{cases} 1&\mathbb{P}[Y=1\,|\,X=x]\ge\frac{1}{2},\\ 0&\mathrm{otherwise} \end{cases} \] は Bayes 最適学習則である．

\[ \begin{align*} \mathcal{E}(\widehat{h}_S)&=R(\widehat{h}_S)-R(h^*)\\ &=\biggr(R(\widehat{h}_S)-\inf_{h\in\mathcal{H}}R(h)\biggl)+\biggr(\inf_{h\in\mathcal{H}}R(h)-R(h^*)\biggl). \end{align*} \] 第一項を 推定誤差，第二項を 近似誤差 という．19

ここから，\(\overline{h}\) を \(\inf_{h\in\mathcal{H}}R(h)\) を達成する oracle machine とすると，推定誤差はさらに２項に分解して評価できる： \[ \begin{align*} &R(\widehat{h}_n)-\inf_{h\in\mathcal{H}}R(H)\\ &=R(\widehat{h}_n)-R(\overline{h})\\ &=\underbrace{\widehat{R}_n(\widehat{h}_n)-\widehat{R}_n(\overline{h}_n)}_{\le0}+R(\widehat{h}_n)-\widehat{R}_n(\widehat{h}_n)+\widehat{R}_n(\overline{h})-R(\overline{h})\\ &\le\biggl|\widehat{R}_n(\widehat{h}_n)-R(\widehat{h}_n)\biggr|+\biggl|\widehat{R}_n(\overline{h})-R(\overline{h})\biggr|. \end{align*} \]

2 統計的決定理論

PAC 学習の枠組みを相対的に理解するため，統計的決定理論の目線から，同じ形式を見直してみる．

2.1 枠組み

最大の違いは，データ生成分布 \(\mathbb{P}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})\) にパラメトリックな仮定をおく点である．このとき，組 \((\mathcal{X}\times\mathcal{Y},(\mathbb{P}_\theta)_{\theta\in\Theta})\) を 統計的実験 ともいう．

損失関数 \(l:\mathcal{Y}\times\mathcal{Y}\to\mathbb{R}_+\) は，より一般には，決定空間 \(\mathcal{Z}\) に対して， \[ l:\mathcal{Y}\times\mathcal{Z}\to\mathbb{R}_+ \] と定まるものである．

2.2 一様最強力検定

学習ではなく，検定の文脈では，PAC 同様全てのデータ生成分布 \(\mathbb{P}\in\mathcal{P}()\) を考えるが，リスクが小さいことを要請する．

3 PAC bound

3.1 定理

PAC bound20

定理 3 仮説集合 \(\mathcal{H}\) が有限であるとする：\(\#\mathcal{H}=:M<\infty\)． このとき，任意の \(\epsilon\in(0,1)\) について， \[ \mathbb{P}\left[\forall_{h\in\mathcal{H}}\;R(h)-\widehat{R}(h)\le C\sqrt{\frac{\log\frac{M}{\epsilon}}{2n}}\right]\ge1-\epsilon. \]

仮説 \(\mathcal{H}\) の数 \(M\) を増やすごとに，訓練データ数 \(n\) は \(\log M\) のオーダーで増やす必要がある，ということになる．

3.2 \(\biggl|\widehat{R}_n(\widehat{h}_n)-R(\widehat{h}_n)\biggr|\) の評価

3.3 \(\biggl|\widehat{R}_n(\overline{h})-R(\overline{h})\biggr|\) の評価

3.4 定理の一般化21

  • 一般の \(\mathcal{H}\subset\mathcal{L}(\mathcal{X};\mathcal{Y})\) への拡張は，VC次元の理論を用いて行われる（ 定理 2 など）．

  • バウンドの変形に，Rademacher 複雑性も使われる．

  • 現実との乖離：現代の深層学習では \(M\) が極めて大きくなり，PAC 不等式はほとんど意味をなさない．これを包括できる理論が試みられている．

References

Alquier, P. (2024). User-friendly introduction to PAC-bayes bounds. Foundations and Trends in Machine Learning, 17(2), 174–303.
Bousquet, O., and Elisseeff, A. (2002). Stability and generalization. Journal of Machine Learning Research, 2, 499–526.
Cantelli, F. P. (1933). Sulla determinazione empirica della leggi di probabilità. Giornale Dell’Instituo Italiano Degli Attuari, 4(1), 421–424.
Daniely, A., Sabato, S., Ben-David, S., and Shalev-Shwartz, S. (2011). Multiclass learnability and the ERM principle. In S. M. Kakade and U. von Luxburg, editors, Proceedings of the 24th annual conference on learning theory,Vol. 19, pages 207–232. Budapest, Hungary: PMLR.
Devroye, L., Györfi, L., and Lugosi, G. (1996). A probabilistic theory of pattern recognition,Vol. 31. Springer New York.
Glivenko, V. I. (1933). Sulla determinazione empirica della leggi di probabilità. Giornale Dell’Instituo Italiano Degli Attuari, 4(1), 92–99.
Haussler, D., and Warmuth, M. (1993). Foundations of knowledge acquisition: Machine learning. In A. L. Meyrowitz and S. Chipman, editors, pages 291–312. Springer New York.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2018). Foundations of machine learning. MIT Press.
Shalev-Shwartz, S., and Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge University Press.
Shalev-Shwartz, S., Shamir, O., Srebro, N., and Sridharan, K. (2010). Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11(90), 2635–2670.
Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27(11), 1134–1142.
Vapnik, Vladimir N. (1998). Statistical learning theory. Wiley-Blackwell.
Vapnik, V. N., and Chervonenkis, A. Ya. (1971). Necessary and sufficient conditions for the uniform convergence of means to their expectations. Theory of Probability and Its Applications, 16(3), 264–280.
金森敬文. (2015). 統計的学習理論. 講談社.

Footnotes

  1. (Mohri et al., 2018, pp. 9–10) と (Shalev-Shwartz and Ben-David, 2014, pp. 13–14), (Alquier, 2024) を参考にした．↩︎

  2. これは訓練セット (training set) ともいう (Shalev-Shwartz and Ben-David, 2014, p. 14)．↩︎

  3. (Bousquet and Elisseeff, 2002) の用語に一致する．(Alquier, 2024, p. 2) では，\(\mathcal{X}\) を object set，\(\mathcal{Y}\) を label set と呼んでいる．(Shalev-Shwartz and Ben-David, 2014, pp. 13–14) は \(\mathcal{X}\) を domain set，\(\mathcal{Y}\) を label set と呼ぶ．↩︎

  4. (Valiant, 1984) では，\(\mathcal{Y}=2\) の場合，元 \(h\in\mathcal{H}\) を 概念 (concept) ともいう．その他の場合を predicate とも呼んでいる．(Shalev-Shwartz and Ben-David, 2014, p. 14) では predictor, predictino rule, classifier とも呼ぶとしている．↩︎

  5. (Alquier, 2024, p. 177) を参考にした．\(\Delta_\mathcal{Y}:=\left\{(y',y)\in\mathcal{Y}^2\mid y=y'\right\}\) を対角集合とした．↩︎

  6. (Alquier, 2024) 第4章ではこの i.i.d. 仮定を外している．↩︎

  7. (Shalev-Shwartz and Ben-David, 2014, p. 24) などでは，\(\mathcal{Y}=2\) として分類問題を考えていることもあり，専らこの損失を考えている．↩︎

  8. (Alquier, 2024, p. 4), (Mohri et al., 2018, p. 10)，(金森敬文, 2015, p. 7) を参考にした．(Shalev-Shwartz and Ben-David, 2014, p. 14) でも，generalization error, risk, error，さらには loss のいずれの名前でも呼ぶし，training error と empirical error /risk とも交換可能に使う，としている．↩︎

  9. (Mohri et al., 2018, pp. 10–11), (金森敬文, 2015, p. 8) など．↩︎

  10. (Haussler and Warmuth, 1993, p. 263) にある Valiant 本人による解説に，その哲学的なモチベーションがよく表れている．↩︎

  11. (Shalev-Shwartz and Ben-David, 2014, p. 25) 定義3.3，(Mohri et al., 2018, p. 22) 定義2.14 など．元々の (Valiant, 1984) の定義では，\(m\) と計算時間の増加レートは \(1/\ep,1/\delta\) の多項式以下であるという制限もあった．↩︎

  12. (Shalev-Shwartz and Ben-David, 2014, p. 28) も参照．↩︎

  13. (Shalev-Shwartz and Ben-David, 2014, p. 34) 系4.6 など．↩︎

  14. (Shalev-Shwartz and Ben-David, 2014, pp. 31–32) 定義3.1 と 定義3.3．↩︎

  15. (Shalev-Shwartz and Ben-David, 2014, p. 35) など．↩︎

  16. (Shalev-Shwartz and Ben-David, 2014, p. 48) 定理6.7 など．↩︎

  17. (Mohri et al., 2018, p. 22) 定義2.15，(金森敬文, 2015, p. 9) を参考．↩︎

  18. (Shalev-Shwartz and Ben-David, 2014, p. 25) など．↩︎

  19. (金森敬文, 2015, p. 17) を参考．↩︎

  20. (Alquier, 2024, p. 7) 定理1.2 など．↩︎

  21. (Devroye et al., 1996) 第11, 12章 参照．(Vladimir N. Vapnik, 1998)．↩︎