Introduction to Natural Language Processing
Introduction to Natural Language Processing CMPSCI 585
Popular in Course
Popular in ComputerScienence
This 144 page Class Notes was uploaded by Roman McCullough on Friday October 30, 2015. The Class Notes belongs to CMPSCI 585 at University of Massachusetts taught by David Smith in Fall. Since its upload, it has received 48 views. For similar materials see /class/232284/cmpsci-585-university-of-massachusetts in ComputerScienence at University of Massachusetts.
Reviews for Introduction to 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: 10/30/15
Course Overview Lecture 1 Computational Linguistics CMPSCI 585 Fall 2007 University of Massachusetts Amherst Andrew McCaIIum httpwwwcsumassedumccallumcoursesinlp2007 Where to find syllabus announcements slides homeworks Andrew McCallurn UNIass Amherst including material from Chris Manning and Jason Eisner Today s Main Points Why is natural language interesting and difficult complex and ambiguous Why How to we resolve this ambiguity Six layers of natural language Natural Language Processing overview current successes Get to know each other and our motivations for being here Course mechanics what you can expect Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner 1967 Stanley Kubrick Arthur C Clarke filmmaker author futurist 1928 1999 1917 Andrew McCanum UMass Amherst including material from Chris Manning and Jason Eisner Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner HAL s Capabilities Display graphics Play chess Natural language production and understanding Vision Planning Learning mmmmmmmmmmmmmmmmmmmm st 433 C 3 63 62 MDNTLNEWBORM KASPARQV VERSUS s Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Natural Language Understanding HAL David Bowman Open the pod bay doors Hal HAL I m sorry Dave I m afraid I can t do that David Bowman What are you talking about Hal HAL I know that you and Frank were planning to disconnect me and I39m afraid that39s something I cannot allow to happen Andrew McCallurn UNIass Amherst including material from Chris Manning and Jason Eisner Now Many useful tools but none that come even close to HAL s ability to communicate in natural language 1950 Alan Turing 1912 1954 Turing Test Computing Machinery and Intelligence Mind Vol 59 No 236 pp 433460 1950 I propose to consider the question quotCan machines think We can only see a short distance ahead but we can see plenty there that needs to be done Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner FDP J F N L ayers of Computational Linguistics Phonetics amp Phonology Morphology Syntax Semantics Pragmatics Discourse 1 Phonetics amp Phonology The study of language sounds systems of discrete how they are sounds eg languages physically formed syllable structure It is easy to recognize speech JeetJet It is easy to wreck a nice beach Andrew McCallum UMass Amherst 39 39ng ial from Chris Manning and Jason Ersner 2 Morphology The study of the subword units of meaning Even more necessary in some other languages eg Turkish uygarasz iramadikarimizdanmissinizcasina uygar las tir ama dik lar imiz dan mis sinz casina behaving as if you are among those whom we could not civilize Andrew McCanum UMass Amherst including material from Chris Manning and Jason Eisner 3 Syntax The study of the structural relationships between words N V SBAR 39 SBAR S I I know that NP VP I NP CONJ NNP i r J you and Frank were planning to disconnect me Not same structure Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner 4 Semantics The study of the literal meaning ACTION disconnect ACTOR you and Frank OBJECT me Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner 5 Pragmatics The study of how language is used to accomplish goals What should you conclude from the fact I said something How should you react Includes notions of polite and indirect styles Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner 6 Discourse The structure of conversations turn taking thread of meaning Open the pod bay doors Hal I m sorry Dave I m afraid I can t do that What are you talking about Hal I know that you and Frank were planning to disconnect me and I39m afraid that39s something I cannot allow to happen Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Linguistic Rules Eg Morphology To make a word plural add s mmmmmmmmmmmmmmmmmm st It 5 dog 9 dogs baby 9 babies dish a dishes goose a geese child 9 children fish a fish l Inherent Ambiguity in Syntax NY Times headline 17 May 2000 S NP VP I N NNP V NP NP PP Fed raises NN NN CD NN PP NP interest rates 05 in NN VP effort V VP to V NP l I control N N inflation Andrew McCanum UMass Amherst including material from Chris Manning and Jason Eisner Where are the ambiguities Partofspeech ambiguities SyntaCtiC attaChment ambiguities VB VBZ VBZ VBZ NNP NNS NNS NNS CD NN Word sense ambiguities Fed 4 federal agent interest ea feeling of wanting to know or learn more Semantic interpretation ambiguities above the word level Andrew McCa11urnUMass Amherst including material from Chris Manning and Jason Eisner Effects of VN Ambiguity 1 S A NP VP I NNP V NP l Fed raises NN NN interest rates Andrew McCallum UMass Amherst 39 39ng in from Chris Manning and Jason Eisner Effects of VN Ambiguity 2 S NP VP N N v NP I Fed raises interest N rates Andrew McCallum UMass Amherst 39 39ng in from cm Manning and Jason Eisner Effects of VN Ambiguity 3 S NP VP N N N v NP i I i Fed raises interest rates CD N 05 Andrew McCallum UMass Amherst 39 39ng in from Chris Manning and Jason Eisner Ambiguous Headlines Iraqi Head Seeks Arms Juvenile Court to Try Shooting Defendant Teacher Strikes Idle Kids Stolen Painting Found by Tree Kids Make Nutritious Snacks Local HS Dropouts Cut in Half British Left Waffles on Falkland Islands Red Tape Holds Up New Bridges Clinton Wins on Budget but More Lies Ahead Ban on Nude Dancing on Governor s Desk mmmmmmmmmmmmmmmmmmmm st Language Evolves Morphology We learn new words all the time bioterrorism cyberstalker infotainment thumb candy energy bar Partofspeech Historically kind and sort were always nouns knowe that sorte of men ryght well 1560 Now also used as degree modi ers I m sort of hungry Present It sort 0 stirs one up to hear about old times 1833 mmmmmmmmmmmmmmmmmmmm st Natural Language Computing is hard because Natural language is highly ambiguous at all levels complex and subtle fuzzy probabilistic interpretation involves combining evidence involves reasoning about the world embedded a social system of people interacting persuading insulting and amusing them changing overtime mmmmmmmmmmmmmmmmmmmm st Probabilistic Models of Language To handle this ambiguity and to integrate evidence from multiple levels we turn to The tools of probability Bayesian Classifiers not rules Hidden Markov Models not DFAs Probabilistic Context Free Grammars other tools of Machine Learning Al Statistics mmmmmmmmmmmmmmmmmmmm st Another Area where Probabilistic Combination of Evidence Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Natural Language Processing Natural Language Processing NLP studies 5 9 how to get computers to do useful things with 63 natural languages 6amp8 Most commonly Natural Language Understanding The complementary task is Natural Language Generation NLP draws on research in Linguistics Theoretical Computer Science Artificial Intelligence Mathematics and Statistics Psychology Cognitive Science etc mmmmmmmmmmmmmmmmmmmm st What amp Where is NLP Goals can be very farreaching True text understanding Reasoning and decisionmaking from text Realtime spoken dialog Or very downtoearth Searching the Web Contextsensitive spelling correction Analyzing readinglevel or authorship statistically Extracting company names and locations from news articles These days the later predominate as NLP becomes increasingly practical focused on performing measurably useful tasks now Although language is complex and ambiguity is pervasive NLP can also be surprisingly easy sometimes rough text features often do half the job Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Linguistics Linguistics is the study of natural languages Understanding this naturallyoccurring 59 phenomenon 0900c Structure meaning how acquired differences and commonalities across languages Linguistics draws on research in Natural Language Processing Theoretical Computer Science Artificial Intelligence Mathematics and Statistics Psychology Cognitive Science etc mmmmmmmmmmmmmmmmmmmm st Andrew McCallun including material Example Applications of NLP O 3 Google Search natural language processing i 4 e L5 htthtwwwgooglexomsearchihlenampiel50 8859 Lampec QVICoeole H r39EIII Yahoo Coogle Slashdot Newsv McC Researchv Reviewingv Macv Java Thesaurus Fundingv Teachingv quot3 a Google Search natural Iquot 7 7 a Advanced Search Preferences Language Tools Search Tigs l Google Search natural language processing Searchedthe web for natural Ian u e rocessin Results 1 10 of about 221000039 Search took 021 seconds Natural Lan ua e Processin Natural Language Processing should make it possible for people to use computers in much the same way that they would use a human assistant to get their work researchmicroseftcomr39nlpl 23k Cached Similar pat es Spoi rsored Links Natural Language Search Returns more relevant searches Installs in days Free i39tu39hite Paeers Wprimuscom SI39s Natural Language Groug Interest Overview of Research Environment Natural Language Processing at USCJISI USC offers a wide range of courses in areas related to natural language processing NLP N Description The Natural Language Processing group at the Information Sciences Institute of J the University of Southemm Category Lnl iITir39IItFII gt Artificial 2 Res ten Grouns WWisiedulnaturalltlanguagei39nlp abisihtml 15k CEILZIIBU Similar gates All the PEWS that s fit to p e Human Language Techn 39 fieldmethodsnet Interest Foundations of Statistical Natural Language Processing Foundations of Statistical Natural Language Processing Chris Manning and Hinricn Schlitze Foundations of Statistical Natural Language Processing MIT Press nlpstanfordeduifsnpi39 i k Cached Similar gages Natural Lang Processing Text MIHIH39 Based on NLP V For scient39 aturo analyse wwwariadnegenomicscom Interest Yahoo Directory Arti cial Intelligence gt Natural Language Artificial Intelligence gt Natural Language Processing Directory gt Science gt Computer Science gt Artificial Intelligence gt Natural Language Processing d39r tlahm rnmthinnrn nmmitnr rinnrni39Artifir inl intnllinnnrni Natural Innminna Prnrnnninnl Work at Gwle l le I irinn e Example Applications of NLP MSWord spelling correction grammar checking If39grnuuseI39u39IinrInsp 39Wprd5rpuhavenndpubtnpticec1 re 21 an jrmis 5 Elle dWprds 101 tD1reeactal wordst1quot didgrauhmwthatynucallcane cttheseermrssimplgrl Microsu WmdM g ve 3rpua1istpfthewnrds thati1 wordgrouwantWmthelist3rpusitnp13rpickitf1 11 appears appease apparels appeals appear Lgnpre Full add AutUCorrecl IP 13 Spelling Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Example Applications of NLP abogle News C e m r a FlmlnxSuDPon ASZD drritAESRev www anlnws muons Dgln mmg1 Vilma Run Web Images Groups News Fluogle Local mare Advanedm Gaggle Searzh News Searzh me Web New Search Hlsmry nbw rnaludessabgle News Learn more Standard News 1 he Versan Ton Sh Top Stories us 1 Ga Aullygerleraked lo rrrirrmes ago We rld us Alito Seen as Car in the Torch ol Rea an E LasAngelesYlmesrlhuursa o quot5 5 ay Dav d s Sav ge Tlm 5 Staff Wmer WASHI ON 7 3 95quot 3 as F WSW 3 Seineelr Twenlyrllve years age Presldem Reagan came m Wasn rnglon BBC NEWS W upreme oeunlolne ngm He lng edurl es Senale Cunfllmallun Vale FOX News senale re eels membera mdyele bldek Allm s eennnnaben b n Washlrlgt F39 l s 5pm Madamra Meals sme MSNECV all 52 lelated Eme alnmem sleelers knew how to WIN quot uquot DelNewscom r all ma relaled ls rune Masl Popular an as e N all 1 512 relaed Landon Flee Fless r all 349 relaled E News Alerts Quote Remembering Corena Scan King Skaa39a ggeg e jquote l Aldm Seallle Fasl lnlelliaeneer 72 lraurs a a 7 About Feeds By THE ASSOCIATED PRESS Commenls by inends and a mlrers reua so Iquot quotquot3 News bl ea db Klng lne wldow bf me Rey Mamn Luther Klng lr lellawrng nerdealn on Tuesday J ll s a bleak er 0 man About us New adb Woodmff JlH CalmH Goagle News momrngl me andf r y pebble W W Mdurners yrsrl Klng s mm m pay reseecls m ms wldm Access Nonlr Georgla Wendy Wassersrern Slale dune Unlo Clvll Rrgne can Cnletta Soon Klng 1927mm Democracy Now Exxon Mebrl Saddam Husseln WJLA e adsNewsul XKAVI V e FageOneQ com r all 353 relaxed Doug Veg Screen Acmls eurld World 1 m Ind ke 0 v0 e a 3 Ian ln39ured ABC newsmen return to US unmeam r 37 rrrrrrulss ago Mansrers and cmreseam 721 minules ago lndra ls llkely lb vole agalnst Iran at me lnlemauenal Alamre NDSTUHL Germany lu 7 ABC newsman Bob Wmde Energy Agency IAEA meelrng ln Vrenna on February 2 ns and cameraman Doug Vagl lelr a nesprlal ln Germany ler comes a er Russla and cnrna wnrbn abslarned lrom volng al aelnesda Md on Tuesday a el belngl lne IAEA meeung rn Searemberzlms changed lnerrsland lrad rn nlured by a bomb rn e men were a lrll ed la lne Landsmhl 39aane mmcam M u r Example Applications of NLP Information Extraction Find experts employees Dr Andrew McCallum JMLR Inc Action Editor lg Send This Profile Journal of Machine Learning Research W519 Your Prome llh il WWWV39mlmru Las mmm quot 1 3 W WW JMLR which publishes highquaity scholarly articles in all areas of machine learning competes with the commercial journal Machine Leamingt which costs US1DOBt A number of Machine Learning editorial board members have resigned to join the editorial board of LR iniorel omer Titles Held lMember Editorial Board Clle here to find other people who work for JMLR Inc WM Contact Us Corporate Headquarters 3210 North Canyon Road Suite 200 Provo UT 84604 gt Phone 801 413 7100 Cmmmees Fax 801 818 0300 litigllwwwwliizbanglabscom WhizBang Labs founded in 1999 is a leader in the field of informatio extraction and document autotagging from unstructured data sources Through our products and services wwwzoominfocom http locate and extract key data f Dragon Health sc39ences elements into XML tagged more Click here to find other people who work for WhizBang Labs Inc lEducatlon I lUniversity of Rochester lPth IOomputer Science I Intelliseek Inc lDartmouth College lBachelor of Arts IComputer Solence I 1128 Main sweet I Founh Floor Cincinnati OH 452027236 1 Information about Andrew McCallum was compiled from 6 sources Phone 513 618 6700 n to 11m HnetwclrkingZelivoncomNetworkingdefaultasp39 Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Example Applications of NLP Information Extraction Job Openings foodsciencecomJob2 ICe Cream Guru foodsciencecorn TravelHospitality Food Services Upper MidWest Phone 8004882611 Abam ems neeMum January 8 2001 Immune mm Source WWWfoodsciencecorrijobs rriidwesthtrr Job um inm Midth foddscienceporriJobl Am manm UMass mm mm mm mchns Mzmlrg ma ymngmx Example Applications of NLP Information Extraction Job Openings 3 lab l a mum a 2 00quot Imam Exvlmel Em dyesx a hug me Vhpdag camhams mm 6 Fuggog Home F a Job Yom Autumn Rusmucg Cenlev 39 support 39 EmPlDYEVS WSW News Q 2 v 39 mu Care m MD m a e m saws m M m y computmq m w M W95 Computmq m MD 0 m mucwun e um 53 641 Empmvars e a W has F nd 3 Jo MWSPWFM and Hm m Dsmummm Fommm mg 5mm FootbaH Coazh gtEmployers Unw Asd FootbaH m m m Coazh mam amp SewFEES Job Seeker D mam b ah Seekerews ener my you e39ma addvess okmg m a We 77 gt Check um Eest mazes m Fwd a Jub Januavy vegan y W gt Seavch 2m WM um FREE amumanc JubHumevsW y Peseavch um dalabase umvev nun emphyevs m we mu sue f gt Get 2X92quot advmz at um new Pesuuvce Came gt Access sa avy sJNeysca cu amvs ve ucatmn and quotKWquot m nemmkmg ugpumnme ampvammgestmgmus i Caveerweb Sue Mom mm 3 mm gt Use thDug cum m seavcmubs quotgm mm yum desktup Duwn uad Enum mday D m mm sue Wemel l j memwm W aa seavphhivdempwmen gaging 21AM E1 WWW u a w mmmmmmmWWW Example Applications of NLP Automatically Solving Crossword Puzzles 3 I w ucs lult run I I E News Contact Suort Advertise Privac About I Crossword Clue Search Having trouble getting the last word in that puzzle Having trouble getting the rst See if our search engine can help Unlike pure pattern dictionary OHACVDSS hanQES SCRI ChCS we actually analyze the clue as well OneAeross 18 moan1 to a bigger better server This may cause some Clue roblems we net kinks worked out p D Pattern Golr but hopefully by early next week eyerything will be in better shape Thanks for your patience How to Search Enter a elue and either the length of the ansnmr or an amwer pattern For unknown 7 1 xquot 2 r v quota aquot l C currently pmvmc amwm EU lettelh 1n the in old pattern y ou ean use a question over IODJUUU searches a day You mml m a I 1quot LT Clue Trout Basket Clue Cut He 0 4 Pattern a Pattern Z n Support tlus Site today Clue Clue luck to Pay Pattern al ske Pattern r fully refundable Andrew M 2 r quot d quotg Hints for better searching Andrew includin Example Applications of NLP Question Answering 0 AnswerBus Question Answering System who is married to bill gates Ahttpwawan5werbuscomicgi binfanswerbusianswerO vaicrosoft spelling correction Yahoo Google Slashdot Newsv McC Researchv Reviewing v Macv Java Thesaurus 75 Funding 7 Teaching v who is married to bilil gates a Ask Type in your question in EnglishfrcnclL Spanish ernmir ltalian or Portuguese Question who is married to biii gates Femible answers amp m a Bill was married to Melinda French Gates in l994 in Hawaii I Maw Gates Bill s mother biunest fan and stron est rodder nallv laid down an ultimatum in 993 She was dvinn of cancer and wanted to see her only son married in Bill Gates married Melinda French in Hawaii on Januan39 l l994 and his mother died a few months later t 1994 Bill Gates and Melinda French married in Hawaii on New Years Dav Try your question on other engines Alta Vista CNN News Engine Ask Jeeves Excite Google Hoth 1 chos I Start Yahoo Example Applications of NLP Machine Translation I WUNSCHZETTEL MEINKONTD HILFE V7 MEINSHDP 11mm Egggfg39 ELEKggg g39 H L 39 T MUS VIDEO SOFTWARE z EXTENDED SPECIALIZED TIME PRICE SEARCH I STOEBERN I BESTSELLER NOVELTXES I BOOKS I I I WRITINGS HIT High speed search 39 German books Stoebarn 39 All categories jALLES MUSS RAUS JETZT ZUGREIFEN 75Chn pp 5henlage391Q39 mlangr Jar v39I39ral mimt m Assault or preventive strike The German More to this book aftgae grathefslfwet Unlon on 22 June 1941 1 uses 1050 starting Overview 0 er ar Bum a from EUR Amazonde reader would you like to sell More of Mstming from EUR 1050 x Diesen Artlkel W l Gerhard Baurnfalk Offerer dispatches in 12 workingdays What do you mean Their ogl nion to this boo Continue to W 39 1 39 39nl Politics Bioqra enamphistorv sgecialized books by EMall Now at money back 1 taxes back Paperback 164 sides Rita Fischer Ffm which are Publication date July 1997 ISBN 3895014931 entitled to you mire c xixnclugnhgamc with the software and Amazonde Verkaufsrang 204896 Example Applications of NLP Automatically generate Harlequin Romance novels Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Goals of the Course Introduce you to Natural Language Processing problems and solutions Ultimate focus on handling ambiguity by probabilistic integration of evidence Give you some handson practice with data and a handful of methods mmmmmmmmmmmmmmmmmmmm st This Class Assumes you come with some skills Some basic mathprobability decent programming skills We will use Python tutorial coming next week Some ability to learn missing knowledge Teaches key theory and methods for language modeling tagging parsing etc But it s something like an Al Systems class Hands on with data Often practical issues dominate over theoretical niceties mmmmmmmmmmmmmmmmmmmm st Course Logistics Professor Andrew McCallum TAs David Mimno Karl Schultz Assistants Hanna Wallach Khash Rohanimanesh Time TueThu 230345pm Mailing list 585 staff cs umass edu More information on Web site httpwwwcsumassedumccalumcoursesinp200 Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Grading 7 short written homework programming assignments no way to really internalize without doing it some handson experience should be fun should take about 12 hours each Random informal inclass collaborative quizzes help you set expectations for the midterm and final Final project with a small team mixed backgrounds chance to explore a special interest at end of term Midterm amp Final and classroom participation mmmmmmmmmmmmmmmmmmmm st For Linguistics Students Programming Yipes Yes but with extensive support for those wout expenence Historically popular language for CL courses Prolog clean hard to learn counterintuitive Perl quick but obfuscated syntax messy to read Interpreted rapid prototyping Why Python is bettersuited easy to learn clean syntax powerful features becoming increasingly popular in CompLinguistics Extensive tutorials CompLing support toolkits data etc Many CS students don t know it either put you on more equal footing Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Syllabus Outline Two parts First handson course introductory methods HW Second more like a seminar project First half Language structures and computation Foundation of probability and information theory Use those foundations to work with language Example topics Language models language prediction spam filtering Collocations word clustering word sense disambiguation Finite state machines Markov models Partofspeech tagging Modern parsing techniques Information extraction semantics question answering discourse Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner To Do This Week Visit course Web site browse around Read Chapters 1 and 2 in Jurafsky amp Martin textbook Available on line See course web site Install Python on your computer Get extensive help from the TAs if you like mmmmmmmmmmmmmmmmmmmm st Thank you Andrew McCallum UMass Amherst including material from Chris Manning and Jason Eisner Course Overview Lecture 1 Introduction to Natural Language Processing CMPSCI 585 Fall 2004 University of Massachusetts Amherst Today s Main Points Why is NLP interesting and difficult complex and ambiguous Why How to humans resolve this ambiguity The six layers of NLP NLP history an overview current successes Course mechanics what you can expect Andrew McCallum 1 967 Stanley Kubrick Arthur C Clarke filmmaker author futurist 1928 1999 1917 CA u39rInN nunnun Enuul39nun ISIAltllVllllllu m C O a space odyssey will u HAL s Capabilities Display graphics Play chess Natural language production and understanding Vision Planning Learning Graphics Natural Language Understanding HAL DaviaBowmai Open the pod bay doors Hal HAL I39m sorry Dave I39m alraid I can39t dothat David Bowman What areyou talking about Hal HAL know thatyou and Frank were planning to disconnect me and I39m afraid that39 som ething I cannot allow to happen Now Nhny useful tools but to communicat in natural language 1950 Alan Turing 1912 a 1954 Turing Test Computing Machinery and Intelllgmce Mrrrd Vol 59 No 236 pp 433460 1950 Ipmpose to consider the question Can mach nes thnk7quot e 1y see a short distance ahead but ca we can see plenry Lhae Lhatneeds to be done Layers of Natural Language Processing Phonetics amp Phonology Morphology Syntax Semantics Pragmatics Discourse Q N 1 Phonetics amp Phonology The study of language sounds systems of discrete th are ounds eg languages physically formed syllable structure It is easy to recognize speechquot JeeLJet It is easy to wreck a nice beachquot 2 Morphology The study of the subword units of meaning notquot to attachquot Even more necessary in some other languages eg Turkish uyga ra Hiramat kaimizdanmissinizcasina uygar as tir ama dik lar imiz dan mis sinz casina behavmg as it you are among tnose Whom We could not ClVlilZe 3 Syntax The study of the structural relationships between words SEAR SEAR 3 know that NP NP com NNP you and Flank weie planning to di connect me Not same strumre 4 Semantics The study of the literal meaning ACTION disconnect ACTOR you and Frank OBJECT me 5 Pragmatics The study of how language is used to accomplish goals What should you conclude from the fact I said something How should you react includes notions of poiite and indirect styies 6 ourse The study of linguistic units larger than a single utterance The structure of conversations turn taking thread of meaning Linguistic Rules Eg Morphology To make a word plural add s 0 dog 6 dogs baby 6 babies dish a dishes goose a geese child 6 children fish e sh l Inherent Ambiguity in Syntax IVY Times headme 77 i A NNP V NP NP PP i i Fed raises NN NN CD NN PP NP May 2000 interest rates 05 m iri NN VP i rifi ati Ori Where are the ambiguities Svritacti c attachrn erit Faitrofrspeech ambiguiIies ambiguities IBZ IBZ NNP NNS NNS NNS CD NN Word serise ambigtiities Fed gt federai agent interestea reeimg or Wanting to know or ieam more Semariiic interpretation ambiguities above the Word ievei Effects of VIN Ambiguity 1 s NP IP i NNP V NP Fed raises NN NN i i interest rates Effects of VIN Ambiguity 2 S NP VP N N v NP i i i Fed raises interest N i rates Effects of VIN Ambiguity 3 s NP IP i N N N v NP i i i i Fed raises interest rates CD 3242 Ambiguous Headlines Iraqi Head Seeks Arms Juvenile Court to Try Shooting Defendant Teacher Strikes Idle i s Stolen Painting Found by Tree Kids Make Nutritious Snacks British Le Waf es on Falkland Islands Red Tape Holds Up New 39 Clinton Wins on Budget but More Lies Ahead Ban on Nude Dancing on Govemor s Desk What is grammatical and what isn t John I believe Sally said Bill believed Sue saw What did Sally whisper that she had secretly read John wants very much for himself to win Who did Jo think said John saw him The boys read Mary s stories about each other Mary while John had had had had had had had had had was the correct answer What is grammatical and what isn t John I believe Sally said Bill believed Sue saw What did Sally whisper that she had secretly read John wants very much for himself to Win Who dicl Jo think said John saw him The boys read Mary s stories about each other Mary while John had had had had had had had quothad had was the correct answer Language Evolves Morphology We learn newwords all the time bioterrorism cyberstalker infotainment t umb candy energy ar Partofspeech Historically kind and sort were always nouns knowe that sorte of men ryght well 1560 Now also used as degree modifiers m sort ofhungry Present It sort 0 stirs one up to hear about old times 1833 Natural Language Computing is hard because Natural language is highly ambiguous at all levels complex and su te fuzzy probabilistic involves reasoning about the world embedded a social system of people interacting persuading ll iSultll ig and amusi gthem cnanging overtime Probabilistic Models of Language To handle this ambiguity and to integrate evidence from multiple levels we turn to Bayesian Classifiers not rules Hidden Markov Models not DFAs Probabilistic Context Free Grammars Maximum Entropy models other tools of Machine Learning Al Statistics Natural Language Processing Natural Language Processing NLP isthe study of the computational treatment of natural languages Most commonly Natural Language Understanding The complementary task is Natural Language Generation NLP draws on research in Linguistics Theoretical Computer Science Arti cial Intelligence Mathematics and Statistics Psychology etc What amp Where is NLP Goats can be yerytanreachrng 7 Truetextunders tandtng 7 Reasuntng and oecrsrpnmahng frurn text 7 Reattrme spuken oratog ye 7 Searchtn the e 7 Contextsenstttye spelhng correctmn 7 Anatyztng reaotngteyet ur authurshtp stattstteauy 7 Extraettng cumpanynamesand lucattunsfrumnevvsamcles These days the taterpreoommate as NLP becomes mcreasrngty practrcat focused on perronmng measurably useful new Although language ts complex and ambrgurty ts pervasrye NLP can also be surpnsmgty easy sometrmes 7 rough text features uften up half thetub Some brief history 1950s Early NLP on machines less powerle than pocket calculators Foundational work on automata formal languages probabilities and information theory First speech systems Davis et al Bell Labs MT heavily Jnded by military but basically just word substitution programs Little understanding of natural language syntax semantics pragmatics Some brief history 1960s Alvey report 1966 ends Jnding for MT in America the lack of real results realized ELIZA MIT Fraudulent NLP in a simple pattern matcher psycholtherapist 7 tt strue larn unhappy 7 Do you thtnk cornrng here Wtmalte you not to be unhappy7 7 1 need some help thatmuch ts ce am 7 What wouo tlmean to you tfyou gotsorne hep7 7 Perhaps 1 could earn to get along wtth my mother 7 Te rne rnore about your famt Early corpora Brovm Corpus Kudera and Francis Some brief history 1970s Winograd s SHRDLU 1971 existence proof ofNLP in tangled LISP code Could interpret questions statements commands 7 Whrch cube ts srttmg on e a te7 7 The arge green one whrch supports the reg pyrarnro 7 ts there a large block behmd the pyramm 7 Yes three of thern A arge red one a targe green cube and the hue one 7 Put a small one onto the green cuube wtth supports a pyramrd Some brief history 1980s Procedural gt Declarative including logic programmin Se aration of processing parser 39om description of linguistic knowledge Representations of meaning procedural semantics SHRDLU semantic nets Schank logic perceived as answer nally applicable to real languages Montague Perceived need for KR Lenat and Cyc Working MT in limited domains METEO Some brief history 1990s Resurgence of nitestate methods for NLP in practice they are incredibly effective Speech recognition becomes widely usable Large amounts of digital text become widely available and reorient the eld The Web Resurgence of probabilisiticstatistical methods led by a few centers especially IBM speech parsing Candide MT system often replacing logic for reasoning Recognition of ambiguity as key problem mphasis on machine learning metho s Some brief history 20005 A bit early to tell But maybe Emphasis on meaning and knowledge representation Emphasis on discouirse and dialog Strong integration of techniques and levels brining together statistical NLP and sophisticted linguistic representations Increased emphasis on unsupervised learning More integration of NLP components into larger systems Example Applications of NLP H n A neegle Seam llalulal la iguaqe pleLis q 4 e a ll nupmpwgeuglesumlsearmnleenareelsoeassaemer q m meal magi Slasmlal Newsv MC Resuuhv Revizwmgv Mar Java Thesaurus Fundmgv Teamvnyv ml l u Advanced Searm Pvelevennes LanguagaTonls Searcthgs g murallunauserprmawu Tuneup apes l Groups lulreamryl News l Web Km Searchsdthewebfmnmumllzn u e mussln Resultslrtlloiatmutz 0M0SearcMoak021secands Natural Lan HE E Processin Nalural Language Prunesslng snoLlu maKe lr posslple ml people to use eernsulers ln rnupn llle same way that play would use a human asslsLanL to geL melrwprk lesealell mleresell cnmlnlp 72M 7 Macl edr sllllllul laces Llnlr nmw prnluscom llilLlLl a wlue range of courses ln areas velaled to narural language pruaesalng NLP N Busrllpllzll rneNamraI Lanluane Pruce na Duupznhelnfomlztlon splelpes lrsllmeuf r r W NM a ma un erley oi spum llllnrr la39 ungplneprilcy n lleldmelmds rel lmcrusr r lll u els e Frilllelal llllilll EH pr u e 1 www sl edunaUlalrla lluegellvaklsl Mle le WW 4 Foundallans of Siallstlbal Narural Language Pracesslng cnlls Mannan and Hmch 39T39a m39 Laquot 3 39quot thutze Foundatlans 0f Siallsllcal uarural Language Preaesslng er Press r nlp sranreru edulsnlp39 a 7x a Ca llllllal ua s Vahual Direclnm Arti cial Intelligence gt Natural Language Anlrlplal lntelllgenne gt Narurai Language Preaeaslng Dlleclory a Science s MSWord spelling correction grammar checking Example Applications of NLP red39 any misspelled39wnrdswr to besexact appease appards appeals appear Ignore All Add Autocurrect D quotmfgquot Cumpuler Sclence e A1lflclallntelllgance gt Namral Language Preaesslng re re aeeqle am 4 e He nihlemgncvlexml l m mun tuna arms News m rllr Mars nu neauns realm mm s nae E mull lws 39 39 39 l i 739 0 6 mp mace amps Ulmc39n39v thdEuuzh Newsge l semenanaerawsueunwseuurres unsursnnnu Tonswnns Wquot Ker linesu endursamenls39Deanshakesu mugglmamsgsml gmmu us 51quot reu eusnea an Hanmswhranlunsimmuhago a llel u eln uelrsnlaurue M Ma uulnlglluruu Wmquot an mun weketed lesnelmeenerls ran llle Sums a l3lnun oancncn Vanleant itlmlslan lllullllllllsllwl lll Enmmmmcni 65mm MMMVMWFWW HM WDW WWH DamsFnaiersmu anmneeakneln um quotl 50 m n E am e w my Mum llemlllsandll rilaled slzlneLgrrrueneceurmmlusllelllwsls um m m PM llllelulsrull nu a relreelreulnuruuulueueenumu 4 Junjeramll are m we MW e 39wla39l izvyvl lu new qua ul llle m ac nlcllv Rmiqn 0 at as Gtvnmam nnnaeeeulelel rll allnllmawu l lwl elllllulall rr mm m m 39 m 39 39 39 Information Extraction Find experts employees httpwwweliyoncom Example Applications of NLP Dr Andrew MECIJlum n lu lunrn r mm m new 7 Emma Jrllunnm emu ru Ran We ur am We lenlanm Fax leallalum m Emplwmu mswv m a M N lur 39 m M a lll clulmum arewarm m rlwzaanJLanlm marmurlanmaurunum McDIIuM unemelleu man a mu Example Applications of NLP Information Extraction39 Job Openin l as y rerun w Elm l lam l39unmwr Il 1LI lA l m Fm 1m as 4 i Maria I l lulu QAMEX new all real rlrrnane lNrEa NArll Example Applications of NLP Example Applications of NLP Information Extraction Job Openings Automatically Solving Crossword Puzzles 2 22 thgog Wm 5uwmanlnwm na mms Reference 9 Fa um Lanuaes News conkacm sum Advertise Privac About Crossword Clue Search Hav c rmubl smug me I m m mm punlcz luring lnlulllc cllillg lllc llll39 Sul ll lmr cm cll cnflnc can help Unllkc pure pmlcm dlcuonar One Across Changes wll L m we uuulllly analyze my line it well Quauml lgt muuw u u rlggc Tim may cause sumc Ina W per k h arm nui quotKm W l I l by curl Ilcxlncck e ll be m better shape 39lurpzmcllc 39 lluw in Search L Ilk rn cluu lml uilllcrlllc lulgm 5 his site m m anwcrornn ansllcrpmm Forun quotmm Mien quotmum mm m lure in ma won plmcm yuu mu llc l qumlun nVcrlllUtllllgtcuullmlimime quot quot 39 cu l lL l l M y m quot Cine 1qu axskg clue cut w a l lacs I 5 p A 33 Suppun ms site lndayl Pm Pam quot lm quotMAv wlw 7mm 7 Clue Clue Etnume lg l l MW 7 1 l fk to P ay Pattern W Finer Ls wwc mml mll 39m limglmmm l njwmvan EH mm W L quot 2 Wham mch mammal mung Example Applications of NLP Example Applications 0f NLP Question Answering Machine Translation amazonde c l n n n Answcl us woman Arlgwpnml Syszem who 1 mlan m hlll gums v L v H l m mam mm m 1 when canal Slmxhdol News39 wc Xexearrhv Reviewingv Mac lava Thesaurus ruudmg renrhrugv 9 SEIKCN l 5mm l 39E395mquot l WEle l 6 gt V a Mxhtlkui cues An 0 l wuunns l m l m mgrnpud um umquot um Stubm 39 All mmgwlcs l a 6 g ALLES MUSS RAUS e JETZI ZLl GRElFENl l Sthnapprhenlaqen l l w 7 mun A sault or preventive strike The 6 man ll L in mm ullCV l m m LynMel i l lll mm ilJClllLAH lglldl l m 1mm 39 39 l v l I Mm m quotquot5 bank aftgac r n thefs fvlet Unlon on 22 June 1941 1 use 1050 my Oulrvlew a if N am a ram EUR Qllm linn Amazurl de reader Wauld you Ilka a sell Mare nf Used amp again starting rmm EUR msu V mmquot Artikgl verkaulen l lm l nmrrlcd m blll gm quot quot Gerhard Ballmfalk Offerer dispatches In 12 workingdays Pllm39hle answers 34 3 What 1 ynu mean Their uglnmn m thls I i lll m mlllllcd In Mollmlll Fu h Gale III I Ml IIl lllm m lll l ll lll nmilln huw39 rim I ll hl u l 4i luv nl Cu nus ta mum and l med w me he ltgnlv mu mam I 3 21me the W mama pm a 5 WV 5mm ma lil Luau I mu lr l I ml M W4 Full 394 l 1 ll mllil v l w c rx an a mnney back New fetch the Try your qucsllun on uhcr engines Allll 39l lll IlIl 39 Flltllll l L taxes back Paperbackr 154 m e m mm Ffm mm are mum am July 1297 x 53quot 3595mm a ml at l l m l lullm mm mm m 2min in Amazama Verkautsrang 204595 Example Applications of NLP Automatically generate Harlequin Romance novels Goals 0f the course Introduce you to NLP problems and solutions Relation to linguistics amp statistics a Give you some hands on practice with data and mm m m Myanmmck r dM a handful of methods lr39 At the end you should Agree that language is subtle and interesting Feel some ownership over the formal amp statistical models Be able to build some useful NLP system of your choosing This Class Assumes you come with some skills Some basic statistics decent programming skills in a language 0 your choice although solu ions etc But it s something like an Al Systems class 5 on with da a Often practical issues dominate over theoretical niceties Course Logistics Professor Andrew McCallum gt 7 TA Aron Culotta I Gary Huang Time TueThu 230345pm Mailing list 055858305 umass edu More information on Web site httpMMANcsumassedulmccallumcourses nlp2004 Grading 5 short written homeworks should take less than 30 minutes each some handson experience help you set expectations for the midterm and nal 3 programming assignments no way to really internalize without doing it should be fun Final project with a partner chance to explore a special interest at end ofterm Midterm amp Final and classroom participation Syllabus Outline Grammars and parsing Foundations probability amp info theory Language models Spam ltering Collocations word clustering disambiguation Finite state machines Markov models Part ofspeech tagging Modern parsing techniques Information extraction Semantics Question answering Dialog systems Recommended Reading Manning amp Schutze Chapter 11 section 1 Context Free Grammars topic ofnext class Manning amp Schutze Chapter 3 for background on linguistics Thank you Intro Questions Implicatures Decision theory Conclusion 00 000000 OOOOOOOOO 0000000000 000 The pragmatics of questions and answers Part 2 Partition semantics and decision theoretic pragmatics Christopher Potts UMass Amherst Linguistics CMPSCI 585 December 4 2007 UMass Amherst Linguistics intro Que mpiKaLnres i m ons Deus rieory Conziusion gooooo ooooooooo oooooooooo 000 What kind of answer is that A cautionary tale Example After Solan and Tiersma 2005220 A I lost my wallet Do you know where it is B I saw it on the kitchen table earlier intro Questions mpiKatnres Deuw rheory Conziusion m cocoon ooooooooo 0000000000 000 What kind of answer is that A cautionary tale Example After Solan and Tiersma 2005220 Context 3 has pocketed A39s wallet A I lost my wallet Do you know where it is B I saw it on the kitchen table earlier lntro Questions linleatnres Deuw rlieory CumluSlon 0 000000000 0000030000 000 What kind of answer is that A cautionary tale Example After Solan and Tiersma 2005220 Context 3 has pocketed A39s wallet A I lost my wallet Do you know where it is B I saw it on the kitchen table earlier Observations 0 2339s answer is superficially partial 0 But contextual factors might lead A to believe that B in fact over answered Enrichment No but lntro Que on linleatnres Deuw rlieory Cunzlusion 0 303000 ooooooooo 0000030000 000 What kind of answer is that A cautionary tale Example After Solan and Tiersma 2005220 Context 3 has pocketed A39s wallet A I lost my wallet Do you know where it is B I saw it on the kitchen table earlier Observations 0 2339s answer is superficially partial 0 But contextual factors might lead A to believe that B in fact over answered Enrichment No but What pragmatic facts has 3 leveraged into a devious answer intro Questions immatures Decisiwn rheory Cunzhision oo oooooo ooooooooo 0000000000 000 Question semantics Groenendijk and Stokhof 1982 Interrogative denotations partition the information state into equivalence classes based on the extension of the question predicate inn Questions immatures De m rl in Lunrlusion Op mom oooocoooo oouooooooo gm Question semantics Groenendijk and Stokhof 1982 lnterrogative denotations partition the information state into equivalence classes based on the extension of the question predicate Answering 0 Fully congruent answers identify a single cell 0 Partial answers overlap with more than one cell 0 Over answers identify a proper subset of one of the cells mm Quesuons mmawes op ucoooo smocooou Polar questions Did Sam Iaugh v E W v E Iaughsam ifF W E Iaughsam W E W Iaughedsam W 7 Iaughedsam mu Quesuons m watnres oooooo oouocooom Polar questions Did Sam Iaugh v E W v E Iaughsam ifF W E Iaughsam W E W Iaughedsam W 7 Iaughedsam Answers Wm Quesmons mmawes De n rhewy Polar questions Did Sam Iaugh v E W v E Iaughsam ifF W E Iaughsam W E W I Iaughedsam Wi laughedsam Answers Wm Quesmons mmawes De n rhewy Polar questions Did Sam Iaugh v E W v E Iaughsam ifF W E Iaughsam W E W Iaughedsam W 7 Iaughedsam Answers No mm Quesuons cu 300 mmwawes Lunrhmon Constituent questions Who Iaughed v e W Vdlaughdv ifF aughdw W e W m rNv fxv w L1 it L1 is in m x M 33 7 n W N w T39Kx w y gt w hm Quesuons cu 30000 anmatnres souocooog Lunrmswon Q Ju Constituent questions Who Iaughed v e W Vdlaughdv ifF aughdw W e W r f M 6 7 k M is M Ms 2 93 Ix A My 32 A Answers cu 000000000 Constituent questions Who Iaughed v e W Vdlaughdv ifF aughdw W e W 2 y39x w er w w J Li a L is in m 3 3 W I L A t L m Answers Bart and Lisa Lunrmsw n ma cu oouooooog Constituent questions Who Iaughed v e W Vdlaughdv ifF aughdw W 5 M 5 3 g Answers Bart Lisa Maggie and Burns Lunrmswon one Lunrmsw n D Ju mu Quesuons mmmat cu oooocoooo Constituent questions Who Iaughed v e W Vdlaughdv ifF aughdw W e W 5 5 w 1 52 if 1 A t 5 is if A t if 161 A Answers No one Questions immatures team n rheow 09 goat Lunrlusion Douocooom gouooooooo 3w Ordering Ans values We get a rough measure of the extent to which p answers Q by inspecting the cells in Q with which p has a nonempty intersection Definition Answer values Ansp7Q 76 Q l p q l Example Bart Did Sam laugh Lisa laughedsam W 7 laughedsam Questions liiipliatiires Dem n l 30000 r yew souocooom Lunrlusion Douooooooo 3w Ordering Ans values We get a rough measure of the extent to which p answers Q by inspecting the cells in Q with which p has a nonempty intersection Definition Answer values Ansp7Q 76 Q l p q l Example Bart Did Sam laugh Lisa Yes lAnsl 1 laughedsam W 7 laughedsam Questions liiipliatiires Dem n l 30000 r yew souocooom Lunrlusion Douooooooo 3w Ordering Ans values We get a rough measure of the extent to which p answers Q by inspecting the cells in Q with which p has a nonempty intersection Definition Answer values Ansp7Q 76 Q l p q l Example Bart Did Sam laugh Lisa No lAnsl 1 laughedsam W 7 laughedsam Questions liiipliatiires op JC De m n rheow scuocooou ocuocoooao Lunr iusion 00 m Ordering Ans values We get a rough measure of the extent to which p answers Q by inspecting the cells in Q with which p has a nonempty intersection Definition Answer values Ansp7Q 76 Q l p q l Example Bart Did Sam laugh Lisa I heard some giggling lAnsl 2 laughedsa n W 7 laughedsam inn Questions liiipliatnres Decisiwn weary Lunrlusion we 3 004003000 oouooooooo ecu Overly informative answers Ans values are a bit too blunt iflAnspQl 1 then lAnsp Ql 1whenever p Q p Example Bart ls Sam happy at his newjob Lisa lhappysamll W happysamll mm Questions linleatnres new in weary Lunr luSlOn we oouooooom oouooooooo or Overly informative answers Ans values are a bit too blunt iflAnspQl 1 then lAnsp Ql 1whenever p Q p Example Bart ls Sam happy at his newjob Lisa Yes lAnsl 1 I happ sam l Wilhapp sam l lntw Questions liiiplinW S Decish n rheoin Lunrlusion we oouocooom 0040000000 gm Overly informative answers Ans values are a bit too blunt iflAnspQl 1 then lAnsp Ql 1whenever p Q p Example Bart ls Sam happy at his newjob Lisa Yes and he hasn39t been tojail yet lAnsl 1 I happys Wilhapp sam l intro Questions impiwatnres Densin rhewy Com insion oo goeso ooooooooo oooooooooo 000 A preference ordering Definition Relevance GampS van Rooij p gtQ q iff Ansp7 Q C Ansq7 Q Or Ansp Q Ansq7 Q and q C p lntro Questions linleatiires Dem in rheoin 304003000 oouoo goo A preference ordering Definition Relevance GampS van Rooij p gtQ q iff Ansp7 Q C Ansq7 Q Or Ansp Q Ansq7 Q and q C p Example In the previous example llhaPPYSamll gt7happysam llhaPPYSam A no39jailsamll While their Ans values are the same the first is a superset of the second Lunr lusion 2m mmwaw Questions Dooocooom Jessa Ordering questions We can order questions as well via the granularity of the cells Example Q Which planet are you from Q Which country are you from 7 Where are you from39 Q Which city are you from mix Questions immatures etlsl n n 4 30300 gooocooou ouimcoooou Ordering questions We can order questions as well via the granularity of the cells Example Q Which planet are you from Q Which country are you from 7 Where are you from39 Q Which city are you from Definition Fine grainedness GampS QEQ ifFVqEQHq EQ qu If Q is more fine grained than Q then an exhaustive answer to Q is more informative than an exhaustive answer to Q lmphcatures De m m 4 oouooooom oouooooooo Lunrluslon om Conversational implicatu res If is not maximal with regard to the A quotQquot ordering lm then quotpquot will be laden B quotPquot with conversational implicatures The goal To get a grip on the nature and source of these incongruence implicatures mphcatures Deuw rheory Lundus 000003000 0000030000 Qua Congruence out of incongruence Zeevat 1994 A proper partial answer is then one where the answerer indi cates that she is not giving a full answer to the question that was asked but a standard answer to a weaker question ntro Que on lmphcatures Deuw rheory Cunzluswon oo 300000 000003000 oooooooooo or Congruence out of incongruence Zeevat 1994 A proper partial answer is then one where the answerer indi cates that she is not giving a full answer to the question that was asked but a standard answer to a weaker question It is then the task of the person interpreting the answer to work out the weaker question on the basis of the formal properties of the answer and the original question imphcatures Decisiwn rheory Lunziusion louooooom 0000030000 or Congruence out of incongruence Zeevat 1994 A proper partial answer is then one where the answerer indi cates that she is not giving a full answer to the question that was asked but a standard answer to a weaker question It is then the task of the person interpreting the answer to work out the weaker question on the basis of the formal properties of the answer and the original question Surer someone has said the comparable thing for overly informative answers I haven39t found a source yet though mphcatures De m m 4 00003000 oouooooooo Lum uswon Partial answers What city does Barbara live in Moscow Petersburg I New York Boston Kazan Volgograd I Chicago Austin Wm Que on lmphcatures Deuw rhewy Cunzlusxon as 30000 00003000 0000030000 or Partial answers 3 What city does Barbara live in Well she lives in RUSSIA I Moscow Petersburg I New York Boston I Kazan l Volgograd I Chicago Austin imphcatures De m m 4 04009000 oouooooooo Lunrhision om Partial answers A B What city does Barbara live in Well she lives in RUSSIA E K r gt What country does Barbara live in in this case recoverable from the intonation Biiring 1999 I Moscow i Petersburg I New York i Boston i I Kazan i Volgograd I Chicago i Austin i impiicatures De m m 4 04009000 oouooooooo Lunriusion om Partial answers A B What city does Barbara live in Well she lives in RUSSIA E K r gt What country does Barbara live in in this case recoverable from the intonation Biiring 1999 Moscow Petersburg I IIBosfon gtWhat city does Barbara live in7 RUSSa lmphcatures beam ma 4 owmcooou mum Partial answers A B What city does Barbara live in7 Well she lives in RUSSIA E K r gt What country does Barbara live in in this case recoverable from the intonation Biiring 1999 Moscow Petersburg I IIBosfon gtWhat city does Barbara live in7 RUSSall The speaker39s motivations for this partial answer are variable Some contexts might even enrich it to a complete answer The pragmatic theoryjust accounts for the disparity between question and reply mphcatures Dems Weary Canduswon 00000000 oooooooooo Goo Over answering A Gricean Classic Is C happy at his nerob A mphcatures Dem rheory 00000000 oooooooooo Conduswon coo Over answering A Gricean Classic Is C happy at his nerob 4 Yes and he hasn39t been to prison A imphcatures Decisiwn mew Lunzius 00000000 0000030000 Qua Over answering A Gricean Classic i Is C happy at his newjob and has he been to prison E A i Is C happy at his nerob Yes and he hasn39t been to prison A 3 just one of the many questions that I might be addressing imphcatures uoooooom Over answering A Gricean Classic i Is C happy at his newjob and has he been to prison i g 39 i i ls C happy at his newjob Yes and he hasn39t been to prison A 3 just one of the many questions that I might be addressing Grice 1975 At this point A might well inquire whatB was implying what he was suggesting or even what he meant by saying that C had not been to prison The answer might be any one of such things as that C is the sort of person likely to yield to the temptation provided by his occupation that imphcatures De m m 4 omoosoom oouooooooo Lunriusion coo Over answering A Gricean Classic i Is C happy at his newjob and has he been to prison E A i Is C happy at his nerob Yes and he hasn39t been to prison A 3 just one of the many questions that I might be addressing C is appy C is not happy imphcatures De m m 4 omoosoom oouooooooo Lunriusion coo Over answering A Gricean Classic i Is C happy at his newjob and has he been to prison E A i Is C happy at his nerob Yes and he hasn39t been to prison A 3 just one of the many questions that I might be addressing Hf93 lls C happy at his newjob7 Yes and he hasn39t been to jail mphcatures Decmun Weary Canduswon 00000000 oooooooooo Goo Over answering Pragbot data Did you find anything A mphcatures Dems Weary 00000000 oooooooooo Condusion coo Over answering Pragbot data Did you find anything 4gtyep h at the top exit A B impiicatures De m m 4 ouoooooom oouooooooo Lunriusion coo Over answering Pragbot data iDid you find anything and if so where is it E Did you find anything yep h at the top exit A B the extra information is a product of the task they need to retrieve specific cards impiicatures Dems mew Cmiwon 00000000 oooooooooo Goo Over answering Required for felicity Is Ali in room 4437 A impiicatures Dems Hiech 00000000 oooooooooo Conziusion coo Over answering Required for felicity Is Ali in room 4437 E No she 39s in room 434 B De My ri in Lunriusion oouoogoogo gm impiicatures 000030000 Over answering Required for felicity What room is Ali in I Is Ali in room 4437 No she 39s in room 434 A B a nearly conventionalized case of over answering though contextual factors can bring out the polar question understanding mphcatures Dems Weary 00000000 oooooooooo Conduswon coo Over answering via enrichment Okay do we have fire coming up through the roofyet A impiicatures De i in ri sumocom i 4 oooooooooo Lunriusion coo Over answering via enrichment Okay do we have fire coming 4 We have a lot of hot embers up through the roof yet blowing through A 23 Strictly speaking we enrich this to No but based on our assumptions about the speaker39s cooperativity and epistemic state A robotic No would be terrible in this context impiicatures Der m n rheoi v somecom Lunriusion 3000000000 3w Over answering via enrichment What is the state of the roof E Okay do we have fire coming We have a lot of hot embers up through the roofyet A blowing through 23 Strictly speaking we enrich this to No but based on our assumptions about the speaker39s cooperativity and epistemic state A robotic No would be terrible in this context lmplicatures Decisiwn mew Lunzlus 00000300 0000030000 Qua lncom para bles perhaps The relation E is a partial one and hence not all questions are comparable along this dimension Speakers exploit this fact Do we have a quiz today lmplicatures Decisiwn mew Lunzlus 00000300 0000030000 Qua lncom para bles perhaps The relation E is a partial one and hence not all questions are comparable along this dimension Speakers exploit this fact Do we have a quiz today 39 It39s rainy outside lmplicatures De m m 4 cameoCm oouooooooo Lunrlusion om lncom para bles perhaps The relation E is a partial one and hence not all questions are comparable along this dimension Speakers exploit this fact What is the weather like Do we have a quiz today It39s rainy outside lmplicatures swamom lncom para bles perhaps The relation E is a partial one and hence not all questions are comparable along this dimension Speakers exploit this fact What is the weather like Z2 Do we have a quiz today It39s rainy outside Topic changing via an answer whose question is incompa rable to the original one However if it is known that there is always a quiz when the weather is bad then the two questions might be contextually comparable lmplicatures De m m 4 oouoooooo oouooooooo Lunrlusion Uncertainty Example After Solan and Tiersma 2005220 Context 3 has pocketed A39s wallet A I lost my wallet Do you know where it is B I saw it on the kitchen table earlier It39s natural to enrich this to No but but that inference depends upon implicit assumptions about 2339s cooperativity lmplicatures otmocooon Uncertainty Example After Solan and Tiersma 2005220 Context 3 has pocketed A39s wallet A I lost my wallet Do you know where it is B I saw it on the kitchen table earlier It39s natural to enrich this to No but but that inference depends upon implicit assumptions about 2339s cooperativity General pragmatic principles and their limits 0 Our general pragmatic inferences tell us only that 2339s answer is non maximal and thus that some other question is in play 0 Our assumptions about the context take us to more specific enrichments impiicatures oouocooo Desiderata 0 What counts as a felicitous answer Earlier I suggested that we keep two questions in mind 0 What shapes the questions themselves B 4 Q A E i What shapes Q and what determines Q rlieory Lunz luS Qua De lSl in 0000030000 lmplicatures oooooooo Desiderata 0 What counts as a felicitous answer Earlier I suggested that we keep two questions in mind 0 What shapes the questions themselves A B Q A E l What shapes Q and what determines Q The final section of this talk introduces some concepts from decision theory with the goal of answering all these questions Decision theory oooooooooo immatures sooocoooo Decision problems Definition Decision problems A decision problem is a structure DP W7 5 PS7 A7 Us W is a space of possible states of affairs 5 is an agent P5 is a subjective probability distribution for agent 5 A is a set of actions that 5 can take and U5 is a utility function for 5 mapping action world pairs to real numbers Lunrlusion 2m immature Decision theory Lunrlusion omooooooo 3w Douocooom Example Schlepp the umbrella Example Should agent 5 bring his umbrella with him The chance of rain is 60 5 is no fan of rain and hates to get wet It39s not good but not terrible to carry the umbrella on a dry day Best of all is sunshine with no umbrella to schlepp rain no rain U5 l W1 l W2 l W3 l W4 W5 umbrella l 2 2 l 2 l 72 l 72 no umbrella l 78 78 l 78 l 8 8 immatures Decision theory 09 i oouocooou summermu Example Schlepp the umbrella Example Should agent 5 bring his umbrella with him The chance of rain is 60 5 is no fan of rain and hates to get wet It39s not good but not terrible to carry the umbrella on a dry day Best of all is sunshine with no umbrella to schlepp rain no rain U5lW1lW2lW3lW4lW5 umbrellal 2i 2i 2l72l72 no umbrella l 78 l 78 l 78 8i 8 Solution concept 5 is deciding under uncertainty If he is rational he will choose the action with the highest expected utility a calculation that balances his utility values with probabilities immatures Decision theory Lunriusion oouocooom 0000030000 ecu Expected utilities Expected utilities take risk into account when measuring the usefulness of performing an action Definition For decision problem DP W7 5 PS7 A7 U5 the expected utility of an action a E A Equa 2 mm Ua W WSW immatures Decision theory COMluSlOn ooooooooo 0000000000 000 Solving decision problems Definition Utility value of a decision problem Let DP W757 P5A7 U5 be a decision problem UVDP max EUDpa 36A Definition Solving a decision problem Let DP W7 5 P57 A7 U5 be a decision problem The solution to DP is choose a such that EUDpa UVDP lntro Question linleatnres Decision theory Lunzlus oo 303000 000003000 000000000 Qua Utility value of new information Incoming information might change the decision problem by changing the expected utilities Definition Conditional expected utility Let DP W757 F 5A7 U5 be a decision problem EUDPalP Z PWlP U37 W WSW linleatnres Decision theory smocoom 3040000in Utility value of new information Incoming information might change the decision problem by changing the expected utilities Definition Conditional expected utility Let DP W757 F 5A7 U5 be a decision problem EUDPalP Z PWlP U37 W WSW Example 0 EUno umbrella 716 o EUno umbrellalW4W5 80 given no rain 0 EUumbrella 4 0 EU umbrellalw1W27 W3 20 given no rain immatures Decision theory Lunrlusion ouuocgoom swooguooo 3m Changes to the utility value The utility value of new information is a measure of the extent to which it changes the utility value of the decision problem Definition UVDpP gig UVDpalP UVDP Example For the umbrella example the utility valuejumps from 4 to 80 when we learn that it will be sunny Thus UVSchleppW47 W5 linleatnres Decision theory soooooooo 0000000300 Action propositions Definition van Rooij DP W7 5 F 5A7 U5 is a decision problem and a E A 3 W E W l U5a7 W 2 U5a7 W for a E A Example Action propositions for schlepping the umbrella rain no rain U5 l W1 W2 W3 l W4 W5 umbrellal 2l 2l 2l72l72 no umbrella l 78 l 78 l 78l 8l 8 umbrella W17 W27 W3 no umbrella W47 W5 Question linleatnres Decision theory 0 303000 000003000 Lunzlusion 0000030000 coo Action propositions Definition van Rooij DP W7 5 F 5A7 U5 is a decision problem and a E A 3 W E W l U5a7 W 2 U5a7 W for a E A Example Action propositions for schlepping the umbrella rain norain UglwllWQlW3lW4lW5 umbrellal 2l 2l 2l72l72 noumbrellal78li8li8l 8l 8 umbrella W17 W27 W3 no umbrella W47 W5 We39ve induced a question meaning from the utility function Intro 0 Implira39nlres Decision theory Conclusion 5300000000 0000000000 OOC Optimal understandings Example Pragbot data Context Player 2 is looking for Player 2 Did you find anything Player 1 yep h at the top exit P1 found cards P1 found JQKH P1 found JQKS P1 found no cards Up2 W1Wk Wk1Wm Wm1Wn meet P1 10 O 0 keep searching O 10 O immatures Decision theory Lunzlus 000003000 000003000 Qua A decision theoretic View of incongruence lncongruous answers don39t signal an alternative question but rather an alternative decision problem one that the answerer would like to addresssolve A DP HQ A DP immatures Decisiwn mew Conciusion 000003000 0000030000 oa Summing up and looking ahead A unified pragmatics Basic relations between questions and between questions and their answers provides a unified perspective on partial answering over answering and the gray area between them A B Q7A linleatnres Decisiwn rlieory Conclusion ooooooooo 0000030000 oa Summing up and looking ahead Greater generality via decision theory The decision theoretic approach frees us from having to define everything in terms of questions Decision problems are more general and thus they can be used to understand other discourse moves Word Disambiguation Lecture 8 Introduction to Natural Language Processing CMPSCI 585 Fall 2004 University of Massachusetts Amherst Andrew McCaIIum Words and their meaning Three lectures Last time Collocations multiple words together different meaning than than the sum of its parts Today Word disambiguation one word multiple meanings Expectation Propagation Future Word clustering multiple words same meaning Today s Main Points What is word sense disambiguation and why is it useful Homonymy Polysemy Other similar NLP problems 4 Methods for performing WSD Supervised na39ive Bayes Unsupervised Expectation Propagation Word Sense Disambiguation The task is to determine which of various senses of a word are invoked in context True annuals are plants grown from seed that blossom set new seed and die in a single year Nissan s Tennessee manufacturing plant beat back a United Auto Workers organizing effort with aggressive tactics This is an important problem Most words are ambiguous have multiple senses Problem statement A word is assumed to have a finite number of discrete senses Make a forced choice between each word usage based on some limited context around the word Converse word or senses that mean almost the same image likeness portrait facsimile picture Next lecture WSD important for Translation The spirit is willing but the esh is weakquot The vodka is good but the meat is spoiledquot Information Retrieval query wireless mousequot document Australian long tail hopping mousequot Computational lexicography To automatically identify multiple de nitions to be listed in a dictionary Parsing To give preference to parses with correct use of senses There isn t generally one way to divide the uses of a word into a set of nonoverlapping categories Senses depend on the task Kilgarriff 1997 WSD Many other cases are harder 0 title Nameheading of a book statute work of art of music etc Material at the start of a film The right of legal ownership of land The document that is evidence of his right An appellation of respect attached to a person s name A written work WSD types of problems Homonymy meanings are unrelated 7 bank ofa river 7 bank financial institution Polysemy related meanings as on previous slide 7 title ora book 7 title material at the start or a film Systematic polysemy standard methods of extending a meaning suc as from an organization to the building where it is housed e The Speaker of the legislature e The legislature decided today 7 He opened the door and entered the legislature word 39equently takes on further related meanings h r through systematic polysemy or metap o Upper and lower bounds on performance Upper bound human performance 7 How often do humaniudges agree on the correct sense assignment 7 Particularlv interesting irvou onl contex given o machine metho A good test for ariv NLF lnelilodi e Gale 1992 give pairs ofvvords in context humans sav irthev are the same sense Agreement 919 forword With clear senses but 65770Uu ror polvsemous Words v give humans the same input d Lower bound simple baseline algorithm 7 Always piclltthe most common sense roreach Word 7 Accuracv depends greatlv on sense distrioutionl goesocm Senseval competitions Senseval 1 September 1998 Results in Computers and the Humanities 3412 OUP Hector corpus Senseval 2 In rst halfof 2001 WordNet senses httpViMANitribrighton acukeventssenseva WSD automated method performance Varies widely depending on how dif cult the disambiguation task 39s Accuracies over 90 are commonly reported on the classic o en fairly easy word disambiguation tasks pike star interest Senseval brought careful evaluation of dif cult WSD many senses different POS Senseval 1 ne grained senses wide range oftypes 7 Overall about 75 accuracv e Nouns about80 accuracv e verbs about 70 accuracv WSD solution 1 expert systems Small 1980 Hirst 1988 Most early work used semantic networks frames logical reasoning or expert system methods for disambiguation based on contexts The problem got quite out of hand The word expert for throvil is currently six pages long but should be ten times that sizequot Small and Rieger 1982 WSD solution 2 dictionarybased Lesk1986 A word s dictionary de nitions are likely to be good indicators for the senses they de ne One sense for each dictionary de nition Look for overlap between words in de nition and words 39n context at hand Word ashquot Sense De nition l liee 2i t e elive ramilv 2 litiriieil liie seiiu residue leitvvilEll CUTllllltS IllllE material isliiimeti quotThis Cigar purns slowy and creates a stirrssn se se1E sense2l h is one ofthe last treesto Come into tear sensell sense2u Insuf cient information in de nitions Accuracy 50 70 WSD solution 3 thesaurusbased Walker 1987 Yarowsky 1992 Occurrences of a word in multiple thesaurus subject codes is a good indicator of its senses Count number of times context words appear among the entries for each possible subject code Increase coverage of rare words and proper nouns by also looking in the thesaurus for words that cooccur with context words more often than chance g Hawking cooccurs with cosmology black hole Word Sense Roget categom Accuracy star space object UNIVERSE 96 celebrity ENTERTAINER 95 starshaped INSIGNIA 82 An extra trick global constraints Yarowsky 1995 One sense per discourse the sense of a word is highly consistent within a document Get a lot more context words because combine the context of multiple occurrences True for topic dependent words Not so true for other items like adjectives and verbs e g make take Other similar disambiguation problems Sentence boundary detection I live on Palm Dr Smith lives downtown Only really ambiguous when word before the period is an abbreviation which can end a sentence not something like a title word alter the period is capitalized and can be a proper name otherwise it must be a sentence end Contextsensitive spelling correction I know their is a problem with there account WSD solution 4 supervised classification Gather a lot of labeled data words in context handlabeled into different sense categories Use naive Bayes document classification with context as the document Straightforward classification problem Simple powerful method Requires handlabeling a lot of data 0 Can we still use naive Bayes but without labeled data7 WSD sol n 5 unsupervised disambiguation wordcontext labeled according to sense it h with Train one multinomial per class via maximum likelihoo What youjust did for HW1 wordcontext unlabeled Label is missing 28 years ago Maximum Likelihood from Incomplete Data via the EM Algorithm By A P DEMPSTER N M me and D E RUBIN Harvmi University and Educullanul Texling Service Read hefure the Rom STA nsncAl Scottiv at a meeting organized by the RISEAKCH SFUHDN on Wednesday December m 1976 Professor 5 D SILVEY in the Chair SUMMARY A i u 39 for 39 quot39 quotL A 39 from incomplnlc data is presented at various levels of generality Theory showing the monotone behaviour or the likelihood and convergence of this algorithm is derived Many examples are sketched including missing value situations applicalions to grouped censored or truncaled data 39te mixture models variance component estimation hyperparaiueler estimation iteratively reweighted least squares and factor analysis Keywords MAXIMUM LIKELIHDDD NCDMPLEI39E DATA EM ALGORXTHM msmuox MODE 1 ImoDucuoN This paper presents a general approach to iterative computation of maximum likelihood the algorithm consists of an expectation step followcd by a maximization step we call it the an algorithm The air nrm c i remarka39hle in mt hecau t or the simplicit and generality of Filling in Missing Labels with EM Dempster etal 77 Ghahramani amp Jordan 95 McLachlan amp Krishnan 97 Expectation Maximization is a class of iterative algorithms for maximum likelihood estimation with incomplete data Estep Use current estimates of model parameters to guess value of missing labels Mstep Use current guesses for missing labels to calculate new estimates of model parameters Repeat E and Msteps until convergence Finds the model parameters that locally maximize the probability of both the labeled and the unlabeled data Recall Na39l39ve Bayes Pick the most probable class given the evidence c argmaxcj Prcj d C a class like Planning d a document like language intelligence proof Bayes Rule Naive Bayes P V M P d I Prcjld PrcjPrd lcj z fC1 1 W39lcj Prd EPrcUPrwd yck Wd the i th word in d like pl39oof Recall Parameter Estimation in Na39I39ve Bayes Estimate of Pc 1C tdE Pcj oun cl IC 2C0untd ck k Estimate of Pwc 1 2Countwdk Ikej IV HE 2Countwdk rl dkEc Pw lcj EM Recipe Initialization Create an array Pcd for each document and ll it with random normalized values Set Pc to the uniform distribution Mstep likelihood Maximization Calculate maximumlikelihood estimates for parameters Pwc using current Pcd 1 2Counuwndg PC IdA 13w Ic fquot IV HE ECnuquHzIJPa39 ldk may Estep missingvalue Estimation Using currentparameters calculate new Pcd the same way you would at test time Ade Prmggjjic Loop back to Mstep until convergence Converged when maximum change in a parameter Pwc is below some thres o d EM We could have simply written down likelihood taken derivative and solved but unlike complete data case not solvable in closed form must use iterative method gradient ascent EM is another form of ascent on this likelihood surface Convergence speed and local minima are all issues If you make hard 0 versus 1 assignments in Pcd you get the Kmeans algorithm Likelihood will always be highest with more classes Use a prior over number of classes orjust pick arbitrarily EM Some good things about EM no learning rate parameter very fast for low dimensions each iteration is guaranteed to improve likelihood adapts unused units rapidly Some bad things about EM can get stuck in local minima ignores model cost how many classes both steps require considering all explanations of the data all classes SemiSupervised Document Classification Training data with class labels i39lu Data available at training time but without class labels pages Web pages Web p user user says are user says are nasn t seen or said interesting uninteresting anytning about Can we use the unlabeled documents to increase accuracy SemiSupervised Document Classi ication Build a classi cation e model to estimate the model using limited labels ofthe unlabeled labeled data documents in H 5 Use all documents to build a new classi cation model which is otten more accurate because it is trained using more data An Example Labeled Data Unlabeled Data Baseball Ice Skating Tara Liginski s FE quot m 2 substitute iee skates nun ner Peneettnpieiurnp l penennanee sne i graeeg tne iee Witn a series eipeneetiurnps ng Wun tne geig mega Tara nglnskl buught a newhuuseluihei arents Pele Ruse is nut E m 5m u an Practice attne iee iinkeveiyday Pr i Llyllriskl i n EIEIl After EM Prl Llplhskl i iee Skating u u Before EM Pr Lrpmskrlnm PrlLlplnSkl isasebaiii WebKB Data Set student faculty cuurse prbieet 4 classes 4199 documents from CS academic departments Word Vector Evolution WIth EM inteiiigenee 00 D 0 DD artificial lemure lemure understanding ee ee DEM 7 00 00 i 00 00 due identical handuut rus ue rllt arrange prebiern assignment a ES Et duut dartmuuth tay set natural DDam hvv E gnlthE yu s iegie humevvurk prebiern preying Darn rulu set pustscript D 15 adtgtt EM as Clustering I unlabeled EM as Clustering Gone Wrong 20 Newsgroups Data Set gaaaaamm39oa39w wfff39f g 9 9662 6 g i i 3 3 3 1 a E E 3028quot 0 65 g 999g 1 w 6 a o w o I g a g wto 9n 31313 lll a i 4 w aa w wa 23 20 class labels 20000 documents 62k unique words Amway 100 90 Na unlabeled documenls 4 60 L 70 60 50 4m gt 30 r 20 r l 0 Newsgroups Classification Accuracy varying labeled documents 10000 unlabeled documenls r 5 0 IUD 200 Sun Innu 20m 5000 Number ol Labeled Documents Lexical Acguisition Lecture 9 Introduction to Natural Language Processing CMPSCI 585 Fall 2004 University of Massachusetts Amherst Andrew McCaIIum Words and their meaning Th ree lectu res Collocations multiple words together different meaning than than the sum of its pa s Word disambiguation one word multiple meanings This time Lexical Acquisition verb subcategorization attachment ambiguity selectional preference semantic similarity multiple words same meaning Today s Main Points What is Lexical Acquisition and why is it useful Verb subcategorization Attachment ambiguity Selectional preference Clustering words into semantically similar classes Lexical Acquisition Acquiring the properties of words Practical filling holes in dictionaries Lots of useful information isn t in dictionaries anyway e g associated with versus associated to Claim most knowledge of language is encoded in words and their properties Acquiring collocations and word sense disambiguation are examples of lexical acquisition but there are many other types Why Lexical Acquisition Language evolves ie new words and new uses of old words are constantly invented Traditional Dictionaries were written for the needs of human users Lexicons are dictionaries formatted for computers In addition to the format lexicons can be useful if they contain quantitative information Lexical acquisition can provide such information Verb Phrase and Subcategorization Verb phrase consists of Verb a number of constituents Examples VP gt V disappear VP gt V NP prefer a morning flight VP gt V NP PP leave Boston in the morning VP gt V PP leave on Thursday VP gt V 8 said you had a 200 fare Sentential complement Different verbs different constituents A verb phrase can have many possible kinds of constituents but Not every verb is compatible with every verb phrase Examples want VP gt V NP I want a ight want VP a VVPto I want to fly to quot nd VP gt V NP I found a ight nd VP a V VPto I found to y to Transitive take a direct object nd I nd a ight Intransitive do not take a direct object disappear I disappeared a ight Transitive and Intransitive are simple examples of verb subcategorization Verb Subcategorization Verbs express their semantic arguments with different syntactic means frame slots for arguments of the verb category verbs that take the same semantic ar s eg verbs with semantic arguments theme and recipient subcategory verbs that use the same syntactic means to express these semantic arguments Additional examples subcategory 1 prepositional phrase He donated a large sum of money to the church subcategory 2 doubleobject He gave the church a large sum of money Examples of subcategorization frames Intransitive verb NPsubject The woman walked quot Transitive verb NPsubject NPobject John loves Mary quot Ditransitive verb NPsubject NPdirect object NPindirect object Mary gave Peter owers quot Intransitive with PP NPsubject PP I rent in Northampton quot Sentential complement NPsubject clause I know that she likes you quot Transitive with sentential complement NPsubject NPobject clause She told me that Gary is coming quot One verb multiple subcategorizations One verb can take different subcategorization frames Example find VPVNP findaflight VPVNP NP find meaflight Subcategorization needed for parsing She told the man where Peter grew up She found the place where Peter grew up She told the man where Peter grew up She found the place where Peter grew up Helps us get attachment right Unfortunately most dictionaries don t contain subcategorization frames and those that do are horribly incomplete Learning subcategorization frames Brent 1993 Does some particular verb take direct object frame 2 VP V NP Cues for frames eg assume that pattern verb pronoun capitalized word punctuation identifies direct object frame with error rate e01 Count occurrences n number of occurrences of verb in question m number of occurrences of cue with verb Hypothesis testing H0 verb does not take frame 77 2 gym 1m PHIII uu mum 2 m Learning subcategorization frames Brent 1993 Manning 1993 Brent s system does well at precision but not well at recall Manning 93 s system addresses this problem by using a tagger and running the cue detection on the output of the tagger eg say ndN DET NPquot indicates direct object frame Manning s method can learn a large number of subcategorization frames even those that have only lowreliability cues Learned subcategorization frames Manning 1993 m Correct Incorrect Oxford AL Dictionam bridge 1 1 1 burden 2 2 depict 2 3 emanate 1 1 k 1 5 occupy 1 3 remark 1 1 4 2 5 1 Error in remark attributed intransitive frame probably due to quotAnd here we are 10 years later with the same problemsquot Mr Smith remarked Attachment Ambiguity Where to attach a phrase in the parse tree I saw the man with the telescope What does with a telescopequot modify Is the problem Al complete Yes but Proposed simple structural factors Rightassociationmmball1973 lovv or near attacnment early closure of NP Minimal attacnment Frazier 1978 depends on grammar nlgn or dlstaht attacnment late closure ofNP Attachment Ambiguity Such simple structural factors dominated in early psycholinguistics and are still widely invoked In the V NP PP context right attachment gets right 5576 of the cases But this means that it gets wrong 3345 of the cases Attachment Ambiguity The children ate the cake with a spoonquot quotThe children ate the cake with frostingquot Joe included the package for Susanquot Joe carried the package for Susanquot Ford Bresnan and Kaplan 1982 It is quite evident then that the closure effects in these sentences are induced in some way by the choice of the lexical items Simple model Log likelihood ratio A common and good way of comparing between two exclusive alternatives Same idea as a na39i39ve Bayes classi er For example Pwith a spoon ate gt Pwith a spoon cake Attachment P roblematic Example Chrysler confirmed that it woud end its troubled venture with Maserati 39 J 2mm end 5156 607 venture 1442 155 Get wrong answer Pwithend 6075156 0118 Pwithventure 1551442 0107 Should also express preference for attaching low Attachment Method Hindle amp Rooth1993 Event space all V NP PP sequences but PP must modify V or first N Don t directly decide whether PP modifies V or N Rather look at binary random variables VAp Is there a PP headed by p which attaches to v NAp Is there a PP headed by p which attaches to n Both can be 1 He put the book on World War II on the table Attachment Method Hindle amp Rooth 1993 Independence assumptions PVAP NAp v n PVAp vn PNAp vn PVAp v PNAp n Decision space first PP after NP NBl PAttchpnvn PVAP0 v VA 1v PNAP1n 10 PNA 1n PNAP1rn It doesn t matter what VAp is If both are true the first PP after the NP must modify the noun in phrase structure trees lines don t cross Attachment Method Hindle amp Rooth 1993 But conversely in orderfor the first PP headed by the preposition p to attach to the verb both VAp1 and NAp0 must ho d PAttachpvvn PVAp1 NAp0vn PVAp1v PNAp0n We assess which is more likely by a log likelihood ratio PAHE hi iilii ll 1 i 1 r I n p 0512 PAlfil h1Il l39 71 FHA 11llvPNAplllv 3 Pump um If large positive decide verb attachment if large negative decide noun attachment Attachment Method Hindle amp Rooth 1993 o How do we learn probabilities From smoothed MLEs PVAP1V CVp CV PNAP1n Cnp Cn How do we get estimates from unlabeled corpus Use partial parser and look for unambiguous cases The road to London is long and winding She sent him to the nursery to gather up his toys x I F Attachment Method Hindle amp Rooth1993 Hindle and Rooth heuristically determine Cvp Cnp and Cn0 from unlabeled data Build an initial model by counting all unambiguous cases Apply initial model to all ambiguous cases and assign them to the appropriate count if I exceeds a threshold 22 Divide the remaining ambiguous cases evenly between the counts increase Cvp and Cnp by 05 for each Attachment Method Example Hindle amp Rooth 1993 Moscow sent more than 100000 soldiers into Afghanistanquot Other attachment issues There are attachment questions other than prepositional phrases adverbial participial noun compounds Examples door bell manufacturer door bell manufacturer Unix system administrator Unix system administrator Data sparseness is a bigger problem with many of these In general indeterminacy is quite common We have not signed a settlement agreement with them Either reading seems equally plausible Lexical acquisition semantic similarity Previous models give same estimate to all unseen events Unrealistic could hope to refine that based on semantic classes of words Examples Susan had never eaten a fresh durian before Although never seen eating pineapple should be more likely than eating holograms because pineapple is similar to apples and we have seen eating apples An application selectional preferences Most verbs prefer arguments of a particular type Such regularities are called selectional preferences or selectional restrictions Bill drove aquot Mustang car truck jeep Selectional preference strength how strongly does a verb constrain direct objects see versus unknotted Measuring selectional preference strength Assume we are given a clustering of direct object nouns Resnick 1993 uses WordNet s m DP39i39lllP39 Z Plz39li39l ltig Selectional association between a verb and a class PlrliillugI D W2 Aii r 39 81 Proportion that its summand contributes to preference strength For nouns in multiple classes disambiguate as most I39kely sense AUX ii i iiiiix Alli l El lilSN39 l ii Selection preference strength made up data Noun class c Hg P c eat Pic seeL Pic find people 025 001 0 25 0 33 furniture 025 0 01 025 033 food 025 097 0 25 0 33 action 025 0 01 025 001 SPS Sv 176 000 035 Aeat food 1 08 A nd action 013 Selectional Preference Strength example Resnick Brown corpus mm 1 A1111 c1115 1 Noun n Aiv m Class mum 449 Speech act zraqedv 2 as wmmumauon label 1111 mmmmn my a 22 n 11 lealure my 59 Lommumuliun 1mm 1 1w mmmummlmu mmemhw 3pr 31 1141111119111 minke o 20 mm arcummme Lammwvi 1 21 mmmumunun 11141141 1 21 111111111 lLalmu mu 80 111111111 12mmquot 41241 amle am a 79 emuy rut1mm in 111 111mm letter 726 writing market 0 no commerce But how might we measure word similarity for word classes Vector spaces A document by word matrix A cosmonaut astronaut mnon av truck 1 d1 0 1 0 11 o 1 1 o o a 1 o D u u 11 o n n 1 1 d o o o 1 o 111 o o o u 1 But how might we measure word similarity for word classes Vector spaces wordbyword matrix B 1111111 m 11m rnimnnam avrnna 1 Similarity measures for binary vectors Sim1larity measure De nition matching coef cient 1x r1 Yl E25133quot 1 1 1 1 3 Dice coef cient mm 1 1 r 1 11 SJ L I f Jaccard coef cient A modi erbyvhead matrix C Overlap coef cient WI usmnraut stmnnut 0mm ar mi mine American 0 1 a 1 1 snauwnlkmg 1 1 u u L m1 1 n 1 1 full 0 CI l D C 12111 D 3 0 l l Cosine measure Example of cosine measure on wordbyword matrix on NYT 11 V V xm costx m WM 1Z139wa1Z111yf maps vectors onto umt 1rcle by dividmg through by lenglha 111111115 5111112011114 SEA 1111191 963 thus word 1 Nearest ne1qhbur gam39r 71er 737 prmwr 77F us 71 m 7m 1211 ell 932 dedlne 321 m 930 drab 929 engmeemd genetically 755 drugs ass research 4357 am 555 red named 514 Robert us 309 Mm 11011 3 You gaz always 951 Probabilistic measures Dis simiarity measure Definition KL divergence Dthq pz39 109 Skew Dmilar i 1 Ma JensenShannon was IRad i7Di Hi DWHL2MJ L1 norm Manhattan 2 rIr mi Neighbors of word company Lee Skew or 00m j s Euclidean airline business city business airiine airiine bank rm industry ageriLy bank program rm siate organization deparrment aqency ank manufacturer group system nerwork govr m ay industry iry series govt iriduslry portion Examples of Verb Subcategorization Frame Functions m Example NP NP sumeer emeer greet greeted B NF 5 sumeer iause up NP iNF subjem infinitive n p serene 55mm NP NPS subject ubjeci ciause EH mundane Wm attend NF NF iNF sumeer emem infinitive EH mien mm attend
Are you sure you want to buy this material for
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'