View source for Transducers as flag diacritics and their topology learning

This proposal stems from (1) the suggested project by Jimmy O'Regan in an irc conversation, as a better an desired alternative to their [http://wiki.apertium.org/wiki/Ideas_for_Google_Summer_of_Code listed idea] for GSoC2011 '''Flag diacritics in lttoolbox''' using instead second level transducers, and (2) from my own expanded proposal to study and use topology-learned transducers to be placed as such 2nd level transducers.


== Short Description ==

The implementation of a module to handle languages with infix inflection (and possibly other forms), to stop, according to defined constraints, useless and invalid continuation computations as flag diacritics do, for example in the HFST platform, but using instead the novel approach of a second/n level. This is approach is desired as transducers may provide greater power, expressiveness, and flexibility.



== Description ==

The HFST platform uses flag diacritics to remove and stop the computation of illegal compounds, thus providing a better handling of languages with infix inflection. The Apertium project aims for this appropriate handling for such languages and, [http://wiki.apertium.org/wiki/Ideas_for_Google_Summer_of_Code/Flag_diacritics_in_lttoolbox as documented in their original idea], planned to used flag diacritics as well.

Jimmy O'Regan suggest, however, that a better approach would be to use a second level of cascaded transducers to process the same continuations and, according to the transducers' decision, either reject the input, prune the states of the otherwise continued computation, and finally emit an epsilon symbol as flag diacritics defined by constraint rules do, or process the input and output the transducer's computation.

The pruning of states module is already implemented in lttoolbox-java by Jacob Nordfalk, therefore my work will consist of the (1) design and implementation of such second-level, by nature cascaded n-level if considered sensible, layer of transducers, (2) the consequent changes in the FST compiling processing code and the pipeline to this other level of transducers, (3) with a limited range, verify and validate such implementation with a sample language, (4) the documentation of such development.


Then, and more exclusively for my master thesis, with a higher research and scientific scope, I propose to study topology transducer learning to construct such n-level transducers, working with some learning corpora, and mostly using the OSTIA state-merging algorithm.


The programming language to use will be mostly Java, using C++ if required.


== Contribution ==

* The implementation of a module for the flexible handling of languages with infix inflection, and possibly other types, that makes possible to avoid the possibly infinite definition of not regular rules in a dictionary to work with more complex forms of inflection.
* The novelty, as far as I know, of the use of transducers to tackle such a problem.
* Altogether, a better support for languages with more complex forms of inflection.


== Work Plan: Timeline == 

I mostly consider here the exact and specific work for the GSoC project, not the thesis's. The following is an estimation:


* '''Community Bonding Period: April 25 - May 23''': 
* know well Apertium's project and internals; get to know the community; know work & code standards; review C++; study Apertium's architecture and code
* study the lttoolbox-java
* study problem to solve; study flag diacritics approach; design plan solution for the problem


* '''Start'''
* Week 1-3: code implementation; parallel testing & documentation
* Week 4: code implementation; start of more formal testing
* '''Deliverable #1''': module ready for the lttoolbox-java & documentation


* '''Verification on target language'''
* Week 5: apply module to some specific language and validate correctness
* '''Deliverable #2''': positive formal verification results


* '''Topology Learning'''
* Week 6: research state-of-the-art methods and algorithms; design solution; ultimate corpus for which to apply the learning method
* Week 7-10: implement, review, test, and document the topology learning algorithm
* Week 11: verify algorithm
* '''Deliverable #3''': topology learning algorithm module ready & documentation


* '''Set & Run'''
* Week 12: (1) Deliver transducer/flag diacritics module into official program; (2) deliver topology learning module into official program


* '''Project Completed: Deliverable #4''': verified & delivered code & documentation



== Original Conversation with Jimmy O'Regan ==

  
  * [16: 04] <jimregan> Jacob and I designed an alternative to flag
  diacritics on the back of some paper plates last year
  * [16:04]  <jimregan> using a second transducer
  * [16:04]  <jimregan> (the original motivation behind flag diacritics -
  which are an ugly hack - was to avoid using a second transducer)
  * [16:05]  <jimregan> we use a fairly large number of transducers, in
  almost every phase of the translation pipeline
  * [16:05]  <jimregan> so we thought it wouldn't be unreasonable to have
  a second transducer to use in state pruning, rather than just
  balancing special symbols
  * [16:07]  <jimregan> the second transducer would basically take the
  same form as translation rules in apertium-transfer, but with the
  ability to fully or partially lexicalise (possibly based on a subset
  of regexes)
  * [16:07]  <jimregan> if the initial analysis involves a continuation,
  pass it to the second for validation
  * [16:07]  <jmcejuela> aha
  * [16:07]  <jimregan> prune it if it doesn't match
  * [16:08]  <jimregan> take the symbols of the second transduction for
  output if it does
  * [16:08]  <jimregan> Jacob was pretty pationate about implementing it
  himself, but I think he'd be interested in mentoring it
  * [16:10]  <jimregan> I just remembered how to summarise it: two level
  morphology as cascading transducers
  * [16:11]  <jimregan> but, as it's cascading, two level could
  potentially be made n-level


  [[Category:Flag diacritics]]