1CS 188: Artificial IntelligenceFall 2008Lecture 26: NLP / Robotics / Vision12/4/2008Dan Klein – UC Berkeley1What is NLP? Fundamental goal: analyze and process human language, broadly, robustly, accurately… End systems that we want to build: Ambitious: speech recognition, machine translation, information extraction, dialog interfaces, question answering… Modest: spelling correction, text categorization…3 Automatic Speech Recognition (ASR) Audio in, text out SOTA: 0.3% error for digit strings, 5% dictation, 50%+ TV Text to Speech (TTS) Text in, audio out SOTA: totally intelligible (if sometimes unnatural)Speech Systems“Speech Lab”4Question Answering Question Answering: More than search Ask general comprehension questions of a document collection Can be really easy: “What’s the capital of Wyoming?” Can be harder: “How many US states’ capitals are also their largest cities?” Can be open ended: “What are the main issues in the global warming debate?” SOTA: Can do factoids, even when text isn’t a perfect match5Information Extraction Unstructured text to database entries SOTA: perhaps 70% accuracy for multi-sentence temples, 90%+ for single easy fieldsNew York Times Co. named Russell T. Lewis, 45, president and general manager of its flagship New York Times newspaper, responsible for all business-side activities. He was executive vice president and deputy general manager. He succeeds Lance R. Primis, who in September was named president and chief operating officer of the parent. startpresident and CEONew York Times Co.Lance R. Primisendexecutive vice presidentNew York Times newspaperRussell T. Lewisstartpresident and general managerNew York Times newspaperRussell T. LewisStatePostCompanyPerson6HMMs for Information Extraction72Syntactic AnalysisHurricane Emily howled toward Mexico 's Caribbean coast on Sunday packing 135 mph winds and torrential rain and causing panic in Cancun, where frightened tourists squeezed into musty shelters .8[demo]PCFGs Natural language grammars are very ambiguous! PCFGs are a formal probabilistic model of trees Each “rule” has a conditional probability (like an HMM) Tree’s probability is the product of all rules used Parsing: Given a sentence, find the best treeROOT → S 375/420S → NP VP . 320/392NP → PRP 127/539VP → VBD ADJP 32/401…..9Coreference ModelingThe Weir Group , whose headquarters is in the U.S , is a large specialized corporation . This power plant ,which , will be situated in Jiangsu , has a large generation capacity.10Machine Translation SOTA: much better than nothing, but more an understanding aid than a replacement for human translators New, better methodsOriginal TextTranslated Text[demo]11Machine Translation Input: example translations (bitext) Output: a system which can translate new sentences?12Learning MT ModelsPhrase Level ModelSyntax Level ModelVP PP PP VPVP VP133MT Overview14A Phrase-Based ModelSegmentation Translation Distortion15A Phrase-Based Decoder Probabilities at each step include LM and TM16MT from MonotextSourceTextTargetText Translation without parallel text?17Output18Language Evolution194Robotics20Motion as Search Motion planning as path-finding problem Problem: configuration space is continuous Problem: under-constrained motion Problem: configuration space can be complexWhy are there two paths from 1 to 2?21[demo]Probabilistic Roadmaps Idea: just pick random points as nodes in a visibility graph This gives probabilistic roadmaps Very successful in practice Lets you add points where you need them If insufficient points, incomplete, or weird paths22Policy Search23Policy Search Problem: often the feature-based policies that work well aren’t the ones that approximate V / Q best E.g. your value functions from project 2 were probably horrible estimates of future rewards, but they still produced good decisions We’ll see this distinction between modeling and prediction again later in the course Solution: learn the policy that maximizes rewards rather than the value that predicts rewards This is the idea behind policy search, such as what controlled the upside-down helicopter24[demo]Policy Search* Advanced policy search: Write a stochastic (soft) policy: Turns out you can efficiently approximate the derivative of the returns with respect to the parameters w (details in the book, but you don’t have to know them) Take uphill steps, recalculate derivatives, etc.255Object RecognitionQueryTemplate26Comparing Local Regions27Shape ContextCount the number of points inside each bin, e.g.:Count = 4Count = 10... Compact representation of distribution of points relative to each point28Shape Context29Similar RegionsNot Quite...Color indicates similarity using Geometric Blur Descriptor30Match for Image
View Full Document
Unlocking...