Rademacher Complexityの考え方

understanding machine learningに出てくるrademacher complexityの導入がなんかしっくり来た。

まずある分布DよりデータSが与えられた時、representativenessという指標を次のように定義する。

${ \displaystyle \sup_{f \in \mathcal{F}} \hspace{1mm} (L_D (f) - L_S (f) ), }$

${ \displaystyle L_D (f) = E_{z \approx \mathcal{D}} \left[f(z)) \right], L_S (f) = \frac{1}{m} \sum^{m}_{i=1} f(z_i). }$

ここで、Fは仮説クラスHが与えられている時、あるサンプルを入力として損失を出力する写像集合。この指標が０に近いほどデータSによる損失計算が真の分布に基づく損失に迫っているため、正しい評価ができている事になる

ところで真の分布Dは分からないので、実際にこの指標を評価する場合は、交差検定と似たようなノリでデータを切り分けて以下のように近似する。

${ \displaystyle \sup_{f \in \mathcal{F}} \hspace{1mm} (L_{S_2} (f) - L_{S_1} (f) ), }$

S1とS2の切り分け方に関しては、σ1,..,σmを導入しσi=1ならS1、σi=-1ならS2とする。さらにσの値は{1,-1}の２値一様分布からサンプルされると仮定する。すると上の表現はもう少し一般化され次のようになる。

${ \displaystyle \frac{1}{m} E _{\sigma \in \left\{1,-1 \right\}} \left[ \sup_{f \in \mathcal{F}} \sum^{m}_{i=1} \sigma_i f(z_i) \right] }$

これでrademacher complexityが出てくる。