Диссертация (Наилучшее отделение двух множеств с помощью нескольких гиперплоскостей)

САНКТ–ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиУДК 519.7Вздыхалкина Екатерина КонстантиновнаНаилучшее отделение двух множествс помощью нескольких гиперплоскостейДиссертация на соискание ученой степеникандидата физико–математических наукпо специальности 01.01.09 — дискретная математикаи математическая кибернетикаНаучный руководительдоктор физ.–мат. наук, профессорЛ.

Н. ПоляковаСанкт–Петербург 2014СОДЕРЖАНИЕВведение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3§1. Наилучшее линейное отделение двух множеств. . . . . . . . . . . . . . 14§2. Постановка задачи строгого h-отделения. . . . . . . . . . . . . . .

. . . . 25§3. Строгая h-отделимость и линейное программирование. . . . . . . . . 30§4. Метод «градиентного типа» строгого h-отделения. . . . . . . . . . . . 37§5. Безградиентный метод локального поиска. . . . . . . . . . . . . . . . . . 47§6. Численные эксперименты . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 56Дополнение A. Двойственность в линейном программировании. . . 79Дополнение B. Свойства плюсиковой функции . . . . . . . . . . . . . . . 82Дополнение C. Производные по направлению. . . . . . . . . . . .

. . . . 85Дополнение D. Лемма о сумме минимумов . . . . . . . . . . . . . . . . . . 89СПИСОК ЛИТЕРАТУРЫ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91Введение1. Область прикладной математики, которая теперь называется математической диагностикой [35], активно развивается с 60-х годов прошлогостолетия.

Она включает широкий круг задач: распознавание образов, классификацию и кластеризацию данных, машинное обучение, медицинскую итехническую диагностику. Простейшей задачей такого рода является отделение двух множеств в конечномерном или бесконечномерном пространствах.При решении задач математической диагностики используются статистические методы [2,53] , методы математического программирования (линейного [12, 38, 41, 51], билинейного [30], выпуклого [52]) и методы глобальной оптимизации [28]. Значительный вклад в развитие этого направлениявнесли М. А.

Айзерман, Э. М. Браверман, Л. И. Розоноэр [1], В. Н. Вапник [2, 53], А. Л. Горелик [4], Ю. И. Журавлёв [6], Ю. И. Неймарк [11],В. Н. Фомин [24], Я. З. Цыпкин [25], В. А. Якубович [26]. Особо следуетотметить О. Л. Мангасаряна. По его работам 1965–2014 годов [в частности,41-47, 29, 30, 37] можно проследить за всеми этапами развития математической диагностики.При решении конкретных задач математической диагностики возникаетнеобходимость в построении правила, в соответствии с которым судят опринадлежности данной точки тому или другому множеству. Это правилоназывают диагностическим правилом. Чаще всего его реализуют в видедискриминантной функции (функционала).

С начала 90-х годов прошлогостолетия в качестве дискриминантной активно используются недифферен-3цируемые функции. С их помощью удаётся, в частности, улучшить результаты в следующем направлении: в случае, когда выпуклые оболочки двухотделяемых множеств пересекаются, более точно выделить «смешаннуюполосу», содержащую точки как одного, так и другого множества.Для решения негладких задач математической диагностики привлекаются методы недифференцируемой оптимизации [35, 36, 27, 5, 7]. Примечательно, что при их реализации важную роль играет линейное программирование. Отметим также работы [31,33,34,39,48–50], которые обогатилиарсенал методов математической диагностики.Данное исследование проводится в русле работ Беннет-Мангасаряна [29]и Асторино-Гаудиозо [27].

Изучается задача наилучшего отделения выпуклой оболочки одного конечного множества от другого конечного множества с помощью нескольких гиперплоскостей. Используется недифференциремая дискриминантная функция с параметром. Параметр вводится дляпреодоления вычислительных трудностей, связанных с принципиальнойнеединственностью решения соответствующих экстремальных задач.2. Диссертация состоит из шести параграфов и четырёх дополнений.В §1 рассматривается задача наилучшего линейного отделения двух конечных множеств A и B из Rn . ПустьkA = {ai }mi=1 и B = {bj }j=1 .(1)Введём функцию [29]mk1 X1 Xhw, ai i − γ + c + +−hw, bj i + γ + c + ,f (g) =m i=1k j=1где g = (w, γ), c > 0 — параметр (в [29] вместо c стоит единица), [u]+ =max{0, u} — плюсиковая функция.

Справедливо следующее утверждение.4Теорема 1.1. Множества A и B строго линейно отделимы тогда итолько тогда, когда существует вектор g∗ , на котором f (g∗ ) = 0.Учитывая, что f (g) ≥ 0 при всех g, заключаем, что задача строгого линейного отделения множества A от множества B сводится к экстремальнойзадаче.f (g) → minn+1(2)g∈RВ свою очередь задача (2) эквивалентна задаче линейного программированияmk1 X1Xyi +zj → min,m i=1k j=1−hw, ai i + γ + yi ≥ c,(3)i ∈ 1 : m;hw, bj i − γ + zj ≥ c, j ∈ 1 : k;yi ≥ 0, i ∈ 1 : m;zj ≥ 0, j ∈ 1 : k.Задача (3) всегда имеет решение. Обозначим его w∗ , γ∗ , {yi∗ }, {zj∗ } ипусть µ — минимальное значение целевой функции.

Если µ = 0, то ги-перплоскость H∗ , определяемая уравнением hw∗ , xi = γ∗ , строго отделяетмножество A от множества B. При этом можно вычислить ширину отделяющей полосы.При µ > 0 множества A и B не допускают строгого линейного отделения. В этом случае будем говорить, что указанная ранее гиперплоскость H∗ , является наилучшей гиперплоскостью, приближённо отделяющей множество A от множества B.

Можно вычислить ширину «смешаннойполосы», содержащей точки обоих множеств.При µ > 0 имеется тонкость: может оказаться, что w∗ = O. Доказывается, что в этом случае у задачи (3) существует другое решение с w∗ 6= O.5Оно строится с помощью вспомогательной задачи линейного программирования.Приводятся примеры строгого и наилучшего приближённого линейногоотделения.

Выясняется, что аддитивный параметр c играет роль нормирующего множителя.§1 написан на основе работ [8, 10, 40].В §2 переходим к основной задаче — отделению выпуклой оболочки одного конечного множества от другого конечного множества с помощью hгиперплоскостей (задача h-отделения).Пусть множества A и B имеют вид (1). Обозначим co(A) выпуклую оболочку множества A.Введём функцию от матрицы [27]mk1X1 Xmax hws , ai i − γs + c + +min −hws , bj i + γs + c + .F (G) =m i=1 s∈1:hk j=1 s∈1:hЗдесь G — матрица размера h × (n + 1) со строкамиg s = (ws , γs ),s ∈ 1 : h,c > 0 — параметр (в [27] вместо c стоит единица).

Матрицу G указанныхразмеров будем называть подходящей, если у неё все ws ненулевые.Справедливо следующее утверждение.Теорема 2.1. Выпуклая оболочка множества A и множество B строгоh-отделимы тогда и только тогда, когда существует подходящая матрица G∗ , на которой F (G∗ ) = 0.Учитывая, что F (G) ≥ 0 при всех G, заключаем, что задача строгогоh-отделения сводится к экстремальной задачеF (G) →min .G∈Rh,n+16(4)При минимизации функции F (G) наибольшую трудность доставляет второе слагаемое (сумма минимумов).

Оно делает функцию F (G) невыпуклой(к тому, что она негладкая).В §3 показывается, что задача (4) с помощью «леммы о сумме минимумов» сводится к конечному числу задач линейного программирования. Дляэтого вводятся индексные цепочки S = (s1 , s2 , . . . , sk ), где sj ∈ 1 : h прикаждом j ∈ 1 : k. Каждой такой цепочке S сопоставляется экстремальнаязадачаmk s1 X1 Xmax hw , ai i − γs + c + +−hwsj , bj i + γsj + c + → min,Gm i=1 s∈1:hk j=1эквивалентная задаче линейного программированияmk1 X1Xpi +qj → min,m i=1k j=1−hai , ws i + γs + pi ≥ c,(5)i ∈ 1 : m, s ∈ 1 : h;hbj , wsj i − γsj + qj ≥ c, j ∈ 1 : k;pi ≥ 0,i ∈ 1 : m;qj ≥ 0,j ∈ 1 : k.Задача (5) имеет решение при всех S. Выделим цепочку S∗ , на которой минимальное значение целевой функции в задаче (5) принимает наименьшеезначение.

Обозначим {w∗s }, {γs∗ }, {p∗i }, {qj∗ } соответствующее решениезадачи (5). В §3 доказывается (теорема 3.1), что матрица G∗ , составленнаяиз строк (w∗s , γs∗ ), s ∈ 1 : h, является решением задачи (4).Возможны такие случаи.1) F (G∗ ) = 0 и G∗ — подходящая матрица. Тогда система гиперплоскостей H∗s , определяемых уравнениями hw∗s , xi = γs∗ , s ∈ 1 : h, строгоотделяет co(A) от B.2) F (G∗ ) = 0, но матрица G∗ — неподходящая. В этом случае справедливо7утверждение (теорема 2.2): не все w∗s нулевые; если обозначить через Jмножество индексов ненулевых w∗s , то множества co(A) и B строгоh − |J| -отделимы.3) F (G∗ ) > 0 и G∗ — подходящая матрица.

По аналогии со случаем h = 1будем говорить, что система гиперплоскостей H∗s , s ∈ 1 : h, осуществляет наилучшее приближённое h-отделение множества co(A) от B.В §3 приведён пример строгого 2-отделения.§2 и §3 написаны на основе работ [19, 21, 22].3. Итак, в §3 установлен принципиальный факт: задача h-отделения сводится к конечному числу задач линейного программирования. Однако количество таких задач линейного программирования может быть большим.Это побуждает обратиться к итерационным методам, которые позволяютполучить приближённое решение задачи h-отделения с требуемой точностью.Из общих соображений следует, что функция от матрицы F (G) дифференцируема по направлениям (в качестве которых также выступают матрицы).

На этой основе в §4 строится метод «градиентного типа» для приближённого решения задачи h-отделения (4). Опишем его принципальнуюсхему.Начнём с производной по направлению. По определениюF (G + tV ) − F (G).t→+0tF ′ (G, V ) = limДля того чтобы записать для F ′ (G, V ) явную формулу, введём обозначения8f (v, u) = hv, ui + c,!!ai−bjâi =, b̌j =,−11ϕ̂i (G) = max f (g s , âi ),s∈1:hψ̌j (G) = min f (g s , b̌j ),s∈1:hψj (G) = ψ̌j (G) + .ϕi (G) = ϕ̂i (G) + ,Тогдаmk1X1 Xϕi (G) +ψj (G).F (G) =m i=1k j=1Положим далееR̂i (G) = s ∈ 1 : h | f (g s , âi ) = ϕ̂i (G) ,Řj (G) = s ∈ 1 : h | f (g s , b̌j ) = ψ̌j (G) .Теорема 4.1.

Справедлива формулаmk1X ′1 X ′ϕ (G, V ) +ψ (G, V ),F (G, V ) =m i=1 ik j=1 j′гдеmax hv s , âi i,s∈R̂i (G) sϕ′i (G, V ) =maxhv,âi,i+s∈R̂(G)i0,min hv s , b̌j i,s∈Ř (G) j sψj′ (G, V ) =,hv,b̌iminj+s∈Řj (G)0,9если ϕ̂i (G) > 0,если ϕ̂i (G) = 0,если ϕ̂i (G) < 0;если ψ̌j (G) > 0,если ψ̌j (G) = 0,если ψ̌j (G) < 0.В Дополнении C приводится доказательство этой теоремы.Переходим к описанию одного шага численного метода минимизациифункции F (G).