# 集中不等式 Navigation: [[index]] | [[_index|concepts]] ## 定義 集中不等式(concentration inequality)とは、確率変数(またはその関数)がその期待値の周りに集中する現象を定量的に表す不等式の総称である。「サンプルサイズを増やすにつれて標本平均が期待値に近づく」という大数の法則を、確率的な精度付きで厳密化する。機械学習理論における汎化誤差バウンドの主要な道具立てをなす。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## マルコフの不等式 非負の確率変数 $X$ と任意の定数 $a > 0$ に対して: $\Pr(X \ge a) \le \frac{\mathbb{E}[X]}{a}$ それ自体は集中不等式ではないが、チェビシェフの不等式やヘフディングの不等式など他の集中不等式の証明の基礎として用いられる。直感: 期待値よりも $a$ 倍以上大きな値をとる確率が高ければ、その項だけで期待値を超えてしまい矛盾する。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) **証明の概要**: $\mathbb{E}[X] = \int_0^\infty x\,p(x)\,dx \ge \int_a^\infty x\,p(x)\,dx \ge a\Pr(X \ge a)$。両辺を $a > 0$ で割る。 ## チェビシェフの不等式 確率変数 $X$ の期待値 $\mu$、分散 $\sigma^2$ に対して任意の $k > 0$ で: $\Pr(|X - \mu| \ge k) \le \frac{\sigma^2}{k^2}$ - 正規分布・一様分布・二項分布など、どんな分布でも成立する(分布非依存) - 裾の確率を多項式($1/k^2$)のスピードで抑えるため、緩い評価になりやすい - $Y = (X-\mu)^2$ にマルコフの不等式を適用して証明する - 標本平均 $\bar{X}$ の分散は $\mathrm{Var}(X)/n$ となるため、サンプルサイズ $n$ を増やすにつれ集中が進む (Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## ヘフディングの不等式 区間 $[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)$ すべての $X_i$ が $[0,1]$ 上の場合: $\Pr(|\bar{X} - \mathbb{E}[\bar{X}]| \ge t) \le 2\exp(-2nt^2)$ - 裾の確率が $n$ と $t$ に対して**指数関数的**に減少する - チェビシェフより遥かに強力(例: $n=100, t=1.5$ でチェビシェフは約 1.3% 以下、ヘフディングは $\approx 3 \times 10^{-8}$) - **証明手法**: ヘフディングの補題(有界確率変数の指数モーメントを $\exp(s^2(b-a)^2/8)$ で上界する)→ 積の形に展開(独立性) → マルコフの不等式 → $s$ を最適化 (Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ### ヘフディングの補題 $a \le X \le b$、$\mathbb{E}[X] = 0$ の確率変数に対し任意の $s \in \mathbb{R}$ で: $\mathbb{E}[e^{sX}] \le \exp\!\left(\frac{s^2(b-a)^2}{8}\right)$ 証明: $e^{sx}$ の凸性による線形上界 → 期待値をとる → $L(h) = \frac{ha}{b-a} + \ln(1 + \frac{a - e^h a}{b-a})$ を定義しテイラー展開で $L(h) \le h^2/8$ を示す。 ## 各不等式の比較 | 不等式 | 使用情報 | 裾の減衰 | 特徴 | |---|---|---|---| | マルコフ | 期待値のみ | $1/a$ | 証明の基礎部品 | | チェビシェフ | 期待値・分散 | $1/k^2$ (多項式) | 分布非依存 | | ヘフディング | 有界性・独立性 | $\exp(-nt^2)$ (指数) | 強力・有界変数に限定 | ## 機械学習理論での役割 集中不等式は汎化誤差バウンドの核心部品として機能する。評価の場合は直接適用でき、訓練の場合は**ユニオンバウンド**と組み合わせて有限(または有限化された)仮説クラス全体への一様収束を保証する。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## 横断的知見 - チェビシェフの不等式の多項式減衰 vs ヘフディングの不等式の指数減衰という対比は、候補数が多くなる場合に決定的な差をもたらす。ユニオンバウンドで候補数倍の確率を加算するとき、多項式減衰では候補数 $m$ に対し上界が $m$ 倍増えてしまうが、指数減衰では $m$ が対数的にしか効かないため、現実的な候補数(例: 100 万)でも有効なバウンドが保てる。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## 未解決の問い - ヘフディングの不等式は有界確率変数にのみ適用できるが、実際の深層学習の損失は必ずしも有界でない。サブガウス分布の仮定など、より広いクラスへの拡張はどの程度有効か。 - マルチンゲール型の集中不等式(McDiarmid の不等式など)は、独立性を緩和した依存構造にどこまで対応できるか。 ## 関連 - [[汎化誤差バウンド]] — 集中不等式を使って汎化誤差を上界する枠組み - [[PAC学習]] — 確率的学習保証の形式化 - [[カバリングナンバー]] — 無限仮説クラスでの一様収束への橋渡し ## 出典 - [[@2025__joisino__絶対に分かる機械学習理論]] — 佐藤竜馬、2025-03-17