Boosting with pairwise constraints

In supervised learning tasks, boosting can combine multiple weak learners into a stronger one. AdaBoost is one of the most popular boosting algorithms, which is widely used and stimulates extensive research efforts in the boosting research community. Different from supervised learning, semi-supervised learning aims to make full use of both labeled and unlabeled data to improve learning performance, and has drawn considerable interests in both research and applications. To harness the power of boosting, it is important and interesting to extend AdaBoost to semi-supervised scenarios. Moreover, in semi-supervised learning, it is believed that incorporating pairwise constraints such as side-information is promising to obtain more satisfiable results. However. how to extend AdaBoost with pairwise constraints remains an open problem. In this paper, we propose a novel framework to solve this problem based on the gradient descent view of boosting. The proposed framework is almost as simple and flexible as AdaBoost, and can be readily applied in the presence of pairwise constraints. We present theoretical results, show possible further extensions, and validate the effectiveness via experiments. (C) 2009 Elsevier B.V. All rights reserved.