Peta fitur untuk kernel Gaussian

24

Dalam SVM, kernel Gaussian didefinisikan sebagai: mana x, y \ in \ mathbb {R ^ n} . Saya tidak tahu persamaan eksplisit \ phi . Saya ingin mengetahuinya.

K(x,y)=exp(xy222σ2)=ϕ(x)Tϕ(y)
x,yRnϕ

Saya juga ingin tahu apakah

iciϕ(xi)=ϕ(icixi)
di mana ciR . Sekarang, saya pikir itu tidak sama, karena menggunakan kernel menangani situasi di mana linear tidak bekerja. Saya tahu ϕ memproyeksikan x ke ruang tanpa batas. Jadi jika masih tetap linier, berapa pun dimensinya, svm tetap tidak bisa membuat klasifikasi yang baik.
Vivian
sumber
mengapa kernel ini menyiratkan transformasi? Atau apakah Anda merujuk ke ruang fitur terkait?
Placidia
Ya, apa ruang fitur ϕ() sehingga ϕT(x)ϕ(x)=exp(12σ2xx2)
user27886

Jawaban:

20

Anda dapat memperoleh persamaan eksplisit ϕ untuk kernel Gaussian melalui perluasan seri Penjahit ex . Untuk kesederhanaan notasi, asumsikan xR1 :

ϕ(x)=ex2/2σ2[1,11!σ2x,12!σ4x2,13!σ6x3,]T

Ini juga dibahas secara lebih rinci dalam slide-slide ini oleh Chih-Jen Lin dari NTU (slide 11 khusus). Perhatikan bahwa dalam slide digunakan sebagai parameter kernel.γ=12σ2

Persamaan dalam OP hanya berlaku untuk kernel linier.

Marc Claesen
sumber
2
Hai, tetapi persamaan di atas hanya cocok untuk satu dimensi.
Vivian
Jadi, di sini, ruang kernel Hilbert yang direproduksi adalah subruang dari , benar? 2
The_Anomaly
Apakah ada juga representasi eksplisit dari kernel Laplacian?
Felix Crazzolara
13

Untuk setiap kernel psd valid , terdapat peta fitur sehingga . Ruang dan embedding sebenarnya tidak harus unik, tetapi ada pasangan unik yang penting dikenal sebagai kernel mereproduksi ruang Hilbert (RKHS).k:X×XRφ:XHk(x,y)=φ(x),φ(y)HHφ(H,φ)

RKHS didiskusikan oleh: Steinwart, Hush and Scovel, Deskripsi yang Eksplisit tentang Ruang Hilbert Kernel yang Direproduksi dari Gaussian RBF Kernels , Transaksi IEEE pada Teori Informasi 2006 ( doi , free citeseer pdf ).

Agak rumit, tetapi intinya adalah: define sebagai en:CC

en(z):=(2σ2)nn!zneσ2z2.

Misalkan menjadi urutan yang berkisar pada semua -tupel bilangan bulat negatif; jika , mungkin , , , dan seterusnya. Nyatakan komponen th tuple ke- oleh .n:N0N0ddd=3n(0)=(0,0,0)n(1)=(0,0,1)n(2)=(0,1,1)jinij

Kemudian th komponen adalah . Jadi memetakan vektor dalam ke vektor kompleks dimensi tak terbatas.iφ(x)j=1denij(xj)φRd

Yang menarik dari hal ini adalah bahwa kita harus mendefinisikan norma untuk vektor kompleks dimensi tak terbatas ini dengan cara yang khusus; lihat kertas untuk detailnya.


Steinwart et al. juga memberikan yang lebih mudah (untuk pemikiran saya) menanamkan ke , ruang Hilbert fungsi persegi-integrable dari : Perhatikan bahwa itu sendiri merupakan fungsi dari untuk . Ini pada dasarnya adalah kepadatan Gaussian dimensional dengan rerata dan kovarians ; hanya konstanta normalisasi yang berbeda. Demikian saat kita ambil L2(Rd)RdR

Φσ(x)=(2σ)d2πd4e2σ2x22.
Φσ(x)RdRdx14σ2I
Φ(x),Φ(y)L2=[Φ(x)](t)[Φ(y)](t)dt,
kami mengambil produk dari fungsi kepadatan Gaussian , yang dengan sendirinya merupakan waktu konstan tertentu fungsi kepadatan Gaussian. Ketika Anda melakukan itu integral dengan , maka, konstanta yang jatuh akhirnya menjadi persis .tk(x,y)

Ini bukan satu-satunya embeddings yang berfungsi.

Lain didasarkan pada transformasi Fourier, yang makalah terkenal Rahimi dan Recht ( Fitur Acak untuk Mesin Kernel Skala Besar , NIPS 2007) mendekati efek yang besar.

Anda juga dapat melakukannya menggunakan seri Taylor: secara efektif versi tak terbatas dari Cotter, Keshet, dan Srebro, Perkiraan Eksplisit dari Kernel Gaussian , arXiv: 1109.4603 .

Dougal
sumber
1
Douglas Zare memberikan versi 1d dari penyisipan "lebih mudah" di utas yang menarik di sini .
Dougal
Di sini Anda menemukan penjelasan yang lebih 'intuitif' bahwa dapat memetakan ke dimensi yang sama dengan ukuran sampel pelatihan, bahkan untuk sampel pelatihan tak terbatas: stats.stackexchange.com/questions/80398/…Φ
6

Tampaknya bagi saya bahwa persamaan kedua Anda hanya akan benar jika adalah pemetaan linear (dan karenanya adalah kernel linier). Karena kernel Gaussian adalah non-linear, persamaan tidak akan berlaku (kecuali mungkin dalam batas sebagai menjadi nol).ϕKσ

Dikran Marsupial
sumber
Terima kasih atas jawaban Anda. Ketika , dimensi proyek kernel Gaussian akan meningkat. Dan dengan inspirasi Anda, sekarang saya pikir itu tidak sama. Karena, menggunakan kernel hanya menangani situasi bahwa klasifikasi linier tidak berfungsi. σ0
Vivian