Naive Bayes Multinomial, independence assumption misunderstood

Question

This is embarrassing but I think I miss understand something.

1. In multinomial distribution, "while the trials are independent, their outcomes X are dependent because they must be summed to n." wiki

2. Naive Bayes assumption is that the features are independent (given the class): "assume that each feature $x_{i}$ is conditionally independent of every other feature" wiki

Thus, how can 1&2 co-exist in what's known as the Multinomial Naive-Bayes model?

Specifically, $p(x_i|c)=p_i^{x_i}(1-p_i)^{n-x_i}\binom{n}{k}$ and $p(x_1,...,x_n)=\frac{n!}{\prod_i{x_i}!}\prod{p_i^{x_i}}$ thus $p(x_1,...,x_n) \ne \prod_ip(x_i|c) $

Answer 1

Their outcomes X are dependent because they must be summed to n

If you are really want to model multiple experiments probabilistically, please do not forget the normalization constant that make the unnormalized quantity normalized by integrating/summing them to one.

Multinomial Naive Bayes model, as described by Manning et al (2008), estimates the conditional probability of a particular word/term/token given a class as the relative frequency of term t in documents belonging to class c:

Thus this variation takes into account the number of occurrences of term t in training documents from class c, including multiple occurrences Not multiple experiments.

see The Naive Bayes Text Classifier

Answer 2

Your confusion stems from the fact that in ML communities people sometimes call categorical distribution multinomial, and also Bernoulli distribution is called binomial.

As for Naive Bayes, see scikit-learn's documentation provides a good explanation.

Answer 3

I found the answer in this document named Text classification and Naive Bayes, I think it gives detailed explanations for you questions.

Of course, I would like to share some of my own explanations, too.

Firstly, I need to introduce some notations, this is important to correct your statements about the question:

The naive bayes assumption shows: $P(X|Y=c_k)=P(X_1,X_2,...,X_n|Y=c_k)=\prod_{i=1}^{n}P(X_i|Y=c_k)$, here the bold character $X_i$ represent r.v, not the values.

The key of multinomial NB is that it assumes $P(X_i|Y=c_k)$ is a multinomial distribution with $n=1$, especially $P(X_i|P=c_k)$ obeys the same distributions for all $X_i$ (actually this is the simplified situation, but it is common for text classification).

Suppose $X_i$ chooses values from the set $\{a_1,a_2,...,a_m\}$,let $p_j$ denotes the probability of $P(X_i=a_j|Y=c_k)$, $n_j$ denotes the occurrences of $X_i=a_j$ and $n=n_1+n_2+...+n_m$,(here $n$ is nothing to do with $n$ in $X_n$, just for convenience). So $P(X_i|Y=c_k)=P((n_1,n_2,...n_m)|Y=c_k)=\frac{n！}{n_1!n_2!···n_m!}p_1^{n_1}p_2^{n_2}···p_m^{n_m}=p_1^{n_1}p_2^{n_2}···p_m^{n_m}$, because $n=1$.

Now we turn to the joint probability $P(X_1,X_2,...,X_n|Y=c_k)$.Since every $X_i$ choose values from $\{a_1,a_2,...,a_m\}$, the result sequence $(X_1,X_2,...,X_n)$ can be represent as $(n_1,n_2,...,n_m)$, which means the occurrences of different results $\{a_1,a_2,...,a_m\}$ , actually this is a multinomial distribution with repeats of $n$. We have $P(X_1,X_2,...,X_n|Y=c_k)=P((n_1,n_2,...n_m)|Y=c_k)=\frac{n！}{n_1!n_2!···n_m!}p_1^{n_1}p_2^{n_2}···p_m^{n_m}$, here $n=n_1+n_2+...+n_m$.

Well, you can see for the present, $\prod_{i=1}^{n}P(X_i|Y=c_k)$ is not equal to $P(X_1,X_2,...,X_n|Y=c_k)$ because they are different in the coefficient $\frac{n！}{n_1!n_2!···n_m!}$.

Here comes a another assumption: positional independence(see the document linked above),it assumes the positions of result $a_j$ in the sequence $(X_1,X_2,...,X_n)$ doesn't matter. This assumption means given an occurrences of $a_j$,say $n_j$, the different combinations $C_n^{n_j}$ doesn't matter. For the coefficient in multinomial distribution, $\frac{n！}{n_1!n_2!···n_m!}=C_n^{n_1}C_{n-n_1}^{n_2}...C_{n-n_1-n_2...-n_{m-1}}^{n_m}$,namely this coefficient is eliminated by the positional independence assumption.

Maybe the way I interpret the feature vector $(X_1,X_2,...,X_n)$ is some kind of confusing, so I strongly recommend you reading the document I linked because you can get a better understand in the specific text classification problem.

Answer 4

There exists a wide-spread confusion (or misconception) about Multinomial Naive Bayes. Here is my understanding based on skimming through lecture notes linked in this comment (the file has been removed from the original location, but can still be found elsewhere).

"Multinomial Naive Bayes" is a misnomer. The claims that Multinomial NB is simply a Naive Bayes model with multinomially distributed features (conditioned on a class) are wrong. The consensus definition of "Multinomial NB" on Wikipedia and scikit-learn documentation is different. Namely, $\mathbf X\mid(Y=y) \sim \mathrm{Mult}(\boldsymbol\theta_y)$, where $\mathbf X = (X_1,\dots, X_D) $ and $Y$ are random variables for features and the class, respectively. Parameters $\boldsymbol\theta_y=(\theta_{y1},\dots,\theta_{yD}),\,\theta_{yi}\in[0,1], \sum_i \theta_{yi} = 1$ are estimated for each $y\in1,\dots ,K$.

Clearly, features $X_i$ are not independent (conditioned on $Y$), because $p(\mathbf{x}|y)=\frac{(\sum_{i}x_{i})!}{x_{1}!\dots x_{D}!}\prod_{i}\theta_{yi}^{x_{i}}$ cannot be represented as a product of terms that involve only $x_i$. Thus, the Naive Bayes assumption breaks for $X_i$: $$p(\mathbf x| y) \neq \prod_i p(x_i| y). $$

While the Naive Bayes assumption breaks when applied to $X_i$, it may hold when applied to other features.

Consider text classification. Let a sentence be represented as $\mathbf z$, where $z_j\in1,\dots,D$ is a code of the $j$th word in the given sentence. We use a vocabulary of size $D$. Thus, a sentence is described by the random variables $Z_j|Y=y ~\sim\mathrm{Cat}(\boldsymbol\theta_y)$, where $\theta_{yi}$ is the probability that a word with code $i$ occurs at position $j$ in a sentence of category $y$. The assumption that words found in different parts of a sentence are independent (conditioned on the topic of the sentence) is somewhat reasonable. Thus, $$p(\mathbf{z}|y)={\prod_{j}p(z_{j}|y)},$$

which is precisely the Naive Bayes assumption applied to $\mathbf Z$. Note that $z_j,j=1,\dots,N$ are word codes, not word counts. Because this model disregards the order of words in a sentence, we may forget about it too and only store word counts: $x_i, i=1,\dots,D$ is the number of times the word with code $i$ occurred in a given sentence. As far as I know, such models are called a "bag of words".

The bottom line is as follows. We use features $\mathbf x=(x_i)_{i=1}^D$, which are (jointly) multinomially distributed. But the Naive Bayes assumption applies to a different set of features, $\mathbf z=(z_j)_{j=1}^N$. Sometimes this distinction is not explicitly made, and notation is abused (as in scikit-learn documentation), which is why this question might be asked.

---

Remark on the 2nd paragraph. Strictly speaking, we have a family of multinomial distribution $\mathbf X\mid(Y=y) \sim \mathrm{Mult}(\boldsymbol\theta_y,N)$, where $N=\sum_i X_i$ is an unknown parameter which varies from data point to data point. E.g., two different observations $\mathbf x^{(1)}=(1, 2, 3)$ and $\mathbf x^{(2)}=(1, 2, 2)$, are drawn from different multinomials, with $N=6$ and $N=5$, respectively. In the context of text classification, $N$ is the length of a sentence or a text excerpt. Without specifying $N$ or a distribution over $N$, it is impossible to generate data. For simplicity and because we are interested in discriminative modelling, I disregarded this detail.