---
title: "Arabic Language Modeling with Finite State Transducers (2008)"
description: "As a result, many test words never appear in training data, which hurts language models used in speech recognition. 13 references."
authors: ["Ilana Heintz"]
year: 2008
venue: "Proceedings of the ACL-08: HLT Student Research Workshop"
source: "https://aclanthology.org/P08-3007/"
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/en/papers/heintz-2008-arabic-language-modeling-finite-state/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/heintz-2008-arabic-language-modeling-finite-state/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2008](https://md.research.elamur.ai/free/en/papers/2008/page/2/) / Arabic Language Modeling with Finite State Transducers

# Arabic Language Modeling with Finite State Transducers

**Authors:** Ilana Heintz · **Year:** 2008 · **Venue:** Proceedings of the ACL-08: HLT Student Research Workshop · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **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/P08-3007/) · [PDF](https://aclanthology.org/P08-3007.pdf) · [OpenAlex](https://openalex.org/W2103744051)

**Citations:** 13 citations (OpenAlex, 2026-10-14)

## Summary
Arabic produces a huge number of distinct surface forms by combining roots, templatic patterns, inflectional affixes and clitics. As a result, many test words never appear in training data, which hurts language models used in speech recognition. Heintz tackles this out-of-vocabulary problem by modeling morphemes instead of whole words. She encodes stem templates (such as CCC, mCCC, CACC) as finite state transducers and composes them with a per-word acceptor. This yields a lattice holding every possible stem/affix split, and the analyses are never disambiguated. Expected 4-gram counts are collected over sentence lattices with SRILM, using the TDT4 Arabic broadcast news transcriptions. The resulting FSM-LM is compared with a word 4-gram model (WORD) and a single-segmentation affix model (AFFIX). Scores are normalized per word so that models with different unit sizes can be compared fairly. FSM-LM gets the lowest average negative log probability. It also has much better bigram-to-4-gram coverage, though AFFIX covers slightly more unigrams. The point is that tolerating spurious analyses and letting corpus statistics choose can beat committing to one segmentation early.

## Key points
- **Data:** a subset of TDT4 (100 files across 4 news sources) is used.
  - 90 files (~6.3M unvoweled tokens) for training and 10 files (~700K tokens, ~5K sentences) for testing.
  - Vocabulary is 104,757 words, with ten-fold cross-validation.
- **Model setup:** all models are 4-gram models with Good-Turing smoothing.
  - Each is capped at the 64,000 most frequent units, so the comparison is fair.
  - SRILM computes posterior expected n-gram counts over the lattices, with all paths weighted equally.
- **AFFIX baseline:** it reuses the affix lists of Xiang et al. (2006), which contain 12 prefixes and 34 suffixes plus their pairwise combinations.
  - Rule-based choices produce a single split per word, keeping a stem of at least 3 characters and preferring the longest affix.
- **Average negative log probability per word** (lower is better):

  | Model | Score |
  |---|---|
  | WORD | 4.65 |
  | AFFIX | 5.30 |
  | FSM-LM | 4.56 |

- **Coverage (%)** of test units given probabilities by the model:

  | Model | Unigram | Bigram | Trigram | 4-gram |
  |---|---|---|---|---|
  | WORD | 96.03 | 17.81 | 1.52 | 0.37 |
  | AFFIX | 99.30 | 53.13 | 11.89 | 3.42 |
  | FSM-LM | 98.89 | 69.56 | 27.25 | 9.62 |

## Interesting ideas
- Rather than picking one morphological analysis per word, keep every candidate decomposition and let frequency statistics favor the common pieces; rare spurious splits get little weight, so no disambiguator is needed.
- Morphological templates are compiled as transducers with self-loop affix arcs and bracket symbols marking stem edges; composing them with a word acceptor directly yields explicit, inspectable analyses.
- Counts are gathered as expected values over a lattice: occurrences of an n-gram divided by the number of paths. Ambiguous inputs thus contribute fractional evidence instead of forcing a hard choice.
- Models with different unit granularity are compared by dividing log probability by the number of words rather than units, which removes the unfair advantage of finer segmentation.
- Coverage is reported separately per n-gram order. This shows that a scheme can lose slightly at the unigram level yet gain a lot on longer contexts.

## For Mova

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

- **I1** (tokens): the English morphology layer could keep a small lattice of segmentations for unknown words (e.g. prefix/stem/suffix options) and let corpus counts rank them, with the chosen path still traceable.
- **I2** (tokens): derivational patterns (e.g. -ness, -able, re-) could be written as small composable FSTs whose bracketed outputs show exactly why a lemma was proposed, keeping the step explainable.
- **I3** (learn): when witness parsers disagree on silver data, each candidate arc or label could receive fractional counts proportional to how many witnesses support it, instead of discarding disagreements.
- **I4** (learn): when evaluating alternative tokenizations or subword schemes, normalize scores per original word or sentence so the comparison is not skewed by unit count.
- **I5** (learn): evaluation reports could break coverage of parser or frame patterns down by context size, revealing where sparsity actually hurts.

*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

- [The Ohio State University](https://md.research.elamur.ai/free/en/universities/the-ohio-state-university/) — University, Columbus, United States · 82 works · 18,502 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works

🧭 Topics (2): [🧠 Language models & pretraining](https://md.research.elamur.ai/free/en/topics/language-models/) · 3,320 works · [Semitic languages](https://md.research.elamur.ai/free/en/topics/semitic-languages/) · 2,908 works

## Cite

Cite as: Ilana Heintz. 2008. Arabic Language Modeling with Finite State Transducers. Proceedings of the ACL-08: HLT Student Research Workshop.

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

```bibtex
@inproceedings{heintz2008arabic,
  title = {{Arabic Language Modeling with Finite State Transducers}},
  author = {Ilana Heintz},
  booktitle = {Proceedings of the ACL-08: HLT Student Research Workshop},
  year = {2008},
  doi = {10.3115/1564154.1564163},
  url = {https://doi.org/10.3115/1564154.1564163}
}
```

- [← previous ProPOSEL: A Prosody and POS English Lexicon for Language Engineering](https://md.research.elamur.ai/free/en/papers/brierley-2008-proposel-prosody-pos-english-lexicon/)
- [next → Diacritic Annotation in the Arabic Treebank and its Impact on Parser Evaluation](https://md.research.elamur.ai/free/en/papers/maamouri-2008-diacritic-annotation-arabic-treebank-its/)
- [↑ back to papers of 2008](https://md.research.elamur.ai/free/en/papers/2008/page/2/)

## References

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

1. A Berton, P Fetter, and P Regel-Brietzmann. 1996. Compound words in large vocabulary German speech recognition system. In Proceedings of ICSLP 96, pages 1165–1168. [find](https://scholar.google.com/scholar?q=A+Berton%2C+P+Fetter%2C+and+P+Regel%2DBrietzmann%2E+1996%2E+Compound+words+in+large+vocabulary+German+speech+recognition+system%2E+In+Proceedings+of+ICSLP+96%2C+pages+1165%E2%80%931168%2E)
2. K. Carki, P. Geutner, and T. Schultz. 2000. Turkish lvcsr: Towards better speech recognition for agglutinative languages. In ICASSP 2000, pages 134–137. [↗](https://doi.org/10.5445/ir/34422000)
3. William A. Gale and Geoffrey Sampson. 1995. Good-Turing frequency estimation without tears. Journal of Quantitative Linguistics, 22:217–37. [↗](https://doi.org/10.1080/09296179508590051)
4. P Geutner. 1995. Using morphology towards better large-vocabulary speech recognition systems. In Proceedings of ICASSP-95, volume 1, pages 445–448. [↗](https://doi.org/10.5445/ir/1000166587)
5. J.A. Haywood and H.M. Nahmad. 1965. A New Arabic Grammar of the Written Language. Lund Humphries, Burlington, VT. [find](https://scholar.google.com/scholar?q=J%2EA%2E+Haywood+and+H%2EM%2E+Nahmad%2E+1965%2E+A+New+Arabic+Grammar+of+the+Written+Language%2E+Lund+Humphries%2C+Burlington%2C+VT%2E)
6. Teemu Hirsimäki, Mathias Creutz, Vesa Siivola, Mikko Kurimo, Sami Virpioja, and Janne Pylkkönen. 2006. Unlimited vocabulary speech recognition with morph language models applied to Finnish. Computer Speech and Language, 20:515–541. [↗](https://doi.org/10.1016/j.csl.2005.07.002)
7. F. Jelinek, B. Merialdo, S. Roukos, and M. Strauss. 1991. A dynamic language model for speech recognition. In Proc. Wkshp on Speech and Natural Language, pages 293–295, Pacific Grove, California. ACL. [find](https://scholar.google.com/scholar?q=F%2E+Jelinek%2C+B%2E+Merialdo%2C+S%2E+Roukos%2C+and+M%2E+Strauss%2E+1991%2E+A+dynamic+language+model+for+speech+recognition%2E+In+Proc%2E+Wkshp+on+Speech+and+Natural+Language%2C+pages+293%E2%80%93295%2C+Pacific+Grove%2C+California%2E+ACL%2E)
8. Katrin Kirchhoff, Dimitra Vergyri, Kevin Duh, Jeff Bilmes, and Andreas Stolcke. 2006. Morphology-based language modeling for conversational Arabic speech recognition. Computer Speech and Language, 20(4):589–608. [↗](https://doi.org/10.1016/j.csl.2005.10.001)
9. Junbo Kong and David Graff. 2005. TDT4 multilingual broadcast news speech corpus. [↗](https://doi.org/10.35111/90ef-0a97)
10. Oh-Wook Kwon. 2000. Performance of LVCSR with morpheme-based and syllable-based recognition units. In Proceedings of ICASSP ’00, volume 3, pages 1567– 1570. [find](https://scholar.google.com/scholar?q=Oh%2DWook+Kwon%2E+2000%2E+Performance+of+LVCSR+with+morpheme%2Dbased+and+syllable%2Dbased+recognition+units%2E+In+Proceedings+of+ICASSP+%E2%80%9900%2C+volume+3%2C+pages+1567%E2%80%93+1570%2E)
11. Andreas Stolcke. 2002. SRILM - an extensible language modeling toolkit. In Proc. Intl. Conf. Spoken Language Processing, Denver, Colorado. [find](https://scholar.google.com/scholar?q=Andreas+Stolcke%2E+2002%2E+SRILM+%2D+an+extensible+language+modeling+toolkit%2E+In+Proc%2E+Intl%2E+Conf%2E+Spoken+Language+Processing%2C+Denver%2C+Colorado%2E)
12. Wen Wang and Dimitra Vergyri. 2006. The use of word n-grams and parts of speech for hierarchical cluster language modeling. In Proceedings of ICASSP 2006, pages 1057–1060. [find](https://scholar.google.com/scholar?q=Wen+Wang+and+Dimitra+Vergyri%2E+2006%2E+The+use+of+word+n%2Dgrams+and+parts+of+speech+for+hierarchical+cluster+language+modeling%2E+In+Proceedings+of+ICASSP+2006%2C+pages+1057%E2%80%931060%2E)
13. Bing Xiang, Kham Nguyen, Long Nguyen, Richard Schwartz, and John Makhoul. 2006. Morphological decomposition for Arabic broadcast news transcription. In Proc. ICASSP 2006, pages 1089–1092. [find](https://scholar.google.com/scholar?q=Bing+Xiang%2C+Kham+Nguyen%2C+Long+Nguyen%2C+Richard+Schwartz%2C+and+John+Makhoul%2E+2006%2E+Morphological+decomposition+for+Arabic+broadcast+news+transcription%2E+In+Proc%2E+ICASSP+2006%2C+pages+1089%E2%80%931092%2E)

*Updated 1 November 2026*