Sen(Qian)’s Memo

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

前回は$L(h^*) \neq 0$、仮説集合が無限と条件をどんどん緩くしたうえで、誤差上界の評価の手法について紹介された。$L(h^*) \neq 0$の時はHoeffdingの不等式で分布の裾で評価した。仮説集合が無限の時は、McDiarmidの不等式で$\hat{G}_n(h) = L_n(\hat{h}) - L(h^*)$と評価した。

損失関数が取る値が$[a,b]$の時、汎化誤差の上界は以下のようになることがわかった。

$R_n(\mathcal{L})$は損失関数の集合についての評価である。ただ、損失関数じゃなくて仮説集合のRademacher複雑度にやはり評価したい。

• 仮説関数は$h : X \to \{ +1, -1 \}$であり、これの集合を$\mathcal{H}$とする。
• 損失関数は01損失であり、$l((x,y),h) = \mathbf{1}[h(x) \neq y]$となる。これの集合を$\mathcal{L}_{01}$とする。

この時、以下の式が成り立つ。

このような変換関係が成り立つ。

指示関数$\mathbb{1}[h(x) \neq y] = \frac{1}{2} (1 - yh(x))$と書き換えることができる(よくある)。

3行目から4行目の式変形では、Rademacher変数$\sigma_i$の和はベルヌーイ分布で半々で1か-1をとることから、実は0であること言うことを利用して消した。その結果、$R_n(\mathcal{L}_{01})$を$R_n(\mathcal{H})$で評価する計算ができた。

有限仮説集合$\mathcal{H}$があるとする。この時、以下のMassartの有限仮説の補題によって、以下のものが成り立つ。

ここで、Massartの有限仮説の補題は以下のとおりである。$\mathcal{A} \in \mathbb{R}^n$の有限集合とする。

$x_1, \cdots, x_n$のデータがあるとする。それらにすべてとある有限仮説集合の元$h \in \mathcal{H}$で予測をする。それを$\mathcal{A}_n$とする。

有限仮説集合で、有限個のデータなので、$\mathcal{A}_n$は有限集合であり、$\{ -1, +1 \} ^ n$の部分集合でもある。以下のように各$\mathcal{A}_n$の元のベクトルの成分の2乗和の上限は高々$n$である。

ここで、Massartの有限仮説の補題と、$\mathcal{A}_n \subset \mathcal{H}$(複数通りの仮説$h$が結果的に同じ$\mathcal{A}_n$の元を生成することがある)によって、以下の式変形が成り立つ。

• ここでは$h(x_i)^2$は上限$M^2=n$が存在することで、Massartの有限仮説補題を利用。
• 中のRademacher複雑度の部分の期待値をMassartの有限仮説で抑えた。
• 期待値を外してもいいので、結果を得る。

結果として、有限仮説集合$\mathcal{H}$のRademacher複雑度は、以下のように評価できる。

そもそも有限仮説集合の場合、誤差上界の評価をするときはHoeffdingの不等式でよく(📄(講義ノート)統計的機械学習第3,4回 )そこでは、上界は以下のようになっていた。

このルートの中の左辺がRademacher複雑度にあたるもの？であるが、見事なまでに一致している。

$\mathcal{A} \in \mathbb{R}^n$の有限集合とする。

まず、一般的に有限集合$X$において、$f(x^*) = \sup _{x \in X} f(x)$をとる。この時、指数関数は単調増加関数なので、以下の式はもちろん成り立つ。このように$\sup$をいじることで、Rademacher複雑度をどうにかできる。

証明の本体を説明する。

まず、任意の$\lambda > 0$を考えて、それを示したい式の左辺になぜか乗じる。

• まず、先ほどの一般的な$\sup$の変形を利用する。$\sup A = \log (\sup (\exp))$という感じ。
• 2行目から3行目は$\sup$を総和で上から押さえている。よくある変形テクらしい。
• 3行目から4行目は、Jensenの不等式を使う。$\log$は凸関数であるので、Jensenの不等式により凸関数$h = \log$は以下が成り立つ。
  • つまり、凸関数に代入した後の和(や期待値)より、和(や期待値)をとった後凸関数に代入したほうが等しいか大きい。

さらに式変形を重ねていく。$\exp$の中の総和を外に出して$\prod$にすることができ、$\mathbb{E}_\sigma$も$\mathbf{a} \in \mathcal{A}$の総和の中に入れていい。

ここで、指数関数の中の総和を外に出したうえ、$\mathbb{E}_{\sigma_i}$を中に持ってきたことによって、独立した各変数の期待値の積という形にすることができ、操作しやすい。これもよくやる変形。

ここからもっと変形していく。ここでやりたいのは、Rademacher変数の期待値の部分を上から押さえることで消滅させたい。こういう時は、Rademacher変数による影響を高々で抑えていくことができる。

ここでは、以下の2点を利用した。

1. Rademacher変数を分解した。半々の確率で＋1や-1をとるというのを愚直に分解すると、簡単な目的関数ならそれだけですっきりする。
2. 指数関数については、以下の特性がある。

最後の仕上げの証明の式変形をする。

• Massartの有限仮説の仮説を用いることで、上限があるということ。これを第2から第3行目への式変形で使用した。
• $\mathcal{A}$自身も有限集合であるという仮説であるので、元の数で抑えることができる。

ここまでで、大体Massartの有限仮説の証明は終わる(おおむね形が出てきた)。しかしなぜ$\lambda$が必要なのだろうか？最初に$\lambda$を付け加えておくと、$\exp(x^2/2)$となる部分で$\lambda^2$を作れて、最終的に相加相乗平均のかたちにできるからだ。

両辺を$\lambda$で割ると、以下のようになる。

相加相乗平均を用いて上限を低く抑えることを考える。書いてあるように、$\lambda = \sqrt{2\frac{\log |\mathcal{A}|}{M^2}}$とすれば、上限を低く抑えて最終的に、$\sqrt{2M^2 \log |\mathcal{A}|} / n$となる。

気持ち: 非常に技巧的な証明ですね！

やりたいことは、$L(\hat{h}) - L(h^*)$を、$1 - \delta$以上の確率で$\epsilon$に抑えたいということ。

これについていろいろ今まで考えてきた 📄(講義ノート)統計的機械学習第2回 📄(講義ノート)統計的機械学習第3,4回 が、別解もあるので軽く紹介していく。

• 一項目の$\{L(\hat{h}) - \hat{L}_n(\hat{h})\}$は、$\hat{h}$は訓練データに依存するため、$\hat{L}_n(\hat{h})$は独立な損失関数の和とならず、確率的なふるまいを分析するのは難しい。
• $\{ \hat{L}_n(h ^ *) - L(h^*) \}$は$h^*$は訓練データから独立しているので、分析は容易である。
  • 大数の弱法則で0へ収束するとわかる。
  • 中心極限定理で、収束速度は$O(1 / \sqrt{n})$であるともわかる。

汎化誤差の導出で今までは、指数関数、Hoeffdingの不等式、McDiarmidの不等式で評価していた。これらについて別解を考えてみる。

同じ仮説に対して、違う損失関数のものは、$\sup_h$で抑えられる。それを使い、McDiarmidの不等式に代入して終わり。

$\hat{h}$は嫌なので、減らしていきたい。実はその部分は$\hat{G}_n$であったので、変形していく。期待値からの外れをわざわざ作り出して、

• (A)は普通に抑えられる。
  • 普通のHoeffdingの不等式で抑えられる。
• (G)は中心極限定理で評価できる。まさにMcDiarmidの不等式で評価する。
• $\mathbb{E}[\hat{G}_n]$をどう評価するか？ここは前に議論した通りRademacher複雑度となる。