Random Fields, Graph Kernels, and Semi-Supervised Learning
Speaker: John Lafferty , Carnegie Mellon University
Date: November 20 2003
In many traditional approaches to machine learning, a target function is estimated using labeled data, which can be thought of as examples given by a human teacher to his silicon student. However labeled examples are most often very time consuming and expensive to obtain, as they require the efforts of people who must be quite skilled. For instance, obtaining a single labeled example for protein shape classification, which is one of the grand challenges of biological and computational science, requires months of expensive analysis by expert crystallographers. The problem of effectively combining unlabeled data with labeled data is therefore of central importance in machine learning.
We present an approach to semi-supervised learning using Gaussian random fields. In comparison to other recent work based on energy minimization and random fields in machine learning and image processing which uses fields over a discrete label set, we use a relaxation to a continuous sample space, resulting in many attractive properties. In particular, the most probable configuration of the field is unique, is characterized in terms of harmonic functions, and has a closed form solution that can be computed using matrix methods or loopy belief propagation. The resulting classification algorithms based on graph kernels and Gaussian fields have intimate connections with random walks, electric networks, and spectral graph theory. Our approach extends to problems where the labels on individual instances form a graphical structure, which is natural in time series problems such speech processing or protein secondary structure prediction.
Joint work with Jerry Zhu and Zoubin Ghahramani.
See other events that are part of AI Colloquium Series Fall 2003
See other events happening in November 2003