統計学習理論 — なぜ学習は汎化するのか

有限個の例しか見ていないのに、なぜ未知のデータに答えられるのか。Hoeffdingの不等式からVC次元・PAC学習まで汎化の保証を1から組み立て、それが深層学習の前で破れた経緯と、評価設計での使いどころまでを解説する。

Understanding Deep Learning Requires Rethinking Generalization

過去問が解けても、本番で受かるとは限らない

資格試験で過去問を10年分やり、全問正解できるようになったとします。本番でも受かるでしょうか。答えは「やり方による」です。解き方を身につけたのなら受かる。答えの記号を丸暗記しただけなら、本番では何も残っていません。

機械学習でも同じです。全データを表に持っておいて「見たことがある入力にはその答えを返す」規則を作れば訓練誤差はゼロですが、誰もそれを学習とは呼びません。知りたいのはまだ見ていないデータでどうなるかだからです。

不思議なのは、それでも学習がしばしばうまくいくことの方です。有限個の例しか見ていないのに、無限にある入力への答えを言い当ててしまう。なぜその飛躍が許されるのか。1970年代から積み上がった回答が一様収束・VC次元・PAC学習という道具立てで、2017年前後、その道具は深層学習の前で音を立てて破れます。この記事はその一部始終です。

「汎化する」とは、2つの数の差が小さいということ

学習が選んだ規則を仮説 $h$ と呼び、その良し悪しを2つの数で測ります。

$D$ は世の中のデータが従う真の分布、$\ell$ は間違いを測る関数（0-1損失なら外したら1・当たったら0）、$n$ は手元の例の数です。式(1)の左が本番の成績（真の誤差＝汎化誤差）、右が過去問の成績（経験誤差＝訓練誤差）。世界中のデータでの平均と、手元の $n$ 件での平均、と言っているだけです。つまり「汎化する」とは、この2つの平均点がほとんど同じ値に落ち着く、というだけの意味になります。

下げたいのは $R(h)$ ですが、$D$ が分からないので計算できません。計算できるのは $\hat{R}(h)$ だけ。だから理論の仕事はひとつに絞られます。

$$R(h) \;\le\; \hat{R}(h) + (\text{計算できる何か})$$

この形の不等式を作ること。右辺の「何か」を複雑さの罰金と呼びます。手元の成績に罰金を足せば本番の成績の上限になる、という保険証書を発行するのが統計学習理論です。つまり読み方は「本番の点 ≤ 過去問の点 ＋ 下駄」で、その下駄の大きさを手元の情報だけで見積もれれば、まだ見ていないデータでの成績に天井をつけられます。その罰金が何を捉えようとしているのかを、先に目で見ておきましょう。

仮説が1つだけなら、これはコイン投げの話

データを見る前に仮説を1つ決め打ちしたとします。すると各例での損失は独立同分布の確率変数になり、$\hat{R}(h)$ はその標本平均、$R(h)$ はその期待値です。大数の法則が効く、教科書どおりの状況。近づく速さを定量化するのが Hoeffdingの不等式で、損失が $[0,1]$ に収まるとき次が成り立ちます。

「過去問の点と本番の点が $\epsilon$ 以上ずれる確率は、例の数 $n$ が増えると指数関数的に潰れる」。つまり、例を集めれば集めるほど「手元の点数はほぼ実力どおりだ」と言い切ってよくなり、その確信は例の数に対して急激に強まる、ということです。指数の中身が $\epsilon^2$ なのが効き所で、精度を2倍にしたければ例は4倍要ります。$\epsilon$ について解けば、確率 $1-\delta$ 以上で $R(h) \le \hat{R}(h) + \sqrt{\log(2/\delta)/(2n)}$。$\delta$ は「保険が外れる確率」です。$n=10{,}000$、$\delta=0.05$ なら罰金は約1.4ポイント。悪くない保証に見えます。

「選ぶ」という行為が代償を生む

しかしこの話には嘘が混ざっています。「データを見る前に $h$ を決めた」という前提です。現実の学習はその逆で、データを見てから候補の中で $\hat{R}$ が最小のものを選ぶ。選ばれた $\hat{h}$ はデータの関数であり、もはや固定された仮説ではありません。

なぜこれが問題かはコインで分かります。100人にコインを10回ずつ投げさせ、いちばん表が多かった人を選ぶ。その人が9回表を出したとして、コインが歪んでいる証拠になるでしょうか。なりません。「いちばん良い人を選ぶ」という操作自体が、偶然の当たりを拾い上げるからです。学習も同じで、多数の仮説から訓練誤差最小のものを選べば、その値は運の良さの分だけ実力より良く見えます。

対策は、選ばれ方に依存しない保証を要求することです。仮説集合 $\mathcal{H}$ のすべての $h$ について同時に成り立つ不等式を作る——これが一様収束です。候補が有限個なら和集合上界（どれか1つが外れる確率は各々が外れる確率の合計以下）で片が付き、確率 $1-\delta$ 以上ですべての $h \in \mathcal{H}$ に対して

$|\mathcal{H}|$ は候補の個数です。式(3)は「候補が多いほど罰金が増えるが、増え方は対数なので緩い」と言っています。つまり、たくさん試したなら試した分だけ最高点を割り引いて読め、ただしその割引はデータを増やせば取り返せる、という取り決めです。候補を1000倍にしても中身は $\log 1000 \approx 6.9$ しか増えず、しかも全体は $\sqrt{n}$ で割られる。表現力とデータ量のトレードオフが、これ以上ないほど素朴な形で式に現れています。