NDLI: Maximum Likelihood and the Graphical Em Algorithm

Content Provider	IEEE Xplore Digital Library
Author	Latombe, G. Granger, E. Dilkes, F.A.
Copyright Year	2006
Description	Author affiliation: Dept. de Genie de la Production Automatisee, Ecole de Technologie Superieure, Montreal, Que. (Latombe, G.; Granger, E.)
Abstract	A challenge in the design of SCFGs for some applications is the computation of the probability distributions associated with its production rules. The most popular methods for this task are by far the inside-outside (IO) algorithm, which maximizes the likelihood of a data set, and the Viterbi score (VS) algorithm, which maximizes the likelihood of its best parse trees. Even though both algorithms are very demanding and have a similar time complexity, VS is known to require an overall lower computational cost in practice. Several methods have been developed to accelerate the computation of production rules probabilities with IO. Among them is the graphical EM (gEM) algorithm. During pre-processing, it computes the rules used in the production of the data set, and organizes them into an ordered data structure called "support graphs." The iterative process uses these graphs to optimize the likelihood of the data set in a similar way to the IO algorithm. In this paper, a VS variant of gEM, that selects in the support graphs the elements belonging to the best parse trees of the data set, is proposed. The performance of the original algorithm, gEM(IO), and the new one, gEM(VS), are compared in terms of time and space complexity, convergence time, and perplexity. An experimental protocol is defined such that the impact on performance of factors like training set size, sequence length, and ambiguity of grammars can be assessed. Computer simulations are performed on the real-world European Molecular Biology Laboratory data set, consisting of DNA sequences. Results indicate that gEM(VS) provides significantly lower convergence time and time complexity, at the expense of a moderately higher perplexity and space complexity level
Starting Page	1475
Ending Page	1480
File Size	224395
Page Count	6
File Format	PDF
ISBN	1424400384
DOI	10.1109/CCECE.2006.277845
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2006-05-07
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Production Tree graphs Iterative algorithms Convergence Sequences Computer applications Distributed computing Probability distribution Viterbi algorithm Computational efficiency Graphical EM Bio-Informatics Maximum Likelihood Stochastic Context Free Grammars Inside-Outside Viterbi Score
Content Type	Text
Resource Type	Article

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

Comparison between the inside-outside algorithm and the viterbi algorithm for stochastic context-free grammars (1996).

Inside-outside estimation meets dynamic EM (2001)

The estimation of stochastic context-free grammars using the Inside-Outside algorithm

Iterative CKY parsing for Probabilistic Context-Free Grammars (2004)

Statistical Estimation of Stochastic Context-Free Grammars Using the Inside-Outside Algorithm and a Transformation on Grammars *

A note on stochastic context-free grammars, termination and the em-algorithm.

Two Algorithms for Learning the Parameters of Stochastic Context-Free Grammars (2001)

A tutorial on the expectation-maximization algorithm including maximum-likelihood estimation and em training of probabilistic context-free grammars (2003).

A Tutorial on the Expectation-Maximization Algorithm Including Maximum-Likelihood Estimation and EM Training of Probabilistic Context-Free Grammars (2003)

Maximum Likelihood and the Graphical Em Algorithm

Similar Documents

Comparison between the inside-outside algorithm and the viterbi algorithm for stochastic context-free grammars (1996).

Inside-outside estimation meets dynamic EM (2001)

The estimation of stochastic context-free grammars using the Inside-Outside algorithm

Iterative CKY parsing for Probabilistic Context-Free Grammars (2004)

Statistical Estimation of Stochastic Context-Free Grammars Using the Inside-Outside Algorithm and a Transformation on Grammars *

A note on stochastic context-free grammars, termination and the em-algorithm.

Two Algorithms for Learning the Parameters of Stochastic Context-Free Grammars (2001)

A tutorial on the expectation-maximization algorithm including maximum-likelihood estimation and em training of probabilistic context-free grammars (2003).

A Tutorial on the Expectation-Maximization Algorithm Including Maximum-Likelihood Estimation and EM Training of Probabilistic Context-Free Grammars (2003)

Maximum Likelihood and the Graphical Em Algorithm