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

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?

In

$$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)}$$

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(x_i \vert C_k)$

---

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 ) $(\hat{y})$$(\mathbf{x}=x_1, \dots, x_n)$$log \left( p(\mathbf{x}|Y=C)p(Y=C) \right)$. Dokładniej:

  $$\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)$$

  który staje się po pobraniu dziennika:

$$\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}$$

• $p(Y=C|\mathbf{x})$

  $$\begin{align} \log \left( p(Y=C|\mathbf{x}) \right) &= \log \left( \frac{p(\mathbf{x}|Y=C)p(Y=C)}{~\sum_{k=1}^{|C|}{}p(\mathbf{x}|Y=C_k)p(Y=C_k)} \right)\\ &= \log \left( \underbrace{p(\mathbf{x}|Y=C)p(Y=C)}_{\text{numerator}} \right) - \log \left( \underbrace{~\sum_{k=1}^{|C|}{}p(\mathbf{x}|Y=C_k)p(Y=C_k)}_{\text{denominator}} \right)\\ \end{align}$$

  $\log \left( ~\sum_{k=1}^{|C|}{}p(\mathbf{x}|Y=C_k)p(Y=C_k) \right)\\ $$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$$p(x_i \vert C_k) = \exp \left( {\log \left(p(x_i \vert C_k) \right)} \right)$

  $$\log \left( ~\sum_{k=1}^{|C|}{}p(\mathbf{x}|Y=C_k)p(Y=C_k) \right) =\log \left( ~\sum_{k=1}^{|C|}{} \exp \left( \log \left( p(\mathbf{x}|Y=C_k)p(Y=C_k) \right) \right) \right)$$

  $\log \left( p(\mathbf{x}|Y=C_k)p(Y=C_k) \right)$$\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}$$

  z:

  • $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.$

  Widzimy, że wprowadzenie zmiennej pozwala uniknąć niedomiarów. Np. Przy , mamy:$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}$

  Używając sztuczki log-sum-exp, unikamy niedomiaru, a : $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}$

  niedomiaru, ponieważ jest znacznie dalej od 0 niż lub .$e^{-10}$$3.96143\times 10^{- 107}$$1.798486 \times 10^{-111}$

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.$a$$e^{b_{t}}$

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|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)}$$

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=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)

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)\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

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

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 .$\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$

A oto pochodna:

$\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}$

gdzie jest w kodzie.$max\_jll$$a\_max$

Gdy otrzymamy zarówno licznik, jak i mianownik w przestrzeni dziennika, możemy uzyskać prawdopodobieństwo warunkowe dziennika ( ), odejmując mianownik od licznika : $\log p(S=1|w_1, ... w_n)$

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?