Relating Function Class Complexity and Cluster Structure in the Function Domain with Applications to Transduction

Guy Lever; JMLR W&CP 9:437-444, 2010.

Abstract

We relate function class complexity to structure in the function domain. This facilitates risk analysis relative to cluster structure in the input space which is particularly effective in semi-supervised learning. In particular we quantify the complexity of function classes defined over a graph in terms of the graph structure.