2010 CompressedFisherLinearDiscrimin

• (Durrant et al., 2010) ⇒ Robert J. Durrant, and Ata Kaban. (2010). “Compressed Fisher Linear Discriminant Analysis: Classification of Randomly Projected Data.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835945

Subject Headings:

Notes

• Categories and Subject Descriptors: H.2.8 Database Management: Database applications — Data mining; I.5.1 Pattern Recognition: Models — Statistical.
• General Terms: Theory

Cited By

• http://scholar.google.com/scholar?q=%22Compressed+fisher+linear+discriminant+analysis%3A+classification+of+randomly+projected+data%22+2010
• http://portal.acm.org/citation.cfm?id=1835945&preflayout=flat#citedby

Quotes

Author Keywords

Dimensionality Reduction, Random Projection, Compressed Learning, Linear Discriminant Analysis, Classification

Abstract

We consider random projections in conjunction with classification, specifically the analysis of Fisher's Linear Discriminant (FLD) classifier in randomly projected data spaces.

Unlike previous analyses of other classifiers in this setting, we avoid the unnatural effects that arise when one insists that all pairwise distances are approximately preserved under projection. We impose no sparsity or underlying low-dimensional structure constraints on the data; we instead take advantage of the class structure inherent in the problem. We obtain a reasonably tight upper bound on the estimated misclassification error on average over the random choice of the projection, which, in contrast to early distance preserving approaches, tightens in a natural way as the number of training examples increases. It follows that, for good generalisation of FLD, the required projection dimension grows logarithmically with the number of classes. We also show that the error contribution of a covariance misspecification is always no worse in the low-dimensional space than in the initial high-dimensional space. We contrast our findings to previous related work, and discuss our insights.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 CompressedFisherLinearDiscrimin	Robert J. Durrant Ata Kaban			Compressed Fisher Linear Discriminant Analysis: Classification of Randomly Projected Data		KDD-2010 Proceedings		10.1145/1835804.1835945		2010