Seminars home
Bias and variance of learning with weighted automata
at
Speaker: Borja Balle, professor at Lancaster University, Lancaster, U.K
Abstract: Weighted automata (WA) are a general class of finite state machines that include many widely used models like hidden Markov models, deterministic finite automata, and predictive state representations. Traditional algorithms for learning WA were developed for particular problems and sub-classes of models (eg. EM for HMM and state-merging for deterministic automata). In recent years, the introduction of spectral techniques has provided a new standard tool for designing efficient algorithms for learning WA that can be applied in many different circumstances (eg. stochastic WFA, transductions, regression on strings). The most salient features of the spectral approach are: polynomial running time without local optima, PAC guarantees in the realizable setting, and very good performance in practice. The last two items in this list suggest spectral learning is a tool to consider in many practical applications, but they also show there is still a gap between the theory and practice of spectral learning. Namely, that in general there is no theoretical explanation for the good behavior of spectral learning with real data.
The purpose of this talk is to present two recent lines of work that shed some light onto the problem of spectral learning without realizability assumptions, and to discuss how these can lead to better algorithms by informing regularization and model selection for WA. Our first set of results looks into how the number of states of the hypothesis WA affects the learning bias. These investigations lead us to the development of a novel canonical form for WA we call the Singular Value Automaton (SVA), which can be interpreted as a compressed representation of the SVD of an infinite Hankel matrix. We will explain how SVA truncation is related to the bias of spectral learning and describe the potential learning applications of efficient algorithms for computing the SVA of a given WA. If time permits, a recent extension of SVA to Weighted Tree Automata will also be discussed. In the second part of the talk I will describe three families of regularizers for learning with WA and provide bounds on the Rademacher complexity of classes of WA defined in terms of these regularizers. These results can be used to understand the different sources of variance when learning WA, and provide principled ways of controlling the capacity of hypothesis classes based on WA. In particular, our approach provides a theoretical justification for regularizing Hankel matrix completion problems with nuclear norm penalties.
This talk is based on joint work with: Shay Cohen, Mehryar Mohri, Prakash Panangaden, Doina Precup, and Guillaume Rabusseau.
To make robots autonomous in real-world everyday spaces, they should be able to learn from their interactions within these spaces, how to best execute tasks specified by non-expert users in a safe and reliable way. To do so requires sequential decision-making skills that combine machine learning, adaptive planning and control in uncertain environments as well as solving hard combinatorial optimisation problems. Our research combines expertise in reinforcement learning, computer vision, robotic control, sim2real transfer, large multimodal foundation models and neural combinatorial optimisation to build AI-based architectures and algorithms to improve robot autonomy and robustness when completing everyday complex tasks in constantly changing environments.
VISION
The research we conduct on expressive visual representations is applicable to visual search, object detection, image classification and the automatic extraction of 3D human poses and shapes that can be used for human behavior understanding and prediction, human-robot interaction or even avatar animation. We also extract 3D information from images that can be used for intelligent robot navigation, augmented reality and the 3D reconstruction of objects, buildings or even entire cities.
Our work covers the spectrum from unsupervised to supervised approaches, and from very deep architectures to very compact ones. We’re excited about the promise of big data to bring big performance gains to our algorithms but also passionate about the challenge of working in data-scarce and low-power scenarios.
Furthermore, we believe that a modern computer vision system needs to be able to continuously adapt itself to its environment and to improve itself via lifelong learning. Our driving goal is to use our research to deliver embodied intelligence to our users in robotics, autonomous driving, via phone cameras and any other visual means to reach people wherever they may be.
This web site uses cookies for the site search, to display videos and for aggregate site analytics.
Learn more about these cookies in our privacy notice.
Cookie settings
You may choose which kind of cookies you allow when visiting this website. Click on "Save cookie settings" to apply your choice.
This content is currently blocked. To view the content please either 'Accept social media cookies' or 'Accept all cookies'.
For more information on cookies see our privacy notice.