Recommender systems inspired by the structure of quantum theory
arXiv:1601.06035
Abstract
Physicists use quantum models to describe the behavior of physical systems. Quantum models owe their success to their interpretability, to their relation to probabilistic models (quantization of classical models) and to their high predictive power. Beyond physics, these properties are valuable in general data science. This motivates the use of quantum models to analyze general nonphysical datasets. Here we provide both empirical and theoretical insights into the application of quantum models in data science. In the theoretical part of this paper, we firstly show that quantum models can be exponentially more efficient than probabilistic models because there exist datasets that admit low-dimensional quantum models and only exponentially high-dimensional probabilistic models. Secondly, we explain in what sense quantum models realize a useful relaxation of compressed probabilistic models. Thirdly, we show that sparse datasets admit low-dimensional quantum models and finally, we introduce a method to compute hierarchical orderings of properties of users (e.g., personality traits) and items (e.g., genres of movies). In the empirical part of the paper, we evaluate quantum models in item recommendation and observe that the predictive power of quantum-inspired recommender systems can compete with state-of-the-art recommender systems like SVD++ and PureSVD. Furthermore, we make use of the interpretability of quantum models by computing hierarchical orderings of properties of users and items. This work establishes a connection between data science (item recommendation), information theory (communication complexity), mathematical programming (positive semidefinite factorizations) and physics (quantum models).
References in corpus (32)
- BPR: Bayesian Personalized Ranking from Implicit Feedback
- Probabilistic Latent Semantic Analysis
- Quantum support vector machine for big data classification
- Quantum principal component analysis
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- Quantum algorithms for supervised and unsupervised machine learning
- Device-independent tests of classical and quantum dimensions
- Self-Consistent Quantum Process Tomography
- Multi-Label Prediction via Compressed Sensing
- Concepts and Their Dynamics: A Quantum-Theoretic Modeling of Human Thought
- No extension of quantum theory can have improved predictive power
- Nested Hierarchical Dirichlet Processes
- A lower bound on the dimension of a quantum system given measured data
- Inferring causal structure: a quantum advantage
- Robust Calibration of a Universal Single-Qubit Gate-Set via Robust Phase Estimation
- Characterizing Universal Gate Sets via Dihedral Benchmarking
- All reversible dynamics in maximally non-local theories are trivial
- Robust, self-consistent, closed-form tomography of quantum logic gates on a trapped ion qubit
- Introduction to Quantum Gate Set Tomography
- Training a Large Scale Classifier with the Quantum Adiabatic Algorithm
- Characterizing finite-dimensional quantum behavior
- Minimum Dimension of a Hilbert Space Needed to Generate a Quantum Correlation
- If no information gain implies no disturbance, then any discrete physical theory is classical
- Detecting correlated errors in SPAM tomography
- Representing probabilistic data via ontological models
- Quantum learning of classical stochastic processes: The Completely-Positive Realization Problem
- Compressibility of positive semidefinite factorizations and quantum models
- Learning optimal quantum models is NP-hard
- Expressive recommender systems through normalized nonnegative models
- Some upper and lower bounds on PSD-rank
- Global Completability with Applications to Self-Consistent Quantum Tomography
- Top-N recommendations from expressive recommender systems