Contrastive Feature Induction for Efficient Structure Learning of Conditional Random Fields
This addresses efficiency issues in high-dimensional CRF structure learning for applications like statistical relational learning, though it is incremental as it builds on existing gradient-based approaches.
The paper tackles the high computational cost of evaluating candidate features in structure learning of Conditional Random Fields (CRFs) by proposing Contrastive Feature Induction (CFI), which efficiently approximates gradient-based methods by focusing on subsets of features involving high signals and errors, resulting in competitive learning speed and accuracy compared to state-of-the-art methods.
Structure learning of Conditional Random Fields (CRFs) can be cast into an L1-regularized optimization problem. To avoid optimizing over a fully linked model, gain-based or gradient-based feature selection methods start from an empty model and incrementally add top ranked features to it. However, for high-dimensional problems like statistical relational learning, training time of these incremental methods can be dominated by the cost of evaluating the gain or gradient of a large collection of candidate features. In this study we propose a fast feature evaluation algorithm called Contrastive Feature Induction (CFI), which only evaluates a subset of features that involve both variables with high signals (deviation from mean) and variables with high errors (residue). We prove that the gradient of candidate features can be represented solely as a function of signals and errors, and that CFI is an efficient approximation of gradient-based evaluation methods. Experiments on synthetic and real data sets show competitive learning speed and accuracy of CFI on pairwise CRFs, compared to state-of-the-art structure learning methods such as full optimization over all features, and Grafting.