Training a Naive Bayes Classifier via the EM Algorithm with a Class Distribution Constraint

Training a Naive Bayes Classifier via the EM Algorithm with a Class Distribution Constraint Yoshimasa Tsuruoka‡† and Jun’ichi Tsujii†‡ †Department of Computer Science, University of Tokyo Hongo 7-3-1, Bunkyo-ku, Tokyo 113-0033 JAPAN ‡CREST, JST (Japan Science and Technology Corporation) Honcho 4-1-8, Kawaguchi-shi, Saitama 332-0012 JAPAN {tsuruoka,tsujii}@is.s.u-tokyo.ac.jp Abstract Combining a naive Bayes classifier with the EM algorithm is one of the promising ap- proaches for making use of unlabeled data for disambiguation tasks when using local con- text features including word sense disambigua- tion and spelling correction. However, the use of unlabeled data via the basic EM algorithm often causes disastrous performance degrada- tion instead of improving classification perfor- mance, resulting in poor classification perfor- mance on average. In this study, we introduce a class distribution constraint into the iteration process of the EM algorithm. This constraint keeps the class distribution of unlabeled data consistent with the class distribution estimated from labeled data, preventing the EM algorithm from converging into an undesirable state. Ex- perimental results from using 26 confusion sets and a large amount of unlabeled data show that our proposed method for using unlabeled data considerably improves classification per- formance when the amount of labeled data is small. 1 Introduction Many of the tasks in natural language processing can be addressed as classification problems. State-of-the- art machine learning techniques including Support Vec- tor Machines (Vapnik, 1995), AdaBoost (Schapire and Singer, 2000) and Maximum Entropy Models (Ratna- parkhi, 1998; Berger et al., 1996) provide high perfor- mance classifiers if one has abundant correctly labeled examples. However, annotating a large set of examples generally requires a huge amount of human labor and time. This annotation cost is one of the major obstacles to applying machine learning techniques to real-world NLP applica- tions. Recently, learning algorithms called minimally super- vised learning or unsupervised learning that can make use of unlabeled data have received much attention. Since collecting unlabeled data is generally much easier than annotating data, such techniques have potential for solv- ing the problem of annotation cost. Those approaches in- clude a naive Bayes classifier combined with the EM al- gorithm (Dempster et al., 1977; Nigam et al., 2000; Ped- ersen and Bruce, 1998), Co-training (Blum and Mitchell, 1998; Collins and Singer, 1999; Nigam and Ghani, 2000), and Transductive Support Vector Machines (Joachims, 1999). These algorithms have been applied to some tasks including text classification and word sense disam- biguation and their effectiveness has been demonstrated to some extent. Combining a naive Bayes classifier with the EM algo- rithm is one of the promising minimally supervised ap- proaches because its computational cost is low (linear to the size of unlabeled data), and it does not require the features to be split into two independent sets unlike co- training. However, the use of unlabeled data via the basic EM algorithm does not always improve classification perfor- mance. In fact, this often causes disastrous performance degradation resulting in poor classification performance on average. To alleviate this problem, we introduce a class distribution constraint …

Content truncated to 500 words