Dynamic Matrix Factorization with Priors on Unknown Values
Dynamic Matrix Factorization with Priors improves sparse recommendation, reaching 0.9276 AUC on AmazonMovies.
Key Findings
Methodology
The paper introduces Dynamic Matrix Factorization with Priors on Unknown Values, treating unobserved ratings as not missing at random. It augments observed-rating loss with a prior that unknown items are usually near the worst score, set to 0 by default. Squared loss, absolute loss, and generalized KL divergence are extended. Randomized block coordinate descent with line search optimizes user and item factors, while Sh, Sw, sh, and sw eliminate explicit enumeration of unknown entries.
Key Results
- With squared loss and a prior, static NDCG on Movielens, FineFoods, and AmazonMovies was 0.5046, 0.1237, and 0.1887, respectively, versus 0.3597, 0.1023, and 0.1103 without a prior. Corresponding AUC scores were 0.8695, 0.8452, and 0.9276.
- On AmazonMovies, prior-aware squared loss exceeded Mult-NMF, which obtained NDCG 0.0959 and AUC 0.6330, and ALS-UV, which obtained 0.0906 and 0.6601. On sparse FineFoods, its AUC was 0.8452 versus 0.3402 for Mult-NMF.
- The prior slightly reduced NDCG restricted to rated items—for example, 0.885 versus 0.886 on Movielens—but strongly improved ranking over the full catalog. This confirms that the method targets realistic discovery rather than reproducing selection-biased observations.
Significance
The study converts a neglected source of recommender bias—selective exposure and voluntary feedback—into an explicit optimization prior. Users tend to rate items they have encountered and expect to like, so observed ratings are not representative of the unobserved catalog. Pushing unknown predictions toward low values regularizes this optimism. The approach is particularly valuable for sparse domains and cold-start users, while its evaluation directly reflects ranking goals through NDCG and AUC rather than RMSE. Industrially, it addresses accuracy, scalability, and update latency together.
Technical Contribution
The central contribution is an algebraic reformulation of dense unknown-item penalties. For squared loss, Sh=Σj hᵀj hj converts the unknown sum into wiShwiᵀ minus observed terms; absolute loss and GKL use sh=Σj hj. Updating one user-item pair costs O((|Ri•|+|R•j|)k+k²) for squared loss and O((|Ri•|+|R•j|)k) for the other losses, independent of total users, items, and ratings. Algorithm 2 locally updates only factors touched by a new rating.
Novelty
Prior work had examined alternative interpretations of missing data, but the authors present this as the first online matrix-factorization mechanism that explicitly regularizes unknown values without significant additional cost. Unlike ALS-UV, Mult-NMF, and standard SGD, the framework does not merely fit observed feedback: it directly shapes the unobserved region and combines randomized block coordinate descent with line-search updates.
Limitations
- The default zero prior assumes that an unknown item is usually undesirable. This can be wrong under forced exposure, passive consumption, or catalogs containing many popular but unseen items, causing excessive down-ranking.
- The online algorithm updates only the directly affected user and item, relying on a local-impact assumption. Long-term accumulated bias, concept drift, and high-volume concurrent arrivals require broader evaluation.
- Squared loss maintains matrix statistics with O(k²) update cost, and the paper does not fully study learned or adaptive user/item-specific priors.
Future Work
The authors suggest adaptive ρ values for users or items. Further work should learn the prior from exposure logs instead of fixing it at zero, incorporate time decay and causal exposure models, and handle distribution drift. Combining the framework with neural ranking, privacy-preserving updates, and production A/B testing could clarify its latency, throughput, and long-term value. A principled treatment of new users, new items, and unobserved-but-unexposed cases remains especially important.
AI Executive Summary
Recommender systems commonly train on observed ratings and treat the rest as ordinary missing data. That assumption is problematic: people voluntarily rate movies, songs, or products they have encountered and often expect to like. The observed matrix is therefore selected, not representative. A model trained only on it can become overoptimistic about the enormous catalog of unseen items. Devooght, Kourtellis, and Mantrach address this issue with Dynamic Matrix Factorization with Priors on Unknown Values, explicitly modeling unknown ratings as not missing at random.
The framework adds a prior term to the standard matrix-factorization objective, usually assigning unknown ratings a value near zero. Its strength is controlled through ρ. The authors extend Squared Loss, Absolute Loss, and Generalized KL Divergence, then optimize factors using Randomized Block Coordinate Descent and line search. Crucially, global statistics such as Sh and Sw transform dense unknown-item sums into sparse computations. When a new rating arrives, Algorithm 2 updates only the affected user and item, making latency independent of the total catalog size.
Across Movielens, FineFoods, and AmazonMovies, prior-aware squared loss achieved NDCG scores of 0.5046, 0.1237, and 0.1887, and AUC scores of 0.8695, 0.8452, and 0.9276. It consistently outperformed prior-free factorization, ALS-UV, and Mult-NMF, especially on sparse data. The trade-off was a small decline when evaluating only already-rated items. The broader lesson is that recommendation models should learn not only what users chose, but also the informative fact that most catalog items were not chosen.
Deep Analysis
Background
Matrix factorization represents users and items with low-dimensional latent vectors and has become central to systems such as Netflix and Yahoo. ALS-UV, nonnegative matrix factorization, and SGD typically optimize observed ratings and extrapolate to unknown entries. Yet exposure and voluntary choice create systematic selection bias. The LaunchCast study cited by the paper found randomly selected songs received predominantly low ratings, whereas voluntary ratings were close to uniform, directly challenging the missing-at-random assumption.
Core Problem
Let R denote observed ratings. Conventional objectives minimize only Σ_(rij∈R)E(rij,wihjᵀ), implicitly assuming that observed feedback generalizes to unobserved items. This can over-rank a huge set of unseen products. The challenge is to impose a low-value prior over unknown entries without enumerating nm positions, and to update the model rapidly when ratings, users, or items arrive.
Innovation
First, the objective adds αΣ_(rij∉R)E(r̂0,wihjᵀ), with r̂0=0 by default. Second, ρ=α(nm−|R|)/|R| expresses the aggregate influence of unknown versus known ratings. Third, dense unknown sums are rewritten using global statistics minus observed terms. Fourth, the paper supplies both static randomized block coordinate descent and dynamic local updates, joining ranking quality with scale-independent update latency.
Methodology
- �� Inputs: sparse ratings R, latent dimension k, regularization λ, and prior ratio ρ.
- �� Squared loss: combine observed squared error, unknown-value penalty, and L1 regularization; maintain Sh=Σj hᵀj hj and Sw=Σi wᵀi wi.
- �� Absolute loss: impose nonnegative W and H, then use sh=Σj hj and sw=Σi wi to remove unknown-item enumeration.
- �� GKL: use D(r||x)=rlog(r/x)−r+x and define D(0||x)=x.
- �� Optimization: traverse users and items in random order, take gradient steps with line search, and update global statistics.
- �� Online learning: for a new rij, alternately optimize wi and hj; initialize a new entity with one random feature set to 1 and the rest to 0.
Experiments
The datasets were Movielens (6,040 users, 3,706 items, 1,000,209 ratings), FineFoods (256,059, 74,258, 568,454), and AmazonMovies (889,176, 253,059, 7,831,442). Comparisons included SL/AL with and without priors, ALS-UV, Mult-NMF, and Vowpal Wabbit. Tested k values ranged from 5 to 500 and ρ from 0.3 to 2. Metrics were NDCG, NDCG on rated items only, and AUC; static results used timestamp-aware splits and ten runs.
Results
Prior-aware squared loss reached NDCG/AUC of 0.5046/0.8695 on Movielens, 0.1237/0.8452 on FineFoods, and 0.1887/0.9276 on AmazonMovies. Without a prior, the corresponding values were 0.3597/0.6548, 0.1023/0.8314, and 0.1103/0.8656. On FineFoods, its AUC dramatically exceeded Mult-NMF's 0.3402, indicating particular value under extreme sparsity.
Applications
The method applies to news, music, movies, products, and advertising, especially when the catalog is much larger than each user's interaction history. A system must maintain latent factors and Sh/Sw or sh/sw. New feedback can trigger a local update, supporting streaming recommendation, rapid personalization after a first interaction, and ranking across very sparse catalogs.
Limitations & Outlook
A fixed low prior is not universally valid: an unobserved item may be unseen rather than disliked, particularly under forced exposure. Local updates may fail to propagate emerging trends quickly, and the reported evidence is stronger for static evaluation than for long-term production dynamics. Squared loss incurs O(k²) statistic updates, while ρ and the prior require validation. Future systems should model exposure, drift, adaptive priors, and online business outcomes.
Plain Language Accessible to non-experts
Imagine a giant bookstore with millions of books, while each customer has opened only a few. A conventional recommendation system studies the books the customer voluntarily picked up and then assumes the untouched books are equally promising. That is like interviewing someone only about books they selected and pretending the rest of the shelves contain no useful information.
This paper adds a sensible rule: books the customer has never picked up should initially be placed lower in the queue, not treated as hidden bestsellers. The system still learns which subjects the customer likes and which books resemble one another, but it also remembers that most untouched books are probably not immediate priorities. A control knob adjusts how strongly this rule matters.
The clever part is speed. When a customer rates a new book, the bookstore does not reorganize every shelf. It mainly adjusts that customer’s profile and the rated book’s position, while keeping a few summary counts for the whole store. This makes updates practical even when the catalog keeps expanding. Tests on movies and food showed especially large gains when the available feedback was very sparse.
ELI14 Explained like you're 14
Suppose you recommend games to friends. If you played a game and gave it five stars, recommending it makes sense. But what about thousands of games you never played? Should the computer assume they are all amazing? Definitely not! You may simply never have seen them. This paper studies exactly that problem: ratings are not random, because people usually rate things they noticed, tried, or expected to enjoy.
The researchers give the computer a useful rule: an unrated item starts with a low score. The computer still learns hidden patterns—who likes strategy games, which movies resemble one another, and which products attract similar people—but it does not push every unknown item to the top just because it lacks information. The rule can be made weaker or stronger with a setting called ρ.
How does it learn quickly? Each person and item gets a short list of hidden numbers. When a new rating appears, the system mainly adjusts the relevant person and item instead of rebuilding the whole website. That is like a teacher correcting only the student and question connected to a new answer. On AmazonMovies, the method reached AUC 0.9276, compared with 0.8656 without the prior.
Still, it is not magic. If a website forced you to see an item, not rating it does not mean you disliked it. Fast local updates may also miss sudden trends. A future version could learn a different starting guess for every user and item.
Glossary
Matrix Factorization
A method that represents users and items with short latent vectors. Their inner product reconstructs observed preferences and produces rankings.
The paper factorizes ratings into user matrix W and item matrix H.
Not Missing At Random
Missingness depends on the value itself or on a selective observation process. Unobserved feedback is therefore not a random sample of preferences.
This assumption motivates the low-value prior.
Prior on Unknown Values
A preferred baseline for unobserved ratings. The paper uses r̂0=0 by default and controls its weight with α or ρ.
It regularizes predictions over the unobserved catalog.
NDCG
A ranking metric that rewards relevant items, especially when placed near the top. Position-dependent discounting reflects user attention.
It evaluates static recommendation quality.
AUC
The probability that a positive item is ranked above a negative one. Random ranking is about 0.5 and perfect ranking is 1.
It tests whether future-rated items outrank unrated items.
Randomized Block Coordinate Descent
An optimizer that updates one user or item factor block at a time in random order. Line search chooses a non-increasing objective step.
It is used for static factorization and convergence.
Open Questions Unanswered questions from this research
- 1 It remains unclear when r̂0=0 is appropriate across exposure mechanisms. Exposure logs and causal models are needed to distinguish dislike from simple non-exposure.
- 2 The long-run stability of local updates under concept drift, sudden popularity changes, and concurrent arrivals is not fully established by the reported experiments.
- 3 User- or item-specific ρ may improve calibration, but its extra parameters, validation burden, and theoretical behavior require study.
Applications
Immediate Applications
Real-time movie and product ranking
A platform can train prior-aware squared loss, maintain Sh and Sw, and locally update the relevant user and item after each new rating. This fits large catalogs with sparse feedback and strict recommendation-latency requirements.
Cold-start personalization
A new user or item can receive the paper's sparse initialization, then be optimized immediately after the first interaction. The system avoids waiting for a full retraining cycle while still using the unknown-value prior.
Long-term Vision
Exposure-aware adaptive recommendation
Future systems could combine exposure, clicks, skips, and time with learned user- and item-specific priors. This may reduce the bias created by applying one fixed low baseline to every unobserved interaction.
Abstract
Advanced and effective collaborative filtering methods based on explicit feedback assume that unknown ratings do not follow the same model as the observed ones (\emph{not missing at random}). In this work, we build on this assumption, and introduce a novel dynamic matrix factorization framework that allows to set an explicit prior on unknown values. When new ratings, users, or items enter the system, we can update the factorization in time independent of the size of data (number of users, items and ratings). Hence, we can quickly recommend items even to very recent users. We test our methods on three large datasets, including two very sparse ones, in static and dynamic conditions. In each case, we outrank state-of-the-art matrix factorization methods that do not use a prior on unknown ratings.