Graph complexity for structure and learning

Posted in Science on September 24, 2008


Graph complexity for structure and learning

The talk will consider ways of bounding the complexity of a graph as measured by the number of partitions satisfying certain properties. The approach adopted uses Vapnik Chervonenkis dimension techniques. An example of such a bound was given by Kleinberg et al (2004) with an application to network failure detection. We describe a new bound in the same vein that depends on the eigenvalues of the graph Laplacian. We show an application of the result to transductive learning of a graph labelling from examples.

Author: John Shawe Taylor, University Of London

Watch Video

Tags: Science, Lectures, Computer Science, Machine Learning, VideoLectures.Net, Graph Theory, Structured data, Mathematics