PaperlayerView exact revision on arXiv

Source-linked AI summary

Markov Random Fields for Collaborative Filtering

Harald Steck

arXiv:1910.09645v1cs.IRcs.LGstat.ML

TL;DR

Collaborative filtering needs to model dependencies among recommended items in settings with many users and items. The paper uses a Gaussian MRF and a controllable sparse approximation; it reports competitive ranking accuracy across three datasets, including about 20% better ranking accuracy than MULT-VAE on MSD.

  • Problem

    The paper addresses modeling dependencies among recommended items in collaborative filtering, particularly where both users and items are numerous and n > m.

    Source: §1 · p. 1

  • Method

    The approach learns sparse Gaussian MRFs through small-subset regression problems, controlling subset size to trade prediction accuracy for training time.

    Source: §3 · p. 3, Conclusions · p. 8

  • Results

    About 20% better ranking-accuracy than MULT-VAE on MSD, with orders of magnitude less training time.

    Source: §5 · p. 8

  • Takeaways & Limitations

    The approximation provides a controllable accuracy–training-time trade-off for sparse MRF learning in collaborative filtering.

    Source: Conclusions · p. 8

    The approximation assumes, without verification, that selected conditioning nodes form a Markov blanket; the authors call this a strong assumption that need not hold generally.

    Source: §3.2 · p. 4

Abstract

from arXiv · show

In this paper, we model the dependencies among the items that are recommended to a user in a collaborative-filtering problem via a Gaussian Markov Random Field (MRF). We build upon Besag's auto-normal parameterization and pseudo-likelihood, which not only enables computationally efficient learning, but also connects the areas of MRFs and sparse inverse covariance estimation with autoencoders and neighborhood models, two successful approaches in collaborative filtering. We propose a novel approximation for learning sparse MRFs, where the trade-off between recommendation-accuracy and training-time can be controlled. At only a small fraction of the training-time compared to various baselines, including deep nonlinear models, the proposed approach achieved competitive ranking-accuracy on all three well-known data-sets used in our experiments, and notably a 20% gain in accuracy on the data-set with the largest number of items.

1 Introduction

The paper frames item dependencies in collaborative filtering as a Gaussian MRF, connecting MRFs to autoencoders and neighborhood methods. It targets the common large-user, large-item regime with a sparse-model approximation that trades prediction accuracy for training time.

1 Introduction

  • MRFs are presented as closely related to autoencoders and neighborhood-based approaches, alongside progress in sparse inverse covariance estimation.The paper situates these connections against collaborative filtering’s embedding, deep-learning, and competitive neighborhood methods.Source: §1 · p. 1
  • The method targets collaborative filtering with both users and items numerous and n > m, using MRFs to model dependencies among recommended items.Users are samples from the MRF distribution; items are its variables.Source: §1 · p. 1
  • The proposed sparse-MRF approximation makes prediction accuracy and training time a controllable trade-off, spanning neighbor regression and covariance-matrix inversion.The paper presents this regime as typical of collaborative-filtering applications.Source: §1 · p. 1

2 Pseudo-Likelihood

The section develops Besag’s auto-normal parameterization and pseudo-likelihood as a basis for fitting MRFs, deriving a closed-form solution for complete graphs and a corollary for fully connected subgraphs.

2.1 Model Parameterization

  • A user is modeled as a sample from a zero-mean Gaussian over item variables, and an item's predicted score is its conditional expectation given the user's other observed interactions.The auto-normal parameterization expresses each conditional mean as a regression on the remaining nodes.Source: §2.1 · p. 2
  • The auto-normal model sets regression coefficients to zero for absent graph edges and uses conditional variances; computationally, the paper does not enforce covariance symmetry or positive definiteness constraints.The coefficient matrix has a zero diagonal to exclude each item from its own regression.Source: §2.1 · p. 2

2.2 Parameter Fitting

  • Besag’s pseudo-likelihood sums conditional log likelihoods, and its decoupled fitting objective permits optimizing each coefficient-matrix column independently.The paper states that pseudo-likelihood estimates are asymptotically consistent for the auto-normal parameterization.Source: §2.2 · p. 2

2.2.1 Complete Graph

  • For the complete graph, L2-regularized fitting with a zero-diagonal constraint yields a closed-form coefficient matrix from the inverse regularized empirical covariance.The coefficient entries are given by the negative off-diagonal concentration-matrix entries divided by the corresponding diagonal entry.Source: §2.2.1 · p. 3

2.2.2 Subgraphs

  • For a fully connected node subset D and its Markov blanket C, the corollary gives asymptotically consistent coefficient estimates for columns in D using the inverse covariance submatrix on C ∪ D.The estimates cover neighbors in C and the other nodes in D.Source: §2.2.2 · p. 3

3 Sparse Approximation

The sparse approximation uses sparsity to trade recommendation accuracy for training time, rather than to recover the true graph. It thresholds the empirical covariance to identify a sparse pattern, then estimates parameters in batches controlled by r.

3 Sparse Approximation

  • The approximation targets faster training rather than recovery of the true graph or the most accurate parameters at any computational cost.The paper motivates this trade-off by the need to retrain recommenders under time constraints as new data arrives.Source: §3 · p. 3

3.1 Approximate Graph Structure

  • Thresholding the regularized empirical covariance produces a sparse pattern for parameter estimation, with a per-column cap to bound iteration cost.The experiments allow at most 1,000 nonzero entries per column; this cap affects about 2% of items at 0.5% sparsity and none at 0.1%.Source: §3 · p. 3, §3.1 · p. 4

3.2 Approximate Parameter-Estimates

  • The parameter-estimation scheme splits each item’s neighbors using r and assumes the remaining set is a Markov blanket, trading approximation accuracy for computational cost.The Markov-blanket assumption is not verified; increasing r generally worsens approximation accuracy, except when the item neighborhood is a connected component.Source: §3.2 · p. 4
  • Estimating a batch of columns from each assumed neighborhood costs about as much as estimating one column, reducing iterations as r increases.At r = 0, there is no speed-up or approximation relative to separate per-column regression.Source: §3.2 · pp. 4–5
  • The scheme’s complexity depends on sparsity and r, and its approximation accuracy must be assessed empirically because no analytical error bound is available.Step 3 can be parallelized across selected items; the authors suggest occasional higher-accuracy models to assess regularly trained models.Source: §3.2 · p. 5

4 Related Work

The paper relates its MRF approach to sparse inverse covariance estimation, dependency networks, autoencoders, and neighborhood methods. It emphasizes the distinct regime and structure of its learned item similarities.

Auto-models

  • Although the paper relies on Gaussian models for computational efficiency, Eq. 4 and its Corollary provide the best least-squares linear-model fit for any distribution of X.The authors describe the empirical results as corroborating this accuracy–training-time trade-off.Source: §4 · p. 5

Sparse inverse covariance estimation

  • Unlike methods focused on n < m or small-data regimes, this work targets large n, m with n > m and uses set-wise rather than node-wise regression for sparse approximation.Dependency networks also regress nodes against neighbors, but use Gibbs sampling to obtain a consistent joint distribution, increasing computational cost.Source: §4 · p. 5

SLIM

  • SLIM adds L1 regularization and non-negativity constraints to an objective similar to Eq. 3; the paper reports reduced accuracy and increased training time versus B̂(dense).The fsSLIM node-wise regression variant is a special case of the paper’s set-based approximation.Source: §4 · p. 5

Autoencoders and deep learning

  • The MRF pseudo-likelihood reproduces X from X using B, like an autoencoder, but has no encoder, decoder, or hidden layer.The learned B is typically full rank, and its zero diagonal is essential for generalizing to unseen data; the paper presents this as an alternative to low-dimensional embeddings.Source: §4 · pp. 5–6

Neighborhood approaches

  • Unlike heuristic cosine similarities, the approach learns the similarity matrix from data and derives it from inverse covariance rather than rescaled covariance.Its similarity matrix is asymmetric rather than symmetric.Source: §4 · p. 6

5 Experiments

On three standard datasets, the paper evaluates a closed-form dense MRF and a sparse approximation against collaborative-filtering baselines. The sparse model trades training time for ranking accuracy and achieves about 20% better ranking accuracy than MULT-VAE on MSD.

Experimental Setup

  • The evaluation follows [33] on ML-20M, Netflix, and MSD, using nDCG@100 and Recall@20 and Recall@50 under a user-disjoint train, validation, and test split.The binary interaction matrix violates the Gaussian assumption, which the paper uses for computational efficiency; the approach then gives a best least-squares fit of a linear model.Source: §5 · p. 6

Closed-Form Dense Solution

  • The dense closed-form solution’s nDCG@100 is about 1% lower on ML-20M, 3% better on Netflix, and 24% better on MSD than MULT-VAE.Table 1 compares ranking accuracy and training time across three datasets; its caption reports standard errors of about 0.002, 0.001, and 0.001, respectively.Source: §5 · p. 6, Table 1 · p. 7
  • More than ten times longer training times are reported for MULT-VAE than the few minutes needed to learn the dense solution across all three datasets.The comparison is qualified: MULT-VAE times use 50 iterations and may not reflect full convergence, while its reported accuracies use 200 iterations.Source: §5 · p. 7

Sparse Approximation

  • About 16 minutes for the dense solution can be reduced to under a minute with the sparse approximation, with a statistically significant but small accuracy loss on MSD.The standard error is about 0.001, and the loss is described as very small compared with the accuracy difference from MULT-VAE.Source: §5 · p. 7, Table 2 · p. 8
  • Different sparsity levels and values of r provide accuracy–training-time trade-offs, and the comparison of 0.5% sparsity with r = 0.5 against 0.1% with r = 0 favors the former on Recall@50 and training time.The r = 0 case regresses each item against its neighbors and can be more computationally expensive than inverting the full covariance matrix; larger r uses larger item subsets.Source: §5 · p. 7
  • About 20% better ranking accuracy than MULT-VAE on MSD, with fewer parameters and orders of magnitude less training time, is reported for the sparse approximation.At sparsity levels 0.5% and 0.1%, its parameter counts are comparable to dense matrices of sizes 41,140×200 and 41,140×40, respectively.Source: Table 2 · p. 8, §5 · p. 8

Conclusions

The paper presents a computationally efficient approximation for learning sparse Gaussian MRFs in collaborative filtering. Its subset-size control trades ranking accuracy for training time, and the sparse model achieves about 20% better ranking accuracy than the best competing model on the dataset with the most items.

Conclusions

  • The sparse approximation learns Gaussian MRFs through regression problems on small item subsets, with subset size controlling the accuracy–training-time trade-off.It subsumes both single-item regression against MRF neighbors and inversion of the full covariance matrix as extreme cases.Source: Conclusions · p. 8
  • The auto-normal parameterization enforces a zero diagonal in the weight matrix, preventing item self-similarity and providing an alternative to low-dimensional autoencoder embeddings for generalizing to unseen data.Source: Conclusions · p. 8
  • On the dataset with the most items, the sparse approximation uses fewer parameters and several orders of magnitude less training time while achieving about 20% better ranking accuracy than competing models.Source: Conclusions · p. 8

Appendix

The appendix gives a constrained closed-form solution that makes the learned weights invariant to centering the training-data columns. The experiments report no significant effect of the added constraint on ranking metrics.

Appendix

  • The mean-preserving constraint yields a closed-form solution whose learned weights are invariant to centering the training-data columns.The experiments did not observe a significant effect of the constraint on ranking metrics.Source: Appendix · p. 9
Loading 1910.09645v1…