Exact Decoding on Latent Variable Conditional Models is NP-Hard

Xu SunarXiv 2014 · arXiv

Abstract

Latent Variable Conditional Models (LVCMs), such as Latent Conditional Random Fields (LCRFs), are powerful tools for modeling hidden structures in data. However, finding the most probable label sequence in these models is computationally challenging. This paper formally proves that exact decoding in LVCMs is NP-hard, even for simple linear-chain structures. To address this, we propose Latent-Dynamic Inference (LDI), an algorithm that leverages A* search and dynamic programming to achieve exact results by exploiting the "probability concentration" observed in trained models.

Introduction: From CRF to LCRF

In standard machine learning models like Conditional Random Fields (CRFs), we map an input sequence $x$ directly to a label sequence $y$. While effective, CRFs are limited in their ability to capture underlying hidden structures. Latent Conditional Random Fields (LCRFs) address this by introducing hidden variables $h$ that represent these unobserved structures—such as sub-gestures in a physical movement or refined grammar rules in a sentence.

Comparison of graphical structures for standard Conditional Random Fields (CRF) and Latent Conditional Random Fields (LCRF).

The Decoding Challenge

The primary difficulty with LCRFs lies in inference. In a standard CRF, the Viterbi algorithm can quickly find the most likely label sequence. However, in an LCRF, each label sequence $y$ is associated with a set of multiple possible latent sequences $h$. To determine the probability of a label sequence $P(y|x)$, one must sum (marginalize) over all possible hidden paths.

Trellis diagram showing the association between label sequences ($y$) and multiple latent sequences ($h$), illustrating the complexity of marginalizing over hidden states.

This paper provides a formal proof that finding the optimal $y$ in this setting is NP-hard. The proof uses a reduction from the Maximum-Clique problem, showing that if an efficient exact decoding algorithm existed for LCRFs, it could also solve one of graph theory's most difficult problems.

Latent-Dynamic Inference (LDI)

To overcome this NP-hardness in practice, the author introduces Latent-Dynamic Inference (LDI). LDI is an exact inference algorithm that combines A* search with dynamic programming.

Instead of calculating the probability for every possible sequence, LDI uses a "tight" heuristic to search for latent sequences ($h$) in order of their individual probabilities. It then maps these to their parent label sequences ($y$) and uses a forward-backward style algorithm to calculate total probabilities. The algorithm terminates as soon as it reaches an "Exact-Condition"—a point where the remaining unsearched probability mass is too small to change the current best result.

Why LDI Works: Probability Concentration

The success of LDI is rooted in a phenomenon called "probability concentration." During training, the model's parameters are optimized to favor latent sequences that already have high probabilities. This creates a "peaky" distribution where a tiny fraction of hidden sequences carries nearly all the probability mass. Because of this concentration, LDI only needs to explore a small number of paths before finding the guaranteed optimal solution.

Conclusion

While exact decoding in latent variable models is theoretically NP-hard, this research demonstrates that it is not practically impossible. By understanding the underlying probability distributions of trained models, the LDI algorithm provides a path toward exact, efficient inference in complex structured prediction tasks.

Summary updated

Abstract

Latent variable conditional models, including the latent conditional random fields as a special case, are popular models for many natural language processing and vision processing tasks. The computational complexity of the exact decoding/inference in latent conditional random fields is unclear. In this paper, we try to clarify the computational complexity of the exact decoding. We analyze the complexity and demonstrate that it is an NP-hard problem even on a sequential labeling setting. Furthermore, we propose the latent-dynamic inference (LDI-Naive) method and its bounded version (LDI-Bounded), which are able to perform exact-inference or almost-exact-inference by using top-$n$ search and dynamic programming.
BibTeX
@misc{sun2014exact,
  author = {Xu Sun},
  title = {{Exact Decoding on Latent Variable Conditional Models is NP-Hard}},
  year = {2014},
  eprint = {1406.4682},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1406.4682},
}
Figure