4. Frequency Analysis of Empty Nodes.pdfVIP

TLT 2003, Va?xjo?. Gerold Schneider Extracting and Using Trace-Free Functional Dependencies from the Penn Treebank to Reduce Parsing Complexity Gerold Schneider Institute of Computational Linguistics, University of Zurich Department of Linguistics, University of Geneva gerold.schneider@lettres.unige.ch November 14, 2003 1 TLT 2003, Va?xjo?. Gerold Schneider Contents 1. Motivation 2. Probability Model 3. Extraction of Dependencies 4. Frequency Analysis of Empty Nodes 5. Evaluation 6. Conclusions 2 TLT 2003, Va?xjo?. Gerold Schneider 1 Motivation 1. Most formal grammars need parsers with high parsing complexity: O(n 5 ) and worse 2. Most statistical parsers allow using O(n 3 ) complexity algorithms (Eisner, 2000), (Nivre, 2003), such as the CYK used here, but they do not express long-distance dependencies (LDD) and empty nodes (EN) 3. Most successful deep-linguistic Dependency Parsers (Lin, 1998), (Tapanainen and Ja?rvinen, 1997) do not have a statistical base 4. Reconstruction of LDD and EN from statistical parser output is not successful (Johnson, 2002) 3 TLT 2003, Va?xjo?. Gerold Schneider 2 Lexicalized Dependency Probability Model In a binary CFG, any two constituents A and B which are adjacent during parsing are candidates for the RHS of a rewrite rule. Terminal types are the word tags. X ! AB; e:g:NP ! DT NN (1) In DG and Bare Phrase Structure, one of these is isomorphic to the RHS, i.e. the head. B ! AB; e:g: NN ! DT NN (2) A! AB; e:g: V B ! V B PP (3) DG rules additionally use a syntactic relation label R. A non-lexicalized model would be: p(RjA! AB)  = #(R;A! AB) #(A! AB) (4) 4 TLT 2003, Va?xjo?. Gerold Schneider Research on PCFG and PP-attachment has shown the importance of probabilizing on lexical heads (a and b). p(RjA! AB; a; b)  = #(R;A! AB; a; b) #(A! AB; a; b) (5) All that A ! AB expresses is that in the dependency relation the dependency is towards the right. p(Rjright; a; b)  = #(R; right; a; b) #(right; a; b) (6) e.g. for the Verb-PP attachment r