【论文阅读】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 数据有限，无法充分利用数据。

论文期望将从其他数据丰富的城市所学到的知识，转移到冷启动城市的推荐任务中。这项任务主要面对两个挑战：

1. 不同城市之间的共享数据极其有限；
2. 不同城市不同用户的地图搜索模式具有很大的多样性，给推荐知识的转移带来了很大的困难。

为了同时解决这两个挑战，论文提出了一个新颖的 Curriculum Hardness Aware Meta-Learning（CHAML）框架，通过将元学习和非均匀采样策略纳入下一个 POI 搜索推荐，来缓解数据稀少和样本多样性问题。

论文主要贡献：

1. 第一个探索 POI 推荐中的城市转移问题，并通过元学习解决这个问题；
2. 提出了一个新颖的 Curriculum Hardness Aware Meta-Learning（CHAML）框架，通过增强元学习器的用户和城市层面的硬样本挖掘和城市层面的课程学习，缓解了冷启动城市的数据稀缺和样本多样性问题。

问题描述

假设每个城市都有其唯一的用户集合$\mathcal{U}$和 POI 集合$\mathcal{V}$，并且不共享任何共同的用户或 POI。

（record）$r=(v,t,l)$为用户$u$的一条记录，表示在$t$时刻访问了 POI $v$，其位置为$l$。

（user history）$hist_u = \{ r_1,r_2,\cdots,r_n \}$为用户访问序列。

（next POI recommendation）$f:(u, hist_u, t_{n+1}, l_{n+1}, v_{candi}) \mapsto y\in[0,1]$，$y$为访问 POI 的概率。

City-Transfer Next POI to Search Recommendation

给定基础城市集合$\mathcal{C_B}=\{c_{base}^{(i)}\}$和目标城市集合$\mathcal{C_T}=\{c_{target}^{(j)}\}$，目标为转移基础城市数据中的知识，以提高目标城市的推荐绩效。

在元学习中，每个城市$c$的推荐被视为一个单一的任务（有它自己的数据集$\mathcal{D}$）。$\mathcal{C_B}$和$\mathcal{C_T}$划分为训练集$\mathbb{D}_{tarin}=\{\mathcal{D}_{base}^{(i)}\}$和测试集$\mathbb{D}_{test}=\{\mathcal{D}_{target}^{(i)}\}$。

假设用户有访问记录$\{r_1,r_2,\cdots,r_n\}$，m 为序列最小长度，则正样本为$\{(\mathbf{x}_i, y_i)\}$：

$$\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}$$

负样本中的候选 POI 是从城市的 POI 集中随机抽样的，并且没有出现在$hist_u^i$中。

此外，每个元学习任务的数据集都有一个用于训练的支持集$\mathcal{D}^{spt}$和一个用于测试的查询集$\mathcal{D}^{qry}$。按时间顺序将每个用户的前$k$条记录放入$\mathcal{D}^{spt}$，其余放入$\mathcal{D}^{qry}$。

最后，论文的目标是利用训练数据集（基础城市$\mathcal{C_B}$的$\mathbb{D}_{train}$）来学习一个元学习器$F$，这样，给定一个测试数据集（目标城市$\mathcal{C_T}$）的$\mathcal{D}^{spt}$，$F$通过预测推荐器$f$的参数$\theta$，在$\mathcal{D}^{qry}$上最小化损失函数$\mathcal{L}$：

$$\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}$$

其中$\omega$和$\theta$分别为$F$和$f$的参数。

CHAML

Curriculum Hardness Aware Meta-Learning (CHAML)框架主要分为两个部分：

• base 推荐
• 拓展的 MAML

Base Recommender

base 推荐$f_\theta$采用了 Deep Interest Network (DIN)，它包含三个模块，将样本特征$\mathbf{x}_i = (u_i, hist_u^i, r_i)$映射到$\hat{y}_i\in[0,1]$。

Embedding module

$\mathbf{x}_i \mapsto (\boldsymbol{e}_{hist}, \boldsymbol{e}_{condi})$

将 POI ID $v_i$以及其类别，小时时间戳进行 Embedding，得到$E_{id}, E_{cate}, E_{time}$，凭借后分别生成$\boldsymbol{e}_{hist}, \boldsymbol{e}_{condi}$

这里没有进行 user embedding，论文的解释是在地图搜索应用中通常没有用户信息及社交关系，同时用户 ID 在不同城市中不进行共享。

Attention module

$(\boldsymbol{e}_{hist}, \boldsymbol{e}_{condi}) \mapsto \boldsymbol{h}$

采用注意模块来捕捉候选记录和用户历史之间的偏好关系：

$$\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}$$

其中$MLP_{att}$是一个两层的多层感知机；$\boldsymbol{h}$为隐藏层向量，$[;]$表示连接操作。

Output module

$(\boldsymbol{h}, \boldsymbol{e}_{candi}) \mapsto \hat{y}_i$

最后通过一个三层的多层感知机得到预测输出：

$$\hat{y}_i = MLP_{rec}([\boldsymbol{h}; \boldsymbol{e}_{condi}])$$

Meta-Learning

为了实现对数据不足的多个冷启动城市的快速适应，论文将 MAML 扩展到现有场景中。

MAML 学习$\omega=\theta_0$，即 base 推荐$f$的初始化，它可以在少量样本上通过少量的更新步骤适应新的任务。在每次迭代过程中 MAML 包含两个阶段：local update 和 global update。

Local update

首先，论文对一批基础城市$\mathcal{B}=\{c\}\subset \mathcal{C_B}$进行抽样，其中每个城市$c$都有其唯一的用户集合$\mathcal{U}_c$和 POI 集合$\mathcal{V}_c$。

从$\mathcal{D}_c^{spt}$和$\mathcal{D}_c^{qry}$中随机选取用户$u_i \sim \mathcal{U}_c \quad (\vert\{u_i\}\vert\ll\vert\mathcal{U}_c\vert)$，然后计算在$\mathcal{D}_c^{spt}$上的训练误差，并更新本地参数$\theta$：

$$\theta_c' = \theta - \alpha\nabla_\theta\mathcal{L}_c(f_\theta, \mathcal{D}_c^{spt})$$

其中$\mathcal{L}$为二值交叉熵损失函数，$\alpha$为本地学习率。

Global update

接着使用$\theta_c'$在每个$\mathcal{D}_c^{qry}$上计算测试损失，然后，对所有测试损失求和，通过一个梯度步长全局更新$\theta$：

$$\theta = \theta - \beta\nabla_\theta\sum_{c\in\mathcal{B}}\mathcal{L}_c(f_{\theta_c'}, \mathcal{D}_c^{qry})$$

其中$\beta$为全局学习率。通过这种方式，在经过足够的元学习迭代后，可以学习到更可转移的$\theta$初始化，以快速适应冷启动城市。

Hardness Aware Meta-Learning

为了使元学习模型更加适应城市转移问题，论文进一步考虑了地图搜索数据的特性

User-POI Distance in Map Search Data

在地图搜索场景中，用户可能会在较远位置就与 POI 进行交互，例如用户在从家中出发时就导航目的地

$\boldsymbol{e}_i\leftarrow [\boldsymbol{e}_i;\frac{d_i-d_{mean}}{d_{std}}]$

其中$\boldsymbol{e}_i$表示原始用户记录；$d_i$是相应的用户-POI 距离矩阵；$d_{mean}, d_{std}$是城市范围内距离的均值和方差。

Meta-Learning with Hardness Awareness

在随机抽样过程中，MAML 倾向于过拟合一些简单的模式（例如对某个 POI 的重复搜索），但是难以学习没有明显规律的搜索模式。此外，由于在目标城市的测试分布是未知的，但是在训练过程中明确这样的多样性有助于提高元学习的泛化能力，因此受到苦难样本挖掘的启发，论文提出了在线调整抽样策略，强迫模型在困难样本搜索中学习更多特征。

这里的「Hardness」是由模型在查询样本上的当前性能表现自我判断的。具体来说，元学习器通过当前迭代中每个城市的$\mathcal{D}^{qry}$的准确率来评估城市级别的困难度，在查询样本上评估用户级别的困难度。具体来说：

阶段 1：初始化一组任务$\mathcal{T}_{hard\_city}$，或承接阶段 2的数据。接着使用$\mathcal{T}_{hard\_city}$进行一个完整的元学习步骤，并对每个城市任务的用户$B_u$根据平均准确率$\{acc_u\}$进行排序，保留准确率最低的部分用户$k_uB_u$，接着在每个城市中重新选择一批新的用户组成$\mathcal{T}_{hard\_user}$：

$$\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}$$

阶段 2：在第二阶段，元学习器使用$\mathcal{T}_{hard\_user}$再次进行完整的元学习步骤，以提高对困难用户的泛化能力。类似于阶段 1，根据在$\mathcal{D}^{qry}$上的准确率$\{acc_t\}$对城市进行排序，保留准确率最低的部分城市$k_cB_c$作为困难城市，并重新选择一些新城市作为$\mathcal{B}_{hard\_city}$。接着为每个城市随机选择一批新的用户，组成$\mathcal{T}_{hard\_city}$，它包含比之前更苦难的城市组合，并传递给阶段 1进行下一轮训练：

$$\begin{aligned} \{c\} &\sim p(\mathcal{C_B \vert \{acc_t\}}) \\ \mathcal{T}_{hard\_city} &\sim p(\mathcal{T}\vert {c}) \end{aligned}$$

综上所述，通过这种困难度感知元训练方式，元学习器逐渐找到最优$\theta_0$，推荐器$f$可以更好地适应较难的地图搜索模式，从而使目标城市和用户的整体推荐性能提升。

City-level Sampling Curriculum

在上面的任务中，困难度是由元学习器自我判断的，但是如果有一个老师加以指导，会使得学习更加容易高效。

Difficulty Measurer

为了判断一个城市的困难度，论文将所有样本按照用户划分为训练集$\mathcal{D}^{train}$和测试集$\mathcal{D}^{valied}$，接着使用 base 推荐训练$\mathcal{D}^{train}$，通过准确率评分城市困难度$\delta$，选择分数最低的城市作为困难城市：

$$\delta_c \propto -\underset{\theta}{\max} \Phi(f_\theta, \mathcal{D}_c^{valid} \vert \mathcal{D}_c^{train})$$

Single Step Scheduler for City Pool

对于所有基础城市$\mathcal{C_B} = \{c_1,c_2,\cdots,c_N\}$根据困难度和最大元学习迭代次数进行排序，论文定义了一个阶梯式调度函数$g:[M] \mapsto [N]$来决定城市序列$\mathcal{C}_1',\cdots,\mathcal{C}_M' \subseteq\mathcal{C_B}$：

$$g(i)=\xi^{\mathbb{1}[i<\eta]}\cdot N$$

其中$\xi$为初始状态城市比例；$\eta$为每步的迭代次数；$\mathbb{1}$为指标函数。

这部分说实话没看懂再干嘛，附录里的证明也没看，感觉有亿点点复杂。

The Algorithm of CHAML

论文整体算法如下：

实验

论文的数据集是百度地图的非公开数据集：

Result

Ablation Study

总结

论文整体感觉比较复杂，用到的东西也比较多，解决的是一个 POI 推荐的城市转移问题，虽然可能不会做这样的内容，但是还是有一定参考意义，特别是 hardness 这块。

参考资料

• [1] Curriculum Meta-Learning for Next POI Recommendation
• [2] Deep Interest Network for Click-Through Rate Prediction
• [3] Model-agnostic meta-learning for fast adaptation of deep networks