6.863J Natural Language ProcessingLecture 14: Features to lambdasInstructor: Robert C. [email protected]•863J/9•611J SP04 Lecture 14The Menu Bar• Administrivia:• Lab 3b out yesterday due April 12Agenda:Features & feature grammars What does all this mean?6•863J/9•611J SP04 Lecture 14Why: recover meaning from structureSNP VPVNPJohnateice-cream= λy.ate (y, ice-cream)VP(NP)= ate (john , icecream)ice-creamjohnλxλy.a t e (y , x )6•863J/9•611J SP04 Lecture 14Design advantage• Decouple skeleton syntactic structure from lexicon• In fact, the syntactic structure really is a skeleton:6•863J/9•611J SP04 Lecture 14From this…NPpresidenttheDetthatNSbarCompSNP VPVPPchokedNPPNPe6•863J/9•611J SP04 Lecture 14To thispresidentthethatchokedeonthethe..6•863J/9•611J SP04 Lecture 14Features are everywheremorphology of a single word: Verb[head=thrill, tense=present, num=sing, person=3,…] → thrillsprojection of features up to a bigger phrase VP[head=α, tense=β, num=γ…] → V[head=α, tense=β, num=γ…] NPprovided α is in the set TRANSITIVE-VERBSagreement between sister phrases:S[head=α, tense=β] → NP[num=γ,…] VP[head=α, tense=β, num=γ…] provided α is in the set TRANSITIVE-VERBS6•863J/9•611J SP04 Lecture 14Better approach to factoring linguistic knowledgeUse the superpositionidea: we superimpose one set of constraints on top of another:1. Basic skeleton tree2. Plus the added feature constraints• S → NP VP[Plural ?x] [Plural ?x] [Plural ?x]the guy eats[Plural -] [Plural -]6•863J/9•611J SP04 Lecture 14Checking featuresS [Plural ?x]NP [Plural ?x]VP [Plural ?x]DT [Plural ?x ]V [Plural ?x]NPthe[Plural -]guy[Plural - ]N [Plural ?x]eats[Plural -]6•863J/9•611J SP04 Lecture 14Feature Structures• Sets of feature-value pairs where:• Features are atomic symbols• Values are atomic symbols or feature structures• Illustrated by feature-value matrix (or list)12...nFeatureFeatureFeature12....nValueValueValue6•863J/9•611J SP04 Lecture 14How to formalize?• Let Fbe a finite set of feature names, let A be a set of feature values• Let p be a function from feature names to permissible feature values, that is, p: F→2A• Now we can define a word categoryas a triple <F, A, p> • This is a partial function from feature names to feature values6•863J/9•611J SP04 Lecture 14Example •F= {CAT, PLU, PER}•p: p(CAT)={V, N, ADJ}p(PER)={1, 2, 3}p(PLU)={+, -}sleep = {[CAT V], [PLU -], [PER 1]}sleep = {[CAT V], [PLU +], [PER 1]}sleeps= {[CAT V], [PLU -], [PER 3]}Checking whether features are compatible is relatively simple here…how bad can it get?6•863J/9•611J SP04 Lecture 14What sort of power do we need here?• We have [feature value] combinations so far• This seems fairly widespread in language• We call these atomic feature-value combinations• Other examples: 1. In English: person feature (1st, 2nd, 3rd); Case feature (degenerate in English: nominative, object/accusative, possessive/genitive): I know hervs. I know she; Number feature: plural/sing; definite/indefiniteDegree: comparative/superlative6•863J/9•611J SP04 Lecture 14Operations on Feature Structures• What will we need to do to these structures?• Check the consistency of two structures• Merge the information in two structures• We can do both using (simple) unification• We say that two feature structures can be unified if the component features that make them up are consistent• [Num SG] U [Num SG] = [Num SG]• [Num SG] U [Num PL] fails!• [Num SG] U [Num []] = [Num SG]6•863J/9•611J SP04 Lecture 14Feature unification examples(1) [ agreement [ Plural - , person first ] ](2) [ agreement [ Plural -] , case nominative ] • (1) and (2) canunify, producing (3):(3) [ agreement [ Plural - , person first ] , case nominative ](try overlapping the graph structures corresponding to these two)6•863J/9•611J SP04 Lecture 14Feature unification examples1) [ agreement [ Plural - , person first ] ](2) [ agreement [ Plural -] , case nominative ] (4) [ agreement [ Plural - ,person third] ]• (2) & (4) canunify, yielding (5):(5) [ agreement [ Plural - , person third], case nominative ]• BUT (1) and (4) cannotunify because their values conflict on <agreement person>6•863J/9•611J SP04 Lecture 14Our feature structures• NP[agr ?B] -> DET[agr ?B] N[agr ?B]• VP[fin ?A, agr ?B] -> V2[fin ?A, agr ?B] NP• Maria NAME[agr [person 3, plural -]]Kimmo entry for Verb (eg, ‘coge’ after analysis):• +e Suffix "[fin +, agr [tense pres, mode ind, person 3, plural -]]"6•863J/9•611J SP04 Lecture 14Parsing with features – hook from kimmo to earley• Features written in this form (in Kimmo)• +as Suffix "[fin +, agr [tense pres, mode ind, person 2, plural -]]”• In general: [feature value, feature [feature val, …, feature val]]6•863J/9•611J SP04 Lecture 14Where wolf6•863J/9•611J SP04 Lecture 146•863J/9•611J SP04 Lecture 14Features and Earley Parsing• Goal:• Use feature structures to provide richer representation• Block entry into chart of ill-formed constituents• Changes needed to Earley• Add feature structures to grammar rules, & lexical entries• Add field to states containing set representing feature structure corresponding to state of parse, e.g.S Æ • NP VP, [0,0], [], Set= [Agr [plural -]]6•863J/9•611J SP04 Lecture 14•**Add new test to Completer operation• Recall: Completer adds new states to chart by finding states whose • can be advanced (i.e., category of next constituent matches that of completed constituent)• Now: Completer will only advance those states if their feature structures are consistent• ** Add New test for whether to enter edge in the chart• Now feature structures may differ, so check must be more complex• Suppose feature structure is more specific than existing one tied to this state? Do we add it?6•863J/9•611J SP04 Lecture 146•863J/9•611J SP04 Lecture 146•863J/9•611J SP04 Lecture 146•863J/9•611J SP04 Lecture 146•863J/9•611J SP04 Lecture 146•863J/9•611J SP04 Lecture 146•863J/9•611J SP04 Lecture 146•863J/9•611J SP04 Lecture 14Feature extensions to other partsof syntaxDetTheNplantoVPVPVswallowNPWandaVhasVbeenVthrillingNPOttoNPVPVPVPSN[num=1][num=1][num=1][num=1][num=1]NP[n=1] → Det N[n=1]N[n=1] → N[n=1] VPN[n=1] → planVP[n=1] → V[n=1] VPV[n=1] → hasS→ NP[n=1]
View Full Document
Unlocking...