Inference of a Probabilistic Finite State Machine from its Output

Abstract

This paper addresses the problem of identifying a probabilistic FSM from its output. We propose a formal description of the FSM and its output, using a regular phrase-structured grammar. This description is associated with a cost measuring its information content. We then state the inference problem as a combinatorial optimization problem with an objective function define as the cost of the description of the FSM and its output A heuristic algorithm is proposed which processes the output “on line” and yields a local minimum of our criterion. At each step (i.e., as new data is observed and processed), the procedure searches locally through the space of non-probabilistic FSMs, i.e., the transitions are initially regarded as being only present or absent. When a non-probabilistic model has been generated, the transition probabilities are determined from their relative frequencies given the behavior indicated by the data. This yields maximum likelihood estimates of the probabilities. The costs of the obtained probabilistic FSMs are then computed, and the K minimum cost FSMs are kept as starting points for the next step search. At each step, the generation of the FSMs is done via a local search through the neighborhoods of the K best FSMs obtained at the previous step. This algorithm is compared with similar algorithms proposed previously, and tested on a range of examples. It is found to work for a wider range of FSMs than the previous methods, and it is much more practical for large problems than previously proposed exhaustive search techniques. © 1995 IEEE