Elamur Research⌕
☰
home / papers / 2013 / Natural Language Inference for Arabic Using Extended Tree Edit Distance with Subtrees

Natural Language Inference for Arabic Using Extended Tree Edit Distance with Subtrees

Paper · 2013 · Maytham Alabbas and Allan Ramsay

Summary

The paper addresses natural language inference (deciding whether a hypothesis follows from a premise) for Modern Standard Arabic. It compares dependency trees with tree edit distance. Standard tree edit distance only edits one node at a time, so dropping a whole modifier phrase costs as much as deleting each of its words separately. The authors extend Zhang-Shasha's dynamic-programming algorithm (ZS-TED) into TED+ST. The new version tracks the actual edit sequences as well as their costs, which lets it notice when a whole subtree is inserted, deleted or exchanged. Such a subtree operation is then charged through a function of its parts' costs, so it can be cheaper than the sum of its node operations. On an annotated Arabic premise–hypothesis dataset, TED+ST beats bag-of-words, Levenshtein distance and ZS-TED, by roughly 5% in F-score and 4% in accuracy. The same ranking appears on the English RTE-2 set parsed with Minipar. This suggests the approach holds across languages and parsers, and supports treating subtrees as units of information for entailment.

Key points

  • TED+ST builds on ZS-TED. It adds two matrices, DPATH for trees and FDPATH for forests, which store the edit operations themselves alongside the D and FD cost matrices.
  • Three-way decision on Arabic (yes / no / unknown):
    • TED+ST: P 67.4%, R 60.2%, F 0.636.
    • ZS-TED: F 0.602.
    • Levenshtein distance: F 0.597.
    • Bag-of-words: F 0.578.
  • Three-way decision on English RTE2:
    • TED+ST: F 0.535.
    • ZS-TED: F 0.512.
    • Bag-of-words: F 0.495.
    • TED+ST beats ZS-TED on precision, recall and F.
  • Parsers used: an Arabic parser at about 81% accuracy on the PATB, and Minipar (about 80% reported on the Suzanne corpus) for RTE-2. The authors expect better parsers to help both TED variants.
  • Lexical relations come from Arabic WordNet (AWN), which is sparse compared with Princeton WordNet (PWN). Future work includes tuning operation costs and thresholds with optimisation algorithms.

Interesting ideas

  • I1. Charging an edit on a whole subtree less than the sum of its single-node edits makes the distance respect phrase-level units, such as removing an optional modifier.
  • I2. The edit algorithm keeps the full sequence of operations (match, exchange, insert, delete) in path matrices, not just a final number, so each decision comes with an inspectable script.
  • I3. Two thresholds on one distance score give a third verdict, "unknown", which reflects how confident the system is rather than claiming contradiction.
  • I4. The method was rerun on a different language, dataset and parser that the authors did not control, as a robustness check.
  • I5. A cheap tree-distance measure can act as a recall-oriented pre-filter before costly deep semantic reasoning.

For Mova

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

  • I1 (answer): when aligning a question's UD tree with a sentence from a fable, dropping an entire adjunct subtree could be penalised lightly, while changes to core arguments stay expensive.
  • I2 (learn): edit scripts between trees from different witness parsers could pinpoint exactly where they disagree, which can feed self-induced repair rules for silver data.
  • I3 (answer): school-test readers could abstain or escalate to a deeper reasoning step when the tree-match cost lands between the thresholds, instead of guessing.
  • I4 (learn): an evaluation could deliberately swap gparse for the perceptron parser, or switch the treebank, to confirm that an improvement does not depend on one parser's quirks.
  • I5 (answer): QA over tales could first rank candidate sentences by subtree-aware edit cost, then send only the top ones through frames and world-model reasoning.

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

🎓University of ManchesterManchester · United Kingdom87 works · 44,938 citations🎓University of BasrahBasra · Iraq3 works · 42 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.Reasoning · 1,426 worksSemitic languages · 2,908 works

Cite

Cite as Maytham Alabbas and Allan Ramsay. 2013. Natural Language Inference for Arabic Using Extended Tree Edit Distance with Subtrees. arXiv:1402.0578 · Journal Of Artificial Intelligence Research, Volume 48, pages 1-22, 2013.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1613/jair.3892 · arXiv 1402.0578

@misc{alabbas2013natural,
  title = {{Natural Language Inference for Arabic Using Extended Tree Edit Distance with Subtrees}},
  author = {Maytham Alabbas and Allan Ramsay},
  year = {2013},
  doi = {10.1613/jair.3892},
  eprint = {1402.0578},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1613/jair.3892}
}

References

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

  1. Alabbas, M. (2011). ArbTE: Arabic textual entailment. In Proceedings of the Second Student Research Workshop associated with RANLP 2011, pp. 48–53, Hissar, Bulgaria. RANLP 2011 Organising Committee.
  2. Alabbas, M., & Ramsay, A. (2011a). Evaluation of combining data-driven dependency parsers for Arabic. In Proceeding of 5th Language & Technology Conference: Human Language Technologies (LTC’11), pp. 546–550, Poznań, Poland. find
  3. Alabbas, M., & Ramsay, A. (2011b). Evaluation of dependency parsers for long Arabic sentences. In Proceeding of International Conference on Semantic Technology and Information Retrieval (STAIR’11), pp. 243–248, Putrajaya, Malaysia. IEEE. find
  4. Alabbas, M., & Ramsay, A. (2012a). Arabic treebank: from phrase-structure trees to dependency trees. In META-RESEARCH Workshop on Advanced Treebanking at the 8th International Conference on Language Resources and Evaluation (LREC), pp. 61–68, Istanbul, Turkey. find
  5. Alabbas, M., & Ramsay, A. (2012b). Combining black-box taggers and parsers for modern standard Arabic. In Federated Conference on Computer Science and Information Systems (FedCSIS-2012), pp. 19 –26, Wroclaw, Poland. IEEE. find
  6. Alabbas, M., & Ramsay, A. (2012c). Improved POS-tagging for Arabic by combining diverse taggers. In Proceedings of 8th Artificial Intelligence Applications and Innovations (AIAI), pp. 107–116, Halkidiki, Greece. Springer. find
  7. Bille, P. (2005). A survey on tree edit distance and related problems. Theoretical Computer Science, 337 (1-3), 217–239. ↗
  8. Black, W., Elkateb, S., Rodriguez, H., Alkhalifa, M., Vossen, P., Pease, A., & Fellbaum, C. (2006). Introducing the Arabic WordNet project. In Proceedings of the 3rd International WordNet Conference (GWC-06), pp. 295–299, Jeju Island, Korea. find
  9. Burger, J., & Ferro, L. (2005). Generating an entailment corpus from news headlines. In Proceedings of the ACL Workshop on Empirical Modeling of Semantic Equivalence and Entailment, pp. 49–54, Ann Arbor, Michigan, USA. Association for Computational Linguistics.
  10. Dagan, I., & Glickman, O. (2004). Probabilistic textual entailment: generic applied modeling of language variability. In PASCAL Workshop on Learning Methods for Text Understanding and Mining, pp. 26–29, Grenoble, France. find
  11. Dagan, I., Glickman, O., & Magnini, B. (2006). The PASCAL recognising textual entailment challenge. In Quiñonero-Candela, J., Dagan, I., Magnini, B., & d’Alché Buc, F. (Eds.), Machine Learning Challenges. Evaluating Predictive Uncertainty, Visual Object Classification, and Recognising Tectual Entailment, Vol. 3944 of Lecture Notes in Computer Science, pp. 177–190. Springer Berlin, Heidelberg. find
  12. Demaine, E., Mozes, S., Rossman, B., & Weimann, O. (2009). An optimal decomposition algorithm for tree edit distance. ACM Transactions on Algorithms (TALG), 6 (1), 2:1–2:19. ↗
  13. Diab, M. (2009). Second generation tools (AMIRA 2.0): fast and robust tokenization, POS tagging, and base phrase chunking. In Proceedings of the 2nd International Conference on Arabic Language Resources and Tools, pp. 285–288, Cairo, Eygpt. The MEDAR Consortium. find
  14. Habash, N. (2010). Introduction to Arabic Natural Language Processing. Synthesis Lectures on Human Language Technologies. Morgan & Claypool Publishers. find
  15. Habash, N., Rambow, O., & Roth, R. (2009). MADA+TOKAN: a toolkit for Arabic tokenization, diacritization, morphological disambiguation, POS tagging, stemming and lemmatization. In Proceedings of the 2nd International Conference on Arabic Language Resources and Tools, Cairo, Eygpt. The MEDAR Consortium. find
  16. Habash, N., Soudi, A., & Buckwalter, T. (2007). On Arabic transliteration. Arabic Computational Morphology, 15–22. ↗
  17. Heilman, M., & Smith, N. (2010). Tree edit models for recognizing textual entailments, paraphrases, and answers to questions. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 1011–1019, Los Angeles, California, USA. Association for Computational Linguistics.
  18. Hobbs, J. R. (2005). The handbook of pragmatics, chap. Abduction in Natural Language Understanding, pp. 724–740. Blackwell Publishing. find
  19. Klein, P. (1998). Computing the edit-distance between unrooted ordered trees. In Proceedings of the 6th Annual European Symposium on Algorithms (ESA ’98), pp. 91–102, Venice, Italy. Springer-Verlag. find
  20. Kouylekov, M. (2006). Recognizing Textual Entailment with Tree Edit Distance: application to Question Answering and Information Extraction. Ph.D. thesis, DIT, University of Trento, Italy. find
  21. Kouylekov, M., & Magnini, B. (2005). Recognizing textual entailment with tree edit distance algorithms. In Proceedings of the1st Challenge Workshop Recognising Textual Entailment, pp. 17–20, Southampton, UK. find
  22. Lin, D. (1998). Dependency-based evaluation of minipar. In Workshop on the Evaluation of Parsing systems, pp. 317–330. Springer. find
  23. Maamouri, M., & Bies, A. (2004). Developing an Arabic treebank: methods, guidelines, procedures, and tools. In Proceedings of the Workshop on Computational Approaches to Arabic Script-based Languages, pp. 2–9, Geneva, Switzerland.
  24. MacCartney, B. (2009). Natural Language Inference. Ph.D. thesis, Department of Computer Science, Stanford University, USA. find
  25. McDonald, R., Lerman, K., & Pereira, F. (2006). Multilingual dependency parsing with a two-stage discriminative parser. In 10th Conference on Computational Natural Language Learning (CoNLL-X), New York, USA. find
  26. Mehdad, Y., & Magnini, B. (2009). Optimizing textual entailment recognition using particle swarm optimization. In Proceedings of the 2009 Workshop on Applied Textual Inference (TextInfer ’09), pp. 36–43, Suntec, Singapore. Association for Computational Linguistics. find
  27. Nivre, J., Hall, J., Nilsson, J., Chanev, A., Eryigit, G., Kübler, S., Marinov, S., & Marsi, E. (2007). MaltParser: a language-independent system for data-driven dependency parsing. Natural Language Engineering, 13 (02), 95–135. ↗
  28. Pawlik, M., & Augsten, N. (2011). RTED: a robust algorithm for the tree edit distance. Proceedings of the VLDB Endowment, 5 (4), 334–345. ↗
  29. Punyakanok, V., Roth, D., & Yih, W. (2004). Natural language inference via dependency tree mapping: An application to question answering. Computational Linguistics, 6, 1–10. find
  30. Ramsay, A., & Sabtan, Y. (2009). Bootstrapping a lexicon-free tagger for Arabic. In Proceedings of the 9th Conference on Language Engineering (ESOLEC’2009), pp. 202–215, Cairo, Egypt. find
  31. Selkow, S. (1977). The tree-to-tree editing problem. Information Processing Letters, 6 (6), 184–186. ↗
  32. Smrž, O., Bielicky, V., Kouřilová, I., Kráčmar, J., Hajič, J., & Zemánek, P. (2008). Prague Arabic dependency treebank: a word on the million words. In Proceedings of the Workshop on Arabic and Local Languages (LREC 2008), pp. 16–23, Marrakech, Morocco. find
  33. Tai, K. (1979). The tree-to-tree correction problem. Journal of the ACM (JACM), 26 (3), 422–433. ↗
  34. Zhang, K., & Shasha, D. (1989). Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal of Computing, 18 (6), 1245–1262. ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/alabbas-2014-natural-language-inference-arabic-using/