4
$\begingroup$

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

enter image description here

$\endgroup$
1
  • $\begingroup$ Might it help if you expand the squares and collect terms with like powers? $\endgroup$
    – Glen_b
    Oct 3, 2018 at 0:50

2 Answers 2

2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ you are right..i should have just expanded the quadratic term... $\endgroup$
    – raaj
    Oct 3, 2018 at 3:10
  • 1
    $\begingroup$ 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. $\endgroup$
    – WazyMaze
    Oct 3, 2018 at 4:47
  • $\begingroup$ oh i forgot to mention the variance/std in my question is 1 $\endgroup$
    – raaj
    Oct 3, 2018 at 16:30
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.