Bagaimana cara cepat sampel X jika exp (X) ~ Gamma?

12

Saya memiliki masalah pengambilan sampel sederhana, di mana loop batin saya terlihat seperti:

v = sample_gamma(k, a)

di mana sample_gammasampel dari distribusi Gamma membentuk sampel Dirichlet.

Ini bekerja dengan baik, tetapi untuk beberapa nilai k / a, beberapa proses hilir perhitungan underflow.

Saya mengadaptasinya untuk menggunakan variabel ruang log:

v = log(sample_gamma(k, a))

Setelah mengadaptasi semua sisa program, ia bekerja dengan benar (setidaknya itu memberi saya hasil yang persis sama pada kasus uji). Namun, ini lebih lambat dari sebelumnya.

Apakah ada cara untuk langsung mencicipi tanpa menggunakan fungsi lambat seperti ? Saya mencoba googling untuk ini, tetapi saya bahkan tidak tahu apakah distribusi ini memiliki nama yang sama (log-gamma?).X,exp(X)Gammalog()

luispedro
sumber
Yang perlu Anda lakukan adalah membagi masing-masing varian gamma dengan jumlah mereka. Lalu, bagaimana cara underflow terjadi? Dan bagaimana cara mengambil logaritma memecahkan masalah ini (Anda tidak dapat menghitung jumlahnya tanpa berharap kembali lagi)?
whuber
@whuber Di ruang log, Anda menghitung jumlah dan kemudian mengurangi dari setiap elemen. Jadi, ini menghindari titik underflow pertama. Ada sedikit proses lebih lanjut ketika balon ini berfungsi sebagai komponen campuran dan dikalikan dengan jumlah kecil lagi.
luispedro
Menambahkan log secara matematis salah: ia sesuai dengan mengalikan gammas daripada menambahkannya. Ya, Anda mungkin mendapatkan hasil yang berhasil, tetapi mereka pasti tidak akan memiliki distribusi Dirichlet! Sekali lagi, apa sebenarnya sifat dari aliran bawah asli dan perhitungan apa yang Anda lakukan ketika itu terjadi? Apa nilai aktual yang Anda kerjakan?
whuber
@whuber saya mungkin telah menyederhanakan terlalu banyak dalam uraian saya. Forall i {t = gamma (a, b); jumlah + = t; d [i] = log (t)}; logsum = log (jumlah); forall i {d [i] - = logsum; }. Sebelumnya, ini underflow jika a sangat kecil.
luispedro
Mengerti: untuk dekat 0 Anda akan berada dalam masalah apa pun yang terjadi. Masalah menarik! α
whuber

Jawaban:

9

Pertimbangkan parameter bentuk kecil dekat 0, seperti . Dalam rentang antara 0 dan , kira-kira , jadi pdf Gamma kira-kira . Ini dapat diintegrasikan ke CDF perkiraan, . Menolaknya, kita melihat kekuatan : eksponen besar. Untuk ini menyebabkan kemungkinan underflow (nilai presisi ganda kurang dari , lebih atau kurang). Berikut adalah plot peluang untuk mendapatkan underflow sebagai fungsi dari basis-sepuluh logaritmaαα=1/100αeα1xα1dx/Γ(α)Fα(x)=xααΓ(α)1/αα=1/10010300α :

masukkan deskripsi gambar di sini

Salah satu solusinya adalah dengan mengeksploitasi perkiraan ini untuk menghasilkan varian log (Gamma): pada dasarnya, cobalah untuk menghasilkan variate Gamma dan jika terlalu kecil, buat logaritma dari perkiraan distribusi daya ini (seperti yang ditunjukkan di bawah). (Lakukan ini berulang kali hingga log berada dalam kisaran underflow, sehingga ini merupakan pengganti yang valid untuk varian underflow yang asli.) Untuk perhitungan Dirichlet, kurangi maksimum semua logaritma dari masing-masing nilai log: ini secara implisit mengubah semua variasi Gamma sehingga tidak akan memengaruhi nilai Dirichlet. Perlakukan setiap log yang dihasilkan yang terlalu kecil (katakanlah, kurang dari -100) sebagai log dengan nol sebenarnya. Exponentiate log lainnya. Sekarang Anda dapat melanjutkan tanpa underflow.

Ini akan memakan waktu lebih lama dari sebelumnya, tetapi setidaknya itu akan berhasil!

Untuk menghasilkan perkiraan log Gamma variate dengan parameter bentuk , precompute . Ini mudah, karena ada algoritma untuk menghitung nilai log Gamma secara langsung . Buat float acak seragam antara 0 dan 1, ambil logaritma, bagi dengan , dan tambahkan ke sana.αC=log(Γ(α))+log(α)αC

Karena parameter skala hanya mengubah skala variasinya, tidak ada masalah mengakomodasinya dalam prosedur ini. Anda bahkan tidak memerlukannya jika semua parameter skala sama.

Edit

Di balasan lain OP menjelaskan metode di mana kekuatan dari varian seragam (a variate) dikalikan dengan . Ini berfungsi karena pdf dari distribusi bersama kedua varian ini sama dengan . Untuk menemukan pdf dari kami mengganti , dibagi dengan Jacobean , dan mengintegrasikan . Integral harus berkisar dari hingga karena , dari mana1/αB(α)Γ(α+1)(αxα1)(yαeydy/Γ(α+1))z=xyyz/xxxz0y1

pdf(z)=αΓ(α+1)z(xα/x)ex(z/x)α1dxdz=1Γ(α)zα1ezdz,

yang merupakan pdf dari distribusi .Γ(α)

Intinya adalah bahwa ketika , nilai yang diambil dari tidak mungkin di-underflow dan dengan menjumlahkan log-nya dan kali log dari varian seragam independen kami akan memiliki log dari . Log cenderung sangat negatif, tetapi kita akan melewati konstruksi antilognya, yang akan melimpah dalam representasi titik mengambang.0<α<1Γ(α+1)1/αΓ(α)

whuber
sumber
1
Hanya argumen untuk membuat hasil edit Anda sedikit lebih elegan, Anda tidak perlu memohon integrasi di sini. Cukup gunakan fakta bahwa , ditambah . Ini adalah properti standar dari distribusi beta dan gamma. Juga, ketika kita memiliki kira-kira , yang mungkin lebih cepat untuk mensimulasikan ( ) daripada variabel acak umum . Γ(α)Γ(α)+Γ(1)Beta(α,1)Γ(α)+Γ(1)Γ(α+1)α0yexpo(1)log(u)Γ(α+1)
probabilityislogic
7

Saya menjawab pertanyaan saya sendiri, tetapi saya menemukan solusi yang cukup bagus, bahkan jika saya tidak sepenuhnya memahaminya. Melihat kode dari Perpustakaan Ilmiah GNU, di sini adalah bagaimana sampel variabel gamma ( radalah nomor acak generator, aadalah dan merupakan ):αbβ

  if (a < 1)
    {
      double u = gsl_rng_uniform_pos (r);
      return gsl_ran_gamma (r, 1.0 + a, b) * pow (u, 1.0 / a);
   }

gsl_ran_gammaadalah fungsi yang mengembalikan sampel gamma acak (jadi di atas adalah panggilan rekursif), sementara gsl_rng_uniform_posmengembalikan nomor yang terdistribusi secara seragam dalam ( untuk positif ketat karena dijamin tidak mengembalikan 0,0).(0,1)_pos

Oleh karena itu, saya dapat mengambil log dari ekspresi terakhir dan menggunakannya

return log(gsl_ran_gamma(r, 1.0 + a, b)) + log(u)/a;

Untuk mendapatkan apa yang saya inginkan. Saya sekarang memiliki dua log()panggilan (tetapi satu lebih sedikit pow()), tetapi hasilnya mungkin lebih baik. Sebelumnya, seperti yang ditunjukkan oleh whuber, saya memiliki sesuatu yang dinaikkan menjadi kekuatan , berpotensi banyak. Sekarang, di logspace, saya mengalikan dengan . Jadi, kecil kemungkinannya untuk underflow.1 / a1/a1/a

luispedro
sumber
Bisakah Anda menjelaskan apa yang gsl_rng_uniform_pos dan gsl_ran_gamma lakukan? Saya kira yang pertama mengembalikan nilai acak seragam antara 0 dan r dan yang kedua terkait dengan nilai Gamma (1 + a, b) - mungkin itu adalah Gamma yang tidak lengkap? Secara keseluruhan ini terlihat sangat dekat dengan perkiraan yang saya sarankan (kecuali, dalam memeriksanya, jelas saya lupa menentukan pembagian dengan bagian , yang penting!)α
whuber
Saya mengedit jawaban saya untuk memasukkan lebih detail sekarang.
luispedro
Terima kasih: tapi apa itu "r"? (Perhatikan bahwa rekursi dibatasi: paling banyak satu panggilan rekursif akan dilakukan, karena a> 0 menyiratkan 1.0 + a> 1.)
whuber
r adalah generator angka acak (dari mana Anda mendapatkan nomor acak).
luispedro
Ah, ini pintar: produk dari dan independen ternyata menjadi . Saya mengedit jawaban saya sehingga menunjuk ke solusi Anda dan menjelaskan mengapa itu berhasil. B ( α , 1 ) Γ ( α )Γ(α+1)B(α,1)Γ(α)
Whuber