Graph-based Semi-supervised Learning With Adaptive Similarity Estimation

With rapid development of Internet, mass data is collected in many fields. How to analyze them or mine the knowledge from them is becoming the common desire in many application fields. In such context, the importance of machine learning is increasingly prominent. Besides, as a subject driven by application, it achieved significant progress in past decades, and plays a most active role in computer science.Semi-supervised learning is a novel learning technique in machine learning field. Comparing with traditional machine learning, its research focus lies on the problem that with few (even only few) labeled data at hand, how to classify large amount data with mass unlabeled data and relationships between labeled and unlabeled data. Graph-based semi-supervised learning algorithm is drawing lots of attention in recent years due its some internal characteristics. It models the whole dataset as a graph, data points'relationships as edges, and data points'similarity as edge weights. The objective is to identify the optimal classification function.This paper briefly summarizes the progress in machine learning, and then discusses the short history of semi-supervised learning. And then it introduces the most relevant algorithm label propagation (LP) and linear neighborhood propagation (LNP). Then it addresses the basic idea of adaptive similarity estimation (ASE) algorithm and theoretic backgrounds. The detail of ASE algorithm is presented as this:ASE firstly adopts binary search technique to estimate the neighborhood threshold, and then constructs the graph by optimizing the linear combination of its neighbors and executes the label propagation procedure to classify the data points. The paper conducts experiments on UCI data sets and benchmark data sets and compares with other state-of-the-art graph construction methods. Experimental results validate the effectiveness and superior of ASE algorithm.