LDA decision boundary

Section of Statistical classifiers and discriminant analysis, part of Statistical learning

Type	Section
Taught in	Statistical classifiers and discriminant analysis
Part	Statistical learning

Assume equal costs, so the plug-in rule ties two classes where their weighted densities are equal. That tie is the decision boundary. Substitute the two normal densities, cancel every factor that does not depend on the class, take logarithms, and expand the quadratic forms. The shared inverse covariance is the assumption that makes the terms in \mathbf{x}^\top\widehat\Sigma^{-1}\mathbf{x} cancel.

The boundary between classes j and l is \widehat\pi_j\widehat f_j(\mathbf{x})=\widehat\pi_l\widehat f_l(\mathbf{x}), that is

\frac{\widehat\pi_j}{(2\pi)^{p/2}\,|\widehat\Sigma|^{1/2}} \exp\Bigl(-\tfrac12(\mathbf{x}-\widehat{\boldsymbol\mu}_j)^\top\widehat\Sigma^{-1}(\mathbf{x}-\widehat{\boldsymbol\mu}_j)\Bigr) = \frac{\widehat\pi_l}{(2\pi)^{p/2}\,|\widehat\Sigma|^{1/2}} \exp\Bigl(-\tfrac12(\mathbf{x}-\widehat{\boldsymbol\mu}_l)^\top\widehat\Sigma^{-1}(\mathbf{x}-\widehat{\boldsymbol\mu}_l)\Bigr).

The factor (2\pi)^{p/2}\,|\widehat\Sigma|^{1/2} is the same on both sides because the covariance was forced to be common, so it cancels. The logarithms turn the remaining ratio into a difference of quadratic forms. Write q_g=(\mathbf{x}-\widehat{\boldsymbol\mu}_g)^\top\widehat\Sigma^{-1}(\mathbf{x}-\widehat{\boldsymbol\mu}_g). Then

\log\frac{\widehat\pi_j}{\widehat\pi_l} =\frac12\bigl(q_j-q_l\bigr),

and the plug-in log posterior odds are \log(\widehat\pi_j\widehat f_j/\widehat\pi_l\widehat f_l)=\log(\widehat\pi_j/\widehat\pi_l)-\tfrac12(q_j-q_l). Expand each quadratic form. Symmetry of \widehat\Sigma^{-1} gives \mathbf{a}^\top\widehat\Sigma^{-1}\mathbf{b}=\mathbf{b}^\top\widehat\Sigma^{-1}\mathbf{a}, so

q_j-q_l =-2\mathbf{x}^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_j +\widehat{\boldsymbol\mu}_j^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_j +2\mathbf{x}^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_l -\widehat{\boldsymbol\mu}_l^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_l.

The two copies of \mathbf{x}^\top\widehat\Sigma^{-1}\mathbf{x} cancel. Therefore

\log\frac{\widehat\pi_j\widehat f_j(\mathbf{x})}{\widehat\pi_l\widehat f_l(\mathbf{x})} =\mathbf{x}^\top\widehat\Sigma^{-1}(\widehat{\boldsymbol\mu}_j-\widehat{\boldsymbol\mu}_l) +\log\frac{\widehat\pi_j}{\widehat\pi_l} +\frac12\bigl( \widehat{\boldsymbol\mu}_l^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_l -\widehat{\boldsymbol\mu}_j^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_j \bigr).

Had the two classes used different covariances, the quadratic terms would have carried different matrices and would have survived. That is the calculation in the next section. Define

\begin{align*} \boldsymbol\beta &=\widehat\Sigma^{-1}(\widehat{\boldsymbol\mu}_j-\widehat{\boldsymbol\mu}_l),\\ \alpha &=\log\frac{\widehat\pi_j}{\widehat\pi_l} +\frac12(\widehat{\boldsymbol\mu}_l+\widehat{\boldsymbol\mu}_j)^\top \widehat\Sigma^{-1}(\widehat{\boldsymbol\mu}_l-\widehat{\boldsymbol\mu}_j). \end{align*}

The identity (\mathbf{a}+\mathbf{b})^\top M(\mathbf{a}-\mathbf{b})=\mathbf{a}^\top M\mathbf{a}-\mathbf{b}^\top M\mathbf{b}, for symmetric M, rewrites the difference of quadratic mean terms as the second summand in \alpha. The log posterior odds are exactly \alpha+\mathbf{x}^\top\boldsymbol\beta, so the boundary is the hyperplane

\alpha+\mathbf{x}^\top\boldsymbol\beta=0.

Predicting the class with the larger weighted density is the sign rule

\eta(\mathbf{x})= \begin{cases} j, & \alpha+\mathbf{x}^\top\boldsymbol\beta\ge 0,\\ l, & \alpha+\mathbf{x}^\top\boldsymbol\beta<0. \end{cases}

What the cancellation establishes is the shape of the boundary. Under the shared-covariance assumption the log posterior odds are linear in \mathbf{x}, so the comparison of two classes is a single number, the projection \alpha+\mathbf{x}^\top\boldsymbol\beta, and the boundary in that one-dimensional projection is a point. With more than two classes there is one such score for each pair, and the predicted class is the one that wins the comparisons it enters. The regions of the partition are bounded by pieces of these hyperplanes, so the boundary is piecewise linear.

Two equivalent forms are useful. First, define the linear discriminant score

\delta_g(\mathbf{x}) =\mathbf{x}^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_g -\tfrac12\widehat{\boldsymbol\mu}_g^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_g +\log\widehat\pi_g.

The rule is \arg\max_g\delta_g(\mathbf{x}), which avoids writing every pair when G>2. The difference \delta_j-\delta_l equals \alpha+\mathbf{x}^\top\boldsymbol\beta. Second, with equal priors the rule assigns \mathbf{x} to the class whose mean is nearest in squared Mahalanobis distance (\mathbf{x}-\widehat{\boldsymbol\mu}_g)^\top\widehat\Sigma^{-1}(\mathbf{x}-\widehat{\boldsymbol\mu}_g). Unequal priors shift each boundary parallel to itself through the term \log(\widehat\pi_j/\widehat\pi_l) in \alpha.

Example 1 (A two-class LDA by hand) Question. Class 1 has observations (3,3), (1,1), (3,2), (1,2) and class 2 has (6,5), (4,3), (6,4), (4,4). Find the LDA rule with equal priors and classify the point (5,1.4).

Solution. The class means are \widehat{\boldsymbol\mu}_1=(2,2)^\top and \widehat{\boldsymbol\mu}_2=(5,4)^\top, and \widehat\pi_1=\widehat\pi_2=\tfrac12. The centred observations of class 1 are (1,1), (-1,-1), (1,0), (-1,0), and class 2 has exactly the same deviations. Each outer product contributes

\begin{pmatrix}1\\1\end{pmatrix}\begin{pmatrix}1&1\end{pmatrix} =\begin{pmatrix}1&1\\1&1\end{pmatrix}, \quad \begin{pmatrix}1\\0\end{pmatrix}\begin{pmatrix}1&0\end{pmatrix} =\begin{pmatrix}1&0\\0&0\end{pmatrix},

and the two negative deviations repeat those matrices, so each class has scatter

A_g=\begin{pmatrix}4&2\\2&2\end{pmatrix}.

The pooled covariance uses divisor n-G=8-2=6:

\widehat\Sigma =\frac{1}{6}(A_1+A_2) =\frac{1}{6}\begin{pmatrix}8&4\\4&4\end{pmatrix} =\begin{pmatrix}4/3&2/3\\2/3&2/3\end{pmatrix}.

The determinant is (4/3)(2/3)-(2/3)^2=8/9-4/9=4/9. The inverse is

\widehat\Sigma^{-1} =\frac{9}{4}\begin{pmatrix}2/3&-2/3\\-2/3&4/3\end{pmatrix} =\begin{pmatrix}1.5&-1.5\\-1.5&3\end{pmatrix}.

With j=1 and l=2,

\boldsymbol\beta =\widehat\Sigma^{-1}(\widehat{\boldsymbol\mu}_1-\widehat{\boldsymbol\mu}_2) =\widehat\Sigma^{-1}\begin{pmatrix}-3\\-2\end{pmatrix} =\begin{pmatrix}-1.5\\-1.5\end{pmatrix}.

Equal priors make the log-weight term zero. The second form of the intercept uses \widehat{\boldsymbol\mu}_2+\widehat{\boldsymbol\mu}_1=(7,6)^\top and \widehat{\boldsymbol\mu}_2-\widehat{\boldsymbol\mu}_1=(3,2)^\top:

\widehat\Sigma^{-1}\begin{pmatrix}3\\2\end{pmatrix} =\begin{pmatrix}1.5\\1.5\end{pmatrix}, \qquad \alpha=\frac12\bigl(7\cdot 1.5+6\cdot 1.5\bigr)=\frac12\cdot 19.5=9.75.

The boundary is 9.75-1.5x_1-1.5x_2=0, that is x_1+x_2=6.5, which passes through the midpoint (3.5,3) of the means. The rule predicts class 1 when x_1+x_2\le 6.5. For (5,1.4), the sum is 6.4<6.5, so the point is class 1.

The Euclidean bisector of the means is the set of \mathbf{x} with (\mathbf{x}-\mathbf{m})^\top(\widehat{\boldsymbol\mu}_2-\widehat{\boldsymbol\mu}_1)=0, where \mathbf{m}=(3.5,3)^\top is the midpoint. That is 3(x_1-3.5)+2(x_2-3)=0, or 3x_1+2x_2=16.5. At the query point, 3(5)+2(1.4)=17.8>16.5, which puts the point on the class-2 side of the Euclidean bisector. The squared Mahalanobis distances agree with LDA. For class 1, \mathbf{x}-\widehat{\boldsymbol\mu}_1=(3,-0.6)^\top and

\widehat\Sigma^{-1}\begin{pmatrix}3\\-0.6\end{pmatrix} =\begin{pmatrix}5.4\\-6.3\end{pmatrix}, \qquad 3\cdot 5.4+(-0.6)(-6.3)=16.2+3.78=19.98.

For class 2, \mathbf{x}-\widehat{\boldsymbol\mu}_2=(0,-2.6)^\top and

\widehat\Sigma^{-1}\begin{pmatrix}0\\-2.6\end{pmatrix} =\begin{pmatrix}3.9\\-7.8\end{pmatrix}, \qquad (-2.6)(-7.8)=20.28.

The nearer mean in Mahalanobis distance is \widehat{\boldsymbol\mu}_1. The covariance tilts the boundary: its normal is (1,1) rather than (3,2). The within-class scatter is largest along the leading eigenvector of \widehat\Sigma. The larger eigenvalue is 1+\sqrt{5}/3, and the matching direction satisfies v_1/v_2=(1+\sqrt{5})/2, so the axis is proportional to (1,(\sqrt{5}-1)/2)\approx(1,0.62)^\top. That direction is close to (3,2)^\top, the direction joining the means, so a displacement along the line of the means is less informative than its Euclidean length suggests.

LDA decision boundary

Used in

See also