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ϕ ( a )k ( x , y) = ϕ ( x )Tϕ ( y)ex + y= exeyϕ ( a ) = eSebuah
Jika Anda beruntung, akan setuju dengan analisis ini. Jika tidak, Anda dapat menggunakan opsi (2):k ( )
- (2) Memeriksa kepastian positif dengan simulasi acak.
D→ x , → yk ( x⃗ , y⃗ ) = ∑Dd= 1min(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{ x⃗ saya}Ni = 1KKsaya j= k ( x⃗ saya, x⃗ j)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⃗ ) = ∑Dd= 1m a x ( 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!