Kirell Benzi,

Vassilis Kalofolias,

Xavier Bresson and Pierre Vandergheynst

Signal Processing Laboratory 2 (LTS2),

Swiss Federal Institute of Technology (EPFL)

代码参见：https://github.com/hxsylzpf/recog

摘  要

本文正式地形式化一个全新的的歌曲推荐算法，其将歌曲推荐的问题转化为矩阵补全的问题来考虑，并通过基于非负矩阵分解（non-negative matrix factorization, NMF）的协同过滤算法以及图上的结合图的全变分（total variation, TV）的基于内容的过滤方法相结合来解决这个问题。相关的图通过使用音频、元数据以及社交特征等丰富的信息的结合，对歌单的邻接信息以及歌曲的相似度信息进行编码。我们证明，我们提出的这个融合了几种知名的方法的混合推荐系统，有着广阔的应用前景，并在效果上超过融合的相关算法。通过在真实数据上进行的实验，我们证实了我们的模型能仅仅根据低秩矩阵的信息或者基于图的信息以及两者的结合进行歌曲的推荐。

关键字：推荐系统，图，非负矩阵分解，全变分，音频特征

一 引言

在 Netflix上推荐电影，在Facebook上推荐好友，或者在LinkedIn上推荐工作等任务在过去几年中吸引了越来越多的关注。大部分Netflix奖的获得者喜爱用的著名的低秩矩阵分解算法需要明确的用户评级作为输入。一些其他相似的方法则通过用户对物品的操作来反映用户对物品的偏好，以致力于解决用户的不明确的反馈问题。具体到歌曲和歌单推荐问题，也已经有了各种不同的方法，其中既有单纯的基于内容的方法，也有各种混合的模型。最近，图的正则化被提出，用来提高矩阵补全算法的效果。

本文的主要贡献在以下几个方面：

l  设计并实现了一个数学上的融合协同过滤以及内容过滤的声音混合系统；

l  介绍了一个新的图正则化项（TV），在推荐系统的背景下，其效果要优于广泛应用的 Tikhonov 正则化；

l  一个良好定义的基于近端分裂方法的迭代优化模式。

大量的实验证明我们提出的推荐系统具有很好的表现。

二 本文的歌曲推荐算法

1. 歌曲推荐算法

假设我们有n个歌单，每个列表都包含m首歌中的其中一部分。我们定义矩阵C∈{0,1}^n×m，矩阵中的元素 C_ij 为 1 则表示歌单 i 中包含歌曲 j，否则为 0。我们再定义一个权重矩阵Ω∈{0,1}^n×m，当输入的 C_ij 可能为 1 时，Ω_ij=1，否则等于一个很小的值 ε（我们使用的 ε=0.1）。这里应用了不明确反馈问题的思路。在矩阵 C 中一个元素为 0 不代表这首歌与这个歌单无关，而是更可能不相关。

训练阶段的目标是找到一个近似的低秩表示，使AB ≈ C，其中A ∈ R₊^n×r，B ∈R₊^r×m都是非负的，且 r 很小。这个问题被称为非负矩阵分解（NMF），并引起了广泛的关注。相比其他的矩阵分解方法，NMF 由于只使用了加性因子，能够学习到物体（本文中即为歌单）的各个部分。NMF 的方法的缺点是其为 NP-hard。所以对于找到一个局部最小点来说正则化使很重要的。在我们的问题中，我们使用歌曲和歌单的图来确定因子 A 和 B。我们模型的公式计算如下：

              (1)

其中（∘）代表点级别的乘法运算符，θ_A, θ_B∈R₊。我们使用一个加权 KL 散度作为 C 和 AB 之间距离的衡量，有研究表明对于不同的 NMF 设置，这比Frobenius 范式更为准确。公式中的第二项是歌单图中 A 的行的全变分，所以对其进行惩罚就提升了分段恒定信号。公式中的第三项与第二项类似，是 B 的列的全变分。最终我们提出的模型利用了参考文献[9, 16]，并利用 TV 半范式将其扩展到图。

1.1 利用全变分进行图的正则化

在我们基于 NMF 的推荐系统中，每个歌单 i 都被矩阵 A 中的第 i 行 A_i 投影到一个低维空间。为了学习到歌单 A_i 的低秩的表示，我们通过歌单的低秩表示，定义歌单之间成对的相似度ω^A_ii’。我们可以从 TV 正则化项的定义中推导出，

‖A‖_TVA= ∑i∑_{i’~ i}ω^A_ii’‖A_i-A_i’‖₁所以当两个歌单 i 和 i'是相似的，那么它们在图中则是连通的，且连接这两个歌单的边的权值ω^A_ii’很大（这里ω^A_ii’≈ 1）。另外，相应的低维向量表示（A_i，A_i’）间的距离过大就会被惩罚，这使得在低维空间中，（A_i，A_i’）的距离会保持较近。同理，每首歌 j 都由矩阵 B 中的一列 B_j 表示到一个低维空间。如果两首歌（j，j’）很接近（ω^B_ii’′≈ 1），那么（B_j，B_j’）以及图的正则化‖B‖ 则遵循上述的规律。

参考文献[10]的思路与本文相似，通过 Tikhonov 正则化将图的信息引入到模型中，例如通过 Dirichlet 能量项1/2∑i∑_{i’~ i}ω^A_ii’‖A_i-A_i’‖²₂。然而这种方法促进了A 的列之间平滑的变化，而本文的方法图的 TV 项的惩罚则促进了在列 A_i 和 A_i’间具有潜在的突变边缘的分段恒定信号。这对于需要寻找多个类别的任务是有益的，例如聚类，或者本文中的推荐系统所涉及的相似歌单属于不同的目录的情况。

我们在第 4 部分会详细分析，歌曲和歌单的图的使用可以显著的提升推荐效果，且 TV 项的表现要比 Tikhonov 正则化更好。

1.2 原始-对偶优化

对于矩阵 A 和 B 来说，优化问题是全局非凸，但是各自凸的。一个常用的方法是固定 A 去优化 B，然后再固定 B 去优化 A，反复直到收敛。我们这里以固定 A 而优化 B 为例来描述上述优化方法。相同的方法可以在固定 B 时应用于A。我们将上述问题重新写为如下形式：

F(AB) + G(K_BB)                     (2)

其中

F(AB)=KL(Ω∘(C‖AB)) = (−Ω_ijC_ij(log )+Ω_ij(AB)_ij        (3)

                 (4)

其中K_B∈R^ne×m是图的梯度算子，n_e 是图 B 中的边的条数。使用函数 F 和G 的共轭函数 F^*和 G^*，则等价于鞍点问题：

               (5)

其中Y₁ ∈ R^n×m，Y2 ∈ R^ne×r。我们定义最近项和时间间隔 σ1，σ2，τ1，τ2：

               (6)

迭代的方式是，当 k≥0 时：

         Y₁^K+1 = prox_σ1F∗(Y₁^K+ σ₁AB^K)                  (7)

Y₂^K+1 = prox_σ2G∗(Y₂^K+ σ₂K_BB^K)                    (8)

B^K+1=(B^K-τ₁A^TY₁^K+1-(K^T_BY₂^K+1)^T)₊                                        (9)

其中 prox 是最近算子，(∙)₊ = max(∙, 0)。在我们的问题中，我们选择了标准Arrow-Hurwicz 时间间隔σ₁ =τ₁ = 1⁄‖A‖,σ₂ =τ₂ = 1⁄‖K‖，其中‖∙‖是算子范数。

则最近解为：

          (10)

其中 shrink 即为软缩减算子。注意到，同样的算法也可以应用于 Tikhonov正则化，例如，通过将上面的第一个式子改为prox_σ2G*(Y)= Y，就可以将‖K_BB‖₁替换为G(K_B B) = ‖K_BB‖₂²。在式(10)中的正则化使用的是 KL 散度的一个对称变形，但是与我们使用的这种方法不同的是，Tikhonov 正则化不存在解析解。所以其目标函数并不像我们的一样满足一个有效的原始-对偶优化方法。我们保留这种非对称的 KL 模型，并称其为 GNMF，来将 TV 与 Tikhonov 正则化进行比较。

1.3 推荐歌曲

我们通过式(1)学到矩阵 A 和 B 之后，我们希望已知一些歌曲 c_in 时(如图 1-1)，能够推荐新的歌单 c_rec。我们也希望能实现实时的推荐，于是我们定义一个快速推荐方法如下：

图1-1 我们的播放清单推荐系统结构

给定一些歌曲 c_in，我们先通过解决一个正则最小平方问题来在歌单的低秩空间学习一个好的表示：a_in=arg min a∈R^1×r||Ω_in。(c_in-aB)||₂²+ε||a||₂²。其解析解a_in=(B^TΩ_inB+εI)^-1(B^TΩ_inc_in)当 r 很小时较容易计算（我们令ε = 0.01）。

与给定的歌单有相似表示的歌单也对于我们推荐歌单有益。所以在低维空间中，我们用加权和a_rec=Σⁿ_i=1ω_iA_i/Σⁿ_i=1ω_i来表示被推荐的歌单。这里权重ω_i=e^{-||ain-Ai||22/σ2}， 取 决 于 与 其 他 歌 单 的 表 示 的 距 离a_in， 且 σ =mean({||a_in-A_i||₂}ⁿ_i=1)/4。最终推荐歌单的低秩表示为：

c_rec=a_recB                                (11)

这里c_rec并不是二元的，而是一个连续的值，表示歌的排名。

2.歌曲和歌单的图

2.1 歌单的图

歌单的图中包含了歌单间成对的相似度信息。图的节点为歌单，边的权重表示了两个歌单之间的距离，当权重很大时（ω^A_ii’ ≈ 1），表示两个歌单具有很高的相似度。在我们的模型中，歌单图中边的权重的计算不仅与外部信息例如元数据有关，还与内部信息有关，例如歌单中的歌曲信息。我们使用预定义好的 Art of the Mix 歌单分类来标注用户的歌单。则歌单的图中边的权重的计算定义为

            ω^A_ii’=Υ₁δ_{cat{i}=cat{i’}}+Υ₂sim_cos(C_i,C_i’)

其中 cat 表示歌单的标签，C_i是矩阵 C 的第 i 行sim_cos(p,q)=

p^Tq/||p||.||q||是两个歌单的歌曲向量之间的余弦相似度距离。余弦相似度为两首歌相似的比例比上两个歌单长度乘积的均方根。两个正的参数Υ1和Υ2满足Υ1 + Υ2 = 1，用于决定歌单标签的相似度和歌单元素级别的相似度之间的相对重要程度。为了控制每个分类的边缘概率密度并让我们的模型更灵活，我们在同一个分类的节点之间保留 20%的边的一个子集。在实验中我们发现，令Υ2 = 0.3能获得较好的效果。 歌单图的效果通过使用标准 Louvain 方法对图进行分割进行衡量。分块的数目由在模块最大的地方切开形成的模块化系数的树图自动给出。第 4 节使用的图的模块化系数在使用只余弦相似度（Υ2 = 0）时为 0.63。如果我们加入元数据的信息，将每个分类下所有歌单对中的 20%进行连接，并令Υ2 = 0.3，则模块化系数增长到 0.82。

2.2 歌曲的图

我们模型中使用的第二个图是歌曲的相似度图。歌曲的图由从音频信号中抽取的 Echonest 特征与元数据信息结合以及音轨的社会信息混合组成。表 2-1 给出了用于构建歌曲图所使用到的特征。

表2-1 用于生成歌曲的图的特征

为了提高我们的音频特征的质量，我们使用从 LastFm 相关标签中抽取的歌曲类型训练了一个大间隔最近邻模型（Large Margin Nearest Neighbors，LMNN）。为了抽取到真实的音乐类型，我们使用了这些标签经过其流行度（根据 LastFm）加权的 Levenshtein 距离以及 ID3 标签中定义的音乐类型。 最终，我们用 k 近邻（k=5）来构建歌曲的图，其中，对于 j 的 k 个最近邻中的一首歌 j’，两首歌 j 和 j’之间的边的权重ω^B_jj’=exp(-||x_j-x_j’||₁/σ)，参数σ是尺度参数，表示 k 个邻居之间距离的平均值。得到的图的模块化系数很高（0.64），使用 k-NN 进行非监督的准确率为 65%左右。

3. 实验结果

在这部分，我们通过在一个真实数据集上进行实验，将我们的模型与其他 3个不同的推荐系统进行比较。我们的测试数据集是从由 McFee 等构建 的 Art of the Mix 语料库中抽取的。我们之前就是在这个数据库中抽取了上述的特征。 评价一个音乐推荐系统是一个众所周知的难题。在本文中，我们使用一个经典的评价使用间接反馈的推荐系统的模型的方法，Mean percentage Ranking（MPR）以及歌单分类准确度，即在查询的分类中，过去已经出现过的歌单中的歌曲的百分比。

3.1 模型

我们先将我们的模型与一个只基于图的方法（我们称为 Cosine only）进行比较。对于给定输入，这个模型使用余弦相似度计算 t 个最接近的歌单（这里 t=50），通过将歌单中的所有歌曲用余弦相似度进行加权从而计算出一个柱状图进行推荐，如式(11)所示。第二个模型是使用了 KL 散度的 NMF，我们成为 NMF。最后一个模型 GNMF 是基于使用了 Tikhonov 正则化的 KL 散度，并应用了我们模型中的图。

3.2 查询

我们用 3 种不同的查询来测试我们的模型。在所有 3 种查询中，一个查询c_test包含 s=3 首歌作为输入，系统以一个歌单的形式返回最相近的 k=30 首歌作为输出。第一种查询为随机查询，从所有类别的歌中随机选择歌曲，其结果仅作为比较的基准。第二种测试查询，在测试集中的一个歌单中随机选择 3 首歌。第三种采样查询，在一个类别下随机选择 3 首歌。这种查询模拟了用户通过歌曲类别查询歌单的推荐系统。

3.3 训练

我们使用从所有歌单中随机选择出 70%的子集作为训练集，由于我们的模型不是联合凸的，初始化可能会对系统的表现产生影响，所以我们使用现在常用的 NNDSVD 技术来得到一个好的近似解。在我们的所有实验中，r=15 的结果很好，这意味着每行都有 5-20 个非零元素。最好的参数θ_A = 18以及θ_B= 1使用了网格搜索的方法。为了防止过拟合，我们在验证集的 MPR 刚停止增长的时候就使用提前停止的方法。

3.4 验证集

我们通过人工的在不用的歌单类别中进行查询的方法来构建验证集中的歌单。对于每个类别，我们在之前已经在用户创建的标注了类别的歌单中出现的歌曲中随机的选择 s=3 首歌。

3.5 结果

模型的结果，即不同模型的歌单分类准确率和 MPR 我们列在表 3-1 和表 3-2 中。如我们所预料的，对于随机查询，所有的模型都不能根据输入的歌曲返回歌单，而且使用了协同滤波同时没有假如图信息的 NMF 表现很差。这可以理解为是数据集的稀疏性造成的，数据集每行只含有 5-20 个非零元素，稀疏度只有 0.11-0.46%。协同过滤模型在有越多的观察到的等级时的表现越好，cosine 模型在类别准确率上表现更好，因为它直接使用了输入歌曲和歌单之间的余弦距离。然而，它的 MPR 说明即使状况很复杂，我们的模型在歌曲推荐时表现的更好。

表3-1 所有模型对不同类别的类别查询准确度

表3-2 所有模型对不同类别的查询的平均准确度排名（MPR）

图 3-1 测试集上每个播放清单类别的MPR

4. 结论

在这篇论文中我们介绍了一个新的灵活的歌曲推荐系统，这个系统结合了歌单的协同过滤信息以及图中包含的歌曲相似度信息。我们使用一个基于原始-对偶的优化模式来得到一个高度并行的、可以用来处理大型数据集的算法。我们选择图的 TV 而不是 Tikhonov 正则化，并通过将我们的系统与 3 个不同的算法在真实的音乐歌单数据集上做比较，展示了我们模型的良好的实验效果。

参考文献

Bach, F.; Jenatton, R.; Mairal, J.; and Obozinski, G. 2012. Optimization with sparsity-inducing penalties. Foundations and Trends in Machine Learning 4(1):1–106.

Byrne, S., and Girolami, M. 2013. Geodesic Monte Carlo on embedded manifolds. Scandinavian Journal of Statistics 40(4):825–845.

Casella, G. 2001. Empirical Bayes Gibbs sampling. Bio-statistics 2(4):485–500.

Dobigeon, N., and Tourneret, J.-Y. 2010. Bayesian orthogonal component analysis for sparse representation. IEEE Transactions on Signal Processing 58(5):2675–2685.

Fazel, M. 2002. Matrix rank minimization with applications. Ph.D. Dissertation, Stanford University.

Goldberg, K.; Roeder, T.; Gupta, D.; and Perkins, C. 2001. Eigentaste: A constant time collaborative filtering algorithm. Information Retrieval 4(2):133–151.

Griffiths, T. L., and Ghahramani, Z. 2011. The Indian buffet process: An introduction and review. Journal of Machine Learning Research 12:1185–1224.

Hastie, T.; Mazumder, R.; Lee, J.; and Zadeh, R. 2014. Matrix completion and low-rank SVD via fast alternating least squares. arXiv preprint arXiv:1410.2596.

Hoff, P. D. 2009. Simulation of the matrix Bingham–von Mises–Fisher distribution, with applications to multivariate and relational data. Journal of Computational and Graphical Statistics 18(2).

James, I. M. 1976. The topology of Stiefel manifolds, volume 24. Cambridge University Press.

Lim, Y. J., and Teh, Y. W. 2007. Variational Bayesian approach to movie rating prediction. In Proceedings of KDD Cup and Workshop, volume 7, 15–21. Citeseer.

Marlin, B. 2004. Collaborative filtering: A machine learn- ing perspective. Ph.D. Dissertation, University of Toronto.

Mazumder, R.; Hastie, T.; and Tibshirani, R. 2010. Spectral regularization algorithms for learning large incomplete matrices. Journal of Machine Learning Research 11:2287– 2322.

Rennie, J. D., and Srebro, N. 2005. Fast maximum margin matrix factorization for collaborative prediction. In International Conference on Machine Learning, 713–719.

Salakhutdinov, R., and Mnih, A. 2008. Bayesian probabilistic matrix factorization using MCMC. In International Conference on Machine Learning.

Srebro, N.; Rennie, J.; and Jaakkola, T. S. 2004. Maximum-margin matrix factorization. In Advances in Neural Information Processing Systems, 1329–1336.

Stiefel, E.¹ 1935. Richtungsfelder und fernparallelismus in n-dimensionalen mannigfaltigkeiten. Commentarii Mathematici Helvetici 8(1):305–353.

Todeschini, A.; Caron, F.; and Chavent, M. 2013. Probabilistic low-rank matrix completion with adaptive spectral regularization algorithms. In Advances in Neural Information Processing Systems, 845–853.

Xu, M.; Zhu, J.; and Zhang, B. 2012. Nonparametric max-margin matrix factorization for collaborative prediction. In Advances in Neural Information Processing Systems, 64–72.