User:David Nemeskey/GSOC progress 2013

Tasks

XML format

See User:David_Nemeskey/CG_XML_brainstorming.

Rule applier

Rough execution flow:

1. Load the rules
   1. DELIMITERS must also be converted to an FST and saved.
   2. Rule organization:
      • separate files in a directory?
      • one file per section?
      • one big file (needs another "index" file then)
2. Read the input stream cohort by cohort
   • StreamReader class in fomacg_stream_reader.h
   • Read until a delimiter is found (see above)
3. Convert the cohorts from the Apertium stream format to fomacg's format
   • Converter in fomacg_converter.h
   • apertium_to_fomacg.foma
   • conversion from wchar_t to utf-8 char
4. Apply rules in the order of the sections they are defined in
5. Convert the cohorts back to the Apertium stream format

Compiler

Code

• Read the fomacg code and understand what it does.
• Add comments do a little refactoring (e.g. separate function for creating @*word@* FSTs).
• Check and test if it works on all grammars, fix it if it isn't.

Development

1. DELIMITERS must also be converted to an FST and saved.
   • I have run into a foma bug, which also corrupted the output of all rules that contained lemma tags. I have patched the code on my side and opened a bug report (two, actually).
2. fomacg treats all tags as symbols. Usually this is OK, but for lemmas, it may not be optimal
   1. it blows up the number of symbols (if not the transducer) => turns out the transducer is smaller this way;
   2. might be slower to parse? Or faster => faster, if we use exploded strings, fomacg_proc becomes about 33% slower.
3. If one tag is a postfix of another, and the longer tag is not mentioned in the rule, fomacg might trigger the wrong rule, believing that it sees the shorter tag. E.g. if there is a "predet " and a "det " tag, and the rule is SELECT (det), it will also select predets as well. This is because in fomacg, the symbol that corresponds to a tag is its name plus a space; in other words, only the right boundary of a symbol is checked.
   1. Change the symbols from "tag " to "<tag> " to ensure the "postfix property", except for word forms and lemmas, which are already enclosed in quotes.
   2. Keep as much of Apertium's format as possible?
4. Insert ">>>" and "<<<" to before and after the sentence, respectively.
5. Make the rules fail-fast?

Speed problems

This first version of fomacg_proc, where rules are separate FSTs applied in order, has some speed issues. With the 40-rule CG-2 subset of my Hungarian grammar, it disambiguates a 13760-token test corpus (the rasskaz sentences 32x concatenated) in 6.3 seconds. Under the same conditions, cg-proc needs 0.3 seconds.

Simple ideas to speed it up:

1. do not use symbols for tags, etc (see above): execution time grows by 33%
2. compose nets on the same priority level: the FSTs become too big too fast -- on some simpler rules:
   1. rule: 3.5 kB. 44 states, 176 arcs
   2. rules: 446.0 kB. 1965 states, 28482 arcs
   3. rules: 4.9 MB. 17303 states, 320664 arcs
   4. rules: 61.5 MB. 163945 states, 4029156 arcs
3. union nets on the same priority level: the nets don't grow as fast as with compose, but still not useable:
   1. rule: 3.5 kB. 44 states, 176 arcs
   2. rules: 47.3 kB. 202 states, 2957 arcs
   3. rules: 238.8 kB. 856 states, 15208 arcs
   4. rules: 1.3 MB. 3988 states, 82261 arcs
   5. rules: 7.2 MB. 20296 states, 471188 arcs
   6. rules: 53.5 MB. 131639 states, 3504119 arcs

Clever ideas:

1. Use fail-fast FSTs. The idea was that these could speed up the computation because unapplicable rules don't have to copy the whole string over, they can return on the first error. I have tried to augment the ConstrainR and ConstrainS pattern in two ways:
   1. compose $"$A$ " at the end: worked, but the rule FSTs became larger and slower;
   2. instead of deleting $1$ and #1# from the string, I composed ["$1$ " => _ MarkedReading & NotMarkedReading] & $"$1$ " at the beginning. This didn't work, the rules only recognized cohorts, not sentences. And if I change the rule to ?* rule ?*, it becomes non-deterministic.
   3. Maybe this idea wasn't that clever after all -- the rule might have to read the whole sentence anyway...
2. Do not pass the sentence to the rule, just the current word (+ the left & right contexts).
   1. Unfortunately, this does not mitigate the need of reading the sentence repeatedly over-and-over, because of right contexts: a rule can be enabled by another that changes something in a later word.
3. Instead of applying the rules to the sentence string, convert the string to an (linear) FSA and compose the rules with it.
   1. Unfortunately, this is even slower: on one of my machines, instead of 6.5 seconds, it takes 47 (the other one: 4s vs 41s)! Why? It could be because:
      1. It is difficult to decide if a rule "worked", so currently I intersect the old and the resulting sentence. TODO This could be remedied by modifying the rules so that they delete the #X# readings.
      2. All fsm_ functions are destructive. However, about half of the time (most, if the TODO above is implemented), I needed the old transducer so I had to fsm_copy it.
      3. Why indeed? According to callgrind:
         1. 28.52% fomacg_to_fsa == fsm_concat
         2. 23.01% fsm_intersect
         3. 43.19% fsm_compose
      4. If we go deeper:
         1. 24.01% fsm_merge_sigma (called by all three)
         2. 24.01% fsm_minimize (called 82.87% of the time by fsm_concat, and 16.05% by fsm_intersect)
      5. What can we take home from this?
         1. About 50% of the time is spent in fsm_compose, which we cannot avoid. It might be possible, however, to write a custom <fsm_compose> that exploits the fact that one of its input is not a general FST, but a linear FSA.
         2. fsm_intersect takes about 50% less than fsm_compose (both are called once per rule), so trying the intersection-based method looks promising (though the sentence won't be linear in that case)
         3. The overhead of fsm_minimize could be avoided entirely by using a custom fsm_concat to construct the sentence. It is a linear automaton, so no minimisation is needed.
   2. Sometimes apply down'ing a rule works, but composing it to the sentence FSA doesn't. This was a bug in fomacg.
   3. Currently we are at 33 seconds
      1. fsm_concat_custom() does not call fsm_minimize().
4. TODO Index rules by their required tags (word-form, target, C conditions, etc.), and skip those that cannot possible be activated by the sentence.

TODO?'s

1. cg-comp is not so strict as fomacg about the position part in contextual tests, e.g. it accepts 1*, not just *1. Loosen up fomacg?

Research

• Decrease the number of rules applied (see in the proposal).
• When and how can rules be merged?

Miscellaneous / Extra

Hungarian CG grammar

Write a simple CG grammar for Hungarian, somewhere around 50-150 rules.

• Read Pasi Tapnainen's The Constraint Grammar Parser CG-2.
• Read the contents of cg_material.zip.
• Install Apertium, VISL CG3 and a language pair (cy-en)
• Study the CG grammar of an Apertium language.
• Write a Hungarian grammar that covers the sentences in this sample file
  • The tags will be based on those in KR-code. See the next task.
• TODOs:
  • add a sentence to the rasskaz file for the "az a" construct.
  • prevb disambiguation
• The file is here.

Hunmorph converter

Write a converter from ocamorph's output to Apertium's format.

• Again, use the sentences in this sample file as reference.
• While a C-based converter would definitely be possible, I opted for a foma-based (xfst -- lexc?) implementation, so that this task also serves for practice.
• TODOs:
  • some analyses are repeated in the output: fix them! -- Not a real fix, because the problem wasn't in the script, but in ocamorph, but I wrote a python script that discards repeated analyses.
  • hunmorph_to_apertium.foma does not handle compounds (+)
  • two-phase conversion (handle special words first, then the general part)
  • a few non-general conversions:
    • "mikor<CONJ>" => <cnjadv>, "mikor<ADV>" => <itg>
    • "hova" => <itg>
    • "így<CONJ>" => <cnjadv>
    • "ekkor<ADV>" => <cnjadv>?
    • "aztán<CONJ>" => <cnjadv>
• Apparently a pure lexc/foma based implementation wasn't possible (at least with the one line -- one word output format I decided ask from hunmorph). The reason is that the tagset of hunmorph and Apertium does not match exactly, and therefore I needed to add exceptional rules for certain words and lexical categories. However, flookup returns all possible analyses, so in this case it returned both the exceptional and the regular translation. The current solution consists of four files:
  • kr_to_apertium_spec.lexc contains the words / lexical categories that need special treatment (vbser, prns, "ez"/"az", etc.)
  • kr_to_apertium.lexc contains the rest of the categories, i.e. whose the translation was straightforward
  • kr_to_apertium.foma is a simple foma script that writes the previous two into the binary file kr_to_apertium.fst
  • hunmorph_to_apertium.cpp loads the two FSTs from the binary file and applies them to the readings. First it tries to parse the reading with the _spec FST; if it fails, it reverts back to the general one. This mechanism ensures that all readings get only one translation, and it is also the correct one.

ATT -> lttoolbox compiler

Write an ATT FST format reading for lttoolbox. A useful practice for moving from foma to lttoolbox. Since lttoolbox lacks some of the functionaty needed, the compiler will most likely stay in foma, but lttoolbox might work as the runtime component.

• ATT format
• "<spectie> the ATT->lttoolbox thing should be a simple as : beer = t.insertSingleTransduction(alphabet(L'e',L'e'), beer);"
  • The actual implementation turned out to be a little more difficult. Anyway, the code is here.
  • The transducer we used for testing, kaz.att, didn't work with lt-proc, so Fran told me to create two transducers instead of one: one for words (main) and one for punctuation (final).