Different types of Matrix Factorization Techniques and Scaling mechanisms for online Recommendation Engines

Introduction

Low-rank approximations of data matrices have become an important tool in Machine Learning in the field of bio-informatics, computer vision, text processing, recommender systems, and others. They provide efficient compact representation of multi-dimensional vectors by embedding high dimensional data in lower dimensional spaces. In such representations, it comes to rescue by mitigating noise, unfolding latent relations, and facilitates further processing.

In general, MF is a process to find two factor matrices, P ∈ R, k×m and Q ∈ R, k×n, to describe a given m-by-n training matrix R in which some entries may be missing. MF can be found in many applications, but in the context of blog, we limit it only to collaborative filtering in recommender systems. It is based on the assumption that the entries of R are the historical users’ preferences for merchandises, and the task on hand is to predict unobserved user behavior to assist any individual with a suitable recommendation.

In this blog, I discuss different types of matrix factorization techniques for real-time recommendation engines and their corresponding Python libraries. In the next blog, let’s get familiar with some Python code samples.

PyMF — Python Matrix Factorization Module

Python Matrix Factorization (PyMF) is a Python open-source tool for MF. It is equipped with a module for several constrained/unconstrained matrix factorization (and related) methods capable of handling both sparse and dense matrices. It requires cvxopt, numpy and scipy. Applications of factorizing large matrices are: gene expression data and microarrays, term by document matrices, graph adjacency matrices, etc.

$ pip install pyMF   # for python 2.67/2.7
$ pip install pymf3   # for python 3

Convex Non-negative Matrix Factorization (CNMF):

NMF factorizes a non-negative input matrix V into two non-negative matrix factors V = WH such that W describes “clusters” of the datasets. While deriving suitable relationship between matrices using MF in genotypes, social networks or images, it has been found that it is often beneficial to ensure V to contain meaningful “cluster centroids”. This process helps to restrict W to be convex combinations of data points. Each data point is a convex combination of vertices of the data convex hull; the aim is to restrict W further to be vertices of the convex hull. Characteristics of convex-hull NMF approach are:

• The expected size of the convex hull typically grows considerably slower than that of the dataset, where for n random Gaussian points in the plane, the expected number of vertices of the convex hull is Ω(√log n), i.e., the candidate set typically grows much slower than the data set.
• Distance preserving, low-dimensional projections of the data allow efficient sampling of the convex hull and evaluate the candidate vertices.
• Convex-NMF enforces notion of cluster centroids and is naturally sparse.

Convex-NMF when applied to both nonnegative and mixed-sign data matrices. It has been further observed that the factors W and G both tend to be very sparse.

Semi Non-negative Matrix Factorization (SNMF)

For an input data matrix X = (x1, . . . , xn) contain a collection of n data vectors as columns. Considering factorizations in the form of SVD as : X ≈ F G^T, where X ∈ R p×n , F ∈ R p×k and G ∈ R n×k . In the case of the SVD, there are no restrictions on the signs of F and G; moreover, the data matrix X is also unconstrained. NMF can also be written in this form, where the data matrix X is nonnegative, as are the factors F and G. For non-negative matrices, the following holds true:

When the data matrix is unconstrained (i.e., it may have mixed signs), the factorization technique can be referred to as Semi-NMF, in which we restrict G to be nonnegative while placing no restriction on the signs of F. Further, Semi-NMF can be motivated from the perspective of clustering. On applying K-means clustering on X with cluster centroids F = (f1, . . . ,fk), G denotes the cluster indicators: i.e., gik = 1, if xi belongs to cluster ck; gik = 0, otherwise.

K-means clustering algorithm is kind of unsupervised technique that also holds the objective function for matrix approximation. This approximation will generally be tighter on relaxing the optimization by allowing gij to range over values in (0, 1), or values in (0,∞). This yields the Semi-NMF matrix factorization.

Tight Semi Non-Negative Matrix Factorization

In close relation to methods SNMF and CMF, the tight semi non-negative matrix decomposition is the result of a multi-objective optimization problem. However, for V = WH, it does not require that the templates, i.e., the columns of W, be convex combinations of the original data in V. There will be two objectives:

• Minimizing the error in the approximation of the original data (model fidelity).
• Minimizing the maximum angle between any two columns of W (model tightness).

NMF-like algorithms (Semi-NMF, Convex-NMF, Kernel-NMF, Tri-NMF) always outperform K- means clustering.

Other matrix factorization techniques supported by PyMF include: Archetypal analysis (AA), Simplex volume maximization (SiVM), Convex-hull non-negative matrix factorization (CHNMF), Binary matrix factorization (BNMF), Singular value decomposition (SVD), Principal component analysis (PCA), K-means clustering (Kmeans), C-means clustering (Cmeans), CUR decomposition (CUR), Compaxt matrix decomposition (CMD).

Fast Parallel Stochastic Gradient Method for Matrix Factorization

LIBMF is an open source large-scale sparse matrix factorization tool. It has been used primarily for approximating an incomplete matrix using multiplication, when the product of two matrices are applied in a latent space.

• LIBMF has in-built “binary matrix factorization (BMF), and one-class matrix factorization”. Some packages (e.g., scikit-learn,2 mlpack,3 and nimfa4) support a variety of MF problems with different functions, but they do not implement parallel MF algorithms published in recent five years”.
• LIBMF framework also supports BMF, OCMF, and L1 regularization.
• LIBMF has supports flexibility of using disk as a buffer to factorize a huge matrix that may not fit into their memory. For example, the training matrix can be cached, thereby helping to reduce the memory usage.
• LIBMF supports parallel computation in a multi-core machine.
• LIBPMF (parallel version of LIBMF) can only solve real-valued matrix factorization (RVMF) with a squared loss and L2-norm regularization.
• RVMF uses MF algorithm to find P and Q to approximate the values of entries as accurate as possible. BMF focuses on learning the correct signs of entries. Both RVMF and BMF can be formulated as a non-convex optimization problem”.
• LIBMF uses “CPU instructions (e.g., SSE) to accelerate vector operations, taking less than 20 minutes to converge to a reasonable level on a dataset of 1.7B ratings.”
• Supports cross-validation for parameter selection and allows selection of suitable evaluation criteria such as mean percentile rank and area under the curve for different MF problems.

pip install libmf

Collective Matrix Factorization (pyCMF and cmfrec)

Collective Matrix Factorization is a Machine Learning method that decomposes two matrices X, Y, into three matrices U, V and Z, such that

where f is either the identity or sigmoid function. This is a collaborative filtering model for recommender systems that takes as input explicit item ratings and side information about users and/or items. The overall idea was extended here to also be able to do cold-start recommendations (of users and items that were not in the training data).

pyCMF

CMF decomposes complex and multiple relationships into a small number of components, and can provide valuable insights into your data.

$ pip install git+https://github.com/smn-ailab/PyCMF

cmfrec

cmfrec fits a collective matrix factorization model. It uses ratings data along with item and/or user side information. It is further known to factorize all matrices with common (shared) factors.

$ pip install cmfrec

Topic modeling and text classification

CMF can be used for topic modeling to explore the data to extract topics like toxicity, sentiments, classify relevant texts and documents clustering.

Movie rating prediction

Prediction tasks involving relations between entities like movies, users, ratings, actors use CMF to the model relations and predict unobserved edges.

Singular Value Decomposition

Singular Value Decomposition (SVD) is a matrix decomposition method. It has been well known over decades for reducing a matrix to its constituent parts in order to make certain subsequent matrix calculations cheaper simpler.

A = U . Sigma . V^Z

where A is the real m x n matrix that is to be decomposed, U is an m x m matrix, Sigma is an m x n diagonal matrix, and V^Z is the transpose of an n x n matrix.

pip install numpy
pip install scipy

Nimfa

Nimfa is a Python library for nonnegative matrix factorization including both dense and sparse matrix, and supports methods like nonnegative double singular value decomposition, initialization approaches, quality scoring.

NMF’s distinguishing feature is imposition of non-negativity constraints, where only non-subtractive combinations of vectors in original space are allowed. Specific knowledge of the problem domain can be modelled by further imposing discriminative constraints, locality preservation, network-regularization or constraint on sparsity.

In a standard model of NMF, a data matrix V is factorized to V ≡ W H by solving a related optimization problem. Non-negative matrices W and H are commonly referred to as basis and mixture matrix, respectively.

Nimfa implements an optimization with Euclidean or Kullback-Leibler cost function, along with Frobenius, divergence or connectivity costs. It also supports alternative optimization algorithms including Bayesian NMF Gibbs sampler, iterated conditional modes NMF, probabilistic NMF and alternating least squares NMF using projected gradient method for sub-problems. Sparse matrix factorization is provided either through probabilistic or alternating non-negativity-constrained least squares factorization. Fisher local factorization may be used when dependency of a new feature is constrained to a given small number of original features.

Nimfa also implements several non-standard models. These comprise non-smooth factorization V ≡ W S(θ) H and multiple model factorization for simultaneous treatment of several input matrices and their factorization with the same basis matrix W.

All mentioned optimizations are incremental, starting with initial approximation of matrices W and H. The initialization choice can speed up the convergence and improve the overall quality of the factorization results.

Surprise

• Surprise python library provides various much easier prediction algorithms that utilises MF. These are baseline algorithms, neighborhood methods, matrix factorization-based (SVD, PMF, SVD++, NMF), and many others. It also has various similarity measures (cosine, MSD, pearson…) as some of its functions.

$ pip install surprise

• Make it easy to implement new algorithm ideas.
• Provide tools to evaluate, analyze and compare the algorithms’ performance. Cross-validation procedures can be run very easily using powerful CV iterators, as well as exhaustive search over a set of parameters.

Probabilistic Matrix Factorization

PMF models user preference matrix as a product of two lower-rank user and movie matrix. It scales linearly with the number of observations and performs well on the large, sparse, and very imbalanced datasets. Further, PMF model can include learnable adaptive priors over the movie and user feature vectors to tune and control the model complexity automatically. Further, dimensionality reduction and regularization help to determine suitable parameters for training the best model, thereby reducing the computational demands of traditional (deterministic) algorithms.

The constrained version of the PMF model is designed on the basis of assumption that users who have rated similar sets of movies are likely to have similar preferences, helping better generalization for users with very few ratings. It achieves this by constraining user-specific feature vectors that have a strong effect on infrequent users. Nimfa supports PMF along with others:

$ git clone https://github.com/Songbo729066989/recsys.git
 
$ git clone https://github.com/meowoodie/Probabilistic-Matrix-Factorization.git

The above figure illustrates use of Probabilistic Matrix Factorization to recommend similar set of users.

Flurs

Flurs library in Python supports online incremental updating (with update() method) of recommendation engines.

$ pip install flurs

FluRS supports incremental recommendation algorithms. Incremental algorithms became important with ever-growing feedback from incoming continuous, variable as well as unpredictable data streams.

• Incremental Collaborative Filtering

Most recommendation systems employ variations of Collaborative Filtering (CF) for formulating suggestions of items relevant to users’ interests. However, CF requires expensive computations that grow polynomially with the number of users and items in the database. The proposed methods suffer from handling scalability problem and speeding up recommendation formulation and accuracy results. This Incremental Collaborative Filtering (ICF) algorithm (i) addresses scalability problem, (ii) provides online recommendations (incremental updates of user-to-user similarities) of magnitude faster than classic CF.

• Incremental Matrix Factorization (MF)

This type of Incremental Matrix Factorization algorithm uses online learning with SGD (Stochastic Gradient Descent) to develop recommendation engines. Further, it supports online evaluation protocol (online monitoring) by taking into consideration positive-only feedback. Most commonly-used algorithms are UserKNN: Incremental user-based neighborhood, (W)BPRMF: (Weighted) Bayesian Personalized Ranking Matrix Factorization (BPR) and Iterative Stochastic Gradient Descent.

Python library for only Factorization Machines is fastFM.

pip install fastFM

and for BPR (https://github.com/gamboviol/bpr.git) with implicit and explicit feedback, recommendation engine library is lightFM.

pip install lightFM

• Incremental Matrix Factorization with BPR optimization

This collaborative method is based on BPR-Opt for personalized ranking (one individual ranking per user) that is the maximum posterior estimator derived from a Bayesian analysis of the problem. The learning method is based on stochastic gradient descent with bootstrap sampling. Research evaluations demonstrate that the task of personalized ranking, models learned by BPR outperform the same models that are optimized with respect to other criteria.

The Bayesian analysis uses a likelihood function for p(i >u j|Θ) and the prior probability for the model parameter p(Θ). The Bayesian formulation of finding the correct personalized ranking for all items i ∈ I is to maximize the following posterior probability where Θ represents the parameter vector of an arbitrary model class (e.g. matrix factorization).

p(Θ| >u) ∝ p(>u |Θ) p(Θ)

Here, >u represents latent preference structure for user u in a classical MF problem. All users are presumed to act independently of each other. Further, the assumption is based on the ordering of each pair of items (i, j) for a specific user is independent of the ordering of every other pair.

Some other matrix factorization models that somewhat resemble BPR optimization are Weighted Regularized Matrix Factorization (WR-MF) and Maximum Margin Matrix Factorization (MMMF).

WR-MF (available rsparse R package, mrec Python package) is a matrix factorization method for item prediction from implicit feedback, where the optimization is on instance level (one item), uses least-square method, known to correspond to the MLE for normally distributed random variables. Further, the weights in the error function are known to increase the impact of positive feedback.

$ pip install mrec

MMMF factorization algorithm is primarily designed for ordinal ranking or “collaborative prediction”, through low-norm factorizations: predicting unobserved entries of a target matrix Y, based on a subset S of observed entries Ys. It is designed for scenarios with explicit feedback in terms of ratings. Even though their ranking MMMF is not intended for implicit feedback datasets, it can be applied for such scenarios by giving all non-observed items the ‘rating’ 0 and the observed ones a 1. Its learning method is designed to work with sparse explicit data, i.e. they assume that there are many missing values and thus they assume to have much less pairs than in an implicit setting. But when the learning method is applied to implicit feedback datasets, the data has to be densified.

• Incremental Factorization Machines (FM)

In real-world applications such as e-commerce and online ad, a user’s activity is not frequent, and item properties change dynamically over time. In the context of item recommendation, such a scenario is referred to as persistent cold-start.

Factorization Machines (FMs) are alternative effective factorization models which enable context-aware recommendation with flexible feature representation. Such persistent cold-start problem are commonly present in scalable distributed real applications. Researchers are trying to evolve simple FMs to address aforesaid problems. However, the captured context by FMs is still static (as it’s not able to capture the relation between the input data and the change of target variable over time), and thus FM is incomplete in terms of robustness against persistently cold-starting data. Incremental update of FMs yields better accuracy compared to the static recommenders.

Incremental MF (iMF), an online extension of a MF-based item recommender is equipped with the following properties:

Generating suitable offers by recommending a top-N list to a user. During the course, the user interacts with an item (e.g. click, buy, rate) , and based on interactions the parameters are updated. It further provides ways to dynamically update parameters in order to improve the system:

• Positive-only feedback: Model update is fast through one-pass online learning scheme.
• Incremental adaptive regularization: Regularization parameters are automatically adjusted at runtime.

The learning procedure in FM requires a set of parameters Θ={w0,w,V} and a loss function ℓ(^y(x∣Θ),y), and the parameters can be optimized by SGD. Here, V∈R, d×k is a rank-k matrix which has v1,⋯,vd ∈Rk, x represents any arbitrary feature (e.g., concatenation of one-hot vectors for several categorical variables) and w∈ Rd.

The algorithm considers incremental adaptive regularization, there is a difficulty that the validation set S′ will be gradually outdated in a streaming environment. The issue is resolved by adding a newly observed sample (x, y) in the pseudo validation sample, so the regularization parameters are adjusted before updating Θ as demonstrated in the figure below:

Incremental Matrix Factorization(item recommender) is designed with a feature vector x, that makes it suitable for a scalable streaming environment.

• Step 1: The learning of parameters which involves estimating w0, w and V as the standard FMs
• Step 2: Prediction of estimates ^y(x∣Θ) for every items, and recommend N closest items to 1
• Step 3: λ-update → Θ-update with (x,1)

iFMs can update parameters in a millisecond range, and recommendation for a user takes at least 30 milliseconds. iFM thus seems to satisfy practical time requirements for now, but higher-dimensional and denser input vectors may lead to worse results in the future. As a result, Incremental Factorization Machines for Persistently Cold-starting Online Item Recommendation seem to achieve a trade-off between context-awareness and efficiency.

• Matrix Sketching

In order to handle hyper-parameter optimization and scalability, a completely different approach based on matrix sketching, which is more mathematically tractable and flexible, was introduced. It outperforms state-of-the-art personalized recommenders, iMF and iFMs.

First, most online item recommenders take a model-based approach which can be optimized by stochastic gradient descent, and they usually face the lack of effective ways to find proper hyper-parameters in an incremental fashion. To give an example of state-of-the-art incremental matrix factorization (iMF) and incremental factorization machines (iFMs), even with a derived optima in an initial batch training step, the best values may show poor compatibility with further unforeseen events. Hence, streaming algorithms with less, simpler hyper-parameters are preferable in reality.

Since modern recommenders stress “post-processing” such as generating explanation and incorporating into a hybrid recommender, the scores have to be easily interpretable. Incremental MF and FMs compute item scores by using heuristic function |1 − yˆ|, where yˆ is the predicted vector

For a set of users U and items I, recommendation and update can be done as:

• Algorithm 1: Recommending top-N items based on orthogonal projection and scoring, taking into consideration past user-item interaction.
• Algorithm 2: Recommending top-N items based on online user-item interaction, and updation of orthonormal bases.

The length of the orthogonal projection of a vector x′ui onto Ul (i.e. item score) represents how much the vector is similar to the past events, items which take smaller scores are more likely to be recommended. It is built on the top of the following algorithm(Source –https://www.groundai.com/project/incremental-factorization-machines-for-persistently-cold-starting-online-item-recommendation/)

• Building a recommender system to create a matrix X for the user-item pairs.
• Top-N recommendation is derived based on the orthogonal projection.
• If a user interacts with an item, Algorithm 2 constructs a vector x′ui and
• Dynamic Updation of orthonormal bases Ul by matrix sketching.

Randomized Matrix Decomposition

The method of randomized matrix factorization uses randomness to ease the computational load. Here the decomposition technique uses probabilistic algorithms in order to employ some amount of randomness. This helps to create a smaller matrix from a high-dimensional data matrix, which is then used to compute the desired low-rank approximation. Such algorithms are shown to be computationally efficient for approximating matrices with low-rank structure. The fundamental problem lies in approximately factorizing an arbitrary m × n matrix A as:

where l ≤ min(m, n) = mxn is the desired rank. The goal is to compute B and C such that A−BC is as small as possible, computed either through spectral norm or the largest singular value or norm 2.

$ git clone https://github.com/erichson/ristretto$ python setup.py install

Additional temporal params to Matrix Factorization

SVD in the collaborative filtering domain needs an essential factoring component that has often been the user-item rating matrix. This often raises difficulties as there are innumerable missing values caused by sparseness in the user-item ratings matrix. Conventional SVD faces extreme difficulty when information about the matrix is unavailable. Moreover, taking into consideration only few known entries is prone to over-fitting. Imputation mechanisms are used to fill in missing ratings and make the rating matrix dense, but can be very expensive as it significantly increases the amount of data.

It has been found that product perception and popularity constantly change and customers’ inclinations evolve, leading them to redefine their taste. Thus, the system is designed to take into consideration the temporal effects reflecting the dynamic, time-drifting nature of user-item interactions. The matrix factorization approach incorporates modeling temporal effects to improve accuracy significantly.

To account dynamic behavior, Netflix Prize Competition (taken from Netflix research publication) uses prediction rule in designing a recommendation model for defining a user-rating at time t. The bias (bui) involved in rating rui accounts for the user and item effects. The model accounts for this effect by taking the user factors (pu) as a function of time. The static item characteristics are specified by (qi). The entire user-item rating matrix can be expressed as a function of time with the following equation:

The accuracy of each of the factor models improves by increasing the number of involved parameters, which seems equivalent to increasing the factor model’s dimensionality. The model with the highest accuracy in addition to plain factorization includes biases, user profiles with implicit feedback, and two variants to express temporal components.

In addition, adding varying confidence levels by attaching weights, helps to identify the level of importance of observations and improve accuracy.

$ git clone https://github.com/williamFalcon/Matrix-Factorization-Recommender-Systems-Netflix-Paper-Implementation.gitpython setup.py install

Deep Matrix Factorization

• Comprises of a user-item matrix with explicit ratings and non-preference implicit feedback.
• The matrix is fed as input to a deep structure learning architecture to learn a common low dimensional space for the representations of users and items.
• Incorporates a new loss function based on binary cross entropy, which considers both explicit ratings and implicit feedback for a better optimization.

$ git clone https://github.com/RuidongZ/Deep_Matrix_Factorization_Models.gitpython Model.py [python = 3.5.3, tensorflow-gpu = 1.5.0, numpy = 1.14.0+mkl]

Conclusion

In this blog, the objective is to understand different matrix factorization techniques and become familiar with the associated Python libraries. In the next blog, let’s see how to run different use cases on the factorization models.