Loading...

Extended deep submodular functions

Hosseini, S. M ; Sharif University of Technology | 2024

73 Viewed
  1. Type of Document: Article
  2. DOI: 10.48550/arXiv.2409.12053
  3. Publisher: ResearchGte , 2024
  4. Abstract:
  5. We introduce a novel representation of monotone set functions called Extended Deep Sub-modular 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, 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 com-ponents of the input vector are non-negative real numbers—an essential feature in certain combinatorial optimization problems. Through extensive experiments, we demonstrate that EDSFs exhibit significantly lower empirical generalization error in representing and learning coverage and cut functions compared to existing baselines, such as DSFs, Deep Sets, and Set Transformers. © 2024, Transactions on Machine Learning Research. All rights reserved
  6. Keywords:
  7. Machine Learning ; Discrete Mathematics
  8. Source: Transactions on Machine Learning Research ; Volume 2024 , 2024 ; 28358856 (ISSN)
  9. URL: https://arxiv.org/abs/2409.12053