DocumentCode :
290057
Title :
Reducing the computational complexity for inferring stochastic context-free grammar rules from example text
Author :
Lucke, Helmut
Author_Institution :
ATR Interpreting Telecommun Res. Labs., Kyoto, Japan
Volume :
i
fYear :
1994
fDate :
19-22 Apr 1994
Abstract :
Learning context-free grammar rules from example text is a difficult task. Existing algorithms exhibit a cubic relationship between the number of non-terminal symbols and the computational complexity which has so far prevented the use of such models for applications with more then, say, 30 non-terminal symbols. The paper introduces a mathematical technique which reduces the complexity to a quadratic one, allowing the training of grammars with far more non-terminal symbols than was previously possible. Different versions of the algorithm are experimentally compared and the difference in order is verified
Keywords :
computational complexity; computational linguistics; context-free grammars; learning (artificial intelligence); natural languages; speech recognition; stochastic processes; computational complexity; example text; learning; mathematical technique; nonterminal symbols; quadratic relationships; stochastic context-free grammar rules; Computational complexity; Entropy; Iterative algorithms; Laboratories; Natural languages; Parameter estimation; Speech recognition; Stochastic processes; Telecommunications; Tree data structures;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Acoustics, Speech, and Signal Processing, 1994. ICASSP-94., 1994 IEEE International Conference on
Conference_Location :
Adelaide, SA
ISSN :
1520-6149
Print_ISBN :
0-7803-1775-0
Type :
conf
DOI :
10.1109/ICASSP.1994.389283
Filename :
389283
Link To Document :
بازگشت