Generalization performance of graph-based semi-supervised classification

被引：0
作者：
Hong Chen
LuoQing Li
机构：
[1] Huazhong Agricultural University,College of Science
[2] Hubei University,Faculty of Mathematics and Computer Science
来源：
Science in China Series A: Mathematics | 2009年 / 52卷
关键词：
semi-supervised learning; generalization error; graph Laplacian; graph cut; localized envelope; 68T05; 62J02;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Semi-supervised learning has been of growing interest over the past few years and many methods have been proposed. Although various algorithms are provided to implement semi-supervised learning, there are still gaps in our understanding of the dependence of generalization error on the numbers of labeled and unlabeled data. In this paper, we consider a graph-based semi-supervised classification algorithm and establish its generalization error bounds. Our results show the close relations between the generalization performance and the structural invariants of data graph.
引用
收藏
页码：2506 / 2516
页数：10
相关论文
共 29 条
[1]  
Wang J.(2007)Large margin semi-supervised learning J Machine Learning Res 8 1867-1891
[2]  
Shen X.(2004)Semi-supervised learning on Riemannian manifolds Machine Learning 56 209-239
[3]  
Belkin M.(2006)Manifold regularizaion: a geometric framework for learning from labeled and unlabeled examples J Machine Learning Res 7 2399-2434
[4]  
Niyogi P.(2009)Error bounds of semi-supervised multi-graph regularized clessification Inform Sci 179 1960-1969
[5]  
Belkin M.(2007)Generalization error bounds in semi-supervised classification under the cluster assumption J Machine Learning Res 8 1369-1392
[6]  
Niyogi P.(2007)On the effectiveness of Laplacian normalization for graph semi-supervised learning J Machine Learning Res 8 1489-1517
[7]  
Sindhwani V.(2008)Graph-based semi-supervised learning and spectral kernel design IEEE Trans Inform Theory 54 275-288
[8]  
Chen H.(2004)Support vector machine soft margin classifiers: error analysis J Machine Learning Res 5 1143-1175
[9]  
Li L. Q.(2006)Concentration inequalities and asymptotic results for ratio type empirical processes Ann Probab 34 1143-1216
[10]  
Rigollet P.(1996)New concentration inequalities in product spaces Invent Math 126 505-563
123