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

14

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?

Josh
la source
2
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:

26

En

p(Oui=C|X)=p(X|Oui=C)p(Oui=C) k=1|C|p(X|Oui=Ck)p(Oui=Ck)

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(Xje|Ck)


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

  • Si nous ne se soucient que de savoir quelle classe l'entrée ( x = x 1 , ... , x n ) 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: l o g ( p ( x | Y = C ) p ( Y = C ) )(y^)(X=X1,,Xn)log(p(X|Oui=C)p(Oui=C)). Plus précisement:

    y^=argmaxk{1,,|C|}p(Ck|X1,,Xn)=argmaxk{1,,|C|} p(Ck)je=1np(Xje|Ck)

    qui devient après avoir pris le journal:

y^=argmaxk{1,,|C|}Journal(p(Ck|X1,,Xn))=argmaxk{1,,|C|}Journal( p(Ck)je=1np(Xje|Ck))=argmaxk{1,,|C|}(Journal(p(Ck))+ je=1nJournal(p(Xje|Ck)))
  • Si nous voulons calculer la probabilité de classe , nous devrons calculer le dénominateur:p(Oui=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)

    Le log de l' élément ( | C | k = 1Journal( k=1|C|p(X|Oui=Ck)p(Oui=Ck))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 p ( x i | C k ) (peut être proche de 0) dans log ( p ( x i | C k ) ) (négatif et plus proche de 0, puisque 0 p ( x i | C k ) 1p(Xje|Ck)p(Xje|Ck)Journal(p(Xje|Ck))0p(Xje|Ck)1). Pour contourner ce problème, nous pouvons utiliser le fait que pour obtenir:p(Xje|Ck)=exp(Journal(p(Xje|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))))

    À ce stade, un nouveau problème se pose: peut être assez négatif, ce qui implique que exp ( loglog(p(x|Y=Ck)p(Y=Ck)) 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(log(p(x|Y=Ck)p(Y=Ck)))

    logkeak=logkeakeAA=A+logkeakA

    avec:

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

    On voit que l'introduction de la variable évite les débordements. Par exemple avec k = 2 , a 1 = - 245 , a 2 = - 255 , nous avons:Ak=2,a1=245,a2=255

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

    En utilisant l'astuce log-sum-exp, nous évitons le sous-dépassement, avec : log k e a kA=max(245,255)=245logkeak=logkeakeAA=A+logkeakA=245+logkeak+245=245+log(e245+245+e255+245)=245+log(e0+e10)

    Nous avons évité le sous-dépassement car est beaucoup plus éloigné de 0 quee10 ou 1,798486 × 10 - 111 .3.96143×101071.798486×10111

Franck Dernoncourt
la source
2

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' e b t s représenterait la probabilité d'observer chacun des mots dans la phrase.aebt

Sid
la source
1

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|w1,...wn)=p(S=1)i=1np(wi|S=1) s={0,1}p(S=s)i=1np(wi|S=s)

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

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)

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

p(S=1|w1,...wn)

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

s={0,1}ejlls-muneX_jllJournals={0,1}ejlls-muneX_jllmuneX_jll+Journals={0,1}ejlls-muneX_jllmuneX_jll

Et voici la dérivation:

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

max_jlla_max dans le code.

logp(S=1|w1,...wn) 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