Spectral learning of weighted automata: a forward-backward perspective
| Autor: | Xavier Carreras, Ariadna Quattoni, Franco M. Luque, Borja Balle |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya. GPLN - Grup de Processament del Llenguatge Natural, Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge |
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Předmět: |
Finite-state machine
Theoretical computer science Learning automata Computer science Sequential machine theory Measure (mathematics) Substring Automaton Autòmats finits Artificial Intelligence Spectral learning Weighted finite automata Dependency parsing Informàtica::Intel·ligència artificial [Àrees temàtiques de la UPC] Algebraic number Spectral method Algorithm Hankel matrix Software |
| Zdroj: | Recercat. Dipósit de la Recerca de Catalunya Universitat Jaume I UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) |
| Popis: | In recent years we have seen the development of efficient provably correct algorithms for learning Weighted Finite Automata (WFA). Most of these algorithms avoid the known hardness results by defining parameters beyond the number of states that can be used to quantify the complexity of learning automata under a particular distribution. One such class of methods are the so-called spectral algorithms that measure learning complexity in terms of the smallest singular value of some Hankel matrix. However, despite their simplicity and wide applicability to real problems, their impact in application domains remains marginal to this date. One of the goals of this paper is to remedy this situation by presenting a derivation of the spectral method for learning WFA that—without sacrificing rigor and mathematical elegance—puts emphasis on providing intuitions on the inner workings of the method and does not assume a strong background in formal algebraic methods. In addition, our algorithm overcomes some of the shortcomings of previous work and is able to learn from statistics of substrings. To illustrate the approach we present experiments on a real application of the method to natural language parsing. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|