Learning Accurate, Compact, and Interpretable Tree Annotation

Learning Accurate, Compact, and Interpretable Tree Annotation

Learning Accurate, Compact, and Interpretable Tree Annotation Slav Petrov, Leon Barrett, Romain Thibaux, Dan Klein The Game of Designing a Grammar Annotation refines base treebank symbols to improve statistical fit of the grammar Parent annotation [Johnson 98] The Game of Designing a Grammar Annotation refines base treebank symbols to improve statistical fit of the grammar Parent annotation [Johnson 98] Head lexicalization [Collins 99, Charniak 00] The Game of Designing a Grammar Annotation refines base treebank symbols to improve statistical fit of the grammar Parent annotation [Johnson 98] Head lexicalization [Collins 99, Charniak 00] Automatic clustering? Previous Work: Manual Annotation

[Klein & Manning 03] Manually split categories NP: subject vs object DT: determiners vs demonstratives IN: sentential vs prepositional Advantages: Fairly compact grammar Linguistic motivations Disadvantages: F1 Performance leveled out Model Nave Treebank Grammar 72.6 Manually annotated Klein & Manning 03 86.3 [Matsuzaki et. al 05, Prescher 05] Previous Work: Automatic Annotation Induction Advantages: Automatically learned: Label all nodes with latent variables. Same number k of subcategories for all categories.

Disadvantages: Grammar gets too large Most categories are oversplit while others are undersplit. Model F1 Klein & Manning 03 86.3 Matsuzaki et al. 05 86.7 Previous work is complementary Manual Annotation This Work Automatic Annotation Allocates splits where needed Very tedious Compact Grammar Misses Features Splits uniformly Automatically learned Large Grammar Captures many features

Learning Latent Annotations Forward EM algorithm: Brackets are known Base categories are known Only induce subcategories X1 X2 X3 X7 X4 X5 X6 . Just like Forward-Backward for HMMs. He was right

Backward Limit of computational resources Overview 90 85 Parsing accuracy (F1) k=16 k=8 k=4 80 k=2 75 70 65 - Hierarchical Training - Adaptive Splitting - Parameter Smoothing k=1

60 50 250 450 650 850 1050 1250 Total Number of grammar symbols 1450 1650 Refinement of the DT tag DT DT-1 DT-2 DT-3

DT-4 Refinement of the DT tag DT Hierarchical refinement of the DT tag Hierarchical Estimation Results 90 Parsing accuracy (F1) 88 86 84 82 80 78 76 74 100 300 500 700 900

Model 1100 1300 Baseline Total Number of grammar symbols 1500 1700 F1 87.3 Hierarchical Training 88.4 Refinement of the , tag Splitting all categories the same amount is wasteful: The DT tag revisited Oversplit? Adaptive Splitting Want to split complex categories more Idea: split everything, roll back splits which

were least useful Adaptive Splitting Want to split complex categories more Idea: split everything, roll back splits which were least useful Adaptive Splitting Want to split complex categories more Idea: split everything, roll back splits which were least useful Adaptive Splitting Evaluate loss in likelihood from removing each split = Data likelihood with split reversed Data likelihood with split No loss in accuracy when 50% of the splits are reversed. Adaptive Splitting Results 90 Parsing accuracy (F1) 88 86 84 82 80

50% Merging 78 Hierarchical Training 76 Flat Training 74 100 300 500 700 900 Model 1100 1300 Total Number of grammar Previous symbols

1500 1700 F1 88.4 With 50% Merging 89.5 0 LST ROOT X WHADJP RRC SBARQ INTJ WHADVP UCP NAC

FRAG CONJP SQ WHPP PRT SINV NX PRN WHNP QP SBAR ADJP S ADVP PP

VP NP Number of Phrasal Subcategories 40 35 30 25 20 15 10 5 0 LST ROOT X

WHADJP RRC SBARQ INTJ WHADVP UCP NAC FRAG CONJP SQ WHPP PRT SINV 25 NX

N P PRN 30 WHNP 35 QP 40 SBAR ADJP S ADVP PP VP NP Number of Phrasal Subcategories

VP PP 20 15 10 5 LST ROOT X WHADJP RRC NA C SBARQ INTJ WHADVP

10 UCP 15 NAC FRAG CONJP SQ WHPP PRT SINV NX PRN WHNP QP SBAR

ADJP S ADVP PP VP NP Number of Phrasal Subcategories 40 35 30 25 20 X 5 0

30 20 0 NNP JJ NNS NN VBN RB VBG VB VBD CD IN VBZ VBP DT NNPS CC JJR JJS : PRP PRP$ MD RBR WP

POS PDT WRB -LRB. EX WP$ WDT -RRB'' FW RBS TO $ UH , `` SYM RP LS # Number of Lexical Subcategories 70 60 50 40

PO S T O , 10 60 50 40 30 0 NNP JJ NNS NN VBN RB VBG VB VBD CD IN VBZ VBP

DT NNPS CC JJR JJS : PRP PRP$ MD RBR WP POS PDT WRB -LRB. EX WP$ WDT -RRB'' FW RBS TO $ UH , `` SYM RP LS #

Number of Lexical Subcategories 70 R B VBx IN DT 20 10 70 60 50 40 30 0 NNP JJ NNS NN

VBN RB VBG VB VBD CD IN VBZ VBP DT NNPS CC JJR JJS : PRP PRP$ MD RBR WP POS PDT WRB -LRB. EX WP$ WDT -RRB'' FW RBS

TO $ UH , `` SYM RP LS # Number of Lexical Subcategories NN P JJ NN S N N 20 10 Smoothing Heavy splitting can lead to overfitting Idea: Smoothing allows us to pool statistics Linear Smoothing

Result Overview 90 Parsing accuracy (F1) 88 86 84 82 80 50% Merging and Smoothing 78 50% Merging Hierarchical Training 76 Flat Training 74 100 300 500

700 Total Number of grammar symbols 900 1100 Result Overview 90 Parsing accuracy (F1) 88 86 84 82 80 50% Merging and Smoothing 78 50% Merging Hierarchical Training 76 Flat Training

74 100 300 500 700 Total Number of grammar symbols 900 1100 Result Overview 90 Parsing accuracy (F1) 88 86 84 82 80 50% Merging and Smoothing 78

50% Merging Hierarchical Training 76 Flat Training 74 100 300 500 700 Model 900 Previous Total Number of grammar symbols 1100 F1 89.5 With Smoothing 90.7

Final Results F1 40 words F1 all words Klein & Manning 03 86.3 85.7 Matsuzaki et al. 05 86.7 86.1 This Work 90.2 89.7 Parser Final Results F1 40 words

F1 all words Klein & Manning 03 86.3 85.7 Matsuzaki et al. 05 86.7 86.1 Collins 99 88.6 88.2 Charniak & Johnson 05 90.1 89.6 This Work

90.2 89.7 Parser Linguistic Candy Proper Nouns (NNP): NNP-14 Oct. Nov. Sept. NNP-12 John Robert James NNP-2 J. E.

L. NNP-1 Bush Noriega Peters NNP-15 New San Wall NNP-3 York Francisco Street Personal pronouns (PRP): PRP-0 It

He I PRP-1 it he they PRP-2 it them him Linguistic Candy Relative adverbs (RBR): RBR-0 further lower higher

RBR-1 more less More RBR-2 earlier Earlier later Cardinal Numbers (CD): CD-7 one two Three CD-4 1989

1990 1988 CD-11 million billion trillion CD-0 1 50 100 CD-3 1 30 31 CD-9

78 58 34 Conclusions New Ideas: Hierarchical Training Adaptive Splitting Parameter Smoothing State of the Art Parsing Performance: Improves from X-Bar initializer 63.4 to 90.2 Linguistically interesting grammars to sift through. Thank You! [email protected] Other things we tried X-Bar vs structurally annotated grammar: X-Bar grammar starts at lower performance, but provides more flexibility Better Smoothing: Tried different (hierarchical) smoothing methods, all worked about the same

(Linguistically) constraining rewrite possibilities between subcategories: Hurts performance EM automatically learns that most subcategory combinations are meaningless: 90% of the possible rewrites have 0 probability

Recently Viewed Presentations

  • EECS 252 Graduate Computer Architecture Lec 01 - Introduction

    EECS 252 Graduate Computer Architecture Lec 01 - Introduction

    EECS 262a Advanced Topics in Computer SystemsLecture 10Transactions and Isolation Levels (Con't)February 24th, 2016. John Kubiatowicz. Slides by Alan Fekete (University of Sydney), Anthony D. Joseph and John Kubiatowicz (UC Berkeley)
  • 2CFR 200 Uniform Administrative Requirements, Cost Principles, and

    2CFR 200 Uniform Administrative Requirements, Cost Principles, and

    Introduction to 2 CFR Part 200 "Uniform Guidance" 2 CFR 200- Introduction. New Awards authorized on or after Dec 26, 2014. Project Modifications made on or after Dec 26, 2014. Audit Requirements - apply to audits of non-Federal entity fiscal...
  • Hot Air Balloons - Oklahoma 4-H

    Hot Air Balloons - Oklahoma 4-H

    Oklahoma 4-H Youth Development. [email protected] Hot Air Balloon Supplies. Things you may need - Glue Sticks. Scissors, pens, sharpies. Gore Pattern. Wire Hoop to use as a pattern. Wire for Hoops (limited) Wire cutters. Electrical tape. 4 Heat Guns. 2...
  • As the Deer Panteth As the deer panteth

    As the Deer Panteth As the deer panteth

    And I long to worship thee. I love you more than gold or silver, only you can satisfy. You alone are the real joy giver. and the apple of my eye. You alone are my strength, my shield. To you...
  • Aucun titre de diapositive - Sterilisation-hopital.com

    Aucun titre de diapositive - Sterilisation-hopital.com

    Enclouage du tibia à foyer fermé Indiquez quels sont les avantages apportés par la solution de l'enclouage à foyer fermé, pour une fracture du fémur au tiers moyen : Qualité du cal osseux après enclouage du tibia à foyer fermé...
  • www.rcs.rome.ga.us

    www.rcs.rome.ga.us

    Tomorrow morning… Some sessions are required (i.e., PreK, media specialists, new K-6 math teachers). Most are suggested. Teachers will need to take 9 hours of professional development over the course of 3 in-service days (tomorrow, one in February, and one...
  • Rise and Fall of NIXON - US History

    Rise and Fall of NIXON - US History

    Arial Calibri Office Theme Rise and Fall of Richard Nixon Nixon Graphic Organizer Example: 1969 1972 Watergate 1973 1974 Design an epitaph for Richard M. Nixon An epitaph is something engraved on the tombstone of an individual.
  • BIOFUELS (Part 2) Diesel Engines Both diesel engines

    BIOFUELS (Part 2) Diesel Engines Both diesel engines

    Both diesel engines and gasoline engines covert fuel into energy through a series of small explosions or combustions. The major difference between diesel and gasoline is the way these explosions happen. In gas engines, fuel is mixed with air, compressed...