Abstract
We present a discriminative learning algorithm for Sum-Product Networks (SPNs) based on the Extended Baum-Welch (EBW) algorithm. We formulate the conditional data likelihood in the SPN framework as a rational function, and we use EBW to monotonically maximize it. We derive the algorithm for SPNs with both discrete and continuous variables. The experiments show that this algorithm performs better than both generative Expectation-Maximization, and discriminative gradient descent on a wide variety of applications. We also demonstrate the robustness of the algorithm in the case of missing features by comparing its performance to Support Vector Machines and Neural Networks.
Introduction
Sum-Product Networks (SPNs) have emerged as a powerful class of deep probabilistic models capable of exact and efficient marginal inference, a task that is often intractable in traditional graphical models. Despite their advantages, training SPNs effectively for classification remains a significant challenge. Most existing training paradigms are generative, focusing on modeling the joint distribution $P(X, Y)$. While robust, generative models often allocate modeling capacity to features that do not contribute to class discrimination.
Discriminative training, which models the conditional distribution $P(Y|X)$ directly, is typically preferred for classification accuracy. However, standard discriminative approaches often rely on Gradient Descent (GD), which is prone to vanishing gradients in deep architectures and requires meticulous hyperparameter tuning. This paper introduces a discriminative learning algorithm based on the Extended Baum-Welch (EBW) technique, providing a mathematically principled alternative that ensures monotonic improvement.
Methodology: The EBW Approach
The core innovation of this work is the application of the Extended Baum-Welch algorithm to the SPN framework. The researchers recognized that the conditional likelihood $P(Y|X)$ in an SPN can be expressed as a rational function—a ratio of two polynomials. EBW is uniquely suited to maximize such functions.
SPN Architecture for Classification
To perform classification, the SPN is structured such that the root node represents a sum over class-specific sub-networks. This hierarchical arrangement allows the model to share features across classes while maintaining distinct pathways for class-specific evidence.
As shown in the figure, the root node $F_{root}$ aggregates sub-networks $F_{root}^1, \dots, F_{root}^Y$ corresponding to each class. The conditional probability $P(y=k|x)$ is then calculated as the ratio of the $k$-th sub-network to the total root sum. This structure is the basis for the derived "growth transforms"—update rules that guarantee the conditional likelihood increases or remains constant at each iteration.
Universal Applicability
The authors derived specific update formulas for both discrete variables (multinomial) and continuous variables (univariate Gaussian leaves). A critical component of EBW is the smoothing constant $D$, which regulates parameter change. The paper provides a heuristic for scheduling $D$ to balance the trade-off between stability and convergence speed.
Experimental Evaluation
The algorithm was evaluated across eight diverse datasets, including UCI/Kaggle public sets (e.g., MNIST, Banknote, Sensorless Drive) and a private industrial fault detection dataset from Huawei. These datasets varied in complexity, ranging from 4 to 784 variables and up to 41 classes.
Key Results
- Superior Accuracy: EBW-trained SPNs outperformed generative EM on all eight datasets, demonstrating the clear advantage of discriminative modeling in classification tasks.
- Convergence and Stability: In comparisons with discriminative Gradient Descent, EBW reached superior solutions in fewer epochs. Unlike GD, which struggled with vanishing gradients in deep SPNs, EBW remained robust and continued to find high-quality optima.
- Visualizing Discrimination: Sampling from the models revealed that while generative SPNs learn the "average" look of a class (e.g., a generic digit), discriminative SPNs focus on the specific features that distinguish one class from another, such as the unique curves that differentiate a '3' from an '8'.
Robustness to Missing Data
A unique strength of SPNs is their ability to handle missing features by "summing them out" during inference. This study demonstrates that discriminative training significantly enhances this inherent robustness. In tests where 50% of input features were randomly removed, EBW-trained SPNs maintained high accuracy, significantly outperforming Support Vector Machines (SVMs) and Neural Networks (NNs). For instance, on the Banknote dataset with 50% missing data, the SPN achieved 94.9% accuracy, while the SVM's performance dropped to 54.7%.
Conclusion and Future Work
The Extended Baum-Welch algorithm provides a robust, monotonic framework for discriminative SPN training that avoids the pitfalls of gradient-based methods. While highly effective for parameter learning, the method currently assumes a fixed network structure. Future research may explore integrating EBW with structure learning algorithms to automatically discover the optimal connectivity of sums and products. Additionally, while marginal inference is efficient, the intractability of Marginal MAP inference remains a challenge for future optimization strategies.
Summary updated