序列推荐
花了三天时间系统性看了一下推荐系统中关于“序列推荐”相关的八篇论文。其中七篇论文来源于SIGIR2018上关于Knowledge-Enhanced Memory Netwroks论文的related work。所有论文时间跨度为2010-2018，基本上是sequential recommendation这方面的主要成果。趁热打铁赶紧记录一下对每篇论文的理解以及一些思考。
1、（2010 FPMC）Rendle, Steffen, C. Freudenthaler, and L. Schmidt-Thieme. “Factorizing personalized Markov chains for next-basket recommendation.” International Conference on World Wide Web ACM, 2010:811-820.
在传统的推荐方法中，Matrix Factorization（MF）能够学习到用户一般性的喜好；而Markov chains（MC）可以通过时间相关的转移矩阵而对序列行为建模。由于其各自的优势，FPMC将这两个方法进行组合来学习个性化的转移矩阵。其主要思想是在原来MC维护一个全局共享转移矩阵的基础上进行改进，对每个用户在自己的行为序列上维护一个transition matrix，从而得到一个|Users|x|Items|*|Items|的立方阵，论文分析了如果使用原来用于MC的MLE（最大似然估计）方法来学习立方阵中的各个概率，其只能作用于用户各自的行为序列，而用户与用户之间无法建立关联，即每个user的共同item无法进行“共享更新”（即不会相互影响），且每个用户数据的稀少导致MLE学习到的个性户转移矩阵过于稀疏，无法进行后续预测。所以作者基于MF的思想，提出”Factorization of the Transition Cube”，即张量分解为“current user”，“current basket items”，“last basket items”。这样不同user的item之间由于同一个向量表示而建立起关联，用户数据稀疏性带来的问题会因为整体数据的稠密性而解决。最后模型的预测方法为下面这个公式。公式前部分可以理解为MF，表示用户偏好；后半部分可以理解为FMC，表示序列行为。两者进行累加，得到user对item在t时间的预测评分。最后对x进行排序得到top-k即为next-basket。
2、（2015 HRM）Wang, Pengfei, et al. “Learning Hierarchical Representation Model for NextBasket Recommendation.” (2015):403-412.
HRM提出FPMC在使用users’ general taste和sequential behavior时，线性叠加过于粗暴。线性组合意味着每个部分对next-basket中的item的影响是独立的，但是作者分析如下分析：
用户偏好和序列行为对next-basket的影响不能单纯的线性组合。
所以HRM通过对所有item、user进行embedding。在用户购买记录中，以每个basket为单元，对其中的所有items采用某种aggregation operation（论文主要是用两种：average pooling和max pooling）合成basket representation，这称为第一层；然后与user embedding进行某种aggregation operation（前后operation不一定相同），生成user在t-1时间的embedding，这称为第二层。得到的结果与候选所有的item embeeding相乘，采用softmax得到每个item被推荐的概率进行推荐。论文使用log probability作为objective function，同时采用negative sampling来优化目标函数。以下为HRM对某个用户某个basket的操作图解。由于每个用户存在多个这样的训练单元，为了防止过拟合，作者采用Dropout（50%）for each unit。
3、（2016 DREAM）Yu, Feng, et al. “A Dynamic Recurrent Model for Next Basket Recommendation.” International ACM SIGIR Conference on Research and Development in Information Retrieval ACM, 2016:729-732.
DREAM算是最直接的RNN应用，其对每个用户的购买记录生成n个basket，每个basket中的item embedding采用HRM中的aggregation operation（也是有两种）生成basket representation，然后按照时间排序当作RNN的input layer，有多少个basket就有多少层RNN，每层共享basket的特征表示，hidden layer为user dynamic representation（这也是DREAM与HRM不同的地方，它使用的动态user表示，而HRM使用的是全局表示）。最后与N个item embedding相乘，即可得到每个item的score。当然也可以加一个activation function。
其中hidden layer计算方法为：
最后分数的计算方法为：
整个网络的结构如下：
4、（2017）Wu, Chao Yuan, et al. “Recurrent Recommender Networks.” Tenth ACM International Conference on Web Search and Data Mining ACM, 2017:495-503.
该论文采用RNN分别对user和item进行分析，即使用user-state RNN和movie-state RNN分别学习user和item的hidden state/latent state。其学习过程以user为例进行解释：公式（5）中，x为当前user（item），通过embedding层，得到隐藏层状态y(t)：
然后基于上一个状态的输出u(t-1)与当前隐藏层y(t)，使用LSTM得到输出u(t)，即用户当前时刻的表示，如公式（6）中呈现。同样的方法作用在item上，得到m(t)，这里的u和m都是user和item的集合，所以我们针对于特定时间的user和item，表示为n(it)和m(it)，
最后再预测r(ij|t)时，不仅仅使用了RNN学习到的u(it)和m(jt)，还考虑到user和item的全局表示的重要性。所以最后r(ij|t) = u(it)·m(jt)+u(i)·m(j)，论文整个网络结构如下。值得说明的是，它没有将输入层描述出来，直接从hidden layer开始，然后图中的方框则表示LSTM单元。由于u(it)与m(jt)都是参数，且存在相关性，所以论文采用subspace descent的方法来对参数进行更新。
5、（2017 RNN-GRU）Donkers, Tim, B. Loepp, and J. Ziegler. “Sequential User-based Recurrent Neural Network Recommendations.” Eleventh ACM Conference on Recommender Systems ACM, 2017:152-160.
上一篇文章是将user和item分别使用RNN结合LSTM来学习其特征。而这篇文章则使用RNN结合GRU，将user和item作为同一个GRU单元的输入。具体做法为：采用GRU来对用户的购买行为（sequence）建模。其中每个用户所购买的item作为输入，以及上一个时间的hidden state也作为输入，考虑到用户的重要性，将user embedding也加入到GRU的输入当中，如何对input layer进行保留便产生了讨论，作者提出了三种方案：
a、Linear User Integration：如下图，输入部分为上一个隐藏层状态h(t-1)、user state u(t)、item state i(t)。图中u为update gate，r为reset gate，k相当于所有信息的记忆，结合h(t-1)可以计算得到当前阶段的隐藏层状态h(t)，这是最基本的GRU单元的处理方式。
b、Rectified Linear User Integration：如下图所示，对user state的范围进行判断，即考虑user的必要性。其方法是通过计算k的范围，判断u(t)与k1和k2的大小关系，得到三种情况：1、全部丢弃，不考虑；2、要么加上w权重；3、要么全部保留。下图表示的只是对u(t)的一个操作，得到的u(t)再相当于上图中的输入来计算当前的隐藏层状态h(t)。
c、Attentional User Integration：如下图所示，该方法不仅仅对user state进行调整，对item state也进行调整。首先计算出图中的Eplison，item state保留（1-Eplison）·i(t)，user state保留（Eplison）·u(t)，同样作为第一个图中的输入，来计算最后的隐藏层状态h(t)。
6、（2018 RUM）Chen, Xu, et al. “Sequential Recommendation with User Memory Networks.” the Eleventh ACM International Conference ACM, 2018:108-116.
这篇文章是结合当前较热的Memoey Network和Attention mechanism来进行时间序列推荐。其主要思想是维护一个memory matrix来保留每个用户最近的行为，然后在计算user u对item i的偏好时，通过当前item与memory matrix中user的历史行为，计算得到用户对此item历史偏好，即user memory embedding，将user memory embedding与user intrisic embedding进行整合，得到用户的user embedding p(u)，最后通过p(u)·q(i)得到偏好值。如下图(c)所示。论文最终以binary cross-entropy作为objective function。
作者对memory matrix进行了两种设计：如下图(a)(b)。
(a)表示item-level RUM：Read Operation即：memory matrix中存储user u最近click或者purchase的item embedding M(u)，然后与当前的item i分别进行计算，采用softmax的方式计算attention的值，即图(a)中z。相应的attention z值与M(u)中对应的item embedding进行相乘后累加即可得到user memory embedding。Write Operation即：每次用当前的item embedding替换掉最旧的item embedding。（注：memory matrix中的embedding数设置为k个，k值在实验中也进行了讨论）
(b)表示feature-level RUM：Read Operation即：memory matrix采用key-value memory neural network，首先存储一个global latent feature tableuser preference（GLFT）来存储feature embedding，然后不同的feature embedding与当前的item embedding进行计算，采用softmax的方式计算attention的值，即图(b)中z，相应的attention z值与M(u)中对应的item embedding进行相乘后累加即可得到user memory embedding。Write Operation即：根据neural turing machine（NTM）的思想，论文提出了erase vector和add vector的两个步骤来更新M(t)。(这个步骤的可解释性不强…)
7、（2018 CMN）Ebesu, Travis, B. Shen, and Y. Fang. “Collaborative Memory Network for Recommendation Systems.” (2018).
该论文使用user-based collabrative filtering和memory network想结合的方式进行建模。如下图(a)所示，m_u为user u的embedding，e_i为item i的embedding，M为所有用户的embedding，通过q_uiv = m_u·m_v+e_i·m_v得到the similarity of the target user u’s level of agreement with user u in the neighborhood give item i，即与user u共同给item i打过分的相似度。通过对q_uiv使用softmax可以得到neighborhood attention，与C进行相乘得到final neighborhood representation，C为与user u存在相关性的user embedding，称为external memory。最后联合neighborhood representation，current user embedding，current item embedding来计算最终的output。如公式(10)。图(b)则是增加层数，即在得到o_ui之后再加入activation function来生成新的attention值，向下一层输入。论文最后使用BPR来作为objective function来更新参数。
8、（2018 KSR）Improving Sequential Recommendation with Knowledge-Enhanced Memory Networks
KSR本质上是对feature-level RUM的扩展，并结合knowledge-based infotmation。论文使用BPR来进行pre-train得到item embedding，在学习的过程中item embedding为固定值。通过RNN-GRU来训练得到sequential preference representation。Read Operation即：memory network采用key-value memory neural network，其中key vector为KB中的relation embedding，而value vector为entity embedding。通过sequential preference representation（Hidden layer h(t)），结合key-value使用softmax得到attention值，attention值与value-vector可以得到attribute-based preference representation。sequential preference representation+attribute-based preference representation即可得到user representation p_u，而q_i+e_i·p_u即可得到最终的item reprenetation q_i，其中e_i为entity embedding。最后对p_u和q_i分别使用MLP（多层感知机）后相乘得到最后user u对item i的打分。Writing Operation即：结合KB information与value vector，对其乘积采用sigmoid得到权重值，再对value vector进行update。图2似乎更能够解读这样一个过程。论文最后使用BPR来作为objective function来更新参数。
几点思考：
1、sequential recommendation的方法的发展可以归纳为：MC、Representation Model、RNN、RNN_LSTM、RNN_GRU、Attention+Memory Network…
2、阅读了这八篇文章，一方面对进行sequential recommendtaion的方法有了一定的了解：sequential behavior、user taste相结合能更好的表述用户的特征。另一方面对RNN如果进行sequential recommendation应用更加清晰：1、单个user单个item作为input layer；2、以basket representation作为input layer，basket representation可以使用max pooling、average pooling的item representation计算得到。在这种情况下，user可以为static（HRM）和dynamic（DREAM）两种情况。
3、在写这篇文章的过程中，最难下手描述的地方可以说是memory network中的writing operation，因为如果直接描述公式似乎有点苍白，但是对其解释却难以找到理论支撑。我一直在思考：这里为什么要这么做？为什么要erase？为什么要add？
4、只有写出来，才能发现自己对论文理解中的模糊点。而且对这些文章的理解还有一些不够全面的地方，之后通过实验来深入理解，并完善这篇文章。
5、之前做时间序列推荐主要有：在传统的推荐系统中以时间权重的形式加入时间特性, 但是随着数据规模的越来越大以及用户需求的增加，这种方法的算法复杂度较高，并且对于时间权重使用，无法有效利用时序数据 规律变化的特征; 另外通过张量分解利用时间信息的方法，这类方法将时间作为单独的一维数据进行数据建模，对用户-项目-时间张量进行分解，但是通常具有很高的计算复杂度。