ラデマッハ複雑度と一様大数の法則のお気持ちについて

大数の法則はいろいろな書籍で言及される超有名な法則なわけですが、

昨今の機械学習などではこれを少し発展させて、

所々の仮定のもとで以下の一様大数の法則を用いたりします。

$\displaystyle \sup_{g \in G} |\frac{1}{n}\sum_{i=1}^{n}g(X_{i})-E[g(X)]| \xrightarrow{p} 0$

いわゆる大数の法則との違いは関数クラスでsupをとっているところです。

機械学習では学習した関数が（全ての）訓練データに依存する構造になっているので、

そこの依存関係を考慮した上で確率収束の議論をやりたいからです。

つまり、何らかの学習を経て得られた $g$ は $n$ 個のデータに依存して決まっており、

各 $g(X_i)$ が独立ではないため、通常の大数の法則が適用できなくなっています。

そこで、supを考えることでデータ依存をなくした議論をしようとしているわけです。

てなわけで、

今回は一様大数の法則と密接に関連するラデマッハ複雑度について見ていきます。

Rademacher complexity

$||g||_{\infty} \le M$ が $\forall g \in G$ とする。

このとき、関数族 $G$ に対してラデマッハ複雑度を以下のように定義します。

$\sigma_i$ を以下を満たすiidなラデマッハ変数とする。
$\displaystyle P(\sigma_i=1)=P(\sigma_i=-1)=\frac{1}{2}$
このとき、観測データ $x_1, x_2,...$ を用いて以下のように定義される変数を経験ラデマッハ複雑度といい
$\displaystyle \hat{R}_{n}(G)=E_{\sigma}[\sup_{g\in G}|\frac{1}{n}\sum_{i=1}^{n}\sigma_i g(x_i)| ]$
この $x$ が確率分布に従っているとして、期待値をラデマッハ複雑度といいます。
$R_{n}(G)=E_{X}[\hat{R}_{n}(G)]$

ここで、 $\hat{R}_{n}(G)$ において、サンプル平均 $\displaystyle \frac{1}{n}\sum_{i=1}^{n}g(x_i)$ ではなく

$\displaystyle \frac{1}{n}\sum_{i=1}^{n}\sigma_i g(x_i)$ のように $\sigma_i$ を挟んだものを考えています。

これは、ランダムなノイズ $\sigma_i$ と $g(x_i)$ の相関みたいなものを表していて、

関数クラス $G$ においてその相関をどれくらい高めることができるか

というのがラデマッハ複雑度の直感的なイメージかと思います。

別の言い方をすると、

ランダムノイズに対して $G$ がどれくらい追従出来るかの指標ですかね。

なお、今後

$\displaystyle Pg = E[g(X)], P_ng = \frac{1}{n}\sum_{i=1}^{n}g(X_{i})$ とする。

で、

早速このラデマッハ複雑度にまつわる定理を見ていきます！

Thm (対称化)
$E_{X_i}[ \sup_{g\in G}|(P-P_n)g| ] \le 2R_n(G)$

この定理、一様大数の法則と似ていますよね！

この期待値の中身は実は結構解析しにくかったりするので、

このようにラデマッハ複雑度で上から抑えて、

そしてそのラデマッハ複雑度をさらに何かで抑えたりするのがよく使われる手法です。

それではこれを証明していきます。

左辺は、 $X_i$ と同じ分布に従う $X_i'$ を用いて以下のように変形でき

$\displaystyle = E_{X_i}[ \sup_{g \in G}|E_{X_i'}[ \frac{1}{n}\sum_{i=1}^n g(X_i') ]-\frac{1}{n}\sum_{i=1}^n g(X_i)|]$

イェンセンの不等式( $E[|・|] \ge |E[・]|, E[sup(・)] \ge sup(E[・])$ )より

$\displaystyle \le E_{X_i,X_i'}[ \sup_{g \in G} |\frac{1}{n}\sum_{i=1}^n(g(X_i')-g(X_i))|]$

$X_i$ と $X_i'$ は同じ分布に従うので

$\displaystyle = E_{\sigma_i} E_{X_i,X_i'}[ \sup_{g \in G} |\frac{1}{n}\sum_{i=1}^n \sigma_i(g(X_i')-g(X_i))|]$

三角不等式より

$\displaystyle \le E_{\sigma_i} E_{X_i'}[ \sup_{g \in G} |\frac{1}{n}\sum_{i=1}^n \sigma_ig(X_i')|] + E_{\sigma_i} E_{X_i}[ \sup_{g \in G} |\frac{1}{n}\sum_{i=1}^n \sigma_ig(X_i)|]$

フビニの定理より

$= 2R_n(G)$

とまぁこれで、

確率変数 $\sup_{g\in G}|(P-P_n)g|$ の期待値を上から抑えることに成功しました。

続いて、この確率変数の裾確率について見ていきます。

Thm
$\displaystyle P(\sup_{g\in G}|(P-P_n)g| \ge 2R_n(G)+ M \sqrt{\frac{2\log{\frac{1}{\delta}}}{n}}) \le \delta$

これは、 $\sup_{g\in G}|(P-P_n)g|$ の期待値が $2R_n(G)$ で抑えられることを思い出すと、

$\sup_{g\in G}|(P-P_n)g|$ が期待値からどれくらいずれうるのかを示しています。

これを示すために以下の関係性を利用します。

McDiamid の不等式
$X_1, ...,X_n$ を独立な（同一とは限らない）確率変数とする。
$f$ を可測関数とし
$|f(x_1,...,x_i,...,x_n)-f(x_1,...,x_{i'},...,x_n)| \le C_{i}$
が任意の $x_1,...,x_n,x_{n'}$ について成り立つとき、
$\displaystyle P(f(X_1,...,X_n)-E[f(X_1,...,X_n)] \ge \epsilon) \le \exp\{-\frac{2\epsilon^2}{\sum_{i=1}^{n}c_{i}^2}\}$

いま、 $||g||_{\infty} \le M$ より

$\displaystyle f(x_1,...,x_n) = \sup_{g \in G}|\frac{1}{n}\sum_{i=1}^n g(x_i)-Pg|$ とおくと

$f(x_1,...,x_n) - f(x_1,...,x_{i'},...,x_n)$

$\displaystyle = \sup_{g \in G}|\frac{1}{n}\sum_{j\neq i}^n g(x_i) + \frac{g(x_{i})}{n} + \frac{g(x_{i}^{'})}{n} - \frac{g(x_{i}^{'})}{n} -Pg| - \sup_{g \in G}|\frac{1}{n}\sum_{j\neq i}^n g(x_j) + \frac{g(x_{i}^{'})}{n} -Pg|$

$\displaystyle \le \sup_{g \in G}|\frac{1}{n}\sum_{j\neq i}^n g(x_i) + \frac{g(x_{i}^{'})}{n} -Pg| + \sup_{g \in G} |\frac{g(x_{i})}{n} - \frac{g(x_{i}^{'})}{n}|- \sup_{g \in G}|\frac{1}{n}\sum_{j\neq i}^n g(x_j) + \frac{g(x_{i}^{'})}{n} -Pg|$