Research On Graph-Based Semi-Supervised Learning And Its Applications

The perception and utilization of prior knowledge is one of the most important tasks of machine learning methods. In addition to regular supervised information such as class labels and pairwise constraints, the geometry structure of the data distribution is also one of the most important parts of the prior knowledge. Recently, using graph to approach local manifold has been intensively studied, thanks to its convenient local representation, connection with other classical models like regularization techniques, kernel methods and spectral graph theory. In particular, graph based semi-supervised learning has gained considerable interest by its ability to utilize both labeled data and a large quantity of unlabeled data to improve learning performance.Following discussion on the development history and existing challenges of graph-based semi-supervise learning, this dissertation focus on two main topics, i.e. graph construction and graph optimization, and its applications in traditional learning tasks such as classification, clustering and dimensionality reduction. The main results and contributions of this dissertation are as follows.1,The regularization framework that respects both local geometry structure and global discriminate structure is developed, which can be extended to a lot of semi-supervised classification methods by choosing different loss function and regularization term. Based on the framework, a novel approach called locality sensitive discriminate transductive learning (LSD-TL) was developed. LSD-TL directly incorporates the discriminative information as well as the local geometry of the data space into the regularization framework of transductive learning, so that it can explore as much underlying knowledge as possible, and maximize the margins between the data of different classes in each local manifold.2,A novel approach that utilizes prior knowledge to enhance the performance of both dimensionality reduction and data clustering was developed. The new method expands the original constraints set by k-nearest neighbors of the pairwise constraints, then assigned weights to each pairwise constraint by its information power, and finally finds a proper projection matrix guided by the weighted pairwise constraints. With the projection matrix, all the data were projected onto a low-dimensional manifold, so that the intra-class distance is decreased and the inter-class distance is increased. In addition, a new evaluation function was introduced to enforce the k-means cluster algorithm, which had enabled it to provide an appealing clustering performance with minimum violation of the pairwise constraints.3,A novel approach called semi-supervised feature selection based on structure and constraints preserving (SCP) was presented. The SCP method takes both the pairwise constraints and the local & nonlocal structure into account, and defines a new feature selection criterion, i.e. SCP Score. The SCP Score exploits abundant unlabeled data points to learn the geometrical structure of the data space, and uses a few pairwise constraints to discover the margins of different classes. Those features that can preserve the geometrical structure and pairwise constraints information are selected.4,A novel approach based on graph random walk was presented. All the data objects are carried by agents and then mapped to the output space represented by lattices, and the spatial configuration of the agents forms a self-organizing Markov stochastic process. The Markov process finally converges to a stationary probability distribution, in which an optimal label distribution is provided.