Surrogate maximization/minimization algorithms and extensions Export

@article{Zhang:SurrogateMaxMin, abstract = {Surrogate maximization (or minimization) (SM) algorithms are a family of algorithms that can be regarded as a generalization of expectation-maximization (EM) algorithms. An SM algorithm aims at turning an otherwise intractable maximization problem into a tractable one by iterating two steps. The S-step computes a tractable surrogate function to substitute the original objective function and the M-step seeks to maximize this surrogate function. Convexity plays a central role in the S-step. SM algorithms enjoy the same convergence properties as EM algorithms. There are mainly three approaches to the construction of surrogate functions, namely, by using Jensen's inequality, first-order Taylor approximation, and the low quadratic bound principle. In this paper, we demonstrate the usefulness of SM algorithms by taking logistic regression models, AdaBoost and the log-linear model as examples. More specifically, by using different surrogate function construction methods, we devise several SM algorithms, including the standard SM, generalized SM, gradient SM, and quadratic SM algorithms, and their two variants called the conditional surrogate maximization (CSM) and surrogate conditional maximization (SCM) algorithms.}, address = {Hingham, MA, USA}, author = {Zhang, Zhihua and Kwok, James T. and Yeung, Dit Y.}, citeulike-article-id = {5839929}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1295912.1295937}, citeulike-linkout-1 = {http://dx.doi.org/10.1007/s10994-007-5022-x}, doi = {10.1007/s10994-007-5022-x}, issn = {0885-6125}, journal = {Mach. Learn.}, keywords = {expectation\_maximization, optimization}, number = {1}, pages = {1--33}, posted-at = {2009-09-25 12:26:34}, priority = {3}, publisher = {Kluwer Academic Publishers}, title = {Surrogate maximization/minimization algorithms and extensions}, url = {http://dx.doi.org/10.1007/s10994-007-5022-x}, volume = {69}, year = {2007} }

TY - JOUR ID - Zhang:SurrogateMaxMin L3 - citeulike-article-id:5839929 N2 - Surrogate maximization (or minimization) (SM) algorithms are a family of algorithms that can be regarded as a generalization of expectation-maximization (EM) algorithms. An SM algorithm aims at turning an otherwise intractable maximization problem into a tractable one by iterating two steps. The S-step computes a tractable surrogate function to substitute the original objective function and the M-step seeks to maximize this surrogate function. Convexity plays a central role in the S-step. SM algorithms enjoy the same convergence properties as EM algorithms. There are mainly three approaches to the construction of surrogate functions, namely, by using Jensen's inequality, first-order Taylor approximation, and the low quadratic bound principle. In this paper, we demonstrate the usefulness of SM algorithms by taking logistic regression models, AdaBoost and the log-linear model as examples. More specifically, by using different surrogate function construction methods, we devise several SM algorithms, including the standard SM, generalized SM, gradient SM, and quadratic SM algorithms, and their two variants called the conditional surrogate maximization (CSM) and surrogate conditional maximization (SCM) algorithms. IS - 1 JF - Mach. Learn. SN - 0885-6125 AD - Hingham, MA, USA EP - 33 TI - Surrogate maximization/minimization algorithms and extensions PB - Kluwer Academic Publishers VL - 69 SP - 1 KW - expectation_maximization KW - optimization AU - Zhang, Zhihua AU - Kwok, James AU - Yeung, Dit PY - 2007/// UR - http://dx.doi.org/10.1007/s10994-007-5022-x ER -