98

Banyak pengklasifikasi pembelajaran mesin (mis. Mesin vektor dukungan) memungkinkan seseorang untuk menentukan kernel. Apa yang akan menjadi cara intuitif untuk menjelaskan apa itu kernel?

Satu aspek yang telah saya pikirkan adalah perbedaan antara kernel linear dan non-linear. Secara sederhana, saya dapat berbicara tentang 'fungsi keputusan linier' dan 'fungsi keputusan non-linear'. Namun, saya tidak yakin apakah memanggil kernel sebagai 'fungsi keputusan' adalah ide yang bagus.

Saran?

machine-learning svm references kernel-trick intuition hashkey
sumber

114

Kernel adalah cara menghitung titik produk dari dua vektor dan dalam beberapa ruang fitur (mungkin sangat tinggi), yang mengapa fungsi kernel kadang-kadang disebut "produk titik umum". $\mathbf x$ $\mathbf y$

Misalkan kita memiliki pemetaan yang membawa vektor kami di beberapa fitur ruang . Maka produk titik dari dan dalam ruang ini adalah. Kernel adalah fungsiyang sesuai dengan produk titik ini, yaitu. $\varphi \, : \, \mathbb R^n \to \mathbb R^m$ $\mathbb R^n$ $\mathbb R^m$ $\mathbf x$ $\mathbf y$ $\varphi(\mathbf x)^T \varphi(\mathbf y)$ $k$ $k(\mathbf x, \mathbf y) = \varphi(\mathbf x)^T \varphi(\mathbf y)$

Mengapa ini berguna? Kernel memberikan cara untuk menghitung titik produk di beberapa ruang fitur tanpa mengetahui apa ruang ini dan apa yang . $\varphi$

Sebagai contoh, pertimbangkan kernel polinomial sederhana dengan . Ini sepertinya tidak sesuai dengan fungsi pemetaan , itu hanya fungsi yang mengembalikan bilangan real. Dengan asumsi bahwa dan , mari perluas ekspresi ini: $k(\mathbf x, \mathbf y) = (1 + \mathbf x^T \mathbf y)^2$ $\mathbf x, \mathbf y \in \mathbb R^2$ $\varphi$ $\mathbf x = (x_1, x_2)$ $\mathbf y = (y_1, y_2)$

$\begin{align} k(\mathbf x, \mathbf y) & = (1 + \mathbf x^T \mathbf y)^2 = (1 + x_1 \, y_1 + x_2 \, y_2)^2 = \\ & = 1 + x_1^2 y_1^2 + x_2^2 y_2^2 + 2 x_1 y_1 + 2 x_2 y_2 + 2 x_1 x_2 y_1 y_2 \end{align}$

Perhatikan bahwa ini tidak lain adalah produk titik antara dua vektor dan $(1, x_1^2, x_2^2, \sqrt{2} x_1, \sqrt{2} x_2, \sqrt{2} x_1 x_2)$ , dan $(1, y_1^2, y_2^2, \sqrt{2} y_1, \sqrt{2} y_2, \sqrt{2} y_1 y_2)$ . Jadi kernelmenghitung produk titik dalam ruang 6 dimensi tanpa secara eksplisit mengunjungi ruang ini. $\varphi(\mathbf x) = \varphi(x_1, x_2) = (1, x_1^2, x_2^2, \sqrt{2} x_1, \sqrt{2} x_2, \sqrt{2} x_1 x_2)$ $k(\mathbf x, \mathbf y) = (1 + \mathbf x^T \mathbf y)^2 = \varphi(\mathbf x)^T \varphi(\mathbf y)$

$k(\mathbf x, \mathbf y) = \exp\big(- \gamma \, \|\mathbf x - \mathbf y\|^2 \big)$ $\varphi$

Akhirnya, saya akan merekomendasikan kursus online "Belajar dari Data" oleh Profesor Yaser Abu-Mostafa sebagai pengantar yang baik untuk metode berbasis kernel. Secara khusus, kuliah "Mendukung Mesin Vektor" , "Metode Kernel" dan "Fungsi Dasar Radial" adalah tentang kernel.

Alexey Grigorev
sumber

2

Definisi tag saat ini: "Intuitif: pertanyaan yang mencari pemahaman statistik konseptual atau non-matematis." Tidak ada indikasi yang jelas apakah konseptual diperlakukan sebagai sinonim dari non-matematika.

rolando2

40

Cara berpikir yang sangat sederhana dan intuitif tentang kernel (setidaknya untuk SVM) adalah fungsi kesamaan. Diberikan dua objek, kernel menghasilkan beberapa skor kesamaan. Objek dapat berupa apa saja mulai dari dua bilangan bulat, dua vektor bernilai nyata, pohon apa pun asalkan fungsi kernel tahu cara membandingkannya.

Contoh yang paling sederhana adalah kernel linear, juga disebut dot-product. Diberikan dua vektor, kesamaannya adalah panjang proyeksi satu vektor pada vektor lainnya.

Contoh kernel lain yang menarik adalah kernel Gaussian. Diberikan dua vektor, kesamaan akan berkurang dengan jari-jari . Jarak antara dua objek adalah "reweighted" oleh parameter radius ini. $\sigma$

Keberhasilan belajar dengan kernel (sekali lagi, setidaknya untuk SVM), sangat bergantung pada pilihan kernel. Anda dapat melihat kernel sebagai representasi ringkas dari pengetahuan tentang masalah klasifikasi Anda. Sangat sering masalah khusus.

Saya tidak akan menyebut kernel sebagai fungsi keputusan karena kernel digunakan di dalam fungsi keputusan. Diberikan titik data untuk diklasifikasi, fungsi keputusan memanfaatkan kernel dengan membandingkan titik data itu dengan sejumlah vektor dukungan yang dibobot oleh parameter yang dipelajari . Vektor pendukung berada dalam domain titik data itu dan sepanjang parameter yang dipelajari ditemukan oleh algoritma pembelajaran. $\alpha$ $\alpha$

Vladislavs Dovgalecs
sumber

Produk dan proyeksi dot tidak persis sama.

ttnphns

Dalam kasus SVM, saya percaya bahwa kernel adalah ukuran jarak di ruang yang berbeda. Ini sesuai dengan gagasan bahwa SVM menggeneralisasikan classifier vektor dukungan. Secara umum, kernel bisa lebih rumit.

aginensky

30

Contoh visual untuk membantu intuisi

Pertimbangkan dataset berikut di mana titik kuning dan biru jelas tidak dapat dipisahkan secara linear dalam dua dimensi.

Jika kita dapat menemukan ruang dimensi yang lebih tinggi di mana titik-titik ini terpisah secara linear , maka kita dapat melakukan hal berikut:

Memetakan fitur asli ke ruang transformator yang lebih tinggi (pemetaan fitur)
Lakukan SVM linier di ruang yang lebih tinggi ini
Dapatkan satu set bobot yang sesuai dengan hyperplane batas keputusan
Petakan hyperplane ini kembali ke ruang 2D asli untuk memperoleh batas keputusan nonlinier

Ada banyak ruang dimensi yang lebih tinggi di mana titik-titik ini terpisah secara linear. Ini salah satu contohnya

x_{1}, x_{2} :\to z_{1}, z_{2}, z_{3}

$x_1, x_2 : \rightarrow z_1, z_2, z_3$

z_{1} = \sqrt{2} x_{1} x_{2} z_{2} = x_{1}^{2} z_{3} = x_{2}^{2}

$z_1 = \sqrt{2}x_1x_2 \ \ z_2 = x_1^2 \ \ z_3 = x_2^2$

Di sinilah trik Kernel berperan. Mengutip jawaban bagus di atas

Misalkan kita memiliki pemetaan yang membawa vektor kita di ke beberapa ruang fitur . Maka produk titik dan di ruang ini adalah . Kernel adalah fungsi yang sesuai dengan produk titik ini, yaitu $\varphi \, : \, \mathbb R^n \to \mathbb R^m$ $\mathbb R^n$ $\mathbb R^m$ $\mathbf x$ $\mathbf y$ $\varphi(\mathbf x)^T \varphi(\mathbf y)$ $k$ $k(\mathbf x, \mathbf y) = \varphi(\mathbf x)^T \varphi(\mathbf y)$

Jika kita dapat menemukan fungsi kernel yang setara dengan peta fitur di atas, maka kita dapat menyambungkan fungsi kernel dalam SVM linier dan melakukan perhitungan dengan sangat efisien.

Kernel polinomial

Ternyata fitur peta di atas sesuai dengan kernel polinomial terkenal : . Biarkan dan kita dapatkan $K(\mathbf{x},\mathbf{x'}) = (\mathbf{x}^T\mathbf{x'})^d$ $d = 2$ $\mathbf{x} = (x_1, x_2)^T$

\begin{aligned} k ((\begin{matrix} x_{1} \\ x_{2} \end{matrix}), (\begin{matrix} x_{1}^{'} \\ x_{2}^{'} \end{matrix})) & = (x_{1} x_{2}^{'} + x_{2} x_{2}^{'})^{2} \\ = 2 x_{1} x_{1}^{'} x_{2} x_{2}^{'} + (x_{1} x_{1}^{'})^{2} + (x_{2} x_{2}^{'})^{2} \\ = (\sqrt{2} x_{1} x_{2} x_{1}^{2} x_{2}^{2}) (\begin{matrix} \sqrt{2} x_{1}^{'} x_{2}^{'} \\ x_{1}^{' 2} \\ x_{2}^{' 2} \end{matrix}) \end{aligned}

$\begin{aligned} k(\begin{pmatrix} x_1 \\ x_2 \end{pmatrix}, \begin{pmatrix} x_1' \\ x_2' \end{pmatrix} ) & = (x_1x_2' + x_2x_2')^2 \\ & = 2x_1x_1'x_2x_2' + (x_1x_1')^2 + (x_2x_2')^2 \\ & = (\sqrt{2}x_1x_2 \ x_1^2 \ x_2^2) \ \begin{pmatrix} \sqrt{2}x_1'x_2' \\ x_1'^2 \\ x_2'^2 \end{pmatrix} \end{aligned}$

k ((\begin{matrix} x_{1} \\ x_{2} \end{matrix}), (\begin{matrix} x_{1}^{'} \\ x_{2}^{'} \end{matrix})) = ϕ (x)^{T} ϕ (x^{'})

$k(\begin{pmatrix} x_1 \\ x_2 \end{pmatrix}, \begin{pmatrix} x_1' \\ x_2' \end{pmatrix} ) = \phi(\mathbf{x})^T \phi(\mathbf{x'})$

ϕ ((\begin{matrix} x_{1} \\ x_{2} \end{matrix})) = (\begin{matrix} \sqrt{2} x_{1} x_{2} \\ x_{1}^{2} \\ x_{2}^{2} \end{matrix})

$\phi(\begin{pmatrix} x_1 \\ x_2 \end{pmatrix}) =\begin{pmatrix} \sqrt{2}x_1x_2 \\ x_1^2 \\ x_2^2 \end{pmatrix}$

Memvisualisasikan peta fitur dan garis batas yang dihasilkan

Plot sisi kiri menunjukkan titik-titik yang diplot dalam ruang yang ditransformasikan bersama-sama dengan bidang batas linear SVM
Plot sisi kanan menunjukkan hasil dalam ruang 2-D asli

Sumber

Pos lengkap dan kode python di sini
https://disi.unitn.it/~passerini/teaching/2014-2015/MachineLearning/slides/17_kernel_machines/handouts.pdf

Xavier Bourret Sicotte
sumber

4

Sangat sederhana (tapi akurat) kernel adalah faktor penimbangan antara dua urutan data. Faktor penimbangan ini dapat menetapkan bobot lebih untuk satu " titik data " pada satu " titik waktu " daripada " titik data " lainnya, atau menetapkan bobot yang sama atau memberikan bobot lebih ke " titik data " lainnya dan seterusnya.

Dengan cara ini, korelasi ( produk titik ) dapat menetapkan lebih banyak "kepentingan" di beberapa titik daripada yang lain dan dengan demikian mengatasi non-linearitas (misalnya ruang non-datar ), informasi tambahan, perataan data , dan sebagainya.

Dengan cara lain kernel adalah cara untuk mengubah dimensi relatif (atau unit dimensi ) dari dua sekuens data untuk mengatasi hal-hal yang disebutkan di atas.

Dengan cara ketiga (terkait dengan dua sebelumnya), kernal adalah cara untuk memetakan atau memproyeksikan satu urutan data ke yang lain secara 1-ke-1 dengan mempertimbangkan informasi atau kriteria yang diberikan (misalnya ruang melengkung, data yang hilang, data pemesanan ulang dan sebagainya). Jadi misalnya kernel yang diberikan dapat meregangkan atau mengecilkan atau memotong atau menekuk satu urutan data agar sesuai atau memetakan 1-ke-1 ke yang lain.

Kernel dapat bertindak seperti Procrustes untuk " paling cocok "

Nikos M.
sumber

Saya pikir Anda mungkin berbicara tentang kernel dalam arti estimasi kepadatan kernel, bukan kernel Mercer positif-semidefinite yang digunakan dalam SVM dan metode terkait.

Dougal

@Dougal, dalam arti jawaban ini, kernel adalah fungsi penimbangan atau ukuran yang digunakan untuk mengkorelasikan data dengan cara tertentu atau untuk mengeksploitasi fitur data tertentu, sehingga metode kernel SVM tercakup juga

Nikos M.

Bagaimana cara menjelaskan kernel secara intuitif?

Jawaban:

Contoh visual untuk membantu intuisi

Kernel polinomial

Memvisualisasikan peta fitur dan garis batas yang dihasilkan

Sumber