Boosting-based Construction of BDDs for Linear Threshold Functions and Its Application to Verification of Neural Networks

Yiping Tang, Kohei Hatano, Eiji TakimotoarXiv 2023 · arXiv

TL;DR

This paper introduces a novel machine learning boosting approach to convert the neurons of a neural network—represented as Linear Threshold Functions (LTFs)—into compact Aligned Binary Decision Diagrams (ABDDs) for formal verification. By eliminating the need to search through an exponential number of variable orderings ($n!$), this method generates smaller Boolean expressions much faster, particularly when the network's neurons exhibit large classification margins.

What Problem Does This Paper Address?

Formal verification is crucial for ensuring that neural networks (NNs) are safe and robust against adversarial attacks. One promising strategy is to translate a neural network into an equivalent Boolean expression (such as a Binary Decision Diagram, or BDD). Once converted, researchers can leverage decades of highly optimized hardware and circuit verification tools to prove network properties.

However, a major bottleneck lies in converting individual neurons—which function as Linear Threshold Functions (LTFs)—into BDDs. Existing exact methods require finding an optimal variable ordering out of $n!$ possibilities to prevent the BDD size from exploding exponentially. Choosing a good ordering is notoriously difficult and computationally prohibitive, severely limiting the scalability of neural network verification.

Methods

The authors tackle this bottleneck by introducing a top-down, greedy boosting algorithm that constructs a specific variant of a BDD called an Aligned BDD (ABDD).

Unlike standard BDDs or Ordered BDDs (OBDDs), an ABDD enforces a strict structural constraint: all nodes at the exact same depth must be labeled with the same variable.

Figure 1: Examples of BDD (A), OBDD (B) and ABDD (C). To express the same linear threshold function in BDD form: nodes at the same depth can be labeled by different variables, which means that the number of variables does not limit the depth of BDD; in OBDD form: the nodes at the same depth are all labeled by the same variables, which results in the depth of OBDD is smaller than the number of variables; in ABDD form: nodes at the same depth are labeled by the same variables, and the depth of ABDD only depends on the reduction of entropy to 0 in our algorithm.

The construction pipeline works as follows:

  1. The Boosting Framework: Inspired by classic top-down decision tree learning (specifically the work of Mansour and McAllester), the algorithm builds the ABDD layer-by-layer.
  2. Split Step: At each layer, the algorithm selects a single variable (a base classifier) that maximizes an information-theoretic criterion based on a newly introduced variant balanced distribution ($\hat{d}$).
  3. Merge Step: To keep the diagram compact, the algorithm merges similar nodes within the same layer using a mathematical structure called a $(\delta, \lambda)$-net.
Figure 2: Illustration of our boosting algorithm. The blue dotted line part represents the process of merging the split temporary nodes into new nodes by searching the equivalence space that does not appear in the ABDD. Following algorithm 1, we find some hypothesis h to construct child nodes in the new layer and then merge nodes afterward.
  1. Circuit Conversion: Once the ABDDs are built for each neuron, they are wired together according to the network's topology to form a massive $(\lor, \land, \neg)$-circuit, which can then be compiled into a Sentential Decision Diagram (SDD) for final robustness verification.

Datasets

The authors evaluated their approach using the USPS digits dataset, a standard benchmark consisting of $16 \times 16$ binary pixel images of handwritten digits. They focused on the binary classification task of distinguishing between the digits 0 and 1. This data was used to train 10 different Convolutional Neural Networks (CNNs) containing two convolutional layers and one fully connected layer, which served as the verification targets.

Key Insights and Ideas

  • The Power of Alignment: Intuitively, forcing every node at a given depth to use the exact same variable seems like a restriction that would yield larger diagrams. Surprisingly, the authors found the opposite: this alignment makes the node-merging process drastically more effective in practice, resulting in much smaller final diagrams.
  • Margin-Driven Complexity: The size of the generated ABDD is theoretically bounded by the margin ($\rho$) of the LTF. If a neuron classifies its training samples with a wide margin, the algorithm guarantees a small BDD size ($O(\frac{n^2}{\rho^4}\ln{\frac{1}ρ})$), completely bypassing the need to search through $n!$ variable orderings.
  • Accelerated Entropy Reduction: During the top-down construction, once node merging begins, the total entropy of the ABDD drops at a significantly faster rate than standard BDD approaches.
Total entropy change at each depth for ABDD vs BDD.

Key Results

  • Fewer Gates: In evaluations across 10 different CNN architectures, the proposed method consistently generated circuits with far fewer gates than competing techniques. For example, on the first network configuration (ID 1), the authors' method required only 3,737 gates, compared to 5,536 gates for the baseline OBDD method (Shi.1) and over 48,000 gates for alternative precision-based methods (Shi.2).
  • Faster Verification: Because the resulting Boolean circuits were significantly more compact, the time required to run Sample-based Robustness (SR) verification algorithms was substantially reduced.

Limitations and Future Work

While the boosting approach successfully avoids the $n!$ variable ordering search, its time complexity still scales with $2^n$ because it evaluates all possible instances of the LTF. As a result, this method is currently restricted to smaller input dimensions or networks with small localized receptive fields (like the $3 \times 3$ convolutions tested).

For future work, the authors aim to extend this boosting framework to handle more complex, non-binary, and larger-scale neural network architectures.

Summary updated

Abstract

Understanding the characteristics of neural networks is important but difficult due to their complex structures and behaviors. Some previous work proposes to transform neural networks into equivalent Boolean expressions and apply verification techniques for characteristics of interest. This approach is promising since rich results of verification techniques for circuits and other Boolean expressions can be readily applied. The bottleneck is the time complexity of the transformation. More precisely, (i) each neuron of the network, i.e., a linear threshold function, is converted to a Binary Decision Diagram (BDD), and (ii) they are further combined into some final form, such as Boolean circuits. For a linear threshold function with $n$ variables, an existing method takes $O(n2^{\frac{n}{2}})$ time to construct an ordered BDD of size $O(2^{\frac{n}{2}})$ consistent with some variable ordering. However, it is non-trivial to choose a variable ordering producing a small BDD among $n!$ candidates. We propose a method to convert a linear threshold function to a specific form of a BDD based on the boosting approach in the machine learning literature. Our method takes $O(2^n \text{poly}(1/ρ))$ time and outputs BDD of size $O(\frac{n^2}{ρ^4}\ln{\frac{1}ρ})$, where $ρ$ is the margin of some consistent linear threshold function. Our method does not need to search for good variable orderings and produces a smaller expression when the margin of the linear threshold function is large. More precisely, our method is based on our new boosting algorithm, which is of independent interest. We also propose a method to combine them into the final Boolean expression representing the neural network.
BibTeX
@misc{tang2023boosting,
  author = {Yiping Tang and Kohei Hatano and Eiji Takimoto},
  title = {{Boosting-based Construction of BDDs for Linear Threshold Functions and Its Application to Verification of Neural Networks}},
  year = {2023},
  eprint = {2306.05211},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.05211},
}
Figure