Exemple de fonctionnement de l'astuce log-sum-exp à Naive Bayes

J'ai lu à propos de l'astuce log-sum-exp à de nombreux endroits (par exemple ici et ici ) mais je n'ai jamais vu un exemple de la façon dont il est appliqué spécifiquement au classifieur Naive Bayes (par exemple avec des fonctionnalités discrètes et deux classes)

Comment éviterait-on exactement le problème du sous-dépassement numérique en utilisant cette astuce?

naive-bayes underflow Josh
la source

Il existe plusieurs exemples de son utilisation ici, mais pas nécessairement explicitement pour les Bayes naïfs . Cependant, cela n'a guère d'importance, car l'idée de l'astuce est assez simple et facilement adaptable.

Glen_b -Reinstate Monica

Le problème est plus susceptible d'être un débordement qu'un débordement.

Henry

Je vous suggère d'essayer une recherche sur underflow , puis de mettre à jour votre question pour répondre plus spécifiquement à tout ce qui n'est pas déjà couvert.

Glen_b -Reinstate Monica

Pourriez-vous également préciser - il s'agit de Bayes naïfs du modèle de Bernoulli? autre chose peut-être?

Glen_b -Reinstate Monica

Voir l'exemple ici , juste en bas (juste avant «Voir aussi» où ils prennent les journaux; exponentiariser les deux côtés mais en laissant le RHS «tel quel» (comme l'expulsion d'une somme de journaux) serait un exemple du journal -sum-exp trick Cela vous donne-t-il suffisamment d'informations concernant son utilisation à Naive Bayes pour poser une question plus spécifique?

Glen_b -Reinstate Monica

Réponses:

p (Oui = C | X) = \frac{p (X | Oui = C) p (Oui = C)}{\sum_{k = 1}^{| C |} p (X | Oui = C_{k}) p (Oui = C_{k})}

$p(Y=C|\mathbf{x}) = \frac{p(\mathbf{x}|Y=C)p(Y=C)}{~\sum_{k=1}^{|C|}{}p(\mathbf{x}|Y=C_k)p(Y=C_k)}$

le dénominateur et le numérateur peuvent devenir très petits, généralement parce que le peut être proche de 0 et nous en multiplions plusieurs entre eux. Pour éviter les débordements, on peut simplement prendre le journal du numérateur, mais il faut utiliser l'astuce log-sum-exp pour le dénominateur. $p(x_i \vert C_k)$

Plus précisément, pour éviter les débordements:

Si nous ne se soucient que de savoir quelle classe l'entrée le plus appartient probablement avec le maximumune règle de décisionposteriori (MAP), nous ne devons pas appliquer la log- astuce somme-exp, puisquenous n'avons pas à calculer le dénominateurdans ce cas. Pour le numérateur on peut simplement prendre le log pour éviter les débordements: $(\hat{y})$ $(\mathbf{x}=x_1, \dots, x_n)$ $log \left( p(\mathbf{x}|Y=C)p(Y=C) \right)$ . Plus précisement:

$\hat{y} = \underset{k \in {1, \dots, | C |}}{argmax} p (C_{k} | X_{1}, \dots, X_{n}) = \underset{k \in {1, \dots, | C |}}{argmax} p (C_{k}) \prod_{je = 1}^{n} p (X_{je} | C_{k})$ $\hat{y} = \underset{k \in \{1, \dots, |C|\}}{\operatorname{argmax}}p(C_k \vert x_1, \dots, x_n) = \underset{k \in \{1, \dots, |C|\}}{\operatorname{argmax}} \ p(C_k) \displaystyle\prod_{i=1}^n p(x_i \vert C_k)$
qui devient après avoir pris le journal:

\begin{aligned} \hat{y} & = \underset{k \in {1, \dots, | C |}}{argmax} Journal (p (C_{k} | X_{1}, \dots, X_{n})) \\ = \underset{k \in {1, \dots, | C |}}{argmax} Journal (p (C_{k}) \prod_{je = 1}^{n} p (X_{je} | C_{k})) \\ = \underset{k \in {1, \dots, | C |}}{argmax} (Journal (p (C_{k})) + \sum_{je = 1}^{n} Journal (p (X_{je} | C_{k}))) \end{aligned}

$\begin{align} \hat{y} &= \underset{k \in \{1, \dots, |C|\}}{\operatorname{argmax}} \log \left( p(C_k \vert x_1, \dots, x_n) \right)\\ &= \underset{k \in \{1, \dots, |C|\}}{\operatorname{argmax}} \log \left( \ p(C_k) \displaystyle\prod_{i=1}^n p(x_i \vert C_k) \right) \\ &= \underset{k \in \{1, \dots, |C|\}}{\operatorname{argmax}} \left( \log \left( p(C_k) \right) + \ \displaystyle\sum_{i=1}^n \log \left(p(x_i \vert C_k) \right) \right) \end{align}$

Si nous voulons calculer la probabilité de classe , nous devrons calculer le dénominateur: $p(Y=C|\mathbf{x})$

$\begin{aligned} \log (p (Y = C | x)) & = \log (\frac{p (x | Y = C) p (Y = C)}{\sum_{k = 1}^{| C |} p (x | Y = C_{k}) p (Y = C_{k})}) \\ = \log (\underset{numerator}{\underset{⏟}{p (x | Y = C) p (Y = C)}}) - \log (\underset{denominator}{\underset{⏟}{\sum_{k = 1}^{| C |} p (x | Y = C_{k}) p (Y = C_{k})}}) \end{aligned}$

Le élément $\log \left( ~\sum_{k=1}^{|C|}{}p(\mathbf{x}|Y=C_k)p(Y=C_k) \right)\\$ peut déborder car peut être très petit: c'est le même problème que dans le numérateur, mais cette fois nous avons une sommation à l'intérieur du logarithme, ce qui nous empêche de transformer le (peut être proche de 0) dans (négatif et plus proche de 0, puisque $p(x_i \vert C_k)$ $p(x_i \vert C_k)$ $\log \left(p(x_i \vert C_k) \right)$ $0 \leq p(x_i \vert C_k) \leq 1$ ). Pour contourner ce problème, nous pouvons utiliser le fait que pour obtenir: $p(x_i \vert C_k) = \exp \left( {\log \left(p(x_i \vert C_k) \right)} \right)$

$\log (\sum_{k = 1}^{| C |} p (x | Y = C_{k}) p (Y = C_{k})) = \log (\sum_{k = 1}^{| C |} \exp (\log (p (x | Y = C_{k}) p (Y = C_{k}))))$

À ce stade, un nouveau problème se pose: peut être assez négatif, ce qui implique que $\log \left( p(\mathbf{x}|Y=C_k)p(Y=C_k) \right)$ peut devenir très proche de 0, c'est-à-dire un débordement. C'est là que nous utilisons l'astuce log-sum-exp: $\exp \left( \log \left( p(\mathbf{x}|Y=C_k)p(Y=C_k) \right) \right)$

$\log \sum_{k} e^{a_{k}} = \log \sum_{k} e^{a_{k}} e^{A - A} = A + \log \sum_{k} e^{a_{k} - A}$

avec:
- , $a_k=\log \left( p(\mathbf{x}|Y=C_k)p(Y=C_k) \right)$
- $A = \underset{k \in \{1, \dots, |C|\}} \max a_k.$
On voit que l'introduction de la variable évite les débordements. Par exemple avec , nous avons: $A$ $k=2, a_1 = - 245, a_2 = - 255$
- $\exp \left(a_1\right) = \exp \left(- 245\right) =3.96143\times 10^{- 107}$
- $\exp \left(a_2\right) = \exp \left(- 255\right) =1.798486 \times 10^{-111}$
En utilisant l'astuce log-sum-exp, nous évitons le sous-dépassement, avec : $A=\max ( -245, -255 )=-245$ $\begin{align}\log \sum_k e^{a_k} &= \log \sum_k e^{a_k}e^{A-A} \\&= A+ \log\sum_k e^{a_k -A}\\ &= -245+ \log\sum_k e^{a_k +245}\\&= -245+ \log \left(e^{-245 +245}+e^{-255 +245}\right) \\&=-245+ \log \left(e^{0}+e^{-10}\right) \end{align}$

Nous avons évité le sous-dépassement car est beaucoup plus éloigné de 0 que $e^{-10}$ ou . $3.96143\times 10^{- 107}$ $1.798486 \times 10^{-111}$

Franck Dernoncourt
la source

Supposons que nous voulons identifier laquelle des deux bases de données est la plus susceptible d'avoir généré une phrase (par exemple, de quel roman cette phrase est plus susceptible de provenir). Nous pourrions supposer l'indépendance des mots conditionnelle à la base de données (hypothèse Naive Bayes).

Recherchez maintenant le deuxième lien que vous avez publié. Il représenterait la probabilité conjointe d'observer la phrase donnée une base de données et l' s représenterait la probabilité d'observer chacun des mots dans la phrase. $a$ $e^{b_{t}}$

Sid
la source

Nous pouvons voir à partir de cette réponse que le plus petit nombre en Python (prenez-le par exemple) est 5e-324dû à l' IEEE754 , et la cause matérielle s'applique également aux autres langages.

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

Et tout flotteur plus petit que cela conduirait à 0.

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

Et voyons la fonction de Naive Bayes with discrete features and two classesselon vos besoins:

p (S = 1 | w_{1}, . . . w_{n}) = \frac{p (S = 1) \prod_{i = 1}^{n} p (w_{i} | S = 1)}{\sum_{s = {0, 1}} p (S = s) \prod_{i = 1}^{n} p (w_{i} | S = s)}

$p(S=1|w_1, ... w_n) = \frac{p(S=1) \prod_{i=1}^n p(\mathbf{w_i}|S=1)}{~\sum_{s=\{0, 1\}}p(S=s)\prod_{i=1}^n p(\mathbf{w_i}|S=s)}$

Permettez-moi d'instancier cette fonction par un simple soufflet de tâche PNL.

$S=1$ $S=0$ $n=5,000$ $w_i$ $p(w_i|S=1)$ $1-p(w_i|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)

$p(S=s)\prod_{i=1}^n p(\mathbf{w_i}|S=s)$ $p(w_i|S=1)$ $1-p(w_i|S=1)$ $\prod_i^{5000}$ $5e^{-324}$ $0/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

$p(S=1|w_1, ... w_n)$

Nous pouvons voir l'implémentation officielle dans 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

Pour le numérateur, il a converti le produit des probabilités en la somme du log vraisemblance et pour le dénominateur, il a utilisé le logsumexp en scipy qui est:

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

$\sum_{s=\{0,1\}} e^{jll_s - max\_jll}$ $\log\sum_{s=\{0,1\}} e^{jll_s - max\_jll}$ $max\_jll+ \log\sum_{s=\{0,1\}} e^{jll_s - max\_jll}$ $max\_jll$

Et voici la dérivation:

$\begin{align} \log \sum_{s=\{0,1\}} e^{jll_s} & = \log \sum_{s=\{0,1\}} e^{jll_s}e^{max\_jll-max\_jll} \\& = \log e ^{max\_jll}+ \log\sum_{s=\{0,1\}} e^{jll_s - max\_jll} \\& = max\_jll+ \log\sum_{s=\{0,1\}} e^{jll_s - max\_jll} \end{align}$

$max\_jll$ $a\_max$ dans le code.

$\log p(S=1|w_1, ... w_n)$ soustrayant le dénominateur du numérateur :

return jll - np.atleast_2d(log_prob_x).T

J'espère que cela pourra aider.

Référence:
1. Bernoulli Naive Bayes Classifier
2. Filtrage des spams avec Naive Bayes - Quels Naive Bayes?

Lerner Zhang
la source