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.