Kapan menggunakan keturunan Gradient vs Monte Carlo sebagai teknik optimasi numerik

11

Ketika satu set persamaan tidak dapat diselesaikan secara analitis, maka kita dapat menggunakan algoritma gradient descent. Tetapi tampaknya ada juga metode simulasi Monte Carlo yang dapat digunakan untuk menyelesaikan masalah yang tidak memiliki solusi analitis.

Bagaimana cara mengetahui kapan harus menggunakan gradient descent dan kapan menggunakan Monte Carlo? Atau apakah saya hanya membingungkan istilah 'simulasi' dengan 'optimasi'?

Terima kasih banyak!

monte-carlo gradient-descent Pemenang
sumber

Jawaban:

4

Teknik-teknik ini melakukan hal yang berbeda.

Gradient descent adalah teknik optimasi, oleh karena itu umum dalam setiap metode statistik yang memerlukan maksimalisasi (MLE, MAP).

Simulasi Monte Carlo adalah untuk menghitung integral dengan mengambil sampel dari distribusi dan mengevaluasi beberapa fungsi pada sampel. Oleh karena itu umumnya digunakan dengan teknik yang memerlukan perhitungan harapan (Bayesian Inference, Bayesian Hypothesis Testing).

jlimahaverford
sumber
Jadi gradient descent terhubung dengan diferensiasi (maxima, minima) dan monte carlo dikaitkan dengan integrasi?
Victor
Gradien adalah generalisasi turunan. Jadi gradient descent dikaitkan dengan diferensiasi. Tetapi saya akan mengatakan, "Gradient Descent menggunakan turunannya demi optimasi" dan "Monte Carlo menggunakan sampling demi integrasi," jika saya harus menggunakan sesedikit mungkin kata.
jlimahaverford
4

Ini adalah keluarga besar algoritma, jadi sulit untuk memberikan jawaban yang tepat, tetapi ...

Gradient ascent (atau descent) berguna ketika Anda ingin menemukan maksimum (atau minimum). Misalnya, Anda mungkin menemukan mode distribusi probabilitas, atau kombinasi parameter yang meminimalkan beberapa fungsi kerugian. "Jalur" yang diperlukan untuk menemukan ekstrem ini dapat memberi tahu Anda sedikit tentang keseluruhan bentuk fungsi, tetapi tidak dimaksudkan untuk itu; pada kenyataannya, semakin baik kerjanya, semakin sedikit Anda akan tahu tentang segala sesuatu kecuali ekstrem.

Metode Monte Carlo diberi nama setelah kasino Monte Carlo karena mereka, seperti kasino, bergantung pada pengacakan. Ini dapat digunakan dalam banyak cara yang berbeda, tetapi sebagian besar fokus pada perkiraan distribusi. Algoritma Markov Chain Monte Carlo, misalnya, menemukan cara untuk mengambil sampel secara efisien dari distribusi probabilitas yang rumit. Simulasi Monte Carlo lainnya mungkin menghasilkan distribusi lebih dari hasil yang mungkin.

Matt Krause
sumber
"Metode Monte Carlo" biasanya merujuk pada apa yang Anda lakukan dengan sampel sebagai kebalikan dari metode untuk mendapatkan sampel. Dalam MCMC "Rantai Markov" mengacu pada proses pengambilan sampel.
jlimahaverford
Betulkah? Saya selalu berpikir bahwa Monte Carlo menyiratkan bahwa ada semacam pengacakan yang terjadi dan tidak berarti lebih dari itu. Dalam MCMC, memang benar bahwa Markov Chains terlibat, tetapi Anda juga mengambil sampel secara acak dari rantai (karenanya. Monte-Carlo) /
Matt Krause
Mungkin ini masalah pendapat. Jika saya menggunakan MCMC untuk memperkirakan rata-rata distribusi posterior, saya akan menggunakan jalan acak pada Rantai Markov untuk sekitar sampel dari distribusi non-normal, saya akan menggunakan Integrasi Monte Carlo untuk memperkirakan rata-rata. Saya menganggap metode pengambilan sampel sebagai alat yang memungkinkan metode Monte Carlo. Sebagai contoh, saya tidak akan menyebut sampel penolakan metode Monte Carlo, tapi saya bisa membayangkan seseorang menggunakannya bersama-sama.
jlimahaverford
Semua itu dikatakan, Wikipedia tidak mempertimbangkan sampel penolakan metode Monte Carlo. Jadi sangat mungkin bahwa ide saya di sini benar-benar salah.
jlimahaverford
2

Seperti dijelaskan oleh orang lain, gradient descent / ascent melakukan optimasi, yaitu menemukan maksimum atau minimum suatu fungsi. Monte Carlo adalah metode simulasi stokastik, yaitu mendekati fungsi distribusi kumulatif melalui pengambilan sampel acak berulang. Ini juga disebut "integrasi Monte Carlo" karena cdf dari distribusi kontinu sebenarnya merupakan bagian integral.

Apa yang umum antara gradient descent dan Monte Carlo adalah keduanya sangat berguna dalam masalah di mana tidak ada solusi bentuk tertutup. Anda dapat menggunakan diferensiasi sederhana untuk menemukan titik maksimum atau minimum dari setiap fungsi cembung setiap kali solusi analitis layak. Ketika solusi seperti itu tidak ada, Anda perlu menggunakan metode iteratif seperti gradient descent. Apakah sama untuk simulasi Monte Carlo; Anda pada dasarnya dapat menggunakan integrasi sederhana untuk menghitung cdf apa pun secara analitis tetapi tidak ada jaminan bahwa solusi bentuk tertutup seperti itu akan selalu dimungkinkan. Masalahnya menjadi terpecahkan lagi dengan simulasi Monte Carlo.

Bisakah Anda menggunakan gradient descent untuk simulasi dan Monte Carlo untuk optimasi? Jawaban sederhananya adalah tidak. Monte Carlo membutuhkan elemen stokastik (distribusi) untuk mengambil sampel dan gradient descent tidak memiliki cara untuk menangani masalah informasi stokastik. Anda dapat, bagaimanapun, menggabungkan simulasi dengan optimasi untuk menghasilkan algoritma optimasi stokastik yang lebih kuat yang mampu memecahkan masalah yang sangat kompleks yang tidak dapat diselesaikan oleh penurunan gradien sederhana. Contohnya adalah Simulasi Annealing Monte Carlo.

Digio
sumber
2

Jawaban ini sebagian salah. Anda memang bisa menggabungkan metode Monte Carlo dengan gradient descent. Anda dapat menggunakan metode Monte Carlo untuk memperkirakan gradien dari fungsi kerugian, yang kemudian digunakan oleh penurunan gradien untuk memperbarui parameter. Metode Monte Carlo yang populer untuk memperkirakan gradien adalah estimator gradien skor , yang dapat misalnya digunakan dalam pembelajaran penguatan. Lihat Estimasi Gradien Monte Carlo dalam Pembelajaran Mesin (2019) oleh Shakir Mohamed et al. untuk info lebih lanjut.

nbro
sumber