We propose a theoretical framework to analyze semi-supervised classification
under the low density separation assumption in a high-dimensional regime. In
particular, we introduce QLDS, a linear classification model, where the low
density separation assumption is implemented via quadratic margin maximization.
The algorithm has an explicit solution with rich theoretical properties, and we
show that particular cases of our algorithm are the least-square support vector
machine in the supervised case, the spectral clustering in the fully
unsupervised regime, and a class of semi-supervised graph-based approaches. As
such, QLDS establishes a smooth bridge between these supervised and
unsupervised learning methods. Using recent advances in the random matrix
theory, we formally derive a theoretical evaluation of the classification error
in the asymptotic regime. As an application, we derive a hyperparameter
selection policy that finds the best balance between the supervised and the
unsupervised terms of our learning criterion. Finally, we provide extensive
illustrations of our framework, as well as an experimental study on several
benchmarks to demonstrate that QLDS, while being computationally more
efficient, improves over cross-validation for hyperparameter selection,
indicating a high promise of the usage of random matrix theory for
semi-supervised model selection.

我们提出了一个理论框架，用于分析高维情况下基于低密度分离假设的半监督分类。我们介绍了 QLDS，一个线性分类模型，其中低密度分离假设通过二次边界最大化来实现。该算法具有显式解和丰富的理论性质，我们证明了我们算法的特殊情况是有监督情况下的最小二乘支持向量机，完全非监督情况下的谱聚类以及一类半监督图方法。因此，QLDS 在这些有监督和无监督学习方法之间建立了一个平滑的桥梁。利用随机矩阵理论的最新进展，我们正式推导了在渐近情况下的分类误差的理论评估。作为应用，我们得出一个超参数选择策略，找到在我们学习准则的有监督项和无监督项之间的最佳平衡。最后，我们提供了我们框架的广泛示例，以及在几个基准测试上的实验研究，证明了 QLDS 在计算效率更高的同时，在超参数选择上优于交叉验证，表明随机矩阵理论在半监督模型选择中具有很大的潜力。