Exemplo de como o truque log-soma-exp funciona em Naive Bayes

14

Eu li sobre o truque log-soma-exp em muitos lugares (por exemplo , aqui e aqui ), mas nunca vi um exemplo de como ele é aplicado especificamente ao classificador Naive Bayes (por exemplo, com recursos discretos e duas classes)

Como exatamente alguém evitaria o problema de subfluxo numérico usando esse truque?

Josh
fonte
2
Existem vários exemplos de seu uso aqui, embora não necessariamente explicitamente para Bayes ingênuo . No entanto, isso dificilmente importa, já que a idéia do truque é bastante direta e facilmente adaptável.
Glen_b -Reinstala Monica
É mais provável que o problema esteja abaixo do fluxo excedente.
Henry
Eu sugiro que você tente uma pesquisa no fluxo insuficiente e atualize sua pergunta para abordar mais especificamente o que já não foi abordado.
Glen_b -Reinstala Monica
Você também pode esclarecer - este é o ingênuo modelo de Bernoulli Bayes? outra coisa talvez?
Glen_b -Reinstar Monica
Veja o exemplo aqui , na parte inferior (logo antes de 'See Also', onde eles recebem logs; exponenciando os dois lados, mas deixando o RHS "como estão" (como a exp de uma soma de logs) seria um exemplo do log Isso fornece informações suficientes sobre o seu uso no Naive Bayes para fazer uma pergunta mais específica?
Glen_b -Reinstate Monica

Respostas:

26

Em

p(Y=C|x)=p(x|Y=C)p(Y=C) k=1|C|p(x|Y=Ck)p(Y=Ck)

o denominador e o numerador podem se tornar muito pequenos, geralmente porque pode estar próximo de 0 e multiplicamos muitos deles entre si. Para evitar vazões, pode-se simplesmente pegar o log do numerador, mas é necessário usar o truque log-soma-exp para o denominador.p(xi|Ck)


Mais especificamente, para evitar vazões:

  • Se nós só se preocupam com saber qual classe a entrada ( x = x 1 , ... , x n ) provavelmente pertence a com o máximo a posteriori (MAP) regra de decisão, não temos de aplicar o log- truque soma-exp, pois não precisamos calcular o denominador nesse caso. Para o numerador, pode-se simplesmente pegar o log para evitar vazões: l o g ( p ( x | Y = C ) p ( Y = C ) )(y^)(x=x1,,xn)log(p(x|Y=C)p(Y=C)). Mais especificamente:

    y^=argmaxk{1,,|C|}p(Ck|x1,,xn)=argmaxk{1,,|C|} p(Ck)i=1np(xi|Ck)

    que se torna após o registro:

y^=argmaxk{1,,|C|}log(p(Ck|x1,,xn))=argmaxk{1,,|C|}log( p(Ck)i=1np(xi|Ck))=argmaxk{1,,|C|}(log(p(Ck))+ i=1nlog(p(xi|Ck)))
  • p(Y=C|x)

    log(p(Y=C|x))=log(p(x|Y=C)p(Y=C) k=1|C|p(x|Y=Ck)p(Y=Ck))=log(p(x|Y=C)p(Y=C)numerator)log( k=1|C|p(x|Y=Ck)p(Y=Ck)denominator)

    log( k=1|C|p(x|Y=Ck)p(Y=Ck))p(xi|Ck)p(xi|Ck)log(p(xi|Ck))0p(xi|Ck)1p(xi|Ck)=exp(log(p(xi|Ck)))

    log( k=1|C|p(x|Y=Ck)p(Y=Ck))=log( k=1|C|exp(log(p(x|Y=Ck)p(Y=Ck))))

    log(p(x|Y=Ck)p(Y=Ck))exp(log(p(x|Y=Ck)p(Y=Ck)))

    logkeak=logkeakeAA=A+logkeakA

    com:

    • ak=log(p(x|Y=Ck)p(Y=Ck))
    • A=maxk{1,,|C|}ak.

    Podemos ver que a introdução da variável evita fluxos insuficientes. Por exemplo, com , temos:Ak=2,a1=245,a2=255

    • exp(a1)=exp(245)=3.96143×10107
    • exp(a2)=exp(255)=1.798486×10111

    Usando o truque log-sum-exp, evitamos o sub-fluxo, com : A=max(245,255)=245logkeak=logkeakeAA=A+logkeakA=245+logkeak+245=245+log(e245+245+e255+245)=245+log(e0+e10)

    pois está muito mais longe de 0 que ou .e103.96143×101071.798486×10111

Franck Dernoncourt
fonte
2

Suponha que desejemos identificar qual dos dois bancos de dados tem mais probabilidade de gerar uma frase (por exemplo, de qual novela é mais provável que essa frase tenha vindo). Poderíamos assumir a independência das palavras condicionais no banco de dados (suposição de Naive Bayes).

Agora procure o segundo link que você postou. Lá representaria a probabilidade conjunta de observar a sentença dada um banco de dados e os s representariam a probabilidade de observar cada uma das palavras na sentença.aebt

Sid
fonte
1

Podemos ver nesta resposta que o menor número em Python (apenas por exemplo) se 5e-324deve ao IEEE754 , e a causa do hardware se aplica a outros idiomas também.

In [2]: np.nextafter(0, 1)
Out[2]: 5e-324

E qualquer flutuação menor que isso levaria a 0.

In [3]: np.nextafter(0, 1)/2
Out[3]: 0.0

E vamos ver a função do Naive Bayes with discrete features and two classesconforme necessário:

p(S=1|w1,...wn)=p(S=1)i=1np(wi|S=1) s={0,1}p(S=s)i=1np(wi|S=s)

Permita-me instanciar essa função com uma simples tarefa de PNL abaixo.

Decidimos detectar se o e-mail a chegar é spam ( ) ou não ( ) e temos um vocabulário de palavras de 5.000 em tamanho ( ) e a única preocupação é se ocorrer uma palavra ( ) ( ) no e-mail ou não ( ) por simplicidade ( Bernoulli ingênuo Bayes ).S=1S=0n=5,000wip(wi|S=1)1p(wi|S=1)

In [1]: import numpy as np
In [2]: from sklearn.naive_bayes import BernoulliNB
# let's train our model with 200 samples
In [3]: X = np.random.randint(2, size=(200, 5000))
In [4]: y = np.random.randint(2, size=(200, 1)).ravel()
In [5]: clf = BernoulliNB()
In [6]: model = clf.fit(X, y)

Podemos ver que seria muito pequeno devido às probabilidades (ambos e estaria entre 0 e 1) em e, portanto, temos certeza de que o produto seria menor que e obtemos .p(S=s)i=1np(wi|S=s)p(wi|S=1)1p(wi|S=1)i50005e3240/0

In [7]: (np.nextafter(0, 1)*2) / (np.nextafter(0, 1)*2)
Out[7]: 1.0

In [8]: (np.nextafter(0, 1)/2) / (np.nextafter(0, 1)/2)
/home/lerner/anaconda3/bin/ipython3:1: RuntimeWarning: invalid value encountered in double_scalars
  #!/home/lerner/anaconda3/bin/python
Out[8]: nan
In [9]: l_cpt = model.feature_log_prob_
In [10]: x = np.random.randint(2, size=(1, 5000))
In [11]: cls_lp = model.class_log_prior_
In [12]: probs = np.where(x, np.exp(l_cpt[1]), 1-np.exp(l_cpt[1]))
In [13]: np.exp(cls_lp[1]) * np.prod(probs)
Out[14]: 0.0

Em seguida, surge o problema: como podemos calcular a probabilidade do email ser um spam ? Ou como podemos calcular o numerador e o denominador?p(S=1|w1,...wn)

Podemos ver a implementação oficial no sklearn :

jll = self._joint_log_likelihood(X)
# normalize by P(x) = P(f_1, ..., f_n)
log_prob_x = logsumexp(jll, axis=1)
return jll - np.atleast_2d(log_prob_x).T

Para o numerador, converteu o produto de probabilidades na soma da probabilidade de log e, para o denominador, usou o logsumexp em scipy, que é:

out = log(sum(exp(a - a_max), axis=0))
out += a_max

Como não podemos adicionar duas probabilidades conjuntas adicionando a probabilidade de log conjunto, devemos sair do espaço de log para o espaço de probabilidade. Mas não podemos adicionar as duas probabilidades verdadeiras porque elas são muito pequenas e devemos escalá-las e fazer a adição: e retornar o resultado no espaço do log seguida, redimensione-o novamente: no espaço de log adicionando o .s={0,1}ejllsmax_jlllogs={0,1}ejllsmax_jllmax_jll+logs={0,1}ejllsmax_jllmax_jll

E aqui está a derivação:

logs={0,1}ejlls=logs={0,1}ejllsemax_jllmax_jll=logemax_jll+logs={0,1}ejllsmax_jll=max_jll+logs={0,1}ejllsmax_jll

onde é o no código.max_jlla_max

Depois de obter o numerador e o denominador no espaço do log, podemos obter a probabilidade condicional do log ( ) subtraindo o denominador do numerador : logp(S=1|w1,...wn)

return jll - np.atleast_2d(log_prob_x).T

Espero que ajude.

Referência:
1. Classificador Bernoulli Naive Bayes
2. Filtragem de Spam com Naive Bayes - Que Naive Bayes?

Lerner Zhang
fonte