Farasa: A Fast and Furious Segmenter for Arabic

What it is about

Farasa splits an Arabic word into prefixes, stem and suffixes. Every character-level split that uses a legal prefix and suffix sequence is generated, and a linear SVM-rank model scores the candidates. The features are stem and affix likelihoods, lexicon membership (a list of valid stems, a gazetteer of names, a list of legal prefix-suffix combinations, a lexicon of stems generated from roots by stem templates) and the length of the stem. A second variant caches segmentations seen in training and applies the classifier only to unseen words. On a new 70-article WikiNews test set of about 18,000 words, Farasa matches MADAMIRA (98.76%) and the lookup variant reaches 98.94%. In machine translation it is about as good as MADAMIRA (BLEU 30.5 against 30.6 in the average row of its Arabic-to-English table) and about fifty times faster. In retrieval on TREC 2001/2002 it is the best of the three segmenters. The main errors are foreign names and very long words.

Ideas

• I1. A legality table as a hard filter: list the prefixes and suffixes and the legal sequences between them (for example, a determiner cannot be followed by another prefix), and reject any split that breaks the table before any scoring. This is cheap, deterministic and easy to check against the pre and suffix tables that tools/hbo already has.
• I2. A stem-validity feature from roots: a candidate stem is accepted only if its root fits a known stem template, for Hebrew the root-and-pattern shapes of the binyanim (for example ktb in the template of katav). Build the stem list from the MACULA lemmas and test whether the feature removes wrong splits.
• I3. A held-out test built from fresh news, not from the Penn treebank alone, with the error types counted (foreign names, long words). Use the same design for tools/hbo, so that segmenter results are not inflated by a narrow training domain.

For Mova

I1 and I2 go into the segmenter of tools/hbo (the pre/lex tables) and into Pronouns, particles and prepositions for the legal sequences of prefixes (w, l, b, k, the article and the relative). I3 is a test set for tools/hbo, built from Hebrew text outside MACULA (for example quotations in commentaries), with the error types counted.

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.18653/v1/n16-3003

@inproceedings{abdelali2016farasa,
  title = {{Farasa: A Fast and Furious Segmenter for Arabic}},
  author = {Abdelali, Ahmed and Darwish, Kareem and Durrani, Nadir and Mubarak, Hamdy},
  booktitle = {Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Demonstrations},
  year = {2016},
  doi = {10.18653/v1/n16-3003},
  url = {https://doi.org/10.18653/v1/n16-3003}
}

References

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

1. Mohammed Aljlayl and Ophir Frieder. 2002. On arabic search: improving the retrieval effectiveness via a light stemming approach. In CIKM-2002, pages 340–347. find
2. Mohammed Attia, Pavel Pecina, Antonio Toral, Lamia Tounsi, and Josef van Genabith. 2011. An open-source finite state morphological transducer for modern standard arabic. In Workshop on Finite State Methods and Natural Language Processing, pages 125– 133. find our card
3. Kenneth Beesley, Tim Buckwalter, and Stuart Newton. 1989. Two-level finite-state analysis of arabic morphology. In Proceedings of the Seminar on Bilingual Computing in Arabic and English, pages 6–7. find
4. Kenneth R Beesley. 1996. Arabic finite-state morphological analysis and generation. In ACL, pages 89–94. find
5. Tim Buckwalter. 2002. Buckwalter {Arabic} morphological analyzer version 1.0. find
6. Mauro Cettolo, Jan Niehues, Sebastian Stüker, Luisa Bentivogli, and Marcello Federico. 2014. Report on the 11th IWSLT Evaluation Campaign. IWSLT-14. find
7. Colin Cherry and George Foster. 2012. Batch Tuning Strategies for Statistical Machine Translation. In Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, HLT-NAACL’12, pages 427–436, Montréal, Canada. find
8. Kareem Darwish and Douglas W Oard. 2007. Adapting morphology for arabic information retrieval*. In Arabic Computational Morphology, pages 245–262. find
9. Kareem Darwish, Walid Magdy, and Ahmed Mourad. 2012. Language processing for arabic microblog retrieval. In ACM CIKM-2012, pages 2427–2430. find
10. Kareem Darwish, Ahmed Abdelali, and Hamdy Mubarak. 2014. Using stem-templates to improve arabic pos and gender/number tagging. In LREC-2014. find our card
11. Kareem Darwish. 2002. Building a shallow arabic morphological analyzer in one day. In Computational Approaches to Semitic Languages, ACL-2002, pages 1–8. http://alt.qcri.org/tools/farasa/ ↗
12. Mona Diab. 2009. Second generation amira tools for arabic processing: Fast and robust tokenization, pos tagging, and base phrase chunking. In Intl. Conference on Arabic Language Resources and Tools. find
13. Nadir Durrani, Helmut Schmid, and Alexander Fraser. 2011. A Joint Sequence Translation Model with Integrated Reordering. In ACL’11, pages 1045–1054, Portland, Oregon, USA, June. find
14. Nadir Durrani, Barry Haddow, Philipp Koehn, and Kenneth Heafield. 2014a. Edinburgh’s Phrase-based Machine Translation Systems for WMT-14. In WMT’14, pages 97–104, Baltimore, Maryland, USA. find
15. Nadir Durrani, Philipp Koehn, Helmut Schmid, and Alexander Fraser. 2014b. Investigating the Usefulness of Generalized Word Representations in SMT. In COLING’14, pages 421–432, Dublin, Ireland. find
16. Nadir Durrani, Hassan Sajjad, Hieu Hoang, and Philipp Koehn. 2014c. Integrating an Unsupervised Transliteration Model into Statistical Machine Translation. In EACL’14, pages 148–153, Gothenburg, Sweden. find
17. Chris Dyer, Victor Chahuneau, and Noah A. Smith. 2013. A Simple, Fast, and Effective Reparameterization of IBM Model 2. In Proceedings of NAACL’13. find
18. Andreas Eisele and Yu Chen. 2010. MultiUN: A Multilingual Corpus from United Nation Documents. In LREC-2010, Valleta, Malta, May. find
19. Michel Galley and Christopher D. Manning. 2008. A Simple and Effective Hierarchical Phrase Reordering Model. In EMNLP-2008, pages 848–856, Honolulu, Hawaii, October. find
20. Spence Green and John DeNero. 2012. A class-based agreement model for generating accurately inflected translations. In ACL-2012. find
21. Nizar Habash, Owen Rambow, and Ryan Roth. 2009. Mada+ tokan: A toolkit for arabic tokenization, diacritization, morphological disambiguation, pos tagging, stemming and lemmatization. In MEDAR, pages 102–109. find
22. Kenneth Heafield. 2011. KenLM: faster and smaller language model queries. In Sixth Workshop on Statistical Machine Translation, EMNLP-2011, pages 187–197, Edinburgh, Scotland, United Kingdom, July. find
23. Liang Huang and David Chiang. 2007. Forest Rescoring: Faster Decoding with Integrated Language Models. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, ACL’07, pages 144–151, Prague, Czech Republic. find
24. Thorsten Joachims. 2006. Training linear svms in linear time. In ACM SIGKDD-2006, pages 217–226. ACM. find
25. Shereen Khoja. 2001. Apt: Arabic part-of-speech tagger. In NAACL, pages 20–25. find
26. Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondrej Bojar, Alexandra Constantin, and Evan Herbst. 2007. Moses: Open source toolkit for statistical machine translation. In ACL-2007, Prague, Czech Republic. find
27. Shankar Kumar and William J. Byrne. 2004. Minimum Bayes-Risk Decoding for Statistical Machine Translation. In Proceedings of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, HLT-NAACL’04, pages 169–176, Boston, Massachusetts, USA. find
28. Will Monroe, Spence Green, and Christopher D Manning. 2014. Word segmentation of informal arabic with domain adaptation. ACL, Short Papers. find
29. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. BLEU: a method for automatic evaluation of machine translation. In ACL-2002, Philadelphia, PA, USA. find our card
30. Arfath Pasha, Mohamed Al-Badrashiny, Mona Diab, Ahmed El Kholy, Ramy Eskander, Nizar Habash, Manoj Pooleery, Owen Rambow, and Ryan M Roth. 2014. Madamira: A fast, comprehensive tool for morphological analysis and disambiguation of arabic. In LREC-2014, Reykjavik, Iceland. Hassan Sajjad, Francisco Guzmà an, Preslav Nakov, Ahmed Abdelali, Kenton Murray, Fahad Al Obaidli, and Stephan Vogel. 2013. QCRI at IWSLT 2013: Experiments in Arabic-English and English-Arabic spoken language translation. In IWSLT-13, December. find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/aclbulk-2016-abdelali-farasa-fast-furious-segmenter-arabic/