论文标题
一个元重量函数的参数化家族
A Parameterized Family of Meta-Submodular Functions
论文作者
论文摘要
在过去的几年中，最大化功能最大化发现了机器学习模型中的大量新应用。相关的超模型最大化模型（superodular最小化）也提供了大量的应用，但即使在简单的基数约束下，它们也似乎非常棘手。因此，虽然有良好的工具可以最大程度地遵守矩阵约束，但在相应的超模型最大化问题上的工作要少得多。 我们提供了一个广泛的单调函数的参数化家族，其中包括次模函数和一类包含多样性函数的超模型函数。此参数化家族中的功能称为\ emph {$γ$ -META-SUBMODULAL}。我们开发了仅取决于参数$γ$的近似因子的本地搜索算法。我们表明，$γ$ - meta-mebmodular的家庭包括众所周知的功能，例如元模块化功能（$γ= 0 $），度量多样性功能和按比例下的函数（$ $γ= 1 $），基于负距离的多样性函数，基于负类型或$ $ $ $ $ $ $ shannon diverricition和$γ= 2 2 = 2 2 = 2 2 = 2 2 = 2 2 = 2 2 = 22功能（$γ=σ$）。
Submodular function maximization has found a wealth of new applications in machine learning models during the past years. The related supermodular maximization models (submodular minimization) also offer an abundance of applications, but they appeared to be highly intractable even under simple cardinality constraints. Hence, while there are well-developed tools for maximizing a submodular function subject to a matroid constraint, there is much less work on the corresponding supermodular maximization problems. We give a broad parameterized family of monotone functions which includes submodular functions and a class of supermodular functions containing diversity functions. Functions in this parameterized family are called \emph{$γ$-meta-submodular}. We develop local search algorithms with approximation factors that depend only on the parameter $γ$. We show that the $γ$-meta-submodular families include well-known classes of functions such as meta-submodular functions ($γ=0$), metric diversity functions and proportionally submodular functions (both with $γ=1$), diversity functions based on negative-type distances or Jensen-Shannon divergence (both with $γ=2$), and $σ$-semi metric diversity functions ($γ= σ$).
