汎化誤差を抑える様々な手法とその関係性（１）

今回は、二値ラベル分類の誤差解析に役立ついろいろな指標について解説していきます。

まずは、「経験ラデマッハ複雑度」です。「経験ラデマッハ複雑度」とは、関数のクラスFに対して定まる集合で、

$\displaystyle{ R_{n}\left( F\right) = E\left[ \dfrac{1}{n}\sup _{f\in F}\sum ^{n}_{i=1}\sigma _{i}f\left( x_{i}\right) \right] }$

ただし、 $\sigma_1, \ldots, \sigma_n$ は $P(\sigma_i=1) = P(\sigma_i=-1) = 1/2$ を満たす確率変数で、期待値は $Z_1, Z_2, \ldots, Z_n$ および $\sigma_1, \sigma_2, \cdots, \sigma_n$ についてとっています。

これは、関数のクラスの「複雑度」を表す一つの指標です。

直観的には、 $\sigma_i$ はランダムラベルとみなすことができ、 $\displaystyle{ \sigma _ {i} f\left( x _ {i}\right) \gt0 }$ のとき関数fの当てはまりが成功しており、そうでないとき失敗しています。つまり、ラデマッハ複雑度は、どんなラベルに対しても、関数をクラスの中からうまく選べば、ある程度大きな値をとる（＝当てはめることができる）ことを（大雑把には）意味しています。

これは、何に役立つかというと深層学習における汎化誤差の解析です。詳しくは述べませんが、この値を用い、「どれぐらい過学習してしまうか」を確率的に不等式で抑えることができるのです。

この「ラデマッハ複雑度」についてですが、以下の不等式が「Massartの補題」というものから成立することが知られています。（証明略）

二値仮説関数の集合をhのクラスをHとし、Hは有限集合とすると

$\displaystyle{ R_{n}\left( H\right) =\sqrt{\dfrac{2\log \left| H\right| }{n}} }$

以上のことを仮定して、growth function, VC dimension, covering numberについて、さらにそれらの関係性について説明をしていきます。

まず、growth functionとは、fを二値関数としてそのset をFとすると、n個の点 $x_1, x_2, \ldots, x_n$ で $\displaystyle{ \tau _ {F}\left( x _ {1}, \ldots ,x _ {N}\right):=max _ {\left( x _ {1}, \ldots ,x _ {N}\right) }\tau _ {F}\left(x _ {1}, \ldots ,x _ {N}\right) }$ と定義したとき