# 統計的学習理論

### 前章までのキーワード
---

##### 予測損失
##### 経験損失
##### ベイズ誤差・ベイズ規則
#### 統計的一致性 (1.4, p14)
#### 普遍カーネル
#### 表現定理

---
## ５章 サポートベクトルマシン

---

### 5.1 導入

本章で扱うSVMは下記の通り。Cと$\nu$はそれぞれ正則化パラメータで、それぞれ適切に設定すると同じ判別器が得られる。
* C-SVM
* データ数に応じてCを調節すると統計的一致性が達成される
* $\nu$-SVM
* データの分布に応じて$\nu$を調節すると統計的一致性が達成される
* 理論的にも$\nu$の調節には交差検証法を必要とする

##### 【復習】統計的一致性 (1.4, p14)
ある学習アルゴリズムの予測損失がサンプルサイズを無限にする極限でベイズ誤差に確率収束する時、この学習アルゴリズムは統計的一致性を持つと言う。

\begin{eqnarray}
\lim_{n\rightarrow\infty}{\rm Pr}_{S\sim D^n}
\left(
R(h_S)\leq R^* +\epsilon
\right) = 1
\end{eqnarray}

##### 本章で扱う問題設定（２クラス分類問題）

###### 判別関数の集合：
\begin{eqnarray}
\mathcal{G} & = & \{f + b | f \in \mathcal{H}, b \in \mathbb{R} \}
\end{eqnarray}

###### 仮説集合：
\begin{eqnarray}
sign \circ \mathcal{G} & = & \{x \mapsto sign(g(x)) | g \in \mathcal{G} \}
\end{eqnarray}

###### マージン損失：
$(x, y)$のマージンは$yg(x)$といい、ある判別関数に対するマージンで決まる損失関数をマージン損失という

---

### 5.2 ヒンジ損失

ヒンジ損失
\begin{eqnarray}
\phi_{hinge}(m) & = & max\{1 - m, 0\}
\end{eqnarray}

##### 【復習】判別適合性損失 (3.2, p42)

##### 【復習】凸マージン損失の判別適合性定理 (3.3, p45)

---

### 【準備】5.3 通常のサポートベクトルマシンの議論（はじパタを参照）

#### 線形かつスラック変数無し

データ$(x_{i}, y_{i})$, $i = 1, \dots, N$が、下記が成り立つように線形分離可能だとする（$f(x) = \alpha^{T}x$の場合を考える）。

\begin{eqnarray}
y_i = 1 \qquad \rightarrow \qquad \alpha^{T}x_{i} + b & \ge & 1\\
y_i = -1 \qquad \rightarrow \qquad \alpha^{T}x_{i} + b & \le & -1
\end{eqnarray}

上記をまとめると下記となる。

\begin{eqnarray}
y_i (\alpha^{T}x_{i} + b) & \ge & 1
\end{eqnarray}

この時、クラス間マージン$r(\alpha, b)$を最大にするよう$\alpha$と$b$を求めたい。クラス間マージンは各データを$\alpha/|\alpha|$の方向に射影した長さの差の最小値である。

\begin{eqnarray}
r(\alpha, b) & = & min_{x_{i} \in C_{y_{i} = 1}} \frac{\alpha^{T}x_{i} + b}{|\alpha|} -
max_{x_{i} \in C_{y_{i} = -1}} \frac{\alpha^{T}x_{i} + b}{|\alpha|}\\
& = & \frac{1}{|\alpha|} - \frac{-1}{|\alpha|}\\
& = & \frac{2}{|\alpha|}
\end{eqnarray}

クラス間マージンを最大化するには$|\alpha|$を最小化すれば良い。よって、$L(\alpha)$の最適化問題は下記の通り。

\begin{eqnarray}
L(\alpha) & = & \frac{1}{2}\alpha^{T}\alpha\\
min_{\alpha} L(\alpha) \quad& subject\ to & \quad y_{i} (\alpha^{T}x_{i} + b) \ge 1
\end{eqnarray}

この不等式制約付き最適化の主問題は$L(\alpha, \gamma, b)$を「最小」にする$(\alpha, b, \gamma)$を求める。

\begin{eqnarray}
L(\alpha, \gamma, b) & = & \frac{1}{2}\alpha^{T}\alpha - \sum_{i = 1}^{N} \gamma_{i} \big( y_{i} (\alpha^{T}x_{i} + b) - 1\big)
\end{eqnarray}

ここで$\gamma_{i} > 0$はラグランジュの未定乗数である。
この最適化問題の解はKKT条件を満たす解として得られる。

\begin{eqnarray}
\nabla_{\alpha} L(\alpha, \gamma, b)\bigg|_{\alpha=\alpha_{0}} & = & \alpha_{0} - \sum_{i = 1}^{N} \gamma_{i} y_{i} x_{i} = 0\\
\nabla_{b} L(\alpha, \gamma, b)\bigg|_{b=b_{0}} & = & \sum_{i = 1}^{N} \gamma_{i} y_{i} = 0\\
y_{i} (\alpha^{T}x_{i} + b) - 1 & \ge & 0\\
\gamma_{i} & \ge & 0\\
\gamma_{i} \big( y_{i} (\alpha^{T}x_{i} + b) - 1\big) & = & 0 \qquad \cdots 相補性条件
\end{eqnarray}

各データについて、$y_i (\alpha^{T}x_{i} + b) - 1 \gt 0$のとき、相補性条件から$\gamma_{i}=0$となる。逆に、マージンを決めるベクトル（サポートベクトル）については$y_i (\alpha^{T}x_{i} + b) - 1 = 0$となり、$\gamma_{i} \ge 0$となる。

$\alpha$の最適解は次のように得られ、
\begin{eqnarray}
\alpha_{0} & = & \sum_{i = 1}^{N} \gamma_{i} y_{i} x_{i}
\end{eqnarray}

$L(\alpha, \gamma, b)$に代入すると$\gamma_{i}$のみの関数となる。
\begin{eqnarray}
L(\gamma) & = & \frac{1}{2}\alpha_{0}^{T}\alpha_{0} - \sum_{i = 1}^{N} \gamma_{i} y_{i} \alpha_{0}^{T}x_{i} - b\sum_{i = 1}^{N} \gamma_{i} y_{i} + \sum_{i = 1}^{N} \gamma_{i}\\
& = & -\frac{1}{2}\alpha_{0}^{T}\alpha_{0} +\sum_{i = 1}^{N} \gamma_{i}\\
& = & \sum_{i = 1}^{N} \gamma_{i} -\frac{1}{2}\sum_{i = 1}^{N}\sum_{j = 1}^{N}\gamma_{i}\gamma_{j} y_{i} y_{j} x_{i} x_{j}
\end{eqnarray}

最適な$\gamma$は$L(\gamma)$を「最大」にする$\gamma$により得られる。

\begin{eqnarray}
max_{\gamma} L(\gamma) \quad& subject\ to & \quad \sum_{i = 1}^{N} \gamma_{i} y_{i} = 0
\end{eqnarray}

#### 線形かつスラック変数有り

線形分離が不可能な場合、スラック変数を導入する。

\begin{eqnarray}
y_i (\alpha^{T}x_{i} + b) - 1 + \xi_{i} & \ge & 0\\
\end{eqnarray}

- $\xi_{i} = 0$ 正しく識別できる
- $0 < \xi_{i} \le 1$ マージン境界を越えるが正しく識別できる（識別境界を越えない）
- $\xi_{i} > 1$ 識別境界を越えて誤識別される

$L(\alpha, \xi)$の最適化問題は以下の通り。

\begin{eqnarray}
L(\alpha, \xi) & = & \frac{1}{2}\alpha^{T}\alpha + C\sum_{i=1}^{N}\xi_{i}\\
min_{\alpha, \xi} L(\alpha, \xi) \quad& subject\ to & \quad y_{i} (\alpha^{T}x_{i} + b) - 1 + \xi_{i} \ge 0, \quad \xi_{i} \ge 0
\end{eqnarray}

この不等式制約付き最適化の主問題は$L(\alpha, \gamma, b)$を「最小」にする$(\alpha, b, \xi, \gamma, \delta)$を求める。$\xi_{i}\ge 0$に対応するラグランジュ未定乗数を$\delta_{i}$とする。

\begin{eqnarray}
L(\alpha, b, \xi, \gamma, \delta) & = & C\sum_{i = 1}^{N}\xi_{i} + \frac{1}{2}\alpha^{T}\alpha - \sum_{i = 1}^{N}\delta_{i}\xi_{i} - \sum_{i = 1}^{N} \gamma_{i} \Big( y_{i} (\alpha^{T}x_{i} + b) - 1 + \xi_{i}\Big)
\end{eqnarray}

この最適化問題の解はKKT条件を満たす解として得られる。

\begin{eqnarray}
\nabla_{\alpha} L(\alpha, \gamma, b)\bigg|_{\alpha=\alpha_{0}} & = & \alpha_{0} - \sum_{i = 1}^{N} \gamma_{i} y_{i} x_{i} = 0\\
\nabla_{b} L(\alpha, \gamma, b)\bigg|_{b=b_{0}} & = & \sum_{i = 1}^{N} \gamma_{i} y_{i} = 0\\
\nabla_{\xi_{i}} L(\alpha, \gamma, b)\bigg|_{b=b_{0}} & = & C - \gamma_{i} - \delta_{i}= 0\\
y_{i} (\alpha^{T}x_{i} + b) - 1 + \xi_{i}& \ge & 0\\
\gamma_{i} \ge 0, \quad \xi_{i} \ge 0, \quad \delta_{i} & \ge & 0 \\
\gamma_{i} \Big( y_{i} (\alpha^{T}x_{i} + b) - 1 + \xi_{i}\Big) & = & 0 \qquad \cdots 相補性条件\\
\delta_{i}\xi_{i} & = & 0 \qquad \cdots 相補性条件
\end{eqnarray}

$\alpha$の最適解$\alpha_{0} = \sum_{i = 1}^{N} \gamma_{i} y_{i} x_{i}$を$L(\alpha, b, \xi, \gamma, \delta)$に代入すると$\gamma_{i}$のみの関数となる。

\begin{eqnarray}
L(\alpha_{0}, b, \xi, \gamma, \delta) & = & C\sum_{i = 1}^{N}\xi_{i} + \frac{1}{2}\alpha_{0}^{T}\alpha_{0} - \sum_{i = 1}^{N}\delta_{i}\xi_{i} - \sum_{i = 1}^{N} \gamma_{i} \Big( y_{i} (\alpha_{0}^{T}x_{i} + b) - 1 + \xi_{i}\Big)\\
& = & C\sum_{i = 1}^{N}\xi_{i} + \frac{1}{2}\alpha_{0}^{T}\alpha_{0} - \sum_{i = 1}^{N}\delta_{i}\xi_{i} - \sum_{i = 1}^{N} \gamma_{i} y_{i} \alpha_{0}^{T}x_{i}\\
&& - b\sum_{i = 1}^{N} \gamma_{i}y_{i} + \sum_{i = 1}^{N} \gamma_{i} - \sum_{i = 1}^{N}\gamma_{i}\xi_{i}\\
& = & \sum_{i = 1}^{N}(C - \delta_{i} -\gamma_{i})\xi_{i} - \frac{1}{2}\alpha_{0}^{T}\alpha_{0} - \sum_{i = 1}^{N}\delta_{i}\xi_{i} - b\sum_{i = 1}^{N} \gamma_{i}y_{i} + \sum_{i = 1}^{N} \gamma_{i}\\
& = & \sum_{i = 1}^{N} \gamma_{i} - \frac{1}{2}\alpha_{0}^{T}\alpha_{0}\\
& = & \sum_{i = 1}^{N} \gamma_{i} -\frac{1}{2}\sum_{i = 1}^{N}\sum_{j = 1}^{N}\gamma_{i}\gamma_{j} y_{i} y_{j} x_{i} x_{j}
\end{eqnarray}

最適な$\gamma$は$L(\gamma)$を「最大」にする$\gamma$により得られる。

\begin{eqnarray}
max_{\gamma} L(\gamma) \quad& subject\ to & \quad \sum_{i = 1}^{N} \gamma_{i} y_{i} = 0 \ , \ \ 0 \le \gamma_{i} \le C
\end{eqnarray}

---

### 5.3 C-サポートベクトルマシン
#### 5.3.1 C-サポートベクトルマシンの最適性条件

参照：付録B.3

#### 5.3.2 サポートベクトル

#### 5.3.3 サポートベクトル比と予測判別誤差

#### 5.3.4 予測判別誤差の上界

#### 5.3.5 統計的一致性

---

### 5.4 $\nu$-サポートベクトルマシン

#### 5.4.1 $\nu$-サポートベクトルマシンの性質

#### 5.4.2 双対表現と最小距離問題

#### 5.4.3 予測判別誤差の評価と統計的一致性

---

## 付録B　凸解析と凸最適化
### B.1 凸集合
#### B.1 (1) 凸集合
#### B.1 (1) 凸集合

### B.2 凸関数

### B.3 凸最適化
#### B.3 (1) 主問題と双対問題
#### B.3 (2) 弱双対条件と強双対条件
#### B.3 (3) 定理B.9：スレイター制約想定

ラグランジュ関数。
\begin{eqnarray}
L(x, \lambda) &=& f(x) + \sum_{j=1}^{m}\lambda_{j}h_{j}(x)
\end{eqnarray}

###### スレーター制約想定
$h_{j}(\tilde{x})<0$を満たす実行可能解$\tilde{x}$がする

###### 定理B.9：ミニマックス定理
$L(x, \lambda)$が$x$について凸関数、$\lambda$について凹関数。

\begin{eqnarray}
p^{*} &=& min_{x\in \mathbb{R}^{d}} \ max_{\lambda \ge 0} \ L(x, \lambda)\\
d^{*} &=& max_{\lambda \ge 0}\ min_{x\in \mathbb{R}^{d}}\ L(x, \lambda)
\end{eqnarray}

弱双対性：$d^{*} \le p^{*}$
強双対性：$d^{*} = p^{*}$

定理内でスレーター制約想定が成り立つなら$p^{*} \le d^{*}$も成立して、$p^{*} = d^{*}$が言え、強双対性が証明される。

##### 超平面分離定理（定理B.4）
#### B.3 (4) KKT条件