apa yang dimaksud dengan integrasi numerik terlalu mahal?

12

Saya membaca tentang kesimpulan Bayesian dan saya menemukan frasa "integrasi numerik dari kemungkinan marginal terlalu mahal"

Saya tidak memiliki latar belakang matematika dan saya bertanya-tanya apa sebenarnya arti mahal di sini? Apakah hanya dalam hal kekuatan perhitungan atau ada sesuatu yang lebih.

discretetimeisnice
sumber
6
Ini berarti membutuhkan terlalu banyak daya komputasi, mungkin dalam hal waktu CPU (karena semua sumber daya komputasi pada dasarnya adalah memori atau CPU).
Sycorax berkata Reinstate Monica
3
Sebenarnya, bandwidth komunikasi dapat menjadi masalah kadang-kadang (misalnya antara cache / RAM / disk secara seri, atau antara menghitung node secara paralel).
GeoMatt22
Ini berarti bahwa terlalu banyak waktu, untuk satu komputer, kami untuk jaringan komputer, untuk melakukan perhitungan.
Jack Maddington
2
Dan jika kemungkinan marjinal diperlukan di dalam beberapa loop, yang dianggap terlalu mahal jauh lebih sedikit. Misalnya. rutinitas integrasi 1 detik terdengar cepat, tetapi mungkin "terlalu mahal" jika Anda perlu melakukannya 1 juta kali ...
Matthew Gunn
Mahal dalam hal upaya komputasi, karena di dalamnya dibutuhkan lebih banyak upaya untuk menghitungnya daripada yang Anda mampu, seperti di dalamnya membutuhkan terlalu banyak waktu, atau membutuhkan terlalu banyak prosesor untuk dilakukan dalam waktu yang wajar.
user253751

Jawaban:

16

Dalam konteks masalah komputasi, termasuk metode numerik untuk inferensi Bayesian, frasa "terlalu mahal" umumnya dapat merujuk pada dua masalah

  1. suatu tertentu masalah terlalu "besar" untuk menghitung untuk "tertentu anggaran "
  2. pendekatan umum berskala buruk, yaitu memiliki kompleksitas komputasi yang tinggi

Untuk kedua kasus, sumber daya komputasi yang terdiri dari "anggaran" dapat terdiri dari hal-hal seperti siklus CPU ( kompleksitas waktu ), memori ( kompleksitas ruang ), atau bandwidth komunikasi (di dalam atau di antara node komputasi). Dalam contoh kedua, "terlalu mahal" akan berarti tidak bisa dipecahkan .

Dalam konteks perhitungan Bayesian, kutipan kemungkinan merujuk pada masalah dengan marginalisasi atas sejumlah besar variabel .

Sebagai contoh, abstrak makalah ini dimulai

Integrasi dipengaruhi oleh kutukan dimensi dan dengan cepat menjadi tidak bisa dikerjakan seiring dengan meningkatnya dimensi masalah.

dan selanjutnya mengatakan

Kami mengusulkan algoritma acak yang ... pada gilirannya dapat digunakan, misalnya, untuk perhitungan marginal atau pemilihan model.

(Sebagai perbandingan, bab buku terbaru ini membahas metode yang dianggap "tidak terlalu mahal".)

GeoMatt22
sumber
4
Ini jawaban yang bagus. Saya hanya akan menambahkan, bahwa "mahal" mungkin semakin dianggap secara harfiah. - seseorang dapat meningkatkan daya komputasi dan penyimpanannya secara dramatis (ke tingkat superkomputer, selama yang dibutuhkan), sangat mudah akhir-akhir ini (dan cukup murah) ... tetapi untuk masalah besar itu masih akan menjadi terlalu mahal - - karena secara harfiah biaya lebih banyak uang aktual daripada yang Anda miliki.
Glen_b -Reinstate Monica
1
@ Glen_b itu poin bagus! Saya membayangkan makna ini kurang umum dalam literatur yang diterbitkan ... tetapi lebih umum dalam proposal (dan ulasan mereka!)
GeoMatt22
@ GeoMatt22 Ini sebenarnya cara lain untuk menyatakan arti yang sama, jika Anda memikirkannya.
user253751
@ GeoMatt22 Terima kasih! Sekarang saya benar-benar mengerti apa artinya mahal dalam konteks Bayesian.
discretetimeisnice
10

Saya akan memberi Anda contoh pada kasus diskrit untuk menunjukkan mengapa integrasi / penjumlahan sangat mahal.

100P(X1,X2,,X100)2100

P(X1)

P(X1)=X2X3X100P(X1,X2,,X100)

99299

Dalam literatur model grafis probabilistik , cara menghitung distribusi marjinal seperti itu disebut pendekatan "brute force" untuk melakukan "inferensi". Berdasarkan namanya, kita mungkin tahu itu mahal. Dan orang menggunakan banyak cara lain untuk melakukan inferensi, misalnya, mendapatkan distribusi marginal secara efektif. "Cara lain" termasuk perkiraan inferensi , dll.

Haitao Du
sumber
3
Mungkin Anda juga bisa mengomentari mengapa pendekatan Bayesian bermanfaat di sini, seperti pertanyaan yang diajukan dalam konteks ini.
Tim
5

Biasanya ketika melakukan inferensi Bayesian mudah untuk menemukan integrasi berat atas variabel gangguan misalnya. Contoh lain dapat berupa sampling numerik seperti dalam hal ini dari fungsi kemungkinan, artinya melakukan sampling acak dari distribusi yang diberikan. Dengan bertambahnya jumlah parameter model, pengambilan sampel ini menjadi sangat berat dan berbagai metode komputasi telah dikembangkan untuk mempercepat prosedur dan memungkinkan implementasi yang sangat cepat, tentu saja menjaga tingkat akurasi yang tinggi. Teknik-teknik ini misalnya MC, MCMC, Metropolis ecc. Lihatlah analisis data Bayesian oleh Gelman et. al itu harus memberi Anda pengantar yang luas! semoga berhasil

Lcol
sumber
3
Jawaban ini sepertinya tidak menjawab pertanyaan utama OP seputar arti "mahal" dalam konteks ini. Atau setidaknya tidak terlalu jelas.
Shufflepants
Penjelasan singkatnya adalah untuk memperkenalkan pembaca pada makna permintaan komputasi ketika melakukan analisis spesifik dalam statistik Bayesian, karena itu dinyatakan bukan ahli matematika. Pokoknya berharap itu jelas bagi seseorang
Lcol