基于贝叶斯概率模型推荐算法 Bayesian Personalized Ranking

  Posted by Mr.Zhang on 22 Jul, 2019

   STATISTICS   

参考论文:[Rendle_et_al2009-Bayesian_Personalized_Ranking]

基本概念

隐式反馈是指用户浏览、购买等反馈数据,通常是二值形式;显式反馈通常指评分数据,为一段区间的数值评分

  • 假设$n$个用户集合$U=\{u_1,u_2,...,u_n\}$
  • $m$个项目集合$I=\{i_1,i_2,...,i_m\}$
  • 用户对项目显式评分数据为一个$n\times m$维的矩阵$R$表示,$r_{u,i}$表示用户$u$对项目$i$的评分
  • 对偶的,定义隐式反馈矩阵$D$,其中$d_{u,i}\in\{0,1\}$$d_{u,i}=1$表示用户$u$对项目$i$有隐式反馈记录,否则$d_{u,i}=0$

矩阵分解(Matrix Factorization)模型 - 定义两个矩阵$W\in\mathbb{R}^{n\times k}$$H\in\mathbb{R}^{m\times k}$ - 矩阵对应行向量$w_u,1\le u\le n$$h_i,1\le i\le m$分别表示用户和项目的特征属性向量 - 矩阵分解模型基于隐语义分析(Latent Class Model) - 假设用户喜好和项目属性都可以用向量表示,传统的矩阵分解模型使用用户喜好向量和项目属性向量的内积来估计用户对项目的评分 - 定义$\hat x_{ui} = \langle w_u,h_i \rangle = \sum_{j=1}^k w_{uf}h_{if}$

问题分析

在隐式反馈系统中仅有正样本,剩余数据是真正的负样本和缺失值的混合

  • 处理缺失值问题的常见方法是忽略缺失值
  • 但常用的机器学习模型就学习不到这类信息,因为其不能区分两类样本
  • 常用推荐算法根据观测到的正样本训练,会导致过拟合;之所以可以被用来排序是加入正则化方法
  • BPR的目标是将项目作为训练数据,优化目标是对项目进行正确排序而不是对单个目标进行评分,这样更好的表示问题而不是仅仅以负样本代替缺失值

BPR模型

BPR模型核心思想是为每一个用户建立一个用户偏好的偏序对,利用这些偏序对训练一个推荐模型,而不是直接利用隐式反馈矩阵$D$来训练模型

  • 假设$I_u^+$表示用户$u$有隐式反馈的项目集合
  • $I \setminus I_u^+$表示用户$u$无隐式反馈的项目集合
  • 用户偏好的偏序对集合$P=\{(u,i,j)|i\in I_u^+ \land j\in I \setminus I_u^+ \}$
  • $P$中每一个元素$(u,i,j)$表示用户$u$对项目$i$的喜好大于项目$j$
  • BPR模型的优化目标就是给定一个推荐模型$\Theta$,对$P$中的所有偏序对$>_u$,最大化后验概率$p(\Theta|>_u)$
  • 根据贝叶斯概率理论,有$p(\Theta|>_u) \propto p(>_u|\Theta)p(\Theta)$
    • 其中$p(>_u|\Theta) = \prod_{(u,i,j\in P)} p(i >_u j | \Theta)$
  • 定义:$p(i >_u j | \Theta) = \sigma(\hat x_{uij}(\Theta))$
    • 其中$\hat x_{uij}(\Theta)$表示用户$u$对项目$i$$j$的偏好关系,是关于模型参数$\Theta$的实函数
    • $\sigma$是Logistic函数,即$\sigma(x)=\frac{1}{1+\exp(-x)}$
  • 所以最终的优化目标为:

$$ \max_\Theta = \ln p(\Theta|>_u) = \sum_{(u,i,j\in P)} \ln \sigma(\hat x_{uij}(\Theta)) - \lambda_\Theta \|\Theta\|^2 $$

  • 其推导过程如下:

$$\begin{aligned} \text{BPR-OPT} = & \ln p(\Theta|>_u) \\ =& \ln p(>_u|\Theta)p(\Theta) \\ =& \ln \prod_{(u,i,j\in P)} \sigma(\hat x_{uij}(\Theta))p(\Theta) \\ =& \sum_{(u,i,j\in P)} \ln \sigma(\hat x_{uij}(\Theta)) + \ln p(\Theta) \\ =& \sum_{(u,i,j\in P)} \ln \sigma(\hat x_{uij}(\Theta)) - \lambda_\Theta \|\Theta\|^2 \end{aligned} $$

  • 这里引入一般性先验密度函数$p(\Theta) \sim N(0,\Sigma_\Theta)$,通常令$\Sigma_\Theta = \lambda_\Theta I$
  • $\lambda_\Theta$是正则化参数

使用随机梯度下降训练,有:

$$\begin{aligned} \frac{\partial \text{BPR-OPT}}{\partial \Theta} &= \sum_{(u,i,j\in P)} \frac{\partial}{\partial \Theta} \ln \sigma(\hat x_{uij}(\Theta)) - \lambda_\Theta \frac{\partial}{\partial \Theta} \|\Theta\|^2 \\ &\propto \sum_{(u,i,j\in P)} \frac{-\exp(-\hat x_{uij}(\Theta))}{1+\exp(-\hat x_{uij}(\Theta))} \cdot \frac{\partial}{\partial \Theta} \hat x_{uij}(\Theta) \lambda_\Theta \cdot \Theta \end{aligned}$$

算法伪代码:

procedure LEARNBPR $(P,\Theta)$

1: initialize $\Theta$

2: repeat

3: $\quad$ draw $(u,i,j)$ from $P$

4: $\quad \Theta \gets \Theta +\alpha( \frac{-\exp(-\hat x_{uij}(\Theta))}{1+\exp(-\hat x_{uij}(\Theta))} \cdot \frac{\partial}{\partial \Theta} \hat x_{uij}(\Theta) - \lambda_\Theta \cdot \Theta )$

5: until convergence

6: return $\hat \Theta$

BPR-MF算法

在BPR模型中,选择训练模型为矩阵分解模型MF,就得到了BPR-MF算法

  • 定义$\hat X = W H^\top$
  • 利用矩阵分解可以得到$\hat x_{ui} = \langle w_u,h_i \rangle $
  • 那么$\hat x_{uij} =\hat x_{ui} - \hat x_{uj}$
  • 模型参数即为$\Theta =(W,H)$
  • BPR-MF算法优化的目标即为:

$$\min_{W,H} O = - \sum_{(u,i,j\in P)} \ln \sigma(\hat x_{uij}) + \lambda ( \|\ W \|_F^2 + \|\ H \|_F^2)$$

  • 使用随机梯度下降训练:

$$\begin{aligned} \frac{\partial O}{\partial u} &= \frac{1}{1+\exp(w_u h_i-w_u h_j)}(h_j - h_i) + \lambda w_u \\ \frac{\partial O}{\partial i} &= \frac{-w_u}{1+\exp(w_u h_i-w_u h_j)} + \lambda h_i \\ \frac{\partial O}{\partial j} &= \frac{w_u}{1+\exp(w_u h_i-w_u h_j)} + \lambda h_j \\ \end{aligned}$$

  • 训练参数过程:
    • 使用$n*m$的数据集,处理成$n$$m*m$的数据集合
    • 随机化初始化$W,H$矩阵,利用$w_u,h_i$来计算$x_{u,i}$
    • 根据训练过程的计算公式迭代更新$\Theta,w_u,h_i$直至$\Theta$收敛