Learning with insufficient training data in a classification problem has become an important topic in the machine learning community. To address this problem, one solution is to integrate new information sources that are complementary to the labeled data. In this talk, I will present an algorithm which effectively learns the classification
decision boundary with only pairwise constraints (a pairwise constraint is a pair of examples together with a binary variable indicating whether they belong to the same class or not). We show that by providing very few labeled examples this approach is Bayes consistent with high probability as the number of pairwise contraints increases. Furthermore, we study how to combine both labeled and pairwise constraints in real applications. Some experimental results will be given to illustrate its practical value.