近日，由阿里巴巴承办的 CIKM 2019 AnalytiCup 在北京圆满落幕，来自青岛大学和春秋航空的成员组成的团队 QDU 摘得了“用户兴趣高效检索”赛道的桂冠。
本文由 QDU 团队独家供稿，AI开发者号加工整理如下，希望给到开发者们一些经验与启发。
注：挑战赛共分为两个赛道，用户兴趣高效检索（Efficient User Interests Retrieval）和用户行为多样性预测（Predicting User Behavior Diversities in A Dynamic Interactive Environment），后者冠军方案请见今日推送二条。
CIKM AnalytiCup 介绍
CIKM 是中国计算机学会（CCF）推荐的数据库/数据挖掘/内容检索领域的 B 类会议。CIKM AnalytiCup 挑战赛是会议同期举行的国际数据挖掘比赛，今年由 CIKM、阿里妈妈、阿里巴巴达摩院、阿里巴巴算法大学、阿里云天池共同承办，挑战赛分为两个赛道，用户兴趣高效检索（Efficient User Interests Retrieval）和用户行为多样性预测（Predicting User Behavior Diversities in A Dynamic Interactive Environment）。QDU 团队在用户兴趣高效检索赛道中斩获冠军。
QDU 团队介绍
本次冠军团队 QDU 的参赛成员包括：
- 薛传雨，青岛大学大四学生，曾获得数据挖掘比赛冠军与季军。
- 张卓然，春秋航空算法工程师，曾多次获得数据挖掘比赛前十名的成绩。
- 吴舜尧，青岛大学助理教授，曾获得数据挖掘比赛冠亚军。
团队在本次竞赛上有几大主要优势：
- 团队队员有丰富的数据挖掘经验，积累了数据挖掘比赛的很多技巧。
- 团队成员从事推荐系统与复杂网络方面的研究，了解推荐系统的基本算法并有能力改进算法。
- 团队成员尝试将统计领域最新理论与方法应用于数据挖掘比赛，这些尝试为模型的性能与精度带来了一定提升。
赛题介绍
用户兴趣高效检索聚焦在解决大规模推荐中用户兴趣检索的问题上，任务要求在很短时间内从千万级的商品库 C 中为用户挑选出最可能感兴趣的 k 个商品。复赛还要求为每个用户进行推荐时的时间复杂度小于 O(n)。其中，
。此外，复赛提交的方案需在一个 8 核 60G P100 的 GPU 容器中对 6 万线上用户进行推荐，限时 1 小时。不仅对复杂度有要求，对内存、CPU 等资源也有限制。
数据集包括用户行为文件、用户信息文件与商品信息文件。用户信息包含用户 ID、性别、年龄与购买力，商品信息包含商品 ID、类目 ID、店铺 ID 与品牌 ID（若有商品价格，有望提高推荐效果），用户行为涉及 16 天（由某个周五开始）的用户对商品的行为日志。
评测指标
比赛要求预测一组给定用户在第 17 天感兴趣的商品列表。需要注意的是，初赛与复赛的方案评价方式有较大差别：
（1）初赛提供了待预测用户的信息、第 1~16 天的行为日志及感兴趣的商品信息，参赛选手可以仅适用待预测用户的信息设计方案，将预测结果提交到线上进行评测，评价指标为
与
的加权均值，Gu 为用户 u 的真实未来兴趣商品集合，Hu 为用户 u 的历史行为类目商品子集，
为选手产出的用户 u 的未来兴趣商品预测集合。其中，Novel-Recall@50 要求推荐的商品不能与历史感兴趣商品属同一类别，因而难度很大。
（2）复赛将待预测的用户信息等文件置于线上，不允许打印相关信息等内容，而且对运行时间及资源又添加了限制。利用线上用户行为日志等信息建模效果尚可，但复杂度可能会超出要求，因而很多信息及模型需要在线下统计、训练。此外，评价指标变为了
，Hu 为用户 u 的历史行为商品集合。该指标比初赛简单些，因为可以推荐同类商品，这在真实业务及该数据集中都较常见。
赛题解析及相关方法介绍
本赛道由阿里巴巴集团阿里妈妈事业部营销技术团队出题。从赛题的设置来看，本次赛题主要想要解决的问题，和实际大规模推荐系统中的 Match 阶段面临的挑战非常类似，即如何在线上系统实际资源有限的情况下，从大规模候选集中迅速、准确地找到一个较小的用户兴趣子集，以供后续模块继续处理。此前，由于客观存在的算力资源限制，学术界及工业界对这一问题的研究，大部分集中在如何提升检索效率上。
在推荐系统发展初期，解决这一问题的主要思路为采用“协同过滤”的方法。这一类方法的中心思想为：“相似”的用户，可能会对“相似”的商品感兴趣。因此，在实际应用中，这类方法通常首先会通过各种相似性计算规则，将商品聚类到相似性 Tag 下；然后在召回阶段，通过用户输入首先召回一些 Tag，再将 Tag 下挂载的商品作为召回集输出。比如，经典的 Item-CF[5] 方法通过相似性计算，首先得到每个商品的相似商品；然后在进行推荐时，把用户历史访问过商品的相似商品作为召回集。这类方法在实现上较为简单，但是基于规则的相似性计算及“用户-Tag-商品”的两段式召回模式，限制了整体的精确度。另外，由于整体的召回思路是基于历史行为找相似，因此召回结果在多样性和发现性上表现欠佳。
随着兴趣建模及索引技术的发展，学术界和工业界对召回系统的研究逐步过渡到了第二阶段，即通过基于向量的兴趣模型加向量相似性检索来实现一段式召回。在索引端，日益完善的向量相似性检索技术，为这一方案的应用提供了效率上的保障；在模型端，其核心思想是通过训练用户兴趣模型，使得模型产出的用户向量与商品向量之间的距离度量（如内积距离等），能表示用户对商品的兴趣度。这类方法首次实现了对大规模候选集的一段式召回，其代表性的工作为 YouTube-DNN 模型[6]。然而，由于对向量相似性检索的依赖，这一方案在兴趣度量方面受到了一定的限制，只能使用内积模型来度量用户对商品的兴趣，一些能在排序阶段使用的更先进的模型结构，以及一些用户-商品的交叉特征等，无法被有效利用。
当前，随着 GPU、人工智能计算芯片等硬件的快速发展，系统整体能使用的算力资源，相比之前有了极大的提升。而更强大的基础算力，促使我们在面对这一问题时需要重新思考：如何设计新的算法，使其能够尽可能地利用丰富的算力资源，来提升召回的精准度。面对这一问题，阿里妈妈技术团队提出了一种基于可学习的树索引加任意检索模型的深度树匹配方法[7,8]。该方法使用了树索引结构来解决检索的效率问题，因为基于树的检索算法时间复杂度为对数级别，所以即使面对超大规模商品库也能够胜任；以在树索引结构中检索相关商品为目标，得益于树检索天然的复杂度优势及 GPU 等硬件提供的强劲算力，任意的深度模型都可以被用作检索模型，来学习如何在树索引中检索目标，而不局限于内积模型的形式，因此打开了模型能力的天花板。此外，树索引和检索模型，可以在数据驱动的方式下进行联合优化来达到系统整体效能的最优。深度树匹配方案在阿里妈妈展示广告核心资源位已经全面应用，取得了显著的实际业务提升。
主办方从工业界实践中面临的实际问题与挑战出发，希望参赛选手能结合业界当前技术的整体发展阶段，思考如何在召回阶段尽可能地利用系统算力资源，来实现最优检索的目标，进而孕育出解决问题的新方法。
核心思路
初赛方案仅基于规则做了 Match 阶段，里面有些技巧，感兴趣的同学可以关注薛传雨的 Github（https://github.com/ChuanyuXue/CIKM-2019-AnalytiCup），之后会在上面发布代码。下面重点阐述复赛方案。图 1 给出了推荐系统的经典流程，先从千万级商品库中为指定用户召回几百或几千个候选商品，再建模为候选商品排序，选出少量商品作为最终的推荐列表。
图1 推荐系统经典流程数据分析与探索
数据分析与探索对方案设计有重要的指导作用。下面介绍几个关键的分析。在做 EDA 时，数据集被切分为了两部分，第 1~14 天日志被视为“历史”行为，第 15 天日志视为“未来”行为，从而可以分析对“未来”行为有重要影响的“历史”行为特点。
图 2 用户对“历史”感兴趣同类商品的“未来”行为统计分析。用户行为共有 4 种类型：’pv’（浏览）、’fav’（喜欢）、’cart’（加入购物车）和’buy’（购买）。按照感兴趣程度，可将这4种类型的权重依次设为 1、2、3、4（论坛发布的初赛 baseline 即是这样设置，效果尚可）。图 2 先获取了用户“历史”感兴趣的商品类别，然后统计了“未来”对历史感兴趣的同类别商品的行为。图 2 表明“未来”感兴趣的商品（出现在第 15 天日志中的商品）几乎不会是以往购买过的同类商品。因而，在复赛方案中将’buy’的权重设为 1。实际上，4 种行为的权重仍可调优，但限于时间和精力未做。
图 3 “未来”感兴趣商品在第 1~14 天被感兴趣的次数如图 3 所示，“未来”感兴趣商品在第 14 天被感兴趣的次数组多，距第 14 天越远次数越少。因而，考虑时间因素对行为重要性的影响，按下式调整行为权重：
其中，
是四种行为的权重，Tu,i 代表距最大时间戳 Dmax 的远近，Ru,i 是考虑时间因素后评估用户 u 对商品 i 的感兴趣程度。
图 4 没有区分行为的种类，统一分析了用户在“未来”是否仍会对“历史”感兴趣的商品类别及店铺感兴趣。如图 4-(a) 所示，用户在“未来”仍会对“历史”感兴趣的商品类别有较高兴趣；图 4-(b) 则表明，用户在“未来”对历史感兴趣的店铺有较低的兴趣。进而，针对类别/店铺提取了一些特征，详见对排序阶段的介绍。
(a)
(b)
图 4 用户是否仍会对“历史”感兴趣的商品类别及店铺感兴趣。
召回阶段
图 5 基于 Item CF 的召回流程召回的策略有很多，即使是基于规则的策略效果也可以。在复赛后期，团队花费了很大精力实现了一种 Item CF 算法，效果也有明显提升。图 5 给出了基于 Item CF 做召回的流程，先利用庞大的历史日志统计 item-item 相似性矩阵，再结合目标用户的历史行为做推荐。实现的难点在于对约 8000 万历史日志做统计的复杂度太高，需要做优化代码、做并行化处理。
如图 6 所示，将用户分为了若干组，并行处理每组内 item-item 共现频率的统计，最终将与每个商品最相似性的 500 个商品存在字典中。实际上，对复赛训练集统计后，发现字典中键值数仅有 40 多万。此外，为了提高效率，团队使用了 Cython 实现统计共现频率的代码。整个流程较复杂，感兴趣的同学可以看随后开源的代码。
图 6 并行统计 item-item 相似性，并转存为字典Item CF 相似性指标关乎召回的效果。在实现时团队借鉴了 2015 年腾讯 SIGMOD 论文 [1]。在 9 月初，按照关联规则中置信度计算 Item CF 相似性如下：
其中，代表对商品感兴趣的用户集合。显然，
。基于该指标做召回，线上效果为0.045。
在此基础上，考虑到用户活跃度（感兴趣的商品数）对相似性的影响，改进了上述指标：
其中，是全体用户集合，Ui 是对商品 i 感兴趣的用户集合；Wu 代表用户 u 对相似性的贡献度，
代表用户感兴趣的商品集合。当 w—>1 时，
等价于
。基于改进指标做召回，并做了些额外处理，线上效果为 0.053。
排序阶段
召回阶段获得少量（300 或 500）候选商品后，可以构建排序模型获得最终的推荐列表。我们将排序任务转化为二类判别问题。在建模前，需要切分数据集。如图 7 所示，利用第 1-15 天数据做召回、生成特征，利用第 16 天的数据生成标签，从而生成线上训练集；利用 1-16 天数据做召回、生成特征，生成线上测试集，加载训练后的模型及相关文件完成预测。
需要特别注意的是，训练集中的正样本和负样本都是从召回列表中生成的，而不是将每个用户感兴趣的商品都拿出来做正样本。这是因为，很多用户感兴趣的商品对应的特征取值都无法统计，使得这些正样本失去了统计意义，对训练模型有负面影响。另一个赛道的亚军也是这样做的，他的解释也很好，“希望建模样本与召回样本同分布”。本赛道很多同学都未能建模做 Ranking，应该是没能发现采样的技巧。
图 7 排序阶段划分数据图 8 为提取的特征列表，只有 64 个。其中，Item CF 的相似性特征是强特征。最终使用了 Catboost 和 Lightgbm 建模。Catboost 对过拟合的处理较好，使用了全部特征（线上效果为 0.0616）；Lightgbm 使用全部特征效果不佳，故做了特征选择，最终只使用了 36 个特征。
图 8 特征列表（共 64 个）为了减少特征的数量，在比赛中使用了多种特征选择方法。虽然 xgboost、lightgbm、catboost 可以做特征重要性分析，但很多同学可能注意到把选出的重要特征给梯度提升树模型建模并无明显提升。我们做特征选择的思路是“劣汰优胜”，先基于独立性检验剔除关联弱的特征，再从剩余特征中选择重要性高的特征。两变量独立是指两变量既不存在线性相关性，也不存在非线性关联。我们采用 Mean Variance Test[2,3] 做“劣汰”，这是首都师范大学崔恒建教授 2015 年发表于统计领域顶刊 JASA 的工作，2018 年进行了拓展，可用于做独立性检验及特征选择。该方法可检验一个离散型变量与一个连续型变量间是否独立，对变量的分布无假定（Distribution free），并且计算简单（只是计数）。这里仅列出其部分理论（图 9），感兴趣的同学可以交流，该方法已被 Chuanyu 做成了工具包，已开源在他的 github。此外，团队成员在 IJCAI 2018 和资金流入流出预测课程视频（天池 AI 课程，之后可能上线）中都使用 Mean Variance Index 做过特征选择，效果都不错。
图 9 Mean Variance Test简介最后，团队进行了简单的模型融合。为了提高稳健性，依次采用了调和平均值、几何平均值和算数表均值（图 10），线上效果为 0.0622。
图 10 模型融合其他尝试
还有一些基于规则的策略及其他方案没有介绍。例如，基于同类商品的规则做召回、基于同店铺的规则做召回、基于 word2vector 的思路做召回（借助 faiss）、基于 MinHash LSH 做 Item CF、取最近 100 条用户行为做统计等等。感兴趣的同学可以交流。
比赛收获与感想
参加 CIKM 挑战赛的原因有二：（1）希望验证自身技术和研究价值；（2）参加会议，与专家交流，帮助薛传雨申请 2020Fall 的博士或研究型硕士（可联系 cs_xcy@126.com）。受限于复赛任务要求，我们没能在比赛中使用开发的推荐系统框架（一种基于组间效应的增量推荐系统框架[4]）。
想法比套路重要得多。大家在做比赛时，应该把精力放在数据分析与探索，从而提取有用的规则，利用规则进行初步想法的验证；进而，基于规则生成特征，再考虑建模、模型融合。其次要敢于尝试新的思路，比起在原来的方案上调整参数，对算法进行改进或引入新算法可能会带来更有大的提升。另一方面，建议大家学好统计，读读统计学领域的论文，有助于加深对机器学习的理解。此外，在比赛后几天，要休息好、能沉住气，不能过于急躁。最后，仅仅提高技术是不足够的，学好英语、提高表达能力也很关键。
参考文献
[1] Y. Huang et al. Tencentrec: Real-time stream recommendation in practice. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 2015: 227-238.
[2] H. Cui et al. Model-free feature screening for ultrahigh dimensional discriminant analysis. Journal of the American Statistical Association. 2015, 110(510): 630-641.
[3] H. Cui et al. A Distribution-Free Test of Independence and Its Application to Variable Selection. arXiv preprint arXiv:1801.10559, 2018.
[4] C. Xue et al. An Incremental Group-Specific Framework Based on Community Detection for Cold Start Recommendation. IEEE Access. 2019, 7: 112363-112374.
