【论文阅读】Curriculum Meta-Learning for Next POI Recommendation
【论文阅读】Curriculum Meta-Learning for Next POI Recommendation
【论文阅读】Curriculum Meta-Learning for Next POI Recommendation
Metadata
authors:: Yudong Chen, Xin Wang, Miao Fan, Jizhou Huang, Shengwen Yang, Wenwu Zhu container:: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining year:: 2021 DOI:: 10.1145/3447548.3467132 rating:: ⭐⭐⭐ share:: false comment:: 着眼于 POI 推荐的城市转移问题，使用元学习概念，并引入了困难度 Hardness 概念
前言
2021 年，KDD 会议 POI 推荐：Curriculum Meta-Learning for Next POI Recommendation
OverView
POI 推荐能够为不同城市的用户提供满意的服务，然而，可用的数据通常是稀缺的。在一些城市规模、人口或市场占用率较小的城市，即在冷启动的城市，在那里可以收集到的用户-POI 数据有限，无法充分利用数据。
论文期望将从其他数据丰富的城市所学到的知识，转移到冷启动城市的推荐任务中。这项任务主要面对两个挑战：
- 不同城市之间的共享数据极其有限；
- 不同城市不同用户的地图搜索模式具有很大的多样性，给推荐知识的转移带来了很大的困难。
为了同时解决这两个挑战，论文提出了一个新颖的 Curriculum Hardness Aware Meta-Learning（CHAML）框架，通过将元学习和非均匀采样策略纳入下一个 POI 搜索推荐，来缓解数据稀少和样本多样性问题。
论文主要贡献：
- 第一个探索 POI 推荐中的城市转移问题，并通过元学习解决这个问题；
- 提出了一个新颖的 Curriculum Hardness Aware Meta-Learning（CHAML）框架，通过增强元学习器的用户和城市层面的硬样本挖掘和城市层面的课程学习，缓解了冷启动城市的数据稀缺和样本多样性问题。
问题描述
假设每个城市都有其唯一的用户集合U\mathcal{U}U和 POI 集合V\mathcal{V}V，并且不共享任何共同的用户或 POI。
（record）r=(v,t,l)r=(v,t,l)r=(v,t,l)为用户uuu的一条记录，表示在ttt时刻访问了 POI vvv，其位置为lll。
（user history）histu={r1,r2,⋯ ,rn}hist_u = \{ r_1,r_2,\cdots,r_n \}histu={r1,r2,⋯,rn}为用户访问序列。
（next POI recommendation）f:(u,histu,tn+1,ln+1,vcandi)↦y∈[0,1]f:(u, hist_u, t_{n+1}, l_{n+1}, v_{candi}) \mapsto y\in[0,1]f:(u,histu,tn+1,ln+1,vcandi)↦y∈[0,1]，yyy为访问 POI 的概率。
City-Transfer Next POI to Search Recommendation
给定基础城市集合CB={cbase(i)}\mathcal{C_B}=\{c_{base}^{(i)}\}CB={cbase(i)}和目标城市集合CT={ctarget(j)}\mathcal{C_T}=\{c_{target}^{(j)}\}CT={ctarget(j)}，目标为转移基础城市数据中的知识，以提高目标城市的推荐绩效。
在元学习中，每个城市ccc的推荐被视为一个单一的任务（有它自己的数据集D\mathcal{D}D）。CB\mathcal{C_B}CB和CT\mathcal{C_T}CT划分为训练集Dtarin={Dbase(i)}\mathbb{D}_{tarin}=\{\mathcal{D}_{base}^{(i)}\}Dtarin={Dbase(i)}和测试集Dtest={Dtarget(i)}\mathbb{D}_{test}=\{\mathcal{D}_{target}^{(i)}\}Dtest={Dtarget(i)}。
假设用户有访问记录{r1,r2,⋯ ,rn}\{r_1,r_2,\cdots,r_n\}{r1,r2,⋯,rn}，m 为序列最小长度，则正样本为{(xi,yi)}\{(\mathbf{x}_i, y_i)\}{(xi,yi)}：
xi=(ui,histui,ri),yi=1histui=(r1,r2,⋯ ,ri−1),i=m+1,⋯ ,n\begin{aligned} \mathbf{x}_i &= (u_i, hist_u^i, r_i), \quad y_i = 1 \\ hist_u^i &= (r_1, r_2, \cdots, r_{i-1}), \quad i=m+1,\cdots, n \end{aligned} xihistui=(ui,histui,ri),yi=1=(r1,r2,⋯,ri−1),i=m+1,⋯,n
负样本中的候选 POI 是从城市的 POI 集中随机抽样的，并且没有出现在histuihist_u^ihistui中。
此外，每个元学习任务的数据集都有一个用于训练的支持集Dspt\mathcal{D}^{spt}Dspt和一个用于测试的查询集Dqry\mathcal{D}^{qry}Dqry。按时间顺序将每个用户的前kkk条记录放入Dspt\mathcal{D}^{spt}Dspt，其余放入Dqry\mathcal{D}^{qry}Dqry。
最后，论文的目标是利用训练数据集（基础城市CB\mathcal{C_B}CB的Dtrain\mathbb{D}_{train}Dtrain）来学习一个元学习器FFF，这样，给定一个测试数据集（目标城市CT\mathcal{C_T}CT）的Dspt\mathcal{D}^{spt}Dspt，FFF通过预测推荐器fff的参数θ\thetaθ，在Dqry\mathcal{D}^{qry}Dqry上最小化损失函数L\mathcal{L}L：
ω∗=argminω∑D=[Dspt,Dqry]∈DtestL(fθ,Dqry∣Dtrain,Dspt)s.t.θ=Fω(Dspt∣Dtrain)\begin{aligned} \omega^* &= \underset{\omega}{\arg\min} \sum_{\mathcal{D}=[\mathcal{D}^{spt}, \mathcal{D}^{qry}] \in \mathbb{D}_{test}} \mathcal{L} (f_\theta, \mathcal{D}^{qry} \vert \mathbb{D}_{train}, \mathcal{D}^{spt}) \\ s.t. \quad \theta &= F_\omega (\mathcal{D}^{spt} \vert \mathbb{D}_{train}) \end{aligned} ω∗s.t.θ=ωargminD=[Dspt,Dqry]∈Dtest∑L(fθ,Dqry∣Dtrain,Dspt)=Fω(Dspt∣Dtrain)
其中ω\omegaω和θ\thetaθ分别为FFF和fff的参数。
CHAML
Curriculum Hardness Aware Meta-Learning (CHAML)框架主要分为两个部分：
- base 推荐
- 拓展的 MAML
Base Recommender
base 推荐fθf_\thetafθ采用了 Deep Interest Network (DIN)，它包含三个模块，将样本特征xi=(ui,histui,ri)\mathbf{x}_i = (u_i, hist_u^i, r_i)xi=(ui,histui,ri)映射到y^i∈[0,1]\hat{y}_i\in[0,1]y^i∈[0,1]。
Embedding module
xi↦(ehist,econdi)\mathbf{x}_i \mapsto (\boldsymbol{e}_{hist}, \boldsymbol{e}_{condi})xi↦(ehist,econdi)
将 POI ID viv_ivi以及其类别，小时时间戳进行 Embedding，得到Eid,Ecate,EtimeE_{id}, E_{cate}, E_{time}Eid,Ecate,Etime，凭借后分别生成ehist,econdi\boldsymbol{e}_{hist}, \boldsymbol{e}_{condi}ehist,econdi
这里没有进行 user embedding，论文的解释是在地图搜索应用中通常没有用户信息及社交关系，同时用户 ID 在不同城市中不进行共享。
Attention module
(ehist,econdi)↦h(\boldsymbol{e}_{hist}, \boldsymbol{e}_{condi}) \mapsto \boldsymbol{h}(ehist,econdi)↦h
采用注意模块来捕捉候选记录和用户历史之间的偏好关系：
h=attention(ecandi,ehist)attention(K,V)=softmax(MLPatt([K;V;K−V;K⋅V]))V\begin{aligned} \boldsymbol{h} &= \text{attention}(\boldsymbol{e}_{candi}, \boldsymbol{e}_{hist}) \\ \text{attention}(K, V) &= \text{softmax}(MLP_{att}([K;V;K-V;K\cdot V]))V \end{aligned} hattention(K,V)=attention(ecandi,ehist)=softmax(MLPatt([K;V;K−V;K⋅V]))V
其中MLPattMLP_{att}MLPatt是一个两层的多层感知机；h\boldsymbol{h}h为隐藏层向量，[;][;][;]表示连接操作。
Output module
(h,ecandi)↦y^i(\boldsymbol{h}, \boldsymbol{e}_{candi}) \mapsto \hat{y}_i(h,ecandi)↦y^i
最后通过一个三层的多层感知机得到预测输出：
y^i=MLPrec([h;econdi])\hat{y}_i = MLP_{rec}([\boldsymbol{h}; \boldsymbol{e}_{condi}]) y^i=MLPrec([h;econdi])
Meta-Learning
为了实现对数据不足的多个冷启动城市的快速适应，论文将 MAML 扩展到现有场景中。
MAML 学习ω=θ0\omega=\theta_0ω=θ0，即 base 推荐fff的初始化，它可以在少量样本上通过少量的更新步骤适应新的任务。在每次迭代过程中 MAML 包含两个阶段：local update 和 global update。
Local update
首先，论文对一批基础城市B={c}⊂CB\mathcal{B}=\{c\}\subset \mathcal{C_B}B={c}⊂CB进行抽样，其中每个城市ccc都有其唯一的用户集合Uc\mathcal{U}_cUc和 POI 集合Vc\mathcal{V}_cVc。
从Dcspt\mathcal{D}_c^{spt}Dcspt和Dcqry\mathcal{D}_c^{qry}Dcqry中随机选取用户ui∼Uc(∣{ui}∣≪∣Uc∣)u_i \sim \mathcal{U}_c \quad (\vert\{u_i\}\vert\ll\vert\mathcal{U}_c\vert)ui∼Uc(∣{ui}∣≪∣Uc∣)，然后计算在Dcspt\mathcal{D}_c^{spt}Dcspt上的训练误差，并更新本地参数θ\thetaθ：
θc′=θ−α∇θLc(fθ,Dcspt)\theta_c' = \theta - \alpha\nabla_\theta\mathcal{L}_c(f_\theta, \mathcal{D}_c^{spt}) θc′=θ−α∇θLc(fθ,Dcspt)
其中L\mathcal{L}L为二值交叉熵损失函数，α\alphaα为本地学习率。
Global update
接着使用θc′\theta_c'θc′在每个Dcqry\mathcal{D}_c^{qry}Dcqry上计算测试损失，然后，对所有测试损失求和，通过一个梯度步长全局更新θ\thetaθ：
θ=θ−β∇θ∑c∈BLc(fθc′,Dcqry)\theta = \theta - \beta\nabla_\theta\sum_{c\in\mathcal{B}}\mathcal{L}_c(f_{\theta_c'}, \mathcal{D}_c^{qry}) θ=θ−β∇θc∈B∑Lc(fθc′,Dcqry)
其中β\betaβ为全局学习率。通过这种方式，在经过足够的元学习迭代后，可以学习到更可转移的θ\thetaθ初始化，以快速适应冷启动城市。
Hardness Aware Meta-Learning
为了使元学习模型更加适应城市转移问题，论文进一步考虑了地图搜索数据的特性
User-POI Distance in Map Search Data
在地图搜索场景中，用户可能会在较远位置就与 POI 进行交互，例如用户在从家中出发时就导航目的地
ei←[ei;di−dmeandstd]\boldsymbol{e}_i\leftarrow [\boldsymbol{e}_i;\frac{d_i-d_{mean}}{d_{std}}]ei←[ei;dstddi−dmean]
其中ei\boldsymbol{e}_iei表示原始用户记录；did_idi是相应的用户-POI 距离矩阵；dmean,dstdd_{mean}, d_{std}dmean,dstd是城市范围内距离的均值和方差。
Meta-Learning with Hardness Awareness
在随机抽样过程中，MAML 倾向于过拟合一些简单的模式（例如对某个 POI 的重复搜索），但是难以学习没有明显规律的搜索模式。此外，由于在目标城市的测试分布是未知的，但是在训练过程中明确这样的多样性有助于提高元学习的泛化能力，因此受到苦难样本挖掘的启发，论文提出了在线调整抽样策略，强迫模型在困难样本搜索中学习更多特征。
这里的「Hardness」是由模型在查询样本上的当前性能表现自我判断的。具体来说，元学习器通过当前迭代中每个城市的Dqry\mathcal{D}^{qry}Dqry的准确率来评估城市级别的困难度，在查询样本上评估用户级别的困难度。具体来说：
阶段 1：初始化一组任务Thard_city\mathcal{T}_{hard\_city}Thard_city，或承接阶段 2的数据。接着使用Thard_city\mathcal{T}_{hard\_city}Thard_city进行一个完整的元学习步骤，并对每个城市任务的用户BuB_uBu根据平均准确率{accu}\{acc_u\}{accu}进行排序，保留准确率最低的部分用户kuBuk_uB_ukuBu，接着在每个城市中重新选择一批新的用户组成Thard_user\mathcal{T}_{hard\_user}Thard_user：
{u}c∼p(Uc∣{accu}c)Thard_user∼p(T∣{u}c),c∈Bhard_city\begin{aligned} \{u\}_c &\sim p(\mathcal{U}_c \vert \{acc_u\}_c) \\ \mathcal{T}_{hard\_user} &\sim p(\mathcal{T} \vert \{u\}_c), \quad c\in\mathcal{B}_{hard\_city} \end{aligned} {u}cThard_user∼p(Uc∣{accu}c)∼p(T∣{u}c),c∈Bhard_city
阶段 2：在第二阶段，元学习器使用Thard_user\mathcal{T}_{hard\_user}Thard_user再次进行完整的元学习步骤，以提高对困难用户的泛化能力。类似于阶段 1，根据在Dqry\mathcal{D}^{qry}Dqry上的准确率{acct}\{acc_t\}{acct}对城市进行排序，保留准确率最低的部分城市kcBck_cB_ckcBc作为困难城市，并重新选择一些新城市作为Bhard_city\mathcal{B}_{hard\_city}Bhard_city。接着为每个城市随机选择一批新的用户，组成Thard_city\mathcal{T}_{hard\_city}Thard_city，它包含比之前更苦难的城市组合，并传递给阶段 1进行下一轮训练：
{c}∼p(CB∣{acct})Thard_city∼p(T∣c)\begin{aligned} \{c\} &\sim p(\mathcal{C_B \vert \{acc_t\}}) \\ \mathcal{T}_{hard\_city} &\sim p(\mathcal{T}\vert {c}) \end{aligned} {c}Thard_city∼p(CB∣{acct})∼p(T∣c)
综上所述，通过这种困难度感知元训练方式，元学习器逐渐找到最优θ0\theta_0θ0，推荐器fff可以更好地适应较难的地图搜索模式，从而使目标城市和用户的整体推荐性能提升。
City-level Sampling Curriculum
在上面的任务中，困难度是由元学习器自我判断的，但是如果有一个老师加以指导，会使得学习更加容易高效。
Difficulty Measurer
为了判断一个城市的困难度，论文将所有样本按照用户划分为训练集Dtrain\mathcal{D}^{train}Dtrain和测试集Dvalied\mathcal{D}^{valied}Dvalied，接着使用 base 推荐训练Dtrain\mathcal{D}^{train}Dtrain，通过准确率评分城市困难度δ\deltaδ，选择分数最低的城市作为困难城市：
δc∝−maxθΦ(fθ,Dcvalid∣Dctrain)\delta_c \propto -\underset{\theta}{\max} \Phi(f_\theta, \mathcal{D}_c^{valid} \vert \mathcal{D}_c^{train}) δc∝−θmaxΦ(fθ,Dcvalid∣Dctrain)
Single Step Scheduler for City Pool
对于所有基础城市CB={c1,c2,⋯ ,cN}\mathcal{C_B} = \{c_1,c_2,\cdots,c_N\}CB={c1,c2,⋯,cN}根据困难度和最大元学习迭代次数进行排序，论文定义了一个阶梯式调度函数g:[M]↦[N]g:[M] \mapsto [N]g:[M]↦[N]来决定城市序列C1′,⋯ ,CM′⊆CB\mathcal{C}_1',\cdots,\mathcal{C}_M' \subseteq\mathcal{C_B}C1′,⋯,CM′⊆CB：
g(i)=ξ1[i<η]⋅Ng(i)=\xi^{\mathbb{1}[i<\eta]}\cdot N g(i)=ξ1[i<η]⋅N
其中ξ\xiξ为初始状态城市比例；η\etaη为每步的迭代次数；1\mathbb{1}1为指标函数。
这部分说实话没看懂再干嘛，附录里的证明也没看，感觉有亿点点复杂。
The Algorithm of CHAML
论文整体算法如下：
实验
论文的数据集是百度地图的非公开数据集：
Result
Ablation Study
总结
论文整体感觉比较复杂，用到的东西也比较多，解决的是一个 POI 推荐的城市转移问题，虽然可能不会做这样的内容，但是还是有一定参考意义，特别是 hardness 这块。
参考资料
腾讯云开发者
