Parsing, PCFGs, and the CKY Algorithm Yoav Goldberg (someslidestakenfromMichaelCollins) November 18, 2013 1/48 Natural Language Parsing (cid:73) Sentences in natural language have structure. (cid:73) Linguists create Linguistic Theories for defining this structure. (cid:73) The parsing problem is recovering that structure. 2/48 Today (cid:73) Hierarchical Structure. Natural Language Parsing Previously (cid:73) Structure is a sequence. (cid:73) Each item can be tagged. (cid:73) We can mark some spans. 3/48 Natural Language Parsing Previously (cid:73) Structure is a sequence. (cid:73) Each item can be tagged. (cid:73) We can mark some spans. Today (cid:73) Hierarchical Structure. 3/48 Hierarchical Structure? 4/48 ADD + * * MUL + MUL 3 2 5 3 3 * 2 5 * 3 Structure Example1: math 3*2+5*3 5/48 + * * 3 2 5 3 Structure Example1: math 3*2+5*3 ADD MUL + MUL 3 * 2 5 * 3 5/48 Structure Example1: math 3*2+5*3 ADD + * * MUL + MUL 3 2 5 3 3 * 2 5 * 3 5/48 Programming Languages? 6/48 Constituency Structure Dependency Structure S like flies banana NP VP Fruit a Adj Noun Vb NP Fruit Flies like Det Noun a banana Structure Example2: LanguageData Fruit flies like a banana 7/48