Contrastive Feature Induction for Efficient Structure Learning of
  Conditional Random Fields
  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.
