Overview

• Ethiopian Semitic verb morphology
• Finite state morphology
• Finite state approaches to Semitic morphology
• Weighted finite state automata
• FSTs weighted with feature structures
• Weighted FSTs for Ethiopian Semitic verb morphology
• An application

Motivation

• Develop computational tools for under-resourced languages: Ethiopia, Guatemala
• Ultimately, practical applications
  • Dictionary and ontology creation
  • Computer-assisted language instruction
  • Computer-assisted translation
• For Semitic languages, morphology a major roadblock on the way to other applications

Ethiopian Semitic: distribution

• ~32 million speakers in Ethiopia and Eritrea

  

Ethiopian Semitic: languages

Morphology of Ethiopian Semitic verbs: stems

Root-template morphology (interdigitation, intercalation)

Notation

• Gemination: _
• Ejective consonants: ṭ, ṣ, q, ċ, ṗ
• Laryngeal consonants (Tigrinya, Tigre): h, ', ħ, \`
• Vowels: ə, u, i, a, e, ɨ, o

Morphology of Ethiopian Semitic verbs: stems: roots

• 3, 4, and 5 consonants
  • Presence of semivowels and laryngeal root consonants leads to apparent 2-consonant or 1-consonant roots in Southern languages, e.g., Am stems sam, bel_a, məš_ə
• Gemination lexical, as well as grammatical, distinguishing small number of roots, e.g., Am ṭbq 'be tight' vs. ṭb_q 'wait'
• Some roots contain vowels (a in all languages, other vowels in some Southern languages), e.g., Am gagr 'bake', mark 'bless', glamṭ 'glare'

Morphology of Ethiopian Semitic verbs: stems: templates

• Each template depends on tense-aspect-mood, voice, and several further aspectual categories
• Four TAM categories: perfective, imperfective, jussive-imperative, gerundive
• In each TAM category, a maximum of nine (or eight in some languages) combinations of voice and aspect categories, yielding a total of 36 templates
• Voice: passive/reciprocal, transitive, (causative)
• Aspect: "iterative", "reciprocal"

Morphology of Ethiopian Semitic verbs: stems: templates:

• Combinations

  	Voice	Aspect
  Simple	simple	simple
  Passive-reflexive	passive	simple
  Transitive	transitive	simple
  (Causative)	causative	simple
  Frequentative	simple	iterative
  Reciprocal 1	passive	reciprocal
  Causative reciprocal 1	transitive	reciprocal
  Reciprocal 2	passive	iterative
  Causative reciprocal 2	transitive	iterative

• Examples: stems for Am verb wrs 'inherit'
  

Morphology of Ethiopian Semitic verbs: affixes

• Subject agreement, e.g., Ti səbirǝ 'I broke', səbirkɨn 'you (fem., pl.) broke'; 'ɨsəb_ɨr, 'I break', tɨsəbra 'you (fem., pl.) break'
• Object "agreement"
  • "Plain", e.g., Am səb_ərkut 'I broke him (it)'
  • Oblique: e.g., Am səb_ərkul_ət 'I broke (sth.) for him', Am səb_ərkub_ǝt 'I broke (sth.) on him (it), to his detriment'
• Polarity, e.g., Ti 'aytɨsəbran 'you (fem., pl.) don't break'
• Relativization, e.g., Am yəsəb_ərku 'which I broke, (I) who broke'
• Accusative case (some Southern languages, with relativized verb only), e.g., Am yəsəb_ərkutɨn 'which I broke (acc.)'
• Prepositional prefixes (with relativized verb only), e.g., ləm_isəbrəw 'for who(ever) breaks it'
• Conjunctive/adverbial prefixes and suffixes, e.g., Am ɨy_ətəsəb_ərə 'while he (it) is/was broken'; Ti 'ɨntəsəbirkɨy_o 'if you (fem., sg.) break him (it)'

Morphology of Ethiopian Semitic verbs: derivational idiomaticity

• Some roots fail to appear in the simple voice: Am/Ti qmṭ: təqəm_əṭǝ 'he sat' ("passive"), *qəm_əṭǝ
• The meanings of some derived forms are somewhat unpredictable: Am ngr: nəg_ərǝ 'he told', tənag_ərə 'he spoke' ("reciprocal")
• Should stems or roots be the lemmas?
• A root-based analyzer is still desirable when the stem or root lexicon is inadequate

Morphology of Ethiopian Semitic verbs: long-distance dependencies and ambiguity

• Long-distance dependencies

  

• Ambiguity
  • Morphological, e.g., Am atfəl_ɨgɨm 'you (mas., sg.) don't want', 'she doesn't want'
  • Orthographic: Geez script — fails to mark gemination and to distinguish bare consonant from consonant + ɨ, e.g., Am yɨbəlal_u 'they eat', yɨb_əl_al_u 'they are eaten' ይበላሉ

Morphology of Ethiopian Semitic verbs: a maximal example

Representing the structure of a verb

'abzəytɨr_axəbalun ↔ `[ (text(root)=text('rkb')), (text(sbj)=[-text(p1),-text(p2),+text(plr),+text(fem)]), (text(obj)=[-text(p1),-text(p2),-text(plr),-text(fem),+text(prep)]), (+text(neg)), (+text(rel)), (text(prep)=text('ab'-)), (text(suf_conj)=text(-'n')) ]`

Goals

• Analyzer and generator: invertible
• Should return multiple analyses/wordforms when there is ambiguity: non-deterministic
• No complete root lexicons available, so two versions
  • "Lexical": including a root lexicon
  • "Guesser": analyzer that can extract unknown roots

Finite state morphology

• Old-style phonology/morphology: context-sensitive, ordered, uni-directional rewrite rules
• Finite state techniques (Johnson; Kaplan & Kay; Koskenniemi) revolutionized computational morphology
• Two-level morphology related surface and lexical levels directly using an intersection of finite state transducers (FSTs)
• FSTs are invertible: generator is trivially derived from analyzer by reversing the input and output characters on the arcs

Finite state transducers

• Intersection only possible when strings have the same number of characters
• Composition of FSTs (Karttunen et al.)
  • `f_1: s_1 -> s_2`
    `f_2: s_2 -> s_3`
    `(f_1 text(.o.) f_2): s_1 -> s_3`
  • Given an ordered set of rules, the effective order is preserved in the composition of the rules
    

The components of a complete system

• Alternation rules
  Example: Am: insert y between i and a
  
• Morphotactics
  

Non-concatenative morphology

• Finite state morphology is biased to view
  • morphemes as sequences of characters
  • words as concatenations of morphemes
• Problems when morphemes are discontinuous and/or when morphemes are not concatenated to form words
  • Discontinuous morphemes (e.g., circumfixes)
  • Reduplication
  • Semitic root-template morphology

Examples to consider

• Am: imperfective stem, voice categories, CCC root

  simple	C1əC2C3
  passive/reflexive	C1_əC2_əC3
  transitive	aC1əC2C3
  causative	asC1əC2_C3

  q_əb_ər ↔ qbr+[ps]
• Ti: negative circumfixation

  yɨxɨ'ɨl	'he can'
  'ayyɨxɨ'ɨlɨn	'he can't'
  zəyyɨxɨ'ɨl	'(he) who can't'
  'ayyɨsɨ\`sɨ\`ulnan	'they don't dance for us'

Three types of finite state approaches to Semitic morphology

• Compile a high-level description of root-template patterns into separate rules for each root-template combination, which are then compiled into FSTs (Beesley & Karttunen)
  • Basis of work on Amharic morphology by Saba and Girma
  • Compile-time solution, no savings in duplicated states at run time
• Allot separate tapes to two or more grammatical/lexical tiers (Kiraz)
• Add finite additional memory to keep track of dependencies (Beesley; Cohen-Sygal & Wintner)

Finite state approaches to Semitic morphology: simple FSTs

Finite state approaches to Semitic morphology: multiple tapes (Kiraz)

• Root-template morphology: a single surface tape, separate lexical tapes for root and template
  
  

  q_əb_ər ↔	qbr
  	1_ə2_ə3

• The tapes must be aligned; when dependencies span variable distances, there must be separate paths for each intermediate distance
• States also seem to multiply with interacting dependencies (ES negative suffix depends on negative prefix and on relative prefix)

Finite state approaches to Semitic morphology: additional memory

• Finite-state registered transducers (Cohen-Sygal and Wintner)
• Registers on arcs; read and write operations
  
  

  q_əb_ər →	qbr
  	ps

• But how do you invert the analyzer to create a geneator?

Weighted finite state automata (Mohri)

• Motivation
  • For some applications, particular transitions are more or less preferred
  • Paths through an FSA/FST need to be ranked
• Semiring
  • Algebraic structure with “addition” and “multiplication” operations, identity elements for each; addition identity element is annihilator for multiplication; multiplication distributes over addition
  • Example: probabilities ("multiplication" is multiplication, "addition" is addition)
• Transitions are weighted with elements of semiring
• Most of the properties of FSTs hold
• Cumulative weight maintained for each path through the FSA/FST by “multiplying” the weights on the transitions
• If there are multiple paths, an overall weight is assigned by "adding" the weights for each path
• 

FSTs weighted with feature structures (Amtrup)

• Feature structures (FSs): sets of attribute-value pairs
• Operation on FSs: unification
• Sets of FSs constitute a semiring: "multiplication" is pairwise unification; "addition" is set union
• FSTs weighted with FS sets
  • Traversing path yields FS set in addition to output string, the result of the repeated unification of FS sets on the transitions in the network, starting with an initial FS set
  • Path fails not only if the input character fails to match the input character on the arc, but also if the accumulated FS set fails to unify with the FS set on the arc
• Advantages
  • FSTs output FSs
  • Long-distance dependencies handled efficiently (and without reference to distance between dependent morphemes)

Weighted FSTs for ES verb morphology: affix dependencies

• Ti negation
  
• Examples
  • fələṭə [-neg;-rel]
  • 'ayfələṭən [+neg;-rel]
  • zɨfələṭə [-neg;+rel]
  • zəyfələṭə [+neg;+rel]
  • 'ayfələṭə fails
  • zəyfələṭən succeeds with a different value for -n

Weighted FSTs for ES verb morphology: stem

• Voice for imperfective Am CCC verbs:
  
• Examples
  • ṭəbq [vc=smp]
  • aṭəbq [vc=tr]
  • asṭəb_q [vc=cs]
  • ṭ_eb_əq [vc=ps]
  • asṭəbq, ṭ_eb_q, aṭəb_q, ṭebəq fail

Ethiopian Semitic verb morphology: architecture

How big are they?

• Amharic
  • Verb: lexical: 58,903 states, 136,370 arcs; guesser: 13,698 states, 118,103 arcs
  • Noun: lexical: 130,406 states, 264,149 arcs; guesser (verbal nouns only): 4,520 states, 36,028 arcs
• Tigrinya
  • Verb: lexical: 52,883 states, 129,291 arcs; guesser: 22,175 states, 132,808 arcs

Coverage

• Iterative refining of rules based on performance
• Tigrinya guesser FST applied to 400 randomly selected Tigrinya words
  • 329 words: unambiguously verbs
  • 308 correctly analyzed
  • 21 errors: irregularities or orthographic/phological variants not yet built into FST
  • 50 words: not verbs, 13 words: verbs with typogrphical errors, 8 words: inidentifiable; program responded by rejecting word or analyzing it on the basis of a non-existent root
• Tigrinya generator applied to 272 representative combinations of roots and grammatical features: all generated correctly
• Lexical analyzer FSTs make few commission errors (roughly 1/200 for Amharic), some ommission errors for irregularities and obscure combinations of root class and grammatical features (fixable)

Idiomaticity

• Adding constraints to the root lexicon

  qmṭ        [vc=ps];[vc=tr];[vc=cs]
  

  This prevents forms of qmṭ in the simple voice (for example, qəm_əṭə) from being produced or generated.

An application: building a root lexicon

• Incomplete root lexicons
• 397,352 Amharic wordforms extracted by web crawler (Biniam Gebremichael)
• Words analyzed by Amharic FSTs
  1. Lexical verb FST (146,866 words analyzed)
  2. Noun FST (76,224 words analyzed)
  3. Guesser verb FST (37,229 words analyzed)
  4. Guesser verbal noun FST (12,518 words analyzed)
• 55,072 potential new roots found by guesser FSTs
• Reduced by filtering out candidate roots
  • belonging to impossible or very unlikely patterns
  • occurring below a given frequency
  • occurring with few templates
• Of the remaining 96 candidate roots
  • 64: genuine roots (including orthographic variants of roots in lexicon)
  • 16: non-existent roots resulting from ambiguity
  • 13: non-existent roots resulting from FST errors (correctable on next pass)
  • 3: non-existent roots resulting from filtering errors

Conclusions

• Finite state transducers with feature structure weights
  • yield feature structures as output (of analysis)
  • avoid wasteful repetition of duplicate states and arcs
  • permit the development of "guesser" analyzers when the root lexicon is incomplete
  • allow the straightforward addition of features to the lexicon to handle exceptional cases
• Current state of verb analyzers handles most Amharic and Tigrinya verbs with familiar roots and hypothesizes roots for most verbs with unfamiliar roots
• Outstanding issues
  • Reduplication
  • Development of a user-friendly interface for linguistically sophisticated but computationally unsophisticated native speakers