Proving that Gaussian Naive Bayes Decision Boundary is Linear

Question

I need to come up with a Proof that Gaussian Naive Bayes has a linear decision boundary (In this case for Y={0,1})

I tried to work it out, but I am not able to pull out the xi term as it is stuck in the squared term

Answer 1

Lets deal with the case that we have a new predictor value $x \in \mathbb{R}^p$.

Then, we write the decision rule as $$ \delta(x) = \frac{P(Y = 1 \mid X=x)}{P(Y=0 \mid X = x)}.$$ If $\delta(x) > 1$, then $P(Y = 1 \mid X=x) > P(Y=0 \mid X = x)$, so our rule would predict the subject with predictors $x$ belongs to class $Y = 1$. Taking the log of both sides of our rule, $$ \log{\delta(x)} = \log P(Y = 1 \mid X=x) - \log P(Y=0 \mid X = x),$$ so $\log{\delta(x)} > 0$ is an equivalent rule. Then, recall: $$ P(Y=j \mid X = x) = \frac{P(X=x \mid Y=j) P(Y=j)}{P(X=x)},$$ so letting $\pi_j = P(Y=j)$ for $j \in \left\{0, 1\right\}$, we have $$ \log{\delta(x)} = \log P(X=x \mid Y=0) + \pi_0 - \log P(X= x \mid Y=1) - \pi_1, $$ and the $\log P(X=x)$ cancel. Then, the Naive-Bayes model says that $$P(X=x \mid Y=j) \sim N_p(\mu_j, D)$$ where $D$ is a diagonal, symmetric and positive definite matrix for $j \in \left\{0, 1\right\}$. Thus, since $\log P(X=x \mid Y=j)$ is the multivariate normal log-likelihood for $j \in \left\{0, 1\right\}$, we have $$ \log{\delta(x)} \propto - (x - \mu_0)' D^{-1}(x - \mu_0) + (x - \mu_1)' D^{-1}(x - \mu_1) + C,$$ where $C$ is a constant which does not depend on $x$. Expanding the quadratic terms, $$ \log{\delta(x)} \propto - x'D^{-1} x + 2x' D^{-1} \mu_0 - \mu_0' D^{-1} \mu_0 + x'D^{-1}x - 2 x D^{-1}\mu_1 + \mu_1' D^{-1} \mu_1 + C,$$ and the quadratic terms cancel, and the $ -\mu_0 D^{-1} \mu_0'$ and $\mu_1 D^{-1} \mu_1$ are absorbed into the constant, so $$ \log{\delta(x)} \propto x'D^{-1}(\mu_0 - \mu_1) + \tilde{C}, $$ which is linear in $x$.

Answer 2

The answer is based off Prof. Raquel Urtasun's lecture notes Slide 20-25. Punchline: Both the classes have to share the same co-variance matrix as the necessary condition.

Let, the decision boundary be $$ d(x) = \frac{P(Y = 1 \mid X=x)}{P(Y=0 \mid X = x)},$$ and we classify according to $d>1$ for class 1 and vice versa. Taking a log on both sides we have $$\log{d(x)} = \log P(Y = 1 \mid X=x) - \log P(Y=0 \mid X = x).$$ Using Baye's rule, we can writre $$P(Y=j \mid X = x) = \frac{P(X=x \mid Y=j) P(Y=j)}{P(X=x)},$$ and denoting $\pi_j = P(Y=j)$, i.e. likelihood of being classified into the $j^{th}$ class, we can expand $\log(d(x))$ as $$\log{d(x)} = \log P(X=x \mid Y=0) + \pi_0 - \log P(X= x \mid Y=1) - \pi_1.$$

At this point we note that $$\log P(X=x \mid Y=0) = -(x - \mu_0)' \Sigma_0^{-1}(x - \mu_0)$$ and $$\log P(X=x \mid Y=1) = -(x - \mu_1)' \Sigma_1^{-1}(x - \mu_1).$$ Substituting both of these in the decision boundary equation we have: $$\log{d(x)} = -(x - \mu_0)' \Sigma_0^{-1}(x - \mu_0) + \pi_0 + (x - \mu_1)' \Sigma_1^{-1}(x - \mu_1) - \pi_1$$ this can only simplify to a linear equation in $x$ iff the quadratic terms cancel i.e. $\Sigma_1 = \Sigma_0$, or else the decision boundary remains quadratic.