Many algorithms for ranked data become computationally intractable as the number of objects grows due to complex geometric structure induced by rankings. An additional challenge is posed by partial rankings, i.e. rankings in which the preference is only known for a subset of all objects. For these reasons, state-of-the-art methods cannot scale to real-world applications, such as recommender systems. We address this challenge by exploiting geometric structure of ranked data and additional available information about the objects to derive a submodular kernel for ranking. The submodular kernel combines the efficiency of submodular optimization with the theoretical properties of kernel-based methods. We demonstrate that the submodular kernel drastically reduces the computational cost compared to state-of-the-art kernels and scales well to large datasets while attaining good empirical performance.
翻译:排名数据的许多算法在计算上变得难以处理,因为排名引发的复杂几何结构导致对象数量的增长。 部分排名带来了另一个挑战,即只有子集才知道优先程度的排序。 由于这些原因,最先进的方法无法与推荐者系统等真实世界应用相适应。 我们通过利用排名数据的几何结构和关于天体的其他可用信息来应对这一挑战,以得出排序所需的子模块内核。 亚模块内核将亚模块优化的效率与内核方法的理论特性结合起来。 我们证明子模块内核在取得良好经验性能的同时,会大幅降低计算成本, 与最先进的内核和尺度相比, 大大降低计算成本。