Minimum Distance Classifier

The minimum distance classifier assigns $\mathbf{x}$ to the class with the nearest mean in Euclidean distance. It comes from special case 2 of the Gaussian Bayes classifier, ${\mathbf{\Sigma }}_i={\sigma }^2\mathbf{I}$, when all prior probabilities are also equal. It is a simpler form of the Linear Classifier.

Main idea

With $\boldsymbol{\Sigma}_i=\sigma^2\mathbf{I}$ the boundary is a hyperplane orthogonal to the line between the means. With equal priors, the rule is: assign $\mathbf{x}$ to the nearest mean. This is template matching.

---

Special Case 2: ${\mathbf{\Sigma }}_i={\sigma }^2\mathbf{I}$

All classes share the same diagonal, scalar covariance matrix ${\sigma }^2\mathbf{I}$, where $\mathbf{I}$ is the identity matrix.

When this case happens:

• all features (components of $\mathbf{x}$) are statistically uncorrelated
• each feature has the same variance ${\sigma }^2$

Useful results:

$${\mathbf{\Sigma }}_i={\sigma }^2\mathbf{I}\Rightarrow {\mathbf{\Sigma }}_i^{-1}=\mathbf{I}/{\sigma }^2,|{\mathbf{\Sigma }}_i|={\sigma }^{2d}$$

---

Discriminant Function

$$\begin{array}{rl}{g}_i(\mathbf{x})& =-\frac{1}{2}(\mathbf{x}-{\mathbf{\mu }}_i{)}^T{\mathbf{\Sigma }}^{-1}(\mathbf{x}-{\mathbf{\mu }}_i)+\ln p({\omega }_i)\\ & =-\frac{1}{2{\sigma }^2}(\mathbf{x}-{\mathbf{\mu }}_i{)}^T(\mathbf{x}-{\mathbf{\mu }}_i)+\ln p({\omega }_i)\\ & =-\frac{1}{2{\sigma }^2}({\mathbf{x}}^T\mathbf{x}-2{\mathbf{\mu }}_i^T\mathbf{x}+{\mathbf{\mu }}_i^T{\mathbf{\mu }}_i)+\ln p({\omega }_i)\end{array}$$

The quadratic term ${\mathbf{x}}^T\mathbf{x}$ is the same for all classes $i$, so drop it. Then multiply by the constant ${\sigma }^2$:

$$\begin{array}{rl}{g}_i(\mathbf{x})& ={\mathbf{\mu }}_i^T\mathbf{x}-{\mathbf{\mu }}_i^T{\mathbf{\mu }}_i/2+{\sigma }^2\ln p({\omega }_i)\\ & ={\mathbf{w}}_i^T\mathbf{x}+w_{i0}\end{array}$$

where ${\mathbf{w}}_i={\mathbf{\mu }}_i$ and $w_{i0}=-{\mathbf{\mu }}_i^T{\mathbf{\mu }}_i/2+{\sigma }^2\ln p({\omega }_i)$ is the threshold or bias for class ${\omega }_i$. This is a linear function of $\mathbf{x}$, so the result is a linear classifier.

Correction to slide 28

The slide says "multiplying the constant 2". The correct constant is ${\sigma }^2$. Multiplying by ${\sigma }^2>0$ does not change the decision, and it gives the ${\sigma }^2\ln p({\omega }_i)$ term in the result.

---

Decision Boundary

$$g_i(\mathbf{x})=g_j(\mathbf{x})\Rightarrow ({\mathbf{w}}_i-{\mathbf{w}}_j{)}^T\mathbf{x}+w_{i0}-w_{j0}=0$$ $$({\mathbf{\mu }}_i-{\mathbf{\mu }}_j{)}^T\mathbf{x}-({\mathbf{\mu }}_i^T{\mathbf{\mu }}_i-{\mathbf{\mu }}_j^T{\mathbf{\mu }}_j)/2+{\sigma }^2\ln [p({\omega }_i)/p({\omega }_j)]=0$$

The normal vector of this hyperplane is ${\mathbf{\mu }}_i-{\mathbf{\mu }}_j$. So the equation defines a hyperplane orthogonal to the line linking the two means.

Position of the hyperplane:

• with equal priors, $\ln [p({\omega }_i)/p({\omega }_j)]=0$ and the hyperplane passes through the midpoint $({\mathbf{\mu }}_i+{\mathbf{\mu }}_j)/2$
• with $p({\omega }_i)>p({\omega }_j)$, the hyperplane moves away from ${\mathbf{\mu }}_i$ toward ${\mathbf{\mu }}_j$, so the more probable class gets a larger region

---

Equal Priors: Minimum Distance Classifier

Start again from:

$$g_i(\mathbf{x})=-\frac{1}{2{\sigma }^2}(\mathbf{x}-{\mathbf{\mu }}_i{)}^T(\mathbf{x}-{\mathbf{\mu }}_i)+\ln p({\omega }_i)$$

If the prior probabilities are the same for all classes, $\ln p({\omega }_i)$ is the same for all classes and can be dropped. Multiply by the positive constant $2{\sigma }^2$:

$$g_i(\mathbf{x})=-(\mathbf{x}-{\mathbf{\mu }}_i{)}^T(\mathbf{x}-{\mathbf{\mu }}_i)=-d_{Eu}(\mathbf{x},{\mathbf{\mu }}_i)=-\Vert \mathbf{x}-{\mathbf{\mu }}_i{\Vert }^2$$

Correction to slide 29

The slide writes $-d_{Eu}(\mathbf{x},{\mathbf{\mu }}_i)=\Vert \mathbf{x}-{\mathbf{\mu }}_i\Vert$. This is missing the minus sign and the square. $d_{Eu}$ is the squared Euclidean distance, so the correct result is $-\Vert \mathbf{x}-{\mathbf{\mu }}_i{\Vert }^2$. The largest $g_i(\mathbf{x})$ is the smallest distance.

Decision rule:

• measure the Euclidean distance from $\mathbf{x}$ to each of the $c$ mean vectors
• assign $\mathbf{x}$ to the class of the nearest mean

This is a minimum distance classifier. If each mean vector is an ideal prototype or template for the patterns in its class, the procedure is template matching.

flowchart TD
    A["Gaussian classes<br/>Σi = σ²I"] --> B{"Equal priors?"}
    B -->|"No"| C["Linear classifier<br/>gi(x) = μiᵀx − μiᵀμi/2 + σ² ln p(ωi)"]
    B -->|"Yes"| D["Minimum distance classifier<br/>gi(x) = −‖x − μi‖²"]
    D --> E["Template matching<br/>nearest mean"]