Explainable AI

OBDD Encoding & Inference

OBDD-NET takes an example as input and evaluates its satisfaction against the learned OBDD. The model's structure consists of nodes partitioned into H+1 distinct levels, where H is the depth. Each level (except root/terminal) contains 2^(H-1) nodes, covering the full search space. Trainable parameters include: @dec (degree of probability a level is associated with a feature), @left (probability of taking a 1-edge to a child node), and @right (probability of taking a 0-edge to a child node).

An "OBDD encoding" restricts these parameters to [0,1]. The @dec parameters allow for automatic feature selection and optimized feature ordering. The @left and @right parameters determine child node probabilities. The satisfaction relation (ESat(θ, w)) is computed recursively via k-reachability vectors, simulating OBDD inference in a continuous space. This "faithful OBDD encoding" ensures a direct correspondence between the neural network's learned parameters and a valid OBDD representation, allowing interpretation without a performance gap.

Learning OBDDs by Encoding

OBDD-NET leverages a "faithful OBDD encoding" for gradient-based learning. The network structure is built using a softmax operation on parameters, satisfying structural properties of a BDD (e.g., unique feature per non-terminal level, exactly one left/right child, children at a greater level). This allows end-to-end optimization.

The primary objective is to maximize consistency with the dataset, formulated as a mean squared error loss (Lo). To address vanishing gradients, a differentiable approximation (σ'01) replaces the non-differentiable step function. Additional regularization losses (L1, L2, L3) enforce constraints for faithfulness:

• L1 ensures each feature appears at most once per non-terminal level.
• L2 and L3 (cross-entropy terms) promote binarization of parameters, approximating the 0/1 assignment required for true OBDDs.

The final objective is a weighted sum of Lo and regularization losses. After training, the model is interpreted into an ROBDD by converting parameters to binary (e.g., setting the maximal @dec value to 1 for each level, others to 0), ensuring faithful representation. A post-processing step reduces the OBDD to a unique ROBDD.

Experiments & Results

OBDD-NET was evaluated against state-of-the-art OBDD learners (OODG, MaxSAT-BDD, Shati et al.'s approach) on 10 small and 8 large datasets. Key findings:

• Scalability: OBDD-NET significantly outperforms SOTAs on large datasets, handling up to million-size datasets where other methods timeout due to massive encoding sizes.
• Prediction Performance: OBDD-NET achieves competitive accuracy and Macro-F1 scores, outperforming SOTAs on 14 out of 18 datasets. On large datasets, it shows improvements of over 3% in accuracy and 4% in Macro-F1.
• Rule Size: OODG generally produces the smallest rules, followed by OBDD-NET and Shati's approach. However, OODG often suffers from poor prediction quality.
• Ablation Study: A "relaxed" version of OBDD-NET (using sigmoid instead of softmax for parameter binarization and no regularization for faithfulness) showed significantly poorer classification performance, validating the importance of faithful encoding.
• Impact of Depth: Increasing depth generally improves accuracy but can lead to training challenges due to exponentially greater search space. This can be alleviated by adjusting the network width.

The results demonstrate OBDD-NET's superior scalability and competitive performance, making it a viable solution for learning interpretable AI models from industrial-scale data.

Discussions & Future Work

The current design of OBDD-NET has two main limitations:

1. Depth Limitations: While effective for small-depth OBDDs, similar to other gradient-based structure learning techniques for logical rules, it may struggle with very deep and complex formulas. However, complex formulas can often be simplified.
2. Binary Features Only: OBDD-NET is currently limited to binary classification with binarized features, relying on conventional pre-processing. This hinders end-to-end learning of more general decision diagrams.

Future work will address these limitations by extending the approach to handle real-valued features and Multi-valued Decision Diagrams (MDDs), integrating advanced differentiable binarization techniques. This would allow for more comprehensive end-to-end learning without relying on external feature binarization. Further research will also explore techniques to enhance the model's ability to learn larger-depth OBDDs more efficiently.