Properly-Weighted Graph Laplacian for Semi-supervised Learning
- PDF / 1,824,984 Bytes
- 49 Pages / 439.37 x 666.142 pts Page_size
- 96 Downloads / 250 Views
Properly-Weighted Graph Laplacian for Semi-supervised Learning Jeff Calder1 · Dejan Slepˇcev2
© Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract The performance of traditional graph Laplacian methods for semi-supervised learning degrades substantially as the ratio of labeled to unlabeled data decreases, due to a degeneracy in the graph Laplacian. Several approaches have been proposed recently to address this, however we show that some of them remain ill-posed in the largedata limit. In this paper, we show a way to correctly set the weights in Laplacian regularization so that the estimator remains well posed and stable in the large-sample limit. We prove that our semi-supervised learning algorithm converges, in the infinite sample size limit, to the smooth solution of a continuum variational problem that attains the labeled values continuously. Our method is fast and easy to implement. Keywords Semi-supervised learning · Label propagation · Asymptotic consistency · PDEs on graphs · Gamma-convergence Mathematics Subject Classification 49J55 · 35J20 · 35B65 · 62G20 · 65N12
1 Introduction For many applications of machine learning, such as medical image classification and speech recognition, labeling data requires human input and is expensive [13], while unlabeled data is relatively cheap. Semi-supervised learning aims to exploit this dichotomy by utilizing the geometric or topological properties of the unlabeled data, in conjunction with the labeled data, to obtain better learning algorithms. A significant portion of the semi-supervised literature is on transductive learning, whereby a func-
B
Jeff Calder [email protected] Dejan Slepˇcev [email protected]
1
Department of Mathematics, University of Minnesota, Minneapolis, USA
2
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, USA
123
Applied Mathematics & Optimization
Fig. 1 Example of the degeneracy of graph Laplacian learning with few labels. The graph is a sequence of n = 105 i.i.d. random variables drawn from the unit box [0, 1]2 in R2 , and two labels are given g(0, 0.5) = 0 and g(1, 0.5) = 1
tion is learned only at the unlabeled points, and not as a parameterized function on an ambient space. In the transductive setting, graph based algorithms, such the graph Laplacian-based learning pioneered by [55], are widely used and have achieved great success [3,26,27,46–48,51–54]. Using graph Laplacians to propagate information from labeled to unlabeled points is one of the earliest and most popular approaches [55]. The constrained version of the graph Laplacian learning problem is to minimize over all u : X → R
G L(u) =
wx y (u(x) − u(y))2
x,y∈X
subject to constraint
(1)
u(x) = g(x) for all x ∈
where the data points X form the vertices of a graph with edge weights wx y and ⊂ X are the labeled nodes with label function g : → R. The minimizer u of (1) is the learned function, which extends the given labels g on to the remainder of the graph. In classification contexts, the values of u are
Data Loading...
