LearnAut 2019

Omega languages, i.e. languages of infinite words (or of infinite trees), play an important role in modeling, verification and synthesis of reactive systems. While query learning of regular languages of finite words can be done in polynomial time using a polynomial number of membership and equivalence queries, there is no known polynomial learning algorithm for the full class of omega regular languages. In this talk we will discuss the obstacles in obtaining a polynomial learning algorithm and go through state-of-the art results on learning of regular languages of infinite words and of infinite trees.

From information integration to scientific discovery to computational social science, we need machine learning methods that are able to exploit both the inherent uncertainty and the innate structure in a domain. Statistical relational learning (SRL) is a subfield that builds on principles from probability theory and statistics to address uncertainty while incorporating tools from knowledge representation and logic to represent structure. In this talk, I will give a brief introduction to SRL, present templates for common structured prediction problems, and describe modeling approaches that mix logic, probabilistic inference and latent variables. I’ll overview our recent work on probabilistic soft logic (PSL), an SRL framework for large-scale collective, probabilistic reasoning in relational domains. I’ll close by highlighting emerging opportunities (and challenges) in realizing the effectiveness of data and structure for knowledge discovery.

The subject of this talk are planning problems where agents operate inside environments that are subject to uncertainties and partial observability. Such problems are naturally modelled by partially observable MDPs (POMDPs). The goal is to compute a strategy for an agent that is guaranteed to satisfy certain safety or performance specifications. We discuss several approaches, ranging from a game-based abstraction framework for POMDPs, the computation of finite-memory controllers, and the employment of recurrent neural networks to efficiently synthesize provably correct strategies. Moreover, we consider preliminary work on actively including humans into the synthesis processes, and what challenges arise.

Weighted finite automata (WFA) are ordinary automata defined over vector spaces. They have been used in a variety of settings related to natural language processing and machine learning. Probabilistic automata, hidden Markov models, partially observable Markov decision processes are all instances of WFA. As far back as the 1960s Schutzenberger had developed a minimization algorithm for WFA. More recently Alexandra Silva and her group at UCL developed a categorical perspective on automata learning which has allowed them to generalize the Angluin automata learning algorithm to a variety of settings including the case of WFA which had been done earlier by other researchers under various names. Importantly, Silva's work shows a tight connection between automata learning and minimization. In recent work with Borja de Balle and Doina Precup, we developed a notion of approximate minimization for WFA. Shortly thereafter, Borja, Pascale Gourdeau and I developed a notion of bisimulation metric between weighted automata. In this survey talk I will quickly review the notion of bisimulation and metrics. I will then specialize to bisimulation for WFA. I will then describe the work on approximate bisimulation and on metrics.