On the Computational Complexity of Approximating Distributions by Probabilistic Automata

Naoki Abe, Manfred K. Warmuth

Abstract

This foundational work by Naoki Abe and Manfred Warmuth provides the first rigorous analysis of the "Probably Approximately Correct" (PAC) learnability of Probabilistic Automata (PAs) and Hidden Markov Models (HMMs). The authors establish that while training these models is efficient in terms of sample complexity, the optimization problem itself is computationally intractable (NP-hard) when the alphabet size is variable. This paper offers a formal justification for common practices like probability "smoothing" and highlights the inherent difficulty in finding global optima for sequence models.

Introduction

In the early 1990s, Probabilistic Automata and Hidden Markov Models were already established as essential tools for sequence modeling, particularly in speech recognition. However, the theoretical guarantees for learning these models were largely absent. Practitioners relied on the Baum-Welch algorithm, an expectation-maximization (EM) approach that finds local optima but provides no global performance guarantees.

Abe and Warmuth addressed this gap by asking: Is there an efficient algorithm that, given a sample of data, is guaranteed to output a model that is "close" to the best possible model? They framed this within the robust PAC learning paradigm, focusing on density estimation—the task of approximating an unknown probability distribution using a specific class of models.

The Probabilistic Automaton Model

A Probabilistic Automaton (PA) is a generative model where transitions between states are governed by probabilities associated with input symbols. Unlike deterministic automata, a PA defines a probability distribution over all possible strings.

Figure 1: An example of a 3-state Probabilistic Automaton showing transitions labeled with symbols (a, b) and their associated probabilities.

The figure above illustrates a typical PA. Each state has outgoing transitions that sum to one (or less, if there is a probability of termination). The goal of learning is to adjust these transition probabilities to best match an observed distribution of strings.

Methods and Theoretical Framework

The authors utilize several key tools from computational learning theory:

  • Kullback-Leibler (KL) Divergence: This metric is used to measure the "distance" between the hypothesis model's distribution and the true target distribution.
  • Uniform Convergence and Hoeffding’s Inequality: These are used to bound the sample complexity. Because KL divergence can be unbounded (e.g., if a model assigns zero probability to a seen event), the authors introduce a "bounded grid" technique. This involves "clamping" transition probabilities above a minimum threshold based on the sample size, providing a mathematical justification for the "smoothing" techniques used in practice.
  • Complexity Reductions: To prove computational hardness, the authors perform a reduction from the 3-SAT problem to the "Maximum Likelihood Model" (MLM) problem for a 2-state PA.

Key Results

Sample Efficiency (The "Good News")

The paper proves that the number of examples required to train a PA is surprisingly low. The sample complexity is essentially linear in the number of transition parameters ($t$) and polynomial in the desired accuracy ($\epsilon$) and confidence ($\delta$). Specifically, a class of PA constraints is shown to be trainable with a sample size of $O((n/\epsilon)^2 t \cdot \log^3(nt/\epsilon))$, where $n$ is the maximum string length.

Computational Intractability (The "Bad News")

Despite the low sample requirements, the optimization process is a significant bottleneck. The authors demonstrate that if the alphabet size is allowed to grow, finding the best 2-state PA is NP-hard. Furthermore, they establish a "strong non-approximability" result: for a 2-state PA, it is NP-hard to approximate the maximum likelihood within a factor of $2^{|w|^{1-\alpha}}$, where $|w|$ is the string length. This implies that even finding a reasonably good model is computationally out of reach in the worst case.

Extension to HMMs

Since HMMs can be efficiently simulated by PAs of the same state size, these hardness and sample complexity results apply directly to HMMs, grounding the limitations of popular speech recognition models in formal complexity theory.

Conclusion and Future Work

Abe and Warmuth's work highlights a fundamental tension in machine learning: a model class can be "learnable" in terms of information (sample complexity) while remaining "unlearnable" in terms of computation.

Future research directions suggested by the authors include:

  • Fixed Alphabets: Determining if training becomes easier when the alphabet size is fixed (e.g., binary).
  • Restricted Architectures: Investigating whether specific structures, such as "left-to-right" HMMs common in speech recognition, are more efficiently trainable.
  • Tightening Bounds: Exploring whether the $1/\epsilon^2$ dependence in sample complexity can be improved to $1/\epsilon$.

This paper remains a cornerstone of the field, reminding researchers that the efficiency of local search heuristics like Baum-Welch is a practical necessity born from the theoretical impossibility of global optimization.

Summary updated

Abstract

We introduce a rigorous performance criterion for training algorithms for probabilistic automata (PAs) and hidden Markov models (HMMs), used extensively for speech recognition, and analyze the complexity of the training problem as a computational problem. The PA training problem is the problem of approximating an arbitrary, unknown source distribution by distributions generated by a PA. We investigate the following question about this important, well-studied problem: Does there exist an *efficient* training algorithm such that the trained PAs *provably converge* to a model close to an optimum one with high confidence, after only a feasibly small set of training data? We model this problem in the framework of computational learning theory and analyze the sample as well as computational complexity. We show that the number of examples required for training PAs is moderate -- essentially linear in the number of transition probabilities to be trained and a low-degree polynomial in the example length and parameters quantifying the accuracy and confidence. Computationally, however, training PAs is quite demanding: Fixed state size PAs are trainable in time polynomial in the accuracy and confidence parameters and example length, but *not* in the alphabet size, unless RP = NP. The latter result is shown via a strong non-approximability result for the single string maximum likelihood model problem for 2-state PAs, which is of independent interest.
BibTeX
@article{abe1992computational,
  author = {Naoki Abe and Manfred K. Warmuth},
  title = {{On the Computational Complexity of Approximating Distributions by Probabilistic Automata}},
  journal = {Machine Learning},
  year = {1992},
  url = {https://openreview.net/forum?id=1oK1xLHvAV},
}

Loading related content...

Figure