Robust Learning of Tractable Probabilistic Models

Rohith Peddi, Tahrima Rahman, Vibhav Giridhar GogateUAI 2022 · OpenReview

Abstract

Tractable probabilistic models (TPMs) compactly represent a joint probability distribution over a large number of random variables and admit polynomial time computation of (1) exact likelihoods; (2) marginal probability distributions over a small subset of variables given evidence; and (3) in some cases most probable explanations overall non-observed variables given observations. In this paper, we leverage these tractability properties to solve the robust maximum likelihood parameter estimation task in TPMs under the assumption that a TPM structure and complete training data is provided as input. Specifically, we show that TPMs learned by optimizing the likelihood perform poorly when data is subject to adversarial attacks/noise/perturbations/corruption and we can address this issue by optimizing robust likelihood. To this end, we develop an efficient approach for constructing uncertainty sets that model data corruption in TPMs and derive an efficient gradient-based local search method for learning TPMs that are robust against these uncertainty sets. We empirically demonstrate the efficacy of our proposed approach on a collection of benchmark datasets.

Introduction

In the realm of generative AI, deep models like Variational Autoencoders (VAEs) and Generative Adversarial Networks (GANs) are highly expressive but often struggle with efficient, exact probabilistic inference. Tractable Probabilistic Models (TPMs), such as Sum-Product Networks (SPNs) and Cutset Networks (CNs), address this by guaranteeing polynomial-time computation for complex queries like marginal probabilities and exact likelihoods.

However, TPMs are traditionally trained using Maximum Likelihood Estimation (MLE), which assumes the training data is clean and representative of the true distribution. In real-world scenarios, data is frequently corrupted by measurement errors, noise, or malicious adversaries. While the robustness of deep generative models has been extensively studied, the vulnerability of TPMs to corrupted data has been largely overlooked. This research bridges that gap by developing methods to train TPMs that remain resilient under adversarial data perturbations.

Methodology: Robust Optimization for TPMs

The core of the proposed approach is a Robust Optimization (RO) framework formulated as a max-min game. Instead of maximizing the likelihood of the observed data, the model parameters are optimized to perform well against the worst-case perturbations within a defined uncertainty set.

The Max-Min Framework

  1. The Adversary (Minimizer): Attempts to corrupt the training data to minimize the model's likelihood. These corruptions are constrained within a deterministic uncertainty set defined by a maximum Hamming distance $h$, allowing the adversary to flip up to $h$ bits per sample.
  2. The Optimizer (Maximizer): Updates the model parameters $\theta$ to maximize the likelihood on this worst-case corrupted data.
Algorithm 1: Robust learning procedure for TPMs using a max-min optimization strategy.

Because exact inner minimization is computationally expensive for complex TPM structures, the authors employ an efficient greedy local search algorithm. By leveraging Danskin's theorem, they compute gradients based on the worst-case perturbed data and update parameters iteratively. To prevent performance degradation on clean data, a Regularized Maximum Likelihood Estimator is introduced, which jointly optimizes standard and robust likelihoods.

Experimental Evaluation

The approach was evaluated on 20 standard benchmark datasets (e.g., Plants, Netflix, DNA) and the binarized MNIST dataset. Robustness was tested against two types of corrupted test sets: Fully Adversarial ($T_a$) and Randomly Perturbed ($T_r$).

Key Findings

  • Brittleness of Standard MLE: Standard TPMs show a significant drop in log-likelihood when even a few bits per sample are flipped (Hamming distance $h=3$ or $5$).
  • Latent Variable Sensitivity: Models with latent variables, like SPNs, are more vulnerable to attacks than simpler structures like Cutset Networks (CNs).
  • Quantitative Performance: Robust models vastly outperformed standard models on corrupted data. For example, on the Netflix dataset with an attack budget of $h=5$, a standard SPN's log-likelihood dropped to -72.06, whereas the regularized robust SPN (SPN-r) achieved -67.69.

Qualitative Results

The efficacy of the robust learning approach is most visible in image completion tasks on MNIST. When presented with corrupted input, standard models fail to reconstruct the original digits, whereas the robust models successfully ignore the noise.

Qualitative comparison of image completion on MNIST. The robust model ("OURS") accurately reconstructs digits from corrupted "Covered Images," while the standard model ("EINET") fails.

Conclusion and Future Work

This work demonstrates that TPMs can be made robust to data corruption through a principled max-min optimization framework. While the current greedy local search is effective, future work could explore more complex uncertainty sets, such as those based on Wasserstein distance, and develop theoretical bounds for robust generalization in tractable models.

Summary updated

Abstract

Tractable probabilistic models (TPMs) compactly represent a joint probability distribution over a large number of random variables and admit polynomial time computation of (1) exact likelihoods; (2) marginal probability distributions over a small subset of variables given evidence; and (3) in some cases most probable explanations overall non-observed variables given observations. In this paper, we leverage these tractability properties to solve the robust maximum likelihood parameter estimation task in TPMs under the assumption that a TPM structure and complete training data is provided as input. Specifically, we show that TPMs learned by optimizing the likelihood perform poorly when data is subject to adversarial attacks/noise/perturbations/corruption and we can address this issue by optimizing robust likelihood. To this end, we develop an efficient approach for constructing uncertainty sets that model data corruption in TPMs and derive an efficient gradient-based local search method for learning TPMs that are robust against these uncertainty sets. We empirically demonstrate the efficacy of our proposed approach on a collection of benchmark datasets.
BibTeX
@inproceedings{peddi2022robust,
  author = {Rohith Peddi and Tahrima Rahman and Vibhav Giridhar Gogate},
  title = {{Robust Learning of Tractable Probabilistic Models}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=Sg-UEuUj5xq},
}
Figure