Safe Screening for Sparse Conditional Random Fields
This work addresses computational efficiency for researchers and practitioners in computer vision and NLP using sparse CRFs, though it is incremental as it builds on existing screening methods.
The paper tackles the challenge of solving sparse Conditional Random Fields (CRFs) in large-scale applications by proposing a novel safe dynamic screening method that uses dual optimum estimation to remove irrelevant features during training, reducing computational cost without sacrificing accuracy, with experimental results showing significant speedup.
Sparse Conditional Random Field (CRF) is a powerful technique in computer vision and natural language processing for structured prediction. However, solving sparse CRFs in large-scale applications remains challenging. In this paper, we propose a novel safe dynamic screening method that exploits an accurate dual optimum estimation to identify and remove the irrelevant features during the training process. Thus, the problem size can be reduced continuously, leading to great savings in the computational cost without sacrificing any accuracy on the finally learned model. To the best of our knowledge, this is the first screening method which introduces the dual optimum estimation technique -- by carefully exploring and exploiting the strong convexity and the complex structure of the dual problem -- in static screening methods to dynamic screening. In this way, we can absorb the advantages of both the static and dynamic screening methods and avoid their drawbacks. Our estimation would be much more accurate than those developed based on the duality gap, which contributes to a much stronger screening rule. Moreover, our method is also the first screening method in sparse CRFs and even structure prediction models. Experimental results on both synthetic and real-world datasets demonstrate that the speedup gained by our method is significant.