# 第7章 SVM発表メモ(繁延)
### **非線形な決定境界を持つデータの線形分類問題への変換**
### **7.1.2 ロジスティック回帰との関係メモ**
## **7.1.3 多クラスSVM**
[One-versus-the-rest](https://www.info.kindai.ac.jp/~shirahama/courses/ml/2018/slides/slides_7.pdf)
[DAG SVM](https://www.researchgate.net/figure/A-DAG-SVM-for-an-L-4-class-classification-problem-In-the-graph-each-node_fig2_240481758)
[誤り訂正出力符号](http://ibisforest.org/index.php?%E8%AA%A4%E3%82%8A%E8%A8%82%E6%AD%A3%E5%87%BA%E5%8A%9B%E7%AC%A6%E5%8F%B7)
[One class SVM](https://recruit.cct-inc.co.jp/tecblog/machine-learning/one-class-svm/)
## **7.1.4 回帰のためのSVM**
### **2次計画法の双対表現**
制約付き2次計画問題は一般的に以下で表現できる。
$$
\begin{aligned}
&\min _{\theta} L(\theta) \\
&\text { subject to } c_{1}(\theta) \leqq 0 \ldots c_{n}(\theta) \leqq 0
\end{aligned}
$$
各制約条件に非負の双対変数$\lambda_{k}$を掛け合わせたものを目的関数に足し合わせたものは
**ラグランジュ関数**と呼ばれる。
$$\tilde{L}(\theta, \lambda)=L(\theta)+\sum_{k=1}^{n} \lambda_{k} C_{k}(\theta), \quad \lambda_{k} \geq 0$$
ラグランジュ関数を双対変数に対して最大化した関数を$\mathcal{P}(\theta)$と定義する。
$$
\mathcal{P}(\theta)=\max _{\lambda_{k} \geq 0} \tilde{L}(\theta, \lambda_{k})
$$
この関数$\mathcal{P}(\theta)$を主変数$\theta$について最小化する以下の最適化問題を考える。
$$
\min _{\theta}\mathcal{P}(\theta)=\min _{\theta} \max _{\lambda_{k} \geq 0} \tilde{L}(\theta, \lambda_{k})
$$
この問題(主問題)は実は**元の最適化問題と等価**である。
今度は、ラグランジュ関数を主変数について最小化した関数を定義する。
$$
\mathcal{D}(\lambda_{k})=\min _{\theta} \tilde{L}(\theta, \lambda_{k})
$$
$\mathcal{D}(\lambda_{k})$を双対変数$\lambda_{k}$について最大値する以下の問題を双対問題と呼ぶことにする。
$$
\max _{\lambda_{k} \geq 0} \mathcal{D}(\lambda_{k})=\max _{\lambda_{k} \geq 0} \min _{\theta} \tilde{L}(\theta, \lambda_{k})
$$
この問題は主問題の***minとmaxを入れ替えた形***になっている。
次に主問題と双対問題の関係性について考える。
主問題の最適値を$\theta^{*}$,双対問題の最適値を$\lambda_{k}^{*}$とすると以下の関係が成立する。
$$
\begin{aligned}
D\left(\lambda_{k}^{*}\right) &=\min _{\theta} \tilde{L}\left(\theta, \lambda_{k}^{*}\right) \\
& \leqslant \tilde{L}\left(\theta^{*}, \lambda_{k}^{*}\right) \\
& \leqslant \max _{\lambda_{k} \geq 0} \tilde{L}\left(\theta^{*}, \lambda_{k}\right)=P\left(\theta^{*}\right)
\end{aligned}
$$
ここから双対問題の最適値が主問題の最適値以下だという関係が分かります。
これは***弱双対性***と呼ばれる性質で、どのような最適化問題でも成立します。
$$
D\left(\lambda_{k}^{*}\right) \leqslant P\left(\theta^{*}\right)
$$
サポートベクトルマシンの場合、より強い以下の***強双対性***と呼ばれる性質が
成り立つことが知られています。※目的関数/制約式が凸関数の場合、概ね強双対性は成り立つ。
$$
D\left(\lambda_{k}^{*}\right) ＝ P\left(\theta^{*}\right)
$$
これは主問題と双対問題の目的関数値が最適解において一致するということです。
強双対性が成り立つラグランジュ関数は[鞍点](https://www.google.com/search?q=%E9%9E%8D%E7%82%B9&bih=890&biw=1920&hl=ja&sxsrf=ALeKk03F6cHMskUTDsh7tlHqA5o-wXiEuQ:1624957027256&tbm=isch&source=iu&ictx=1&fir=1iKdjQZpbqoibM%252CYgSHmlWhhFw1YM%252C_&vet=1&usg=AI4_-kSwQepeYym8Ix02kTdYBWtiX3nfNg&sa=X&ved=2ahUKEwiHtonTvLzxAhUkNKYKHYKxCtIQ_h16BAgNEAE#imgrc=1iKdjQZpbqoibM)の形をしている。
### **SVM回帰において相補性条件(KKT条件の一部)から決定関数に寄与するデータの条件が何かを考える。(P52-53)**
まず双対問題を解くと、決定関数は以下の式で示される。
$$
y(\mathbf{x})=\sum_{n=1}^{N}\left(a_{n}-\widehat{a}_{n}\right) k\left(\mathbf{x}, \mathbf{x}_{n}\right)+b
$$
この関数は、学習データの特徴ベクトル${\phi}(\mathbf{x}_{n})$と予測したいデータの特徴ベクトル${\phi}(\mathbf{x})$のカーネルと、双対問題の解である$a_{n},\hat{a}_{n}$との線形結合で表される。具体的にn=3の場合を書き下すと以下となる。
$$
y(x)=\left(a_{1}-\hat{a}_{1}\right) k\left(x, x_{1}\right)+\left(a_{2}-\hat{a}_{2}\right) k\left(x, x_{2}\right)+\left(a_{3}-\hat{a}_{3}\right) k\left(x, x_{3}\right)
$$
サポートベクトル分類の場合は、サポートベクトルは$a_{n}\neq 0$となり、それ以外は${a}_{n}=0$となるので、決定関数はサポートベクトルの情報のみで決まる。同様のことがサポートベクトル回帰でも言えるか確認する。
サポートベクトル回帰におけるラグランジュ最適化問題の相補性条件は以下の式で示される。
$$
\begin{aligned}
&a_{n}\left(\epsilon+\xi_{n}+y_{n}-t_{n}\right)=0\qquad(7.65) \\
&\hat{a}_{n}\left(\epsilon+\widehat{\xi}_{n}-y_{n}+t_{n}\right)=0\quad(7.66) \\
&\left(c-a_{n}\right) \xi_{n}=0\qquad(7.67) \\
&\left(c-\hat{a}_{n}\right) \widehat{\xi}_{n}=0\qquad(7.68)
\end{aligned}
$$
また、データ点の制約条件を以下に示す。
$$
\begin{aligned}
&t_{n} \leqslant y_{n}+\epsilon+\xi_{n}\qquad(7.53) \\
&t_{n} \geqslant y_{n}-\epsilon-\widehat{\xi}_{n}\qquad(7.54)
\end{aligned}
$$
ここで、$a_{n} \geqslant 0$ , $\hat{a}_{n} \geqslant 0$ , $\xi_{n} \geqslant 0$ , $\widehat{\xi}_{n} \geqslant 0$ , $\epsilon > 0$ , $c > 0$ となる。
(スラック変数、双対変数、$\epsilon$許容誤差関数の定義)
(7.65) , (7.66)より以下の条件に分けられる
(1) $a_{n} \neq 0, \quad \hat{a}_{n}=0$
(2) $a_{n}=0, \quad \hat{a}_{n}\neq 0$
(3) $a_{n} = 0, \quad \hat{a}_{n}=0$
※$a_{n} \neq 0, \quad \hat{a}_{n}\neq0$は同時に成り立たない。
(1) $a_{n} \neq 0, \quad \hat{a}_{n}=0$
$a_{n}\neq 0$
$\Leftrightarrow\epsilon+\xi_{n}+y_{n}-t_{n}=0$ (7.65より)
$\Leftrightarrow y_{n}-t_{n}+\epsilon=-\xi_{n} \leqslant 0$ ($\xi_{n} \geqslant 0$より)
$\Leftrightarrow t_{n} \geqslant y_{n}+\varepsilon$
$\hat{a}_{n}=0$
$\Leftrightarrow c \widehat{\xi}_{n}=0\quad$ (7.68より)
$\Leftrightarrow \widehat{\xi}_{n}=0\quad ($c > 0より$)$
$\Leftrightarrow t_{n} \geqslant y_{n}-\epsilon\quad$(7.54より)
(2) $a_{n}=0, \quad \hat{a}_{n}\neq 0$
$a_{n}=0$
$\Leftrightarrow c \xi_{n}=0\quad$ (7.67より)
$\Leftrightarrow \xi_{n}=0\quad ($c > 0より$)$
$\Leftrightarrow t_{n} \leqslant y_{n}+\epsilon\quad$(7.53より)
$\hat{a}_{n}\neq 0$
$\Leftrightarrow\epsilon+\widehat{\xi}_{n}-y_{n}+t_{n}=0$ (7.66より)
$\Leftrightarrow -y_{n}+t_{n}+\epsilon=-\widehat{\xi}_{n} \leqslant 0$ ($\widehat{\xi}_{n} \geqslant 0$より)
$\Leftrightarrow t_{n} \leqslant y_{n}-\epsilon$
(3)$a_{n} = 0, \quad \hat{a}_{n}=0$
$a_{n}=0$
$\Leftrightarrow c \xi_{n}=0\quad$ (7.67より)
$\Leftrightarrow \xi_{n}=0\quad ($c > 0より$)$
$\Leftrightarrow t_{n} \leqslant y_{n}+\epsilon\quad$(7.53より)
$\hat{a}_{n}=0$
$\Leftrightarrow c \widehat{\xi}_{n}=0\quad$ (7.68より)
$\Leftrightarrow \widehat{\xi}_{n}=0\quad ($c > 0より$)$
$\Leftrightarrow t_{n} \geqslant y_{n}-\epsilon\quad$(7.54より)
以上をまとめると
(1) $a_{n} \neq 0, \quad \hat{a}_{n}=0\quad$ $\Leftrightarrow\quad t_{n} \geqslant y_{n}+\varepsilon$
：データ点が$\varepsilon$チューブの上側の境界もしくは、$\varepsilon$チューブの上側に存在する。
(2) $a_{n}=0, \quad \hat{a}_{n}\neq 0\quad$ $\Leftrightarrow\quad t_{n} \leqslant y_{n}-\varepsilon$
：データ点が$\varepsilon$チューブの下側の境界もしくは、$\varepsilon$チューブの下側に存在する。
(3) $a_{n} = 0, \quad \hat{a}_{n}=0\quad$ $\Leftrightarrow\quad\ y_{n}-\varepsilon \leqslant t_{n} \leqslant y_{n}+\varepsilon$
：データ点が$\varepsilon$チューブの内側に存在する。
決定関数は(1),(2)のデータ情報のみで決まる。よって、サポートベクトルは$\varepsilon$チューブの境界面もしくは、その外側に位置するデータになる。(サポートベクトル分類とは少し異なる)
(3)より$\varepsilon$チューブの内側に存在するデータは決定関数の決定に寄与しない。
## **7.1.5 計算論的学習理論**
[計算論的学習理論](https://www.slideshare.net/sleepy_yoshi/prm11-715)
詳細は理解できなかったが、、ざっくりいうと以下の感じ。
PAC学習– 仮説集合𝐻(学習モデル)の学習問題において，危険率𝛿で汎化誤差𝜖の予測器を学習するために必要な訓練データ数の下界を求める枠組み
VC次元– モデルの複雑さの指標。そのモデルが任意の2クラス分類できるデータの数。VC次元を使えば無限次元のモデルに対してもPAC学習が使える。
ただ、データ数の下界は実運用上は大きすぎるとのこと(上記リンク先参照)
Sign in with Wallet
Connect another wallet