Monotone and Separable Set Functions: Characterizations and Neural Models
This work addresses set containment problems in machine learning, offering a novel theoretical framework and practical model for tasks requiring monotonicity, though it is incremental in extending existing set function concepts.
The paper tackles the problem of designing set-to-vector functions that preserve set containment order, introducing Monotone and Separating (MAS) set functions and showing they do not exist for infinite sets but providing a weakly MAS model with Holder continuity. The experiments demonstrate improved performance on set containment tasks compared to standard models without this inductive bias.
Motivated by applications for set containment problems, we consider the following fundamental problem: can we design set-to-vector functions so that the natural partial order on sets is preserved, namely $S\subseteq T \text{ if and only if } F(S)\leq F(T) $. We call functions satisfying this property Monotone and Separating (MAS) set functions. % We establish lower and upper bounds for the vector dimension necessary to obtain MAS functions, as a function of the cardinality of the multisets and the underlying ground set. In the important case of an infinite ground set, we show that MAS functions do not exist, but provide a model called our which provably enjoys a relaxed MAS property we name "weakly MAS" and is stable in the sense of Holder continuity. We also show that MAS functions can be used to construct universal models that are monotone by construction and can approximate all monotone set functions. Experimentally, we consider a variety of set containment tasks. The experiments show the benefit of using our our model, in comparison with standard set models which do not incorporate set containment as an inductive bias. Our code is available in https://github.com/yonatansverdlov/Monotone-Embedding.