Recommendation via matrix completion using Kolmogorov complexity

Guilherme Ramos, João Saúde, Carlos Caleiro, Soummya KararXiv 2017 · arXiv

Abstract

Traditional recommendation systems often rely on the assumption that user-item matrices are low-rank, which may not hold for complex, real-world datasets. This paper introduces KolMaC (Kolmogorov Matrix Completion), a novel information-theoretic approach that utilizes Kolmogorov complexity, approximated via data compression, to perform matrix completion. KolMaC is model-free, assumption-free, and highly parallelizable, demonstrating superior performance on high-rank synthetic data and competitive results on standard benchmarks.

Introduction

Modern recommendation engines typically frame the task as a matrix completion problem. Given a sparse matrix of user ratings for items, the goal is to predict missing values. Most state-of-the-art algorithms, such as Singular Value Decomposition (SVD), assume the matrix is "low-rank," implying that a few latent factors can explain user preferences. However, this assumption is often violated in practice. Furthermore, the optimization techniques required for these models are computationally intensive. KolMaC addresses these challenges by shifting the paradigm from linear algebra to information theory.

Methodology: KolMaC

KolMaC employs a neighborhood-based collaborative filtering strategy powered by Kolmogorov complexity.

Kolmogorov Complexity as Similarity

The Kolmogorov complexity of a string is the length of the shortest program required to generate it. KolMaC uses this concept to measure similarity: if two users' rating histories can be compressed significantly when combined, they share high mutual information and are considered similar.

Compression as a Proxy

Since true Kolmogorov complexity is uncomputable, KolMaC uses standard compression algorithms (e.g., zlib) as a practical proxy. User histories are represented as strings of "ItemID:Rating" pairs. The algorithm calculates both user-user similarity and item-item similarity to build a comprehensive recommendation profile.

Decoupled Computation

A significant advantage of KolMaC is its independence. Unlike global optimization methods, recommendations for each user are calculated independently. This "embarrassingly parallel" nature allows the system to scale efficiently across distributed computing clusters without requiring inter-node communication during the prediction phase.

Experimental Evaluation

The authors evaluated KolMaC against several baselines, including SVD, SVD++, and KNN-based methods, using both synthetic and real-world datasets.

Synthetic Data Performance

To test robustness against high-rank data, the researchers used randomly generated full-rank matrices. In these scenarios, traditional low-rank models struggle because their underlying assumptions are invalid.

Table 1: RMSE results on synthetic datasets ($M_1$ through $M_4$). KolMaC CS consistently outperforms traditional methods.

As shown in Table 1, the "Compression Similarity" (CS) variant of KolMaC achieved the lowest Root Mean Square Error (RMSE) across all synthetic configurations, validating its effectiveness in scenarios where the low-rank assumption fails.

Real-World Benchmarks

The algorithm was also tested on the industry-standard MovieLens 100k and 1M datasets.

Table 2: RMSE results on MovieLens datasets. KolMaC remains competitive with state-of-the-art latent factor models.

On these datasets, which are known to exhibit low-rank characteristics, KolMaC achieved competitive RMSE scores. While specialized models like SVD++ maintained a slight edge in accuracy for ML-100k, KolMaC's performance remained within a comparable range while offering superior scalability and fewer modeling assumptions.

Conclusion

KolMaC represents a significant departure from traditional recommendation techniques. By leveraging Kolmogorov complexity, it provides a robust, model-free alternative that excels in high-rank environments and scales naturally with modern distributed hardware. Future work will focus on improving noise sensitivity and implementing pre-clustering techniques to further enhance computational efficiency.

Summary updated

BibTeX
@misc{ramos2017recommendation,
  author = {Guilherme Ramos and João Saúde and Carlos Caleiro and Soummya Kar},
  title = {{Recommendation via matrix completion using Kolmogorov complexity}},
  year = {2017},
  eprint = {1707.06055},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1707.06055},
}
Figure