Uncertainty Reduction in Collaborative Bootstrapping: Measure and Algorithm

Uncertainty Reduction in Collaborative Bootstrapping: Measure and Algorithm Yunbo Cao Microsoft Research Asia 5F Sigma Center, No.49 Zhichun Road, Haidian Beijing, China, 100080 i-yucao@microsoft.com Hang Li Microsoft Research Asia 5F Sigma Center, No.49 Zhichun Road, Haidian Beijing, China, 100080 hangli@microsoft.com Li Lian Computer Science Department Fudan University No. 220 Handan Road Shanghai, China, 200433 leelix@yahoo.com Abstract This paper proposes the use of uncertainty reduction in machine learning methods such as co-training and bilingual boot- strapping, which are referred to, in a gen- eral term, as ‘collaborative bootstrapping’. The paper indicates that uncertainty re- duction is an important factor for enhanc- ing the performance of collaborative bootstrapping. It proposes a new measure for representing the degree of uncertainty correlation of the two classifiers in col- laborative bootstrapping and uses the measure in analysis of collaborative boot- strapping. Furthermore, it proposes a new algorithm of collaborative bootstrapping on the basis of uncertainty reduction. Ex- perimental results have verified the cor- rectness of the analysis and have demonstrated the significance of the new algorithm. 1 Introduction We consider here the problem of collaborative bootstrapping. It includes co-training (Blum and Mitchell, 1998; Collins and Singer, 1998; Nigam and Ghani, 2000) and bilingual bootstrapping (Li and Li, 2002). Collaborative bootstrapping begins with a small number of labelled data and a large number of unlabelled data. It trains two (types of) classifiers from the labelled data, uses the two classifiers to label some unlabelled data, trains again two new classifiers from all the labelled data, and repeats the above process. During the process, the two classifiers help each other by exchanging the la- belled data. In co-training, the two classifiers have different feature structures, and in bilingual boot- strapping, the two classifiers have different class structures. Dasgupta et al (2001) and Abney (2002) con- ducted theoretical analyses on the performance (generalization error) of co-training. Their analyses, however, cannot be directly used in studies of co- training in (Nigam & Ghani, 2000) and bilingual bootstrapping. In this paper, we propose the use of uncertainty reduction in the study of collaborative bootstrap- ping (both co-training and bilingual bootstrapping). We point out that uncertainty reduction is an im- portant factor for enhancing the performances of the classifiers in collaborative bootstrapping. Here, the uncertainty of a classifier is defined as the por- tion of instances on which it cannot make classifi- cation decisions. Exchanging labelled data in bootstrapping can help reduce the uncertainties of classifiers. Uncertainty reduction was previously used in active learning. We think that it is this paper which for the first time uses it for bootstrapping. We propose a new measure for representing the uncertainty correlation between the two classifiers in collaborative bootstrapping and refer to it as ‘uncertainty correlation coefficient’ (UCC). We use UCC for analysis of collaborative bootstrap- ping. We also propose a new algorithm to improve the performance of existing collaborative boot- strapping algorithms. In the algorithm, one classi- fier always asks the other classifier to label the most uncertain instances for it. Experimental …

Content truncated to 500 words