# Why is it easier to estimate $P(X|Y)$ rather than $P(Y|X)$ in terms of number of parameters?

In chapter 3 of the book by Mitchell ("Generative and discriminative classifiers: Naive Bayes and logistic regression") he states that "accurately estimating P(X|Y) typically requires many more examples. To see why, consider the number of parameters we must estimate when Y is boolean and X is a vector of n boolean attributes. In this case, we need to estimate a set of parameters

$$\theta_{ij} \equiv P(X=x_i|Y=y_i)$$

where the index $$i$$ takes on $$2^n$$ possible values (one for each of the possible vector values of $$X$$), and $$j$$ takes on $$2$$ possible values. Therefore, we will need to estimate approximately $$2^{n+1}$$ parameters."

Is that meaning it is needed to find a parameter for each probability for each possible combination of $$X$$ and $$Y$$? Given I've done that, how to put all together?

The author compares $$P(Y)$$ (not $$P(Y|X)$$) and $$P(X|Y)$$ in terms of estimation complexity, due to the quickly growing $$2^n$$ term wrt number of dimensions. This is because of the dependence modelling in the joint distribution. Naive Bayes uses conditional independence assumption and relaxes this to $$2n$$ terms.
• I'm not getting where that $2^n$ comes from. Is that due to the law of total probability? Feb 15, 2020 at 16:04
• when X is boolean with dimension n, there are $2^n$ different possibilities for it. Feb 15, 2020 at 20:56