📄 Arabic Language Modeling with Finite State Transducers

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

• I1. 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.
• I2. 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.
• I3. 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.
• I4. 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.
• I5. 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.