While reading the book Elements of Statistical Learning p. 113, the author used eigendecomposition of the covariance matrix $\hat{\Sigma}_k =\mathbf{U}_k\mathbf{D}_k\mathbf{U}_k^T$ where $\mathbf{U}_k$ is $p \times p$ orthonormal, and $\mathbf{D}_k$ a diagonal matrix of positive eigenvalues $d_{kl}$

The formula for the quadratic function is as follows:

$$ \delta_k(x) = -\frac{1}{2}\log|\mathbf{\Sigma}_k|-\frac{1}{2}(x-\mu_k)^T\mathbf{\Sigma}^{-1}_k(x-\mu_k)+\log \pi_k $$

Using the idea of eigendecomposition the $\delta_k(x)$ is redefind:

1) $(x-\mu_k)^T\mathbf{\Sigma}^{-1}_k(x-\mu_k) = |\mathbf{U}_k^T(x-\mu_k)|^T\mathbf{D}_k^{-1}|\mathbf{U}_k^T(x-\mu_k)|$

2) $\log|\hat{\mathbf{\Sigma}}| = \Sigma_l\log(d_{kl})$

Apparently, the computational steps for the LDA classifier can be implemented by starting with the following step:

$Sphere$ the data with respect to the commmon covariance estimate $\hat{\Sigma}$:

$X^*\leftarrow \mathbf{D}^{-\frac{1}{2}}\mathbf{U}^TX$, where $\hat{\mathbf{\Sigma}} = \mathbf{UDU}^T$. The common covariance estimate of $X^*$ will now be the identity.

I did not understand how the author came to this step and I don't know how to read the back arrow from $\mathbf{D}^{-\frac{1}{2}}\mathbf{U}^TX$. Anybody who has an idea where I should start or how I should tackle this? What do I have to imagine when reading $X^*$?

  • $\begingroup$ What is the definition of $\mu_k$ and $\pi_k$? $\endgroup$ – Marc Bogaerts Aug 31 '14 at 21:11
  • $\begingroup$ $\mu_k$ is the mean of class k and $\pi_k$ the prior probability of class k. These are estimated as $\hat{\pi}_k = N_k/N $, where $N_k$ is the number of class-k observations; and $\hat{\mu}_k = \Sigma_{g_{i=k}}x_i/N_k$. $\endgroup$ – hendiadys Aug 31 '14 at 21:20
  • $\begingroup$ So, mathematically, these are just some unrelated numbers? $\endgroup$ – Marc Bogaerts Aug 31 '14 at 21:42
  • $\begingroup$ Yes, I guess so. $\pi_k$ is just a scalar, $\mu_k$ will be a vector of means for each variable in class k so $\mu_k = (\mu_{k1}, \mu_{k2}, ... \mu_{kp})^T$. $\endgroup$ – hendiadys Aug 31 '14 at 21:48

What you might want to begin with here is the most general form of the discriminant function that is mentioned in the text:

$$\delta_{k}(x) = log \ \mathbb{P} (G = k | X = x)$$

Under assumptions that $X | G = k \sim \mathcal{N}(\mu_{k},\,\Sigma)$ and $\mathbb{P} (G = k) = \pi_{k}$ (as introduced for linear discriminant analysis in the book) and after eliminating normalization constant from normal distribution density (because it is common for all discriminants) you obtain

$$ \delta_{k} (x) = - \frac{1}{2} (x - \mu_{k})^{T} \Sigma^{-1} (x - \mu_{k}) + log \ \pi_{k}$$ by Bayes theorem obviously. From here (after plugging in $\mu_{k}$, $\Sigma$ and $\pi_{k}$ estimates) you can either simplify again to obtain linear discriminant functions by removing common quadratic term (and arrive at

$$ \delta_{k} (x) = x^{T} \hat{\Sigma}^{-1} \hat{\mu}_{k} - \frac{1}{2} \hat{\mu}_{k}^{T} \hat{\Sigma}^{-1} \hat{\mu}_{k} + log \ \hat{\pi}_{k}$$ which is eq. (4.10) in II edition of ESL) or you can use eigenvalue decomposition of $\hat{\Sigma}$ just like the authors used it for $\hat{\Sigma}_{k}$ (which you mention in 1) in your question):

$$ \begin{align} \delta_{k} (x) &= - \frac{1}{2} (\mathbf{U}^{T} (x - \hat{\mu}_{k}))^{T} \mathbf{D}^{-1} (\mathbf{U}^{T}(x - \hat{\mu}_{k})) + log \ \hat{\pi}_{k} \\ &= - \frac{1}{2} (\mathbf{U}^{T} (x - \hat{\mu}_{k}))^{T} \mathbf{D}^{- \frac{1}{2}} \mathbf{D}^{- \frac{1}{2}} (\mathbf{U}^{T}(x - \hat{\mu}_{k})) + log \ \hat{\pi}_{k} \\ &= - \frac{1}{2} (\mathbf{D}^{- \frac{1}{2}} \mathbf{U}^{T} (x - \hat{\mu}_{k}))^{T} (\mathbf{D}^{- \frac{1}{2}} \mathbf{U}^{T}(x - \hat{\mu}_{k})) + log \ \hat{\pi}_{k} \\ &= - \frac{1}{2} \left \Vert \mathbf{D}^{- \frac{1}{2}} \mathbf{U}^{T} (x - \hat{\mu}_{k}) \right \Vert^{2}_{2} + log \ \hat{\pi}_{k}, \end{align} $$ where obviously $\hat{\Sigma} = \mathbf{U D U}^{T}$ is the eigendecomposition.

So we have an alternative form of the discriminant function. Now to my understanding that back arrow in $X^{\ast} \leftarrow \mathbf{D}^{- \frac{1}{2}} \mathbf{U}^{T} X$ means that the first step of this LDA implementation is to apply the sphering transform (linear map defined by $\mathbf{D}^{- \frac{1}{2}} \mathbf{U}^{T}$ matrix) to each observation (both in training set and to inputs at prediction time). That means we transform each row of the $N \times p$ data matrix $\mathbf{X}$ (matrix rows of which are training observations), so we obtain $\mathbf{X}^{\ast} = \mathbf{X} \mathbf{U} \mathbf{D}^{- \frac{1}{2}}$. Class labels of the observations do not change, so you can again consider class centroids - and it can be easily seen that the centroids in the transformed data are of form $\mathbf{D}^{- \frac{1}{2}} \mathbf{U}^{T} \hat{\mu}_{k}$.

And not only that, it's rather trivial to derive covariance matrix of the transformed data $\mathbf{X}^{\ast}$ and see that it's indeed identity matrix. Hence the name: sphering or whitening the data, because separate features are now uncorrelated and have unit variance. If the term is unfamiliar to you, you might want to start at https://en.wikipedia.org/wiki/Whitening_transformation, if you haven't already.

Having said all that we can go back to our alternative form of discriminant above and see that the first term is indeed square distance between $k$ class centroid in the transformed data and transformed input observation $x$. Hence maximizing the discriminant amounts to classifying

to the closest class centroid in the transformed space, modulo the effect of the class prior probabilities $\pi_{k}$.

to quote the book.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.