Fungsi apa yang bisa menjadi kernel?

21

Dalam konteks pembelajaran mesin dan pengenalan pola, ada konsep yang disebut Kernel Trick . Menghadapi masalah di mana saya diminta untuk menentukan apakah suatu fungsi bisa menjadi fungsi kernel atau tidak, apa sebenarnya yang harus dilakukan? Haruskah saya periksa dulu apakah mereka dalam bentuk tiga atau empat fungsi kernel seperti polinomial, RBF dan Gaussian? Lalu apa yang harus saya lakukan? Haruskah saya tunjukkan pasti positif? Bisakah seseorang memecahkan contoh untuk menunjukkan solusi langkah-demi-langkah untuk masalah seperti itu? Seperti misalnya, apakah fungsi kernelf(x)=extx (misalkan kita tidak tahu itu adalah kernel Gaussian)?

Gigili
sumber

Jawaban:

27

Secara umum, fungsi adalah fungsi kernel yang valid (dalam arti trik kernel) jika memenuhi dua properti utama:k(x,y)

  • simetri: k(x,y)=k(y,x)

  • semi-definiteness positif.

Referensi: Halaman 4 dari http://www.cs.berkeley.edu/~jordan/courses/281B-spring04/lectures/lec3.pdf

Memeriksa simetri biasanya langsung dengan inspeksi. Memverifikasi semi-kepastian positif secara analitis kadang-kadang bisa sangat berbulu. Saya dapat memikirkan dua strategi untuk memeriksa fakta ini:

  • (1) Memeriksa representasi "produk dalam"

Pertimbangkan . Bisakah kita menemukan beberapa sedemikian rupa sehingga ? Sedikit matematika menunjukkan bahwa , jadi biarkan dan kita selesai. ϕ ( a ) k ( x , y ) = ϕ ( x ) T ϕ ( y ) e x + y = e x e y ϕ ( a ) = e ak(x,y)=ex+yϕ(Sebuah)k(x,y)=ϕ(x)Tϕ(y)ex+y=exeyϕ(Sebuah)=eSebuah

Jika Anda beruntung, akan setuju dengan analisis ini. Jika tidak, Anda dapat menggunakan opsi (2):k()

  • (2) Memeriksa kepastian positif dengan simulasi acak.

Dx , yk(x,y)=d=1Dmin(xd,yd)x,y

Kami dapat memeriksa ini dengan simulasi. Gambarkan sekumpulan vektor acak dan bangun matriks Gram mana . Kemudian periksa apakah positif (semi-) pasti.{ x i } N i = 1 K K i j = k ( x i , x j ) KN{xi}i=1NKKij=k(xi,xj)K

Cara terbaik untuk melakukan ini secara numerik adalah dengan menemukan nilai eigen dari matriks (menggunakan perpustakaan numerik yang ada seperti scipy atau matlab), dan memverifikasi bahwa nilai eigen terkecil lebih besar dari atau sama dengan 0 . Jika ya, matriks adalah psd. Jika tidak, Anda tidak memiliki kernel yang valid.K

Contoh kode MATLAB / Oktaf:

D=5;
N=100;

X = zeros(N,D);
for n = 1:N
   xcur = rand(1,D);
   X(n,:) = xcur/sum(xcur);
end

K = zeros(N,N);
for n = 1:N;  for m = 1:N
    K(n,m) = sum( min( X(n,:), X(m,:) ) );
end;  end;

disp( min( eig(K) ) );

Ini adalah tes yang sangat sederhana, tetapi hati-hati . Jika pengujian gagal, Anda dapat memastikan kernel tidak valid, tetapi jika melewati kernel mungkin masih tidak valid.

Saya menemukan bahwa tidak peduli berapa banyak matriks acak yang saya hasilkan dan terlepas dari dan , kernel ini lulus tes, jadi mungkin positif semi-pasti (pada kenyataannya, ini adalah persimpangan kernel histogram terkenal , dan telah terbukti sah).D.ND

Namun, pengujian yang sama pada gagal pada setiap percobaan yang saya berikan (setidaknya 20) . Jadi itu jelas tidak valid, dan cukup mudah untuk diverifikasi.k(x,y)=d=1DmSebuahx(xd,yd)

Saya sangat suka opsi kedua ini karena ini cukup cepat dan jauh lebih mudah untuk di-debug daripada bukti formal yang dikompilasi. Menurut slide 19 Jitendra Malik , kernel persimpangan diperkenalkan pada tahun 1991 tetapi tidak terbukti benar sampai tahun 2005. Bukti formal bisa sangat menantang!

Mike Hughes
sumber
Seperti yang saya pahami, kondisi kedua hanya setengah- positif positif . Dan dari apa yang saya katakan, hanya perlu jika Anda ingin membuktikan konvergensi dari algoritma SVM. Dalam prakteknya, ada banyak kernel yang bukan PSD, tetapi bekerja dengan baik dalam praktik.
Peter
@ Peter: ya, Anda benar. Itu bisa * semi- * pasti, bukan hanya pasti. Diedit sesuai.
Mike Hughes
Dalam domain SVM, menggunakan kernel PSD memastikan masalahnya adalah cembung, sehingga optimasi mencapai solusi unik, optimal secara global. Tanpa properti PSD, tidak ada jaminan bahwa solusi yang ditemukan mendekati yang terbaik. Tapi, ya ada beberapa kernel (seperti Sigmoid) yang bukan PSD tetapi masih berhasil dalam praktik. Referensi yang layak untuk masalah ini adalah: perso.lcpc.fr/tarel.jean-philippe/publis/jpt-icme05.pdf .
Mike Hughes