Pembatalan bencana dalam logsum

Saya mencoba menerapkan fungsi berikut dalam floating point presisi ganda dengan kesalahan relatif rendah :

l o g s u m (x, y) = \log (\exp (x) + \exp (y))

$\mathrm{logsum}(x,y) = \log(\exp(x) + \exp(y))$

Ini digunakan secara luas dalam aplikasi statistik untuk menambahkan probabilitas atau kepadatan probabilitas yang diwakili dalam ruang log. Tentu saja, baik atau dapat dengan mudah overflow atau underflow, yang akan menjadi buruk karena ruang log digunakan untuk menghindari underflow. Ini adalah solusi khas: $\exp(x)$ $\exp(y)$

l o g s u m (x, y) = x + l o g 1 p (\exp (y - x))

$\mathrm{logsum}(x,y) = x + \mathrm{log1p}(\exp(y - x))$

Pembatalan dari memang terjadi, tetapi dikurangi dengan . Lebih buruk lagi adalah ketika dan dekat. Berikut ini plot kesalahan relatif: $y-x$ $\exp$ $x$ $\mathrm{log1p}(\exp(y - x))$

masukkan deskripsi gambar di sini

Plot dipotong pada untuk menekankan bentuk kurva , tentang pembatalan yang terjadi. Saya telah melihat kesalahan hingga dan menduga bahwa itu menjadi jauh lebih buruk. (FWIW, fungsi "kebenaran dasar" diimplementasikan menggunakan float presisi arbitrer MPFR dengan presisi 128-bit.) $10^{-14}$ $\mathrm{logsum}(x,y) = 0$ $10^{-11}$

Saya sudah mencoba reformulasi lain, semuanya dengan hasil yang sama. Dengan sebagai ekspresi luar, kesalahan yang sama terjadi dengan mengambil log sesuatu di dekat 1. Dengan sebagai ekspresi luar, pembatalan terjadi di ekspresi dalam. $\log$ $\mathrm{log1p}$

Sekarang, kesalahan absolut sangat kecil, jadi memiliki kesalahan relatif sangat kecil (dalam epsilon). Orang mungkin berpendapat bahwa, karena pengguna benar-benar tertarik pada probabilitas (bukan probabilitas log), kesalahan relatif yang mengerikan ini bukan masalah. Mungkin biasanya tidak, tapi saya sedang menulis fungsi perpustakaan, dan saya ingin kliennya dapat mengandalkan kesalahan relatif tidak lebih buruk daripada kesalahan pembulatan. $\exp(\mathrm{logsum}(x,y))$ $\mathrm{logsum}$

Sepertinya saya perlu pendekatan baru. Apa itu?

floating-point stability numerics Neil Toronto
sumber

Saya tidak mengerti paragraf terakhir Anda. "dalam epsilon" tidak berarti apa-apa bagiku. Apakah yang Anda maksud adalah Unit di Tempat Terakhir ? Adapun pengguna yang tertarik pada probabilitas, kesalahan log probabilitas kecil akan menghasilkan kesalahan probabilitas besar, jadi ini bukan masalahnya.

Aron Ahmadia

Karena penasaran, apakah Anda mencoba mengambil yang terbaik dari dua metode Anda dan merencanakan kesalahan itu? Maka yang Anda butuhkan adalah logika yang tepat untuk mendeteksi kasus Anda (mudah-mudahan menjadi lebih murah atau bagian dari biaya yang diperlukan dari algoritma), kemudian beralih ke metode yang sesuai.

Aron Ahmadia

@AronAhmadia: "Within an epsilon" berarti kesalahan relatif kurang dari epsilon floating-point presisi ganda, yaitu sekitar 2.22e-16. Untuk mengapung normal (yaitu bukan subnormal), itu sesuai dengan sekitar ulp. Juga, jika adalah kesalahan absolut , maka kesalahan relatif dari adalah , yang hampir merupakan fungsi identitas mendekati nol. TKI, kesalahan absolut kecil untuk menyiratkan kesalahan relatif kecil untuk .

a

$a$

x

$x$

\exp (x)

$\exp(x)$

\exp (a) - 1

$\exp(a)-1$

x

$x$

\exp (x)

$\exp(x)$

Neil Toronto

Tambahan: Ketika kesalahan absolut mendekati nol. Ketika , misalnya, Anda benar: relatif akan meledak.

a

$a$

a > 1

$a > 1$

Neil Toronto

l o g s u m (x, y) = max (x, y) + l o g 1 p (\exp (- abs (x - y))

$\mathrm{logsum}(x,y)=\max(x,y)+\mathrm{log1p}(\exp(-\operatorname{abs}(x-y))$

\log \sum_{i} e^{x_{i}} = ξ + \log \sum_{i} e^{x_{i} - ξ}, ξ = max_{i} x_{i}

$\log \sum_i e^{x_i} = \xi+ \log\sum_i e^{x_i-\xi},~~~\xi=\max_i x_i$

Jika logsum sangat dekat dengan nol dan Anda menginginkan akurasi relatif tinggi, Anda mungkin dapat menggunakan menggunakan akurasi (yaitu, lebih dari presisi ganda) implementasi yang hampir linier untuk kecil .

l o g s u m (x, y) = max (x, y) + l e x p (x - y)

$\mathrm{logsum}(x,y)=\max(x,y)+\mathrm{lexp}(x-y)$

l e x p (z) := \log (1 + e^{- | z |})

$\mathrm{lexp}(z):=\log(1+e^{-|z|})$

z

$z$

Arnold Neumaier
sumber

Dalam hal kesalahan absolut, itu. Dalam hal kesalahan relatif, itu mengerikan ketika output mendekati nol.

Neil Toronto

@ NeilToronto: Tolong beri contoh dengan dua input eksplisit dan , sehingga saya bisa bermain dengannya.

x

$x$

y

$y$

Arnold Neumaier

Untuk x = -0,775 dan y = -0,6175, saya mendapatkan 62271 ulps kesalahan dan 1,007e-11 relatif kesalahan.

Neil Toronto

Hitung titik data yang sangat akurat dalam rentang minat - setidaknya diperlukan dua rentang berbeda karena perilaku asimptotik. Seseorang dapat menggunakan ekspresi yang didefinisikan untuk z tidak mendekati nol. Untuk rentang yang luar biasa cocok dengan fungsi rasional yang cukup tinggi untuk mendapatkan akurasi yang diinginkan. Untuk stabilitas numerik, gunakan polinomial bernstein atau polinomial Tchebychev dalam pembilang dan penyebut, yang disesuaikan dengan interval waktu. Pada akhirnya, perluas fraksi lanjutan dan cari tahu berapa banyak yang bisa memotong koefisien tanpa meningkatkan akurasi.

Arnold Neumaier

Ini memberikan Untuk mendapatkan melakukan hal yang sama tetapi diterapkan pada fungsi lexp (z) -l (z).

l = l (z)

$l=l(z)$

m

$m$

Arnold Neumaier

Pembatalan bencana dalam logsum

Jawaban: