1CS 188: Artificial IntelligenceFall 2008Lecture 26: NLP / Robotics / Vision12/4/2008Dan Klein – UC Berkeley12What 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…33 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”44Question 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 match55Information 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. LewisStatePostCompanyPerson66HMMs for Information Extraction77Syntactic 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]8PCFGs 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…..99Coreference 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.1010Machine Translation SOTA: much better than nothing, but more an understanding aid than a replacement for human translators New, better methodsOriginal TextTranslated Text[demo]1111Machine Translation Input: example translations (bitext) Output: a system which can translate new sentences?1212Learning MT ModelsPhrase Level ModelSyntax Level ModelVP PP PP VPVP VP1313MT Overview1414A Phrase-Based ModelSegmentation Translation Distortion1515A Phrase-Based Decoder Probabilities at each step include LM and TM1616MT from MonotextSourceTextTargetText Translation without parallel text?1717Output1818Language Evolution1919Robotics2020Motion 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]21Probabilistic 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 paths2222Policy Search2323Policy 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]24Policy 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.2525Object RecognitionQueryTemplate2626Comparing Local Regions2727Shape ContextCount the number of points inside each bin, e.g.:Count = 4Count = 10... Compact representation of distribution of points relative to each point2828Shape Context2929Similar RegionsNot Quite...Color indicates similarity using Geometric Blur Descriptor3030Match for Image
View Full Document