Computational LinguisticsWhat is Computational Linguistics?Goals of this LectureIt’s 2007, but we’re not anywhere close to realizing the dream (or nightmare …) of 2001PowerPoint PresentationWhy is NLP difficult?Hidden StructureLanguage subtletiesWorld Knowledge is subtleWords are ambiguous (have multiple meanings)Headline AmbiguityThe Role of MemorizationSlide 13But there is too much to memorize!Rules and MemorizationRepresentation of MeaningHow to tackle these problems?Corpus-based Example: Pre-Nominal Adjective OrderingSlide 19Real-World Applications of NLPSynonym GenerationSlide 22Slide 23Levels of LanguageSlide 25Parsing at Every LevelTokens and TypesTokenization (continued)TerminologyExampleWhat does Tagging do?Significance of Parts of SpeechChoosing a tagsetSome of the best-known TagsetsThe Brown CorpusPenn TreebankHow hard is POS tagging?Important Penn Treebank tagsVerb inflection tagsThe entire Penn Treebank tagsetTagging methodsDefault TaggerTraining vs. TestingEvaluating a TaggerLanguage ModelingN-GramsFeatures and ContextsUnigram TaggerNth Order TaggingTagging with lexical frequenciesRule-Based TaggerThe Brill taggerBrill Tagging: In more detailAn exampleTransformation-based learning in the Brill taggerExamples of learned transformationsTemplatesProbabilities in Language ModelingNext Word PredictionSlide 60Human Word PredictionClaimApplicationsN-Gram Models of LanguageSimple N-GramsA Word on NotationComputing the Probability of a Word SequenceBigram ModelUsing N-GramsTraining and TestingShallow (Chunk) ParsingChunk Parsing ExamplesShallow Parsing: MotivationRepresentationComparison with Full Syntactic ParsingChunks and ConstituencyChunkingUnchunkingChinkingMergingApplying Chunking to Treebank DataSlide 82Slide 83Classifying at Different GranulariesExample: The Problem: Looking for a JobWhat is Information ExtractionSlide 87Slide 88Slide 89Slide 90IE in ContextLandscape of IE Tasks: Degree of FormattingLandscape of IE Tasks: Intended Breadth of CoverageLandscape of IE Tasks” ComplexityLandscape of IE Tasks: Single Field/RecordState of the Art Performance: a sampleThree generations of IE systemsLandscape of IE TechniquesTrainable IE systemsMUC: the genesis of IEMessage Understanding Conference (MUC)MUC Typical TextSlide 103MUC TemplatesSlide 105Slide 106Slide 107Slide 108Evaluating IE AccuracyMUC Information Extraction: State of the Art c. 1997Finite State Transducers for IEThree Equivalent RepresentationsQuestion AnsweringA of Search TypesBeyond Document RetrievalQuestions and AnswersSlide 117Slide 118Slide 119Slide 120The Problem of Question AnsweringSlide 122Question Answering from textPeople want to ask questions…A Brief (Academic) HistoryAskJeevesQuestion Answering at TRECSample TREC questionsTREC ScoringTop Performing SystemsExample QA SystemQA Block ArchitectureQuestion Processing FlowQuestion Stems and Answer TypesDetecting the Expected Answer TypeAnswer Type TaxonomyAnswer Type Detection AlgorithmAnswer Type HierarchyUnderstanding a Simple NarrativeTemporal Aspects of Narrative TextTemporal AssumptionsAllen’s 13 Temporal RelationsAllen’s Temporal OntologyDesiderata for Temporal Specification LanguageTemporal Expression TypesEventsDifferent Notions of EventsTIMEX3 Annotation SchemaExample TIMEX3 MarkupSlide 150Events and TimesFeatures of TimeMLRepresenting Time and Events in TextTemporal ExpressionsTimeML Event ClassesEvent ExpressionsLinksTLINK Temporal Anchoring/OrderingLinking Timex to TimexAnchoring Event to TimexOrdering EventsALINKAspectual LinksSLINKSubordinated LinksSLINK: Reported SpeechEvaluation of Answer Type HierarchyKeyword SelectionLexical Terms ExtractionKeyword Selection AlgorithmKeyword Selection ExamplesPassage RetrievalPassage Extraction LoopPassage Retrieval ArchitecturePassage ScoringSlide 176Answer ExtractionRanking Candidate AnswersFeatures for Answer RankingAnswer Ranking based on Machine LearningEvaluation on the WebCan we make this simpler?AskMSR System ArchitectureStep 1: Rewrite the questionsQuery rewritingQuery Rewriting - weightingStep 2: Query search engineStep 3: Gathering N-GramsStep 4: Filtering N-GramsStep 5: Tiling the AnswersResultsSlide 192IssuesIntermediate Approach: Surface pattern discoveryUse Pattern LearningPattern Learning (cont.)QA Typology from ISIExperimentsExperiments: pattern precisionExperiments (cont.)Slide 201Shortcomings & ExtensionsShortcomings... (cont.)Slide 204Slide 205Computational LinguisticsJames Pustejovsky Brandeis UniversityBoston Computational Linguistics Olympiad TeamFall, 2007What is Computational Linguistics?Computational Linguistics is the computational analysis of natural languages.Process information contained in natural language. Can machines understand human language?Define ‘understand’Understanding is the ultimate goal. However, one doesn’t need to fully understand to be useful.Goals of this LectureLearn about the problems and possibilities of natural language analysis:What are the major issues?What are the major solutions?At the end you should:Agree that language is subtle and interesting!Know about some of the algorithms.Know how difficult it can be!It’s 2007,but we’re not anywhere closeto realizing the dream(or nightmare …) of 2001Dave Bowman: “Open the pod bay doors.”HAL 9000: “I’m sorry Dave. I’m afraid I can’t do that.”Dave Bowman: “Open the pod bay doors, please, HAL.”Why is NLP difficult?Computers are not brainsThere is evidence that much of language understanding is built-in to the human brainComputers do not socializeMuch of language is about communicating with peopleKey problems:Representation of meaningLanguage presupposed knowledge about the worldLanguage only reflects the surface of meaningLanguage presupposes communication between peopleHidden StructureEnglish plural pronunciationToy + s  toyz ; add zBook + s  books ; add sChurch + s  churchiz ; add izBox + s  boxiz ; add izSheep + s  sheep ; add nothingWhat about new words?Bach + ‘s  boxs ; why not boxiz?Language subtleties Adjective order and placementA big black dogA big black scary dogA big scary dogA scary big dogA black big dogAntonymsWhich sizes go together?–Big and little–Big and small–Large and smallLarge and littleWorld Knowledge is subtleHe arrived at the lecture.He chuckled at the lecture.He arrived drunk.He chuckled drunk.He chuckled his way through the lecture.He arrived his way through the lecture.Words are ambiguous(have