Regularization and semi-supervised learning on large graphs
Regularization and semi-supervised learning on large graphs
复制标题
DOI：
10.1007/978-3-540-27819-1_43
复制
发表时间：
2004-01-01
期刊：
影响因子：
--
通讯作者：
Niyogi, P
中科院分区：
文献类型：
--
作者：
Belkin, M;Matveeva, I;Niyogi, P
本文研究了部分标号图的标号问题。这种设置可能出现在许多情况下，从调查抽样到信息检索，再到多种设置中的模式识别。它也是潜在的实际重要性，当数据是丰富的，但标签是昂贵的或需要人工assistance.We的方法开发了一个框架，这样的图的正则化。这些算法非常简单，只需要求解一个单一的、通常是稀疏的线性方程组。使用算法稳定性的概念，我们推导出的泛化误差的界限，并将其与图的结构不变量。一些实验结果测试的正则化算法的性能和推广界的有用性。
We consider the problem of labeling a partially labeled graph. This setting may arise in a number of situations from survey sampling to information retrieval to pattern recognition in manifold settings. It is also of potential practical importance, when the data is abundant, but labeling is expensive or requires human assistance.Our approach develops a framework for regularization on such graphs. The algorithms are very simple and involve solving a single, usually sparse, system of linear equations. Using the notion of algorithmic stability, we derive bounds on the generalization error and relate it to structural invariants of the graph. Some experimental results testing the performance of the regularization algorithm and the usefulness of the generalization bound are presented.