0
$\begingroup$

We are given a classification problem within Bayesian decision theory, with 3 equi-probable classes $w_i,\,i=1,2,3$ and 2 features (or dimensions). The average of the three classes are known to be $\mu_1 = \pmatrix{0 \\ 0}$, $\mu_2 = \pmatrix{6\\0}$ and $\mu_3 = \pmatrix{-4 \\ 0}$. The covariance matrix is assumed to be the same for all three classes, given by $\Sigma = \pmatrix{2 & 0 \\0 & 2}$. Using Bayesian classification, what would be the decision boundary?

My attempt: In the Bayesian framework, given a feature vector $x = \pmatrix{x_1\\x_2}$ the decision (or discriminant) function for class $w_i$ is in general given by $$ d_i(x) = -0.5\, \text{ln} |\Sigma_i| - 0.5 (x - \mu_i)^{T} \Sigma^{-1}(x-\mu_i) + \text{ln}(P(w_i)), $$ where $P(w_i)$ is the probability of class $w_i$. In the problem at hand, the discriminant function simplifies to $$d_i(x)= - 0.5 (x - \mu_i)^{T} \Sigma^{-1}(x-\mu_i). $$

According to my textbook, the decision surface (which I guess is just another term for decision boundary?) is the $x$ for which $d_i(x) = 0$ for all $i$. Writing this our for $i=1$ gives $$(x_1,x_2)\pmatrix {0.5&0\\0&0.5} \pmatrix{x_1\\x_2} = \frac{x_1^2 + x_2^2}{2} = 0 \Rightarrow x_1 = x_2 = 0.$$ Similarly for $i=2$ you get $x_1 = 6 $ and $x_2 = 0$ and for $i=3$, $x_1=-4$ and $x_2 = 0$.

I know in advance that the solution to the problem is $x_1=3$ and $x_1= -2$ but this doesn't appear to be deducible from our computations. So what's the trick?

$\endgroup$
4
  • 3
    $\begingroup$ A decision boundary would be $d_i(x)=d_j(x)>d_k(x)$ as $d_i(x)=0$ for one or several $i$'s does not make sense. $\endgroup$
    – Xi'an
    Jan 2, 2021 at 9:44
  • $\begingroup$ Thanks for the hint. Does the same rule apply when we have more than 3 features? That is, if we have $n$ features, we're still looking for some $x$ for which 2 discriminants are equal and larger than all the remaining $n-2$ discriminants? $\endgroup$
    – User32563
    Jan 2, 2021 at 15:15
  • $\begingroup$ Sorry, I would not know, as I have never met this notion before. $\endgroup$
    – Xi'an
    Jan 2, 2021 at 15:16
  • $\begingroup$ No worries! Thanks for the hint above all the same. It's been already a great help. $\endgroup$
    – User32563
    Jan 2, 2021 at 15:55

1 Answer 1

2
$\begingroup$

Under all three hypotheses, $X_1$ and $X_2$ are two uncorrelated random variables with $E[X_1\mid H_i]$ taking on values $0,6,-4$ according as $i=1,2,3$ while $E[X_2\mid H_i]=0$ regardless of the value of $i$, and $\operatorname{var}(X_1\mid H_i) = \operatorname{var}(X_2\mid H_i)=2$ for all choices of $i$. Thus, the likelihoods of the three hypotheses are $$L(H_i;x_1,x_2)=f_{X_1,X_2\mid H_i}(x_1,x_2\mid H_i) = f_i(x_1,x_2; H_i)$$ where $f_i(x_1,x_2; H_i)$ is the joint pdf/pmf of $X_1$ and $X_2$ when $H_i$ is the true hypothesis. Since the a priori probabilities of the hypotheses are equal, the Bayesian decision rule is the same as the maximum-likelihood decision rule:

Upon observing $(x_1,x_2)$, choose the hypothesis that has the maximum likelihood, that is, decide that $H_k$ is the true hypothesis where $$k = \arg\max_i L(H_i;x_1,x_2) = \arg\max_i f_i(x_1,x_2; H_i).$$

Note that in general, $X_1$ and $X_2$ cannot be assumed to be (conditionally) independent random variables and so it is not necessarily true that the decision boundaries are straight lines as the OP wants them to be. One important case when the decision boundaries are indeed straight lines occurs when $X_1$ and $X_2$ are assumed to be (conditionally) independent normal random variables with identical variances (and possibly different means) under all hypotheses. In this special case that the OP is considering, the value taken on by $X_2$ is irrelevant as far as the decision is concerned, and we are left with the problem of deciding which of three equally likely hypotheses is true given the value of $X_1$ only. A brief mental visualization of the pdfs of $\mathcal N(0,\sqrt{2}), \mathcal N(6,\sqrt{2}), \mathcal N(-4,\sqrt{2})$ look like immediately suggests that the decision regions are $$ \Gamma_1 = (-2,3], \quad \Gamma_2 = (3,\infty), \quad \Gamma_3 = (-\infty,-2],$$ and the decision boundaries are $x_1=-2$ and $x_1=3$ exactly as the OP's solution manual says.


Turning to the discriminant functions that the OP knows about, note that for the specific problem (independent normally distributed observations with identical variance), the discriminant functions are the log-likelihoods and so the decision rule is still the same:

Upon observing $(x_1,x_2)$, choose the hypothesis that has the maximum log-likelihood, that is, decide that $H_k$ is the true hypothesis where $$k = \arg\max_i \ln L(H_i;x_1,x_2) = \arg\max_i \ln f_i(x_1\mid H_i) + \ln f_i(x_2; H_i).$$

Now, since $f_1(x_2; H_1) = f_2(x_2;H_2) = f_3(x_2;H_3)\sim \mathcal N(0,\sqrt{2}),$ we can ignore the $\ln f_i(x_2; H_i)$ term in the discriminant function; it is not relevant to the decision as to which of $\ln L(H_i;x_1,x_2)$ is the largest. So, we are down to deciding which of $$\ln f_1(x_1; H_1) = -\frac{x_1^2}{4}, \quad \ln f_2(x_1;H_2) = -\frac{(x_1-6)^2}{4}, \quad \ln f_3(x_1;H_3)-\frac{(x_1+4)^2}{4}$$ which can be done with a lot of formalism and tortuous mathematical calculations but I prefer the simpler visual approach that says that the three functions are identical downwards parabolas that differ only in where the apexes are (at $0$, $6$ and $-4$), and so the decision boundaries are obviously $x_1=3$ and $x_1=-2$ as derived earlier (also via visualization).

$\endgroup$
3
  • $\begingroup$ Thank you very much for your time and help. Do you think a simpler solution is feasible, one that primarily relies on the discriminant function? Because the topics of hypothesis testing or maximum likelihood aren't perfectly covered by my course (which is biomedical signal processing). $\endgroup$
    – User32563
    Jan 3, 2021 at 20:07
  • $\begingroup$ @Erfan Your discriminant functions are just the natural logarithms of what most people including me call the likelihoods; indeed we know your discriminants as log-likelihood functions. Since the logarithm is a monotone increasing function, finding which likelihood of the three is the largest (my way of expressing it) gives the same result as your comparison of the three log-likelihoods. Do your math correctly and you will get the same answer as I did. $\endgroup$ Jan 4, 2021 at 3:43
  • $\begingroup$ Thanks for the update! $\endgroup$
    – User32563
    Jan 6, 2021 at 18:30

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.