推荐算法

一、推荐问题

  在推荐问题中，我们通常需要根据一系列的特征预测出一定的目标。比如一个电影网站要给用户推荐合适的电影，则推荐什么电影以及推荐电影的排序就是我们的目标，而user ID、电影名称、用户以往观看过的电影、用户以往给出的电影评分、观影时间等等就是我们可能会用到的特征。

  对于特征的表示，常用的一种方式是one-hot encoding：一个特征，若其有N个状态，则用N位寄存器来表示它，其中每一个状态都占用一个独立的寄存器位。假设有一群大学生，其特征包括了性别、学校、专业：

• 性别：[male, female]
• 学校：[THU, PKU, ZJU, MIT, Harvard, Stanford]
• 专业：[EE, CS, ME, IEOR, Physics, Mathmatics]

  对于一个学生，若性别为male表示为[1, 0]，就读于THU表示为[1, 0, 0, 0, 0, 0]，专业为EE的学生表示为[1, 0, 0, 0, 0, 0]，其所有特征可以表示为[1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]，可以想象用这种方式得到的特征将会是非常稀疏的向量。

二、推荐算法

1. Factorization Machine (FM)算法

  假设特征向量为x = [x₁, x₂, ..., x_n]，则在FM模型下，输出与特征的关系为：

  其中

  下图是利用特征，预测目标的示意图，图中1-4列蓝色部分表示user ID，接下来5列红色部分表示当前用户正要评价的电影，后面5列黄色部分表示其他用户评价过的电影的分数，后面一列绿色部分表示用户数据收集自2009年1月后所经历的月份，后面5列棕色部分表示用户上一个评价的电影，最后结果部分表示用户对这部电影的评分。

  FM可以间接分析出在原表中不直接相关的两个因素，比如在上图中x_A和x_ST不直接相关，二者的直接关联因子应为w_A,ST=0。但是通过factorization interaction参数<V_A, V_ST>，我们能够估计出x_A和x_ST之间的关系：
  1. x_B和x_C有相似的因子向量V_B和V_C，因为他们在预测Star War电影评分时，和V_SW有相似的交互关系，即<V_B, V_SW>和<V_C, V_SW>是相似的；
  2. 因子向量V_A和V_C是不同的，因为A给TI的评分为5，给SW的评分为1，而C给TI的评分为1，给SW的评分为5；
  3. 因子向量V_SW和V_ST是相似的，因为B在给二者评分时是相似的；
  4. 所以<V_A, V_ST>和<V_A, V_SW>应该是相似的，也就是说通过间接的方式估计出了，x_A和x_ST应该与x_A和x_SW的关系相似。

学习方法
  主要训练的参数有w₀,w和V，采用梯度下降的算法进行训练，关于不同参数的梯度如下所示。

2. DeepFM——for click through rate (CTR) prediction

  在很多推荐系统中，推荐的目标是使得链接点击的数量最高，因此给用户推荐的内容应按照预测的用户点击量来排序。有时候不同链接的点击量的收益是不同的，对于每一个点击我们可以赋予一个权重或者出价(bid)，则排序的目标变为CTR*bid。
现有的方法在对特征交互关系分析时或是只能分析高维相关性或是只能处理低维相关性。DeepFM是一种结合FM和深度神经网络的结构，能够同时考虑低维和高维特征交互。其网络结构如下所示：

DeepFM

  整个网络包括了FM和Deep两个子网络，设二者的输出分别为y_FM和y_DNN，则最终的输出为：y=sigmoid(y_FM+y_DNN)。DeepFM网络将输入的一阶特征以及二阶交互特征交于FM层处理，更高阶的特征交互则交于深度隐层处理。
输入特征：网络的输入为x=[x_field1, x_field2, ..., x_fieldm]，其中m为输入特征的数量，每一个特征，若是离散的，则用one-hot encoding方式来表示，若是连续的则用其连续值来表示。

Dense Embedding：Embedding层是将每一个特征x_i（注意不是每一个字段）乘上一个隐含向量v_i，其中v_i的维度为k1，k是认为设定的一个值。即通过Embedding层后，我们能得到V={v₁x₁, v₂x₂, ..., v_nx_n}。对于输入的每一个字段(field)，Embedding层与输入层是全连接的。具体的网络结构如下图所示。每一个特征字段都有一个对应的Embedding，比如Field 1对应e₁，此Embedding的包含k个元素，比如e₁，其第i个元素(i=1, 2, ..., k)值为v_1ix₁+v_2ix₂+...+v_field1ix_field1i。

FM Layer： FM层起的作用和前面提到的FM算法中一样，但值得注意的是，根据DeepFM结构图，在做FM时，同一个字段内的两个特征并不会做内积，只有不同字段之间的特征才会做内积。但奇怪的是文献中并没有明确说到提到这一点，仍然采用原有所有特征两两做内积的公式。

Hidden Layer：深层网络隐层的输入为Embedding的每一个元素，比如input₁=v₁₁x₁+v₂₁x₂+...+v_field11x_field11。

Embedding

  总结而言：DeepFM结构通过将Embedding后的特征数据同时输入了一个FM网络和一个Deep隐层网络，其中FM网络考虑特征的低阶交互关联，Deep隐层网络考虑特征的高阶交互关联。此外，此网络结构可以自动从输入的特征中选择出强关联性的特征，而不需要人为挑选关联特征。

3. NeuralFM

  NeuralFM网络的结果如下所示

NeuralFM

  此图中没有包括输出与输入特征的线性关联部分，但在网络中其仍然是存在的。网络的主要创新点在于提出了Bi-Interaction Pooling层，事实上，这层完成的事情就是计算特征的二阶交互关联，得到一个k维的向量，并将此向量输入至全连接网络中。
  网络在Frappe和MovieLens两个数据集上进行了测试，相较于其余FM方法，比如LibFM，Wide&Deep等网络，NeuralFM的效果是最好的，但好的不明显，预测精度提升有限。

参考文献

1. S. Rendle. Factorization machines. In ICDM, 2010.