Исследование устойчивости параллельного алгоритма решения задачи сильной отделимости на базе Фейеровских отображений
Ключевые слова:
Фейеровское отображение, задача сильной отделимости, итерационный метод, псевдопроекция точки, устойчиво фейеровское отображение.Аннотация
В теории распознавания образов важное значение имеет задача сильной отделимости, заключающаяся в разделении двух выпуклых непересекающихся многогранников слоем наибольшей толщины. В работе рассматриваются нестационарные задачи сильной отделимости, то есть задачи, исходные данные которых меняются в ходе вычислительного процесса. Алгоритмы решения таких задач должны обладать двумя свойствами: автокорректируемостью и устойчивостью. Автокорректируемость подразумевает, что алгоритм может эффективно продолжать свою работу после единичного изменения входных данных. Устойчивость означает, что малое изменение входных данных приводит к малому изменению результата. Свойством автокорректируемости обладают итерационные алгоритмы, использующие фейеровские процессы. В статье описывается параллельный алгоритм решения задачи сильной отделимости на базе фейеровских отображений, допускающий эффективную реализацию на многопроцессорных системах с массовым параллелизмом. Вводится понятие устойчиво фейеровского отображения. Доказывается теорема, определяющая условия, при которых Фейеровское отображение будет устойчиво Фейеровским.Библиографические ссылки
Еремин, И.И. Фейеровские методы сильной отделимости выпуклых полиэдральных множеств / И.И. Еремин // Известия вузов. Сер. Математика. - 2006. - № 12. - C. 33 - 43.
Boser, B. A training algorithm for optimal margin classifiers / B. Boser, I. Guyon, V. Vapnik // Proc. of the 5th Annual ACM Workshop on Computational Learning Theory. Pittsburgh: ACM Press, 1992. - P. 144 - 152.
Еремин, И.И. Нестационарные процессы математического программирования / И.И. Еремин, В.Д. Мазуров. - М.: Наука, 1979. - 288 с.
Ершова, А.В. Параллельный алгоритм решения задачи сильной отделимости на основе фейеровских отображений / А.В. Ершова, И.М. Соколинская // Вычислительные методы и программирование. - 2011. - Т. 12, № 2. - С. 53 - 56.
Еремин, И.И. Теория линейной оптимизации / И.И. Еремин. - Екатеринбург: 'Екатеринбург', 1999. - 312 с.
Ершова, А.В. Алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений / А.В. Ершова // Системы управления и информационные технологии. - 2009. - № 1(35). - С. 53 - 56.
Черников, С.Н. Линейные неравенства / С.Н. Черников. - М.: Наука, 1968. - 488 с.
