PaperlayerView exact revision on arXiv

Source-linked AI summary

Fusing Similarity Models with Markov Chains for Sparse Sequential Recommendation

Ruining He, Julian McAuley

arXiv:1609.09152v1cs.IR

TL;DR

Personalized sequential recommendation must combine long-term preferences with short-term transitions, despite sparsity in real-world data. Fossil fuses similarity-based models with Markov Chains, outperforming existing methods especially on sparse datasets while capturing sequential and personalized dynamics.

  • Problem

    Sparse real-world data complicates personalized sequential prediction, which requires combining long-term preferences with short-term dynamics.

  • Method

    Fossil fuses similarity-based methods with Markov Chains using personalized weighting over sequence items.

  • Results

    Fossil outperforms existing methods considerably, with especially strong performance under sparsity, while capturing sequential and personalized dynamics.

  • Takeaways & Limitations

    Similarity-based modeling and high-order Markov Chains both contribute considerably to Fossil's performance on sparse sequential recommendation.

Abstract

from arXiv · show

Predicting personalized sequential behavior is a key task for recommender systems. In order to predict user actions such as the next product to purchase, movie to watch, or place to visit, it is essential to take into account both long-term user preferences and sequential patterns (i.e., short-term dynamics). Matrix Factorization and Markov Chain methods have emerged as two separate but powerful paradigms for modeling the two respectively. Combining these ideas has led to unified methods that accommodate long- and short-term dynamics simultaneously by modeling pairwise user-item and item-item interactions. In spite of the success of such methods for tackling dense data, they are challenged by sparsity issues, which are prevalent in real-world datasets. In recent years, similarity-based methods have been proposed for (sequentially-unaware) item recommendation with promising results on sparse datasets. In this paper, we propose to fuse such methods with Markov Chains to make personalized sequential recommendations. We evaluate our method, Fossil, on a variety of large, real-world datasets. We show quantitatively that Fossil outperforms alternative algorithms, especially on sparse datasets, and qualitatively that it captures personalized dynamics and is able to make meaningful recommendations.

I. INTRODUCTION

Personalized sequential recommendation must combine long-term preferences with short-term transitions, yet sparsity makes both difficult to estimate. Fossil fuses similarity-based modeling with Markov Chains and is designed for sparse, long-tailed data.

  • Long-term user preferences and short-term sequential patterns correspond to user-item and item-item interactions, respectively.
  • Sparse real-world datasets make personalized sequential prediction difficult because limited training sequences hinder accurate parameter estimation.
  • FPMC combines Matrix Factorization with a first-order Markov Chain but remains vulnerable to sparsity and long-tailed data.
  • Fossil fuses similarity-based methods with Markov Chains using personalized weights over sequence items to model preferences and sequential behavior.
  • For users with few observed actions, Fossil can shift more weight toward short-term dynamics and make reasonable predictions.
  • Across large real-world datasets, Fossil outperforms state-of-the-art algorithms and analyzes learned sequential and personalized dynamics.

III. SEQUENTIAL PREDICTION

Sequential recommendation predicts a user's next action from historical events while modeling long-term preferences through user-item affinities and item similarities. Similarity-based methods reduce reliance on explicit user parameters but face large parameterization challenges under sparse interactions.

  • A. Problem Formulation and Notation: Sequential prediction uses each user's action sequence to predict that user's next action and generate recommendations.
  • B. Modeling User Preferences: Matrix Factorization represents users and items in a K-dimensional latent space, estimating affinity through the inner product of their vectors.
  • B. Modeling User Preferences: SLIM learns an item-to-item similarity matrix from user action histories to estimate user-item affinity from similarities to previously interacted items.
  • B. Modeling User Preferences: Without explicit user parameterization, SLIM relaxes low-rank user representations and has achieved higher recommendation accuracy.
  • B. Modeling User Preferences: SLIM must estimate |I|×|I| parameters from sparse interactions, while FISM reduces parameters by decomposing similarity into two low-rank matrices.

C. Modeling Sequential Patterns

Markov Chains capture short-term item transitions, while Matrix Factorization captures personalized preferences. FPMC combines them, motivating methods that integrate sequential and long-term dynamics more carefully.

  • A first-order Markov Chain estimates the next item's probability from the last interacted item using an item-to-item transition matrix.
  • Factorizing the transition matrix into low-rank matrices provides a further improvement for modeling sequential transitions.
  • SLIM can assign zero similarity to indirectly related items when only two-step co-purchase links are observed.
  • Markov Chains capture short-term dynamics but are limited in modeling personal, long-term preferences.
  • FPMC combines Matrix Factorization and a first-order Markov Chain so its prediction includes both user preference and similarity to the last item.

IV. THE PROPOSED Fossil MODEL

Fossil combines similarity-based recommendation with Markov Chains, using personalized weighting to balance long-term preferences and short-term sequential dynamics. It reduces parameters for sparse data by tying item representations across these components.

  • Fossil combines similarity-based methods with Markov Chains to make personalized sequential predictions.The approach contrasts with FPMC-style combinations of Matrix Factorization and first-order Markov Chains.
  • Each user has a scalar ηu that controls the relative weights of long-term and short-term dynamics, while η is shared globally.The global parameter centers user-specific weights at 0.
  • Fossil reduces four item-embedding matrices to two by enforcing P = M and Q = N.The reduction limits the number of parameters, which is useful for sparse datasets; the paper motivates it by noting that sequentially related items are also similar.
  • The model adds an item bias βj and normalizes its long-term component before forming the final prediction.The displayed formulation includes the personalized weighting term and item-vector inner product.

B. Modeling Higher-order Markov Chains

The higher-order extension uses the most recent L consumed items to model smoothness across multiple time steps. Personalized and global vectors assign different weights to actions at different lags, and S-BPR trains the resulting ranking model.

  • Modeling Higher-order Markov Chains: An Lth-order Markov Chain predicts the next item from the most recent L items consumed by user u.The formulation is designed to capture smoothness across multiple time steps.
  • Modeling Higher-order Markov Chains: Each previous action receives a different lag weight through user-specific ηu and global η vectors.Both vectors contain L components corresponding to the preceding time steps.
  • Parameter Inference: S-BPR uses a sigmoid to model the probability that the ground-truth item outranks a negative item at each user-time step.The prediction shorthand refers to the higher-order model output.
  • Parameter Inference: The parameters are inferred by MAP estimation over pairwise rankings across users and time steps, with a Gaussian prior.The additive formulation allows training to begin at t = 2 rather than L + 1.
  • Parameter Inference: SGD samples a user, a time step, and a negative item to optimize the pairwise ranking objective.The procedure is used because the large number of positive-negative pairs makes conventional batch gradient descent unaffordable.

V. EXPERIMENTS

The experiments use large datasets from multiple recommendation domains, including products, movies, reviews, and check-ins. The datasets are filtered and converted to implicit binary actions before reporting statistics.

  • Datasets and Statistics: The evaluation spans large datasets covering next-product, next-movie, next-review, and next-place prediction.The datasets differ substantially in user and item density.
  • Datasets and Statistics: Amazon categories, Epinions, and other domains provide varied real-world sequential recommendation settings.Amazon data span timestamps from May 1996 to July 2014 and are organized by product category.
  • Datasets and Statistics: Users and items with fewer than five associated actions are filtered from each dataset.The resulting dataset statistics are reported in Table II.
  • Datasets and Statistics: Star ratings are converted to implicit binary actions, preserving whether a purchase, review, or check-in occurred rather than the rating value.The processed datasets treat these actions as positive feedback.

B. Evaluation Methodology

The study evaluates methods with AUC on held-out recent actions, using common training and validation procedures. Comparisons cover popularity, personalized and similarity-based recommenders, Markov models, FPMC, and Fossil.

  • Evaluation Methodology: All methods are evaluated with AUC because the comparison methods directly optimize this metric during training.The evaluation therefore aligns the test metric with the pairwise ranking objective.
  • Evaluation Methodology: For each user, the two most recent actions form validation and test sets, while earlier actions comprise the training set.Hyperparameters are tuned on validation data before final evaluation on the test set.
  • Evaluation Methodology: The held-out ground-truth item is evaluated by how highly it ranks against negative items for each user.The indicator function records whether the ground-truth score exceeds a negative item's score.
  • Comparison Methods: Baselines include POP, BPR-MF, FISM, FMC, and FPMC, alongside the proposed Fossil method.These methods represent popularity, long-term preference, similarity-based, purely sequential, and combined modeling strategies.
  • Comparison Methods: The comparison framework distinguishes methods by personalization, sequential awareness, similarity modeling, explicit user modeling, and high-order Markov Chains.The attributes are collated in Table III.
  • Comparison Methods: The baselines test sequentially unaware methods, purely sequential methods, FPMC's combination, and Fossil's similarity-plus-Markov design.All methods except POP optimize pairwise ground-truth-versus-negative ranking during training.

D. Performance and Quantitative Analysis

Fossil is evaluated against personalized, similarity-based, Markov-chain, and popularity baselines using AUC across multiple datasets. The experiments show strong performance under a common latent dimension setting, with Fossil outperforming all baselines on average.

  • FISM improves over BPR-MF by over 4 percent on average across all datasets.FISM avoids explicitly parameterizing users and therefore serves as a strong building block for sparse recommendation.
  • FPMC improves over BPR-MF by 0.99 percent and over FMC by 0.80 percent on average when K = 10.FPMC combines long-term personalization with short-term sequential modeling.
  • Fossil outperforms the best baseline in every case, with an average improvement of 2.5 percent.The comparison includes POP, BPR-MF, FISM, FMC, and FPMC.
  • The experiments use large real-world datasets, and the largest dataset requires around four hours to train Fossil with third-order Markov Chains and 20 latent dimensions.Prediction costs O(LK), which remains manageable when L and K are small.

VI. A STUDY ON THE EFFECT OF DATA SPARSITY

Experiments progressively reduce the number of recent actions per user to study sparsity. Fossil benefits increasingly from its combined similarity and Markov-chain modeling as data become sparser.

  • VI. A STUDY ON THE EFFECT OF DATA SPARSITY: Reducing each user’s history from 50 to 5 recent actions creates increasingly sparse datasets without sampling away sequential structure.Accuracy declines for all methods as the threshold decreases.
  • A. How Much do Short-term Dynamics Help?: FPMC’s improvement over BPR-MF decreases as data become sparser because modeling short-term dynamics introduces additional parameters.Fossil improves over FISM more consistently because it adds only the weighting vectors η and ηu.
  • B. How Much do Long-term Dynamics Help?: As datasets become sparser, Fossil’s improvement over FMC increases by as much as 9 percent, compared with FPMC’s relatively flat improvement of around 3 percent.This supports the compatibility of similarity-based modeling with Markov Chains.
  • C. Fossil and FPMC: Fossil increasingly outperforms FPMC as sparsity grows, while FPMC requires as many as 50 actions per user to achieve comparable performance.Reducing FPMC’s parameters by setting M = N does not significantly improve prediction accuracy.
  • C. Fossil and FPMC: The similarity-based and high-order Markov-chain components both contribute considerably to Fossil’s performance, especially on sparse datasets.The combined model generates strong results for sparse sequential recommendation.

VII. VISUALIZATION AND QUALITATIVE ANALYSIS

The qualitative analysis visualizes Fossil’s learned sequential and personalized dynamics on the Clothing, Shoes and Jewelry dataset. It shows how item transitions and user-specific weighting produce meaningful recommendations.

  • VII. VISUALIZATION AND QUALITATIVE ANALYSIS: The visualization uses a first-order Fossil model trained on the Clothing, Shoes and Jewelry dataset with K = 10.The dataset is selected for its large size, variability, and suitability for demonstrating user actions.
  • A. Visualizing Sequential Dynamics: Fossil represents an item transition through the inner product of the consumed item’s P vector and the candidate item’s Q vector.The highest-ranked next items are selected by minimizing ⟨Pquery, Qj⟩ according to the figure description.
  • For cold users, Fossil assigns higher weights to sequential patterns rather than relying as heavily on personalized history.This weighting strategy is presented as a way to make reasonable predictions from few observed actions.
  • A. Visualizing Sequential Dynamics: The retrieved items preserve recognizable category structure, including Star Wars items, watches, shirts, and jewelry.Some recommendations also cross subcategories to form compatible outfits, such as the examples in rows 2 and 5.

B. Visualizing Personal Dynamics

Fossil learns personalized weights that balance short-term sequential dynamics against long-term preferences. Its visualizations show that this balance shifts with user history and reflects recognizable within-sequence consistency.

  • Fossil learns personalized weights ηu_0 to compare the importance of short-term and long-term dynamics.These weights are visualized for users in the dataset.
  • Users with few actions receive higher sequential weights, while users with more actions receive greater reliance on long-term preferences.The paper attributes this shift to the increasing accuracy of preference estimates as observations accumulate.
  • Figure 8 samples users with the largest ηu_0 and at least five training actions to visualize sequential consistency rather than sparsity alone.The displayed recommendations are compared with corresponding test-set ground-truth items.
  • Within-sequence consistency is visible in examples involving jewelry, wearables for boys, and business men.
  • Fossil’s ability to accommodate multiple dynamics and personalization is presented as central to its success in sequential recommendation.The broader experiments report favorable quantitative results and meaningful personalized dynamics.
Loading 1609.09152v1…