论文标题
稀疏可分解的子解次功能
Sparsification of Decomposable Submodular Functions
论文作者
论文摘要
supperular功能是许多机器学习和数据挖掘任务的核心。这些任务中许多任务的基础下函数都是可分解的，即它们是几个简单的下函数的总和。但是，在许多数据密集型应用程序中，原始函数中的基本函数的数量是如此之大，以至于我们需要大量的时间来处理它和/或甚至不适合主内存。为了克服这个问题，我们介绍了可分解的次化功能的稀疏概念，其目的是获得只有少数少数次传统函数的（加权）总和的原始函数的准确近似。我们的主要结果是多项式时间随机稀疏算法，使输出中使用的预期功能数与原始函数中的下义函数的数量无关。我们还研究了算法在各种限制（例如矩阵和基数约束）下的有效性。我们通过对算法的性能进行实证研究来补充理论分析。
Submodular functions are at the core of many machine learning and data mining tasks. The underlying submodular functions for many of these tasks are decomposable, i.e., they are sum of several simple submodular functions. In many data intensive applications, however, the number of underlying submodular functions in the original function is so large that we need prohibitively large amount of time to process it and/or it does not even fit in the main memory. To overcome this issue, we introduce the notion of sparsification for decomposable submodular functions whose objective is to obtain an accurate approximation of the original function that is a (weighted) sum of only a few submodular functions. Our main result is a polynomial-time randomized sparsification algorithm such that the expected number of functions used in the output is independent of the number of underlying submodular functions in the original function. We also study the effectiveness of our algorithm under various constraints such as matroid and cardinality constraints. We complement our theoretical analysis with an empirical study of the performance of our algorithm.
