Fast and Robust Wrapper Method for $N$ -gram Feature Template Induction in Structured Prediction

N-gram feature templates that consider consecutive contextual information comprise a family of important feature templates used in structured prediction. Some previous studies considered the n-gram feature selection problem but they focused on one or several types of features in certain tasks, e.g., consecutive words in a text categorization task. In this paper, we propose a fast and robust bottom-up wrapper method for automatically inducing n-gram feature templates, which can induce any type of n-gram feature for any structured prediction task. According to the significance distribution for n-gram feature templates based on the n-gram and bias (offset), the proposed method first determines the n-gram that achieves the best tradeoff between the severity of the sparse data problem with n-gram feature templates and the richness of the corresponding contextual information, before combining the best n-gram with lower-order gram templates in an extremely efficient manner. In addition, our method uses a template pair, i.e., the two symmetrical templates, rather than a template as the basic unit (i.e., including or excluding a template pair rather than a template). Thus, when the data in the training set change slightly, our method is robust to this fluctuation, thereby providing a more consistent induction result compared with the template-based method. The experimental results obtained for three tasks, i.e., Chinese word segmentation, named entity recognition, and text chunking, demonstrated the effectiveness, efficiency, and robustness of the proposed method.