# Why is $p(y|x)$ infeasible when discussing Naive Bayes?

This is a question in which I think I am missing some key information. When discussing Naive Bayes, I've noticed that lecturers typically say that we really want is $$p(y|x)$$ (label given features), but that this becomes infeasible once $$x$$ is high-dimensional (since we won't observe many examples of $$y$$ for each specific instance of $$x$$). This is also what is stated in the Wikipedia article on Naive Bayes. Because of this, we use Bayes Rule to turn the problem on its head and estimate a generative model, and then use the "naive" assumption of feature independence given the class.

However, models such as linear regression and k-nearest neighbors do this just fine, albeit with the assumptions of neighboring points belonging to the same class (kNN) or with some linear relationship in the parameters (lin. reg.). This seems to contradict the general statement that estimating $$p(y|x)$$ becomes infeasible. Somethings missing?

Is it that the discussion of $$p(y|x)$$ in the context of Naive Bayes assumes Bernoulli/multinoulli distributions, for which the MLE is indeed sparse in this case? But that they leave out this information?

$$k$$-NN just measures the distances between observations and may suffer the curse of dimensionality as well as other algorithms. It also does not try finding the distribution of the variables, just makes local approximations. So it is hard to compare to the two other methods you mention.

Logistic regression (same applies to linear regression) makes the assumption that the model is linear

$$p(y|x) = \sigma(\beta_0 + \beta_1 x_1 + \beta_2 x_2 + \dots + \beta_k x_k)$$

Naive Bayes algorithm makes the assumption that the features are independent

$$p(x, y) = p(x_1 | y) \, p(x_2 | y) \dots p(x_k|y) \, p(y)$$

In both cases we assume a model that simplifies the conditional distribution to something computationally manageable.

You seem to be asking why can't we use the "full Bayes" algorithm, i.e. calculate $$p(x_1, x_2, \dots, x_k | y)$$ directly from the data. The problem is that the dimensionality of such distribution is so large, that you would need huge amount of data and tremendous computational resources.

Moreover, it might simply not be possible to find the full distribution. Imagine, for example, that you are building a spam detection algorithm. To calculate the full distribution of the data, you would need to observe $$n$$ samples per each of the possible combination of all the possible words. Even if you limit yourself to limited grammar of, say, 100 000 most common words, the number of possible combinations of those words is literally infinite.

• Thanks Tim! The juxtaposition of the assumptions they make and the notion of "full Bayes [...] directly from the data" made it click for me. I think for this material approaching it as a beginner, it's sometimes tricky to see the big picture of how the ideas relate. – jodles Oct 15 '19 at 9:05
• By the way, to actually derive the "full Bayes" solution directly from the data (i.e. frequency of occurrence for each data point), what would be the procedure? Choose some appropriate distribution, e.g. multinoulli and compute the MLE? – jodles Oct 15 '19 at 9:11
• @jodles I used quotation marks in around "full Bayes" because if you had enough data, then you don't need the Bayes theorem in here, you'd just calculate the empirical distribution of all the data. This would be just the joint empirical distribution of the data, i.e. count how often any of the combination of the data occurs divided by the total number of samples. – Tim Oct 15 '19 at 9:15
• Ah, I see. Thanks for clarifying! I think I got stuck on the notion that we would always require some choice of distribution (e.g. don't jump directly to mean and variance for a Gaussian model, even though intuitive, without having first derived it through MLE) -- but as you say, given sufficient data we can estimate a probability table from the empirical distribution of that data. Thanks again! – jodles Oct 16 '19 at 12:44