● 摘要
机器学习是人工智能的一个重要领域，目前已广泛应用于各个领域。统计学习理论为机器学习问题提供了坚实有力的理论基础，同时也为学习算法的实现提供了条件和保证。随着人们对统计学习理论更加深入的研究和广泛的应用，它已发展成为一门与众多学科交叉的学科。上世纪七十年代起，利用图理论的图割、最短路径以及谱图理论等相关知识，机器学习领域出现了许多基于图的学习算法并在聚类、数据降维、数据挖掘等多种领域得到应用。本文主要研究了三类基于图的正则化学习算法：正则化谱聚类、正则化拉普拉斯特征映射及拉普拉斯正则化最小二乘回归算法，分析了算法的相容性并给出了算法的学习率。主要贡献包括：一、本文证明了正则化谱聚类算法的相容性并给出了收敛阶，这是关于该算法的第一个收敛阶。相容性和学习率是统计学习理论的核心问题，而聚类算法作为机器学习的经典算法已得到广泛应用，然而，由于涉及理论过于复杂，有关聚类算法的相容性结果却不多见。正则化谱聚类算法是近年来备受关注的一类算法，该算法能给出经典谱聚类算法的~out-of-sample~拓展形式。该算法中约束条件与以往不同，这给理论分析带来了本质困难。针对这一问题，本文提出了一些新的思路和方法。我们的证明过程主要是采用学习理论中的误差分析技巧对聚类目标泛函进行详细分析，并利用逼近理论及再生核空间性质给出了算法的收敛阶。二、本文研究了拉普拉斯正则化最小二乘回归（LapRLS）算法的推广误差界，并进一步探讨了无标记样本改进算法学习性能的量化依据。据我们所知，此类量化结果的提出尚属首次。半监督学习是机器学习领域中一个新兴的研究方向，该类算法旨在利用大量易于获取的无标记样本来改进学习性能。虽然国内外学者近年来提出了各种基于不同理念的半监督算法，但是对算法的推广性能估计这一核心问题却仍缺乏了解。我们证明了无标记样本的加入能够将目标函数的选取限制在一个更小的函数集合中，从而降低采样误差。另一方面，利用流形假设，我们可以限制逼近误差使其不会过大，最终能够改进算法的一致误差界。三、我们提出了一种非线性降维算法：正则化拉普拉斯特征映射（RLEM）算法，并给出了该算法的学习率。在计算生物、人工智能等多个领域，人们经常需要面对处理高维复杂数据的困难。如何找到高维数据的一个合适的低维表示是首要的问题。传统的降维方法都是针对高维线性变量设计的。然而，在实际应用中，线性算法不能对非线性分布数据给出可靠的降维结果。近几年兴起的流形学习算法是一类针对非线性数据的有效降维方法。本文提出的~RLEM~算法不再只针对给定样本进行降维，而是给出整个流形的降维映射，从而可直接处理不在原始样本集中的新数据。我们针对不同流形数据进行了多种仿真实验，实验结果表明该算法能够对流形数据进行有效的降维。本文针对基于图的学习算法进行了充分研究，不仅给出了理论上的突破性成果，也设计了新的应用算法，希望我们的工作能为统计学习理论的发展做出贡献。