EFFECTIVE EXPECTATION MAXIMIZATION ALGORITHM IMPLEMENTATION USING MULTICORE COMPUTER SYSTEMS

Alexei Kasitskij

pbidyuke_00@ukr.net
National Technical University "Kyiv Polytechnic Institute", Institute for Applied System Analysis (Ukraine)

Peter Bidyuk


National Technical University "Kyiv Polytechnic Institute", Institute for Applied System Analysis (Ukraine)

Alexander Gozhyi


Petro Mohyla Black Sea State University, Department of Information Technologies and Program Systems (Ukraine)

Abstract

A popular expectation maximization algorithm that is widely used in modern data processing systems to solve various problems including optimization and parameter estimation is considered in the paper. The task of the study was to enhance effectiveness of the algorithm execution in time. An enhancement of execution rate for the EM algorithm using multicore architecture of modern computer systems was carried out. Necessary modifications aimed at better parallelism were proposed for implementation of the EM algorithm. An efficiency of the software implementation was tested on the classic problem of Gaussian random variables mixture separation. It is shown that in the mixture separation problem EM algorithm performance degrades when the distance between mean values of distributions is less than three standard deviations, which is totally in the spirit of three sigma law. In such cases, it is very important to have an efficient EM algorithm implementation to be able to process such test cases in a reasonable time.


Keywords:

expectation maximization algorithm, multicore architecture, parallelism, problem of Gaussian random variables mixture separation, three sigma law

Ben-Ari M.: Principles of Concurrent and Distributed Programming (2nd ed.). Addison-Wesley, 2006.
  Google Scholar

Bidyuk P. I., Gozhij O. P., Korshevnyuk L.O.: Computer based decision support systems. Chornomorsky State University named after Petro Mogyla, Mykolaiv, 2012.
  Google Scholar

Borman S.: The expectation maximization algorithm a short tutorial. http://www.seanborman.com/publications/EM_algorithm.pdf
  Google Scholar

Chapman B., Jost G. R., Kuck D. J.: Using Open MP: Portable Shared Memory Parallel Programming. The MIT Press, Boston 2007.
  Google Scholar

Dellaert F.: The expectation maximization algorithm. Techn. paper, Georgia Institute of Technology, 2002.
  Google Scholar

Dinov I. D.: Expectation maximization and mixture modeling tutorial. http://www.stat.ucla.edu/~dinov/courses_students.dir/04/Spring/Stat233.dir/STAT233_notes.dir/EM_Tutorial.pdf
  Google Scholar

Hollsapple C. W., Winston A. B.: Decision support systems. West Publishing Company, New York 1996.
  Google Scholar

Korbicz J.(Ed.): Measurements, models, systems and design. Wydawnictwa Komunikacji i łączności, 2007.
  Google Scholar

Quinn M. J.: Parallel Programming in C with MPI and Open MP. McGraw-Hill Inc. 2004.
  Google Scholar

Shuicheng Y., Chang S. F., Johnson M. H., Xi Z., Xiaodan Z., Huang T. S.: Sift-bag kernel for video event analysis. Proceeding of the 16th ACM international conference on Multimedia, 2008, 229-238.
  Google Scholar

Download


Published
2014-12-09

Cited by

Kasitskij, A., Bidyuk, P., & Gozhyi, A. (2014). EFFECTIVE EXPECTATION MAXIMIZATION ALGORITHM IMPLEMENTATION USING MULTICORE COMPUTER SYSTEMS. Informatyka, Automatyka, Pomiary W Gospodarce I Ochronie Środowiska, 4(4), 35–37. https://doi.org/10.5604/20830157.1130179

Authors

Alexei Kasitskij 
pbidyuke_00@ukr.net
National Technical University "Kyiv Polytechnic Institute", Institute for Applied System Analysis Ukraine

Authors

Peter Bidyuk 

National Technical University "Kyiv Polytechnic Institute", Institute for Applied System Analysis Ukraine

Authors

Alexander Gozhyi 

Petro Mohyla Black Sea State University, Department of Information Technologies and Program Systems Ukraine

Statistics

Abstract views: 194
PDF downloads: 63