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?

naive-bayes underflow

— Josh
źródło

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:

p (Y = C | x) = \frac{p (x | Y = C) p (Y = C)}{\sum_{k = 1}^{| C |} p (x | Y = C_{k}) p (Y = 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)}$

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 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: $(\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 |}}{argmax} p (C_{k} | x_{1}, \dots, x_{n}) = \underset{k \in {1, \dots, | C |}}{argmax} p (C_{k}) \prod_{i = 1}^{n} p (x_{i} | 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)$
który staje się po pobraniu dziennika:

\begin{aligned} \hat{y} & = \underset{k \in {1, \dots, | C |}}{argmax} \log (p (C_{k} | x_{1}, \dots, x_{n})) \\ = \underset{k \in {1, \dots, | C |}}{argmax} \log (p (C_{k}) \prod_{i = 1}^{n} p (x_{i} | C_{k})) \\ = \underset{k \in {1, \dots, | C |}}{argmax} (\log (p (C_{k})) + \sum_{i = 1}^{n} \log (p (x_{i} | 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}$

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

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

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

— Franck Dernoncourt
źródło

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

— Sid
źródło

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

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?

— Lerner Zhang
źródło