Участник:Victoria Evstefeeva

Данный документ содержит описание схемы, по которой предлагается описывать свойства и структуру каждого алгоритма. Описание состоит из двух частей. В первой части описываются собственно алгоритмы и их свойства, а вторая посвящена описанию особенностей их программной реализации с учетом конкретных программно-аппаратных платформ. Такое деление на части сделано для того, чтобы машинно-независимые свойства алгоритмов, которые определяют качество их реализации на параллельных вычислительных системах, были бы выделены и описаны отдельно от множества вопросов, связанных с последующими этапами программирования алгоритмов и исполнения результирующих программ.

Общая схема описания алгоритмов имеет следующий вид:

Свойства и структура алгоритмов

Содержание [убрать] 1 Свойства и структура алгоритмов 1.1 Общее описание алгоритма 1.2 Математическое описание алгоритма 1.3 Вычислительное ядро алгоритма 1.4 Макроструктура алгоритма 1.5 Схема реализации последовательного алгоритма 1.6 Последовательная сложность алгоритма 1.7 Информационный граф 1.8 Ресурс параллелизма алгоритма 1.9 Входные и выходные данные алгоритма 1.10 Свойства алгоритма 2 Программная реализация алгоритма 2.1 Особенности реализации последовательного алгоритма 2.2 Локальность данных и вычислений 2.3 Возможные способы и особенности параллельной реализации алгоритма 2.4 Масштабируемость алгоритма и его реализации 2.5 Динамические характеристики и эффективность реализации алгоритма 2.6 Выводы для классов архитектур 2.7 Существующие реализации алгоритма 3 Литература 1 Свойства и структура алгоритмов[править]

1.1 Общее описание алгоритма[[[править]]] EM-алгоритм (англ. expectation-maximization) - алгоритм итерационного типа для численного решения задачи поиска экстремума целевой функции в разнообразных задачах оптимизации. В частности, алгоритм используется в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.

Как правило, ЕМ-алгоритм применяется для решения задач двух типов. 1. К первому типу можно отнести задачи, связанные с анализом действительно неполных данных, когда некоторые статистические данные отсутствуют в силу каких-либо причин. 2. Ко второму типу задач можно отнести статистические задачи, в которых функция правдоподобия имеет вид, не допускающий удобных аналитических методов исследования, но допускающий серьезные упрощения, если в задачу ввести дополнительные «ненаблюдаемые» (скрытые, латентные) переменные. Примерами прикладных задач второго типа являются задачи распознавания образов, реконструкции изображений. Математическую суть данных задач составляют задачи кластерного анализа, классификации и разделения смесей вероятностных распределений.

1.2 Математическое описание алгоритма[править]

1.3 Вычислительное ядро алгоритма[править]

1.4 Макроструктура алгоритма[править]

1.5 Схема реализации последовательного алгоритма[править]

1.6 Последовательная сложность алгоритма[править] 1.7 Информационный граф[править] 1.8 Ресурс параллелизма алгоритма[править]

1.9 Входные и выходные данные алгоритма[править]

1.10 Свойства алгоритма[править]

2 Программная реализация алгоритма[править]

2.1 Особенности реализации последовательного алгоритма[править]

2.2 Локальность данных и вычислений[править] 2.3 Возможные способы и особенности параллельной реализации алгоритма[править]

2.4 Масштабируемость алгоритма и его реализации[править] 2.5 Динамические характеристики и эффективность реализации алгоритма[править]

2.6 Выводы для классов архитектур[править]

2.7 Существующие реализации алгоритма[править]

3 Литература[править] ↑ http://www.machinelearning.ru/wiki/index.php?title=EM-алгоритм Перейти ↑ Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15. Перейти ↑ Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229. Перейти ↑ Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27. Перейти ↑ Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.