{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T04:04:04Z","timestamp":1746245044456,"version":"3.40.4"},"reference-count":28,"publisher":"MIT Press","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2014,12]]},"abstract":"<jats:p>This paper explores lexicographic semirings and their application to problems in speech and language processing. Specifically, we present two instantiations of binary lexicographic semirings, one involving a pair of tropical weights, and the other a tropical weight paired with a novel string semiring we term the categorial semiring. The first of these is used to yield an exact encoding of backoff models with epsilon transitions. This lexicographic language model semiring allows for off-line optimization of exact models represented as large weighted finite-state transducers in contrast to implicit (on-line) failure transition representations. We present empirical results demonstrating that, even in simple intersection scenarios amenable to the use of failure transitions, the use of the more powerful lexicographic semiring is competitive in terms of time of intersection. The second of these lexicographic semirings is applied to the problem of extracting, from a lattice of word sequences tagged for part of speech, only the single best-scoring part of speech tagging for each word sequence. We do this by incorporating the tags as a categorial weight in the second component of a \u3008Tropical, Categorial\u3009 lexicographic semiring, determinizing the resulting word lattice acceptor in that semiring, and then mapping the tags back as output labels of the word lattice transducer. We compare our approach to a competing method due to Povey et al. (2012).<\/jats:p>","DOI":"10.1162\/coli_a_00198","type":"journal-article","created":{"date-parts":[[2014,4,14]],"date-time":"2014-04-14T18:38:40Z","timestamp":1397500720000},"page":"733-761","source":"Crossref","is-referenced-by-count":2,"title":["Applications of Lexicographic Semirings to Problems in Speech and Language Processing"],"prefix":"10.1162","volume":"40","author":[{"given":"Richard","family":"Sproat","sequence":"first","affiliation":[{"name":"Google, Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahsa","family":"Yarmohammadi","sequence":"additional","affiliation":[{"name":"Oregon Health & Science University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Izhak","family":"Shafran","sequence":"additional","affiliation":[{"name":"Oregon Health & Science University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brian","family":"Roark","sequence":"additional","affiliation":[{"name":"Google, Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1017\/S1351324997001599"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Allauzen, Cyril, Mehryar Mohri, and Brian Roark. 2003. Generalized algorithms for constructing statistical language models. In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics, pages 40\u201347, Sapporo.","DOI":"10.3115\/1075096.1075102"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Allauzen, Cyril, Michael Riley, Johan Schalkwyk, Wojciech Skut, and Mehryar Mohri. 2007. OpenFst: A general and efficient weighted finite-state transducer library. In Proceedings of the Twelfth International Conference on Implementation and Application of Automata (CIAA 2007), Lecture Notes in Computer Science, volume 4793, pages 11\u201323, Prague.","DOI":"10.1007\/978-3-540-76336-9_3"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.3115\/1073336.1073354"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1162\/coli_a_00006"},{"key":"R7","unstructured":"Eidelman, Vladimir, Zhongqiang Huang, and Mary Harper. 2010. Lessons learned in part-of-speech tagging of conversational speech. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 821\u2013831, Cambridge, MA."},{"key":"R8","unstructured":"Eisner, Jason. 1998. FootForm decomposed: Using primitive constraints in OT. In Proceedings of SCIL VIII, volume 31, pages 115\u2013143."},{"key":"R10","unstructured":"Eisner, Jason. 2001. Expectation semirings: Flexible EM for learning finite-state transducers. In Proceedings of the ESSLLI Workshop on Finite-State Methods in NLP (FSMNLP), pages 1\u20135, Helsinki."},{"key":"R11","unstructured":"Ellison, T. Mark. 1994. Phonological derivation in Optimality Theory. In COLING-1994, pages 1,007\u20131,013, Kyoto."},{"key":"R12","unstructured":"Frank, Robert and Giorgio Satta. 1998. Optimality theory and the generative complexity of constraint violability. Computational Linguistics, 24:307\u2013315."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1017\/S1351324997001538"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Karttunen, Lauri. 1998. The proper treatment of optimality in computational phonology. In Proceedings of the International Workshop on Finite-State Methods in Natural Language Processing, pages 1\u201312, Ankara.","DOI":"10.3115\/1611533.1611534"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Koskenniemi, Kimmo. 1983. Two-Level Morphology: A General Computational Model of Word-Form Recognition and Production. Ph.D. thesis, University of Helsinki.","DOI":"10.3115\/980431.980529"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.2307\/2310058"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1109\/TASL.2010.2090518"},{"key":"R20","unstructured":"Marcus, Mitch, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313\u2013330."},{"key":"R21","unstructured":"Mohri, Mehryar. 2002. Semiring framework and algorithms for shortest-distance problems. Journal of Automata, Languages and Combinatorics, 7(3):321\u2013350."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1006\/csla.2001.0184"},{"key":"R24","unstructured":"Povey, Daniel, Arnab Ghoshal, Gilles Boulianne, Luk\u00e1\u0161 Burget, Ond\u0159ej Glembek, Nagendra Goel, Mirko Hanneman, Petr Motl\u00ed\u010dek, Yanmin Qian, Petr Schwarz, Jan Silovsk\u00fd, Georg Stemmer, and Karel Vesel\u00fd. 2011. The Kaldi speech recognition toolkit. In IEEE Workshop on Automatic Speech Recognition and Understanding (ASRU). Available from: homepages.inf.ed.ac.uk\/aghoshal\/pubs\/asru11-kaldi.pdf."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Povey, Daniel, Mirko Hannemann, Gilles Boulianne, Luk\u00e1\u0161 Burget, Arnab Ghoshal, Milos Janda, Martin Karafiat, Stefan Kombrink, Petr Motl\u00ed\u010dek, Yanmin Qian, Korbinian Riedhammer, Karel Vesel\u00fd, and Ngoc Thang Vu. 2012. Generating exact lattices in the WFST framework. In IEEE International Conference on Acoustic, Speech, and Signal Processing (ICASSP), pages 4,213\u20134,216, Kyoto.","DOI":"10.1109\/ICASSP.2012.6288848"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/j.csl.2006.06.006"},{"key":"R29","unstructured":"Roark, Brian, Richard Sproat, Cyril Allauzen, Michael Riley, Jeffrey Sorensen, and Terry Tai. 2012. The OpenGrm open-source finite-state grammar software libraries. In Proceedings of the Association for Computational Linguistics, System Demonstrations, pages 61\u201366, Jeju Island."},{"key":"R30","unstructured":"Roark, Brian, Richard Sproat, and Izhak Shafran. 2011. Lexicographic semirings for exact automata encoding of sequence models. In Proceedings of ACL-HLT, 2011, volume 2, pages 1\u20135, Portland, OR."},{"key":"R31","unstructured":"Roche, Emmanuel and Yves Schabes. 1995. Deterministic part-of-speech tagging with finite-state transducers. Computational Linguistics, 21:227\u2013253."},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Shafran, Izhak, Richard Sproat, Mahsa Yarmohammadi, and Brian Roark. 2011. Efficient determinization of tagged word lattices using categorial and lexicographic semirings. In IEEE Workshop on Automatic Speech Recognition and Understanding (ASRU), pages 283\u2013288, Waikoloa, HI.","DOI":"10.1109\/ASRU.2011.6163945"},{"key":"R33","unstructured":"Shugrina, Maria. 2010. Formatting time-aligned ASR transcripts for readability. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, HLT '10, pages 198\u2013206, Los Angeles, CA."},{"key":"R34","doi-asserted-by":"crossref","unstructured":"Soltau, Hagen, Brian Kingsbury, Lidia Mangu, Daniel Povey, George Saon, and Geoffrey Zweig. 2005. The IBM 2004 conversational telephony system for rich transcription. In International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pages 205\u2013208, Philadelphia, PA.","DOI":"10.1109\/ICASSP.2005.1415086"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1017\/S1351324997001654"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/COLI_a_00198","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T10:58:37Z","timestamp":1746183517000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/40\/4\/733-761\/1496"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,12]]}},"alternative-id":["10.1162\/COLI_a_00198"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00198","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"type":"print","value":"0891-2017"},{"type":"electronic","value":"1530-9312"}],"subject":[],"published":{"date-parts":[[2014,12]]}}}