Structured prediction tasks, such as parsing sentences or extracting information from contact cards, often face a trade-off between accuracy and computational efficiency. While complex models like semi-Markov Conditional Random Fields (CRFs) provide high accuracy, their decoding process—typically using the Viterbi algorithm—can be prohibitively slow, scaling quadratically or cubically with sequence length. This paper introduces a novel approach to bridge this gap by learning A* search heuristics that use a fast, simple model to guide the search of a complex, accurate one.
The Challenge of Admissible Heuristics
A search offers a faster alternative to Viterbi by using a "heuristic" to prune the search space. To guarantee an optimal solution, the heuristic must be an admissible underestimate*, meaning it never overestimates the remaining cost to reach the goal. However, deriving tight, admissible heuristics manually is mathematically difficult and must be redone for every new model.
Methodology: Probable Approximate Underestimates (PAU)
The authors propose relaxing the strict requirement of admissibility. They introduce the Probable Approximate Underestimate (PAU), a heuristic that is allowed to be an underestimate "most of the time" within a small error margin ($\delta$). They prove that using a PAU still yields solutions that are provably near-optimal with high probability.
The core technique involves a hierarchy of models:
- The Complex Model: A semi-Markov model that is accurate but computationally expensive ($O(n^2)$).
- The Simple Model: A linear-chain model that is less accurate but very fast ($O(n)$).
By treating the parameters of the Simple Model as variables in an optimization problem, the authors use unlabeled data to train it to mimic the "cost-to-go" of the Complex Model. They enforce the "underestimate" constraint via a margin-based optimization similar to Support Vector Machines (SVMs). This allows the system to learn from raw, unlabeled text, "sharpening" the A* search without requiring additional human-labeled data.
Key Results and Performance
The approach was evaluated on a Contact Fragment Labeling task, involving the identification of 24 distinct labels (e.g., FirstName, JobTitle) across approximately 1,500 test records.
As shown in the results table, the learned A search (A-SCMM) achieved a decoding time of 2.26, compared to 7.17 for the standard Viterbi-SCMM—a speedup of over 3x. Crucially, this efficiency gain came with virtually no loss in accuracy; the Token Error Rate (TER) remained nearly identical (0.927 for Viterbi vs. 0.923 for A*, where higher values indicate better performance in this context).
The efficiency of the learned heuristic is particularly evident as sequences grow longer. While A* search carries a small overhead for managing a priority queue—making it less effective for very short sequences—the speedup scales significantly with record length, reaching a factor of 3.5x for the longest records in the dataset.
Conclusion
By moving from "guaranteed optimal" to "probably approximate," this research demonstrates that machine learning can be used to automatically generate effective search heuristics. This "inference guiding inference" framework allows practitioners to deploy highly complex models that were previously too slow for real-time applications, leveraging unlabeled data to optimize the search process itself.
Summary updated