Sen(Qian)’s Memo

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

前回は真の損失関数$L$で、有限の訓練データについて$\hat{h}$が最適であったとき、以下のような式が成り立っていた。$\hat{h} \in \argmin _{h \in \mathcal{H}} \hat{L}_n (h)$つまり経験損失を最小化させるものを$\hat{h}$だとすると、少なくとも$1 - \delta$以上の確率で

ただし、ここでは、最適な$\exist h^*, L(h^*)=0$が存在しない場合を考える。

非常に基礎的なモデルから解析していく。

• $\mathcal{X} \subset \mathbb{R}^d$が学習データ
• $\mathcal{Y} = \{+1, -1\}$がラベルである二値分類。
• 損失関数はすべて01損失。つまり、損失関数というのは条件を満たさない確率そのものである。

仮説は2つの仮定の下で行う。

• 仮説空間$\mathcal{H}$は有限である。

この仮定の下で、$\hat{h} \in \argmin _{h \in \mathcal{H}} \hat{L}_n(h)$とする。この時、少なくとも$1 - \delta$以上の確率で以下の式が成り立つ。

理想損失を0にするような識別器が存在しないとき、$1/n \to 2/n$となり、$1 / \delta \to 2/\delta$となっている。

📄(講義ノート)乱択アルゴリズム第2回 を参考

各確率変数が独立で、それぞれ上と下にとる値が定まっている=有界である。

ここで、経験平均と平均の期待値が$\epsilon$より大きくずれるのは、上限で評価できるというもの。

下の式は、両側のすそを考慮したものである。

今まで通り、$L(\hat{h}) - L(h^*)$ではなく、すべての$h$についての上限$\sup _{h \in \mathcal{H}} |L(h)-\hat{L}_n(h)|$を考える。ある$h \in \mathcal{H}$で成り立つので、Union Boundで示していく感じ。

ある$h$を固定すると、$\hat{L}_n(h)$は$n$個の独立な損失関数$l((x_i, y_i), h)$の平均であり、$L$も$\hat{L}_n$も確率と同等なので、$[0,1]$の値をとって有界である。なので、Hoeffdingの不等式を使うことができる。よって、以下のようになる。

そこから、$h \in \mathcal{H}$で仮説集合は有限サイズだという仮説なので、以下のようにUniform Convergenceで、集合全部のサイズで抑える形で確率の和というかたちで変形できる。

ここで、以下のように$\delta$を置くと、与えられたものを得る。

ここで、前回の授業のように、$L(\hat{h}) - L(h^*)$は$\sup_{h \in \mathcal{H}} | \hat{L}_n(h) - L(h) |$で一様収束性を使って評価することができることを使う。

ここで不等式を逆にすることで、以下のようになる。先ほど定義した$\delta$を使う。

なので、左辺と右辺の評価からして、少なくとも$1 - \delta$以上の確率で、以下が成り立つ。

証明したかったのは$L(\hat{h}) - L(h ^ *)$の差による不等式だが、不等式をそのまま使うと評価できるのは$L_n(\hat{h}) - L(h ^ *)$のかたちである。なので最初から$\epsilon / 2$で計算していて、その後変換をした。

1. $L(\hat{h}) - L(h^*)$は$\sup_{h \in \mathcal{H}} | \hat{L}_n(h) - L(h) |$で一様収束性を使って評価を変える。
2. $\sup$は有限仮説集合であることを利用して、Uniform Convergenceを使って抑える。
3. Uniform Convergenceの合算する各要素の$Pr[|\hat{L}_n(h) - L(h)| > \frac {\epsilon}{2}]$であるが、この確率をHoeffdingの不等式を用いて評価した。
   1. 前回の理想損失を0にできる$h^*$が存在していたときは、毎回のサンプリングでは高々$(1-\epsilon)$の確率でしか正解できないということで上界を評価した。
   2. 今回は理想損失を0にできないし、$h^*$が理想損失をどれほどに抑えられるともわからない。
   3. ここをもうちょっと掘り下げてみる。

$L(h^*)=0$ができる場合は、$O(1/n)$のオーダで収束するが、できない場合は$O(1/\sqrt{n})$のオーダで収束する。

$L(h^*)=0 \Rightarrow \hat{L}(h^*) = 0$になるので、経験損失が0になるものの中から、適格となるものを選べばよかった。これは結局、高々$1 - \epsilon$の確率でしか正解できない+独立性があるということから、$\exp(-\epsilon n)$で抑えられた。

だがこうとは限らないとき、その条件はないので、$|L(h) - \hat{L}(h^*)| > \epsilon$のような分布のすそについてHoeffdingの不等式で評価するしかない。その結果、必要データが増えて$\exp(- n \epsilon^2)$となってしまう。

前提条件として、Realizabilityの$\exist h^*, L(h^*) = 0$を外したが、今度は$\mathcal{H}$が有限集合であるという仮説も外したい。

仮説集合が無限集合となるとき、Union Boundを使うことができなくなる。これの代わりに、McDiarmidの不等式やRademacher複雑度を使っていく。

非常に基礎的なモデルから解析していく。

• $\mathcal{X} \subset \mathbb{R}^d$が学習データ
• $\mathcal{Y} = \{+1, -1\}$がラベルである二値分類。
• 損失関数はすべて01損失。つまり、損失関数というのは条件を満たさない確率そのものである。
  • 後程定義されるMcDirmidの不等式により、$[0,1]$でなくても、区間$[a,b]$でも問題はない。

追加の仮定は一切なし。

関数$f$の引数が1つだけ違うものの値の変化の絶対値を抑えられる場合に成り立つ不等式。関数を「平均値を出力する関数」とみなせば、Hoeffdingの不等式そのものである。

ここで、関数$f$の取りうる値が$[a, b]$とすれば、$\forall i, c_i = b-a$であるといえる。この時、

なお、前と同様に両側で定義すると以下のようになる。

ここで、片側でもMcDiarmidの不等式は実用的である。なぜなら、$f > \mathbb{E}[f] + \epsilon$の確率を評価できるから。

$n$個の観測データに依存した確率変数$\hat{G}_n = \sup_{h \in \mathcal{H}} L(h) - \hat{L}_n(h)$を定義する。これは理想損失の最適解$h$を与えた時の損失と経験損失に$h$を与えた時の損失の差である。評価するのはこの$\hat{G}_n = \sup_{h \in \mathcal{H}} L(h) - \hat{L}_n(h)$であり、今までは$L_n, L$で$L$についてのみ計算していた。

片側のMcDirmidの不等式で$\hat{G}_n$を評価すると、以下のようになる。

ここで、√の中の$n$が分母ではなく分子に来ているが、これは$L$自体の取る範囲が$[a,b]$であるので、McDiarmidの不等式として毎イテレーション評価するのは、平均をとるための係数$1/n$で割られたものであるということ。故に、毎イテレーションの間隔は$b-a$ではなく、$(b-a)/n$である。

そして、$\mathbb{E}[\hat{G}_n]$を評価するのが、Rademacher複雑度である。

Rademacher複雑度は以下のように定義される。

ここで、$\sigma_i$は独立に生成した確率変数であるので、ランダムなノイズと言える。そんなノイズを正解ラベルとしてそこに適合させることは、モデルの表現力が十分に高ければ可能である。

これを踏まえて、ランダムなノイズに対して学習器がうまく適合させられるので、最悪の確率変数のセットを引いたときの、上式の下限は大きくなる。簡単に言うと表現力が高ければ完全にノイズですら学習でき、その結果Rademacher Complexityで大きな値を取る。

示したいものは、以下のものである。$R_n(\mathcal{L})$がRademacher Complexity。

少なくとも$1-\delta / 2$の確率で以下が成り立つ。

これが成り立てば、$\hat{L}_n(h) - L(h)$の評価は

という式で抑えることができることから、

少なくとも$1 - \delta$の確率で以下の式が成り立つ。

まず、$\hat{G}_n = \sup _{h \in \mathcal{H}} \hat{L}_n(h) - L(h)$である。

そして、相補的なものとして、$\hat{G}_n^- = \sup _{h \in \mathcal{H}} L(h) - \hat{L}_n(h)$を考える。

以上の式が成り立つならば、以下のように合算できる。このように絶対値ついてるものは丁寧に符号を逆転させて外すとやりやすい。

ということで、$\hat{G}_n, \hat{G}^-_n$についてそれぞれ評価していきたい。

McDirmidの不等式を使いたい。$\hat{G}_n = \sup _{h \in \mathcal{H}} \hat{L}_n(h) - L(h)$について、データ$Z_1, \cdots, Z_n$の関数として、1つだけ$Z_i \to Z_i ^ \prime$にしたとき、$\hat{G}_n^\prime$になったとする。

これの差の上界は$L=1/n \sum l(Z_i, h)$となるので、$l(Z_i, h) - l(Z_i^\prime, h)$はたかだか$[a, b]$であることから、差の上界は$(b-a)/n$となる。

これと、$\delta / 2$(2つを合わせるから導入した)というのを使ってMcDirmidの不等式を適用する。すると、$1 - \delta /2$以上の確率で、一番下の式が成り立つ。

次に、$\mathbb{E}[\hat{G}_n]$をRademacher複雑度で評価する。

すでにあるデータ$Z_1, \cdots, Z_n$を使って、$\hat{L}_n(h) = 1/n \sum_{i=1}^n l(Z_i, h)$を定義した。

ここで別の独立なデータ$Z_1^\prime, \cdots, Z_n^\prime$を用いて、同様に計算した$\hat{L}_n ^ \prime(h)$も定義できる。

期待値自体は両方同じである。なので、$\hat{G}_n$を展開した中身に$Z \to Z^\prime$にした。そして、赤い線の部分で平均した後でsup ≤ supしたものの平均が使われている。

そして、交換した中で、さらに展開して$\sup_{h \in \mathcal{H}} \frac{1}{n} \sum_{i=1}^n l(Z_i ^ \prime, h) - l(Z_i, h)$を得る。期待値の計算に対称性があるので、符号はランダムに決まる→Rademacher変数を導入して書けるぞ！！！

このようにRademacher変数を導入したので、次のように解析を進められる。

Rademacher変数の部分をそれぞれに分割すると、まったく同じ分布が2つ得られることから、最終的に足すことで上界として$2 R_n(\mathcal{L})$が得られる。

よって、ここまでの議論をまとめると、

• 最適な$L(h)=0$となる$h$がなく
• 仮説空間$\mathcal{H}$が無限集合である

条件下でも、McDirmidの不等式で$\hat{G}_n = \sup _{h \in \mathcal{H}} \hat{L}_n(h) - L(h)$について評価し、Rademacher複雑度による$\mathbb{E}[\hat{G}_n]$の評価で抑えるということができる。

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

• 一番厳しかったのが、$L(h)=0$が存在し、仮説空間も有限集合である。この時は以下のようになり、一番厳しい評価である。

• 次は、$L(h)=0$が存在しないが、仮説空間が有限集合であるという前提条件。

• 最後はいずれの前提条件も成り立たない場合。

どんどん上界としては緩くなっているのが$\log$ で見て取れる。