Research On Learning Of Grap Propagation And Its Applications

Semi-supervised learning (SSL) has not only a significant study in theory, but also many extensively applications in recent years. SSL means learning from both labeled and unlabeled samples, and the start point of which is to improve learning performance depended on the structure information within unlabeled samples. Since such structure information usually can be presented by a graph, learning of graph propagation becomes one of mainstream researches in SSL. The main idea of graph propagation is that the label information can be propagate from labeled vertexs (samples) to unlabeled vertexs (samples), and both the length and quantity of graph paths connecting two vertexs can measure their similarity between them. Currently, learning of graph propagation has incoparated into many research fields of machine learning such as classification, clustering, ranking and dimensionality reduction.However, many key problems still remain open in graph propagation learning, such as: (1) How to progagate given constraints when just some constraints instead of class label are available? (2) How to re-view and re-mine graph propagation idea if no any supervised information given? (3) Can we treat graph propagation as a means of data preprocessing rather than a specific classifier? (4) Whether we can do propagation on a partial graph rather than a full one when we encounter a very lager graph? After making the best of research aiming at these existing problems, we achieve the major results in this thesis as follows:(1) The problem of constraint progagation is converted into learning a kernel matrix, which is named kernel propagation (KP). The previous label propagation (LP) can not directly diffuse partial pair-wise constraint, so we translate constraint diffusion into the propagation of kernel matrix. The main idea of KP is that the available pair-wise constraints are firstly encoded into a small-sized'seed'kernel matrix after solving a small-scale SDP problem, and then such'seed'kernel matrix is diffused into a full kernel matrix by the obtained propagation formula. Specially, LP can be interpreted as a specific KP in certain sense. The experimental results imply that KP has a better integrative performance in comparison to three state-of-art algorithms on the given datasets.(2) A novel data-preprossing method named manifold contraction is proposed. The traditional method of label propagation must be unworkable under unsuperived setting such that an unsupervised data processing named manifold contraction (MC) is suggested. On the one hand, MC can be intuitively interpreted as samples'random walks on a graph; On the other hand, MC is equivalent to making a contraction map on the given sample-set. Morever, MC not only can be incoparated into kernel trick and dimensionality-reduction method intuitively and naturally, but also can guarantee better generalization for classification in thoery.(3) A semi-supervised data preprocessing method named semi-supervised pattern shift (SSPS) is developed. LP usually acts as a specific classifier when partial class labels available, but this limit to use another classifier further to classification task. To combine the strongpoint of graph propagation with many common-used supervised classifer, we introduce the concept of SSPS worked as a data preprocessing under semi-supervsied circumstance. Furthermore, we introduce a sampling technique to accerlate SSPS, and by which the problem of"out-of-sample"in SSPS is also solved. The experimental results indicate that SSPS is superior over some dimensinality reduction methods on the given datasets.(4) An image retrieval method, based on sub-graph regularization, is suggested. Despite feedback-based image retrieval can be treated as a problem of online classication, it bears specific characteristics including the problems of small-sized sample-set, asymmetrical training sample and real-time requirement. It did not take the problems of symmetrical training sample and real-time requirement account into Lu et al.'s work [1] that applying a support vector machine classifier based on full-graph regularization for image retrieval, so thus we popose a new image retrieval algorithm based on query-subgraph regularization, which is named BlapSVM (Biased Laplacian Support Vector Machine). The final experimental results indicate that BlapSVM can cope with the problems of small-sized sample-set, asymmetrical training sample and real-time requirement in feedback-based image retrieval.