Przykład działania sztuczki log-sum-exp w Naive Bayes

14

Czytałem o sztuczce log-sum-exp w wielu miejscach (np. Tutaj i tutaj ), ale nigdy nie widziałem przykładu, w jaki sposób jest ona stosowana konkretnie do klasyfikatora Naive Bayes (np. Z funkcjami dyskretnymi i dwiema klasami)

Jak dokładnie można uniknąć problemu niedopełnienia liczb przy użyciu tej sztuczki?

Josh
źródło
2
Jest tu kilka przykładów jego użycia, choć niekoniecznie wprost dla naiwnych Bayesów. Nie ma to jednak większego znaczenia, ponieważ pomysł na podstęp jest dość prosty i można go łatwo dostosować.
Glen_b
Prawdopodobnie problem jest przepełniony niż przepełniony.
Henry
Sugeruję, aby spróbować wyszukać przy niedopełnieniu , a następnie zaktualizować pytanie, aby dokładniej odpowiedzieć na to, co nie jest jeszcze objęte.
Glen_b
Czy mógłbyś także wyjaśnić - to jest naiwny Bayes, model Bernoulliego? może coś jeszcze?
Glen_b
Zobacz przykład tutaj , tuż na dole (tuż przed „Zobacz także”, gdzie biorą logi; wykładniczo obie strony, ale pozostawiając RHS „tak jak jest” (jako exp sumy logów) byłoby przykładem logu -sum-exp sztuczka. Czy to daje wystarczające informacje dotyczące jego użycia w Naive Bayes, aby zadać bardziej szczegółowe pytanie?
Glen_b -Reinstate Monica

Odpowiedzi:

26

In

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

zarówno mianownik i licznik może być bardzo mała, zwykle dlatego, że może być zbliżona do 0 i mnożymy wielu z nich ze sobą. Aby zapobiec niedomiarom, można po prostu wziąć log licznika, ale trzeba użyć lewy log-sum-exp dla mianownika.p(xi|Ck)


Mówiąc dokładniej, aby zapobiec niedomiarom:

  • Jeśli interesują nas tylko wiedząc, jakiej klasy wejście ( x = x 1 , ... , x n ) najprawdopodobniej należy do z maksimum a posteriori (MAP) reguły decyzyjnej, nie musimy stosować log- sztuczka sum-exp, ponieważ w tym przypadku nie musimy obliczać mianownika . W przypadku licznika można po prostu wziąć dziennik, aby zapobiec niedomiarom: l o g ( p ( x | Y = C ) p ( Y = C ) )(y^)(x=x1,,xn)log(p(x|Y=C)p(Y=C)). Dokładniej:

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

    który staje się po pobraniu dziennika:

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

    z:

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

    Widzimy, że wprowadzenie zmiennej pozwala uniknąć niedomiarów. Np. Przy , mamy:Ak=2,a1=245,a2=255

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

    Używając sztuczki log-sum-exp, unikamy niedomiaru, a : A=max(245,255)=245logkeak=logkeakeAA=A+logkeakA=245+logkeak+245=245+log(e245+245+e255+245)=245+log(e0+e10)

    niedomiaru, ponieważ jest znacznie dalej od 0 niż lub .e103.96143×101071.798486×10111

Franck Dernoncourt
źródło
2

Załóżmy, że chcemy ustalić, która z dwóch baz danych prawdopodobnie wygenerowała frazę (na przykład, która powieść jest bardziej prawdopodobna z tej frazy). Możemy założyć niezależność słów zależnych od bazy danych (założenie Naive Bayes).

Teraz wyszukaj drugi opublikowany link. Tam reprezentuje wspólne prawdopodobieństwo zaobserwowania zdania w bazie danych, a s reprezentuje prawdopodobieństwo zaobserwowania każdego słowa w zdaniu.aebt

Sid
źródło
1

Widzimy z tej odpowiedzi, że najmniejsza liczba w Pythonie (tylko weźmy na przykład) 5e-324wynika z IEEE754 , a przyczyna sprzętowa dotyczy również innych języków.

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

A każda liczba zmienna mniejsza niż ta prowadziłaby do 0.

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

Zobaczmy funkcję Naive Bayes with discrete features and two classeszgodnie z wymaganiami:

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

Pozwólcie, że utworzę tę funkcję przez proste zadanie poniżej NLP.

Postanawiamy wykryć, czy nadchodzący e-mail jest spamem ( ), czy nie spamem ( ), i dysponujemy słownikiem słów o wielkości 5000 ( ), a jedynym problemem jest to, czy pojawi się słowo ( ) ( ) w e-mailu lub nie ( ) dla uproszczenia ( Bernoulli naiwny 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)

Widzimy, że byłoby bardzo małe ze względu na prawdopodobieństwo (oba i będzie między 0 a 1) w , a zatem jesteśmy pewni, że produkt będzie mniejszy niż i otrzymamy po prostu .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

Potem pojawia się problem: jak obliczyć prawdopodobieństwo, że wiadomość e-mail jest spamem ? Lub jak obliczyć licznik i mianownik?p(S=1|w1,...wn)

Oficjalne wdrożenie możemy zobaczyć w 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

Dla licznika przekształcił iloczyn prawdopodobieństwa w sumę prawdopodobieństwa logarytmicznego, a dla mianownika użył logsumexp w scipy, który jest:

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

Ponieważ nie możemy dodać dwóch wspólnych prawdopodobieństw, dodając prawdopodobieństwo wspólnego dziennika, i powinniśmy wyjść z przestrzeni dziennika do przestrzeni prawdopodobieństwa. Ale nie możemy dodać dwóch prawdziwych prawdopodobieństw, ponieważ są one za małe i powinniśmy je przeskalować i dodać: i odłożyć wynik z powrotem do przestrzeni logów a następnie przeskaluj ponownie: w przestrzeni dziennika, dodając .s={0,1}ejllsmax_jlllogs={0,1}ejllsmax_jllmax_jll+logs={0,1}ejllsmax_jllmax_jll

A oto pochodna:

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

gdzie jest w kodzie.max_jlla_max

Gdy otrzymamy zarówno licznik, jak i mianownik w przestrzeni dziennika, możemy uzyskać prawdopodobieństwo warunkowe dziennika ( ), odejmując mianownik od licznika : logp(S=1|w1,...wn)

return jll - np.atleast_2d(log_prob_x).T

Mam nadzieję, że to pomaga.

Odniesienie:
1. Klasyfikator Bernoulliego naiwnego Bayesa
2. Filtrowanie spamu za pomocą Naive Bayesa - Który Naive Bayesa?

Lerner Zhang
źródło