# 絶対に分かる機械学習理論 Navigation: [[index]] | [[_index|sources]] 出典: 佐藤竜馬(joisino)、2025-03-17、[ジョイジョイジョイ](https://joisino.hatenablog.com/entry/theory) 英語版: [A Gentle Introduction to Machine Learning Theory](https://data-processing.club/theory/) --- ## 概要 「なぜ訓練データで損失を下げれば、未見のテストデータでも性能が保証されるのか」という問いを出発点に、統計学の基礎(期待値・分散)だけから機械学習理論の最先端まで丁寧に解説した入門ブログ記事。マルコフの不等式 → チェビシェフの不等式 → ヘフディングの不等式 → ユニオンバウンド → 有限仮説クラスの汎化 → カバリングナンバーによる無限仮説クラスへの拡張 → 深層学習の理論(損失地形の盆地)という一本道で構成される。 --- ## 各節の内容 ### 期待値への集中 独立なデータの標本平均が期待値に集中する現象をサイコロの例で示す。サンプルサイズ $n$ を増やすにつれ、標本平均は期待値の周りに集まる。この直感的現象を以降の集中不等式で厳密化する。 ### マルコフの不等式 非負確率変数 $X$ と定数 $a > 0$ に対して: $\Pr(X \ge a) \le \frac{\mathbb{E}[X]}{a}$ 期待値よりも極端に大きな値を取る確率が低いことを表す。以降の集中不等式の基礎となる。 ### チェビシェフの不等式 確率変数 $X$ の期待値 $\mu$、分散 $\sigma^2$ に対して: $\Pr(|X - \mu| \ge k) \le \frac{\sigma^2}{k^2}$ 分散に依存するバウンド。どんな分布(正規・一様・二項など)にも成立するのが強み。$Y=(X-\mu)^2$ にマルコフの不等式を適用することで証明できる。標本平均 $\bar{X}$ の分散が $\mathrm{Var}(X)/n$ となることと組み合わせると、サンプルサイズ $n$ が増えるにつれ $\bar{X}$ が $\mu$ に集中することを定量的に示せる。弱点: 裾の確率を多項式($1/k^2$)のスピードでしか抑えられない。 ### ヘフディングの不等式 区間 $[a_i, b_i]$ に値をとる独立確率変数 $X_1, \ldots, X_n$ の標本平均 $\bar{X}$ に対して: $\Pr(|\bar{X} - \mathbb{E}[\bar{X}]| \ge t) \le 2\exp\!\left(-\frac{2n^2 t^2}{\sum_{i=1}^{n}(b_i - a_i)^2}\right)$ 裾の確率が $n$ と $t$ に対して**指数関数的**に減少する。チェビシェフの不等式と比べて、サンプルサイズ・ずれ幅が大きい場合に遥かに強力な保証を与える。証明はヘフディングの補題(指数モーメントの上界)とマルコフの不等式を組み合わせる。 ### モデルの評価 経験損失 $\hat{R}_n = \frac{1}{n}\sum_i \ell(X_i; \theta)$ と真のリスク $R = \mathbb{E}[\ell(X;\theta)]$ の関係。パラメータ $\theta$ があらかじめ固定されている評価の場合、各損失値 $Z_i = \ell(X_i;\theta)$ は独立であるため、集中不等式が直接適用でき、$|\hat{R}_n - R|$ を高確率で小さく抑えられる。 ### 訓練の場合には同じ議論は成り立たない 訓練では $\theta^* = \mathrm{argmin}_\theta \hat{R}_n(\theta)$ をデータを見た後に決定する。$\Theta^*$ は確率変数となり、各 $Z_i = \ell(X_i; \Theta^*)$ が独立でなくなるため、評価の場合の議論がそのまま適用できない。「サイコロを振った後に予測を宣言する」のと同じ問題。 ### ユニオンバウンド 任意の事象 $E_1, \ldots, E_N$ に対して: $\Pr(E_1 \cup \cdots \cup E_N) \le \Pr(E_1) + \cdots + \Pr(E_N)$ 独立でない場合にも使える。各仮説候補について個別に集中不等式で確率を抑え、それらをユニオンバウンドで合算することで、「全ての候補で経験損失が真のリスクに近い」という一様収束(uniform convergence)を達成する。 ### 候補の数が有限の場合 $m$ 個のパラメータ候補 $\theta_1, \ldots, \theta_m$ が固定(データとは独立に事前決定)されている場合、各候補に集中不等式を適用してユニオンバウンドをとることで: $\Pr\!\left(|\hat{R}_n(\Theta^*) - R(\Theta^*)| < k\right) \ge 1 - \frac{\sum_j \mathrm{Var}(Z_{\theta_j})}{nk^2}$ が保証される。ヘフディングの不等式を用いると、各候補の確率が指数的に小さいため、候補数が例えば 100 万個あってもユニオンバウンドで合算しても小さい。候補数の増加に対して必要なサンプルサイズは対数的な増加で十分。 ### 候補の数が無限の場合(カバリングナンバー) 実際のパラメータは $\mathbb{R}^d$ の連続空間をとるため候補は無限。$\varepsilon$-被覆と**カバリングナンバー** $N(\varepsilon, A)$ を導入して有限化する。 仮定: 1. $\Theta^* \in \mathcal{H} = \{\theta \in \mathbb{R}^d : \|\theta\| \le R\}$ 2. 損失は $[0, 1]$ の値をとる 3. 損失は $L$-リプシッツ連続: $\|\theta_1 - \theta_2\| \le \varepsilon \Rightarrow |\ell(X;\theta_1) - \ell(X;\theta_2)| \le L\varepsilon$ 上記の仮定のもとで、カバリングナンバーを $N(\mathcal{H};\varepsilon) \le \lceil\sqrt{d}R/\varepsilon\rceil^d$ と抑えた上でユニオンバウンドを適用すると、99% 以上の確率で: $|\hat{R}_n(\Theta^*) - R(\Theta^*)| \le 2\sqrt{\frac{d \log(200\lceil 4\sqrt{d}RnL\rceil)}{2n}}$ このバウンドから分かること: - 有用なバウンド(右辺 lt; 1$)を得るには $n$ が $d$ 以上のオーダーが必要 - バウンドは $n$ の平方根に大まかに反比例して小さくなる - パラメータ次元の 100 倍のデータがあれば訓練・テスト性能の差を約 $1/10$ 程度に抑えられる ### 深層学習の理論へ 深層学習では $d \gg n$(過パラメータ化)が一般的で、古典的バウンドが $\ge 1$ となり意味をなさない。提示される方向性: 損失地形の構造に着目する。 - 確率的勾配降下法は先鋭な谷ではなく**広大な盆地**(flat minima)に収束する - 盆地内では損失の変動が小さいため、各盆地を 1 つの代表点として扱える - 本質的な盆地の個数 $K$ が定数であれば、パラメータ次元 $d$ に依存しないバウンド: $1 - 2K\exp(-2nt^2) \quad \text{で誤差} \quad \sqrt{\frac{\log(200K)}{2n}} + \text{(盆地内の変動)}$ が成立する 現在未解決: 本質的な盆地が定数個であることの厳密な証明とその成立条件。 --- ## 主な定理・概念の一覧 | 概念 | 内容 | |---|---| | マルコフの不等式 | $\Pr(X \ge a) \le \mathbb{E}[X]/a$。非負確率変数の上端確率の上界 | | チェビシェフの不等式 | $\Pr(|X-\mu| \ge k) \le \sigma^2/k^2$。多項式減衰 | | ヘフディングの補題 | 有界確率変数の指数モーメントの上界 | | ヘフディングの不等式 | 標本平均の裾確率の指数関数的上界 | | ユニオンバウンド | $\Pr(\bigcup E_i) \le \sum \Pr(E_i)$。一様収束の基礎 | | $\varepsilon$-被覆 | 集合を有限個の開球で覆う | | カバリングナンバー $N(\varepsilon, A)$ | 最小の $\varepsilon$-被覆の要素数 | | 経験損失 $\hat{R}_n$ | 有限サンプル上の損失平均 | | 真のリスク $R$ | データ分布全体の期待損失 | | 汎化誤差 | $|R(\Theta^*) - \hat{R}_n(\Theta^*)|$ | | 一様収束 | 全候補で同時に経験損失が真のリスクに近い | | 過パラメータ化 | $d > n$、深層学習の典型的状況 | | 損失地形の盆地 | 確率的勾配降下法が収束する平坦な極小領域 | --- ## 関連 - [[汎化誤差バウンド]] — 本記事の中核となる理論的枠組み - [[集中不等式]] — マルコフ・チェビシェフ・ヘフディングの不等式 - [[PAC学習]] — 本記事が暗示する PAC フレームワーク - [[カバリングナンバー]] — 無限仮説クラスへの拡張手法 - [[深層学習の汎化]] — 過パラメータ化と損失地形の盆地の議論 - [[佐藤竜馬]] — 著者 ## 出典 - `.raw/articles/joisino-theory-2025-03-17.md` - URL: https://joisino.hatenablog.com/entry/theory