2
$\begingroup$

From what I understand, linear discriminant analysis (LDA) has an objective function, where you try to find a matrix that maps data from a $p$-dimensional feature space to a $r$-dimensional feature space with $r<p$.

Per my understanding, an objective function implies that there is learning being done. I define learning as a process by which an optimized solution is found, over several iterations, as in neural machine learners such as backpropagation, etc.

I'm having a hard time understanding if/how LDA "learns". You calculate the between, within and total scatter - fine. But what do you do with them? How do you find that matrix, $G$, that maps your data to a lower dimensional feature space?

I've been looking at an implementation of LDA here, and I do not understand how "pooled covariance" and "W" relates to any of the definitions from the mathematics described in the image below (from a paper by Wang, Ding & Huang, 2010). Can anyone help me? How do I find $G$ in formula (5)? Where is the optimization occurring in the code implementation attached?

enter image description here

Update: This was very helpful to me.

Improve this question
$\endgroup$
5
  • $\begingroup$ This does not really answer your question, but the LDA code that you linked to seems to be badly wrong. It does perhaps work correctly for 2 balanced classes, but it is definitely not the correct implementation of multiclass LDA. $\endgroup$ – amoeba Oct 22 '15 at 9:34
  • $\begingroup$ That is helpful! I'm trying to find any pseudocode online and I can't really find it. I'm definitely interested in multiclass LDA. I'm trying to understand single-label multi-class LDA so I can write the multi-label multi-class version, but I don't understand the original algorithm, currently. $\endgroup$ – areyoujokingme Oct 22 '15 at 17:13
  • $\begingroup$ I must admit that I don't really understand your question. Are you simply asking how to compute $G$ that maximized the trace from equation (5)? The answer is that it is given by leading eigenvectors of $S_w^{-1}S_b$. I suppose this is the written on the next page of the paper you are reading. Or are you asking about something else? $\endgroup$ – amoeba Oct 22 '15 at 18:09
  • 1
    $\begingroup$ I was trying to understand how LDA learns. K-nearest neighbor, for example, is a machine learning method, but no learning occurs. Thus, it is called a "lazy learner". It uses "context clues" given by the "neighborhood" in input space, to predict the class of a test observation. I didn't understand how G was calculated, but after your direction, the links given below and the link I just added to my update, I have come to the understanding that G is solved via the generalized eigenvalue problem. $\endgroup$ – areyoujokingme Oct 22 '15 at 18:54
  • $\begingroup$ That is right! I am glad that the issue is resolved. $\endgroup$ – amoeba Oct 22 '15 at 19:08
1
$\begingroup$

The paper you're reading is describing Fisher's linear discriminant and the MATLAB code is actually implementing LDA that assumes a multivariate normal distribution.

Take a look at this link for a more thorough description but mainly the part that is confusing you ($\vec{G}$) is calculated here:

Temp = GroupMean(i,:) / PooledCov;

% Constant
W(i,1) = -0.5 * Temp * GroupMean(i,:)' + log(PriorProb(i));

and corresponds to the fairly standard maximum likelihood estimation of the multivariate normal (page 7 in the slides).

Just to be clear. Fisher's linear discriminant and LDA are equivalent (assuming LDA's assumptions are satisfied) in that both will give you the same projection.

UPDATE: Actually, Wikipedia offers an overview of both approaches.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your response! Those slides helped me I think. For the arg max k of the W(i,1) (which is G) line... we are getting the points where the multivariate normal is at its maximum. How many points should we expect to get - the number of classes (k)? W / G are the "coefficients" of the solution. How should we interpret these coefficients? Are these similar to the coefficients from, say, a general linear model (GLM)? $\endgroup$ – areyoujokingme Oct 22 '15 at 17:57
  • $\begingroup$ $\vec{W}$ are the coefficients for your input value $\vec{x}$ (including a constant working as a bias parameter.) In most implementations, you're going to get the coefficients for every class in a single matrix/array. The coefficients are describing a plane (or hyperplane) such that projection of your data onto that plane separates the classes more effectively while keeping inter-class variance as low as possible. The coefficients are similar w.r.t GLM but here you have appropriate constraints for a classification task. $\endgroup$ – Robert Smith Oct 22 '15 at 20:15

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.