【疑問】SVMの「マージン最大化」と「カーネルトリック」、何をしてるん？次元を上げたら計算が重くならんの？【G検定】

SVM（サポートベクターマシン）の説明で、マージン最大化とカーネルトリックが出てくる
ロジスティック回帰も境界の線を引くやつやろ？何が違うん

前提のおさらい。ロジスティック回帰は、重みつきの和 $z=\mathbf{w}\cdot \mathbf{x}+b$ をシグモイド関数で確率にして分類する。$z=0$ のところが2つのクラスの境界になる

＞＞1
SVMも $\mathbf{w}\cdot \mathbf{x}+b=0$ の境界を引く。違うのは、境界の決め方
2つのクラスを分けられる線はたくさんある。SVMはその中で、境界から一番近いデータまでの距離（マージン）が一番広くなる線を選ぶ
この一番近いデータをサポートベクターと呼ぶ。境界はサポートベクターだけで決まって、遠くのデータを動かしても変わらん

＞＞3
マージンの幅は、両側のサポートベクターが $\mathbf{w}\cdot \mathbf{x}+b=\pm 1$ に乗るようにそろえると

$\mathbf{w}=(3,4)$ なら $\Vert \mathbf{w}\Vert =5$ で、幅は0.4。$\Vert \mathbf{w}\Vert$ を小さくするほどマージンが広がる

＞＞3
現実のデータはきれいに分けられんことのほうが多いやろ

＞＞5
そこで、境界をはみ出すデータを少し許すソフトマージンを使う。はみ出しへの罰の強さを $C$ で決める
$C$ を大きくすると、はみ出しを許さず学習データに合わせこむ。小さくすると、多少間違えてもマージンを広くとる

カーネルトリックは、まっすぐの線では分けられないデータのための工夫
1次元で、クラスAが $x=-1,0,1$、クラスBが $x=-3,3$ だと、しきい値を1つ置くだけでは分けられん
$x$ を $(x,x^2)$ の2次元に移すと、Aは $x^2\le 1$、Bは $x^2=9$ になって、$x^2=5$ の横線で分けられる

＞＞7
次元を上げたら、そのぶん計算が重くなるんちゃうの？

＞＞8
そこがトリック。SVMの計算には、データどうしの内積しか出てこん。だから、変換したあとの内積を、変換せずに直接計算できる関数（カーネル）があればええ
たとえば $k(\mathbf{x},\mathbf{z})=(\mathbf{x}\cdot \mathbf{z}{)}^2$ は、2次元の $\mathbf{x}$ を $(x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2)$ に移したあとの内積と同じ
$\mathbf{x}=(1,2)$、$\mathbf{z}=(3,1)$ なら、$(1\cdot 3+2\cdot 1{)}^2=25$。移したあとの $(1,2.83,4)\cdot (9,4.24,1)=9+12+4=25$ と一致する

＞＞9
よく使われるガウスカーネル（RBFカーネル）$k=\exp (-\gamma \Vert \mathbf{x}-\mathbf{z}{\Vert }^2)$ は、移したあとの次元が無限になる。それでも、この式1つで内積が計算できる

＞＞10
便利やけど、データが何十万件もあると、全部のペアのカーネルを扱うのが重くなる。大きなデータでは、ほかのモデルが選ばれることも多い