New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Natural Language Processing

by: Donnell Kertzmann

Natural Language Processing CSE 842

Donnell Kertzmann
GPA 3.97


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Computer Science and Engineering

This 11 page Class Notes was uploaded by Donnell Kertzmann on Saturday September 19, 2015. The Class Notes belongs to CSE 842 at Michigan State University taught by Staff in Fall. Since its upload, it has received 26 views. For similar materials see /class/207421/cse-842-michigan-state-university in Computer Science and Engineering at Michigan State University.

Similar to CSE 842 at MSU

Popular in Computer Science and Engineering


Reviews for Natural Language Processing


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/19/15
CSE842 Natural Language Processing Lecture 12 Feature Structures and Uni cation 2232009 CSE842 Spring 2009 MSU Limits of CFGs Recall that there are several things CFGs don t handle elegantly Agreement A cat sleeps Cats sleep S 9 NP VP NP 9 Det Nom But these rules overgenerate allowing eg they sleeps these dog Subcategorization they nd 2232009 CSE842 Spring 2009 MSU 2 VP 9 V VP 9 V NP But these also allow She disappeared the elephant We need to constrain the grammar rules to enforce e g number agreement and subcategorization differences 2232009 CSE842 Spring 2009 MSU CFG Solution Encode constraints into the nonterminals Nounverb agreement s9 SgS S 9 P18 SgS 9 SgNP SgVP SgNP 9 SgDet SgNom Verb subcat IntransVP 9 IntransV TransVP 9 TransV NP But this means huge proliferation of rules 2232009 CSE842 Spring 2009 MSU 4 A11 Alternathe Feature Structures View terminals and nonterminals as complex objects with associated features Sets Of featmeva1ue pairs where which take on different values Features are atomic Symbols 39 Write grammar rules Whose application is Values are atomic symbols or feature structures constrained by tests on these features e g Illustrated by attributevalue matrix 9 NP P onl if the NP and P a rec in S numbgi y V g F eature Value F eature Value We ll do this with feature structures and Feature iiiamen the constraintbased unification formalism 2232009 CSE842 Spring 2009 MSU 5 2232009 CSE842 Spring 2009 MSU Number feature Num 5G Feature values can be feature structures Numberperson features themselves bundles of features Jigum EVG Useful when certain features commonly co EVS occur e g number and person Numberpersoncategory features 3 sgNP Cat NP Cat NP A Num SG Num SG gr Per 3 Pers 3 2232009 CSE842 Spring 2009 MSU 7 2232009 CSE842 Spring 2009 MSU Graphical Notation for Feature Structures CAT NP N UM BER AG R EE39MENT PERSON 2232009 CSESAZ Spring 2009 MSU 9 Reentrant Structures Feature structures may also contain features that share some feature structure as a value Cat S Num SG A gr 1 Pars 3 i Head Sub Agr l Numerical indices indicate the shared values Path ltHEAD AGREEMENT NUMBERgt 2232009 CSESAZ Spring 2009 MSU 10 Reentrant Structures AGREEMENT NUMBE 39 59 SUBJECT AGREEMENT PERS 3rd 2232009 CSESAZ Spring 2009 MSU ll Operations on Feature Structures 0 What will we need to do to these structures Check the compatibility of two structures Merge the information in two structures 0 We can do both using uni cation 2232009 CSESAZ Spring 2009 MSU 12 We say that two feature structures can be uni ed 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 Num SG Pers 3 Structure are compatible if they contain no features that are incompatible 2232009 CSE842 Spring 2009 MSU 13 Unification of two feature structures Merger of the original structures into one larger structure Are the structures compatible If so return the union of all featurevalue pairs Does the following uni cation succeed Num SG Ag lNum SG Agr Pers 3 Pers 3 U N PL um Sub Agr 1 Sub Agr Pars 3 2232009 CSE842 Spring 2009 MSU 14 Feature Structures in the Grammar Used to express syntactic constraints that would be dif cult by using CFG alone How do we incorporate feature structures into our grammars Assume that constituents are objects which have feature structures associated with them Associate sets of uni cation constraints with grammar rules Constraints must be satis ed for rule to be satis ed 2232009 CSE842 Spring 2009 MSU 15 Feature Structures in the Grammar For a grammar rule 30 9 Bl Bn set of constraints Where each constraint has one of the following forms lt3i feature pathgt Atomic value lt3i feature pathgt lt3j feature pathgt 2232009 CSE842 Spring 2009 MSU 16 Example To enforce subject verb number agreement S 9 NP VP Only if the number of NP is equal to the number of VP S 9 NP VP ltNP NUMBERgt ltVP NUMBERgt 2232009 CSE842 Spring 2009 MSU 17 Agreement in English We need to add PERS to our subject verb agreement constraint This ight serves dinner S 9 NP VP ltNP AGRgt ltVP AGRgt Does this ight serve dinner S 9 Aux NP VP ltAux AGRgt ltNP AGRgt 2232009 CSE842 Spring 2009 MSU 18 Determiner Nominal agreement can be handled similarly These cats This cat NP 9 Det Nom ltDet AGRgt ltNom AGRgt ltNP AGRgt ltNom AGRgt And so on for other constituents and rules 2232009 CSE842 Spring 2009 MSU 19 How to Acquire Values Lexical constituents directly acquire values from the lexicon Examples Det 9 this ltDet AGREEMENT NUMBER gt s g Det 9 these ltDet AGREEMENT NUMBER gt pl V 9 serve ltVerb AGREEMENT NWBER gt pl V 9 serves ltV AGREEMENT NUMBER gt sg ltV AGREEMENT PERSONgt 3rd 2232009 CSE842 Spring 2009 MSU 20 Head Features Observation Features of most grammatical categories are copied from head child to parent eg from V to VP Nom to NP N to Nom Examples VP 9 V NP ltVP AGREEMENTgt ltV AGREEMENTgt NP 9 Det Nom ltDet AGREEMENTgt ltN0m AGREEMENTgt ltNP AGREEMENTgt ltNom AGREEMENTgt Nom 9 N ltN0m AGREEEMNTgt ltN AGREEMENTgt 2232009 CSE842 Spring 2009 MSU 21 Rewrite Rules with Head Features ReWritten as head features eg VP 9 V NP ltVP HEADgt ltv HEADgt NP 9 Det Nom ltNP9 HEADgt ltNom HEADgt ltDet HEAD AGRgt ltNom HEAD AGRgt Nom 9 N ltNom HEADgt ltN HEADgt N 9 i ts ltN HEAD AGREEMENT NUMBERgt pl V 9 serves ltV HEAD AGREEMENT NUMBER gt s g ltV HEAD AGREEMENT PERSONgt 3rd 2232009 CSE842 Spring 2009 MSU 22 Subcategorization O Recall Different verbs take different types of argument O Solution introduce feature structures to distinguish among the various members of verb catego SUBCAT feature or subcategorization frames One Way of doing this ltV HEAD AGREEDHENT NUlV 3ER gt sg ltV HEAD AGREEDHENT PERSONgt 3Id ltV HEAD SUBCATgt trans VP 9 V ltVP THEADgt ltV HEADgt ltVP HEAD SUBCATgt intrans VP9VNP ltVP THEADgt ltV HEADgt ltVP HEAD SUBCATgt trans 2232009 CSE842 Spring 2009 MSU 23 Subcategorization More expressive way to encode SUBCAT feature or subcategorization frames V 9 serves ltv HEAD AGREEMENT NUMBER gt sg ltv HEAD AGREEMENT PERSONgt 3xd ltv HEAD SUBCAT FIRST CATgt NP ltv HEAD SUBCAT SECONDgt end VP 9 V NP ltVP HEADgt ltV HEADgt ltVP HEAD SUBCAT FIRST CATgt ltNP CAD ltVP HEAD SUBCAT SECONDgt end 2232009 CSE842 Spring 2009 MSU 2A Complexity in Subcategorization are many phrasal types and many types of subcategorization frames Each Verb allows many different subcategorization frames m1 volvltl our entrainurn mini 1 lmlnrmmiuil mini mwln dquulimll Advil to mini Isnh in tr root rm will In vr sy NPAP vp sir Resources exist eg COMLEX 2212009 CSESA2 Spring 2009 MSU Uni cation and Barley Parsrng Uni cation operator takes two feature structures and re either a merged feature structure or fail Uni cation algorithm goes through features in one input DAGl trying to find corresponding features in DAG2 if all match success else fail Earley Parsing with Uni cation Use feature structures to provide richer representation Add feature structures to the grammar ru e Block entry into chart of illrformed constituents DAG to the state representation New corresponding tests ergr compieter based on uni cation indicated by DAG 2212009 cSEm Spring 2009 MSU Summing Up Feature structures encodes rich information about components of grammar rules Unification provides a mechanism for merging structures and for comparing them Feature structures can be quite complex Subcategorization constraints Unification parsing Merge or fail Modifying Earley to do unification parsing 2212009 CSESA2 Spring 2009 MSU Meaning Representation 2212009 cSEm Spring 2009 MSU Meaning So far we have focused on the structure of language not on what things mean We have seen that words have different meaning depending on the context in which they are used Everyday language tasks that require some semantic processing Answering an essay question on an exam Deciding what to order at a restaurant by reading a menu Realizing that you ve been insulted 2232009 CSE842 Spring 2009 MSU 29 Meaning Now look at meaning representations representations that link linguistic forms to knowledge of the world We are going to cover What is the meaning of a word How can we represent the meaning What formalisms can be used 2232009 CSE842 Spring 2009 MSU 30 Common Meaning Representations I have a car FOPC Ele y Havinge A Havere Speaker A HadThinge y A Cary Semantic Net having haver thing had speaker car 2232009 CSE842 Spring 2009 MSU 31 Common Meaning Representations Conceptual Dependency Diagram Car ll PossBy Speaker Framebased Representations Having Haver Speaker HadThing Car 2232009 CSE842 Spring 2009 MSU 32 Commonalities Between Representations They all share a common foundation meaning representation consists of structures composed of sets of symbols all represent the meaning of a particular linguistic input All represent the state of affair in some world 2232009 CSE842 Spring 2009 MSU 33 What Can Serve as a Meaning Representation Anything that serves the core practical purposes of a program that is doing semantic processing Answer questions What is the tallest building in the world Determining truth Is the blue block on the red block Drawing inferences If the blue block is on the red block and the red block is on the tallest building in the world then the blue block is on the tallest building in the world What are basic requirements of meaning representation 2232009 CSE842 Spring 2009 MSU 34 What requirements must meaning representations ful ll Veri ability The system s ability to compare the state of affairs described by a representation to the state of affairs in some world as modeled in the knowledge base Does Maharani serve vegetarian food ServesMaharani vegetarian food 2232009 CSE842 Spring 2009 MSU 35 What requirements must meaning representations ful ll Ambiguity The system should allow us to represent meanings unambiguously I wanna eat someplace that s close to ICSI Vagueness The system should allow us to represent vagueness 1 want to eat Italian food pasta spaghetti lasagna 2232009 CSE842 Spring 2009 MSU 36 Canonical Form Distinct inputs could have the same meaning Does Maharani serve vegetarian dishes Do they have vegetarian food at Maharani Are vegetarian dishes served at Maharani Does Maharani serve vegetarian fare Alternative Four different semantic representations Problem with matching KB 2232009 CSE842 Spring 2009 MSU 37 Canonical Form Solution inputs that mean the same thing should have the same meaning representation Vegetarian dishes vegetarian food vegetarian fare Have serve Relations among objects to be identical how gtsyntactic role analysis eg subjects and objects Maharani serves vegetarian dishes Vegetarian dishes are served by Maharani 2232009 CSE842 Spring 2009 MSU 38 Inference Consider a more complex request Can vegetarians eat at Maharani It would be a mistake to invoke the canonical form to force the system to assign the same representation to this request as those of Does Maharani serve vegetarian food Why are they result in the same answer 2232009 CSE842 Spring 2009 MSU 39 Inference Inference system s ability to draw valid conclusions based on the meaning representation of inputs and the background knowledge The system must draw conclusions about the truth of propositions that are not explicitly represented in the KB but that are logically derivable from the propositions that are present 2232009 CSE842 Spring 2009 MSU 40 Variables I 0 like to nd a restaurant where I can get vegetarian food First observation The request does not make reference to any particular restaurant Use of variables since we do not know the name of restaurant A representation can be ServesX vegetarianFood 2232009 CSE842 Spring 2009 MSU 41 Expressiveness Must accommodate Wide variety of meanings FOPC is expressive enough to handle many of the NLP needs 2232009 CSE842 Spring 2009 MSU 42 First Order Predicate Calculus FOPC provides a sound computational basis for the veri ability inference and expressiveness requirements Supports the determination of truth Supports compositionality of meaning Supports representation of variables Supports inference 2232009 CSE842 Spring 2009 MSU 43 FOPC Syntax Terms constants functions variables Constants objects in the world eg Maharam Functions concepts eg Location0fMaharani Variables x eg Locati0n0fx Predicates symbols that refer to relations that hold among objects in some domain or properties ServesMaharant VegetarianFood RestaurantMaharant 2232009 CSE842 Spring 2009 MSU 44


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.