notebooks/MATH_Generalization_margin_loss_and_SVM.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# マージン損失\n",
    "\n",
    "参考：\n",
    "* [統計的学習理論 (機械学習プロフェッショナルシリーズ)](https://amzn.asia/d/5OudVVi)\n",
    "\n",
    "準備：\n",
    "* 入力空間 $\\mathcal{X}$\n",
    "* 出力空間 $\\mathcal{Y}= \\{-1, 1\\}$\n",
    "* 判別関数の集合 $\\mathcal{G}\\subset \\{g : \\mathcal{X} \\to \\mathbb{R}\\}$\n",
    "\n",
    "ここで，判別関数はデータ$x$を受け取って何かしらの実数$g(x)$を返します．\n",
    "この帰ってきた実数とそのラベル$y$の積$yg(x)$のことを**マージン**といいます．\n",
    "\n",
    "二値分類の場合は，マージンが正なら$g(x)$（の符号）は正しいラベル予測ができており，マージンが負ならラベルの予測が間違っています．\n",
    "マージンが０の場合はラベル予測が成立しません（サンプルが識別平面のちょうど上にあることになります）．\n",
    "このような場合は避けたいので，識別平面の上にある場合は予測が間違っていることにするのが一般的です（多分）．\n",
    "\n",
    "一般にマージンから計算される損失のことをマージン損失と呼び，次で定義されます：\n",
    "\n",
    "---\n",
    "\n",
    "**マージン損失**\n",
    "\n",
    "非負関数$\\phi : \\mathbb{R}\\to \\mathbb{R}_{\\geq 0}$と二値データ$(x, y) \\in \\mathcal{X} \\times \\{-1, 1\\}$に対して，判別関数$g: \\mathcal{X} \\to \\mathbb{R}$のマージン損失を$\\phi(y g(x))$と定義します．\n",
    "\n",
    "例えば\n",
    "$$\\phi_{\\mathrm{err}}(m)=\\mathbb{I}\\{m \\leq 0\\}$$\n",
    "は0-1マージン損失と呼ばれます．0-1損失とほぼ同じですが，ちゃんとマージンが０の部分で間違いを出しています．実際，\n",
    "\n",
    "* $g(x)\\neq 0$のとき：$\\ell_{err}(\\operatorname{sign}(g(x)), y)=\\phi_{\\mathrm{err}}(y g(x))$\n",
    "* $g(x)= 0$のとき：$\\ell_{err}(\\operatorname{sign}(g(x)), y)\\leq \\phi_{\\mathrm{err}}(y g(x)) = 1$\n",
    "\n",
    "であり，よって，任意の$m$に対して0-1損失より0-1マージン損失のほうが大きいです．\n",
    "\n",
    "---\n",
    "\n",
    "[MATH_finite_hypothesis_bound.ipynb](MATH_finite_hypothesis_bound.ipynb)でやった経験判別誤差（$\\hat{R}_{err}$）と期待判別誤差（$R_{err}$）と同様に，マージン損失も経験損失（$\\hat{R}_\\phi$）と期待損失（$R_\\phi$）が定義できます（Notationは本参照．）\n",
    "特に上で見たように，$\\phi_{err}(m) \\leq \\phi(m)$が常に成り立つようなマージン関数を使えば，マージン損失が小さくなれば判別誤差も小さくなること期待されます．\n",
    "\n",
    "特にサポートベクトルマシンはヒンジ損失$\\phi(m)=\\max\\{1-m, 0\\}$を使います．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## TODO: 判別適合的損失\n",
    "\n",
    "判別関数$g$に対して，マージン損失と判別誤差の関係について見てみましょう．\n",
    "期待マージン損失は\n",
    "\n",
    "$$\n",
    "R_\\phi(g) = \\mathbb{E}_X[\\mathbb{E}_Y[(\\phi(Y g(X))) \\mid X]]\n",
    "$$\n",
    "で表現されます．$Y$は二値であることを使って，\n",
    "$$\n",
    "C_\\eta(\\alpha) = \\eta \\phi(\\alpha) + (1-\\eta)\\phi(-\\alpha)\n",
    "$$\n",
    "を定義すると，$\\eta = \\operatorname{Pr}(Y=+1 \\mid X)$とすれば\n",
    "$$\n",
    "R_\\phi(g) = \\mathbb{E}_X[C_\\eta(g(X))]\n",
    "$$\n",
    "と書けます．\n",
    "\n",
    "ここで，ベイズ規則は\n",
    "* $\\operatorname{Pr}(Y=+1 \\mid X) > 1/2$のときに+1\n",
    "* $\\operatorname{Pr}(Y=+1 \\mid X) < 1/2$のときに-1\n",
    "\n",
    "を返す仮説と等価です．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## サポートベクトルマシン (SVM)\n",
    "\n",
    "サポートベクトルマシンは次の最適化問題として定式化されます：\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\min _w\\|w\\|_2^2 \\\\\n",
    "& \\text { subject to } 0 \\geq 1-\\underbrace{y_i\\overbrace{\\left\\langle w, x_i\\right\\rangle}^{判別関数 g(x_i)}}_{マージン}\n",
    "\\end{aligned}\n",
    "$$\n",
    "この定式化は問題が線形分離可能であることを仮定しています（一般の場合は後で見ます）．また簡単のためにバイアス項は無視してます．\n",
    "\n",
    "ヒンジ損失が$\\phi(m) = \\max\\{1-m, 0\\}$であることを思い出すと，SVMの制約の部分は「ヒンジ損失を常に$0$にする判別関数だけを許容」しています．その判別関数の中でも，ノルム$\\|w\\|_2^2$を最小にするものを探しているわけですね．\n",
    "\n",
    "用語を整理しましょう．\n",
    "* 判別関数$g(x_i) = \\left\\langle w, x_i\\right\\rangle$は$\\left\\langle w, x_i\\right\\rangle=0$を考えれば，$\\mathcal{X}$上の平面を規定します．これを**識別平面**と呼びます．\n",
    "* 識別平面から最も近い訓練データのことを**サポートベクトル**と呼びます（複数存在します）．これを$x_*$とします．\n",
    "* 上で見たように，$y g(x)$のことをマージンと呼びますが，SVMでは識別平面からデータまでの距離$M_i$をマージンと呼びます．[点と直線の距離の公式](https://manabitimes.jp/math/859)を使えば，\n",
    "$$\n",
    "M_i=\\frac{\\left|\\left\\langle w, x_i\\right\\rangle\\right|}{\\|w\\|_2}\n",
    "$$\n",
    "で距離が与えられます．線形分離可能な場合は結局$y f(x) = y \\langle w, x_i\\rangle \\geq 0$になるので，通常のマージンは$M_i$の分子を与えます．よって，SVMのマージンは通常のマージンを正規化した特殊ケースです．\n",
    "\n",
    "SVMの制約は各データについて$0 \\geq 1-y_i\\left\\langle w, x_i\\right\\rangle$でした．\n",
    "$y_i\\in \\{-1, +1\\}$なので，$\\left|y_*\\left\\langle w, x_*\\right\\rangle\\right|=\\left|\\left\\langle w, x_*\\right\\rangle\\right|$であり，特に平面の式では$w$のスケールが関係ないので，$\\left|\\left\\langle w, x_*\\right\\rangle\\right|=1$であるような$w$が取れます．\n",
    "このとき，\n",
    "\n",
    "$$\n",
    "M_i=\\frac{\\left|\\left\\langle w, x_i\\right\\rangle\\right|}{\\|w\\|_2} \\geq \\frac{1}{\\|w\\|_2}(i=1,2, \\ldots, n)\n",
    "$$\n",
    "\n",
    "が成立します．\n",
    "SVMではこのマージン$M_*=\\frac{1}{\\|w\\|_2}$を最大にするよう最適化します．つまり，SVMはサポートベクトルに対してのマージンの最大化を通じて，全てのデータに対してのマージン最大化をしているわけですね．\n",
    "\n",
    "**線形分離可能ではない場合**\n",
    "\n",
    "一般に問題が線形分離可能とは限らないので，上の最適化問題には解が存在しない場合があります．\n",
    "\n",
    "そこで，次の\"ソフト\"なSVMを考えることがあります．$C > 0$は正則化係数です（TODO: ここの$C$ちょっと正しいか自信ないのでちゃんと下と等価になるか確かめよう．多分正確なバリア関数法とほぼ同じノリのはず）．\n",
    "$$\n",
    "\\hat{w}=\\underset{w}{\\operatorname{argmin}} \\underbrace{\\frac{1}{n} \\sum_{i=1}^n \\max \\left\\{0,1-y_i\\left\\langle w, x_i\\right\\rangle\\right\\}}_{=\\widehat{L}_n^{\\text {hinge }}(w)}+\\frac{1}{C}\\|w\\|_2^2 .\n",
    "$$\n",
    "\n",
    "これはスラック変数$\\xi_{1:n}$を使うと\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\min _{w, \\xi_{1: n}}\\|w\\|_2^2+C \\sum_{i=1}^n \\xi_i \\\\\n",
    "& \\text { subject to } \\xi_i \\geq 1-y_i\\left\\langle w, x_i\\right\\rangle, \\xi_i \\geq 0(i=1, \\ldots, n)\n",
    "\\end{aligned}\n",
    "$$\n",
    "と同じです．\n",
    "これは$C$を$\\to \\infty$とすれば，結局$\\xi_i=0$を考えないといけないので，上の線形分離可能の場合と同じです．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## SVMの汎化誤差解析\n",
    "\n",
    "### 解析の前の準備\n",
    "\n",
    "次のソフトなSVMを考えます．\n",
    "$$\n",
    "\\hat{w}=\\underset{w}{\\operatorname{argmin}} \\underbrace{\\frac{1}{n} \\sum_{i=1}^n \\max \\left\\{0,1-y_i\\left\\langle w, x_i\\right\\rangle\\right\\}}_{=\\widehat{L}_n^{\\text {hinge }}(w)}+\\frac{1}{C}\\|w\\|_2^2 .\n",
    "$$\n",
    "\n",
    "SVMの解析を始める前に，これを先に解釈してみましょう．\n",
    "そのために次の制約付き最適化問題について考えます：\n",
    "\n",
    "$$\n",
    "\\min _w L(w) \\quad \\text { subject to } \\quad\\|w\\|_2 \\leq B_2\n",
    "$$\n",
    "\n",
    "これは\n",
    "$$\n",
    "\\min _w L(w) \\quad \\text { subject to } \\quad\\|w\\|^2_2 \\leq B^2_2\n",
    "$$\n",
    "と同じです．このラグランジュ関数\n",
    "\n",
    "$$\n",
    "\\mathcal{L}(w, \\lambda)=L(w)+\\lambda\\left(\\|w\\|^2-B^2\\right)\n",
    "$$\n",
    "\n",
    "について考えてみましょう．\n",
    "KKT条件から，上の制約付き最適化問題の最適解$\\hat{w}$は相補性条件\n",
    "$$\n",
    "\\lambda\\left(\\|w\\|^2-B_2^2\\right)=0\n",
    "$$\n",
    "を満たします．\n",
    "\n",
    "---\n",
    "\n",
    "まず，$B_2$が先に決まってる場合を考えてみましょう．\n",
    "相補性条件から，$\\|\\hat{w}\\|^2=B_2^2$もしくは$\\lambda=0$です．\n",
    "例えば$B_2$がめっちゃ大きい場合は制約を無視できるので，$\\lambda=0$ですね．すなわち，$B_2$の値を決めると$\\lambda$の値が決まります．\n",
    "\n",
    "---\n",
    "\n",
    "逆に$\\lambda > 0$の値を決めてみましょう．その際に停留点の条件$\\nabla_w \\mathcal{L}(w, \\lambda)=0$を満たすような$\\hat{w}$を探したとします．これは正則化付き最適化問題です．\n",
    "\n",
    "このとき，$\\hat{B}^2_2 = \\|\\hat{w}\\|^2_2$なる$\\hat{B}_2$を定義すれば，この$\\hat{w}$は，この$B_2 = \\hat{B}_2$のもとでの制約付き最適化問題\n",
    "\n",
    "$$\n",
    "\\min _w L(w) \\quad \\text { subject to } \\quad\\|w\\|_2 \\leq \\hat{B}_2\n",
    "$$\n",
    "\n",
    "を解いていることになります．\n",
    "よって，SVMの最適化問題：\n",
    "$$\n",
    "\\hat{w}=\\underset{w}{\\operatorname{argmin}} \\underbrace{\\frac{1}{n} \\sum_{i=1}^n \\max \\left\\{0,1-y_i\\left\\langle w, x_i\\right\\rangle\\right\\}}_{=\\widehat{L}_n^{\\text {hinge }}(w)}+\\frac{1}{C}\\|w\\|_2^2 .\n",
    "$$\n",
    "は正則化付き最適化問題ですが，これは$\\|w\\|_2$についての制約がついた制約付き最適化問題として捉えることができます．\n",
    "そこで，L2ノルムが制限された仮説空間とヒンジ損失による学習問題を考え，その汎化誤差解析をすれば，SVMの汎化誤差解析ができるはずです．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### L2ボールにおける汎化誤差解析\n",
    "\n",
    "まず[MATH_L2_L1_regularization](MATH_L2_L1_regularization.ipynb)でやったL2ボール上の結果をつかった汎化誤差解析について見ていきましょう．まず，[MATH_infinite_hypothesis_Rademacher.ipynb](MATH_infinite_hypothesis_Rademacher.ipynb)\n",
    "でやったように，\n",
    "$$\n",
    "\\begin{aligned}\n",
    "R(\\hat{h}) & =\\widehat{R}(\\hat{h})+R(\\hat{h})-\\widehat{R}(\\hat{h}) \\\\\n",
    "& \\leq \\widehat{R}(\\hat{h})+\\sup _{h \\in \\mathcal{H}}\\left\\{R(h)-\\widehat{R}(h)\\right\\} \\\\\n",
    "& \\leq \\widehat{R}(\\hat{h})+2 \\mathcal{R}(\\mathcal{L})+(b-a) \\sqrt{\\frac{\\log \\frac{1}{\\delta}}{2 n}}\n",
    "\\end{aligned}\n",
    "$$\n",
    "が成り立ちます（$b-a$は損失の上界です．）．これと，ヒンジ損失が0-1損失より大きく，また，Talagrandの補題とヒンジ損失が1-リプシッツであることを使えば，\n",
    "$$\n",
    "\\begin{aligned}\n",
    "R^{0-1}(h) & \\leq R^{\\text {hinge }}(h) \\\\\n",
    "& \\leq \\widehat{R}_n^{\\text {hinge }}(h)+2 \\mathcal{R}_n\\left(\\mathcal{L}^{\\text {hinge }}\\right)+(b-a) \\sqrt{\\frac{\\log \\frac{2}{\\delta}}{2 n}} \\\\\n",
    "& \\leq \\widehat{R}_n^{\\text {hinge }}(h)+2 \\mathcal{R}_n(\\mathcal{H})+(b-a) \\sqrt{\\frac{\\log \\frac{2}{\\delta}}{2 n}}\n",
    "\\end{aligned}\n",
    "$$\n",
    "が言えます．\n",
    "\n",
    "ここで，$\\mathbb{E}_{(x, y) \\sim \\mathcal{D}}\\left[\\|y x\\|_2^2\\right]=C_2^2$を仮定しましょう．また，$h_w(x)=\\langle w, x\\rangle$とします．このとき，[MATH_L2_L1_regularization.ipynb](MATH_L2_L1_regularization.ipynb)でやったように，仮説空間\n",
    "$$\n",
    "\\mathcal{H}_2=\\left\\{h_w:\\|w\\|_2 \\leq B_2\\right\\}=\\left\\{x \\mapsto\\langle w, x\\rangle:\\|w\\|_2 \\leq B_2\\right\\}\n",
    "$$\n",
    "のラデマッハ複雑度は\n",
    "$$\n",
    "R_n\\left(\\mathcal{H}_2\\right) \\leq \\frac{B_2 C_2}{\\sqrt{n}}\n",
    "$$\n",
    "で抑えられます．さらにデータに対する仮定を置いて，\n",
    "$$\n",
    "\\max \\{0,1-y\\langle w, x\\rangle\\} \\leq 1+\\|w\\|_2\\|x\\|_2 \\leq 1+B_2 U_2\n",
    "$$\n",
    "であるとすれば，少なくとも$1-\\delta$の確率で，\n",
    "\n",
    "$$\n",
    "R(h_w) \\leq \\hat{R}_n^{\\mathrm{hinge}}(h_w)\n",
    "+2 \\frac{B_2 C_2}{\\sqrt{n}}+\\left(1+B_2 U_2\\right) \\sqrt{\\frac{\\log \\frac{1}{\\delta}}{2 n}}\n",
    "$$\n",
    "が言えます．\n",
    "\n",
    "これでも一応出せましたが，$w$のノルム$B_2$と$\\|x\\|_2^2 \\leq U_2$が残っています．\n",
    "SVMは上で述べたように制約を正則化によって実現しています．また，入力空間に対するバウンドも要求しません．これから$B_2$と$U_2$を外していきます．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### $B_2$を消す\n",
    "\n",
    "無限場合を考えるときによくやるテクニックですが，次の仮説空間を考えましょう：\n",
    "\n",
    "$$\n",
    "\\mathcal{H}_i=\\left\\{x \\mapsto\\langle w, x\\rangle:\\|w\\|_2 \\leq 2^i\\right\\}\n",
    "$$\n",
    "つまり，$i$が大きくなるにつれて膨らんでいく空間です．\n",
    "\n",
    "このときヒンジ損失は1-リプシッツで\n",
    "\n",
    "$$\n",
    "\\max \\{0,1-y\\langle w, x\\rangle\\} \\leq 1+\\|w\\|_2\\|x\\|_2 \\leq 1+2^i U_2\n",
    "$$\n",
    "\n",
    "が成り立ちます．よって，上でやった議論から，$\\forall h_w \\in \\mathcal{H}_i$について\n",
    "$$\n",
    "L\\left(h_w\\right) \\leq \\hat{L}_n^{\\text {hinge }}\\left(h_w\\right)+2 \\frac{2^i C_2}{\\sqrt{n}}+\\left(1+2^i U_2\\right) \\sqrt{\\frac{\\log \\frac{1}{\\delta_i}}{2 n}} .\n",
    "$$\n",
    "です．\n",
    "\n",
    "ここで次の簡単な事実を使います．\n",
    "\n",
    "---\n",
    "\n",
    "$\\sum_{i=1}^{\\infty} \\delta_i=\\delta$かつ$\\mathbb{P}\\left[\\left\\{Z>\\epsilon_i\\right\\}\\right] \\leq \\delta_i$のとき，Union boundから\n",
    "\n",
    "$$\\mathbb{P}\\left[\\bigcup_{i \\in \\mathbb{N}}\\left\\{Z>\\epsilon_i\\right\\}\\right] \\leq \\delta$$\n",
    "\n",
    "です．ド・モルガンの法則から\n",
    "$$\n",
    "\\mathbb{P}\\left[\\bigcap_{i \\in \\mathbb{N}}\\left\\{Z \\leq \\epsilon_i\\right\\}\\right]>1-\\delta\n",
    "$$\n",
    "です．よって，任意の$i \\in \\mathbb{N}$に対して$Z \\leq \\epsilon_i$が$1-\\delta$の確率で成立します．\n",
    "\n",
    "---\n",
    "\n",
    "等比数列の和の公式から\n",
    "$$\n",
    "\\sum_{i=1}^{\\infty} \\delta_i=\\sum_{i=1}^{\\infty} \\frac{\\delta}{2^i}=\\delta\n",
    "$$\n",
    "です．また，$\\|w\\|_2>1$なる任意の$w$について，\n",
    "\n",
    "$$\n",
    "i-1 \\leq \\log _2\\|w\\|_2 \\leq i\n",
    "$$\n",
    "\n",
    "を満たすような$i\\in \\mathbb{N}$が存在します．\n",
    "\n",
    "以上を使うと，少なくとも$1-\\delta$の確率で，任意の$i \\in \\mathbb{N}$における$\\forall h'_w \\in \\mathcal{H}_i$について，\n",
    "\n",
    "$$\n",
    "L\\left(h_w^{\\prime}\\right) \\leq \\hat{L}_n^{\\text {hinge }}\\left(h_w^{\\prime}\\right)+2 \\frac{2^i C_2}{\\sqrt{n}}+\\left(1+2^i U_2\\right) \\sqrt{\\frac{\\log \\frac{2^i}{\\delta}}{2 n}}\n",
    "$$\n",
    "\n",
    "が成り立ちます．さらに，任意の$w$に対して$2^{i-1} \\leq\\|w\\|_2 \\leq 2^i$であるような$i$が存在することを思い出しましょう．\n",
    "つまり，**上では$i$を先に考えて$w$を決めてましたが，ここでは$w$を先に決めて$i$を持ってきます**．\n",
    "\n",
    "適当な$w$を決めると，$2^{i-1} \\leq\\|w\\|_2 \\leq 2^i$を満たすような$i$が存在し，さらに上の議論から\n",
    "\n",
    "$$\n",
    "L\\left(h_w\\right) \\leq \\hat{L}_n^{\\text {hinge }}\\left(h_w\\right)+2 \\frac{2^i C_2}{\\sqrt{n}}+\\left(1+2^i U_2\\right) \\sqrt{\\frac{\\log \\frac{2^i}{\\delta}}{2 n}}\n",
    "$$\n",
    "\n",
    "です．これはさらに$2^{i-1} \\leq\\|w\\|_2 \\leq 2^i$を使って\n",
    "\n",
    "$$\n",
    "L\\left(h_w\\right) \\leq \\hat{L}_n^{\\text {hinge }}\\left(h_w\\right)+2 \\frac{2\\|w\\|_2 C_2}{\\sqrt{n}}+\\left(1+2\\|w\\|_2 U_2\\right) \\sqrt{\\frac{\\log \\frac{2\\|w\\|_2}{\\delta}}{2 n}}\n",
    "$$\n",
    "\n",
    "とできるわけですね．\n",
    "\n",
    "**補足**：これは多分[RL_uniform_PAC.ipynb](RL_uniform_PAC.ipynb)で出てきたようなPeeling techniqueと同じことをしてます．このように，パラメータの有界性を外したいときなどで活躍したりもします．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### $U_2$を消す\n",
    "\n",
    "上で残った$U_2$も実は外せます．\n",
    "次のランプ損失を考えましょう．\n",
    "\n",
    "$$\n",
    "\\phi^{\\mathrm{ramp}}(m)= \\begin{cases}0, & 1 \\leq m \\\\ 1-m, & 0 \\leq m \\leq 1 \\\\ 1, & m \\leq 0\\end{cases}\n",
    "$$\n",
    "\n",
    "このとき，\n",
    "$$\n",
    "\\mathbb{I}(m \\leq 0) \\leq \\phi^{\\mathrm{ramp}}(m) \\leq \\max \\{0,1-m\\}\n",
    "$$\n",
    "が成り立ちます（図示すればすぐわかりますが，0-1損失より大きく，ランプ損失よりも小さいです．）．\n",
    "また，すぐわかるように，ランプ損失は$1$-リプシッツ連続かつ$\\phi^{\\mathrm{ramp}}(m) \\leq 1$です．\n",
    "これを使うと，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "R^{0-1}(h) & \\leq R^{\\text {ramp }}(h) \\\\\n",
    "& \\leq \\widehat{R}_n^{\\text {ramp }}(h)+2 \\underbrace{\\mathcal{R}_n(\\mathcal{H})}_{1 \\text {-lipschitz }}+\\underbrace{(b-a)}_{=1} \\sqrt{\\frac{\\log \\frac{2}{\\delta}}{2 n}} \\\\\n",
    "& \\leq \\widehat{R}_n^{\\text {hinge }}(h)+2 \\mathcal{R}_n(\\mathcal{H})+\\sqrt{\\frac{\\log \\frac{2}{\\delta}}{2 n}}\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成り立ちます．ランプ損失を一回経由することで有界性を出しているわけですね．\n",
    "\n",
    "最終的に，\n",
    "\n",
    "$$\n",
    "R^{0-1}\\left(h_w\\right) \\leq \\hat{R}_n^{\\text {hinge }}\\left(h_w\\right)+4 \\frac{\\|w\\|_2 C_2}{\\sqrt{n}}+\\sqrt{\\frac{\\log \\frac{2\\|w\\|_2}{\\delta}}{2 n}}\n",
    "$$\n",
    "\n",
    "が出てきます．\n",
    "\n",
    "### もうちょっと良いバウンド\n",
    "\n",
    "実はこの$\\log \\frac{2\\|w\\|_2}{\\delta}$の部分は更に改善できます．\n",
    "これは\n",
    "$$\n",
    "L\\left(h_w\\right) \\leq \\hat{L}_n^{\\text {hinge }}\\left(h_w\\right)+2 \\frac{2^i C_2}{\\sqrt{n}}+\\left(1+2^i U_2\\right) \\sqrt{\\frac{\\log \\frac{2^i}{\\delta}}{2 n}}\n",
    "$$\n",
    "における$\\frac{2^i}{\\delta}$が原因だったことを思い出しましょう．\n",
    "\n",
    "\n",
    "証明はしませんが，\n",
    "$$\n",
    "\\sum_{i=1}^{\\infty} \\frac{1}{i^2}=\\frac{\\pi^2}{6}\n",
    "$$\n",
    "であることを使います．\n",
    "$\\delta_i=\\frac{\\delta}{2 i^2}$とすると，\n",
    "\n",
    "$$\n",
    "\\sum_{i=1}^{\\infty} \\delta_i=\\sum_{i=1}^{\\infty} \\frac{\\delta}{2 i^2}=\\frac{\\pi^2}{12} \\delta<\\delta\n",
    "$$\n",
    "\n",
    "が成り立つことはすぐにわかります．よって，上でやった$2^i \\leq 2\\|w\\|_2$より，$i \\leq \\log _2\\left(2\\|w\\|_2\\right)$なので，更に\n",
    "\n",
    "$$\n",
    "\\frac{2}{\\delta_i}=\\frac{(2 i)^2}{\\delta}<\\frac{\\left(2 \\log _2\\left(2\\|w\\|_2\\right)\\right)^2}{\\delta}\n",
    "$$\n",
    "\n",
    "が言えます．よって$\\frac{2^i}{\\delta}$は次のように上からバウンドできます：\n",
    "\n",
    "$$\n",
    "R^{0-1}\\left(h_w\\right) \\leq \\hat{R}_n^{\\text {hinge }}\\left(h_w\\right)+4 \\frac{\\|w\\|_2 C_2}{\\sqrt{n}}+\\sqrt{\\frac{\\log \\frac{2 \\log _2\\left(2\\|w\\|_2\\right)}{\\delta}}{n}}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}