A Convex Exemplar-based Approach to MAD-Bayes Dirichlet Process Mixture Models

En-Hsu Yen, Xin Lin, Kai Zhong, Pradeep Ravikumar, Inderjit Dhillon
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:2418-2426, 2015.

Abstract

MAD-Bayes (MAP-based Asymptotic Derivations) has been recently proposed as a general technique to derive scalable algorithm for Bayesian Nonparametric models. However, the combinatorial nature of objective functions derived from MAD-Bayes results in hard optimization problem, for which current practice employs heuristic algorithms analogous to k-means to find local minimum. In this paper, we consider the exemplar-based version of MAD-Bayes formulation for DP and Hierarchical DP (HDP) mixture model. We show that an exemplar-based MAD-Bayes formulation can be relaxed to a convex structural-regularized program that, under cluster-separation conditions, shares the same optimal solution to its combinatorial counterpart. An algorithm based on Alternating Direction Method of Multiplier (ADMM) is then proposed to solve such program. In our experiments on several benchmark data sets, the proposed method finds optimal solution of the combinatorial problem and significantly improves existing methods in terms of the exemplar-based objective.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-yen15, title = {A Convex Exemplar-based Approach to MAD-Bayes Dirichlet Process Mixture Models}, author = {Yen, En-Hsu and Lin, Xin and Zhong, Kai and Ravikumar, Pradeep and Dhillon, Inderjit}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {2418--2426}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/yen15.pdf}, url = {https://proceedings.mlr.press/v37/yen15.html}, abstract = {MAD-Bayes (MAP-based Asymptotic Derivations) has been recently proposed as a general technique to derive scalable algorithm for Bayesian Nonparametric models. However, the combinatorial nature of objective functions derived from MAD-Bayes results in hard optimization problem, for which current practice employs heuristic algorithms analogous to k-means to find local minimum. In this paper, we consider the exemplar-based version of MAD-Bayes formulation for DP and Hierarchical DP (HDP) mixture model. We show that an exemplar-based MAD-Bayes formulation can be relaxed to a convex structural-regularized program that, under cluster-separation conditions, shares the same optimal solution to its combinatorial counterpart. An algorithm based on Alternating Direction Method of Multiplier (ADMM) is then proposed to solve such program. In our experiments on several benchmark data sets, the proposed method finds optimal solution of the combinatorial problem and significantly improves existing methods in terms of the exemplar-based objective.} }
Endnote
%0 Conference Paper %T A Convex Exemplar-based Approach to MAD-Bayes Dirichlet Process Mixture Models %A En-Hsu Yen %A Xin Lin %A Kai Zhong %A Pradeep Ravikumar %A Inderjit Dhillon %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-yen15 %I PMLR %P 2418--2426 %U https://proceedings.mlr.press/v37/yen15.html %V 37 %X MAD-Bayes (MAP-based Asymptotic Derivations) has been recently proposed as a general technique to derive scalable algorithm for Bayesian Nonparametric models. However, the combinatorial nature of objective functions derived from MAD-Bayes results in hard optimization problem, for which current practice employs heuristic algorithms analogous to k-means to find local minimum. In this paper, we consider the exemplar-based version of MAD-Bayes formulation for DP and Hierarchical DP (HDP) mixture model. We show that an exemplar-based MAD-Bayes formulation can be relaxed to a convex structural-regularized program that, under cluster-separation conditions, shares the same optimal solution to its combinatorial counterpart. An algorithm based on Alternating Direction Method of Multiplier (ADMM) is then proposed to solve such program. In our experiments on several benchmark data sets, the proposed method finds optimal solution of the combinatorial problem and significantly improves existing methods in terms of the exemplar-based objective.
RIS
TY - CPAPER TI - A Convex Exemplar-based Approach to MAD-Bayes Dirichlet Process Mixture Models AU - En-Hsu Yen AU - Xin Lin AU - Kai Zhong AU - Pradeep Ravikumar AU - Inderjit Dhillon BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-yen15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 2418 EP - 2426 L1 - http://proceedings.mlr.press/v37/yen15.pdf UR - https://proceedings.mlr.press/v37/yen15.html AB - MAD-Bayes (MAP-based Asymptotic Derivations) has been recently proposed as a general technique to derive scalable algorithm for Bayesian Nonparametric models. However, the combinatorial nature of objective functions derived from MAD-Bayes results in hard optimization problem, for which current practice employs heuristic algorithms analogous to k-means to find local minimum. In this paper, we consider the exemplar-based version of MAD-Bayes formulation for DP and Hierarchical DP (HDP) mixture model. We show that an exemplar-based MAD-Bayes formulation can be relaxed to a convex structural-regularized program that, under cluster-separation conditions, shares the same optimal solution to its combinatorial counterpart. An algorithm based on Alternating Direction Method of Multiplier (ADMM) is then proposed to solve such program. In our experiments on several benchmark data sets, the proposed method finds optimal solution of the combinatorial problem and significantly improves existing methods in terms of the exemplar-based objective. ER -
APA
Yen, E., Lin, X., Zhong, K., Ravikumar, P. & Dhillon, I.. (2015). A Convex Exemplar-based Approach to MAD-Bayes Dirichlet Process Mixture Models. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:2418-2426 Available from https://proceedings.mlr.press/v37/yen15.html.

Related Material