# Naive Bayes Multinomial, independence assumption misunderstood

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

• As I mentioned in my answer, you confuse two things - multinomial and categorical (because of terminology). This also means that the equations you wrote aren't the ones that are used - see the link I posted for the correct equations. – Jakub Bartczuk May 29 '18 at 10:44

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.

• I don't see how it answers the question. $p(x_i|c)=p_i^x_i(1-p_i)^(n-x_i) \binom{n}{k}$ but multiplying all these is not the $p(x_1,x_2,...,x_n|c)$ – Hanan Shteingart May 23 '18 at 8:44
• the features are independent given the class (factorial distribution), each feature is normalized independently. – Fadi Bakoura May 23 '18 at 9:27
• please explain. see the link to NB MN - features are counts. en.wikipedia.org/wiki/… – Hanan Shteingart May 23 '18 at 13:15
• p(x1,x2,...,xn|c) the likelihood is factorial distribution by design (features independent given the class), i.e. it's equal to multiplying each feature p(xi|c) – Fadi Bakoura May 23 '18 at 16:37
• you cannot design counts to be independent if they sum to n – Hanan Shteingart May 23 '18 at 22:09

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.

• I don't see how this answers the problem – Hanan Shteingart May 23 '18 at 8:47
• Well, there's no problem, since the Multinomial Naive Bayes doesn't use the actual multinomial distribution, so what you mentioned as Problem 1 doesn't exist. – Jakub Bartczuk May 23 '18 at 8:49

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.

• Multinomial distribution already include the order independence assumption. Actually removing the multinomial coefficient reduces the distribution to a one where order is important... (e.g. probability for a specific sequence). Thus, I fear your explanation is not valid – Hanan Shteingart Jul 16 '18 at 8:59
• @HananShteingart I think we should distinguish the "order" and the "position". Multinomial distribution does include the "order" independence, but it does not include positional independence. Different orders don't matter, but different positional combinations do——that is where the coefficient come from. – LollipopKnight Jul 17 '18 at 10:35
• What do you mean by position vs. order? – Hanan Shteingart Jul 17 '18 at 15:48