Semi-Supervised Learning Based On Graph Representation And Convex Non-Convex Sparse Regularization

In various real-world machine learning applications,the acquisition of data labels is often time-consuming and laborious,and the cost is high.Semi-supervised learning（SSL）can learn the label information of unlabeled data from a small amount of labeled data,which has great practical value.Graph-based semi-supervised learning（GSSL）combines the advantages of graph representation and the learning ability of semi-supervised learning.Compared with other semi-supervised learning methods,the GSSL method has better performance and has been widely concerned in practical applications.Based on the the cluster or piece-wise smoothing assumption in the GSSL model,that is,labels of close-by nodes do not vary much,the graph total variation（GTV）regularization is used to predict unknown labels,which plays a key role in GSSL.By introducing the oriented incidence matrix,the GTV regularization can converted to L₁ norm regularization,and the GSSL model can be converted to a sparse optimization problem.However,the L₁ norm will underestimate the larger value in the sparse solution.In contrast,non-convex sparse regularization can be used to estimate larger values more accurately,but it may cause the objective function to be non-convex and fall into local optimal.Convex non-convex（CNC）sparse regularization reduces underestimation by constructing non-convex regularization terms,and ensures global convexity of objective function by adjusting non-convex parameters under certain conditions,which has attracted wide attention.In this thesis,we propose a novel SSL model based on graph representation and CNC total variation regularization and apply it to video background subtraction for the moving camera.The following is a summary of the main contributions:Firstly,based on the CNC strategy,we build a non-convex GTV regularization as the difference between the GTV regularization and its generalized Moreau envelope（GME）.Secondly,we construct a GSSL model by the proposed non-convex GTV regularization.We also prove that by changing the non-convex control parameters,the proposed GSSL model’s global convexity can be guaranteed,which provides that the proposed model can be solved by ADMM algorithm.Finally,we verify the validity of the proposed GSSL model on both synthetic and real-world data.In the real-world data experiment,we apply GSSL to video background subtraction for the moving camera and conduct the comparison experiments on the PTZ challenge of CDnet2014 dataset.Experimental results show that the proposed GSSL model outperforms the existing unsupervised and supervised learning models in both visual effects and numerical criteria.