📿 ✌🏿 🤷🏼 サポートベクターマシン、30行 🛵 👨🏻‍💻 🧝🏼

この記事では、scikit-learnやその他のライブラリを使用せずに、Pythonでわずか30行で既製の実装を使用して、非常に単純なサポートベクターマシンを作成する方法を紹介します。SMOアルゴリズムを理解したいが、複雑すぎるように思われる場合は、この記事が役立つかもしれません。

~~マトリックス~~サポートベクターマシンが何であるかを説明することは不可能です...あなたはそれを自分で見なければなりません。

Habréにはメディア要素を挿入する機能があることを知ったので、小さなデモを作成しました（突然機能しない場合でも、github [1]のバージョンで運試しをすることができます）。平面上に配置（2つのフィーチャのスペース）

$X$ そして

$Y$ ）いくつかの赤と青のポイント（これは私たちのデータセットです）とマシンが分類を実行します（対応するリクエストが分類される場所に応じて、背景の各ポイントが塗りつぶされます）。ポイントを移動し、コア（放射基底関数を試すことをお勧めします）と境界の硬さ（一定）を変更します

$C$ ）。JSのひどいコードについてお詫びします-私は人生で数回だけそれを書きました。アルゴリズムを理解するために、記事の後半でPythonコードを使用してください。

コンテンツ

, , , . , — . , — [2] [3], , , .
« SMO» SMO , , . , , SMO, .
, «» Python .
« sklearn.svc.svm» — 2D confusion matrix MNIST.
«» - .

サポートベクターマシンは、分類、回帰、異常検出などの問題を解決するための機械学習手法（教師あり学習）です。バイナリ分類問題の例を使用して検討します。トレーニングサンプルは、特徴ベクトルのセットです。

$\boldsymbol{x}_i$ 2つのクラスのいずれかに分類されます

$y_i = \pm 1$ ..。分類リクエスト-ベクター

$\boldsymbol{x}$ クラスを割り当てる必要があります

$+1$ または

$-1$ ..。

最も単純なケースでは、トレーニングサンプルのクラスは、図のように1本の直線のみを描画することで分割できます（フィーチャの数が多い場合、これは超平面になります）。さて、あるポイントを分類するように要求が来たとき

$\boldsymbol{x}$ 、どちら側になるかをクラスに配置するのが妥当です。

最適な直線を選択する方法は？直感的には、クラスの真ん中で直線を通過させたいです。これを行うには、直線の方程式を次のように記述します。

$\boldsymbol{x} \cdot \boldsymbol{w} + b = 0$ 直線に最も近いデータセットポイントが満たすようにパラメータをスケーリングします

$\boldsymbol{x} \cdot \boldsymbol{w} + b = \pm 1$ （クラスに応じてプラスまたはマイナス）-これらの点はサポートベクターと呼ばれます。

この場合、クラスの境界点間の距離は次のようになります。

$2/|\boldsymbol{w}|$ ..。明らかに、クラスを可能な限り分離するために、この値を最大化する必要があります。後者は最小化と同等です

$\frac{1}{2} |\boldsymbol{w}|^2$ 、最適化問題全体が書かれています

$\begin{aligned} &\min \frac{1}{2} |\boldsymbol{w}|^2 \\ \text{subject to: } &y_i \left(\boldsymbol{x}_i \cdot \boldsymbol{w} + b\right) - 1 \geq 0. \end{aligned}$

あなたがそれを解決するならば、それから要求に応じて分類

$\boldsymbol{x}$ このように生産

$\text{class}(\boldsymbol{x}) = \text{sign}\left(\boldsymbol{x} \cdot \boldsymbol{w} + b\right).$

これは最も単純なサポートベクターマシンです。

そして、図のように異なるクラスのポイントが相互に侵入した場合はどうすればよいでしょうか。

以前の最適化問題を解決することはできなくなりました。これらの条件を満たすパラメーターはありません。そうすれば、ポイントが境界に違反することをその量だけ許可することができます。

$\xi_i \geq 0$ 、しかし、そのような違反者はできるだけ少ないことが望ましい。これは、目的関数を追加の項で変更することで実現できます（正則化

$L_1$ ）：

$\begin{aligned} &\min\left( \frac{1}{2} |\boldsymbol{w}|^2 + C \sum_i \xi_i \right)\\ \text{subject to: }&\xi_i + y_i \left(\boldsymbol{x}_i \cdot \boldsymbol{w} + b\right) - 1 \geq 0,\\ &\xi_i \geq 0, \end{aligned}$

分類手順は以前と同じように続行されます。ここでハイパーパラメータ

$C$ 正則化の強さに責任があります。つまり、境界を尊重するためにポイントがどれだけ厳密に要求されるかを決定します。

$C$ - もっと

$\xi_i$ 消え、より少ないポイントが境界に違反します。この場合のサポートベクターは、

$\xi_i > 0$ ..。

しかし、トレーニングセットがザ・フーのロゴに似ていて、ドットを直線で区切ることができない場合はどうなるでしょうか。

ここでは、独創的な手法であるカーネルトリック [4]によって支援されます。ただし、それを適用するには、いわゆる双対（または双対）ラグランジュ問題に合格する必要があります。詳細な説明は、ウィキペディア [5]またはコースの6番目の講義 [3]にあります。新しい問題が解決される変数は、デュアルまたは ラグランジュ乗数と呼ばれます ..。双対問題は、多くの場合、元の問題よりも単純であり、優れた追加のプロパティがあります。たとえば、元の問題が非凸である場合でも、凹型です。その解は元の問題の解（双対性の破れ）と常に一致するとは限りませんが、特定の条件下でそのような一致（強双対性）を保証する定理がいくつかあります。そしてこれは私たちの場合だけなので、双対問題に安全に進むことができます

$\begin{aligned} &\max_{\lambda} \sum_{i=1}^n \lambda_i - \frac12 \sum_{i=1}^n \sum_{j=1}^n y_i y_j (\boldsymbol{x}_i \cdot \boldsymbol{x}_j) \lambda_i \lambda_j,\\ \text{subject to: } &0 \leq \lambda_i \leq C, \quad \mbox{ for } i=1, 2, \ldots, n,\\ &\sum_{i=1}^n y_i \lambda_i = 0, \end{aligned}$

どこ

$\lambda_i$ -双対変数。最大化問題を解いた後、パラメータを計算することも必要です

$b$ 、双対問題には含まれていませんが、分類器には必要です

$b = \mathbb{E}_{k,\xi_k \neq 0}\left[y_k - \sum_i \lambda_i y_i (\boldsymbol{x}_i \cdot \boldsymbol{x}_k)\right].$

分類器は、双対変数の観点から書き直すことができます（そして書き直す必要があります）。

$\text{class}(\boldsymbol{x}) = \text{sign}(f(\boldsymbol{x})),\quad f(\boldsymbol{x}) = \sum_i \lambda_i y_i (\boldsymbol{x}_i \cdot \boldsymbol{x}) + b.$

この録音の利点は何ですか？トレーニングセットのすべてのベクトルは、ドット積の形式でのみここに含まれていることに注意してください

$(\boldsymbol{x}_i \cdot \boldsymbol{x}_j)$ ..。最初にポイントを高次元空間のサーフェスにマッピングしてから、新しい空間の画像の内積を計算することができます。なぜこれが図からわかるのでしょうか。

マッピングが成功すると、ポイントの画像は超平面で区切られます。実際、すべてがさらに優れています。ドット積のみに関心があり、ポイントの特定の座標には関心がないため、表示する必要はありません。したがって、内積を関数に置き換えることで、手順全体をエミュレートできます。

$K(\boldsymbol{x}_i; \boldsymbol{x}_j)$ 、コアと呼ばれます。もちろん、すべての関数がカーネルになるわけではありません-少なくとも仮説的には、マッピングが必要です

$\varphi$ そのような

$K(\boldsymbol{x}_i; \boldsymbol{x}_j)=(\varphi(\boldsymbol{x}_i) \cdot \varphi(\boldsymbol{x}_j))$ ..。必要な条件はマーサーの定理[6]によって決定されます。Pythonの実装は線形を表します（

$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = \boldsymbol{x}_i^T \boldsymbol{x}_j$ ）、多項式（

$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = (\boldsymbol{x}_i^T \boldsymbol{x}_j)^d$ ）カーネルと動径基底関数のカーネル（

$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = e^{-\gamma |\boldsymbol{x}_i - \boldsymbol{x}_j|^2}$ ）。例からわかるように、カーネルは特定のハイパーパラメータをアルゴリズムに導入できます。これは、その動作にも影響します。

じょうごの形をしたゴムフィルムを伸ばした例を使って重力の作用を説明するビデオを見たことがあるかもしれません [7]。これが機能するのは、高次元空間での曲面上の点の動きは、重要なメトリックを提供する場合、低次元空間でのその画像の動きと同等であるためです。実際、コアは空間を曲げます。

SMOアルゴリズム

ですから、私たちは目標に向かっています。前のセクションで提起された二重の問題を解決することは残っています。

$\def\M{{\color{red}M}} \def\L{{\color{blue}L}} \begin{aligned} &\max_{\lambda} \sum_{i=1}^n \lambda_i - \frac12 \sum_{i=1}^n \sum_{j=1}^n y_i y_j K(\boldsymbol{x}_i; \boldsymbol{x}_j) \lambda_i \lambda_j,\\ \text{subject to: } &0 \leq \lambda_i \leq C, \quad \mbox{ for } i=1, 2, \ldots, n,\\ &\sum_{i=1}^n y_i \lambda_i = 0, \end{aligned}$

次に、パラメータを見つけます

$b = \mathbb{E}_{k,\xi_k \neq 0}[y_k - \sum_i \lambda_i y_i K(\boldsymbol{x}_i; \boldsymbol{x}_k)], \tag{1}$

分類器は次の形式になります

$\text{class}(\boldsymbol{x}) = \text{sign}(f(\boldsymbol{x})),\quad f(\boldsymbol{x}) = \sum_i \lambda_i y_i K(\boldsymbol{x}_i; \boldsymbol{x}) + b. \tag{2}$

双対問題を解くためのSMO（逐次最小最適化[8]）アルゴリズムは次のとおりです。ループでは、複雑なヒューリスティック（[9]）を使用して、双対変数のペアが選択されます

$\lambda_\M$ そして

$\lambda_\L$ 、そして、目的関数は、合計が一定であるという条件で、それらに対して最小化されます。

$インライン$ y_ \ M \ lambda_ \ M + y_ \ L \ lambda_ \ L $インライン$

$y_\M\lambda_\M + y_\L\lambda_\L$ および制限

$0 \leq \lambda_\M \leq C$ 、

$0 \leq \lambda_\L \leq C$ （境界線の硬さを設定します）。合計条件は、すべての合計を格納します

$y_i\lambda_i$ 変更されていません（結局のところ、残りのラムダには触れませんでした）。アルゴリズムは、いわゆるKKT条件の十分な遵守を検出すると停止します（Karush-Kuna-Tucker [10]）。

いくつか簡単にします。

インデックス選択の複雑なヒューリスティックを破棄し（これはスタンフォード大学のコース[11]で行われます）、一方のインデックスを反復処理し、もう一方をランダムに選択します。
CCPの確認を拒否し、事前に所定の回数の反復を実行します。
最適化手順自体では、古典的な研究[9]やスタンフォードアプローチ[11]とは対照的に、直線のベクトル方程式を使用します。これにより、計算が大幅に簡素化されます（[12]と[13]のボリュームを比較してください）。

詳細はこちら。トレーニングサンプルからの情報は、マトリックスの形式で書き込むことができます

$\boldsymbol{K} = \begin{pmatrix} y_1 y_1 K(\boldsymbol{x}_1; \boldsymbol{x}_1) & y_1 y_2 K(\boldsymbol{x}_1; \boldsymbol{x}_2) & \dots & y_1 y_N K(\boldsymbol{x}_1; \boldsymbol{x}_N) \\ y_2 y_1 K(\boldsymbol{x}_2; \boldsymbol{x}_1) & y_2 y_2 K(\boldsymbol{x}_2; \boldsymbol{x}_2) & \dots & y_2 y_N K(\boldsymbol{x}_2; \boldsymbol{x}_N) \\ \cdots & \cdots & \cdots & \cdots \\ y_N y_1 K(\boldsymbol{x}_N; \boldsymbol{x}_1) & y_N y_2 K(\boldsymbol{x}_N; \boldsymbol{x}_2) & \dots & y_N y_N K(\boldsymbol{x}_N; \boldsymbol{x}_N) \\ \end{pmatrix}. \tag{3}$

以下では、2つのインデックスを持つ表記を使用します（

$\boldsymbol{K}_{i,j}$ ）行列の要素を参照し、1つのインデックス（

$\boldsymbol{K}_{k}$ ）行列の列ベクトルを示します。双対変数を列ベクトルに収集します

$\boldsymbol{\lambda}$ ..。私たちは興味があります

$\max_{\boldsymbol{\lambda}} \underbrace{ \sum_{i=1}^n \lambda_i - \frac12 \boldsymbol{\lambda}^T \boldsymbol{K} \boldsymbol{\lambda} }_{\mathscr{L}}.$

現在の反復で、インデックスによって目的関数を最大化するとします。

$\L$ そして

$\M$ ..。導関数を取るので、インデックスを含む用語を選択すると便利です

$\L$ そして

$\M$ ..。量のある部分でやるのは簡単です

$\lambda_i$ 、ただし、2次形式にはいくつかの変換が必要です。

計算するとき

$\boldsymbol{\lambda}^T \boldsymbol{K} \boldsymbol{\lambda}$ 合計は2つのインデックスに対して実行されます。

$i$ そして

$j$ ..。を含むインデックスのペアを強調表示

$\L$ または

$\M$ ..。

含まれていないものをすべて組み合わせて問題を書き直してみましょう

$\lambda_\L$ または

$\lambda_\M$ ..。インデックスの追跡を容易にするために、次のことに注意してください。

$\boldsymbol{K}$ 画像で。

$$$ display $$ \ begin {aligned} \ mathscr {L}＆= \ lambda_ \ M + \ lambda_ \ L- \ sum_ {j} \ lambda_ \ M \ lambda_j K _ {\ M、j}-\ sum_ { i} \ lambda_ \ L \ lambda_i K _ {\ L、i} + \ text {const} + \\ {\ text {compensation} \ atop \ text {double count}} \ rightarrow \ qquad＆+ \ frac {1 } {2} \ lambda_ \ M ^ 2 K _ {\ M、\ M} + \ lambda_ \ M \ lambda_ \ LK _ {\ M、\ L} + \ frac {1} {2} \ lambda_ \ L ^ 2 K_ {\ L、\ L} = \\＆= \ lambda_ \ M \ left（1- \ sum_ {j} \ lambda_j K _ {\ M、j} \ right）+ \ lambda_ \ L \ left（1 -\ sum_ {i} \ lambda_i K _ {\ L、i} \ right）+ \\＆+ \ frac {1} {2} \ left（\ lambda_ \ M ^ 2 K _ {\ M、\ M} + 2 \ lambda_ \ M \ lambda_ \ LK _ {\ M、\ L} + \ lambda_ \ L ^ 2 K _ {\ L、\ L} \ right）+ \ text {const} = \\＆= \ boldsymbol {k} ^ T_0 \ boldsymbol {v} _0 + \ frac {1} {2} \ boldsymbol {v} ^ {\、T} _0 \、\ boldsymbol {Q} \、\ boldsymbol {v} _0 + \ text {const}、\ end {aligned} $$ display $$$

$\begin{aligned} \mathscr{L} &= \lambda_\M + \lambda_\L - \sum_{j} \lambda_\M \lambda_j K_{\M,j} - \sum_{i} \lambda_\L \lambda_i K_{\L,i} + \text{const} + \\ {\text{}\atop\text{ }} \rightarrow\qquad &+ \frac{1}{2}\lambda_\M^2 K_{\M,\M} + \lambda_\M \lambda_\L K_{\M,\L} + \frac{1}{2}\lambda_\L^2 K_{\L,\L} = \\ &= \lambda_\M \left(1-\sum_{j} \lambda_j K_{\M,j}\right) + \lambda_\L \left(1-\sum_{i} \lambda_i K_{\L,i}\right)+\\ &+\frac{1}{2}\left(\lambda_\M^2 K_{\M,\M} + 2 \lambda_\M \lambda_\L K_{\M,\L}+\lambda_\L^2 K_{\L,\L} \right) + \text{const} = \\ &=\boldsymbol{k}^T_0 \boldsymbol{v}_0 + \frac{1}{2}\boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const}, \end{aligned}$

どこ

$\text{const}$ 独立した用語を示します

$\lambda_\L$ または

$\lambda_\M$ ..。最後の行では、表記を使用しました

$$$ display $$ \ begin {align} \ boldsymbol {v} _0＆=（\ lambda_ \ M、\ lambda_ \ L）^ T、\ tag {4a} \\ \ boldsymbol {k} _0＆= \ left（ 1- \ boldsymbol {\ lambda} ^ T \ boldsymbol {K} _ {\ M}、1- \ boldsymbol {\ lambda} ^ T \ boldsymbol {K} _ {\ L} \ right）^ T、\ tag { 4b} \\ \ boldsymbol {Q}＆= \ begin {pmatrix} K _ {\ M、\ M}＆K _ {\ M、\ L} \\ K _ {\ L、\ M}＆K _ { \ L、\ L} \\ \ end {pmatrix}、\ tag {4c} \\ \ boldsymbol {u}＆=（-y_ \ L、y_ \ M）^ T。 \ tag {4d} \ end {align} $$ display $$$

$\begin{align} \boldsymbol{v}_0 &= (\lambda_\M, \lambda_\L)^T, \tag{4a}\\ \boldsymbol{k}_0 &= \left(1 - \boldsymbol{\lambda}^T\boldsymbol{K}_{\M}, 1 - \boldsymbol{\lambda}^T\boldsymbol{K}_{\L}\right)^T, \tag{4b}\\ \boldsymbol{Q} &= \begin{pmatrix} K_{\M,\M} & K_{\M,\L} \\ K_{\L,\M} & K_{\L,\L} \\ \end{pmatrix},\tag{4c}\\ \boldsymbol{u} &= (-y_\L, y_\M)^T. \tag{4d} \end{align}$

ご了承ください

$\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0$ に依存しません

$\lambda_\L$ からも

$\lambda_\M$

$$$ display $$ \ boldsymbol {k} _0 = \ begin {pmatrix} 1- \ lambda_ \ M K _ {\ M、\ M}-\ lambda_ \ L K _ {\ M、\ L}-\ sum_ {i \ neq \ M、\ L} \ lambda_i K _ {\ M、i} \\ 1- \ lambda_ \ MK _ {\ L、\ M}-\ lambda_ \ LK _ {\ L、\ L}-\ sum_ { i \ neq \ M、\ L} \ lambda_i K _ {\ L、i} \\ \ end {pmatrix} = \ begin {pmatrix} 1- \ sum_ {i \ neq \ M、\ L} \ lambda_i K _ {\ M、i} \\ 1- \ sum_ {i \ neq \ M、\ L} \ lambda_i K _ {\ L、i} \\ \ end {pmatrix}-\ boldsymbol {Q} \ boldsymbol {v} _0。 $$ディスプレイ$$$

$\boldsymbol{k}_0 = \begin{pmatrix} 1 - \lambda_\M K_{\M,\M} - \lambda_\L K_{\M,\L} - \sum_{i \neq \M,\L} \lambda_i K_{\M,i}\\ 1 - \lambda_\M K_{\L,\M} - \lambda_\L K_{\L,\L} - \sum_{i \neq \M,\L} \lambda_i K_{\L,i}\\ \end{pmatrix} = \begin{pmatrix} 1 - \sum_{i \neq \M,\L} \lambda_i K_{\M,i}\\ 1 - \sum_{i \neq \M,\L} \lambda_i K_{\L,i}\\ \end{pmatrix} - \boldsymbol{Q} \boldsymbol{v}_0.$

カーネルは対称的であるため、

$\boldsymbol{Q}^T = \boldsymbol{Q}$ そしてあなたは書くことができます

$\mathscr{L} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0 - \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}_0 + \frac{1}{2}\boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}_0 - \frac{1}{2} \boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const}$

最大化を実行して、

$インライン$ y_ \ L \ lambda_ \ L + y_ \ M \ lambda_ \ M $インライン$

$y_\L\lambda_\L + y_\M\lambda_\M$ 一定のままでした。このため、新しい値は直線上にある必要があります

$$$ display $$（\ lambda_ \ M ^ \ text {new}、\ lambda_ \ L ^ \ text {new}）^ T = \ boldsymbol {v}（t）= \ boldsymbol {v} _0 + t \ boldsymbol {u}。 $$ディスプレイ$$$

$(\lambda_\M^\text{new}, \lambda_\L^\text{new})^T = \boldsymbol{v}(t) = \boldsymbol{v}_0 + t \boldsymbol{u}.$

誰にとってもそれを確認するのは簡単です

$t$

$$$表示$$ y_ \ M \ lambda_ \ M ^ \ text {new} + y_ \ L \ lambda_ \ L ^ \ text {new} = y_ \ M \ lambda_ \ M + y_ \ L \ lambda_ \ L + t （-y_ \ M y_ \ L + y_ \ L y_ \ M）= y_ \ M \ lambda_ \ M + y_ \ L \ lambda_ \ L。 $$ディスプレイ$$$

$y_\M\lambda_\M^\text{new} + y_\L\lambda_\L^\text{new} = y_\M \lambda_\M + y_\L \lambda_\L + t (-y_\M y_\L + y_\L y_\M) = y_\M\lambda_\M + y_\L\lambda_\L.$

この場合、最大化する必要があります

$\mathscr{L}(t) = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}(t) - \frac12 \boldsymbol{v}^{\,T}(t) \, \boldsymbol{Q} \, \boldsymbol{v}(t) + \text{const},$

導関数を取ることで簡単にできます

$\begin{align} \frac{d \mathscr{L}(t)}{d t} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \frac{d \boldsymbol{v}}{dt} &- \frac12 \left(\frac{d(\boldsymbol{v}^{\,T} \, \boldsymbol{Q} \, \boldsymbol{v})}{d \boldsymbol{v}}\right)^T \frac{d\boldsymbol{v}}{d t} =\\ &= \boldsymbol{k}_0^T \boldsymbol{u} + \underbrace{\boldsymbol{v}_0^T \boldsymbol{Q}^T \boldsymbol{u} - \boldsymbol{v}^T \boldsymbol{Q}^T \boldsymbol{u}}_{(\boldsymbol{v}_0^T - \boldsymbol{v}^T)\boldsymbol{Q} \boldsymbol{u}} = \boldsymbol{k}_0^T \boldsymbol{u} - t \boldsymbol{u}^T \boldsymbol{Q} \boldsymbol{u}. \end{align}$

導関数をゼロに等しくすると、次のようになります。

$t_* = \frac{\boldsymbol{k}^T_0 \boldsymbol{u}}{\boldsymbol{u}^{\,T} \boldsymbol{Q} \boldsymbol{u}}. \tag{5}$

そしてもう1つ、写真のように、必要以上に登って広場の外に出てしまうかもしれません。次に、一歩下がって国境に戻る必要があります

$$$ display $$（\ lambda_ \ M ^ \ text {new}、\ lambda_ \ L ^ \ text {new}）= \ boldsymbol {v} _0 + t _ * ^ {\ text {restr}} \ boldsymbol { u}。 $$ディスプレイ$$$

$(\lambda_\M^\text{new}, \lambda_\L^\text{new}) = \boldsymbol{v}_0 + t_*^{\text{restr}} \boldsymbol{u}.$

これで反復が完了し、新しいインデックスが選択されます。

実装

簡略化されたサポートベクターマシンのトレーニングの概略図は、次のように記述できます。

実際のプログラミング言語のコードを見てみましょう。記事のコードが気に入らない場合は、github [14]で調べることができます。

簡略化されたサポートベクターマシンのソースコード

import numpy as np

class SVM:
  def __init__(self, kernel='linear', C=10000.0, max_iter=100000, degree=3, gamma=1):
    self.kernel = {'poly'  : lambda x,y: np.dot(x, y.T)**degree,
         'rbf': lambda x,y: np.exp(-gamma*np.sum((y-x[:,np.newaxis])**2,axis=-1)),
         'linear': lambda x,y: np.dot(x, y.T)}[kernel]
    self.C = C
    self.max_iter = max_iter

  #   t,       
  def restrict_to_square(self, t, v0, u): 
    t = (np.clip(v0 + t*u, 0, self.C) - v0)[1]/u[1]
    return (np.clip(v0 + t*u, 0, self.C) - v0)[0]/u[0]

  def fit(self, X, y):
    self.X = X.copy()
    #   0,1  -1,+1;     sklearn
    self.y = y * 2 - 1 
    self.lambdas = np.zeros_like(self.y, dtype=float)
    #  (3)
    self.K = self.kernel(self.X, self.X) * self.y[:,np.newaxis] * self.y
    
    #  self.max_iter 
    for _ in range(self.max_iter):
      #     
      for idxM in range(len(self.lambdas)):                                    
        # idxL  
        idxL = np.random.randint(0, len(self.lambdas))                         
        #  (4)
        Q = self.K[[[idxM, idxM], [idxL, idxL]], [[idxM, idxL], [idxM, idxL]]] 
        #  (4a)
        v0 = self.lambdas[[idxM, idxL]]                                        
        #  (4b)
        k0 = 1 - np.sum(self.lambdas * self.K[[idxM, idxL]], axis=1)           
        #  (4d)
        u = np.array([-self.y[idxL], self.y[idxM]])                            
        #   (5),    idxM = idxL
        t_max = np.dot(k0, u) / (np.dot(np.dot(Q, u), u) + 1E-15) 
        self.lambdas[[idxM, idxL]] = v0 + u * self.restrict_to_square(t_max, v0, u)
    
    #    
    idx, = np.nonzero(self.lambdas > 1E-15) 
    #  (1)
    self.b = np.mean((1.0-np.sum(self.K[idx]*self.lambdas, axis=1))*self.y[idx]) 
  
  def decision_function(self, X):
    return np.sum(self.kernel(X, self.X) * self.y * self.lambdas, axis=1) + self.b

  def predict(self, X): 
    #   -1,+1  0,1;     sklearn
    return (np.sign(self.decision_function(X)) + 1) // 2

SVMクラスのオブジェクトを作成するときに、ハイパーパラメータを指定できます。トレーニングはfit関数を呼び出すことによって行われます。クラスは、次のように指定する必要があります。

$0$ そして

$1$ （内部的に変換されます

$-1$ そして

$+1$ 、sklearnとの互換性を高めるために作成された）、特徴ベクトルの次元は任意に許可されます。予測関数は分類に使用されます。

sklearn.svm.SVCとの比較

学生を教えることだけを目的として開発された非常に単純化されたアルゴリズムについて話しているので、この比較はあまり意味がありませんが、それでもなおです。テストするために（そしてそれをすべて使用する方法を確認するために）、次のことを行うことができます（このコードはgithub [14]でも入手できます）。

単純な2Dデータセットでのsklearn.svm.SVCとの比較

from sklearn.svm import SVC
import matplotlib.pyplot as plt
import seaborn as sns; sns.set()
from sklearn.datasets import make_blobs, make_circles
from matplotlib.colors import ListedColormap

def test_plot(X, y, svm_model, axes, title):
  plt.axes(axes)
  xlim = [np.min(X[:, 0]), np.max(X[:, 0])]
  ylim = [np.min(X[:, 1]), np.max(X[:, 1])]
  xx, yy = np.meshgrid(np.linspace(*xlim, num=700), np.linspace(*ylim, num=700))
  rgb=np.array([[210, 0, 0], [0, 0, 150]])/255.0
  
  svm_model.fit(X, y)
  z_model = svm_model.decision_function(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
  
  plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')
  plt.contour(xx, yy, z_model, colors='k', levels=[-1, 0, 1], alpha=0.5, linestyles=['--', '-', '--'])
  plt.contourf(xx, yy, np.sign(z_model.reshape(xx.shape)), alpha=0.3, levels=2, cmap=ListedColormap(rgb), zorder=1)
  plt.title(title)

X, y = make_circles(100, factor=.1, noise=.1)
fig, axs = plt.subplots(nrows=1,ncols=2,figsize=(12,4))
test_plot(X, y, SVM(kernel='rbf', C=10, max_iter=60, gamma=1), axs[0], 'OUR ALGORITHM')
test_plot(X, y, SVC(kernel='rbf', C=10, gamma=1), axs[1], 'sklearn.svm.SVC')

X, y = make_blobs(n_samples=50, centers=2, random_state=0, cluster_std=1.4)
fig, axs = plt.subplots(nrows=1,ncols=2,figsize=(12,4))
test_plot(X, y, SVM(kernel='linear', C=10, max_iter=60), axs[0], 'OUR ALGORITHM')
test_plot(X, y, SVC(kernel='linear', C=10), axs[1], 'sklearn.svm.SVC')

fig, axs = plt.subplots(nrows=1,ncols=2,figsize=(12,4))
test_plot(X, y, SVM(kernel='poly', C=5, max_iter=60, degree=3), axs[0], 'OUR ALGORITHM')
test_plot(X, y, SVC(kernel='poly', C=5, degree=3), axs[1], 'sklearn.svm.SVC')

起動後、画像が生成されますが、アルゴリズムがランダム化されているため、起動ごとにわずかに異なります。簡略化されたアルゴリズムがどのように機能するかの例を次に示します（左から右へ：線形、多項式、およびrbfカーネル）

そして、これはサポートベクターマシンの産業用バージョンの結果です。

寸法の場合

$2$ 小さすぎるようですが、MNISTでテストできます

MNISTの2つのクラスでのsklearn.svm.SVCとの比較

from sklearn import datasets, svm
from sklearn.model_selection import train_test_split
from sklearn.metrics import confusion_matrix
import matplotlib.pyplot as plt
import seaborn as sns

class_A = 3
class_B = 8

digits = datasets.load_digits()
mask = (digits.target == class_A) | (digits.target == class_B)
data = digits.images.reshape((len(digits.images), -1))[mask]
target = digits.target[mask] // max([class_A, class_B]) # rescale to 0,1
X_train, X_test, y_train, y_test = train_test_split(data, target, test_size=0.5, shuffle=True)

def plot_confusion(clf):
  clf.fit(X_train, y_train)
  y_fit = clf.predict(X_test)

  mat = confusion_matrix(y_test, y_fit)
  sns.heatmap(mat.T, square=True, annot=True, fmt='d', cbar=False, xticklabels=[class_A,class_B], yticklabels=[class_A,class_B])
  plt.xlabel('true label')
  plt.ylabel('predicted label');
  plt.show()

print('sklearn:')
plot_confusion(svm.SVC(C=1.0, kernel='rbf', gamma=0.001))
print('custom svm:')
plot_confusion(SVM(kernel='rbf', C=1.0, max_iter=60, gamma=0.001))

MNISTの場合、クラスのランダムなペアをいくつか試しましたが（簡略化されたアルゴリズムはバイナリ分類のみをサポートします）、簡略化されたアルゴリズムとsklearnの作業に違いは見つかりませんでした。次の混同行列は、品質のアイデアを提供します。

結論

最後まで読んでくださった皆様、ありがとうございました。この記事では、サポートベクターマシンの簡略化されたチュートリアル実装について説明しました。もちろん、工業デザインと競合することはできませんが、Pythonの非常にシンプルでコンパクトなコード、およびSMOの基本的な考え方がすべて保持されているため、このバージョンのSVMは教室。このアルゴリズムは、非常にトリッキーなアルゴリズム[9]だけでなく、スタンフォード大学の簡略化されたバージョン [11]よりも単純であることに注意してください。結局のところ、30行のサポートベクターマシンは美しいです。

参考文献一覧

https://fbeilstein.github.io/simplest_smo_ever/
http://www.machinelearning.ruのページ
「機械学習の始まり」、KAU
https://en.wikipedia.org/wiki/Kernel_method
https://en.wikipedia.org/wiki/Duality_(optimization)
http://www.machinelearning.ru
https://www.youtube.com/watch?v=MTY1Kje0yLg
https://en.wikipedia.org/wiki/Sequential_minimal_optimization
Platt, John. Fast Training of Support Vector Machines using Sequential Minimal Optimization, in Advances in Kernel Methods – Support Vector Learning, B. Scholkopf, C. Burges, A. Smola, eds., MIT Press (1998).
https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
http://cs229.stanford.edu/materials/smo.pdf
https://www.researchgate.net/publication/344460740_Yet_more_simple_SMO_algorithm
http://fourier.eng.hmc.edu/e176/lectures/ch9/node9.html
https://github.com/fbeilstein/simplest_smo_ever

サポートベクターマシン、30行

コンテンツ

SMOアルゴリズム

実装

sklearn.svm.SVCとの比較

結論

参考文献一覧

More articles: