View source for User:David Nemeskey/GSOC progress 2013

== Tasks ==

=== XML format ===

See [[User:David_Nemeskey/CG_XML_brainstorming]].

=== Rule applier ===

Rough execution flow:

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

=== Compiler ===

==== Code ====

* Read the [https://apertium.svn.sourceforge.net/svnroot/apertium/branches/fomacg/ fomacg] code<ref>Hulden, Mans. 2011. Constraint Grammar parsing with left and right sequential finite transducers. In: Proceedings of the 9th International Workshop on Finite State Methods and Natural Language Processing, pages 39--47.</ref> 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 ====

# ''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 [http://code.google.com/p/foma/issues/detail?id=49 bug report] ([http://code.google.com/p/foma/issues/detail?id=50 two, actually]).''
# '' ''fomacg'' treats all tags as symbols. Usually this is OK, but for lemmas, it may not be optimal''
## ''it blows up the number of symbols (if not the transducer) => turns out the transducer is smaller this way;''
## ''might be slower to parse? Or faster => faster, if we use exploded strings, ''fomacg_proc'' becomes about 33% slower.''
# ''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 <code>"predet "</code> and a <code>"det "</code> tag, and the rule is <code>SELECT (det)</code>, it will also select <code>predet</code>s 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.''
## ''Change the symbols from <code>"tag "</code> to <code>"<tag> "</code> to ensure the "postfix property", except for word forms and lemmas, which are already enclosed in quotes.''
## Keep as much of Apertium's format as possible?
# ''Insert ">>>" and "<<<" to before and after the sentence, respectively.''
# 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.4 seconds. Under the same conditions, ''cg-proc'' needs 0.3 seconds.

===== Speed measurements (see below for details) summary =====
# <code>apply_down</code>
## original rules, <code>strcmp</code>-based application check: 6.4 seconds
## deleteX rules, <code>strlen</code>-based application check: '''5.9''' seconds
# <code>fsm_compose</code>
## simple rules, <code>fsm_intersect</code>-based application check: 45 seconds
## deleteX rules, <code>fsa->statecount</code>-based application check: '''28.3''' seconds

===== Simple ideas to speed it up =====
# do not use symbols for tags, etc (see above): ''execution time '''grows''' by 33%''
# <code>compose net</code>s on the same priority level: ''the FSTs become too big too fast -- on some simpler rules:''
## rule:  3.5 kB. 44 states, 176 arcs
## rules: 446.0 kB. 1965 states, 28482 arcs
## rules: 4.9 MB. 17303 states, 320664 arcs
## rules: 61.5 MB. 163945 states, 4029156 arcs
# <code>union net</code>s on the same priority level: ''the nets don't grow as fast as with <code>compose</code>, but still not useable:''
## rule:  3.5 kB. 44 states, 176 arcs
## rules: 47.3 kB. 202 states, 2957 arcs
## rules: 238.8 kB. 856 states, 15208 arcs
## rules: 1.3 MB. 3988 states, 82261 arcs
## rules: 7.2 MB. 20296 states, 471188 arcs
## rules: 53.5 MB. 131639 states, 3504119 arcs

===== Clever ideas =====
# 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 <code>ConstrainR</code> and <code>ConstrainS</code> pattern in two ways:
## compose <code>$"$A$ "</code> at the end: worked, but the rule FSTs became larger and slower;
## instead of deleting <code>$1$</code> and <code>#1#</code> from the string, I composed <code>["$1$ " => _ MarkedReading & NotMarkedReading] & $"$1$ "</code> at the beginning. This didn't work, the rules only recognized cohorts, not sentences. And if I change the rule to <code>?* rule ?*</code>, it becomes non-deterministic.
## Maybe this idea wasn't that clever after all -- the rule might have to read the whole sentence anyway...
# Do not pass the sentence to the rule, just the current word (+ the left & right contexts).
## 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.
# Instead of applying the rules to the sentence string, convert the string to an (linear) FSA and compose the rules with it. 
## ''Unfortunately, this is even slower: on one of my machines, instead of 6.5 seconds, it takes 47! Why? It could be because:''
### All <code>fsm_</code> 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 <code>fsm_copy</code> it.
### Why indeed? According to callgrind ('''note: the numbers are not entirely accurate, because there was a bug in the program when I measured them. <code>fomacg_to_fsa</code> could be around 13%'''):
#### 28.52% <code>fomacg_to_fsa</code> == <code>fsm_concat</code>
#### 23.01% <code>fsm_intersect</code>
#### 43.19% <code>fsm_compose</code>
### If we go deeper:
#### 24.01% <code>fsm_merge_sigma</code> (called by all three)
#### 24.01% <code>fsm_minimize</code> (called 82.87% of the time by <code>fsm_concat</code>, and 16.05% by <code>fsm_intersect</code>)
### What can we take home from this?
#### About 50% of the time is spent in <code>fsm_compose</code>, 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.
#### <code>fsm_intersect</code> takes about 50% less than fsm_compose</code> (both are called once per rule), so trying the intersection-based method looks promising (though the sentence won't be linear in that case)
#### ''The overhead of <code>fsm_minimize</code> could be avoided entirely by using a custom <code>fsm_concat</code> to construct the sentence. It is a linear automaton, so no minimisation is needed.''
## ''Sometimes ''apply down'''ing a rule works, but composing it to the sentence FSA doesn't. This was a bug in fomacg.''
## ''Currently we are at 28.3 seconds''
### ''<code>fsm_concat_custom()</code> does not call <code>fsm_minimize()</code>.''
### ''We use rules that delete the <tt>#X#</tt> readings.''
# ''(Mans's suggestion)'': Create an automaton for each rule that doesn't change anything, but only accepts the sentence the associated rule would change. "This automaton can be determinized and minimized and applied *much* faster than the corresponding transducer."
## If the automaton is just used to check the applicability of a single rule, execution time goes up to '''9 seconds'''. :(
### According to ''callgrind'', <code>apply_follow_next_arc</code> is called 1,358,508 times when we used only FTSs, and 2,589,103 times with the new method.
### This is especially interesting if we know that the total number of states in the rule FSTs is 3,467, while the total number of states in the rule FSAs is only 1,597. The total number of arcs in the FSAs also seem to be about half of that in the FSTs. So why?
## It could be possible to check the applicability of a number of rules with a single automaton. Researching this right now...
# '''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 ====

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

==== Research ====

* Decrease the number of rules applied (see [[User:David_Nemeskey/GSOC_proposal_2013#Detailed work plan|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 [https://apertium.svn.sourceforge.net/svnroot/apertium/incubator/apertium-hun-eng/texts/rasskaz.hun.txt this sample file]''
** ''The tags will be based on those in KR-code<ref>András Kornai, Péter Rebrus, Péter Vajda, Péter Halácsy, András Rung, Viktor Trón. 2004. Általános célú morfológiai elemző kimeneti formalizmusa (The output formalism of a general-purpose morphological analyzer). In: Proceedings of the 2nd Hungarian Computational Linguistics Conference.</ref>. See the [[#Hunmorph converter|next task]].''
* TODOs:
** ''add a sentence to the rasskaz file for the "az a" construct.''
** ''prevb disambiguation''
* ''The file is [https://svn.code.sf.net/p/apertium/svn/incubator/apertium-hun-eng/dev/hun.rlx here].''

==== Hunmorph converter ====

''Write a converter from [[Hunmorph|ocamorph]]'s output to Apertium's format.''

* ''Again, use the sentences in [https://apertium.svn.sourceforge.net/svnroot/apertium/incubator/apertium-hun-eng/texts/rasskaz.hun.txt 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, ''<code>flookup</code>'' returns all possible analyses, so in this case it returned both the exceptional and the regular translation. The current solution consists of four files:''
** ''[https://svn.code.sf.net/p/apertium/svn/incubator/apertium-hun-eng/dev/kr_to_apertium_spec.lexc kr_to_apertium_spec.lexc] contains the words / lexical categories that need special treatment (''<code>vbser</code>'', ''<code>prn</code>''s, "''ez''"/"''az''", etc.)''
** ''[https://svn.code.sf.net/p/apertium/svn/incubator/apertium-hun-eng/dev/kr_to_apertium.lexc kr_to_apertium.lexc] contains the rest of the categories, i.e. whose the translation was straightforward''
** ''[https://svn.code.sf.net/p/apertium/svn/incubator/apertium-hun-eng/dev/kr_to_apertium.foma kr_to_apertium.foma] is a simple foma script that writes the previous two into the binary file'' <code>kr_to_apertium.fst</code>
** ''[https://svn.code.sf.net/p/apertium/svn/incubator/apertium-hun-eng/dev/hunmorph_to_apertium.cpp 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 ''<code>_spec</code>'' 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 [https://svn.code.sf.net/p/apertium/svn/incubator/apertium-hun-eng/dev/att_to_ltt/att_to_ltt.cpp here].
** ''The transducer we used for testing, [https://svn.code.sf.net/p/apertium/svn/incubator/apertium-hun-eng/dev/att_to_ltt/kaz.att kaz.att], didn't work with <tt>lt-proc</tt>, so Fran told me to create two transducers instead of one: one for words ('''main''') and one for punctuation ('''final''').''

== References ==

<references/>