Conversation

The problem

• Conversation as collaborative behavior
• Interpretation and generation
• Utterances as actions: speech act theory (Austin, Searle)
  • Generation as planning to achieve communicative goals
  • Interpretation as recognition of speaker's plans
  • Types of speech acts: request, inform, promise, etc.
  • Speech act independent of the linguistic form which realizes it: indirect speech acts
    • Where's the post office?
    • Can you tell me where the post office is?
    • You wouldn't happen to know where the post office is, would you?
• Mutual knowledge and beliefs
• Conversational structure: closure and grounding: presentation and acceptance; adjacency pairs; turn-taking
• Conversational implicature; Grice's Maxims

A classifier for dialogue acts

• Dialogue acts: request, inform, yes-no question, check question, backchannel, etc.
• Features (Jurafsky et al., 1998)
  • Words and collocations; dialogue-specific N-gram model (probability of words given previous words and particular dialogue act)
  • Prosody
  • Conversational structure
• To find the dialogue act d* with the highest probability for an observation of a sentence o with prosody f and word sequence W:
  d* = argmax_d P(d|o)
  = argmax_d P(d) P(o|d)
  = argmax_d P(d|d_t-1) P(f|d) P(W|d)

Dialogue as a Markov decision process (Levin et al., 1998)

• Objective function for a dialogue designed to satisfy a particular goal: weighted function of number of interactions, cost of data retrieval, cost of data presentation, distance from application goal
• Markov decision processes: states, actions, reinforcement function, next-state function, policy
• Reinforcement learning: learning an optimal policy by optimizing a cost function for an MDP
  • Optimal policy in terms of Q-values expressing the sum of discounted future rewards (γ is the discount rate, s' and a' the next state and action)
    Q(s,a) = r(s,a) + γ Σ_s' P(s'|s,a) max_a' Q(s',a')
  • Updating Q(s,a) on the basis of reinforcement received and current estimate of best Q(s',a') for actual next state s' (η is the learning rate)
    ΔQ(s,a) = η[r(s,a) + γ max_a' Q(s',a')]
  • Deciding on an action: exploitation (using the Q-values) vs. exploration (trial-and-error)
• Training with a user model instead of on real data

Plan-based dialogue agents (Allen et al.)

• Each act defined in terms of the preconditions that need to be satisfed to make it successful and the effect that it has on the hearer
• STRIPS-style planning
  • Planning knowledge is organized in operators which can add or delete states in the world
  • Each operator has preconditions, states which must be true before it can be applied and effects, the addition or deletion of states
  • Planning (over-simplified)
    • Given an initial set of states characterizing the world and one or more desired states, find operators with the desired states as effects.
    • Check the preconditions of each selected operator. If the preconditions are satisfied, apply the operator and change the world accordingly (add or delete the effect states). If not, add each unsatisfied precondition to the desired states.
    • Halt when there are no more desired states.
• Implementing speech-act theory in a STRIPS-style planner; two over-simplified examples

  Request (sp, hr, act)
  Preconditions:
    Believe (sp, Cando (hr, act))
    Want (sp, Request (sp, hr, act))
    Channel (sp, hr)
  Effect:
    Believe (hr, Want (sp, act))
  
  Inform (sp, hr, prop)
  Preconditions:
    Believe (sp, prop)
    Want (sp, Inform (sp, hr, prop)
    Channel (sp, hr)
  Effect:
    Believe (hr, Believe (sp, prop))
  

  In order to use these operators in planning, we need two additional operators, which could be assumed to hold in a cooperative, trusting sort of world.

  Cause-to-want (agt1, agt2, act)
  Preconditions:
    Believe (agt2, Want (agt1, act))
    Believe (agt2, Cando (agt2, act))
  Effect:
    Want (agt2, act)
  
  Convince (agt1, agt2, prop)
  Precondition:
    Believe (agt2, Believe (agt1, prop))
  Effect:
    Believe (agt2, prop)
  

• Example of planning a simple speech act

  Initial state:
    Inside (Frank, Room3)
    Believe (Frank, Cando (Frank, Go-Out (Frank, Room3)))
    Believe (Self, Cando (Frank, Go-Out (Frank, Room3)))
    Channel (Self, Frank)
  
  Final state:
    Outside (Frank, Room3)
  
  Selecting Go-Out operator, with bindings
    agt = Frank, src = Room3
  Satisfies
    Outside (Frank, Room3)
  Has preconditions
    Inside (Frank, Room3) [satisfied]
    Want (Frank, Go-Out (Frank, Room3))
  
  Selecting Cause-to-Want operator, with bindings
    agt1 = Self, agt2 = Frank,
    act = Go-Out (Frank, Room3)
  Satisfies
    Want (Frank, Go-Out (Frank, Room 3))
  Has preconditions
    Believe (Frank, Want (Self, Go-Out (Frank, Room3)))
    Believe (Frank, Cando (Frank, Go-Out (Frank, Room3)))
       [satisfied]
  
  Selecting Request operator, with bindings
    sp = Self, hr = Frank,
    act = Go-Out (Frank, Room3)
  Satisfies
    Believe (Frank, Want (Self, Go-Out (Frank, Room3)))
  Has preconditions
    Believe (Self, Cando (Frank, Go-Out (Frank, Room3)))
      [satisfied]
    Channel (Self, Frank) [satisfied]
    Want (Self, Request (Self, Frank, Go-Out (Frank, Room3)))
  
  Assuming the speaker (Self) has control over her own wants,
    she can simply create the new goal
    Want (Self, Request (Self, Frank, Go-Out (Frank, Room3))),
    thus satisfying all of the preconditions
  

Planning questions

• ∃x (Believe (Mary, (Name (Mother (John)) = x)))
  Knowref (Mary, x, Name (Mother (John)))

• Believe (Ken, Mammal (Whale)) or Believe (Ken, not (Mammal (Whale)))
  Knowif (Ken, Mammal (Whale))

• Operators for asking questions

  Informref (sp, hr, x, p(x))
  Preconditions:
    Knowref (sp, x, p(x))
    Want (sp, Informref (sp, hr, x, p(x)))
    Channel (sp, hr)
  Effect:
    Knowref (hr, x, p(x))
  

  Informif (sp, hr, p)
  Preconditions:
    Knowif (sp, p)
    Want (sp, Informif (sp, hr, p)
    Channel (sp, hr)
  Effect:
    Knowif (hr, p)
  

Recognizing a speaker's plans

• Knowing S's plan can aid in making useful responses
  • H can execute other actions required as a part of S's plan
  • H can recognize obstacles in S's plan and do something about them
  • H can find errors in S's beliefs and correct them
• Example: Jack: How much is a ticket for the 3:00 to Chicago? (There is no 3:00 train to Chicago; the next train leaves at 3:30.)
  • Anticipated actions

    Informref (Clerk, Jack, y, Price (Ticket (Train.1530)))
    Give (Clerk, Jack, Ticket (Train.1530))
    

  • Obstacles

    Knowref (Jack, x, Price (Ticket (Train.1530)))
    Knowref (Jack, x, Depart-Loc (Train.1530))

  • Belief errors

    Believe (Jack,
      ∃x
        (Train (x) and Dest (x, Chicago) and Depart-Time (x) = 1500)

  • Appropriate response: There's no 3:00 train; the next one is at 3:30. The ticket costs $50.

Indirect speech acts

• Example: Do you know the departure gate for the train to Chicago?
• 3 possibilities
  • S really wants to knowif the proposition.
  • S has a plan that has the proposition (or its negation) as a precondition.
  • S wants the proposition to be true.
• Plan recognition based on the third possibility

  Take-Trip (Jack, Train1, Chicago)
     decomposes to
  Go-To (Jack, Depart-Loc (Train1))
     presupposes
  Knowref (Jack, Depart-Loc (Train1))
     effect of
  Informref (Clerk, Jack, x, Depart-Loc (Train1))
     presupposes
  Believe (Jack, Knowref (Clerk, x, Depart-Loc (Train1)))
     effect of (if yes)
  Knowif (Jack, Knowref (Clerk, x, Depart-Loc (Train1)))
     effect of
  Informif (Clerk, Jack, Knowref (Clerk, x, Depart-Loc (Train1)))
     presupposes
  Want (Clerk, 
        Informif (Clerk, Jack,
                  Knowref (Clerk, x, Depart-Loc (Train1))))
     effect of
  Request (Jack, Clerk,
           Informif (Clerk, Jack,
                     Knowref (Clerk, x
                              Depart-Loc (Train1))))
  

© 2008. Indiana University and Michael Gasser. www.cs.indiana.edu/classes/B651/conversation.html 2008-04-23