VC次元・Rademacher複雑度

1. VC次元

VC次元（Vapnik-Chervonenkis dimension）：仮説クラスHが「粉砕」できる最大の点集合のサイズ。

粉砕（Shattering）:
点集合S = {x₁, ..., xₘ} がHで粉砕される
⟺ 任意のラベル付け y ∈ {0,1}^m に対して
   ∃h ∈ H: ∀i, h(xᵢ) = yᵢ

VC(H) = max{m : ∃S, |S|=m, Hが Sを粉砕}

VC(H) = d のとき、
m点上でHが取りうるラベリングの数 ≤ Σ_{i=0}^{d} C(m,i) = O(m^d)

→ 無限クラスでも有効なサンプル複雑度

確率 1-δ 以上で、任意の h ∈ H に対して:

|error(h) - error_train(h)| ≤ O(√(d·log(m/d)/m) + √(log(1/δ)/m))

d: VC次元, m: サンプル数

汎化誤差εを達成するには：

m = O((d/ε²)log(1/ε) + (1/ε²)log(1/δ))

データ依存的な複雑度尺度：

経験的Rademacher複雑度:
R̂_S(H) = E_σ[sup_{h∈H} (1/m)Σᵢ σᵢh(xᵢ)]

σᵢ ∈ {-1, +1}: 一様ランダム（Rademacher変数）
S = {x₁,...,xₘ}: データセット

確率 1-δ 以上で:
error(h) ≤ error_train(h) + 2R̂_S(H) + √(log(1/δ)/2m)