推荐系统简介

推荐系统首先通过分析用户的使用历史获得用户的兴趣偏向，然后使用得到的用户兴趣偏向获得用户潜在感兴趣的产品或服务。鉴于产生推荐的方式不同，推荐系统通常可以分为以下三类[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)}$¹；
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]

脚注