サポートベクターマシン

同義語:support vector machineSVM

概要

サポートベクターマシン(support vector machine)とは、2 つの類に分かれたデータ $(x_i,y_i)$($y_i=\pm1$)を超平面 $\langle w,x\rangle+b=0$ で分ける分類の方法で、超平面から最も近いデータ点までの距離(マージン)が最大のものを選ぶものである。マージンの最大化は $y_i(\langle w,x_i\rangle+b)\ge1$ のもとで $\frac12\|w\|^2$ を最小化する凸 2 次計画の問題で、その双対問題の解 $\alpha$ により $w=\sum_i\alpha_iy_ix_i$ と書け、$\alpha_i>0$ の点(サポートベクター)はマージンの境界の上にある。分離できないデータには条件の破れに罰を課すソフトマージンを使い、内積をカーネルに置き換えると非線形の境界が得られる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Karush–Kuhn–Tucker条件, 凸最適化, カーネル法

サポートベクターマシン(support vector machine、SVM)は、2 つの類に分かれたデータ $(x_i,y_i)$($x_i\in\mathbb{R}^d$、$y_i\in\{+1,-1\}$)を超平面 $\langle w,x\rangle+b=0$ で分ける分類の方法で、超平面とデータ点との距離の最小値(マージン)が最も大きくなるものを選ぶ。新しい点 $x$ は $\langle w,x\rangle+b$ の符号で分類する。
マージンを最大にする問題は凸 2 次計画の問題に書け、その双対問題を解くと、$w$ はデータ点の 1 次結合 $w=\sum_i\alpha_iy_ix_i$ で、係数 $\alpha_i$ が $0$ でない点(サポートベクター)はマージンの境界の上にあることが分かる。残りの点は取り除いても答えが変わらない。双対問題にはデータが内積 $\langle x_i,x_j\rangle$ の形でしか現れないので、内積を カーネル法 のカーネル $k(x_i,x_j)$ に置き換えると非線形の境界が得られる。
この記事では、マージン最大化の問題の解の存在と一意性、双対問題とサポートベクターの性質(主定理)を Karush–Kuhn–Tucker条件 から証明し、分けきれないデータのためのソフトマージン、カーネルによる拡張を述べる。

定義と使える条件

この記事を通して、データ $(x_1,y_1),\dots,(x_m,y_m)$($x_i\in\mathbb{R}^d$、$y_i\in\{+1,-1\}$)を固定し、$y_i=+1$ の点と $y_i=-1$ の点がどちらも 1 つ以上ある とする。内積を $\langle\cdot,\cdot\rangle$、ノルムを $\|\cdot\|$ と書く。

線形分離可能とマージン

$w\in\mathbb{R}^d\setminus\{0\}$、$b\in\mathbb{R}$ について、全ての $i$ で $y_i(\langle w,x_i\rangle+b)>0$ となるとき、超平面 $\langle w,x\rangle+b=0$ はデータを 分離する といい、そのような $(w,b)$ があるときデータは 線形分離可能 であるという。分離する $(w,b)$ の マージン を
$$ \gamma(w,b)=\min_{i}\frac{y_i(\langle w,x_i\rangle+b)}{\|w\|} $$
とおく。これは超平面から最も近いデータ点までの距離である。

ハードマージン SVM

次の問題 (P) を ハードマージン SVM という。
$$ \text{(P)}\qquad\text{最小化 }\tfrac12\|w\|^2\quad\text{条件 }y_i(\langle w,x_i\rangle+b)\ge1\ (i=1,\dots,m) $$
変数は $(w,b)\in\mathbb{R}^{d+1}$ である。その解 $(w^\ast,b^\ast)$ に対し、$f(x)=\langle w^\ast,x\rangle+b^\ast$ の符号で分類する。$y_if(x_i)=1$ となる点はマージンの境界 $\langle w^\ast,x\rangle+b^\ast=\pm1$ の上にある。

双対問題

$\alpha\in\mathbb{R}^m$ について
$$ D(\alpha)=\sum_{i=1}^m\alpha_i-\frac12\sum_{i,j=1}^m\alpha_i\alpha_jy_iy_j\langle x_i,x_j\rangle $$
とおき、次の問題 (D) を (P) の 双対問題 という。
$$ \text{(D)}\qquad\text{最大化 }D(\alpha)\quad\text{条件 }\alpha_i\ge0\ (i=1,\dots,m),\quad\sum_{i=1}^m\alpha_iy_i=0 $$
(D) の解 $\alpha$ について $\alpha_i>0$ となる $x_i$ を サポートベクター という。

$D(\alpha)=\sum_i\alpha_i-\frac12\|\sum_i\alpha_iy_ix_i\|^2$ なので $D$ は凹関数で、(D) は凸 2 次計画の問題である。
この記事の定理を使う条件は次のとおりである。

  • (i) ハードマージン SVM はデータが線形分離可能なときだけ意味をもつ(分離可能でなければ (P) の条件を満たす点がない)。分離可能でないデータにはソフトマージン SVM(thm-svm-soft)を使う。
  • (ii) 2 つの類がどちらも現れること。片方だけなら $b$ が決まらない(反例の表の 2 行目)。
  • (iii) カーネルに置き換えるときは、カーネルが正定値カーネル(カーネル法 の定義「正定値カーネル」)であること(反例の表の 3 行目)。

主定理:双対問題とサポートベクター

マージンと (P) の関係

点 $x_0$ と超平面 $\{x\mid\langle w,x\rangle+b=0\}$($w\ne0$)の距離は $\lvert\langle w,x_0\rangle+b\rvert/\|w\|$ である。データが線形分離可能であることと (P) の条件を満たす点があることは同値で、そのとき分離する超平面のマージンの上限は $1/\min\|w\|$($\min$ は (P) の条件を満たす $(w,b)$ についてとる)に等しく、(P) の解はマージンが最大の分離超平面を与える。

超平面への正射影は $x_0-\frac{\langle w,x_0\rangle+b}{\|w\|^2}w$ で、その差の長さが距離の式である。$(w,b)$ が分離するとき $c=\min_iy_i(\langle w,x_i\rangle+b)>0$ とおくと、$(w/c,b/c)$ は (P) の条件を満たし、$\gamma(w,b)=c/\|w\|=1/\|w/c\|$ である。逆に (P) の条件を満たす $(w,b)$ は分離し($w=0$ なら $y_ib\ge1$ が両方の符号で成り立たないので $w\ne0$)、$\gamma(w,b)\ge1/\|w\|$ である。よってマージンの上限は、(P) の条件を満たす $(w,b)$ についての $1/\|w\|$ の上限に等しい。$\square$

解の存在と一意性

データが線形分離可能なら、(P) の解 $(w^\ast,b^\ast)$ がただ 1 つ存在し、$w^\ast\ne0$ である。

存在。 条件を満たす $(w_0,b_0)$ をとる。$\|w\|\le\|w_0\|$ で条件を満たす $(w,b)$ の集合 $F$ は閉集合である。$y_p=+1$、$y_q=-1$ となる $p,q$ をとると、$\langle w,x_p\rangle+b\ge1$ と $\langle w,x_q\rangle+b\le-1$ から $1-\|w_0\|\|x_p\|\le b\le-1+\|w_0\|\|x_q\|$ なので $F$ は有界で、コンパクトである。連続関数 $\frac12\|w\|^2$ は $F$ で最小値をとり、それが (P) の最小値である。
$w^\ast$ の一意性。 解 $(w_1,b_1)$、$(w_2,b_2)$ で $w_1\ne w_2$ なら、中点も条件を満たし(条件は凸)、
$$ \Bigl\|\frac{w_1+w_2}2\Bigr\|^2=\frac{\|w_1\|^2+\|w_2\|^2}2-\Bigl\|\frac{w_1-w_2}2\Bigr\|^2< \|w_1\|^2 $$
となって最小性に反する。
$b^\ast$ の一意性。 prf-svm-margin と同じく $w^\ast\ne0$ である。解 $(w^\ast,b_1)$、$(w^\ast,b_2)$ で $b_1< b_2$ とし、$b=\frac{b_1+b_2}2$、$\varepsilon=\frac{b_2-b_1}2$ とおく。$y_i=+1$ なら $\langle w^\ast,x_i\rangle+b\ge1+\varepsilon$、$y_i=-1$ なら $-(\langle w^\ast,x_i\rangle+b)=-(\langle w^\ast,x_i\rangle+b_2)+\varepsilon\ge1+\varepsilon$ である。よって $(w^\ast,b)/(1+\varepsilon)$ は条件を満たし、ノルムは $\|w^\ast\|/(1+\varepsilon)< \|w^\ast\|$ となって矛盾する。$\square$

双対問題とサポートベクター

データが線形分離可能とし、$(w^\ast,b^\ast)$ を (P) の解とする。

  1. (D) は解をもち、(D) の最大値は $\frac12\|w^\ast\|^2$ である。
  2. (D) の任意の解 $\alpha$ について、$w^\ast=\sum_i\alpha_iy_ix_i$ であり、全ての $i$ で $\alpha_i\bigl(y_i(\langle w^\ast,x_i\rangle+b^\ast)-1\bigr)=0$ である。とくにサポートベクターはマージンの境界の上にある。
  3. $\alpha_j>0$ となる $j$ があり、そのような任意の $j$ について $b^\ast=y_j-\langle w^\ast,x_j\rangle$ である。また $\sum_i\alpha_i=\|w^\ast\|^2$ で、最大のマージンは $1/\|w^\ast\|=1/\sqrt{\sum_i\alpha_i}$ である。
  4. $S=\{i\mid\alpha_i>0\}$ とする。データを $(x_i,y_i)$($i\in S$)だけにした問題 (P) の解も $(w^\ast,b^\ast)$ である。
KKT 条件と Lagrange 双対

$g_i(w,b)=1-y_i(\langle w,x_i\rangle+b)$ とおくと (P) は $\mathbb{R}^{d+1}$ での問題「$\frac12\|w\|^2$ を $g_i\le0$ のもとで最小化」で、目的関数は凸で微分可能、制約は全て 1 次式である。Lagrange 関数は
$$ L(w,b,\alpha)=\frac12\|w\|^2+\sum_i\alpha_i\bigl(1-y_i(\langle w,x_i\rangle+b)\bigr) $$
である。
1。 $(w^\ast,b^\ast)$ は大域解なので局所解であり、制約は 1 次式なので Karush–Kuhn–Tucker条件 の系「ほかの制約想定」の 2 により KKT 条件を満たす $\alpha^\ast\ge0$ がある。$w$ と $b$ についての停留性は $w^\ast-\sum_i\alpha_i^\ast y_ix_i=0$、$-\sum_i\alpha_i^\ast y_i=0$ である。
$\theta(\alpha)=\inf_{w,b}L(w,b,\alpha)$ を計算する。$L$ は $b$ について 1 次で係数は $-\sum_i\alpha_iy_i$ なので、これが $0$ でなければ $\theta(\alpha)=-\infty$ である。$\sum_i\alpha_iy_i=0$ なら $v=\sum_i\alpha_iy_ix_i$ とおいて $L=\frac12\|w\|^2-\langle w,v\rangle+\sum_i\alpha_i$ で、これは $w=v$ でだけ最小値 $\sum_i\alpha_i-\frac12\|v\|^2=D(\alpha)$ をとる。よって $\alpha\ge0$ での $\theta$ の最大化は (D) と同じである。Karush–Kuhn–Tucker条件 の定理「凸な問題での十分性」により $\alpha^\ast$ は $\theta$ を最大にし、$\theta(\alpha^\ast)=\frac12\|w^\ast\|^2$ である。よって $\alpha^\ast$ は (D) の解で、最大値は $\frac12\|w^\ast\|^2$ である。
2。 $\alpha$ を (D) の解とする。$\alpha\ge0$ で $(w^\ast,b^\ast)$ は条件を満たすので、和の各項は $0$ 以下で
$$ D(\alpha)=\theta(\alpha)\le L(w^\ast,b^\ast,\alpha)\le\frac12\|w^\ast\|^2=D(\alpha) $$
である。よって等号が成り立つ。右の等号から $0$ 以下の項の和 $\sum_i\alpha_i(1-y_i(\langle w^\ast,x_i\rangle+b^\ast))$ が $0$ なので各項が $0$ である。左の等号から $(w^\ast,b^\ast)$ は $L(\cdot,\cdot,\alpha)$ の最小点で、最小点の $w$ は $v=\sum_i\alpha_iy_ix_i$ だけなので $w^\ast=v$ である。
3。 $w^\ast\ne0$(prop-svm-unique)なので $\alpha\ne0$ で、$\alpha_j>0$ となる $j$ がある。2 から $y_j(\langle w^\ast,x_j\rangle+b^\ast)=1$ で、両辺に $y_j$ を掛けて $y_j^2=1$ を使えば $b^\ast=y_j-\langle w^\ast,x_j\rangle$ である。$D(\alpha)=\sum_i\alpha_i-\frac12\|w^\ast\|^2=\frac12\|w^\ast\|^2$ から $\sum_i\alpha_i=\|w^\ast\|^2$ で、マージンは prop-svm-margin から $1/\|w^\ast\|$ である。
4。 $\sum_{i\in S}\alpha_iy_i=0$ で $\alpha_i>0$($i\in S$)、$S\ne\emptyset$ なので、$S$ には両方の類の点がある。$(w^\ast,b^\ast)$ は $S$ だけの問題の条件を満たし、$(\alpha_i)_{i\in S}$ とあわせて停留性($w^\ast=\sum_{i\in S}\alpha_iy_ix_i$、$\sum_{i\in S}\alpha_iy_i=0$)と相補性(2)を満たすので KKT 点である。定理「凸な問題での十分性」により $(w^\ast,b^\ast)$ は $S$ だけの問題の解で、prop-svm-unique により解はこれだけである。$\square$

2 から、分類に使う関数は
$$ f(x)=\sum_{i\in S}\alpha_iy_i\langle x_i,x\rangle+b^\ast $$
と、サポートベクターとの内積だけで書ける。4 は、マージンの境界より外側にある点を動かしたり取り除いたりしても(境界を越えない限り)答えが変わらないことを表す。(D) の解 $\alpha$ そのものは一意とは限らないが、$w^\ast$ と $b^\ast$ は一意である。マージン最大化の問題とその双対は SSBD14 第 15 章(Lemma 15.2。§15.4 は $b=0$ の問題の双対)、HTF09 §12.2.1(pp. 420–421)にもある。
図: 左は例「4 点のハードマージン」。正の点 (2,0)、(0,2)、(3,3)(丸)と負の点 (0,0)(四角)を、実線の直線 x₁+x₂=1 が分ける。破線はマージンの境界 x₁+x₂=0 と x₁+x₂=2 で、その上の 3 点(大きな丸で囲んだもの)がサポートベクター。(3,3) は境界の外にあり、取り除いても直線は変わらない。矢印は (0,0) から直線までの距離 1/‖w‖=1/√2。右は例「XOR と多項式カーネル」。4 点 (±1,±1) に対する f(x)=x₁x₂ の等高線で、実線 f=0(座標軸)が決定境界、破線 f=±1 がマージンの境界。灰色の領域が |f|<1。 図: 左は例「4 点のハードマージン」。正の点 (2,0)、(0,2)、(3,3)(丸)と負の点 (0,0)(四角)を、実線の直線 x₁+x₂=1 が分ける。破線はマージンの境界 x₁+x₂=0 と x₁+x₂=2 で、その上の 3 点(大きな丸で囲んだもの)がサポートベクター。(3,3) は境界の外にあり、取り除いても直線は変わらない。矢印は (0,0) から直線までの距離 1/‖w‖=1/√2。右は例「XOR と多項式カーネル」。4 点 (±1,±1) に対する f(x)=x₁x₂ の等高線で、実線 f=0(座標軸)が決定境界、破線 f=±1 がマージンの境界。灰色の領域が |f|<1。

ソフトマージンとカーネル

データが線形分離可能でないときは、条件を破る量 $\xi_i\ge0$ を許し、その和に罰を課す。

ソフトマージン SVM

$C>0$ とし、次の問題を ソフトマージン SVM という。
$$ \text{(P}_C\text{)}\qquad\text{最小化 }\tfrac12\|w\|^2+C\sum_{i=1}^m\xi_i\quad\text{条件 }y_i(\langle w,x_i\rangle+b)\ge1-\xi_i,\ \xi_i\ge0 $$
その双対問題 (D$_C$) は、(D) の条件 $\alpha_i\ge0$ を $0\le\alpha_i\le C$ に替えたものとする。

  1. (P$_C$) は(データが分離可能でなくても)解をもつ。解では $\xi_i=\max\{0,1-y_i(\langle w,x_i\rangle+b)\}$(ヒンジ損失)で、$w$ は全ての解で同じ $w^\ast$ である。
  2. (D$_C$) は解をもち、その最大値は (P$_C$) の最小値に等しい。(D$_C$) の任意の解 $\alpha$ と (P$_C$) の任意の解 $(w^\ast,b^\ast,\xi^\ast)$ について $w^\ast=\sum_i\alpha_iy_ix_i$ で、$f(x)=\langle w^\ast,x\rangle+b^\ast$ とおくと、$\alpha_i=0$ なら $y_if(x_i)\ge1$、$0< \alpha_i< C$ なら $y_if(x_i)=1$、$\alpha_i=C$ なら $y_if(x_i)\le1$ である。
  3. データが線形分離可能で、(D) のある解 $\alpha^\ast$ が $\max_i\alpha_i^\ast\le C$ を満たすなら、(P) の解 $(w^\ast,b^\ast)$ と $\xi=0$ は (P$_C$) の解である。

1。 $(w,b)$ を固定すると、条件を満たす最小の $\xi_i$ はヒンジ損失なので、(P$_C$) は $F(w,b)=\frac12\|w\|^2+C\sum_i\max\{0,1-y_i(\langle w,x_i\rangle+b)\}$ の最小化と同じである。$F(w,b)\le F(0,0)=Cm$ なら $\|w\|^2\le2Cm$ で、各ヒンジ損失は $m$ 以下なので、prf-svm-unique の $p,q$ について $1-\langle w,x_p\rangle-b\le m$、$1+\langle w,x_q\rangle+b\le m$ となり $b$ も有界である。よって $F$ は有界閉集合の上で最小値をとる。$F$ は凸で $\frac12\|w\|^2$ は $w$ について狭義凸なので、prf-svm-unique と同じ中点の議論で $w$ は一意である。
2。 変数 $(w,b,\xi)$ について制約は 1 次式なので、prf-svm-dual の 1 と同じく乗数 $\alpha\ge0$(マージンの条件)、$\mu\ge0$($\xi_i\ge0$)がある。Lagrange 関数で $\xi_i$ の係数は $C-\alpha_i-\mu_i$ なので、$\inf_\xi$ が $-\infty$ でないのは $\mu_i=C-\alpha_i$ のときで、$\mu_i\ge0$ は $\alpha_i\le C$ になる。残りは prf-svm-dual の 1 と同じ計算で、Lagrange 双対は (D$_C$) になり、最大値は (P$_C$) の最小値に等しい。(D$_C$) の解 $\alpha$ と $\mu_i=C-\alpha_i$ について prf-svm-dual の 2 と同じ不等式の列から、$w^\ast=\sum_i\alpha_iy_ix_i$ と、$\alpha_i(1-\xi_i^\ast-y_if(x_i))=0$、$\mu_i\xi_i^\ast=0$ が従う。$\alpha_i< C$ なら $\mu_i>0$ で $\xi_i^\ast=0$、よって $y_if(x_i)\ge1$。$\alpha_i>0$ なら $y_if(x_i)=1-\xi_i^\ast\le1$。両方なら $=1$ である。
3。 $(w^\ast,b^\ast,0)$ と $\alpha^\ast$、$\mu=C-\alpha^\ast\ge0$ は (P$_C$) の KKT 条件を満たす($\xi$ の停留性は $C-\alpha_i^\ast-\mu_i=0$、相補性は $\xi=0$ から、残りは thm-svm-dual から)。Karush–Kuhn–Tucker条件 の定理「凸な問題での十分性」により解である。$\square$

$\alpha_i=C$ の点はマージンの内側にあるか誤って分類される点で、これもサポートベクターである。$b^\ast$ は $0< \alpha_j< C$ の $j$ から $b^\ast=y_j-\langle w^\ast,x_j\rangle$ で求まるが、そのような $j$ がないと $b^\ast$ は一意とは限らない(ex-svm-soft)。1 から (P$_C$) は「ヒンジ損失の和 $+\frac1{2C}\|w\|^2$」の最小化で、カーネル法 の表現定理の形になる(SSBD14 Claim 15.5、HTF09 §12.3.2、pp. 426–428)。

カーネルへの置き換え

$\varphi$ を集合 $X$ から Hilbert 空間 $H$ への写像、$k(x,y)=\langle\varphi(x),\varphi(y)\rangle$ とし、$x_i\in X$ とする。(P) で $w\in H$、$\langle w,x_i\rangle$ を $\langle w,\varphi(x_i)\rangle$ に替えた問題が条件を満たす点をもつなら、その解はただ 1 つで、$w^\ast=\sum_i\alpha_iy_i\varphi(x_i)$、分類の関数は
$$ f(x)=\sum_i\alpha_iy_ik(x_i,x)+b^\ast $$
である。ここで $\alpha$ は (D) の $\langle x_i,x_j\rangle$ を $k(x_i,x_j)$ に替えた問題の解で、$b^\ast$ は thm-svm-dual の 3 の式の内積を $k$ に替えて求まる。(P$_C$) についても同じである。

$V$ を $\varphi(x_1),\dots,\varphi(x_m)$ の張る部分空間(有限次元なので閉)、$P$ を $V$ への直交射影とする。$\langle w,\varphi(x_i)\rangle=\langle Pw,\varphi(x_i)\rangle$ で、$\|Pw\|\le\|w\|$、等号は $w\in V$ のときだけなので、解は $V$ にしかない。$V$ の正規直交基底での $\varphi(x_i)$ の座標を $z_i\in\mathbb{R}^r$ とすると $\langle z_i,z_j\rangle=k(x_i,x_j)$ で、$V$ での問題はデータ $(z_i,y_i)$ の (P) である。prop-svm-unique と thm-svm-dual を当て、$\langle w^\ast,\varphi(x)\rangle=\sum_i\alpha_iy_ik(x_i,x)$ を使う。(P$_C$) も同様である。$\square$

$k$ が正定値カーネルなら、カーネル法 の系「正定値カーネルの特徴づけ」により $k$ はこの形に書ける($H$ は再生核 Hilbert 空間)。

公式の表

名前式条件根拠
点と超平面の距離$\lvert\langle w,x_0\rangle+b\rvert/\Vert w\Vert$$w\ne0$prop-svm-margin
双対の目的関数$D(\alpha)=\sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_jk(x_i,x_j)$線形なら $k=\langle\cdot,\cdot\rangle$def-svm-dual
双対の条件$\sum_i\alpha_iy_i=0$、$0\le\alpha_i$(ソフトなら $\le C$)thm-svm-soft
重み$w^\ast=\sum_i\alpha_iy_ix_i$(D) の任意の解thm-svm-dual
定数項$b^\ast=y_j-\sum_i\alpha_iy_ik(x_i,x_j)$$0< \alpha_j$(ソフトなら $< C$)thm-svm-dual
マージン$1/\Vert w^\ast\Vert=1/\sqrt{\sum_i\alpha_i}$ハードマージンthm-svm-dual
分類$\operatorname{sign}\bigl(\sum_i\alpha_iy_ik(x_i,x)+b^\ast\bigr)$$k$ は正定値カーネルprop-svm-kernel

計算の手順

  1. 尺度をそろえる。 各特徴を標準化する(距離と内積が尺度に依存するため)。
  2. カーネルと $C$ を選ぶ。 線形、多項式、Gauss のカーネルなど。
  3. (D$_C$) を解く。 凸 2 次計画である。変数を 2 つずつ更新する方法(SMO)などの専用の解法が使われる。
  4. $b^\ast$ を求める。 $0< \alpha_j< C$ の各 $j$ で $y_j-\sum_i\alpha_iy_ik(x_i,x_j)$ を計算し、数値誤差を考えて平均する。
  5. 予測する。 $f(x)=\sum_{\alpha_i>0}\alpha_iy_ik(x_i,x)+b^\ast$ の符号。和はサポートベクターだけでよい。
  6. $C$ とカーネルの幅を選ぶ。 学習に使っていないデータでの誤り率で比べる(交差検証)。
    状況起こること対処
    $C$ が大きすぎる外れた点に合わせて境界が曲がる(ハードマージンに近づく)$C$ を小さくする
    $C$ が小さすぎるマージンが広がり、多くの点が $\alpha_i=C$ になる$C$ を大きくする
    Gauss カーネルの幅が小さすぎる各点のまわりだけを囲む境界になる幅を点の間隔より大きくする

例題

4 点のハードマージン

$\mathbb{R}^2$ の正の点 $x_1=(2,0)$、$x_2=(0,2)$、$x_3=(3,3)$ と負の点 $x_4=(0,0)$ のハードマージン SVM を解く。
使う公式:thm-svm-dual、Karush–Kuhn–Tucker条件 の定理「凸な問題での十分性」。
答え:$w^\ast=(1,1)$、$b^\ast=-1$、$\alpha=(\frac12,\frac12,0,1)$。境界は $x_1+x_2=1$、マージンは $1/\sqrt2$。サポートベクターは $x_1,x_2,x_4$ で、$x_3$ を取り除いても答えは変わらない。$\sum_i\alpha_i=2=\|w^\ast\|^2$ である。

確かめを開く

$\sum_i\alpha_iy_ix_i=\frac12(2,0)+\frac12(0,2)-(0,0)=(1,1)$、$\sum_i\alpha_iy_i=\frac12+\frac12+0-1=0$。$y_i(\langle w^\ast,x_i\rangle+b^\ast)$ は順に $1,1,5,1$ で条件を満たし、$\alpha_3=0$ の点以外は等号なので相補性も成り立つ。よって KKT 点で、定理「凸な問題での十分性」により解である。$b^\ast$ は $x_4$ から $-1-0=-1$、$x_1$ から $1-2=-1$ で一致する。$(0,0)$ と直線 $x_1+x_2=1$ の距離は $1/\sqrt2$。

XOR と多項式カーネル

正の点 $(1,1),(-1,-1)$、負の点 $(1,-1),(-1,1)$ を、カーネル $k(x,y)=(1+\langle x,y\rangle)^2$ のハードマージン SVM で分ける。
使う公式:prop-svm-kernel、thm-svm-dual。
答え:$\alpha_i=\frac18$(4 点とも)、$b^\ast=0$、$f(x)=x_1x_2$。4 点全てがサポートベクターで、特徴の空間でのマージンは $1/\sqrt{\sum_i\alpha_i}=\sqrt2$ である。

途中の計算を開く

Gram 行列は対角が $(1+2)^2=9$、それ以外が全て $1$($(1-2)^2=1$、$(1+0)^2=1$)。$Q_{ij}=y_iy_jk(x_i,x_j)$ の各行の和は $9+1-1-1=8$ なので、$\alpha=\frac18(1,1,1,1)$ で $D$ の勾配 $1-Q\alpha$ は $0$、$\sum_i\alpha_iy_i=0$ を満たす。$D$ は凹なので (D) の解で、$D=\frac12-\frac12\cdot\frac1{64}\cdot32=\frac14$。$f(x)-b^\ast=\frac18\bigl[(1+s)^2+(1-s)^2-(1+t)^2-(1-t)^2\bigr]=\frac14(s^2-t^2)=x_1x_2$($s=x_1+x_2$、$t=x_1-x_2$)。$x=(1,1)$ で $1+b^\ast=1$ から $b^\ast=0$。

線形のカーネルでは同じ 4 点は分離できない(反例の表の 1 行目)。2 次の多項式カーネルの特徴写像は $x_1x_2$ の成分を含むので(カーネル法 の例「2 次の多項式カーネルの特徴写像」)、特徴の空間では分離できる。

1 次元のソフトマージン

$\mathbb{R}$ の点 $x=-1,0$(負)と $x=1$(正)について、ハードマージン SVM と $C=1,2$ のソフトマージン SVM を解く。
使う公式:thm-svm-dual、thm-svm-soft。
答え:ハードマージンは $w^\ast=2$、$b^\ast=-1$、$\alpha=(0,2,2)$、マージン $\frac12$。$C=2$ では thm-svm-soft の 3 から同じ答えである。$C=1$ では $\alpha=(0,1,1)$、$w^\ast=1$、最小値 $\frac32$ で、$b^\ast$ は区間 $[-1,0]$ のどれでもよい($0< \alpha_j< C$ の点がない)。

確かめを開く

(D) の条件 $\sum\alpha_iy_i=0$ は $\alpha_3=\alpha_1+\alpha_2$。$w=\alpha_1+\alpha_3=2\alpha_1+\alpha_2$、$D=2(\alpha_1+\alpha_2)-\frac12(2\alpha_1+\alpha_2)^2\le2s-\frac12s^2$($s=\alpha_1+\alpha_2$)で、等号は $\alpha_1=0$。ハードでは $s=2$ で最大値 $2=\frac12\cdot2^2$。$C=1$ では $s=\alpha_3\le1$ なので $\alpha=(0,1,1)$、$D=\frac32$。$w=1$ のとき目的関数は $\frac12+\max\{0,1+b\}+\max\{0,-b\}+\max\{0,b\}$ で、$-1\le b\le0$ で $\frac32$、$b>0$ で $\frac32+2b$、$b< -1$ で $\frac12-b$。

使える条件と反例

各行は、この記事の定理の仮定を 1 つだけ外す。

外す仮定反例成り立たなくなること
線形分離可能線形のカーネルで XOR の 4 点(ex-svm-xor の点)(P) の条件を満たす点がない。ソフトマージン($C=1$)の解は $w^\ast=0$、$b^\ast\in[-1,1]$ で、$f$ は定数になり点を分けない
両方の類が現れる$\mathbb{R}$ の点 $1,2$ がともに正(P) の解は $w=0$、$b\ge1$ の全てで一意でない。(D) の解は $\alpha=0$ で、$b^\ast$ の式が使えない
正定値カーネル$k(x,y)=-xy$、点 $1$(正)、$-1$(負)$\alpha=(a,a)$ で $D=2a+2a^2\to\infty$。(D) に解がない
反例の確かめを開く

1 行目:条件は $w_1+w_2+b\ge1$、$-w_1-w_2+b\ge1$、$-(w_1-w_2+b)\ge1$、$-(-w_1+w_2+b)\ge1$。最初の 2 つの和は $b\ge1$、後の 2 つの和は $b\le-1$ で矛盾する。ソフトでは目的関数 $F$ は $x\mapsto-x$ でデータが自分に移るので $F(w,b)=F(-w,b)$、凸性から $F(0,b)\le F(w,b)$。$F(0,b)=2\max\{0,1-b\}+2\max\{0,1+b\}\ge4$ で、等号は $-1\le b\le1$。2 行目:$\sum\alpha_iy_i=\alpha_1+\alpha_2=0$ と $\alpha\ge0$ から $\alpha=0$。3 行目:Gram 行列 $\begin{pmatrix}-1&1\\1&-1\end{pmatrix}$ の固有値は $-2,0$。$y_iy_jk(x_i,x_j)$ は全て $-1$ で、$D=2a-\frac12a^2(-4)$。

よくある誤り

誤り正しくはなぜ
双対で $\sum_i\alpha_iy_i=0$ を落とす$b$ を入れたモデルでは必須$L$ を $b$ で微分した条件である。ex-svm-hard で落とすと、$x_4=(0,0)$ の $\alpha_4$ がいくらでも大きくでき $D\to\infty$
$b^\ast$ を $\alpha_j=C$ の点から計算する$0< \alpha_j< C$ の点を使う$\alpha_j=C$ の点は $\xi_j>0$ のことがあり、$y_jf(x_j)=1$ が成り立たない
サポートベクターはマージンの境界上の点だけソフトでは $\alpha_i=C$ の点(境界の内側、誤分類)も含むthm-svm-soft の 2
マージンを $2/\Vert w^\ast\Vert$ とする最も近い点までは $1/\Vert w^\ast\Vert$、2 本の境界の間が $2/\Vert w^\ast\Vert$prop-svm-margin
$f(x)$ の値を確率と読む$f$ は符号と大きさの目安だけ確率が要るなら別の較正が要る

補足

マージンと汎化

$\mathbb{R}^d$ の半空間の族の VC次元 は $d+1$ で(VC次元 の例「半平面と半空間」)、VC 次元による誤り率の上界は次元 $d$ に依存する。マージンを使うと次元によらない上界がある。データの分布が $\|x\|\le\rho$ に載り、原点を通る超平面で $\|w\|=1$、$y\langle w,x\rangle\ge\gamma$ となる $w$ があるとき、$m$ 個の標本から $b=0$ に限ったハードマージン SVM で得た分類の誤り率は、確率 $1-\delta$ 以上で
$$ \sqrt{\frac{4(\rho/\gamma)^2}{m}}+\sqrt{\frac{2\log(2/\delta)}{m}} $$
以下である(SSBD14 Theorem 15.4。証明は同書第 26 章)。ここでは証明しない。証明の道具のうち、一様な偏差の上界とノルムが有界な線形の族の評価は Rademacher複雑度 で証明し、損失を合成するときの縮小の補題は同記事で主張を述べる。$\rho/\gamma$ だけに依存するので、無限次元の特徴の空間を使うカーネルの場合にも意味をもつ。

ヒンジ損失の形(thm-svm-soft の 1)のまま確率的勾配法で解くこともできる(SSBD14 §15.5)。ヒンジ損失をロジスティック損失 $\log(1+e^{-yf})$ に替えるとロジスティック回帰になる。

文献

SSBD14 第 15 章(Lemma 15.2、Theorem 15.4、Claim 15.5、§15.4、§15.5)、第 16 章 §16.3、HTF09 §12.2–12.3(pp. 417–428)。

関連項目

参考文献

[1]
Shai Shalev-Shwartz, Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, 第 15 章(Lemma 15.2、Theorem 15.4、Claim 15.5、§15.4、§15.5)、第 16 章 §16.3

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する