Label propagation for classification and ranking
Rong Jin, Ming‐Tsang Wu · 2007
Label Propagation has been proven to be an effective semi-supervised learning approach in many applications. The key idea behind label propagation is to first construct a graph in which each node represents a data point and each edge is assigned a weight often computed as the similarity between data points, then propagate the class labels of labeled data to neighbors in the constructed graph in order to make predictions. This dissertation is a comprehensive study of the label propagation approaches in different directions including Relation Propagation, Rank Propagation and Propagation over Directed Graphs. Most previous works on label propagation propagate information among a single type of objects. However, many applications involve multiple types of objects. Inspired by the assumption that the correlation among different types of objects can be very helpful in many cases, a generalized framework for Relation Propagation is proposed to explore the correlation in semi-supervised learning. The key idea behind relation propagation is to construct a graph which involves multiple types of objects and then propagate the relation among different types of objects in this graph. The framework for Relation Propagation is applied to multi-label learning (classification problems) and collaborative filtering (ranking problems). Empirical results show that relation propagation is a more effective approach in comparison with the previous approaches in label propagation. It is very important to study the label propagation approaches for ranking problems due to the existing challenges for label propagation. First, it may not be appropriate to propagate class labels (ordinal values) as numerical values in classification problems. It seems more reasonable to cast the problem into a ranking problem in which the class labels are converted to pairwise preferences between classes for each example and then the preferences are propagated. Second, most previous studies require absolute labels for learning which are often hard to obtain. Instead, relative ordering information is more easily available. Traditional label propagation approaches may not fit with ranked data. Inspired by these challenges, a Rank Propagation framework is proposed for supervised learning. The key idea behind Rank Propagation is to propagate the given preference judgements, instead of the true labels, from the labeled data to unlabeled data and compute the preference matrices for unlabeled data whose principal eigenvectors correspond to the class assignments. The application of this framework is presented in a multi-label categorization task with multiple datasets. The empirical results show that Rank Propagation is an effective approach in comparison with other commonly used supervised learning approaches. Most studies in label propagation focus on using the undirected graphs. Motivated by the assumption that directed graph may better capture the nature of data, a framework for Propagation over Directed Graphs is proposed for utilizing the directed graph in propagation. The question involved in this approach is how to construct and utilize a directed graph. Two asymmetric weight measures, namely KL divergence-based measure and asymmetric cosine similarity, are proposed in order to construct a directed graph. To utilize the directed graphs, one common method is to convert the directed graphs into undirected ones and then apply a standard label propagation approach to the converted undirected graphs. A random walk related method is discussed for this conversion. The application of this framework is presented in a binary classification task and a multi-label classification task. The empirical results show the effectiveness of Propagation over Directed Graphs in comparison with other approaches. In summary, this dissertation discusses the proposed approaches in label propagation, namely Relation Propagation, Rank Propagation and Propagation over Directed Graphs, in order to address the existing challenges in this area. Empirical studies show that the proposed approaches achieve promising performance in given scenarios.