1 Введение 3
2 Глава 1. Теоретические аспекты декомпозиционного подхода к решению оптимизационной задачи
1.1. Формулировка метода декомпозиции для алгоритмов
типа градиентного спуска 8
1.2. Постановка оптимизационной задачи метода опорных
векторов
1.3. Модификация алгоритма применения
декомпозиционного подхода для решения оптимизационной задачи метода опорных векторов 20
3 Глава 2. Практическая реализация применения декомпозиции
к оптимизационной задаче
4 Глава 3. Экспериментальные исследования
декомпозиционного подхода к решению оптимизационной задачи метода опорных векторов
Заключение .
Список использованной литературы
Приложение 1…
Купить

Во многих случаях реальные задачи, возникающие в различных областях, которые описывают разнообразные процессы и явления, требуют решения сложных оптимизационных задач и характеризуются большим количеством переменных, не меньшим количеством ограничений, целевых функций, задающихся алгоритмически. Как показывает опыт, нет такого единого подхода, применение которого было бы успешно для широкого круга практических задач. Разнообразие методов решения оптимизационных задач позволяют находить подходящее, варьируя различные параметры, но недостаточная эффективность традиционных методов, ограничения по времени и памяти, особенно для задач большой размерности с несколькими сотнями переменных делают вопросы создания нового математического, программного подхода особенно актуальными. В частности, при решении задач оптимального планирования на макроуровне, матрица ограничений достигает размерности 104—105. При такой размерности классические методы математического программирования (линейного, нелинейного, дискретного) оказываются малоэффективными. Т.е. мы сталкиваемся здесь с феноменом 'проклятие размерности' в понимании Р.Беллмана.
Данная работа посвящена разработке декомпозиционного подхода к решению оптимизационных задач и исследования его применимости. Декомпозиция - разделение целого на части. Суть этих методов можно описать следующим образом, различными способами исходная задача большой размерности разлагается на ряд независимых блоков, нахождения решения для каждого из них и последующей связке этих частных решений в общее решение исходной задачи. Впервые идея декомпозиции применительно к большим задачам оптимизации с блочно-диагональной структурой части ограничений была сформулирована совместно с Г.Данцигом и Вульфом, см.[1], а позднее развита в работах И.Корнаи, Т.Липтака [2]. Два декомпозиционных подхода, которые уже стали классическими и носящие имена их авторов. Метод решения представляет собой итеративный процесс, где решается так называемая координирующая или главная задача и имеется также локальная задача, которая при этом состоит из ряда независимых подзадач, соответствующих каждому блоку. Отличительной особенностью метода декомпозиции является использование координирующей задачи, которая имеет по сравнению с исходной небольшое число строк и большое число столбцов. Существенным является то, что для решения координирующей задачи не требуется задания всех столбцов в явном виде. Как показали исследования, метод применим для задач линейного программирования с матрицей общего вида. Однако неплохо бы было построить такой алгоритм, который позволил бы сократить решение до простых вычислительных процедур, которые выполнялись бы параллельно друг другу.
Обратим свое внимание на одну из широких и динамически развивающихся областей знаний - машинное обучение. Под этим термином понимается класс методов, отличающихся направленностью не на прямое решение задачи, а на процесс обучения, приспособления и применению ко множеству сходных задач. Для построения таких методов используются многочисленные средства математической статистики, численных методов, методов оптимизации, теории вероятности. Целью машинного обучения является частичная или полная автоматизация решения сложных профессиональных задач в самых разных областях человеческой деятельности, например, распознавание речи, жестов, образов, категоризация документов, обнаружение спама. И этот спектр применения постоянно расширяется
В качестве примера возьмем задачу оптимизации, которая ставится в одном из современных методов классификации и распознавания образов - метод опорных векторов (Support Vector Machines, SVM). Подобные системы обладают высокой точностью классификации, однако время обучения, особенно на больших наборах данных, очень велико и сложно, поскольку приходится скрупулезно подбирать параметры системы путем многократного запуска процедуры обучения. Данный метод изначально относится к бинарным классификаторам, хотя существуют способы заставить его работать и для задач мультиклассификации. Основная идея — перевод исходных векторов в пространство более высокой размерности и поиск разделяющей гиперплоскости с максимальным зазором в этом пространстве. Алгоритм работает в предположении, что чем больше разница или расстояние между этими параллельными гиперплоскостями, тем меньше будет средняя ошибка классификатора. Таким образом, для обучения метода опорных векторов можно решать как прямую задачу оптимизации, так и двойственную задачу(из решения которой легко получить решение прямой задачи). При этом граничные условия двойственной задачи имеют простую форму гиперпараллелепипеда.
Актуальность. Популярным подходом к решению двойственной задачи является метод декомпозиции. В этом методе на каждой итерации выбирается небольшое подмножество переменных X, по которым осуществляется оптимизация. Если оптимизируемых переменных всего две, то соответствующая задача решается аналитически. Итерационный процесс останавливается, когда текущее решение удовлетворяет достаточным условиям Куна-Таккера. Одной из наиболее популярных библиотек обучения SVM является LIBSVM1. В ней реализован метод декомпозиции, описанный в работе [4]. За основу же данной работы предполагается взять идею, предложенную И.В.Конновым [4], в которой модифицируются методы спуска интервальной функции, включающие декомпозицию для оптимизационной проблемы, поддерживающей свойство основной сходимости, но позволяющей уменьшить вычислительные затраты на одной итерации и обеспечить вычисление распределенным образом. Они в основном состоят в создании покоординатных шагов вместе со специальным пороговым контролем, которые позволяют установить скорость сходимости.
Целью диссертации является исследование применения декомпозиционного подхода при осуществлении решения задач оптимизации большой размерности, особенно характерных для задач машинного обучения (на примере метода опорных векторов).
Задачи исследования. Для достижения поставленной цели в диссертации сформулированы и решены следующие задачи:
1. Изучить методологию применения декомпозиции в алгоритмах типа градиентного спуска;
2. Сформулировать алгоритм с применением декомпозиции для метода опорных векторов;
3. Разработать программную реализацию алгоритма с применением декомпозиции для решения задачи классификации методом опорных векторов (последовательный и параллельный варианты);
4. Провести экспериментальное исследование алгоритма на основе использования различных подходов при декомпозиции;
5. Сформулировать рекомендации по применению алгоритма для решения задачи классификации;
Методы исследования. Теоретическое исследование базируется на общих принципах теории метрических пространств, аналитической геометрии и линейной алгебры, методе опорных векторов, методах выпуклой и невыпуклой оптимизации. Экспериментальное исследование проводилось с использованием программно-алгоритмического комплекса, разработанного автором.
Научная новизна. В данной работе разработан новый алгоритм для решения задачи бинарной классификации на основе метода градиентного спуска, который находит решение двойственной оптимизационной задачи метода опорных векторов с применением декомпозиции. Разработано программное обеспечение, на основе которого были проведены экспериментальные исследования, позволившие сделать вывод об эффективности использования сформулированного метода, а также разработать стратегии применения для различных вариантов декомпозиции.
Практическая значимость. Разработанный подход позволяет решать широкий класс оптимизационных задач, в частности к ним относиться задача бинарной классификации метода опорных векторов. А различные варианты стратегий декомпозиций позволяют подобрать наиболее подходящую для уже конкретной задачи и решать ее быстрее классического метода.

Купить