User Memory Reasoning for Conversational Recommendation (2020)

Abstract: We study an end-to-end approach for conversational recommendation that dynamically manages and reasons over users’ past (offline) preferences and current (online) requests through a structured and cumulative user memory knowledge graph. This formulation extends existing state tracking beyond the boundary of a single dialog to user state tracking (UST). For this study, we create a new Memory Graph (MG) <-> Conversational Recommendation parallel corpus called MGConvRex with 7K+ human-to-human role-playing dialogs, grounded on a large-scale user memory bootstrapped from real-world user scenarios. MGConvRex captures human-level reasoning over user memory and has disjoint training/testing sets of users for zero-shot (cold-start) reasoning for recommendation. We propose a simple yet expandable formulation for constructing and updating the MG, and an end-to-end graph-based reasoning model that updates MG from unstructured utterances and predicts optimal dialog policies (eg recommendation) based on updated MG. The prediction of our proposed model inherits the graph structure, providing a natural way to explain policies. Experiments are conducted for both offline metrics and online simulation, showing competitive results.

## introduction conversational recommendation system has recently gained traction in the dialog community, in which the model aims to learn up-to-date (online) user preferences, instead of using static (offline) preferences as in the traditional, e.g. collaborative filtering (cf). most existing works focus on combining a static recommender system with a dialog system, by updating user preferences via asking relevant questions (often referred to as "system ask user respond (saur)" @xcite . however, this "shortterm" update in the model unnaturally isolates users' history and their preference in the current dialog (often forgotten after the dialog is finished). an intelligent system should be able to dynamically maintain and reason over users' knowledge for current (and possibly future) recommendations. to this end, we introduce a novel concept called user memory graph to holistically represent the knowledge about users and associated items. this user memory graph extends the notion of dialog state tracking (dst) beyond the boundary of a single dialog to user state tracking (ust). as in figure 1 , such a graph contains static knowledge obtained offline (e.g. items, attributes, the history of users and past dialogs) and users' knowledge online (e.g. from the current and possibly future dialogs). user memory graph naturally has the following benefits. (1) holistic reasoning considers available knowledge about users and items all together (not just dialog states) to generate policies. we focus on two types of reasoning policies: graph update policy and dialog policy, where the former updates users' online knowledge and serves as the basis for the later to generate outputs of the agent's current turn. we believe reasoning is the core problem in conversational recommendation because asking a good question or finding a good candidate item needs to explore the "soft match" of the knowledge between users and items foot_0 @xcite . (2) zero-shot (cold-start) reasoning for users/items unseen during training: user memory graph naturally separates user/item knowledge from the reasoning process of policy. as such, one can train a user/item agnostic model that can be later applied to another user memory graph (after the model is deployed). in contrast, most cf-based system "overfits" to existing users / items (in their embeddings). (3) open space policy is a key challenge in conversational recommendation because of the innumerable items involved in dialog policy. this requires a flexible space of policy to cover all items (and possibly all valid values and slots foot_1 ) instead of a pre-defined space and user memory graph can serve for that purpose. user memory reasoning for recommendation: assuming an agent involves in a conversation with a user e u . the agent (1) constructs foot_2 a user memory graph g 0 = {(e, r, e )|e, @xmath0, @xmath1, candidate items c, and their associated slots and values; (2) without loss of generality, updates g x-1 with new knowledge from the x-th turn d x , in the form of tuples g x ← g x-1 ∪ {(e, r, e ), . . . } ; (3) performs reasoning over g x to yield a dialog policy π x that either (i) performs more rounds of interaction to collect users' knowledge, or (ii) recommends items t ⊂ c to the user. in this paper, we first collect a dataset as existing public datasets hardly meet the needs for the following reasons. (1) lacking users' history and thus dialogs referring to history (e.g. the 2nd and 4th turn in figure 1 ): one reason is that most datasets aim for task-oriented systems, where users' history and reasoning are not core issues to solve. (2) lacking fine-grained annotation (for updating the user memory graph): most public datasets for conversational recommendation are combinations of the datasets for recommender systems and dialogs transcribed separately @xcite . the process is not designed for knowledge-grounded dialogs and leads to the hardness of annotating entity-level knowledge. (3) lacking human-level reasoning: the transcribed policies in existing datasets do not reflect deep reasoning over knowledge (e.g. asking a good question). some actions are taken at the transcribers' will @xcite . our collected dataset is called memory graph ↔ conversational recommendation (mgconvrex), which contains 7.6k+ dialogs with 73k turns with fine-grained annotation to meet the above needs. we first define a simple yet flexible ontology for user memory graph, as detailed in section 4. based on that, we propose a model called end-to-end user memory graph reasoner (e2e-umgr) that performs two types of reasoning: updating graph and generating dialog policies. we cast the former reasoning as a graph generation problem @xcite , which infers new knowledge from unstructured utterances into user memory graph. the later reasoning deals with the challenge of open space policy by preserving the structure of the graph and generating policy. in summary, the contributions of this paper are as following: (1) we propose a novel task of user memory reasoning for conversational recommendation; (2) we collect a dataset and propose an ontology to construct user memory graph; (3) we propose an end-to-end baseline for reasoning updates and dialog policy over the user memory graph. experimental results show that such a reasoning model is promising. datasets for task-oriented systems typically lack users' history, probably because users' history is not very important to correctly locate a record for the current dialog. although certain types of dialog act, slots, and values are shareable for both task-oriented system and conversational recommendation, the core problem of conversational recommendation is to reason and to rank items or questions to ask. graph reasoning is essential for updating graphs and generating dialog policy from the proposed user memory graph. this paper casts the graph updates as a graph generation problem @xcite ) from both structured graph and unstructured utterances. although our graph generation problem is closer to the link prediction problem @xcite in a social network, the key difference is that our problem focuses on progressively incorporating unstructured utterances into graph instead of inferring missing relations. there are many studies on leveraging knowledge graphs for recommender systems. for example, @xcite introduced a graph-based recommender (not dialog) system that is trained via reinforcement learning. graph neural networks are popular in recent years, which aim to learn hidden representations over discrete graph structures @xcite @xcite . several extensions to the original graph neural network have been proposed @xcite , most notably r-gcns @xcite , which can be applied to large-scale and multi-relational graphs. a few works have recently been proposed to allow knowledge graph reasoning in dialog systems. @xcite propose a new corpus to learn knowledge graph paths that connect dialog turns. @xcite introduce a knowledge-grounded dialog generation task given a knowledge graph that is dynamically updated. however, these works often focus on response generation and do not address the reasoning of user knowledge in conversational recommendations. ## mgconvrex mgconvrex aims to contain dialogs that draw the relevance of the user's history and fine-grained user preferences to update the user memory graph. as such, we propose to leverage existing data from ## user memory graph we describe the formulation of a user memory graph. there are many design choices for constructing a user memory graph. our goal is to model user/item knowledge with extensibility and maintenance. ## user memory graph reasoner we propose a baseline model called end-to-end user memory graph reasoner (e2e-umgr), which uses previous user memory graph to reason both graph updates (sentiment relations) and dialog policy (see figure 3 ). e2e-umgr simplifies the process of turning unstructured data into structured form and reasons dialog policy directly over graph to resolve the issue of open space policy. input: (1) past utterances up to the current turn d 1:x ; output: dialog policy π = (ŷ a , ŷc , ŷs , ŷv ) for the current turn, where a, c, s, v indicate the space of dialog acts, candidate items, slots and values, respectively. note that ŷc , ŷs , and ŷv can be interpreted as the arguments of dialog acts and are essentially rankings over their corresponding entity sets. for example, when ŷa = recommendation, the top-1 entity arg max e @xmath2. similarly, ŷa = open question is related to the top-1 slot arg max @xmath3. as such, the policy space of e2e-umgr can be determined by the user memory graph where only valid entities can be generated. a structure-preserving model is preferred for reasoning where all entities in policy are generated as a holistic reasoning process. we first encode all entities e @xmath4: to reason dialog policies, we first update g x-1 with sentiment relations as g x and use n r,gx j for the rest 5 layers. we compute dialog acts based on the hidden state of the overall user memory: the policy space is open-ended because entities in policy are determined by the rankings of entities in the user memory graph instead of a pre-defined set for the model. ## experiments 6.1 evaluation metrics we propose the following metrics to evaluate e2e-umgr both offline (against the collected testing dialogs) and online (against a user simulator) running on testing scenarios in mgconvrex. ## conclusion this paper proposes a problem of user memory graph reasoning for conversational recommendation. we expect to release a conversational recommendation dataset with a grounded user memory graph from the behaviors of real-world users. user memory graph has the benefits of accumulating knowledge for a user to reason dialog policy. we propose a baseline model called e2e-umgr that performs reasoning over such a user memory graph for graph updates and dialog policy in open space. experimental results demonstrate the effectiveness of e2e-umgr over a wide spectrum of metrics.