1Introduction to NLPCMSC 723: Computational Linguistics I ― Session #1Jimmy LinThe iSchoolUniversity of MarylandWednesday, September 2, 2009About MeNLP IRTeaching Assistant: Melissa EganCLIPAbout You (pre-requisites)| Must be interested in NLP| Must have strong computational background| Must be a competent programmer| Do not need to have a background in linguisticsAdministrivia| Text: z Speech and Language Processing: An Introduction to Natural Language Processing, Speech Recognition, and Computational Linguistics, second edition, Daniel Jurafsky and James H. Martin (2008)| Course webpage:z http://www.umiacs.umd.edu/~jimmylin/CMSC723-2009-Fall/| Class: z Wednesdays, 4 to 6:30pm (CSI 2107)z Two blocks, 5-10 min break in betweenCourse Grade| Exams: 50%| Class Assignments: 45%z Assignment 1 “warm up”: 5%z Assignments 2-5: 10% each| Class participation: 5%z Showing up for class, demonstrating preparedness, and contributing to class discussions| Policy for late and incomplete work, etc.Out-of-Class Support| Office hours: by appointment| Course mailing list: [email protected]’s get started!Let s get started!What is Computational Linguistics?| Study of computer processing of natural languages| Interdisciplinary fieldz Roots in linguistics and computer science (specifically, AI)z Influenced by electrical engineering, cognitive science, psychology, and other fieldszDominated today by machine learning and statisticsDominated today by machine learning and statistics| Goes by various namesz Computational linguisticsz Natural language processingz Speech/language/text processingz Human language technology/technologiesWhere does NLP fit in CS?Computer ScienceAlgorithms, TheoryProgramming LanguagesSystems, Networks…ArtificialIntelligenceDatabasesHuman-ComputerInteractionMachineLearningNLP Robotics…Science vs. Engineering| What is the goal of this endeavor?z Understanding the phenomenon of human languagez Building a better applications| Goals (usually) in tensionz Analogy: flightRationalism vs. Empiricism| Where does the source of knowledge reside?| Chomsky’s poverty of stimulus argument| It’s an endless pendulum?Success Stories| “If it works, it’s not AI”| Speech recognition and synthesis| Information extraction| Automatic essay gradingGhki|Grammar checking| Machine translation3NLP “Layers”SpeechRecognitionMorphological AnalysisParsingSemantic AnalysisRiPhonology Morphology Syntax Semantics ReasoningReasoning,PlanningSpeechSynthesisMorphological RealizationSyntactic RealizationUtterancePlanningSource: Adapted from NLTK book, chapter 1Speech Recognition| Conversion from raw waveforms into text| Involves lots of signal processing| “It’s hard to wreck a nice beach”Optical Character Recognition| Conversion from raw pixels into text| Involves a lot of image processing| What if the image is distorted, or the original text is in poor condition?What’s a word?| Break up by spaces, right? | What about these?Ebay | Sells | Most | of | Skype | to | Private | InvestorsSwine | flu | isn’t | something | to | be | feared达赖喇嘛在高雄为灾民祈福ﺔﻄﻠﺴﻟا ﻰﻟإ ﻲﻓاﺬﻘﻟا لﻮﺻو ىﺮآذ ﻲﻴﺤﺗ ﺎﻴﺒﻴﻟ百貨店、８月も不振 大手５社の売り上げ８～１１％減  ,   Morphological Analysis| Morpheme = smallest linguistic unit that has meaning| Inflectionalz duck + s = [Nduck] + [plurals]z duck + s = [Vduck] + [3rd person singulars] | Derivationalz organize, organizationz happy, happinessComplex Morphology| Turkish is an example of agglutinative languageuyuyorum I am sleepinguyuyorsun you are sleepinguyuyor he/she/it is sleepinguyuyoruz we are sleepinguyuyorsunuz you are sleepinguyuyorlar they are sleepinguyuduk we sleptFrom the root “uyu-” (sleep), the following can be derived…uyudukça as long as (somebody) sleepsuyumalıyız we must sleepuyumadan without sleepinguyuman your sleepinguyurken while (somebody) is sleepinguyuyunca when (somebody) sleepsuyutmak to cause somebody to sleepuyutturmak to cause (somebody) to cause (another) to sleepuyutturtturmak to cause (somebody) to cause (some other) to cause (yet another) to sleep. .From Hakkani-Tür, Oflazer, Tür (2002)4What’s a phrase?| Coherent group of words that serve some functionz Organized around a central “head”z The head specifies the type of phrase| Examples:z Noun phrase (NP): the happy camperzVerb phrase (VP): shot the birdzVerb phrase (VP): shot the birdz Prepositional phrase (PP): on the deckSyntactic Analysis| Parsing: the process of assigning syntactic structureSNP VPNNPNdetVNI saw the man[S[NPI ] [VPsaw [NPthe man] ] ]I saw the mandetNNSemantics| Different structures, same* meaning:z I saw the man.z The man was seen by me.z The man was who I saw.z …| Semantic representations attempt to abstract “meaning”pp gz First-order predicate logic: ∃ x, MAN(x) ∧ SEE(x, I) ∧ TENSE(past)z Semantic frames and roles: (PREDICATE = see, EXPERIENCER = I, PATIENT = man)Semantics: More Complexities| Scoping issues:z Everyone on the island speaks two languages.z Two languages are spoken by everyone on the island.| Ultimately, what is meaning?z Simply pushing the problem onto different sets of SYMBOLS?Lexical Semantics| Any verb can add “able” to form an adjective.z I taught the class. The class is teachable.z I loved that bear. The bear is loveable.z I rejected the idea. The idea is rejectable.| Association of words with specific semantic formszJohn: noun masculine properzJohn: noun, masculine, properz the boys: noun, masculine, plural, humanz load/smear verbs: specific restrictions on subjects and objectsPragmatics and World Knowledge| Interpretation of sentences requires context, world knowledge, speaker intention/goals, etc.| Example 1:z Could you turn in your assignments now? (command)z Could you finish the assignment? (question, command)El2|Example 2:z I couldn’t decide how to catch the crook. Then I decided to spy on the crook with binoculars.z To my surprise, I found out he had them too. Then I knew to just follow the crook with binoculars.[ the crook [with binoculars]] vs. [the crook] [with binoculars]5Discourse Analysis| Discourse: how multiple sentences fit together| Pronoun reference:z The professor told the student to finish the exam. He was pretty aggravated at how long it was taking him to complete it. | Multiple reference to same entity:z