Skip to content

Latest commit

 

History

History
2417 lines (1821 loc) · 160 KB

Recommender System and Computational Advertising.md

File metadata and controls

2417 lines (1821 loc) · 160 KB

Recommender System

Recommender Systems (RSs) are software tools and techniques providing suggestions for items to be of use to a user. RSs are primarily directed towards individuals who lack sufficient personal experience or competence to evaluate the potentially overwhelming number of alternative items that a Web site, for example, may offer.

Xavier Amatriain discusses the traditional definition and its data mining core.

Traditional definition: The recommender system is to estimate a utility function that automatically predicts how a user will like an item.

User Interest is implicitly reflected in Interaction history, Demographics and Contexts, which can be regarded as a typical example of data mining. Recommender system should match a context to a collection of information objects. There are some methods called Deep Matching Models for Recommendation. It is an application of machine learning, which is in the representation + evaluation + optimization form. And we will focus on the representation and evaluation.

Evolution of the Recommender Problem:

  • Rating
  • Ranking
  • Page Optimization
  • Context-aware Recommendations
------------------
Collaborative Filtering (CF)
Content-Based Filtering (CBF)
Demographic Filtering (DF)
Knowledge-Based Filtering (KBF)
Hybrid Recommendation Systems

Evaluation of Recommendation System

The evaluation of machine learning algorithms depends on the tasks. The evaluation of recommendation system can be regarded as some machine learning models such as regression, classification and so on. We only take the mathematical convenience into consideration in the following methods. Gini index, covering rate and more realistic factors are not discussed in the following content.

Collaborative Filtering

There are 3 kinds of collaborative filtering: user-based, item-based and model-based collaborative filtering.

The user-based methods are based on the similarities of users. If user ${u}$ and ${v}$ are very similar friends, we may recommend the items which user ${u}$ bought to the user ${v}$ and explains it that your friends also bought it.

The item-based methods are based on the similarity of items. If one person added a brush to shopping-list, it is reasonable to recommend some toothpaste to him or her. And we can explain that you bought item $X$ and the people who bought $X$ also bought $Y$. And we focus on the model-based collaborative filtering.

Matrix Completion

Matrix completion is to complete the matrix $X$ with missing elements, such as

$$ \min_{Z} Rank(Z) \\ s.t. \sum_{(i,j):Observed}(Z_{(i,j)}-X_{(i,j)})^2\leq \delta $$

Note that the rank of a matrix is not easy or robust to compute.

We can apply customized PPA to matrix completion problem

$$ \min { {|Z|}{\ast}} \ s.t. Z{\Omega} = X_{\Omega} $$

We let ${Y}\in\mathbb{R}^{n\times n}$ be the the Lagrangian multiplier to the constraints $Z_{\Omega} = X_{\Omega}$ and Lagrange function is $$ L(Z,Y) = {|Z|}{\ast} - Y(Z{\Omega} - X_{\Omega}). $$

  1. Producing $Y^{k+1}$ by $$Y^{k+1}=\arg\max_{Y} {L([2Z^k-Z^{k-1}],Y)-\frac{s}{2}|Y-Y^k|};$$
  2. Producing $Z^{k+1}$ by $$Z^{k+1}=\arg\min_{Z} {L(Z,Y^{k+1}) + \frac{r}{2}|Z-Z^k|}.$$

Rahul Mazumder, Trevor Hastie, Robert Tibshirani reformulate it as the following:

$$ \min f_{\lambda}(Z)=\frac{1}{2}{|P_{\Omega}(Z-X)|}F^2 + \lambda {|Z|}{\ast} $$

where $X$ is the observed matrix, $P_{\Omega}$ is a projector and ${|\cdot|}_{\ast}$ is the nuclear norm of matrix.

Maximum Margin Matrix Factorization

A novel approach to collaborative prediction is presented, using low-norm instead of low-rank factorizations. The approach is inspired by, and has strong connections to, large-margin linear discrimination. We show how to learn low-norm factorizations by solving a semi-definite program, and present generalization error bounds based on analyzing the Rademacher complexity of low-norm factorizations.

Consider the soft-margin learning, where we minimize a trade-off between the trace norm of $Z$ and its hinge-loss relative to $X_O$: $$ \min_{Z} { | Z | }{\Omega} + c \sum{(ui)\in O}\max(0, 1 - Z_{ui}X_{ui}). $$

And it can be rewritten as a semi-definite optimization problem (SDP): $$ \min_{A, B} \frac{1}{2}(tr(A)+tr(B))+c\sum_{(ui)\in O}\xi_{ui}, \ s.t. , \begin{bmatrix} A & X \ X^T & B \ \end{bmatrix} \geq 0, Z_{ui}X_{ui}\geq 1- \xi_{ui}, \xi_{ui}>0 ,\forall ui\in O $$ where $c$ is a trade-off constant.

This technique is also called nonnegative matrix factorization.

$\color{red}{Note:}$ The data sets we more frequently encounter in collaborative prediction problem are of ordinal ratings $X_{ij} \in {1, 2, \dots, R}$ such as ${1, 2, 3, 4, 5}$. To relate the real-valued $Z_{ij}$ to the discrete $X_{ij}$. we use $R − 1$ thresholds $\theta_{1}, \dots, \theta_{R-1}$.

SVD and Beyond

If we have collected user ${u}$'s explicit evaluation score to the item ${i}$ , $R_{[u][i]}$, and all such data makes up a matrix $R=(R_{[u][i]})$ while the user $u$ cannot evaluate all the item so that the matrix is incomplete and missing much data. SVD is to factorize the matrix into the multiplication of matrices so that $$ \hat{R} = P^{T}Q. $$

And we can predict the score $R_{[u][i]}$ via $$ \hat{R}{[u][i]} = \hat{r}{u,i} = \left<P_u, Q_i\right> = \sum_f p_{u,f} q_{i,f} $$

where $P_u, Q_i$ is the ${u}$-th column of ${P}$ and the ${i}$-th column of ${Q}$, respectively. And we can define the cost function

$$ C(P,Q) = \sum_{(u,i):Observed}(r_{u,i}-\hat{r}{u,i})^{2}=\sum{(u,i):Observed}(r_{u,i}-\sum_f p_{u,f}q_{i,f})^{2}\ \arg\min_{P_u, Q_i} C(P, Q) $$

where $\lambda_u$ is always equal to $\lambda_i$.

Additionally, we can add regular term into the cost function to void over-fitting

$$ C(P,Q) = \sum_{(u,i):Observed}(r_{u,i}-\sum_f p_{u,f}q_{i,f})^{2}+\lambda_u|P_u|^2+\lambda_i|Q_i|^2. $$

It is called the regularized singular value decomposition or Regularized SVD.

Funk-SVD considers the user's preferences or bias. It predicts the scores by $$ \hat{r}{u,i} = \mu + b_u + b_i + \left< P_u, Q_i \right> $$ where $\mu, b_u, b_i$ is biased mean, biased user, biased item, respectively. And the cost function is defined as $$ \min\sum{(u,i): Observed}(r_{u,i} - \hat{r}_{u,i})^2 + \lambda (|P_u|^2+|Q_i|^2+|b_i|^2+|b_u|^2). $$

SVD ++ predicts the scores by

$$ \hat{r}{u,i} = \mu + b_u + b_i + (P_u + |N(u)|^{-0.5}\sum{i\in N(u)} y_i) Q_i^{T} $$ where $y_j$ is the implicit feedback of item ${j}$ and $N(u)$ is user ${u}$'s item set. And it can decompose into 3 parts:

  • $\mu + b_u + b_i$ is the base-line prediction;
  • $\left&lt;P_u, Q_i\right&gt;$ is the SVD of rating matrix;
  • $\left&lt;|N(u)|^{-0.5}\sum_{i\in N(u)} y_i, Q_i\right&gt;$ is the implicit feedback where $N(u)$ is user ${u}$'s item set, $y_j$ is the implicit feedback of item $j$.

We learn the values of involved parameters by minimizing the regularized squared error function.

Probabilistic Matrix Factorization

In linear regression, the least square methods is equivalent to maximum likelihood estimation of the error in standard normal distribution.

Regularized SVD
$C(P,Q) = \sum_{(u,i):Observed}(r_{(u,i)}-\sum_f p_{(u,f)} q_{(i,f)})^{2}+\lambda_u|P_u|^2+\lambda_i|Q_i|^2$
Probabilistic model
$r_{u,i}\sim N(\sum_f p_{(u,f)} q_{(i,f)},\sigma^2), P_u\sim N(0,\sigma_u^2 I), Q_i\sim N(0,\sigma_i^2 I)$

And $\sigma_u^2$ and $\sigma_i^2$ is related with the regular term $\lambda_u$ and $\lambda_u$.

So that we can reformulate the optimization problem as maximum likelihood estimation.

Poisson Factorization

We develop a Bayesian Poisson matrix factorization model for forming recommendations from sparse user behavior data. These data are large user/item matrices where each user has provided feedback on only a small subset of items, either explicitly (e.g., through star ratings) or implicitly (e.g., through views or purchases). In contrast to traditional matrix factorization approaches, Poisson factorization implicitly models each user's limited attention to consume items. Moreover, because of the mathematical form of the Poisson likelihood, the model needs only to explicitly consider the observed entries in the matrix, leading to both scalable computation and good predictive performance. We develop a variational inference algorithm for approximate posterior inference that scales up to massive data sets. This is an efficient algorithm that iterates over the observed entries and adjusts an approximate posterior over the user/item representations. We apply our method to large real-world user data containing users rating movies, users listening to songs, and users reading scientific papers. In all these settings, Bayesian Poisson factorization outperforms state-of-the-art matrix factorization methods.

Collaborative Less-is-More Filtering(CliMF)

Sometimes, the information of user we could collect is implicit such as the clicking at some item.

In CLiMF the model parameters are learned by directly maximizing the Mean Reciprocal Rank (MRR).

Its objective function is $$ F(U,V)=\sum_{i=1}^{M}\sum_{j=1}^{N} Y_{ij} [\ln g(U_{i}^{T}V_{j})+\sum_{k=1}^{N}\ln (1 - Y_{ij} g(U_{i}^{T}V_{k}-U_{i}^{T}V_{j}))] \-\frac{\lambda}{2}({|U|}^2 + {|V|}^2) $$

where ${M, N}$ is the number of users and items, respectively. Additionally, $\lambda$ denotes the regularization coefficient and $Y_{ij}$ denotes the binary relevance score of item ${j}$ to user ${i}$, i.e., $Y_{ij} = 1$ if item ${j}$ is relevant to user ${j}$, 0 otherwise. The function $g$ is logistic function $g(x)=\frac{1}{1+\exp(-x)}$. The vector $U_i$ denotes a d-dimensional latent factor vector for user ${i}$, and $V_j$ a d-dimensional latent factor vector for item ${i}$.

Numbers Factors Others
$M$ the number of users $U_i$ latent factor vector for user ${i}$ $Y_{ij}$ binary relevance score
$N$ the number of items $V_j$ latent factor vector for item ${i}$ $f$ logistic function

We use stochastic gradient ascent to maximize the objective function.

Matrix Factorization for Implicit Feedback

Another advantage of collaborative filtering or matrix completion is that even the element of matrix is binary or implicit information such as

Explicit and implicit feedback

WRMF is simply a modification of this loss function:

$$ {C(P,Q)}{WRMF} = \sum{(u,i):Observed}c_{u,i}(I_{u,i} - \sum_f p_{u,f}q_{i,f})^{2} + \underbrace{\lambda_u|P_u|^2 + \lambda_i|Q_i|^2}_{\text{regularization terms}}. $$

We make the assumption that if a user has interacted at all with an item, then $I_{u,i} = 1$. Otherwise, $I_{u,i} = 0$. If we take $d_{u,i}$ to be the number of times a user ${u}$ has clicked on an item ${i}$ on a website, then $$c_{u,i}=1+\alpha d_{u,i}$$ where $\alpha$ is some hyperparameter determined by cross validation. The new term in cost function $C=(c_{u,i})$ is called confidence matrix.

WRMF does not make the assumption that a user who has not interacted with an item does not like the item. WRMF does assume that that user has a negative preference towards that item, but we can choose how confident we are in that assumption through the confidence hyperparameter.

Alternating least square (ALS) can give an analytic solution to this optimization problem by setting the gradients equal to 0s.

Discrete Collaborative Filtering

Recommendation with Implicit Information

Inductive Matrix Completion

One possible improvement of this cost function is that we may design more appropriate loss function other than the squared error function.

utexas.edu

Inductive Matrix Completion (IMC) is an algorithm for recommender systems with side-information of users and items. The IMC formulation incorporates features associated with rows (users) and columns (items) in matrix completion, so that it enables predictions for users or items that were not seen during training, and for which only features are known but no dyadic information (such as ratings or linkages).

IMC assumes that the associations matrix is generated by applying feature vectors associated with its rows as well as columns to a low-rank matrix ${Z}$. The goal is to recover ${Z}$ using observations from ${P}$.

The inputs $x_i, y_j$ are feature vectors. The entry $P_{(i, j)}$ of the matrix is modeled as $P_{(i, j)}=x_i^T Z y_j$ and ${Z}$ is to recover in the form of $Z=WH^T$.

$$ \min \sum_{(i,j)\in \Omega}\ell(P_{(i,j)}, x_i^T W H^T y_j) + \frac{\lambda}{2}(| W |^2+| H |^2) $$ The loss function $\ell$ penalizes the deviation of estimated entries from the observations. And $\ell$ is diverse such as the squared error $\ell(a,b)=(a-b)^2$, the logistic error $\ell(a,b) = \log(1 + \exp(-ab))$.

More on Matrix Factorization

Beyond Matrix Completion

There are 2 common techniques in recommender systems:

  1. The goal of matrix factorization techniques in RS is to determine a low-rank approximation of the user-item rating matrix by decomposing it into a product of (user and item) matrices of lower dimensionality (latent factors).
  2. The idea of ensemble methods is to combine multiple alternative machine learning models to obtain more accurate predictions.

There are 2 disadvantages of Matrix Completion:

  1. $Postdiction \not= prediction$
    • Need initial post data
    • Predict poorly on a random set of items the user has not rated.
    • Repeated recommendation of purchased items
    • The evaluation method of Netflix Prize is misleading. RMSE(regression) vs Rank-based measures(sorting)
  2. Quality factors beyond accuracy
    • Introduce why we use the quality factors:
    • Novelty, diversity and unexpectedness(How to recommend new things to users exactly)
    • Depend on context and different problems
    • Interact with users: conversational recommender systems
    • Example of context and interaction:To Be Continued: Helping you find shows to continue watching on Netflix(search the “context”)
    • Manipulation resistance
    • Recommendation is optimal to sellers not users - transparency and explanation strategy (nearly a moral problem).

From Algorithms to Systems

Beyond the computer science perspective.

Putting the user back in the loop.

Toward a more comprehensive characterization of the recommendation task.

Collaborative filtering has become a key tool in recommender systems. The Netflix competition was instrumental in this context to further development of scalable tools. At its heart lies the minimization of the Root Mean Squares Error (RMSE) which helps to decide upon the quality of a recommender system. Moreover, minimizing the RMSE comes with desirable guarantees of statistical consistency. In this talk I make the case that RMSE minimization is a poor choice for a number of reasons: firstly, review scores are anything but Gaussian distributed, often exhibiting asymmetry and bimodality in their scores. Secondly, in a retrieval setting accuracy matters primarily for the top rated items. Finally, such ratings are highly context dependent and should only be considered in interaction with a user. I will show how this can be accomplished easily by relatively minor changes to existing systems.

Factorization Machines(FM)

The matrix completion used in recommender system are linear combination of some features such as regularized SVD and they only take the user-user interaction and item-item similarity. Factorization Machines(FM) is inspired from previous factorization models. It represents each feature an embedding vector, and models the second-order feature interactions: $$ \hat{y} = w_0 + \sum_{i=1}^{n} w_i x_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\left<v_i, v_j\right> x_i x_j\ = \underbrace{w_0 + \left<w, x\right>}{\text{First-order: Linear Regression}} + \underbrace{\sum{i=1}^{n-1}\sum_{j=i+1}^{n}\left<v_i, v_j\right> x_i x_j}_{\text{Second-order: pair-wise interactions between features}} $$

where the model parameters that have to be estimated are $$ w_0 \in \mathbb{R}, w\in\mathbb{R}^n, V\in\mathbb{R}^{n\times k}. $$

And $\left&lt;\cdot,\cdot\right&gt;$ is the dot (inner) product of two vectors so that $\left&lt;v_i, v_j\right&gt;=\sum_{f=1}^{k}v_{i,f} \cdot v_{j,f}$. A row $v_i$ within ${V}$ describes the ${i}$-th latent variable with ${k}$ factors for $x_i$.

And the linear regression $w_0 + \sum_{i=1}^{n} w_i x_i$ is called the first order part; the pair-wise interactions between features $\sum_{i=1}^{n}\sum_{j=i+1}^{n}\left&lt;v_i, v_j\right&gt; x_i x_j$ is called the second order part.

However, why we call it factorization machine? Where is the factorization? If ${[W]}{ij}=w{ij}= \left<v_i, v_j\right>$, $W=V V^T$, the second order part $\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\left&lt;v_i, v_j\right&gt; x_i x_j$ is equivalent to the following relationship: $$\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\left&lt;v_i, v_j\right&gt; x_i x_j=\frac{1}{2}x^TWx=\frac{1}{2}\sum_{i,j}w_{ij}x_i x_j$$ thus it is to factorize the matrix $W$ into the product of the $V$ and $V^T$.

In order to reduce the computation complexity, the second order part $\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\left&lt;v_i, v_j\right&gt; x_i x_j$ is rewritten in the following form $$\frac{1}{2}\sum_{l=1}^{k}{[\sum_{i=1}^{n}(v_{il}x_i))]^2-\sum_{i=1}^{n}(v_{il}x_i)^2}.$$ This show that we can use less resource to compute the model.

The next step is to find the optimal parameters of the model using the numerical optimization methods. Optimality of model parameters is usually defined with a loss function $\ell$ where the task is to minimize the sum of losses over the observed data $S={(x_i,y_i)}{i=1}^N$. $$\arg\min{\Theta}\sum_{(x_i,y_i)\in S}\ell(\hat{y}(x_i), x_i)$$

FMs model all interactions between variables using factorized parameters. Thus they are able to estimate interactions even in problems with huge sparsity (like recommender systems) where SVMs fail. It is shown that the model equation of FMs can be calculated in linear time and thus FMs can be optimized directly.

In Factorization Machines, the factorization machine models all nested variable interactions (comparable to a polynomial kernel in SVM), but uses a factorized parametrization instead of a dense parametrization like in SVMs.

And sparse factorization machines enforce group sparsity to remove the effect of a feature of user or a feature of item.

Polynomial networks and factorization machines are two recently-proposed models that can efficiently use feature interactions in classification and regression tasks. In this paper, we revisit both models from a unified perspective. Based on this new view, we study the properties of both models and propose new efficient training algorithms. Key to our approach is to cast parameter learning as a low-rank symmetric tensor estimation problem, which we solve by multi-convex optimization. We demonstrate our approach on regression and recommender system tasks.

Field-aware Factorization Machine(FFM)

In FMs, every feature has only one latent vector to learn the latent effect with any other features. In FFMs, each feature has several latent vectors. Depending on the field of other features, one of them is used to do the inner product. Mathematically, $$ \hat{y}=\sum_{j_1=1}^{n}\sum_{j_2=i+1}^{n}\left<v_{j_1,f_2}, v_{j_2,f_1}\right> x_{j_1} x_{j_2} $$ where $f_1$ and $f_2$ are respectively the fields of $j_1$ and $j_2$.

Convex Factorization Machines

Factorization machines are a generic framework which allows to mimic many factorization models simply by feature engineering. In this way, they combine the high predictive accuracy of factorization models with the flexibility of feature engineering. Unfortunately, factorization machines involve a non-convex optimization problem and are thus subject to bad local minima. In this paper, we propose a convex formulation of factorization machines based on the nuclear norm. Our formulation imposes fewer restrictions on the learned model and is thus more general than the original formulation. To solve the corresponding optimization problem, we present an efficient globally-convergent two-block coordinate descent algorithm. Empirically, we demonstrate that our approach achieves comparable or better predictive accuracy than the original factorization machines on 4 recommendation tasks and scales to datasets with 10 million samples.

And the objective function to optimize is the regularized empirical loss function or structured empirical loss function: $$\sum_{i}\ell(\hat{y}(x_i), y_i)+\frac{\alpha}{2}|w|2^2+\beta|Z|{\ast}$$ where $|Z|_{\ast}$ is the nuclear norm of the matrix $Z$.

Higher-Order Factorization Machines

In Factorization Machines, the d-way factorization machines are proposed in the following form: $$\hat{y}=w_0+\left&lt;x, w\right&gt;+\sum_{m=2}^d\sum_{n_1=1}^n\cdots\sum_{n_m}^n(\prod_{j=1}^{m}x_j)(\sum_{f}^k\prod_{j=1}^{m}v_{m_j,f}^{(m)}).$$ Unfortunately, despite increasing interest in FMs, there exists to date no efficient training algorithm for higher-order FMs (HOFMs).

The FM can be considered as the second order polynomial regression with lower computation complexity. And FM is also considered as the ANOVA kernel regression of degree 2. So we can generalize the FM into Higher-Order Factorization Machines (HOFM) based on ANOVA kernel.

Deep Learning for Recommender System

Deep learning is powerful in processing visual and text information so that it helps to find the interests of users such as Deep Interest Network, xDeepFM and more.

Deep learning models for recommender system may come from the restricted Boltzman machine. And deep learning models are powerful information extractors. Deep learning is really popular in recommender system such as spotlight.

What is the role deep learning plays in recommender system? At one hand, deep learning helps to match the user and items based on the history of their interactions such as deep matching and deep collaborative learning. In mathematics, it is a function that evaluates the how likely the user would interact with the items in some context: $f(X_U, X_I, X_C)$ where $X_U, X_I, X_C$ is the features of user, item and context, respectively. At another hand, deep learning leads a role as one representation methods to embedded high dimensional sparse data into semantics space.

Restricted Boltzmann Machines for Collaborative Filtering

Let ${V}$ be a $K\times m$ observed binary indicator matrix with $v_i^k = 1$ if the user rated item ${i}$ as ${k}$ and ${0}$ otherwise. We also let $h_j$, $j = 1, \dots, F,$ be the binary values of hidden (latent) variables, that can be thought of as representing stochastic binary features that have different values for different users.

We use a conditional multinomial distribution (a “softmax”) for modeling each column of the observed "visible" binary rating matrix ${V}$ and a conditional Bernoulli distribution for modeling "hidden" user features ${h}$: $$ p(v_i^k = 1 \mid h) = \frac{\exp(b_i^k + \sum_{j=1}^{F} h_j W_{i,j}^{k})}{\sum_{l=1}^{K}\exp( b_i^k + \sum_{j=1}^{F} h_j W_{i, j}^{l})} \ p( h_j = 1 \mid V) = \sigma(b_j + \sum_{i=1}^{m}\sum_{k=1}^{K} v_i^k W_{i,j}^k) $$ where $\sigma(x) = \frac{1}{1 + exp(-x)}$ is the logistic function, $W_{i,j}^{k}$ is is a symmetric interaction parameter between feature ${j}$ and rating ${k}$ of item ${i}$, $b_i^k$ is the bias of rating ${k}$ for item ${i}$, and $b_j$ is the bias of feature $j$.

The marginal distribution over the visible ratings ${V}$ is $$ p(V) = \sum_{h}\frac{\exp(-E(V,h))}{\sum_{V^{\prime},h^{\prime}} \exp(-E(V^{\prime},h^{\prime}))} $$ with an "energy" term given by:

$$ E(V,h) = -\sum_{i=1}^{m}\sum_{j=1}^{F}\sum_{k=1}^{K}W_{i,j}^{k} h_j v_i^k - \sum_{i=1}^{m}\sum_{k=1}^{K} v_i^k b_i^k -\sum_{j=1}^{F} h_j b_j. $$ The items with missing ratings do not make any contribution to the energy function

The parameter updates required to perform gradient ascent in the log-likelihood over the visible ratings ${V}$ can be obtained $$ \Delta W_{i,j}^{k} = \epsilon \frac{\partial\log(p(V))}{\partial W_{i,j}^{k}} $$ where $\epsilon$ is the learning rate. The authors put a Contrastive Divergence to approximate the gradient.

We can also model “hidden” user features $h$ as Gaussian latent variables: $$ p(v_i^k = 1 | h) = \frac{\exp(b_i^k+\sum_{j=1}^{F}h_j W_{i,j}^{k})}{\sum_{l=1}^{K}\exp(b_i^k+\sum_{j=1}^{F}h_j W_{i,j}^{l})} \ p( h_j = 1 | V) = \frac{1}{\sqrt{2\pi}\sigma_j} \exp(\frac{(h - b_j -\sigma_j \sum_{i=1}^{m}\sum_{k=1}^{K} v_i^k W_{i,j}^k)^2}{2\sigma_j^2}) $$ where $\sigma_j^2$ is the variance of the hidden unit ${j}$.

AutoRec for Collaborative Filtering

AutoRec is a novel autoencoder framework for collaborative filtering (CF). Empirically, AutoRec’s compact and efficiently trainable model outperforms state-of-the-art CF techniques (biased matrix factorization, RBMCF and LLORMA) on the Movielens and Netflix datasets.

Formally, the objective function for the Item-based AutoRec (I-AutoRec) model is, for regularization strength $\lambda &gt; 0$,

$$\min_{\theta}\sum_{i=1}^{n} {|r^{i}-h(r^{i}|\theta)|}_{O}^2 +\frac{1}{2}({|W|}_F^{2}+ {|V|}_F^{2})$$

where ${r^{i}\in\mathbb{R}^{d}, i=1,2,\dots,n}$ is partially observed vector and ${| \cdot |}_{o}^2$ means that we only consider the contribution of observed ratings. The function $h(r|\theta)$ is the reconstruction of input $r\in\mathbb{R}^{d}$:

$$h(r|\theta) = f(W\cdot g(Vr+\mu)+b)$$

for for activation functions $f, g$ as described in dimension reduction. Here $\theta = {W,V,r,b}$.

Deep crossing

Neural collaborative filtering

This model leverages the flexibility and non-linearity of neural networks to replace dot products of matrix factorization, aiming at enhancing the model expressiveness. In specific, this model is structured with two subnetworks including generalized matrix factorization (GMF) and MLP and models the interactions from two pathways instead of simple inner products. The outputs of these two networks are concatenated for the final prediction scores calculation. Unlike the rating prediction task in AutoRec, this model generates a ranked recommendation list to each user based on the implicit feedback. We will use the personalized ranking loss introduced in the last section to train this model.

Collaborative deep learning for RecSys

Collaborative filtering (CF) is a successful approach commonly used by many recommender systems. Conventional CF-based methods use the ratings given to items by users as the sole source of information for learning to make recommendation. However, the ratings are often very sparse in many applications, causing CF-based methods to degrade significantly in their recommendation performance. To address this sparsity problem, auxiliary information such as item content information may be utilized. Collaborative topic regression (CTR) is an appealing recent method taking this approach which tightly couples the two components that learn from two different sources of information. Nevertheless, the latent representation learned by CTR may not be very effective when the auxiliary information is very sparse. To address this problem, we generalize recently advances in deep learning from i.i.d. input to non-i.i.d. (CF-based) input and propose in this paper a hierarchical Bayesian model called collaborative deep learning (CDL), which jointly performs deep representation learning for the content information and collaborative filtering for the ratings (feedback) matrix. Extensive experiments on three real-world datasets from different domains show that CDL can significantly advance the state of the art.

Given part of the ratings in ${R}$ and the content information $X_c$, the problem is to predict the other ratings in ${R}$, where row ${j}$ of the content information matrix $X_c$ is the bag-of-words vector $Xc;j{\ast}$ for item ${j}$ based on a vocabulary of size ${S}$.

Stacked denoising autoencoders(SDAE) is a feedforward neural network for learning representations (encoding) of the input data by learning to predict the clean input itself in the output. Using the Bayesian SDAE as a component, the generative process of CDL is de fined as follows:

  1. For each layer ${l}$ of the SDAE network,

    • For each column ${n}$ of the weight matrix $W_l$, draw $$W_l;{\ast}n \sim \mathcal{N}(0,\lambda_w^{-1} I_{K_l}).$$
    • Draw the bias vector $$b_l \sim \mathcal{N}(0,\lambda_w^{-1} I_{K_l}).$$
    • For each row ${j}$ of $X_l$, draw $$X_{l;j\ast}\sim \mathcal{N}(\sigma(X_{l-1;j\ast}W_l b_l), \lambda_s^{-1} I_{K_l}).$$

  2. For each item ${j}$,

    • Draw a clean input $$X_{c;j\ast}\sim \mathcal{N}(X_{L, j\ast}, \lambda_n^{-1} I_{K_l}).$$
    • Draw a latent item offset vector $\epsilon_j \sim \mathcal{N}(0, \lambda_v^{-1} I_{K_l})$ and then set the latent item vector to be: $$v_j=\epsilon_j+X^T_{\frac{L}{2}, j\ast}.$$

  3. Draw a latent user vector for each user ${i}$: $$u_i \sim \mathcal{N}(0, \lambda_u^{-1} I_{K_l}).$$

  4. Draw a rating $R_{ij}$ for each user-item pair $(i; j)$: $$R_{ij}\sim \mathcal{N}(u_i^T v_j, C_{ij}^{-1}).$$

Here $\lambda_w, \lambda_s, \lambda_n, \lambda_u$and $\lambda_v$ are hyperparameters and $C_{ij}$ is a confidence parameter similar to that for CTR ($C_{ij} = a$ if $R_{ij} = 1$ and $C_{ij} = b$ otherwise).

And joint log-likelihood of these parameters is $$L=-\frac{\lambda_u}{2}\sum_{i} {|u_i|}2^2-\frac{\lambda_w}{2}\sum{l} [{|W_l|}F+{|b_l|}2^2]\ -\frac{\lambda_v}{2}\sum{j} {|v_j - X^T{\frac{L}{2},j\ast}|}2^2-\frac{\lambda_n}{2}\sum{l} {|X_{c;j\ast}-X_{L;j\ast}|}2^2 \ -\frac{\lambda_s}{2}\sum{l}\sum_{j} {|\sigma(X_{l-1;j\ast}W_l b_l)-X_{l;j}|}2^2 -\sum{ij} {|R_{ij}-u_i^Tv_j|}_2^2 $$

It is not easy to prove that it converges.

Wide & Deep Model

The output of this model is $$ P(Y=1|x) = \sigma(W_{wide}^T[x,\phi(x)] + W_{deep}^T \alpha^{(lf)}+b) $$ where the wide part deal with the categorical features such as user demographics and the deep part deal with continuous features.

Deep FM

DeepFM ensembles FM and DNN and to learn both second order and higher-order feature interactions: $$\hat{y}=\sigma(y_{FM} + y_{DNN})$$ where $\sigma$ is the sigmoid function so that $\hat{y}\in[0, 1]$ is the predicted CTR, $y_{FM}$ is the output of FM component, and $y_{DNN}$ is the output of deep component.

The FM component is a factorization machine and the output of FM is the summation of an Addition unit and a number of Inner Product units:

$$ \hat{y} = \left<w, x\right>+\sum_{j_1=1}^{n}\sum_{j_2=i+1}^{n}\left<v_i, v_j\right> x_{j_1} x_{j_2}. $$

The deep component is a feed-forward neural network, which is used to learn high-order feature interactions. There is a personal guess that the component function in activation function $e^x$ can expand in the polynomials form $e^x=1+x+\frac{x^2}{2!}+\dots,+\frac{x^n}{n!}+\dots$, which include all the order of interactions.

We would like to point out the two interesting features of this network structure:

  1. while the lengths of different input field vectors can be different, their embeddings are of the same size $(k)$;
  2. the latent feature vectors $(V)$ in FM now server as network weights which are learned and used to compress the input field vectors to the embedding vectors.

It is worth pointing out that FM component and deep component share the same feature embedding, which brings two important benefits:

  1. it learns both low- and high-order feature interactions from raw features;
  2. there is no need for expertise feature engineering of the input.

Neural Factorization Machines

$$ \hat{y} = w_0 + \left<w, x\right> + f(x) $$ where the first and second terms are the linear regression part similar to that for FM, which models global bias of data and weight of features. The third term $f(x)$ is the core component of NFM for modelling feature interactions, which is a multi-layered feedforward neural network.

B-Interaction Layer including Bi-Interaction Pooling is an innovation in artificial neural network.

Attentional Factorization Machines

Attentional Factorization Machine (AFM) learns the importance of each feature interaction from data via a neural attention network.

We employ the attention mechanism on feature interactions by performing a weighted sum on the interacted vectors:

$$\sum_{(i, j)} a_{(i, j)}(V_i \odot V_j) x_i x_j$$

where $a_{i, j}$ is the attention score for feature interaction.

xDeepFM

It mainly consists of 3 parts: Embedding Layer, Compressed Interaction Network(CIN) and DNN.

RepeatNet

Deep Matrix Factorization

Matrix Factorization is a widely used collaborative filtering method in recommender systems. However, most of them are under the assumption that the rating data is missing at random (MAR), which may not be very common. For some users, they may only rate those movies they like, so the inferences will be biased in previous models. In this paper, we proposed a deep matrix factorization method based on missing not at random (MNAR) assumption. As far as we know, this model firstly uses deep learning method to address MNAR issue. The model consists of a complete data model (CDM) and a missing data model (MDM), which are both learned by neural networks. The CDM is nonlinearly determined by two factors, the user latent features and item latent features like other matrix factorization methods. And the MDM also use these two factors but taking the rating value as extra information while training. We used variational Bayesian inference to generate the posterior distribution of our proposed model. Through extensive experiments on different kind of datasets, our proposed model produce gains in some widely used metrics, comparing with several state-of-the-art models. We also explore the performance of our model within different experimental settings.

Deep Matching Models for Recommendation

It is essential for the recommender system to find the item which matches the users' demand. Its difference from web search is that recommender system provides item information even if the users' demands or generally interests are not provided. It sounds like modern crystal ball to read your mind.

In A Multi-View Deep Learning Approach for Cross Domain User Modeling in Recommendation Systems the authors propose to extract rich features from user’s browsing and search histories to model user’s interests. The underlying assumption is that, users’ historical online activities reflect a lot about user’s background and preference, and therefore provide a precise insight of what items and topics users might be interested in.

Its training data set and the test data is ${(\mathrm{X}i, y_i, r_i)\mid i =1, 2, \cdots, n}$ and $(\mathrm{X}{n+1}, y_{n+1})$, respectively. Matching Model is trained using the training data set: a class of `matching functions’ $\mathcal F= {f(x, y)}$ is defined, while the value of the function $r(\mathrm{X}, y)\in \mathcal F$ is a real number a set of numbers $R$ and the $r_{n+1}$ is predicted as $r_{n+1} = r(\mathrm{X}{n+1}, y{n+1})$.

The data is assumed to be generated according to the distributions $(x, y) \sim P(X,Y)$, $r \sim P(R \mid X,Y)$ . The goal of the learning task is to select a matching function $f (x, y)$ from the class $F$ based on the observation of the training data. The learning task, then, becomes the following optimization problem. $$\arg\min_{r\in \mathcal F}\sum_{i=1}^{n}L(r_i, r(x_i, y_i))+\Omega(r)$$ where $L(\cdot, \cdot)$ denotes a loss function and $\Omega(\cdot)$ denotes regularization.

In fact, the inputs x and y can be instances (IDs), feature vectors, and structured objects, and thus the task can be carried out at instance level, feature level, and structure level.

And $r(x, y)$ is supposed to be non-negative in some cases.

Framework of Matching
Output: MLP
Aggregation: Pooling, Concatenation
Interaction: Matrix, Tensor
Representation: MLP, CNN, LSTM
Input: ID Vectors $\mathrm{X}$, Feature Vectors $y$

Sometimes, matching model and ranking model are combined and trained together with pairwise loss. Deep Matching models takes the ID vectors and features together as the input to a deep neural network to train the matching scores including Deep Matrix Factorization, AutoRec, Collaborative Denoising Auto-Encoder, Deep User and Image Feature, Attentive Collaborative Filtering, Collaborative Knowledge Base Embedding.

semantic-based matching models

Embedding methods for RecSys

Hyperbolic Recommender Systems

Many well-established recommender systems are based on representation learning in Euclidean space. In these models, matching functions such as the Euclidean distance or inner product are typically used for computing similarity scores between user and item embeddings. Hyperbolic Recommender Systems investigate the notion of learning user and item representations in hyperbolic space.

Given a user ${u}$ and an item ${v}$ that are both lying in the Poincare ball $B^n$, the distance between two points on P is given by $$d_p(x, y)=cosh^{-1}(1+2\frac{|(x-y|^2}{(1-|x|^2)(1-|y|^2)}).$$

Hyperbolic Bayesian Personalized Ranking(HyperBPR) leverages BPR pairwise learning to minimize the pairwise ranking loss between the positive and negative items. Given a user ${u}$ and an item ${v}$ that are both lying in Poincare ball $B^n$, we take: $$\alpha(u, v) = f(d_p(u, v))$$ where $f(\cdot)$ is simply preferred as a linear function $f(x) = \beta x + c$ with $\beta\in\mathbb{R}$ and $c\in\mathbb{R}$ are scalar parameters and learned along with the network. The objective function is defined as follows: $$\arg\min_{\Theta} \sum_{i, j, k} -\ln(\sigma{\alpha(u_i, v_j) - \alpha(u_i, v_k)}) + \lambda {|\Theta|}_2^2$$

where $(i, j, k)$ is the triplet that belongs to the set ${D}$ that contains all pairs of positive and negative items for each user; $\sigma$ is the logistic sigmoid function; $\Theta$ represents the model parameters; and $\lambda$ is the regularization parameter.

The parameters of our model are learned by using RSGD.

Prod2Vec

Product embedding

  • Based on item-item co-occurrence from transaction sequences co-purhased products)
  • Uses method of word embedding: low-dimensional, distributed embeddings of words based on word sequences in text documents

Item2vec

Meta-Prod2Vec

Meta-Prod2ve is a novel method to compute item similarities for recommendation that leverages existing item metadata.

Graph Embeddings for RecSys

proNet

Modularize Graph Embedding for Recommendation

We can take the recommendation as Link Prediction on Graphs.

  1. Efficient retrieval from approximate nearest neighbor (ANN) search methods.
  2. Efficient pairwise comparison due to dimensionality reduction (DR)
  3. Reduced space complexity due to DR
  4. Transfer learning with pertained embeddings

So graph embedding is GREAT for recommendation :

  • Reduces data sparsity and cold start via integrating auxiliary information
  • Provides holistic view of REC problem and jointly mines different relations in terms of graph structures
  • Trains fast, compares fast, and retrieves fast while taking less space

In order to address the challenges of the graph embedding, we need modularize graph embedding for adaptability.

  • Extracts graph structures from dataset while remains type-agnostic to sampled entities, i.e., nodes & edges
  • Converts entities into spatial features via embedding stacking operations, e.g, lookup, pooling (average, etc.)
  • Preserves entity relatedness as spatial properties with customizable similarity metrics and loss functions

Graph-based RecSys

Graph is an important structure for System II intelligence, with the universal representation ability to capture the relationship between different variables, and support interpretability, causality, and transferability / inductive generalization. Traditional logic and symbolic reasoning over graphs has relied on methods and tools which are very different from deep learning models, such Prolog language, SMT solvers, constrained optimization and discrete algorithms. Is such a methodology separation between System I and System II intelligence necessary? How to build a flexible, effective and efficient bridge to smoothly connect these two systems, and create higher order artificial intelligence?

Graph neural networks, have emerged as the tool of choice for graph representation learning, which has led to impressive progress in many classification and regression problems such as chemical synthesis, 3D-vision, recommender systems and social network analysis. However, prediction and classification tasks can be very different from logic/symbolic reasoning.

In this tutorial, we revisit the recommendation problem from the perspective of graph learning. Common data sources for recommendation can be organized into graphs, such as user-item interactions (bipartite graphs), social networks, item knowledge graphs (heterogeneous graphs), among others. Such a graph-based organization connects the isolated data instances, bringing benefits for exploiting high-order connectivities that encode meaningful patterns for collaborative filtering, content-based filtering, social influence modeling and knowledge-aware reasoning. Together with the recent success of graph neural networks (GNNs), graph-based models have exhibited the potential to be the technologies for next generation recommendation systems. The tutorial provides a review on graph-based learning methods for recommendation, with special focus on recent developments of GNNs and knowledge graph-enhanced recommendation. By introducing this emerging and promising area in the tutorial, we expect the audience can get deep understanding and accurate insight on the spaces, stimulate more ideas and discussions, and promote developments of technologies.

Deep Geometric Matrix Completion

It’s easy to observe how better matrix completions can be achieved by considering the sparse matrix as defined over two different graphs: a user graph and an item graph. From a signal processing point of view, the matrix ${X}$ can be considered as a bi-dimensional signal defined over two distinct domains. Instead of recurring to multigraph convolutions realized over the entire matrix ${X}$, two independent single-graph GCNs (graph convolution networks) can be applied on matrices ${W}$ and ${H}$.

Given the aforementioned multi-graph convolutional layers, the last step that remains concerns the choice of the architecture to use for reconstructing the missing information. Every (user, item) pair in the multi-graph approach and every user/item in the separable one present in this case an independent state, which is updated (at every step) by means of the features produced by the selected GCN.

PinSage

Spectral Collaborative Filtering

LightGCN

GraphRec

Feature Interaction Selection in RecSys

A feature interaction is some way in which a feature or features modify or influence another feature in defining overall system behavior.

Generally, feature interactions matter in recommender system.

Attribute interactions are the irreducible dependencies between attributes. Interactions underlie feature relevance and selection, the structure of joint probability and classification models: if and only if the attributes interact, they should be connected. While the issue of 2-way interactions, especially of those between an attribute and the label, has already been addressed, we introduce an operational definition of a generalized n-way interaction by highlighting two models: the reductionistic part-to-whole approximation, where the model of the whole is reconstructed from models of the parts, and the holistic reference model, where the whole is modelled directly. An interaction is deemed significant if these two models are significantly different. Correlation is a special case of attribute interaction.

AutoCross

By performing beam search in a tree-structured space, AutoCross enables efficient generation of high-order cross features, which is not yet visited by existing works.

Product-based Neural Network

Facing with the extreme sparsity, traditional models may limit their capacity of mining shallow patterns from the data, i.e. low-order feature combinations. Deep models like deep neural networks, on the other hand, cannot be directly applied for the high-dimensional input because of the huge feature space.

Deep Crossing

The Deep Crossing model is a deep neural network that automatically combines features to produce superior models. The input of Deep Crossing is a set of individual features that can be either dense or sparse. The important crossing features are discovered implicitly by the networks, which are comprised of an embedding and stacking layer, as well as a cascade of Residual Units.

AutoGroup

AutoGroup casts the selection of feature interactions as a structural optimization problem. In a nutshell, AutoGroup first automatically groups useful features into a number of feature sets. Then, it generates interactions of any order from these feature sets using a novel interaction function. The main contribution of AutoGroup is that it performs both dimensionality reduction and feature selection which are not seen in previous models.

AutoFIS

AutoFIS can automatically identify important feature interactions for factorization models with computational cost just equivalent to training the target model to convergence. In the $\color{red}\text{search stage}$, instead of searching over a discrete set of candidate feature interactions, we relax the choices to be continuous by introducing the architecture parameters

AutoFeature

$\mathrm{AutoInt}$ to automatically learn the high-order feature interactions of input features. Our proposed algorithm is very general, which can be applied to both numerical and categorical input features. Specifically, we map both the numerical and categorical features into the same low-dimensional space. Afterwards, a multi-head self-attentive neural network with residual connections is proposed to explicitly model the feature interactions in the low-dimensional space. With different layers of the multi-head self-attentive neural networks, different orders of feature combinations of input features can be modeled.

Automated Embedding

AutoEmb can enable various embedding dimensions according to the popularity in an automated and dynamic manner.

Ensemble Methods for Recommender System

The RecSys can be considered as some regression or classification tasks, so that we can apply the ensemble methods to these methods as BellKor's Progamatic Chaos used the blended solution to win the prize. In fact, its essence is bagging or blending, which is one sequential ensemble strategy in order to avoid over-fitting or reduce the variance.

In this section, the boosting is the focus, which is to reduce the error and boost the performance from a weaker learner.

There are two common methods to construct a stronger learner from a weaker learner: (1) reweight the samples and learn from the error: AdaBoosting; (2) retrain another learner and learn to approximate the error: Gradient Boosting.

BellKor's Progamatic Chaos

Until now, we consider the recommendation task as a regression prediction process, which is really common in machine learning. The boosting or stacking methods may help us to enhance these methods.

A key to achieving highly competitive results on the Netflix data is usage of sophisticated blending schemes, which combine the multiple individual predictors into a single final solution. This significant component was managed by our colleagues at the Big Chaos team. Still, we were producing a few blended solutions, which were later incorporated as individual predictors in the final blend. Our blending techniques were applied to three distinct sets of predictors. First is a set of 454 predictors, which represent all predictors of the BellKor’s Pragmatic Chaos team for which we have matching Probe and Qualifying results. Second, is a set of 75 predictors, which the BigChaos team picked out of the 454 predictors by forward selection. Finally, a set of 24 BellKor predictors for which we had matching Probe and Qualifying results. from Netflix Prize.

BoostFM

BoostFM integrates boosting into factorization models during the process of item ranking. Specifically, BoostFM is an adaptive boosting framework that linearly combines multiple homogeneous component recommender system, which are repeatedly constructed on the basis of the individual FM model by a re-weighting scheme.

BoostFM

  • Input: The observed context-item interactions or Training Data $S ={(\mathbf{x}_i, y_i)}$ parameters E and T.
  • Output: The strong recommender $g^{T}$.
  • Initialize $Q_{ci}^{(t)}=1/|S|,g^{(0)}=0, \forall (c, i)\in S$.
  • for $t = 1 \to T$ do
      1. Create component recommender $\hat{y}^{(t)}$ with $\bf{Q}^{(t)}$ on $\bf S$,$\forall (c,i) \in \bf S$, , i.e., Component Recommender Learning Algorithm;
      1. Compute the ranking accuracy $E[\hat{r}(c, i, y^{(t)})], \forall (c,i) \in \bf S$;
      1. Compute the coefficient $\beta_t$, $$ \beta_t = \ln (\frac{\sum_{(c,i) \in \bf S} \bf{Q}^{(t)}{ci}{1 + E[\hat{r}(c, i, y^{(t)})]}}{\sum{(c,i) \in \bf S} \bf{Q}^{(t)}_{ci}{1- E[\hat{r}(c, i, y^{(t)})]}})^{\frac{1}{2}} ; $$
      1. Create the strong recommender $g^{(t)}$, $$ g^{(t)} = \sum_{h=1}^{t} \beta_h \hat{y}^{(t)} ;$$
      1. Update weight distribution (\bf{Q}^{t+1}), $$ \bf{Q}^{t+1}{ci} = \frac{\exp(E[\hat{r}(c, i, y^{(t)})])}{\sum{(c,i)\in \bf{S}} E[\hat{r}(c, i, y^{(t)})]} ; $$
  • end for

Component Recommender

Naturally, it is feasible to exploit the L2R techniques to optimize Factorization Machines (FM). There are two major approaches in the field of L2R, namely, pairwise and listwise approaches. In the following, we demonstrate ranking factorization machines with both pairwise and listwise optimization.

Weighted Pairwise FM (WPFM)

Weighted ‘Listwise’ FM (WLFM)

Adaptive Boosting Personalized Ranking (AdaBPR)

AdaBPR (Adaptive Boosting Personalized Ranking) is a boosting algorithm for top-N item recommendation using users' implicit feedback. In this framework, multiple homogeneous component recommenders are linearly combined to achieve more accurate recommendation. The component recommenders are learned based on a re-weighting strategy that assigns a dynamic weight to each observed user-item interaction.

Here explicit feedback refers to users' ratings to items while implicit feedback is derived from users' interactions with items, e.g., number of times a user plays a song.

The primary idea of applying boosting for item recommendation is to learn a set of homogeneous component recommenders and then create an ensemble of the component recommenders to predict users' preferences.

Here, we use a linear combination of component recommenders as the final recommendation model $$f=\sum_{t=1}^{T}{\alpha}t f{t}.$$

In the training process, AdaBPR runs for ${T}$ rounds, and the component recommender $f_t$ is created at t-th round by $$ \arg\min_{f_t\in\mathbb{H}} \sum_{(u,i)\in\mathbb{O}} {\beta}{u} \exp{-E(\pi(u,i,\sum{n=1}^{t}{\alpha}n f{n}))}. $$

where the notations are listed as follows:

  • $\mathbb{H}$ is the set of possible component recommenders such as collaborative ranking algorithms;
  • $E(\pi(u,i,f))$ denotes the ranking accuracy associated with each observed interaction pair;
  • $\pi(u,i,f)$ is the rank position of item ${i}$ in the ranked item list of ${u}$, resulted by a learned ranking model ${f}$;
  • $\mathbb{O}$ is the set of all observed user-item interactions;
  • ${\beta}{u}$ is defined as reciprocal of the number of user $u$'s historical items ${\beta}{u}=\frac{1}{|V_{u}^{+}|}$ ($V_{u}^{+}$ is the historical items of ${u}$).

Gradient Boosting Factorization Machines

Gradient Boosting Factorization Machine (GBFM) model is to incorporate feature selection algorithm with Factorization Machines into a unified framework.

Gradient Boosting Factorization Machine Model

  • Input: Training Data $S ={(\mathbf{x}_i, y_i)}$.
  • Output: $\hat{y}S =y_0(x) + {\sum}^S{s=1}\left<v_{si}, v_{sj}\right>$.
  • Initialize rating prediction function as $\hat{y}_0(x)$
  • for $s = 1 \to S$ do
    1. Select interaction feature $C_p$ and $C_q$ from Greedy Feature Selection Algorithm;
    1. Estimate latent feature matrices $V_p$ and $V_q$;
    1. Update $\hat{y}s(\mathrm{x}) = \hat{y}{s-1}(\mathrm{x}) + {\sum}{i\in C_p}{\sum}{j\in C_q} \mathbb{I}[i,j\in \mathrm{x}]\left<V_{p}^{i}, V_{q}^{j}\right>$
  • end for

where s is the iteration step of the learning algorithm. At step s, we greedily select two interaction features $C_p$ and $C_q$ where $\mathbb{I}$ is the indicator function, the value is 1 if the condition holds otherwise 0.

Greedy Feature Selection Algorithm

From the view of gradient boosting machine, at each step s, we would like to search a function ${f}$ in the function space ${F}$ that minimize the objective function: $$L=\sum_{i}\ell(\hat{y}_s(\mathrm{x}_i), y_i)+\Omega(f)$$

where $\hat{y}s(\mathrm{x}) = \hat{y}{s−1}(\mathrm{x}) + \alpha_s f_s(\mathrm{x})$.

We heuristically assume that the function ${f}$ has the following form: $$ f_{\ell}(\mathrm{x})={\prod}{t=1}^{\ell} q{C_{i}(t)}(\mathrm{x}) $$ where the function q maps latent feature vector x to real value domain $$ q_{C_{i}(t)}(\mathrm{x})=\sum_{j\in C_{i}(t)}\mathbb{I}[j\in \mathrm{x}]w_{t} $$

It is hard for a general convex loss function $\ell$ to search function ${f}$ to optimize the objective function: $L=\sum_{i}\ell(\hat{y}_s(\mathrm{x}_i), y_i)+\Omega(f)$.

The most common way is to approximate it by least-square minimization, i.e., $\ell={| \cdot |}_2^2$. Like in xGBoost, it takes second order Taylor expansion of the loss function $\ell$ and problem isfinalized to find the ${i}$(t)-th feature which:

$$\arg{\min}{i(t)\in {0, \dots, m}} \sum{i=1}^{n} h_i(\frac{g_i}{h_i}-f_{t-1}(\mathrm{x}i) q{C_{i}(t)}(\mathrm{x}_i))^2 + {|\theta|}_2^2 $$ where the negativefirst derivative and the second derivative at instance ${i}$ as $g_i$ and $h_i$.

Gradient Boosted Categorical Embedding and Numerical Trees

Gradient Boosted Categorical Embedding and Numerical Trees (GB-CSENT) is to combine Tree-based Models and Matrix-based Embedding Models in order to handle numerical features and large-cardinality categorical features. A prediction is based on:

  • Bias terms from each categorical feature.
  • Dot-product of embedding features of two categorical features,e.g., user-side v.s. item-side.
  • Per-categorical decision trees based on numerical features ensemble of numerical decision trees where each tree is based on one categorical feature.

In details, it is as following: $$ \hat{y}(x) = \underbrace{\underbrace{\sum_{i=0}^{k} w_{a_i}}{bias} + \underbrace{(\sum{a_i\in U(a)} Q_{a_i})^{T}(\sum_{a_i\in I(a)} Q_{a_i}) }{factors}}{CAT-E} + \underbrace{\sum_{i=0}^{k} T_{a_i}(b)}_{CAT-NT}. $$ And it is decomposed as the following table.

Ingredients Formulae Features
Factorization Machines $\underbrace{\underbrace{\sum_{i=0}^{k} w_{a_i}}{bias} + \underbrace{(\sum{a_i\in U(a)} Q_{a_i})^{T}(\sum_{a_i\in I(a)} Q_{a_i}) }{factors}}{CAT-E}$ Categorical Features
GBDT $\underbrace{\sum_{i=0}^{k} T_{a_i}(b)}_{CAT-NT}$ Numerical Features

Deep Embedding Networks and Gradient Boosting Decision Trees

Tree-based Deep Model for Recommender Systems

By indexing items in a tree hierarchy and training a user-node preference prediction model satisfying a max-heap like property in the tree, TDM provides logarithmic computational complexity w.r.t. the corpus size, enabling the use of arbitrary advanced models in candidate retrieval and recommendation.

Our purpose, in this paper, is to develop a method to jointly learn the index structure and user preference prediction model.

Recommendation problem is basically to retrieve a set of most relevant or preferred items for each user request from the entire corpus. In the practice of large-scale recommendation, the algorithm design should strike a balance between accuracy and efficiency.

The above methods include 2 stages/models: (1) find the preference of the users based on history or other information; (2) retrive some items according to the predicted preferences.

TDM uses a tree hierarchy to organize items, and each leaf node in the tree corresponds to an item. Like a max-heap, TDM assumes that each user-node preference is the largest one among the node’s all children’s preferences. The main idea is to predict user interests from coarse to fine by traversing tree nodes in a top-down fashion and making decisions for each user-node pair.

Each item in the corpus is firstly assigned to a leaf node of a tree hierarchy $\mathcal{T}$. The non-leaf nodes can be seen as a coarser abstraction of their children. In retrieval, the user information combined with the node to score is firstly vectorized to a user preference representation as the input of a deep neural network $\mathcal{M}$ (e.g. fully connected networks). While retrieving for the top-k items (leaf nodes), a top-down beam search strategy is carried out level by level.

TDM uses a tree as index and creatively proposes a max-heap like probability formulation on the tree, where the user preference for each non-leaf node $n$ in level $l$ is derived as: $$p^{(l)}(u \mid n)=\frac{\max_{n_c\in{\text{the children of the node $n$ in the $l+1$ level}}} p^{(l)}(n_c \mid u)}{\alpha^{(l)}}$$

where $p^{(l)}(u \mid n)$ is the ground truth probability that the user $u$ prefers the node $n$. The above formulation means that the ground truth user-node probability on a node equals to the maximum user-node probability of its children divided by a normalization term. Therefore, the top-k nodes in level $l$ must be contained in the children of top-k nodes in level $l −1$ and the retrieval for top-k leaf items can be restricted to top-k nodes in each layer without losing the accuracy. Based on this, TDM turns the recommendation task into a hierarchical retrieval problem. By a top-down retrieval process, the candidate items are selected gradually from coarse to detailed.

According to the retrieval process, the recommendation accuracy of TDM is determined by the quality of the user preference model $\mathcal M$ and tree index $\mathcal T$. Given n pairs of positive training data $(u_i, c_i)$, which means the user $u_i$ is interested in the target item $c_i$, $\mathcal T$ determines which non-leaf nodes $\mathcal M$ should select to achieve $c_i$ for $u_i$.

Denote $p (\pi(c_i)|u_i; \pi)$ as user u’s preference probability over leaf node $\pi(c_i)$ given a user-item pair $(u_i, c_i)$, where $\pi(·)$ is a projection function that projects an item to a leaf node in $\mathcal T$. Note that the projection function $\pi(\cdot)$ actually determines the item hierarchy in the tree. The model $\mathcal M$ is used to estimate and output the user-node preference $\hat{p} (\pi(c_i)|u_i;\theta \pi)$ given $\theta$ as model parameters. If the pair $(u_i , c_i)$ is a positive sample, we have the ground truth preference $p (\pi(c_i)|u_i; \pi)=1$. According to the max-heap property, the user preference probability of all $π(c_i)$’s ancestor nodes, i.e., ${p(b_j (\pi(c_i))|u_i; \pi)}^{l_{max}}{j=0}$ should also be 1, in which $b_j(\cdot)$ is the projection from a node to its ancestor node in level $j$ and $l{max}$ is the max level in $\mathcal T$. To fit such a user-node preference distribution, the global loss function is formulated as

$$L(\theta, \mathcal T)= -\sum_{i=1}^n \sum_{j=1}^{l_{max}}\log(\hat{p}(b_j (\pi(c_i))|u_i; \pi) )$$

where we sum up the negative logarithm of predicted user-node preference probability on all the positive training samples and their ancestor user-node pairs as the global empirical loss.

The core of TDM is to regard the recommendation as ranking.

Context-aware Recommendations

Context-aware information is widely available in various ways and is becoming more and more important for enhancing retrieval performance and recommendation results. The current main issue to cope with is not only recommending or retrieving the most relevant items and content, but defining them ad hoc. Further relevant issues are personalizing and adapting the information and the way it is displayed to the user’s current situation and interests.

Context-Aware Factorization Machines

Sequential Recommender Systems

Top-N recommendation

Explainable Recommendations

Explainable recommendation and search attempt to develop models or methods that not only generate high-quality recommendation or search results, but also intuitive explanations of the results for users or system designers, which can help improve the system transparency, persuasiveness, trustworthiness, and effectiveness, etc.

Providing personalized explanations for recommendations can help users to understand the underlying insight of the recommendation results, which is helpful to the effectiveness, transparency, persuasiveness and trustworthiness of recommender systems. Current explainable recommendation models mostly generate textual explanations based on pre-defined sentence templates. However, the expressiveness power of template-based explanation sentences are limited to the pre-defined expressions, and manually defining the expressions require significant human efforts

Social Recommendation

We present a novel framework for studying recommendation algorithms in terms of the ‘jumps’ that they make to connect people to artifacts. This approach emphasizes reachability via an algorithm within the implicit graph structure underlying a recommender dataset and allows us to consider questions relating algorithmic parameters to properties of the datasets.

Social Recommender Systems (SRSs) aim to alleviate information overload over social media users by presenting the most attractive and relevant content, often using personalization techniques adapted for the specific user. SRSs also aim at increasing adoption, engagement, and participation of new and existing users of social media sites. In addition to recommending content to consume, new types of recommendations emerge within social media, such as of people and communities to connect to, to follow, or to join.

User-item/user-user interactions are usually in the form of graph/network structure. What is more, the graph is dynamic, and we need to apply to new nodes without model retraining.

SocialMF: MF with social trust propagation

Based on the assumption of trust aware recommender

  • users have similar tastes with other users they trust
  • the transitivity of trust and propagate trust to indirect neighbors in the social network.

Algorithmic Bias in Search and Recommendation

Both search and recommendation algorithms provide results based on their relevance for the current user. In order to do so, such a relevance is usually computed by models trained on historical data, which is biased in most cases. Hence, the results produced by these algorithms naturally propagate, and frequently reinforce, biases hidden in the data, consequently strengthening inequalities. Being able to measure, characterize, and mitigate these biases while keeping high effectiveness is a topic of central interest for the information retrieval community.

Knowledge Graph and Recommender System

Items usually correspond to entities in many fields, such as books, movies and music, making it possible for transferring information between them. These information involving in recommender system and knowledge graph are complementary revealing the connectivity among items or between users and items. In terms of models, the two tasks are both to rank candidates for a target according to either implicit or explicit relations. For example, KG completion is to find correct movies (e.g., Death Becomes Her) for the person Robert Zemeckis given the explicit relation is Director Of. Item recommendation aims at recommending movies for a target user satisfying some implicit preference. Therefore, we are to fill in the gap between item recommendation and KG completion via a joint model, and systematically investigate how the two tasks impact each other.

RippleNet

Reinforcement Learning and Recommender System

Services that introduce stores to users on the Internet are increasing in recent years. Each service conducts thorough analyses in order to display stores matching each user's preferences. In the field of recommendation, collaborative filtering performs well when there is sufficient click information from users. Generally, when building a user-item matrix, data sparseness becomes a problem. It is especially difficult to handle new users. When sufficient data cannot be obtained, a multi-armed bandit algorithm is applied. Bandit algorithms advance learning by testing each of a variety of options sufficiently and obtaining rewards (i.e. feedback). It is practically impossible to learn everything when the number of items to be learned periodically increases. The problem of having to collect sufficient data for a new user of a service is the same as the problem that collaborative filtering faces. In order to solve this problem, we propose a recommender system based on deep reinforcement learning. In deep reinforcement learning, a multilayer neural network is used to update the value function.

Traditional Approaches Beyond Traditional Methods
Collaborative Filtering Tensor Factorization & Factorization Machines
Content-Based Recommendation Social Recommendations
Item-based Recommendation Learning to rank
Hybrid Approaches MAB Explore/Exploit

Adversarial Learning for Recommender Systems

Generative Adversarial Networks for Recommender Systems

Adversarial Attacks

Adversarial Training

Health Recommender Systems

Recommendations are becoming evermore important in health settings with the aim being to assist people live healthier lives. Three previous workshops on Health Recommender Systems (HRS) have incorporated diverse research fields and problems in which recommender systems can improve our awareness, understanding and behaviour regarding our own, and the general public's health. At the same time, these application areas bring new challenges into the recommender community. Recommendations that influence the health status of a patient need to be legally sound and, as such, today, they often involve a human in the loop to make sure the recommendations are appropriate. To make the recommender infallible, complex domain-specific user models need to be created, which creates privacy issues. While trust in a recommendation needs to be explicitly earned through, for example, transparency, explanations and empowerment, other systems might want to persuade users into taking beneficial actions that would not be willingly chosen otherwise. Multiple and diverse stakeholders in health systems produce further challenges.

  • Taking the patient's perspective, simple interaction and safety against harmful recommendations might be the prioritized concern.
  • For clinicians and experts, on the other hand, what matters is precise and accurate content.
  • Healthcare and insurance providers and clinics all have other priorities.

This workshop will deepen the discussions started at the three prior workshops and will work towards further development of the research topics in Health Recommender Systems.

Recommdender System for Doctor

Finding a primary care doctor is simpler than it used to be, thanks to on-demand services like ZocDoc, SimplyBook, and Doodle. But matching up with a clinician who’s compatible with your (or your family’s) personality is another story.

The recommender system is the core component of the social network named HealthNet (HN). The recommendation algorithm first computes similarities among patients, and then generates a ranked list of doctors and hospitals suitable for a given patient profile, by exploiting health data shared by the community. Accordingly, the HN user can find her most similar patients, look how they cured their diseases, and receive suggestions for solving her problem.

HN is implemented as a standard social network where users are patients. The first interaction with the system is the registration step. Then, the patient can enter personal health data: conditions, treatments (e.g., drugs, dosages, side effects, surgeries), health indicators (e.g., blood pressure, body weight, laboratory analysis, etc.), consulted doctors, hospitalizations. In this way, HN centralizes individual health data and allows a simple and organized access to them.

The Recommender System is the core component of HN. It exploits patient profiles for suggesting other similar patients, doctors,hospitals (the list of suggested, patients, doctors and hospitals can be further filtered by position and disease). The similarity between two patients $p,p^{\prime}$ is computed in terms of conditions and treatments. The semantic matching between the conditions exploits the HN disease hierarchy. More formally, the similarity score between two patients is computed as follows: $$s(p, p^{\prime}) = \alpha\frac{\sum_{i=1}^{k}\sum_{j=1}^{n}s_c(p_{c_i}, p^{\prime}_{c_j})}{kn}\

  • (1-\alpha)\frac{\sum_{i=1}^{z}\sum_{j=1}^{r}s_t(p_{t_i}, p^{\prime}{t_j})}{zr} $$ where $k$ (respectively $n$) is the number of conditions $p$ (respectively $p^{\prime}$) is affected by, $p_c$ is a condition of the patient $p$, $z$ (respectively $r$) is the number of treatments for $p$ (respectively $p^{\prime}$), $p_t$ is a treatment for the patient $p$. They are computed as follows: $$s_c(p{c_i}, p^{\prime}{c_j}) = \begin{cases} \log\frac{p{c_i}}{p^{\prime}{c_j}}, &\text{if $c_i=c_j$}\ \frac{1}{sp(c_i, c_j)}, &\text{otherwise} \end{cases}, s_t(p{t_i}, p^{\prime}_{t_j}) = \begin{cases} 1, &\text{if $t_i=t_j$}\ 0, &\text{otherwise} \end{cases}. $$

Patient-Doctor Matchmaking

There are different perspectives of patient-doctor matchmaking system:

  • From patients’ perspectives, such systems should provide explainable recommendations and safeguard against poor recommendations in order to be trustworthy.
  • From the perspective of healthcare professionals, these systems need to provide suitable recommendations based on their domain knowledge and experience.
  • More generally, insurance companies and healthcare institutes are interested in improving recommendation rates through research and reaping the potential benefits of these recommendation systems.

The features include demographic data, behevioral data, ICD-9, interaction, the number of visits to the doctor.

A Hybrid Recommender System for Patient-Doctor Matchmaking in Primary Care perform hybrid matrix factorization (MF) and recommend each patient a list of family doctors according to the level of information available about them. We achieve this by learning latent representations for patients and doctors from their interactions and metadata

Given the different level of information available to us about different patients, five use cases are proposed to make doctor recommendations in different scenarios.

The patient-doctor interaction matrix $Y \in \mathbb{R}^{M\times N}$ is defined as: $$y_{ij} = \begin{cases} 1, &\text{if interaction (patient i, doctor j) exists}\ 0, &\text{otherwise} \end{cases} $$

MF learns $\mathbf{p}i$ and $\mathbf{q}j$, such that the predicted score for unobserved entries $\hat{y}{ij}$ is given by the inner product of latent patient and doctor representations: $$\hat{y}{ij}=g(i,j\mid \mathbf{p}_i, \mathbf{q}_j)=g(\mathbf{p}_i\cdot \mathbf{q}_j)=\frac{1}{1+\exp(\left<\mathbf{p}_i,\mathbf{q}_j)\right>}.$$

Then formulate a learning-to-rank task by using Weighted Approximate-Rank Pairwise (WARP) loss. For each observed interaction $\hat{y}{ij}$, WARP samples a negative doctor $d$ and computes the difference between predicted $\hat{y}{ij}$ and $\hat{y}_{id}$, and performs a gradient update to rank the positive doctor higher if the difference is negative, i.e., a rank violation is found. Otherwise, it continues sampling negative doctors until it identifies a violating example. Thus, the rank of doctor j for patient i is minimized when taking a large number of sampled doctors d that need to be considered before finding a violating example.

We can model the trust $T_{ij} (t)$ between a patient $i$ and a family doctor $j$ at time $t$, given both the frequency and recency of their consultation history as: $$T_{ij} (t)=\sum_{t}\sum_{k}\frac{C_{ij}(t)e^{-\lambda t}}{C_{ik}(t)}$$ where $\lambda$ is annualized discount rate for the exponential decay function and treated as hyper-parameter during the model training, $C_{ij}(t)$ is the number of consultations between patient $i$ and doctor $j$ until year $t$, which is normalized by the total number of her consultations with $k$ doctors $C_{ik} (t)$ thus far.

DeepReco

Resource on RecSys

Labs

Workshop

Implementation

Preference Learning

Roughly speaking, preference learning is about methods for learning preference models from explicit or implicit preference information, typically used for predicting the preferences of an individual or a group of individuals. Approaches relevant to this area range from learning special types of preference models, such as lexicographic orders, over "learning to rank" for information retrieval to collaborative filtering techniques for recommender systems.

Pairwise Preference Learning and Ranking

Collaborative Preference Learning

Preference Learning and Gaussian Processes

Preference Learning and Choice Model

Preference learning has been studied for several decades and has drawn increasing attention in recent years due to its importance in web applications, such as ad serving, search, and electronic commerce. In all of these applications, we observe (often discrete) choices that reflect relative preferences among several items, e.g. products, songs, web pages or documents. Moreover, observations are in many cases censored. Hence, the goal is to reconstruct the overall model of preferences by, for example, learning a general ordering function based on the partially observed decisions. Choice models try to predict the specific choices individuals (or groups of individuals) make when offered a possibly very large number of alternatives. Traditionally, they are concerned with the decision process of individuals and have been studied independently in machine learning, data and web mining, econometrics, and psychology. However, these diverse communities have had few interactions in the past. One goal of this workshop is to foster interdisciplinary exchange, by encouraging abstraction of the underlying problem (and solution) characteristics.

Modeling Users’ Preferences

The ever-growing nature of user generated data in online systems poses obvious challenges on how we process such data. Typically, this issue is regarded as a scalability problem and has been mainly addressed with distributed algorithms able to train on massive amounts of data in short time windows. However, data is inevitably adding up at high speeds. Eventually one needs to discard or archive some of it. Moreover, the dynamic nature of data in user modeling and recommender systems, such as change of user preferences, and the continuous introduction of new users and items make it increasingly difficult to maintain up-to-date, accurate recommendation models.

Computational Advertising

Advertising, recommendation and search is 3 fundation stone of e-economics.

Online advertising has grown over the past decade to over 26 billion dollars in recorded revenue in 2010. The revenues generated are based on different pricing models that can be fundamentally grouped into two types: cost per (thousand) impressions (CPM) and cost per action (CPA), where an action can be a click, signing up with the advertiser, a sale, or any other measurable outcome. A web publisher generating revenues by selling advertising space on its site can offer either a CPM or CPA contract. We analyze the conditions under which the two parties agree on each contract type, accounting for the relative risk experienced by each party.

The information technology industry relies heavily on the on-line advertising such as [Google，Facebook or Alibaba]. Advertising is nothing except information, which is not usually accepted gladly. In fact, it is more difficult than recommendation because it is less known of the context where the advertisement is placed.

Hongliang Jie shares 3 challenges of computational advertising in Etsy, which will be the titles of the following subsections.

Click-Through Rate Modeling

GBRT+LR

When the feature vector ${x}$ are given, the tree split the features by GBRT then we transform and input the features to the logistic regression.

Practical Lessons from Predicting Clicks on Ads at Facebook or the blog use the GBRT to select proper features and LR to map these features into the interval $[0,1]$ as a ratio. Once we have the right features and the right model (decisions trees plus logistic regression), other factors play small roles (though even small improvements are important at scale).

Conversion Rate Modeling

Bid Optimization

User Engagement

User engagement measures whether users find value in a product or service. Engagement can be measured by a variety or combination of activities such as downloads, clicks, shares, and more. Highly engaged users are generally more profitable, provided that their activities are tied to valuable outcomes such as purchases, signups, subscriptions, or clicks.

User Modeling

User models are used to generate or adapt user interfaces at runtime, to address particular user needs and preferences. User models are also known as user profiles, personas or archetypes. They can be used by designers and developers for personalisation purposes and to increase the usability and accessibility of products and services.

Resource

Labs

Courese