Содержание к диссертации
Введение
Глава 1. Распознавание образов и фейеровские отображения 13
1.1. Задача распознавания образов 13
1.1.1. Классификация основных задач распознавания 13
1.1.2. Отделимость непересекающихся многогранников 15
1.2. Итерационные методы фейеровского типа 17
1.3. Обзор методов решения задачи сильной отделимости 21
1.3.1. Метод на основе операции проектирования 21
1.3.2. Метод опорных векторов 24
1.3.3. Метод с использованием теоремы об альтернативах 27
1.4. Выводы по главе 1 31
Глава 2. Метод псевдопроекций 32
2.1. Формализация задачи сильной отделимости 32
2.2. Метод последовательного проектирования 32
2.3. Метод на базе фейеровских процессов 34
2.4. Устойчивость алгоритма F 36
2.5. Масштабируемый алгоритм S построения псевдопроекции 40
2.6. Теорема сходимости 45
2.7. Выводы по главе 2 52
Глава 3. Параллельные алгоритмы решения задачи сильной отделимости 54
3.1. Параллельная реализация алгоритма F 54
3.2. Параллельный алгоритм Simple 56
3.3. Параллельный алгоритм Block 59
3.4. Выводы по главе 3 65
Глава 4. Программный комплекс и вычислительные эксперименты 66
4.1. Структура программного комплекса 66
4.1.1. Программа генерации случайных многогранников 66
4.1.2. Программа, реализующая последовательный алгоритм 68
4.1.3. Программа, реализующая параллельный алгоритм Simple 68
4.1.4. Программа, реализующая параллельный алгоритм Block 69
4.2. Вычислительные эксперименты 70
4.3. Масштабируемая модельная задача Model-n 71
4.4. Исследование последовательного алгоритма 72
4.5. Исследование параллельного алгоритма Simple 75
4.6. Исследование алгоритма Block 76
4.7. Выводы по главе 4 82
Заключение 83
Литература 88
- Отделимость непересекающихся многогранников
- Метод на базе фейеровских процессов
- Параллельный алгоритм Simple
- Программа, реализующая параллельный алгоритм Block
Введение к работе
Актуальность темы. Создание вычислительных машин и связанное с этим ускоренное развитие математических теорий, в том числе математической кибернетики и дискретной математики позволило ставить и решать на ЭВМ новые задачи, до недавнего времени находившиеся исключительно в компетенции человека. Одной из таких фундаментальных задач является рассматриваемая в настоящей работе задача распознавания образов. В общем виде эта задача может быть сформулирована следующим образом: необходимо отнести предъявленный объект, определяемый некоторой совокупностью своих признаков, к одному из нескольких непересекающихся классов-образов. В том или ином виде данная задача решается человеком практически во всех сферах его деятельности.
Задача сильной отделимости имеет большое значение теоретического и прикладного характера в распознавании образов, включающем задачи дискриминации, классификации и др. Хорошо известен итерационный метод решения задачи сильной отделимости, использующий операцию проектирования. Однако на практике применение этого метода существенно ограничивается тем, что далеко не всегда удается построить конструктивную формулу для вычисления проекции точки на выпуклое множество. Поэтому целесообразно заменить операцию проектирования последовательностью фейеровских отображений.
Алгоритмы разделения выпуклых многогранников на базе фейеровских отображений обладают тем преимуществом по сравнению с другими известными методами, что они применимы к нестационарным задачам, то есть к задачам, в которых исходные данные могут меняться в процессе решения задачи. Примерами таких нестационарных задач являются, например, задача о портфеле ценных бумаг, задача о спам-фильтре и задачи классификации в метеорологии.
При решении практических задач распознавания образов часто встречаются задачи с большим количеством переменных и ограничений. Подобные задачи при решении требуют значительных вычислительных мощностей. В связи с этим возникает необходимость разработки параллельного алгоритма разделения выпуклых многогранников с помощью фейеровских отображений, допускающего эффективную реализацию на многопроцессорных системах с массовым параллелизмом.
В соответствие с этим актуальной является задача разработки, анализа и реализации на ЭВМ масштабируемых методов и алгоритмов решения задачи сильной отделимости двух выпуклых непересекающихся многогранников на базе фейеровских отображений.
Цель и задачи исследования. Цель данной работы состояла в разработке итерационных методов и алгоритмов решения нестационарных задач сильной отделимости двух выпуклых непересекающихся многогранников, допускающих эффективное распараллеливание на многопроцессорных системах с массовым параллелизмом. Для достижения этой цели необходимо было решить следующие задачи:
Описать общий подход к решению задачи сильной отделимости двух выпуклых многогранников на основе последовательных проектирований.
На базе данного подхода разработать масштабируемый метод решения задачи сильной отделимости с использованием фейеровских отображений для построения псевдопроекций, обобщающих операцию проектирования, и исследовать устойчивость этого метода.
Разработать алгоритм построения псевдопроекции, допускающий эффективное распараллеливание на многопроцессорных системах с массовым параллелизмом, и исследовать его сходимость.
4. Спроектировать и реализовать программный комплекс для решения задачи силь-
ной отделимости, использующий разработанные методы и алгоритмы. Провести вычислительные эксперименты для анализа эффективности предложенного подхода.
Методы исследования. Исследования, проводимые в настоящей диссертационной работе, опираются на теорию фейеровских отображений академика И.И. Еремина и теорию нестационарных процессов, развитую И.И. Ереминым и Вл.Д. Мазуровым. Для построения алгоритмов и доказательства теорем также использовался математический аппарат, в основе которого лежат теория множеств, теория алгоритмов, линейная алгебра, теория линейных неравенств и теория распознавания образов.
Научная новизна работы заключается в следующем:
Предложен новый итерационный метод решения задачи сильной отделимости двух выпуклых многогранников, базирующийся на делении вектора на подвекто-ры, и допускающий эффективную реализацию на многопроцессорных многоядерных вычислительных системах с массовым параллелизмом.
На основе предложенного метода разработан новый параллельный алгоритм, для которого доказаны теоремы сходимости и устойчивости, обосновывающие возможность эффективного применения этого алгоритма для решения нестационарных задач сильной отделимости на базе фейеровских отображений.
Впервые выполнена реализация разработанного алгоритма решения задачи сильной отделимости двух выпуклых многогранников в виде программного комплекса для многопроцессорных систем на основе стандарта MPI-2, и проведены вычислительные эксперименты, подтверждающие эффективность предложенных подходов.
Теоретическая ценность работы состоит в том, что в ней дано формальное описание масштабируемого метода решения задачи сильной отделимости, для которого доказаны сходимость и устойчивость.
Практическая ценность работы заключается в том, что предложенный метод реализован в виде программного комплекса для супер-ЭВМ, позволяющего эффективно решать нестационарные задачи сильной отделимости в различных предметных областях.
Апробация работы. Основные положения диссертационной работы, разработанные методы, алгоритмы и результаты вычислительных экспериментов докладывались автором на следующих международных и всероссийских научных конференциях:
на Международной конференции «Алгоритмический анализ неустойчивых задач» (1-6 сентября 2008 г., г. Екатеринбург);
на Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2010)» (29 марта - 2 апреля 2010 г., г. Уфа);
на XVIII Международной конференции «Математика. Экономика. Образование» (25 мая - 1 июня 2010 г., г. Новороссийск);
на Международной научной конференции «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи» (20-25 сентября 2010 г., г. Новороссийск);
на XIV Всероссийской конференции "Математическое программирование и приложения" (28 февраля - 4 марта 2011 г., г. Екатеринбург);
на Международной научной конференции «Научный сервис в сети Интернет: эк-зафлопсное будущее» (19-24 сентября 2011 г., г. Новороссийск);
на Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2012)» (26-30 марта 2012 г., г. Новосибирск).
Публикации. По теме диссертации опубликовано 10 печатных работ, причем работы [1-4] опубликованы в журналах, включенные ВАК в перечень журналов, в которых должны быть опубликованы основные результаты диссертаций на соискание ученой степени доктора и кандидата наук. Получено 3 свидетельства Роспатента об официальной регистрации программ для ЭВМ. В совместных работах научному руководителю И.М. Соколинской принадлежит постановка задачи, А.В. Ершовой принадлежат все полученные результаты.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и библиографии. Объем диссертации составляет 97 страниц, объем библиографии - 92 наименования.
Отделимость непересекающихся многогранников
При решении практических задач распознавания образов часто встречаются задачи с большим количеством переменных и ограничений. Размер типичной средней задачи может составлять 20 000 переменных и 5 000 ограничений [74]. В отдельных случаях количество переменных может превышать 100 000, а количество ограничений – 20 000. Подобные задачи при решении требуют значительных вычислительных мощностей. В связи с этим возникает необходимость разработки параллельного алгоритма разделения выпуклых многогранников с помощью фейеровских отображений, допускающего эффективную реализацию на многопроцессорных системах с массовым параллелизмом.
В соответствие с этим актуальной является задача разработки, анализа и реализации на ЭВМ масштабируемых методов и алгоритмов решения задачи сильной отделимости двух выпуклых непересекающихся многогранников на базе фейеровских отображений.
Цель и задачи исследования
Цель данной работы состояла в разработке итерационных методов и алгоритмов решения нестационарных задач сильной отделимости двух выпуклых непересекающихся многогранников, допускающих эффективное распараллеливание на многопроцессорных системах с массовым параллелизмом. Для достижения этой цели необходимо было решить следующие задачи:
1. Описать общий подход к решению задачи сильной отделимости двух выпуклых многогранников на основе последовательных проектирований.
2. На базе данного подхода разработать масштабируемый метод решения задачи сильной отделимости с использованием фейеровских отображений для построения псевдопроекций, обобщающих операцию проектирования, и исследовать устойчивость этого метода. 3. Разработать алгоритм построения псевдопроекции, допускающий эффективное распараллеливание на многопроцессорных системах с массовым параллелизмом, и исследовать его сходимость.
4. Спроектировать и реализовать программный комплекс для решения задачи сильной отделимости, использующий разработанные методы и алгоритмы. Провести вычислительные эксперименты для анализа эффективности предложенного подхода.
Методы исследования Исследования, проводимые в настоящей диссертационной работе, опираются на теорию фейеровских отображений академика И.И. Еремина и теорию нестационарных процессов, развитую И.И. Ереминым и Вл.Д. Мазуровым. Для построения алгоритмов и доказательства теорем также использовался математический аппарат, в основе которого лежат теория множеств, теория алгоритмов, линейная алгебра, теория линейных неравенств и теория распознавания образов. Научная новизна Научная новизна работы заключается в следующем:
1. Предложен новый итерационный метод решения задачи сильной отделимости двух выпуклых многогранников, базирующийся на делении вектора на подвекторы, и допускающий эффективную реализацию на многопроцессорных многоядерных вычислительных системах с массовым параллелизмом.
2. На основе предложенного метода разработан новый параллельный алгоритм, для которого доказаны теоремы сходимости и устойчивости, обосновывающие возможность эффективного применения этого алгоритма для решения нестационарных задач сильной отделимости на базе фейеровских отображений. 3. Впервые выполнена реализация разработанного алгоритма решения задачи сильной отделимости двух выпуклых многогранников в виде программного комплекса для многопроцессорных систем на основе стандарта MPI-2, и проведены вычислительные эксперименты, подтверждающие эффективность предложенных подходов.
Теоретическая и практическая ценность
Теоретическая ценность работы состоит в том, что в ней дано формальное описание масштабируемого метода решения задачи сильной отделимости, для которого доказаны сходимость и устойчивость.
Практическая ценность работы заключается в том, что предложенный метод реализован в виде программного комплекса для супер-ЭВМ, позволяющего эффективно решать нестационарные задачи сильной отделимости в различных предметных областях. Структура и объем работы Диссертация состоит из введения, четырех глав, заключения и библиографии. Объем диссертации составляет 97 страниц, объем библиографии – 92 наименования. Содержание работы
Метод на базе фейеровских процессов
Это задача квадратичной минимизации при линейных ограничениях. Она выпукла, и, если ограничения совместны, имеет единственное решение. Алгоритмы приближенного решения таких задач достаточно хорошо изучены [68].
Метод опорных векторов обладает хорошей точностью решения, однако при этом время работы, особенно на больших наборах данных, очень велико и увеличивается пропорционально квадрату числа классифицируемых объектов. Решить проблему недостаточной скорости обучения SVM возможно при использовании многопроцессорных вычислительных систем. Для параллельной реализации метода было предложено использование алгоритмов кластеризации, благодаря которым становится возможной декомпозиция по данным [46]. К недостаткам метода можно отнести тот факт, что метод опорных векторов неустойчив по отношению к шуму в исходных данных (т.е. значения признаков объектов, используемых в качестве обучающей выборки, могут отсутствовать или быть искажены). Шум возникает из-за таких причин как некорректное измерение входного параметра, неверное описание значения параметра экспертом, использование испорченных измерительных приборов, потеря данных при пересылке и хранении информации [80]. Если обучающая выборка содержит шумовые выбросы, они будут существенным образом влиять на построение разделяющей гиперплоскости [13].
В работе [15] рассматривается задача о численном нахождении семейства гиперплоскостей, разделяющих два непересекающихся непустых полиэдра, заданных с помощью систем неравенств. Используется специфический вид разделяющей гиперплоскости, нормаль и сдвиг которой выражены через произвольное решение некоторой системы, альтернативной к несовместной системе. Эта несовместная система состоит из двух совместных подсистем, каждая из которых определяет непустой полиэдр. Система несовместна, т.к. эти полиэдры не пересекаются. Построение разделяющих гиперплоскостей существенно опирается на теоремы об альтернативах.
Норма вектора у - расстояние между гиперплоскостями Г (1) и Г(0) - называется толщиной семейства гиперплоскостей [15]. Вектор сдвига у и \\у\\ - толщину семейства гиперплоскостей Г (а) можно найти по формулам: приведены множества X1, X2 , разделяющие гиперплоско сти, соответствующие а = 0, а = 1 и нормированный вектор Q = JT. Множество Х1 лежит в положительном полупространстве относительно вектора с, множество Х2 лежит в отрицательном полупространстве. Толщина семейства гиперплоскостей составила IWI = 2,8. Недостатком данного метода является то, что в зависимости от начальных условий задачи, найденная толщина семейства гиперплоскостей не всегда совпадает с минимальным расстоянием между двумя непересекающимися множествами X1 и X2 [15]. Помимо этого, можно выделить еще ряд недостатков данного метода: не рассмотрены вопросы реализации представленного метода для задач большой размерности и поведения алгоритма в условиях неполных, противоречивых и изменяющихся исходных данных.
На сегодняшний день существует большое количество методов решения задачи разделения двух выпуклых непересекающихся множеств, которые условно можно разделить на три основные группы: методы на основе операции проектирования, опорных векторов и теоремы об альтернативах. Однако указанные методы не позволяют эффективно решать задачу сильной отделимости большой размерности для нестационарных систем. Кроме того, некоторые описанные методы не всегда приводят к правильному решению задачи, при этом наибольшие проблемы возникают при увеличении размерности задачи. Помимо этого, большинство описанных методов не допускают эффективной реализации на многопроцессорных системах с массовым параллелизмом. В связи с этим актуальной является задача разработки, описания и исследования новых методов и алгоритмов решения нестационарных задач сильной отделимости большой размерности, которые допускают эффективную реализацию на высокопроизводительных вычислительных кластерах.
Параллельный алгоритм Simple
Семантика переменных и массивов, использованных в реализации алгоритма Block, приведена в Табл. 2. Реализация содержит г параллельных ветвей, каждая из которых вычисляет «в своем подпространстве» часть вектора хк, применяя к нему отображение щ (і - номер подпространства) s раз, после чего происходит объединение этих частей в единый вектор. Каждая из этих параллельных ветвей может выполняться в виде независимого процесса. Это позволяет теоретически достигнуть ускорения в г раз. Действительно, циклы Фи (см. Рис. 11) имеют временную сложность 0{тпп) и 0{mnr) соответственно. Цикл (D имеет временную сложность 0(ml) = 0(mn/r). Соответственно, объемлющий его цикл имеет временную сложность 0(mns/r). Цикл (D имеет временную сложность 0(пг).
Обозначим через h количество итераций цикла при = 1. Мы вправе ожидать, что количество итераций цикла при s 1 будет равно h/s (в разделе 4.6 будут приведены результаты вычислительных экспериментов, подтверждающие это предположение). Тогда цикл имеет временную [ j =m ]
Точность приближения сложность 0(mnh/r + nrh/s). Возьмем г т и s = r. При этих значениях временная сложность цикла принимает вид О (mnh/r + rnh/r) = О { max(mnh гпИХ Л = о (mnh/r). Соответственно, вре V г ) менная сложность параллельной реализации, изображенной на Рис. 11, составит О (mnh/r). В то же время, временная сложность последовательной реализации алгоритма вычисления псевдопроекции с помощью формулы (3.2) составляет 0(mnh). Таким образом, параллельный алгоритм Block позволяет получить максимальное (теоретическое) ускорение в r раз. 3.4. Выводы по главе 3
В главе 3 были описаны два параллельных алгоритма вычисления псевдопроекций: Simple и Block. Простой параллельный алгоритм Simple основан на хорошо известной технике распараллеливания независимых итераций цикла. Для алгоритма Simple был построен информационный граф, который показывает, что этот алгоритм не допускает эффективную реализацию на многопроцессорных системах с распределенной памятью. На таких системах может быть эффективно использован алгоритм Block, базирующийся на оригинальном масштабируемом алгоритме 6, описанном в разделе 2.5. Суть этого подхода заключается в том, что n-мерное пространство разбивается в прямую сумму r подпространств. Для каждого подпространства конструируется независимый фейеровский процесс. Указанный подход позволяет получить максимальное ускорение в r раз. ГЛАВА 4. ПРОГРАММНЫЙ КОМПЛЕКС И ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ
Разработанные и описанные в диссертационной работе модели, методы и алгоритмы были реализованы в виде программного комплекса на языке Си++. Данный программный комплекс может быть использован на кластерных вычислительных системах для решения задач сильной отделимости большой размерности в условиях быстро изменяющихся исходных данных. В этой главе описывается структура программного комплекса и результаты вычислительных экспериментов, проведенных с его помощью, на масштабируемых модельных и случайных задачах.
На программный комплекс получены свидетельства Роспатента об официальной регистрации программ для ЭВМ: программа генерации случайных многогранников [42]; программа, реализующая последовательный алгоритм [41]; программа, реализующая параллельный алгоритм Block [43]. Исходные тексты программ свободно доступны в Интернет по адресу http://life.susu.ru/discr/.
Программа, реализующая параллельный алгоритм Block
Методы и алгоритмы, описанные в главах 2 и 3, были реализованы в виде программного комплекса на языке Си++, описанного в данной главе. С использованием программного комплекса на вычислительном кластере «СКИФ-Урал» были проведены вычислительные эксперименты на случайных и модельных масштабируемых задачах. Была исследована последовательная реализация алгоритма F для фейеровских отображений различных типов. Эксперименты показали, что тип используемого фейеровского отображения может существенно влиять на скорость работы алгоритма. Далее был исследован последовательный алгоритм Simple. На основе проведенных экспериментов можно сделать вывод, что алгоритм Simple может эффективно работать только на небольшом (до 16) количестве процессорных ядер. Также в вычислительных экспериментах был исследован параллельный алгоритм Block, разработанный в рамках настоящего диссертационного исследования. Были исследованы различные параметры алгоритма Block и даны рекомендации по выбору их значений. Проведены исследования по масштабируемости алгоритма Block, показавшие, что данный алгоритм может быть эффективно использован на многопроцессорных системах с массовым параллелизмом для решения задач сильной отделимости большой размерности. ЗАКЛЮЧЕНИЕ
В диссертационной работе были рассмотрены вопросы, связанные с методами решения задачи сильной отделимости, имеющей важное значение в теории распознавания образов. Особое внимание было уделено нестационарным задачам большой размерности. Подобные задачи возникают во многих прикладных областях. В диссертации был дан обзор известных методов решения задачи сильной отделимости, по результатам которого был сделан вывод, что среди них отсутствуют методы, позволяющие эффективно решать нестационарные задачи сильной отделимости большой размерности, что обосновывает актуальность темы диссертационного исследования. Был описан общий метод решения задачи сильной отделимости для двух выпуклых непересекающихся многогранников путем последовательных проектирований. На основе теории фейеровских отображений введено понятие псевдопроекции, в определенном смысле обобщающее понятие проекции точки на выпуклый многогранник. Дано формальное описание нового алгоритма F, реализующего итерационный метод решения задачи сильной отделимости путем последовательных построений псевдопроекций на разделяемые многогранники. Доказана теорема устойчивости, обосновывающая применимость алгоритма F для случая нестационарных задач сильной отделимости. Приведено формальное описание оригинального масштабируемого алгоритма S построения псевдопроекций, в основе которого лежит метод разбиения пространства на подпространства. Для алгоритма S доказана теорема сходимости, обеспечивающая его практическую применимость для решения задач сильной отделимости. На базе построенных методов и алгоритмов разработан эффективный параллельный численный алгоритм, реализованный в составе программного комплекса, ориентирован 84 ного на решение нестационарных задач сильной отделимости большой размерности на многопроцессорных системах с массовым параллелизмом. С помощью указанного программного комплекса на суперкомпьютере с кластерной архитектурой проведены вычислительные эксперименты, подтверждающие эффективность предложенных подходов. В заключение перечислим основные результаты диссертационной работы и приведем данные о публикациях и апробациях. Основные результаты диссертационной работы На защиту выносятся следующие новые научные результаты:
1. Разработан новый масштабируемый метод решения нестационарных задач сильной отделимости большой размерности. Для предложенного метода доказана теорема устойчивости.
2. Разработан параллельный итерационный алгоритм нахождения псевдопроекции точки на выпуклый многогранник, позволяющий эффективно решать задачи сильной отделимости на многопроцессорных системах с массовым параллелизмом. Для предложенного алгоритма доказана теорема сходимости.
3. Разработан и реализован программный комплекс для решения нестационарных задач сильной отделимости большой размерности на многопроцессорных системах с массовым параллелизмом, на базе которого проведены вычислительные эксперименты на модельных и случайных задачах, подтверждающие эффективность предложенных подходов. Публикации по теме диссертации в журналах из списка ВАК
1. Ершова А.В. Алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Системы управления и информационные технологии. 2009. № 1(35). С. 53-56. 2. Ершова А.В., Соколинская И.М. Параллельный алгоритм решения задачи сильной отделимости на основе фейеровских отображений // Вычислительные методы и программирование. 2011. Т. 12, № 2. С. 178-189.
3. Ершова А.В., Соколинская И.М. О сходимости масштабируемого алгоритма построения псевдопроекции на выпуклое замкнутое множество // Вестник ЮУрГУ. Серия «Математическое моделирование и программирование». 2011. № 37(254), вып. 10. C. 12-21.
4. Ершова А.В., Соколинская И.М. Исследование устойчивости параллельного алгоритма решения задачи сильной отделимости на базе фей-еровских отображений // Вестник ЮУрГУ. Серия «Математическое моделирование и программирование». 2012. № 18(277), вып. 12. C. 5-12. Публикации по теме диссертации в рецензируемых изданиях
5. Ершова А.В., Соколинская И.М. Масштабируемый параллельный алгоритм построения псевдопроекций в задачах сильной отделимости // Научный сервис в сети Интернет: экзафлопсное будущее: Труды международной научной конференции (19–24 сентября 2011 г., г. Новороссийск). М.: Изд-во МГУ, 2011. С. 132-138.
