Learning Bigrams from Unigrams

Proceedings of ACL-08: HLT, pages 656–664, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Learning Bigrams from Unigrams Xiaojin Zhu† and Andrew B. Goldberg† and Michael Rabbat‡ and Robert Nowak§ †Department of Computer Sciences, University of Wisconsin-Madison ‡Department of Electrical and Computer Engineering, McGill University §Department of Electrical and Computer Engineering, University of Wisconsin-Madison {jerryzhu, goldberg}@cs.wisc.edu, michael.rabbat@mcgill.ca, nowak@ece.wisc.edu Abstract Traditional wisdom holds that once docu- ments are turned into bag-of-words (unigram count) vectors, word orders are completely lost. We introduce an approach that, perhaps surprisingly, is able to learn a bigram lan- guage model from a set of bag-of-words docu- ments. At its heart, our approach is an EM al- gorithm that seeks a model which maximizes the regularized marginal likelihood of the bag- of-words documents. In experiments on seven corpora, we observed that our learned bigram language models: i) achieve better test set per- plexity than unigram models trained on the same bag-of-words documents, and are not far behind “oracle bigram models” trained on the corresponding ordered documents; ii) assign higher probabilities to sensible bigram word pairs; iii) improve the accuracy of ordered- document recovery from a bag-of-words. Our approach opens the door to novel phenomena, for example, privacy leakage from index files. 1 Introduction A bag-of-words (BOW) is a basic document repre- sentation in natural language processing. In this pa- per, we consider a BOW in its simplest form, i.e., a unigram count vector or word histogram over the vocabulary. When performing the counting, word order is ignored. For example, the phrases “really neat” and “neat really” contribute equally to a BOW. Obviously, once a set of documents is turned into a set of BOWs, the word order information within them is completely lost—or is it? In this paper, we show that one can in fact partly recover the order information. Specifically, given a set of documents in unigram-count BOW representa- tion, one can recover a non-trivial bigram language model (LM)1, which has part of the power of a bi- gram LM trained on ordered documents. At first glance this seems impossible: How can one learn bigram information from unigram counts? However, we will demonstrate that multiple BOW documents enable us to recover some higher-order information. Our results have implications in a wide range of natural language problems, in particular document privacy. With the wide adoption of natural language applications like desktop search engines, software programs are increasingly indexing computer users’ personal files for fast processing. Most index files include some variant of the BOW. As we demon- strate in this paper, if a malicious party gains access to BOW index files, it can recover more than just unigram frequencies: (i) the malicious party can re- cover a higher-order LM; (ii) with the LM it may at- tempt to recover the original ordered document from a BOW by finding the most-likely word permuta- tion2. Future research will quantify the extent to which such a privacy breach is possible in theory, and will find solutions to prevent …

Content truncated to 500 words