Fast And Incremental Algorithms For Exponential Semi-supervised Discriminant Embedding

In various pattern classification problems,semi-supervised learning methods have shown its effectiveness in utilizing unlabeled data to yield better performance than some supervised and unsupervised learning methods.Semi-supervised discriminant embedding(SDE)is a semi-supervised extension of local discriminant embedding(LDE).However,when dealing with high dimensional data,SDE often suffers from the small-sample-size(SSS)problem.In order to settle this problem,an exponential semi-supervised discriminant embedding(ESDE)method was proposed,which makes use of the tool of matrix exponential.Despite its high discriminative ability,the computational overhead and storage capacity of ESDE is very large for high dimensional data.In order to cure this drawback,the first contribution of this paper is to propose a fast implementation on the ESDE method.The key is to equivalently transform the large matrix problem of size (9 into a much smaller one of size 9),where (9 is the data dimension and 9)is the number of training samples,with (9?9)in practice.On the other hand,in many real world applications,it is likely that whole labeled training set is unavailable beforehand,and the training data is obtained incrementally,and the incremental samples may be labeled or unlabeled.Many incremental semi-supervised learning methods have been proposed to deal with this problem,to the best of our knowledge,however,there are no incremental algorithms for matrix exponential discriminant methods till now.To fill in this gap,the second contribution of this paper is to propose incremental ESDE algorithms for incremental learning problems.By studying the structure of the algorithm,the calculation of large matrix is equivalent to that of small matrix.Numerical experiments on some real-world data sets show the numerical behavior of the proposed algorithms.