Pairwise constraint propagation by semidefinite programming for semi-supervised classification
Pairwise constraint propagation by semidefinite programming for semi-supervised classification
复制标题
DOI：
10.1145/1390156.1390229
复制
发表时间：
2008-07
影响因子：
1
通讯作者：
Zhenguo Li;Jianzhuang Liu;Xiaoou Tang
中科院分区：
文献类型：
--
作者：
Zhenguo Li;Jianzhuang Liu;Xiaoou Tang
我们考虑了从成对约束和未标记数据中学习的一般问题。成对约束指定两个对象是否属于同一类，称为必须链接约束和不能链接约束。我们建议学习一种在数据图上平滑的映射，并将数据映射到一个单位超球面上，其中两个必须链接的对象被映射到同一个点，而两个不能链接的对象被映射到正交的。我们证明了这样的映射可以通过构造一个半定规划问题来实现，这个半定规划问题是凸的，并且可以全局求解。我们的方法可以有效地将成对约束传播到整个数据集。它可以直接应用于多类分类，并可以在统一的框架中处理数据标签、成对约束或它们的混合。对于各种合成和真实数据集上的分类任务，给出了有希望的实验结果。
We consider the general problem of learning from both pairwise constraints and unlabeled data. The pairwise constraints specify whether two objects belong to the same class or not, known as the must-link constraints and the cannot-link constraints. We propose to learn a mapping that is smooth over the data graph and maps the data onto a unit hypersphere, where two must-link objects are mapped to the same point while two cannot-link objects are mapped to be orthogonal. We show that such a mapping can be achieved by formulating a semidefinite programming problem, which is convex and can be solved globally. Our approach can effectively propagate pairwise constraints to the whole data set. It can be directly applied to multi-class classification and can handle data labels, pairwise constraints, or a mixture of them in a unified framework. Promising experimental results are presented for classification tasks on a variety of synthetic and real data sets.