Regularization and Semi-supervised Learning on Large Graphs
Lecture notes in computer sciencePublished 1 January 2004
Mikhail Belkin, Irina Matveeva, Partha Niyogi
Citations543
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work considers the problem of labeling a partially labeled graph, which may arise in a number of situations from survey sampling to information retrieval to pattern recognition in manifold settings.
Abstract
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.
Keywords
Computer ScienceEngineering
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
MPG.PuRe (Max Planck Society)Learning with Local and Global Consistency
3,750 Citations2003Dengyong Zhou, Olivier Bousquet +3 more
A principled approach to semi-supervised learning is to design a classifying function which is sufficiently smooth with respect to the intrinsic structure collectively revealed by known labeled and unlabeled points.
Semi-supervised learning using Gaussian fields and harmonic functions
3,377 Citations2003Xiaojin Zhu, Zoubin Ghahramani +1 more
Machine LearningText Classification from Labeled and Unlabeled Documents using EM
2,749 Citations2000Kamal Nigam, Andrew Kachites McCallum +2 more
This paper shows that the accuracy of learned text classifiers can be improved by augmenting a small number of labeled training documents with a large pool of unlabeled documents, and presents two extensions to the algorithm that improve classification accuracy under these conditions.
Transductive Inference for Text Classification using Support Vector Machines
2,717 Citations1999Thorsten Joachims
An analysis of why TSVMs are well suited for text classi(cid:12)cation is presented, and an algorithm for training TSVMs e(cid:14)-ciently, handling 10,000 examples and more is proposed.
Matrix Algebra From a Statistician’s Perspective
1,130 Citations1997David A. Harville
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)Learning from Labeled and Unlabeled Data using Graph Mincuts
947 Citations2018Avrim Blum, Shuchi Chawla
An algorithm based on finding minimum cuts in graphs, that uses pairwise relationships among the examples in order to learn from both labeled and unlabeled data is considered.
Lecture notes in computer scienceKernels and Regularization on Graphs
839 Citations2003Alexander J. Smola, Risi Kondor
It is shown that the class of positive, monotonically decreasing functions on the unit interval leads to kernels and corresponding regularization operators and can be found as a special case of the reasoning.
Diffusion Kernels on Graphs and Other Discrete Input Spaces
732 Citations2002Risi Kondor, John Lafferty
This paper proposes a general method of constructing natural families of kernels over discrete structures, based on the matrix exponentiation idea, and focuses on generating kernels on graphs, for which a special class of exponential kernels called diffusion kernels are proposed.
Partially labeled classification with Markov random walks
563 Citations2001Martin Szummer, Tommi Jaakkola
This work combines a limited number of labeled examples with a Markov random walk representation over the unlabeled examples and develops and compares several estimation criteria/algorithms suited to this representation.
Cluster Kernels for Semi-Supervised Learning
461 Citations2002Olivier Chapelle, Jason Weston +1 more
A framework to incorporate unlabeled data in kernel classifier, based on the idea that two points in the same cluster are more likely to have the same label is proposed by modifying the eigenspectrum of the kernel matrix.
Bulletin of the London Mathematical SocietySPECTRAL GRAPH THEORY (CBMS Regional Conference Series in Mathematics 92)
438 Citations1998Norman Biggs
Journal of the ACMApproximation algorithms for classification problems with pairwise relationships
405 Citations2002Jon Kleinberg, Éva Tardos
IEEE Transactions on Information TheoryDistribution-free performance bounds for potential function rules
227 Citations1979Luc Devroye, T. Wagner
It is shown that the mean-square difference between the probability of error for the nde and its deleted estimate is bounded by A/ \sqrt{n} where A is an explicitly given constant depending only on M and the potential function.
IEEE Transactions on Information TheoryDistribution-free inequalities for the deleted and holdout error estimates
119 Citations1979Luc Devroye, T. Wagner
In the discrimination problem the random variable \theta, known to take values in {1,\ldots,M} , is estimated from the random vector X taking values in {\bfR}^{d} .
Algorithmic Stability and Generalization Performance
88 Citations2000Olivier Bousquet, André Elisseeff
This work presents a novel way of obtaining PAC-style bounds on the generalization error of learning algorithms, explicitly using their stability properties, and demonstrates that regularization networks possess the required stability property.