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


Guy Lever ;
Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, PMLR 9:437-444, 2010.


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.

Related Material