Separating points by parallel hyperplanes--characterization problem.

Area of Science:

• Computational Geometry
• Machine Learning Theory
• Discrete Mathematics

Background:

• Partitions of discrete point sets in d-dimensional space are fundamental geometric structures.
• These partitions correspond to multilinear threshold functions used in neural networks and multivalued logic.
• Understanding the encoding and characterization of these partitions is essential for efficient representation.

Purpose of the Study:

• To investigate the characterization (encoding) problem for partitions of discrete point sets.
• To establish a unique encoding scheme for multilinear partitions.
• To determine the bit rate required for such encoding and analyze its dependencies.

Main Methods:

• Utilizing parallel hyperplanes to partition a discrete set S of points in d-dimensional space.
• Establishing a correspondence between these partitions and multilinear threshold functions.
• Developing a characterization (code) based on discrete moments of order no bigger than 1.

Main Results:

• A unique characterization (encoding) of multilinear partitions is shown to be possible.
• The required bit rate for encoding is determined to be theta(h x d^2 x log m) per partition.
• The proposed encoding uses (d + 1) x (h + 1) discrete moments of order up to 1.

Conclusions:

• The study provides an efficient method for encoding multilinear partitions.
• The derived bit rate offers insights into the complexity of representing these structures.
• Optimality in bit rate is achieved under specific relationships between h, d, and m.