Contoh bagaimana trik log-sum-exp bekerja di Naive Bayes

Saya telah membaca tentang trik log-sum-exp di banyak tempat (misalnya di sini , dan di sini ) tetapi belum pernah melihat contoh bagaimana itu diterapkan secara khusus untuk classifier Naive Bayes (misalnya dengan fitur diskrit dan dua kelas)

Bagaimana tepatnya seseorang menghindari masalah underflow numerik menggunakan trik ini?

naive-bayes underflow Josh
sumber

Ada beberapa contoh penggunaannya di sini, meskipun tidak harus secara eksplisit untuk Bayes naif . Namun, itu hampir tidak penting, karena ide triknya cukup mudah dan mudah beradaptasi.

Glen_b -Reinstate Monica

Masalahnya lebih cenderung menjadi underflow daripada overflow.

Henry

Saya sarankan Anda mencoba pencarian di bagian bawah , dan kemudian perbarui pertanyaan Anda untuk lebih spesifik membahas apa pun yang belum tercakup.

Glen_b -Reinstate Monica

Bisakah Anda juga mengklarifikasi - ini adalah Bernoulli-model naif Bayes? sesuatu yang lain mungkin?

Glen_b -Reinstate Monica

Lihat contoh di sini , tepat di bagian bawah (tepat sebelum 'Lihat Juga' di mana mereka mengambil log; eksponensial kedua belah pihak tetapi meninggalkan RHS "apa adanya" (seperti exp dari jumlah log) akan menjadi contoh log -sum-exp trick. Apakah itu memberi Anda informasi yang cukup terkait dengan penggunaannya di Naif Bayes untuk mengajukan pertanyaan yang lebih spesifik?

Glen_b -Reinstate Monica

Jawaban:

Dalam

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

baik penyebut dan pembilangnya bisa menjadi sangat kecil, biasanya karena bisa mendekati 0 dan kami mengalikan banyak dari mereka satu sama lain. Untuk mencegah underflow, seseorang dapat dengan mudah mengambil log dari pembilang, tetapi kita perlu menggunakan trik log-sum-exp untuk penyebut. $p(x_i \vert C_k)$

Lebih khusus lagi, untuk mencegah underflow:

Jika kita hanya peduli mengetahui kelas mana input kemungkinan besar milik dengan aturan keputusan maksimum a posteriori (MAP), kita tidak harus menerapkan trik log-sum-exp, karena kita tidak harus menghitung penyebut dalam kasus itu. Untuk pembilang, cukup ambil log untuk mencegah arus bawah: . Lebih spesifik: $(\hat{y})$ $(\mathbf{x}=x_1, \dots, x_n)$ $log \left( p(\mathbf{x}|Y=C)p(Y=C) \right)$

$\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)$
yang menjadi setelah mengambil log:

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

Jika kita ingin menghitung probabilitas kelas , kita perlu menghitung penyebutnya: $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}$

Elemen dapat di bawah karena bisa sangat kecil: ini adalah masalah yang sama seperti pada pembilang, tetapi kali ini kami memiliki penjumlahan di dalam logaritma, yang mencegah kami mengubah (bisa dekat dengan 0) ke dalam (negatif dan tidak dekat dengan 0 lagi, karena ). Untuk menghindari masalah ini, kita dapat menggunakan fakta bahwa untuk mendapatkan: $\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}))))$

Pada titik itu, muncul masalah baru: mungkin cukup negatif, yang menyiratkan bahwa dapat menjadi sangat dekat dengan 0, yaitu underflow. Di sinilah kami menggunakan trik log-sum-exp : $\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}$

dengan:
- $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.$
Kita dapat melihat bahwa memperkenalkan variabel menghindari arus bawah. Misalnya dengan , kita memiliki: $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}$
Dengan menggunakan trik log-sum-exp kita menghindari underflow, dengan : $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}$

Kami menghindari aliran bawah karena jauh lebih jauh dari 0 daripada atau . $e^{-10}$ $3.96143\times 10^{- 107}$ $1.798486 \times 10^{-111}$

Franck Dernoncourt
sumber

Misalkan kita ingin mengidentifikasi dari dua basis data mana yang lebih mungkin menghasilkan frasa (misalnya, novel mana yang frasa ini lebih cenderung berasal). Kita dapat mengasumsikan independensi kata-kata yang tergantung pada database (asumsi Naif Bayes).

Sekarang lihat tautan kedua yang telah Anda poskan. Di sana akan mewakili probabilitas gabungan dari mengamati kalimat yang diberikan database dan akan mewakili probabilitas mengamati setiap kata dalam kalimat. $a$ $e^{b_{t}}$

Sid
sumber

Kita dapat melihat dari jawaban ini bahwa angka terkecil dalam Python (anggap saja) adalah 5e-324karena IEEE754 , dan penyebab perangkat keras juga berlaku untuk bahasa lain.

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

Dan setiap float yang lebih kecil dari itu akan menghasilkan 0.

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

Dan mari kita lihat fungsi Naif Bayes with discrete features and two classesseperti yang Anda inginkan:

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

Biarkan saya instantiate fungsi itu dengan tugas NLP sederhana di bawah.

Kami memutuskan untuk mendeteksi apakah email yang datang adalah spam ( ) atau bukan spam ( ) dan kami memiliki kosakata kata berukuran 5.000 ( ) dan satu-satunya masalah adalah jika sebuah kata ( ) muncul ( ) di email atau tidak ( ) untuk kesederhanaan ( Bernoulli naif 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)

Kita dapat melihat bahwa akan sangat kecil karena probabilitasnya (baik dan akan berada antara 0 dan 1) di , dan karenanya kami yakin bahwa produk akan lebih kecil dari dan kami hanya mendapatkan . $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

Kemudian muncul masalah: Bagaimana kita bisa menghitung probabilitas email adalah spam ? Atau bagaimana kita bisa menghitung pembilang dan penyebutnya? $p(S=1|w_1, ... w_n)$

Kita bisa melihat implementasi resmi di 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

Untuk pembilang itu dikonversi produk probabilitas ke jumlah kemungkinan log dan untuk penyebutnya menggunakan logsumexp dalam scipy yaitu:

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

Karena kita tidak dapat menambahkan dua probabilitas gabungan dengan menambahkan log kemungkinan gabungannya, dan kita harus keluar dari ruang log ke ruang probabilitas. Tetapi kami tidak dapat menambahkan dua probabilitas benar karena terlalu kecil dan kami harus menskalakannya dan melakukan penambahan: dan mengembalikan hasilnya ke dalam ruang log lalu kembali: di ruang log dengan menambahkan . $\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$

Dan di sini adalah derivasi:

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

di mana adalah dalam kode. $max\_jll$ $a\_max$

Setelah kita mendapatkan pembilang dan penyebut dalam ruang log kita bisa mendapatkan probabilitas bersyarat log ( ) dengan mengurangi penyebut dari pembilang : $\log p(S=1|w_1, ... w_n)$

return jll - np.atleast_2d(log_prob_x).T

Semoga itu bisa membantu.

Referensi:
1. Bernoulli Naive Bayes Classifier
2. Penyaringan Spam dengan Naive Bayes - Naive Bayes yang mana?

Lerner Zhang
sumber