[en] We propose a gossip-based distributed algorithm for Gaussian mixture learning, Newscast EM. The algorithm operates on network topologies where each node observes a local quantity and can communicate with other nodes in an arbitrary point-to-point fashion. The main difference between Newscast EM and the standard EM algorithm is that the M-step in our case is implemented in a decentralized manner: (random) pairs of nodes repeatedly exchange their local parameter estimates and combine them by (weighted) averaging. We provide theoretical evidence and demonstrate experimentally that, under this protocol, nodes converge exponentially fast to the correct estimates in each M-step of the EM algorithm.
Disciplines :
Sciences informatiques
Identifiants :
UNILU:UL-ARTICLE-2011-729
Auteur, co-auteur :
Kowalczyk, W.
VLASSIS, Nikos ; University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB)
Langue du document :
Anglais
Titre :
Newscast EM
Date de publication/diffusion :
2005
Nom de la manifestation :
Advances in Neural Information Processing Systems 17
Date de la manifestation :
2005
Titre de l'ouvrage principal :
Advances in Neural Information Processing Systems 17
R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking. Randomized rumour spreading. In Proc. 41th IEEE Symp. on Foundations of Computer Science, Redondo Beach, CA, November 2000.
D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation of aggregate information. In Proc. 44th IEEE Symp. on Foundations of Computer Science, Cambridge, MA, October 2003.
M. Jelasity, W. Kowalczyk, and M. van Steen. Newscast computing. Technical report, Dept. of Computer Science, Vrije Universiteit Amsterdam, 2003. IR-CS-006.
C. C. Moallemi and B. Van Roy. Distributed optimization in adaptive networks. In S. Thrun, L. Saul, and B. Scholkopf, editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004.
D. Kempe and F. McSherry. A decentralized algorithm for spectral analysis. In Proc. 36th ACM Symp. on Theory of Computing, Chicago, IL, June 2004.
A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Statist. Soc. B, 39:1-38, 1977.
G. Forman and B. Zhang. Distributed data clustering can be efficient and exact. ACM SIGKDD Explorations, 2(2):34-38, 2000.
R. D. Nowak. Distributed EM algorithms for density estimation and clustering in sensor networks. IEEE Trans. on Signal Processing, 51(8):2245-2253, August 2003.
R. M. Neal and G. E. Hinton. A view of the EM algorithm that justifies incremental, sparse, and other variants. In M. I. Jordan, editor, Learning in graphical models, pages 355-368. Kluwer Academic Publishers, 1998.
S. Voulgaris, D. Gavidia, and M. van Steen. Inexpensive membership management for unstructured P2P overlays. Journal of Network and Systems Management, 2005. To appear.
J. R. J. Nunnink, J. J. Verbeek, and N. Vlassis. Accelerated greedy mixture learning. In Proc. Belgian-Dutch Conference on Machine Learning, Brussels, Belgium, January 2004.
M. A. Paskin and C. E. Guestrin. Robust probabilistic inference in distributed systems. In Proc. 20th Int. Conf. on Uncertainty in Artificial Intelligence, Banff, Canada, July 2004.
