• Topics:
• Empirical Risk Minimization
• Graphical Models
• Support Vector Machines

Download: pdf

Citation

• Dual Decomposed Learning with Factorwise Oracle for Structural SVM with Large Output Domain (pdf, software)
  I. Yen, X. Huang, K. Zhong, R. Zhang, P. Ravikumar, I. Dhillon.
  In Neural Information Processing Systems (NIPS), December 2016.
  
  Bibtex:
  
  @inproceedings{yen2016dualdecom, author = "Ian En-Hsu Yen AND Xiangru Huang AND Kai Zhong AND Ruohan Zhang AND Pradeep Ravikumar AND Inderjit S. Dhillon", title = "Dual Decomposed Learning with Factorwise Oracle for Structural SVM with Large Output Domain", booktitle = "Neural Information Processing Systems (NIPS)", year = "2016", month = "dec", abstract = "Many applications of machine learning involve structured outputs with large domains, where learning of a structured predictor is prohibitive due to repetitive calls to an expensive inference oracle. In this work, we show that by decomposing training of a Structural Support Vector Machine (SVM) into a series of multiclass SVM problems connected through messages, one can replace an expensive structured oracle with Factorwise Maximization Oracles (FMOs) that allow efficient implementation of complexity sublinear to the factor domain. A Greedy Direction Method of Multiplier (GDMM) algorithm is then proposed to exploit the sparsity of messages while guarantees convergence to eps sub-optimality after O(log(1/eps)) passes of FMOs over every factor. We conduct experiments on chain-structured and fully-connected problems of large output domains, where the proposed approach is orders-of-magnitude faster than current state-of-the-art algorithms for training Structural SVMs" }