К задаче построения кусочно-линейной дискриминантной функции

Рассматривается задача численного нахождения кусочно-линейной функции, разделяющей два конечных множества A и B из Rn, трактуемых как обучающее множество в задаче дискриминантного анализа. Для целей строгой отделимости множеств подразумевается, что множества и не имеют общих точек, но и их наличие не является препятствием для предлагаемого алгоритма. Выпуклость дискриминантной функции или пустота пересечения выпуклых оболочек этих множеств также не предполагается. Естественным ограничением является требование принадлежности распознаваемого элемента аффинной оболочке обучающего множества. Для этих целей обобщает- ся основной результат статьи [1]. В этой работе была предложена формализация разбиений Делоне [2] средствами линейного программирования для случая принадлежности элемента выпуклой оболочке исходных точек и при условии телесности этой оболочки. В настоящей заметке показано, что эти ограничения можно снять, сохраняя экстремальные свойства разбиений Делоне в аффинной оболочке обучающего множества.

Обозначим через X = { a 1 ,...,a m } обучающее множество точек, часть которых, с индексом I ₁ , принадлежит множеству A , а остальные, с индексом I ₂ , множеству B . Требуется определить значение кусочно-линейной дискриминантной функции f ( x ) для распознаваемого элемента x _е R n из аффинной оболочки обучающего множества M = aff X , в предположении, что значения f j = f ( a^j ), j = 1,..., m на обучающем множестве известны. В рамках рассматриваемой задачи распознавания, пусть f j <  0 ( j е I 1 ) и fj >  0 ( j е 1 2 ), 1 1 и 1 2 = { 1,..., m } . По знаку f ( x ) будем судить о принадлежности элемент а x _е L одному из множеств, а ^ а или В ^ B , а именно, при f ( x ) <  0 отнесем элемент _{x е} Rⁿ к множеству а , а в случае противоположного знака будем считать, что x _е В .

В статье [1] James E. Falk предложил (по совету Christoph J. Witzgall и для несколько иных целей) оценивать значение f (x) при x е co X величиной ю

m

S аjfj, где j=1

вектор а = ( а 1 ,..., а_m ) T является базисным решением следующей линейной программы:

min t

mm

S ^а 11 a \ I : S a a

i j ^{= i}

j = 1

m

= x , S a j = 1, все a , >  0 >  (1)

j = 1

Если при этом m >  n и aff X = R " , то гиперсфера S ( a ), определяемая _n + 1 точками _a j ,..., _a j + i , соответствующими базисным компонентам α ˆ _j ,..., α ˆ _j вектора α ˆ , не содержит других точек _a ^j в своей внутренности [1, p.80].

Описанная выше конструкция привлека- тельна тем, что в ней процедуры получения симплициального разбиения со свойствами Делоне и последующего вычисления значения f (x) совмещены и выполняются одновременно. Кроме того, кусочнолинейная дискриминация этим способом позволяет допускать наличие общих точек a j во множествах A и B , в таких случаях можно положить f (aj) = 0.

В целях применения этой конструкции к задачам распознавания образов распространим ее в двух направлениях: во-первых, откажемся от ограничительного требования aff X = R" ; во-вторых, укажем способ применения конструкции в случае x t coX .

1. Рассмотрим случай aff X * R" , x е coX . Для этого сохраним общую канв у доказательства соответствующей Теоремы [1, p.80], дополняя ее необходимыми замечаниями.

Теорема 1 . Пусть размерность аффинной оболочки M = aff X равна r <  n и a j ,..., a j + ¹ - точки, соответствующие базисным компонентам α ^ˆ _j ,..., α ^ˆ _j базисного решения задачи (1) при _{x е co}X . Тогда гиперсфера с центром в M , проходящая через точки _a j ,..., _a j + 1 , определяется однозначно и не содержит других точек _a ^j в своей внутренности.

Доказательству теоремы предпошлем следующие очевидные (в разной степени) факты.

Лемма 1 . Пусть a ¹,..., a^k - произвольные точки из _R ⁿ . Тогда

,       ,               ( a ¹ )     ( a ^k )

dim a^{ff {} a ,..., a ^} + 1 = dim^{ ! ,..., ! ^} (2)

V ¹ 7 V ¹ У

Лемма 2 . Пусть точки a ¹,..., a^k находятся в общем положении. Тогда существует единственная гиперсфера с центром в аффинной оболочке этих точек, проходящая через эти точки, а ее центр c определяется системой линейных уравнений

2 c^T (a^J - a ¹) = || a ⁷ || - || a ¹1 ( j = 2,..., k ) (3)

с дополнительным требованием c е aff {a 1,...,ak}.

К ЗАДАЧЕ ПОСТРОЕНИЯ КУСОЧНО-ЛИНЕЙНОЙ ДИСКРИМИНАНТНОЙ ФУНКЦИИ

Плотников С.В.

Лемма 3 . Пусть задача линейного про-

граммирования T p X г ШП1

Ax = b x > 0

разрешима и ранг ее матрицы Anхm равен r . Если Bnхr - произвольная базисная матрица, соответствующая оптимальному базисному решению задачи (4), то найдется оптимальное решение у * двойственной к ней задачи bTу ^ max

A T У <  Р ,

для которого будет выполнено равенство

B T y = Р .

Доказательство теоремы 1 . Пусть a = ( а 1 ,..., а_m ) T является оптимальным базисным решением задачи (1). В силу соотношения (2) и условия dim M = r каждый базис, соответствующий этому базисному решению, содержит r + 1 вектор вида

' a j ²

' a j ^{+1 2}

V

¹ )

у

Следовательно, точки _a ^{j 1},..., a j ^{+ |} находятся в общем положении и гиперсфера с центром в M определяется однозначно (см. Лемму 2) соотношениями:

2 c^T ( a j - a^J 1 ) = || a^jk || -|| a^{j |}|| ( k = 2,..., r + 1),

такую же, как и в (5). Но элемент u e r" не обязан принадлежать M . Обозначим через uˆM ортогональную проекцию элемента uˆ на аффинную оболочку м. Тогда й = йM + йM1, причем йM1 (aj - aj1) = 0 (k = 2,...,r +1) . Поэтому получаем йM (aj - aj1) = ||ajk|| -||aj'|| (k = 2,..., r +1) , что означает йM = 2c. Таким образом, центр гиперсферы совпадает с точкой 12 uˆM .

Покажем, что для любой другой точки a e X , кроме a^{j 1} ,..., a j ⁺¹ , будет выполнено неравенство || c - a ||² > || c - a^{j 1}|| . Из соотношений (6) и (7) получаем й^T ( a - a^{j 1} ) < || a ||² - || a^{j 1}|| .

Так как й ^TM 1 ( a - aj) = 0 и й _M = 2 c , то 2 c T ( a - a^J'~) < || a ||² - || a^{j 1}|| .

Последнее неравенство эквивалентно соотношению || c - a ||² > || c - a^j '|| . Теорема доказана .

Рассмотрим следующий пример. Пусть a1 = (-1,0)T, a2 = (0,0)T, a3 = (1,0)T      и x = (0,0)T . Здесь dimaff {a1,a2,a3} = 1, а задачи 1 и 6 имеют вид

1 a ₁ + 0 a ₂ + 1 a ₃ ^ min

- 1 a + 0 a + 1 a = 0

L :               ^{1       2       3}

0 a ₁ + 0 a ₂ + 0 a ₃ = 0

a ₁ + a ₂ + a ₃ = 1

a >  0 a >  0 a ₃ >  0

123    и

c e aff { a^{j 1},..., a^{jr + |}} = M                     (5)

Рассмотрим двойственную к (1) задачу xTu ^ max uTaj + v < ||aj'|| (j = 1,...,m)              (6)

Согласно лемме 3, задача (6) имеет оптимальное базисное решение ( u ˆ, v ˆ) , удовлетворяющее равенствам

0 u ₁ + 0 u ₂ + v ^ max

L^ :      - 1 u 1 + 0 u 2 + v <  1

0 u ₁ + 0 u ₂ + v <  0

1 u ₁ + 0 u ₂ + v <  1

Оптимальным базисным решением задачи L является вектор (0,1, 0) ^T , которому соответствуют две разных базисных матрицы:

й ^Ta j + v = || a^j ||  ( k = 1,..., r + 1)       (7)

	'- 1 0 ^		' 0 1
B 1 =	0  0	и   B 2 =	0 0
	V 1    1 у		V 1 1

Из соотношений (7) получаем систему равенств йT (aj - aj) = ||ajk || -11aj|| (k = 2,..., r +1),

Для первой находим (в согласии с Леммой 3) решение двойственной задачи u ₃ = - 1, u ₂ = v = 0; для второй - решение u₁ = 1, u ₂ = v = 0.

Этим решениям соответствуют окружности радиуса 12 с центрами в точках c1 = (-12,0)T и c2 = (12,0)T .

При этом оптимальное множество двойственной задачи составляют векторы вида ( u 1 , u 2 ,0) T с условием - 1 <  u 1 <  1. В исходной статье [1] не отмечено, что равенства (7) будут справедливы только для особых (см. Лемму 3) решений двойственной задачи.

2. Рассмотрим случай x t co X . Покажем один из способов продолжения кусочнолинейной дискриминантной функции, описанной в предыдущем разделе, на область x t coX . Основой для такого подхода является метод точных штрафных функций, разработанный И.И.Ереминым [3].

Определим следующую кусочно-линейную программу с параметрами X j >  0 ( j = 1,..., m ), аппроксимирующую задачу (1):

впадения оптимальных множеств и оптимальных значений.

Доказательство . Разрешимость задачи (8) при x e aff X является следствием ограниченности снизу кусочно-линейной целевой функции на непустом допустимом множестве. При X j >  a^j ( j = 1,..., m ) имеем:

m       2 m              m                   2 m        2

£HHI ⁺ Е х ^(-aj^{) +} > E ^aj ^+(-aj ⁾⁺⁾| l ^aj || ⁼ E ^a +l ^aj ll > ⁰

j = 1                j = 1                    j = 1                                  j = 1

Вторая часть Теоремы проверяется прямым применением стандартной техники точных штрафных функций [3, с.120; 4, с.84]. Теорема доказана .

Важно отметить, что кусочно-линейная программа (8) при X j >  0 ( j = 1,..., m ) эквивалентна следующей задаче линейного программирования (в смысле совпадения оптимальных значений и соответствующих частей оптимальных значений переменных α ˆ ):

m

m

m

min

mm  m

E a V I + E X (a ^{) + :} E ^a X

i 1 = 1                  .j = 1

.i = 1

m

= x E a ¹ = 1 1 (8)

.i = 1

m   mm miniEalkll +E Xjtj; E

l j = 1

j = 1          j = 1

m aja = x, Eajj = j =1

Теорема 2 . Пусть x e aff X . Тогда задача (8) разрешима при любых X j > || a^j ||² ( j = 1,..., m ). Пусть x e coX и ( u ˆ, v ˆ) - какое-нибудь решение задачи (6). Тогда при любых X j > || a^j || - й T a j - v задачи (1) и (8) эквивалентны в смысле со-

= 1, a j + t j >  0, t j >  0 ( j = 1,..., m ) >

Таким образом, задача идентификации элемента x e aff X требует решения единственной задачи линейного программирования. Условие принадлежности распознаваемого элемента аффинной оболочке обучающего множества представляется обязательным с позиций корректности постановки задачи.