Exact Decoding on Latent Variable Conditional Models is NP-Hard
This addresses a fundamental computational challenge for researchers and practitioners using latent variable models in NLP and vision, though it is incremental in clarifying complexity rather than solving it.
The paper tackles the computational complexity of exact decoding in latent variable conditional models, proving it is NP-hard even for sequential labeling, and proposes LDI-Naive and LDI-Bounded methods for exact or near-exact inference using top-n search and dynamic programming.
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.