サポートベクターマシン(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$ の点(サポートベクター)はマージンの境界の上にある。分離できないデータには条件の破れに罰を課すソフトマージンを使い、内積をカーネルに置き換えると非線形の境界が得られる。
前提知識: 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\|}
$$
とおく。これは超平面から最も近いデータ点までの距離である。
次の問題 (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 次計画の問題である。
この記事の定理を使う条件は次のとおりである。
点 $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) の解とする。
$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。
データが線形分離可能でないときは、条件を破る量 $\xi_i\ge0$ を許し、その和に罰を課す。
$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。 $(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 |
| 状況 | 起こること | 対処 |
|---|---|---|
| $C$ が大きすぎる | 外れた点に合わせて境界が曲がる(ハードマージンに近づく) | $C$ を小さくする |
| $C$ が小さすぎる | マージンが広がり、多くの点が $\alpha_i=C$ になる | $C$ を大きくする |
| Gauss カーネルの幅が小さすぎる | 各点のまわりだけを囲む境界になる | 幅を点の間隔より大きくする |
$\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$。
正の点 $(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 次の多項式カーネルの特徴写像」)、特徴の空間では分離できる。
$\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)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する