NDLI: Inference of a probabilistic finite state machine from its output

Content Provider	IEEE Xplore Digital Library
Author	Rouvellou, I. Hart, G.W.
Copyright Year	1971
Abstract	This paper addresses the problem of identifying a probabilistic FSM from its output. The authors 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. The authors 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 the authors' 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.<>
Starting Page	424
Ending Page	437
Page Count	14
File Size	1414855
File Format	PDF
ISSN	00189472
Volume Number	25
Issue Number	3
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1995-03-01
Publisher Place	U.S.A.
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Automata Cost function Heuristic algorithms Inference algorithms Frequency Maximum likelihood estimation Yield estimation Testing Speech processing Protocols
Content Type	Text
Resource Type	Article
Subject	Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Optimum and heuristic algorithms for finite state machine decomposition and partitioning

Computationally efficient adaptive control algorithms for Markov chains

Co-channel speaker separation

Automatic and reliable estimation of glottal closure instant and period

Hybrid Algorithms For Maximum Likelihood And Maximum A Posterior Sequence Estimation

On the probability density of a maximum likelihood mean frequency estimator

Fast heuristic algorithms for finite state machine minimization

A new maximum likelihood gradient algorithm for on-line hidden Markov model identification

Maximum likelihood estimation of magnitude-squared coherence

Inference of a probabilistic finite state machine from its output

Similar Documents

Optimum and heuristic algorithms for finite state machine decomposition and partitioning

Computationally efficient adaptive control algorithms for Markov chains

Co-channel speaker separation

Automatic and reliable estimation of glottal closure instant and period

Hybrid Algorithms For Maximum Likelihood And Maximum A Posterior Sequence Estimation

On the probability density of a maximum likelihood mean frequency estimator

Fast heuristic algorithms for finite state machine minimization

A new maximum likelihood gradient algorithm for on-line hidden Markov model identification

Maximum likelihood estimation of magnitude-squared coherence

Inference of a probabilistic finite state machine from its output