Learning via automaton minimization and matrix factorization

Thesis

This thesis focuses on weighted-automaton learning and minimization, matrix factorization, and the relationships between these areas.

The first part of the thesis studies minimization and learning of weighted automata with weights in a field, focusing on tree automata as representations of distributions over trees. We give a minimization algorithm that runs in polynomial time assuming unit-cost arithmetic, and show that a polynomial bound in the Turing model would require a breakthrough in the complexity of polynomial identity testing. We also improve the complexity of minimizing weighted word automata. Secondly, we look at learning minimal weighted automata in both active and passive learning frameworks, analysing both the computational and query complexity. For active learning, we give a new algorithm for learning weighted tree automata in Angluin's exact learning model that efficiently processes DAG counterexamples, and show a complexity lower bound in terms of polynomial identity testing. For passive learning, we characterise the complexity of finding a minimal weighted automaton that is consistent with a set of observations.

The second part of the thesis studies nonnegative matrix factorization (NMF), a powerful dimension-reduction and feature-extraction technique with numerous applications in machine learning and other scientific disciplines. Despite being an important technique in practice, there are a number of open questions about the theory of NMF---especially about its complexity and the existence of good heuristics. We answer a major open problem posed in 1993 by Cohen and Rothblum: the nonnegative ranks over the rationals and over the reals differ. We first tackle a variant of the problem, restricted NMF, which has applications in topic modelling and a geometric interpretation as the nested polytope problem. Lastly we show that NMF is polynomial-time reducible to automaton minimization, and then use our results on NMF to answer old open problems on minimizing labelled Markov chains and probabilistic automata.

Authors: Marusic, I

• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Subjects: Computer science