Построение семейств разделяющих гиперплоскостей

В последние 50 лет бурное развитие получило новое направление в научных исследованиях — теория распознавания и обработка изображений. Интенсивное развитие этой области знаний обусловлено большой потребностью в решении практических задач в самых различных областях: в медицинской диагностике, в геологическом прогнозировании, в робототехнике, в оценке политических и экономических ситуаций, в предсказании землетрясений и других природных катаклизмов, в задачах идентификации букв для автоматического чтения, идентификации речи и т. д.

Крупные результаты в этой области были получены во второй половине прошлого века. Укажем лишь некоторых из ведущих ученых, стоявших у истоков исследований в этой области: А. А. Ляпунов, О. Б. Лупанов, С. В. Яблонский, Ю. И. Журавлев, С. Н. Черников, И. И. Еремин, М. А. Айзерман. В 1998 году вышли в свет «Избранные научные труды Ю.И. Журавлева», в которых изложены основополагающие работы по математическим методам распознавания образов и дискретной математике. Научная школа Ю. И. Журавлева, создававшаяся на базе Вычислительного центра АН СССР, постоянно расширяется и сейчас имеет своих последователей не только в нашей стране, но и за рубежом.

Среди других научных школ упомянем коллектив МГУ, созданный А. А. Ляпуновым, С. В. Яблонским, О. Б. Лупановым. В Институте математики и механики УрО РАН успешно работает группа, образованная в 60-е годы С. Н. Черниковым и впоследствии возглавленная И. И. Ереминым.

На протяжении последних 14 лет в Москве издается журнал «Pattern recognition and image analysis», в котором публикуются важнейшие работы, выполненные в области кибернетики и теоретической информатики.

Большая работа в области распознавания образов ведется в США в университете Висконсина под руководством профессора О. Мангасарьяна. Вместе со своими учениками О. Мангасарьян провел обширные исследования, но общей теории диагностики, классификации и по применению методов оптимизаций в распознавании образов, решение прикладной задач в медицине и биологии. Укажем лишь на некоторые из многочисленных публикации О. Мангасарьяна и его учеников: работа О. Мангасарьяна, Н. Стрита, В. Волберта [44], К. Беннетт, Е. Бредестейра [30]. Алгоритмы и программы распознавания образов приведены в книге В. Н. Вапника [3]. Проблемы классификации изучаются в книге С. Бойда и JI. Ванденберга [32].

Среди многочисленных проблем, возникающих в области распознавания, укажем задачу построения гиперплоскостей, разделяющих два выпуклых множества. Построению численных методов решения этой задачи посвящена данная работа. В качестве выпуклых множеств рассмотрены полиэдры (пересечение конечного числа полупространств) и политопы (выпуклые оболочки конечного числа точек).

Теорема о существовании разделяющей гиперплоскости играет важную роль в функциональном анализе, в теории оптимизации и исследовании операций. При решении практических задач важно не только знать, что разделяющая гиперплоскость существует, но и уметь конструктивно ее строить. В данной работе в главах 1−3 предлагаются численные методы нахождения семейств гиперплоскостей, разделяющих два непересекающихся непустых полиэдра, заданных с помощью систем линейных неравенств и систем линейных уравнений с неотрицательными переменными. В главах 4 и 5 разработаны численные методы построения разделяющих гиперплоскостей для политопов.

Предлагаемые численные методы основаны на использовании теорем об альтернативах и метода модифицированных функций Лагранжа. Подход, связанный с применением теорем об альтернативах в численных методах, возник несколько лет назад и изложен в работах [7]—[15], [33]- [37]. Он основан на отыскании исевдорешений несовместных систем линейных равенств и неравенств. По найденным псевдорешениям строятся нормальные решения альтернативных совместных систем и с их помощью определяются гиперплоскости, разделяющие полиэдры. В работе приводятся иллюстративные примеры, даны таблицы с численными расчетами тестовых примеров. Теоремам об альтернативах посвященное большое количество публикаций. Укажем, например, [6],[22], [31]-[33], [38].

В главе 1 рассмотрено применение нормального решения альтернативной системы для построения семейства разделяющих гиперплоскостей. Использование результатов работы [9, 11, 12], позволяет найти нормальное решение из решения задачи безусловной минимизации невязки несовместной системы неравенств, задающей оба полиэдра. Если число переменных в задаче безусловной минимизации гораздо меньше, чем в альтернативной совместной системе, то такие расчеты менее трудоемки, чем нахождение решения альтернативной системы.

В основе лежит теорема И. И. Еремина о гиперплоскости, разделяющей полиэдры, заданные системами неравенств [15, теорема 10.1]. Используется специфический вид разделяющей гиперплоскости, нормаль и сдвиг которой выражены через произвольное решение некоторой системы, являющейся альтернативной к несовместной системе. Эта несовместная система состоит из двух совместных подсистем, каждая из которых определяет непустой полиэдр. Система несовместна, так как эти полиэдры не пересекаются. Построение разделяющих гиперплоскостей существенно опирается на теоремы об альтернативах.

В главе 1 рассмотрены два полиэдра.

Хг = {х € Шп: А&- > h}, Xi = {xGRn: А2х >'b2}.

Предполагается, что эти полиэдры непусты, а их пересечение пусто. Тогда система.

Агх > Ьи А2х > Ь2 (0.1) несовместна, а альтернативная система.

Ajui + Aju2 = 0n, bjui + bjui+ = p, щ > 0mi, щ > 0m2, (0.2) где p > 0, напротив, совместна. Определим линейную функцию ip (x, а) от неременного вектора я, скаляра, а из интервала [0,1]: ip (x, а) = uJ{Ax — &i) + ар. (0.3).

Если щ — решение системы (0.2), то уравнение <�р (х, а) = 0 задает гиперплоскость, разделяющую полиэдры Х и Х2. Гиперплоскость (0.3) при, а = 0.5 была впервые построена И. И. Ереминым. Метод определения функции ip состоит в нахождении решения системы (0.2) и использовании формулы (0.3). Такой подход весьма затруднителен в том случае, когда т п. Поэтому в первой главе данной работы для построения разделяющей гиперплоскости предлагается решать следующую задачу безусловной минимизации в п — мерном пространстве: mini[||(bi — Aia-)+||2 + ||(Ь2 — Л2х)+||2]. (0.4) хеК ^.

Доказана теорема, утверждающая, что найденный из этой задачи вектор х* является псевдорешением системы (0.1) и нормальное решение й*т = [?"iT, W2T] системы (0.1) определяется, но формулам z = (bi — Aix*)+, 4 = fa — А2х*)+, fii = рА! (Ikl2 + II4II2), Й2 = Р4/(т2 + ш2).

Функция (р, которая определяет разделяющую гиперплоскость, записывается в виде: ufiAxx — Ъг) + ар = 0, где 0 < а < 1. (0.5).

Объединение всех таких гиперплоскостей, когда, а изменяется от 0 до 1, называется семейством параллельных разделяющих гиперплоскостей.

В теореме 1.2 дан анализ решений задачи (0.4). Показано в частности, что, если Х ф 0, Х2 ф 0, Х П Хч = 0, то все решения системы (0.2) отличны от нуля, кроме того, дана формула для определения толщины семейства разделяющих гиперплоскостей. Предложенный подход к построению разделяющих гиперплоскостей наиболее эффективен в задачах, где размерность вектора п невелика, но количество ограничений т может быть значительным, т. е. пС га .

В § 1.2 показано, что в ряде случаев найденное семейство разделяющих гиперплоскостей можно расширить, решая две вспомогательные задачи линейного программирования. Приведены три примера, иллюстрирующие найденные свойства разделяющих гиперплоскостей. Система (0.2) имеет весьма глубокий смысл. Приведенная в диссертации теорема 1.4 утверждает, что всякая строго разделяющая гиперплоскость такова, что всегда ее направляющий вектор с и сдвиг 7 выражаются через какое-нибудь решение системы (0.2).

При решении практических задач может оказаться, что полученные в результате экспериментов данные содержат погрешности, изза которых матрица, А и вектор b вычислены неточно. В результате этого множества Х и Х2 могут пересекаться. В этом случае рекомендуется так скорректировать множества Х и Х2, что полученные вместо них множества Х С Х и Х2 С Х2 не пересекаются. Для этих множеств можно построить разделяющие гиперплоскости, используя технику, изложенную выше. При этом желательно, чтобы норма корректирующего вектора были бы минимально возможной. В § 1.4 приведены формулы определения оптимальной коррекции и предлагаемая техника проиллюстрирована на простейшем примере.

В § 1.5 рассмотрена возможность применения масштабирования целевой функции для максимизации толщины семейства разделяющих гиперплоскостей. Вместо (0.4)решается иромасштабированная задача min 1[||(б! — А1Х)+1|2 + Л||(62 — Л2а-)+||2], (0.6) где Л — искомый коэффициент.

Толщина семейства (0.5) становится функцией Л. Найдя из (0.6) оптимальный вектор х*(Х), определим и|(А), А) и, но формулам, аналогичным (0.5), получим новое семейство разделяющих гиперплоскостей. Численно ищется максимум толщины семейства по, А. Во всех примерах за счет введения, А удалось так повернуть гиперплоскости, что в результате получались семейства, толщины которых совпадали с расстояниями между множествами Xi и Х2.

В § 2.1 ставится задача квадратичного программирования об определении семейства гиперплоскостей максимальной толщины, совпадающей с минимальным расстоянием между полиэдрами. Эта задача сводится к минимизации функции от 2п переменных при наличии т линейных ограничений типа неравенства. Построена двойственная задача, состоящая в максимизации квадратичной функции от т неременных на положительном ортанте при наличии п линейных ограничений тина равенства. Показано, что, решив эту задачу, можно легко определить семейства разделяющих гиперплоскостей максимальной толщины.

В § 2.2 ставится задача нахождения такого решения системы Еремина (0.2), при котором толщина семейства разделяющих гиперплоскостей была бы максимальной. Показано, что эта задача состоит в минимизации квадратичной функции от т переменных при наличии п + 1 ограничений на положительном ортанте. Построена задача, двойственная к этой задаче. В работе даны три варианта задач, позволяющих построить разделяющую гиперплоскость максимальной толщины. Выбор наиболее подходящего варианта производится в зависимости от конкретных чисел тип.

В главе 3 строятся семейства разделяющих гиперплоскостей для двух полиэдров, заданных с помощью системы линейных уравнений с неотрицательными переменными. Показано, что в отличие от случая полиэдров, заданных с помощью системы линейных неравенств, любое решение альтернативной системы определяет два различных семейства разделяющих гиперплоскостей. Установлено, что не любая разделяющая гиперплоскость может быть представлена с помощью решения альтернативной системы (0.2). Приведен соответствующий иллюстративный пример.

В главе 4 рассмотрен случай построения семейства гиперплоскостей, разделяющих два политопа. Предполагается, что в Rn задан набор из mi точек и другой набор из Ш2 точек. Общее число точек равно т + Ш2 = т. Выпуклые оболочки (политопы), натянутые на эти множества, обозначены через Х и Х-2 соответственно.

В § 4.1 ставится задача нахождения вектора, соединяющего две ближайшие точки из двух политопов. Эта задача заменена эквивалентной, более простой задачей, для которой построена двойственная к ней задача.

В § 4.2 приведены формулы, определяющие семейство гиперплоскостей максимальной толщины, разделяющих два политопа.

В § 4.3 метод модифицированных функций Лагранжа (МФЛ) применяется к прямой, а в § 4.4 — к двойственной задаче. В задачах, где т п, целесообразно использовать метод МФЛ для решения двойственной задачи, так как в ней ищется безусловный минимум в п + 1-мерном пространстве. Если п т, то, напротив, метод МФЛ применяется к прямой задаче, где вспомогательная задача состоит в отыскании безусловного минимума в т-мерном пространстве. Оба варианта метода МФЛ были реализованы автором в системе MATLAB. Программы использовали в качестве вспомогательной процедуры обобщенный метод Ньютона (краткое его описание приведено в приложении). Метод МФЛ, примененный для решения прямой задачи, оформлен в виде программы MLF1. Для решения двойственной задачи — в виде MLF2. В § 4.3 и § 4.4 даны результаты численных расчетов с помощью программ MLF1 MLF2 и программ, содержащихся в библиотеке оптимизационных программ системы MATLAB. При решении задач небольшой размерности оба подхода давали примерно одинаковые результаты. При решении задач большой размерности методы МФЛ показали более высокую эффективность расчетов по сравнению с алгоритмами, содержащимися в библиотеке MATLAB. Объясняется это тем, что в данной реализации метода МФЛ высокую эффективность демонстрирует обобщенный метод Ньютона.

В § 4.4 приведен генератор тестовых задач (программа Codel). С его помощью задавались различные варианты задач, в том числе и задачи высокой размерности. В § 4.3, например, решается задача, в которой т = 1000, п = 10 000. В § 4.4 — задача с т = 5 • 106, п — 2. Далеко не все задачи большой размерности удалось решить с помощью библиотеки программ оптимизации MATLAB. Например, задача с т = 300, п = 10 000 и т = 1000, п = 10 000 были решены программой MLF1 за 8.5 сек. и 96.6 сек. соответственно, но не были решены программой MATLAB .

Аналогично, в § 4.4 с помощью программы MLF2 решена задача с т = 5 • 106 и п = 2 за 167.7 сек. Эта задача также не была решена программой MATLAB. При решением задачи с т = 4*106, п = 2 время счета, но программе MLF2 было в 2 раза меньше, чем по программе MATLAB .

В главе 5 изучается случай, когда выпуклые оболочки двух множеств (политопов) пересекаются. Вводится процедура сжатия выпуклых оболочек. В результате получаются два непересекающихся политопа и для скорректированных выпуклых оболочек строится семейство разделяющих гиперплоскостей. В качестве разделяющей гиперплоскости берется гиперплоскость, проходящая через середину семейства. Она условно разделяет исходные множества точек. В приведенном примере эта гиперплоскость отделяет 96% точек одного множества от 97% точек другого множества.

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

ЗАКЛЮЧЕНИЕ

.

В диссертационной работе были получены следующие основные результаты.

1. На основе применения теорем об альтернативах разработаны новые численные методы построения семейств гиперплоскостей, разделяющих полиэдры, заданные в n-мерном пространстве. При этом простейший метод состоит в безусловной минимизации кусочно-квадратичной выпуклой функции в n-мерном пространстве. Безусловная минимизация проводится с помощью глобально сходящегося за конечное число шагов обобщенного метода Ныотона.

2. Исследована возможность построения семейства разделяющих гиперплоскостей максимальной толщины на основе применения теоремы об альтернативах.

3. Дано обобщение теоремы И. И. Ерёмина о семействе гиперплоскостей, разделяющих полиэдры, при задании их системами равенств на неотрицательном ортанте. Показано, что в этом случае каждому решению альтернативной совместной системы соответствует два семейства разделяющих гиперплоскостей.

4. Программно реализован в системе MATLAB численный метод построения семейства гиперплоскостей, разделяющий полиэдры, заданные большим числом (несколько миллионов) линейных неравенств.

5. На основе модифицированной функции Лагранжа и обобщенного метода Ньютона предложены и программно реализованы в системе MATLAB численные методы построения семейства гиперплоскостей максимальной толщины, разделяющих политопы. Численные эксперименты показали возможность решения таких задач с количеством данных до пяти миллионов.

6. Рассмотрен случай, когда два политопа пересекаются. С помощью операции сжатия из них образуются непересекающиеся политопы. Для скорректированных таким образом политопов задача построены семейства разделяющих гиперплоскостей максимальной толщины сведена к задаче безусловной минимизации в т + п + 1- мерном пространстве.