New EM derived from Kullback-Leibler divergence

ABSTRACT

We introduce a new EM framework in which it is possible not only to optimize the model parameters but also the number of model components. A key feature of our approach is that we use nonparametric density estimation to improve parametric density estimation in the EM framework. While the classical EM algorithm estimates model parameters empirically using the data points themselves, we estimate them using nonparametric density estimates.There exist many possible applications that require optimal adjustment of model components. We present experimental results in two domains. One is polygonal approximation of laser range data, which is an active research topic in robot navigation. The other is grouping of edge pixels to contour boundaries, which still belongs to unsolved problems in computer vision.

REFERENCES

• 1: M. J. Beal and Z. Ghahramani. The variational bayesian em algorithm for incomplete data. In BAYESIAN STATISTICS 7. Oxford Univ. Press, 2003.
• 2: A. Dempster, N. Laird, and D. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society, Series B, 39(1):1--38, 1977.
• 3: P. Green. Reversible jump markov chain monte carlo computation and bayesian model determination. Biometrica, 82:711--732, 1995.
• 4: G. Grisetti, C. Stachniss, and W. Burgard. Improving grid-based slam with rao-blackwellized particle filters by adaptive proposals and selective resampling. In ICRA, 2005.
• 5: W. Hardle. Smoothing Techniques with implementation in S. Springer Verlag, 1991.
• 6: M. J. R. Healy and M. Wesmacott. Missing values inexperiments analyzed on automatic computers. Appl.Statist., 5:203--206, 1956.
• 7: Radford M. Neal , Geoffrey E. Hinton, A view of the EM algorithm that justifies incremental, sparse, and other variants, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 8: S. T. Pfister, S. I. Roumeliotis, and J. W. Burdick. Weighted line fitting algorithms for mobile robot map building and efficient data representation. In ICRA, 2003.
• 9: A. Pievatolo and P. Green. Boundary detection through dynamic polygons. Journal of the Royal Statistical Society, B, 60:609--626, 1998.
• 10: Paul L. Rosin, Techniques for Assessing Polygonal Approximations of Curves, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.6, p.659-666, June 1997 [doi>10.1109/34.601253]
• 11: D. Sack and W. Burgard. A comparison of methods for line extraction from range data. In Proc. of the 5th IFAC Symposium on Intelligent Autonomous Vehicles(IAV), 2004.
• 12: D. W. Scott. Multivariate Density Estimation: Theory, Practice, and Visualization. Wiley and Sons, 1992.
• 13: B. W. Silverman. Density Estimation for Statistics and Data Analysis. Chapman and Hall, 1986.
• 14: J. S. Simono. Smoothing Methods in Statistics. Springer-Verlag, 1996.
• 15: G. R. Terrell and D. W. Scott. Variable kernel density estimation. The Annals of Statistics, 20(3):1236--1265,1992.
• 16: N. Ueda, R. Nakano, Z. Ghahramani, and G. E. Hinton. Smem algorithm for mixture models. Neural Computation, 12(9):2109--2128, 2000.
• 17: M. Veeck and W. Burgard. Learning polyline maps from range scan data acquired with mobile robots. In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2004.
• 18: M. Wertheimer. Untersuchungen zur lehre von der gestalt ii. Psycologische Forschung, 4:301--350, 1923.
• 19: Z. Zhang, C. Chen, J. Sun, and K. L. Chan. Em algorithms for gaussian mixtures with split-and-merge operation. Pattern Recogntion, 36:1973--1983, 2003.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.0 General

General Terms:
Algorithms, Experimentation, Performance

Keywords:
EM, Kullback-Leibler divergence, expectation maximization