Enumeration of linear threshold functions from the lattice of hyperplane intersections

Area of Science:

• Computational Geometry
• Algebraic Combinatorics
• Machine Learning Theory

Background:

• Enumerating linear threshold functions is crucial for understanding their complexity in machine learning and computational geometry.
• Existing methods often rely on geometric lattices that are computationally intensive for higher dimensions.

Purpose of the Study:

• To develop a more efficient method for enumerating linear threshold functions for n-dimensional binary inputs.
• To leverage group theory and poset theory to create a compact and tractable representation of hyperplane intersections.

Main Methods:

• Utilized the hyperoctahedral group O(n+1) to construct a symmetry-adapted poset (Deltan) of hyperplane intersections.
• Defined a generalized Zeta function and its inverse, the generalized Möbius function, on the symmetry-adapted poset.
• Computed the number of linear threshold functions using the generalized Möbius function for dimensions 3, 4, and 5.

Main Results:

• Demonstrated that the symmetry-adapted poset (Deltan) is more compact and computationally tractable than the traditional geometric lattice (Ln).
• Successfully enumerated linear threshold functions for low-dimensional inputs by applying the generalized Möbius function.
• Showcased a method to enumerate equivalence classes of linear threshold functions by unfolding the symmetry-adapted poset.

Conclusions:

• The developed symmetry-adapted approach offers a significant improvement in the tractability of enumerating linear threshold functions.
• This construction provides a foundation for potentially deriving asymptotic bounds on the number of equivalence classes of linear threshold functions.