Bagaimana cara kerja wastafel dapur acak?

18

Tahun lalu di NIPS 2017 Ali Rahimi dan Ben Recht memenangkan ujian penghargaan waktu untuk makalah mereka "Fitur Acak untuk Mesin Kernel Skala Besar" di mana mereka memperkenalkan fitur acak, yang kemudian dikodifikasikan sebagai algoritma kitchen sink acak. Sebagai bagian dari mempublikasikan makalah mereka, mereka menunjukkan bahwa model mereka dapat diimplementasikan dalam 5 baris matlab.

% Approximates Gaussian Process regression
%     with Gaussian kernel of variance gamma^2
% lambda: regularization parameter
% dataset: X is dxN, y is 1xN
% test: xtest is dx1
% D: dimensionality of random feature

% training
w = randn(D,d);
b = 2 * pi * rand(D, 1);
Z = cos(gamma * w * X + b * ones(1,N));

alpha = (lambda * eye(D) +Z * Z') \ (Z * y);

% testing
ztest = alpha' * cos(gamma * w * xtest + b);

Bagaimana algoritma di atas mempelajari sesuatu tidak jelas bagi saya. Bagaimana cara kerja wastafel dapur acak? Bagaimana cara perkiraan proses Gaussian dan mendukung mesin vektor?

Edit

Mengutip pembicaraan Rahimi, istilah kitchen sink secara acak tidak diperkenalkan di surat kabar dimana mereka memenangkan penghargaan tetapi pada akhir trilogi makalah yang dimulai dengan "Fitur Acak untuk Mesin Kernel Skala Besar". Makalah lainnya adalah:

Rahimi, Ali, dan Benjamin Recht. "Perkiraan fungsi yang seragam dengan basis acak." Komunikasi, Kontrol, dan Komputasi, Konferensi Allerton Tahunan ke-46 2008 tentang. IEEE, 2008.

Rahimi, Ali, dan Benjamin Recht. "Jumlah terbobot dari wastafel dapur acak: Mengganti minimalisasi dengan pengacakan dalam pembelajaran." Kemajuan dalam sistem pemrosesan informasi saraf. 2009

Saya pikir cuplikan kode yang diperkenalkan di atas adalah spesialisasi Algoritma 1 pada makalah terakhir.

MesinEpsilon
sumber
Baik kata "sink" maupun kode yang Anda kutip muncul di kertas yang tertaut. Apakah Anda kehilangan referensi?
Kodiologist
2
Anda benar, terima kasih. Tanpa konteks pembicaraan 2017, pertanyaannya tampak agak terputus-putus! Gagasan ini dikembangkan di makalah pertama, saya pikir tetapi istilah kitchen sink hanya diperkenalkan kemudian. Cuplikan kode dibagikan pada sesi poster 2007 untuk makalah tersebut. Saya menyalinnya dari ceramah Rahimi di NIPS 2017.
MachineEpsilon

Jawaban:

15

Wastafel dapur acak (atau fitur Fourier acak) dan metode terkait lainnya tidak berusaha melakukan inferensi melainkan mencoba mengurangi hambatan metode inferensi berbasis kernel.

n×nO(n3)

Fitur Random Fourier (Rehimi & Recht 2007) dipertimbangkan untuk membuat perkiraan peringkat rendah dari kernel invarian shift dengan mengambil sampel hanya subset acak dari komponen Fourier kernel. Karena ruang Fourier berubah invarian, properti ini dipertahankan tetapi sekarang ruang Hilbert yang mereproduksi dimensi eksplisit eksplisit dibentuk oleh penyatuan komponen Fourier ini. RKHS dimensi yang tak terbatas sekali didekati oleh kernel perkiraan degenerasi.

Catatan tentang cuplikan kode: Ada beberapa detail yang disikat dalam 5 baris. Yang paling penting adalah bahwa fungsi Gaussian juga merupakan fungsi Gaussian di ruang Fourier, hanya varians yang dibalik. Itu sebabnya mereka mengambil sampel dari randn dan kemudian mengalikannya dengan varians. Kemudian mereka menghasilkan alfa yang hanya merupakan sub-prosedur untuk menemukan ztest. Pada dasarnya prediksi kernel normal seperti,

ztest=K(xtest,x)(K(x,x)+λI)1y.

ztest=Φ(xtest)TΦ(x)(Φ(x)TΦ(x)+λI)1y.

Φ()

Komentar sampingan: Haruskah Anda menggunakannya? Jawabannya tidak jelas ya. Tergantung sepenuhnya pada apa yang Anda modelkan. Penggunaan ruang Fourier belum tentu sesuai untuk kernel invarian non-stasioner non-stasioner. Orang-orang tidak pernah mengklaim itu akan berhasil dalam pengaturan ini tetapi jika Anda baru memulai di daerah itu kadang-kadang nuansa tidak jelas.

j__
sumber
5
Butuh waktu sedetik untuk menyadari bahwa komputasi alfa di sini menyelesaikan masalah regresi ridge dalam X dan y dengan regularizer lambda. Jika Anda datang dari dokter kemudian melihat formula Anda ini agak jelas, datang dari sudut SVM itu sedikit membingungkan. "Prediksi kernel normal" Anda adalah GP dengan derau yang ditambahkan, alias regresi ridge kernel.
Andreas Mueller
1
@ AndreasMueller ya maaf itu benar! Saya sangat banyak dari komunitas GP awalnya jadi kadang-kadang mengabaikan itu! Senang Anda mendapatkan apa yang saya maksudkan :)
j__
1
@ j__, jika Anda punya waktu, saya punya pertanyaan tentang RFF di sini: stats.stackexchange.com/questions/440633 . Kedengarannya seperti jawaban untuk pertanyaan saya adalah lebih memahami RKHS dan teorema representer.
gwg