Наилучшее отделение двух множеств с помощью нескольких гиперплоскостей тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах, рукописи

/

Г '

Вздыхалкина Екатерина Константиновна

НАИЛУЧШЕЕ ОТДЕЛЕНИЕ ДВУХ МНОЖЕСТВ С ПОМОЩЬЮ НЕСКОЛЬКИХ ГИПЕРПЛОСКОСТЕЙ

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

3 О иК1 2014

Санкт-Петербург

2014

005553987

005553987

Работа выполнена в Санкт-Петербургском государственном университете.

Научный руководитель: доктор физико-математических паук, профессор Полякова Людмила Николаевна

Официальные оппоненты:

Ерохин Владимир Иванович, доктор физико-математических наук, профессор, Санкт-Петербургский государственный технологический институт (технический университет), заведующий кафедрой инноватики и информационных технологий

Певный Александр Борисович, доктор физико-математических наук, профессор, Сыктывкарский государственный университет, профессор кафедры прикладной математики

Ведущая организация: Академический университет РАН

Защита состоится " " tiCU ¿VVi 2014 г. в Ы часов на заседании диссертационного совета Д.212.232.29 на базе Санкт-Петербургского государственного университета по адресу: 199178, Санкт-Петербург, 10 линия В.О., д. 33/35, ауд. 74.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9 и на сайте http://spbu.ru/science /disser/dissertatsii-dopushchennye-k-zashchite-i-svedeniya-o-zashchite.

Автореферат разослан " "_2014 года.

Ученый секретарь диссертационного совета

доктор физ.-мат. наук, профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Область прикладной математики, которая теперь называется математической диагностикой, активно развивается с 60-х годов прошлого столетия. Она включает широкий круг задач: распознавание образов, классификацию и кластеризацию данных, машинное обучение, медицинскую и техническую диагностику. Простейшей задачей такого рода является отделение двух множеств в конечномерном или бесконечномерном пространствах.

При решении задач математической диагностики используются статистические методы, методы математического программирования (линейного, билинейного, выпуклого) и методы глобальной оптимизации. Значительный вклад в развитие этого направления внесли М. А. Айзерман, Э. М. Браверман, Л. И. Ро-зоноэр, В. Н. Вапник, А. Л. Горелик, Ю. И. Журавлев, Ю. И. Неймарк, В. Н. Фомин, Я. 3. Цыпкин, В. А. Якубович. Особо следует отметить О. Л. Мангасаряна. По его работам 1965-2014 годов можно проследить за всеми этапами развития математической диагностики.

При решении конкретных задач математической диагностики возникает необходимость в построении правила, в соответствии с которым судят о принадлежности данной точки тому или другому множеству. Это правило называют диагностическим правилом. Чаще всего его реализуют в виде дискрими-нантной функции (функционала). С начала 90-х годов прошлого столетия в качестве дискриминантной активно используются недифференцируемые функции. С их помощью удается, в частности, улучшить результаты в следующем направлении: в случае, когда выпуклые оболочки двух отделяемых множеств пересекаются, более точно выделить «смешанную полосу», содержащую точки как одного, так и другого множества.

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

з

методы недифференцируемой оптимизации. Примечательно, что при их реализации важную роль играет линейное программирование.

Целью диссертационной работы является исследование параметрического варианта задачи наилучшего отделения выпуклой оболочки одного конечного множества от другого конечного множества с помощью нескольких гиперплоскостей и разработка численных методов решения таких задач. Исследование проводилось в русле работ Беннет-Мангасаряна1 и Асторино-Гаудиозо2.

Основные результаты, полученные в диссертации и выносимые на защиту:

• получены необходимые и достаточные условия строгой отделимости двух множеств с помощью h гиперплоскостей;

• показано, что задача /г-отделения сводится к конечному числу задач линейного программирования;

• введен параметр для преодоления вычислительных трудностей, связанных с принципиальной неединственностью решения соответствующих экстремальных задач;

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

• разработан безградиентный метод /i-отделения, максимально учитывающий специфику данной задачи;

• оба предложенных метода реализованы в системе MATLAB;

• исследована проблема выбора начального приближения в задачах строгой /i-отделимости.

Научная новизна. Все основные результаты диссертации являются новыми.

'Bennett К. Р., Mangassarian О. L. Robust linear programming discrimination of two linearly inseparable sets // Optimization Methods and Software. 1992. Vol. 1, pp. 23-34.

'Astorino A., Gaudioso M. Polyhedral separability througt successive LP // JOTA. 2002. Vol. 112. No. 2, pp. 2G5-293.

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

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

Апробация работы. Результаты, изложенные в диссертации, докладывались и обсуждались на на 40-й, 41-й, 42-й и 44-й Международных научных конференциях аспирантов и студентов «Процессы управления и устойчивость» (г. Санкт-Петербург, 6-9 апреля 2009 г., 5-8 апреля, 2010 г., 4-7 апреля 2011 г., и 1-4 апреля 2013г.), международной конференции «Конструктивный негладкий анализ и смежные вопросы» (СКЗЛ-2012) (г. Санкт-Петербург, 18-23 июня 2012 г.), на Всероссийской молодежной научной школе-семинаре «Дискретные модели и методы принятия решений» (г. Новосибирск, 21-23 июня, 2013 г.; диплом за лучший доклад), на Санкт-Петербургском городском семинаре по дискретному гармоническому анализу и геометрическому моделированию и на семинарах кафедры математической теории моделирования систем управления (факультет прикладной математики - процессов управления СПбГУ).

Публикации. По результатам исследований опубликовано 9 печатных работ, две из которых в соавторстве и три в изданиях, рекомендуемых ВАК. В работах [3, 9] все результаты принадлежат диссертанту: соавтору (руководителю семинара) принадлежит постановка задачи.

Структура и объем диссертации. Диссертация состоит из введения, шести параграфов, четырех дополнений и списка литературы. Объем диссертации составляет 96 страниц. Список литературы содержит 53 наименования. В диссертации имеется 36 рисунков.

СОДЕРЖАНИЕ РАБОТЫ

Во введении приводится обзор литературы по теме работы, обсуждается актуальность исследования, его теоретическая и практическая ценность, научная новизна.

В § 1 рассматривается задача наилучшего линейного отделения двух конечных множеств Л и В из R™. Пусть

A = {ai)Z! И В = {6j}jU- (1)

Введем функцию

1 m 1 ^

f(9) = - Е i(w' + + l HHW' bj) + 7 + с]

¡=1 j=1

где g = (w,j), с > 0 — параметр, [u]+ = max{0, и} — плюсиковая функция. Справедливо следующее утверждение.

Теорема 1.1. Множества А и В строго линейно отделимы тогда и только тогда, когда существует вектор д,, па котором f(g*) = 0.

Учитывая, что f(g) >0 при всех д, заключаем, что задача строгого линейного отделения множества А от множества В сводится к экстремальной задаче

/(<7)-+ min (2)

seRn+1

В свою очередь задача (2) эквивалентна задаче линейного программирования

к

1 ^

тп к .

i=i j=i

- {w, а,) + 7 + yt > с, г 6 1 : тп; (w, bj) -7 + Zj>c, j el: к; Vi > 0, г € 1 : m; Zj>Q,j&l:k.

Задача (3) всегда имеет решение. Обозначим его (ад,, 7,, {у,*}, и пусть /х — минимальное значение целевой функции. Если /I = 0, то гиперплоскость Н,, определяемая уравнением (гу»,х) = 7«, строго отделяет множество А от множества В. При этом можно вычислить ширину отделяющей полосы.

При /х > 0 множества Л и В не допускают строгого линейного отделения. В этом случае будем говорить, что указанная ранее гиперплоскость Н,, является наилучшей гиперплоскостью, приближенно отделяющей мноэ/сество А от множества В. Можно вычислить ширину «смешанной полосы», содержащей точки обоих множеств.

При ц > 0 имеется тонкость: может оказаться, что и= О. Доказывается, что в этом случае у задачи (3) существует другое решение с ш, / О. Оно строится с помощью вспомогательной задачи линейного программирования.

Приводятся примеры строгого и наилучшего приближенного линейного отделения. Выясняется, что аддитивный параметр с играет роль нормирующего множителя.

В § 2 мы переходим к основной задаче — отделению выпуклой оболочки одного конечного множества от другого конечного множества с помощью к гиперплоскостей (задача И,-отделения).

Пусть множества А и В имеют вид (1). Обозначим со (Л) выпуклую оболочку множества А.

Введем функцию от матрицы

^ т 1 ^

о.-> - -Г- + с]+ + - тт [-<!«-, Ь;)+Ъ + с]+.

¿=1 .7=1

Здесь £7 — матрица размера /1 х (п + 1) со строками

д* = (-ш8, 7а), з е 1 : Л, с > О — параметр. Матрицу С указанных размеров будем называть подходящей,

если у нее все w ненулевые.

Справедливо следующее утверждение.

Теорема 2.1. Выпуклая оболочка множества А и множество В строго h-отделимы тогда и только тогда, когда существует подходящая матрица G», на которой F(G,) = 0.

Учитывая, что F(G) > 0 при всех G, заключаем, что задача строгого /i-отделения сводится к экстремальной задаче

F(G) —> min . (4)

GeR'l>n+1

При минимизации функции F(G) наибольшую трудность доставляет второе слагаемое (сумма минимумов). Оно делает функцию F(G) невыпуклой (к тому, что она негладкая).

В § 3 показывается, что задача (4) с помощью «леммы о сумме минимумов» сводится к конечному числу задач линейного программирования. Для этого вводятся индексные цепочки S = (si, s?,..., Sk), где Sj S 1 : h при каждом j б 1 : к. Каждой такой цепочке S сопоставляется экстремальная задача

1 m 1 к

m 1С ~ 7s + с] + + ^ S Ь . Ь) + Ъj + с] + -> nun,

i=1 j=1

эквивалентная задаче линейного программирования

1 т 1 к ~ + min> (5)

тп к t—'

1=1 3=1

— (di, ws) + 7s + pi > с, i £ 1 : m, s £ 1 : h\ (bj, ws») - 7Sj. +qj>c, je 1 : k\ Pi> 0, i € 1 : m\ qj > 0, j G 1 : k.

Задача (5) имеет решение при всех S. Выделим цепочку S,, на которой мини-

мальное значение целевой функции в задаче (5) принимает наименьшее значение. Обозначим ({к;®}, {7^}, {?*},{?]}) соответствующее решение задачи (5). В § 3 доказывается (теорема 3.1), что матрица (3», составленная из строк (ги®,7*), в £ 1 : Л, является решением задачи (4).

Возможны такие случаи.

1) ^(б») = 0 и б, — подходящая матрица. Тогда система гиперплоскостей Щ, определяемых уравнениями (и>1,х) = 7*, я € 1 : /1, строго отделяет со(Л) от В.

2) ^(С«) = 0, но матрица (3, — неподходящая. В этом случае справедливо утверждение (теорема 2.2): не все нулевые; если обозначить через 7 множество индексов ненулевых то множества со(Л) и В строго (Ъ,— \ J\)-отделимы.

3) ^(С») > 0 и С, — подходящая матрица. По аналогии со случаем /г = 1 будем говорить, что система гиперплоскостей Н€ 1 : /г, осуществляет наилучшее приближенное /г-отделение множества со(Л) от В.

В § 3 приведен пример строгого 2-отделения.

Итак, в § 3 установлен принципиальный факт: задача /¡.-отделения сводится к конечному числу задач линейного программирования. Однако количество таких задач линейного программирования может быть большим. Это побуждает обратиться к итерационным методам, которые позволяют получить приближенное решение задачи /г-отделения с требуемой точностью.

Из общих соображений следует, что функция от матрицы ^(С?) дифференцируема по направлениям (в качестве которых также выступают матрицы). На этой основе в § 4 строится метод «градиентного типа» для приближенного решения задачи /¿-отделения (4). Опишем его принципальную схему.

Начнем с производной по направлению. По определению

т ю = нш пс+т-р{с)

Для того чтобы записать для Р'(С, V) явную формулу, введем обозначения

/(и, и) = (V, и) + с, ( а.

, Ъ}= I

-6, 1

Тогда

фг(С) = тах/(д", а{), ф^С) = тт/(/, Ь^,

т 1 ^

¿=1

Положим далее

Мс) = {5 е 1 : /г I /($', о,-) = фг(С)}, Я, (С) = е 1 : Л | /(<Д Ь) = ^-(С)}.

Теорема 4.1. Справедлива формула

- т - А

= +У),

«=1

3=1

где

ч>'№, V) =

тах (V5, ¿¿), если фг(С) > О, тах [(г;8, а,-)1 , если ф^С) = О,

О,

если <£г(С?) < 0;

ю

min (vs, bj}, если tpj(G) > 0, seflj(C)

Tp'j(G,V)=l min [(us, если ipj(G) = 0,

seRj(G)

+

0

если i>j{G) < 0.

В Дополнении С приводится доказательство этой теоремы. Переходим к описанию одного шага численного метода минимизации функции Р(С). Пусть имеется г/-е приближение (Зу. Для определения направления спуска из точки решаем вспомогательную экстремальную задачу

где минимум берется по матрицам V размера h х (n+1), все элементы которых ограничены по модулю некоторой константой К > 0. Задача (6) сводится к небольшому числу задач линейного программирования. Она имеет решение Vv. Если F'(GV, Vv) > 0, то G„ — стационарная точка функции F(G). Вычисления прекращаются. В противном случае матрица Vv является направлением убывания функции F(G) из точки Gv. Находим шаг t„ > 0 в направлении Vv, обеспечивающий гарантированное уменьшение функции F(G). Полагаем G„+1 = G„ + tl/Vu, после чего вычисления повторяются. Описание принципиальной схемы метода «градиентного типа» для решения задачи (4) завершено.

В § 4 приводится пример на применение данного метода к решению задачи 3-отделения. Основное внимание уделяется организации вычислений.

В § 5 предлагается еще один численный метод решения задачи (4), максимально усиливающий ее специфику. Опишем общий шаг этого метода.

Фиксируем положительные параметры точности ел, £в и а.

Пусть имеется v-e приближение — матрица Gy со строками qsu, s £ 1 : /i. Для получения очередного приближения Gv+1 выполняем следующие операции:

F'(G, V) ->• min,

(6)

1) Вычисляем F{GV).

2) Формируем индексные множества

I„ - U 6 1 : тп | тащ) > -еА}, Л = {i £ 1 : fc I min f(gf„ Ь5) > -ев},

s€l:h

L- = {sel:h\ f(gsu, bj) = min /(«?£, b,-)}, j € J„.

p£l:/l

3) Перебираем индексные цепочки S = {sj}jej„, Sj € Lj, пока не найдется цепочка S = {Sj}jgj„ со следующим свойством: решение V„ экстремальной задачи

Q(GU + V):=-J2 <Pi(G„ + V) + \ J2 [ftö + Л h)}+ min,

te/„ JBJ„

где минимум берется по матрицам V, все элементы которых ограничены по модулю некоторой константой К > 0, удовлетворяет неравенству

Q{Gv + Vv)<F(Gv)-a. (7)

4) Полагаем Gv+1 = Gv + tvVv, где tv — точка минимума функции F{GV + tVv) на отрезке [0, 1].

Если цепочка S, обеспечивающая неравенство (7), отсутствует, то Gv — почти локально оптимальная матрица. В этом случае вычисления прекращаются.

Доказывается, что описанный процесс конечен.

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

Дополнение А посвящено линейному программированию. Приводится

теорема существования решения и две теоремы двойственности. Делается замечание о практическом решении задач линейного программирования в среде MATLAB.

В Дополнении В собраны многочисленные свойства плюсиковой функции.

В Дополнении С выводится формула для производной по направлению от функции матрицы F(G).

В Дополнении D доказывается лемма о сумме минимумов.

Все результаты из Дополнений активно используются в основном тексте.

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, входящих в перечень ВАК рецензируемых научных журналов:

1. Чернэуцану (Вздыхалкина) Е. К. Анализ задачи строгого h-отделения двух множеств. Вестник СПбГУ. Сер. 10. 2012. No 4, с. 85-91.

2. Чернэуцану (Вздыхалкина) Е. К. Метод градиентного типа для решения задачи строгого /i-отделения // Вестник СПбГУ. Сер. 10. 2013. No 2, с. 67-75.

3. Malozemov V. N. and Chemeutsanu (Vzdykhalkina) E. К. The best linear separation of two sets // Springer Optimization and its Applications. Springer Sciense+Business Media. New York, 2014. Vol. 87, pp. 175-183.

Публикации в других изданиях:

4. Chemeutsanu (Vzdykhalkina) E. On strict /i-polyhedral separability of two sets // International Conference «Constructive Nonsmooth Analysis and Related Topics». Abstracts. SPb, 2012. P.33-34.

5. Черпэуцану (Вздыхалкина) Е. К. Наилучшее линейное отделение двух множеств / Всероссийская молодежная школа-семинар «Дискретные модели и методы принятия решений»: Материалы школы-семинара (г. Новосибирск, 21-23 июня 2013). Новосибирск: Изд-во ин-та математики, 2013. С. 329.

6. Черпэуцану (Вздыхалкина) Е. К. Нахождение разделяющей гиперплоскости между двумя политопами / Процессы управления и устойчивость: Труды 41-й международной научной конференции аспирантов и студентов. Санкт-Петербург, 2010. С. 736-739.

7. Черпэуцану (Вздыхалкина) Е. К. Строгая Л-отделимость двух множеств и линейное программирование / Процессы управления и устойчивость: Труды 42-й международной научной конференции аспирантов и студентов. Санкт-Петербург, 2011. С. 259-265.

8. Черпэуцану (Вздыхалкина) Е. К. Численные эксперименты по строгой /¿-отделимости / Процессы управления и устойчивость: Труды 44-й международной научной конференции аспирантов и студентов. Санкт-Петербург, 2013.

9. Малозёмов В. Н., Черпэуцану (Вздыхалкина) Е. К. Численный метод строгого Ь-отделения // Семинар по дискретному гармоническому анализу и геометрического моделированию «БНА & САСБ». Избранные доклады. 15 октября 2011 г. (http://dha.spb.ru/PDF/hSepNumerical.pdf)

Подписано к печати 05.09.14. Формат60x84 'Лб. Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 1,00. Тираж 100 экз. Заказ 6075.

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043,428-6919

С. 88-93.