摘要翻译：
本文提出了一种新的两两约束传播方法，将具有挑战性的约束传播问题分解为一组独立的半监督学习子问题，并利用基于k-最近邻图的标号传播在二次时间内求解。考虑到这个时间开销与所有可能的成对约束的数量成正比，我们的方法实际上为在整个数据集中穷举传播成对约束提供了一个有效的解决方案。得到的传播成对约束的穷举集进一步用于调整约束谱聚类的相似性矩阵。除了传统的单源数据上的约束传播，我们的方法还扩展到更具挑战性的多源数据上的约束传播，其中每个成对约束定义在来自不同源的一对数据点上。这种多源约束传播在跨模态多媒体检索中有着重要的应用。大量的结果表明了我们的方法的优越性。
---
英文标题：
《Exhaustive and Efficient Constraint Propagation: A Semi-Supervised
  Learning Perspective and Its Applications》
---
作者：
Zhiwu Lu, Horace H.S. Ip, Yuxin Peng
---
最新提交年份：
2011
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Machine Learning        机器学习
分类描述：Papers on all aspects of machine learning research (supervised, unsupervised, reinforcement learning, bandit problems, and so on) including also robustness, explanation, fairness, and methodology. cs.LG is also an appropriate primary category for applications of machine learning methods.
关于机器学习研究的所有方面的论文（有监督的，无监督的，强化学习，强盗问题，等等），包括健壮性，解释性，公平性和方法论。对于机器学习方法的应用，CS.LG也是一个合适的主要类别。
--

---
英文摘要：
  This paper presents a novel pairwise constraint propagation approach by decomposing the challenging constraint propagation problem into a set of independent semi-supervised learning subproblems which can be solved in quadratic time using label propagation based on k-nearest neighbor graphs. Considering that this time cost is proportional to the number of all possible pairwise constraints, our approach actually provides an efficient solution for exhaustively propagating pairwise constraints throughout the entire dataset. The resulting exhaustive set of propagated pairwise constraints are further used to adjust the similarity matrix for constrained spectral clustering. Other than the traditional constraint propagation on single-source data, our approach is also extended to more challenging constraint propagation on multi-source data where each pairwise constraint is defined over a pair of data points from different sources. This multi-source constraint propagation has an important application to cross-modal multimedia retrieval. Extensive results have shown the superior performance of our approach.
---
PDF链接：
https://arxiv.org/pdf/1109.4684