The BeMi Stardust: a Structured Ensemble of Binarized Neural Networks

Ambrogio Maria Bernardelli, Stefano Gualandi, Hoong Chuin Lau, Simone Milanesi

Abstract

Training neural networks with discrete weights—such as Binarized Neural Networks (BNNs)—presents a significant challenge for gradient-based optimization due to the non-differentiable nature of the weight space. While Mixed-Integer Linear Programming (MILP) offers a path toward exact solutions, it historically struggles with scalability. This paper discusses the "BeMi" framework, which overcomes these limitations through a combination of lexicographic multi-objective optimization and a structured "One-Versus-One" (OvO) ensemble architecture. Our results demonstrate that BeMi significantly outperforms previous solver-based methods in few-shot learning tasks, achieving high accuracy on MNIST and Fashion-MNIST while maintaining extreme model sparsity.

Introduction

The proliferation of deep learning in industrial embedded systems and edge computing has intensified the need for resource-efficient models. Binarized Neural Networks (BNNs) and Integer Neural Networks (INNs), which utilize weights restricted to $\pm1$ or small integer sets, are ideal for these environments due to their minimal memory footprint and reliance on efficient boolean or integer arithmetic.

However, training these networks is notoriously difficult. Standard gradient descent requires smooth, differentiable loss surfaces, which discrete weights do not provide. While combinatorial optimization solvers like MILP can find optimal discrete weights, they are computationally expensive and typically fail to scale beyond very small datasets. The BeMi framework addresses these challenges by restructuring the optimization problem into manageable, parallelizable components.

Methodology

The BeMi approach introduces two primary innovations to the training of discrete networks.

1. Lexicographic Multi-Objective Optimization

Rather than optimizing for a single accuracy metric, the MILP solver follows a prioritized three-step objective function:

  • Sat-Margin: The primary goal is to maximize the number of correctly classified training samples.
  • Max-Margin: To enhance generalization and robustness against input perturbations, the solver maximizes the "margin" of the neurons.
  • Min-Weight: Finally, the solver minimizes the number of active (non-zero) weights, promoting extreme sparsity.

2. Structured One-Versus-One Ensemble

To solve the scalability issue, BeMi decomposes a multi-class classification problem into a series of binary sub-problems. For a dataset with $k$ classes, the framework trains $k(k-1)/2$ tiny networks, each specialized in distinguishing between a specific pair of classes (e.g., "4 vs 9"). At inference time, a majority voting scheme aggregates the outputs of these networks. This "divide and conquer" strategy ensures that each MILP problem remains small enough for efficient solving, even as the total training data increases.

Experimental Evaluation

The researchers evaluated BeMi across three benchmarks: MNIST (handwritten digits), Fashion-MNIST (clothing items), and the UCI Heart Disease dataset (low-dimensional medical data).

Performance in Few-Shot Learning

BeMi demonstrated a substantial improvement over previous state-of-the-art solver-based methods. On the MNIST dataset with only 10 images per class, BeMi achieved 68.4% accuracy, compared to the previous benchmark of 51.1%. When the training set was increased to 40 images per class, accuracy reached 81.8%.

Model Sparsity and Weight Distribution

A key finding was the framework's ability to produce highly compressed models. In the MNIST experiments, up to 75.3% of network links were pruned (set to zero) without a loss in performance. Furthermore, when training INNs with a wider range of allowed integer weights, the solver exhibited "Spontaneous Magnitude Pruning." Weights tended to cluster at the extreme boundaries (e.g., $\pm P$) or at zero, suggesting that binary-like structures are often mathematically optimal for these tasks.

Discussion and Limitations

The success of BeMi highlights the potential of using exact solvers for few-shot learning in constrained environments. By explicitly optimizing for margins, the framework achieves better generalization than previous discrete optimization attempts.

However, several challenges remain. The OvO ensemble architecture scales quadratically with the number of classes, making it difficult to apply to large-scale datasets like ImageNet without further modification. Additionally, the performance of few-shot models is inherently sensitive to the specific samples selected for training.

Conclusion

The BeMi framework represents a significant step forward in training discrete neural networks using mathematical solvers. By combining structured ensembles with multi-objective optimization, it provides a robust solution for high-accuracy, high-sparsity learning in data-scarce and hardware-limited environments. Future research will focus on improving class scaling and exploring more stable data selection techniques to further enhance the framework's utility.

Summary updated

BibTeX
@inproceedings{bernardelli2023bemi,
  author = {Ambrogio Maria Bernardelli and Stefano Gualandi and Hoong Chuin Lau and Simone Milanesi},
  title = {{The BeMi Stardust: a Structured Ensemble of Binarized Neural Networks}},
  booktitle = {LION},
  year = {2023},
  doi = {10.1007/978-3-031-44505-7\_30},
}
Figure