Både probabilistisk kontextfri grammatik (PCFG) och shift-reduce probabilistic pushdown automata (PPDA) har använts för språkmodellering och maximal sannolikhet tolkning. Vi undersöker det exakta förhållandet mellan dessa två formalismer, vilket visar att även om de definierar samma klasser av probabilistiska språk, verkar de påtvinga olika induktiva fördomar. 1 Introduktion Aktuell arbete i stokastiska språkmodeller och maximal sannolikhet parsers faller in i två huvudstrategier. Den första metoden (Collins, 1998; Charniak, 1997) använder direkt definitionen av stokastisk grammatik, som definierar sannolikheten för ett parsträd som sannolikheten att en viss top-down stokastisk generativ process producerar det trädet. Den andra metoden (Briscoe och Carroll, 1993; Black et al., 1992; Magerman, 1994; Ratnaparkhi, 1997; Chelba och Jelinek, 1998) definierar sannolikheten för ett parseträd som sannolikheten för att en viss shiftreduce stokastisk parserande automaton ger det trädet. Dessa två metoder motsvarar de klassiska begreppen kontextfri grammatik respektive icke-deterministisk pushdown automata. Det är välkänt att dessa två klassiska formalismer definierar samma språkklass. I denna artikel visar vi att probabilistisk kontextfri grammatik (PCFG) och probabilistisk pushdown automata (PPDA) definierar samma klass av distributioner på strängar, vilket utvidgar det klassiska resultatet till det stokastiska fallet. Vi tar också upp den kanske mer intressanta frågan om huruvida PCFG och shift-reduce parsing modeller har samma induktiva fördomar när det gäller automatisk inlärning av modellparametrar från data. Även om vi inte kan ge ett definitivt svar, de konstruktioner vi använder för att
Medan kontextfri grammatik är lika koncis som pushdown automata är probabilistisk kontextfri grammatik, även om de genererar samma probabilistiska distributioner som probabilistiska pushdown automata, exponentiellt mindre koncisa REF.
Relating Probabilistic Grammars And Automata
{'venue': 'Annual Meeting Of The Association For Computational Linguistics', 'journal': None, 'mag_field_of_study': ['Computer Science']}