Manifoldron: Direct Space Partition via Manifold Discovery

Dayang Wang, Feng-Lei Fan, Bojian Hou, Hao Zhang, Rongjie Lai, Hengyong Yu, Fei WangIEEE TNNLS 2022 · DOI · OpenReview

TL;DR

This paper introduces Manifoldron, a novel machine learning model that partitions data space by directly discovering underlying manifold structures. Unlike traditional models that rely on parameterized decision boundaries, Manifoldron offers improved interpretability and robustness by learning directly from data, achieving competitive performance across various benchmarks.

What Problem Does This Paper Address?

Traditional machine learning models, particularly neural networks with ReLU activations, partition the input space into convex polytopes. While this offers a form of interpretability (each polytope corresponds to a unique neuron activation state), it becomes computationally infeasible for large networks. Furthermore, parameterized decision boundaries in these models suffer from several limitations: compromised interpretability as models grow complex, inflexibility in constructing decision boundaries that might not align with data's true structure, and a tendency to fall into "shortcut solutions" that rely on spurious correlations rather than genuine features. Non-parameterized models, on the other hand, often oversimplify data or fail to capture complex manifold structures, limiting their power. This paper aims to bridge this gap by proposing a non-parameterized model that directly leverages manifold structures for decision boundary construction, offering both power and interpretability.

Methods

The core of Manifoldron lies in its ability to discover and utilize the manifold structure of data. The process involves:

  • Delaunay Triangulation: For each class, the training data points are used to construct a simplicial complex that covers the data's convex hull.
  • Simplex Trimming: To refine the triangulation and better reflect the manifold's true shape, simplices with vertices too far apart are removed. This is achieved using a KD-tree for efficient neighborhood searches.
  • Envelope Detection: The outer boundary of the refined simplicial complex for each class is identified as the "envelope." These envelopes collectively form the decision boundaries.
  • Sample Prediction: For a new data point, Manifoldron first checks if it falls within any class's envelope (in-out simplex detection). If not, it determines the closest envelope to classify the point. Distance estimation is performed efficiently using KD-trees.

To address computational challenges, Manifoldron employs:

  • Feature Bagging: Random subsets of features are used to train multiple Manifoldron models, whose predictions are then aggregated. This reduces dimensionality and allows for parallel computation.
  • Point2Point Projection: Instead of calculating the distance to hyperplanes, Manifoldron approximates this by calculating the distance to the vertices of the envelopes, further speeding up inference.

The paper also proves a universal boundary approximation theorem, demonstrating Manifoldron's capability to learn complex manifolds and avoid shortcut solutions. Additionally, it establishes a connection between Manifoldron and neural networks, showing that Manifoldron can be represented by a piecewise constant function over a simplicial complex, which can, in turn, be expressed by a ReLU neural network.

Datasets

Manifoldron was evaluated on a diverse set of datasets:

  • Synthetic Datasets: Four complex 3D manifolds were generated (SixCircles, DNA, RingSpiral, TwoCurlySpirals) to specifically test manifold characterization capabilities.
  • Public Benchmark Datasets:
    • 20 datasets from recent machine learning studies (9 small and 11 large tabular datasets).
  • A real-world application dataset from pathogen identification using a chromogenic array.
  • Regression Datasets: Datasets constructed based on elementary functions (f1 to f6) for evaluating its regressor capabilities.

Key Insights and Ideas

  • Direct Manifold Discovery for Decision Boundaries: The core innovation is using manifold structure directly to define decision boundaries, bypassing the limitations of parameterized models.
  • Robustness to Data Shifts: Figure 3 visually demonstrates that Manifoldron's decision boundaries are less affected by shifts in data clusters compared to other models, suggesting greater robustness.
  • Escape from Shortcut Solutions: By focusing on intrinsic manifold structures rather than spatial occupancy, Manifoldron is inherently less prone to learning spurious correlations.
  • Theoretical Foundation: The paper provides a theoretical guarantee (universal boundary approximation theorem) for Manifoldron's ability to learn complex decision boundaries.
  • Connection to Neural Networks: Establishing a link to neural networks opens avenues for hybrid approaches and initialization strategies.

Key Results

  • Classification Performance: Manifoldron achieved the highest accuracy on all four synthetic datasets. On public benchmark datasets, it performed competitively, often achieving the best or near-best results, with an average rank of 4.35 across 20 benchmarks.
  • Real-World Application: Manifoldron delivered the highest accuracy and macro-F1 scores on the pathogen identification dataset, outperforming even deep learning models.
  • Regression Performance: Manifoldron served as a good regressor, achieving the lowest errors on most elementary functions, often surpassed only by MLP regressors.
  • Computational Efficiency: Techniques like feature bagging and KD-trees significantly reduce computational cost, making Manifoldron scalable to datasets with tens of thousands of samples and hundreds of features within acceptable timeframes.

Limitations and Future Work

  • Computational Overhead: While improved, Manifoldron can still be slow on extremely large datasets (e.g., ImageNet) with very high dimensions.
  • Sensitivity to Neighbor Number: The performance is sensitive to the choice of the number of neighbors (k) used in simplex trimming, which is a key hyperparameter.
  • Missing Value Treatment: Manifoldron cannot handle datasets with missing values.
  • Outlier Sensitivity: Delaunay triangulation and trimming can be affected by outliers, potentially leading to inaccurate envelopes and decision boundaries.

Future work suggested includes reducing the sensitivity to the neighbor number hyperparameter, developing methods for handling missing values and outliers, and exploring Manifoldron's application in more diverse domains.

Summary updated

Abstract

A neural network with the widely-used ReLU activation has been shown to partition the sample space into many convex polytopes for prediction. However, the parameterized way a neural network and other machine learning models use to partition the space has imperfections, \textit{e}.\textit{g}., the compromised interpretability for complex models, the inflexibility in decision boundary construction due to the generic character of the model, and the risk of being trapped into shortcut solutions. In contrast, although the non-parameterized models can adorably avoid or downplay these issues, they are usually insufficiently powerful either due to over-simplification or the failure to accommodate the manifold structures of data. In this context, we first propose a new type of machine learning models referred to as Manifoldron that directly derives decision boundaries from data and partitions the space via manifold structure discovery. Then, we systematically analyze the key characteristics of the Manifoldron such as manifold characterization capability and its link to neural networks. The experimental results on 4 synthetic examples, 20 public benchmark datasets, and 1 real-world application demonstrate that the proposed Manifoldron performs competitively compared to the mainstream machine learning models. We have shared our code in \url{https://github.com/wdayang/Manifoldron} for free download and evaluation.
BibTeX
@article{wang2022manifoldron,
  author = {Dayang Wang and Feng-Lei Fan and Bojian Hou and Hao Zhang and Rongjie Lai and Hengyong Yu and Fei Wang},
  title = {{Manifoldron: Direct Space Partition via Manifold Discovery}},
  journal = {IEEE TNNLS},
  year = {2022},
  doi = {10.1109/tnnls.2024.3486252},
}
Figure