Skip to content
Kembali ke hasil pencarian

Teknik Pengurangan Varians untuk Simulasi Monte Carlo

Diperkenalkan oleh
Hammersley & Morton (antithetic variates, 1956); Lavenberg & Welch (control variates, 1981); importance sampling roots in Kahn & Marshall (1953)
Tahun
1950s–1980s (technique family)
Jenis
Simulation variance-reduction technique family

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Teknik pengurangan varians adalah keluarga metode yang meningkatkan efisiensi simulasi Monte Carlo dengan mencapai akurasi estimasi yang sama dengan lebih sedikit penarikan acak.

Dikembangkan secara bertahap mulai tahun 1950-an — dengan variat antitetik yang diatribusikan kepada Hammersley dan Morton, variat kontrol yang diformalkan oleh Lavenberg dan Welch, dan sampling kepentingan yang berakar pada Kahn dan Marshall — keluarga ini mencakup variat antitetik (AV), variat kontrol (CV), sampling kepentingan (IS), dan stratifikasi, yang masing-masing memanfaatkan sifat struktural yang berbeda dari kuantitas target untuk menurunkan varians estimator tanpa menimbulkan bias.

Intuisi di balik metode

Monte Carlo standar bekerja dengan merata-ratakan sejumlah besar penarikan acak independen. Kelemahannya adalah penarikan acak murni dapat menjadi redundan — banyak penarikan mendarat di wilayah yang memberikan sedikit informasi, dan kesalahan positif dan negatif tidak saling meniadakan secara efisien. Teknik pengurangan varians memperbaiki ini dengan merekayasa keacakan. Variat antitetik memasangkan setiap penarikan dengan citra cerminnya sehingga kesalahan cenderung saling meniadakan; variat kontrol menyesuaikan estimasi menggunakan kuantitas yang berkorelasi yang rata-rata sebenarnya diketahui; sampling kepentingan memusatkan penarikan di tempat yang paling penting; dan stratifikasi memastikan sampling mencakup ruang input secara merata. Imbalannya adalah akurasi yang sama dengan evaluasi fungsi yang jauh lebih sedikit.

Sejarah

Dasar-dasar pengurangan varians untuk simulasi Monte Carlo diletakkan pada tahun 1950-an. Kahn dan Marshall (1953) memperkenalkan sampling kepentingan dalam konteks transportasi partikel nuklir. Hammersley dan Morton (1956) memformalkan variat antitetik sebagai cara untuk memanfaatkan simetri dalam input acak. Variat kontrol disistematisasi oleh Lavenberg dan Welch pada tahun 1980-an untuk digunakan dalam simulasi stokastik. Monograf Paul Glasserman tahun 2003 menyatukan teori dan praktik teknik-teknik ini untuk rekayasa keuangan, dan buku teks Sheldon Ross tentang simulasi sejak itu menjadikannya bagian standar dari pendidikan simulasi pascasarjana. Saat ini teknik-teknik tersebut menjadi pusat dalam keuangan komputasi, rekayasa keandalan, dan bidang apa pun di mana run simulasi mahal.

Kapan digunakan

Gunakan teknik pengurangan varians ketika Monte Carlo standar hanya memberikan akurasi yang dapat diterima pada jumlah run yang tidak praktis besar. AV cocok untuk integrand yang mulus dan monoton; CV cocok untuk masalah di mana kuantitas bantu yang berkorelasi dengan rata-rata yang diketahui tersedia; IS cocok untuk estimasi kejadian langka atau integrasi di atas ekor yang berat; stratifikasi cocok untuk ruang input berdimensi rendah. Semua teknik memerlukan setidaknya beberapa ratus — idealnya beberapa ribu — iterasi sebelum manfaat pengurangan varians terlihat. Teknik ini sesuai untuk kuantitas acak kontinu dan untuk domain aplikasi apa pun di mana biaya simulasi adalah kendala pengikat.

Batasan dan pertimbangan

  • Setiap teknik memerlukan pengetahuan struktural tentang masalah: AV membutuhkan integrand yang monoton, CV membutuhkan rata-rata bantu yang diketahui secara analitis, IS membutuhkan distribusi proposal yang dirancang dengan baik.
  • Distribusi proposal yang dipilih dengan buruk untuk sampling kepentingan dapat meningkatkan varians alih-alih menguranginya.
  • Menggabungkan beberapa teknik meningkatkan kompleksitas implementasi dan dapat berinteraksi dengan cara yang tidak terduga.
  • Manfaat pengurangan varians dapat diabaikan pada jumlah iterasi yang sangat rendah (di bawah ~1.000 run).

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Secara substansial mengurangi jumlah run simulasi yang diperlukan untuk mencapai akurasi target, menurunkan biaya komputasi.
  • Teknik dapat digabungkan (misalnya, AV dengan CV) untuk pengurangan varians gabungan.
  • Tidak ada bias yang diperkenalkan: semua teknik standar menghasilkan estimator yang tidak bias.
  • Berlaku luas di berbagai domain — keuangan, teknik, perawatan kesehatan, riset operasi — di mana pun integrasi Monte Carlo digunakan.

Penerapan

  • Penetapan harga opsi dalam keuangan komputasi, di mana sampling kepentingan memusatkan penarikan pada jalur in-the-money.
  • Analisis keandalan dan risiko, di mana probabilitas kegagalan langka diestimasi dengan lebih sedikit run simulasi menggunakan IS.
  • Analisis kinerja sistem antrian dan layanan menggunakan AV dan CV untuk mengurangi panjang run.
  • Simulasi efektivitas biaya perawatan kesehatan, di mana CV memanfaatkan aproksimasi analitik yang diketahui untuk model biaya.
  • Desain teknik di bawah ketidakpastian, di mana sampling bertingkat memastikan cakupan di seluruh ruang parameter input.

Cara kerjanya

Cara kerjanya

1

Mulai dengan mengekspresikan kuantitas yang diminati sebagai ekspektasi — misalnya, rata-rata fungsi yang diterapkan pada input acak. Kerangka kerja ini memperjelas dari distribusi probabilitas mana sampel berasal dan seperti apa estimator Monte Carlo mentah sebelum pengurangan varians diterapkan.

2

Pilih teknik yang sesuai dengan struktur masalah. Variat antitetik bekerja ketika integrand monoton terhadap input, sehingga memasangkan setiap penarikan uniform u dengan komplemennya 1 − u menjamin korelasi negatif dan pembatalan kesalahan. Variat kontrol bekerja ketika kuantitas yang berkorelasi dengan ekspektasi analitik yang diketahui ada; estimator disesuaikan dengan perbedaan antara rata-rata simulasi kontrol dan rata-rata yang diketahui. Sampling kepentingan bekerja ketika probabilitas kejadian langka atau berbobot tinggi perlu ditingkatkan; distribusi proposal yang lebih berat di ekor menggantikan yang asli, dan setiap sampel diberi bobot ulang berdasarkan rasio kemungkinan. Stratifikasi membagi ruang input menjadi strata dan mengalokasikan penarikan secara proporsional, memastikan tidak ada wilayah yang terlalu banyak atau terlalu sedikit disampling. Teknik dapat digabungkan — misalnya, CV dan AV bersama-sama — untuk penghematan tambahan.

3

Tarik sampel sesuai dengan teknik yang dipilih. Untuk AV, hasilkan pasangan penarikan (u, 1 − u); untuk IS, tarik dari distribusi proposal dan catat bobot kepentingan; untuk stratifikasi, tarik di dalam setiap strata. Jumlah iterasi setidaknya harus ribuan agar manfaat pengurangan varians dapat diukur.

4

Agregasikan sampel menjadi estimasi titik dan estimasi varians. Untuk AV, estimator adalah rata-rata dari nilai fungsi yang dipasangkan. Untuk CV, rata-rata mentah dikoreksi oleh koefisien optimal dikalikan dengan deviasi rata-rata sampel kontrol dari ekspektasi yang diketahui. Untuk IS, setiap evaluasi fungsi dikalikan dengan bobot kepentingannya sebelum dirata-ratakan.

5

Bandingkan varians estimator yang dikurangi variansnya terhadap varians estimator Monte Carlo biasa pada jumlah penarikan yang sama. Rasio kedua varians — faktor pengurangan varians — mengukur keuntungan. Jika faktornya mendekati 1, teknik tersebut tidak memanfaatkan struktur masalah dan pendekatan yang berbeda atau iterasi lebih lanjut mungkin diperlukan.

Kesalahan umum

  • Menggunakan variat antitetik ketika integrand tidak monoton terhadap input: asumsi korelasi negatif rusak dan metode tersebut sebenarnya dapat meningkatkan varians.
  • Menggunakan distribusi proposal sampling kepentingan yang memiliki ekor lebih ringan daripada target: kejadian langka kurang disampling dan varians estimator dapat meledak.
  • Mengestimasi koefisien CV dari sampel yang sama yang digunakan untuk estimator tanpa memperhitungkan bias yang diinduksi pada ukuran sampel kecil.
  • Menjalankan iterasi terlalu sedikit (di bawah ~1.000): faktor pengurangan varians tidak dapat diukur secara andal, dan manfaat dibandingkan Monte Carlo biasa tidak terlihat.
  • Menggabungkan AV dan CV tanpa memverifikasi bahwa kombinasi tersebut mempertahankan korelasi negatif: estimator gabungan mungkin tidak mencapai penghematan yang diharapkan.

Pertanyaan yang sering diajukan

Teknik mana yang harus saya pilih — AV, CV, IS, atau stratifikasi?

Pilih berdasarkan struktur masalah Anda. Jika integrand monoton terhadap input, AV lugas dan efektif. Jika Anda memiliki kuantitas terkait yang ekspektasinya dapat Anda hitung secara analitis, CV biasanya merupakan pilihan yang paling kuat. Jika Anda perlu mengestimasi probabilitas kejadian langka atau mengintegrasikan di atas ekor yang berat, IS adalah alat yang tepat. Stratifikasi bekerja dengan baik dalam dimensi rendah hingga sedang ketika Anda menginginkan cakupan ruang input yang seragam. Teknik juga dapat digabungkan untuk keuntungan tambahan.

Berapa banyak run simulasi yang saya butuhkan?

Manfaat pengurangan varians hanya dapat diukur setelah Anda memiliki setidaknya beberapa ratus run; beberapa ribu adalah ambang batas yang lebih andal. Dengan iterasi yang sangat sedikit, faktor pengurangan varians tidak dapat diestimasi secara stabil, dan estimator Monte Carlo biasa sebenarnya dapat berkinerja sebanding. Sebagai aturan praktis, jangan gunakan teknik ini dengan kurang dari 1.000 iterasi.

Bisakah teknik pengurangan varians menimbulkan bias?

Tidak — keempat teknik standar (AV, CV, IS, stratifikasi) menghasilkan estimator yang tidak bias jika diimplementasikan dengan benar. Estimator CV memang memerlukan estimasi yang akurat dari koefisien optimal; mengestimasinya dari sampel pilot kecil dan menggunakan kembali sampel yang sama untuk estimasi utama dapat menimbulkan bias sampel terbatas yang kecil, jadi praktik terbaiknya adalah menggunakan pilot terpisah atau formula koefisien yang valid secara asimtotik.

Apa yang terjadi jika proposal sampling kepentingan saya dipilih dengan buruk?

Distribusi proposal yang terlalu ringan di ekor relatif terhadap target dapat menyebabkan peningkatan varians yang katastropik, membuat IS lebih buruk daripada Monte Carlo biasa. Selalu verifikasi bahwa proposal memiliki ekor yang lebih berat daripada target di wilayah yang relevan, dan periksa varians bobot kepentingan sebagai diagnostik — nilai bobot yang sangat besar menandakan proposal yang buruk.

Metode terkait

Sumber

  1. Ross, S.M. (2012). Simulation (5th ed.). Academic Press.

    ISBN: 978-0124158252
    Disalin.
  2. Glasserman, P. (2003). Monte Carlo Methods in Financial Engineering. Springer.

    Buka referensi DOI
    Disalin.