【笔记】Recommender System:Social RS

重新整理出来的推荐系统相关的资料；

Social Recommendation 包括：

1. 加入了 Social Network 的 SoRec
2. 与在前者基础上改进的 Social Trust

SoRec

推荐阅读 《SoRec Social Recommendation using Probabilistic Matrix Factorization》^[1]^

数据的稀疏性一直是推荐算法发展的一个巨大难题，作者考虑到了社交媒体在当今社会的发展，提出了一种加入 social network 的信息和评分记录来改进模型的方法。其主要思路是，用户对一件物品的评分很可能受关注的人/朋友的影响。

假设有m个物品(item)，n个用户(user)，f个因子(factor)

$U :$ 所有用户的集合

$I :$ 所有物品的集合

$P_{n\times f}: $ user-factor matrix

$Q_{m\times f}:$ item-factor matrix

$Z_{n\times f}:$ user-factor matrix in the social network graph

$R^f:$ 1$×$factor vector

$q_i:$ $Q$ 中物品 $i$ 所在行的向量

$p_u:$ $P$ 中用户 $u$ 所在的行的向量

$\vartheta :$ social network graph

$\nu :$ all the users in a social network

$\varepsilon :$ the edge set in social network graph

$$\vartheta = (\nu,\varepsilon)$$

$C_{n\times n} :$ user-user matrix of $\vartheta$

$c_{uj}\in (0,1] :$ donate the weight associated with an edge from $\nu_{u}$ to $\nu_{j}$

这里特别注意，在 social network 中的信息是单项的。这代表一个用户 A 关注了另一个用户 B，但 用户 B 不一定知道用户 A。

$d^{+}(\nu_{u}) :$ the outdegree of $\nu_{u}$

$d^{-}(\nu_{u}) :$ the indegree of $\nu_{u}$

$$c_{uj}^{*} = \sqrt{\frac{d^{-}(\nu_{j})}{d^{+}(\nu_{u})+d^{-}(\nu_{j})}}c_{uj}$$

如果将上式进行解释，就是一个用户 u 关注的其他的用户越多，那么他受某个特定用户 k 的影响就越少。如果特定用户 k 被很多人关注，那么用户 u 就会更加信任他。

$\kappa$ $:$ $\{ (u,i)|$ $r_{ui}$ is known $\}$

$\hat{r_{ui}}:$ 用户 $u$ 对物品 $i$ 的评分的预测值

$$\hat{r_{ui}}=q_{i}^{T}p_{u}$$

$N(x|\mu,\sigma^2): $ 正态分布,均值为 $\mu$ , 方差为 $\sigma^2$

假设 P，Q，R，C，S 皆服从高斯分布，既：

$$\begin{align} \\p(R|P,Q,\sigma_{R}^{2})&=\prod\limits_{u\in U}\prod\limits_{i\in I}N(r_{ui}|p_{u}^{T}q_{i},\sigma_{R}^{2}) \\p(C|P,Z,\sigma_{C}^{2})&=\prod\limits_{u\in U}\prod\limits_{j\in U}N(c_{uj}|p_{u}^{T}z_{j},\sigma_{C}^{2}) \\p(P|\sigma_{P}^{2})&=\prod\limits_{u\in U} N(p_{u}|0,\sigma_{P}^{2}) \\p(Q|\sigma_{Q}^{2})&=\prod\limits_{i\in I} N(q_{i}|0,\sigma_{Q}^{2}) \\p(Z|\sigma_{Z}^{2})&=\prod\limits_{u\in U} N(z_{u}|0,\sigma_{Z}^{2}) \end{align}$$

使用极大似然估计，既希望最大化：

$$\begin{align} p(P,Q|R,\overrightarrow{\theta})\qquad and \qquad p(P,Z|C,\overrightarrow{\theta}) \end{align}$$

使用贝叶斯定理可知：

$$\begin{align} &p(P,Q|R,\overrightarrow{\theta})\propto p(R|P,Q,\overrightarrow{\theta_{1}})p(P,Q|\overrightarrow{\theta_{2}}) \\ =&p(P,Q|R,\overrightarrow{\theta})\propto p(R|P,Q,\overrightarrow{\theta_{1}})p(P|\overrightarrow{\theta_{2}})p(Q|\overrightarrow{\theta_{2}}) \\ =&\prod\limits_{u\in U}\prod\limits_{i\in I}N(r_{ui}|p_{u}^{T}q_{i},\sigma_{R}^{2})\prod\limits_{u\in U} N(p_{u}|0,\sigma_{P}^{2})\prod\limits_{i\in I} N(q_{i}|0,\sigma_{Q}^{2}) \end{align}$$

同理得出 $p(P,Z|C,\overrightarrow{\theta})$ 后进行 $log$ 处理，并且合并两个式子，得：

$$\begin{align} &lnp(P,Q,Z|C,R,\sigma_{C}^{2},\sigma_{R}^{2},\sigma_{P}^{2},\sigma_{Q}^{2},\sigma_{Z}^{2}) \\ =&-\frac{1}{2\sigma_{R}^{2}}\sum\limits_{u\in U}\sum\limits_{i\in I}(r_{ui}-p_{u}^{2}q_{i})^{2} -\frac{1}{2\sigma_{C}^{2}}\sum\limits_{u\in U}\sum\limits_{j\in U}(c_{uj}^{*}-p_{u}^{2}z_{j})^{2} \\ &-\frac{1}{2\sigma_{P}^{2}}\sum\limits_{u\in U}p_{u}^{T}p_{u} -\frac{1}{2\sigma_{Q}^{2}}\sum\limits_{i\in I}q_{i}^{T}q_{i} -\frac{1}{2\sigma_{Z}^{2}}\sum\limits_{u\in U}z_{u}^{T}z_{u} \\ &-\frac{1}{2}\sum\limits_{u\in U}\sum\limits_{i\in I}ln\sigma_{R}^{2}-\frac{1}{2}\sum\limits_{u\in U}\sum\limits_{i\in I}ln\sigma_{C}^{2} -\frac{1}{2}(n\times f ln\sigma_{P}^{2}+m\times f ln\sigma_{Q}^{2}+n\times f ln\sigma_{Z}^{2}) \end{align}$$

$\lambda:$ 正则化系数

$\alpha:$ 学习速率(learning rate)

$$C(q_{i},p_{u},z_{u})=\sum\limits_{(u,i)\in \kappa}(r_{ui}-\hat{r_{ui}})^{2}+\lambda(\sum\limits_{u\in \nu}\sum\limits_{j\in \nu}(c^{*}_{uj}-p_{u}^{T}z_{j})^{2}+\Arrowvert q_{i}\Arrowvert^{2}+\Arrowvert p_{u}\Arrowvert^{2}+\Arrowvert z_{u}\Arrowvert^{2})$$ $$error=r_{ui}-\hat{r_{ui}}$$ $$err = c^{*}_{uj}-p_{u}^{T}z_{j}$$ $$\begin{align} q_{i}:&=q_{i}-\frac{\alpha}{2}\triangledown C(q_{i},p_{u},z_{u}) \\ &=q_{i}-\frac{\alpha}{2}\frac{\partial C(q_{i},p_{u},z_{u})}{\partial q_{i}} \\ &=q_{i}-\frac{\alpha}{2}(2error\times(-p_{u})+2\lambda q_{i}) \\ &=q_{i}+\alpha(error\times p_{u}-\lambda q_{i}) \end{align}$$ $$\begin{align} p_{u}:&=p_{u}-\frac{\alpha}{2}\triangledown C(q_{i},p_{u},z_{u}) \\ &=p_{u}-\frac{\alpha}{2}\frac{\partial C(q_{i},p_{u},z_{u})}{\partial p_{u}} \\ &=p_{u}-\frac{\alpha}{2}(2error\times(-q_{i})+2err\times(-z_{u})+2\lambda p_{u}) \\ &=p_{u}+\alpha(error\times q_{i}+err\times z_{u}-\lambda p_{u}) \end{align}$$ $$\begin{align} z_{u}:&=z_{u}-\frac{\alpha}{2}\triangledown C(q_{i},p_{u},z_{u}) \\ &=z_{u}-\frac{\alpha}{2}\frac{\partial C(q_{i},p_{u},z_{u})}{\partial z_{u}} \\ &=z_{u}-\frac{\alpha}{2}(2err\times(-p_{u})+2\lambda p_{u}) \\ &=z_{u}+\alpha(err\times p_{u}-\lambda z_{u}) \end{align}$$

Social Trust

推荐阅读 《Learning to recommend with social trust ensemble》^[2]^

这个模型是作者在上一个模型的基础改进的，主要思想是不再对用户在 social network 中关注的所有用户进行运算，而是挑选出几个用户最信任的朋友。

假设有m个物品(item)，n个用户(user)，f个因子(factor)

$P_{n\times f}: $ user-factor matrix

$Q_{m\times f}:$ item-factor matrix

$\vartheta :$ social network graph

$R^f:$ 1$×$factor vector

$q_i:$ $Q$ 中物品 $i$ 所在行的向量

$p_u:$ $P$ 中用户 $u$ 所在的行的向量

$\nu :$ all the users in a social network

$\varepsilon :$ the edge set in social network graph

$$\vartheta = (\nu,\varepsilon)$$

$S_{n\times n} :$ user-user matrix of $\vartheta$

$s_{uj}\in (0,1] :$ donate the weight associated with an edge from $\nu_{u}$ to $\nu_{j}$

$T(u) :$ the friends set that user $u$ trusts

$$s_{uj}^{*} = \frac{s_{uj}}{|T(u)|}$$

$r_{ui}:$ 用户 $u$ 对物品 $i$ 的打分

$\kappa$ $:$ $\{ (u,i)|$ $r_{ui}$ is known $\}$

$\lambda:$ 正则化系数

$\alpha:$ 学习速率(learning rate)

$\gamma :$ controls how much do users trust themselves or their trusted friends

注意此处依旧有一个控制变量，来调节用户对朋友的信任度

$$C(q_{i},p_{u})=\sum\limits_{(u,i)\in \kappa}(r_{ui}-(\gamma p_{u}^{T}q_{i}+(1-\gamma)\sum\limits_{j \in T(u)}s_{uj}^{*} p_{j}^{T} q_{i}))^{2}+\lambda(\Arrowvert q_{i}\Arrowvert^{2}+\Arrowvert p_{u}\Arrowvert^{2})$$

$\hat{r_{ui}}:$ 用户 $u$ 对物品 $i$ 的评分的预测值

$$\hat{r_{ui}}=\gamma p_{u}^{T}q_{i}+(1-\gamma)\sum\limits_{j \in T(u)}s_{uj}^{*} p_{j}^{T} q_{i}$$ $$error=r_{ui}-\hat{r_{ui}}$$

$B(u) :$ is the set that includes all the users who trust user $u$

$$\begin{align} q_{i}:&=q_{i}-\frac{\alpha}{2}\triangledown C(q_{i},p_{u}) \\ &=q_{i}-\frac{\alpha}{2}\frac{\partial C(q_{i},p_{u})}{\partial q_{i}} \\ &=q_{i}-\frac{\alpha}{2}(2error\times(-\gamma p_{u}-(1-\gamma)\sum\limits_{j \in T(u)}s_{uj}^{*} p_{j}^{T})+2\lambda q_{i}) \\ &=q_{i}+\alpha(error\times(\gamma p_{u}+(1-\gamma)\sum\limits_{j \in T(u)}s_{uj}^{*} p_{j}^{T})-\lambda q_{i}) \end{align}$$ $$\begin{align} p_{u}:&=p_{u}-\frac{\alpha}{2}\triangledown C(q_{i},p_{u}) \\ &=p_{u}-\frac{\alpha}{2}\frac{\partial C(q_{i},p_{u})}{\partial p_{u}} \\ &=p_{u}-\frac{\alpha}{2}(2error\times(-\gamma q_{i})+(1-\gamma)\sum\limits_{p\in B(u)}\sum\limits_{j\in T(u)}(-2error_{pi}\times s_{pj}^{*}q_{i}^{T}))+2\gamma p_{j}) \\ &=p_{u}+\frac{\alpha}{2}(error\times(\gamma q_{i})+(1-\gamma)\sum\limits_{p\in B(u)}\sum\limits_{j\in T(u)}(error_{pi}\times s_{pj}^{*}q_{i}^{T}))-\gamma p_{j}) \end{align}$$

---

Reference

1. Ma, H., Yang, H., Lyu, M.R., & King, I. (2008). SoRec: social recommendation using probabilistic matrix factorization. CIKM ‘08.
2. Ma, H., King, I., & Lyu, M.R. (2009). Learning to recommend with social trust ensemble. Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval.