サイコロを6回振って平均が3.5にぴったり一致することは、まずありません。でも6000回振れば、平均はほぼ確実に3.5の近くに来ます。「ほぼ確実に」「近くに」とは、どれくらい確実で、どれくらい近いのでしょうか。この素朴な問いに、確率の言葉で速度まで込めて答えるのが集中不等式（concentration inequalities）です。
機械学習の論文を読むと、付録の定理にほぼ必ず「with probability at least $1-\delta$（確率 $1-\delta$ 以上で）」という枕詞が出てきます。あの「高確率で〜が成り立つ」という言い回しの正体が、まさに集中不等式です。集中不等式を知らないまま論文を読むと、この一行が魔法のように見えてしまいます。逆に一度わかってしまえば、汎化バウンドの証明が「ただ集中不等式を当てはめているだけ」に見えるようになります。
この概念が活きる応用先を、先に2つ挙げておきます。
- 機械学習の汎化保証：手元のデータで測った誤差（経験リスク）が、未知のデータでの本当の誤差（真のリスク）にどれだけ近いかを保証する。これが学習理論の心臓部です。
- A/Bテストの標本サイズ設計：「クリック率の差を誤差±1%で見たい。何人集めれば十分か？」という問いに、必要なサンプル数を数式で答える。
本記事の内容
- 集中不等式の出発点：Markov不等式とChebyshev不等式（導出つき）
- 指数で締める一般戦略：Chernoff法とsub-Gaussian
- 有界確率変数の集中：Hoeffding補題とHoeffding不等式の導出
- 分散を使った鋭い評価：Bernstein不等式
- 関数の集中：McDiarmid不等式（bounded differences）
- 機械学習への接続：単一仮説から仮説集合へ、union boundとその先
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
集中とは何か：まずは絵で掴む
「集中する（concentrate）」という言葉のイメージから始めましょう。たくさんの独立な観測を平均すると、その平均値は真の平均のまわりにぎゅっと集まっていきます。観測が1個や2個だとバラバラに散らばりますが、何千個も平均すれば、ほとんど真の平均にへばりつきます。この「散らばりが消えていく速さ」を定量化したいのです。
まず、標本平均が本当に集中していく様子を見てみましょう。平均 $0.5$ の一様分布から少しずつ観測を増やし、累積平均がどう動くかを8本の軌跡で描きます。
この図から2つのことが読み取れます。第一に、$n$ が小さいうちは8本の軌跡が大きく上下に散らばっていますが、$n$ が増えると一気に真の平均 $\mu=0.5$ に吸い寄せられます。第二に、灰色の帯 $\mu \pm \sigma/\sqrt{n}$ が軌跡をだいたい包んでいます。つまり散らばりの幅は $1/\sqrt{n}$ のスケールで縮みます。この「$\sqrt{n}$ で縮む」という感覚は、本記事を通じて何度も登場する主役です。
ここで自然な疑問が生まれます。「だいたい包んでいる」ではなく、「確率いくつ以上で、必ず幅 $t$ の中に入る」と保証できないでしょうか。それを可能にするのが、これから見ていく一連の不等式です。
Markov不等式：すべての出発点
集中不等式の最も原始的な形がMarkov不等式です。これはたった一つの仮定——「確率変数が非負である」——だけから、裾の確率（大きな値を取る確率）を平均で押さえます。
直感はこうです。テストの平均点が70点だったとします。では「90点以上を取った人」はどれくらいいるでしょうか。全員が90点以上なら平均は90点を超えてしまうので、平均70点という事実だけから、90点以上の割合はそんなに多くないはずです。具体的には $70/90 \approx 0.78$、つまり最大でも78%です。これがMarkov不等式の心です。
数式で書くと、非負の確率変数 $X \ge 0$ と任意の $a > 0$ に対して、
$$ P(X \ge a) \le \frac{\mathbb{E}[X]}{a} $$
が成り立ちます。導出は驚くほど短いです。まず、$X \ge 0$ なので、次の不等式が各点で成り立ちます。
$$ a \cdot \mathbf{1}\{X \ge a\} \le X $$
ここで $\mathbf{1}\{X \ge a\}$ は事象 $X \ge a$ が起きたとき $1$、そうでないとき $0$ を返す指示関数です。なぜこの不等式が成り立つのか確認しましょう。$X \ge a$ のときは左辺が $a$、右辺は $a$ 以上なので成立。$X < a$ のときは左辺が $0$、右辺は非負なので成立。どちらの場合も成り立ちます。
両辺の期待値を取ります。期待値は不等式の向きを保つので、
$$ a \cdot \mathbb{E}[\mathbf{1}\{X \ge a\}] \le \mathbb{E}[X] $$
指示関数の期待値はその事象の確率そのもの、つまり $\mathbb{E}[\mathbf{1}\{X \ge a\}] = P(X \ge a)$ です。これを代入して両辺を $a$ で割ると、
$$ P(X \ge a) \le \frac{\mathbb{E}[X]}{a} $$
が得られます。これがMarkov不等式です。仮定が「非負」だけなので適用範囲は広いですが、その分バウンドはゆるい（$1/a$ でしか減らない）という弱点があります。この弱さをどう克服するかが、本記事の物語の軸になります。
Markov不等式は「平均」しか使っていません。では、もう一つの基本統計量である「分散」を使えば、もっと鋭くできるのではないでしょうか。
Chebyshev不等式：分散を投入する
Markov不等式の弱点は、平均しか見ていないので「平均の周りにどれだけ散らばっているか」を一切考慮しない点でした。散らばりの指標といえば分散です。分散を組み込むと、平均から両側に外れる確率を押さえられます。これがChebyshev不等式です。
直感の例を続けます。テストの平均が70点、標準偏差が10点だったとします。「平均から20点以上離れた人（50点未満または90点以上）」はどれくらいいるでしょうか。20点のズレは標準偏差の2倍です。Chebyshevは「標準偏差の $k$ 倍以上外れる人は最大でも $1/k^2$」と言うので、$k=2$ なら最大25%です。
数式では、平均 $\mu = \mathbb{E}[X]$、分散 $\sigma^2 = \mathrm{Var}(X)$ を持つ確率変数 $X$ に対し、任意の $t > 0$ で
$$ P(|X – \mu| \ge t) \le \frac{\sigma^2}{t^2} $$
導出は、Markov不等式を上手に使うのがポイントです。やりたいのは $|X-\mu| \ge t$ の確率を押さえることですが、$|X-\mu|$ は非負なのでそのままMarkovを当てたくなります。しかしより鋭くするために、両辺を2乗してから当てます。$|X-\mu| \ge t$ と $(X-\mu)^2 \ge t^2$ はまったく同じ事象なので、
$$ P(|X-\mu| \ge t) = P\big((X-\mu)^2 \ge t^2\big) $$
右辺は非負確率変数 $(X-\mu)^2$ が $t^2$ 以上になる確率です。ここでMarkov不等式（$a = t^2$）を適用すると、
$$ P\big((X-\mu)^2 \ge t^2\big) \le \frac{\mathbb{E}[(X-\mu)^2]}{t^2} $$
最後に、$\mathbb{E}[(X-\mu)^2]$ は分散の定義そのもの、つまり $\sigma^2$ です。これを代入して、
$$ P(|X-\mu| \ge t) \le \frac{\sigma^2}{t^2} $$
が得られました。Markovが「2乗してから当てる」だけでChebyshevになる、というのは美しい構造です。Chebyshevを標本平均 $\bar{X}_n$ に当てると、$\mathrm{Var}(\bar{X}_n) = \sigma^2/n$ なので、
$$ P(|\bar{X}_n – \mu| \ge t) \le \frac{\sigma^2}{n t^2} $$
となり、$n$ が増えれば確率が $1/n$ で減ることがわかります。これは大数の法則の定量版です。
しかし $1/(nt^2)$ という減り方は、$t$ について見るとまだ多項式（$1/t^2$）でしか減りません。先ほどの図1で見た散らばりは、実際にはもっと急激に——指数的に——薄くなっていそうです。多項式の壁を破って指数まで持っていく方法はあるのでしょうか。
Chernoff法：指数で締める一般戦略
ここからが集中不等式の本領です。Chernoff法は、Markov不等式を「指数関数を通して」当てるという一つのトリックで、多項式バウンドを指数バウンドに化けさせます。これは特定の不等式の名前ではなく、HoeffdingにもBernsteinにも共通する戦略の名前です。
アイデアはこうです。$P(X \ge a)$ を直接Markovで押さえると $1/a$ でしか減りません。そこで、単調増加な関数 $e^{\lambda x}$（$\lambda > 0$）を両辺にかけても事象は変わらないことを使います。$X \ge a$ と $e^{\lambda X} \ge e^{\lambda a}$ は同じ事象なので、
$$ P(X \ge a) = P\big(e^{\lambda X} \ge e^{\lambda a}\big) $$
右辺の $e^{\lambda X}$ は非負なので、Markov不等式（$a$ の役を $e^{\lambda a}$ が担う）を当てられます。
$$ P\big(e^{\lambda X} \ge e^{\lambda a}\big) \le \frac{\mathbb{E}[e^{\lambda X}]}{e^{\lambda a}} = e^{-\lambda a}\, \mathbb{E}[e^{\lambda X}] $$
ここで登場した $\mathbb{E}[e^{\lambda X}]$ はモーメント母関数（MGF）と呼ばれ、$M_X(\lambda)$ と書きます。重要なのは、この不等式が任意の $\lambda > 0$ で成り立つことです。だから、右辺を $\lambda$ について最小化すれば、一番きついバウンドが得られます。
$$ P(X \ge a) \le \min_{\lambda > 0}\, e^{-\lambda a}\, M_X(\lambda) $$
この「$\lambda$ で最適化する」ステップが、指数バウンドを生む鍵です。具体例として、標準正規分布 $X \sim \mathcal{N}(0,1)$ を考えます。このMGFは $M_X(\lambda) = e^{\lambda^2/2}$ なので、バウンドは $e^{\lambda^2/2 – \lambda a}$ です。$\lambda$ を動かして最小化する様子を描いてみます。
この図から、指数の肩 $\lambda^2/2 – \lambda a$ を $\lambda$ について最小化していることが読み取れます。肩を $\lambda$ で微分して $\lambda – a = 0$、つまり最適は $\lambda^* = a$。代入すると最良バウンドは $e^{-a^2/2}$ になり、図でも谷底がちょうど $\lambda = 2$（$a=2$ のとき）で $e^{-2}$ 付近に達しています。これが正規分布の有名な裾バウンド $P(X \ge a) \le e^{-a^2/2}$ です。$1/a^2$ ではなく $e^{-a^2/2}$ という、けた違いに速い減衰が手に入りました。
各バウンドが実際どれくらい違うのか、正規分布の裾を例に並べてみましょう。
縦軸は対数です。青の真の裾確率に対して、赤の $1/t^2$（Markov/Chebyshev型）は $t$ が大きくなってもゆっくりとしか落ちません。一方、緑の $e^{-t^2/2}$（指数型）は真の裾にぴったり寄り添いながら急降下します。多項式バウンドと指数バウンドの差は、$t$ が大きいほど決定的に開いていきます。Chernoff法が「ゲームを変える」と言われる理由がここにあります。
Chernoff法の効き目はMGFの形で決まります。では、どんな確率変数なら正規分布のように $e^{\lambda^2/2}$ 型のMGFを持つのでしょうか。それを抽象化したのが次のsub-Gaussianです。
sub-Gaussian：正規分布なみに薄い裾を持つ仲間
Chernoff法の威力は「MGFが $e^{\sigma^2\lambda^2/2}$ で押さえられる」ことに依存していました。この性質を満たす確率変数をsub-Gaussian（劣ガウス）と呼びます。正規分布そのものでなくても、裾が正規分布と同じかそれより薄ければ仲間に入れる、という発想です。
定義は、平均 $0$ の確率変数 $X$ が、ある $\sigma > 0$ に対してすべての $\lambda \in \mathbb{R}$ で
$$ \mathbb{E}[e^{\lambda X}] \le \exp\!\left(\frac{\sigma^2 \lambda^2}{2}\right) $$
を満たすとき、$X$ は分散プロキシ $\sigma^2$ で sub-Gaussian であると言います。この一行の条件さえ満たせば、先ほどのChernoff法がそのまま流れ、裾バウンドが自動で出ます。実際、Chernoff法に代入して $\lambda$ で最適化すると、$\lambda^* = t/\sigma^2$ で
$$ P(X \ge t) \le \exp\!\left(-\frac{t^2}{2\sigma^2}\right) $$
が得られます。両側にすれば $P(|X| \ge t) \le 2\exp(-t^2/2\sigma^2)$ です。この裾が $\sigma$ によってどう変わるか見てみましょう。
この図から、分散プロキシ $\sigma$ が小さいほど裾が急速にゼロに落ちることが読み取れます。$\sigma=0.5$ では $t=2$ ですでに $10^{-3}$ を下回りますが、$\sigma=1.5$ ではまだ $0.4$ 程度です。sub-Gaussianの「分散プロキシ」は、その確率変数がどれだけ集中しやすいかを表すノブだと考えると直感的です。
sub-Gaussianの偉いところは和に閉じていることです。独立な sub-Gaussian $X_1, \dots, X_n$（それぞれ分散プロキシ $\sigma_i^2$）の和は、分散プロキシ $\sum_i \sigma_i^2$ の sub-Gaussian になります。MGFが積に分解し、指数の肩が足し算になるからです。この性質のおかげで、標本平均の集中をきれいに扱えます。
では、機械学習で最も頻繁に出てくる「有界な確率変数」（たとえば $0/1$ の誤分類）は sub-Gaussian なのでしょうか。それを保証するのが、次のHoeffding補題です。
Hoeffding補題とHoeffding不等式
機械学習で扱う量の多くは有界です。誤分類の指示関数は $\{0,1\}$、正規化した損失は $[0,1]$ に収まります。こうした有界確率変数が自動的に sub-Gaussian になることを保証するのがHoeffding補題です。
Hoeffding補題
主張はこうです。確率変数 $X$ が $[a, b]$ に値を取り、平均 $\mathbb{E}[X] = 0$ なら、すべての $\lambda \in \mathbb{R}$ に対して
$$ \mathbb{E}[e^{\lambda X}] \le \exp\!\left(\frac{\lambda^2 (b-a)^2}{8}\right) $$
つまり有界な確率変数は、分散プロキシ $\sigma^2 = (b-a)^2/4$ の sub-Gaussian だということです。証明の核は、$e^{\lambda x}$ が凸関数であることを使う点にあります。区間 $[a,b]$ 上で $x$ を端点の凸結合 $x = \frac{b-x}{b-a}a + \frac{x-a}{b-a}b$ と書き、凸性から
$$ e^{\lambda x} \le \frac{b-x}{b-a}e^{\lambda a} + \frac{x-a}{b-a}e^{\lambda b} $$
両辺の期待値を取り、$\mathbb{E}[X]=0$ を使って整理すると、MGFが補助関数 $\varphi(s) = -s p + \log(1 – p + p e^{s})$（$p = -a/(b-a)$、$s = \lambda(b-a)$）の指数で書けます。この $\varphi$ をテイラー展開すると $\varphi(0)=0$、$\varphi'(0)=0$、そして $\varphi”(s) \le 1/4$ が示せるので、2次の剰余項評価から $\varphi(s) \le s^2/8$ が従います。これを戻すと上の補題が出ます。「凸性で端点に押し付け、2階微分を $1/4$ で抑える」のが筋道です。
Hoeffding不等式
補題が手に入れば、独立和への一般化はsub-Gaussianの加法性で一瞬です。$X_1, \dots, X_n$ を独立で各 $X_i \in [a_i, b_i]$ とし、標本平均 $\bar{X}_n = \frac{1}{n}\sum_i X_i$、その期待値を $\mu = \mathbb{E}[\bar{X}_n]$ とします。中心化した $X_i – \mathbb{E}[X_i]$ は補題より分散プロキシ $(b_i-a_i)^2/4$ の sub-Gaussian、和の $\sum_i(X_i-\mathbb{E}[X_i])$ は分散プロキシ $\frac{1}{4}\sum_i (b_i-a_i)^2$ の sub-Gaussian です。これにChernoff法を当て、$\bar{X}_n$ のスケール（$1/n$ 倍）を反映して $\lambda$ で最適化すると、すべての $a_i=a, b_i=b$ の場合に
$$ P(\bar{X}_n – \mu \ge t) \le \exp\!\left(-\frac{2n t^2}{(b-a)^2}\right) $$
両側版は
$$ P(|\bar{X}_n – \mu| \ge t) \le 2\exp\!\left(-\frac{2n t^2}{(b-a)^2}\right) $$
これがHoeffding不等式です。分散の情報すら要らず、各変数の範囲 $[a,b]$ だけで、$n$ について指数的に集中することを保証します。機械学習の汎化バウンドで最初に出てくる道具がこれです。
このバウンドが本当に成り立つのか、シミュレーションで確かめましょう。$[0,1]$ 一様分布から $n=50$ 個取った標本平均が、$\mu=0.5$ から $t$ 以上ずれる確率を20万回試行で測り、Hoeffdingバウンドと重ねます。
この図から、緑の実測裾が赤のHoeffdingバウンドに常に下から抑えられていることが読み取れます。たとえば $t=0.1$ では実測がおよそ $0.014$ なのにバウンドは $0.736$、$t=0.15$ では実測 $0.0002$ に対しバウンド $0.211$ です。バウンドは正しく「上から押さえる」役目を果たしますが、かなり保守的（ゆるい）でもあります。これは「分散を捨てて範囲だけ使った」代償です。この保守性を改善するのが、次のBernstein不等式です。
Hoeffding不等式を「確率 $1-\delta$ 以上で成り立つ」形に書き換えると、論文でおなじみの形になります。$2\exp(-2nt^2/(b-a)^2) = \delta$ を $t$ について解くと、
$$ t = (b-a)\sqrt{\frac{\ln(2/\delta)}{2n}} $$
つまり確率 $1-\delta$ 以上で $|\bar{X}_n – \mu| \le (b-a)\sqrt{\ln(2/\delta)/(2n)}$ が成り立ちます。これがまさに「高確率の信頼区間」です。半幅が $\sqrt{n}$ で縮む様子を描いてみます。
この図から、$\delta=0.05$（95%信頼）のときの半幅が $1/\sqrt{n}$ の曲線にぴったり乗ることが読み取れます。$n=100$ で半幅 $0.136$、$n=1000$ で $0.043$。精度を10倍上げる（半幅を1/10にする）には、$n$ を100倍にする必要があります。これがA/Bテストで「もう少し精度が欲しい」と思ったときにサンプルが爆発的に増える理由です。実際、半幅を $0.01$ にしたければ $n \approx 18444$ が必要になります。
Hoeffdingは範囲しか使わないため、分散が小さい場合に損をしていました。分散を取り戻すとどうなるでしょうか。
Bernstein不等式：分散が小さいと速くなる
サイコロのように $[0,1]$ で大きくばらつく変数と、ほとんど常に $0$ に近いがごくたまに $1$ になる変数を考えます。範囲はどちらも同じ $[0,1]$ ですが、後者は分散がずっと小さく、平均のまわりにもっと固く集中するはずです。Hoeffdingは範囲だけ見るので両者を区別できません。この区別を取り戻すのがBernstein不等式です。
主張は、独立な $X_i$ が平均 $0$、$|X_i| \le M$（有界）、分散の和を $\sum_i \mathbb{E}[X_i^2] = n\sigma^2$ とするとき、$S = \sum_i X_i$ について
$$ P(S \ge t) \le \exp\!\left(-\frac{t^2}{2\left(n\sigma^2 + \frac{Mt}{3}\right)}\right) $$
指数の分母に注目してください。$n\sigma^2$（分散項）と $\frac{Mt}{3}$（有界項）の和になっています。$t$ が小さいうち、つまり典型的な揺らぎの範囲では分散項が支配し、指数は $-t^2/(2n\sigma^2)$ という正規分布型（分散で決まる速い減衰）になります。一方 $t$ が非常に大きい裾の奥では有界項が支配し、指数は $-3t/(2M)$ という線形（やや遅い）減衰に切り替わります。この「中央はガウス、極端な裾は指数」という二相構造がBernsteinの本質です。導出はChernoff法ですが、MGFをHoeffdingのように範囲だけで潰さず、$\mathbb{E}[X_i^2]$ を温存して評価する点が違います。
低分散のときにHoeffdingとどれだけ差がつくか、$X_i \in [-1,1]$（範囲は同じ）で分散だけ変えて比べます。
この図から、分散 $\sigma^2 = 0.05$ という低分散のケース（青破線）では、Bernsteinが赤のHoeffdingよりはるかに鋭く（同じ $t$ で何けたも小さく）落ちることが読み取れます。一方 $\sigma^2 = 0.5$（緑破線）と分散が大きくなると差は縮まり、Hoeffdingに近づきます。Hoeffdingは「最悪の分散（$=$ 範囲の半分の2乗）を仮定したBernstein」とも言え、分散が本当に小さいデータではBernsteinを使う価値が大きいのです。
ここまでは「数の平均」の集中でした。しかし機械学習で本当に押さえたいのは、もっと複雑な量——たとえば「仮説集合全体での最悪の誤差」——の集中です。これは単なる平均ではなく、多くの変数の複雑な関数です。関数の集中を扱う道具が必要になります。
McDiarmid不等式：関数の集中
最大値、中央値、ヒストグラム、そして「経験誤差の上限」のような量は、入力データの単純な平均ではありません。それでも、ある条件を満たす関数なら集中することを保証するのがMcDiarmid不等式（有界差分不等式、bounded differences inequality）です。
鍵となる条件は有界差分（bounded differences）です。関数 $f(x_1, \dots, x_n)$ が、$i$ 番目の引数だけを任意に変えても出力が高々 $c_i$ しか変わらない、つまり
$$ \sup_{x_1,\dots,x_n,\,x_i’} \big| f(x_1,\dots,x_i,\dots,x_n) – f(x_1,\dots,x_i’,\dots,x_n) \big| \le c_i $$
を満たすとき、$f$ は有界差分定数 $c_i$ を持つと言います。「1つの入力が暴れても、出力はちょっとしか動かない」という鈍感さの条件です。標本平均 $f = \frac{1}{n}\sum x_i$（各 $x_i \in [a,b]$）なら、1座標を変えても平均は高々 $(b-a)/n$ しか動かないので $c_i = (b-a)/n$ です。この条件を絵にすると次のようになります。
この図では、座標 $j=4$ の入力値を $0.26$ から $0.05$ へ大きく変えています。それでも関数値（ここでは平均）は $f(x)=0.457$ から $f(x’)=0.431$ へ、わずか $0.026$ しか動きません。1座標の大変動が、出力では $c_j$ までに抑え込まれる——これが有界差分の感覚です。
McDiarmid不等式の主張は、独立な $X_1, \dots, X_n$ と有界差分定数 $c_1, \dots, c_n$ を持つ $f$ に対して、
$$ P\big(f(X_1,\dots,X_n) – \mathbb{E}[f] \ge t\big) \le \exp\!\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right) $$
形がHoeffdingにそっくりなことに気づくはずです。実際、Hoeffdingは $f = \sum x_i$、$c_i = b-a$ とした特殊ケースとして回収できます（$\sum c_i^2 = n(b-a)^2$ を代入すれば一致）。McDiarmidは「平均」を「鈍感な関数一般」に拡張したHoeffdingなのです。
証明はマルチンゲール差分列（Doob martingale）に基づきます。$f – \mathbb{E}[f]$ を、変数を1つずつ条件付けて明らかにしていく増分 $D_i$ の和に分解し、各 $D_i$ が有界差分条件から $[L_i, L_i + c_i]$ という長さ $c_i$ の区間に収まることを示します。あとは各 $D_i$ にHoeffding補題を当て、sub-Gaussianの加法性で和を取れば、上の指数バウンドが出ます。Hoeffding補題が「部品」として再利用されているのが見どころです。
McDiarmidが手に入ると、「経験誤差と真の誤差のギャップの最悪値」のような、学習理論の中心的な量の集中を一発で扱えるようになります。いよいよ機械学習との接続です。
機械学習への接続：単一仮説から仮説集合へ
機械学習が知りたいのは結局これです。「手元のデータで測った誤差は、見たことのないデータでの本当の誤差とどれだけ近いか」。前者を経験リスク $\hat{R}_n(h)$、後者を真のリスク $R(h)$ と呼びます。$\hat{R}_n(h) = \frac{1}{n}\sum_i \ell(h, z_i)$ は損失の標本平均、$R(h) = \mathbb{E}[\ell(h, z)]$ はその期待値です。
単一の仮説：Hoeffdingで一撃
仮説 $h$ を1つに固定して考えます。損失 $\ell(h, z_i)$ が $[0,1]$ に収まるなら、$\hat{R}_n(h)$ はまさに有界確率変数の標本平均です。Hoeffding不等式をそのまま当てて、確率 $1-\delta$ 以上で
$$ |R(h) – \hat{R}_n(h)| \le \sqrt{\frac{\ln(2/\delta)}{2n}} $$
が成り立ちます。経験リスクが真のリスクのまわりに集中していく様子を見ましょう。
この図から、真のリスク $R=0.30$ を中心に、経験リスク $\hat{R}_n$ の分布（箱ひげ）が $n$ の増加とともに細く絞られていくことが読み取れます。$n=10$ では $0.1$ から $0.5$ 程度まで広がっていますが、$n=3000$ ではほぼ $0.30$ に張り付きます。Hoeffdingが保証するのは、まさにこの「箱が縮む速さ」です。
仮説集合全体：そのままでは破綻する
ところが、ここに学習理論で最も大切な落とし穴があります。学習アルゴリズムは仮説 $h$ をデータを見てから選ぶので、固定された $h$ ではありません。データに最も都合よく当てはまる $h$ を選ぶと、その $h$ では $\hat{R}_n(h)$ がたまたま小さく出やすく、ギャップが大きくなりえます。固定 $h$ のHoeffdingは、この「選んだ後の $h$」には直接使えないのです。
解決の第一歩がunion bound（和集合上界、ブールの不等式）です。仮説集合 $\mathcal{H}$ が有限個 $\{h_1, \dots, h_M\}$ なら、「どれか1つでもギャップが大きい」確率は、各仮説でギャップが大きい確率の和で押さえられます。
$$ P\left(\exists\, h \in \mathcal{H}:\ |R(h) – \hat{R}_n(h)| \ge t\right) \le \sum_{j=1}^{M} P\big(|R(h_j) – \hat{R}_n(h_j)| \ge t\big) \le M \cdot 2e^{-2nt^2} $$
各項にHoeffdingを当てただけです。これを $\delta$ に等しいと置いて $t$ を解くと、確率 $1-\delta$ 以上ですべての $h \in \mathcal{H}$ について同時に
$$ |R(h) – \hat{R}_n(h)| \le \sqrt{\frac{\ln(2M/\delta)}{2n}} $$
が成り立ちます。$\ln(2/\delta)$ が $\ln(2M/\delta)$ に変わり、仮説の個数 $M$ が対数で効いてくるのが代償です。この代償の大きさを見てみましょう。
この図から、仮説数 $M$ が増えると保証される誤差の半幅が $\sqrt{\ln M}$ の速さで増えることが読み取れます。$M=1$（単一仮説）の半幅 $0.061$ に対し、$M=10000$ では $0.114$ とおよそ2倍です。対数なので増え方は緩やかですが、それでも「複雑なモデル（仮説が多い）ほど、同じ精度を保証するのに多くのデータが要る」というオーバーフィッティングの本質を、この一本の式が語っています。
union boundの限界とその先
しかし $M$ が無限大の場合（連続パラメータを持つモデルなど）はどうでしょうか。$\ln M = \infty$ になり、union boundは無意味になります。実際のニューラルネットや線形分類器は無限個の仮説を持つので、これは深刻な問題です。
ここで必要になるのが、有限の $M$ を「実質的な複雑さ」に置き換える、より洗練された道具です。具体的には、一様収束の議論、$f = \sup_{h}(R(h) – \hat{R}_n(h))$ という量にMcDiarmid不等式を当てて集中を示し、その期待値をRademacher複雑度やVC次元で押さえる、という流れになります。集中不等式は、その全体の議論を支える土台です。一様収束については一様収束とは？関数列の収束を徹底解説も参照してください。
こうして、論文の付録に出てくる「with probability at least $1-\delta$」の正体が見えてきました。それは、Hoeffdingやその仲間で各仮説の集中を保証し、union boundやRademacher複雑度で仮説集合全体に持ち上げた結果なのです。
Pythonで集中不等式を確かめる
理論を実験で裏づけましょう。本記事の図の数値主張がシミュレーションと一致することを、コードで確認します。まずHoeffdingバウンドが実測裾を上から抑えることの検証です。
import numpy as np
from math import log, sqrt, exp
# Hoeffding: n=50, [0,1]一様分布の標本平均の裾を測る
n = 50
a, b = 0.0, 1.0
trials = 200000
rng = np.random.default_rng(123)
X = rng.uniform(a, b, size=(trials, n))
means = X.mean(axis=1)
mu = 0.5
dev = np.abs(means - mu)
for t in [0.1, 0.15, 0.2]:
emp = (dev >= t).mean() # 実測の裾確率
hoeff = min(2 * exp(-2 * n * t**2 / (b - a)**2), 1.0) # Hoeffdingバウンド
print(f"t={t}: 実測={emp:.5f} Hoeffding={hoeff:.5f}")
このコードの出力は t=0.1: 実測=0.01393 Hoeffding=0.73576、t=0.15: 実測=0.00018 Hoeffding=0.21080、t=0.2: 実測=0.00000 Hoeffding=0.03663 となります。すべての $t$ で実測裾がHoeffdingバウンドより小さく、図10の主張どおりバウンドが正しく上から押さえていることが確認できます。同時に、バウンドが実測よりかなり大きい（保守的）こともはっきり見て取れます。
次に、信頼区間の半幅が $1/\sqrt{n}$ で縮むこと、そして精度を上げるコストを確認します。
import numpy as np
from math import log, sqrt
delta = 0.05 # 95%信頼
# Hoeffding信頼区間の半幅 t = sqrt(ln(2/delta) / (2n)) ([0,1]区間)
for n in [100, 1000]:
t = sqrt(log(2 / delta) / (2 * n))
print(f"n={n}: 信頼区間の半幅 = {t:.4f}")
# 半幅0.01を達成するのに必要なn
n_needed = log(2 / delta) / (2 * 0.01**2)
print(f"半幅0.01に必要なn = {round(n_needed)}")
出力は n=100: 信頼区間の半幅 = 0.1358、n=1000: 信頼区間の半幅 = 0.0429、半幅0.01に必要なn = 18444 です。図4で述べたとおり、$n$ を10倍にすると半幅は $1/\sqrt{10} \approx 0.316$ 倍になり（$0.1358 \to 0.0429$）、さらに半幅 $0.01$ という高精度には2万近いサンプルが要ることがわかります。$\sqrt{n}$ の壁の厳しさが数値で実感できます。
最後に、union boundによる仮説数 $M$ の代償を確認します。
import numpy as np
from math import log, sqrt
delta = 0.05
n = 500
# 単一仮説の半幅
single = sqrt(log(2 / delta) / (2 * n))
# M=10000個の仮説（union bound後）の半幅
multi = sqrt(log(2 * 10000 / delta) / (2 * n))
print(f"単一仮説の半幅 = {single:.4f}")
print(f"M=10000での半幅 = {multi:.4f}")
print(f"代償の倍率 = {multi / single:.2f}倍")
出力は 単一仮説の半幅 = 0.0607、M=10000での半幅 = 0.1136、代償の倍率 = 1.87倍 です。図9のとおり、1万個もの仮説を同時に保証しても、必要な誤差マージンは2倍弱しか増えません。$M$ が対数でしか効かないおかげで、この代償は驚くほど安いのです。これが、有限仮説集合に対する学習がうまくいく理由の数学的な核心です。
補遺：主要定理の証明を全行たどる
この補遺は読み飛ばしても大丈夫です。 ここから先は、上で使った不等式を補題から一行ずつ証明する部分です。前半までで「どの不等式が何を言っているか」というイメージは押さえられているので、結論を使えれば十分という方は次の節へ進んでください。証明を自分の手で追いたい方、論文の付録を読めるようになりたい方のための部分です。
ここまでは各不等式の「気持ち」と使い方を中心に説明し、証明はスケッチに留めた箇所がありました。この補遺では、本文で省略・圧縮した証明を補題から全行で埋めます。標準教科書 Boucheron, Lugosi, Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence（Oxford, 2013）の流儀に従い、数学的に正確であることを最優先にします。論文の付録を自分の手で再現できるレベルを目標にします。
記号の確認から始めます。$\mathbb{E}[\cdot]$ は期待値（確率変数の平均値）、$\mathrm{Var}(\cdot)$ は分散、$\inf$（infimum）は下限（その集合の値より小さくならないギリギリの値、最小値が存在すればそれと一致）、$\sup$（supremum）は上限です。$\mathbf{1}\{A\}$ は事象 $A$ が起きたとき $1$、起きなければ $0$ を返す指示関数です。証明は「Markov → Chebyshev → Chernoff → Hoeffding補題 → Hoeffding不等式 → Bernstein → Azuma–Hoeffding → McDiarmid」の順に積み上げます。後ろの定理は前の定理だけを使うので、上から順に読めば前提記事に飛ばずに全部たどれます。
補遺1. Markov不等式
主張. 非負の確率変数 $X \ge 0$ と任意の $a > 0$ に対して $P(X \ge a) \le \mathbb{E}[X]/a$。
証明. 出発点は、各点（$X$ がどんな値を取っても）で成り立つ次の不等式です。
$$ a \cdot \mathbf{1}\{X \ge a\} \le X $$
なぜ成り立つかを場合分けで確かめます。$X \ge a$ のとき、左辺は $a \cdot 1 = a$、右辺は $X \ge a$ なので左辺以上、よって成立します。$X < a$ のとき、左辺は $a \cdot 0 = 0$、右辺は仮定 $X \ge 0$ より非負なので $0$ 以上、よって成立します。どちらの場合も不等式が成り立つので、これは恒等的に正しい不等式です。
次に両辺の期待値を取ります。期待値には「$U \le V$ が常に成り立つなら $\mathbb{E}[U] \le \mathbb{E}[V]$」という単調性があるので、不等号の向きは保たれます。さらに期待値は定数倍を外に出せる（線形性）ので、
$$ a \cdot \mathbb{E}[\mathbf{1}\{X \ge a\}] \le \mathbb{E}[X] $$
ここで指示関数の期待値を計算します。$\mathbf{1}\{X\ge a\}$ は値 $1$（確率 $P(X\ge a)$）と値 $0$（確率 $1-P(X\ge a)$）しか取らない確率変数なので、その期待値は $1\cdot P(X\ge a) + 0\cdot(1-P(X\ge a)) = P(X\ge a)$ です。つまり $\mathbb{E}[\mathbf{1}\{X \ge a\}] = P(X \ge a)$。これを代入し、$a>0$ で両辺を割ると
$$ P(X \ge a) \le \frac{\mathbb{E}[X]}{a} $$
が得られます。$\blacksquare$
補遺2. Chebyshev不等式
主張. 平均 $\mu=\mathbb{E}[X]$、分散 $\sigma^2 = \mathrm{Var}(X)$ を持つ $X$ と任意の $t>0$ に対して $P(|X-\mu|\ge t) \le \sigma^2/t^2$。
証明. まず、押さえたい事象を2乗で書き換えます。$|X-\mu|\ge t$ と $(X-\mu)^2 \ge t^2$ は——両辺とも非負なので2乗は単調——まったく同じ事象です。したがって確率も等しく、
$$ P(|X-\mu|\ge t) = P\big((X-\mu)^2 \ge t^2\big) $$
ここで右辺に補遺1のMarkov不等式を適用します。Markovの「$X$」の役を非負確率変数 $(X-\mu)^2$ が、「$a$」の役を $t^2>0$ が担います。すると
$$ P\big((X-\mu)^2 \ge t^2\big) \le \frac{\mathbb{E}[(X-\mu)^2]}{t^2} $$
最後に分子を分散の定義で置き換えます。分散の定義は $\mathrm{Var}(X)=\mathbb{E}[(X-\mu)^2]=\sigma^2$ なので、
$$ P(|X-\mu|\ge t) \le \frac{\sigma^2}{t^2} $$
が従います。Markovを「2乗してから当てる」だけでChebyshevが出ました。$\blacksquare$
補遺3. Chernoff法
主張. 任意の確率変数 $X$ と実数 $a$ に対して、MGF $M_X(s)=\mathbb{E}[e^{sX}]$ が存在する範囲で
$$ P(X \ge a) \le \inf_{s>0} e^{-sa}\, \mathbb{E}[e^{sX}] $$
証明. $s>0$ を1つ固定します。指数関数 $x\mapsto e^{sx}$ は $s>0$ のとき狭義単調増加なので、不等式 $X\ge a$ の両辺に $e^{s(\cdot)}$ を作用させても同値性が保たれます。すなわち事象として $\{X\ge a\}=\{e^{sX}\ge e^{sa}\}$ であり、
$$ P(X\ge a) = P\big(e^{sX}\ge e^{sa}\big) $$
右辺の $e^{sX}$ は常に正なので非負確率変数です。これに補遺1のMarkov不等式を「$X$」$=e^{sX}$、「$a$」$=e^{sa}>0$ として当てると、
$$ P\big(e^{sX}\ge e^{sa}\big) \le \frac{\mathbb{E}[e^{sX}]}{e^{sa}} = e^{-sa}\,\mathbb{E}[e^{sX}] $$
ここまでで $P(X\ge a)\le e^{-sa}\mathbb{E}[e^{sX}]$ が任意の $s>0$ で成り立ちました。左辺は $s$ に依存しないので、右辺を $s>0$ にわたって動かしたときの一番小さい値（下限 $\inf$）でも左辺を上から押さえます。よって
$$ P(X\ge a) \le \inf_{s>0} e^{-sa}\,\mathbb{E}[e^{sX}] $$
が得られます。「$s$ をどう選んでもよいので、一番きつくなる $s$ を選ぶ」——これがChernoff法の心臓部です。$\blacksquare$
補遺4. Hoeffding補題（完全証明）
主張. 確率変数 $X$ が $[a,b]$ に値を取り $\mathbb{E}[X]=0$ なら、すべての $s\in\mathbb{R}$ に対して
$$ \mathbb{E}[e^{sX}] \le \exp\!\left(\frac{s^2(b-a)^2}{8}\right) $$
本文ではこれを「凸性で端点に押し付ける」と圧縮しましたが、ここでは指数傾斜測度を使う筋道で、各ステップを全部書きます。この方法は $\varphi”$ が傾斜後の分散になることが見え、Popoviciuの不等式が自然に効くので教育的です。
ステップ0：補助関数の定義. キュムラント母関数（cumulant generating function）を
$$ \psi(s) := \log \mathbb{E}[e^{sX}] $$
と定義します。これは「MGFの対数」です。目標を $\psi(s)\le s^2(b-a)^2/8$ と言い換えられれば、両辺の指数を取って主張が出ます。なお $s=0$ では $\mathbb{E}[e^0]=1$ なので $\psi(0)=\log 1 = 0$ です。
ステップ1：1階微分を計算する. 微分と期待値（積分）の順序交換が許される（$X$ が有界なので $\mathbb{E}[e^{sX}]$ は $s$ について何度でも微分可能）ことを使い、$\psi$ を $s$ で微分します。合成関数の微分から
$$ \psi'(s) = \frac{\frac{d}{ds}\mathbb{E}[e^{sX}]}{\mathbb{E}[e^{sX}]} = \frac{\mathbb{E}[X e^{sX}]}{\mathbb{E}[e^{sX}]} $$
ここで指数傾斜測度（exponential tilting）を導入すると見通しがよくなります。元の分布 $P$ に対し、新しい確率測度 $P_s$ を「密度（重み）を $e^{sx}/\mathbb{E}[e^{sX}]$ 倍したもの」として定義します。重みの総和が $\mathbb{E}[e^{sX}]/\mathbb{E}[e^{sX}]=1$ なので確かに確率測度です。この $P_s$ のもとでの期待値を $\mathbb{E}_s[\cdot]$ と書くと、任意の関数 $g$ について
$$ \mathbb{E}_s[g(X)] = \frac{\mathbb{E}[g(X)e^{sX}]}{\mathbb{E}[e^{sX}]} $$
が定義そのものです。これを使うと $\psi'(s)=\mathbb{E}_s[X]$ と書けます。とくに $s=0$ では $P_0=P$（重みが全部 $1$）なので、$\psi'(0)=\mathbb{E}_0[X]=\mathbb{E}[X]=0$（仮定）です。
ステップ2：2階微分が傾斜後の分散になる. $\psi'(s)=\mathbb{E}[Xe^{sX}]/\mathbb{E}[e^{sX}]$ をもう一度 $s$ で微分します。商の微分法 $(u/v)’=(u’v-uv’)/v^2$ で、$u=\mathbb{E}[Xe^{sX}]$、$v=\mathbb{E}[e^{sX}]$ とおくと $u’=\mathbb{E}[X^2e^{sX}]$、$v’=\mathbb{E}[Xe^{sX}]$ なので
$$ \psi”(s) = \frac{\mathbb{E}[X^2 e^{sX}]\,\mathbb{E}[e^{sX}] – \big(\mathbb{E}[X e^{sX}]\big)^2}{\big(\mathbb{E}[e^{sX}]\big)^2} $$
分子と分母を $\big(\mathbb{E}[e^{sX}]\big)^2$ で割って傾斜測度の言葉に直すと、
$$ \psi”(s) = \frac{\mathbb{E}[X^2 e^{sX}]}{\mathbb{E}[e^{sX}]} – \left(\frac{\mathbb{E}[X e^{sX}]}{\mathbb{E}[e^{sX}]}\right)^2 = \mathbb{E}_s[X^2] – \big(\mathbb{E}_s[X]\big)^2 = \mathrm{Var}_s(X) $$
つまり $\psi”(s)$ は指数傾斜測度 $P_s$ のもとでの $X$ の分散にぴったり等しいのです。これが本文で「$\varphi”(s)=\mathrm{Var}_{P_s}[X]$」と述べた内容です。
ステップ3：Popoviciuの不等式で分散を区間幅で抑える. ここが要です。傾斜測度 $P_s$ も $X$ を $[a,b]$ から外には出さない（$e^{sx}>0$ は台 = 値の取りうる範囲を変えないため）ので、$P_s$ のもとでも $X\in[a,b]$ です。台が幅 $b-a$ の区間に収まる確率変数の分散は $(b-a)^2/4$ を超えない——これがPopoviciuの不等式です。これを示します。
任意の定数 $c$ に対し、分散は平均まわりで最小なので $\mathrm{Var}_s(X) \le \mathbb{E}_s[(X-c)^2]$ が成り立ちます（分散の定義 $\mathrm{Var}_s(X)=\min_c \mathbb{E}_s[(X-c)^2]$、最小は $c=\mathbb{E}_s[X]$）。そこで区間の中点 $c=(a+b)/2$ を代入します。$X\in[a,b]$ なら中点からの距離は半幅以下、すなわち
$$ \left|X – \frac{a+b}{2}\right| \le \frac{b-a}{2} $$
両辺2乗すると $\big(X-\tfrac{a+b}{2}\big)^2 \le \big(\tfrac{b-a}{2}\big)^2 = (b-a)^2/4$ がすべての値で成り立ちます。これは確率変数として「定数 $(b-a)^2/4$ 以下」という各点不等式なので、$P_s$ で期待値を取っても保たれ、
$$ \mathrm{Var}_s(X) \le \mathbb{E}_s\!\left[\left(X-\tfrac{a+b}{2}\right)^2\right] \le \frac{(b-a)^2}{4} $$
を得ます。すなわちすべての $s$ について $\psi”(s) \le (b-a)^2/4$ が示せました。
ステップ4：テイラーの定理（剰余項つき）で結論する. $\psi$ を $s=0$ のまわりで2次まで展開します。テイラーの定理（ラグランジュ剰余）より、ある $\xi$（$0$ と $s$ の間）が存在して
$$ \psi(s) = \psi(0) + \psi'(0)\,s + \frac{1}{2}\psi”(\xi)\,s^2 $$
ステップ0・1で $\psi(0)=0$、$\psi'(0)=0$ を示したので、最初の2項は消えます。残った剰余項にステップ3の上界 $\psi”(\xi)\le (b-a)^2/4$ を代入すると、
$$ \psi(s) = \frac{1}{2}\psi”(\xi)\,s^2 \le \frac{1}{2}\cdot\frac{(b-a)^2}{4}\cdot s^2 = \frac{s^2(b-a)^2}{8} $$
最後に $\psi(s)=\log\mathbb{E}[e^{sX}]$ だったので、両辺の指数を取って
$$ \mathbb{E}[e^{sX}] \le \exp\!\left(\frac{s^2(b-a)^2}{8}\right) $$
これがHoeffding補題です。$\blacksquare$ なお主張は「分散プロキシ $\sigma^2=(b-a)^2/4$ の sub-Gaussian」と同義で、指数の肩 $\tfrac{s^2}{2}\cdot\tfrac{(b-a)^2}{4}=\tfrac{s^2(b-a)^2}{8}$ がそれを示しています。
補遺5. Hoeffding不等式（全行）
主張. 独立な $X_1,\dots,X_n$ が各 $X_i\in[a,b]$、$\bar{X}_n=\frac1n\sum_i X_i$、$\mu=\mathbb{E}[\bar X_n]$ とするとき、任意の $t>0$ に対し
$$ P(\bar X_n – \mu \ge t) \le \exp\!\left(-\frac{2nt^2}{(b-a)^2}\right),\qquad P(|\bar X_n – \mu| \ge t) \le 2\exp\!\left(-\frac{2nt^2}{(b-a)^2}\right) $$
証明. 中心化した変数 $Y_i := X_i – \mathbb{E}[X_i]$ を導入します。すると $\mathbb{E}[Y_i]=0$、かつ $X_i\in[a,b]$ より $Y_i\in[a-\mathbb{E}[X_i],\,b-\mathbb{E}[X_i]]$ で、この区間の幅は $b-a$ のままです（平行移動しただけ）。また $\bar X_n-\mu = \frac1n\sum_i Y_i$ です。
押さえたい事象は $\bar X_n-\mu\ge t$、すなわち $\sum_i Y_i \ge nt$ です。これに補遺3のChernoff法を $S:=\sum_i Y_i$、$a=nt$ として当てます。任意の $s>0$ で
$$ P\Big(\sum_i Y_i \ge nt\Big) \le e^{-snt}\,\mathbb{E}\Big[e^{s\sum_i Y_i}\Big] $$
次にMGFを積に分解します。$e^{s\sum_i Y_i}=\prod_i e^{sY_i}$ で、$Y_1,\dots,Y_n$ は独立（$X_i$ の独立性は平行移動で保たれる）なので、独立な確率変数の積の期待値は期待値の積に等しく、
$$ \mathbb{E}\Big[e^{s\sum_i Y_i}\Big] = \prod_{i=1}^n \mathbb{E}[e^{sY_i}] $$
各因子に補遺4のHoeffding補題（$Y_i\in$ 幅 $b-a$ の区間、平均 $0$）を当てると $\mathbb{E}[e^{sY_i}]\le \exp\!\big(s^2(b-a)^2/8\big)$ なので、
$$ \prod_{i=1}^n \mathbb{E}[e^{sY_i}] \le \prod_{i=1}^n \exp\!\left(\frac{s^2(b-a)^2}{8}\right) = \exp\!\left(\frac{n s^2(b-a)^2}{8}\right) $$
ここまでをまとめると、任意の $s>0$ で
$$ P\Big(\sum_i Y_i \ge nt\Big) \le \exp\!\left(-snt + \frac{n s^2(b-a)^2}{8}\right) $$
指数の肩を $s$ について最小化します（Chernoff最適化）。肩 $g(s)=-snt+\frac{ns^2(b-a)^2}{8}$ を $s$ で微分して $g'(s)=-nt+\frac{ns(b-a)^2}{4}=0$ を解くと、
$$ s^\ast = \frac{4t}{(b-a)^2} $$
これは $g$ が $s$ の上に凸でない（係数が正の2次関数）ので最小点です。$s^\ast$ を肩に代入します。第1項は $-s^\ast nt = -\frac{4nt^2}{(b-a)^2}$、第2項は $\frac{n(s^\ast)^2(b-a)^2}{8}=\frac{n}{8}\cdot\frac{16t^2}{(b-a)^4}\cdot(b-a)^2=\frac{2nt^2}{(b-a)^2}$。足すと
$$ g(s^\ast) = -\frac{4nt^2}{(b-a)^2} + \frac{2nt^2}{(b-a)^2} = -\frac{2nt^2}{(b-a)^2} $$
よって片側バウンド
$$ P(\bar X_n – \mu \ge t) \le \exp\!\left(-\frac{2nt^2}{(b-a)^2}\right) $$
を得ます。両側版は、$-Y_i$ も同じ幅の区間に入り平均 $0$ なので同じ片側バウンドが $P(\bar X_n-\mu\le -t)$ にも成り立ち、
$$ P(|\bar X_n-\mu|\ge t) = P(\bar X_n-\mu\ge t)+P(\bar X_n-\mu\le -t) \le 2\exp\!\left(-\frac{2nt^2}{(b-a)^2}\right) $$
と、2つの事象の確率の和（互いに排反）で押さえられます。$\blacksquare$
補遺6. Bernstein不等式（片側の主要評価まで）
主張. 独立な $X_1,\dots,X_n$ が $\mathbb{E}[X_i]=0$、$|X_i|\le M$、$\sum_i\mathbb{E}[X_i^2]=n\sigma^2$ を満たすとき、$S=\sum_i X_i$ について
$$ P(S\ge t) \le \exp\!\left(-\frac{t^2}{2\big(n\sigma^2 + \tfrac{Mt}{3}\big)}\right) $$
Hoeffdingとの違いは、Hoeffding補題で範囲だけに潰さず、$\mathbb{E}[X_i^2]$（分散の情報）を温存してMGFを評価する点です。証明はChernoff法ですが、鍵となる補題を先に立てます。
補題（1変数のMGF評価）. $\mathbb{E}[X]=0$、$|X|\le M$ のとき、$0 $$
\mathbb{E}[e^{sX}] \le \exp\!\left(\frac{s^2\,\mathbb{E}[X^2]}{2(1-sM/3)}\right)
$$ 補題の証明. 指数を級数展開して $k=2$ 以降の項を分散と $M$ で押さえます。$e^{sX}=1+sX+\sum_{k\ge 2}\frac{(sX)^k}{k!}$ の期待値を取ると、$\mathbb{E}[X]=0$ より1次項が消えて $$
\mathbb{E}[e^{sX}] = 1 + \sum_{k=2}^{\infty} \frac{s^k\,\mathbb{E}[X^k]}{k!}
$$ 各高次モーメントを抑えます。$|X|\le M$ なので $|X^k| = X^2\cdot|X|^{k-2} \le X^2 M^{k-2}$、よって $\mathbb{E}[X^k]\le \mathbb{E}[X^2]M^{k-2}$（$k\ge 2$）。さらに $k!\ge 2\cdot 3^{k-2}$（$k\ge 2$ で帰納的に確認できる：$k=2$ で $2\ge2$、$k\to k+1$ で左辺は $(k+1)$ 倍 $\ge 3$ 倍以上）を使うと、 $$
\sum_{k=2}^{\infty}\frac{s^k\,\mathbb{E}[X^k]}{k!}
\le \sum_{k=2}^{\infty}\frac{s^k\,\mathbb{E}[X^2]M^{k-2}}{2\cdot 3^{k-2}}
= \frac{s^2\mathbb{E}[X^2]}{2}\sum_{k=2}^{\infty}\left(\frac{sM}{3}\right)^{k-2}
$$ 最後の和は公比 $sM/3<1$ の等比級数で、$\sum_{j=0}^\infty (sM/3)^j = \frac{1}{1-sM/3}$。したがって $$
\mathbb{E}[e^{sX}] \le 1 + \frac{s^2\mathbb{E}[X^2]}{2(1-sM/3)}
$$ 最後に $1+u\le e^{u}$（すべての $u$ で成立する基本不等式）を $u=\frac{s^2\mathbb{E}[X^2]}{2(1-sM/3)}$ に当てて、 $$
\mathbb{E}[e^{sX}] \le \exp\!\left(\frac{s^2\mathbb{E}[X^2]}{2(1-sM/3)}\right)
$$ 補題が示せました。$\square$ 本体の証明. $S=\sum_i X_i$ に補遺3のChernoff法を当て、独立性でMGFを積に分解し、上の補題を各因子に使います。$0 $$
P(S\ge t) \le e^{-st}\prod_{i=1}^n \mathbb{E}[e^{sX_i}]
\le e^{-st}\prod_{i=1}^n \exp\!\left(\frac{s^2\mathbb{E}[X_i^2]}{2(1-sM/3)}\right)
$$ 指数の肩を足し合わせ、$\sum_i\mathbb{E}[X_i^2]=n\sigma^2$ を代入すると、 $$
P(S\ge t) \le \exp\!\left(-st + \frac{s^2\,n\sigma^2}{2(1-sM/3)}\right)
$$ この肩を $s$ について最小化します。標準的な選び方は $$
s^\ast = \frac{t}{n\sigma^2 + Mt/3}
$$ です（$0 $$
-s^\ast t + \frac{(s^\ast)^2(n\sigma^2+Mt/3)}{2}
= -\frac{t^2}{n\sigma^2+Mt/3} + \frac{1}{2}\cdot\frac{t^2}{n\sigma^2+Mt/3}
= -\frac{t^2}{2(n\sigma^2+Mt/3)}
$$ となり、 $$
P(S\ge t) \le \exp\!\left(-\frac{t^2}{2\big(n\sigma^2+\tfrac{Mt}{3}\big)}\right)
$$ が得られます。分母が「分散項 $n\sigma^2$ ＋有界項 $Mt/3$」の二相構造になっているのが本文で述べた特徴です。$\blacksquare$ McDiarmidの前に、その骨格となるAzuma–Hoeffding不等式を証明します。まず登場人物を初見向けに定義します。確率変数の列 $Z_0,Z_1,\dots,Z_n$ がマルチンゲールであるとは、「これまで（$Z_0,\dots,Z_k$）の情報をすべて知ったうえでの次の値の条件付き期待値が、現在値に等しい」、すなわち $\mathbb{E}[Z_{k}\mid Z_0,\dots,Z_{k-1}]=Z_{k-1}$ が成り立つことです。差 $D_k := Z_k – Z_{k-1}$ をマルチンゲール差分と呼び、定義から $\mathbb{E}[D_k\mid Z_0,\dots,Z_{k-1}]=0$（過去を知っても平均的には動かない＝公平な賭けの増分）が成り立ちます。 主張. $Z_0,\dots,Z_n$ をマルチンゲールとし、各差分が（過去に依存してよい）区間幅 $c_k$ の中に収まる、すなわちある過去依存の確率変数 $A_k$ が存在して $A_k \le D_k \le A_k + c_k$（過去で条件付けると差分は長さ $c_k$ の区間に入る）とする。このとき任意の $t>0$ に対して $$
P(Z_n – Z_0 \ge t) \le \exp\!\left(-\frac{2t^2}{\sum_{k=1}^n c_k^2}\right)
$$ 証明. $Z_n-Z_0=\sum_{k=1}^n D_k$ にChernoff法を当てます。$s>0$ で $$
P(Z_n-Z_0\ge t) \le e^{-st}\,\mathbb{E}\!\left[e^{s\sum_k D_k}\right]
$$ ここで独立和のときのように単純な積分解はできません（$D_k$ は独立とは限らない）。代わりに条件付き期待値で1段ずつ剥がします（tower property: $\mathbb{E}[U]=\mathbb{E}[\mathbb{E}[U\mid \text{過去}]]$）。$\mathcal{F}_{k}$ を「$Z_0,\dots,Z_k$ までの情報」とすると、 $$
\mathbb{E}\!\left[e^{s\sum_{k=1}^n D_k}\right]
= \mathbb{E}\!\left[e^{s\sum_{k=1}^{n-1} D_k}\;\mathbb{E}\big[e^{sD_n}\mid \mathcal{F}_{n-1}\big]\right]
$$ なぜなら $\sum_{k=1}^{n-1}D_k$ は $\mathcal{F}_{n-1}$ で決まる（既知の）量なので、条件付き期待値の外に出せるからです。いま $D_n$ は $\mathcal{F}_{n-1}$ で条件付けると「平均 $0$（マルチンゲール差分）かつ長さ $c_n$ の区間に入る」確率変数です。これはまさに補遺4のHoeffding補題の仮定（有界・平均0）を、条件付き分布に対して満たします。よって $$
\mathbb{E}\big[e^{sD_n}\mid \mathcal{F}_{n-1}\big] \le \exp\!\left(\frac{s^2 c_n^2}{8}\right)
$$ この上界は定数（過去に依存しない数）なので期待値の外に出せて、 $$
\mathbb{E}\!\left[e^{s\sum_{k=1}^n D_k}\right] \le \exp\!\left(\frac{s^2 c_n^2}{8}\right)\,\mathbb{E}\!\left[e^{s\sum_{k=1}^{n-1} D_k}\right]
$$ 同じ操作を $k=n-1,n-2,\dots,1$ と繰り返します（各段で1つ前の差分にHoeffding補題を当てる）。$n$ 回剥がし終えると（一番内側は $\mathbb{E}[e^{s\cdot 0}]=1$）、 $$
\mathbb{E}\!\left[e^{s\sum_{k=1}^n D_k}\right] \le \prod_{k=1}^n \exp\!\left(\frac{s^2 c_k^2}{8}\right) = \exp\!\left(\frac{s^2}{8}\sum_{k=1}^n c_k^2\right)
$$ これをChernoffの式に戻すと、任意の $s>0$ で $$
P(Z_n-Z_0\ge t) \le \exp\!\left(-st + \frac{s^2}{8}\sum_{k=1}^n c_k^2\right)
$$ 肩を $s$ で最小化します。$g(s)=-st+\frac{s^2}{8}\sum_k c_k^2$ を微分して $g'(s)=-t+\frac{s}{4}\sum_k c_k^2=0$、よって $s^\ast = 4t/\sum_k c_k^2$。代入すると Hoeffding不等式のときと同じ計算で $g(s^\ast)=-2t^2/\sum_k c_k^2$ になり、 $$
P(Z_n-Z_0\ge t) \le \exp\!\left(-\frac{2t^2}{\sum_{k=1}^n c_k^2}\right)
$$ が従います。$\blacksquare$ 主張. 独立な $X_1,\dots,X_n$ と、有界差分定数 $c_1,\dots,c_n$ を持つ関数 $f$（$i$ 番目の引数だけを変えると出力が高々 $c_i$ しか変わらない）に対して $$
P\big(f(X_1,\dots,X_n) – \mathbb{E}[f] \ge t\big) \le \exp\!\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right)
$$ 証明. 戦略は、$f-\mathbb{E}[f]$ をDoob martingale（ドゥーブのマルチンゲール）として表し、補遺7のAzuma–Hoeffdingを当てることです。 ステップ1：Doob martingaleの構成. 変数を1つずつ「明らかにしていく」条件付き期待値の列を作ります。$f=f(X_1,\dots,X_n)$ と略記し、 $$
V_k := \mathbb{E}[\,f \mid X_1,\dots,X_k\,]\qquad(k=0,1,\dots,n)
$$ と定義します。$V_k$ は「最初の $k$ 個の入力を見たうえでの $f$ の予測値」です。両端は意味がはっきりしていて、$k=0$ では何も条件付けないので $V_0=\mathbb{E}[f]$、$k=n$ では全変数が決まるので $V_n=f$ です。したがって $$
f – \mathbb{E}[f] = V_n – V_0 = \sum_{k=1}^n (V_k – V_{k-1}) = \sum_{k=1}^n D_k,\qquad D_k:=V_k-V_{k-1}
$$ と差分の和に分解できます。$\{V_k\}$ がマルチンゲールであることは tower property から従います：$\mathbb{E}[V_k\mid X_1,\dots,X_{k-1}]=\mathbb{E}[\mathbb{E}[f\mid X_1,\dots,X_k]\mid X_1,\dots,X_{k-1}]=\mathbb{E}[f\mid X_1,\dots,X_{k-1}]=V_{k-1}$。内側の条件付けがより細かいので、外側で平均すると粗い条件付けに戻る、というのがポイントです。 ステップ2：差分が幅 $c_k$ の区間に収まることを示す. Azuma–Hoeffdingを当てるには、$D_k$ が過去で条件付けたとき長さ $c_k$ の区間に入ることが要ります。独立性を使うと、$X_k=x$ を代入した「部分的に固定した期待値」 $$
g_k(x_1,\dots,x_k) := \mathbb{E}[\,f(x_1,\dots,x_k,X_{k+1},\dots,X_n)\,]
$$ （$X_{k+1},\dots,X_n$ だけ平均、$X_1,\dots,X_k$ は固定値）を使って $V_k=g_k(X_1,\dots,X_k)$、$V_{k-1}=g_{k-1}(X_1,\dots,X_{k-1})=\mathbb{E}_{X_k}[g_k(X_1,\dots,X_{k-1},X_k)]$ と書けます（独立性のおかげで $X_k$ について平均すれば $g_{k-1}$ になる）。そこで $X_1,\dots,X_{k-1}$ を固定したうえで、$x_k$ を動かしたときの $g_k$ の上限と下限を $$
U := \sup_{x_k} g_k(X_1,\dots,X_{k-1},x_k),\qquad
L := \inf_{x_k} g_k(X_1,\dots,X_{k-1},x_k)
$$ とおきます。$D_k = g_k(X_1,\dots,X_k) – \mathbb{E}_{X_k}[g_k(\dots,X_k)]$ は、$X_k$ について平均した値を引いているので、その値は $L$ 以上 $U$ 以下にあり、 $$
L – \mathbb{E}_{X_k}[g_k] \le D_k \le U – \mathbb{E}_{X_k}[g_k]
$$ なので $D_k$ は長さ $U-L$ の区間 $[\,L-\mathbb{E}_{X_k}[g_k],\,U-\mathbb{E}_{X_k}[g_k]\,]$ に収まります。あとは $U-L\le c_k$ を示せば十分です。任意の2つの値 $x_k, x_k’$ について、$g_k$ は $X_{k+1},\dots,X_n$ の期待値なので、有界差分条件（$k$ 番目だけ変えると $f$ は高々 $c_k$ しか変わらない）が期待値を取っても保たれ、 $$
\big| g_k(X_1,\dots,X_{k-1},x_k) – g_k(X_1,\dots,X_{k-1},x_k’) \big|
\le \mathbb{E}\big[|f(\dots,x_k,\dots)-f(\dots,x_k’,\dots)|\big] \le c_k
$$ これは「どの2点を比べても差は $c_k$ 以下」ということなので、上限と下限の差も $U-L\le c_k$ です。したがって $D_k$ は（過去で条件付けると）長さ $c_k$ の区間に入るマルチンゲール差分です。 ステップ3：Azuma–Hoeffdingを適用する. ステップ1で $\{V_k\}$ はマルチンゲール、ステップ2で各差分 $D_k$ は過去依存の長さ $c_k$ の区間に収まることが示せました。これは補遺7の仮定そのものです。$Z_k=V_k$、$Z_0=V_0=\mathbb{E}[f]$、$Z_n=V_n=f$ としてAzuma–Hoeffdingを当てると、 $$
P\big(f – \mathbb{E}[f] \ge t\big) = P(Z_n – Z_0 \ge t) \le \exp\!\left(-\frac{2t^2}{\sum_{k=1}^n c_k^2}\right)
$$ が得られます。$\blacksquare$ なお両側版は $-f$ も有界差分定数 $c_i$ を持つので同じバウンドが成り立ち、和をとって右辺を2倍すれば出ます。また $f=\sum_i x_i$、$c_i=b-a$ とすればHoeffding不等式（補遺5）が特殊ケースとして回収できることも、$\sum_i c_i^2=n(b-a)^2$ を代入すれば確認できます。 補遺で示した各バウンドが、本文の数値主張と矛盾しないこと、とくに証明の最適化ステップで使った最適パラメータ $s^\ast$ が確かにMGFバウンドを最小化していることを数値で確かめます。下のコードは独立に実行でき、Hoeffding補題の上界が経験MGFを上から押さえること、Hoeffdingの $s^\ast=4t/(b-a)^2$ が肩を最小化すること、Bernsteinが低分散でHoeffdingより鋭いことを順に検証します。 このコードを実行すると、(1) では3つの $s$ すべてで経験MGFが補題の上界以下（ 本記事では、機械学習の論文に頻出する「高確率で成り立つ」を支える集中不等式を、土台から解説しました。 集中不等式は、確率論と統計的学習理論をつなぐ蝶番です。次のステップとして、有限の仮説数 $M$ を無限集合に拡張する道具を学ぶと、現代の汎化バウンドの全体像が見えてきます。 次に読むと理解が深まる記事も挙げておきます。補遺7. Azuma–Hoeffding不等式
補遺8. McDiarmid不等式（完全証明）
補遺9. 証明の数値確認
import numpy as np
from math import exp, log
rng = np.random.default_rng(0)
# --- (1) Hoeffding補題: 有界・平均0の経験MGF <= exp(s^2(b-a)^2/8) ---
a, b = -1.0, 1.0
X = rng.uniform(a, b, size=2_000_000)
X = X - X.mean() # 平均0に中心化
for s in [0.5, 1.0, 2.0]:
emp_mgf = np.mean(np.exp(s * X))
bound = exp(s**2 * (b - a)**2 / 8)
print(f"補題 s={s}: 経験MGF={emp_mgf:.4f} <= 補題上界={bound:.4f} {emp_mgf <= bound}")
# --- (2) Hoeffding不等式の s* = 4t/(b-a)^2 が指数の肩を最小化するか ---
n, t = 50, 0.15
g = lambda s: -s * n * t + n * s**2 * (b - a)**2 / 8
s_star = 4 * t / (b - a)**2
grid = np.linspace(0.01, 4 * s_star, 4000)
print(f"\nHoeffding: s*={s_star:.4f} 肩(s*)={g(s_star):.5f} "
f"グリッド最小={grid[np.argmin([g(s) for s in grid])]:.4f}")
print(f" -2nt^2/(b-a)^2 = {-2*n*t**2/(b-a)**2:.5f} (片側指数の肩の理論値)")
# --- (3) Bernstein vs Hoeffding: 低分散で Bernstein が鋭い ---
def hoeffding_tail(t, n, a, b):
return exp(-2 * n * t**2 / (b - a)**2)
def bernstein_tail(t, n, sigma2, M):
return exp(-t**2 / (2 * (n * sigma2 + M * t / 3)))
n, M = 100, 1.0
T = 5.0 # 和 S = sum X_i のしきい値
for sigma2 in [0.05, 0.5]:
h = hoeffding_tail(T / n, n, -1.0, 1.0) # 平均のしきい t=T/n
be = bernstein_tail(T, n, sigma2, M)
print(f"\nsigma^2={sigma2}: Hoeffding={h:.3e} Bernstein={be:.3e} "
f"Bernsteinが鋭い={be < h}")
True）になり、補遺4のHoeffding補題が正しく上から押さえていることが確認できます。具体的には $s=1.0$ で経験MGFがおよそ $1.175$、上界 $e^{1/2}\approx 1.649$ で、確かに下回ります。(2) では解析的に求めた $s^\ast=4t/(b-a)^2=0.15$ がグリッド探索の最小点と一致し、そのときの肩が理論値 $-2nt^2/(b-a)^2=-0.5625$ にぴったり一致します——補遺5の最適化が正しいことの数値的裏づけです。(3) では分散 $\sigma^2=0.05$ の低分散ケースでBernstein裾がHoeffding裾より何けたも小さく（True）、$\sigma^2=0.5$ では差が縮むことが確認でき、補遺6の二相構造の主張と整合します。まとめ