Higher-Order DeepTrails: Unified Approach to *Trails Tobias Koopmann1 , Jan Pfister1 , André Markus2 , Astrid Carolus3 , Carolin Wienrich2 and Andreas Hotho1 1 University of Würzburg, Department of Computer Science, CAIDAS, Chair for Data Science, Germany 2 University of Würzburg, Institute Human-Computer-Media, Psychology of Intelligent Interactive Systems, Germany 3 University of Würzburg, Institute Human-Computer-Media, Media Psychology, Germany Abstract Analyzing, understanding, and describing human behavior is advantageous in different settings, such as web browsing or traffic navigation. Understanding human behavior naturally helps to improve and optimize the underlying infrastructure or user interfaces. Typically, human navigation is represented by sequences of transitions between states. Previous work suggests to use hypotheses, representing different intuitions about the navigation to analyze these transitions. To mathematically grasp this setting, first-order Markov chains are used to capture the behavior, consequently allowing to apply different kinds of graph comparisons, but comes with the inherent drawback of losing information about higher-order dependencies within the sequences. To this end, we propose to analyze entire sequences using autoregressive language models, as they are traditionally used to model higher-order dependencies in sequences. We show that our approach can be easily adapted to model different settings introduced in previous work, namely HypTrails, MixedTrails and even SubTrails, while at the same time bringing unique advantages: 1. Modeling higher-order dependencies between state transitions, while 2. being able to identify short comings in proposed hypotheses, and 3. naturally introducing a unified approach to model all settings. To show the expressiveness of our approach, we evaluate our approach on different synthetic datasets and conclude with an exemplary analysis of a real-world dataset, examining the behavior of users who interact with voice assistants. Keywords Behavior Analysis, Sequential Data Analysis, Autoregressive Language Models 1. Introduction Understanding and describing human behavior by analysing transitions between different actions or states has been an established field of research for several years now. It aims to study the dynamics of human behavior by analyzing sequences of user transitions over different states and applying sequential analysis techniques. Understanding human behavior and identifying the most common patterns of interaction can lead to improvements in many aspects, for example, web site design, traffic routing, or usability of different devices. As an exemplary use case, we will dive into the analysis of interactions with digital voice assistants like Alexa or Google Home. These smart devices have become increasingly popular in households over the last few years, capturing and responding to voice commands, aiming to help users with their daily tasks. LWDA’23: Lernen, Wissen, Daten, Analysen. October 09–11, 2023, Marburg, Germany � koopmann@informatik.uni-wuerzburg.de (T. Koopmann); pfister@informatik.uni-wuerzburg.de (J. Pfister); andre.markus@uni-wuerzburg.de (A. Markus); astrid.carolus@uni-wuerzburg.de (A. Carolus); carolin.wienrich@uni-wuerzburg.de (C. Wienrich); hotho@informatik.uni-wuerzburg.de (A. Hotho) © 2023 by the paper’s authors. Copying permitted only for private and academic purposes. CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings Sequences of usage behavior, if systematically analyzed, can offer valuable insight into the behavioral patterns, and therefore help improve the usability of the device. To mathematically represent these sequences, one approach is to aggregate the sequences into graph-like structures with respective transitions between states. Based on this, approaches have been proposed which rely on first-order Markov chain models, such as HypTrails [1], MixedTrails [2] and SubTrails [3]). Hypotheses represent intuitions about human behavior and are constructed and ranked according to how well they fit the observed data. We argue that this aggregation does not come without limitations: mainly the usage of first-order Markov chains is unable to capture vital information about the sequence, like higher-order dependencies. Real-life user behavior is seldom first order; consequently, we propose to model behavior explicitly as sequences and show that allowing for higher-order dependencies by default is a natural fit for this setting [4]. We propose to leverage recent advances in machine learning approaches to address this setting while being able to naturally capture higher-order dependencies in human behavior. For this, the natural choice are autoregressive language models, commonly used in Natural Language Processing. After fitting a model to sequences of user behavior, we propose to test the “validity” of a hypothesis for the training data by evaluating the model’s loss. This effectively determines whether the hypotheses exhibit expected behavior with respect to the observed user actions. Thereby we introduce an explicitly sequence-aware variation to HypTrails, MixedTrails, and SubTrails. The latter is a setting without available hypotheses, where we show how to incorporate transition features to analyze the sequences in a self-supervised manner. Being able to model higher-order dependencies within user interactions provides valuable insights into user behavior patterns and decision-making processes, consequently surpassing the expressiveness of previous approaches. The insights derived from this research have implications for improving user experience, personalizing recommendations, and designing more intuitive and adaptive systems.1 2. Related Work Our work is located in the intersection of two research areas: firstly user behavior analysis from sequences or graph-structured data and secondly sequential machine learning architectures. User Behavior Analysis describes the research domain of analyzing human behavior in any kind of sequences or graphs. The most closely related work uses hypotheses about human behavior to evaluate to which degree a certain hypothesis fits the observed transitions. Namely HypTrails [1] uses Bayesian inferences and sets a prior according to the believed transition probabilities from the hypothesis. The marginal likelihood for each hypothesis with respect to the observed data is calculated, and thus, the hypotheses can be ranked according to how well they fit the observed user behavior. MixedTrails [2] analyzed heterogeneous data, allowing researchers to study sequential data with varying behaviors. Here, each transition is manually assigned to a group, and each group can be explained with its own hypothesis. Furthermore, Subtrails [3] proposes a method to detect interpretable subgroups with exceptional transition 1 Our source code is available at https://github.com/LSX-UniWue/DeepTrails. behavior from sequential data. These hypothesis-driven approaches were also adapted on multigraphs [5] by creating a first-order Markov chain from the multigraph instead of aggregated sequences. Finally, behavioral networks can be compared using commonly used graph metrics such as centrality, graph distance, and number of triangles [6]. All of these approaches aggregate the sequences to first-order Markov chains, and hence loose information about higher-order dependencies. Machine Learning for Sequential Data has been a challenging setting, primarily due to the temporal dependencies present in the data. In comparison, traditional machine learning models, such as Random Forest [7] or Support Vector Machines [8], are powerful but also limited to handling data with fixed-length feature vectors. Nowadays, sequential data is usually processed using the transformer architecture [9]. Based on this architecture, different forms of autoregressive language models were developed [10, 11, 12], which are commonly used in Natural Language Processing, where the long-range and higher-order dependencies of words and tokens are a relevant topic. Due to their effectiveness, sequential language models have also been adapted in other areas of research, where it might not seem intuitive at first: e.g. in the research domain of recommendation [13, 14], but also graph-based machine learning approaches started by embedding nodes using sequential random walks and a form of Word2Vec [15, 16, 17]. 3. Methodology This work introduces a novel methodology to analyze and describe sequential user behavior. For this, we follow established settings as introduced in HypTrails and its follow-up extensions. Given a set of user observations modeled as sequences, the goal is to either find the best matching hypothesis that explains the observed user behavior (HypTrails [1] & MixedTrails [2]) or to find “interesting” subgroups of users that behave differently from other groups (SubTrails [3]). These existing approaches address this topic by limiting themselves to analyzing single-step transition behavior, hence breaking the observed sequences into first-order Markov chains and analyzing these using Bayesian inference. We argue that this inherently fails to take into account the sequential nature of the data and therefore propose using sequential machine learning models to address this problem. Specifically, we use autoregressive language models, traditionally applied to Natural Language Modeling and sequential data, based on the intuition that the models will discover and utilize higher-order dependencies. The following sections explain how we model user behavior represented as sequences with autoregressive language models, as well as measure how well a (higher-order) hypothesis matches these user sequences. In addition to these HypTrails [1] and MixedTrails [2] settings, we also explore a setting without available hypotheses to show how to take advantage of transition features to analyze the sequences in a self-supervised manner (cf. SubTrails [3]). We can address all these settings using our language model-based approach with only minor modifications needed between the settings, as depicted in Figure 1 and described in the following. We begin by introducing our common underlying methodology in Sections 3.1 and 3.2. DeepHypTrails Optional User Hypothesis Calculating Features defined by User Behavior Transition Trained Language Loss to Probabilities Model Estimate Fit Sampled biased Random Walks User Sequences DeepMixedTrails User Behavior Trained Language Multiple User Behavior Calculating (Higher-Order) Loss to Model Hypotheses Trained Language Model Estimate Fit Sampled biased Random Walks Permutating DeepSubTrails Observed User Sequences Training Model all possible Calculating Loss to Feature and User Behavior Estimate Fit between all Trained Language Sequence possible Feature/Sequence Model Combinations Combinations Training Hypothesis Testing & Evaluation Figure 1: DeepTrails: Schematic overview of our approach. We train a small language model on observed user sequences, optionally with user features. Then we freeze the trained model and plug it into the respective setting: 1. DeepHypTrails: evaluating the model on sequences generated from first-order hypothesis, or 2. DeepMixedTrails: using sequences that contain mixed transition behavior, or 3. DeepSubTrails: identifying interesting subgroups of features. 3.1. Representation of User Behavior Using Autoregressive Language Models Traditionally autoregressive language models are trained to predict the next token given the sequence of previous observations. Mathematically, a language model can be described by the probability assigned to a sentence x, defined asQ the conditional probability over all next words st given all previous words s