新模型可精准表示所有单调集合函数,且泛化能力更强。
Extended Deep Submodular Functions
- 用神经网络构建可表示任意单调子模函数的新框架
- 实验显示其在覆盖率学习中误差显著低于旧模型
- 适合需要强泛化与优化保证的组合优化场景
我们提出一种新型集合函数——扩展深度子模函数(EDSFs),其可通过神经网络表示。EDSFs是深度子模函数(DSFs)的拓展,在继承DSFs关键性质的同时克服了固有局限。已有研究表明DSFs仅能表示子模函数的一小部分;而通过拟模体性质分析,我们证明EDSFs具备表示所有单调子模函数的能力,实现显著提升。进一步地,我们证明EDSFs可表示任意单调集合函数,表明其与所有单调集合函数家族等价。此外,当输入向量分量为非负实数时,EDSFs保持了DSFs固有的凹性,这对某些组合优化问题至关重要。大量实验表明,EDSFs在覆盖率函数学习中表现出远低于DSFs的实证泛化误差,展现出更优的表示与学习能力。
原文摘要 · Abstract (English)
We introduce a novel category of set functions called Extended Deep Submodular functions (EDSFs), which are neural network-representable. EDSFs serve as an extension of Deep Submodular Functions (DSFs), inheriting crucial properties from DSFs while addressing innate limitations. It is known that DSFs can represent a limiting subset of submodular functions. In contrast, through an analysis of polymatroid properties, we establish that EDSFs possess the capability to represent all monotone submodular functions, a notable enhancement compared to DSFs. Furthermore, our findings demonstrate that EDSFs can represent any monotone set function, indicating the family of EDSFs is equivalent to the family of all monotone set functions. Additionally, we prove that EDSFs maintain the concavity inherent in DSFs when the components of the input vector are non-negative real numbers-an essential feature in certain combinatorial optimization problems. Through extensive experiments, we illustrate that EDSFs exhibit significantly lower empirical generalization error than DSFs in the learning of coverage functions. This suggests that EDSFs present a promising advancement in the representation and learning of set functions with improved generalization capabilities.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。