Using Pseudo-Stochastic Rational Languages in Probabilistic Grammatical Inference

Computer Science – Learning

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Using Pseudo-Stochastic Rational Languages in Probabilistic Grammatical Inference does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Using Pseudo-Stochastic Rational Languages in Probabilistic Grammatical Inference, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using Pseudo-Stochastic Rational Languages in Probabilistic Grammatical Inference will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-121447

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.