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

Question

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?

Answer 1

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