Introduction

Understanding and describing human behavior by analysing transitions between di erent actions or states has been an established eld of research for several years now. It aims to study the dynamics of human behavior by analyzing sequences of user transitions over di erent 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, tra c routing, or usability of di erent 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.

Sequences of usage behavior, if systematically analyzed, can o er 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 rst-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 t the observed data. We argue that this aggregation does not come without limitations: mainly the usage of rst-order Markov chains is unable to capture vital information about the sequence, like higher-order dependencies. Real-life user behavior is seldom rst order; consequently, we propose to model behavior explicitly as sequences and show that allowing for higher-order dependencies by default is a natural t 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 tting 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 e ectively 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

Related Work

Our work is located in the intersection of two research areas: rstly 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 ts 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 t 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 behavior from sequential data. These hypothesis-driven approaches were also adapted on multigraphs [5] by creating a rst-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 rst-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 xed-length feature vectors. Nowadays, sequential data is usually processed using the transformer architecture [9]. Based on this architecture, di erent 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 e ectiveness, sequential language models have also been adapted in other areas of research, where it might not seem intuitive at rst: 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].

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 nd the best matching hypothesis that explains the observed user behavior (HypTrails [1] & MixedTrails [2]) or to nd "interesting" subgroups of users that behave di erently 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 rst-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. Speci cally, 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 modi cations 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.

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, de ned as the conditional probability over all next words s t given all previous words s <t [18]:

P (x) = Q T t=1 P (s t | s <t )

, where s t is the input token at time step t. We aim to exploit the fact that this is closely related to modeling sequences of user behavior by training autoregressive language models on these sequences to describe and analyze user behavior. To this end, we model user states as input tokens by mapping every distinct state s of a user's behavior to its own token, thus generating our state-vocabulary S. Using teacher-forcing [9] and the cross-entropy loss, we train the model to predict the next state given the sequence of all previous states (Figure 1). The model thus learns the transition probabilities for the current state s t given the entire history of previously visited states s <t .

Estimating How Well Hypotheses Align with the Training Data

The core of our methodology is to measure how "suprised" the trained and frozen model is, when given a sequence of user behavior not seen during training. The intuition is that a model trained on sequences of speci c user behavior can adequately model sequences that were created by the same behavior, while unseen behavior is likely to be surprising to the model. Therefore, we can identify the types of behavior the model encountered during training and those it did not.

We measure how surprised the model is when presented with a new sequence using the loss function. For this, we freeze the model, and we calculate the positionwise cross-entropy loss of our model, between the sequence and the model's prediction, like during training, but we do not update the model. By calculating the mean loss over the entire sequence, we obtain a measure of the model's t for the currently evaluated sequence: a small loss indicates that the model "expected" this sequence, while a large loss shows that the model has not seen similar user behavior during training. Additionally, we are able to analyze the loss per position, allowing us to provide a more in-depth analysis of the sequences, which helps us to identify where a hypothesis might be lacking -something that is not possible using the traditional HypTrails methodology.

DeepHypTrails: Evaluating sequences on Homogeneous Observations

HypTrails [1] aims to analyze sequential user behavior using hypotheses. The setting is to identify the best matching hypothesis for the observed data, that is, the hypothesis that best describes the observed sequences. Since HypTrails only allows rst-order dependencies, hypotheses are represented as |S| ⇥ |S| transition probability matrices, which describe the transition probabilities from one state to any other given state.

In contrast, our approach uses entire sequences, which we can generate by sampling biased random walks on the transition probability matrices (Figure 1). We then evaluate our model on these randomly generated walks as described in Section 3.2. By averaging over all random walks -each following a speci c hypothesis -we identify the hypothesis resulting in the lowest loss.

DeepMixedTrails: Analyzing Hypotheses on Heterogeneous Observations

This extension of HypTrails allows the analysis of heterogeneous sequences. The underlying assumption is that the sequences are not generated by a single driving force but by multiple driving forces. Therefore, it is assumed that transition probabilities can change given the circumstances, e.g. after a certain amount of time, or they might even originate from entirely di erent groups of users. Since the method proposed in MixedTrails [2] is strictly transitionbased and relies on a rst-order Markov chain, it inherently cannot distinguish if sequences 1. change behavior after a certain amount of time, i.e. contain higher-order dependencies, or 2. originate from di erent groups, i.e. consist of di erent types of rst-order behavior. Each case can be exemplary illustrated as a soccer team that plays o ensive in the rst half and defensive in the second or tourists and locals that have a di erent movement behavior in a city [2].

Since our approach takes entire sequences into account, it is naturally able to distinguish between these two settings. The model has no access to information on which behavior a sequence is generated by. We rely entirely on the model to implicitly learn the di erent behaviors present on its own, such that the loss is low when testing hypotheses that match the training sequences, and high if the behavior was not present in training (section 3.2). Additionally, this even allows us to combine both scenarios of MixedTrails, by training the model on sequences from di erent groups, where each might contain higher-order dependencies.

DeepSubTrails: Identifying Subgroups with Interesting Behavior

Lastly, we use our approach in the SubTrails setting [3]. For this, instead of using prede ned hypotheses to describe human behavior, we analyze observed user behavior to nd unique subgroups that show "exceptional" transition behavior. These subgroups exhibiting interesting transition behaviors -when compared to all transitions -are identi ed by attributes or features assigned to each transition. We have to slightly adapt our approach to accommodate for this scenario, by conditioning our autoregressive model on the features that are associated with the sequence (details in Section 4.3). To this end, we feed all features to the model, and thus enable it to learn a di erent conditional behavior based on the given feature expressions. For evaluation, we assess the loss across all possible combinations between features and observed sequences, thereby identifying interesting user behavior through the corresponding loss values. A large loss indicates that the given combination of feature expression and sequence is unexpected to the model and, respectively, shows atypical sequential behavior for this feature expression. Furthermore, we introduce a similarity measure for features: features are similar if the model assigns a similar loss for the same sequences, when conditioned with the respective feature. This measure allows us to cluster similar feature expressions together, and thus identify similarly behaving users. As before, our approach has the advantage of naturally capturing higher-order dependencies.

Experimental Setup

We create several di erent arti cial datasets with known synthetic user behavior. Additionally, we demonstrate the expressiveness of our approach on a real-world dataset, in which we analyze the behavior of users interacting with voice assistants.

Generation of Synthetic Datasets

We generate several synthetic datasets containing di erent types of user behavior that can be described or uncovered using our methodology introduced in Section 3. To arti cially generate user transitions, we de ne user behavior over an underlying Barabasi-Albert graph [19]. This graph structure is scale-free, which means that the graph is densely connected in the "center" and less connected in the periphery. For all synthetic datasets, we generate a graph with n = 100 nodes and new nodes connected to m = 10 existing nodes using preferential attachment [19]. We divide the graph nodes equally into even and odd nodes, allowing us to de ne synthetic user behavior based on these classi cations. To model di erent types of behavior, we introduce di erently biased random walkers that follow a prede ned transition behavior based on the node categories. For each synthetic behavior, we start a new biased random walker from each node 1000 times and generate sequences of length 20. Notably, the model has no explicit information about the underlying graph structure or node categorization and only has access to the exhibited user observations. Synthetic Data for HypTrails To evaluate our approach, we de ne di erent synthetic behaviors as follows: (i) even: The walker only transitions towards even nodes (ii) odd: The walker only transitions towards odd nodes (iii) random: The walker randomly transitions towards any adjacent node (iv) teleport: In contrast the walker randomly teleports to any node on the graph. Additionally, to show the applicability of our model to noisy data, we create matching biased probabilistic walkers for each behavior, where the walker follows the hypothesis only 90% of the time, otherwise following the opposite behavior. Following each of the above behaviors, we generate separate sets of sequences for observed user behavior as well as for hypotheses, which will be used for evaluation.

Synthetic Data for MixedTrails

As explained in Section 3.4 we distinguish between two scenarios (i) The sequences are generated by di erent driving forces or (ii) transitions within a sequences are created by a changing behavior. The latter scenario can be modeled by using higher-order dependencies in the creation process. We create a single dataset containing both scenarios at the same time: a mixture of sequences originating from several di erently biased random walkers, and some of them even showing varying behavior over time. To this end, we add the following behaviors: (i) rst-even: The walker only transitions to even nodes for the rst half of the walk, and only odd nodes for the second half. (ii) rst-odd: The walker only transitions as above, but in reverse. (iii) two-odd-two-even: The walker transitions twice to odd nodes, then twice to even nodes, and so forth. The dataset consists of 330 walks per node for each of the following behaviors: even, odd and first even.

Synthetic Data for SubTrails Following the SubTrails approach, we only generate observed sequences and no hypotheses, but introduce additional matching feature vectors for each sequence. The model has access to this feature vector consisting of attributes that may in uence user behavior. Some features explicitly correlate with the observed behavior, while some do not.

Here, our dataset consists of 250 biased random walks per node each: even, odd, first even, and first odd bias. We add a feature vector with six binary features, where the rst feature activates only if the random walker follows the even bias, the second feature only activates if the random walker follows an odd bias, etc. The last two features are activated at random and serve as noise that the model has to learn to ignore. This results in a total of 16 possible feature combinations, where the last two features exhibit four potential permutations. The rst 4 features are one-hot encoded, thereby combining the 4 permutations to each one-hot encoding, we can create 16 possible feature combinations.

Case Study on Long-Term Study on Voice Assistant Usage

As a real-world case study of our methodology, we analyze a dataset containing various types of user behavior. It was created by a long-term study in which 39 students received an Amazon Alexa or Google Home device and their usage was tracked and analyzed. For our analysis, we represent user interactions with these devices as sequences. To this end, we introduce 33 distinct states that are shared between all sequences. Every state represents one type of command, e.g. "playing music" or "asking about the news". Sequences are constructed from consecutive voice commands: Every time a user interacts with the device twice within a 15-minute time window, a transition between the two types of voice commands is added for the current sequence. Thus, we construct 217 sequences with a length between 2 and 94 and an average of 6.43. Information about the users' perception of the voice assistants as well as other psychological features have been systematically collected using questionnaires. We use these features, e.g. how lonely a user is or to which extent the user describes the voice assistant as a friend as additional input for the model. We also use time of day and day of the week as additional metadata, leading to 150 distinct feature sets, each used by at least one user.

Autoregressive Language Models

Our methodology requires a model that can be used to autoregressively model sequences. Traditional language models are an obvious t, but we also explore a signi cantly smaller and deterministic language model based on a Random Forest.

Transformer Decoder

The rst model uses a transformer decoder following the GPT architecture. Every state in the sequence is modeled as a token. The model is trained to predict the next state given the history of current states autoregressively using teacher forcing [9]. We use the nanoGPT implementation2 with a vocabulary size of "number of states" plus 2 (e.g. 100 nodes + EOS and BOS tokens for the synthetic datasets), four layers with four heads, and an embedding dimension of 16. For our DeepSubTrails setting, we additionally adapt the model to encode a feature vector. Categorical features are encoded as a one-hot vector, whereas numerical features are kept as is. All features are concatenated into a vector and then consequently embedded to match the dimensionality of the token embedding. This new token embedding replaces the BOS token, thus conditioning the model to predict a sequence with respect to the given user features. This is comparable to user embeddings in sequential recommendation [20].

Random Forest-based Language Model

As a second model, we will use a language model based on a random forest classi er and train it on our sequences. For this, we encode each state as a one-hot vector and multiply it by an exponentially decaying weight, depending on the positional distance of the embedded token to the current token. This can be compared to a positional embedding. All these weighted one-hot encoded vectors are summed up into a single vector, and thus the shape becomes independent of the sequence length. The positional information for each state is encoded in the magnitude of this multi-hot vector. For modeling user features, we create a vector which contains an integer per categorical feature and a oat per numerical value, and concatenate it to the sequence information described above. Thus, the model has access to the sequence and user information at the same time.

Results

In the following section, we will show the di erent experiments conducted, interpret the results, and show further analysis with respect to the learned embeddings. We conduct experiments for all of the previously mentioned scenarios, namely DeepHypTrails, DeepMixedTrails, and DeepSubTrails, and additionally show the applicability of our approach in a real-world setting, where users interact with a voice assistant.

DeepHypTrails

In the following, we evaluate the GPT model in the DeepHypTrails setting on synthetic data as previously introduced. The Random Forest language model leads to similar results, but we limit our analysis here to GPT due to space constraints; additional plots for the random forest model Applying autoregressive language models, here GPT, to sequential behavior analysis. Figure 2a shows the results trained on sequences with only even behavior and evaluates it on di erent hypotheses. For each time step, we rank the predicted tokens by logits in descending order. We plot the average rank of the target token per decoding step for each hypothesis. A low rank indicates a high likelihood for the next transition according to the model. Figure 2b shows the result when training on sequences of heterogeneous behaviors, as introduced in Section 4.1. The number in the legend indicates the average loss over all sequences and positions for the given hypothesis. can be found in the appendix 3 . Figure 2a shows the rank-wise analysis for di erent hypotheses of the output of our model, when trained on even behavior. The x-axis shows the decoding time step, i.e. the position in the walk. At each time step, we rank the tokens according to their logits in descending order. The y-axis shows the average rank of the target token per position, where a low rank indicates a high likelihood for the next token according to the model. All hypotheses begin with an average rank of ~50, since we start from each of the 100 nodes in the graph equally often. As the model has to randomly guess the rst node from which the walk starts, the expected average rank for this step is 50. Furthermore, the last node at decoding step 20 has an average rank of 1, since all synthetic sequences have a length of 20 and the model is able to predict the position of the EOS token perfectly. Sequences created from hypotheses showing the same behavior as the observed sequences have the lowest average ranks, as expected and shown by the blue line (even). The opposing behavior (orange line, odd) leads to average ranks above 60, which shows that the model expects these nodes to be very unlikely. Using a random walker (green line, rand) as hypothesis leads to an average rank of ~30, which is higher than a hypothesis with even bias, but also lower than the odd walker. Naturally, transitioning at random is more similar to the observed user behavior than actively following an opposite behavior than during training. Furthermore, a teleporting walker (red line, tele) stays at an average rank of ~50 after the rst step, which is expected, since this again means that the model cannot predict the next transition. Furthermore, this shows the ability of the model to learn the graph structure, since the average rank of the rand hypothesis is lower, showing that the model is less surprised by a randomly sampled adjacent node than any randomly sampled node. Finally, using sequences with higher-order dependencies in Figure 2b, namely first even, we can observe a similar rank for the rst half of the sequences. Subsequently, the average rank increases to the same level as the odd hypothesis after the behavior changes. We nd that first even biased results in comparable ranks, but with a smaller amplitude, as it e ectively is a mixture of first even and rand. This shows that our approach is capable of ranking the sequences generated with the respective behavior accordingly and is even possible to analyze sequences by position, thus indicating at which transitions a hypothesis might not be adequately explaining the data. Furthermore, in Figure 3a, we analyze the extracted token embeddings for each state of a model trained on first even observations. The UMAP plot with annotated classes shows that the model is able to neatly separate both state types in the token embedding space, indicating that the model is able to understand the di erent types of nodes. The label "ST" denotes the embeddings of the special tokens.

Finally, we show an ablation study in the appendix, where we applied the original HypTrails approach on data created by higher-order sequences. Our results show that HypTrails, due to the use of a rst-order Markov chain, is not able to distinguish between the higher-order sequences and random navigation.

DeepMixedTrails

In the next experiment, we use our approach in both MixedTrails settings as introduced in Section 3.4. In Figure 2b, we show the results for a model trained on sequences from di erent groups of users who also show a change in behavior over time, as explained in Section 4.1. We expect hypotheses that exist in the training observations to have on average a lower rank than hypotheses not occurring in the data. Since the model is trained on equal amounts of even, odd and first even behavior, all of these hypotheses lead to similarly low ranks (see Figure 2b). Notice that the rank at step 1 is about 15, since the model does not know yet to which behavior the current sequence belongs to -either one of the even behaviors follows if it is an odd walk. After time step one this is unambiguous, thus the rank decreases further. At decoding step ten, we can observe a peak which is explainable by higher-order hypotheses first even. The model cannot know whether the current hypothesis follows even or first even, therefore this spike appears for both hypotheses. In particular, this spike is absent for the odd hypothesis as the model can be certain to follow this behavior known from the training data. The average rank for the rand hypothesis increases after the rst decoding step, since the model assumes that the subsequent steps follow the rst observed time step and not random nodes. As before, tele remains at a rank of ~50. We show additional experiments for DeepMixedTrails in the appendix.

DeepSubTrails

As nal synthetic experiment, we analyze transitions with respect to features, instead of using hypotheses. For this, we train our model on the synthetic dataset described in Section 4.1, which contains a feature vector with six categories for each walk. For evaluation, we use 10 exemplary walks per behavior (40 total). Walks 0 to 10 are walks containing even behavior, 11 to 20 contain odd behavior, 21 to 30 contain first even behavior and 31 to 40 contain first odd behavior. We sort the matching feature sets in the same ordering, where feature sets 0 to 4 have category 1 activated, all possible permutations for category 5 and 6 (which are walks 3a shows the ability of our model to learn the graph structure and the di erent node types. We use a UMAP visualization of node embeddings, which shows a separation between the di erent node types. Figure 3b shows a visualization of the DeepSubTrails loss scores in synthetic data. The model is trained on sequences prepended with features. For evaluation, we create di erent combinations of features and walk behavior and visualize the loss. Figure 3d shows the same visualization in our real-world dataset. Here the x-axis lists all command sequences and the y-axis all distinct feature combinations. Figure 3c clusters the possible feature sets with respect to the column-wise probability given by our model from Figure 3d.

containing even behavior), and so forth. We combine the 16 unique feature sets with each of the 40 walks and visualize the resulting loss as a heat map in Figure 3b. We observe the lowest loss across the diagonal, where the model correctly nds that the behavior in the walks matches the features. The highest loss can be found in the dark blue rectangles in the upper left corners, where the feature suggests even walks, but the walks contain only odd behavior and vice versa. Next, we can observe medium loss scores for the top right and bottom left corner, where the feature suggests changing behavior walks, but the walks match only partially by containing only odd or even behavior. Finally, we can observe that noise categories 5 and 6 do not have any impact: the loss is stable across all feature combinations where only these noncorrelating categories change (feature combination 0 to 3, 4 to 7, etc.). Feature combinations 0 through 3 iterate over all possible combinations only of categories 5 & 6, but the loss and the other categories remain stable. By recombining features and sequences, this allows us to estimate how well a feature set matches to each walk and therefore hypothesis and behavior. We add further analysis and visualizations by clustering the features and sequences in the appendix.

Case Study: DeepSubTrails on Voice Assistant Data

The last experiment uses the DeepSubTrails methodology on our voice assistant dataset, as previously introduced using the random-forest based language model. Figure 3d displays clear patterns by analyzing which feature set best matches which sequence. We nd that several rows possess the same probability distribution across all sequences (columns), showing that these feature sets indicate similar transition behavior. The same phenomenon can be observed when analyzing the heatmap column-wise, w.r.t. the sequences: several sequences are similar to each other based on which sets of feature expressions they match best. Consequently, in Figure 3c, we use UMAP and HDBSCAN to cluster similar feature sets by interpreting each row in the heatmap as its representation. Thus, we can identify 10 di erent clusters of features that behave similarly and, therefore, yield similar probabilities for the same sequences. When analyzing clustered feature sets, we nd that commonly di erent feature sets are clustered together, which di er only by the "day of the week" feature, indicating consistent behavior across di erent week days. Furthermore, we also nd that there are, in general, two types of clusters: mono-user clusters and multi-user clusters and follow up with a more detailed analysis of these clusters found in Section 7.4.

Conclusion

This work explores the use of autoregressive language models to analyze and describe sequential user behavior. We train a model on observed sequences, therefore, predict user behavior present in these sequences and test hypothesis on user behavior. We evaluate our approach in three di erent settings, which are adopted from previous work. For the rst two settings, we construct (higher-order) sequences, sourced from hypotheses, each embodying a possible explanation for the observed user behavior. Consequently, we calculate the loss of the frozen model on these generated sequences to estimate the t of the hypothesis for the observed behavior. In a third setting, where user features but no hypotheses are available, we can nd exceptional feature sets that indicate unique user behavior. We show the applicability and advantages of our approach on several synthetic datasets and conclude by showing one setting on a real-world dataset, namely the usage behavior of users interacting with their voice assistants.