Statistical learning theory

• VC dimension, Rademacher complexity, and growth function

  Nathanaël Fijalkow

  We define the VC dimension, the Rademacher complexity, and the growth function of a class of functions.Let $X$ be the set of inputs. The general learning question we consider is the following: we want to learn a target function \(f : X \to \left\{...

• The fundamental theorem of statistical learning

  Nathanaël Fijalkow

  We state and prove the fundamental theorem of statistical learning, which says that a class of functions is learnableif and only if it has finite VC dimension.This post uses all the notations of the previous post. Theorem: If $H$ has infinit...

• Fliess' theorem for minimising weighted automata

  Nathanaël Fijalkow

  We state and prove Fliess' theorem, which says that the minimal automaton recognising a given formal series has size the rank of its Hankel matrix.A formal series (here over the reals) is a function \(f : \Sigma^* \to \R\).The Hankel matrix of \(f...

• Angluin's style learning for weighted automata

  Nathanaël Fijalkow

  We show that weighted automata over the reals can be learned efficiently in Angluin's supervised scenario.This post uses all the notations of the previous post,and the result presented here was proved in this paper.The scenario is Angluin’s style ...

• Minimising weighted tree automata and context-free grammars

  Nathanaël Fijalkow

  We discuss an extension of Fliess' theorem for minimising weighted tree automata.This post is somehow a follow-up of this one, but it can be read independently.Minimising weighted tree automataWe consider tree formal series (here over the reals), ...

• PAC-learning and compression schemes

  Nathanaël Fijalkow

  We state and prove the equivalence between PAC-learnability, finite VC dimension, and the existence of compression schemes.Many thanks to Borja Balle, Pascale Gourdeau, and Pierre Ohlmann, for discussions on compression schemes and for the joint e...

• Weighted automata and matrix factorisations

  Nathanaël Fijalkow

  We discuss extensions of Fliess' theorem which says that the smallest weighted automaton for a function is exactly the rank of its Hankel matrix.The goal is to extend this theorem to subclasses of weighted automata such as probabilistic automata.M...