# 集中不等式 Navigation: [[index]] | [[_index|concepts]] ## 定義 集中不等式(concentration inequality)とは、確率変数(またはその関数)がその期待値の周りに集中する現象を定量的に表す不等式の総称である。「サンプルサイズを増やすにつれて標本平均が期待値に近づく」という大数の法則を、確率的な精度付きで厳密化する。機械学習理論における汎化誤差バウンドの主要な道具立てをなす。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]]) ## マルコフの不等式 非負の確率変数 $X$ と任意の定数 $a > 0$ に対して: $\Pr(X \ge a) \le \frac{\mathbb{E}[X]}{a}$ それ自体は集中不等式ではないが、チェビシェフの不等式やヘフディングの不等式など他の集中不等式の証明の基礎として用いられる。直感: 期待値よりも $a$ 倍以上大きな値をとる確率が高ければ、その項だけで期待値を超えてしまい矛盾する。(Source: [[joisino-機械学習理論入門-2025|@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$ で割る。 **下界を使った改良(bounded variable trick)**: $R$ に既知の下界 $b>0$ があるとき、$R$ そのものではなく $R-b$(これも非負)にマルコフの不等式を適用すると、より強い上界 $\Pr[R\ge x]\le \mathbb{E}[R-b]/(x-b)$ が得られる。同様に上界 $u$ が既知なら $u-S$ に適用することで、$S$ が期待値より大幅に小さくなる確率を上から抑えられる。これは「マルコフの不等式をうまく選んだ $R$ の関数に適用する」という、チェビシェフの不等式(下記)やチェルノフ限界(下記)にも共通する一般的な証明パターンの最も単純な例になっている。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 19 Deviation from the Mean]] §19.1.2) ## チェビシェフの不等式 確率変数 $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: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]]) **一般化とペアワイズ独立標本抽出定理**: チェビシェフの不等式は、より一般に $\Pr[|R|\ge x]\le \mathbb{E}[|R|^z]/x^z$($z$: 任意の正の実数)という補題の $z=2$ の特殊ケースとして導かれる($|R|^z$ が非負であることにマルコフの不等式を適用するだけでよい)。標本平均への応用では、平均 $\mu$・分散 $\sigma^2$ を共有する**対独立(pairwise independent)**な確率変数 $G_1,\ldots,G_n$(相互独立である必要はない)の和 $S_n$ について $\Pr[|S_n/n-\mu|\ge x]\le \sigma^2/(nx^2)$ が成り立つ(Pairwise Independent Sampling Theorem)。この定理は大数の弱法則(Weak Law of Large Numbers)の証明にそのまま使われる。誕生日マッチング問題(異なるペアの一致は対独立だが相互独立ではない)がこの一般化が実用上必要になる典型例である。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 19 Deviation from the Mean]] §19.2, §19.4) ## ヘフディングの不等式 区間 $[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: [[joisino-機械学習理論入門-2025|@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$ を示す。 ## チェルノフ限界 $0 \le T_i \le 1$ を満たす**相互独立**な確率変数 $T_1,\ldots,T_n$ の和 $T := T_1+\cdots+T_n$ に対して、$c\ge 1$ のとき $\Pr[T \ge c\,\mathbb{E}[T]] \le e^{-\beta(c)\,\mathbb{E}[T]}, \qquad \beta(c) := c\ln c - c + 1$ - ヘフディングの不等式と同じく**指数関数的**な裾の減衰を持つが、区間の幅を $[0,1]$ に固定し、対称な両側評価ではなく片側($T$ が期待値を上回る側)の評価を与える点でヘフディングと定式化が異なる。二項分布はこの条件を満たす最も代表的な例だが、$T_i$ の分布は互いに異なっていても、未知であってもよい。 - **証明の要点(指数化トリック)**: 不等式 $T\ge c\,\mathbb{E}[T]$ の両辺を $c>1$ で指数化してからマルコフの不等式を適用する($\Pr[c^T\ge c^{c\mathbb{E}[T]}] \le \mathbb{E}[c^T]/c^{c\mathbb{E}[T]}$)。凸性による不等式 $c^v\le 1+(c-1)v$($v\in[0,1]$、$c\ge 1$)と $1+z\le e^z$ を組み合わせて各 $T_i$ の指数モーメント $\mathbb{E}[c^{T_i}]$ を $e^{(c-1)\mathbb{E}[T_i]}$ で上から抑え、独立性による積の期待値の乗法性で $T=\sum T_i$ 全体に拡張する。区間を $[0,1]$ に制限するのは、この凸性不等式を成立させるために必須である。 - **応用例**: 負荷分散(24,000件のタスクを $m$ 台のサーバへランダムに割り当てる Fussbook の例)では、サーバ数を $m=11$ から $m=13$ に増やすだけで過負荷確率の上界が $0.784$ から $7.6\times10^{-8}$ へ激減する。ロトくじ(Pick-4)の運営者が期待当選者数の2倍以上の当選者が出る確率が $e^{-386}$ 未満であることを示すのにも使われる。 (Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 19 Deviation from the Mean]] §19.6.1-§19.6.6) ### マーフィーの法則(Chernoff限界の系) 相互独立な事象 $A_1,\ldots,A_n$ の指示確率変数の和 $T=T_1+\cdots+T_n$(発生した事象の個数)について $\Pr[T=0] \le e^{-\mathbb{E}[T]}$ が成り立つ。証明は $1-x\le e^{-x}$ を使い、どの事象も起きない確率(積 $\prod(1-\Pr[A_i])$)を $e^{-\sum \Pr[A_i]}=e^{-\mathbb{E}[T]}$ という指数の和に変換するだけでよい。$\mathbb{E}[T]$ が1よりずっと大きければ、何も起きない確率は指数的に小さい——「起こりうる独立な悪いことの期待件数が多ければ、実際に何かが起きる」ことの定量化であり、チェルノフ限界と同じ指数化トリックの系として得られる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 19 Deviation from the Mean]] §19.6.8) ## 各不等式の比較 | 不等式 | 使用情報 | 裾の減衰 | 特徴 | |---|---|---|---| | マルコフ | 期待値のみ | $1/a$ | 証明の基礎部品 | | チェビシェフ | 期待値・分散 | $1/k^2$ (多項式) | 分布非依存 | | ヘフディング | 有界性・独立性 | $\exp(-nt^2)$ (指数) | 強力・有界変数に限定・両側評価 | | チェルノフ | $[0,1]$ 値・相互独立性 | $\exp(-\beta(c)\mathbb{E}[T])$ (指数) | 片側評価・和の期待値の指数で減衰 | ## 機械学習理論での役割 集中不等式は汎化誤差バウンドの核心部品として機能する。評価の場合は直接適用でき、訓練の場合は**ユニオンバウンド**と組み合わせて有限(または有限化された)仮説クラス全体への一様収束を保証する。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]]) ## 横断的知見 - チェビシェフの不等式の多項式減衰 vs ヘフディングの不等式の指数減衰という対比は、候補数が多くなる場合に決定的な差をもたらす。ユニオンバウンドで候補数倍の確率を加算するとき、多項式減衰では候補数 $m$ に対し上界が $m$ 倍増えてしまうが、指数減衰では $m$ が対数的にしか効かないため、現実的な候補数(例: 100 万)でも有効なバウンドが保てる。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]]) - 機械学習理論の教科書(joisino 2025)と離散数学の教科書(Mathematics for Computer Science 第19章)は、同じマルコフ・チェビシェフの不等式を扱いながら**位置づけが対照的**である。前者はこれらを**汎化誤差バウンド**という単一の下流応用(訓練データから見えない汎化誤差を上から抑える)の部品として導入し、ヘフディングの不等式(指数減衰)への足がかりとして手短に扱う。後者は逆に、Markov's Theorem・Chebyshev's Theoremという章の中で最も長く紙幅を割く独立した理論的主題として扱い、無作為抽出による推定(世論調査)・信頼水準の哲学的な区別・負荷分散という**3つの異なる応用**へ展開する。前者は「強い不等式(ヘフディング)へ速く到達するための踏み台」として、後者は「情報が少ないところから情報を追加するたびにどれだけ強い主張が言えるか」という**認識論的な系列**(非負性のみ→分散も既知→有界性と独立性も既知)として、同じ数学的対象を異なる物語で提示している。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]], [[@2015__MIT__Mathematics for Computer Science - Chapter 19 Deviation from the Mean]]) - ヘフディングの不等式(joisino 2025)とチェルノフ限界(Mathematics for Computer Science 第19章)は、いずれも「有界な独立確率変数の和」に指数関数的な裾確率の上界を与える点で数学的に近縁だが、定式化が異なる。ヘフディングは区間 $[a_i,b_i]$ 上の変数の標本平均が期待値から**両側に** $t$ 以上ずれる確率を評価するのに対し、チェルノフ限界は $[0,1]$ 上の変数の和が期待値の $c$ 倍(**片側**、$c\ge 1$)を超える確率を評価する。ヘフディングの証明はヘフディングの補題(指数モーメントの二次形式による上界)を経由するのに対し、チェルノフ限界の証明は「両辺を指数化してからマルコフの不等式を適用する」という指数化トリックを直接使う点で証明の道具立ても異なる。両者はどちらも独立性を本質的に要求し、区間の有界性(ヘフディングは $[a_i,b_i]$、チェルノフは $[0,1]$)が指数評価を可能にする鍵になっている、という共通の設計原理を持つ。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]], [[@2015__MIT__Mathematics for Computer Science - Chapter 19 Deviation from the Mean]] §19.6.6) ## 未解決の問い - ヘフディングの不等式は有界確率変数にのみ適用できるが、実際の深層学習の損失は必ずしも有界でない。サブガウス分布の仮定など、より広いクラスへの拡張はどの程度有効か。 - マルチンゲール型の集中不等式(McDiarmid の不等式など)は、独立性を緩和した依存構造にどこまで対応できるか。 - チェルノフ限界とヘフディングの不等式はいずれも指数減衰を与えるが、同一の設定(例: $[0,1]$ 値の相互独立な和)に両方を適用した場合、どちらがより強い(タイトな)上界を与えるかは本 vault の2ソースからは判断できない。定数 $\beta(c)$ と $2t^2$ の直接比較を行う3つ目のソースが入ってきたときに追記する。 ## 関連 - [[汎化誤差バウンド]] — 集中不等式を使って汎化誤差を上界する枠組み - [[PAC学習]] — 確率的学習保証の形式化 - [[カバリングナンバー]] — 無限仮説クラスでの一様収束への橋渡し - [[分散]] — チェビシェフの不等式が使う統計量、Mathematics for Computer Science 第19章で性質を詳述 - [[信頼水準]] — チェビシェフの不等式を無作為抽出による推定に応用する際の解釈上の注意点 - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 19 Deviation from the Mean]] ## 出典 - [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]] — 佐藤竜馬、2025-03-17 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 19 §19.1-§19.2, §19.6.