Using Pseudo-Stochastic Rational Languages in Probabilistic Grammatical
  Inference
  In probabilistic grammatical inference, a usual goal is to infer a good
approximation of an unknown distribution P called a stochastic language. The
estimate of P stands in some class of probabilistic models such as
probabilistic automata (PA). In this paper, we focus on probabilistic models
based on multiplicity automata (MA). The stochastic languages generated by MA
are called rational stochastic languages; they strictly include stochastic
languages generated by PA; they also admit a very concise canonical
representation. Despite the fact that this class is not recursively enumerable,
it is efficiently identifiable in the limit by using the algorithm DEES,
introduced by the authors in a previous paper. However, the identification is
not proper and before the convergence of the algorithm, DEES can produce MA
that do not define stochastic languages. Nevertheless, it is possible to use
these MA to define stochastic languages. We show that they belong to a broader
class of rational series, that we call pseudo-stochastic rational languages.
The aim of this paper is twofold. First we provide a theoretical study of
pseudo-stochastic rational languages, the languages output by DEES, showing for
example that this class is decidable within polynomial time. Second, we have
carried out a lot of experiments in order to compare DEES to classical
inference algorithms such as ALERGIA and MDI. They show that DEES outperforms
them in most cases.
