# What is Bayes decision rule?

Assume binary classification i.e. $$y \in \{-1,1\}$$ and that the underlying joint probability distribution generating the data is known i.e. $$P_{x,y}(x,y)$$ is known

I was told that Bayes decision rule was the predictor you choose when solving the following minimization problem with the indicator variable cost function (indicating whether you are right or wrong):

$$min_{c \in \mathcal{H}} \mathbb{E}_{x,y}[\mathbb{1}_{\{c(x) \neq y \}}]$$

I was wondering, what was the resulting predictor $$c^*$$ from solving the above optimization problem and what its relation to the known distribution generating the data was. i.e. what was the predictors $$c^*$$ relation to $$P_{y|x}(1|x)$$ and $$P_{y|x}(-1|x)$$.

What I had done so far was expand $$\mathbb{E}_{x,y}[\mathbb{1}_{\{c(x) \neq y \}}]$$:

$$\mathbb{E}_{x,y}[\mathbb{1}_{\{c(x) \neq y \}}] = \mathbb{E}_{x} \mathbb{E}_{y|x}[\mathbb{1}_{\{c(x) \neq y \}}]$$

and then minimize the following:

$$\mathbb{E}_{y|x}[\mathbb{1}_{\{c(x) \neq y \}}] = P_{y|x}(1 | x)\mathbb{1}_{\{c(x) \neq 1\}} + P_{y|x}(-1|x)\mathbb{1}_{\{ c(x) \neq 1\}}$$

But I had a hard time moving on because I was unsure how to minimize the above expression. Intuitively I want to choose the predictor that makes my error the lowest. So I would choose the label $$1$$ or $$-1$$, depending on which had the highest probability of occurring. But I was having a hard time linking that intuition with the math and the equation above, in a precise or rigorous matter.

What is the explicit function for $$c^*(x)$$?

Is the following function the correct one? If it is, why so?

$$c^*(x) = sign(2p_{y|x}(1|x) - 1)$$

Consider random variables $X$ and $Y$, where $Y \in \{+1,-1\}$. When the observation $X$ has value $x$, the decision rule $c(x)$, which takes on one of the two values $+1$ and $-1$, tells us what value the rule thinks $Y$ has taken on. The choice of decision function $c(x)$ effectively partitions the range of $X$ into two disjoint sets $\Gamma_{+1}$ and $\Gamma_{-1}$, that is, $c(x)$ can be expressed as $$c(x) = \begin{cases}+1, & x \in \Gamma_{+1},\\-1, & x \in \Gamma_{-1}. \end{cases}$$ The experiment is performed, resulting in $(X,Y)$ taking on value $(x,y)$, but we can only observe the value of $x$. We apply the function $c(x)$ to get our decision $+1$ or $-1$ as to what the value of $y$ is. A superior being (who knows everything including the value of $y$ that has been hidden from us) then tells us whether we made a mistake or not: mistakes when $y$ does not match the decision $c(x)$ that we reached. Let $f_{-1}(x)$ denote the conditional density of $X$ given that $Y = -1$. Then, given that $Y=-1$, we make a mistake if the observed value of $X$ is in the region $\Gamma_{+1}$, and the conditional probability of error is thus $\displaystyle P(E\mid Y=-1) = \int_{\Gamma_{+1}} f_{-1}(x)\,\mathrm dx.$ Similarly, the conditional probability of error when $Y=+1$ is $\displaystyle P(E\mid Y=+1) = \int_{\Gamma_{-1}} f_{+1}(x)\,\mathrm dx.$ Hence, the unconditional probability of error $P(E)$ of this decision rule is \begin{align} P(E) &= P\{E \mid Y = -1\}P\{Y = -1\} + P\{E \mid Y = +1\}P\{Y = +1\}\\ &= \int_{\Gamma_{+1}}\pi_{-1}\cdot f_{-1}(x)\,\mathrm dx + \int_{\Gamma_{-1}}\pi_{+1}\cdot f_{+1}(x)\,\mathrm dx\\ &= \int_{\Gamma_{+1}}\pi_{-1}\cdot f_{-1}(x)\,\mathrm dx + \int_{\Gamma_{-1}}\pi_{+1}\cdot f_{+1}(x)\,\mathrm dx\\ &\quad + \int_{\Gamma_{-1}}\pi_{-1}\cdot f_{-1}(x)\,\mathrm dx - \int_{\Gamma_{-1}}\pi_{-1}\cdot f_{-1}(x\,\mathrm dx\\ &= \pi_{-1} \int_{\mathbb R}f_{-1}(x)\,\mathrm dx + \int_{\Gamma_{-1}}\left[\pi_{+1}\cdot f_{+1}(x) - \pi_{-1}\cdot f_{-1}(x)\right]\,\mathrm dx\\ P(E) &= \pi_{-1} + \int_{\Gamma_{-1}}\left[\pi_{+1}\cdot f_{+1}(x) - \pi_{-1}\cdot f_{-1}(x)\right]\,\mathrm dx\tag{1} \end{align}

The Bayesian decision rule is the rule which minimizes the right side of $(1)$. We can do nothing with the first term which is the same for all decision rules, but by clever choice of the region $\Gamma_{-1}$ (the decision rule is effectively defined by the region $\Gamma_{-1}$), we can make $P(E)$ smaller. Note that the integrand in $(1)$ can be positive or negative, and by choosing $$\Gamma_{-1} = \{x \colon \pi_{+1}\cdot f_{+1}(x) - \pi_{-1}\cdot f_{-1}(x) \leq 0\}, \tag{2}$$ (thus excluding from $\Gamma_{-1}$ all points $x$ for which $\pi_{+1}\cdot f_{+1}(x) - \pi_{-1}\cdot f_{-1}(x) > 0$), we make sure that the integrand is never positive in the range of integration, and so the integral has as negative a value as possible. Hence, the decision rule described in $(2)$ minimizes $P(E)$, and is the Bayesian decision rule.

So how does all this play out in terms of posterior distributions? The posterior distribution of $Y$ given $X$ is discrete, and the Bayesian decision rule works out to be to choose whichever value of $Y$ has greater posterior probability. In fact, we have that \begin{align} P\{Y=+1\mid X = x\} &= \frac{\pi_{+1}f_{+1}(x)}{\pi_{+1}\cdot f_{+1}(x) + \pi_{-1}\cdot f_{-1}(x)}\tag{3}\\ P\{Y=-1\mid X = x\} &= \frac{\pi_{-1}f_{-1}(x)}{\pi_{+1}\cdot f_{+1}(x) + \pi_{-1}\cdot f_{-1}(x)}\tag{4} \end{align} and so, choosing whichever posterior probability is larger gives the same decision rule as $(2)$. Now, if $P\{Y=+1\mid X = x\} = p_{y|x}(1|x)$ in the OP's notation is larger than $P\{Y=-1\mid X = x\}$, then is is true that $p_{y|x}(1|x) > \frac 12$, and so $\operatorname{sgn}(2p_{y|x}(1|x) -1) = +1$, and so

Yes, the Bayes decision rule $c^*(x)$ can be expressed as $\operatorname{sgn}(2p_{y|x}(1|x) -1)$

However, the fact that this choice minimizes $P(E)$ is a lot harder to see from $(3)$ and $(4)$ or from the succinct expression $\operatorname{sgn}(2p_{y|x}(1|x) -1)$ than from the development that led to $(2)$. Or at least, that is how I, a non-statistician, perceive the matter; your mileage may vary.

It is easier to prove it, if you formulate the problem in a slightly different way:

$$P(c(x) \neq y) \geq P(c^{*}(x) \neq y)$$ or equivalently, $$\mathbb{E}_{x,y}\left[1_{\{c(x)=y\}}\right] \leq \mathbb{E}_{x,y}\left[1_{\{c^{*}(x)=y\}}\right]$$ and instead of having $$y \in \{-1,1\}$$, you have $$y \in \{0,1\}$$.

Notice that $$P_{y|x}(0|x) = 1-P_{y|x}(1|x)$$ and $$1_{\{c(x) = 0\}} = 1-1_{\{c(x) = 1\}}$$, hence if we subtract,

$$\mathbb{E}_{y|x}\left[1_{\{c^{*}(x)=y\}}\right] - \mathbb{E}_{y|x}\left[1_{\{c(x)=y\}}\right] = P_{y|x}(1|x)\left(1_{\{c^{*}(x)=1\}}-1_{\{c(x)=1\}}\right) +P_{y|x}(0|x)\left(1_{\{c^{*}(x)=0\}}-1_{\{c(x)=0\}}\right) = \left(2P(1|x)-1\right)\left(1_{\{c^{*}(x)=1\}}-1_{\{c(x)=1\}}\right) \geq 0$$

Now, if $$P(1|x) > 1/2$$, then by the definition of $$c^{*}(x)$$, $$c^{*}(x) = 1$$, and since $$1_{\{c(x)=1\}} \leq 0$$, then this expression is greater or equal to zero. Likewise, if $$P(1|x) < 1/2$$, then, by definition, $$c^{*}(x) = 0$$ and since $$1_{\{c(x)=1\}} \geq 0$$, then the inequality applies.

• I have a question about your notation: by $==$ did you mean $\equiv$ (\equiv)? The == sign is used rather in programming (correct me if I'm wrong).
– Tim
Dec 19 '14 at 21:21
• @Tim I agree. Same holds for != indicating "not equals" Jan 10 '20 at 7:59