Convex relaxation of mixture regression with efficient algorithms

Quadrianto, Novi; Caetano, Tiberio S; Lim, John; Schuurmans, Dale;

Open Access

English

Published: 01 Jan 2009

Publisher: Curran

- Summary
- References
  (23)

Abstract

We develop a convex relaxation of maximum a posteriori estimation of a mixture of regression models. Although our relaxation involves a semidefinite matrix variable, we reformulate the problem to eliminate the need for general semidefinite programming. In particular, we provide two reformulations that admit fast algorithms. The first is a max-min spectral reformulation exploiting quasi-Newton descent. The second is a min-min reformulation consisting of fast alternating steps of closed-form updates. We evaluate the methods against Expectation-Maximization in a real problem of motion segmentation from video data.

Subjects by Vocabulary

ACM Computing Classification System: MathematicsofComputing_NUMERICALANALYSIS

Subjects

Related Organizations

University of Alberta
Canada
THE GOVERNORS OF THE UNIVERSITY OF ALBERTA UNIVERSITY OF ALBERTA
Canada

23 references, page 1 of 3

[1] S. Gaffney and P. Smyth. Trajectory clustering with mixtures of regression models. In ACM SIGKDD, volume 62, pages 63-72, 1999.

[2] S. Finney, L. Kaelbling, and T. Lozano-Perez. Predicting partial paths from planning problem parameters. In Proceedings of Robotics: Science and Systems, Atlanta, GA, USA, June 2007.

[3] A. J. Storkey and M. Sugiyama. Mixture regression for covariate shift. In Scho¨lkopf, editor, Advances in Neural Information Processing Systems 19, pages 1337-1344, 2007. [OpenAIRE]

[4] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society. Series B (Methodological), 39(1):1-38, 1977.

[5] T. De Bie, N. Cristianini, P. Bennett, and E. Parrado-herna¨ndez. Fast sdp relaxations of graph cut clustering, transduction, and other combinatorial problems. JMLR, 7:1409-1436, 2006.

[6] Y. Guo and D. Schuurmans. Convex relaxations for latent variable training. In Platt et al., editor, Advances in Neural Information Processing Systems 20, pages 601-608, 2008.

[7] S. M. Goldfeld and R.E. Quandt. Nonlinear methods in econometrics. Amsterdam: NorthHolland Publishing Co., 1972.

[8] D. W. Hosmer. Maximum likelihood estimates of the parameters of a mixture of two regression lines. Communications in Statistics, 3(10):995-1006, 1974.

[9] H. Spa¨th. Algorithm 39: clusterwise linear regression. Computing, 22:367-373, 1979.

[10] W.S. DeSarbo and W.L. Cron. A maximum likelihood methodology for clusterwise linear regression. Journal of Classification, 5(1):249-282, 1988.

chevron_left
1
2
3
chevron_right

See an issue? Give us feedback

Download from

lock_open

CORE (RIOXX-UK Aggregator)

Other ORP type . 2009

Providers: CORE (RIOXX-UK Aggregator)