Multiclass LDA Boundaries And Decision Regions

From Linear Scores to Multiclass Geometry

In linear discriminant analysis, every class is scored by an affine function of the observation. Comparing two such scores produces a linear inequality; comparing one score with all the others produces a class decision region. The geometry is therefore simple to state, but two distinctions matter: a pairwise equality plane need not be an active part of the multiclass boundary, and a tie at the maximum need not be a boundary when two score functions are identical.

Assume there are \(K\) classes and an observation \(x\in\mathbb{R}^p\). Conditional on class \(k\), suppose \(X\sim N(\mu_k,\Sigma)\), where the common covariance matrix \(\Sigma\) is positive definite. Let the class prior probabilities satisfy \(\pi_k>0\) and \(\sum_{k=1}^K\pi_k=1\). Under zero-one misclassification loss, a Bayes rule assigns \(x\) to a class with the largest prior-weighted Gaussian density. Equivalently, it maximizes the following discriminant score:

This score follows by taking the log of \(\pi_k f_k(x)\) and removing terms common to every class. In particular, the quadratic term in \(x\) cancels because all classes share \(\Sigma\). The class assigned at a tie depends on the chosen tie-breaking rule; for geometric descriptions, it is useful first to retain all maximizing classes.

Pairwise Score Equality

Fix two distinct class labels \(i\) and \(j\). Subtracting their scores gives

The equality set is affine. If \(\mu_i\ne\mu_j\), positive definiteness makes \(\Sigma^{-1}\) nonsingular, so the coefficient vector \(\Sigma^{-1}(\mu_i-\mu_j)\) is nonzero. The equality set is then a genuine hyperplane in \(\mathbb{R}^p\). The sign of the same affine expression tells which side favors each class.

If the means coincide, the linear term in the score difference vanishes. The difference is then the constant \(\log(\pi_i/\pi_j)\). With unequal priors, the scores never tie; with equal priors, the score functions are identical everywhere. Thus, in these cases the equality set is respectively empty or all of \(\mathbb{R}^p\), not a hyperplane.

Decision Regions as Intersections of Half-Spaces

For each class, define its weak score-dominance region to include every observation at which that class attains the maximum score. These regions can overlap at ties. A deterministic classifier can assign tied points by a rule, but the weak regions expose the full geometry without hiding ties.

Proof. By definition, \(x\in R_i\) exactly when \(\delta_i(x)\) is at least every score \(\delta_j(x)\). This is equivalent to the finite collection of inequalities \(\delta_i(x)-\delta_j(x)\geq0\), one for each \(j\ne i\), which proves the set equality. Each difference is affine by the displayed score subtraction. Its nonnegative set is a closed half-space when its linear coefficient is nonzero, and is all or none of \(\mathbb{R}^p\) when the difference is a constant. A finite intersection of closed sets is closed. The intersection may be empty or have dimension smaller than \(p\), so neither nonemptiness nor a full-dimensional region is guaranteed. \(\square\)

This description also explains why pairwise planes alone do not determine the visible multiclass boundary. The part of the plane for classes \(i,j\) relevant to their shared maximizing region is \(\{x:\delta_i(x)=\delta_j(x)\geq\delta_m(x)\text{ for every }m\}\). Equality without the dominance condition may be hidden below a third class’s score.

Active Interfaces and Degenerate Ties

A tie at the maximum is always a point of overlap between the corresponding weak regions. When the two means are distinct, it is also a topological boundary point of each region. To see this, set \(a=\Sigma^{-1}(\mu_i-\mu_j)\), which is nonzero. At a point \(x\) where \(i\) and \(j\) tie at the maximum, consider \(x+ta\). The score difference changes by \(t\,a^\mathsf{T}a\). For arbitrarily small positive \(t\), class \(i\)'s score exceeds class \(j\)'s; for negative \(t\), class \(j\)'s score exceeds class \(i\)'s. In particular, points outside \(R_i\) and outside \(R_j\) occur arbitrarily close to \(x\), while \(x\) belongs to both closed regions. So \(x\) lies on the boundary of both.

This argument depends on the score difference being nonconstant. If \(\mu_i=\mu_j\) and \(\pi_i=\pi_j\), the score functions are identical. With only these two classes, both weak regions equal all of \(\mathbb{R}^p\); their overlap is all of \(\mathbb{R}^p\), but their topological boundaries are empty. With additional classes, their shared score may be maximal only on part of the space, and the two regions still coincide there. Such a tie does not by itself separate one region from the other.

Common Mistake

A tempting but incorrect claim is: “Whenever \(\delta_i(x)=\delta_j(x)\geq\delta_m(x)\) for all \(m\), the point \(x\) lies on a decision boundary between \(i\) and \(j\).” The condition correctly describes \(R_i\cap R_j\), but an overlap need not be a boundary. The identical-score example shows why: both regions can contain an open set—or all of the space—without being separated there.

The correction is to distinguish three statements. Pairwise equality identifies a score tie; equality at the maximum identifies overlap of the weak regions; and a genuine separating interface requires boundary behavior. For distinct means, the nonconstant score difference ensures that a maximal tie lies on the topological boundary of both regions. For identical score functions, that conclusion does not follow. Also, a pairwise plane may be inactive when another class scores higher, as in the one-dimensional example.