# Proving that Gaussian Naive Bayes Decision Boundary is Linear

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 • Might it help if you expand the squares and collect terms with like powers? Oct 3, 2018 at 0:50

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

• you are right..i should have just expanded the quadratic term...
– raaj
Oct 3, 2018 at 3:10
• Correct. Also, you're missing variance terms in your derivation. Naive-Bayes does not assume all predictors have the same variance, but rather, predictors are independent conditional on the category. Oct 3, 2018 at 4:47
• oh i forgot to mention the variance/std in my question is 1
– raaj
Oct 3, 2018 at 16:30

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.