novelty日記

データサイエンスやプログラムなど

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が与えられている時、あるサンプルを入力として損失を出力する写像集合。 この指標が0に近いほどデータ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}の2値一様分布からサンプルされると仮定する。 すると上の表現はもう少し一般化され次のようになる。

{ \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が出てくる。