Analysis and algorithms for ℓ-based semi-supervised learning on graphs
Analysis and algorithms for ℓ-based semi-supervised learning on graphs
复制标题
DOI：
10.1016/j.acha.2022.01.004
复制
发表时间：
2022-01
影响因子：
2.5
通讯作者：
Mauricio Flores Rios;J. Calder;Gilad Lerman
中科院分区：
文献类型：
--
作者：
Mauricio Flores Rios;J. Calder;Gilad Lerman
本文研究了基于半监督学习的Laplacian正则化理论及其应用。最近提出了p> 2的图p-Laplacian，作为标准（p= 2）图Laplacian的替代品，用于具有很少标签的半监督学习问题，其中Laplacian学习是退化的。在本文的第一部分中，我们证明了新的离散连续收敛结果的p-Laplace问题的k-最近邻（k-NN）图，这是更常用的在实践中比随机几何图。我们的分析表明，在k-NN图上，当p→∞时，p-Laplacian保留了关于数据分布的信息，Lipschitz学习（p=∞）对数据分布敏感。这种情况可以与随机几何图形成对比，其中p-Laplacian忘记了p→∞时的数据分布。我们还提出了一个一般框架，用于证明基于图的学习中的离散到连续收敛结果，只需要逐点一致性和单调性。在本文的第二部分中，我们开发了快速算法，用于求解p> 2的加权图上的变分和博弈论p-Laplace方程。我们提出了几个有效的和可扩展的算法，这两种配方，并提出数值模拟结果的合成数据表明其收敛性能。最后，我们在MNIST、FashionMNIST和EMNIST数据集上进行了广泛的数值实验，说明了p-Laplacian公式对于具有较少标签的半监督学习的有效性。特别是，我们发现Lipschitz学习（p=∞）在k-NN图上的标签很少的情况下表现良好，这在实验上验证了我们的理论发现，即Lipschitz学习保留了关于k-NN图上数据分布（未标记数据）的信息。
This paper addresses theory and applications of ℓ p-based Laplacian regularization in semi-supervised learning. The graph p-Laplacian for p> 2 has been proposed recently as a replacement for the standard (p= 2) graph Laplacian in semi-supervised learning problems with very few labels, where Laplacian learning is degenerate. In the first part of the paper we prove new discrete to continuum convergence results for p-Laplace problems on k-nearest neighbor (k-NN) graphs, which are more commonly used in practice than random geometric graphs. Our analysis shows that, on k-NN graphs, the p-Laplacian retains information about the data distribution as p→∞ and Lipschitz learning (p=∞) is sensitive to the data distribution. This situation can be contrasted with random geometric graphs, where the p-Laplacian forgets the data distribution as p→∞. We also present a general framework for proving discrete to continuum convergence results in graph-based learning that only requires pointwise consistency and monotonicity. In the second part of the paper, we develop fast algorithms for solving the variational and game-theoretic p-Laplace equations on weighted graphs for p> 2. We present several efficient and scalable algorithms for both formulations, and present numerical results on synthetic data indicating their convergence properties. Finally, we conduct extensive numerical experiments on the MNIST, FashionMNIST and EMNIST datasets that illustrate the effectiveness of the p-Laplacian formulation for semi-supervised learning with few labels. In particular, we find that Lipschitz learning (p=∞) performs well with very few labels on k-NN graphs, which experimentally validates our theoretical findings that Lipschitz learning retains information about the data distribution (the unlabeled data) on k-NN graphs.