Ex. 4.2

Ex. 4.2

Suppose we have features $x\in {\mathbb{R}}^p$, a two-class response, with class sizes $N_1$, $N_2$, and the target coded as $-N/N_1$, $N/N_2$.

(a)

Show that the LDA rule classifies to class 2 if

$$\begin{array}{}\text{(1)}& x^T{\hat{\mathrm{\Sigma }}}^{-1}({\hat{\mu }}_2-{\hat{\mu }}_1)>\frac{1}{2}({\hat{\mu }}_2+{\hat{\mu }}_1{)}^T{\hat{\mathrm{\Sigma }}}^{-1}({\hat{\mu }}_2-{\hat{\mu }}_1)-\log (N_2/N_1),\end{array}$$

and class 1 otherwise.

(b)

Consider minimization of the least squares criterion

$$\sum _{i=1}^N(y_i-{\beta }_0-x_i^T\beta {)}^2.$$

Show that the solution $\hat{\beta }$ satisfies

$$[(N-2)\hat{\mathrm{\Sigma }}+N{\hat{\mathrm{\Sigma }}}_B]\beta =N({\hat{\mu }}_2-{\hat{\mu }}_1)$$

(after simplification), where ${\hat{\mathrm{\Sigma }}}_B=\frac{N_1{N}_2}{N}({\hat{\mu }}_2-{\hat{\mu }}_1)({\hat{\mu }}_2-{\hat{\mu }}_1{)}^T$.

(c)

Hence show that ${\hat{\mathrm{\Sigma }}}_B\beta$ is in the direction $({\hat{\mu }}_2-{\hat{\mu }}_1)$ and thus

$$\hat{\beta }\propto {\hat{\mathrm{\Sigma }}}^{-1}({\hat{\mu }}_2-{\hat{\mu }}_1).$$

Therefore the least-squares regression coefficient is identical to the LDA coefficient, up to a scalar mupliple.

(d)

Show that this result holds for any (distinct) coding of the two classes.

(e)

Find the solution ${\hat{\beta }}_0$ (up to the same scalar multiple as in (c)), and hence the predicted value $\hat{f}(x)={\hat{\beta }}_0+x^T\hat{\beta }$. Consider the following rule: classify to class 2 if $\hat{f}(x)>0$ and class 1 otherwise. Show this is not the same as the LDA rule unless the classes have equal numbers of observations.

(The use of multiple measurements in taxonomic problems, Pattern Recognition and Neural Networks)

Soln. 4.2

(a)

We have ${\pi }_1=N_1/N$ and ${\pi }_2=N_2/N$. The conclusion follows directly by (4.9) in the textbook.

(b)

We start by introducing notations used in Chapter 3.

Let $x_i^T=(x_{i1},...,x_{ip})\in {\mathbb{R}}^{1\times p}$, ${\mathbf{\text{1}}}^T=(1,...,1)\in {\mathbb{R}}^{1\times p}$, $Y^T=(y_1,...,y_N)\in {\mathbb{R}}^{1\times N}$, ${\beta }^T=({\beta }_1,...,{\beta }_p)\in {\mathbb{R}}^{1\times p}$.

$$\mathbf{\text{X}}=\left(\begin{array}{cccc}1& x_{11}& \cdots & x_{1p}\\ 1& x_{21}& \cdots & x_{2p}\\ ⋮& ⋮& \ddots & ⋮\\ 1& x_{N1}& \cdots & x_{Np}\end{array}\right)=\left(\begin{array}{cc}1& x_1^T\\ 1& x_2^T\\ ⋮& ⋮\\ 1& x_N^T\end{array}\right)\in {\mathbb{R}}^{N\times (p+1)}$$

and

$${\mathbf{\text{X}}}^T=\left(\begin{array}{cccc}1& 1& \cdots & 1\\ x_{11}& x_{21}& \cdots & x_{N1}\\ ⋮& ⋮& \ddots & ⋮\\ x_{1p}& x_{2p}& \cdots & x_{Np}\end{array}\right)=\left(\begin{array}{cccc}1& 1& \cdots & 1\\ x_1& x_2& \cdots & x_N\end{array}\right)\in {\mathbb{R}}^{(p+1)\times N}.$$

So that we have

$${\mathbf{\text{X}}}^T\mathbf{\text{X}}=\left(\begin{array}{cc}N& \sum _{i=1}^N{x}_i^T\\ \sum _{i=1}^N{x}_i& \sum _{i=1}^N{x}_i{x}_i^T\end{array}\right)\in {\mathbb{R}}^{(p+1)\times (p+1)}.$$

From knowledge in linear regression, e.g., (3.6) in the textbook, we have

$${\mathbf{\text{X}}}^T\mathbf{\text{X}}\left(\begin{array}{c}{\beta }_0\\ \beta \end{array}\right)=\left(\begin{array}{cc}N& \sum _{i=1}^N{x}_i^T\\ \sum _{i=1}^N{x}_i& \sum _{i=1}^N{x}_i{x}_i^T\end{array}\right)\left(\begin{array}{c}{\beta }_0\\ \beta \end{array}\right)={\mathbf{\text{X}}}^{T}Y=\left(\begin{array}{c}\sum _{i=1}^N{y}_i\\ \sum _{i=1}^N{y}_i{x}_i\end{array}\right)\in {\mathbb{R}}^{(p+1)\times 1}.$$

Therefore we have

$$\begin{array}{rcl}N{\beta }_0+\left(\sum _{i=1}^N{x}_i^T\right)\beta & =& \sum _{i=1}^N{y}_i\\ \text{(2)}& {\beta }_0\sum _{i=1}^N{x}_i+\left(\sum _{i=1}^N{x}_i{x}_i^T\right)\beta & =& \sum _{i=1}^N{y}_i{x}_i.\end{array}$$

From the first equation above, we get

$$\begin{array}{}\text{(3)}& {\beta }_0=\frac{1}{N}(\sum _{i=1}^N{y}_i-\left(\sum _{i=1}^N{x}_i^T\right)\beta ),\end{array}$$

plug above into $\text{(2)}$ and solve for $\beta$ we obtain

$$\begin{array}{}\text{(4)}& [\sum _{i=1}^N{x}_i{x}_i^T-\frac{1}{N}\left(\sum _{i=1}^N{x}_i\right)\left(\sum _{i=1}^N{x}_i^T\right)]\beta =\sum _{i=1}^N{y}_i{x}_i-\frac{1}{N}\left(\sum _{i=1}^N{y}_i\right)\left(\sum _{i=1}^N{x}_i\right).\end{array}$$

We pause here and turn to ${\hat{\mu }}_1,{\hat{\mu }}_2$ and $\mathrm{\Sigma }$. Let's we encode $y_i$ for class 1 as $t_1$ and $y_i$ for class 2 as $t_2$. Note that for this particular problem (b), $t_1=-N/N_1$ and $t_2=N/N_2$. By definition, we have

$$\begin{array}{rcl}{\hat{\mu }}_1=\frac{1}{N_1}\sum _{i:g_i=1}{x}_i,& & {\hat{\mu }}_2=\frac{1}{N_2}\sum _{i:g_i=2}{x}_i\\ \sum _{i=1}^N{x}_i=N_1{\hat{\mu }}_1+N_2{\hat{\mu }}_2,& & \sum _{i=1}^N{x}_i^T=N_1{\hat{\mu }}_1^T+N_2{\hat{\mu }}_2^T\\ \sum _{i=1}^N{y}_i=N_1{t}_1+N_2{t}_2,& & \sum _{i=1}^N{y}_i{x}_i=t_1{N}_1{\hat{\mu }}_1+t_2{N}_2{\hat{\mu }}_2\end{array}$$

and

$$\hat{\mathrm{\Sigma }}=\frac{1}{N-2}(\sum _{i:g_i=1}(x_i-{\hat{\mu }}_1)(x_i-{\hat{\mu }}_1{)}^T+\sum _{i:g_i=2}(x_i-{\hat{\mu }}_2)(x_i-{\hat{\mu }}_2{)}^T).$$

From equations above we can rewrite

$$\sum _{i=1}^N{x}_i{x}_i^T=(N-2)\hat{\mathrm{\Sigma }}+N_1{\hat{\mu }}_1{\hat{\mu }}_1^T+N_2{\hat{\mu }}_2{\hat{\mu }}_2^T.$$

Now we turn back to $\text{(4)}$. For the LHS,

$$\begin{array}{rcl}& & \sum _{i=1}^N{x}_i{x}_i^T-\frac{1}{N}\left(\sum _{i=1}^N{x}_i\right)\left(\sum _{i=1}^N{x}_i^T\right)\\ & =& \sum _{i=1}^N{x}_i{x}_i^T-\frac{1}{N}(N_1{\hat{\mu }}_1+N_2{\hat{\mu }}_2)(N_1{\hat{\mu }}_1^T+N_2{\hat{\mu }}_2^T)\\ & =& (N-2)\hat{\mathrm{\Sigma }}+N_1{\hat{\mu }}_1{\hat{\mu }}_1^T+N_2{\hat{\mu }}_2{\hat{\mu }}_2^T-\frac{1}{N}(N_1{\hat{\mu }}_1+N_2{\hat{\mu }}_2)(N_1{\hat{\mu }}_1^T+N_2{\hat{\mu }}_2^T)\\ & =& (N-2)\hat{\mathrm{\Sigma }}+\frac{N_1{N}_2}{N}({\hat{\mu }}_2-{\hat{\mu }}_1)({\hat{\mu }}_2-{\hat{\mu }}_1{)}^T\\ \text{(5)}& & =& (N-2)\hat{\mathrm{\Sigma }}+N{\hat{\mathrm{\Sigma }}}_B,\end{array}$$

where ${\hat{\mathrm{\Sigma }}}_B=\frac{N_1{N}_2}{N^2}({\hat{\mu }}_2-{\hat{\mu }}_1)({\hat{\mu }}_2-{\hat{\mu }}_1{)}^T$.

For the RHS of $\text{(4)}$,

$$\begin{array}{rcl}& & \sum _{i=1}^N{y}_i{x}_i-\frac{1}{N}\left(\sum _{i=1}^N{y}_i\right)\left(\sum _{i=1}^N{x}_i\right)\\ & =& t_1{N}_1{\hat{\mu }}_1+t_2{N}_2{\hat{\mu }}_2-\frac{1}{N}(N_1{t}_1+N_2{t}_2)(N_1{\hat{\mu }}_1+N_2{\hat{\mu }}_2)\\ \text{(6)}& & =& \frac{N_1{N}_2}{N}(t_2-t_1)({\hat{\mu }}_2-{\hat{\mu }}_1).\end{array}$$

Combining $\text{(4)}$, $\text{(5)}$ and $\text{(6)}$ we get

$$\begin{array}{}\text{(7)}& [(N-2)\hat{\mathrm{\Sigma }}+N{\hat{\mathrm{\Sigma }}}_B]\beta =\frac{N_1{N}_2}{N}(t_2-t_1)({\hat{\mu }}_2-{\hat{\mu }}_1).\end{array}$$

Note that $t_1=-N/N_1$, $t_2=N/N_2$ and $N=N_1+N_2$, so that $t_2-t_1=\frac{N^2}{N_1{N}_2}$.

Thus, $\text{(6)}$ reduces to $N({\hat{\mu }}_2-{\hat{\mu }}_1)$ and we finish the proof.

(c)

We have

$${\hat{\mathrm{\Sigma }}}_B\beta =\frac{N_1{N}_2}{N^2}({\hat{\mu }}_2-{\hat{\mu }}_1)({\hat{\mu }}_2-{\hat{\mu }}_1{)}^T\beta$$

where $({\hat{\mu }}_2-{\hat{\mu }}_1{)}^T\beta \in \mathbb{R}$ is a scalar, thus ${\hat{\mathrm{\Sigma }}}_B\beta$ is in the direction $({\hat{\mu }}_2-{\hat{\mu }}_1)$. By part (b) we have

$$\hat{\beta }\propto {\hat{\mathrm{\Sigma }}}^{-1}({\hat{\mu }}_2-{\hat{\mu }}_1).$$

(d)

This follows directly from $\text{(7)}$ for $t_1\ne t_2$.

(e)

Assuming the encoding of $-N/N_1$ and $N/N_2$, by $\text{(3)}$ we have

$$\begin{array}{rcl}{\hat{\beta }}_0& =& \frac{1}{N}(\sum _{i=1}^N{y}_i-\left(\sum _{i=1}^N{x}_i^T\right)\beta )\\ & =& -\frac{1}{N}\left(\sum _{i=1}^N{x}_i^T\right)\hat{\beta }\\ \text{(8)}& & =& -\frac{1}{N}(N_1{\hat{\mu }}_1^T+N_2{\hat{\mu }}_2^T)\hat{\beta }\end{array}$$

so that

$$\hat{f}(x)={\hat{\beta }}_0+x^T\hat{\beta }=[x^T-\frac{1}{N}(N_1{\hat{\mu }}_1^T+N_2{\hat{\mu }}_2^T)]\hat{\beta }.$$

Since $\hat{\beta }\propto {\hat{\mathrm{\Sigma }}}^{-1}({\hat{\mu }}_2-{\hat{\mu }}_1)$, there exists $\lambda >0$ (up to a scalar constant, i.e., we can flip the classification sign if $\lambda <0$) such that $\hat{\beta }=\lambda {\hat{\mathrm{\Sigma }}}^{-1}({\hat{\mu }}_2-{\hat{\mu }}_1)$. Therefore, $\hat{f}(x)>0$ is equivalent to

$$[x^T-\frac{1}{N}(N_1{\hat{\mu }}_1^T+N_2{\hat{\mu }}_2^T)]{\hat{\mathrm{\Sigma }}}^{-1}({\hat{\mu }}_2-{\hat{\mu }}_1)>0,$$

which is equivalent to LDA rule $\text{(1)}$ when $N_1=N_2$. When $N_1\ne N_2$, $\log (N_2/N_1)\ne 0$ in $\text{(1)}$ so they are not equivalent.