IWSDS 11th Dec. 2009

Using Collaborative Filteringto Predict User
Utterances in Dialogue
Ryuichiro Higashinaka, Noriaki
Kawamae, Kohji Dohsaka,and Hideki Isozaki
NTT Communication Science Labs.
1

Motivation• Our goal is to improve closeness between asystem and a user through dialogue– Useful for task-completion and continued use• Inducing user agreement is important for
improving closeness (Higashinaka et al., 2008)• One possible way to induce user agreement is tosay in advance what the user would say2

Predicting
what the userwould say
about cats anddogs.

ExampleCloseness
I like cats because they arecapricious, aren’t they?
Yes I Agree!

SystemAnd, I hate dogs because
they bark at me.

UserMe too!
Suppose that (a) the user likes cats for their capriciousness.
(b) the user doesn’t like dogs because they bark.
3

Previous Work• Importance of closeness– Bickmore et al., (2001, 2005)• Closeness improves task-completion inpossible face-threatening real-estate transactions• Closeness encourages the continued use of ahealth-care system• Need for inducing user agreement– Higashinaka et al. (2008)• The number of dialogue acts corresponding touser agreement correlates with closeness4

Goal of this work
• Predict user utterances to induce useragreement• However, it is difficult to predict every userutterance• Focus on predicting a user’s evaluative
expressions about entities– Entity: movies, books, animals, etc.
– Evaluative expression:
good, bad, interesting, terrible, cute, etc.
5Approach• Use collaborative filtering– A technique for using other users’ information
to model the behavior of a certain user(Breese et al., 1998)– Used in many recommendation systems– Has not been used to predict users’ linguistic
choices• We predict a user’s evaluative expressions
about entities from other users’ data
6

Approach (cont’d)Current
Topic
Entity Ej

SystemHow Ui
used expressions
for other entities

How other users
used expressions
for entities

Expression candidate
Expr1
Expr2
ExprN

Score

User Ui

The score means how likely each expression can be used by Ui.
7

Approach (cont’d)Current
Topic
Entity Ej

SystemHow Ui
used expressions
for other entities

How other users
used expressions
for entities

Expression candidate
Expr1
Expr2ExprNScore
1030
20User Ui

The score means how likely each expression can be used by Ui.
8Approach (cont’d)• Two ways to use other users’ data
– Use similar users’ expressions• When Ui is similar to Uj, assign large
scores to the expressions used by Uj– Use similar entities’ expressions• When Ej is similar to El, assign large
scores to the expressions used for El byother users
9Using similar users’ expressions• Assumption: similar users are likely to usesimilar expressions for the same entity• Score of each expression:
Number of times Uhused ek

Similarity between Ui and Uh

sim returns a variant of cosine similarity (Amatriain et al., 2009)

A vector indicating how Ui uses evaluative expressions

10

Example
User1

User2
good

bad

cute

cat

122

dog

2

07

sim(User1,User3)=cos([3,2,9],[1,5,1])= 0.44sim(User2,User3)=cos([2,9,3],[1,5,1])= 0.99

User3
good

bad

cute

cat

2

8

1

cat

dog

012

dog

good

bad

cute

User1329

User2

293

User3

151dogbadcute151

Suppose we want toassign scoresfor these
0*0.44+1*0.99 = 0.99

User3
2*0.44+0*0.99= 0.88

goodgood

badcute

0.88

0.99

5.06

7*0.44+2*0.99= 5.06

System’s predictions: cute>bad>good11

Using similar entities’ expressions• Assumption: similar entities are likely to be
expressed by similar expressions• Score of each expression:
Similarity between Ej and El

Number of times users used ek for El
12

Example
User1

User2
good

bad

cute

cat

1

2

2

bear

01

dog

2

2

good

bad

cute

cat

2

3

1

7

bear

3

2

1

dog

3sim(cat, dog)=sim([4,10,4],[5,4,2])=0.88
sim(bear, dog)=sim([5,4,17],[5,4,2])=0.62
0.88*4+0.62*5+5=3.52+3.1+5
=11.6

User3
good

bad

cute

cat

1

5

1

8bear

2

12

2

1

dog

good

bad

cute

cat

4

104

bear

5

4

17dog

5

4

2

good

bad

cute

11.6

15.3

16.1

User3
dog

System’s predictions: cute>bad>good

Suppose we want toassign scoresfor these
0.88*10+0.62*4+4=8.8+2.48+4=15.3
0.88*4+0.62*17+2=3.52+10.54+2
=16.1

13

Using both similar users’ andsimilar entities’ expressions• Assumption:– similar users use similar expressions– similar entities are likely to be expressed bysimilar expressions• Score of each expression:

Number of times similarusers used ek for El

Similarity between entities Ej and El

14

Prediction Experiment• Compare the prediction accuracy of four
variations of our approach– (1) UserSim: use similar users’ expressions– (2) AnimalSim: use similar entities’ expressions– (3) UserSim+AnimalSim: use similar users’ andentities’ expressions– (4) Baseline: simple voting of other users’
expressions (UseSim without the user similarityweighting)• Predict expressions of Ui for Ej by masking thisinformation from data
15

Data
• Dialogue data
– 1,000 human-computer dialogues (in text)– 50 users (25 males, 25 females)– Domain: Animal discussion• Participants talk about likes and dislikes aboutanimals– Manually annotated with dialogue acts

• Extracted data for experiment– Sets of <Animal, Expressions> for 50 users• 47 evaluative expressions (mainly, adjectives)for 90 animals
16

Example Dialogue
UtteranceDialogue Act

System Hello

Greeting

User

Greeting

Hello

System Let’s discuss likes and dislikes
about animals.

Open-dialogue

User

Do you like insects?

Question

System Do you like insects?

Question

User

Self-disclosure

I like fireflies.

System You like fireflies.

Agreement

User

Self-disclosure

I like fireflies because they are
beautiful.

System I also like them very much.

Agreement

User

Question
Self-disclosure

You too?
They are evanescent, aren’t
they?

Entity:firefly
Expressions:beautifulevanescent17

Evaluation Criterion• Top-3 accuracy– the ratio of animals for which the top-3
predicted expressions contained those actuallyuttered by the user

• Limit the animals to make prediction– Some animals are expressed by many
expressions → too difficult to predict– We set a skewness threshold to remove certain
animals from evaluation
18Skewness• Capture the distortion of a distribution• Calculate the skewness for the distributionof frequencies of evaluative expressions
Number of expressions
Easy to predict
There are only a few
dominating
expressions

Difficult topredict
There are many
dominating
expressions

Frequency
Negative Skewness

Positive Skewness(© Wikimedia)

19

Example• Frequencies of expressions for Panda– cute(32), big(5), round(4), dangerous(2),white(2), good(2), eyes are cute(2), warm(1),sweet(1), black(1), small(1), strong(1), soft(1)6

Numberofexpressions

Skewness = 3.47
Panda’s expressions can beeasily predicted.

412

1

1

1

4

5

32

Frequency

20

Results

The number of animals
over the threshold t

Top-3 accuracies depending on the skewness threshold tNone(90) t=1.0(74) t=1.5(59) t=2.0(35) t=2.5(17)Baseline

0.753

0.760

0.756

0.771

0.776

UserSim

0.752

0.765

0.774

0.794

0.799

AnimalSim

0.733

0.741

0.759

0.773

0.802

UserSim+AnimalSim

0.740

0.740

0.755

0.760

0.778

•Accuracy is generally high with 75~80%•UserSim and AnimalSim significantly outperform
Baseline for easy-to-predict animals•AnimalSim performs poorly when no threshold is set⇒ Some animals have specific expressions for them21

Results (cont’d)

UserSim is performing better
than others in most cases

22Summary and Future Work• Proposed using collaborative filtering to predict auser’s evaluative expressions in order toincrease closeness in dialogue– First to apply CF to the prediction of users’ linguisticchoices• Similarity of users/entities is useful for improving
the prediction accuracy• Future work:– Verify our approach in an on-going dialogue– Expand to larger domains23