Efficient K-NN for Playlist Continuation

关键论述

原文引用 The core of our approach is a playlist-based nearest neighbor method, which recommends items from similar playlists. Our solution uses a modified cosine similarity metric that takes into account the popularity of the tracks.

基于播放列表的最近邻方法是本论文的核心,关键点在于基于特定任务(根据歌曲的流行度或者说共现)修改余弦相似度。

原文引用 The use of Inverse Document Frequency in information retrieval is justified by the fact that rare items define similarity better than common items. We utilize this idea to define Inverse Item Frequency: Two playlists are more likely similar if they include the same low popularity tracks than if they share tracks that a very large number of other lists also include.

TF-IDF是预处理文本、文档时的关键思想,详情请看
这里使用IDF(Inverse Document Frequency 逆文档频次)非常合理且巧妙,有助于缓解冷启动问题,因为某些列表中的音轨可能出现的频次极少,可能是小众或者是新歌。在计算两个列表的相似度时,如果都包含这种频次少的音轨,能表示这两个播放列表更加相似。

方法

基本思想是为所给的播放列表匹配最相似的播放列表,再进一步排序推荐。

符号 含义
suvs_{uv} 两个列表u,vu,v的相似度
suvαs^\alpha_{uv} 经过α\alpha扩大后的两个列表的相似度
ii 某个track(音轨)
r^u,i\hat{r}_{u,i} 预测的i对于播放列表u的相关性
Nk(u)N_k(u) 与播放列表u最相似的k个播放列表

预备定义

定义音轨ii对于播放列表uu的相关性:

r^u,i=vNk(u)suvrvivNk(u)suv(1) \hat{r}_{u,i}=\frac{\sum_{v\in N_k(u)}{s_{uv}\cdot r_{vi}}} {\sum_{v\in N_k(u)}{s_{uv}}} \tag{1}

其中rvir_{vi}是已知的音轨i对于播放列表v的相关度。

对于相似度的度量,本文使用常用的余弦相似度进行计算,两个播放列表的余弦相似度可以用下式计算:

suv=iIruirviRu2Rv2(2) s_{uv}=\sum_{i\in I}{\frac{r_ui r_vi}{||R_u||_2||R_v||_2}} \tag{2}

扩大和归一化的技巧

  • 扩大(amplification)
    引用自论文 Empirical analysis of predictive algorithms for collaborative filtering.
    将上述定义的suvs_{uv}改进为suvαs^\alpha_{uv},其中α>1\alpha>1,这样的话对于相似的播放列表,他们的相似度更大,增加了相似的播放列表的权重。
  • 规范化(nomalization)
    因为播放列表和其相似的列表之间的相似度Su=suvvNkuS_u={s_{uv}|v\in N_k{u}}可能差值非常大,因此在做扩大操作前进行规范化效果会更好,这里使用最小最大规范化。

基于IDF加权的技巧

将公式(2)(2)改进为下式,
suv=iI((fi1)ρ+1)1ruirviRu2Rv2(3) s_{uv}=\sum_{i\in I}{((f_i-1)^\rho+1)^{-1}}{\frac{r_{ui}r_{vi}}{||R_u||_2||R_v||_2}} \tag{3}

其中,fif_i是包含音轨ii的播放列表的数量,因此出现频次越高收到的惩罚越大。

对位置的加权

在公式(1)(1)中对于同一播放列表下的各音轨的相关度ruir_{ui}计算是相同权重的,此处,对这些音轨在播放列表中的位置进行加权(此技巧对于子任务9的提升非常大)。
r~ui=rui(1+max(l,pu(i))d)4)(() \widetilde{r}_{ui}=r_{ui}(1+\frac{max(l,p_u(i))}{d}) \tag(4)
其中,pu(i)p_u(i)是音轨ii在播放列表uu中的位置,l和d是超参数。

反思

以往打比赛的时候其实更多是对于算法的优化,对于数据预处理的优化,在此过程中忽视了对数据特性、数据分布详细分析,此外,对于业务的理解也不够到位。做学术的过程中可以大胆假设,更多尝试。本文的基本思想其实非常简单,就是传统的协同过滤,计算相似度,但是作者们结合播放列表的特性和实际业务的理解,对传统方法进行了改进。整个读下来,及其非常像KDD2018的最佳应用论文[1],出自Airbnb,其实就是对传统word2vec算法进行魔改,但是每个改进点都是针对业务和数据特性,并且有大量实验和结果支撑。

[1]Real-time Personalization using Embeddings for Search Ranking at Airbnb