Seminars

General Departmental Seminar Series

Refining the Structure of a Stochastic Context-Free Grammar

Joe Bockhorst, Graduate Student,
Department of Biostatistics and Medical Informatics
University of Wisconsin-Madison

Thursday, March 8, 2001, 4:00pm

1325 Computer Sciences Statistics Center - 1210 W. Dayton St.

ABSTRACT

We present a machine learning algorithm for refining the structure of a stochastic context--free grammar (SCFG). This algorithm consists of a heuristic for identifying structural errors and an operator for fixing them. The heuristic identifies nonterminals in the model SCFG that appear to be performing the function of two or more nonterminals in the target SCFG, and the operator attempts to rectify this problem by introducing a new nonterminal. Structural refinement is important because most common SCFG learning methods set the probability parameters while leaving the structure of the grammar fixed. Thus, any structural errors introduced prior to training will persist. We present experiments that show our approach is able to significantly improve the accuracy of an SCFG designed to model an important class of RNA sequences called terminators.

Back to General Departmental Seminar Series