Sen(Qian)’s Memo

前回はこちら。📄(講義ノート)統計的機械学習第5回

📄(講義ノート)統計的機械学習第3,4回 でRademacher複雑度を導入することで、理想誤差を0にできる仮説、そして有限仮説の集合ではない場合でも解析できるとしていた。しかし、それは損失関数についてのRademacher複雑度であり、仮説についてのRademacher複雑度の変換$R_n(\mathcal{L}_{01}) = \frac{1}{2} R_n(\mathcal{H})$がわかった。

また、有限仮説の集合であれば、Massartの有限仮説の補題を用いることによって、Hoeffdingの不等式で得た結果と同じ結果が得られるとわかった。Massartの有限仮説の補題自体は非常に有益な補題。

今まででは、$1 - \delta$以上の確率で

で成り立つという結果がわかった(McDirmidの不等式など)。これは理想の$L$について、経験的に決めた$\hat{h}$と理想の仮説$h^*$の差であった。しかし、経験的に決めた仮説の、経験的な損失$L_n(\hat{h})$と$L(\hat{h})$との差も重要である。

$1 - \delta$以上の確率で、以下の式が成り立つ。

まず、📄(講義ノート)統計的機械学習第3,4回 でのMcDiarmidの不等式+Rademacher複雑度で、$L(h) - \hat{L}_n(h)$は上限で評価すると、$1 - \delta$以上の確率で以下が成立していた。(これの符号を逆転させたものの上限と両方していった 第3，4回のノートでは$1 - \delta / 2$以上の確率としていたので、$log (2 / \delta)$となっていた)

よって、これで右辺を抑えることができるので示せた。

今までは損失関数のクラス、仮説のクラスについてのRademacher複雑度について論じてきたが、データは理想的な分布からえるという仮定だった。

これを経験的なデータから計算する、ということはもちろんできる。以下のように期待値はデータ分布ではなくなり、Rademacher変数のみの期待値となる。

この経験Rademacher複雑度について、以下の式が成り立つ。2つのデータ集合$S_n, S ^ \prime _n$があり、1つだけデータ$Z_j \to Z_j ^ \prime$と変わっていて違うとする。仮説集合は$\mathcal{F} : f : \mathcal{Z} \to [a,b]$である。

つまり、データが違くとも、仮説に対するRademacher複雑度は1つ変えるだけなら- 高々$(b - a) / n$しかずれない。

一般的に以下が成り立つ。別々にsupとったものの差より、一緒に動かしたsupのほうが大きい。

Rademacher複雑度を展開すると、以下のようになる。上の式を利用してだいぶ打ち消すことができ、最終的には$f$の取りうる値の最大の差で抑えることができる。

これによって、経験Rademacher複雑度のズレを評価できたので、McDiarmidの不等式を使っていく。

$1 - \delta$以上の確率で、以下が成り立つ。

つまり、経験Rademacher複雑度は理想と比べてのズレを評価することができた。今までは理想的データ分布に基づくズレについて議論してきたので、これらを統合できるようになる。

なお、理想的なデータ分布を用いたRademacher複雑度の評価をしたのは、McDiarmidの不等式を用いて示せた以下の式である。$1 - \delta$以上の確率で成り立つ。

Rademacher複雑度のルールから、損失関数集合と仮説集合の関係性がわからないと、Rademacher複雑度の評価は損失関数の集合の評価で終わってしまう。

ここで、有名な各モデルについての分析していきたい。

そこで、重要なLedoux Talagrandの補題というのについて説明する。

界隈でよく言われる、Talagrandの補題である。

$\phi : \mathbb{R} \to \mathbb{R}$を、リプシッツ連続な関数でリプシッツ定数が$L_\phi$であるとする。つまり、

そして、$\mathcal{F} \subset \mathbb{R}^n$であるとき、以下が成り立つ。

つまり、傾きの上界を抑えられる関数の場合、その傾きの上界=リプシッツ定数$L_\phi$とすることで、外に出すことで抑えることができる。

以下のことを$i=1, 2, \cdots$と繰り返せばよい。

まず1つだけ出してから、Rademacher変数は$\frac{1}{2} (+1) \cdot A + \frac{1}{2} (-1) \cdot B$と分解できることを利用する。このように出すことができるが、別々のsupに分解していることについては、=ではなく$\leq$では？？

そしてくくりだした部分について、仮定を用いることができ、最後に$f, f ^ \prime$は対称性を持っているのでsupをどうせとっているので、絶対値を外すこともできる。これをずっと繰り返していくことで、Talagrandの補題を証明することができる。

入力$\mathbf{x}$に対して、ラベル$y=+1. -1$とすると、損失関数に入れるのはだいたい$\mathbf{x}$と予測した結果。$||\mathbf{x} ||_2^2 = C_2^2$という二次ノルムの上界で抑えられるとする。

そして、仮説は$h(\mathbf{x}) = \mathbf{w} ^ T \mathbf{x}$であるとする。この時、重みのノルムの上界は$||\mathbf{w}||_2^2 \leq B_2$だと、同様に二次ノルムで抑えられるとする。この制限は実質的にはL2正則化項を損失関数に加えることに相当する。つまり、ここで仮説空間は線形モデルであるうえ、重みのL2ノルムに上界を設けたものである。

、Rademacher複雑度は以下のように抑えられる。

愚直に展開したあと、内積の形であるので、$\sigma_i$をデータ$x_i$にまとめて、そこからコーシー・シュワルツの不等式を用いることで$||\mathbf{w}||_2$と$||\sum_{i=1}^n \sigma_i x_i||_2$に分割できる。これでうまく$\mathbf{w}$を出す形になった。目標は$sup$よりも外に出して、すでに分かっている制約$||\mathbf{w}||_2^2 \leq B_2$を適用させること。

次に、$||\mathbf{w}||_2$は、上界をとれば外に$B_2$として出すことができる。中に残った部分に関してはまた評価を進める。

中にあるのは一次の形なので、2乗の和のルートということになる。ここでほしいのは、Rademacher変数の線形和についての期待値(ルートは評価するうえで邪魔なので出したい)

ここで、ルートは上に凸の関数なので、Jensenの不等式を用いることでうまく出すことができるのだ。

期待値の中は単純に2乗であるが、Rademacher変数入りのものを二乗するときは、Rademacher変数がそれぞれ独立になることに留意。つまり、$\sigma_i, \sigma_j$についての期待値になるということ。

そして、$\mathbb{E}[\sigma_i \sigma_j] = 0, i \neq j$が成り立つ。$i=j$ならば1となる。これを利用すると、2乗の項しか残らないし、しっかり$||\mathbf{x}||_2^2 \leq C_2^2$を利用することができ、評価することができた。

これによって、重みについてL1ノルムについての評価なので、L1正則化？

データ$\mathbf{x}$について、最大の成分が有界である。つまり、$||\mathbf{x}||_{\infty} \leq C_{\infty}$となる

同様に、$h(\mathbf{x}) = \mathbf{w} ^ T\mathbf{x}$を使うとする。

重みについて、L1ノルムが上界であるとき、$||\mathbf{w}||_1 \leq B_1$である。

この時、Rademacher複雑度は、以下のように抑えられる。

なお、なぜ$L_\infty$ノルムを使うのかというと双対ノルムだから、以下のように双対ノルム$|| \cdot ||_*$は定義されている。対象のベクトルに対して、今のノルムで1以下のベクトルとの内積の最大値である。

ここで、$\mathbf{x}$が$L_\infty$ノルムで制約されている(最大の成分が有界)とき、$\sup$を満たすのは同じ向きを向いている$L_\infty$ノルムが1以下(最大成分が1)のベクトルであり、これは$(1,1,\cdots)$となる。よって、この内積を計算すると、実質すべての$\mathbf{x}$の成分を足し合わせるので、$|| \cdot ||_*$は$L_1$ノルムである。

📄(講義ノート)統計的機械学習第5回 でやったMassartの有限仮説の補題を使う(かたちがいかにもそれ)
$\mathcal{A} \in \mathbb{R}^n$の有限集合とする。

Racdemacher複雑度の$\sup$として、線形モデルかつ重みベクトルがL1ノルムで制限されているという仮説集合を考えている。

Holderの不等式を使う。L2ノルムの場合ここでコーシー・シュワルツの不等式を使っていた。Holderの不等式では以下のようになっていた。

任意の数列$\{ a_i \}, \{ b_i \}$について、$p > 1, 1 / p + 1 / q = 1$を満たす$q$について以下が成り立つ。等号成立条件は$p=q=2$であり、通常の我々が見る内積でのコーシー・シュワルツの不等式にあたる。

つまり、$L_p$ノルムと$L_q$ノルムの積は普通の内積以上ということ。

そして、これを満たす$p, q$はお互いに双対ノルムの関係にある。

実際に、$p=1, q = \infty$でも成り立つ。

このHolderの不等式について、二行目は内積なので$\mathbf{w}$についての$L_1$ノルムと、$\sigma _i x_i$についての$L_\infty$ノルムについて分けられて、その積以下と抑えることができる。

そして、$\mathbf{w}$の$L_1$ノルムのほうについて明らかに最大値が$B_1$であることから、出すことができてて期待値の中で$L_\infty$ノルムが残る。

さて、$L_\infty$については最大の成分を取り出すので、$\sup$で一番最大の値をとる$j \in \{1, \cdots, d\}$を考える。そして、その中のΣではRademacher変数を掛け合わせているので、ちょうどMassartの有限仮説の補題を使える形である(仮定により、各成分$x_i$は有界)。

よって、使うことによって(示した形の左辺の$1/n$は右辺に移すせば$\sqrt{n}$になる)

$|\mathcal{A}|=2d$となっていて、これは$x_i$は実質最大を取ると考えるなら、$d$次元なら各成分$+B_1, -B_1$と2つあるので、$2d$個の有限集合である。

L2正則化はデータも、係数も2乗ノルムで制限されている。L1正則化はデータは成分の最大値が、係数は1乗ノルムが制限されている。

実をいうと上の式も$d$を持っている。同じデータに対して、$||\mathbf{x}||_\infty \leq C_\infty$と抑えられるとき、データのL2ノルムは$||\mathbf{x}||_2 = C_2 = \sqrt{d} C_\infty$となる(各成分が最大値をとって$d$個足し合わせる感じ)

このように、$C_2$は$\sqrt{d}$を含んでいる、というわけである。

L1正則化はsparse化することができる。📄NNDL 第7章 Networkの最適化と正則化

説明変数のほうがデータ数よりも多い(over parameterized)の時は、実質どれを選ぶかを決定できず、選ばれたor選ばれなかった特徴量に解釈性があるわけではない。

また、相関が高い説明変数の集合があるとき、そこから1つしか変数しか選ばれない(良くも悪くも)

確かに選んだものの説明はできるが、選んだものが本当に最重要かはわからない。あくまで仮説の生成。