Matriks kovarians yang dikondisikan buruk dalam regresi GP untuk optimisasi Bayesian

12

Latar belakang dan masalah

Saya menggunakan Proses Gaussian (GP) untuk regresi dan optimasi Bayesian berikutnya (BO). Untuk regresi saya menggunakan paket gpml untuk MATLAB dengan beberapa modifikasi custom-made, tetapi masalahnya umum.

Adalah fakta yang diketahui bahwa ketika dua input pelatihan terlalu dekat dalam ruang input, matriks kovarians dapat menjadi tidak-pasti pasti (ada beberapa pertanyaan tentang hal itu di situs ini). Akibatnya, dekomposisi Cholesky dari matriks kovarians, yang diperlukan untuk berbagai perhitungan GP, ​​dapat gagal karena kesalahan numerik. Ini terjadi pada saya dalam beberapa kasus ketika melakukan BO dengan fungsi objektif yang saya gunakan, dan saya ingin memperbaikinya.

Solusi yang diajukan

AFAIK, solusi standar untuk mengurangi pengondisian udara adalah dengan menambahkan punggungan atau nugget ke diagonal matriks kovarians. Untuk regresi GP, jumlah ini untuk menambahkan (atau meningkatkan, jika sudah ada) kebisingan pengamatan.

Sejauh ini baik. Saya memodifikasi kode untuk inferensi yang tepat dari gpml sehingga setiap kali dekomposisi Cholesky gagal, saya mencoba untuk memperbaiki matriks kovarians ke matriks SPD (simetrik positif pasti terdekat) dalam norma Frobenius, yang terinspirasi oleh kode MATLAB oleh John d'Errico. Alasannya adalah untuk meminimalkan intervensi pada matriks asli.

Solusi ini berfungsi, tetapi saya perhatikan bahwa kinerja BO berkurang secara substansial untuk beberapa fungsi - mungkin setiap kali algoritma perlu memperbesar di beberapa area (misalnya, karena semakin dekat ke minimum, atau karena panjangnya skala dari masalah menjadi tidak seragam kecil). Perilaku ini masuk akal karena saya secara efektif meningkatkan kebisingan setiap kali dua titik input terlalu dekat, tetapi tentu saja itu tidak ideal. Atau, saya bisa saja menghilangkan titik-titik bermasalah, tetapi sekali lagi, kadang-kadang saya membutuhkan titik input untuk menjadi dekat.

Pertanyaan

Saya tidak berpikir bahwa masalah numerik dengan faktorisasi Cholesky dari matriks kovarian GP adalah masalah baru, tetapi yang mengejutkan saya sejauh ini saya tidak dapat menemukan banyak solusi, selain meningkatkan kebisingan atau menghilangkan titik yang terlalu dekat satu sama lain. Di sisi lain, memang benar bahwa beberapa fungsi saya berperilaku sangat buruk, jadi mungkin situasi saya tidak terlalu khas.

Adakah saran / referensi yang bisa berguna di sini?

Lacerbi
sumber
Anda mungkin melihat ke dalam pembentukan entri matriks kovarians, serta menghitung atau memperbarui faktorisasi Cholesky-nya, dalam presisi yang lebih tinggi, misalnya, presisi quad atau bahkan lebih tinggi. Selain dari kerumitan, kalkulasi mungkin order lebih lambat lebih lambat. Ada add-ons presisi yang sewenang-wenang untuk MATLAB. Saya tidak mengatakan ini ideal, tetapi ini bisa menjadi pilihan. Saya tidak tahu seberapa baik mereka bermain dengan gpml, tetapi jika Anda dapat mengubah kode sumber gpml (file m), mungkin Anda bisa melakukannya.
Mark L. Stone
Apakah Anda mencoba menambahkan jitter kecil ke diagonal dari matriks kovarians?
Zen
@ MarkL.Stone Terima kasih atas sarannya. Sayangnya saya perlu kode pelatihan untuk menjadi cepat, jadi angka-angka presisi tinggi mungkin tidak akan menjadi pilihan yang baik untuk aplikasi saya.
lacerbi
2
Pertanyaan ini sangat menarik. Saat menambahkan efek nugget ke matriks kovaraince Anda seperti lakukan Anda mengoptimalkan sigma dalam kemungkinan Anda, atau apakah diberikan. Saya perhatikan bahwa mengoptimalkan efek nugget menangkap noise pengukuran dan membantu dia memproses gaussσσ2Iσ
Wis
1
Saya biasanya mengoptimalkan. Dalam beberapa kasus saya mencoba meminggirkannya, tetapi tidak mendapatkan banyak perbaikan optimasi wrt (saya berasumsi posterior sangat sempit).
lacerbi

Jawaban:

7

Pilihan lain adalah untuk rata-rata poin yang menyebabkan - misalnya jika Anda memiliki 1000 poin dan 50 masalah menyebabkan, Anda bisa mengambil pendekatan peringkat rendah yang optimal menggunakan 950 nilai eigen / vektor pertama. Namun, ini tidak jauh menghapus datapoints berdekatan yang Anda katakan Anda lebih suka tidak melakukannya. Harap diingat bahwa saat Anda menambahkan jitter, Anda mengurangi derajat kebebasan - yaitu setiap titik memengaruhi prediksi Anda lebih sedikit, jadi ini bisa lebih buruk daripada menggunakan lebih sedikit poin.

dxk(x,x)dxdxk(x,x)

Edit:

Berdasarkan komentar saya pikir saya akan menguraikan apa yang saya maksud dengan memasukkan pengamatan turunan. Jika kita menggunakan kernel gaussian (sebagai contoh),

kx,x=k(x,x)=σexp((xx)2l2)

turunannya adalah,

kdx,x=dk(x,x)dx=2(xx)l2σexp((xx)2l2)

kdx,dx=d2k(x,x)dxdx=2l22(xx)l4σexp((xx)2l2)

{xi,yi;i=1,...,n}x1m1

Y=[m1,y1,,yn]

K=(kdx0,dx0kdx0,x0kdx0,xnkdx0,x0kx0,x0kx0,xnkdx0,xnkx0,xnkxn,xn)

Sisa GP adalah sama seperti biasanya.

j__
sumber
Apakah Anda ingin memperluas detail tentang usulan penggunaan informasi perkiraan gradien?
Mark L. Stone
@ j Terima kasih - Saya berpikir untuk melakukan pendekatan peringkat rendah, saya mungkin mencobanya (menghindarinya sejauh ini karena saya mungkin harus menulis ulang sebagian besar kode). Mengenai menggabungkan dua poin menjadi satu, saya telah mengusulkannya dalam pertanyaan sebelumnya , tetapi saya tidak berpikir tentang mendapatkan informasi turunan. Pada prinsipnya kedengarannya rapi tetapi saya tidak yakin bagaimana saya akan menggunakannya karena saya hanya akan memiliki beberapa pengamatan turunan (sesuai dengan poin yang digabungkan), dengan beban menambahkan satu GP per dimensi input.
lacerbi
@ j Terima kasih atas penjelasan tambahannya. Ini memang terlihat sangat rapi. Apakah Anda memiliki referensi untuk pendekatan ini (atau sesuatu yang serupa)?
lacerbi
2
Lihatlah halaman tesis Mike Osborne 67 ( robots.ox.ac.uk/ ~mosb / public / pdf / 136 / full_thesis.pdf ) - ia memperkenalkan pengamatan derivatif dan integral. Semoga membantu :)
j__
4

Salah satu solusi yang telah kami lakukan di kantor adalah dengan hanya mengubah poin yang merepotkan. Ini bisa berupa penghapusan langsung atau sesuatu yang lebih canggih. Pada dasarnya, pengamatannya adalah bahwa titik-titik dekat sangat redundan: pada kenyataannya, sangat redundan sehingga mereka mengurangi pangkat matriks kovarians. Dengan cara yang sama, satu titik menyumbang sedikit informasi untuk masalah yang dihadapi, jadi menghapus satu atau yang lain (atau melakukan sesuatu yang lain, seperti rata-rata mereka atau "memantul" satu titik dari yang lain ke jarak minimal yang dapat diterima) akan tidak terlalu banyak mengubah solusi Anda.

Saya tidak yakin bagaimana cara menilai pada titik mana kedua poin menjadi "terlalu dekat." Mungkin ini bisa menjadi opsi penyetelan yang tersisa untuk pengguna.

(Ups! Setelah saya memposting ini, saya menemukan pertanyaan Anda di sini yang memajukan jawaban ini ke solusi yang jauh lebih rumit. Saya harap dengan menghubungkannya dari jawaban saya, saya akan membantu dengan SEO ...)

Sycorax berkata Reinstate Monica
sumber
ini cukup membantu, bisakah Anda juga menjelaskan hal ini jika memungkinkan.
GENIVI-LEARNER