Citation
Tianqi Chen, Sameer Singh, Ben Taskar, Carlos Guestrin. "Efficient Second-Order Gradient Boosting for Conditional Random Fields". International Conference on Artificial Intelligence and Statistics (AISTATS), 2015.

Abstract
Conditional random fields (CRFs) are an important class of models for accurate structured prediction, but effective design of the feature functions is a major challenge when applying CRF models to real world data. Gradient boosting, which is used to automatically induce and select feature functions, is a natural candidate solution to the problem. However, it is non-trivial to derive gradient boosting algorithms for CRFs due to the dense Hessian matrices introduced by variable dependencies. Existing approaches thus use only first-order information when optimizing likelihood, and hence face convergence issues. We incorporate second-order information by deriving a Markov Chain mixing rate bound to quantify the dependencies, and introduce a gradient boosting algorithm that iteratively optimizes an adaptive upper bound of the objective function. The resulting algorithm induces and selects features for CRFs via functional space optimization, with provable convergence guarantees. Experimental results on three real world datasets demonstrate that the mixing rate based upper bound is effective for learning CRFs with non-linear potentials.

Electronic downloads

• https://www.src.org/library/publication/p073168/. (Link to paper on SRC website.)

• HTML

  Tianqi Chen, Sameer Singh, Ben Taskar, Carlos Guestrin.
  <a
  href="http://www.terraswarm.org/pubs/481.html"
  >Efficient Second-Order Gradient Boosting for Conditional
  Random Fields</a>, International Conference on
  Artificial Intelligence and Statistics (AISTATS), 2015.

• Plain text

  Tianqi Chen, Sameer Singh, Ben Taskar, Carlos Guestrin.
  "Efficient Second-Order Gradient Boosting for
  Conditional Random Fields". International Conference on
  Artificial Intelligence and Statistics (AISTATS), 2015.

• BibTeX

  @inproceedings{ChenSinghTaskarGuestrin15_EfficientSecondOrderGradientBoostingForConditionalRandom,
      author = {Tianqi Chen and Sameer Singh and Ben Taskar and
                Carlos Guestrin},
      title = {Efficient Second-Order Gradient Boosting for
                Conditional Random Fields},
      booktitle = {International Conference on Artificial
                Intelligence and Statistics (AISTATS)},
      year = {2015},
      abstract = {Conditional random fields (CRFs) are an important
                class of models for accurate structured
                prediction, but effective design of the feature
                functions is a major challenge when applying CRF
                models to real world data. Gradient boosting,
                which is used to automatically induce and select
                feature functions, is a natural candidate solution
                to the problem. However, it is non-trivial to
                derive gradient boosting algorithms for CRFs due
                to the dense Hessian matrices introduced by
                variable dependencies. Existing approaches thus
                use only first-order information when optimizing
                likelihood, and hence face convergence issues. We
                incorporate second-order information by deriving a
                Markov Chain mixing rate bound to quantify the
                dependencies, and introduce a gradient boosting
                algorithm that iteratively optimizes an adaptive
                upper bound of the objective function. The
                resulting algorithm induces and selects features
                for CRFs via functional space optimization, with
                provable convergence guarantees. Experimental
                results on three real world datasets demonstrate
                that the mixing rate based upper bound is
                effective for learning CRFs with non-linear
                potentials.},
      URL = {http://terraswarm.org/pubs/481.html}
  }
  

Posted by Sameer Singh on 31 Jan 2015.
Groups: services