ENID
Lensa ML

Cara Kerja Monte Carlo

Langkah 1 dari 6: Random Sampling

Mengambil pengamatan dari sebuah distribusi

Jumlah sampel (N)30
0.00.10.20.30.40.50.60.70.80.91.0NilaiJumlahrata-rata=0.556
N sampel
30
Rata-rata
0.5561
Simpangan baku
0.2672

Dengan lebih banyak sampel, histogram mulai terlihat seperti distribusi seragam, dan rata-rata makin dekat ke 0,5.

Geser Jumlah sampel (N) dari 5 sampai 200. Tiap nilai berasal dari generator pseudo-random, yaitu rumus deterministik yang output-nya terlihat seragam pada [0, 1], jadi N yang sama selalu menghasilkan histogram yang sama. Library sungguhan memakai generator seperti Mersenne Twister atau PCG, dengan seed agar eksperimen bisa diulang. Sampel dari distribusi lain dibangun dari nilai seragam ini. Misalnya, inverse transform sampling mengubah nilai seragam u menjadi −ln(1 − u)/λ, yaitu sampel eksponensial dengan laju λ, dengan membalik CDF distribusi itu.

Langkah 2 dari 6: Hukum Bilangan Besar

Rata-rata sampel konvergen ke rata-rata sebenarnya

Jumlah sampel (N)50
0.5 ± 0.050.20.350.50.650.8Nomor sampelRata-rata berjalan
N
50
Rata-rata berjalan
0.4594
Rata-rata sebenarnya
0.5000
Error
0.0406

Rata-rata berjalan mulai tenang dan mendekati 0,5. Fluktuasinya mengecil, tetapi estimasinya masih berkeliaran di sekitar nilai sebenarnya.

Geser Jumlah sampel (N) dari 1 sampai 500 dan ikuti rata-rata berjalan menuju garis putus-putus di 0,5. Dengan seluruh 500 sampel, nilainya mencapai 0,485. Hukum bilangan besar adalah jaminan di balik semua metode Monte Carlo: nilai harapan E[f(X)] apa pun bisa diestimasi dengan merata-ratakan f atas sampel, selama nilai harapannya berhingga. Namanya berasal dari kasino Monte Carlo. Stanislaw Ulam dan John von Neumann mengembangkan metode ini di Los Alamos pada 1940-an untuk masalah difusi neutron, dan Metropolis serta Ulam menerbitkannya pada 1949.

Langkah 3 dari 6: Mengestimasi π

Lempar anak panah untuk mendekati luas lingkaran

Jumlah anak panah (N)50
011xydi dalamdi luar
N anak panah
50
Di dalam
40
Estimasi π (klik)
3.2000
Error
0.0584

Dengan lebih banyak anak panah, estimasinya membaik. Seperempat lingkaran berjari-jari 1 punya luas π/4, jadi 4 kali rasio titik di dalam mengestimasi π.

Geser Jumlah anak panah (N) dari 10 sampai 300, lalu klik kartu Estimasi π untuk melihat hitungannya. Tiap anak panah adalah titik (x, y) yang diambil secara seragam di persegi satuan, dan dihitung di dalam jika x² + y² ≤ 1. Jadi tiap anak panah adalah percobaan ya/tidak yang berhasil dengan probabilitas π/4 ≈ 0.785. Dengan titik-titik ini, 50 anak panah menghasilkan 3,20 dan 300 menghasilkan 3,147. Rumus deret menghitung π jauh lebih cepat. Contoh ini berguna karena uji keanggotaan yang sama bisa mengestimasi luas atau volume apa pun, termasuk bentuk yang tidak punya rumus.

Langkah 4 dari 6: Integrasi Monte Carlo

Mendekati integral dengan random sampling

Jumlah sampel (N)30
Estimasi = (1/N) × Σ f(xᵢ) dengan xᵢ ~ Uniform[0,1]est2/πxf(x) = sin(πx)00.5100.250.50.751
N
30
Estimasi (klik)
0.6256
Nilai sebenarnya (klik)
0.6366
Error
0.0110

Dengan sedikit sampel, tiap nilai x acak menyumbang estimasi integral yang masih kasar. Rata-rata nilai f(xᵢ) hanya pendekatan kasar untuk luas di bawah sin(πx).

Geser Jumlah sampel (N) dari 10 sampai 300, lalu klik kartu Estimasi untuk melihat hitungannya. Estimatornya ∫ f(x) dx ≈ (b − a) · (1/N) Σ f(xᵢ), dengan xᵢ seragam pada [a, b]. Di sini [a, b] = [0, 1], jadi hasilnya cukup rata-rata sin(πxᵢ): 0,626 pada N = 30 dan 0,629 pada N = 300, dibandingkan 2/π ≈ 0.637. Di satu dimensi, aturan grid sederhana lebih unggul. Keunggulan Monte Carlo muncul di banyak dimensi: 10 titik grid per sumbu di 100 dimensi membutuhkan 10¹⁰⁰ evaluasi.

Langkah 5 dari 6: Importance Sampling

Ambil sampel dengan lebih cerdas, bukan lebih banyak

Jumlah sampel (N)40
Pusat proposal0.70
targetproposal00.250.50.751seragamx
N
40
Est. seragam
0.920
Est. importance
0.945
Rasio varians
0.08

Distribusi proposal sangat cocok dengan puncak target. Importance sampling memusatkan sampel di tempat nilai target besar, sehingga variansnya lebih kecil dibanding sampling seragam.

Geser Pusat proposal dari 0 sampai 1 dan Jumlah sampel (N) dari 10 sampai 200. Targetnya Gaussian sempit di 0,7 dengan σ = 0.15, jadi integral pada [0, 1] sekitar 0,977. Proposal-nya Gaussian dengan σ = 0.2, dipotong ke [0, 1] dan dinormalisasi ulang. Dengan proposal berpusat di 0,7 dan 200 sampel, estimasinya 0,973 dengan varians sekitar sepersepuluh varians seragam. Sampel diambil dari proposal q, dan masing-masing mendapat bobot w = p(x)/q(x), yang mengoreksi pengambilan sampel di tempat yang salah: E_p[f] = E_q[f · p/q]. Kartu Rasio varians membagi varians importance sampling dengan varians sampling seragam, jadi nilai di bawah 1 berarti proposal-nya membantu. Off-policy reinforcement learning, termasuk PPO, memakai rasio yang sama.

Langkah 6 dari 6: MCMC: Metropolis-Hastings

Random walk yang mengambil sampel dari distribusi apa pun

Step size0.80
Jumlah langkah (N)100
-1-100112233awalditerimaditolak
N langkah
100
Diterima
74
Laju terima
74%
Rata-rata rantai
1.4, 0.9

Keseimbangan yang baik. Rantai cukup sering menerima usulan untuk terus bergerak, dan langkahnya cukup panjang untuk menjangkau target dengan cepat.

Geser Step size dari 0,1 sampai 2,0 dan Jumlah langkah (N) dari 10 sampai 200. Rantai mulai dari (0, 0) dan menargetkan Gaussian 2D yang berpusat di (1, 1) dengan σ = 0.8. Setiap langkah mengusulkan gerakan acak dan menerimanya dengan probabilitas min(1, p(new)/p(current)). Hanya rasio itu yang dibutuhkan, sehingga konstanta normalisasi saling menghapus. Karena itulah MCMC bisa mengambil sampel dari posterior Bayesian yang suku evidence-nya tidak diketahui. Langkah-langkah awal masih dipengaruhi titik mulai dan biasanya dibuang sebagai burn-in. Untuk proposal random walk berdimensi tinggi, teori menyarankan laju penerimaan sekitar 23%.

Apa itu metode Monte Carlo?

Metode Monte Carlo mengestimasi suatu besaran dengan random sampling: ambil banyak input acak, hitung sesuatu untuk tiap input, lalu rata-ratakan hasilnya. Integral, nilai harapan, atau probabilitas yang sulit dihitung secara eksak bisa didekati dengan cara ini, dan estimasinya membaik seiring jumlah sampel bertambah.

Machine learning memakai sampling di mana-mana. Stochastic gradient descent mengestimasi gradient penuh dari mini-batch acak, dropout mengambil subnetwork acak di setiap langkah training, dan model bahasa menghasilkan teks dengan mengambil sampel token berikutnya. Metode Bayesian memakai Markov chain Monte Carlo (MCMC) untuk mengambil sampel dari posterior, dan reinforcement learning mengestimasi expected return dengan merata-ratakan episode hasil sampling.

Ide utama

  • Estimasi Monte Carlo mengganti nilai harapan dengan rata-rata atas sampel acak.
  • Hukum bilangan besar menjamin rata-rata sampel konvergen ke nilai harapan.
  • Integral apa pun bisa ditulis sebagai nilai harapan dan diestimasi dengan sampling.
  • Laju konvergensi Monte Carlo tidak bergantung pada jumlah dimensi, berbeda dengan metode grid.
  • Importance sampling mengambil sampel dari proposal q dan memberi tiap sampel bobot p/q.
  • MCMC membangun random walk yang distribusi jangka panjangnya adalah target, hanya dengan rasio probabilitas.

Pertanyaan umum

Apa bedanya Monte Carlo dan MCMC?

Monte Carlo biasa mengambil sampel independen langsung dari distribusinya. MCMC dipakai untuk distribusi yang tidak bisa disampel langsung: metode ini menjalankan rantai Markov yang sampelnya pada akhirnya mengikuti target. Sampel MCMC saling berkorelasi, jadi 1.000 sampel membawa informasi lebih sedikit daripada 1.000 pengambilan independen. Selisih ini diukur dengan effective sample size.

Apa itu rejection sampling?

Rejection sampling mengambil x dari proposal sederhana q, dengan M·q(x) ≥ p(x) di semua titik, lalu menyimpan x dengan probabilitas p(x) / (M·q(x)). Sampel yang disimpan mengikuti p secara tepat. Sebagian besar proposal terbuang ketika M besar, dan ini umum terjadi di dimensi tinggi.

Apakah angka pseudo-random cukup baik untuk Monte Carlo?

Untuk hampir semua pekerjaan ML dan simulasi, ya. Generator modern lolos uji statistik yang ketat, dan seed yang tetap membuat hasil bisa direproduksi. Barisan quasi-random seperti titik Sobol melangkah lebih jauh dengan sengaja menyebarkan titik secara merata, sehingga error lebih rendah untuk integran yang mulus.

Apa itu reparameterization trick?

Sampel z yang diambil dari N(μ, σ²) tidak punya gradient terhadap μ dan σ. Dengan menuliskannya sebagai z = μ + σ·ε, dengan ε diambil dari N(0, 1), keacakan berpindah ke ε, sehingga gradient bisa mengalir melalui μ dan σ. VAE mengandalkan ini untuk melatih encoder-nya dengan estimasi Monte Carlo dari loss.

Penjelasan terkait

Referensi

  1. Metropolis & Ulam (1949), "The Monte Carlo Method", Journal of the American Statistical Association
  2. Metropolis et al. (1953), "Equation of State Calculations by Fast Computing Machines", Journal of Chemical Physics
  3. Hastings (1970), "Monte Carlo Sampling Methods Using Markov Chains and Their Applications", Biometrika
  4. MacKay (2003), "Information Theory, Inference, and Learning Algorithms", chapters 29–30

Terakhir diperbarui