Cancelamento catastrófico na soma do log

Estou tentando implementar a seguinte função no ponto flutuante de precisão dupla com baixo erro relativo :

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

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

Isso é usado extensivamente em aplicativos estatísticos para adicionar probabilidades ou densidades de probabilidade representadas no espaço de log. Obviamente, $\exp(x)$ ou $\exp(y)$ poderiam facilmente estourar ou estourar, o que seria ruim porque o espaço de log é usado para evitar o estouramento em primeiro lugar. Esta é a solução típica:

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))$

O cancelamento de $y-x$ acontece, mas é mitigado pela $\exp$ . Pior ainda, de longe, é quando $x$ e $\mathrm{log1p}(\exp(y - x))$ encontram-se perto. Aqui está um gráfico de erro relativo:

insira a descrição da imagem aqui

A trama é cortada em para enfatizar a forma da curva de , sobre a qual o cancelamento ocorrer. Eu vi erro até e suspeito que ele fica muito pior. (FWIW, a função "verdade da terra" é implementada usando flutuadores de precisão arbitrária do MPFR com precisão de 128 bits.) $10^{-14}$ $\mathrm{logsum}(x,y) = 0$ $10^{-11}$

Eu tentei outras reformulações, todas com o mesmo resultado. Com como a expressão exterior, o mesmo ocorre por erro tendo um registo de algo perto 1. Com como a expressão exterior, cancelamento acontece na expressão interior. $\log$ $\mathrm{log1p}$

Agora, o absoluto de erro é muito pequena, de modo tem muito pequeno erro relativo (dentro de um epsilon). Alguém poderia argumentar que, porque um usuário de está realmente interessado em probabilidades (não probabilidades de log), este erro relativo terrível não é um problema. É provável que geralmente não seja, mas estou escrevendo uma função de biblioteca e gostaria que seus clientes pudessem contar com um erro relativo não muito pior do que um erro de arredondamento. $\exp(\mathrm{logsum}(x,y))$ $\mathrm{logsum}$

Parece que preciso de uma nova abordagem. O que poderia ser?

floating-point stability numerics Neil Toronto
fonte

Eu não entendo o seu último parágrafo. "dentro de um epsilon" não significa nada para mim. Você quer dizer uma unidade em último lugar ? Quanto aos usuários interessados em probabilidades, um pequeno erro de probabilidade de log resultará em um grande erro de probabilidade; portanto, esse não é o caso.

Aron Ahmadia 22/10/12

Por curiosidade, você já tentou tirar o melhor de seus dois métodos e traçar o erro disso? Então, tudo o que você precisa é a lógica certa para detectar em qual caso você está (espero que seja menos oneroso ou parte do custo exigido do algoritmo) e depois mude para o método apropriado.

Aron Ahmadia 22/10/12

a

$a$

x

$x$

\exp (x)

$\exp(x)$

\exp (a) - 1

$\exp(a)-1$

x

$x$

\exp (x)

$\exp(x)$

a

$a$

a > 1

$a > 1$

Respostas:

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$

Caso a soma do log esteja muito próxima de zero e você queira alta precisão relativa, provavelmente você pode usar usando um método preciso (isto é, mais do que precisão dupla) implementação de que é quase linear para pequeno .

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
fonte

Em termos de erro absoluto, é. Em termos de erro relativo, é horrível quando a saída está próxima de zero.

Neil Toronto

@ NeilToronto: Por favor, dê um exemplo com duas entradas explícitas e , para que eu possa brincar com ela.

x

$x$

y

$y$

Arnold Neumaier 22/10/12

Para x = -0,775 ey = -0,6175, recebo o erro 62271 ulps e o erro relativo 1.007e-11.

Neil Toronto

Calcule pontos de dados altamente precisos no intervalo de interesse - são necessários pelo menos dois intervalos diferentes devido ao comportamento assintótico. Pode-se usar a expressão definidora para z não próxima de zero. Para a faixa excepcional, ajuste uma função racional de grau suficientemente alto para obter a precisão desejada. Para estabilidade numérica, use polinômios de Bernstein ou polinômios de Tchebychev no numerador e denominador, adaptados ao intervalo de interesse. No final, expanda para uma fração contínua e descubra quanto é possível truncar os coeficientes sem medir a precisão.

Arnold Neumaier

Isso fornece Para obter faça o mesmo, mas aplicado à função lexp (z) -l (z).

l = l (z)

$l=l(z)$

m

$m$

Arnold Neumaier