融合非负矩阵分解和图全变分的歌曲推荐算法

  • 时间:
  • 浏览:1
  • 来源:决战梭哈棋牌APP下载_决战梭哈棋牌APP官网

在亲戚亲戚亲们基于 NMF 的推荐系统中,每个歌单 i 都被矩阵 A 中的第 i 行 Ai 投影到一另好好多个 低维空间。为了学习到歌单 Ai 的低秩的表示,亲戚亲戚亲们通过歌单的低秩表示,定义歌单之间成对的之类度ωAii’。亲戚亲戚亲们才能从 TV 正则化项的定义中推导出,

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

则最近解为:

亲戚亲戚亲们通过人工的在不必的歌单类别中进行查询的土辦法 来构建验证集中的歌单。对于每个类别,亲戚亲戚亲们在前一天可能在用户创建的标注了类别的歌单中出現的歌曲中随机的选泽 s=3 首歌。

Kirell Benzi,

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

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

         Y1K+1 = proxσ1F(Y1K+ σ1ABK)                  (7)

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.

图1-1 亲戚亲戚亲们的播放清单推荐系统价值形式

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

歌单的图中中含了歌单间成对的之类度信息。图的节点为歌单,边的权重表示了一另好好多个 歌单之间的距离,当权重很大时(ωAii’ ≈ 1),表示一另好好多个 歌单具有很高的之类度。在亲戚亲戚亲们的模型中,歌单图中边的权重的计算不仅与内部信息之类元数据有关,还与内部信息有关,之类歌单中的歌曲信息。亲戚亲戚亲们使用预定义好的 Art of the Mix 歌单分类来标注用户的歌单。则歌单的图中边的权重的计算定义为

              (1)

亲戚亲戚亲们先将亲戚亲戚亲们的模型与一另好好多个 只基于图的土辦法 (亲戚亲戚亲们称为 Cosine only)进行比较。对于给定输入,你这个模型使用余弦之类度计算 t 个最接近的歌单(这里 t=500),通过将歌单中的所有歌曲用余弦之类度进行加权从而计算出一另好好多个 柱状图进行推荐,如式(11)所示。第好好多个 模型是使用了 KL 散度的 NMF,亲戚亲戚亲们成为 NMF。最后一另好好多个 模型 GNMF 是基于使用了 Tikhonov 正则化的 KL 散度,并应用了亲戚亲戚亲们模型中的图。

亲戚亲戚亲们在第 4 每段会完整分析,歌曲和歌单的图的使用才能显著的提升推荐效果,且 TV 项的表现要比 Tikhonov 正则化更好。

本文正式地形式化一另好好多个 全新的的歌曲推荐算法,其将歌曲推荐的现象报告 转化为矩阵补全的现象报告 来考虑,并通过基于非负矩阵分解(non-negative matrix factorization, NMF)的协同过滤算法以及图上的结合图的全变分(total variation, TV)的基于内容的过滤土辦法 相结合来除理你这个现象报告 。相关的图通过使用音频、元数据以及社交价值形式等充足的信息的结合,对歌单的邻接信息以及歌曲的之类度信息进行编码。亲戚亲戚亲们证明,亲戚亲戚亲们提出的你这个融合了几种知名的土辦法 的混合推荐系统,有着广阔的应用前景,并在效果上超过融合的相关算法。通过在真实数据上进行的实验,亲戚亲戚亲们证实了亲戚亲戚亲们的模型能仅仅根据低秩矩阵的信息可能基于图的信息以及两者的结合进行歌曲的推荐。

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

训练阶段的目标是找到一另好好多个 近似的低秩表示,使AB ≈ C,其中A ∈ R+n×r,B ∈R+r×m也有非负的,且 r 很小。你这个现象报告 被称为非负矩阵分解(NMF),并引起了广泛的关注。相比许多的矩阵分解土辦法 ,NMF 可能只使用了加性因子,才能学习到物体(本文中即为歌单)的各个每段。NMF 的土辦法 的缺点是其为 NP-hard。全都有对于找到一另好好多个 局部最小点来说正则化使有点硬要的。在亲戚亲戚亲们的现象报告 中,亲戚亲戚亲们使用歌曲和歌单的图来选泽 因子 A 和 B。亲戚亲戚亲们模型的公式计算如下:

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

其中 prox 是最近算子,(∙)+ = max(∙, 0)。在亲戚亲戚亲们的现象报告 中,亲戚亲戚亲们选泽 了标准Arrow-Hurwicz 时间间隔σ11 = 1⁄‖A‖,σ2 =τ2 = 1⁄‖K‖,其中‖∙‖是算子范数。

其中 shrink 即为软缩减算子。注意到,同样的算法也才能应用于 Tikhonov正则化,之类,通过将后边的第一另好好多个 式子改为proxσ2G*(Y)=Y,就可以将‖KBB‖1替换为G(KB B) = ‖KBB‖22。在式(10)中的正则化使用的是 KL 散度的一另好好多个 对称变形,怎么让与亲戚亲戚亲们使用的你这个土辦法 不同的是,Tikhonov 正则化不地处解析解。全都有其目标函数不须像亲戚亲戚亲们的一样满足一另好好多个 有效的原始-对偶优化土辦法 。亲戚亲戚亲们保留你这个非对称的 KL 模型,并称其为 GNMF,来将 TV 与 Tikhonov 正则化进行比较。

迭代的土辦法 是,当 k≥0 时:

这里crec并也有二元的,全都我一另好好多个 连续的值,表示歌的排名。

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

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

假设亲戚亲戚亲们有n个歌单,每个列表都中含m首歌中的其中一每段。亲戚亲戚亲们定义矩阵C∈{0,1}n×m,矩阵中的元素 Cij 为 1 则表示歌单 i 中中含歌曲 j,怎么让为 0。亲戚亲戚亲们再定义一另好好多个 权重矩阵Ω∈{0,1}n×m,当输入的 Cij 可能为 1 时,Ωij=1,怎么让等于一另好好多个 很小的值 ε(亲戚亲戚亲们使用的 ε=0.1)。这里应用了不明确反馈现象报告 的思路。在矩阵 C 中一另好好多个 元素为 0 不代表这首歌与你这个歌单无关,全都我更可能不相关。

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

摘  要

            ωAii’1δcat{i}=cat{i’}2simcos(Ci,Ci’)

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.

F(AB)=KL(Ω∘(C‖AB)) =(−ΩijCij(log)+Ωij(AB)ij        (3)

在 Netflix上推荐电影,在Facebook上推荐好友,可能在LinkedIn上推荐工作等任务在过去几年中吸引了太多的关注。大每段Netflix奖的获得者喜爱用的著名的低秩矩阵分解算法都要明确的用户评级作为输入。许多许多之类的土辦法 则通过用户对物品的操作来反映用户对物品的偏好,以致力于除理用户的不明确的反馈现象报告 。具体到歌曲和歌单推荐现象报告 ,也可能有了各种不同的土辦法 ,其中既有单纯的基于内容的土辦法 ,也有各种混合的模型。最近,图的正则化被提出,用来提高矩阵补全算法的效果。

F(AB) + G(KBB)                     (2)

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

                 (4)

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.

Signal Processing Laboratory 2 (LTS2),

               (5)

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

亲戚亲戚亲们使用从所有歌单中随机选泽 出 70%的子集作为训练集,可能亲戚亲戚亲们的模型也有联合凸的,初始化可能会对系统的表现产生影响,全都有亲戚亲戚亲们使用现在常用的 NNDSVD 技术来得到一另好好多个 好的近似解。在亲戚亲戚亲们的所有实验中,r=15 的结果很好,这由于每行也有 5-20 个非零元素。最好的参数θA = 18以及θB= 1使用了网格搜索的土辦法 。为了除理过拟合,亲戚亲戚亲们在验证集的 MPR 刚停止增长的前一天就使用提前停止的土辦法 。

Xavier Bresson and Pierre Vandergheynst

本文的主要贡献在以下好多个方面:

亲戚亲戚亲们通过式(1)学到矩阵 A 和 B 前一天,亲戚亲戚亲们希望已知许多歌曲 cin 时(如图 1-1),才能推荐新的歌单 crec。亲戚亲戚亲们也希望能实现实时的推荐,于是亲戚亲戚亲们定义一另好好多个 快速推荐土辦法 如下:

其中KB∈Rne×m是图的梯度算子,ne 是图 B 中的边的条数。使用函数 F 和G 的共轭函数 F*和 G*,则等价于鞍点现象报告 :

BK+1=(BK-τ1ATY1K+1-(KTBY2K+1)T)+                                        (9)

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

参考文献[10]的思路与本文之类,通过 Tikhonov 正则化将图的信息引入到模型中,之类通过 Dirichlet 能量项1/2∑i∑i’~ iωAii’‖Ai-Ai’22然而你这个土辦法 能助 了A 的列之间平滑的变化,而本文的土辦法 图的 TV 项的惩罚则能助 了在列 Ai 和 Ai间具有潜在的突变边缘的分段恒定信号。这对于都要寻找多个类别的任务是有益的,之类聚类,可能本文中的推荐系统所涉及的之类歌单属于不同的目录的请况。

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

参考文献

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

表2-1 用于生成歌曲的图的价值形式

          (10)

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

crec=arecB                                (11)

与给定的歌单有之类表示的歌单也对于亲戚亲戚亲们推荐歌单有益。全都有在低维空间中,亲戚亲戚亲们用加权和arecni=1ωiAini=1ωi来表示被推荐的歌单。这里权重ωi=e-||ain-Ai||22/σ2, 取 决 于 与 其 他 歌 单 的 表 示 的 距 离ain, 且 σ =mean({||ain-Ai||2}ni=1)/4。最终推荐歌单的低秩表示为:

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

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

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

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

关键字:推荐系统,图,非负矩阵分解,全变分,音频价值形式

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

给定许多歌曲 cin,亲戚亲戚亲们先通过除理一另好好多个 正则最小平方现象报告 来在歌单的低秩空间学习一另好好多个 好的表示:ain=arg min a∈R1×r||Ωin。(cin-aB)||22+ε||a||22。其解析解ain=(BTΩinB+εI)-1(BTΩincin)当 r 很小时较容易计算(亲戚亲戚亲们令ε = 0.01)。

               (6)

其中

Swiss Federal Institute of Technology (EPFL)

Vassilis Kalofolias,

亲戚亲戚亲们模型中使用的第好好多个 图是歌曲的之类度图。歌曲的图由从音频信号中抽取的 Echonest 价值形式与元数据信息结合以及音轨的社会信息混合组成。表 2-1 给出了用于构建歌曲图所使用到的价值形式。

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

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

对于矩阵 A 和 B 来说,优化现象报告 是全局非凸,怎么让各自 凸的。一另好好多个 常用的土辦法 是固定 A 去优化 B,怎么让再固定 B 去优化 A,反复直到收敛。亲戚亲戚亲们这里以固定 A 而优化 B 为例来描述上述优化土辦法 。相同的土辦法 才能在固定 B 时应用于A。亲戚亲戚亲们将上述现象报告 重新写为如下形式:

‖A‖TVA= ∑i∑i’~ iωAii’‖Ai-Ai’1全都有当一另好好多个 歌单 i 和 i'是之类的,没法它们在图中则是连通的,且连接你这个另好好多个 歌单的边的权值ωAii’很大(这里ωAii’≈ 1)。另外,相应的低维向量表示(Ai,Ai)间的距离过大就会被惩罚,这使得在低维空间中,(Ai,Ai)的距离会保持较近。同理,每首歌 j 都由矩阵 B 中的一列 Bj 表示到一另好好多个 低维空间。可能两首歌(j,j’)很接近(ωBii’′≈ 1),没法(Bj,Bj)以及图的正则化‖B‖则遵循上述的规律。

其中Y1 ∈ Rn×m,Y2 ∈ Rne×r。亲戚亲戚亲们定义最近项和时间间隔 σ1,σ2,τ1,τ2:

Y2K+1 = proxσ2G∗(Y2K+ σ2KBBK)                    (8)

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

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.

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

l  介绍了一另好好多个 新的图正则化项(TV),在推荐系统的背景下,其效果要优于广泛应用的 Tikhonov 正则化;

表3-2 所有模型对不之类别的查询的平均准确度排名(MPR)

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

在这篇论文中亲戚亲戚亲们介绍了一另好好多个 新的灵活的歌曲推荐系统,你这个系统结合了歌单的协同过滤信息以及图中中含的歌曲之类度信息。亲戚亲戚亲们使用一另好好多个 基于原始-对偶的优化模式来得到一另好好多个 深度并行的、才能用来除理大型数据集的算法。亲戚亲戚亲们选泽 图的 TV 而也有 Tikhonov 正则化,并通过将亲戚亲戚亲们的系统与 3 个不同的算法在真实的音乐歌单数据集上做比较,展示了亲戚亲戚亲们模型的良好的实验效果。

在这每段,亲戚亲戚亲们通过在一另好好多个 真实数据集上进行实验,将亲戚亲戚亲们的模型与许多 好好多个 不同的推荐系统进行比较。亲戚亲戚亲们的测试数据集是从由 McFee 等构建 的 Art of the Mix 语料库中抽取的。亲戚亲戚亲们前一天全都我在你这个数据库中抽取了上述的价值形式。 评价一另好好多个 音乐推荐系统是一另好好多个 众所周知的现象报告 。在本文中,亲戚亲戚亲们使用一另好好多个 经典的评价使用间接反馈的推荐系统的模型的土辦法 ,Mean percentage Ranking(MPR)以及歌单分类准确度,即在查询的分类中,过去可能出現过的歌单中的歌曲的百分比。

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

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