User preference and embedding learning with implicit feedback for recommender systems

Abstract

In this paper, we propose a novel ranking framework for collaborative filtering with the overall aim of learning user preferences over items by minimizing a pairwise ranking loss. We show the minimization problem involves dependent random variables and provide a theoretical analysis by proving the consistency of the empirical risk minimization in the worst case where all users choose a minimal number of positive and negative items. We further derive a Neural-Network model that jointly learns a new representation of users and items in an embedded space as well as the preference relation of users over the pairs of items. The learning objective is based on three scenarios of ranking losses that control the ability of the model to maintain the ordering over the items induced from the users’ preferences, as well as, the capacity of the dot-product defined in the learned embedded space to produce the ordering. The proposed model is by nature suitable for implicit feedback and involves the estimation of only very few parameters. Through extensive experiments on several real-world benchmarks on implicit data, we show the interest of learning the preference and the embedding simultaneously when compared to learning those separately. We also demonstrate that our approach is very competitive with the best state-of-the-art collaborative filtering techniques proposed for implicit feedback.

Appendix

Theorem 1

Let ${\mathcal {U}}$ be a set of M independent users, such that each user $u \in {\mathcal {U}}$ prefers $n_*^+$ items over $n_*^-$ ones in a predefined set of ${\mathcal {I}}$ items. Let $S=\{({\mathbf {z}}_{i,u,i'}\doteq (i,u,i'),y_{i,u,i'})\mid u\in {\mathcal {U}}, (i,i')\in {\mathcal {I}}^+_u\times {\mathcal {I}}^-_u\}$ be the associated training set, then for any $1>\delta >0$ the following generalization bound holds for all $f\in {\mathcal {F}}_{B,r}$ with probability at least $1-\delta$:

$$\begin{aligned} {\mathcal {L}}(f)\le ~~&{\hat{{\mathcal {L}}}}_{*}(f,S) + \frac{2B{\mathfrak {C}}(S)}{Nn^+_*}\\&+\frac{5}{2}\left( \sqrt{\frac{2B{\mathfrak {C}}(S)}{Nn^+_*}}+\sqrt{\frac{r}{2}}\right) \sqrt{\frac{\log \frac{1}{\delta }}{n_*^+}}+\frac{25}{48}\frac{\log \frac{1}{\delta }}{n_*^+}, \end{aligned}$$

where ${\mathfrak {C}}(S)=\sqrt{ \frac{1}{n^-_*}\sum _{j=1}^{n_*^-}{\mathbb {E}}_{{\mathcal {M}}_j}\left[ \sum _{\begin{array}{c} \alpha \in {\mathcal {M}}_j \\ {\mathbf {z}}_{\alpha } \in S \end{array}}d({\mathbf {z}}_\alpha ,{\mathbf {z}}_{\alpha }))\right] }$, ${\mathbf {z}}_\alpha =(i_\alpha ,u_\alpha ,i'_\alpha )$ and

$$\begin{aligned} d({\mathbf {z}}_\alpha ,{\mathbf {z}}_{\alpha })=~&\kappa (\Phi (u_\alpha ,i_\alpha ),\Phi (u_\alpha ,i_\alpha ))\\&\quad +\kappa (\Phi (u_\alpha ,i'_\alpha ),\Phi (u_\alpha ,i'_\alpha ))- 2\kappa (\Phi (u_\alpha ,i_\alpha ),\Phi (u_\alpha ,i'_\alpha )). \end{aligned}$$

Proof

Let $n_\star ^+$ and respectively $n_\star ^-$ be the minimum number of preferred and non-preferred items for any user $u\in {\mathcal {U}}$, then we have:

$$\begin{aligned} {{\hat{{\mathcal {L}}}}}(f,S)\le \underbrace{\frac{1}{N}\frac{1}{n_*^- n_*^+}\sum _{u\in {\mathcal {U}}}\sum _{i\in {\mathcal {I}}^+_u}\sum _{i'\in {\mathcal {I}}^-_u} \mathbb {1}_{y_{i,u,i'}f(i,u,i')<0}}_{={\hat{{\mathcal {L}}}}_{*}(f,S)}. \end{aligned}$$

(9)

As the set of users ${\mathcal {U}}$ is supposed to be independent, the exact fractional cover of the dependency graph corresponding to the training set S will be the union of the exact fractional cover associated to each user such that cover sets which do not contain any items in common are joined together.

Following [Ralaivola and Amini (2015), Proposition 4], for any $1>\delta >0$ we have with probability at least $1-\delta$:

$$\begin{aligned} \begin{aligned} {\mathbb {E}}_S[{\hat{{\mathcal {L}}}}_{*}(f,S)]&-{\hat{{\mathcal {L}}}}_{*}(f,S)\\&\le \inf _{\beta >0}\left( (1+\beta ){\mathfrak {R}}_{S}({\mathcal {F}}_{B,r})+\frac{5}{4}\sqrt{\frac{2r\log \frac{1}{\delta }}{n_*^+}}+\frac{25}{16}\left( \frac{1}{3}+\frac{1}{\beta }\right) \frac{\log \frac{1}{\delta }}{n_*^+}\right) . \end{aligned} \end{aligned}$$

The infimum is reached for $\beta ^*=\sqrt{\frac{25}{16}\frac{\log \frac{1}{\delta }}{n_*^+\times {\mathfrak {R}}_{S}({\mathcal {F}}_{B,r})}}$ which by plugging it back into the upper-bound, and from Eq. (4), gives:

$$\begin{aligned} {\mathcal {L}}(f) \le {\hat{{\mathcal {L}}}}_{*}(f,S) + {\mathfrak {R}}_{S}({\mathcal {F}}_{B,r})+\frac{5}{2}\left( \sqrt{{\mathfrak {R}}_{S}({\mathcal {F}}_{B,r})}+\sqrt{\frac{r}{2}}\right) \sqrt{\frac{\log \frac{1}{\delta }}{n_*^+}}+\frac{25}{48}\frac{\log \frac{1}{\delta }}{n_*^+}. \end{aligned}$$

(10)

Now, for all $j\in \{1,\ldots ,J\}$ and $\alpha \in {\mathcal {M}}_j$, let $(u_\alpha ,i_\alpha )$ and $(u_\alpha ,i'_\alpha )$ be the first and the second pair constructed from ${\mathbf {z}}_\alpha$, then from the bilinearity of dot product and the Cauchy-Schwartz inequality, ${\mathfrak {R}}_{S}({\mathcal {F}}_{B,r})$ is upper-bounded by:

$$\begin{aligned} \frac{2}{m}{\mathbb {E}}_{\xi }\sum _{j=1}^{n_*^-}{\mathbb {E}}_{{\mathcal {M}}_j}\sup _{f\in {\mathcal {F}}_{B,r}}&\left\langle {\varvec{w}},\sum _{\begin{array}{c} \alpha \in {\mathcal {M}}_j \\ {\mathbf {z}}_\alpha \in S \end{array}}\xi _\alpha \left( \Phi (u_\alpha ,i_\alpha )-\Phi (u_\alpha ,i'_\alpha )\right) \right\rangle \nonumber \\&\le \frac{2B}{m}\sum _{j=1}^{n_*^-}{\mathbb {E}}_{{\mathcal {M}}_j} {\mathbb {E}}_{\xi }\left\| \sum _{\begin{array}{c} \alpha \in {\mathcal {M}}_j \\ {\mathbf {z}}_\alpha \in S \end{array}}\xi _\alpha (\Phi (u_\alpha ,i_\alpha )-\Phi (u_\alpha ,i'_\alpha ))\right\| \nonumber \\&\le \frac{2B}{m}\sum _{j=1}^{n_*^-}\left( {\mathbb {E}}_{{\mathcal {M}}_j \xi }\left[ \sum _{\begin{array}{c} \alpha ,\alpha '\in {\mathcal {M}}_j \\ {\mathbf {z}}_\alpha ,{\mathbf {z}}_{\alpha '} \in S \end{array}}\xi _\alpha \xi _{\alpha '}d({\mathbf {z}}_\alpha ,{\mathbf {z}}_{\alpha '}))\right] \right) ^{1/2}, \end{aligned}$$

(11)

where the last inequality follows from Jensen’s inequality and the concavity of the square root, and

$$\begin{aligned} d({\mathbf {z}}_\alpha ,{\mathbf {z}}_{\alpha '})=\left\langle \Phi (u_\alpha ,i_\alpha )-\Phi (u_\alpha ,i'_\alpha ),\Phi (u_\alpha ,i_\alpha )-\Phi (u_\alpha ,i'_\alpha )\right\rangle . \end{aligned}$$

Further, for all $j\in \{1,\ldots ,n^-_*\}, \alpha ,\alpha ' \in {\mathcal {M}}_j, \alpha \ne \alpha ';$ we have ${\mathbb {E}}_\xi [\xi _\alpha \xi _{\alpha '}]=0$, [Shawe-Taylor and Cristianini (2004), p. 91] so:

$$\begin{aligned} {\mathfrak {R}}_{S}({\mathcal {F}}_{B,r})\le&~\frac{2B}{m}\sum _{j=1}^{n_*^-}\left( {\mathbb {E}}_{{\mathcal {M}}_j}\left[ \sum _{\begin{array}{c} \alpha \in {\mathcal {M}}_j \\ {\mathbf {z}}_\alpha \in S \end{array}}d({\mathbf {z}}_\alpha ,{\mathbf {z}}_{\alpha }))\right] \right) ^{1/2}\\ =&~ \frac{2Bn^-_*}{m}\sum _{j=1}^{n_*^-}\frac{1}{n^-_*}\left( {\mathbb {E}}_{{\mathcal {M}}_j}\left[ \sum _{\begin{array}{c} \alpha \in {\mathcal {M}}_j \\ {\mathbf {z}}_\alpha \in S \end{array}}d({\mathbf {z}}_\alpha ,{\mathbf {z}}_{\alpha }))\right] \right) ^{1/2}. \end{aligned}$$

By using Jensen’s inequality and the concavity of the square root once again, we finally get

$$\begin{aligned} {\mathfrak {R}}_{S}({\mathcal {F}}_{B,r})\le \frac{2B}{Nn^+_*}\sqrt{\sum _{j=1}^{n_*^-}\frac{1}{n^-_*}{\mathbb {E}}_{{\mathcal {M}}_j}\left[ \sum _{\begin{array}{c} \alpha \in {\mathcal {M}}_j \\ {\mathbf {z}}_\alpha \in S \end{array}}d({\mathbf {z}}_\alpha ,{\mathbf {z}}_{\alpha }))\right] }. \end{aligned}$$

(12)

The result follows from Eqs. (10) and (12). $\square$