Diberikan satu set poin dalam ruang dua dimensi, bagaimana bisa satu fungsi keputusan desain untuk SVM?

Adakah yang bisa menjelaskan bagaimana merancang fungsi keputusan SVM? Atau arahkan saya ke sumber yang membahas contoh konkret.

EDIT

Untuk contoh di bawah ini, saya dapat melihat bahwa persamaan memisahkan kelas dengan margin maksimum. Tetapi bagaimana cara menyesuaikan bobot dan menulis persamaan untuk hyperplanes dalam bentuk berikut.$X_2 = 1.5$

$$\begin{array}{ll} H_1 : w_0+w_1x_1+w_2x_2 \ge 1 & \text{for}\; Y_i = +1 \\ H_2 : w_0+w_1x_1+w_2x_2 \le -1 & \text{for}\; Y_i = -1.\end{array}$$

Saya mencoba untuk mendapatkan teori dasar di ruang 2-D (karena lebih mudah untuk divisualisasikan) sebelum saya berpikir tentang dimensi yang lebih tinggi.

Saya telah menemukan solusi untuk ini. Dapatkah seseorang mengonfirmasi apakah ini benar?

vektor bobot adalah (0, -2) dan W_0 adalah 3

$$\begin{array}{ll} H_1 : 3+0x_1-2x_2 \ge 1 & \text{for}\; Y_i = +1 \\ H_2 : 3+0x_1 -2x_2 \le -1 & \text{for}\; Y_i = -1.\end{array}$$

Setidaknya ada dua cara untuk memotivasi SVM, tetapi saya akan mengambil rute yang lebih sederhana di sini.

Sekarang, lupakan semua yang Anda ketahui tentang SVM untuk saat ini dan hanya fokus pada masalah yang ada. Anda diberi satu set poin bersama dengan beberapa label ( ) yang berasal dari . Sekarang, kami berusaha menemukan garis dalam 2D ​​sehingga semua titik dengan label jatuh di satu sisi garis dan semua titik dengan label jatuh di sisi lain.y i { 1 , - 1 } 1 - $\mathcal{D} = \{(x^i_1, x^i_2, y_i)\}$$y_i$$\{1, -1\}$$1$$-1$

Pertama-tama, sadari bahwa adalah garis dalam 2D ​​dan mewakili "satu sisi" dari garis dan mewakili "sisi lain" dari baris.w 0 + w 1 x 1 + w 2 x 2 > 0 w 0 + w 1 x 1 + w 2 x 2 < $w_0 + w_1x_1 + w_2x_2 = 0$$w_0 + w_1x_1 + w_2x_2 > 0$$w_0 + w_1x_1 + w_2x_2 < 0$

Dari di atas kita dapat menyimpulkan bahwa kita menginginkan beberapa vektor sedemikian rupa sehingga, untuk semua titik dengan dan untuk semua poin dengan [1].w 0 + w 1 x i 1 + w 2 x i 2 ≥ 0 x i y i = 1 w 0 + w 1 x i 1 + w 2 x i 2 < 0 x i y i = - $[w_0, w_1, w_2]$$w_0 + w_1x^i_1 + w_2x^i_2 \geq 0$$x^i$$y_i = 1$$w_0 + w_1x^i_1 + w_2x^i_2 < 0$$x^i$$y_i = -1$

Mari kita asumsikan bahwa garis seperti itu benar-benar ada maka saya dapat mendefinisikan classifier dengan cara berikut,

$$\min |w_0| + |w_1| + |w_2| \\ \text{subject to} : w_0 + w_1x^i_1 + w_2x^i_2 \geq 0, \forall x^i\text{ with }y_i = 1 \\ w_0 + w_1x^i_1 + w_2x^i_2 < 0, \forall x^i\text{ with }y_i = -1 \\ $$

Saya telah menggunakan fungsi tujuan yang sewenang-wenang di atas, kami tidak benar-benar peduli pada saat ini fungsi tujuan mana yang digunakan. Kami hanya menginginkan yang memenuhi kendala kami. Karena kami berasumsi bahwa ada garis sehingga kami dapat memisahkan dua kelas dengan garis itu, kami akan menemukan solusi untuk masalah optimasi di atas.$w$

Di atas bukan SVM tetapi akan memberi Anda classifier :-). Namun klasifikasi ini mungkin tidak terlalu baik. Tetapi bagaimana Anda mendefinisikan classifier yang baik? Pengklasifikasi yang baik biasanya merupakan pengelompokan yang baik pada set tes. Idealnya, Anda akan pergi ke semua mungkin 's yang memisahkan data training dan melihat mana dari mereka tidak baik pada data uji. Namun, ada tak terbatas , jadi ini sangat tidak ada harapan. Sebagai gantinya, kami akan mempertimbangkan beberapa heuristik untuk mendefinisikan classifier yang baik. Satu heuristik adalah bahwa garis yang memisahkan data akan cukup jauh dari semua titik (yaitu selalu ada kesenjangan atau margin antara titik dan garis). Klasifikasi terbaik di antara ini adalah satu dengan margin maksimum. Inilah yang digunakan dalam SVM.$w$$w$

Alih-alih bersikeras bahwa untuk semua poin dengan dan untuk semua poin dengan , jika kita bersikeras bahwa untuk semua poin dengan dan untuk semua poin dengan , maka kita sebenarnya bersikeras bahwa poin berada jauh dari garis. Margin geometris yang sesuai dengan persyaratan ini adalah .x i y i = 1 w 0 + w 1 x i 1 + w 2 x i 2 < 0 x i y i = - 1 w 0 + w 1 x i 1 + w 2 x i 2 ≥ $w_0 + w_1x^i_1 + w_2x^i_2 \geq 0$$x^i$$y_i = 1$$w_0 + w_1x^i_1 + w_2x^i_2 < 0$$x^i$$y_i = -1$$w_0 + w_1x^i_1 + w_2x^i_2 \geq 1$y i = 1 w 0 + w 1 x i 1 + w 2 x i 2 ≤ - 1 x i y i = - 1 $x^i$$y_i = 1$$w_0 + w_1x^i_1 + w_2x^i_2 \leq -1$$x^i$$y_i = -1$$\frac{1}{\|w\|_2}$

Jadi, kami mendapatkan masalah pengoptimalan berikut, Bentuk penulisan yang agak ringkas ini adalah, Ini pada dasarnya adalah formulasi dasar SVM. Saya telah melewatkan cukup banyak diskusi untuk singkatnya. Mudah-mudahan, saya masih mendapatkan sebagian besar ide.

$$\max \frac{1}{\|w\|_2} \\ \text{subject to} : w_0 + w_1x^i_1 + w_2x^i_2 \geq 1, \forall x^i\text{ with }y_i = 1 \\ w_0 + w_1x^i_1 + w_2x^i_2 \leq -1, \forall x^i\text{ with }y_i = -1 \\ $$ $$\min \|w\|_2 \\ \text{subject to} : y_i(w_0 + w_1x^i_1 + w_2x^i_2) \geq 1, \forall i$$

---

Script CVX untuk memecahkan contoh masalah:

A = [1 2 1; 3 2 1; 2 3 1; 3 3 1; 1 1 1; 2 0 1; 2 1 1; 3 1 1];
b = ones(8, 1);
y = [-1; -1; -1; -1; 1; 1; 1; 1];
Y = repmat(y, 1, 3);
cvx_begin
variable w(3)
minimize norm(w)
subject to
(Y.*A)*w >= b
cvx_end

---

Addendum - Margin Geometris

Di atas kami telah meminta kami mencari sedemikian rupa sehingga atau umumnya . LHS di sini yang Anda lihat disebut margin fungsional, jadi apa yang kami minta di sini adalah margin fungsional menjadi . Sekarang, kami akan mencoba untuk menghitung margin geometris mengingat persyaratan margin fungsional ini.$w$$y_i(w_0 + w_1x_1 + w_2x_2) \geq 1$$y_i(w_0 + w^Tx) \geq 1$$\geq 1$

Apa itu margin geometris? Margin geometris adalah jarak terpendek antara titik dalam contoh positif dan titik dalam contoh negatif. Sekarang, titik yang memiliki jarak terpendek seperti yang dipersyaratkan di atas dapat memiliki margin fungsional lebih besar dari sama dengan 1. Namun, mari kita perhatikan kasus ekstrim, ketika mereka paling dekat dengan hyperplane yaitu, margin fungsional untuk titik terpendek persis sama ke 1. Biarkan menjadi titik pada contoh positif menjadi titik sehingga dan menjadi titik pada contoh negatif menjadi titik sedemikian rupa sehingga . Sekarang, jarak antara dan akan menjadi yang terpendek ketika$x_+$$w^Tx_+ + w_0 = 1$$x_-$$w^Tx_- + w_0 = -1$$x_+$$x_-$$x_+ - x_-$ tegak lurus terhadap hyperplane.

Sekarang, dengan semua informasi di atas kami akan mencoba menemukan yang merupakan margin geometrik. $\|x_+ - x_-\|_2$

$$w^Tx_+ + w_0 = 1$$ $$w^Tx_- + w_0 = -1$$ $$w^T(x_+ - x_-) = 2$$ $$|w^T(x_+ - x_-)| = 2$$ ‖ x + - x - ‖ 2 = $$\|w\|_2\|x_+ - x_-\|_2 = 2$$ $$\|x_+ - x_-\|_2 = \frac{2}{\|w\|_2}$$

---

[1] Tidak masalah sisi mana yang Anda pilih untuk dan . Anda hanya harus tetap konsisten dengan apa pun yang Anda pilih.- $1$$-1$