8th European Conference on Speech Communication and Technology

Geneva, Switzerland
September 1-4, 2003


Learning Rule Ranking by Dynamic Construction of Context-Free Grammars Using AND/OR Graphs

Anna Corazza (1), Louis ten Bosch (2)

(1) University of Milan, Italy
(2) University of Nijmegen, The Netherlands

This paper^1 discusses a novel approach for the construction of a context-free grammar based on a sequential processing of sentences. The construction of the grammar is based on a search algorithm for the minimum weight subgraph in an AND/OR graph. Aspects of optimality and robustness are discussed. The algorithm plays an essential role in a model for adaptive learning of probabilistic ordering. The novelty in the proposed model is the combination of well-established methods from two different disciplines: graph theory and statistics. The set-up of this paper is mainly theoretical, and we follow a quite formal approach. There is a close link with Optimality Theory, one of the mainstream approaches in phonology, and with graph theory. The resulting techniques, however, can be applied in a more general domain.

Full Paper

Bibliographic reference.  Corazza, Anna / Bosch, Louis ten (2003): "Learning rule ranking by dynamic construction of context-free grammars using AND/OR graphs", In EUROSPEECH-2003, 773-776.