半监督排序的局部学习算法设计与推广性能研究

Ranking is the central problem of many real applications such as information retrieval and collaborative filtering and so on, and it has become a novel hot research topic in machine learning community. Due to the large amount of unlabeled samples in real applications, this project is scheduled to study the semi-supervised ranking problem. The current semi-supervised ranking algorithms are mainly based on manifold learning which is global and their performance depends on the constructed graphs. The time and space complexity of manifold ranking is too high, which makes it difficult to apply to large scale real-world problems. Therefore, how to reduce the computation complexity of semi-supervised ranking has become one difficult problem to be solved. This project aims to utilize the idea of local risk minimization in statistical learning theory to design and analyze localized semi-supervised ranking algorithm, demonstrate the influence of localization strategy and its optimization technique on the learning rate of ranking. Our main research topics include designing localized semi-supervised kernel ranking algorithm, constructing the kernel function based on the background of real problem, designing local and sparse semi-supervised ranking algorithm, studying its fast optimization technique,analyzing the consistency and convergence, establishing its generalization error bound based on the capacity of the hypothesis space. As far as we know, it is our project that introduces the idea of local learning and sparse learning into semi-supervised ranking for the first time, which is expected to enrich statistical learning theory and promote the development of its applications.

排序是信息检索、协同过滤等大量现实应用的核心问题，它已经成为机器学习领域中新的研究热点。由于现实应用中往往存在大量未标记样本，因此本课题主要研究半监督排序问题。当前的半监督排序算法主要是基于流形学习的，此类算法是全局性的，其性能依赖于图的构造，计算的空间与时间复杂度都比较高，难以应用于大规模现实问题之中。如何降低半监督排序算法的计算复杂度是亟待解决的难题。本课题拟运用统计学习理论中局部风险最小化的思想来设计和分析局部化的半监督排序算法，阐明局部化策略及其优化方法对排序学习速度的影响机制。主要研究内容包括：设计局部化的半监督排序算法模型，深入研究基于实际问题背景的核函数的构造，设计局部化稀疏正则化半监督排序学习算法，探讨其快速求解技巧，分析其一致性与收敛性，建立基于假设函数空间容量的推广误差界。本课题首次将局部学习与稀疏学习的思想引入半监督排序之中，有望丰富统计学习理论并推动排序应用的发展。

排序是信息检索、协同过滤等大量现实应用的核心问题，它已经成为机器学习领域中新的研究热点。由于现实问题中往往存在大量训练样本（标记与未标记），因此本课题主要研究如何克服排序学习问题中的计算复杂性问题，并对排序学习模型进行推广性能分析。课题组取得了以下成果：（1）提出了一个新的基于系数的正则化排序模型CLSRRank。与传统的排序学习模型相比，该模型弱化了对函数假设空间的附加条件，不再要求核函数对称正定，从而在计算上具有更大的灵活性。导出了该模型的表示定理，表明该模型的解满足一个既定的线性方程组，从而可以方便地在计算机上运行。（2）提出了一个新的基于随机加权网络的排序模型ELMRank。该模型首次将随机加权网络应用到排序之中，继承了该算法的高效计算的特点。与传统的基于核的排序学习模型相比，ELMRank中的隐层节点参数与训练样本是独立的，因此在训练模型之前就可以对这些参数进行预赋值，从而使计算更加灵活。（3）提出了一个新的多尺度核正则化排序模型MLSRRank。该模型将多尺度核引入到正则化排序之中，能同时学习排序函数中对应不同变化率的部分，使得模型学习能力增强。同时，利用这些不同模型假设空间的复杂度给出了该模型推广误差的上界。这些成果丰富了排序学习的算法模型，降低了模型的计算复杂度，对其做的理论性分析证明了这些模型在较弱的条件下都具有较好的收敛阶。