稀疏图学习的统计基础研究

Graph-based learning techniques have drawn considerable attentions in the recent years. Graph has become an important mathematical tool to encode the relationships among samples, features, labels, or models. How to construct a high-equality graph, or more generally speaking, how to learn the relationships above, is not only a main factor for the success of data analysis and learning algorithms, but also a big challenge in machine learning fields. More recently, researchers proposed a novel graph learning strategy based on sparse representation, which improves traditional graph construction methods to some extent, and is applied successfully in many learning tasks such as dimensionality reduction, clustering, semi-supervised classification, and so on. However, this is currently a research topic in its infancy stage, and thus there exist many open problems which need to be solved urgently. In the project, we expect to study some crucial problems as follows: 1) discuss the statistical assumption behind sparse graph learning, and 2) develop asymptotic analysis result as the increase of sparsity and sample size, in order to digging into the nature of the success of sparse graph and providing theoretical support for related algorithms and applications.

近年来基于图的数据分析和机器学习技术备受关注，图不仅是重要的数据表现形式，并且已成为刻画样本之间、特征之间、标号之间或模型之间相互关系的必要数学工具。如何构建“高质量”的图(更一般地说，如何学习上述关系)既是数据分析与机器学习算法成功的关键，也是其面临的重大挑战。最近研究者提出了基于稀疏表示的图学习策略，克服了传统局部型建图方法的某些不足，并成功应用于降维、聚类和半监督学习等诸多数据分析任务。然而，稀疏图学习的研究刚刚起步，尽管其在很多实际问题中获得了经验性的成功，但其理论基础尚不完善，存在众多问题亟待解决。本项目拟对其中一些关键问题展开深入研究：1）讨论稀疏图学习背后的统计假设；2）分析稀疏图随着样本数增加和稀疏性增强的渐近性结论，旨在发掘稀疏表示建图成功的本质，为相关算法和应用提供必要的理论依据。

. 图不仅是数据分析的对象，更是数据分析的重要工具，在降维、聚类及其半监督学习等问题中具有广泛的应用。图构建方式众多，根据节点的空间位置关系可将其分为“局部”型与“非局部”型两类。前者具有相对完善的理论基础，但实际问题中往往导致参数选择困难等诸多问题；后者（以稀疏表示构图为例）在一定程度上缓解了上述问题，但理论基础尚不完善. 为此，本项目首先基于我们之前的工作——图优化的局部保持投影（GoLPP），设计了一种新型的“非局部”图学习算法——任务依赖的半监督图构建。相关工作发表在SCI期刊Intern. J. Mach. Learn. & Cyber.(DOI: 10.1007/s13042-014-0321-6）。该方法通过松弛和一约束对GoLPP的模型进行了改进，然后在改进的模型中嵌入逐对约束的监督信息。比较传统的局部构图算法，1）半监督的GoLPP将监督信息嵌入到了图与投影矩阵的迭代优化过程中，这些信息既可以是“局部”的，又可以是“非局部”的。2）半监督的GoLPP最后得到的图的边权有清晰的概率解释。具体地，若这两个样本属于must link 或cannot link,则边权是1或0；否则，即没有监督信息时，它们之间的权值位于0,1之间。最后，我们在大量公开数据集上验证了其有效性. 进一步，我们研究了非局部稀疏图与局部近邻图之间的内在联系，以稀疏表示建图的L1准则为例，在多种不同类型数据集上实验，尝试不同的稀疏表示近似算法分析当样本数逐渐增多以及稀疏性逐渐增强时，稀疏表示建图的性能, 并获得了初步的经验性结论，以供相关研究者参考。