Parallel Algorithms for Unsupervised Tagging

Parallel Algorithms for Unsupervised Tagging Sujith Ravi Google Mountain View, CA 94043 sravi@google.com Sergei Vassilivitskii Google Mountain View, CA 94043 sergeiv@google.com Vibhor Rastogi∗ Twitter San Francisco, CA vibhor.rastogi@gmail.com Abstract We propose a new method for unsupervised tagging that finds minimal models which are then further improved by Expectation Max- imization training. In contrast to previous approaches that rely on manually specified and multi-step heuristics for model minimiza- tion, our approach is a simple greedy approx- imation algorithm DMLC (DISTRIBUTED- MINIMUM-LABEL-COVER) that solves this objective in a single step. We extend the method and show how to ef- ficiently parallelize the algorithm on modern parallel computing platforms while preserving approximation guarantees. The new method easily scales to large data and grammar sizes, overcoming the memory bottleneck in previ- ous approaches. We demonstrate the power of the new algorithm by evaluating on various sequence labeling tasks: Part-of-Speech tag- ging for multiple languages (including low- resource languages), with complete and in- complete dictionaries, and supertagging, a complex sequence labeling task, where the grammar size alone can grow to millions of entries. Our results show that for all of these settings, our method achieves state-of-the-art scalable performance that yields high quality tagging outputs. 1 Introduction Supervised sequence labeling with large labeled training datasets is considered a solved problem. For ∗The research described herein was conducted while the author was working at Google. instance, state of the art systems obtain tagging ac- curacies over 97% for part-of-speech (POS) tagging on the English Penn Treebank. However, learning accurate taggers without labeled data remains a chal- lenge. The accuracies quickly drop when faced with data from a different domain, language, or when there is very little labeled information available for training (Banko and Moore, 2004). Recently, there has been an increasing amount of research tackling this problem using unsuper- vised methods. A popular approach is to learn from POS-tag dictionaries (Merialdo, 1994), where we are given a raw word sequence and a dictionary of legal tags for each word type. Learning from POS- tag dictionaries is still challenging. Complete word- tag dictionaries may not always be available for use and in every setting. When they are available, the dictionaries are often noisy, resulting in high tag- ging ambiguity. Furthermore, when applying tag- gers in new domains or different datasets, we may encounter new words that are missing from the dic- tionary. There have been some efforts to learn POS taggers from incomplete dictionaries by extending the dictionary to include these words using some heuristics (Toutanova and Johnson, 2008) or using other methods such as type-supervision (Garrette and Baldridge, 2012). In this work, we tackle the problem of unsuper- vised sequence labeling using tag dictionaries. The first reported work on this problem was on POS tag- ging from Merialdo (1994). The approach involved training a standard Hidden Markov Model (HMM) using the Expectation Maximization (EM) algo- rithm (Dempster et al., 1977), though EM does not 105 Transactions of the Association for Computational Linguistics, 2 (2014) 105–118. Action Editor: …

Content truncated to 500 words