🏏 🦓 🕠 Mendukung Mesin Vektor, 30 baris 🌜 👨🏽‍🏭 💋

Pada artikel ini saya akan menunjukkan kepada Anda cara menulis mesin vektor dukungan yang sangat sederhana tanpa scikit-learn atau pustaka lain dengan implementasi siap pakai hanya dalam 30 baris dengan Python. Jika Anda ingin memahami algoritma SMO, tetapi sepertinya terlalu rumit, maka artikel ini mungkin bermanfaat bagi Anda.

Tidak mungkin untuk menjelaskan apa itu mesin vektor dukungan ~~Matriks~~ ... Anda harus melihatnya sendiri.

Setelah mengetahui bahwa Habré memiliki kemampuan untuk memasukkan elemen media, saya membuat demo kecil (jika tiba-tiba tidak berhasil, Anda masih dapat mencoba keberuntungan Anda dengan versi di github [1] ). Tempatkan di pesawat (ruang dua fitur

$X$ dan

$Y$ ) beberapa titik merah dan biru (ini adalah kumpulan data kami) dan mesin akan melakukan klasifikasi (setiap titik latar belakang dicat tergantung di mana permintaan terkait akan diklasifikasikan). Pindahkan poin, ubah kernel (saya sarankan Anda untuk mencoba Fungsi Dasar Radial) dan kekerasan batas (konstan

$C$ ). Saya minta maaf atas kode yang mengerikan di JS - saya menulis di dalamnya hanya beberapa kali dalam hidup saya, untuk memahami algoritme, gunakan kode Python nanti di artikel.

Kandungan

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

Support Vector Machine adalah metode pembelajaran mesin (supervised learning) untuk menyelesaikan masalah klasifikasi, regresi, deteksi anomali, dll. Kami akan mempertimbangkannya menggunakan contoh masalah klasifikasi biner. Sampel pelatihan kami adalah sekumpulan vektor fitur

$\boldsymbol{x}_i$ diklasifikasikan menjadi salah satu dari dua kelas

$y_i = \pm 1$ ... Permintaan Klasifikasi - Vektor

$\boldsymbol{x}$ ke mana kita harus menetapkan kelas

$+1$ atau

$-1$ ...

Dalam kasus yang paling sederhana, kelas sampel pelatihan dapat dibagi dengan hanya menggambar satu garis lurus seperti pada gambar (untuk sejumlah besar fitur, ini akan menjadi bidang-hiper). Sekarang, ketika sebuah permintaan datang untuk mengklasifikasikan beberapa poin

$\boldsymbol{x}$ , masuk akal untuk menempatkannya di kelas di sisi yang mana.

Bagaimana cara memilih garis lurus terbaik? Secara intuitif, saya ingin garis lurus lewat di tengah-tengah antar kelas. Untuk melakukan ini, tulis persamaan garis lurus sebagai

$\boldsymbol{x} \cdot \boldsymbol{w} + b = 0$ dan menskalakan parameter sehingga titik set data yang paling dekat dengan garis lurus memenuhi

$\boldsymbol{x} \cdot \boldsymbol{w} + b = \pm 1$ (plus atau minus, tergantung kelasnya) - titik-titik ini disebut vektor pendukung .

Dalam hal ini, jarak antara titik batas kelas adalah

$2/|\boldsymbol{w}|$ ... Jelas, kami ingin memaksimalkan nilai ini untuk memisahkan kelas sebaik mungkin. Yang terakhir ini setara dengan meminimalkan

$\frac{1}{2} |\boldsymbol{w}|^2$ , seluruh masalah pengoptimalan telah ditulis

$\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}$

Jika Anda menyelesaikannya, maka klasifikasi berdasarkan permintaan

$\boldsymbol{x}$ diproduksi seperti ini

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

Ini adalah mesin vektor dukungan paling sederhana.

Dan apa yang harus dilakukan jika titik-titik dari kelas yang berbeda saling menembus seperti pada gambar?

Kami tidak dapat lagi menyelesaikan masalah pengoptimalan sebelumnya - tidak ada parameter yang memenuhi kondisi tersebut. Maka dimungkinkan untuk membiarkan poin melanggar batas dengan jumlah

$\xi_i \geq 0$ , tetapi juga diharapkan agar pelanggar seperti itu sesedikit mungkin. Ini dapat dicapai dengan memodifikasi fungsi tujuan dengan istilah tambahan (regularisasi

$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}$

dan prosedur klasifikasi akan berlanjut seperti sebelumnya. Di sini hyperparameter

$C$ bertanggung jawab atas kekuatan regularisasi, yaitu menentukan seberapa ketat kami memerlukan poin untuk menghormati batas: semakin

$C$ - lebih

$\xi_i$ akan lenyap dan poin yang lebih sedikit akan melanggar batas. Vektor pendukung dalam hal ini adalah titik-titiknya

$\xi_i > 0$ ...

Tetapi bagaimana jika set pelatihan menyerupai logo The Who dan titik-titiknya tidak pernah dapat dipisahkan oleh garis lurus?

Di sini kita akan dibantu oleh teknik yang cerdik - trik kernel [4] . Namun, untuk menerapkannya, seseorang harus meneruskan ke apa yang disebut masalah Lagrange ganda (atau ganda ). Penjelasan rinci tentang hal itu dapat ditemukan di Wikipedia [5] atau di kuliah keenam kursus [3] . Variabel di mana masalah baru diselesaikan disebut pengali ganda atau Lagrange... Masalah ganda sering kali lebih sederhana daripada masalah asli dan memiliki sifat tambahan yang baik, misalnya, masalah cekung meskipun masalah aslinya bukan cembung. Meskipun solusinya tidak selalu sesuai dengan solusi dari masalah aslinya (dualitas putus), ada sejumlah teorema yang, dalam kondisi tertentu, menjamin kebetulan seperti itu (dualitas kuat). Dan ini hanya kasus kami, jadi Anda dapat dengan aman menuju ke masalah ganda

$\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}$

Dimana

$\lambda_i$ - variabel ganda. Setelah menyelesaikan masalah maksimalisasi, perlu juga dihitung parameternya

$b$ , yang tidak termasuk dalam masalah ganda, tetapi dibutuhkan untuk pengklasifikasi

$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].$

Pengklasifikasi dapat (dan harus) ditulis ulang dalam istilah variabel ganda

$\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.$

Apa keuntungan dari rekaman ini? Harap dicatat bahwa semua vektor dari set pelatihan disertakan di sini secara eksklusif dalam bentuk produk titik

$(\boldsymbol{x}_i \cdot \boldsymbol{x}_j)$ ... Pertama-tama Anda dapat memetakan titik-titik ke permukaan di ruang berdimensi lebih tinggi, dan baru kemudian menghitung produk titik dari gambar di ruang baru. Mengapa ini bisa dilihat dari gambar.

Jika pemetaan berhasil, gambar dari titik-titik tersebut dipisahkan oleh hyperplane! Faktanya, semuanya bahkan lebih baik: tidak perlu menampilkan, karena kami hanya tertarik pada perkalian titik, dan bukan pada koordinat spesifik dari titik-titik tersebut. Jadi keseluruhan prosedur dapat ditiru dengan mengganti perkalian titik dengan fungsinya

$K(\boldsymbol{x}_i; \boldsymbol{x}_j)$ , yang disebut inti . Tentu saja, tidak setiap fungsi bisa menjadi kernel - setidaknya secara hipotetis, harus ada pemetaan

$\varphi$ seperti yang

$K(\boldsymbol{x}_i; \boldsymbol{x}_j)=(\varphi(\boldsymbol{x}_i) \cdot \varphi(\boldsymbol{x}_j))$ ... Kondisi yang diperlukan ditentukan oleh teorema Mercer [6] . Implementasi Python akan mewakili linier (

$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = \boldsymbol{x}_i^T \boldsymbol{x}_j$ ), polinomial (

$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = (\boldsymbol{x}_i^T \boldsymbol{x}_j)^d$ ) kernel dan kernel fungsi basis radial (

$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = e^{-\gamma |\boldsymbol{x}_i - \boldsymbol{x}_j|^2}$ ). Seperti yang Anda lihat dari contoh, kernel dapat memasukkan hyperparameter spesifiknya ke dalam algoritme, yang juga akan memengaruhi operasinya.

Anda mungkin pernah melihat video di mana aksi gravitasi dijelaskan menggunakan contoh film karet yang diregangkan dalam bentuk corong [7] . Ini berfungsi, karena pergerakan titik pada permukaan lengkung di ruang berdimensi tinggi setara dengan pergerakan bayangannya di ruang berdimensi lebih rendah, jika Anda memberikannya metrik nontrivial. Faktanya, inti membengkokkan ruang.

Algoritma SMO

Jadi, kami berada di tujuan, tetap menyelesaikan masalah ganda yang diajukan di bagian sebelumnya

$\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}$

kemudian temukan parameternya

$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}$

dan pengklasifikasi akan berbentuk seperti berikut

$\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}$

Algoritma SMO (Sequential minimal optimization, [8] ) untuk memecahkan masalah ganda adalah sebagai berikut. Dalam loop, menggunakan heuristik kompleks ( [9] ), sepasang variabel ganda dipilih

$\lambda_\M$ dan

$\lambda_\L$ , dan kemudian fungsi tujuan diminimalkan di atasnya, dengan kondisi keteguhan jumlah

$ sebaris $ y_ \ M \ lambda_ \ M + y_ \ L \ lambda_ \ L $ sebaris $

$y_\M\lambda_\M + y_\L\lambda_\L$ dan pembatasan

$0 \leq \lambda_\M \leq C$ ,

$0 \leq \lambda_\L \leq C$ (mengatur kekerasan perbatasan). Kondisi penjumlahan menyimpan jumlah semua

$y_i\lambda_i$ tidak berubah (setelah semua, kami tidak menyentuh lambda lainnya). Algoritma berhenti ketika mendeteksi ketaatan yang cukup baik dari apa yang disebut kondisi KKT (Karush-Kuna-Tucker [10] ).

Saya akan membuat beberapa penyederhanaan.

Saya akan membuang heuristik kompleks pemilihan indeks (ini dilakukan dalam kursus Universitas Stanford [11] ) dan akan mengulang satu indeks, dan memilih indeks lainnya secara acak.
Saya akan menolak untuk memeriksa PKC dan akan melakukan sejumlah pengulangan yang telah ditentukan sebelumnya.
Dalam prosedur optimasi itu sendiri, berbeda dengan karya klasik [9] atau pendekatan Stanford [11] , saya akan menggunakan persamaan vektor dari sebuah garis lurus. Ini akan sangat menyederhanakan penghitungan (bandingkan volume [12] dan [13] ).

Sekarang untuk detailnya. Informasi dari sampel pelatihan dapat ditulis dalam bentuk matriks

$\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}$

Berikut ini, saya akan menggunakan notasi dengan dua indeks (

$\boldsymbol{K}_{i,j}$ ) untuk merujuk ke elemen matriks dan dengan satu indeks (

$\boldsymbol{K}_{k}$ ) untuk menunjukkan vektor kolom dari matriks. Kumpulkan variabel ganda menjadi vektor kolom

$\boldsymbol{\lambda}$ ... Kami tertarik

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

Misalkan, pada iterasi saat ini, kami ingin memaksimalkan fungsi tujuan dengan indeks

$\L$ dan

$\M$ ... Kami akan mengambil derivatif, jadi akan lebih mudah untuk memilih istilah yang mengandung indeks

$\L$ dan

$\M$ ... Ini mudah dilakukan di bagian dengan jumlah

$\lambda_i$ , tetapi bentuk kuadrat akan membutuhkan beberapa transformasi.

Saat menghitung

$\boldsymbol{\lambda}^T \boldsymbol{K} \boldsymbol{\lambda}$ penjumlahan dilakukan pada dua indeks, mari

$i$ dan

$j$ ... Sorot pasangan indeks yang mengandung

$\L$ atau

$\M$ ...

Mari tulis ulang masalahnya dengan menggabungkan semua yang tidak mengandung

$\lambda_\L$ atau

$\lambda_\M$ ... Untuk mempermudah melacak indeks, perhatikan

$\boldsymbol{K}$ di gambar.

$$$ 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 {kompensasi} \ atop \ text {hitungan ganda}} \ 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 \ kiri (1- \ sum_ {j} \ lambda_j K _ {\ M, j} \ kanan) + \ lambda_ \ L \ kiri (1 - \ sum_ {i} \ lambda_i K _ {\ L, i} \ kanan) + \\ & + \ frac {1} {2} \ kiri (\ lambda_ \ M ^ 2 K _ {\ M, \ M} + 2 \ lambda_ \ M \ lambda_ \ LK _ {\ M, \ L} + \ lambda_ \ L ^ 2 K _ {\ L, \ L} \ kanan) + \ text {const} = \\ & = \ boldsymbol {k} ^ T_0 \ simbol tebal {v} _0 + \ frac {1} {2} \ simbol tebal {v} ^ {\, T} _0 \, \ simbol tebal {Q} \, \ simbol tebal {v} _0 + \ teks {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}$

Dimana

$\text{const}$ menunjukkan istilah independen dari

$\lambda_\L$ atau

$\lambda_\M$ ... Di baris terakhir, saya menggunakan notasi

$$$ display $$ \ begin {align} \ boldsymbol {v} _0 & = (\ lambda_ \ M, \ lambda_ \ L) ^ T, \ tag {4a} \\ \ boldsymbol {k} _0 & = \ kiri ( 1 - \ boldsymbol {\ lambda} ^ T \ boldsymbol {K} _ {\ M}, 1 - \ boldsymbol {\ lambda} ^ T \ boldsymbol {K} _ {\ L} \ kanan) ^ 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}$

catat itu

$\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0$ tidak bergantung pada

$\lambda_\L$ atau dari

$\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. $$ 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_\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.$

Oleh karena itu, kernelnya simetris

$\boldsymbol{Q}^T = \boldsymbol{Q}$ dan Anda bisa menulis

$\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}$

Kami ingin melakukan maksimalisasi sehingga

$ sebaris $ y_ \ L \ lambda_ \ L + y_ \ M \ lambda_ \ M $ sebaris $

$y_\L\lambda_\L + y_\M\lambda_\M$ tetap konstan. Untuk ini, nilai baru harus berada pada garis lurus

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

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

Mudah untuk memastikannya untuk semua orang

$t$

$$$ display $$ y_ \ M \ lambda_ \ M ^ \ text {baru} + y_ \ L \ lambda_ \ L ^ \ text {baru} = 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. $$ display $$$

$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.$

Dalam hal ini, kita harus memaksimalkan

$\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},$

yang mudah dilakukan dengan mengambil turunannya

$\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}$

Menyamakan turunannya dengan nol, kita dapatkan

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

Dan satu hal lagi: mungkin kita akan mendaki lebih jauh dari yang diperlukan dan menemukan diri kita di luar alun-alun seperti pada gambar. Maka Anda perlu mundur selangkah dan kembali ke perbatasannya

$$$ display $$ (\ lambda_ \ M ^ \ text {baru}, \ lambda_ \ L ^ \ text {baru}) = \ boldsymbol {v} _0 + t _ * ^ {\ text {restr}} \ boldsymbol { u}. $$ display $$$

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

Ini menyelesaikan iterasi dan memilih indeks baru.

Penerapan

Diagram skema pelatihan mesin vektor dukungan yang disederhanakan dapat ditulis sebagai

Mari kita lihat kode dalam bahasa pemrograman yang sebenarnya. Jika Anda tidak menyukai kode di artikel, Anda dapat mempelajarinya di github [14] .

Kode sumber mesin vektor dukungan yang disederhanakan

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

Saat membuat objek kelas SVM, Anda dapat menentukan hyperparameter. Pelatihan dilakukan dengan memanggil fungsi fit, kelas harus ditentukan sebagai

$0$ dan

$1$ (diubah secara internal menjadi

$-1$ dan

$+1$ , dibuat untuk kompatibilitas yang lebih besar dengan sklearn), dimensi vektor fitur diizinkan secara sewenang-wenang. Fungsi prediksi digunakan untuk klasifikasi.

Perbandingan dengan sklearn.svm.SVC

Bukan berarti perbandingan ini masuk akal, karena kita berbicara tentang algoritma yang sangat disederhanakan, dikembangkan hanya untuk tujuan mengajar siswa, tetapi tetap saja. Untuk pengujian (dan untuk melihat bagaimana menggunakan semuanya), Anda dapat melakukan hal berikut (kode ini juga tersedia di github [14] ).

Perbandingan dengan sklearn.svm.SVC pada dataset 2D sederhana

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')

Setelah peluncuran, gambar akan dibuat, tetapi karena algoritme diacak, gambar akan sedikit berbeda untuk setiap peluncuran. Berikut adalah contoh cara kerja algoritme yang disederhanakan (dari kiri ke kanan: kernel linier, polinomial, dan rbf)

Dan ini adalah hasil dari versi industri dari mesin vektor pendukung.

Jika dimensi

$2$ tampaknya terlalu kecil, Anda masih dapat menguji di MNIST

Perbandingan dengan sklearn.svm.SVC pada 2 kelas dari MNIST

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))

Untuk MNIST, saya mencoba beberapa pasang kelas secara acak (algoritme yang disederhanakan hanya mendukung klasifikasi biner), tetapi saya tidak menemukan perbedaan dalam pekerjaan algoritme dan sklearn yang disederhanakan. Matriks konfusi berikut memberikan gambaran tentang kualitas.

Kesimpulan

Terima kasih untuk semua orang yang membaca sampai akhir. Dalam artikel ini, kami melihat implementasi tutorial yang disederhanakan dari mesin vektor dukungan. Tentu saja, ini tidak dapat bersaing dengan desain industri, tetapi karena kesederhanaan ekstrim dan kode yang ringkas dalam Python, serta fakta bahwa semua ide dasar SMO telah dipertahankan, versi SVM ini mungkin akan menggantikan tempatnya di kelas. Perlu dicatat bahwa algoritma ini lebih sederhana tidak hanya dari algoritma yang sangat rumit [9] , tetapi bahkan versi yang disederhanakan dari Universitas Stanford [11] . Bagaimanapun, mesin vektor dukungan dalam 30 baris itu indah.

Daftar referensi

https://fbeilstein.github.io/simplest_smo_ever/
halaman di http://www.machinelearning.ru
"Permulaan Machine Learning", 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

Mendukung Mesin Vektor, 30 baris