He leído sobre el truco log-sum-exp en muchos lugares (por ejemplo , aquí y aquí ) pero nunca he visto un ejemplo de cómo se aplica específicamente al clasificador Naive Bayes (por ejemplo, con características discretas y dos clases)
¿Cómo se evitaría exactamente el problema del desbordamiento numérico con este truco?
naive-bayes
underflow
Josh
fuente
fuente
Respuestas:
En
tanto el denominador como el numerador pueden volverse muy pequeños, típicamente porque la puede estar cerca de 0 y multiplicamos muchos de ellos entre sí. Para evitar desbordamientos, uno simplemente puede tomar el registro del numerador, pero necesita usar el truco log-sum-exp para el denominador.p(xi|Ck)
Más específicamente, para evitar desbordamientos:
Si solo nos interesa saber a qué clase la entrada probablemente pertenece con la regla de decisión de máximo a posteriori (MAP), no tenemos que aplicar el truco log-sum-exp, ya que no tenemos que calcular el denominador en ese caso. Para el numerador, uno simplemente puede tomar el registro para evitar desbordamientos: . Más específicamente:( x = x 1 , ... , x n ) l o g ( p ( x | Y = C ) p ( Y = C ) )(y^) (x=x1,…,xn) log(p(x|Y=C)p(Y=C))
que se convierte después de tomar el registro:
Si queremos calcular la probabilidad de clase , necesitaremos calcular el denominador:p(Y=C|x)
El elemento puede desbordarse porque puede ser muy pequeño: es el mismo problema que en el numerador, pero esta vez tenemos una suma dentro del logaritmo, que nos impide transformar el (puede estar cerca de 0) en (negativo y ya no está cerca de 0, ya que ). Para evitar este problema, podemos utilizar el hecho de que para obtener:log( ∑|C|k=1p(x|Y=Ck)p(Y=Ck)) p(xi|Ck) p(xi|Ck) log(p(xi|Ck)) 0≤p(xi|Ck)≤1 p(xi|Ck)=exp(log(p(xi|Ck)))
En ese punto, surge un nuevo problema: puede ser bastante negativo, lo que implica que puede llegar a estar muy cerca de 0, es decir, bajo flujo. Aquí es donde usamos el truco log-sum-exp :log(p(x|Y=Ck)p(Y=Ck)) exp(log(p(x|Y=Ck)p(Y=Ck)))
con:
Podemos ver que la introducción de la variable evita los desbordamientos. Por ejemplo, con , tenemos:A k=2,a1=−245,a2=−255
Al usar el truco log-sum-exp evitamos el inferior, con :A=max(−245,−255)=−245 log∑keak=log∑keakeA−A=A+log∑keak−A=−245+log∑keak+245=−245+log(e−245+245+e−255+245)=−245+log(e0+e−10)
Evitamos el desbordamiento ya que está mucho más lejos de 0 que o .e−10 3.96143×10−107 1.798486×10−111
fuente
Supongamos que queremos identificar cuál de las dos bases de datos es más probable que haya generado una frase (por ejemplo, de qué novela es más probable que haya surgido esta frase). Podríamos asumir la independencia de las palabras condicionales en la base de datos (supuesto de Naive Bayes).
Ahora busque el segundo enlace que ha publicado. Allí representaría la probabilidad conjunta de observar la oración dada una base de datos y los s representarían la probabilidad de observar cada una de las palabras en la oración.a ebt
fuente
Podemos ver en esta respuesta que el número más pequeño en Python (solo tómalo , por ejemplo) se
5e-324
debe al IEEE754 , y la causa del hardware también se aplica a otros idiomas.Y cualquier flotador más pequeño que eso llevaría a 0.
Y veamos la función de Naive Bayes
with discrete features and two classes
como lo requirió:Permítanme crear una instancia de esa función con una simple tarea de PNL a continuación.
Decidimos detectar si el correo electrónico entrante es spam ( ) o no spam ( ) y tenemos un vocabulario de 5.000 palabras ( ) y la única preocupación es si aparece una palabra ( ) ( ) en el correo electrónico o no ( ) por simplicidad ( Bernoulli ingenuo Bayes ).S=1 S=0 n=5,000 wi p(wi|S=1) 1−p(wi|S=1)
Podemos ver que sería muy pequeño debido a las probabilidades (tanto como estaría entre 0 y 1) en , y por lo tanto, estamos seguros de que el producto será menor que y solo obtenemos .p(S=s)∏ni=1p(wi|S=s) p(wi|S=1) 1−p(wi|S=1) ∏5000i 5e−324 0/0
Entonces surge el problema: ¿cómo podemos calcular la probabilidad de que el correo electrónico sea un spam ? ¿O cómo podemos calcular el numerador y el denominador?p(S=1|w1,...wn)
Podemos ver la implementación oficial en sklearn :
Para el numerador, convirtió el producto de probabilidades en la suma de la probabilidad logarítmica y para el denominador usó logsumexp en scipy, que es:
Debido a que no podemos agregar dos probabilidades conjuntas agregando su probabilidad de registro conjunto, debemos salir del espacio logarítmico al espacio de probabilidad. Pero no podemos agregar las dos probabilidades verdaderas porque son demasiado pequeñas y debemos escalarlas y hacer la suma: y poner el resultado de nuevo en el espacio de registro luego vuelva a : en el espacio de registro agregando .∑s={0,1}ejlls−max_jll log∑s={0,1}ejlls−max_jll max_jll+log∑s={0,1}ejlls−max_jll max_jll
Y aquí está la derivación:
donde es el en el código.max_jll a_max
Una vez que obtenemos tanto el numerador como el denominador en el espacio logarítmico, podemos obtener la probabilidad condicional logarítmica ( ) restando el denominador del numerador :logp(S=1|w1,...wn)
Espero que ayude.
Referencia:
1. Bernoulli Naive Bayes Classifier
2. Filtrado de spam con Naive Bayes - ¿Qué Naive Bayes?
fuente