Пример того, как трюк log-sum-exp работает в наивном байесовском

Я читал о трюке log-sum-exp во многих местах (например, здесь и здесь ), но никогда не видел пример того, как он применяется конкретно к наивному байесовскому классификатору (например, с дискретными функциями и двумя классами)

Как именно можно избежать проблемы числового снижения при использовании этого трюка?

naive-bayes underflow мистифицировать
источник

Здесь есть несколько примеров его использования, хотя это не обязательно явно для наивного Байеса. Однако это вряд ли имеет значение, так как идея трюка довольно проста и легко адаптируется.

Glen_b

Проблема, скорее всего, заключается в недостаточном объеме, а не в переполнении.

Генри

Я бы посоветовал вам попробовать поиск по недополнению , а затем обновить свой вопрос, чтобы более конкретно указать, что уже не охватывалось.

Glen_b

Не могли бы вы также уточнить - это модель Бернулли наивного Байеса? что-то еще, возможно?

Glen_b

Посмотрите пример здесь , прямо внизу (как раз перед «См. Также», где они берут журналы; возводят в степень обе стороны, но оставляют RHS «как есть» (как exp из суммы журналов), будет примером журнала Трюк -sum-exp. Дает ли это вам достаточную информацию, касающуюся его использования в

Наивном Байесе,

Ответы:

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

и знаменатель, и числитель могут стать очень маленькими, как правило, потому что может быть близко к 0, и мы умножаем многие из них друг на друга. Чтобы предотвратить потери, можно просто взять журнал числителя, но для знаменателя нужно использовать трюк log-sum-exp. $p(x_i \vert C_k)$

Более конкретно, для предотвращения недопущения:

Если нам важно знать, к какому классу вход скорее всего, относится с максимальным апостериорным (MAP) правилом принятия решений, мы не будем нужно применить трюк log-sum-exp, так как нам не нужно вычислять знаменатель в этом случае. Для числителя можно просто взять журнал, чтобы предотвратить потери: . Более конкретно: $(\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)$
который становится после взятия журнала:

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

Элемент может опуститься из-за того, что может быть очень маленьким: это та же проблема, что и в числителе, но на этот раз у нас есть суммирование внутри логарифма, что не позволяет нам преобразовать (может быть близко к 0) в (отрицательно и больше не близко к 0, поскольку ). Чтобы обойти эту проблему, мы можем использовать тот факт, что чтобы получить: $\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}))))$

В этот момент возникает новая проблема: может быть весьма отрицательным, что означает, что может стать очень близким к 0, т.е. Вот где мы используем трюк 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}$

с участием:
- $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.$
Мы можем видеть, что введение переменной позволяет избежать потерь. Например, с , имеем: $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}$
Используя трюк log-sum-exp, мы избегаем : : $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}$

Мы избежали потери, поскольку намного дальше от 0, чем или . $e^{-10}$ $3.96143\times 10^{- 107}$ $1.798486 \times 10^{-111}$

Франк Дернонкур
источник

Предположим, мы хотим определить, какая из двух баз данных с большей вероятностью сгенерировала фразу (например, из какого романа эта фраза с большей вероятностью пришла). Мы могли бы предполагать независимость слов, обусловленных базой данных (наивное байесовское предположение).

Теперь найдите вторую ссылку, которую вы опубликовали. Здесь будет представлять собой общую вероятность соблюдения предложения для данной базы данных, а s будет представлять вероятность наблюдения каждого из слов в предложении. $a$ $e^{b_{t}}$

Sid
источник

Из этого ответа мы можем видеть, что наименьшее число в Python (просто возьмем его, например) 5e-324связано с IEEE754 , а аппаратная причина относится и к другим языкам.

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

И любое число с плавающей запятой меньше этого приведет к 0.

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

И давайте посмотрим на функцию наивного Байеса, with discrete features and two classesкак вам нужно:

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

Позвольте мне описать эту функцию простой задачей НЛП ниже.

Мы решили определить, является ли приходящее письмо спамом ( ) или не спамом ( ), и у нас есть словарный запас размером 5000 слов ( ), и единственное беспокойство вызывает то, что слово ( ) встречается ( ) в электронном письме или нет ( ) для простоты ( Бернулли наивный Байес ). $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)

Мы можем видеть, что будет очень маленьким из-за вероятностей (оба и будет между 0 и 1) в , и, следовательно, мы уверены, что произведение будет меньше и мы просто получим . $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

Тогда возникает проблема: как мы можем вычислить вероятность того, что письмо является спамом ? Или как мы можем вычислить числитель и знаменатель? $p(S=1|w_1, ... w_n)$

Мы можем увидеть официальную реализацию в 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

Для числителя он преобразовал произведение вероятностей в сумму логарифмического правдоподобия, а для знаменателя он использовал logsumexp в scipy, который:

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

Потому что мы не можем добавить две совместные вероятности, добавив их совместную логарифмическую вероятность, и мы должны выйти из логарифмического пространства в вероятностное пространство. Но мы не можем добавить две истинные вероятности, потому что они слишком малы, и мы должны масштабировать их и сделать сложение: и вернуть результат обратно в пространство журнала затем измените его масштаб: в пространстве журнала, добавив . $\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$

А вот и вывод:

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

где - это в коде. $max\_jll$ $a\_max$

Как только мы получим как числитель, так и знаменатель в лог-пространстве, мы можем получить условную вероятность ( ), вычитая знаменатель из числителя : $\log p(S=1|w_1, ... w_n)$

return jll - np.atleast_2d(log_prob_x).T

Надеюсь, это поможет.

Ссылка:
1. Наивный байесовский классификатор Бернулли
2. Фильтрация спама наивным байесовским фильтром - какие наивные байесовские?

Лернер Чжан
источник