Two-way Markov random walk transductive learning algorithm

LI Hong(李宏)¹, LU Xiao-yan(卢小燕)¹, LIU Wei-wen(刘玮文)², Clement K. Kirui¹

(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;
2. Department of Electronic and Information Engineering, Huazhong University of
Science and Technology, Wuhan, 430074, China)

Abstract:Researchers face many class prediction challenges stemming from a small size of training data vis-a-vis a large number of unlabeled samples to be predicted. Transductive learning is proposed to utilize information about unlabeled data to estimate labels of the unlabeled data for this condition. This work presents a new transductive learning method called two-way Markov random walk (TMRW) algorithm. The algorithm uses information about labeled and unlabeled data to predict the labels of the unlabeled data by taking random walks between the labeled and unlabeled data where data points are viewed as nodes of a graph. The labeled points correlate to unlabeled points and vice versa according to a transition probability matrix. We can get the predicted labels of unlabeled samples by combining the results of the two-way walks. Finally, ensemble learning is combined with transductive learning, and Adboost.MH is taken as the study framework to improve the performance of TMRW, which is the basic learner. Experiments show that this algorithm can predict labels of unlabeled data well.

Key words:classification; transductive learning; two-way Markov random walk (TMRW); Adboost.MH