PaperlayerView exact revision on arXiv

Source-linked AI summary

Semi-supervised learning with max-margin graph cuts

Branislav Kveton, Michal Valko, Ali Rahimi, Ling Huang

arXiv:2604.26818v1cs.LGstat.ML

TL;DR

Semi-supervised learning addresses settings where labeled data are limited relative to available unlabeled data. This paper learns margin-maximizing graph cuts from labels inferred by a harmonic function, and reports that the method usually outperforms manifold regularization of SVMs. The paper also identifies a mismatch between the soft-label assumption in its theory and the hard labels used in its solutions.

  • Problem

    Semi-supervised learning uses both labeled and unlabeled examples, addressing settings where data are abundant but labeling resources are limited.

    Source: §1 · p. 1

  • Method

    The method computes harmonic-function labels on a data graph and learns a margin-maximizing discriminator conditioned on those labels.

    Source: §1 · p. 1

  • Results

    The method usually outperforms manifold regularization of SVMs across evaluations on a synthetic problem and three UCI datasets.

    Source: §7 · p. 8

  • Takeaways & Limitations

    The paper presents a semi-supervised max-margin approach whose generalization error can be bounded and which incorporates the kernel trick and sparse adjacency matrices.

    Source: §1 · p. 1

    The theoretical analysis assumes soft labels, whereas the reported solutions use hard labels; whether the theoretically sound setting performs better in practice remains open.

    Source: §7 · p. 8

Abstract

from arXiv · show

This paper proposes a novel algorithm for semisupervised learning. This algorithm learns graph cuts that maximize the margin with respect to the labels induced by the harmonic function solution. We motivate the approach, compare it to existing work, and prove a bound on its generalization error. The quality of our solutions is evaluated on a synthetic problem and three UCI ML repository datasets. In most cases, we outperform manifold regularization of support vector machines, which is a state-of-the-art approach to semi-supervised max-margin learning.

1 INTRODUCTION

Semi-supervised learning uses labeled and unlabeled examples, addressing settings where data are plentiful but labeling resources are limited. The paper combines harmonic-function label inference with a margin-maximizing discriminator, and reports improved results over manifold regularization in typical cases.

1 INTRODUCTION

  • Semi-supervised learning combines labeled and unlabeled examples, a setting suited to abundant data and limited labeling resources.Source: §1 · p. 1
  • The method first computes harmonic-function labels on a data adjacency graph, then learns a discriminator that maximizes margin with respect to those inferred labels.The paper calls this approach max-margin graph cuts.Source: §1 · p. 1
  • It typically outperforms manifold regularization of SVMs, especially for linear and cubic decision boundaries.The paper evaluates its solutions on UCI ML repository datasets.Source: §1 · p. 1
  • The paper also shows that manifold regularization of linear and cubic SVMs can fail on an almost trivial problem and makes the harmonic solution with soft labeling constraints stable.Source: §1 · p. 1

2 REGULARIZED HARMONIC FUNCTION SOLUTION

The section reviews harmonic-function label inference on a data graph and regularizes the graph Laplacian to control confidence in labels assigned to unlabeled vertices. The regularization parameter changes the solution from ordinary harmonic inference toward vanishing confidence on unlabeled vertices.

2 REGULARIZED HARMONIC FUNCTION SOLUTION

  • The harmonic-function solution can be viewed as a random walk on the data graph that ends when it reaches a labeled vertex, with predictions reflecting the walk's label probabilities.Source: §2 · p. 2
  • Adding γgI to the Laplacian controls confidence in labels assigned to unlabeled vertices.Here γg is a scalar and I is the identity matrix.Source: §2 · p. 2
  • In the random-walk interpretation, γg adds a sink where each step can terminate with probability γg/(di+γg), reducing confidence with distance from labeled vertices.Source: §2 · p. 2
  • At γg = 0 the solution is the ordinary harmonic solution, while at γg = ∞ confidence on unlabeled vertices falls to zero; regularization also shifts all Laplacian eigenvalues by γg.The eigenvalue shift is used in the paper's generalization-error bound.Source: §2 · p. 2

3 MAX-MARGIN GRAPH CUTS

Max-margin graph cuts first compute regularized harmonic labels, then train a kernel discriminator using examples selected by confidence in those labels. Confidence thresholding and the graph regularizer govern which examples contribute to learning and allow interpolation toward supervised learning.

3 MAX-MARGIN GRAPH CUTS

  • The algorithm computes a regularized harmonic solution from a sparse linear system when the data adjacency graph is sparse, then learns a max-margin discriminator conditioned on its inferred labels.Source: §3 · p. 2
  • The hinge loss is V(f, x, y) = max{1 − yf(x), 0}; f belongs to an RKHS HK, and ∥·∥K measures the complexity of f.Source: §3 · p. 2
  • Examples with uncertain inferred labels are excluded when |ℓ*i| < ε, and increasing γg lowers confidence toward zero.Thresholding by ε allows interpolation between supervised learning on labeled examples and semi-supervised learning on all data.Source: §3 · p. 2
  • The learned function has a kernel expansion, enabling the kernel trick; when γg = ∞, the solution corresponds to supervised SVM learning.Source: §3 · p. 2

4 EXISTING WORK

The section reviews semi-supervised SVMs and manifold-regularized SVMs, contrasting their objectives and highlighting where restricted manifold regularization can fail.

4.1 SEMI-SUPERVISED SVMS

  • Semi-supervised SVMs use a non-convex hat loss that is hard to optimize globally, whereas max-margin graph cuts use two stages to make learning convex.The stages infer unlabeled labels with the regularized harmonic solution and then minimize corresponding convex losses.Source: §4 · p. 2, §4.1 · p. 3

4.2 MANIFOLD REGULARIZATION OF SVMS

  • Manifold regularization smooths decision functions through f^TLf; its solutions may resemble graph cuts when both methods’ regularization terms have matching relative weights.The comparison sets γg = γ/γu.Source: §4.2 · p. 3

4.3 MANIFOLD REGULARIZATION FAILS

  • When the function class is restricted, as with linear functions, manifold regularization can perform significantly worse than the harmonic solution.With two labeled examples, changing the regularizer weight changes the discriminator’s slope but not its direction.Source: §4.3 · pp. 3–4
  • For the illustrative linear problem, the manifold-regularized discriminator stays at f*(x) = 0 as γu varies, while max-margin graph cuts are optimal for small γg.The paper reports similar trends for max-margin learning with a cubic kernel.Source: §4.3 · p. 4

5 THEORETICAL ANALYSIS

The theoretical analysis bounds generalization error by combining stability of the harmonic-function solution with existing transductive and inductive bounds. It also examines thresholding uncertain graph-induced labels, reporting lower errors in practice and retained convergence guarantees.

5 THEORETICAL ANALYSIS

  • The analysis combines transductive and inductive bounds, then uses a union bound to obtain a result for a function class with VC dimension h.The harmonic-function solution's stability is part of the generalization analysis.Source: §5 · p. 4, §5.1 · p. 6

5.1 GENERALIZATION ERROR

  • With sufficient regularization, the relaxed harmonic-function problem is stable and the max-margin-cut solution has bounded generalization error.The analysis uses a relaxed harmonic-function solution, while the stated result concerns the solution to problem (16).Source: §5.1 · pp. 4, 6
  • The bound is not practical for choosing γg because its two error terms are difficult to minimize jointly, so the experiments choose γg using a validation set.The passage notes that a similar tuning issue was observed by Belkin et al. (2004).Source: §5.1 · p. 6

5.2 THRESHOLD ε

  • The thresholded bound is asymptotically as good as Proposition 1's and retains the same convergence guarantees despite excluding highly uncertain labels.The passage states this result for the new upper bound.Source: §5.2 · p. 6
  • Excluding examples with |ℓ*_i| < ε from optimization often yields lower thresholded risk and lower training and test errors.The paper attributes the observed trend to excluding the most uncertain examples and illustrates it on three learning problems.Source: §5.2 · p. 6
  • Because γg and ε are often redundant, the experiments fix ε and optimize γg.Different combinations of their values often achieve the same result.Source: §5.2 · p. 7

6 EXPERIMENTS

The experiments compare max-margin graph cuts with manifold-regularized and supervised SVMs on a synthetic problem and three UCI datasets. Graph cuts typically outperform manifold-regularized SVMs, with the largest gains for linear and cubic kernels.

6 EXPERIMENTS

  • The experiments cover a synthetic comparison and three UCI datasets, implementing graph cuts and supervised SVMs with LIBSVM.The manifold-regularized SVM implementation is based on Belkin et al. (2006).Source: §6 · p. 7

6.1 SYNTHETIC PROBLEM

  • On the synthetic problem, graph cuts interpolate between supervised learning on two labeled examples and semi-supervised learning on all data as γg decreases; linear and cubic manifold-regularized SVMs never perfectly separate the clusters.The graph-cut experiment also shows similarity between graph cuts and RBF manifold-regularized SVMs.Source: §6.1 · p. 7

6.2 UCI ML REPOSITORY DATASETS

  • The UCI evaluation transforms letter, digit, and image-segmentation recognition into binary classification problems and varies the training-set labeled fraction from 1% to 10%.Test errors are averaged over binary problems within each dataset; the comparison includes graph cuts, manifold-regularized SVMs, and supervised SVMs.Source: §6.2 · pp. 7–8, Figure 4 · p. 8
  • Max-margin graph cuts outperform manifold-regularized SVMs in 29 of 36 experiments, with the largest improvements usually for linear and cubic kernels.Figure 4 compares the methods across three UCI datasets as the labeled fraction varies from 1% to 10%.Source: §6.2 · p. 8, Figure 4 · p. 8

7 CONCLUSIONS

The paper presents max-margin graph cuts conditioned on harmonic-function-inferred labels, proves a generalization bound, and reports that the method usually outperforms manifold regularization of SVMs. It also leaves open whether the theoretically analyzed soft-label setting improves practice, since the solutions use hard labels.

7 CONCLUSIONS

  • The proposed algorithm learns max-margin graph cuts conditioned on labels induced by the harmonic function solution.The paper also proves a generalization bound for the method.Source: §7 · p. 8
  • The method usually outperforms manifold regularization of SVMs across evaluation on a synthetic problem and three UCI datasets.Source: §7 · p. 8
  • The theoretical analysis assumes soft labels, whereas the solutions use hard labels; whether the theoretically sound setting improves results in practice remains open.Source: §7 · p. 8
Loading 2604.26818v1…