1 Natural Language UnderstandingLing575 Spoken Dialog Systems April 17, 2013

2

3 Natural Language UnderstandingGenerally: Given a string of words representing a natural language utterance, produce a meaning representation

4 Natural Language UnderstandingGenerally: Given a string of words representing a natural language utterance, produce a meaning representation For well-formed natural language text (see ling571), Full parsing with a probabilistic context-free grammar Augmented with semantic attachments in FOPC Producing a general lambda calculus representation

5 Natural Language UnderstandingGenerally: Given a string of words representing a natural language utterance, produce a meaning representation For well-formed natural language text (see ling571), Full parsing with a probabilistic context-free grammar Augmented with semantic attachments in FOPC Producing a general lambda calculus representation What about spoken dialog systems?

6 NLU for SDS Few SDS fully exploit this approach

7 NLU for SDS Few SDS fully exploit this approach Why not?

8 NLU for SDS Few SDS fully exploit this approach Why not?Examples of travel air speech input (due to A. Black) Eh, I wanna go, wanna go to Boston tomorrow If its not too much trouble I’d be very grateful if one might be able to aid me in arranging my travel arrangements to Boston, Logan airport, at sometime tomorrow morning, thank you. Boston, tomorrow

9 NLU for SDS Analyzing speech vs text

10 NLU for SDS Analyzing speech vs text Utterances:ill-formed, disfluent, fragmentary, desultory, rambling Vs well-formed

11 NLU for SDS Analyzing speech vs text Utterances: Domain:ill-formed, disfluent, fragmentary, desultory, rambling Vs well-formed Domain: Restricted, constrains interpretation Vs. unrestricted

12 NLU for SDS Analyzing speech vs text Utterances: Domain:ill-formed, disfluent, fragmentary, desultory, rambling Vs well-formed Domain: Restricted, constrains interpretation Vs. unrestricted Interpretation: Need specific pieces of data Vs. full, complete representation

13 NLU for SDS Analyzing speech vs text Utterances: Domain:ill-formed, disfluent, fragmentary, desultory, rambling Vs well-formed Domain: Restricted, constrains interpretation Vs. unrestricted Interpretation: Need specific pieces of data Vs. full, complete representation Speech recognition: Error-prone, perfect full analysis difficult to obtain

14 NLU for Spoken Dialog Call routing (aka call classification):(Chu-Carroll & Carpenter, 1998, Al-Shawi 2003) Shallow form of NLU

15 NLU for Spoken Dialog Call routing (aka call classification):(Chu-Carroll & Carpenter, 1998, Al-Shawi 2003) Shallow form of NLU Goal: Given a spoken utterance, assign to class c, in finite set C

16 NLU for Spoken Dialog Call routing (aka call classification):(Chu-Carroll & Carpenter, 1998, Al-Shawi 2003) Shallow form of NLU Goal: Given a spoken utterance, assign to class c, in finite set C Banking Example: Open prompt: "How may I direct your call?”

17 NLU for Spoken Dialog Call routing (aka call classification):(Chu-Carroll & Carpenter, 1998, Al-Shawi 2003) Shallow form of NLU Goal: Given a spoken utterance, assign to class c, in finite set C Banking Example: Open prompt: "How may I direct your call?” Responses: may I have consumer lending?,

18 NLU for Spoken Dialog Call routing (aka call classification):(Chu-Carroll & Carpenter, 1998, Al-Shawi 2003) Shallow form of NLU Goal: Given a spoken utterance, assign to class c, in finite set C Banking Example: Open prompt: "How may I direct your call?” Responses: may I have consumer lending?, l'd like my checking account balance, or

19 NLU for Spoken Dialog Call routing (aka call classification):(Chu-Carroll & Carpenter, 1998, Al-Shawi 2003) Shallow form of NLU Goal: Given a spoken utterance, assign to class c, in finite set C Banking Example: Open prompt: "How may I direct your call?” Responses: may I have consumer lending?, l'd like my checking account balance, or "ah I'm calling 'cuz ah a friend gave me this number and ah she told me ah with this number I can buy some cars or whatever but she didn't know how to explain it to me so l just called you you know to get that information."

20 Call Routing General approach:Build classification model based on labeled training data, e.g. manually routed calls Apply classifier to label new data

21 Call Routing General approach: Vector-based call routing:Build classification model based on labeled training data, e.g. manually routed calls Apply classifier to label new data Vector-based call routing: Model

22 Call Routing General approach: Vector-based call routing:Build classification model based on labeled training data, e.g. manually routed calls Apply classifier to label new data Vector-based call routing: Model: Vector of word unigram, bigrams, trigrams Filtering:

23 Call Routing General approach: Vector-based call routing:Build classification model based on labeled training data, e.g. manually routed calls Apply classifier to label new data Vector-based call routing: Model: Vector of word unigram, bigrams, trigrams Filtering: by frequency

24 Call Routing General approach: Vector-based call routing:Build classification model based on labeled training data, e.g. manually routed calls Apply classifier to label new data Vector-based call routing: Model: Vector of word unigram, bigrams, trigrams Filtering: by frequency Exclude high frequency stopwords, low frequency rare words Weighting

25 Call Routing General approach: Vector-based call routing:Build classification model based on labeled training data, e.g. manually routed calls Apply classifier to label new data Vector-based call routing: Model: Vector of word unigram, bigrams, trigrams Filtering: by frequency Exclude high frequency stopwords, low frequency rare words Weighting: term frequency * inverse document frequency

26 Call Routing General approach: Vector-based call routing:Build classification model based on labeled training data, e.g. manually routed calls Apply classifier to label new data Vector-based call routing: Model: Vector of word unigram, bigrams, trigrams Filtering: by frequency Exclude high frequency stopwords, low frequency rare words Weighting: term frequency * inverse document frequency (Dimensionality reduction by singular value decomposition) Compute cosine similarity for new call & training examples

27 Meaning Representations for Spoken DialogTypical model: Frame-slot semantics Majority of spoken dialog systems Almost all deployed spoken dialog systems

28 Meaning Representations for Spoken DialogTypical model: Frame-slot semantics Majority of spoken dialog systems Almost all deployed spoken dialog systems Frame: Domain-dependent information structure Set of attribute-value pairs Information relevant to answering questions in domain

29 Natural Language UnderstandingMost systems use frame-slot semantics Show me morning flights from Boston to SFO on Tuesday SHOW: FLIGHTS: ORIGIN: CITY: Boston DATE: DAY-OF-WEEK: Tuesday TIME: PART-OF-DAY: Morning DEST: CITY: San Francisco

30 Another NLU Example Sagae et 2009Utterance (speech): we are prepared to give you guys generators for electricity downtown ASR (NLU input): we up apparently give you guys generators for a letter city don town Frame (NLU output): .mood declarative .sem.agent kirk .sem.event deliver .sem.modal.possibility can .sem.speechact.type offer .sem.theme power-generator .sem.type event

31 Question Given an ASR output string, how can we tractably and robustly derive a meaning representation?

32 Question Given an ASR output string, how can we tractably and robustly derive a meaning representation? Many approaches: Shallow transformation: Terminal substitution

33 Question Given an ASR output string, how can we tractably and robustly derive a meaning representation? Many approaches: Shallow transformation: Terminal substitution Integrated parsing and semantic analysis E.g. semantic grammars

34 Question Given an ASR output string, how can we tractably and robustly derive a meaning representation? Many approaches: Shallow transformation: Terminal substitution Integrated parsing and semantic analysis E.g. semantic grammars Classification or sequence labeling approaches HMM-based, MaxEnt-based

35 Grammars Formal specification of strings in a language A 4-tuple:A set of terminal symbols: Σ A set of non-terminal symbols: N A set of productions P: of the form A -> α A designated start symbol S In regular grammars: A is a non-terminal and α is of the form {N}Σ* In context-free grammars: A is a non-terminal and α in (Σ U N)*

36 Simple Air Travel GrammarLIST -> show me | I want | can I see|… DEPARTTIME -> (after|around|before) HOUR| morning | afternoon | evening HOUR -> one|two|three…|twelve (am|pm) FLIGHTS -> (a) flight|flights ORIGIN -> from CITY DESTINATION -> to CITY CITY -> Boston | San Francisco | Denver | Washington

37 Shallow Semantics Terminal substitutionEmployed by some speech toolkits, e.g. CSLU

38 Shallow Semantics Terminal substitutionEmployed by some speech toolkits, e.g. CSLU Rules convert terminals in grammar to semantics LIST -> show me | I want | can I see|…

39 Shallow Semantics Terminal substitutionEmployed by some speech toolkits, e.g. CSLU Rules convert terminals in grammar to semantics LIST -> show me | I want | can I see|… e.g. show -> LIST

40 Shallow Semantics Terminal substitutionEmployed by some speech toolkits, e.g. CSLU Rules convert terminals in grammar to semantics LIST -> show me | I want | can I see|… e.g. show -> LIST see -> LIST I > ε can -> ε * Boston -> Boston

41 Shallow Semantics Terminal substitutionEmployed by some speech toolkits, e.g. CSLU Rules convert terminals in grammar to semantics LIST -> show me | I want | can I see|… e.g. show -> LIST see -> LIST I > ε can -> ε * Boston -> Boston Simple, but… VERY limited, assumes direct correspondence

42 Semantic Grammars Domain-specific semantic analysis

43 Semantic Grammars Domain-specific semantic analysisSyntactic structure: Context-free grammars (CFGs) (typically) Can be parsed by standard CFG parsing algorithms e.g. Earley parsers or CKY

44 Semantic Grammars Domain-specific semantic analysisSyntactic structure: Context-free grammars (CFGs) (typically) Can be parsed by standard CFG parsing algorithms e.g. Earley parsers or CKY Semantic structure: Some designated non-terminals correspond to slots Associate terminal values to corresponding slot

45 Semantic Grammars Domain-specific semantic analysisSyntactic structure: Context-free grammars (CFGs) (typically) Can be parsed by standard CFG parsing algorithms e.g. Earley parsers or CKY Semantic structure: Some designated non-terminals correspond to slots Associate terminal values to corresponding slot Frames can be nested Widely used: Phoenix NLU (CU, CMU), vxml grammars

46 Show me morning flights from Boston to SFO on TuesdayLIST -> show me | I want | can I see|… DEPARTTIME -> (after|around|before) HOUR| morning | afternoon | evening HOUR -> one|two|three…|twelve (am|pm) FLIGHTS -> (a) flight|flights ORIGIN -> from CITY DESTINATION -> to CITY CITY -> Boston | San Francisco | Denver | Washington SHOW: FLIGHTS: ORIGIN: CITY: Boston DATE: DAY-OF-WEEK: Tuesday TIME: PART-OF-DAY: Morning DEST: CITY: San Francisco

47 Semantic Grammars: Issues

48 Semantic Grammars: IssuesGenerally manually constructed Can be expensive, hard to update/maintain

49 Semantic Grammars: IssuesGenerally manually constructed Can be expensive, hard to update/maintain Managing ambiguity: Can associate probabilities with parse & analysis Build rules manually, then train probabilities w/data

50 Semantic Grammars: IssuesGenerally manually constructed Can be expensive, hard to update/maintain Managing ambiguity: Can associate probabilities with parse & analysis Build rules manually, then train probabilities w/data Domain- and application-specific Hard to port

51 Learning Probabilistic Slot FillingGoal: Use machine learning to map from recognizer strings to semantic slots and fillers

52 Learning Probabilistic Slot FillingGoal: Use machine learning to map from recognizer strings to semantic slots and fillers Motivation: Improve robustness – fail-soft Improve ambiguity handling – probabilities Improve adaptation – train for new domains, apps

53 Learning Probabilistic Slot FillingGoal: Use machine learning to map from recognizer strings to semantic slots and fillers Motivation: Improve robustness – fail-soft Improve ambiguity handling – probabilities Improve adaptation – train for new domains, apps Many alternative classifier models HMM-based, MaxEnt-based

54 HMM-Based Slot FillingFind best concept sequence C given words W

55 HMM-Based Slot FillingFind best concept sequence C given words W C*= argmax P(C|W)

56 HMM-Based Slot FillingFind best concept sequence C given words W C*= argmax P(C|W) = argmax P(W|C)P(C)/P(W)

57 HMM-Based Slot FillingFind best concept sequence C given words W C*= argmax P(C|W) = argmax P(W|C)P(C)/P(W) = argmax P(W|C)P(C)

58 HMM-Based Slot FillingFind best concept sequence C given words W C*= argmax P(C|W) = argmax P(W|C)P(C)/P(W) = argmax P(W|C)P(C) Assume limited M-concept history, N-gram words =

59 Probabilistic Slot FillingExample HMM

60 VoiceXML

61 VoiceXML W3C standard for voice interfacesXML-based ‘programming’ framework for speech systems Provides recognition of: Speech, DTMF (touch tone codes)

62 VoiceXML W3C standard for voice interfacesXML-based ‘programming’ framework for speech systems Provides recognition of: Speech, DTMF (touch tone codes) Provides output of synthesized speech, recorded audio

63 VoiceXML W3C standard for voice interfacesXML-based ‘programming’ framework for speech systems Provides recognition of: Speech, DTMF (touch tone codes) Provides output of synthesized speech, recorded audio Supports recording of user input

64 VoiceXML W3C standard for voice interfacesXML-based ‘programming’ framework for speech systems Provides recognition of: Speech, DTMF (touch tone codes) Provides output of synthesized speech, recorded audio Supports recording of user input Enables interchange between voice interface, web-based apps

65 VoiceXML W3C standard for voice interfacesXML-based ‘programming’ framework for speech systems Provides recognition of: Speech, DTMF (touch tone codes) Provides output of synthesized speech, recorded audio Supports recording of user input Enables interchange between voice interface, web-based apps Structures voice interaction

66 VoiceXML W3C standard for voice interfacesXML-based ‘programming’ framework for speech systems Provides recognition of: Speech, DTMF (touch tone codes) Provides output of synthesized speech, recorded audio Supports recording of user input Enables interchange between voice interface, web-based apps Structures voice interaction Can incorporate Javascript for functionality

67 Capabilities Interactions:Default behavior is FST-style, system initiative

68 Capabilities Interactions:Default behavior is FST-style, system initiative Can implement frame-based mixed initiative

69 Capabilities Interactions:Default behavior is FST-style, system initiative Can implement frame-based mixed initiative Support for sub-dialog call-outs

70 Speech I/O ASR: Supports speech recognition defined by GrammarsTrigrams Domain managers: credit card nos etc

71 Speech I/O ASR: TTS: Supports speech recognition defined byGrammars Trigrams Domain managers: credit card nos etc TTS: markup language Allows choice of: language, voice, pronunciation Allows tuning of: timing, breaks

72 Simple VoiceXML ExampleMinimal form:

73 Basic VXML Document Main body: