5
$\begingroup$

In the fourth edition of "Artificial Intelligence: a modern approach" by Russel and Norvig, they write in section 12.6, regarding the Naive Bayes Model for text classification, the following:

The naive Bayes model assumes that words occur independently in documents, with frequencies determined by the document category. This independence assumption is clearly violated in practice. For example, the phrase “first quarter” occurs more frequently in business (or sports) articles than would be suggested by multiplying the probabilities of “first” and “quarter.” The violation of independence usually means that the final posterior probabilities will be much closer to 1 or 0 than they should be; in other words, the model is overconfident in its predictions. On the other hand, even with these errors, the ranking of the possible categories is often quite accurate.

(Emphasis mine)

I do not see why the assumption of conditional independence would lead the naive Bayes model to be overly confident in its predictions.

Just to make sure I understand their statement correctly, I assume that they mean that that naive Bayes is overly confident compared to non-naive Bayes. As an example, assuming we wanted to determine whether an article is a sport article or not and that $s = \text{sport article}, f=\text{"first" occured in article}, q=\text{"quarter" occured in article}$, we get the non-naive Bayes model as:

$$ P(s | f, q) = \dfrac{P(s)P(f, q|s)}{P(f, q|s)P(s)+P(f, q|\neg s)P(\neg s)} \quad (1.) $$
The conditional independence assumption then gives the naive Bayes model

\begin{align} P(s | f, q) = \dfrac{P(s)P(f, q|s)}{P(f, q|s)P(s)+P(f, q|\neg s)P(\neg s)} = \\\\ \dfrac{P(s)P(f|s)P(q|s)}{P(f|s)P( q|s)P(s)+P(f|\neg s)P(q|\neg s)P(\neg s)} \quad (2.) \end{align}

As far as I can see then, the statement amounts to saying that the numerator and denominator in $(2.)$ usually takes the value further away from $0.5$ than in $(1.)$. Is there a theoretical explanation for this or is it more of an empirical fact that just happens to be true?

$\endgroup$
4
  • 1
    $\begingroup$ I guess you are missing the prior probabilities in the partition function (denominator) in (1) and (2) $\endgroup$ Sep 11, 2021 at 23:02
  • 1
    $\begingroup$ Consider what happens when $P(f,q|s)$ is substantially greater than $P(f|s)P(q|s)$. $\endgroup$
    – jbowman
    Sep 12, 2021 at 2:18
  • $\begingroup$ @SandipanDey Good catch! I've edited that now. $\endgroup$
    – Paradox
    Sep 12, 2021 at 7:12
  • $\begingroup$ what about the fact that P(quarter|sport) < P(quarter|prev_word = first, category = sport) ? $\endgroup$
    – ofer-a
    Sep 12, 2021 at 9:15

1 Answer 1

1
$\begingroup$

For sports articles, the given bigram is much more frequent and will have much higher probability than the one is computed with naive assumption as the product of the probabilities for the corresponding unigrams, when compared to non-sports articles, as per assumption, so that we have,

$\frac{P(f, q|s)}{P(f|s)P(q|s)} \gg \frac{P(f, q|\neg s)}{P(f|\neg s)P(q|\neg s)} \quad \quad (3)$

here all probability values are $\in [0,1]$.

Now, we have, in (1), (ignoring the trivial cases and assuming non-zero probabilities)

$P(s | f, q) = \dfrac{P(s)P(f, q|s)}{P(f, q|s)P(s)+P(f, q|\neg s)P(\neg s)} = \dfrac{1}{1+\dfrac{P(f, q|\neg s)P(\neg s)}{P(f, q|s)P(s)}}$

Similarly from (2), we have,

$P_{naive}(s | f, q) = \dfrac{P(s)P(f|s)P(q|s)}{P(f|s)P( q|s)p(s)+P(f|\neg s)P(q|\neg s)P(\neg s)}=\dfrac{1}{1+\dfrac{P(f|\neg s)P(q|\neg s)P(\neg s)}{P(f|s)P(q|s)P(s)}}$

$\Rightarrow\frac{P_{naive}(s|f,q)}{P(s|f,q)}$

$=\dfrac{1+\dfrac{P(f, q|\neg s)P(\neg s)}{P(f, q|s)P(s)}}{1+\dfrac{P(f|\neg s)P(q|\neg s)P(\neg s)}{P(f|s)P(q|s)P(s)}}$

$=\dfrac{1+\dfrac{P(f, q|\neg s)}{P(f, q|s)}}{1+\dfrac{P(f|\neg s)P(q|\neg s)}{P(f|s)P(q|s)}}$, (let's assume a uniform prior for simplicity, i.e., $P(s)=P(\neg s)$)

$\gg 1$, from (3)

Hence, we have,

$P_{naive}(s|f,q) \gg P(s|f,q)$ (overconfidence)

$\endgroup$
4
  • $\begingroup$ Thank you for this. This is an interesting answer. I think $(3.)$ is a reasonable assumption, but the conclusion of the answer somewhat evades me. From the quoted passage, it seems that by overconfidence, the author means probabilities closer to $0$ or to $1$ than warranted. But $P_{naive}(s|f,q) >> P(s|f, q)$ does not necessarily imply that $P(s|f, q)$ is closer to $0.5$ than $P_{naive}(s|f,q)$. I think that the validity of such an implication depends on exactly how much bigger $P_{naive}(s|f,q)$ is than $P(s|f,q)$ and the value of $P(s|f,q)$. $\endgroup$
    – Paradox
    Sep 12, 2021 at 15:34
  • $\begingroup$ @Paradox if $P(s|f,q)$ is around $0.5$ (the original posterior has high uncertainty), it implies that the naive approximation $P_{naive}(s|f,q)$ reduces the uncertainty (entropy) by increasing the value closer to $1$ and simultaneously decreasing the value of $P_{naive}(\neg s|f,q)$ down to $0$. $\endgroup$ Sep 12, 2021 at 15:54
  • $\begingroup$ Yes, that is true. But doesn't this kind of beg the question then whether there actually is any empirical or theoretical reason for why $P(s|f,q)$ would be around $0.5$? $\endgroup$
    – Paradox
    Sep 12, 2021 at 16:51
  • $\begingroup$ @Paradox I guess with the same assumption (3) we can derive another corollary that when $P(s|f,q)$ is low (close to $0$) / very confident (with low uncertainty) then the naive assumption can increase the uncertainty of the predicted posterior making it under-confident. That way the conditional independence assumption is bad in this case too. $\endgroup$ Sep 12, 2021 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.