Trouble reading multinomial naive bayes notation

Question

$C_{MAP}$: most likely class (i.e., "maximum a posteriori")

$C_{NB}$: Naive Bayes

x: document d is represented as $x_n$ features or words

$c_j$: I think it's a class j

Source is here on page 27: http://www.stanford.edu/class/cs124/lec/naivebayes.pdf

---

Anyway,

$$ \begin{aligned} C_{MAP} &= \mathop{\text{argmax}}_{c\in C} P(c|d) \\&= \mathop{\text{argmax}}_{c \in C} \frac{P(d|c)P(c)}{P(d)} \qquad \text{(Bayes Rule)} \\&= \mathop{\text{argmax}}_{c\in C} P(d|c)P(c) \end{aligned}$$

Firstly, I thought Bayes Rule was just $\frac{P(d|c)}{P(d)}$, which is just conditional probability of the number of occurrences of {c & d}/d, so why is $P(c)$ multiplied by $P(d|c)$? And why is $c|d$ flipped to $d|c$?

Also, for multinomial naive bayes classifier, we have:

$$C_{NB} = \mathop{\text{argmax}}_{c \in C} P(c_j)\prod P(x | c). $$

I'm not sure how to read that equation... Is it saying Classifiers for N = the max probability of class j * PI of x in X * Probability of (x given c)?

If someone could help break down that notation that would be great.

Thanks!

Answer 1

MAP = maximum a posteriori

Going down your equation line by line:

$$ \underset{ \boldsymbol{c \in C} }{\operatorname{argmax}} P( c | d ) $$

means there is a class (C) of things. For each element of that class, calculate P( c | d )

an equivalent is

Type bestc = C[ 0 ];

for (Type c : C ){
  if (P( c | d ) > P( bestc | d )
    bestc = c;
}

return bestc

next line: bayes' theorem says you can flip conditioning, that is

$P(A | B ) = \frac{ P(B | A) \cdot P( A ) }{ P(B) }$

next line: you are selecting a c, and note that $P(d)$ is constant in c. Thus you don't have to do the division.

The multinomial naive bayes classifier: By basic probability theorems, you can break down a joint probability as follows (where $P(A,B,C,D) = $ the probability of A and B and C and D) $$ \begin{align} P(A,B,C,D) & = P(A) \cdot P(B,C,D|A) \\ & = P(A) \cdot P(B|A) \cdot P(C,D|A,B) \\ & = P(A) \cdot P(B|A) \cdot P(C|A,B) \cdot P(D \vert A,B,C) \end{align} $$

Then you apply the naive bayes assumption, that is, we assume $$ P(D | A, B, C ) = P(D| class) $$

That is, you have a bunch of observations, in typical machine learning notation, that look like $ (y^{(i)}, \boldsymbol{x}^{(i)} )$ that is, we have $N$ observations indexed by $i$ where $y^{(i)}$ is a class and $\boldsymbol{x}^{(i)}$ is a vector of predictors. In a typical use case, $i$ is a single email, $y^{(i)}$ is spam/not spam, and $\boldsymbol{x}^{(i)}$ is 1/0 counts for whether a vocabulary of words was present or not in that email.

Thus naive bayes says, as per the argmax in your first equation, we will train a classifier so that it will, for each example $y^{(new)}$, predict the probability that $y^{(new)}$ is spam and notspam, end up with two numbers, and classify as the class with the larger probability. And our naive bayes assumption, for example: $$ \begin{align} P(y = \text{spam} | \boldsymbol{x} ) & = ... \\ & = \frac{ P( \boldsymbol{x} | y = \text{spam} ) \cdot P(y = \text{spam}) }{ P( \boldsymbol{x} ) } \\ & \text{ here I used bayes' theorem to flip conditioning} \\ & = P( \boldsymbol{x} | y = \text{spam} ) \cdot P(y = \text{spam}) \\ & \text{ because } P( \boldsymbol{x} ) \text{ doesn't depend on } c \\ & = P( x_{1},...,x_{m} | y = \text{spam}) \cdot P(y = \text{spam}) \\ & = P( x_{1} | y = \text{spam} ) \cdot P(x_{2:m} | x_{1}, y = \text{spam} ) \cdot P(y = \text{spam}) \\ & = P( x_{1} | y = \text{spam} ) \cdot P( x_{2} | x_{1}, y = \text{spam} ) \cdot P( x_{3:m}| y = \text{spam} ) \cdot P(y = \text{spam}) \\ & = \ldots \\ & = P( x_{1} | y = \text{spam} ) \cdot P( x_{2} | x_{1}, y = \text{spam} ) \cdot P( x_{3} | x_{1:2}, y = \text{spam} ) \cdot \ldots \cdot P( x_{m} | x_{1:m-1}, y = \text{spam} ) \cdot P(y = \text{spam} ) \\ & \text{and now I apply the naive bayes assumption} \\ & = P( x_{1} | y = \text{spam} ) \cdot P( x_{2} | y = \text{spam} ) \cdot P( x_{3} | y = \text{spam} ) \cdot \ldots \cdot P( x_{m} | y = \text{spam} ) \cdot P(y = \text{spam} ) \\ & = P(y=\text{spam}) \cdot \prod_{i=1}^{m} P( x_{i} | y = \text{spam} ) \end{align} $$ where again, the naive bayes assumption is that $P( x_{k} | y = \text{spam}, x_{k+1:m} ) = P( x_{k} | y = \text{spam} )$ note that this is a very strong assumption, equivalent to saying that given an email from your friend that is not spam, the probability that the words sportscenter and basketball appear equals the probability that sportscenter appears times the probability basketball appears, which wildly misestimates that probability.