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.

Intro
Brief History of Automata Learning
Talk Outline
From Hankel Matrices to DFA
Closed and consistent Finite Hankel Matrices
Learning from Membership and Equivalence Queries
Weighted Finite Automata (WFA)
Hankel Matrices and WFA
From Hankel Matrices to WFA
WFA Reconstruction via Singular Value Decomposition
Estimating Hankel Matrices from Samples
Spectral PAC Learning of Stochastic WFA
Statistical Learning in the Non-realizable Setting
Leaming WFA via Hankel Matrix Completion
Generalization Bounds for Learning WFA
Same Practical Applications