Why can logistic regression always outperform naive Bayes for every conditional distribution?

Question

We know that the generative model assumes that $X_i \perp X_{-i}| Y$; while the discriminative model assumes that $p(Y=1|x; \alpha)=\frac{e^{\alpha_0+\sum_{i=1}^n\alpha_ix_i}}{1+e^{\alpha_0+\sum_{i=1}^n\alpha_ix_i}}=\frac{1}{1+e^{-\alpha_0-\sum_{i=1}^n\alpha_ix_i}}$. And it(slide 19) says that the later can be derived from(as below, and more information can be found here) the former because if $p(x_i|y)\sim \mathscr{N}(\mu_{iy}, \sigma_i)$ and $p(y)\sim Bernoulli(\pi)$ the P(y|x_1,...,x_n) would have a logistic form. \begin{align} p(y = 1 \mid \mathbf{x}) &= \frac{p(\mathbf{x} \mid y = 1) p(y = 1)}{p(\mathbf{x} \mid y = 1) p(y = 1) + p(\mathbf{x} \mid y = 0) p(y = 0)} \\ &= \frac{1}{1 + \frac{p(\mathbf{x} \mid y = 0) p(y = 0)}{p(\mathbf{x} \mid y = 1) p(y = 1)}} \\ &= \frac{1}{1 + \exp\left( -\log\frac{p(\mathbf{x} \mid y = 1) p(y = 1)}{p(\mathbf{x} \mid y = 0) p(y = 0)} \right)} \\ &= \sigma\left( \sum_i \log \frac{p(x_i \mid y = 1)}{p(x_i \mid y = 0)} + \log \frac{p(y = 1)}{p(y = 0)} \right) \end{align}

It seems that I can truly obtain a logistic form but I don't understand why we can claim the following:

that every conditional distribution that can be represented using naive Bayes can also be represented using the logistic model

What are the other conditional distributions? Do I understand it right that every conditional distribution implies some other conditional distributions except $p(y|x)$?

In On Discriminative vs. Generative classifiers: A comparison of logistic regression and naive Bayes, Ng said that given sufficient data logistic regression would be at least as good as Naive Bayes. Could we see that from the formulas? Is it because of these two assumptions: $p(x_i|y)\sim \mathscr{N}(\mu_{iy}, \sigma_i)$ and $p(y)\sim Bernoulli(\pi)$? But why these two assumptions are necessary?

Answer 1

You quote:

that every conditional distribution that can be represented using naive Bayes can also be represented using the logistic model

This only means what you had written down before: If the model behaves as assumed by naive Bayes, it can be written down as a special case of a logistic model. This does not talk about "other conditional distributions".

However, this statement does not imply that logistic regression always "outperforms" naive Bayes, because logistic regression estimates a different parameterisation, which if the naive Bayes model assumption is fulfilled may not be optimal, and naive Bayes may make more efficient use of the data. The "given a sufficient amount of data" qualification is crucial here; if the number of variables doesn't grow with $n$, logistic regression can emulate naive Bayes more and more precisely, ultimately reaching a performance that is arbitrarily close to the one of naive Bayes in case naive Bayes's model assumption is fulfilled.

Otherwise one can expect the more flexible logistic regression to be better, however I'm not sure if examples can be constructed that violate model assumptions of both approaches in such a way that naive Bayes will do better even for large $n$. The plain fact that logistic regression can emulate naive Bayes is not enough to rule this out in my opinion, as it is conceivable that the logistic regression parameter estimates are led astray in a way not possible for naive Bayes.

I should also add that I have seen the term "naive Bayes" for a method that assumes x-variables independent but not necessarily normal (for example using kernel density estimators), in which case it is not always a special case of logistic regression.

Answer 2

I learned from the blog that if $P(X_i|Y_j)$ is a Gaussian distribution it can be written as a Gaussian function and hence the denominator and the numerator are all Gaussian functions, thereby the fraction $ \sum_i \log \frac{p(x_i \mid y = 1)}{p(x_i \mid y = 0)}$ can be transformed into a $WX$ form and log $\frac{p(y = 1)}{p(y = 0)}$ into a bias b, making the Gaussian Naive Bayes the same as logistic regression.

And because the logistic regression doesn't assume that X's are independent logistic regression can perform better than Naive Bayes.

Hope that I am right. If not please kindly help correct.