Morphological Parsing Explained

Parsing/Generation vs. Recognition

• Machines can recognize strings in a language.
• Recognition isn't always sufficient.
• Parsing assigns a structure to a string. An example is converting the surface form "ate" to the parsed form "eat +V +PAST".
• Production/generation produces a surface form from a structure, like converting "eat +V +PAST" to "ate".

Morphological Parsing

• This process finds constituent morphemes in a word.
• Recognizing "foxes" involves breaking it into "fox" and "-es".
• Examples of morphological parsing include labeling morphemes with category labels, where "cats" becomes "cat +N +PL".
• Morphological parsing is useful in information retrieval, machine translation, and spelling checking.

Finite-State Morphological Parsing

• It aims to find the lexical form of a word from its surface form.
• Ambiguity is possible, where a word can have multiple lexical-level representations.

Building a Morphological Parser

• A lexicon provides a list of stems and affixes with basic information.
• Morphotactics models morpheme order, determining how morpheme classes can combine within a word.
• Orthographic rules model spelling changes during morpheme combination, such as changing "city + -s" to "cities", which is the y→ ie rule.
• Words consist of stems and affixes and may be prefixes, suffixes, circumfixes or infixes.

Morphology and FSAs

• FSAs are used to capture facts about morphology.
• FSAs must accept strings in the language and reject those that are not.
• It avoids listing every form of every word in the language which would be inefficient and sometimes impossible.

Simple Rules

• Regular singular nouns are acceptable as they are.
• Regular plural nouns usually have an "-s" at the end.
• Irregular nouns are accepted as they are.

Finite-State Morphological Parsing: Lexicon and Morphotactics

• A Lexicon serves as a repository for words.
• Computational lexicons comprise lists of stems and affixes, along with a representation of the morphotactics.
• The most common way of modeling morphotactics is the finite-state automaton.

Plugging in Words

• Replace class names such as "reg-noun" with FSAs to recognize all words within that class.
• The resulting FSA defines the level of the individual letter.
• FSAs can then solve the problem of morphological recognition: determining if an input string forms a valid English word.

Notes on FSA Use

• The FSA only confirms validity without giving the lexical representation, and also doesn't address orthographic issues.
• Note: Sometimes an FSA can accept a wrong word (foxs).

Generalizations

• Sets of related words can be built with derivational morphology.
• ADJ + -ity → NOUN.
• ADJ or NOUN + -ize → VERB.

Morphological Parsing with FST

• FSTs produce "cat +N +PL" from the input "cats."
• Two-level morphology represents a word as a correspondence between a lexical level (simple morpheme concatenation) and the surface level (actual spelling).
• Mapping rules that maps letter sequences like "cats" on the surface level into morpheme and features sequence like "cat +N +PL" on the lexical level.

Morphological Parsing with FST (Cont.)

• The mapping between levels uses a finite-state transducer (FST).
• A transducer maps one set of symbols to another.
• An FST is a two-tape automaton that recognizes or generates pairs of strings with a more general function than an FSA.
• An FSA defines a formal language, while an FST defines a relation between sets of strings.
• Viewing an FST: A machine reads one string and generates another.

Finite State Transducers (FSTs)

• A simple explanation: it is the addition of another tape or extra symbols to the transitions.
• One tape is used to read "cats" while the other writes "cat +N +PL".

Finite State Transducers (Cont.)

• A-finite state transducer is defined by the tuple (∑i, ∑o, Q, qo, F, ∆):
• Σi is the input alphabet.
• Σo is the output alphabet.
• Q is a finite set of states.
• q0 is the start state, where q0 ∈ Q.
• F is the set of accepting states, where F ⊆ Q.
• Δ is a relation (Δ : Q × Σi → Q × Σo).

Regular Relations

• A regular language is defined as a set of strings.
• Regular relation: a set of pairs of strings, e.g., {a:1, b:2, c:2}.
• An example has an input alphabet Σi = {a, b, c} and an output alphabet Σo = {1, 2}.

Transitions

• c:c means read a c on one tape and write a c on the other.
• +N:ɛ means read a +N symbol on one tape and write nothing on the other.
• +PL:s means read +PL and write an s on the other.

Typical Uses

• Read from one tape using the first symbol on the machine transitions
• Write to the second tape using the other symbols on the transitions.

Example

• Find FST that takes the lexical form: box +N +PL and produces the intermediate form: box^s#.

Spelling Rules and FSTs.

• Consonant doubling doubles the 1-letter consonant before -ing/-ed. e.g. beg/begging.
• E deletion removes the silent e before -ing and -ed. e.g. make/making.
• E insertion is where e is added after -s , -z, -x, -ch, -sh, before -s. e.g. watch/watches.
• Y replacement is where -y changes to -ie before -s, -i before -ed. e.g. try/tries.
• K insertion is where Verb ending with vowel + -c add -k. e.g. panic/panicked.

Multi-Tape Machines

• They add more tapes, using one tape machine's output as the next's input, to handle complications.
• They also handle irregular spelling changes via intermediate tapes with intermediate symbols.
• This is called Generativity.
• Nothing is privileged about the directions
• Writing is possible from one and reading from the other or vice-versa.
• Generation is one way, whereas analysis (or parsing) is the other.

Multi-Level Tape Machines

• One machine transduces between the lexical and intermediate level.
• Another machine handles spelling changes to the surface tape.