Kernelised k Neighbor Terdekat

Saya baru mengenal kernel dan telah mengalami kesulitan saat mencoba kernelkan kNN.

Persiapan

Saya menggunakan kernel polinomial:
$K(\mathbf{x},\mathbf{y}) = (1 + \langle \mathbf{x},\mathbf{y} \rangle)^d$

KNN Euclidean khas Anda menggunakan metrik jarak berikut:
$d(\mathbf{x}, \mathbf{y}) = \vert\vert \mathbf{x} - \mathbf{y} \vert\vert$

Biarkan memetakan ke dalam ruang fitur dimensi yang lebih tinggi. Kemudian kuadrat dari metrik jarak di atas dalam ruang Hilbert dapat dinyatakan oleh produk dalam: x d 2 ( f ( x ) , f ( y ) ) = K ( x , x ) - 2 K ( x , y ) + K ( y , y$f(\mathbf{x})$$\mathbf{x}$$d^2(f(x), f(y)) = K(\mathbf{x},\mathbf{x}) - 2K(\mathbf{x}, \mathbf{y}) + K(\mathbf{y} ,\mathbf{y})$

Perhatikan bahwa jika kita membiarkan di atas akan merosot ke jarak Euclidean standar Anda.$d = 1$

Pertanyaan

Masalah utama yang saya miliki adalah bahwa saya tidak dapat melihat bagaimana kernelisasi kNN menghasilkan hasil yang lebih baik seperti yang ditunjukkan secara eksperimental oleh, misalnya, makalah ini (peringatan, tautan pdf langsung!).

Teorema Cover: Secara kasar dinyatakan, dikatakan diberi set acak hingga poin (dengan label arbitrer), maka dengan probabilitas tinggi titik-titik ini dapat dibuat terpisah secara linear [1] dengan memetakannya ke dimensi yang lebih tinggi [2].

Implikasi: Hebat, apa yang dikatakan teorema ini kepada saya adalah bahwa jika saya mengambil dataset dan memetakan titik-titik ini ke dimensi yang lebih tinggi, maka saya dapat dengan mudah menemukan classifier linier. Namun, sebagian besar pengklasifikasi perlu menghitung semacam kesamaan seperti produk titik dan ini berarti bahwa kompleksitas waktu dari algoritma klasifikasi sebanding dengan dimensi titik data. Jadi, dimensi yang lebih tinggi berarti kompleksitas waktu yang lebih besar (belum termasuk kompleksitas ruang untuk menyimpan titik-titik dimensi besar).

$n$$f$$N (>> n)$$K$$x$$y$$K(x, y) = \langle f(x), f(y) \rangle$$O(n)$$O(N)$

$f$

Apakah keterpisahan linear menyiratkan bahwa poin dari kelas yang sama akan lebih dekat daripada poin dari kelas yang berbeda? Tidak, tidak ada jaminan seperti itu. Keterpisahan linear tidak benar-benar menyiratkan bahwa titik dari kelas yang sama telah semakin dekat atau bahwa poin dari dua kelas yang berbeda telah semakin jauh.

Jadi mengapa kNN bekerja? Tidak perlu! Namun, jika ya, maka itu murni karena kernel.

$x = (x_1, x_2)$$x$$(x_1^2, \sqrt{2} x_1x_2, x_2^2)$

Lalu mengapa menggunakan kernel kNN? Kami menunjukkan bahwa kompleksitas perhitungan menggunakan kernel hanya sedikit lebih banyak daripada kNN biasa dan jika data mendapat manfaat dari penggunaan kernel maka mengapa tidak menggunakannya?

Apakah ada makalah yang telah mempelajari kelas data mana yang dapat mengambil manfaat dari kernel di kNN? Sejauh yang saya tahu, tidak.

[1] http://en.wikipedia.org/wiki/Linear_separability
[2] http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4038449&tag=1