Data Driven Approaches For Spoken Dialog Processing

Data Driven Approaches for SpokenDialog ProcessingGary Geunbae Lee, Ph.D., ProfessorDept. CSE, POSTECHEurope-Korea SDS workshop

Contents SLU DM On-going researches

Ubiquitous spoken dialog interface?Telematics Dialog Interface (POSTECH, LG, DiQuest)Car-navigationTele-serviceHome networkingRobot interface

What‟s hard – ambiguities, ambiguities, alldifferent levels of ambiguitiesJohn stopped at the donut store on his way home fromwork. He thought a coffee was good every few hours.But it turned out to be too expensive there. [from J.Eisner lecture note]- donut: To get a donut (doughnut; spare tire) for his car?- Donut store: store where donuts shop? or is run by donuts? or looks like a bigdonut? or made of donut?- From work: Well, actually, he stopped there from hunger and exhaustion, notjust from work.- Every few hours: That‟s how often he thought it? Or that‟s for coffee?- it: the particular coffee that was good every few hours? the donut store? thesituation- Too expensive: too expensive for what? what are we supposed to concludeabout what John did?

Spoken Dialog SystemUser SpeechSystem SpeechWhich date do you want to fly fromWashington to Denver?ASRResponseGenerationAutomatic SpeechRecognitionRGModels,RulesRecognized Sentence“I need a flight fromWashington DC toDenver roundtrip”System ActionGET DEPARTURE DATESLUDialogManagementDMSemantic MeaningSpoken LanguageUnderstandingORIGIN CITY: WASHINGTONDESTINATION CITY: DENVERFLIGHT TYPE: ROUNDTRIP

Spoken Language Understanding

SLU Spoken language understanding (SLU) is to map naturallanguage speech to frame structure encoding of itsmeanings. frame domain „ATIS‟ utt Show me flights from Denver to New Yorkon Nov. 18th /utt slot type „DA‟ name „Show Flight‟/ slot type „NE‟ name „FROM.CITY‟ Denver /slot slot type „NE‟ name „TO.CITY‟ New York /slot slot type „NE‟ name „MONTH‟ Nov. /slot slot type „NE‟ name „DAY NUMBER‟ 18th /slot /frame Automatic SpeechRecognitionxSequenceLabelingx,y frame domain „EPG‟ utt I want to watch LOST /utt slot type „DA‟ name „Search Program‟/ slot type „NE‟ name „PROGRAM‟ LOST /slot /frame Classification(Named Entity /Frame Slot)(Dialog Act / Intent)SequenceLabeling ModelClassificationModel(e.g. HMM, CRFs)(e.g. MaxEnt, SVM)x,y,zDialogManagement

Non-local ochicagoondec.to dec.Selected Trigger (return dec.)to dec.want dec.I dec. Long-distance dependency and Trigger Features Outline of Trigger Selection Algorithm

Non-local Features Learning & Precision-Recall Curveson Communicator DataInducer typeTime# featuresF1 435:12:111,3202,05088.3666.88Approx. 10:47:302:14:028004,22795.1772.23Approx. 20:11:101:34:374671,42195.8772.72Approx. 1 20:05:301:29:266084,22796.1973.01Approx.1: Only Non-localApprox. 2: ME-based

Joint SLUhkyz1,1yzT,1yz1,1xzytyt 1xtxt 1y T,1yz1,1zy 1,1 yzstartyzT,1zyzendy T,1yzstartsstartzzf2kzy t-1yzT,Jyz1,JyzT,Jyz1,Jzgky T,J Search Spacext-1 Factor Graph of Triangular-chain CRF

Joint ir-TravelDANE91.29 86.5492.7688.9692.85 86.3692.18 88.9493.77 88.24Robot-CaféDANE88.59 96.1189.4096.1387.74 96.0088.64 96.1389.47 96.12TelebankDANE94.53 88.5596.5888.8596.57 88.2994.65 88.8896.92 88.91TV-EPGDANE96.84 96.2996.9196.7696.86 96.3196.60 96.5196.99 96.94AverageDANE92.81 91.8793.9192.6893.51 91.7493.02 92.6294.29 92.55 A description of four dialog data setsData setAir-TravelRobot-CaféTelebankTV-EPG# of utt1,1786262,2391,917DA1282516NE5420177 Log-likelihood for DA, NE and Joint Optimization

Contents SLU DM On-going researches

Example-based Dialog Management

Introduction Pipeline Architecture for SDSSpeech InputInputRecognitionKeyboard InputSpeech RecognitionNatural Language ProcessingNaturalLanguageUnderstandingDialog Act RecognitionNamed Entity RecognitionDialogManagementDiscourse AnalysisDatabase QuerySystem Action PredictionNaturalLanguageGenerationInformation PresentationUtterance Realization Dialog Management– A central component to select correct system actions based onobserved evidences and inferred beliefs. Goal– Dialog modeling for practical deployment of multi-domain dialogsystem

Introduction Related Works– Knowledge-based approach Regularized Language & Grammar Hand-crafted Rules & Finite State Automaton Pros & Cons– This approach have been deployed in many practical application. ( )– Can be controlled by developers ( ) (-)– Not good for domain portability and flexibility. (-)– Data-driven approach A stochastic modeling using reinforcement learning [Levin et al.,2000]– Formalization : fully or partially observable Markov Decision Processes. Pros & Cons [Paek, 2006]––––The training is done automatically ( )Theoretically formalized ( )Time-consuming corpus collection & annotation (-)High Complexity & Hardly practical deployment (-)

Example-Based Dialog Modeling Concept– From Example-Based Machine Translation (EBMT) Nagao (1984) introduced the EBMT methodology.– Source Sentence Processing Finding Similar Sentence Retrieval Target Sentence– The idea of EBMT can be extended to determine the nextsystem actions by finding the similar dialog example in thecorpus.– Example-Based Dialog Modeling (EBDM) [Lee et al.,2006;Lee et al., 2007] A dialog model in which the system action can be selected by thesimilar user utterance within dialog corpus.– User Utterance Processing Finding Similar Utterance RetrievalSystem Action Dialog Example Database (DEDB)– Indexed by state variables chosen by system designer.

Example-Based Dialog Modeling Indexing and Querying– DEDB is semantically indexed and queried to generalize the data.Goal-Oriented Dialog Corpus (Domain Navigation)#1User: Where is the Korean restaurants?[Dialog Act wh-question][Main Goal search-location][LOC TYPE Korean restaurant]System: There are A, B, and C in D and E and F in G.[System Action inform(name,address)]DEDB (Dialog Example Database)User Utterance Where is the LOC TYPE?Domain navigationDialog Act wh-questionMain Goal search-locationLOC TYPE 1 (filled)LOC ADDRESS 0 (unfilled)LOC NAME 0ROUTE TYPE 0Previoius Dialog Act s Previous Main Goal s Discourse History Vector [1,0,0,0]System Action inform(name,address)#2User: Let me go the A in D.[Dialog Act request][Main Goal guide][LOC NAME A][LOC ADDRESS D]System: Ok. You selected the A in D.[System Action select(name,address)]System: Choose the route type of the fastest or the easiest path.[System Action specify(rotue type)]User Utterance Let me go the LOC NAME in LOC ADDRESS.Domain navigationDialog Act requestMain Goal guideLOC TYPE 0LOC NAME 1LOC ADDRESS 1ROUTE TYPE 0Previous Dialog Act wh-questionPrevious Main Goal search-locationDiscourse History Vector [1,1,1,0]System Action select(name,address); specify(route type)* Discourse History Vector [LOC TYPE, LOC ADDRESS, LOC NAME, ROUTE TYPE]

Example-Based Dialog Modeling Relaxation– Once there is no example, dialog experts have some relaxationstrategies according to the genre and domain of dialog. State can be approximated by relaxing particular state variables foravoiding data sparseness. Utterance Similarity– Select the best one among the retrieved dialog examples Considering the lexical and discourse history informationCurrent User UtteranceRetrieved ExamplesWhere is the LOC TYPE?Where is the LOC TYPE in LOC ADDRESS?Discourse History Vector : [1,0,0,0]Discourse History Vector : [1,1,0,0]Let me know where the LOC TYPE is?Discourse History Vector : [1,0,0,0]Lexico-Semantic Similarity (by edit distance)Discourse History Similarity (by cosine measure)

Example-Based Dialog ModelingDialogueCorpusUser’s emanticFrameAutomaticIndexingDiscourseHistoryQuery GenerationUtterance SimilarityDialogueExample DBRetrieval Lexico-semantic Similarity Discourse history SimilarityBest DialogueExampleTie-breakingDialogueExamples

Domain Spotter Feature ExtractionUser : When do the KBS dramas start?Linguistic AnalysisSemantic AnalysisWhen/WRB do/VBP the/DT KBS/NNP drama/NN start/VBLast Word start Last Marker ? Last Tag VBLast Verb start Last Noun drama First Noun KBSDialog Act WH-QUESTIONMain Goal SEARCHAgent SpotterTask AgentKeyword AnalysisBest Keyword drama Second Keyword startBest Class EPG Second Class NavigationDomain SpotterEPG domain20

Experimental Results Spotter Evaluation– Domain Spotter– Agent Spotter21

Experimental Results Dialog Modeling Evaluation– Success Turn Rate– Task Completion Rate22

Error Recovery SystemNoisy Input(from leDBError Detected NOSystemTemplateContaining some errors.Error Detected YESS {# of Examples, # of Contents, # of Slots}NLGA {HelpType, Content, lection

Error Detection of EBDM No Example– No dialog example is retrieved by both exact and partial matches areused. OOV, OOU, and unexpected input may be out-of-example. This is a potential error because out-of-example is hard tounderstand and manage.No Content– No information is retrieved using the slot values of the current dialogframe. In this case, the user does not know the slot values of interest orunexpected errors in SLU module occurs.No Slot– The understanding module cannot extract any slot value from the userutterance The utterance without slot information may be erroneous when NoExample is detected. Because, in goal-oriented dialogs, most utterances contain slotinformation to search contents.24

Error Recovery Strategy Our Goal– The system should give help messages to learn what and how to say.Error Recovery Strategy– UtterHelp A help message for possible utterance template– Triggered by No Example detection The system gives an example template of what the user could sayat this situation.– InfoHelp A help message for domain content database– Triggered by No Content detection The system recommends relevant contents which can be retrievedwith the current dialog frame– UsageHelp A longer help message for a system usage– Triggered by all (No Example/No Content/No Slot) detection This system provides guidelines of using the system25

Recovery ExampleUtterHelpUser: Please inform me a category of the restaurants that serves Korean food.ASR output: Please me a car of a restaurant that Korean foodSLU output: [REQUEST, GUIDE LOC, FOOD-TYPE Korean food][Error Detection: No Example]System: You can say "Please give me a category of the restaurants that serve [FOOD-TYPE]"to search restaurants of [FOOD-TYPE].InfoHelpUser: Please inform me a category of the restaurants that serves Korean food.ASR output: Please inform me a category of restaurant that Korean fishSLU output: [REQUEST, SEARCH LOC, FOOD-TYPE Korean fish][Error Detection: No Content]System: There is no content on "Korean fish". You can say "Korean food", "Koreanbeef", and "Japanese fish" as the slot of [FOOD-TYPE].26

Experimental Result User Evaluation [Lee et al., 2007]– Car navigation domain for 4 slot-filling dialog Provides support for the information and selection of the desired destinationin Pohang city.– About 160 places names related to the restaurants, hospital, etc.– 10 novice users with prior knowledge about the system 50 dialogs of evaluation set (5 dialogs for each user)– Measure TCR Task Completion Rate #AvgTurn # of user utters / # of dialogs #DetErr # of detected errors / # of dialogs27

Dialog for EPG (POSTECH)Unified Chatting and Goaloriented Dialog (POSTECH)

Contents SLU DM On-going researches

Context-sensitive Chatbot

Advanced ChatBot Discourse-Sensitive ChatBot– Most of chatbot can not reflect the discourse context of previous userturns. [ALICE, 2002; B. Shawar, 2002]Context-Free ChatBotUSER : Did you watch a Korean team’s gameyesterday?SYSTEM : What game?.USER : How come you didn’t know that?SYSTEM : Well, I don’t know.Obscure answeringWhat’s better?Context-Sensitive ChatBotUSER : Did you watch a Korean team’sgame yesterday?SYSTEM : What game?.USER : How come you didn’t know that?SYSTEM : I am not interested in sports.More intelligent answering