基于pitf的个性化标签推荐摘要关键词引言相关工作个性化标签推荐非个性化标签推荐张量分解模型成对交互模型个性化标签推荐形式化定义数据分析标签推荐的贝叶斯个性化排序bprbpr最优化准则bpr学习算法张量分解模型塔克分解模型tdtf规范化分解模型cdtf成对交互张量分解模型pitftdcd和pitf之间的关系实验评价数据集评价方法实验结果学习运行时间预测质量ecmlpkdd 2009知识发现挑战赛结论和未来工作基于pitf的个性化标签推荐摘要在很多最近的网站中，标签扮演了一个重要的角色。推荐系统在用户想要给某个产品打标签时向其推荐他可能会使用的标签。基于tucker分解(td)模型的分解模型已经显示出了较高的性能，其标签推荐质量优于其它方法如pagerank，folkrank和协同过滤等等。td模型的问题在于三次核张量会导致在预测和学习时候的三次方的时间复杂度。
本文我们给出分解模型pitf(pairwise interaction tensor factorization，成对交互张量分解)，这是一种特殊的td模型，但是在学习和预测时的时间复杂度是线性的。pitf可以对用户、产品和标签之间的两两交互进行准确建模。之前用于产品推荐的贝叶斯个性化排序(bpr)准则被用于学习该模型。在真实数据集上的实验表明pitf模型在运算时间上远远优于传统td模型，甚至能得到更好的预测精度。除了本文的实验外，pitf还赢得了ecml/pkdd 2009知识发现竞赛中基于图的标签推荐的奖项。
关键词标签推荐，张量分解，个性化，推荐系统
引言标签是web 2.0时代的一个重要特征。它允许用户给产品/资源如音乐，图片和书签用关键词进行注释。标签帮助用户组织他的项目，促进浏览和搜索行为。标签推荐系统通过向用户推荐他可能用于一件产品的标签集合从而辅助用户的标记过程。个性化标签系统在推荐时会考虑到用户过去的标记行为。这意味着每个用户都被推荐一个个性化标签列表：也就是推荐的标签列表取决于用户和产品。由于不同的用户会使用不同的标签标记同一个项目因此需要进行个性化。last.fm网站使用的是非个性化标签推荐系统，但是用户还是会使用不同的标签标记音乐。文献[18]给出了一个实证例子，表明最近的个性化标签推荐系统优于任何非个性化标签推荐系统的理论上的性能上限。
本文工作基于最近的使用分解模型的个性化标签推荐模型。这些模型如高维奇异值分解(hosvd)和排序张量分解(rtf)都是基于tucker分解模型。rtf已经表现出了很高的预测精度。使用完全tucker分解模型的缺陷在于在分解维度上模型方程是三次方的。这使得td模型较难应用于中等规模和大型数据集。本文我们介绍一种新的分解模型，该模型对用户、产品和标签之间的两两交互关系进行准确建模。该摸想的优势在于模型的计算复杂度是线性的，使得其可以在高维数据上进行计算。在统计学中，还有另外一种张量分解方法也有着线性的计算复杂度称作正规分解(canonical decomposition, cd)，也称作并行因子分析(parallel factor analysis, parafac)[2]。后面我们会说明我们的模型是cd和td模型的特例。我们的实验结果也表明我们的两两交互模型在预测精度上明显优于cd模型，在运行时间上也略优于cd。此外，为了学习一般化的标签推荐模型，我们将贝叶斯个性化排序优化准则进行改进以适应标签推荐。
总体上，我们的贡献在于以下几点：
1. 我们将贝叶斯个性化排序优化准则(bpr-opt)[17]进行了扩展以适应标签任务，并提供了一个基于bootstrap抽样的随机梯度下降学习算法。该优化准则和学习算法是通用的而不限于td分解模型。
2. 我们提出的pttf分解模型有着线性的预测时间复杂度，并分析了pitf模型与一般的tucker分解模型和正规化分解模型之间的关系。
3. 我们的实验表明我们的bpr-pitf模型的性能在运行时间上优于预测质量最高的方法rtf-tf，计算复杂度从o(k3)降到o(k)——其中k为分解维度。此外，bpr-pitf方法在bibsonomy数据集上跟rtf-td效果相当，而在更大的last.fm数据集上甚至要优于rtf-td方法。
相关工作个性化标签推荐个性化标签推荐是推荐系统中近来的一个热门话题。hotho等人便引进了pagerank的改进版本folkrank[5]。
非个性化标签推荐张量分解模型成对交互模型个性化标签推荐个性化标签推荐是给用户推荐一个用于注释（如，描述）某件产品的标签列表。例如，在一个音乐网站上，一个听众（用户）想要给一首音乐（产品）打上标签，系统给他推荐了他可能想要用于标记这首歌的关键词列表。为了推断这个列表，一个个性化标签推荐系统可以使用系统中的历史数据也就是过去的标记行为。例如，推荐系统可以利用用户过去给相似的产品打过的标签，或者更一般化地，利用相似用户给相似产品打过的相似标签。
形式化定义为了形式化描述个性化标签推荐问题，我们使用[18]中的数学符号：u为所有用户集合，i是所有产品集合，t是所有标签集合。历史标签信息由s?u×i×t给定。由于这是一个分类变量上的三元关系，因此s可以看作是一个三维张量（如图1所示），s中的三元组为历史观测值。对于标签推荐而言，我们的任务是，对于向一个给定用户-产品对(u,i)，推荐一个标签列表。按照[7]的描述，我们称这样一个组合(u,i)为一个帖子(post)，并定义所有可观测的帖子如下：
ps:={(u,i)|?t∈t:(u,i,t)∈s}
ps可以视作根据or操作s在用户/产品维度上的二维映射。
对给定帖子(u,i)推荐标签的任务可以形式化描述为一个排序问题，也就是预测>u,i?t×t
这意味着排序>u,i必须满足：
?t1,t2∈t:t1≠t2?t1>u,it2∨t2>u,it1(1)
?t1,t2∈t:t1>u,it2∨t2>u,it1?t1=t2(2)
?t1,t2,t3∈t:t1>u,it2∨t2>u,it3?t1>u,it3(3)
其中(1)式为总体性，(2)为反对称性，(3)为传递性。本文所有模型都是预测一个评分函数y^:u×i×