Homework 3

2. Gaussian Classification

Let $f_{X\mid Y=C_i}(x) \sim \mathcal{N}(\mu _i,\sigma^2)$ for a two-class, one-dimensional ($d = 1$) classification problem with classes $C_1$ and $C_2$, $P(Y = C_1) = P(Y = C_2) = 1/2$, and $\mu _2 > \mu _1$.

$Q1$

Find the Bayes optimal decision boundary and the corresponding Bayes decision rule by finding the point(s) at which the posterior probabilities are equal. Use the 0-1 loss function.

$Answer:$ 对于0-1损失函数，贝叶斯最优决策规则是：对于一个给定的观测值 $x$，我们应该选择后验概率 $P(Y=C_i|X=x)$ 最大的那个类别$C_i$。而决策边界即为两者的后验概率相等：

$$P(Y=C_1|X=x) = P(Y=C_2|X=x)$$

也即：

$$p(x|Y=C_1) P(Y=C_1) = p(x|Y=C_2) P(Y=C_2)$$

由于两个类别的先验概率相同，有：

$$p(x|Y=C_1) = p(x|Y=C_2)$$

带入正态分布PDF中：

$$\begin{aligned} &\exp\left(-\frac{(x-\mu _1)^2}{2\sigma^2}\right)=\exp\left(-\frac{(x-\mu _2)^2}{2\sigma^2}\right) \\ &\Rightarrow \ln\left(\exp\left(-\frac{(x-\mu _1)^2}{2\sigma^2}\right)\right) = \ln\left(\exp\left(-\frac{(x-\mu _2)^2}{2\sigma^2}\right)\right) \\ &\Rightarrow -\frac{(x-\mu _1)^2}{2\sigma^2} = -\frac{(x-\mu _2)^2}{2\sigma^2} \\ &\Rightarrow (x-\mu _1)^2 = (x-\mu _2)^2 \\ &\Rightarrow x^2 - 2x\mu _1 + \mu _1^2 = x^2 - 2x\mu _2 + \mu _2^2 \\ &\Rightarrow -2x\mu _1 + \mu _1^2 = -2x\mu _2 + \mu _2^2 \\ &\Rightarrow 2x\mu _2 - 2x\mu _1 = \mu _2^2 - \mu _1^2 \\ &\Rightarrow 2x(\mu _2 - \mu _1) = (\mu _2 - \mu _1)(\mu _2 + \mu _1) \\ &\Rightarrow 2x = \mu _1 + \mu _2 \quad(\text{since }\mu _2>\mu _1) \\ &\Rightarrow x = \frac{\mu _1 + \mu _2}{2} \end{aligned}$$

决策边界为两个均值的中点。

$Q2$

Suppose the decision boundary for your classifier is $x = b$. The Bayes error is the probability of misclassification, namely

$$P_e = P\big((C_1\ \text{misclassified as}\ C_2)\cup (C_2\ \text{misclassified as}\ C_1)\big)$$

Show that the Bayes error associated with this decision rule, in terms of $b$, is

$$e(b)=\frac{1}{2\sqrt{2\pi}\,\sigma}\left( \int_{-\infty}^{b}\exp\left(-\frac{(x-\mu _2)^2}{2\sigma^2}\right)\,dx +\int_{b}^{\infty}\exp\left(-\frac{(x-\mu _1)^2}{2\sigma^2}\right)\,dx \right)$$

$proof:$

$$P_e(b)=P\big(\text{decide }C_2\mid\text{actual }C_1\big)\,P(\text{actual }C_1) +P\big(\text{decide }C_1\mid\text{actual }C_2\big)\,P(\text{actual }C_2)$$

将先验概率带入这个公式：

$$P_e(b) = \frac{1}{2} P(X > b | Y=C_1) + \frac{1}{2} P(X < b | Y=C_2) \tag{1}$$

决策边界是 $x=b$ 并且 $\mu _2 > \mu _1$，自然的分类规则是：

$$\text{decide}\; \begin{cases} C_2, & x > b\\[4pt] C_1, & x < b \end{cases}$$

$P\big(\text{decide }C_2\mid\text{actual }C_1\big)\,P(\text{actual }C_1)$ 的实际概率为$P(X > b | Y=C_1)$，这可以通过下面的积分得到：

$$\int_b^\infty p(x|Y=C_1) dx = \int_b^\infty \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{(x-\mu _1)^2}{2\sigma^2}\right) dx$$

$P\big(\text{decide }C_1\mid\text{actual }C_2\big)\,P(\text{actual }C_2)$ 的实际概率为$P(X < b | Y=C_2)$，这可以通过下面的积分得到：

$$\int_{-\infty}^b p(x|Y=C_2) dx = \int_{-\infty}^b \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{(x-\mu _2)^2}{2\sigma^2}\right) dx$$

带入 $(1)$，整理即得：

$$P_e(b) = \frac{1}{2\sqrt{2\pi}\sigma} \left( \int_b^\infty \exp\left(-\frac{(x-\mu _1)^2}{2\sigma^2}\right) dx + \int_{-\infty}^b \exp\left(-\frac{(x-\mu _2)^2}{2\sigma^2}\right) dx \right)$$