Effective expectation maximization algorithm implementation using multicore computer systems

• Autorzy: Kasitskij A. , Bidyuk P. , Gozhyi A.

Identyfikatory

DOI

10.5604/20830157.1130179

Warianty tytułu

PL

Efektywny algorytm EM i jego implementacja przy użyciu wielordzeniowych systemów komputerowych

• Języki publikacji: EN

Abstrakty

EN

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.

PL

W artykule opisany jest popularny algorytm EM (expectation maximization), który jest powszechnie stosowany w nowoczesnych systemach przetwarzania danych do rozwiązywania różnych problemów, w tym optymalizacji i estymacji parametrów. Celem badań było zwiększenie efektywności czasu wykonywania algorytmu. Zwiększenie szybkości wykonania algorytmu EM użyto wielordzeniowy architektury nowoczesnych systemów komputerowych. Zostały zaproponowane niezbędne modyfikacje mające na celu lepszą równoległość realizacji algorytmu EM. Skuteczność implementacji programu była testowana na klasycznym problemie separacji Gaussowskich zmiennych losowych. Wykazano, że w przypadku rozdziału mieszaniny wydajność algorytmu EM ulega degradacji, kiedy odległość między średnimi wartościami rozkładu wynosi mniej niż trzy odchylenia standardowe, co jest całkowicie zgodnie z regułą trzech sigm. W takich przypadkach, jest bardzo ważne, aby mieć efektywną realizację algorytmu EM móc przetworzyć takie przypadki w rozsądnym czasie.

Słowa kluczowe

EN

expectation-maximization algorithm; multicore architecture; parallelism; Gaussian random variables mixture; separation; three sigma law

PL

algorytm EM; zmienna losowa Gaussowska; separacja; równoległość; architektura wielordzeniowa

• Wydawca: Wydawnictwo Politechniki Lubelskiej
• Czasopismo: Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Środowiska
• Rocznik: 2014
• Tom: nr 4
• Strony: 35--37
• Opis fizyczny: Bibliogr. 10 poz., tab., wykr.

Twórcy

autor

Kasitskij A.

• National Technical University "Kyiv Polytechnic Institute"

autor

Bidyuk P.

• National Technical University "Kyiv Polytechnic Institute"

autor

Gozhyi A.

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

Bibliografia

• [1] Ben-Ari M.: Principles of Concurrent and Distributed Programming (2nd ed.). Addison-Wesley, 2006.
• [2] Bidyuk P. I., Gozhij O. P., Korshevnyuk L.O.: Computer based decision support systems. Chornomorsky State University named after Petro Mogyla, Mykolaiv, 2012.
• [3] Borman S.: The expectation maximization algorithm a short tutorial. http://www.seanborman.com/ publications /EM_algorithm.pdf
• [4] Chapman B., Jost G. R., Kuck D. J.: Using Open MP: Portable Shared Memory Parallel Programming. The MIT Press, Boston 2007.
• [5] Dellaert F.: The expectation maximization algorithm. Techn. paper, Georgia Institute of Technology, 2002.
• [6] Dinov I. D.: Expectation maximization and mixture modeling tutorial. http://www.stat.ucla.edu/~dinov/courses_students.dir/04/Spring/Stat233.dir/ST AT233_notes.dir/EM_Tutorial.pdf
• [7] Hollsapple C. W., Winston A. B.: Decision support systems. West Publishing Company, New York 1996.
• [8] Korbicz J.(Ed.): Measurements, models, systems and design. Wydawnictwa Komunikacji i Łączności, 2007.
• [9] Quinn M. J.: Parallel Programming in C with MPI and Open MP. McGraw-Hill Inc. 2004.
• [10] 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.