CMSC 723 LING 645 Intro to Computational Linguistics November 10 2004 Lecture 10 Dorr CFG s Finish Chapter 9 Parsing Chapter 10 Prof Bonnie J Dorr Dr Christof Monz TA Adam Lee What Issues Arise in Creating Grammars Agreement Subcategorization Movement Agreement Simple Examples This dog Those dogs Those dog This dogs More complicated examples Do any flights stop in Chicago Does Delta fly from Atlanta to Boston Do I get dinner on this flight What flights leave in the morning What flight leave in the morning Agreement Nouns Nominal Noun Noun Noun NominalSg NounSg NounSg NounSg NominalPl NounPl NounPl NounPl Subj Verb Agreement S Aux NP VP S Aux3sg NP3sg VP S Auxnon3sg NPnon3sg VP Lexical items NounSg flight NounPl flights Aux3sg does has can Auxnon3sg do have can Agreement Features Propagate Downard NP3sg Det Card Ord Quant AP NominalSg NPnon3sg Det Card Ord Quant AP NominalPl What s wrong with this picture Combinatorial explosion Other feature based expansions Loss of Generalization Subcategorization Verbs have preferences for the kinds of constituents they co occur with For example VP Verb disappear VP Verb NP prefer a morning flight VP Verb NP PP leave Boston in the morning VP Verb PP leaving on Thursday But not I disappeared the cat Sentential complements Example You VP V said S there were two flights that were the cheapest You VP V said S you had a two hundred sixty six dollar fare VP V Tell NP me S how to get from the airport in Philadelphia to downtown Rule VP Verb S Other VP Constituents A VP can be the constituent of another VP VP Verb VP I want VP to fly from Milwaukee to Orlando I m trying VP to find a flight that goes from Pittsburgh to Denver next Friday Verbs can also be followed by particles to form a phrasal verb VP Verb Particle take off Why do we need Subcategorization Important observation while a verb phrase can have many possible kinds of constituents not every verb is compatible with every verb phrase Example verb want can be used With a NP complement I want a flight With an infinitive VP complement I want to fly to Dallas But verb find cannot take such a VP complement I find to fly to Dallas Subcategorization Frame NP NP NP PPfrom PPto NP PPwith VPto VPbrst S Verb eat sleep prefer find leave show give fly travel help load prefer want need can would might mean Example I want to eat Find NP the flight from Pittsburgh to Boston Show NP me NP airlines with flights from Pittsburgh I would like to fly pp from Boston pp to Philadelphia Can you help NP me pp with a flight I would prefer VPto to go by United airlines I can VPbrst go from Boston Does this mean S AA has a hub in Boston Auxiliaries Examples Modals can could may might Perfect have Progressive be Passive be What are their subcategories Ordering modal perfect progressive passive e g might have been prevented Movement I looked up his grade I looked his grade up John put the book on the table What did John put on the table Long distance dependencies Grammar Equivalence and Normal Form Weak equivalence Strong equivalence Chomsky Normal Form CNF A B C or A a CNF Example Convert to Chomsky Normal Form CNF S aYX X aX b Y Ya b Why do care about grammar We need grammars for parsing Note Parsing is the topic we will cover next What Linguistic Representations are necessary for parsing Words Classes groups of words which behave similarly Function Content P O S Nouns Verbs Adjectives Prepositions Constituents Groupings of words into larger units which behavior similarly and have a particular p o s as their head Phrases NP headed by Noun VP PP Analyzing Language in Terms of these Representations Morphological parsing analyze words into morphemes and affixes rule based FSAs FSTs POS Tagging Syntactic parsing identify component parts and how related to see if a sentence is grammatical to assign a semantic structure Syntactic Parsing Declarative formalisms like CFGs define the legal strings of a language but don t specify how to recognize or assign structure to them Parsing algorithms specify how to recognize the strings of a language and assign each string one or more syntactic structures Parse trees useful for grammar checking semantic analysis MT QA information extraction speech recognition and almost every task in NLP CFG for Fragment of English G0 Parse Tree for Book that flight using G0 Parsing as a Search Problem Searching FSAs Finding the right path through the automaton Search space defined by structure of FSA Searching CFGs Finding the right parse tree among all possible parse trees Search space defined by the grammar Constraints provided by the input sentence and the automaton or grammar Two Search Strategies Top Down Search for tree starting from S until input words covered Bottom Up Start with words and build upwards toward S Top Down Parser Builds from the root S node to the leaves Assuming we build all trees in parallel Find all trees with root S Next expand all constituents in these trees rules Continue until leaves are pos Candidate trees failing to match pos of input string are rejected Top Down Rationalist Tradition Expectation driven Goal Build tree for input starting with S Top Down Search Space for G0 Bottom Up Parsing Parser begins with words of input and builds up trees applying G0 rules whose right hand sides match Book that flight N Det N V Det N Book that flight Book that flight Book ambiguous Parse continues until an S root node reached or no further node expansion possible Bottom Up Empiricist Tradition Data driven Primary consideration Lowest sub trees of final tree must hook up with words in input Expanding Bottom Up Search Space for Book that flight Comparing Top Down and Bottom Up Top Down parsers never explore illegal parses e g can t form an S but waste time on trees that can never match the input Bottom Up parsers never explore trees inconsistent with input but waste time exploring illegal parses no S root For both how to explore the search space Pursuing all parses in parallel or Which node to expand next Which rule to apply next Search Strategy and Search Control Parallel Explore all possible trees in parallel Depth first search Agenda of search states expand search space incrementally exploring most recently generated state tree each time When you reach a state tree inconsistent with input backtrack to most recent unexplored state tree Which node to expand Leftmost Which grammar rule to use Order in the grammar Basic Algorithm for Top Down Depth First Left Right Strategy Initialize