Semi-supervised Classification Algorithm Based On Graph And Entropy Regularization

Semi-supervised learning (SSL) tries to discover the intrinsic structure of the given data by use of lot of unlabeled data, on the basis of which, it finishes the task of dimensionality reduction, classification and regression by making use of few labeled data. Because of its prominent advantage of reducing the cost of labeling manually and improving the performance of machine learning, and its widespread popularity in web page retrieval, text classification, personal identification based on biometrics feature and medical diagnosis, SSL has received the attention of machine learning community since 1990. Now, SSL becomes one of the most active research areas in the machine learning field. Based on analyzing the state of the art and the existing problems of SSL, the thesis mainly investigates some key issues of graph-based and entropy regularization SSL. The contributions are as follows:1. Graph construction. Graph construction is the first step of graph-based SSL algorithm. Most traditional graph construction methods depend on parameters and are sensitive to these parameters. The solutions of the recently proposed L1 norm reconstruction error minimization graph construction models based on sparse representation may be negative, so they can not be used as the graph weights directly. According to these deficiencies, two L1 norm minimization graph construction models based on nonnegative sparse representation named L1_IMP and L1_IMPv which add nonnegative constraints to the existing L1 norm minimization models are proposed. The solutions of the proposed models can not only reflect the close relation between the sample pairs, but also can be used as the graph weights directly. Moreover, L1_IMP and L1_IMPv complete the neighborhood graph construction and graph weights calculation within one step. Experimental results on UCI and face recognition datasets show that the classification accuracy of the label propagation algorithms using L1_IMP and L1_IMPv are better than that of the label propagation algorithms using traditional graph construction methods in most cases.2. Graph-based SSL algorithm by dissimilarity. Dissimilarity, or negative similarity frequently appears in many practical applications such as collaborative filtering problem. Considering that most graph-based SSL algorithms can not deal with negative similarity, a graph-based SSL model based on negative similarity named SMLP is proposed. The optimization objective of SMLP is the ratio between the following inconsistency and consistency: the inconsistency between the class assignment and the positive similarity, and the consistency between the class assignment and the negative similarity. Also SMLP allows the labeled data to be relabeled. A global optimal algorithm is applied for solving SMLP, yielding an??global optimal solution in a computational effort of O ( n 3 log??1 ). Experimental results on UCI datasets and collaborative filtering problem verify the effectiveness of SMLP algorithm.3. Graph-based SSL algorithm for misclassified data. We use soft labels to deal with misclassified data in the circumstance of SSL. First hard labels of labeled samples are converted to soft labels by several existing methods which can accommodate the uncertainty of an external teacher about uncertain patterns better than hard labels. Then soft labels are embedded into the existing graph-based SSL algorithm LGC to deal with the misclassified data. Experimental results on UCI and object recognition datasets with some classes overlapping show that LGC with soft labels is more resistant to label errors compared with LGC with hard labels.4. SSL algorithm based on minimum entropy regularization. A discriminative SSL classification model named MinEnt is established based on the conditional Havrda-Charvat's Structural?-entropy regularization. The basic idea of MinEnt is that a good clustering criterion is also a good description of the unlabeled data. In MinEnt, conditional Havrda-Charvat's Structural?-entropy clustering criterion is used to describe the relation of unlabeled data and theirs labels, log likelihood function is used to describe the labeled data and Quasi-Newton method is applied for solving MinEnt. The proposed algorithm is discriminative which has less dependence on the model selection. Moreover, the proposed algorithm is inductive, so it can predict the labels of the out of the samples easily. Experimental results on several UCI datasets demonstrate the effectiveness of the proposed algorithm.