MoST: A monotone set transformer for scalable and verifiable neuro-fuzzy aggregation

Area of Science:

• Machine Learning
• Artificial Intelligence
• Set Theory

Background:

• Deep learning models for set-structured data require permutation invariance, monotonicity, and scalability for safety-critical applications.
• Existing architectures like Deep Sets and attention mechanisms have limitations in satisfying these axioms simultaneously, particularly regarding monotonicity and efficiency.

Purpose of the Study:

• To address the limitations of current deep learning architectures in handling set-structured data with axiomatic constraints.
• To introduce a novel architecture, the Monotone Set Transformer (MoST), that satisfies theoretical axioms like monotonicity and computational scalability.

Main Methods:

• Formalizing efficiency limitations in canonical additive architectures (Deep Sets) for order-statistics.
• Introducing the Monotone Set Transformer (MoST), a neuro-fuzzy architecture with a non-competitive gating mechanism and Ordered Weighted Averaging (OWA) for rank-dependent aggregation.
• Proving MoST's preservation of set-inclusion monotonicity by construction and analyzing its computational complexity (O(NlogN)).

Main Results:

• Demonstrating that sum-pooling in Deep Sets requires linear feature scaling (m=Ω(N)) for exact order-statistics, leading to dimension inefficiency.
• Showing that standard attention mechanisms violate monotonicity due to competitive normalization.
• MoST achieves near-exact max aggregation in synthetic settings and exhibits favorable time/memory scaling compared to attention baselines.
• Experimental results on molecular tasks indicate a trade-off between strict monotonicity and predictive flexibility.

Conclusions:

• The Monotone Set Transformer (MoST) provides a verifiable solution for learning on set-structured data while adhering to crucial theoretical axioms.
• MoST offers improved efficiency and monotonicity guarantees compared to existing deep learning approaches.
• The findings suggest a practical approach for deploying set-based learning in safety-critical domains, with a noted trade-off between constraint adherence and performance.