NationMaster - Encyclopedia: Linear discriminant analysis

Linear discriminant analysis (LDA) and the related Fisher's linear discriminant are methods used in statistics and machine learning to find the linear combination of features which best separate two or more classes of object or event. The resulting combination may be used as a linear classifier, or, more commonly, for dimensionality reduction before later classification. A graph of a normal bell curve showing statistics used in educational assessment and comparing various grading methods. ... As a broad subfield of artificial intelligence, machine learning is concerned with the design and development of algorithms and techniques that allow computers to learn. At a general level, there are two types of learning: inductive, and deductive. ... In mathematics, linear combinations are a concept central to linear algebra and related fields of mathematics. ... In pattern recognition, features are the individual measurable heuristic properties of the phenomena being observed. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ... In statistics, dimensionality reduction is mapping a multidimensional space into a space of fewer dimensions. ... Statistical classification is a type of supervised learning problem in which labeled training data is used to create a function that will correctly predict the label of future data. ...

LDA is closely related to ANOVA (analysis of variance) and regression analysis, which also attempt to express one dependent variable as a linear combination of other features or measurements. In the other two methods however, the dependent variable is a numerical quantity, while for LDA it is a categorical variable (i.e. the class label). In statistics, analysis of variance (ANOVA) is a collection of statistical models and their associated procedures which compare means by splitting the overall observed variance into different parts. ... In statistics, regression analysis examines the relation of a dependent variable (response variable) to specified independent variables (explanatory variables). ... In experimental design, a dependent variable (also known as response variable, responding variable or regressand) is a factor whose values in different treatment conditions are compared. ... The categorical imperative is the philosophical concept central to the moral philosophy of Immanuel Kant and to modern deontological ethics. ...

LDA is also closely related to principal component analysis (PCA) and factor analysis in that both look for linear combinations of variables which best explain the data. LDA explicitly attempts to model the difference between the classes of data. PCA on the other hand does not take into account any difference in class, and factor analysis builds the feature combinations based on differences rather than similarities. Discriminant analysis is also different from factor analysis in that it is not an interdependence technique : a distinction between independent variables and dependent variables (also called criterion variables) must be made. In statistics, principal components analysis (PCA) is a technique that can be used to simplify a dataset; more formally it is a linear transformation that chooses a new coordinate system for the data set such that the greatest variance by any projection of the data set comes to lie on... Factor analysis is a statistical data reduction technique used to explain variability among observed random variables in terms of fewer unobserved random variables called factors. ...

LDA works when the measurements made on each observation are continuous quantities. When dealing with categorical variables, the equivalent technique is Discriminant Correspondence Analysis (see References).

1 LDA for two classes
2 Fisher's linear discriminant
3 Multiclass LDA
4 Practical use
5 Applications
- 5.1 Face recognition
- 5.2 Marketing
  - 5.2.1 See also
6 See also
7 References
8 External links

LDA for two classes

Consider a set of observations x (also called features, attributes, variables or measurements) for each sample of an object or event with known class y. This set of samples is called the training set. The classification problem is then to find a good predictor for the class y of any sample of the same distribution (not necessarily from the training set) given only an observation x. A training set is used in artificial intelligence, together with a supervised training method, and it consists of an input vector and an answer vector. ...

LDA approaches the problem by assuming that the probability density functions $p(vec x|y=1)$ and $p(vec x|y=0)$ are both normally distributed. Under this assumption, the Bayes optimal solution is to predict points as being from the second class if the likelihood ratio is below some threshold T, so that In mathematics, a probability density function (pdf) is a function that represents a probability distribution in terms of integrals. ... The normal distribution, also called the Gaussian distribution, is an important family of continuous probability distributions, applicable in many fields. ...

$(vec x- vec mu_0)^T Sigma_{y=0}^{-1} ( vec x- vec mu_0) + mathrm{ln}|Sigma_{y=0}| - (vec x- vec mu_1)^T Sigma_{y=1}^{-1} ( vec x- vec mu_1) - mathrm{ln}|Sigma_{y=1}| < T$

Without any further assumptions, the resulting classifier is referred to as QDA (quadratic discriminant analysis). LDA also makes the simplifying homoscedastic assumption (i.e. that the class covariances are identical, so $Σ y = 0 = Σ y = 1 = Σ$ ) and that the covariances have full rank. In this case, several terms cancel and the above decision criterion becomes a threshold on the dot product A quadratic classifier is used in machine learning to separate measurements of two or more classes of objects or events by a quadric surface. ... In statistics, a sequence or a vector of random variables is homoscedastic if all random variables in the sequence or vector have the same finite variance. ... In probability theory and statistics, the covariance between two real-valued random variables X and Y, with expected values and is defined as: where E is the expected value. ... In mathematics, the dot product, also known as the scalar product, is a binary operation which takes two vectors over the real numbers R and returns a real-valued scalar quantity. ...

$vec w cdot vec x < c$

for some constant c, where

$vec w = Sigma^{-1} (vec mu_1 - vec mu_0)$

This means that the probability of an input x being in a class y is purely a function of this linear combination of the known observations.

Fisher's linear discriminant

The terms Fisher's linear discriminant and LDA are often used interchangeably, although Fisher's original article The Use of Multiple Measures in Taxonomic Problems (1936) actually describes a slightly different discriminant, which does not make some of the assumptions of LDA such as normally distributed classes or equal class covariances. Sir Ronald Fisher Sir Ronald Aylmer Fisher, FRS (February 17, 1890–July 29, 1962) was an extraordinarily talented evolutionary biologist, geneticist and statistician. ... 1936 (MCMXXXVI) was a leap year starting on Wednesday (link will take you to calendar). ...

Suppose two classes of observations have means $vec mu_{y=0}, vec mu_{y=1}$ and covariances $Σ y = 0,Σ y = 1$ . Then the linear combination of features $vec w cdot vec x$ will have means $vec w . vec mu_{y=i}$ and variances $vec w^T Sigma_{y=i} vec w$ for $i = 0,1$ . Fisher defined the separation between these two distributions to be the ratio of the variance between the classes to the variance within the classes:

$S=frac{sigma_{between}^2}{sigma_{within}^2}= frac{(vec w cdot vec mu_{y=1} - vec w cdot vec mu_{y=0})^2}{vec w^T Sigma_{y=1} vec w + vec w^T Sigma_{y=0} vec w} = frac{(vec w cdot (vec mu_{y=1} - vec mu_{y=0}))^2}{vec w^T (Sigma_{y=0}+Sigma_{y=1}) vec w}$

This measure is, in some sense, a measure of the signal-to-noise ratio for the class labelling. It can be shown that the maximum separation occurs when Signal-to-noise ratio (often abbreviated SNR or S/N) is an electrical engineering concept defined as the ratio of a signal power to the noise power corrupting the signal. ...

$vec w = (Sigma_{y=0}+Sigma_{y=1})^{-1}(vec mu_{y=1} - vec mu_{y=0})$

When the assumptions of LDA are satisfied, the above equation is equivalent to LDA.

Multiclass LDA

In the case where there are more than two classes, the analysis used in the derivation of the Fisher discriminant can be extended to find a subspace which appears to contain all of the class variability. Suppose that each of C classes has a mean $μ i$ and the same covariance $Σ$ . Then the between class variability may be defined by the sample covariance of the class means Screenshot (from SSCX Star Warzone). ...

$Sigma_b = frac{1}{C} sum_{i=1}^C (mu_i-mu) (mu_i-mu)^T$

where $μ$ is the mean of the class means. The class separation in a direction $vec w$ in this case will be given by

This means that when $vec w$ is an eigenvector of $Σ b Σ - 1$ the separation will be equal to the corresponding eigenvalue. Since $Σ b$ is of most rank C-1, then these non-zero eigenvectors identify a vector subspace containing the variability between features. These vectors are primarily used in feature reduction, as in PCA. The smaller eigenvectors will tend to be very sensitive to the exact choice of training data, and it is often necessary to use regularisation as described in the next section.

Other generalizations of LDA for multiple classes have been defined to address the more general problem of heteroscedastic distributions (i.e., where the data distributions are not homoscedastic). One such method is Heteroscedastic LDA (see e.g. HLDA among others). In statistics, a sequence or a vector of random variables is heteroskedastic if the random variables in the sequence or vector may have different variances. ... In statistics, a sequence or a vector of random variables is homoscedastic if all random variables in the sequence or vector have the same finite variance. ...

If classification is required, instead of dimension reduction, there are a number of alternative techniques available. For instance, the classes may be partitioned, and a standard Fisher discriminant or LDA used to classify each partition. A common example of this is "one against the rest" where the points from one class are put in one group, and everything else in the other, and then LDA applied. This will result in C classifiers, whose results are combined. Another common method is pairwise classification, where a new classifier is created for each pair of classes (giving C(C-1) classifiers in total), with the individual classifiers combined to produce a final classification.

Practical use

In practice, the class means and covariances are not known. They can, however, be estimated from the training set. Either the maximum likelihood estimate or the maximum a posteriori estimate may be used in place of the exact value in the above equations. Although the estimates of the covariance may be considered optimal in some sense, this does not mean that the resulting discriminant obtained by substituting these values is optimal in any sense, even if the assumption of normally distributed classes is correct. In statistics, the method of maximum likelihood, pioneered by geneticist and statistician Sir Ronald A. Fisher, is a method of point estimation, that uses as an estimate of an unobservable population parameter the member of the parameter space that maximizes the likelihood function. ... In statistics, the method of maximum a posteriori (MAP, or posterior mode) estimation can be used to obtain a point estimate of an unobserved quantity on the basis of empirical data. ...

Another complication in applying LDA and Fisher's discriminant to real data occurs when the number of observations of each sample exceeds the number of samples. In this case, the covariance estimates do not have full rank, and so cannot be inverted. There are a number of ways to deal with this. One is to use a pseudo inverse instead of the usual matrix inverse in the above formulae. Another, called regularised discriminant analysis, is to artificially increase the number of available samples by adding white noise to the existing samples. These new samples do not actually have to be calculated, since their effect on the class covariances can be expressed mathematically as In mathematics, and in particular linear algebra, the pseudoinverse of a matrix is a generalization of the inverse matrix [IG2003]. More precisely, this article talks about the Moore-Penrose pseudoinverse which was apparently independently described by Moore [Moore1920] and Penrose [Penrose1955]. A common use of the pseudoinverse is as an...

$C_{new} = C+sigma^2 I,$

where $I$ is the identity matrix, and $σ$ is the amount of noise added, called in this context the regularisation parameter. The value of $σ$ is usually chosen to give the best results on a cross-validation set. The new value of the covariance matrix is always invertible, and can be used in place of the original sample covariance in the above formulae. In statistics cross-validation is the practice of partitioning a sample of data into subsamples such that analysis is initially performed on a single subsample, while further subsamples are retained blind in order for subsequent use in confirming and validating the initial analysis. ...

Also, in many practical cases linear discriminants are not suitable. LDA and Fisher's discriminant can be extended for use in non-linear classification via the kernel trick. Here, the original observations are effectively mapped into a higher dimensional non-linear space. Linear classification in this non-linear space is then equivalent to non-linear classification in the original space. The most commonly used example of this is the kernel Fisher discriminant. In machine learning, the kernel trick is a method for converting a linear classifier algorithm into a non-linear one by using a non-linear function to map the original observations into a higher-dimensional space; this makes a linear classification in the new space equivalent to non-linear classification...

LDA can be generalized to multiple discriminant analysis, where c becomes a categorical variable with N possible states, instead of only two. Analogously, if the class-conditional densities $p(vec x|c=i)$ are normal with shared covariances, the sufficient statistic for $P(c|vec x)$ are the values of N projections, which are the subspace spanned by the N means, affine projected by the inverse covariance matrix. These projections can be found by solving a generalized eigenvalue problem, where the numerator is the covariance matrix formed by treating the means as the samples, and the denominator is the shared covariance matrix. The level of measurement of a variable in mathematics and statistics describes how much information the numbers associated with the variable contain. ... In statistics, one often considers a family of probability distributions for a random variable X (and X is often a vector whose components are scalar-valued random variables, frequently independent) parameterized by a scalar- or vector-valued parameter, which let us call θ. A quantity T(X) that depends on... Screenshot (from SSCX Star Warzone). ... In geometry, an affine transformation or affine map (from the Latin, affinis, connected with) between two vector spaces (strictly speaking, two affine spaces) consists of a linear transformation followed by a translation: In the finite-dimensional case each affine transformation is given by a matrix A and a vector b... Fig. ...

Applications

Face recognition

In computerised face recognition, each face is represented by a large number of pixel values. Linear discriminant analysis is primarily used here to reduce the number of features to a more manageable number before classification. Each of the new dimensions is a linear combination of pixel values, which form a template. The linear combinations obtained using Fisher's linear discriminant are called Fisher faces, while those obtained using the related principal component analysis are called eigenfaces. A facial recognition system is a computer-driven application for automatically identifying a person from a digital image. ... In statistics, principal components analysis (PCA) is a technique that can be used to simplify a dataset; more formally it is a linear transformation that chooses a new coordinate system for the data set such that the greatest variance by any projection of the data set comes to lie on... Eigenfaces are a set of eigenvectors used in the computer vision problem of human face recognition. ...

Marketing

In marketing, discriminant analysis is often used to determine the factors which distinguish different types of customers and/or products on the basis of surveys or other forms of collected data. The use of discriminant analysis in marketing is usually described by the following steps: Wikibooks has more about this subject: Marketing Look up marketing in Wiktionary, the free dictionary. ...

Formulate the problem and gather data - Identify the salient attributes consumers use to evaluate products in this category - Use quantitative marketing research techniques (such as surveys) to collect data from a sample of potential customers concerning their ratings of all the product attributes. The data collection stage is usually done by marketing research professionals. Survey questions ask the respondent to rate a product from one to five (or 1 to 7, or 1 to 10) on a range of attributes chosen by the researcher. Anywhere from five to twenty attributes are chosen. They could include things like: ease of use, weight, accuracy, durability, colourfulness, price, or size. The attributes chosen will vary depending on the product being studied. The same question is asked about all the products in the study. The data for multiple products is codified and input into a statistical program such as SPSS or SAS. (This step is the same as in Factor analysis).
Estimate the Discriminant Function Coefficients and determine the statistical significance and validity - Choose the appropriate discriminant analysis method. The direct method involves estimating the discriminant function so that all the predictors are assessed simultaneously. The stepwise method enters the predictors sequentially. The two-group method should be used when the dependent variable has two categories or states. The multiple discriminant method is used when the dependent variable has three or more categorical states. Use Wilks’s Lambda to test for significance in SPSS or F stat in SAS. The most common method used to test validity is to split the sample into an estimation or analysis sample, and a validation or holdout sample. The estimation sample is used in constructing the discriminant function. The validation sample is used to construct a classification matrix which contains the number of correctly classified and incorrectly classified cases. The percentage of correctly classified cases is called the hit ratio.
Plot the results on a two dimensional map, define the dimensions, and interpret the results. The statistical program (or a related module) will map the results. The map will plot each product (usually in two dimensional space). The distance of products to each other indicate either how different they are. The dimensions must be labelled by the researcher. This requires subjective judgement and is often very challenging. See perceptual mapping.

Because too much data can cause â€œcognitive clutterâ€, individuals need a system to enable them to rank available data in terms of its immediate importance. ... Quantitative marketing research is a social research method that utilizes statistical techniques. ... Statistical surveys are used to collect quantitative information about items in a population. ... The computer program SPSS (originally, Statistical Package for the Social Sciences) was released in its first version in 1968, and is among the most widely used programs for statistical analysis in social science. ... Overview The SAS System is an integrated system of software products (provided by the SAS Institute) that enables the programmer to perform: data entry, retrieval, and management report writing and graphics statistical and mathematical analysis business planning, forecasting, and decision support operations research and project management quality improvement applications development. ... Perceptual mapping is a graphics technique used by marketers that attempts to visually display the perceptions of customers or potential customers. ...

References

Fisher, R.A. The Use of Multiple Measurements in Taxonomic Problems. Annals of Eugenics, 7: 179-188 (1936) pdf file
Discriminant Analysis and Statistical Pattern Recognition. G.J. McLachlan. Wiley-Interscience; New Ed edition (August 4, 2004).
Pattern Classification (2nd ed.), R.O. Duda, P.E. Hart, D.H. Stork, Wiley Interscience, (2000). ISBN 0-471-05669-3
Friedman, J.H. Regularized Discriminant Analysis. Journal of the American Statistical Association, (1989)pdf file
Martinez, A.M., Kak, A.C. PCA versus LDA. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 23, No. 2, pp. 228-233, 2001. pdf file
Mika, S. et al. Fisher Discriminant Analysis with Kernels. IEEE Conference on Neural Networks for Signal Processing IX, (1999) gzipped ps file
Nagendra Kumar Goel, Investigation of Silicon Auditory Models and Generalization of Linear Discriminant Analysis for improved Speech Recognition. Chapter 5 PhD Thesis, Johns Hopkins University, (1997) ps file

Annals of Human Genetics, formerly Annals of Eugenics is a scientific journal. ...

External links

Tutorial about LDA from msstate.edu
LDA tutorial using MS Excel

Results from FactBites:

Linear discriminant analysis - Wikipedia, the free encyclopedia (1716 words)
	Discriminant analysis is also different from factor analysis in that it is not an interdependence technique : a distinction between independent variables and dependent variables (also called criterion variables) must be made.
	The terms Fisher's linear discriminant and LDA are often used interchangeably, although Fisher's original article The Use of Multiple Measures in Taxonomic Problems (1936) actually describes a slightly different discriminant, which does not make some of the assumptions of LDA such as normally distributed classes or equal class covariances.
	LDA and Fisher's discriminant can be extended for use in non-linear classification via the kernel trick.

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.

Contents

LDA for two classes var ACE_AR = {Site: '756743', Size: '300250'};