Elamur Research⌕
☰
home / papers / 1996 / Markov random field based English Part-Of-Speech tagging system

Markov random field based English Part-Of-Speech tagging system

Paper · 1996 · Sung-Young Jung, Young C. Park, Key-Sun Choi et al.

Summary

The paper addresses English part-of-speech tagging. Its starting point is the weaknesses of HMM taggers: they struggle to fuse heterogeneous evidence, they suffer badly from sparse data, and they adapt poorly to new conditions. The authors model the tag sequence as a Markov random field over a one-dimensional neighbourhood of the sentence. Cliques of neighbouring tags carry the unigram, bigram and trigram evidence. A Gibbs distribution represents the posterior over tag sequences, tagging is done by MAP search, and the parameters are learned with maximum-entropy estimation through Improved Iterative Scaling. They build three MRF variants, each adding more information, and compare them with an HMM tagger that uses the same environment and data: the Brown corpus portion of the Penn Treebank, with a 30,000-word test set. The richest MRF variant reaches 97.1% accuracy, against 96.11% for the HMM. The MRF taggers also degrade less when training data is scarce. This matters because it shows that a log-linear model, in which scores are summed, smooths naturally and can absorb extra features without the usual hand-tuned interpolation.

Key points

  • Accuracy is HMM 96.11%, MRF(1) 96.2%, MRF(2) 96.5% and MRF(3) 97.1%. MRF(1) uses the same information as the HMM.
  • MRF(2) adds morphological information, which mainly helps with unknown words and gives the largest gain when training data is small.
  • The neighbourhood system has distance L=2, so each tag is linked to the two tags before and after it. Cliques are tag windows that carry bigram and trigram relations.
  • Parameters come from ME estimation with IIS, following Della Pietra's method, with a Newton-method step for each λ.
  • Decoding can use either Viterbi or simulated annealing.
  • The HMM baseline needed linear interpolation, tuned by forward-backward, plus a frequency of 1 for unknown words.

Interesting ideas

  • I1. The model scores a sequence by adding clique functions rather than multiplying probabilities, so a single unseen local event cannot zero out the whole analysis; strong neighbouring evidence can make up for it.
  • I2. The authors argue that linear interpolation of n-gram sources is a poor way to combine heterogeneous evidence. Maximum entropy lets each source act as a constraint, and the least committed model consistent with all of them is chosen.
  • I3. The models are built incrementally (same information, then plus morphology, then more), and each is plotted against training-set size, which shows where each information source pays off.
  • I4. The design separates the scoring model from the search procedure, so the same MRF can be decoded by Viterbi or by simulated annealing.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

  • I1 (tokens): The en tagger could score tag sequences as sums of weighted local features, so that rare word–tag pairs in fables or school texts do not collapse the whole sentence's analysis.
  • I2 (learn): When fusing votes from several witness parsers into silver data, an ME-style combination could weigh the witnesses consistently instead of relying on hand-set interpolation weights.
  • I3 (learn): Evaluations could routinely report learning curves for each feature-ablation step, making it explainable which feature helps on small or low-resource data.
  • I4 (tree): Keeping parser scoring independent from the decoder would let the perceptron and gparse scores be searched by alternative decoders when exact dynamic programming does not fit non-local features.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Korea Advanced Institute of Science and TechnologyDaejeon · South Korea51 works · 3,167 citations🏢Korea TelecomSeongnam-si · South Korea2 works · 17 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 2Research subjects and languages the work is about.English · 2,263 worksPart-of-speech tagging · 126 works

Cite

Cite as Sung-Young Jung, Young C. Park, Key-Sun Choi and Youngwhan Kim. 1996. Markov random field based English Part-Of-Speech tagging system. COLING 1996 Volume 1: The 16th International Conference on Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{jung1996markov,
  title = {{Markov random field based English Part-Of-Speech tagging system}},
  author = {Sung-Young Jung, Young C. Park, Key-Sun Choi and Youngwhan Kim},
  booktitle = {COLING 1996 Volume 1: The 16th International Conference on Computational Linguistics},
  year = {1996},
  doi = {10.3115/992628.992671},
  url = {https://doi.org/10.3115/992628.992671}
}

References

23 references, 3 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Besag, J. "Spatial interaction and the statistical anMysis of lattice systems( with discusstion )," J. Royal Statist. ,%c., series B, vol. 36, pp. 192-326, 1974. find
  2. Besag, J. "On the Statistical Analysis of Dirty Pictures", J. Royal Statist. Soc., vol. B48, 1986. ↗
  3. Brill, E. "A Simple Rule-Based Part of Speech Tagger", In Proceedings of the 3rd Co@ on Applied Natural Language Processing, pages 153-155, April, 1992.
  4. Charniak, E., C. ltendrickson, N. Jacobson and M. Perkowitz, "Equations for Part-of Speech 'Fagging," Proc. of Nat'l Conf. on Artificial [ntelligence(AAAI-86), pp. 784-789, 11993. In, G. Chun, "Range hnage Segmentation Using Multiple Markov Random Fiehls", Ph.D. thesis, KAIST, KOt{EA, 1993. find
  5. Church, K. W., "A Stochastic PAI~;rS Program and Noun Phrase Parser for Unrestricted Text,", Proceedings of Applied Natural Language Processing, Austin, Texas, pp. 136-143, 1988. find
  6. Darroch, J. N. and D. Ratcliff, "Generalized Iterative Scaling for Long-Linear Models..", The Annals of Mathematical Statistics, Volume 43, pages 1470-1480, 1972. find
  7. Derouault, A. M. and B. Merialdo, "Natural Language Modeling for Phoneme-to-Text Transcription,", [EEE Tr. on Pattern Anaysis and Machine Intelligence, vol. PAMI-8, no.6, Nov. 1986. ↗
  8. Curtis, F. G. and Patric O. Wheatley, "Applied Numerical Analysis", forth edition, ADDISON WESLEY, 1989. find
  9. Forney, G. D., "The Viterbi Algorithm", Proc. of the IEEE, vo[. 61, pp. 268-278, Mar. 1973. ↗
  10. Gamble, E. B., Geiger D. and Possio T., "integration of Vision Modules and labeling of Surface Discontinuities", IEEE Transactions on systems, man and cybernetics, vol. 19, no. 6, November/deeemver 1989. ↗
  11. Geman, S. and Geman D., "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images", IEEE transactions on pattern analysis and machine intelligence, VoI.PAMI-6, NO. 6, NOVEMBER 1984. ↗
  12. Geiger, D. and Girosi F., "ParalM and Deterministic Algorithms from MRF's: Surface Reconstruction", [EEE Transactions on pattern analysis and machine intelligence, VOL 13, NO. 5, MAY 1991. find
  13. IIUANF, X.D., Y. AtHKI and M.A. JACK, "Hidden Markov Models for Speech Recognition", 1990. find
  14. Jaynes, E. T., Information Theory and StatisticM Mechanics, Physics Reviewsl06, pages 620-630, 1957. find
  15. Jelinek, F. , "Self-Organized Language Modeling for Speech Recognition." , in Readings in Speech Recognition, Alex Waibel and Kai-l,'u Lee(Editors). Morgan Kaufinann, 1989. ↗
  16. Kupiec, ,l., Robust Part-of-Speeh Tagging Using a llidden Markov Model, Computer Speech and Language, 1992. find
  17. Marcus, M. P., Beatrice Santorini and Mary Ann Marcinkiewiez, "Building a large annotated corpus of English: the Penn Treebank", Computational Linguistics, Vol. 19, No. 2, pp 313-330, June, 1993. ↗
  18. Merialdo, B., "Tagging English Text with a Probabilistic M o d e l " , Computational Linguistics, Volume 20, no 2, June 1994. find
  19. Nakamura, M., K. Maruyama, T. Kawanata and K. Shikano, "Neural Network Approach of Word Category Prediction for English rl~XtS," Int'l Conf on Computational Linguislics(Coling-90), pp. 213-218, 1990. find
  20. Pietra, S. D., V. D. Pietra and J. Lafferty, "Inducing features of random fields", Carnegie Mellon University, Technical report CMU-CS-95-144, MAY, 1995. find
  21. Rosenfeld, R., "Adaptive Statistical language Modeling: A Maximum Entropy Approach" , Carnegie Mellon Uniw~rsity, technical report CMU-CS-94-138, April 19, 1994. find
  22. Weischedel, 1{., R. Scewartz, a. Ralmucci, M. Meteer, and L. P~awshaw. "Coping with Ambiguity and Unknown Words through Probabilistic Models", Computational Linguistics, 19(2):359-382, 1993.
  23. Zhang, J. and J.W. Modestino, "A Markov Ran-dora Field model-based approach to image interpretation", Visual Communications and image Processing IV, Vol 1199, 1989. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/jung-1996-markov-random-field-based-english/