# 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. Commented May 29, 2018 at 10:44
• Thank you for asking this. I was having the same question, and judging from the number of wrong answers on both ds.SE and stats.SE, there is nothing embarrassing about it. Commented Feb 7, 2022 at 21:36

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)$ Commented May 23, 2018 at 8:44
• the features are independent given the class (factorial distribution), each feature is normalized independently. Commented May 23, 2018 at 9:27
• please explain. see the link to NB MN - features are counts. en.wikipedia.org/wiki/… Commented May 23, 2018 at 13:15
• you cannot design counts to be independent if they sum to n Commented May 23, 2018 at 22:09
• forget about normalisation, this is not the issue. The issue is the assumption of independence whereas the multinomial distribution is dependent Commented Jun 3, 2018 at 19:15

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 Commented May 23, 2018 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. Commented May 23, 2018 at 8:49
• scikit-learn's documentation abuses notation and only adds to the confusion. Therein, $x_i$ is used for conditionally independent features ($P(\mathbf x|y) = \prod_i P(x_i|y)$), as well as for not independent counts $x_i$, which are jointly distributed as $Mult(\theta_{y1}, \dots \theta_{yn})$. This is exactly the contradiction OP was pointing at. Commented Feb 7, 2022 at 21:03

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 Commented Jul 16, 2018 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. Commented Jul 17, 2018 at 10:35
• What do you mean by position vs. order? Commented Jul 17, 2018 at 15:48
• There are multiple issues with your answer, starting with _"...here the bold character $X_i$ represent r.v", which would imply that $P(X_i|Y=c_k)$ is a random variable, because a function of a r.v. is a r.v. Yet the main issue is that your answer does not address the question. I guess, what you mean by "order" and "position", would be best referred to as "column/feature-wise" and "row/record-wise" (or the other way around). The question is about conditional independence of features, not of sampled observations. Commented Feb 7, 2022 at 21:35

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.