Using Collaborative Filtering to Predict User
Utterances in Dialogue
Ryuichiro Higashinaka, Noriaki Kawamae, Kohji Dohsaka, and Hideki Isozaki
NTT Communication Science Laboratories, NTT Corporation
2-4 Hikaridai, Seika-cho, Soraku-gun, 619-0237 Kyoto, Japan.
{rh,kawamae.noriaki,dohsaka,isozaki}@cslab.kecl.ntt.co.jp
Abstract. This paper proposes using collaborative filtering, a techniquefor using other users’ information to model the behavior of a certain user,
to predict users’ evaluative expressions for entities in dialogue. Previousstudies have found that inducing users’ empathic utterances towards
systems can improve user satisfaction. Predicting what users may utter
and communicating this information in advance would make it easy forusers to show empathy, leading to possible improvement in the qualityof dialogue. Experimental results show that our approach, which uses
the similarity users and entities, can significantly improve the prediction of evaluative expressions compared to a baseline that ignores such
similarity.

1Introduction

Although task-oriented dialogue systems have been actively studied over theyears [M. Walker et al., 2002], systems that aim to affect the minds of users arebeginning to be actively investigated [Bickmore and Picard, 2005,Dohsaka et al.,2009]. In our previous work, which investigated the effects of self-disclosure andempathy on closeness and user satisfaction, we found that inducing emphatic
utterances of users is most important for improving closeness and user satisfaction [Higashinaka et al., 2008].
This paper examines how such empathic utterances can be induced using
collaborative filtering, a technique for using other users’ information to model
the behavior of a certain user [Breese et al., 1998]. We adopt this technique topredict user utterances (in particular, evaluative expressions) in dialogue. For
example, for users who think cats are capricious, if the system could predict thisand utter, “Cats are capricious, aren’t they?” in advance, users would likely toagree and may feel close to the system.
Collaborative filtering has already been used to predict the ratings of user
reviews [Amatriain et al., 2009,Titov and McDonald, 2008]. However, it has neverbeen used for predicting expressions of users in dialogue. Recently, automaticallymining emphatic utterances from the web has also been proposed [Shimizu et al.,2009]. However, this does not take into account the information of users.

2ApproachFor a user Ui (1 ≤ i ≤ n) and an entity Ej (1 ≤ j ≤ m), we want to predict theexpressions {e1 . . . ek } for that entity from other users’ information. Since thework is still preliminary, we focus on predicting a user’s evaluative expressions(mainly adjectives) in this paper, although we plan to extend our approach todealing with more complex expressions.
First, we make a frequency table where rows represent users and columns
represent evaluative expressions, showing the use of evaluative expressions byusers. Here, we weight the frequencies by Residual IDF (RIDF). From this table, using a variant of the cosine similarity metric [Amatriain et al., 2009], we
calculate the user similarity between Ui and Uj bysim(Ui , Uj ) =ui · uj
2Ni∪j·| ui || uj | Ni + Nj

(1)

where ui and uj mean the weighted frequency vectors for Ui and Uj , Ni thenumber of entities mentioned by Ui , and Ni∪j the number of entities mentioned
by both Ui and Uj .
Then, we make another frequency table where rows represent entities andcolumns represent evaluative expressions, showing how entities are described byusers using the evaluative expressions. Here, each cell represents the number oftimes an evaluative expression ek was used for an entity by all users except for
Ui . We calculate this count entity(Ui , El , ek ) byentity(Ui , El, ek ) =nsim(Ui , Uh ) · freq(Uh , El , ek )

(2)

h=1

where freq is a function that counts how many times a user Uh used an evaluative expression ek for an entity El . The frequency is weighted by the similarity
between Ui and Uj so that the counts of users who are not similar to Ui can betreated lightly. This way, each row can represent a frequency vector of evaluative
expressions adapted to Ui . In addition, since similar entities may share similarevaluative expressions, we update the counts byentityupdate (Ui , Ej , ek ) =msim(Ej , El ) · entity(Ui , El , ek )

(3)

l=1

Finally, when predicting the evaluative expressions of Ui for Ej , we rank theexpressions {e1 . . . ek } in descending order of entityupdate (Ui , Ej , ek ).

3

Experiment

We prepared sets of evaluative expressions for 90 animals (i.e., entities) for 50
users. We created this data set from our text-chat dialogue data in the animal
discussion domain, in which a user and a system discuss their favorite animals(see details in [Higashinaka et al., 2008]).
We extracted the users’ evaluative expressions for the animals from the dialogue act annotation we performed on user utterances. Here, the evaluative
expressions are adjectives, adjective verbs, and phrases that match the pattern

Table 1. Top-3 accuracies for evaluative expressions averaged over all users dependingon the skewness threshold t. Asterisks indicate statistical significance (p<0.05) overBaseline. The numbers in parentheses denote the number of animals over t.
Baseline
UserSim
AnimalSim
UserSim+AnimalSim

none (90) t=1.0 (74) t=1.5 (59) t=2.0 (35) t=2.5 (17)
0.753
0.760
0.756
0.771
0.776
0.752
0.765
0.774*
0.794*
0.799
0.733
0.741
0.759
0.773
0.802*
0.740
0.740
0.755
0.760
0.778

[NN is ADJ] where NN and ADJ stand for a general noun and an adjective, respectively. For example, we have “clever” and “eyes are cute” for dolphins. Note
that, in extracting the expressions, we did not select expressions that occurred
less than ten times in the data because such expressions may be too specific tocertain users. We extracted 48 evaluative expressions in all.
For the prediction experiment, we excluded one user’s evaluative expressions
for an animal from the data set and predicted them using our approach. This
process was repeated for all animals for all users in a round robin fashion. For
evaluation, we calculated the accuracy of evaluative expressions by first predicting top-N evaluative expressions for the animals, and then calculating the ratioof animals for which the top-N expressions contained those actually uttered bythe user. We used 3 for N in this experiment. We prepared three configurations ofour proposed approach and compared them with a baseline. They are as follows.
UserSim The evaluative expressions are simply ranked by Eqn.2.
AnimalSim The evaluative expressions are ranked by Eqn.3 but the similarityof users is not used; namely, Eqn.1 returns 1.
UserSim+AnimalSim The evaluative expressions are ranked by Eqn.3.
Baseline The evaluative expressions are ranked by Eqn.2 and Eqn.1 returns 1.
Table 1 shows the top-3 accuracies for the evaluative expressions averaged
over all users. We selected the animals for evaluation on the basis of the skewnessof the distribution of evaluative expressions because we noticed that the ease ofprediction depends on whether an animal is expressed by only a few dominating evaluative expressions. The skewness is calculated by {N/(N − 1)/(N −N2)} i=1 (xi − µ)3 /σ 3 , where N , xi , µ, and σ denote the number of evaluative
expressions, the frequency of each evaluative expression, the mean, and the standard deviation of the frequencies of the evaluative expressions for a given animal,respectively. Since the skewness can capture such distortion in a distribution, weused the skewness threshold t to remove certain animals from evaluation. For thestatistical comparison of the accuracies, we performed a sign test that compares
the number of users whose accuracies were higher or lower than the baseline.
From the table, it can be seen that UserSim significantly outperformed thebaseline when t = 1.5 (p=0.019) and t = 2.0 (p=0.013). AnimalSim also outperformed the baseline when t = 2.5 (p=0.035). Figure 1 shows how the accuracies
change depending on t. Although our current approach does not work sufficiently
for animals with low skewness (i.e., animals that are expressed by many lowfrequency evaluative expressions), the results demonstrate the effectiveness ofusing other users and entities for the prediction of users’ evaluative expressions.

0.9

Baseline
UserSim
AnimalSim
UserSim+AnimalSim

Top-3 Accuracy

0.85

0.8

0.75

0.7
-1

-0.5

00.5

1
1.5
22.5
Skewness Threshold

3

3.5

4Fig. 1. Plot of top-3 accuracies for evaluative expressions averaged over all users depending on the skewness threshold t.

4

Summary and Future Work

This paper proposed using collaborative filtering to predict users’ evaluative
expressions for entities in dialogue. The experimental results show that our approach is promising. As future work, we plan to improve the prediction accuracy
and coverage of entities. We also plan to use larger and more realistic data toverify our approach. We also need to show that the effectiveness of our approachin an ongoing dialogue. Finally, we also plan to apply our approach to spoken
dialogue data.

References[Amatriain et al., 2009] Amatriain, X., Lathia, N., Pujol, J., Kwak, H., and Oliver,N. (2009). The Wisdom of the Few: A Collaborative Filtering Approach Based onExpert Opinions from the Web. In Proc. SIGIR, pages 532–539.
[Bickmore and Picard, 2005] Bickmore, T. W. and Picard, R. W. (2005). Establishingand maintaining long-term human-computer relationships. ACM Transactions on
Computer-Human Interaction (TOCHI), 12(2):293–327.
[Breese et al., 1998] Breese, J. S., Heckerman, D., and Kadie, C. M. (1998). Empiricalanalysis of predictive algorithms for collaborative filtering. In Proc. the 14th Annual
Conference on Uncertainty in Artificial Intelligence, pages 43–52.
[Dohsaka et al., 2009] Dohsaka, K., Asai, R., Higashinaka, R., Minami, Y., and Maeda,
E. (2009). Effects of conversational agents on human communication in thoughtevoking multi-party dialogues. In Proc. SIGDIAL, pages 217–224.
[Higashinaka et al., 2008] Higashinaka, R., Dohsaka, K., and Isozaki, H. (2008). Effectsof self-disclosure and empathy in human-computer dialogue. In Proc. SLT, pages
109–112.
[M. Walker et al., 2002] M. Walker et al. (2002). DARPA Communicator evaluation:
Progress from 2000 to 2001. In Proc. ICSLP, pages 273–276.
[Shimizu et al., 2009] Shimizu, T., Inui, K., and Matsumoto, Y. (2009). Back-channel
feedback using evaluation expression for chat. SIG-SLUD-A803-02, Japanese Societyof AI, pages 7–12. (in Japanese).
[Titov and McDonald, 2008] Titov, I. and McDonald, R. (2008). Modeling online reviews with multi-grain topic models. In Proc. WWW, pages 111–120.