A Semi-supervised Learning Algorithm Based On The Decomposition Of Symmetric Matrix

With the rapidly development of Internet, people can more easily collect a large number of unlabeled data. As a result, semi-supervised learning has become a new research hotspot in machine learning recently. In supervised learning, the performance of the model isn’t good enough because of the lack of label data. But In semi-supervised learning, the large number of unlabeled data can improve the performance of the model.The graph-based semi-supervised learning is one of the most commonly used methods.But the graph-based semi-supervised learning usually has a cubic time complexity O(n3) because the inverse of the n×n graph Laplacian is needed. Recently Wei Liu proposed the AnchorGraphReg algorithm which design a regression matrix Z to reduce the time complexity of the inverse of graph Laplacian. But it can’t fit for different data sets because of the fixed graph construction, which may result in bad performance.So, we propose a semi-supervised learning algorithm based on symmetric matrix decomposition in this paper. Given the symmetric matrix S over training sample, we propose a matrix decomposition algorithm based on coordinate descent method to decompose S into a product of HHT where H can effectively reserve the information about the similarity of the samples in the matrix S, which provide favorable conditions for the follow-up semi-supervised learning. We can obtain a "reduced" Laplacian matrix using the matrix H, so it can reduce the the time complexity of the inverse of graph Laplacian and improve the efficiency of building the SSL model. Moreover, we can get a smaller prediction model because of the "reduced" Laplacian matrix. It is easy for us to applicate the prediction model in the memory constrained embedded devices. Lastly, we use some multi-class classification dataset to verify the efficiency of thealgorithm. Compare with the AnchorGraphReg algorithm, our method can get a blanceamong the training speed, accuracy performance, prediction speed and the memory thatoccupied by the prediction model.