Beispiel, wie der Log-Sum-Exp-Trick in Naive Bayes funktioniert

14

Ich habe an vielen Stellen (z. B. hier und hier ) über den Log-Sum-Exp-Trick gelesen , aber noch nie ein Beispiel dafür gesehen, wie er speziell auf den Naive Bayes-Klassifikator angewendet wird (z. B. mit diskreten Merkmalen und zwei Klassen).

Wie genau würde man mit diesem Trick das Problem des numerischen Unterlaufs vermeiden?

Josh
quelle
2
Es gibt hier einige Beispiele für seine Verwendung, jedoch nicht unbedingt explizit für naive Bayes. Dies spielt jedoch kaum eine Rolle, da die Idee des Tricks recht einfach und leicht anpassbar ist.
Glen_b -State Monica
Das Problem ist eher ein Unterlauf als ein Überlauf.
Henry
Ich würde vorschlagen, dass Sie eine Suche nach Unterlauf versuchen und dann Ihre Frage aktualisieren, um genauer zu behandeln, was noch nicht behandelt wurde.
Glen_b -Reinstate Monica
Könnten Sie auch klarstellen - das ist Bernoulli-Modell naive Bayes? vielleicht noch etwas?
Glen_b -Reinstate Monica
Sehen Sie sich das Beispiel hier unten an (kurz vor 'Siehe auch', wo sie Protokolle aufnehmen; beide Seiten zu potenzieren, aber die RHS "wie sie ist" zu belassen (als Exp einer Summe von Protokollen) wäre ein Beispiel für das Protokoll -sum-exp Trick. Gibt Ihnen das genügend Informationen bezüglich seiner Verwendung in Naive Bayes, um eine spezifischere Frage zu stellen?
Glen_b -Reinstate Monica

Antworten:

26

In

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

Sowohl der Nenner als auch der Zähler können sehr klein werden, typischerweise weil nahe 0 sein kann und wir viele von ihnen miteinander multiplizieren. Um Unterläufe zu vermeiden, kann man einfach das Protokoll des Zählers nehmen, aber man muss den log-sum-exp-Trick für den Nenner verwenden.p(xi|Ck)


Genauer gesagt, um Unterläufe zu verhindern:

  • Wenn wir nur zu wissen , welche Klasse Pflege der Eingang ( x = x 1 , ... , x n ) höchstwahrscheinlich gehört mit dem Maximum a posteriori (MAP) Entscheidungsregel, müssen wir nicht die Log- gelten Summen-Exp-Trick, da wir in diesem Fall den Nenner nicht berechnen müssen . Für den Zähler kann man einfach das Protokoll nehmen, um Unterläufe zu vermeiden: l o g ( p ( x | Y = C ) p ( Y = C ) )(y^)(x=x1,,xn)log(p(x|Y=C)p(Y=C)). Genauer:

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

    was wird, nachdem das Protokoll genommen wurde:

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)))
  • If we want to compute the class probability p(Y=C|x), we will need to compute the denominator:

    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)

    The element log( k=1|C|p(x|Y=Ck)p(Y=Ck)) may underflow because p(xi|Ck) can be very small: it is the same issue as in the numerator, but this time we have a summation inside the logarithm, which prevents us from transforming the p(xi|Ck) (can be close to 0) into log(p(xi|Ck)) (negative and not close to 0 anymore, since 0p(xi|Ck)1). To circumvent this issue, we can use the fact that p(xi|Ck)=exp(log(p(xi|Ck))) to obtain:

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

    At that point, a new issue arises: log(p(x|Y=Ck)p(Y=Ck)) may be quite negative, which implies that exp(log(p(x|Y=Ck)p(Y=Ck))) may become very close to 0, i.e. underflow. This is where we use the log-sum-exp trick:

    logkeak=logkeakeAA=A+logkeakA

    with:

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

    We can see that introducing the variable A avoids underflows. E.g. with k=2,a1=245,a2=255, we have:

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

    Using the log-sum-exp trick we avoid the underflow, with A=max(245,255)=245: logkeak=logkeakeAA=A+logkeakA=245+logkeak+245=245+log(e245+245+e255+245)=245+log(e0+e10)

    We avoided the underflow since e10 is much farther away from 0 than 3.96143×10107 or 1.798486×10111.

Franck Dernoncourt
quelle
2

Suppose we want to identify which of two databases is more likely to have generated a phrase (for example, which novel is this phrase more likely to have come from). We could assume independence of the words conditional on the database (Naive Bayes assumption).

Now look up the second link you have posted. There a would represent the joint probability of observing the sentence given a database and the ebts would represent the probability of observing each of the words in the sentence.

Sid
quelle