BLOG

个人博客,记录学习与生活

矩阵分解和因子分解机

Published Oct. 25, 2020, 11:40 p.m. by kkk

继协同过滤后的一大推荐算法,成名为2006年的Netflix Prize推荐比赛。主要解决的是协同过滤难以处理稀疏矩阵的问题,提高了泛化能力。

问题定义

已有用户-物品交互矩阵,交互值为0、1或评分值,根据交互矩阵为指定用户进行物品兴趣度预测(CTR)和物品推荐(TopN)。

技术方案

构造隐向量空间,将用户-物品交互矩阵分解为两个矩阵:用户-隐向量矩阵、隐向量-物品矩阵

相当于将用户和物品都投影到一个低维的向量隐空间,设向量空间为$k$维,则两矩阵中每个$k$维向量表示用户向量和物品向量,两者的内积认定为两者的相似度。

分解算法

  1. SVD。对于矩阵分解,常用算法就是EVD(特征值分解)和SVD(奇异值分解),因为用户-物品交互矩阵不是方阵,无法使用EVD,所有使用SVD。但是对于$m\times n$的矩阵,复杂度高达$O(mn^2)$,对于规模较大的矩阵,SVD计算成本比较大,基本无法满足工业需求。
  2. LFM。称为Latent Factor Model,将求解两个矩阵的参数问题转换成一个最优化问题,通过训练集数据来不断更新用户矩阵和物品矩阵中的参数,通常使用梯度下降法。

理论分析

相似度预测: $$ \hat r_{ui} = \mu + b_u + b_i + p_u^T\cdot q_i $$ 其中$\mu, b_u, b_i$都为偏置参数,为了消除用户和物品打分的差异,$\mu$是所有用户-商品记录评分的全局平均数;$b_u$为用户偏置,可以使用用户$u$的平均均值也可以作为训练参数;$b_i$为物品偏置,可以使用物品$i$的平均均值。加入偏置后,隐向量更能反映不同用户对不同物品的态度差异

可以使用带正则项的MSE作为损失函数。

目标函数: $$ L(p_u, q_i, b_u, b_i)= \frac{1}{2}\sum_{u,i}[ (r_{ui}-\hat r_{ui})^2 + \lambda(\Vert p_u\Vert^2 + \Vert q_i\Vert^2+b_u^2 + b_i^2)] $$ 求导有(向量、矩阵求导参考The Matrix Cookbook): $$ \begin{align} \frac{\partial L}{\partial p_u} &= \sum_{ui}[-q_i^T(r_{ui}-\hat r_{ui}) + \lambda p_u]\\ \frac{\partial L}{\partial q_i} &= \sum_{ui}[-q_{u}^T(r_{ui}-\hat r_{ui}) + \lambda q_i]\\ \frac{\partial L}{\partial b_u} &= \sum_{ui}[-(r_{ui}-\hat r_{ui})+\lambda b_u]\\ \frac{\partial L}{\partial b_i} &= \sum_{ui}[-(r_{ui}-\hat r_{ui}) + \lambda b_i] \end{align} $$ 设置好epoch, learning_rate, lambda等参数,进行梯度更新即可。

实现

见Github页面矩阵分解

因子分解机(FM)

另外介绍一下因子分解机(FM)。因子分解机思想同矩阵分解,在推荐系统中的场景不多,主要在于降低特征交叉的复杂度,主要贡献在于处理特征交叉的思想

对于CTR问题,以前常用的技术是LR,输入用户的特征,输出对用户是否会点击(某产品、某服务等)的概率,为了增强特征的表示能力,对用户特征加以组合: $$ y = w_0 + \sum_{i=1}^n w_i x_i + \sum_{i=1}^n\sum_{i+1}^nw_{ij}x_i x_j $$ 解释

  • 上式中除去最后一项就是标准的LR,$x$为输入,$y$为输出
  • 输入$x$具有$n$个类别(通常都是一维),表示$n$种不同的特征
  • 最后一项$w_{ij}$是特征$i$和特征$j$的组合特征,为了提高特征表达能力
  • 可知,需要的参数$w_{ij}$个数为$C_n^2$,规模是$n^2$

正如上述中,直接对特征进行(二项)交叉,需要重新学习的参数规模为$n^2$,为了降低这个复杂度,应用到FM的思想,将$w_{ij}$所有元素构成的整体视为一个矩阵(且是方阵,称为$W$),对该方阵进行降维得到$n\times h, h\times n$的两个矩阵,实际上两个矩阵互为转置(根据$W$元素特征可知为半正定矩阵,可以分解为$W=V^TV$)。进一步理解:就是Embedding的思想,将每个特征用一个隐向量表示,$n$个特征就是$n$个隐向量,不同特征的二项交叉通过两者隐向量的内积表示

由于隐向量是具有维数的,设为$k$,那么应用FM思想之后,分解的矩阵总特征交叉参数规模为$kn$,而原规模是$n^2$。


Share this post
< Pre: 协同过滤(Collaborative Filtering) Pos: Wide&Deep >
1294 comments
Similar posts
Add a new comment