Selecting features of linear-chain conditional random fields via greedy stage-wise algorithms

This paper presents two embedded feature selection algorithms for linear-chain CRFs named GFSA_LCRF and PGFSA_LCRF. GFSA_LCRF iteratively selects a feature incorporating which into the CRF will improve the conditional log-likelihood of the CRF most at one time. For time efficiency, only the weight of the new feature is optimized to maximize the log-likelihood instead of all weights of features in the CRF. The process is iterated until incorporating new features into the CRF can not improve the log-likelihood of the CRF noticeably. PGFSA_LCRF adopts pseudo-likelihood as evaluation criterion to iteratively select features to improve the speed of GFSA_LCRF. Furthermore, it scans all candidate features and forms a small feature set containing some promising features at certain iterations. Then, the small feature set will be used by subsequent iterations to further improve the speed. Experiments on two real-world problems show that CRFs with significantly fewer features selected by our algorithms achieve competitive performance while obtaining significantly shorter testing time.