CL 07 lec6 2 15

Information about CL 07 lec6 2 15

Published on November 15, 2007

Author: Roxie

Source: authorstream.com

Content

LIN6932 Topics in Computational Linguistics:  LIN6932 Topics in Computational Linguistics Lecture 6: Grammar and Parsing (I) February 15, 2007 Hana Filip Outline for Grammar/Parsing:  Outline for Grammar/Parsing Context-Free Grammars (CFG) and Constituency Some common CFG phenomena for English Sentence-level constructions NP, PP, VP Coordination Subcategorization Levels of complexity in grammars and automata: The Chomsky hierarchy Top-down and Bottom-up Parsing Earley Parsing Quick sketch of probabilistic parsing Review:  Review Parts of Speech Basic syntactic/morphological categories that words belong to Part of Speech tagging Assigning parts of speech to all the words in a sentence Syntax:  Syntax Syntax: from Greek syntaxis, “setting out together, arrangement’ Refers to the way words are arranged together, and their relationships Distinction: Prescriptive grammar: how people ought to talk Descriptive grammar: how they do talk Goal of syntax is to model the knowledge that people unconsciously have about the grammar of their native language Syntax:  Syntax Why should you care? Grammar checkers Question answering Information extraction Machine translation 4 key ideas of syntax:  4 key ideas of syntax Constituency Grammatical relations Subcategorization Lexical dependencies Plus one part we won’t have time for: Movement/long-distance dependency Context-Free Grammars:  Context-Free Grammars Capture constituency and ordering Ordering: What are the rules that govern the ordering of words and bigger units in the language? Constituency: How words group into units and how the various kinds of units behave Constituency:  Constituency Noun phrases (NPs) Three parties from Brooklyn A high-class spot such as Mindy’s The Broadway coppers They Harry the Horse The reason he comes into the Hot Box How do we know these form a constituent? They can all appear before a verb: Three parties from Brooklyn arrive… A high-class spot such as Mindy’s attracts… The Broadway coppers love… They sit… Constituency (II):  Constituency (II) They can all appear before a verb: Three parties from Brooklyn arrive… A high-class spot such as Mindy’s attracts… The Broadway coppers love… They sit But individual words can’t always appear before verbs: *from arrive… *as attracts… *the is *spot is… Must be able to state generalizations like: Noun phrases occur before verbs Constituency (III):  Constituency (III) Preposing and postposing: On September 17th, I’d like to fly from Atlanta to Denver I’d like to fly on September 17th from Atlanta to Denver I’d like to fly from Atlanta to Denver on September 17th. But not: *On September, I’d like to fly 17th from Atlanta to Denver *On I’d like to fly September 17th from Atlanta to Denver CFG Examples:  CFG Examples S -> NP VP NP -> Det NOMINAL NOMINAL -> Noun VP -> Verb Det -> a Noun -> flight Verb -> left CFGs:  CFGs S -> NP VP This says that there are units called S, NP, and VP in this language That an S consists of an NP followed immediately by a VP Doesn’t say that that’s the only kind of S Nor does it say that this is the only place that NPs and VPs occur Generativity:  Generativity As with FSAs you can view these rules as either analysis or synthesis machines Generate strings in the language Reject strings not in the language Impose structures (trees) on strings in the language Derivations:  Derivations A derivation is a sequence of rules applied to a string that accounts for that string Covers all the elements in the string Covers only the elements in the string Derivations as Trees:  Derivations as Trees CFGs more formally:  CFGs more formally A context-free grammar has 4 parameters (“is a 4-tuple”) A set of non-terminal symbols (“variables”) N A set of terminal symbols  (disjoint from N) A set of productions P, each of the form A ->  Where A is a non-terminal and  is a string of symbols from the infinite set of strings (  N)* A designated start symbol S Defining a CF language via derivation:  Defining a CF language via derivation A string A derives a string B if A can be rewritten as B via some series of rule applications More formally: If A -> is a production of P  and  are any strings in the set (  N)* Then we say that A directly derives  Or A   Derivation is a generalization of direct derivation Let 1, 2, … m be strings in (  N)*, m>= 1, s.t. 1 2, 2 3… m-1 m We say that 1derives m or 1* m We then formally define language LG generated by grammar G As set of strings composed of terminal symbols derived from S LG = {w | w is in * and S * w} Parsing:  Parsing Parsing is the process of taking a string and a grammar and assigning correct trees to input strings Correct tree: a tree that covers all and only the elements of the input and has an S node at the top Context?:  Context? The notion of context in CFGs has nothing to do with the ordinary meaning of the word context in language. All it means is that the non-terminal on the left-hand side of a rule is out there all by itself (free of context) A -> B C Means that I can rewrite an A as a B followed by a C regardless of the context in which A is found Key Constituents (English):  Key Constituents (English) Sentences Noun phrases Verb phrases Prepositional phrases Sentence-Types:  Sentence-Types Declaratives: A plane left S -> NP VP Imperatives: Leave! S -> VP Yes-No Questions: Did the plane leave? S -> Aux NP VP WH Questions: When did the plane leave? S -> WH Aux NP VP NPs:  NPs NP -> Pronoun I came, you saw it, they conquered NP -> Proper-Noun Los Angeles is west of Texas NP -> Det Noun The president NP -> Nominal Nominal -> Noun Noun A morning flight to Denver PPs:  PPs PP -> Preposition NP From LA To Boston On Tuesday With lunch Recursion:  Recursion We’ll have to deal with rules such as the following where the non-terminal on the left also appears somewhere on the right (directly). NP -> NP PP [[The flight] [to Boston]] VP -> VP PP [[departed Miami] [at noon]] Recursion:  Recursion Of course, this is what makes syntax interesting flights from Denver Flights from Denver to Miami Flights from Denver to Miami in February Flights from Denver to Miami in February on a Friday Flights from Denver to Miami in February on a Friday under $300 Flights from Denver to Miami in February on a Friday under $300 with lunch Etc. Recursion:  Recursion Of course, this is what makes syntax interesting [[flights] [from Denver]] [[[Flights] [from Denver]] [to Miami]] [[[[Flights] [from Denver]] [to Miami]] [in February]] [[[[[Flights] [from Denver]] [to Miami]] [in February]] [on a Friday]] Etc. Implications of recursion and context-freeness:  Implications of recursion and context-freeness If you have a rule like VP -> V NP It only cares that the thing after the verb is an NP. It doesn’t have to know about the internal affairs of that NP The Point:  The Point VP -> V NP I hate flights from Denver Flights from Denver to Miami Flights from Denver to Miami in February Flights from Denver to Miami in February on a Friday Flights from Denver to Miami in February on a Friday under $300 Flights from Denver to Miami in February on a Friday under $300 with lunch Bracketed Notation:  Bracketed Notation [S [NP [PRO I] [VP [V prefer [NP [NP [Det a] [Nom [N morning] [N flight]]]] Coordination Constructions:  Coordination Constructions S -> S and S John went to NY and Mary followed him NP -> NP and NP VP -> VP and VP … In fact the right rule for English is X -> X and X Other Syntactic stuff:  Other Syntactic stuff Grammatical Relations Subject I booked a flight to New York The flight was booked by my agent. Object I booked a flight to New York Complement I said that I wanted to leave Problems:  Problems Agreement Subcategorization Movement (for want of a better term) Agreement:  Agreement This dog Those dogs This dog eats Those dogs eat *This dogs *Those dog *This dog eat *Those dogs eats Possible CFG Solution:  Possible CFG Solution S -> NP VP NP -> Det Nominal VP -> V NP … SgS -> SgNP SgVP PlS -> PlNp PlVP SgNP -> SgDet SgNom PlNP -> PlDet PlNom PlVP -> PlV NP SgVP ->SgV Np … CFG Solution for Agreement:  CFG Solution for Agreement It works and stays within the power of CFGs But its ugly (loss of generalization) And it doesn’t scale all that well Subcategorization:  Subcategorization Verbs have preferences for the number and syntactic kinds of constituents they co-occur with Sneeze: John sneezed intransitive verb Find: Please find [a flight to NY]NP transitive verb Give: Give [me]NP[a cheaper fare]NP ditransitive verb Help: Can you help [me]NP[with a flight]PP DO IO/Oblique Prefer: I prefer [to leave earlier]TO-VP VP complement Said: You said [United has a flight]S sentential complement … Subcategorization:  Subcategorization But not: *John sneezed the book *I prefer United has a flight *Give with a flight Subcategorization expresses the constraints that a lexical predicate places on the number and syntactic kinds of arguments it wants to take (occur with) So far we have only considerate one type of lexical predicate: verb Nouns, adjectives and prepositions also take arguments So?:  So? So the various CFG rules for VPs overgenerate. They permit the presence of strings containing verbs and arguments that don’t go together For example VP -> V NP predicts that Sneezed the book is a VP since “sneeze” is a verb and “the book” is a valid NP Forward Pointer:  Forward Pointer It turns out that verb subcategorization facts will provide a key element for semantic analysis (determining who did what to who in an event). Possible CFG Solution:  Possible CFG Solution VP -> V VP -> V NP VP -> V NP PP … VP -> IntransV VP -> TransV NP VP -> TransVwPP NP PP … Movement:  Movement Core example My travel agent booked the flight Movement:  Movement Core example [[My travel agent]NP [booked [the flight]NP]VP]S I.e. “book” is a straightforward transitive verb. It expects a single NP arg as the subject and a single NP arg within the VP Movement - Long Distance Dependencies:  Movement - Long Distance Dependencies What about? Which flight do you want me to have the travel agent book __? The direct object argument to “book” isn’t appearing in the right place. It is a long way from where it originally appeared And note that it is separated from its verb by 2 other verbs. CFGs: a summary:  CFGs: a summary CFGs appear to be just about what we need to account for a lot of basic syntactic structure in English But there are problems That can be dealt with adequately, although not elegantly, by staying within the CFG framework. There are simpler, more elegant, solutions that take us out of the CFG framework (beyond its formal power) Syntactic theories: HPSG, LFG, CCG, Minimalism, etc

Related presentations


Other presentations created by Roxie

Apricot 2004 Sinkholes
07. 10. 2007
0 views

Apricot 2004 Sinkholes

Mattel
02. 11. 2007
0 views

Mattel

Option
17. 04. 2008
0 views

Option

Value of Nonpartisan
14. 04. 2008
0 views

Value of Nonpartisan

stifelcapital
13. 04. 2008
0 views

stifelcapital

m lecture 1 2007
10. 04. 2008
0 views

m lecture 1 2007

renewable report summary
09. 04. 2008
0 views

renewable report summary

Costa Rica
07. 04. 2008
0 views

Costa Rica

pptrick
30. 03. 2008
0 views

pptrick

060516202103
28. 03. 2008
0 views

060516202103

field to flour
04. 10. 2007
0 views

field to flour

wolff
27. 11. 2007
0 views

wolff

danielle
11. 12. 2007
0 views

danielle

WP6 CurriculumDevelopment
01. 11. 2007
0 views

WP6 CurriculumDevelopment

paris 23jan
02. 11. 2007
0 views

paris 23jan

why b entrepreneur
07. 11. 2007
0 views

why b entrepreneur

Miss Earth 2007
13. 11. 2007
0 views

Miss Earth 2007

Lecture15 Discourse
20. 08. 2007
0 views

Lecture15 Discourse

oasis case study
20. 08. 2007
0 views

oasis case study

4121
20. 08. 2007
0 views

4121

mediaplan
20. 08. 2007
0 views

mediaplan

evaluating quant research
20. 08. 2007
0 views

evaluating quant research

soren mateu kast prop13
20. 08. 2007
0 views

soren mateu kast prop13

The Given New Principle
14. 12. 2007
0 views

The Given New Principle

FadorFact
20. 08. 2007
0 views

FadorFact

Socia lContent
11. 08. 2007
0 views

Socia lContent

Staff Wellness
11. 08. 2007
0 views

Staff Wellness

SAR presentation 2005 2006
11. 08. 2007
0 views

SAR presentation 2005 2006

Typhoid 2004b
11. 08. 2007
0 views

Typhoid 2004b

Presentation Al Jisr
23. 10. 2007
0 views

Presentation Al Jisr

large animal power point
03. 10. 2007
0 views

large animal power point

patents
03. 10. 2007
0 views

patents

meta analysis 09 2006
20. 08. 2007
0 views

meta analysis 09 2006

li2 2007 gender
09. 07. 2007
0 views

li2 2007 gender

Picture Chinese in Your Future
12. 10. 2007
0 views

Picture Chinese in Your Future

socratesswissranking 28 11 06
18. 10. 2007
0 views

socratesswissranking 28 11 06

Nonverbal
09. 07. 2007
0 views

Nonverbal

MJ
09. 07. 2007
0 views

MJ

Milk Fortification
09. 07. 2007
0 views

Milk Fortification

MakeUp
09. 07. 2007
0 views

MakeUp

allexp 052404
05. 10. 2007
0 views

allexp 052404

lamm1
01. 01. 2008
0 views

lamm1

schindel
11. 08. 2007
0 views

schindel

BuildingStrategyMaps v5
24. 02. 2008
0 views

BuildingStrategyMaps v5

03n 0312 ts00002 vol1
29. 02. 2008
0 views

03n 0312 ts00002 vol1

OMA TP 2003 0354
20. 08. 2007
0 views

OMA TP 2003 0354

Digital Reference Shelf
22. 11. 2007
0 views

Digital Reference Shelf

anspaugh
23. 11. 2007
0 views

anspaugh

Neolithic Europe
26. 03. 2008
0 views

Neolithic Europe

KAT PRESENTATION
21. 11. 2007
0 views

KAT PRESENTATION

Prezentacja o rekrutacji
18. 03. 2008
0 views

Prezentacja o rekrutacji

Met en zonder MakeUp Antwoord
09. 07. 2007
0 views

Met en zonder MakeUp Antwoord

media body image
09. 07. 2007
0 views

media body image

Diario Intimo de los gatos 1913
19. 06. 2007
0 views

Diario Intimo de los gatos 1913

globus
19. 06. 2007
0 views

globus

Article VIII
21. 09. 2007
0 views

Article VIII

Montreal Summer School2005
31. 12. 2007
0 views

Montreal Summer School2005

El Dulce Aroma Del Cafe 2118
19. 06. 2007
0 views

El Dulce Aroma Del Cafe 2118

El Caballo Y Cerdo 2117
19. 06. 2007
0 views

El Caballo Y Cerdo 2117

El pajaro de la paz 1853
19. 06. 2007
0 views

El pajaro de la paz 1853

El genio 2046
19. 06. 2007
0 views

El genio 2046

El buen uso de los espejos
19. 06. 2007
0 views

El buen uso de los espejos

El ladrillazo 2092
19. 06. 2007
0 views

El ladrillazo 2092

2005 JRC Workshop Smrz
06. 03. 2008
0 views

2005 JRC Workshop Smrz

El camino de las estrellas 2075
19. 06. 2007
0 views

El camino de las estrellas 2075

El sustento de la pareja 1935
19. 06. 2007
0 views

El sustento de la pareja 1935

CJ Addiction
21. 09. 2007
0 views

CJ Addiction

BLUE BEAUTY
16. 06. 2007
0 views

BLUE BEAUTY

Biler Kvinder
16. 06. 2007
0 views

Biler Kvinder

2CF Japanese Fishing Story
16. 06. 2007
0 views

2CF Japanese Fishing Story

2007 0505 Fishoree
16. 06. 2007
0 views

2007 0505 Fishoree

2006 Function Presentation
16. 06. 2007
0 views

2006 Function Presentation

El mejor doctor 2076
19. 06. 2007
0 views

El mejor doctor 2076

BWands
04. 01. 2008
0 views

BWands

El Hombre Perfecto 2059
19. 06. 2007
0 views

El Hombre Perfecto 2059

Maria project
09. 07. 2007
0 views

Maria project

13 14
14. 11. 2007
0 views

13 14

El hipopotamo y la tortuga 2119
19. 06. 2007
0 views

El hipopotamo y la tortuga 2119

Ejercicios Espirituales 2116
19. 06. 2007
0 views

Ejercicios Espirituales 2116

CSU Presentation
20. 08. 2007
0 views

CSU Presentation

Jeff
28. 12. 2007
0 views

Jeff

El Respeto 2120
19. 06. 2007
0 views

El Respeto 2120

17579
20. 08. 2007
0 views

17579

Peru Seminar
20. 08. 2007
0 views

Peru Seminar

temptations
11. 08. 2007
0 views

temptations

SAB SA CorpStdPgm05608
21. 09. 2007
0 views

SAB SA CorpStdPgm05608

Edificios colmena 1993
19. 06. 2007
0 views

Edificios colmena 1993

eval
20. 08. 2007
0 views

eval

Takahiro Sato
29. 11. 2007
0 views

Takahiro Sato

tfpresent
11. 08. 2007
0 views

tfpresent

LMK preze
09. 07. 2007
0 views

LMK preze

pods03
29. 10. 2007
0 views

pods03

Social Engineering ISACA RIFE v5
20. 08. 2007
0 views

Social Engineering ISACA RIFE v5

Volkow505
20. 08. 2007
0 views

Volkow505

Towards Extracting Personality 4
11. 08. 2007
0 views

Towards Extracting Personality 4

Dios y el Zodiaco 1737
19. 06. 2007
0 views

Dios y el Zodiaco 1737

sanford poster
11. 08. 2007
0 views

sanford poster