Order-Two Markov Chain

Let’s consider an example of an order-two Markov Chain model using the weather. Let’s assume we have three states: sunny ($S$), cloudy ($C$), and rainy ($R$).

In an order-two Markov Chain, the weather of today ($t$) would depend on the weather of yesterday ($t-1$) and the day before yesterday ($t-2$). The transition probability can be denoted as $P\left(S_t\right|S_{t-1},S_{t-2})$.

The Markov Chain can be defined by a transition matrix which provides the probabilities of transitioning from one state to another. However, because we’re dealing with an order-two Markov Chain, we would have a transition tensor instead. For simplicity, let’s say we have the following transition probabilities:

You can visualize these probabilities in a three-dimensional cube, where the first two dimensions represent the state of today and yesterday, and the third dimension represents the possible states of tomorrow.

If the weather was sunny for the last two days, and we want to predict the weather for tomorrow, we would look at the transition probabilities starting with $(S,S)$, which are $P\left(S\right|S,S)=0.7$, $P\left(C\right|S,S)=0.2$, and $P\left(R\right|S,S)=0.1$. Therefore, according to our model, there’s a 70% chance that it will be sunny, a 20% chance that it will be cloudy, and a 10% chance that it will be rainy.

The probabilities in the transition matrix (or tensor) are typically estimated from data. If you have a historical record of the weather for several years, you can count the number of times each transition occurs and divide by the total number of transitions to estimate the probability.

This is only a basic demonstration of an order-two Markov Chain. In real applications, the states might be much more numerous and the transition matrix much larger, but the principles remain the same.

Other Markov Models

A more advanced Markovian approach is the Markov Decision Process (MDP), which extends the Markov Chain by introducing actions and rewards. In the context of recommender systems, each action could represent a recommendation, and the reward could be the user’s response to the recommendation. By incorporating user feedback, the MDP can learn more personalized recommendation strategies.

MDPs are defined by a tuple $(S,A,P,R)$, where $S$ is the set of states, $A$ is the set of actions, $P$ is the state transition probability matrix, and $R$ is the reward function.

Let’s use a simplified MDP for a movie recommender system as an example.

1. States ($S$): These could represent the genres of movies a user has watched in the past. For simplicity, let’s say we have three states: Comedy ($C$), Drama ($D$), and Action ($A$).

2. Actions ($A$): These could represent the movies that can be recommended. For this example, let’s say we have five actions (movies): Movie 1, 2, 3, 4, and 5.

3. Transition Probabilities ($P$): This represents the likelihood of transitioning from one state to another given a specific action. For instance, if the user just watched a Drama ($D$), and we recommend Movie 3 (which is an Action movie), the transition probability $P\left(A\right|D,Movie3)$ might be 0.6, indicating a 60% chance the user will watch another Action movie.

4. Rewards ($R$): This is the feedback from the user after taking an action (recommendation). Let’s assume for simplicity that a user’s click on a recommended movie gives a reward of +1, and no click is a reward of 0.

The aim of the recommender system in this context is to learn a policy $\pi :S\to A$ that maximizes the expected cumulative reward. A policy dictates which action the agent (the recommender system) should take in each state.

This can be learned via reinforcement learning algorithms, such as Q-Learning or Policy Iteration, which essentially learn the value of taking an action in a state (i.e., recommending a movie after the user has watched a certain genre), considering the immediate reward and the potential future rewards.

The main challenge in a real-world recommender system scenario is that both the state and action spaces are extremely large, and the transition dynamics and reward function can be complex and difficult to estimate accurately. But, the principles demonstrated in this simple example remain the same.

Despite the promising performance of Markov Chain-based recommender systems, several challenges remain. The memorylessness assumption of the Markov Chain may not hold in certain scenarios where long-term dependencies exist. Furthermore, most Markov Chain models treat user-item interactions as binary events (either interaction or no interaction), which oversimplifies the variety of interactions users may have with items, such as browsing, clicking, and purchasing.

Next, we’ll cover neural networks. We’ll see how some architectures you’re likely familiar with can be relevant to learn a sequential recommender task.

Self-Attentive Sequential Recommendation:

SASRec is the first transformer model we’ll consider. It is an auto-regressive sequential model (very similar to a causal language model) to predict the next user-interaction from the past user-interactions. Inspired by the success of the transformer models in sequential mining tasks, the self-attention based architecture is used for sequential recommendation.

When we say that the SASRec model is trained in an autoregressive manner we mean that the self-attention is only allowed to attend to the earlier positions in the sequence – looking into the future is not permitted. Earlier when we talk about the mushing, think of this as only mushing forward the influence. Some people call this “causal” because it respects the causal arrow of time. The model also allows for a learnable positional encoding, which means that the updates carry down to the embedding layer. This model used 2 transformer blocks.

BERT4Rec:

Inspired by the BERT model in NLP, BERT4Rec improved upon SASRec by training a bi-directional masked sequential (language) model.

While BERT used a masked language model for pre-training word embeddings, BERT4Rec used this architecture to train end-to-end recommendation system. It tries to predict the masked items in the user interaction sequence. Similar to the original BERT model, the self-attention is bidirectional i.e. it can look at both the past as well as future interactions in the action sequence. To prevent leakage of future information and to emulate the realistic settings, only the last item in the sequence is masked during inference. Using item masking, BERT4Rec outperforms SASRec, however a drawback of the BERT4Rec model is that it is quite compute intensive and requires much more training time.

Recency Sampling

Sequential recommendation and the adoption of transformer architecture in these tasks has seen a lot of interest recently. These deep neural network models like BERT4Rec and SASRec have shown improved performance over traditional approaches. However, these models suffer from slow training problems. A recently published paper – haha, get it – addresses the question of improving training efficiency while achieving state-of-the-art performance.

The two training paradigms we’ve just seen for sequential models are - autoregressive which tries to predict the next item in the user interaction sequence, and masked which tries to predict masked items in the interaction sequence. The autoregressive approach doesn’t use the beginning of the sequence as labels in the training process, and thus valuable information is lost. The masked approach on the other hand is only weakly related to the end goal of the sequential recommendation.

This paper, proposes a recency-based sampling of sequences which samples positive examples from the sequences to build the training data. The sampling is designed to give more recent interactions higher chances of being sampled. However, due to the probabilistic nature of the sampling mechanism, even the oldest of the interactions have non-zero chances of being chosen. An exponential function is employed as a sampling routine which interpolates between the masking-based sampling where each interaction has equal probability of being sampled and autoregressive sampling where items from the end of sequence are sampled. This showed superior performance in sequential recommendation tasks while requiring much less training time. Compare this approach to some of the other examples where we saw sampling provide significant improvements in training recommender systems!

Merging Static and Sequential

Pinterest recently released a paper describing their personalized recommendation system which is built to leverage raw user actions. The recommendation task is decomposed into modeling users’ long-term and short-term intentions.

The process of comprehending long-term user interests is accomplished by training an end-to-end embedding model, referred to as PinnerFormer, to learn from a user’s historical actions on the platform. These actions are subsequently transformed into user embeddings, which are designed for optimization based on anticipated long-term future user activities.

This procedure employs an adapted transformer model to operate on users’ sequential actions with the intent to forecast their long-term future activities. Each user’s activity is compiled into a sequence, encompassing their actions over a specific time window, such as one year. The Graph Neural Network-based (GNN-based) PinSage embeddings, in conjunction with relevant metadata (for example, the type of action, the timestamp, and so forth), are used to add features to each action in the sequence.

Distinct from traditional sequential modeling tasks and sequential recommendation systems, PinnerFormer is designed to predict extended future user activities rather than the immediately subsequent action. This objective is achieved by training the model to foresee a user’s positive future interactions over a window of 14 days following the embedding’s generation. In comparison, traditional sequential models would only anticipate the subsequent action.

This alternate approach allows for the embedding generation to occur offline in a batch processing mode, resulting in significant reductions in infrastructure needs. In contrast to most traditional sequential modeling systems, which operate in real-time and incur substantial computational and infrastructure costs, these embeddings can be produced in batches, for instance, on a daily basis, rather than every time a user performs an action.

A dense all-action loss is introduced in this methodology to facilitate batch training of the model. The objective here is not to predict the immediate next action but rather all the actions the user will undertake over the subsequent $K$ days. The aim is to predict all occurrences of a user’s positive interactions at intervals such as $T+3$, $T+8$, and $T+12$, thereby compelling the system to learn long-term intentions. While traditionally the last action’s embedding is used to make the prediction, the dense all-action loss employs randomly selected positions in the action sequence, and the corresponding embedding is used to predict all actions for each of those positions.

Based on offline and online experimental results, the use of dense all-action loss to train for long-term user actions has significantly bridged the gap between batch generation and real-time generation of user embeddings. Moreover, to accommodate users’ short-term interests, the transformer model retrieves the most recent actions for each user in real-time, processing them along with the long-term user embeddings.