Research On Weakly Supervised Learning Based On Controlled Random Walk Model

Traditional supervised learning deals with objects carrying explicit and complete supervision information, requiring enough labeled data to guarantee learners’generaliza-tion ability. However, along with the deepening of research and spreading of application, more and more learning problems face the lack of sufficient and explicit supervision in-formation, which consequently gives birth to various new learning paradigms, such as semi-supervised learning, multi-label learning, multi-instance learning, etc. and emerg-ing learning problems arising from specific applications, i.e. learning with weak label, probabilistic label, ambiguous label, noisy label, etc. In addition, learning problems in practical applications always appear mixed, such as multi-label multi-instance classifi-cation, semi-supervised multi-label classification and multi-label classification with weak labels, etc. In this dissertation, all the problems of learning with incomplete or ambiguous supervision are referred to as the generalized weakly supervised learning.Weakly supervised learning problems arise from various machine learning and pat-tern recognition applications, such as information retrieval, image recognition and under-standing, visual tracking, etc. Weakly supervised examples can be utilized for training set expansion, and hence can be exploited to improve models’generalization ability. Ex-isting weakly supervised learning algorithms are generally subject to specific learning problems and thus can only be applied to certain scenarios. Due to the absence of unified learning frameworks, they are not capable of dealing with more complex (mixed) weakly supervised problems.While previous researches study different weakly supervised learning problem in separate ways, this dissertation, however, treats all weakly supervised learning problems as a whole, aiming to establish an unified framework, which can exploit all kinds of weak supervision information and be applied to any scenarios. The established framework is expected to handle any existing weakly supervised problems and mixtures. In this dissertation, graph based methods are employed as the main techniques. By combining graph methods with existing weakly supervised learning algorithms, we give intensive studies on semi-supervised, multi-label and mixed problems, more details are provided below. (1) Two unified learning frameworks for mixed weakly supervised learning problems are proposed. One framework is the EM model, which is built based on maximum like-lihood estimation; another is the graph model, which derives from graph based methods. We first model the uncertainty of supervision information, and then give a unified descrip-tion for all types of weakly supervised examples, based on which a quantitative method for measuring the degree of supervision information is proposed. Under the framework of EM model, solutions for semi-supervised problem, multi-label learning problem and more complex mixed weakly supervised problem are given respectively. Under the frame-work of graph model, we first investigate the possibility of generalizing existing semi-supervised graph methods to weakly supervised learning. Then, in order to cover the shortage of existing graph methods, an improved graph based method based on Graph Controlled Random Walk, i.e. CRW, is proposed. CRW has strong noise-tolerance, thus it is suitable for learning scenarios where wrong labels may be present in initial labeled training sets. CRW can be employed as one of the common methods which can exploit all kinds of weak supervision information and be fitted into any learning scenarios.(2) An adaptive semi-supervised self-training via embedded manifold transduction is proposed. Conventional self-training only uses labeled examples to label and select the unlabeled examples for training set augmentation. Inevitably, potential classification noise will be introduced to the training set. As a result, self-training’s performance would degrade. This dissertation combines graph methods with self-training by incorporating CRW graph model into the self-labeling process of self-training. Proposed self-training labels all the unlabeled examples in a transductive way. The embedded CRW can not only utilize manifold assumption to output more reliable label predictions by exploiting the information from both labeled and unlabeled data, but also is able to learn directly from noisy examples, resulting in further reduction of risk of introduced noise. Moreover, an adaptive strategy based on learning from noisy examples is proposed. It can auto-matically determine the optimal choice for newly labeled examples by minimizing the expected classification error rates. This strategy is more reasonable than the preset way adopted by conventional algorithms. Extensive experiments on UCI benchmarks verify the effectiveness of the proposed algorithm.(3) A conditional value-based co-training is proposed. Standard co-training itera-tively trains two classifiers under different views, then uses predictions of either classi-fier on the unlabeled examples to augment the training set of the other. In each round of co-training, newly added examples are selected barely according to the classifier’s posteriori probability output, which neglects examples’value with respect to the current classifier. This dissertation combines graph methods with co-training, employs a condi-tional value-based strategy for the guideline of each classifier’s refinement. It is pointed out that both label confidence and informativeness should be considered when selecting newly labeled examples. The previous CRW is incorporated into the auto labeling pro-cess to output more confident label predictions. When selecting newly labeled examples for training set augmentation, the improved co-training will consider classification confi-dence of one classifier as well as the needs of the other. Experiments on several real-world data sets show that proposed algorithm can effectively exploit unlabeled data to achieve better generalization performance.(4) A transductive multi-label graph method for weak labeling is proposed. Real world multi-label learning applications often suffer from shortage of labeled examples and weak label problem (missing labels and noise), where traditional supervised multi-label learning algorithms will fail to work. To rectify the above problem, this dissertation transplants semi-supervised graph methods to the multi-label learning area. First, a graph controlled random walk is utilized to output label information on all the unlabeled ex-amples by label set propagation. Second, a heuristic method is adopted to automatically determine the optimal label set for each unlabeled example. The proposed method can not only use both labeled and unlabeled data to effectively boost the performance of multi-label classification, but also is capable of dealing with weak labeling problems such as learning with missing or wrong labels. Extensive experiments on gene function analysis and natural scene classification data sets under various configurations validate the perfor-mance of proposed method.