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.
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