Regroupement non-supervisé d'utilisateurs par leur comportement pour les systèmes de dialogue parlé

Senthilkumar Chandramohan, Matthieu Geist, Fabrice Lefèvre, Olivier PietquinHAL 2012

TL;DR

This paper introduces a novel unsupervised clustering method to group users based on their dialogue behavior, addressing the challenge of diverse user interaction patterns in spoken dialogue systems. By representing user dialogues as feature vectors derived from Markov Decision Processes, the authors demonstrate the ability to automatically identify distinct user groups, paving the way for more personalized and adaptive dialogue strategies.

What Problem Does This Paper Address?

Spoken Dialogue Systems (SDS) aim to provide natural human-computer interaction. To make these systems truly effective, their interaction strategies need to adapt to individual users. While machine learning, particularly reinforcement learning, has shown promise for optimizing these strategies, it often requires vast amounts of data. To overcome this data scarcity and to evaluate system performance, user simulators are frequently employed. However, existing user simulators are often trained on limited, generic data, failing to capture the diverse ways users interact with a system. This can lead to dialogue managers that are optimized for an "average" user, which may not represent any real user effectively. The core problem this paper tackles is the lack of a robust method to automatically identify and group different user behaviors from dialogue data, which is crucial for developing adaptive and personalized SDS.

Methods

The paper proposes an unsupervised clustering approach to group users based on their dialogue behavior. The core idea is to model user interactions as Markov Decision Processes (MDPs). Each user's dialogue is transformed into a compact feature vector representing their "behavior." This is achieved by:

  1. Modeling User Behavior as an MDP: Users are conceptualized as decision-making agents optimizing an unknown reward function. Their actions within a dialogue (e.g., providing information, confirming, negating) are mapped to states and actions within an MDP framework.
  2. Feature Expectation Vector: Instead of directly learning the user's reward function (which is complex), the authors focus on the feature expectation of the user's policy. This quantity, denoted as $\mu_{\pi_k}$, represents the expected sum of discounted feature values over a dialogue trajectory, given a user's policy $\pi_k$. This vector captures the user's behavioral patterns.
  3. Dialogue Trajectory Vector: For practical computation, dialogue trajectories are represented by a vector $\delta_n$, which is an empirical estimate of the feature expectation. This vector is derived from the sequence of states visited during a dialogue, weighted by a discount factor.
  4. Unsupervised Clustering: Once dialogues are represented as these feature vectors, standard unsupervised clustering algorithms can be applied. The paper specifically uses the K-means algorithm with cosine similarity as the distance metric (due to the symbolic nature of the state space).

Datasets

The paper describes experiments using two types of datasets:

  1. Simulated User Data: For a 3-criteria restaurant information dialogue task, the authors generated 3000 dialogue trajectories by simulating two distinct user behaviors: an "expert" user and a "novice" user. This dataset was used to validate the clustering method's ability to separate known user types.
  2. Real User Data: For a more complex 12-criteria restaurant information dialogue task, the authors utilized a dataset of 480 dialogues collected from real human users interacting with a system. This dataset had limited annotations, making it a more realistic scenario for unsupervised learning.

Key Insights and Ideas

  • User Behavior as MDP Feature Expectations: The key insight is that user behavior can be effectively summarized by the feature expectations of their underlying MDP policies. This provides a principled way to quantify complex, sequential interactions.
  • Bridging Dialogue Representation and Clustering: By transforming dialogue trajectories into fixed-size feature vectors, the paper enables the application of standard vector-based clustering techniques, overcoming the challenge of variable dialogue lengths.
  • Unsupervised Discovery of User Groups: The method allows for the automatic discovery of user groups without prior knowledge of their types or behaviors, making it applicable to real-world scenarios where user diversity is unknown.
  • Validation on Simulated and Real Data: The successful application of the method on both simulated (where ground truth is known) and real user data demonstrates its robustness and practical applicability.

Key Results

  • 3-Criteria Dialogue Task: The K-means algorithm successfully clustered the simulated dialogues into two groups that strongly correlated with the predefined "expert" and "novice" user behaviors, as visualized in Figure 1.
  • 12-Criteria Dialogue Task:
    • The clustering method was applied to real user data, and the authors determined an optimal number of clusters (K=4) by analyzing the evolution of average distortion and cosine similarity (Figure 2).
  • The resulting 4 clusters showed distinct user behaviors, evidenced by low inter-cluster Kullback-Leibler (KL) divergence values (Table 2), indicating significant differences in their action distributions.
  • High intra-cluster cosine similarity values (Table 3) demonstrated strong cohesion within each identified user group, meaning users within a cluster exhibited similar interaction patterns.

Limitations and Future Work

  • Limitations:
    • The K-means algorithm is sensitive to the initial choice of centroids and can struggle with non-uniformly distributed data.
  • While the method groups users, the qualitative interpretation of these groups (i.e., precisely what makes them distinct) requires further analysis.
  • Future Work:
    • Explore other clustering algorithms, such as Gaussian Mixture Models, that are less sensitive to data distribution.
  • Develop methods to automatically qualify the discovered user behaviors, providing finer-grained insights into their distinct characteristics.
  • Leverage the identified user groups to build more accurate and diverse user simulators for adaptive dialogue strategy optimization and evaluation.
  • Investigate methods for generating missing data in corpora based on the identified user behavior clusters.

Summary updated

Abstract

National audience
BibTeX
@inproceedings{chandramohan2012regroupement,
  author = {Senthilkumar Chandramohan and Matthieu Geist and Fabrice Lefèvre and Olivier Pietquin},
  title = {{Regroupement non-supervisé d'utilisateurs par leur comportement pour les systèmes de dialogue parlé}},
  booktitle = {HAL},
  year = {2012},
}
Figure