Dimensional Reduction Using Fisher Linear Discriminant Based on Markov Sampling

A High-dimensional data refers to data with a large number of variables, often larger than the number of observations. High-dimensional data are encountered in a wide range of areas such as engineering, biometrics, psychometrics, and neuroimaging. Classifying these data is a difficult problem because the enormous number of variables poses challenges to conventional classification methods and renders many classical techniques impractical. A natural solution is to add a dimensionality reduction step before a classification technique is applied. Fisher linear discriminant (FLD) is a well-known method for dimensionality reduction and classification that projects high-dimensional data onto a low-dimensional space where the data achieves maximum class separability. The previous works describing the generalization ability of FLD have usually been based on the assumption of independent and identically distributed (i.i.d.) samples. FLD in finite fixed dimensional settings as a special case, and exhibits the natural properties that it becomes tighter. To overcome this we use Kernel Fisher Discriminant Analysis (KFD),based on Markov sampling for dimensionality reduction. We first establish the bounds on the generalization performance ofKFD based on uniformly ergodic Markov chain (u.e.M.c.) samples, and prove that KFD based on u.e.M.c. samples is consistent. By following the enlightening idea from Markov chain Monto Carlo methods, we also introduce a Markov sampling algorithm for KFD to generate u.e.M.c. samplesfrom a given data of finite size. Through simulation studies and numerical studies on benchmark repository using KFD, we find that KFD based on u.e.M.c. samples generated by Markov sampling can provide smaller misclassification rates compared to i.i.d. samples