Applying causal-state splitting reconstruction algorithm to natural language processing tasks

Tesis doctoral de Montserrat Padró Cirera

This thesis is focused on the study and use of causal state splitting reconstruction (cssr) algorithm for natural  language processing (nlp) tasks. cssr is an algorithm that captures patterns from data building automata in the  form of visible markov models. it is based on the principles of computational mechanics and takes advantage of many  properties of causal state theory. one of the main advantages of cssr with respect to markov models is that it builds  states containing more than one $n$­gram (called history in computational mechanics), so the obtained automata are  much smaller than the equivalent markov model. in this work, we first study the behavior of the algorithm when learning patterns related to nlp tasks but without  performing any annotation task. this first experiments are useful to understand the parameters that affect the  algorithm and to check that it is able to capture the patterns present in natural language sentences.  secondly, we propose a way to apply cssr to nlp annotation tasks. the algorithm is not originally conceived to use  the hidden information necessary for annotation tasks, so we devised a way to introduce it into the system in order to  obtain automata including this information that can be afterwards used to annotate new text. also, some methods to  deal with unseen events and a modification of the algorithm to make it more suitable for nlp tasks have been  presented and tested. these three aspects conform the first line of contributions of this research, altogether with a  deep experimental study of the proposed methods.  the experimental study of the proposed approach is performed in three different tasks: named entity recognition in  general and biomedical domain and chunking. the obtained results are promising in the two first tasks though not so  good for chunking. nevertheless, it is not easy to improve the obtained performance following the same approach,  since cssr needs quite reduced feature sets to build correct automaton and that limits the performance of the  developed system. for that reason, we propose to combine cssr with graphical models, in order to enrich the  features that the system can take into account. this combination conforms the second line of contributions of this thesis. there is a variety of possible graphical  models that can be used, but for the moment we propose to combine cssr algorithm with maximum entropy (me)  models. me models can be used as a way of introducing more information into the system, encoding it as features. in  this line, we propose and test two methods for combining cssr and me models in order to improve the results  obtained with original cssr. the first method is simple and does not modify the automata­building algorithm while the  second one is more sophisticated and builds automata taking into account the me features. we will see that though  much more simpler, the first method leads to an important improvement with respect to original cssr but the second  method does not.

Datos académicos de la tesis doctoral «Applying causal-state splitting reconstruction algorithm to natural language processing tasks«

• Título de la tesis:  Applying causal-state splitting reconstruction algorithm to natural language processing tasks
• Autor:  Montserrat Padró Cirera
• Universidad:  Politécnica de catalunya
• Fecha de lectura de la tesis:  18/07/2008

Dirección y tribunal

• Director de la tesis
  • Lluís Padró Cirera
• Tribunal
  • Presidente del tribunal: horacio Rodríguez hontoria
  • iñaki Alegria loinaz (vocal)
  • bill Keller (vocal)
  • ferrán Pla santamaría (vocal)