Bayes Decision Rule

• Objective is to reduce error probability in classification.
• Requires prior probabilities $P(ω_i)$ and conditional probability density functions $p(x|ω_i)$.

Bayes Formula

• Describes the relationship between conditional and posterior probabilities:

  $P(ω_i|x) = \frac{p(x|ω_i)P(ω_i)}{p(x)}$

  • $p(x) = \sum_{i=1}^{c} p(x|ω_i)P(ω_i)$

• A posteriori probability: $P(ω_i|x)$ is the probability of category $ω_i$ given observation $x$.

• Bayes decision rule: Assign to $ω_1$ if $P(ω_1|x) > P(ω_2|x)$, otherwise assign to $ω_2$.

Minimum Error Rate

• Classification error is $P(error|x) = min[P(ω_1|x), P(ω_2|x)]$.
• To minimize error, select $ω_i$ if $P(ω_i|x) > P(ω_j|x)$ for all $j \neq i$.

Discriminant Functions

• Decision boundaries can be defined using discriminant functions $g_i(x)$.
• Assign to $ω_i$ if $g_i(x) > g_j(x)$ for all $j \neq i$.
• Possible forms:
  • $g_i(x) = P(ω_i|x)$
  • $g_i(x) = p(x|ω_i)P(ω_i)$
  • $g_i(x) = ln p(x|ω_i) + ln P(ω_i)$

Two-Category Case

• Can define a single discriminant function $g(x) = P(ω_1|x) - P(ω_2|x)$.
• Assign to $ω_1$ if $g(x) > 0$, and $ω_2$ if $g(x) < 0$.
• Likelihood ratio: $l(x) = \frac{p(x|ω_1)}{p(x|ω_2)}$.
• Decide $ω_1$ if $l(x) > \frac{P(ω_2)}{P(ω_1)}$, otherwise decide $ω_2$.

Cost Functions

• Let $\alpha_i$ represent the action of deciding the state of nature is $ω_i$

• $\lambda_{ij} = \lambda(\alpha_i|ω_j)$ is the cost of action $\alpha_i$ when the true state is $ω_j$.

• Expected cost of action $\alpha_i$:

  $R(\alpha_i|x) = \sum_{j=1}^{c} \lambda_{ij}P(ω_j|x)$

• Bayes decision rule: Minimize expected cost $R(\alpha_i|x)$.

Minimum Error Rate

• Cost function: $\lambda_{ij} = 0$ if $i = j$, and $\lambda_{ij} = 1$ if $i \neq j$.
• Risk: $R(\alpha_i|x) = \sum_{j=1}^{c} \lambda_{ij}P(ω_j|x) = \sum_{j \neq i} P(ω_j|x) = 1 - P(ω_i|x)$.
• Minimizing risk is equivalent to maximizing $P(ω_i|x)$.

Bayes Classifier

• Uses Bayes decision rule to minimize expected cost.
• Requires:
  • Prior probabilities $P(ω_i)$.
  • Conditional probability density functions $p(x|ω_i)$.
  • Cost functions $\lambda_{ij}$.

Curse of Dimensionality

• The number of training samples needed to accurately estimate probability density functions increases exponentially with the dimensionality of the feature space.