--- title: "Name Tagging with Word Clusters and — Miller 2004" description: "The authors, from BBN Technologies, aim to cut the annotation effort needed to build a named-entity tagger from days to hours." authors: ["Scott Miller", "Jethran Guinness", "Alex Zamanian"] year: 2004 venue: "Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004" source: "https://aclanthology.org/N04-1043/" licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/papers/miller-2004-name-tagging-word-clusters-discriminative/" --- [Elamur Research](https://md.research.elamur.ai/) · [this page in HTML](https://research.elamur.ai/free/papers/miller-2004-name-tagging-word-clusters-discriminative/) [home](https://md.research.elamur.ai/) / [papers](https://md.research.elamur.ai/free/papers/) / [2004](https://md.research.elamur.ai/free/papers/2004/) / Name Tagging with Word Clusters and Discriminative Training # Name Tagging with Word Clusters and Discriminative Training **Authors:** [Scott Miller](https://md.research.elamur.ai/free/authors/scott-miller/), Jethran Guinness, Alex Zamanian · **Year:** 2004 · **Venue:** Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004 · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/) **Links:** [Publisher's page](https://aclanthology.org/N04-1043/) · [PDF](https://aclanthology.org/N04-1043.pdf) · [OpenAlex](https://openalex.org/W130850236) **Citations:** 262 citations (openalex-snapshot · 2026-10-14) · [103](#cited-by) in our library, of the 140673 papers whose bibliographies we read ## Summary The authors, from BBN Technologies, aim to cut the annotation effort needed to build a named-entity tagger from days to hours. They combine three existing techniques. First, Brown-style hierarchical word clusters, which they reimplemented following the Spatter parser, are learned from about 100 million unlabeled words of Wall Street Journal text from CSR-III. Second, the clusters are encoded as bit-string prefix features in a tagger trained with Collins' averaged perceptron, which, unlike a generative HMM, can handle many overlapping features. Third, active learning selects the sentences the model is least confident about. On the seven MUC-6 categories, the full system needs only about 13% of the labeled data that a strong HMM name finder requires for equal accuracy. It reaches 90 F with under 20,000 annotated words, roughly half a working day for one annotator. With 1M training words it still cuts errors by 25%. This shows that unlabeled text plus smart example selection can largely substitute for manual annotation. ## Key points - **Clustering:** Clusters come from the bigram mutual-information algorithm of Brown et al. (1990), run on the WSJ portion of CSR-III (LDC95T6, about 100M words). Each word gets a binary path in the cluster tree, and the 8-, 12-, 16- and 20-bit prefixes of that path give four cluster granularities. - **Features:** The model uses 19 feature classes. Seven mirror a standard HMM tagger: tag bigram, current, previous and next word, capitalization/number shape, and lowercased word. The other twelve are cluster prefixes for the previous, current and next word. - **Tag set:** 16 tags cover 8 classes (the 7 MUC classes plus null), each split into START and CONTINUE. - **Training:** The averaged perceptron runs for a fixed 5 epochs, with no cross-validation. - **Results:** - Without clusters, the discriminative tagger is slightly worse than the HMM at mid-size training sets. - With clusters, it exceeds 90 F at 50k words, whereas the HMM needs 150k. - At 1M words it scores 96.08 F versus 94.72 for the HMM. - Adding active learning reaches 90 F with fewer than 20k words. ## Interesting ideas - **Multiple cluster granularities:** Using several prefix lengths of a hierarchical cluster code as separate features avoids choosing one cluster size in advance. The discriminative learner decides which granularity is useful. This is easy to transfer to any low-resource tagging task, such as Ukrainian NER or POS tagging. - **Cheap confidence measure:** Confidence is the margin between the best and second-best scores at each word, computed from forward and backward Viterbi passes. The sentence takes the minimum of its word margins. This gives active-learning selection without any extra model. - **Clusters make active learning work better:** Uncertainty is no longer just "seen vs. unseen word", because clusters give partial knowledge about unknown words. Selection therefore becomes informative earlier, so the two techniques reinforce each other. - **Simulated active learning:** Selection can be simulated by letting the system pick from an already-annotated pool, which makes experiments cheap and repeatable. The authors warn that the benefit vanishes once the pool is exhausted, so this setup is most meaningful for small training sets. - **Cost-based evaluation:** Results are framed in annotator time (about 5,000 words per hour, "4 person-hours vs. 4 person-days"), not just F-score. This is a practical way to report gains for projects that must budget annotation. *Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.* Fields: [Linguistics & languages](https://md.research.elamur.ai/free/shelves/linguistics/) Topics: [Part-of-speech tagging](https://md.research.elamur.ai/free/topics/part-of-speech-tagging/) ## Cited by Cited by 103 papers of our library cite it (of the 140673 whose bibliographies we read); 11 of them have a page here, 92 not yet. - [Tailoring Continuous Word Representations for Dependency Parsing](https://md.research.elamur.ai/free/papers/bansal-2014-tailoring-continuous-word-representations-dependency/) - [Natural Language Processing (almost) from Scratch](https://md.research.elamur.ai/free/papers/collobert-2011-natural-language-processing-almost-scratch/) - [Representation Learning for Text-level Discourse Parsing](https://md.research.elamur.ai/free/papers/ji-2014-representation-learning-text-level-discourse/) - [Paraphrasing for Automatic Evaluation](https://md.research.elamur.ai/free/papers/kauchak-2006-paraphrasing-automatic-evaluation/) - [Simple Semi-supervised Dependency Parsing](https://md.research.elamur.ai/free/papers/koo-2008-simple-semi-supervised-dependency-parsing/) - [Lexicon Infused Phrase Embeddings for Named Entity Resolution](https://md.research.elamur.ai/free/papers/passos-2014-lexicon-infused-phrase-embeddings-named/) - [Design Challenges and Misconceptions in Named Entity Recognition](https://md.research.elamur.ai/free/papers/ratinov-2009-design-challenges-misconceptions-named-entity/) - [Discriminative Lexical Semantic Segmentation with Gaps: Running the MWE Gamut](https://md.research.elamur.ai/free/papers/schneider-2014-discriminative-lexical-semantic-segmentation-gaps/) - [Cross-lingual Word Clusters for Direct Transfer of Linguistic Structure](https://md.research.elamur.ai/free/papers/tackstrom-2012-cross-lingual-word-clusters-direct/) - [Word Representations: A Simple and General Method for Semi-Supervised Learning](https://md.research.elamur.ai/free/papers/turian-2010-word-representations-simple-general-method/) - [Emergent Abilities of Large Language Models](https://md.research.elamur.ai/free/papers/wei-2022-emergent-abilities-large-language-models/) ## Cite The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @inproceedings{miller2004name, title = {{Name Tagging with Word Clusters and Discriminative Training}}, author = {Miller, Scott and Guinness, Jethran and Zamanian, Alex}, booktitle = {Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004}, year = {2004}, url = {https://aclanthology.org/N04-1043/} } ``` - [← previous Multi-level Dialogue Act Tags](https://md.research.elamur.ai/free/papers/clark-2004-multi-level-dialogue-act-tags/) - [next → OntoSem Methods for Processing Semantic Ellipsis](https://md.research.elamur.ai/free/papers/aclbulk-2004-mcshane-ontosem-methods-processing-semantic-ellipsis/) - [↑ back to papers of 2004](https://md.research.elamur.ai/free/papers/2004/) ## References 12 references, 3 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. Avrim Blum, Tom Mitchell. 1998. Combining Labeled and Unlabeled Data with Co-Training. COLT: Proceedings of the Workshop on Computational Learning Theory, Morgan Kaufmann Publishers Elizabeth Boschee, Scott Miller, Ralph Weischedel. 2002. Rapid Annotation through Human-Machine Collaboration. HLT-200… [find](https://scholar.google.com/scholar?q=Avrim+Blum%2C+Tom+Mitchell%2E+1998%2E+Combining+Labeled+and+Unlabeled+Data+with+Co%2DTraining%2E+COLT%3A+Proceedings+of+the+Workshop+on+Computational+Learning+Theory%2C+Morgan+Kaufmann+Publishers+Elizabeth+Boschee%2C) [our card](https://md.research.elamur.ai/free/papers/blum-1998-combining-labeled-unlabeled-data-co-training/) 2. Peter F. Brown, Vincent J. Della Pietra, Peter V. deSouza, Jenifer C. Lai, Robert L. Mercer. 1990. Class-based n-gram models of natural language. [find](https://scholar.google.com/scholar?q=Peter+F%2E+Brown%2C+Vincent+J%2E+Della+Pietra%2C+Peter+V%2E+deSouza%2C+Jenifer+C%2E+Lai%2C+Robert+L%2E+Mercer%2E+1990%2E+Class%2Dbased+n%2Dgram+models+of+natural+language%2E) 3. Computational Linguistics Michael Collins. 2002. Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms. [find](https://scholar.google.com/scholar?q=Computational+Linguistics+Michael+Collins%2E+2002%2E+Discriminative+Training+Methods+for+Hidden+Markov+Models%3A+Theory+and+Experiments+with+Perceptron+Algorithms%2E) [our card](https://md.research.elamur.ai/free/papers/collins-2002-discriminative-training-methods-hidden-markov/) 4. Michael Collins. 1997. Three Generative, Lexicalised Models for Statistical Parsing. Proceedings of the 35th Annual Meeting of the ACL, Madrid. [find](https://scholar.google.com/scholar?q=Michael+Collins%2E+1997%2E+Three+Generative%2C+Lexicalised+Models+for+Statistical+Parsing%2E+Proceedings+of+the+35th+Annual+Meeting+of+the+ACL%2C+Madrid%2E) 5. Michael Collins and Yoram Singer. 1999. Unsupervised Models for Named Entity Classification. EMNLP/VLC-99 [find](https://scholar.google.com/scholar?q=Michael+Collins+and+Yoram+Singer%2E+1999%2E+Unsupervised+Models+for+Named+Entity+Classification%2E+EMNLP%2FVLC%2D99) 6. David A. Cohn, Zoubin Ghahramani, Michael I. Jordan. 1996. Active Learning with Statistical Models Advances in Neural Information Processing Systems. [find](https://scholar.google.com/scholar?q=David+A%2E+Cohn%2C+Zoubin+Ghahramani%2C+Michael+I%2E+Jordan%2E+1996%2E+Active+Learning+with+Statistical+Models+Advances+in+Neural+Information+Processing+Systems%2E) 7. Ellen Riloff, Rosie Jones. 1999. Learning Dictionaries for Information Extraction by Multi-Level Bootstrapping AAAI/IAAI John Lafferty, Andrew McCallum, Fernando Pereira. 2001. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. Proc. 18th International Conf. o… [find](https://scholar.google.com/scholar?q=Ellen+Riloff%2C+Rosie+Jones%2E+1999%2E+Learning+Dictionaries+for+Information+Extraction+by+Multi%2DLevel+Bootstrapping+AAAI%2FIAAI+John+Lafferty%2C+Andrew+McCallum%2C+Fernando+Pereira%2E+2001%2E+Conditional+Random+Fiel) 8. Winston Lin, Roman Yangarber and Ralph Grishman. 2003. Bootstrapped Learning of Semantic Classes from Positive and Negative Examples. Proceedings of the ICML-2003 Workshop on The Continuum from Labeled to Unlabeled Data, Washington, D.C. [find](https://scholar.google.com/scholar?q=Winston+Lin%2C+Roman+Yangarber+and+Ralph+Grishman%2E+2003%2E+Bootstrapped+Learning+of+Semantic+Classes+from+Positive+and+Negative+Examples%2E+Proceedings+of+the+ICML%2D2003+Workshop+on+The+Continuum+from+Labele) 9. David M. Magerman. 1995. Statistical Decision-Tree Models for Parsing. Proceedings, ACL Conference. [find](https://scholar.google.com/scholar?q=David+M%2E+Magerman%2E+1995%2E+Statistical+Decision%2DTree+Models+for+Parsing%2E+Proceedings%2C+ACL+Conference%2E) 10. Andrew McCallum, Kamal Nigam. 1998. Employing EM in Pool-Based Active Learning for Text Classification. Proceedings of ICML-98, 15th International Conference on Machine Learning Fernando Pereira, Naftali Tishby, and Lillian Lee. 1993. Distributional Clustering of English Words. Proceedings of the 31… [find](https://scholar.google.com/scholar?q=Andrew+McCallum%2C+Kamal+Nigam%2E+1998%2E+Employing+EM+in+Pool%2DBased+Active+Learning+for+Text+Classification%2E+Proceedings+of+ICML%2D98%2C+15th+International+Conference+on+Machine+Learning+Fernando+Pereira%2C+Naft) 11. Fei Sha and Fernando Pereira. 2003. Shallow Parsing with Conditional Random Fields. Proceedings of Human Language Technology-NAACL, Edmonton, Canada. [find](https://scholar.google.com/scholar?q=Fei+Sha+and+Fernando+Pereira%2E+2003%2E+Shallow+Parsing+with+Conditional+Random+Fields%2E+Proceedings+of+Human+Language+Technology%2DNAACL%2C+Edmonton%2C+Canada%2E) 12. David Yarowsky. 1995. Unsupervised Word Sense Disambiguation Rivaling Supervised Methods. Meeting of the Association for Computational Linguistics [find](https://scholar.google.com/scholar?q=David+Yarowsky%2E+1995%2E+Unsupervised+Word+Sense+Disambiguation+Rivaling+Supervised+Methods%2E+Meeting+of+the+Association+for+Computational+Linguistics) [our card](https://md.research.elamur.ai/free/papers/yarowsky-1995-unsupervised-word-sense-disambiguation-rivaling/)