Towards easier and faster sequence labeling for natural language processing: A search-based probabilistic online learning framework (SAPO)

摘要

There are two major approaches for structured classification. One is theprobabilistic gradient-based methods such as conditional random fields (CRF),which has high accuracy but with drawbacks: slow training, and no support ofsearch-based optimization (which is important in many cases). The other one isthe search-based learning methods such as perceptrons and margin infusedrelaxed algorithm (MIRA), which have fast training but also with drawbacks: lowaccuracy, no probabilistic information, and non-convergence in real-worldtasks. We propose a novel and "shockingly easy" solution, a search-basedprobabilistic online learning method, to address most of those issues. Thismethod searches the output candidates, derives probabilities, and conductefficient online learning. We show that this method is with fast training,support search-based optimization, very easy to implement, with top accuracy,with probabilities, and with theoretical guarantees of convergence. Experimentson well-known tasks show that our method has better accuracy than CRF andalmost as fast training speed as perceptron and MIRA. Results also show thatSAPO can easily beat the state-of-the-art systems on those highly-competitivetasks, achieving record-breaking accuracies.