Realization of common statistical methods in computational linguistics with functional automata

Proceedings of Recent Advances in Natural Language Processing, pages 294–301, Hissar, Bulgaria, 7-13 September 2013. Realization of Common Statistical Methods in Computational Linguistics with Functional Automata Stefan Gerdjikov Faculty of Mathematics and Informatics, Sofia University 5 James Bourchier blvd., 1164 Sofia, Bulgaria st gerdjikov@ abv.bg Petar Mitankin Faculty of Mathematics and Informatics, Sofia University 5 James Bourchier blvd., 1164 Sofia, Bulgaria pmitankin@ fmi.uni-sofia.bg Vladislav Nenchev Faculty of Mathematics and Informatics, Sofia University 5 James Bourchier blvd., 1164 Sofia, Bulgaria lucifer.dev.0@ gmail.com Abstract In this paper we present the functional au- tomata as a general framework for repre- sentation, training and exploring of vari- ous statistical models as LLM’s, HMM’s, CRF’s, etc. Our contribution is a new construction that allows the representation of the derivatives of a function given by a functional au- tomaton. It preserves the natural repre- sentation of the functions and the stan- dard product and sum operations of real numbers. In the same time it requires no additional overhead for the standard dy- namic programming techniques that yield the computation of a functional value. 1 Introduction Statistical models such as n-gram language mod- els (Chen and Goodman, 1996), hidden Markov models (Rabiner, 1989), conditional random fields (Lafferty et al., 2001), log-linear models (Dar- roch and Ratcliff, 1972) are widely applied in the natural language processing in order to approach various problems, e.g. parsing (Sha and Pereira, 2003), speech recognition (Juang and Rabiner, 1991), statistical machine translation (Brown et al., 1993). Different statistical models perform differently on different tasks. Thus in order to find the best practical solution one might need to try several approaches before getting the desired ef- fect. Disposing on a general framework that al- lows the flexibility to change the statistical model or/and training scheme would spend much efforts and time. Focusing on this pragmatical problem, we pro- pose the functional automata as a possible solu- tion. The basic idea is to consider the mathemati- cal expressions of sums and products arising in the statistical models as regular expressions. Thus re- garding the functions in these expressions as indi- vidual characters, the sums as unions and the prod- ucts as concatenation, we get the desired corre- spondence. The relation between a particular sta- tistical model and a functional automaton for its representation is then rather straightforward. The training of the statistical models is in a way more involved. Most of the approaches require a gradient method that estimates the best model pa- rameters. To this end one needs to have an efficient representation not only of the function used by the model but also of its (partial) derivatives. To solve similar problem Eisner and Li in- troduce first-order and second-order expectation semirings. In (Jason Eisner, 2002; Zhifei Li and Jason Eisner, 2009) it is shown how derivatives of functions arising in statistical models can be represented. This is achieved by the means of an algebraic construction that: (i) considers pairs of functions (first-order expectation semiring) and quadruples of functions (second-order expectation semiring); (ii) introduces …

Content truncated to 500 words