INTR TO COMPUT LING
INTR TO COMPUT LING LING 472
Popular in Course
Popular in Linguistics
This 56 page Class Notes was uploaded by Kurtis Spencer I on Wednesday September 9, 2015. The Class Notes belongs to LING 472 at University of Washington taught by Staff in Fall. Since its upload, it has received 7 views. For similar materials see /class/192184/ling-472-university-of-washington in Linguistics at University of Washington.
Reviews for INTR TO COMPUT LING
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/09/15
May 12 2008 Chapter I I Feature structures Uni cation Overview Leftovers Earley parser Problems with CFG One solution feature structure and uni cation An aside on modeling language Practice with uni cation pizza Concepts relating to feature structures Feature structures in the grammar Using types to capture linguistic generalizations The Earley Chart Parser Outline 0 Add the initial S y gt 08 00 to the chart at position 0 a Loop for each of the rest of the cells in the chart a PREDICTOR Expand nonpreterminals o SCANNER Check if preterminals match current word COMPLETER Check if completed edges complete others The Earley Chart Parser Features a One pass through the chartsentence o Recognizer which can be modi ed into a parser o Topdown unidirectional exhaustive as parser Discussion How does the Earley algorithm solve these problems a Ambiguity o Inef cient reparsing 0f subtrees 0 In nite loops with leftrecursive grammars o NP gt NP PP o The eat on the mat by the door slept Overview Leftovers Earley parser Problems with CFG One solution feature structure and uni cation An aside on modeling language Practice with uni cation pizza Concepts relating to feature structures Feature structures in the grammar Using types to capture linguistic generalizations Problems with CF G o Potentially arbitrary rules D gt S VP 0 Gets clunky quickly with crosscutting properties we ll return to this a Not quite powerful enough for natural languages Solution Replace atomic node labels with feature structures Some grammatical theories which explicitly use feature structures and uni cation o GPSG Generalized Phrase Structure Grammar o HPSG Headdriven Phrase Structure Grammar httphpsgstanfordedu o LFG Lexical Functional Grammar httpWwwlfgstanfordedulfg a Construction Grammar http WWW constructiongrammar org 0 Combinatory Categorial Grammar 8 Modeling language HPSG Two kinds of modeling 0 Speakers internalized grammars a Set of possible English sentences Modeling language HPSG Three things involved in modeling a Realworld entities o Models o Descriptions of models 10 Feature Structure Descriptions FEATURE1 VALUE1 FEATURE2 VALUE2 LFEATURETL VALUEnJ 11 A Pizza Type Hierarchy pizzathing i pizza toppingset CRUST OLDES 1 TOPPINGS ONIONS MUSHROOMSJ vegetarian nonvegetarian SAUSAGE PEPPERONI HAM 12 TYPE FEATURESVALUES IST pizzathing Pm l CRUST hmktmmsumampdl Pm m TOPPINGS toppingset J toppingset OLIVES pizzathing C HONS h MUSHROOMS H vegetarian toppingset nonvegetarian S AUS AGE toppingset 4 PEPPERONI HAM 13 Type Hierarchies A type hierarchy o states what kinds of objects we claim exist the types a organizes the objects hierarchically into classes with shared properties the IST relations a states What general properties each kind of object has the feature and feature value declarations l4 Pizza Descriptions and Pizza Models pizza 1 CRUST thick vegetarian 1 l TOPPINGS OLIVES ONIONS JJ How many fully resolved pizza models satisfy this description 15 Pizza Descriptions and Pizza Models pizza 1 CRU S T thick I vegetarian I OLIVES 1 TOPPINGS ONIONS H 0N10NSgtltMUSHROOMs gtgt lt CRUST thick lt TOPPINGS lt OLIVES gt L lt CRUST thick TOPPINGS OLIVES gt lt ltON10NSgtltMUSHR00MSgtgt 16 Pizza Descriptions and Pizza Models pizza 1 ICRUST thick I vegetarian 1 l TOPPINGS OLIVES L ONIONS JJ How many pizzasin theworld do the pizza models correspond to type token distinction applies to sentences as well 17 Uni cation pizza 1 plZZCl CRUST th1ck 1 I lLl OLIVES I OLIVES I TOPPINGS TOPPINGS ONIONS L HAM J 18 Uni cation plZZCl 1 I CRUST thick I I OLIVES 1 I ITOPPINGS ONIONS l L HAM J 19 Uni cation pizza I pizza I I CRUST thick I I CRUST thin I U I OLIVES I I OLIVES I TOPPINGS TOPPINGS I I I ONIONS I 20 Uni cation 21 Uni cation pizza CRU S T thick TOPPINGS vegetarianj pizza CRUST thick u OLIVES I HAM J ITOPPINGS 22 Uni cation 23 Uni cation pizza CRU S T thick TOPPINGS vegetarianj pizza CRUST thick u OLIVES I J ITOPPINGS 24 Uni cation 25 A Pizza Type Hierarchy pizzathing i pizza toppingset CRUST OLDES 1 TOPPINGS ONIONS MUSHROOMSJ vegetarian nonvegetarian SAUSAGE PEPPERONI HAM 26 A New Theory of Pizzas CRUST thick thin stuffed I ONEHALF toppingset I OTHERHALF toppingset J pizza 27 Uni cation Pizza 1 pizza 1 J ONIONS ONIONS ONEHALF OTHERHALF L OLIVES J L OLIVES 28 Uni cation pizza ONIONS ONEHALF LOLIVES ONIONS OTHERHALF LOLIVES 29 Identity Constraints Tags pizza CRUST thin OLIVES 1 ONEHALF ONIONS J OLIVES 1 OTHERHALF ONIONS J 30 Uni cation pizza pizza ONIONS i 1 ONEHALF MUSHROOMS I OLIVES OTHERHALF I I L OLIVES J OTHERHALF J 31 Uni cation pizza ONIONS OLIVES MUSHROOMS J ONEHALF I l OTHERHALF 32 Uni cation pizza ONEHALF ONIONS 1 OTHERHALF OLIVES MUSHROOMS J I l L 33 Uni cation pizza 1 plZZCl ONIONS ONEHALF U I OLIVES J I ONEHALF OTHERHALF vegetarian J 34 SAUSAGE 1 HAM Uni cation 35 Concepts relating to feature structures Underspeci cation Subsumption o De nes a partialorder a Mutual nonsubsumption does not entail incompatibility a Mutual subsumption does entail equality Monotonicity Order independence 36 Feature structures as DAGs Features label arcs Nodes are associated with subDAGs or atomic values With types each node is labeled with a type Identity constraints represented by reentrancy 37 Activity Represent as a DAG pizza 1 ONEHALF l ONIONS l IOTHERHALF OLIVES 1 L MUSHROOMS JJ 38 Feature structures in the grammar Associate complex feature structures with both lexical items and instances of grammatical categories a Guide the composition of feature structures for larger grammatical constituents based on the feature structures of their component parts a Enforce compatibility constraints between speci ed parts of grammatical constructions 39 Example I Subjectverb agreement What does it mean for the subject and the verb to agree How would we handle agreement in plain CF G What kind of information would it be useful to encode in features Two ways to make the rules use the features a Multiple rules with feature speci ed a Identity constraints What do each of those look like 40 Example 2 Subcategorization What is subcategorization eg verb subcategorization How would we handle agreement in plain CF G What kind of information would it be useful to encode in features Two ways to make the rules use the features a Multiple rules with feature speci ed a Identity constraints What do each of these look like 41 Example 3 Subcategorization and agreement a How would we handle both agreement and subcategorization together in plain CFG Are our new rules for each compatible already or do they need modi cation 42 Using types to capture linguistic generalizations o The lexicon is both the repository of idiosyncrasy and full of redundancy o Rather than state VAL tr or SUBCAT NP gt on every single transitive verb 0 Create a type transitiveverb subject to that constraint and let individual verbs be instances of that type 43 Using types to capture linguistic generalizations 0 Allow for intermediate generalizations as well transitiveverb A stricttransitive a itransitive pptransitive 44 Using types to capture linguistic generalizations person number V A 1st 2nd 3rd sing plur n0n3sgverb NUMB ER sing 1 IL 1 st PERSON 2nd J NUMBER plur 45 Using types to capture linguistic generalizations pernum I r3sg n n3sg sg sg n nIsg 191 sg 2p nonSsg verb AGR PERNUM n0n3sg Summary Feature structures can be used to express nergrained details within grammatical categories Feature structures can be combined with uni cation Feature structures allow grammar writers to capture more generalizations Types allow grammar writers to capture even more generalizations 47 Next time 0 Implementing uni cation 0 Integrating uni cation into the parser o More linguistic examples 48 Long distance dependencies Questions 0 Which book did you say that you thought Kim liked 0Which book did you say that you thought Kim liked The Wizard ofOZ a To which author has Kim written several fan letters 0 Which author has Kim written several fan letters to 0To which author has Kim written several fan letters to o Which author has Kim written several fan letters 49 Long distance dependencies English focus movement a Bagels 1 like 0 Bagels 1 know Kim likes 0Bagels I know Kim likes lox o Of bagels I know Kim is fond 0 Bagels 1 know Kim is fond of 0Bagels I know Kim is fond oOf bagels I know Kim is fond of 50 Other long distance dependencies Relative clauses This is the house that Jack built Tough adjectives This book is easy to read Tough nouns Those shoes are a challenge to walk in Multiple LDDs Violins this well crafted these sonatas are easy to play on 51 Three pieces of an LDD Bottom recording the fact that something s missing a Middle propagating the information that something s missing a Top matching a ller to the gap and sealing off the LDD 52 Startgap A traceless bottom startgap rule unary head initial sg amp SPR spr COMPS comps GAP lt1 gap lgt ARGS lt SPR spr COMPS lt gap comps gt gt 53 Middle Passing up GAP values in unary rules unary rule pg unary rule amp GAP gap REL rel ARGS lt GAP gap REL rel gt 54 Middle Passing up GAP values in binary rules binary rule pg binary rule amp GAP LIST gfront LAST gtail ARGS lt GAP LIST gfront LAST gmiddle GAP LIST gmiddle LAST gtail gt 55 Top Pairing a ller with the gap filler head rule binary head final amp HEAD verb amp head SPR ltgt COMPS ltgt GAP lt1 lgt ARGS lt gap amp phrase amp SPR ltgt COMPS ltgt HEAD head SPR ltgt COMPS ltgt GAP lt1 gap lgt gt 56