Research And Application On Graph Transduction

Classification is one of the important part during intelligent process of information and has a wide range of application on digital image recognition and other fields. To predict the the relationship between label and data, we need to collect enough labeled data. However it is unrealistic in some fields. Usually unlabeled dataset is much larger than labeled dataset. Compared to supervised learning algorithm, semi-supervised learning algorithm is more effective in classifying the unlabeled dataset with a small portion of the labeled dataset. Graph transduction is an important branch of semi-supervised learning algorithm. The paper studies the theory of graph transduction and its related theories and it discusses the base theroy of graph transduction and analyzes its mainstream, then simply introduces theory of active learning and discribes its representative algorithms.There are two main aspects in this paper. Firstly, it proposes the classification based on graph transduction; Because graph transduction algorithms are sensitive to graph structure that the edges between different classes could create strong connections across the classes, even with relatively small weights, the paper proposes a measure of the shortest path between the labeled dataset and the unlabeled dataset, which is used to classify the unlabeled dataset. In this process, it proposes two measuring forms of the shortest path. Secondly, it proposes the active learning algorithm based on graph transduction. Graph transduction algorithms strongly depend on initial labeled dataset, while active learning can effectively reduce the dependence. In order to obtain the more effective labeled dataset, the target of active learning changes from maximum decrease the uncertainty of the dataset to maximum decrease the value of loss fuction. Entropy is a measure of the uncertainty of system, so active learning based on entropy is not suitable in this case. The proposed approach of active learning can reach the taget of decreasing the value of loss fuction. The efficiency of the proposed algorithms is verified and the accuracy of the algorithms is given by experiments in the relevant sections.