INF5820 Natural Language Processing - NLP. H2009 Jan Tore Lønning - PDF

Description
INF5820 Natural Language Processing - NLP H2009 Jan Tore Lønning Dependensparsing INF5830 Lecture 12 Nov 2, 2009 Today Dependency grammar Dependency parsing w/maltparser Dependency grammar

Please download to get full document.

View again

of 37
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

History

Publish on:

Views: 14 | Pages: 37

Extension: PDF | Download: 0

Share
Transcript
INF5820 Natural Language Processing - NLP H2009 Jan Tore Lønning Dependensparsing INF5830 Lecture 12 Nov 2, 2009 Today Dependency grammar Dependency parsing w/maltparser Dependency grammar Syntax as dependency structure between words Asymmetric relationship between head and dependent Different from phrase structure: only terminals Lucien Tesnière ( ) Éléments de syntaxe structurale (1959) Alternativ grafikk SBJ news:nn had:vbd OBJ effect:nn P.:PU economic:jj little:jj on:in PMOD markets:nns financial:jj Sammenheng Fra et hodemerket PS-tre: Lag depedensstruktur ved å slå sammen hodet med sin mor Bestem dependenstype Fra depedens til frasestruktur ikke rett frem Formell definisjon Styrker Færre ting å ta stilling til Velegnet for språk med friere ordstilling Men ikke trivielt å parse fri ordstilling Har den vesentlige informasjonen for videre semantisk prosessering: hvem gjorde hva med hvem Velegnet for parsing: Liknende informasjon som i leksikalsk PCFG tilgjengelig: ord og POS-tagg for hodet Projektiv? Mulige krav 3. Single-Head: Ikke i j og i k 4. Acyklisk: ikke i j og j * i 5. Projektiv: Hvis i j og i k j eller j k i, så i * k MaltParser 1. Deterministisk SR-parser for depedenssturktur 2. History-based trekkmodell for å predikere neste trekk (a la Collins) 3. Diskriminativ læring av orakel for å styre parservalgene Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets.shift Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets.shift news had little effect on financial markets. LEFT-ARCH Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets.shift news had little effect on financial markets. LEFT-ARCH news had little effect on financial markets. SHIFT SBJ Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets.shift news had little effect on financial markets. LEFT-ARCH news had little effect on financial markets. SHIFT had little effect on financial markets. LEFT-ARCH SBJ Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets.shift news had little effect on financial markets. LEFT-ARCH news had little effect on financial markets. SHIFT had little effect on financial markets. LEFT-ARCH had little effect on financial markets. SHIFT + SHIFT SBJ Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets.shift news had little effect on financial markets. LEFT-ARCH news had little effect on financial markets. SHIFT had little effect on financial markets. LEFT-ARCH had little effect on financial markets. SHIFT + SHIFT had effect on financial markets. LEFT-ARCH SBJ OBJ Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets.shift news had little effect on financial markets. LEFT-ARCH news had little effect on financial markets. SHIFT had little effect on financial markets. LEFT-ARCH had little effect on financial markets. SHIFT + SHIFT had effect on financial markets. LEFT-ARCH had effect on financial markets. SBJ OBJ Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets.shift news had little effect on financial markets. LEFT-ARCH news had little effect on financial markets. SHIFT had little effect on financial markets. LEFT-ARCH had little effect on financial markets. SHIFT + SHIFT had effect on financial markets. LEFT-ARCH had effect on financial markets. had effect on financial markets. SBJ OBJ Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets.shift news had little effect on financial markets. LEFT-ARCH news had little effect on financial markets. SHIFT had little effect on financial markets. LEFT-ARCH had little effect on financial markets. SHIFT + SHIFT had effect on financial markets. LEFT-ARCH had effect on financial markets. had effect on financial markets. had effect on financial markets. SHIFT SBJ OBJ Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets.shift news had little effect on financial markets. LEFT-ARCH news had little effect on financial markets. SHIFT had little effect on financial markets. LEFT-ARCH had little effect on financial markets. SHIFT + SHIFT had effect on financial markets. LEFT-ARCH had effect on financial markets. had effect on financial markets. had effect on financial markets. SHIFT had effect on markets. LEFT-ARCH OBJ SBJ PMOD Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets.shift news had little effect on financial markets. LEFT-ARCH news had little effect on financial markets. SHIFT had little effect on financial markets. LEFT-ARCH had little effect on financial markets. SHIFT + SHIFT had effect on financial markets. LEFT-ARCH had effect on financial markets. had effect on financial markets. had effect on financial markets. SHIFT had effect on markets. LEFT-ARCH had effect on markets. OBJ SBJ PMOD Economic news had little effect on financial markets. Economic news had little effect on financial markets. Economic news had little effect on financial markets.shift news had little effect on financial markets. LEFT-ARCH news had little effect on financial markets. SHIFT had little effect on financial markets. LEFT-ARCH had little effect on financial markets. SHIFT + SHIFT had effect on financial markets. LEFT-ARCH had effect on financial markets. had effect on financial markets. had effect on financial markets. SHIFT had effect on markets. LEFT-ARCH had effect on markets. had. 3 x REDUCE OBJ SBJ PMOD Economic news had little effect on financial markets. P Economic news had little effect on financial markets. Economic news had little effect on financial markets.shift news had little effect on financial markets. LEFT-ARCH news had little effect on financial markets. SHIFT had little effect on financial markets. LEFT-ARCH had little effect on financial markets. SHIFT + SHIFT had effect on financial markets. LEFT-ARCH had effect on financial markets. had effect on financial markets. had effect on financial markets. SHIFT had effect on markets. LEFT-ARCH had effect on markets. had. 3 x REDUCE had. OBJ SBJ PMOD Economic news had little effect on financial markets. P Economic news had little effect on financial markets. Economic news had little effect on financial markets.shift news had little effect on financial markets. LEFT-ARCH news had little effect on financial markets. SHIFT had little effect on financial markets. LEFT-ARCH had little effect on financial markets. SHIFT + SHIFT had effect on financial markets. LEFT-ARCH had effect on financial markets. had effect on financial markets. had effect on financial markets. SHIFT had effect on markets. LEFT-ARCH had effect on markets. had. 3 x REDUCE had. 2 x REDUCE 0 SBJ OBJ PMOD Economic news had little effect on financial markets. P Detalj: starter med kant fra 0 til alle andre noder fjerner kanten fra 0 til n når vi legger inn ny kant til n (SINGLE-HEAD) står igjen med kant fra 0 til had Deterministic So far: non-deterministic algorithm Deterministic: An oracle decides the next move when stack is non-empty The oracle is learned from a treebank Features σ j is j-th token on stack τ j is j-th token in input h(j), head of j in graph l(j), leftmost child of j r(j), rightmost child of j Standard modell: p(.): σ 0, σ 1 τ 0, τ 1, τ 2, τ 3 w(.): σ 0, h(σ 0 ) p(j) is tag of j d(j) is dependency type of j w(j) is word of j τ 0, τ 1 d(.): l(σ 0 ), σ 0, r(σ 0 ), l(τ 0 ) SBJ OBJ Economic news had little effect on financial markets. had effect on financial markets. p(σ 0 ) = p(effect) = NN p(σ 1 ) = p(had) = VBD p(τ 0 ) = p(on) = IN p(τ 1 ) = p(financial) = JJ p(τ 2 ) = p(markets) = NNS p(τ 3 ) = p(.) = PU w(σ 0 ) = effect w(h((σ 0 )) = had w(τ 0 ) = on w(τ 1 ) = financial d(l(σ 0 )) = d(σ 0 ) = OBJ d(r(σ 0 )) = nil d(l(τ 0 )) = nil Læring Trekkene læres fra en trebank med eksempler Forenlig med ulike læringsteknikker: Memory-based learning, som TiMBL Support-Vector Machines Osv. Evaluering Results Time complexity O(n 3 ): CKY-recognition CKY w/parse forest CKY for PCFG n-best CKY with PCFG Collins-parser: O(n 5 ) (an adaption is O(n 4 )) MaltParser O(n) with standard model O(n 2 ) with unrestricted look-ahead Generative model E.g. PCFG Generates tree with probability: P(t) = P(t, s) if s is the yield of t P(t, s) = 0 for other s Hence: and Also language model: Discriminative model Does not construct the tree Only compares P(t1 s) to P(t2 s) for candidate trees MaltParser does not compare full trees but moves: local decisions
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks