Novel algorithms for large scale supervised and one class learning
Lingyan Sheng · 2013
Supervised learning is the machine learning task of inferring a function from labeled training data. There have been numerous algorithms proposed for supervised learning, such as linear discriminant analysis (LDA), support vector machine (SVM), decision trees, and etc. However, most of them are not able to handle an increasingly popular type of data, high dimensional data, such as gene expression data, text documents, MRI images, and etc. This phenomenon is often called the curse of dimensionality. Our solution to this problem is an improvement to LDA that imposes a regularized structure on the covariance matrix, so that it becomes block diagonal while feature reduction is performed. The improved method, which we call block diagonal discriminant analysis (BDLDA), effectively exploits the off diagonal information in the covariance matrix without huge computation and memory requirement. BDLDA is further improved by using treelets as a preprocessing tool. Treelets, by transforming the original data by successive local PCA, concentrates more energy near the diagonal items in the covariance matrix, and thus achieves even better accuracy compared to BDLDA. ? Supervised learning requires labeled information of all classes. However, since labeled data is often more difficult to obtain than unlabeled data, there is an increasing interest in a special form of learning, namely, one class learning. In one class learning, the training set only has samples of one class, and the goal is to distinguish the class from all other samples. We propose a one class learning algorithm, Graph-One Class Learning (Graph-OCL). Graph-OCL is a two step strategy, where we first identify reliable negative samples, and then we classify the samples based on labeled data and the identified negative samples in the first step. The main novelty is the first step, in which graph-based ranking by learning with local and global consistency (LGC) is used. Graph-based ranking is particularly accurate if the samples and their similarities are well represented by a graph. We also theoretically prove that there is a simple method to select a constant parameter ? for LGC, thus eliminating the necessity of model selection by time consuming validation. ? Graph-based methods usually scale badly as a function of the sample size. This can be solved by using the Nystr�m approximation, which samples a few columns to represent the affinity matrix. We propose a new method, BoostNystr�m, which adaptively samples a subset of columns at each iterative step and updates the sampling probability in the next iterative step. This algorithm is based on a novel perspective, which relates the quality of Nystr�m approximation with the subspace spanned by the sampled columns. BoostNystr�m can be potentially applied to Graph-OCL to solve the problem of large data size.