推荐系统简介

| 研究学术  | 推荐系统  特征学习  机器学习应用 

推荐系统首先通过分析用户的使用历史获得用户的兴趣偏向,然后使用得到的用户兴趣偏向获得用户潜在感兴趣的产品或服务。鉴于产生推荐的方式不同,推荐系统通常可以分为以下三类[1]:基于内容的过滤(content-based filtering)、协同过滤(collaborative filtering)和CBF与CF的混合过滤(hybrid filtering)。

以电影的推荐系统为例,相关变量定义如下[2]

  • $n_u$:用户数目;
  • $n_m$:电影数目;
  • $r(i, j)$:若用户$j$对电影$i$进行了评分则赋值为1;
  • $y^{(i, j)}$:用户$j$对电影$i$的评分;
  • $\boldsymbol\theta^{(j)}$:用户$j$的参数向量;
  • $\mathbf x^{(i)}$:电影$i$的特征向量;
  • $m^{(j)}$:用户$j$评价过的电影数目。

基于内容的过滤

基于内容的过滤(CBF)方法根据抽取出的用户和产品特征获得推荐。这类方法利用用户和产品的特征计算他们之间的匹配度,最终把匹配得最好的数个产品推荐给相应的用户。

用户对电影的评价
图 1: 用户对电影的评价 [PNG]

上图展示了用户对电影的评分$0\sim 5$,用属于爱情片(romance)和动作片(action)的概率表示电影特征。用户评分?表示用户$j$未对电影$i$作出评价,也就是$r(i, j)=0$。

如何估计用户未评价电影的得分呢?这时一个线性回归问题。利用电影特征向量$\mathbf x^{(i)}$和参数$\boldsymbol\theta^{(j)}$,可估计用户$j$对电影$i$的评分 \begin{equation} y^{(i, j)} = \left(\boldsymbol\theta^{(j)}\right)^T\mathbf x^{(i)}。 \label{eq:user-rating} \end{equation}

因此,基于内容的的推荐需要学习参数$\boldsymbol\theta^{(1)},\boldsymbol\theta^{(2)},\dots,\boldsymbol\theta^{(n_u)}$。假设已知$\mathbf x^{(1)}, \mathbf x^{(2)}, \ldots, \mathbf x^{(n_m)}$,学习算法采用代价函数 \begin{equation} \begin{aligned} J\left(\boldsymbol\theta^{(1)},\dots,\boldsymbol\theta^{(n_u)}\right) = &{1\over 2}\sum_{j=1}^{n_u}\sum_{i:r(i, j)=1}\left(\left(\boldsymbol\theta^{(j)}\right)^T\mathbf x^{(i)} - y^{(i, j)}\right)^2 + \\ &{\lambda\over 2}\sum_{j=1}^{n_u}\sum_{k=1}^n\left(\theta_k^{(j)}\right)^2, \end{aligned} \label{eq:cf-learn-user-parameters} \end{equation} 由于电影评分的总数目是固定的,省去平均化过程对最小化代价函数没有影响,只保留$1\over 2$方便求导,梯度下降法更新参数的规则为 \begin{equation} \begin{aligned} \theta_k^{(j)}&:=\theta_k^{(j)}-\alpha\sum_{i:r(i,j)=1}\left(\left(\boldsymbol\theta^{(j)}\right)^T\mathbf x^{(i)} - y^{(i, j)}\right)x_k^{(i)} & (k=0)\\ \theta_k^{(j)}&:=\theta_k^{(j)}-\alpha\left(\sum_{i:r(i,j)=1}\left(\left(\boldsymbol\theta^{(j)}\right)^T\mathbf x^{(i)} - y^{(i, j)}\right)x_k^{(i)}+\lambda\theta_k^{(j)}\right)&(k\neq 0) \end{aligned}。 \end{equation}

CBF就是把某用户评价高的电影推荐给该用户。为了实现推荐,需要计算用户对所有电影的评分,计算复杂度高。

CBF方法具有两个主要的缺陷:

  1. CBF需要预处理产品以得到代表它们的特征,但这种预处理在实际问题中往往非常困难;
  2. CBF推荐给某个用户的产品往往和此用户已经消费过的产品很相似,它们无法发现用户并不熟悉但具有潜在兴趣的产品种类。

协同过滤

协同过滤(CF)方法不需要事先获得产品或用户的特征,它们只依赖于用户过去的行为(如对产品的浏览、评价或购买等)。 通过用户过去的行为企业可以收集用户对产品的显式评分(如Netflix)或隐式评分(如Google新闻)。通常 CF方法首先分析已经收集到的用户-产品评分对中所呈现的用户与产品的相互作用,然后它们使用这些相互作用为用户产生个性化产品推荐。

CF通常分为基于产品的(item-based)推荐和基于用户的(user-based)推荐。基于用户的推荐假设如果两个用户过去对产品有相似的喜好,那么他们现在对产品仍有相似的喜好;基于产品的推荐假设如果某个用户过去喜欢某种产品,那么该用户现在仍喜欢与此产品相似的产品。

在实际应用中,电影的特征向量往往也是未知的,需要通过学习得到。协同过滤不仅可以学习到用户对电影的评价,而且能学习到电影的特征。

电影特征向量学习与用户评价模型参数估计\eqref{eq:cf-learn-user-parameters}类似,假设已知$\boldsymbol\theta^{(1)},\boldsymbol\theta^{(2)},\dots,\boldsymbol\theta^{(n_u)}$,学习$\mathbf x^{(1)}, \mathbf x^{(2)}, \ldots, \mathbf x^{(n_m)}$采用的代价函数为 \begin{equation} \begin{aligned} J\left(\mathbf x^{(1)}, \ldots, \mathbf x^{(n_m)}\right) = &{1\over 2}\sum_{i=1}^{n_m}\sum_{i: r(i, j)=1}\left(\left(\boldsymbol\theta^{(j)}\right)^T\mathbf x^{(i)} - y^{(i, j)}\right)^2 + \\ &{\lambda\over 2}\sum_{i=1}^{n_m}\sum_{k=1}^n\left(x_k^{(i)}\right)^2 \end{aligned}。 \label{eq:cf-learn-item-features} \end{equation}

根据\eqref{eq:cf-learn-user-parameters}和\eqref{eq:cf-learn-item-features},同时学习$\mathbf x^{(1)}, \mathbf x^{(2)}, \ldots, \mathbf x^{(n_m)}$和$\boldsymbol\theta^{(1)},\boldsymbol\theta^{(2)},\dots,\boldsymbol\theta^{(n_u)}$可以采用代价函数 \begin{equation} \begin{aligned} J\left(\mathbf x^{(1)},\ldots,\mathbf x^{(n_m)},\boldsymbol\theta^{(1)},\dots,\boldsymbol\theta^{(n_u)}\right) = &{1\over 2}\sum_{(i,j): r(i, j)=1}\left(\left(\boldsymbol\theta^{(j)}\right)^T\mathbf x^{(i)} - y^{(i, j)}\right)^2 + \\ &{\lambda\over 2}\sum_{i=1}^{n_m}\sum_{k=1}^n\left(x_k^{(i)}\right)^2+{\lambda\over 2}\sum_{j=1}^{n_u}\sum_{k=1}^n\left(\theta_k^{(j)}\right)^2 \end{aligned}, \label{eq:cf-learn-all-parameters} \end{equation} 梯度下降法更新参数的规则为 \begin{equation} \begin{aligned} x_k^{(i)}&:=x_k^{(i)}-\alpha\left(\sum_{j:r(i,j)=1}\left(\left(\boldsymbol\theta^{(j)}\right)^T\mathbf x^{(i)} - y^{(i, j)}\right)\theta_k^{(j)}+\lambda x_k^{(i)}\right)\\ \theta_k^{(j)}&:=\theta_k^{(j)}-\alpha\left(\sum_{i:r(i,j)=1}\left(\left(\boldsymbol\theta^{(j)}\right)^T\mathbf x^{(i)} - y^{(i, j)}\right)x_k^{(i)}+\lambda\theta_k^{(j)}\right) \end{aligned}, \label{eq:grd-x-theta} \end{equation} 由于电影的特征$\mathbf x$也通过学习得到,不再需要额外增加$x_0^{(i)}=1$的项。

####协同过滤算法

  1. 用小的随机变量初始化$\mathbf x^{(1)},\ldots,\mathbf x^{(n_m)},\boldsymbol\theta^{(1)},\dots,\boldsymbol\theta^{(n_u)}$1
  2. 最小化代价函数\eqref{eq:cf-learn-all-parameters},若采用梯度下降法,采用\eqref{eq:grd-x-theta}更新参数;
  3. 学习到参数后,利用\eqref{eq:user-rating}计算用户$j$对电影$i$的评分。

协同过滤算法是一个不断进化的过程,$\mathbf x^{(i)}$和$\boldsymbol\theta^{(j)}$相互作用,$\mathbf x^{(i)}$推动$\boldsymbol\theta^{(j)}$更新,$\boldsymbol\theta^{(j)}$也推动$\mathbf x^{(i)}$更新。

当学习到电影的特征向量$\mathbf x^{(i)}$后,可以用$\left\lVert \mathbf x^{(i_1)}-\mathbf x^{(i_2)}\right\rVert$计算电影之间的相似度。通过电影的相似度,为用户推荐相关的电影,这就是基于物品的推荐方法。

CF方法存在的主要问题:

  1. 冷启动:对于一个新用户,由于缺乏其对产品的评分,CF无法为其提供可靠的 产品推荐;对于一种新的产品,CF无法确定该把它推荐给哪些用户。
  2. 可扩展性:CF方法中可能涉及到数以百万计的用户为成千上万种产品提供的评分。传统的CF推荐算法通常需要计算每对用户或产品之间的相似度,然后把这些相似度存放至电脑的主存中以便高效地产生推荐。当用户或产品的数量较大时,计算复杂度很高。

均值规范化

针对新用户的冷启动,该用户$j$从未对任何电影做出评价,协同过滤算法会得到用户的参数向量$\boldsymbol\theta^{(j)}=\mathbf 0$,如果估计该用户对电影的评分,也将全为$0$,这显然不符合逻辑。因此,需要对数据进行适当的处理,避免这样的情况发生。

均值规范化
图 2: 均值规范化 [PNG]

定义用户对所有电影评价的均值为$\boldsymbol\mu$,重新对用户对电影的评分规范化 \begin{equation} y^{(i,j)} := y^{(i,j)} - \mu_i。 \end{equation} 规范化评分后,公式\eqref{eq:user-rating}计算用户$j$对电影$i$的评分规则变为 \begin{equation} y^{(i, j)} = \left(\boldsymbol\theta^{(j)}\right)^T\mathbf x^{(i)}+\mu_i, \end{equation} 即使参数向量$\boldsymbol\theta^{(j)}=\mathbf 0$,估计新用户对电影的评分将是所有用户的平均分,合情合理。

思考问题

  • 如果系统已经有了部分标注的特征$\mathbf x$,如何融入到协同过滤算法中?
  • 如何利用协同过滤提高广告点击率?
  • 协同过滤的特征学习方法可以做传感器校准么?
  • 协同过滤和广联规则挖掘有何联系?
  • 协同过滤的特征学习可以解决盲源信号分离么?

混合过滤

混合过滤(HF)组合CBF和CF,以期在克服它们各自缺点的同时,融合它们特有的优势。通常组合的方式包括以下三种:

  1. 加权(weighted)组合:首先分别独立应用CBF和CF获得对产品的预测评分,然后组合它们的预测评分以便获得混合过滤的预测评分,最后根据混合预测评分为用户产生推荐列表。
  2. 混合(mixed)组合:首先分别独立应用CBF和CF产生各自的推荐列表,然后组合这两组推荐列表以便获得最终的推荐列表。
  3. 序贯(sequential)组合:当可用评分较少时使用CBF方法获得用户的特征并进行推荐;而当可用评分积聚到一定程度时,使用CF方法代替原来的CBF方法获得最终的推荐列表。

参考资料

  1. [1]吴金龙, “Netflix Prize 中的协同过滤算法,” PhD thesis, 北京大学, 2010.
  2. [2]A. Ng, “Recommender Systems.” Coursera, 2014. [Online]

脚注

  1. 如何确定电影的特征多少维合适呢? 


打赏作者


上一篇:异常检测     下一篇:计算广告学:广告基础