Learning from Labeled and Unlabeled Data with Label Propagation

Published 1 January 2002

Xiongjie Zhu, Zoubin Ghahramani

Citations1,568

TL;DR

A simple iterative algorithm, label propagation, to propagate labels through the dataset along high density areas deﬁned by unlabeled data is proposed and its solution is analyzed, and its connection to several other algorithms is analyzed.

Abstract

We investigate the use of unlabeled data to help labeled data in classification. We propose a simple iterative algorithm, label propagation, to propagate labels through the dataset along high density areas defined by unlabeled data. We give the analysis of the algorithm, show its solution, and its connection to several other algorithms. We also show how to learn parameters by minimum spanning tree heuristic and entropy minimization, and the algorithm&apos;s ability to do feature selection. Experiment results are promising.

Keywords

Computer Science

Proceedings of the American Mathematical SocietyOn the shortest spanning subtree of a graph and the traveling salesman problem

5,003 Citations1956Joseph B. Kruskal

View PDF

Machine LearningAn Introduction to Variational Methods for Graphical Models

3,775 Citations1999Michael I. Jordan, Zoubin Ghahramani +2 more

This paper presents a tutorial introduction to the use of variational methods for inference and learning in graphical models (Bayesian networks and Markov random fields), and describes a general framework for generating variational transformations based on convex duality.

View PDF

neural information processing systemsHandwritten Digit Recognition with a Back-Propagation Network

3,637 Citations1989Yann LeCun, Bernhard E. Boser +5 more

Minimal preprocessing of the data was required, but architecture of the network was highly constrained and specifically designed for the task, and has 1% error rate and about a 9% reject rate on zipcode digits provided by the U.S. Postal Service.

IEEE Transactions on Pattern Analysis and Machine IntelligenceA database for handwritten text recognition research

2,237 Citations1994J.J. Hull

An image database for handwritten text recognition research is described that contains digital images of approximately 5000 city names, 5000 state names, 10000 ZIP Codes, and 50000 alphanumeric characters to overcome the limitations of earlier databases.

Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)Learning from Labeled and Unlabeled Data using Graph Mincuts

947 Citations2018Avrim Blum, Shuchi Chawla

An algorithm based on finding minimum cuts in graphs, that uses pairwise relationships among the examples in order to learn from both labeled and unlabeled data is considered.

Diffusion Kernels on Graphs and Other Discrete Input Spaces

732 Citations2002Risi Kondor, John Lafferty

This paper proposes a general method of constructing natural families of kernels over discrete structures, based on the matrix exponentiation idea, and focuses on generating kernels on graphs, for which a special class of exponential kernels called diffusion kernels are proposed.

Partially labeled classification with Markov random walks

563 Citations2001Martin Szummer, Tommi Jaakkola

This work combines a limited number of labeled examples with a Markov random walk representation over the unlabeled examples and develops and compares several estimation criteria/algorithms suited to this representation.

Encyclopedia of Machine Learning and Data MiningLearning from Labeled and Unlabeled Data

469 Citations2017Claude Sammut, Geoffrey I. Webb

View PDF

Link analysis, eigenvectors and stability

203 Citations2001Andrew Y. Ng, Alice X. Zheng +1 more

This paper addresses the question of when HITS and PageRank can be expected to give stable rankings under small perturbations to the hyperlink patterns, using tools from matrix perturbation theory and Markov chain theory.