Lecture 11Limits of CFGsSlide 3CFG SolutionSlide 5Feature StructuresSlide 7Slide 8Graphical Notation for Feature StructuresReentrant StructuresOperations on Feature StructuresSlide 12Features, Unification and GrammarsSlide 14Agreement in EnglishSlide 16Head FeaturesSubcategorizationSlide 19Slide 20Slide 21Long-Distance DependenciesHow can we parse with feature structures?Unification and Earley ParsingSlide 25Summing UpCS 4705Lecture 11Feature Structures and Unification ParsingLimits of CFGs•Recall that there are several things CFGs don’t handle elegantly:–Agreement (A cat sleeps. Cats sleep.)S  NP VPNP  Det NomBut these rules overgenerate, allowing, e.g., *A cat sleep…–Subcategorization (Cats dream. Cats eat cantaloupe.)VP  VVP  V NPBut these also allow *Cats dream cantaloupe. •We need to constrain the grammar rules to enforce e.g. number agreement and subcategorization differences•We’ll do this with feature structures and the constraint-based unification formalismCFG Solution•Encode constraints into the non-terminals–Noun/verb agreementS SgSS  PlSSgS  SgNP SgVPSgNP  SgDet SgNom–Verb subcat:IntransVP  IntransVTransVP  TransV NP•But this means huge proliferation of rules…•An alternative:–View terminals and non-terminals as complex objects with associated features, which take on different values–Write grammar rules whose application is constrained by tests on these features, e.g.S  NP VP (only if the NP and VP agree in number)Feature Structures•Sets of feature-value pairs where:–Features are atomic symbols–Values are atomic symbols or feature structures–Illustrated by attribute-value matrixnFeatureFeatureFeature...21nValueValueValue....21•Number feature•Number-person features•Number-person-category features (3sgNP)NumSGPersNumCat3SGNPPersNum3SG–How does this improve over the CFG solution?•Feature values can be feature structures themselves–Useful when certain features commonly co-occur, e.g. number and person–Feature path: path through structures to value (e.g. Agr  Num  SGAgrCat3PersSGNumNPGraphical Notation for Feature StructuresReentrant Structures•Feature structures may also contain features that share some feature structure as a value•Numerical indices indicate the shared values131AgrSubjPersSGNumAgrHeadSCatOperations on Feature Structures•What will we need to do to these structures?–Check the compatibility of two structures–Merge the information in two structures•We can do both using unification•We say that two feature structures can be unified if the component features that make them up are compatible–[Num SG] U [Num SG] = [Num SG]–[Num SG] U [Num PL] fails!–[Num SG] U [Num []] = [Num SG]•[Num SG] U [Pers 3] =•Structure are compatible if they contain no features that are incompatible •Unification of two feature structures:–Are the structures compatible?–If so, return the union of all feature/value pairs•A failed unification attempt3PersSGNum131AgrSubjPersSGNumAgr33PersPLNumAgrSubjPersPlNumAgrUFeatures, Unification and Grammars•How do we incorporate feature structures into our grammars?–Assume that constituents are objects which have feature-structures associated with them–Associate sets of unification constraints with grammar rules –Constraints must be satisfied for rule to be satisfied•For a grammar rule 0  1 …n–<i feature path> = Atomic value–<i feature path> = <j feature path>•To enforce subject/verb number agreementS  NP VP<NP NUM> = <VP NUM>Agreement in English•We need to add PERS to our subj/verb agreement constraintThis cat likes kibble.S  NP Vp<NP AGR> = <VP AGR>Do these cats like kibble?S  Aux NP VP<Aux AGR> = <NP AGR>•Det/Nom agreement can be handled similarlyThese cats This catNP  Det Nom<Det AGR> = <Nom AGR><NP AGR> = <Nom AGR>•And so on for other constituents and rulesHead Features•Features of most grammatical categories are copied from head child to parent (e.g. from V to VP, Nom to NP, N to Nom, …)•These normally written as ‘head’ features, e.g.VP  V NP<VP HEAD> = <V HEAD>NP  Det Nom<NP HEAD> = <Nom HEAD><Det HEAD AGR> = <Nom HEAD AGR>Nom  N<Nom HEAD> = <N HEAD>Subcategorization•Recall: Different verbs take different types of argument–Solution: SUBCAT feature, or subcategorization framese.g. Bill wants to eat.INFVFORMHEADVPCATNPCATSUBCATHEADVCATwantORTH,•But there are many phrasal types and so many types of subcategorization frames, e.g.–believe –believe [VPrep in] [NP ghosts]–believe [NP my mother]–believe [Sfin that I will pass this test]–believe [Swh what I see] ...•Verbs also subcategorize for subject as well as object types ([Swh What she wanted] seemed clear.)•And other p.o.s. can be seen as subcategorizing for various arguments, such as prepositions, nouns and adjectives (It was clear [Sfin that she was exhausted])•NB: p.o.s. that subcategorize similarly define rough classes e.g. verb categories like transfer verbs and subcat frame relationships within verb classes are called alternations–George gave Martha a letter [NP NP]–George gave a letter to Martha [NP PP]Long-Distance Dependencies•What happens when a verb’s arguments are not in the VP?–What meals does the restaurant serve?Wh-NP fills a slot in serveS --> wh-NP Aux NP VP•How to solve?–Gap list: GAP feature (filler: what meals) passed up from phrase to phrase in parse tree -- complicated mechanism–Even bigger problem for representations such as FSAs and NgramsHow can we parse with feature