Noise Tolerant Versions of the Perceptron Algorithm and New Methods for Processing Structured Data with Kernels

Abstract

Abstract :

The performance of any learning algorithm on real-world data depends heavily on the algorithm's ability to tolerate noise. The perceptron, a remarkably simple and resilient fifty-year-old algorithm, still performs as well or better than more computationally expensive state-of-the-art methods such as support vector machines. In this talk, I present the results of recent work in which I explored several modifications to the classical perceptron algorithm that improve its performance on noisy data.

Structured data are data that are naturally represented as a graph or hypergraph. Examples of such data are molecules and inductive logic programs. Normally a linear classifier would take such data and embed it directly into Euclidean space using some feature-selection algorithm; such techniques can be quite successful. Recent publications in machine learning, however, give compelling evidence that, through the use of so-called "graph" kernels, structured data can be implicitly embedded into a much more expressive feature space than would be possible using an explicit transformation. To date, perceptrons using graph kernels have performed on par with existing methods in certain domains, but have failed to demonstrate any conclusive performance gain. I will present ideas for new graph kernels that I am in the midst of exploring.