Scaling Semi-supervised Naive Bayes with Feature Marginals

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 343–351, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Scaling Semi-supervised Naive Bayes with Feature Marginals Michael R. Lucas and Doug Downey Northwestern University 2133 Sheridan Road Evanston, IL 60208 mlucas@u.northwestern.edu ddowney@eecs.northwestern.edu Abstract Semi-supervised learning (SSL) methods augment standard machine learning (ML) techniques to leverage unlabeled data. SSL techniques are often effective in text classification, where labeled data is scarce but large unlabeled corpora are readily available. However, existing SSL tech- niques typically require multiple passes over the entirety of the unlabeled data, meaning the techniques are not applicable to large corpora being produced today. In this paper, we show that improving marginal word frequency estimates using unlabeled data can enable semi-supervised text classification that scales to massive unlabeled data sets. We present a novel learning algorithm, which optimizes a Naive Bayes model to accord with statis- tics calculated from the unlabeled corpus. In experiments with text topic classifica- tion and sentiment analysis, we show that our method is both more scalable and more accurate than SSL techniques from previ- ous work. 1 Introduction Semi-supervised Learning (SSL) is a Machine Learning (ML) approach that utilizes large amounts of unlabeled data, combined with a smaller amount of labeled data, to learn a tar- get function (Zhu, 2006; Chapelle et al., 2006). SSL is motivated by a simple reality: the amount of available machine-readable data is exploding, while human capacity for hand-labeling data for any given ML task remains relatively constant. Experiments in text classification and other do- mains have demonstrated that by leveraging un- labeled data, SSL techniques improve machine learning performance when human input is limited (e.g., (Nigam et al., 2000; Mann and McCallum, 2010)). However, current SSL techniques have scal- ability limitations. Typically, for each target concept to be learned, a semi-supervised classi- fier is trained using iterative techniques that exe- cute multiple passes over the unlabeled data (e.g., Expectation-Maximization (Nigam et al., 2000) or Label Propagation (Zhu and Ghahramani, 2002)). This is problematic for text classification over large unlabeled corpora like the Web: new tar- get concepts (new tasks and new topics of interest) arise frequently, and performing even a single pass over a large corpus for each new target concept is intractable. In this paper, we present a new SSL text classi- fication approach that scales to large corpora. In- stead of utilizing unlabeled examples directly for each given target concept, our approach is to pre- compute a small set of statistics over the unlabeled data in advance. Then, for a given target class and labeled data set, we utilize the statistics to improve a classifier. Specifically, we introduce a method that ex- tends Multinomial Naive Bayes (MNB) to lever- age marginal probability statistics P(w) of each word w, computed over the unlabeled data. The marginal statistics are used as a constraint to im- prove the class-conditional probability estimates P(w|+) and P(w|−) for the positive and negative classes, which are often noisy …

Content truncated to 500 words