Learning Automata with Hankel Matrices - Borja Balle, Amazon Research Cambridge

Explore the intersection of logic and learning in this comprehensive talk on learning automata with Hankel matrices. Delve into a unified framework that encompasses various classical and recent algorithms for automata learning across different paradigms. Discover the power of Hankel matrices as a fundamental tool in weighted automata theory. Examine query learning algorithms, spectral learning techniques, and Hankel matrix completion methods. Trace the brief history of automata learning and understand key concepts such as closed and consistent finite Hankel matrices, weighted finite automata (WFA), and WFA reconstruction via singular value decomposition. Investigate the process of estimating Hankel matrices from samples and explore spectral PAC learning of stochastic WFA. Gain insights into statistical learning in non-realizable settings and generalization bounds for learning WFA. Conclude with practical applications of these techniques in real-world scenarios.