画像解析等で、任意の次元のデータポイント群を２つに分類したい場合がよく出てきますが、分離境界超平面のパラメータを決定できる線形SVMを実装してみます。
目次
SVM実装基礎知識
n次元空間での境界超平面を決定するための基礎的な知識をまとめます。
点と直線の距離
２次元平面における点$(x,y)$と直線$ax+by+c=0$の距離は以下のように与えられます。
$$d = \frac{|ax+by+c|}{\sqrt{a^2+b^2}}$$
これを行列表示すると、
$$d = \frac{|\mathbf{a}^\mathrm{T}\mathbf{x}+c|}{\|\mathbf{a}\|}$$
ただし、
$$\mathbf{a}=(a,b)^\mathrm{T}\in \mathbb{R}^2$$
点と超平面の距離
任意の次元の超平面と点の距離は上記のn次元空間バージョンを考えると求めることができます。
$$\mathbf{D}_n = \frac{|\mathbf{a}^\mathrm{T}\mathbf{x}+c|}{\|\mathbf{a}\|}$$
勾配
二次元空間での勾配は以下のように表されます。
$$\nabla f = (\frac{\partial f}{\partial x},\frac{\partial f}{\partial y})^\mathrm{T}$$
ここで、
$$\mathbf{x}\in \mathbb{R}^n$$
とすると、
n次元空間での勾配について、
$$\nabla = \frac{\partial }{\partial \mathbf{x}}$$
となります。
勾配に関する公式
$$\nabla \mathbf{a}^\mathrm{T}\mathbf{x} = \frac{\partial \mathbf{a}^\mathrm{T}\mathbf{x}}{\partial \mathbf{x}} = \mathbf{a}$$
$$\nabla \|\mathbf{x}\|^2 = 2\mathbf{x}$$
ラグランジュの未定乗数法の不等式制約とKKT条件
通常の多変数、複数制約条件でのラグランジュの未定乗数法については以下にまとめています。
制約条件を不等式に拡張し、条件の元での最小値を求める問題について考えます。
$$\min f(\mathbf{x})\:\: s.t. \mathbf{g}(\mathbf{x})\leq 0$$
等式条件と同様にラグランジアンを以下のようにします。
$$\cal{L}(\mathbf{x},\mathbf{\lambda})=f(\mathbf{x})-\mathbf{\lambda}^\mathrm{T}\mathbf{G}$$
この時、
$$\nabla_\mathbf{x}\cal{L}=0$$
$$g_i(\mathbf{x})\leq 0, \: \lambda_i \geq 0,\: \lambda_i g_i(\mathbf{x})=0\:\:\:\forall i $$
を解くことで、fを最小化することができます。(KKT条件）
２次計画問題
難しいので別称でまとめます。
サポートベクターマシン
n次元空間におけるデータポイント$\mathbf{x}_i\in\mathbb{R}^n$を以下のような超平面によって２群に分類するという場合について考えます。
$$\cal{D}_n = \mathbf{w}^\mathrm{T}\mathbf{x}$$
この時、超平面とそれぞれのデータポイント群の点(サポートベクター）との最小の距離をマージンとします。
各データポイント$\mathbf{x}_i\in\mathbb{R}^n$がクラスター１とクラスター２どちらに属するかを標識するラベルを以下のように定義します。
$$\left\{ \begin{align} &\mathbf{w}^\mathrm{T}\mathbf{x}_i + b>0 \cdots y_i =1\\ &\mathbf{w}^\mathrm{T}\mathbf{x}_i + b<0 \cdots y_i= -1 \end{align} \right.$$
まとめると、
$$y_i(\mathbf{w}^\mathrm{T}\mathbf{x}_i + b)>0$$
ここで、マージンの大きさは。。。。
理論は書きかけです。
