Tesis doctoral de Borja De Balle Pigem
The present thesis addresses several machine learning problems on generative and predictive models on sequential data. All the models considered have in common that they can be defined in terms of finite-state machines. On one line of work we study algorithms for learning the probabilistic analog of deterministic finite automata (dfa). This provides a fairly expressive generative model for sequences with very interesting algorithmic properties. State-merging algorithms for learning these models can be interpreted as a divisive clustering scheme where the ¿dependency graph¿ between clusters is not necessarily a tree. We characterize these algorithms in terms of statistical queries and a use this characterization for proving a lower bound with an explicit dependency on the distinguishability of the target machine. In a more realistic setting, we give an adaptive state-merging algorithm satisfying the stringent algorithmic constraints of the data streams computing paradigm. Our algorithms come with strict pac learning guarantees. At the heart of state-merging algorithms lies a statistical test for distribution similarity. In the streaming version this is replaced with a bootstrap-based test which yields faster convergence in many situations. We also studied a wider class of models for which the state-merging paradigm also yield pac learning algorithms. Applications of this method are given to continuous-time markovian models and stochastic transducers on pairs of aligned sequences. The main tools used for obtaining these results include a variety of concentration inequalities and sketching algorithms. in another line of work we contribute to the rapidly growing body of spectral learning algorithms. The main virtues of this type of algorithms include the possibility of proving finite-sample error bounds in the realizable case and enormous savings on computing time over iterative methods like expectation-maximization. In this thesis we give the first application of this method for learning conditional distributions over pairs of aligned sequences defined by probabilistic finite-state transducers. We also prove that the method can learn the whole class of probabilistic automata, thus extending the class of models previously known to be learnable with this approach. In the last two chapters we present works combining spectral learning with methods from convex optimization and matrix completion. Respectively, these yield an alternative interpretation of spectral learning and an extension to cases with missing data. In the latter case we used a novel joint stability analysis of matrix completion and spectral learning to prove the first generalization bound for this type of algorithms that holds in the non-realizable case. Work in this area has been motivated by connections between spectral learning, classic automata theory, and statistical learning; tools from these three areas have been used.
Datos académicos de la tesis doctoral «Learning finite-state machines: statistical and algorithmic aspects«
- Título de la tesis: Learning finite-state machines: statistical and algorithmic aspects
- Autor: Borja De Balle Pigem
- Universidad: Politécnica de catalunya
- Fecha de lectura de la tesis: 12/07/2013
Dirección y tribunal
- Director de la tesis
- Jorge Castro Rabal
- Tribunal
- Presidente del tribunal: José Luis Balcazar navarro
- alexander Clark (vocal)
- colin De la higuera (vocal)
- Ana alejandra Cabaña nigro (vocal)