带约束的图上学习算法研究 

Graph-based learning uses graph theory to deal with the machine learning problems that have underlying graph structures. The performance of a graph-based learning algorithm, to a great extent, depends on its utilization of constraint information. However, researchers rarely systematically analyze the ways how the existing learning algorithms utilize the graph constraints and explore their shortcomings. This project classifies the constraint information in graph-based learning under first-order, second-order and higher-order graph constraints three categories. First, for the classification problems with first-order graph constraints and the clustering problems with second-order graph constraints, we will respectively develop a manifold classification algorithm and an online semi-supervised clustering algorithm, by using a pair of constraint utilization strategies in a dual form. Compared with the existing classification and clustering algorithms, they can make use of the lower-order graph constraints more efficiently and more comprehensively. On that basis, we will propose a new semi-supervised learning problem with higher-order graph constraints. It will be proved as a generalization of the existing semi-supervised learning problems with lower-order and hyper-edge graph constraints. Furthermore, we will develop a semi-supervised classification algorithm that can exploit the structure of the sub-graph constraints, to improve the use of the higher-order graph constraints in respect of efficiency and scope. The research in this project will provide theoretical foundations for the graph-based learning with constraints, and promote both the development and application of the graph-based learning approaches.

基于图的学习应用图论处理具有潜在图结构的机器学习问题。一个基于图的学习算法能否产生好的性能在很大程度上取决于它对约束信息的利用程度。然而，人们却鲜少从图约束的角度系统地分析已有学习算法对约束信息的利用方式及其存在的不足之处。本项目拟将图上学习的约束信息划分为图的一阶、二阶和高阶约束，首先针对带一阶图约束的分类和带二阶图约束的聚类，分别提出一种采用对偶约束利用策略的流形分类算法和在线半监督聚类算法，它们与以往的分类和聚类算法相比，对低阶图约束的利用更高效更全面。在此基础上，我们拟提出一种具有高阶图约束的半监督学习问题，证明它是以往具有图的低阶约束和超边约束的半监督学习问题的泛化描述，并针对其中带子图约束的半监督分类问题，提出一种能充分利用高阶约束结构特征的半监督分类算法，提高对高阶图约束的利用范围和效率。本项目的研究能够为带约束的图上学习算法提供理论基础，进一步推动图上学习方法的发展和应用。

近年来，基于图的学习越来越受到机器学习和数据挖掘研究者的关注。一个基于图的学习算法能否产生好的性能在很大程度上取决于它对约束信息的利用程度。然而，人们却鲜少从图约束的角度系统地分析已有学习算法对约束信息的利用方式及其存在的不足之处。以往的图学习研究大多孤立地看待图和约束两部分信息，仅限于局部地研究某种特定约束的利用方式，缺乏对各种形式各异的图约束的一个整体认识，同时也缺乏在全局观基础上对图约束的有效利用。本项目将图上学习的约束信息划分为图的一阶，二阶和高阶约束。针对具有图的一阶约束的有监督分类问题，我们提出一种采用“点→边→点”的约束利用策略的流形非线性多分类算法，即有监督等度规映射分类器。与其他分类算法相比，该算法从图的一阶和二阶结构两方面同时利用给定约束信息，提高了对一阶图约束的利用效率，有利于提高分类准确率。针对具有图的二阶约束的半监督聚类问题，我们提出一种采用“边→点→边”约束利用策略的在线双层随机游走半监督聚类算法。与其他半监督聚类算法相比，该算法不仅能够处理静态的半监督聚类问题，而且还能高效地处理数据和约束都随时间更新的在线半监督聚类问题，提高了对二阶图约束的利用效率，有助于发现数据潜在的簇内亚结构。在处理低阶图约束的基础上，我们进一步针对具有图的高阶约束的分类问题，提出一种能够利用约束的高阶结构特征的层次多流形分类算法。该算法可以用于处理复杂数据内部包含子数据的分类问题。考虑到有标签数据的高代价性，我们还把层次多流形分类算法扩展为能够利用高阶图约束的半监督分类算法，可以从少量的无标签数据准确推导出大量无标签数据的类别。与以往的超图学习算法相比，该算法不仅拓宽了对高阶图约束不同表现形式的利用范围，而且还提升了半监督学习算法对高阶图约束的利用效率。此外, 我们还应用这些带图约束的学习算法有效解决了一些实际应用问题，包括人脸识别，手写字符识别和医疗诊断等领域，取得了很好的效果。