Минимизация эмпирического риска и задачи построения линейных классификаторов
Розглянуто задачі побудови лінійних класифікаторів для класифікації багатьох множин. У випадку лінійно роздільних множин наведені формулювання є узагальненням раніше відомих. Для лінійно нерозділимих множин природним критерієм вибору класифікатора є мінімізація емпіричного ризику. Розглядаються част...
Gespeichert in:
| Datum: | 2011 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84224 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Минимизация эмпирического риска и задачи построения линейных классификаторов / Ю.П. Лаптин, Ю.И. Журавлев, А.П. Виноградов // Кибернетика и системный анализ. — 2011. — Т. 47, № 4. — С. 155-164. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84224 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-842242025-02-09T09:43:53Z Минимизация эмпирического риска и задачи построения линейных классификаторов Мінімізація емпіричного ризику та задачі побудови лінійних класифікаторів Empirical risk minimization and problems of constructing linear classifiers Лаптин, Ю.П. Журавлев, Ю.И. Виноградов, А.П. Системный анализ Розглянуто задачі побудови лінійних класифікаторів для класифікації багатьох множин. У випадку лінійно роздільних множин наведені формулювання є узагальненням раніше відомих. Для лінійно нерозділимих множин природним критерієм вибору класифікатора є мінімізація емпіричного ризику. Розглядаються частково цілочисельне формулювання задачі мінімізації емпіричного ризику, можливості вирішення безперервної релаксації цієї задачі. Порівнюється запропонована безперервна релаксація з задачами, які вирішуються при використанні інших підходів для побудови лінійних кла-сифікаторів. Описано особливості використання методів негладкої оптимізації для вирішення сфор-мульованих задач. We consider constructing linear classifiers for the classification of many sets. In the case of linearly separable sets, the problem formulations are a generalization of already known ones. For linearly inseparable sets, a natural criterion for choosing a classifier is empirical risk minimization. The article deals with a mixed integer formulation of the empirical risk minimization problem and possible solutions of its continuous relaxation. We compare the proposed continuous relaxation problem with problems solved by using other approaches for constructing linear classifiers. We describe the features of nonsmooth optimization methods used to solve the formulated problems. Работа выполнена в рамках совместного проекта НАН Украины и Российского фонда фундаментальных исследований № 10-01-90419 «Оптимизационные подходы в задачах машинного обучения и анализа данных». 2011 Article Минимизация эмпирического риска и задачи построения линейных классификаторов / Ю.П. Лаптин, Ю.И. Журавлев, А.П. Виноградов // Кибернетика и системный анализ. — 2011. — Т. 47, № 4. — С. 155-164. — Бібліогр.: 15 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84224 519.8 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Лаптин, Ю.П. Журавлев, Ю.И. Виноградов, А.П. Минимизация эмпирического риска и задачи построения линейных классификаторов Кибернетика и системный анализ |
| description |
Розглянуто задачі побудови лінійних класифікаторів для класифікації багатьох множин. У випадку лінійно роздільних множин наведені формулювання є узагальненням раніше відомих. Для лінійно нерозділимих множин природним критерієм вибору класифікатора є мінімізація емпіричного ризику. Розглядаються частково цілочисельне формулювання задачі мінімізації емпіричного ризику, можливості вирішення безперервної релаксації цієї задачі. Порівнюється запропонована безперервна релаксація з задачами, які вирішуються при використанні інших підходів для побудови лінійних кла-сифікаторів. Описано особливості використання методів негладкої оптимізації для вирішення сфор-мульованих задач. |
| format |
Article |
| author |
Лаптин, Ю.П. Журавлев, Ю.И. Виноградов, А.П. |
| author_facet |
Лаптин, Ю.П. Журавлев, Ю.И. Виноградов, А.П. |
| author_sort |
Лаптин, Ю.П. |
| title |
Минимизация эмпирического риска и задачи построения линейных классификаторов |
| title_short |
Минимизация эмпирического риска и задачи построения линейных классификаторов |
| title_full |
Минимизация эмпирического риска и задачи построения линейных классификаторов |
| title_fullStr |
Минимизация эмпирического риска и задачи построения линейных классификаторов |
| title_full_unstemmed |
Минимизация эмпирического риска и задачи построения линейных классификаторов |
| title_sort |
минимизация эмпирического риска и задачи построения линейных классификаторов |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2011 |
| topic_facet |
Системный анализ |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84224 |
| citation_txt |
Минимизация эмпирического риска и задачи построения линейных классификаторов / Ю.П. Лаптин, Ю.И. Журавлев, А.П. Виноградов // Кибернетика и системный анализ. — 2011. — Т. 47, № 4. — С. 155-164. — Бібліогр.: 15 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT laptinûp minimizaciâémpiričeskogoriskaizadačipostroeniâlinejnyhklassifikatorov AT žuravlevûi minimizaciâémpiričeskogoriskaizadačipostroeniâlinejnyhklassifikatorov AT vinogradovap minimizaciâémpiričeskogoriskaizadačipostroeniâlinejnyhklassifikatorov AT laptinûp mínímízacíâempíričnogorizikutazadačípobudovilíníjnihklasifíkatorív AT žuravlevûi mínímízacíâempíričnogorizikutazadačípobudovilíníjnihklasifíkatorív AT vinogradovap mínímízacíâempíričnogorizikutazadačípobudovilíníjnihklasifíkatorív AT laptinûp empiricalriskminimizationandproblemsofconstructinglinearclassifiers AT žuravlevûi empiricalriskminimizationandproblemsofconstructinglinearclassifiers AT vinogradovap empiricalriskminimizationandproblemsofconstructinglinearclassifiers |
| first_indexed |
2025-11-25T11:49:06Z |
| last_indexed |
2025-11-25T11:49:06Z |
| _version_ |
1849762881242923008 |
| fulltext |
ÓÄÊ 519.8
Þ.Ï. ËÀÏÒÈÍ, Þ.È. ÆÓÐÀÂËÅÂ, À.Ï. ÂÈÍÎÃÐÀÄÎÂ
ÌÈÍÈÌÈÇÀÖÈß ÝÌÏÈÐÈ×ÅÑÊÎÃÎ ÐÈÑÊÀ È ÇÀÄÀ×È
ÏÎÑÒÐÎÅÍÈß ËÈÍÅÉÍÛÕ ÊËÀÑÑÈÔÈÊÀÒÎÐÎÂ1
Êëþ÷åâûå ñëîâà: ëèíåéíûå àëãîðèòìû êëàññèôèêàöèè, ëèíåéíàÿ ðàçäåëè-
ìîñòü ìíîæåñòâ, ýìïèðè÷åñêèé ðèñê, ìåòîä îïîðíûõ âåêòîðîâ, ìåòîäû
îïòèìèçàöèè.
ÂÂÅÄÅÍÈÅ
Ïðîáëåìàì ïîñòðîåíèÿ ëèíåéíûõ àëãîðèòìîâ êëàññèôèêàöèè (êëàññèôèêàòî-
ðîâ) ïîñâÿùåíî áîëüøîå êîëè÷åñòâî ðàáîò [1–5]. ×àñòî òàêèå ïðîáëåìû ðàñ-
ñìàòðèâàþòñÿ äëÿ êëàññèôèêàöèè äâóõ ìíîæåñòâ. Çàäà÷è ïîñòðîåíèÿ îïòè-
ìàëüíûõ ëèíåéíûõ êëàññèôèêàòîðîâ îáû÷íî ôîðìóëèðóþòñÿ äëÿ ëèíåéíî ðàç-
äåëèìûõ ìíîæåñòâ. Äëÿ ýòîãî ñëó÷àÿ òàêèå çàäà÷è ðåøàþòñÿ äîñòàòî÷íî
ýôôåêòèâíî. Ïîíÿòèå îïòèìàëüíîñòè äëÿ äâóõ ëèíåéíî ðàçäåëèìûõ ìíîæåñòâ
èìååò ïðîñòîé ãåîìåòðè÷åñêèé ñìûñë — îïòèìàëüíûé êëàññèôèêàòîð îïðåäå-
ëÿåò ïîëîñó ìàêñèìàëüíîé øèðèíû, ðàçäåëÿþùóþ ýòè ìíîæåñòâà.
Äëÿ ëèíåéíîé ðàçäåëèìîñòè äâóõ êîíå÷íûõ ìíîæåñòâ íåîáõîäèìî è äîñòà-
òî÷íî, ÷òîáû âûïóêëûå îáîëî÷êè ýòèõ ìíîæåñòâ íå ïåðåñåêàëèñü.  ñëó÷àå ìíî-
ãèõ ìíîæåñòâ ýòèõ óñëîâèé íåäîñòàòî÷íî.  [6–8] ôîðìóëèðóþòñÿ íåêîòîðûå
äîñòàòî÷íûå óñëîâèÿ ëèíåéíîé ðàçäåëèìîñòè ïðîèçâîëüíîãî ÷èñëà ìíîæåñòâ.
Áîëåå óãëóáëåííûé ãåîìåòðè÷åñêèé àíàëèç òàêèõ óñëîâèé ïðèâåäåí â [9].
 ñëó÷àå ëèíåéíî íåðàçäåëèìûõ ìíîæåñòâ åñòåñòâåííûì êðèòåðèåì âûáîðà
êëàññèôèêàòîðà ÿâëÿåòñÿ ìèíèìèçàöèÿ ýìïèðè÷åñêîãî ðèñêà.  íàñòîÿùåé
ñòàòüå ðàññìàòðèâàþòñÿ ÷àñòè÷íî öåëî÷èñëåííàÿ ôîðìóëèðîâêà çàäà÷è ìèíèìè-
çàöèè ýìïèðè÷åñêîãî ðèñêà, âîçìîæíîñòè ðåøåíèÿ íåïðåðûâíîé ðåëàêñàöèè
ýòîé çàäà÷è. Ïðîâîäèòñÿ ñðàâíåíèå ïðåäëîæåííîé íåïðåðûâíîé ðåëàêñàöèè ñ çà-
äà÷àìè, êîòîðûå ðåøàþòñÿ ïðè èñïîëüçîâàíèè äðóãèõ ïîäõîäîâ äëÿ ïîñòðîåíèÿ
ëèíåéíûõ êëàññèôèêàòîðîâ â ñëó÷àå ëèíåéíî íåðàçäåëèìûõ ìíîæåñòâ.
Îïèñûâàþòñÿ îñîáåííîñòè èñïîëüçîâàíèÿ ìåòîäîâ íåãëàäêîé îïòèìèçàöèè äëÿ
ðåøåíèÿ ñôîðìóëèðîâàííûõ çàäà÷.
1. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ïóñòü çàäàíà ñîâîêóïíîñòü ëèíåéíûõ ôóíêöèé f x W w x wi
i i i( , ) ( , ) ,� �
0
i m�1, ,� , ãäå x R n� — âåêòîð ïðèçíàêîâ, W w w Ri i i n� � �( , )
0
1 — âåêòîð ïà-
ðàìåòðîâ, i m�1, ,� .
Îáîçíà÷èì W W W m� ( , , )1
� , W R L m nL� � �, ( )1 . Áóäåì ðàññìàòðèâàòü
ëèíåéíûå àëãîðèòìû êëàññèôèêàöèè (ëèíåéíûå êëàññèôèêàòîðû) ñëåäóþùåãî
âèäà:
a x W f x W i m
i
i
i( , ) ( , ): , ,� �arg max{ }1 � , x R n� , W R L� . (1)
 [7] ðàññìàòðèâàëèñü òàêæå êëàññèôèêàòîðû, â êîòîðûõ f i — âûïóêëûå êó-
ñî÷íî-ëèíåéíûå ôóíêöèè.
Ñ÷èòàåòñÿ çàäàííîé ñîâîêóïíîñòü êîíå÷íûõ íåïåðåñåêàþùèõñÿ ìíîæåñòâ
� i i m, , ,�1 � . Áóäåì ãîâîðèòü, ÷òî êëàññèôèêàòîð a x W( , ) ïðàâèëüíî ðàçäåëÿåò
òî÷êè èç � i i m, , ,�1 � , åñëè a x W i( , ) � , äëÿ âñåõ x i mi� �� , , ,1 � .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4 155
1Ðàáîòà âûïîëíåíà â ðàìêàõ ñîâìåñòíîãî ïðîåêòà ÍÀÍ Óêðàèíû è Ðîññèéñêîãî ôîíäà
ôóíäàìåíòàëüíûõ èññëåäîâàíèé ¹ 10-01-90419 «Îïòèìèçàöèîííûå ïîäõîäû â çàäà÷àõ ìàøèí-
íîãî îáó÷åíèÿ è àíàëèçà äàííûõ».
© Þ.Ï. Ëàïòèí, Þ.È. Æóðàâëåâ, À.Ï. Âèíîãðàäîâ, 2011
Ìíîæåñòâà � i i m, , ,�1 � , íàçûâàþòñÿ ëèíåéíî ðàçäåëèìûìè, åñëè ñóùåñò-
âóåò ëèíåéíûé êëàññèôèêàòîð, ïðàâèëüíî ðàçäåëÿþùèé òî÷êè èç ýòèõ ìíîæåñòâ.
Èçâåñòíî, ÷òî äâà ìíîæåñòâà ëèíåéíî ðàçäåëèìû, åñëè âûïóêëûå îáîëî÷êè
ýòèõ ìíîæåñòâ íå ïåðåñåêàþòñÿ (ñì., íàïðèìåð, [2]).  ñëó÷àå m� 2 ýòîãî óñëîâèÿ
íåäîñòàòî÷íî.
Ðàññìîòðèì óñëîâèÿ ëèíåéíîé ðàçäåëèìîñòè ìíîæåñòâ äëÿ ïðîèçâîëüíîãî m.
Ëåììà 1 [7]. Ïóñòü êàæäîå ìíîæåñòâî � i ñîñòîèò èç îäíîé òî÷êè,
i m�1, ,� . Òîãäà ñóùåñòâóåò ëèíåéíûé êëàññèôèêàòîð a x W( , ) , ïðàâèëüíî ðàçäå-
ëÿþùèé òî÷êè èç � i i m, , ,�1 � (ìíîæåñòâà � i i m, , ,�1 � , ëèíåéíî ðàçäåëèìû).
Òåîðåìà 1 [7, 8]. Ïóñòü âîêðóã êàæäîãî ìíîæåñòâà � i ìîæåò áûòü ïîñòðîå-
íà ñôåðà S i , i m�1, ,� , òàê, ÷òî S S i ji j� �� , . Òîãäà ìíîæåñòâà
� i i m, , ,�1 � , ëèíåéíî ðàçäåëèìû.
Äîêàçàòåëüñòâî â [7] áîëåå ïðîñòîå è ïîëó÷åíî íåçàâèñèìî.
Òåîðåìà 2 [7]. Ïóñòü n C m
2
, äëÿ ëþáûõ äâóõ ìíîæåñòâ: � �i j i j, , , ñó-
ùåñòâóåò ãèïåðïëîñêîñòü, ðàçäåëÿþùàÿ ýòè ìíîæåñòâà è íå ïåðåñåêàþùàÿ âû-
ïóêëûå îáîëî÷êè îñòàëüíûõ ìíîæåñòâ. Òîãäà ìíîæåñòâà � i i m, , ,�1 � , ëèíåé-
íî ðàçäåëèìû.
Äðóãèå óñëîâèÿ ëèíåéíîé ðàçäåëèìîñòè ïðèâåäåíû â [9]. Ñëåäóåò îòìåòèòü, ÷òî
óñëîâèÿ ñôîðìóëèðîâàííûõ òåîðåì äîñòàòî÷íîñòè âåñüìà æåñòêèå. Ìîæíî ïðèâåñòè
ìíîãî ïðèìåðîâ, êîãäà ýòè óñëîâèÿ íå âûïîëíÿþòñÿ, íî, òåì íå ìåíåå, ñóùåñòâóåò ëè-
íåéíûé êëàññèôèêàòîð, ïðàâèëüíî ðàçäåëÿþùèé òî÷êè èç � i i m, , ,�1 � .
Êàæäîå ìíîæåñòâî � i i m, , ,�1 � , åñòü îáó÷àþùàÿ âûáîðêà òî÷åê èç íåêîòî-
ðîãî êëàññà � i , èçâåñòíîãî òîëüêî íà ýëåìåíòàõ âûáîðêè. Îáó÷åíèå êëàññèôè-
êàòîðà a x W( , ) çàêëþ÷àåòñÿ â ïîäáîðå çíà÷åíèé ïàðàìåòðîâ W, ïðè êîòîðîì êëàñ-
ñû � i i m, , ,�1 � , ðàçäåëÿþòñÿ «íàèëó÷øèì» îáðàçîì. Äëÿ îïðåäåëåíèÿ êà÷åñòâà
ðàçäåëåíèÿ ñóùåñòâóþò ðàçëè÷íûå ïîäõîäû.
Îáîçíà÷èì � ��
�
i
i
m
1
� . Ïóñòü òî÷êè ìíîæåñòâà � ïåðåíóìåðîâàíû, T — ñî-
âîêóïíîñòü èíäåêñîâ, � � �{ }x t Tt : , Ti — ñîâîêóïíîñòü èíäåêñîâ ìíîæåñòâà
� i , � i
t
ix t T� �{ }: , T Ti
i
m
�
�1
� . Ïîëîæèì i t( ) — íîìåð ìíîæåñòâà � i , êîòîðîìó
ïðèíàäëåæèò òî÷êà x t , t T� . Âåëè÷èíà
g W f x W f x W j m i i i tt
i
t i
j
t j( ) min ( , ) ( , ): , , \ , ( )� � � � �{ { } }1 �
� � � � � �min ( , ) : , , \ , ( ){ { } }w w x w w j m i i i ti j t i j
0 0
1 � (2)
íàçûâàåòñÿ îòñòóïîì (margin) èëè çàçîðîì (gap) êëàññèôèêàòîðà a x W( , ) íà
òî÷êå x t , t T� .
Êëàññèôèêàòîð a x W( , ) äîïóñêàåò îøèáêó íà òî÷êå x t òîãäà è òîëüêî òîãäà,
êîãäà çàçîð g Wt ( ) îòðèöàòåëåí. Âåëè÷èíà g W g W t Tt( ) min ( ) :� �{ } íàçûâàåòñÿ
çàçîðîì êëàññèôèêàòîðà a x W( , ) íà ñîâîêóïíîñòè ìíîæåñòâ � i i m, , ,�1 � . Êëàñ-
ñèôèêàòîð a x W( , ) ïðàâèëüíî ðàçäåëÿåò òî÷êè èç � i i m, , ,�1 � , åñëè g W( ) � 0.
Çàìå÷àíèå 1. Êëàññèôèêàòîð a x W( , ) èíâàðèàíòåí îòíîñèòåëüíî óìíîæåíèÿ
âñåõ ôóíêöèé f i (âåêòîðîâ W i ) íà ïîëîæèòåëüíîå ÷èñëî, çàçîð g W( ) ëèíååí îò-
íîñèòåëüíî òàêîé îïåðàöèè óìíîæåíèÿ. Êëàññèôèêàòîð a x W( , ) è îòñòóï g W( )
èíâàðèàíòíû îòíîñèòåëüíî äîáàâëåíèÿ ïðîèçâîëüíîãî ÷èñëà êî âñåì f i .
Âåëè÷èíó g W( ) ìîæíî èñïîëüçîâàòü êàê êðèòåðèé êà÷åñòâà êëàññèôèêàòîðà
a x W( , ) (÷åì áîëüøå çíà÷åíèå g W( ), òåì íàäeæíåå ðàçäåëÿþòñÿ òî÷êè èç
� i i m, , ,�1 � ), îäíàêî ïðè ýòîì äîëæíà ó÷èòûâàòüñÿ íåêîòîðàÿ íîðìèðîâêà ñî-
156 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4
âîêóïíîñòè âåêòîðîâ W, êîòîðóþ îáîçíà÷èì �( )W è íàçîâåì íîðìîé êëàññèôèêà-
òîðà a x W( , ) .
 äàëüíåéøåì áóäåì ïîëàãàòü
�( ) ( )W w j
i
j
n
i
m
�
��
�� 2
11
. (3)
 êà÷åñòâå íîðìû �( )W ìîãóò èñïîëüçîâàòüñÿ òàêæå äðóãèå ôóíêöèè [7].
Ïóñòü çàäàíà ñîâîêóïíîñòü ìíîæåñòâ � i i m, , ,�1 � . Ñ ó÷åòîì ââåäåííûõ îáî-
çíà÷åíèé çàäà÷ó ïîñòðîåíèÿ îïòèìàëüíîãî êëàññèôèêàòîðà (îïðåäåëåíèÿ çíà÷å-
íèé ïàðàìåòðîâ W) çàïèøåì â ñëåäóþùåì âèäå: íàéòè
g g W W W R
W
L* max ( ): ( ) ,�
�{ }� 1 . (4)
Ïîñêîëüêó âåêòîð W � 0 ÿâëÿåòñÿ äîïóñòèìûì, òî çàäà÷à (4) èìååò ðåøåíèå
âñåãäà è g g* ( )
�0 0. Çàìåòèì, ÷òî g * � 0, åñëè ìíîæåñòâà � i i m, , ,�1 � , ëè-
íåéíî ðàçäåëèìû, ò.å. ñóùåñòâóåò ëèíåéíûé êëàññèôèêàòîð, ïðàâèëüíî ðàçäåëÿ-
þùèé ýòè ìíîæåñòâà. Ðàññìîòðèì òàêæå çàäà÷ó: íàéòè
� �* min ( ): ( ) ,�
�
V
LV g V V R{ }1 . (5)
Áëèçêèå ïî ñìûñëó çàäà÷è ðàññìàòðèâàëèñü ðàçíûìè àâòîðàìè (ñì., íàïðèìåð, [5, 10]).
Ëåììà 2. Ïóñòü W * — îïòèìàëüíîå ðåøåíèå çàäà÷è (4). Òîãäà:
1) åñëè g * � 0, òî çàäà÷à (5) òàêæå èìååò îïòèìàëüíîå ðåøåíèå V * ,
V W g* * */� ; � * */� 1 g ;
2) åñëè g * � 0, òî çàäà÷à (5) íå èìååò äîïóñòèìûõ ðåøåíèé.
Äîêàçàòåëüñòâî ïðîñòîå è ïðèâåäåíî â [7].
Ðàññìîòðèì áîëåå ïîäðîáíî çàäà÷è ïîñòðîåíèÿ ëèíåéíûõ êëàññèôèêàòîðîâ
äëÿ çàäàííîé ñîâîêóïíîñòè ìíîæåñòâ � i
t
ix t T i m� � �{ }, , , ,1 � . Íåòðóäíî âè-
äåòü, ÷òî çàäà÷à (4) ìîæåò áûòü ïðåäñòàâëåíà â ôîðìå çàäà÷è ëèíåéíîãî ïðî-
ãðàììèðîâàíèÿ ñ äîïîëíèòåëüíûì êâàäðàòè÷íûì îãðàíè÷åíèåì: íàéòè
g z
w z
*
,
max� (6)
ïðè îãðàíè÷åíèÿõ
( , ) , , , \ , , , ,w w x w w z j m i t T i mi j t i j
i� � �
� � �
0 0
1 1{ }� � , (7)
( )w j
i
j
n
i
m
��
��
1
2
1
1 . (8)
Ñîîòâåòñòâåííî çàäà÷à (5) åñòü çàäà÷à êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ:
íàéòè
� �
�
* min ( )�
��
�� j
i
j
n
i
m
1
2
1
(9)
ïðè îãðàíè÷åíèÿõ
( , ) , , , \ , , , ,� � � �i j t i j
ix j m i t T i m� � �
� � �
0 0
1 1 1{ }� � . (10)
Çàìåòèì, ÷òî â ñëó÷àå m � 2 çàäà÷à (9),(10) ýêâèâàëåíòíà çàäà÷å, êîòîðàÿ èñ-
ïîëüçóåòñÿ äëÿ ïîñòðîåíèÿ ïîëîñû ìàêñèìàëüíîé øèðèíû, ðàçäåëÿþùåé ëèíåé-
íî ðàçäåëèìûå ìíîæåñòâà � �1 2, , è çàïèñûâàåòñÿ (ñì., íàïðèìåð, [3]) â ñëåäóþ-
ùåì âèäå: íàéòè çíà÷åíèÿ ïàðàìåòðîâ u R u Rn� �, 0 òàêèå, ÷òî
( , ) minu u � (11)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4 157
ïðè îãðàíè÷åíèÿõ
( , ) ,u x u t Tt �
�0 11 , (12)
( , ) ,u x u t Tt �
� �0 21 . (13)
Ïóñòü � � � �1
0
1 2
0
2, , , — îïòèìàëüíîå ðåøåíèå çàäà÷è (9), (10), u u* *, 0 —
îïòèìàëüíîå ðåøåíèå çàäà÷è (11)–(13). Òîãäà � � � � � �1 2 1 2
0 0
1
0
2� � � � � �, ,* *u u .
Äëÿ ðåøåíèÿ ðàññìîòðåííûõ çàäà÷ ìîæåò èñïîëüçîâàòüñÿ ñóùåñòâóþùåå ýô-
ôåêòèâíîå ïðîãðàììíîå îáåñïå÷åíèå çàäà÷ îïòèìèçàöèè îáùåãî íàçíà÷åíèÿ, åñëè
÷èñëî òî÷åê â îáó÷àþùåé âûáîðêå íåâåëèêî. Ðåçóëüòàòû òàêîãî ðîäà âû÷èñëèòåëü-
íûõ ýêñïåðèìåíòîâ ïðèâåäåíû â [7]. Ïðè áîëüøîì ÷èñëå òî÷åê â îáó÷àþùåé âûáîð-
êå öåëåñîîáðàçíî èñïîëüçîâàòü ìåòîäû íåãëàäêîé îïòèìèçàöèè [10, 13].
Çàäà÷è (6)–(8) è (9),(10) ïîçâîëÿþò íàõîäèòü îïòèìàëüíûé ëèíåéíûé êëàñ-
ñèôèêàòîð òîëüêî äëÿ ëèíåéíî ðàçäåëèìûõ ìíîæåñòâ. Äëÿ ëèíåéíî íåðàçäåëè-
ìûõ ìíîæåñòâ çàäà÷è äîëæíû ôîðìóëèðîâàòüñÿ èíà÷å.
Äëÿ ñëó÷àÿ äâóõ ìíîæåñòâ: � �1 2, , â ðÿäå ðàáîò (ñì., íàïðèìåð, [3, 11, 12])
ïðåäëàãàþòñÿ íåêîòîðûå ôîðìóëèðîâêè çàäà÷, ïîçâîëÿþùèå íàõîäèòü ëèíåéíûå
êëàññèôèêàòîðû â ñëó÷àå ëèíåéíî íåðàçäåëèìûõ ìíîæåñòâ.  äðóãèõ ðàáîòàõ
(ñì., íàïðèìåð, [5]) äëÿ ýòîãî ïðåäëàãàþòñÿ ñïåöèàëüíûå àëãîðèòìû. Íàèáîëåå
èçâåñòíûì â ýòîé ñâÿçè ÿâëÿåòñÿ ìåòîä îïîðíûõ âåêòîðîâ (ñì., íàïðèìåð, [3]).
2. ÌÈÍÈÌÈÇÀÖÈß ÝÌÏÈÐÈ×ÅÑÊÎÃÎ ÐÈÑÊÀ
 ñëó÷àå ëèíåéíî íåðàçäåëèìîé âûáîðêè åñòåñòâåííûì êðèòåðèåì âûáîðà
êëàññèôèêàòîðà ÿâëÿåòñÿ ìèíèìèçàöèÿ ýìïèðè÷åñêîãî ðèñêà, ò.å. ÷èñëà òî÷åê
îáó÷àþùåé âûáîðêè, êîòîðûå êëàññèôèêàòîð ðàçäåëÿåò íåïðàâèëüíî.
Áóäåì ñ÷èòàòü, ÷òî çàäàí íåêîòîðûé ïàðàìåòð �� 0 íàäåæíîñòè ðàçäåëåíèÿ òî-
÷åê îáó÷àþùåé âûáîðêè � i i m, , ,�1 � . Áóäåì ãîâîðèòü, ÷òî òî÷êè x t Tt , � , äëÿ êî-
òîðûõ âåëè÷èíà çàçîðà g Wt ( )� �, ðàçäåëÿþòñÿ êëàññèôèêàòîðîì a x W( , ) íåíàäåæíî.
 äàëüíåéøåì çíà÷åíèå ýìïèðè÷åñêîãî ðèñêà áóäåì îïðåäåëÿòü ñ ó÷åòîì
íàäåæíîñòè, îïðåäåëÿåìîé ïàðàìåòðîì � — ýìïèðè÷åñêèé ðèñê ðàâåí ÷èñëó òî-
÷åê îáó÷àþùåé âûáîðêè, êîòîðûå êëàññèôèêàòîð ðàçäåëÿåò íåïðàâèëüíî èëè
íåíàäåæíî.
Ëåììà 3. Ïóñòü x xi j
� �� �� �, , êëàññèôèêàòîð a x W( , ) ïðàâèëüíî ðàçäå-
ëÿåò ýòè òî÷êè, äëÿ íîðìû êëàññèôèêàòîðà âûïîëíÿåòñÿ îãðàíè÷åíèå (8). Òîãäà
�
�
R w w Ri j
0 0
, (14)
ãäå R x x i mi� � �2 1max | | | | : , , ,{ }� � .
Äîêàçàòåëüñòâî. Äëÿ òî÷åê x x� �, çàïèøåì íåðàâåíñòâà � �
( , )w w xi j �
�
� �w w w w xi j i j
0 0
( , )� . Ó÷èòûâàÿ (8), ìîæíî ïîêàçàòü, ÷òî �
2| | | |x �
�
w w xi j
0 0
2| | | |� . Îòñþäà ñëåäóåò óòâåðæäåíèå ëåììû.
Ïóñòü � i
t
ix t T� �{ }, , i m�1, ,� , T Ti
i
m
�
�1
� . Êàæäîé òî÷êå x t Tt , � , ïîñòà-
âèì â ñîîòâåòñòâèå ïåðåìåííóþ yt � �0 1 òàê, ÷òî yt � 0, åñëè òî÷êà x t ó÷èòûâà-
åòñÿ ïðè ôîðìèðîâàíèè çàäà÷è (6)–(8), yt �1 â ïðîòèâíîì ñëó÷àå.
Ïóñòü çàäàíî áîëüøîå ïîëîæèòåëüíîå ÷èñëî B. Çàäà÷à ìèíèìèçàöèè ýìïè-
ðè÷åñêîãî ðèñêà ñ ó÷åòîì íàäåæíîñòè, îïðåäåëÿåìîé ïàðàìåòðîì �, èìååò âèä:
íàéòè
Q y
w y
t
t T
*
,
min�
�
�{ } (15)
158 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4
ïðè îãðàíè÷åíèÿõ
( , ) , , , \ , , , ,w w x w w B y j m i t T i mi j t i j
t i� � �
� � � � �
0 0
1 1� { }� � , (16)
�( )W
1, (17)
y T i mt
t T
i
i�
�
� �| | , , ,1 1 � , (18)
0 1
�y t Tt , , (19)
y t Tt � � �0 1, . (20)
Èç îãðàíè÷åíèé (14), (17) ñëåäóåò, ÷òî åñëè yt �1, òî ïðè äîñòàòî÷íî áîëü-
øîì çíà÷åíèè ÷èñëà B ñîîòâåòñòâóþùèå íåðàâåíñòâà âèäà (16) âûïîëíÿþòñÿ
âñåãäà, ò.å. òî÷êà x t èñêëþ÷àåòñÿ èç çàäà÷è. Îãðàíè÷åíèÿ (18) îïðåäåëÿþò óñëî-
âèå òîãî, ÷òî, ïî êðàéíåé ìåðå, îäíà òî÷êà èç êàæäîãî ìíîæåñòâà � i äîëæíà
áûòü âêëþ÷åíà â çàäà÷ó.
Îïòèìàëüíîå çíà÷åíèå Q * ðàâíî ìèíèìàëüíîìó ýìïèðè÷åñêîìó ðèñêó ñ
ó÷åòîì íàäåæíîñòè �. Ïðè ôîðìóëèðîâêå çàäà÷è ìèíèìèçàöèè ýìïèðè÷åñêîãî
ðèñêà ìîãóò ó÷èòûâàòüñÿ äîïîëíèòåëüíûå óñëîâèÿ è èíôîðìàöèÿ:
• öåíà îøèáêè íà ðàçíûõ òî÷êàõ ìîæåò áûòü ðàçíîé, ò.å. öåëåâîé ôóíêöèåé
ìîæåò áûòü âçâåøåííàÿ ñóììà îøèáîê,
• íà äîïóñòèìóþ îáëàñòü çíà÷åíèé âåêòîðîâ W ìîãóò íàêëàäûâàòüñÿ äîïîë-
íèòåëüíûå îãðàíè÷åíèÿ.
Çàäà÷à (15)–(20) ÿâëÿåòñÿ NP-òðóäíîé, åå ïðèáëèæåííûå ðåøåíèÿ ìîãóò
áûòü íàéäåíû â ðàìêàõ îáùåé ñõåìû ìåòîäà âåòâåé è ãðàíèö. Äëÿ âû÷èñëåíèÿ
îöåíêè ñíèçó äëÿ âåëè÷èíû Q * (ìèíèìàëüíîãî ýìïèðè÷åñêîãî ðèñêà) ðàññìîò-
ðèì íåïðåðûâíóþ ðåëàêñàöèþ ñôîðìóëèðîâàííîé çàäà÷è — çàäà÷ó (15)–(19)
Îïòèìàëüíîå çíà÷åíèå ðåëàêñèðîâàííîé çàäà÷è îáîçíà÷èì q * . Äëÿ åå ðåøåíèÿ
èñïîëüçóåì ñõåìó äåêîìïîçèöèè ïî ïåðåìåííûì W. Ïóñòü ïåðåìåííûå W çàôèê-
ñèðîâàíû. Ó÷èòûâàÿ (2), çàäà÷ó ìèíèìèçàöèè ïî ïåðåìåííûì y ïðåäñòàâèì â
ñëåäóþùåì âèäå: íàéòè
q W y
y
t
t T
( ) min�
�
�
�
�
�
��
� (21)
ïðè îãðàíè÷åíèÿõ
y
B
g W t Tt
t
� �
1
( ( )),� , (22)
�( )W
1 , (23)
y T i mt
t T
i
i�
�
� �| | , , ,1 1 � , (24)
0 1
�y t Tt , . (25)
Îáîçíà÷èì d W
B
g Wt t( ) max , ( ( ))� �
�
�
�
�
�
�0
1
� . Î÷åâèäíî, ÷òî åñëè çàäà÷à
(21)–(25) èìååò ðåøåíèå y* , òî y d Wt
t* ( )� . Îòñþäà ïîëó÷àåì çàäà÷ó ìèíèìèçà-
öèè ïî ïåðåìåííûì W: íàéòè
q d Wt
t T
* min ( )�
�
� (26)
ïðè îãðàíè÷åíèÿõ
�( )W
1 , (27)
d W T i mt
i
t Ti
( ) | | , , ,
� �
�
� 1 1 � , (28)
d W t Tt ( ) ,
�1 . (29)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4 159
Ôóíêöèè d Wt ( ) âûïóêëûå êóñî÷íî-ëèíåéíûå, �( )W — êâàäðàòè÷íàÿ ïîëî-
æèòåëüíî îïðåäåëåííàÿ. Äëÿ ðåøåíèÿ çàäà÷è (26)–(29) öåëåñîîáðàçíî ïðèìåíÿòü
ýôôåêòèâíûå ìåòîäû íåãëàäêîé îïòèìèçàöèè [13]. Îñîáåííîñòè òàêîãî
ïðèìåíåíèÿ ðàññìàòðèâàþòñÿ â ðàçä. 4.
3. ÑÐÀÂÍÈÒÅËÜÍÛÉ ÀÍÀËÈÇ
Ïðåäëîæåííûé âûøå ïîäõîä ñðàâíèâàåòñÿ ñ ìåòîäîì îïîðíûõ âåêòîðîâ
(ñì., íàïðèìåð, [3]) è ìåòîäîì ðîáàñòíîãî ðàçäåëåíèÿ [10–12] äëÿ ñëó÷àÿ äâóõ
ëèíåéíî íåðàçäåëèìûõ ìíîæåñòâ. Ïóñòü, êàê è ðàíåå, � i
t
ix t T� �{ }, , i �1 2, ,
T T T� �1 2 .
 ìåòîäå îïîðíûõ âåêòîðîâ ðåøàåòñÿ çàäà÷à, êîòîðàÿ ìîæåò áûòü ïðåäñòàâ-
ëåíà â ñëåäóþùåì âèäå: íàéòè
min ( , )
, ,u u
t
t T
u u C
0
1
2�
��
�
!
"
#
$
�
� (30)
ïðè îãðàíè÷åíèÿõ
( , ) ,u x u t Tt t�
� �0 11 � , (31)
( , ) ,� �
� �u x u t Tt t
0 21 � , (32)
� t t T
�0, , (33)
ãäå u R u Rn� �, 0 , � t R t T� �, .
Ïðè ðîáàñòíîì ðàçäåëåíèè äâóõ ìíîæåñòâ [10–12] ïîñòðîåíèå êëàññèôèêà-
òîðà âûïîëíÿåòñÿ â äâà ýòàïà. Íà ïåðâîì ðåøàåòñÿ çàäà÷à: íàéòè
min
| | | |, ,u u
t
t T
t
t TT T0
1 2
1 1
1 2�
� �
� �
� ��
�
�
%
�%
�
�
%
�%
(34)
ïðè îãðàíè÷åíèÿõ (31)–(33). Íà âòîðîì ýòàïå ïðè ôèêñèðîâàííûõ çíà÷åíèÿõ
âåêòîðà u óòî÷íÿåòñÿ çíà÷åíèå ïàðàìåòðà u0 .
Äëÿ ñðàâíåíèÿ ðàçëè÷íûõ ïîäõîäîâ ïðåäñòàâèì àíàëîã çàäà÷è (15)–(20) äëÿ
ñëó÷àÿ äâóõ ìíîæåñòâ â ñëåäóþùåì âèäå:
Q y
w w y
t
t T
*
, ,
min�
�
�
�
�
�
��
�
0
(35)
ïðè îãðàíè÷åíèÿõ
( , ) ,w x w B y t Tt
t�
� � �0 1� , (36)
( , ) ,� �
� � �w x w B y t Tt
t0 2� , (37)
( , )w w
1, (38)
y T it
t T
i
i�
�
� �| | , ,1 12 , (39)
0 1
�y t Tt , , (40)
y t Tt � � �0 1, . (41)
160 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4
Ñäåëàåì çàìåíó ïåðåìåííûõ â çàäà÷å (35)–(41): w u w u� �� �, 0 0 ,
�
�
t tBy
t T T� � �, 1 2 . Òîãäà íåïðåðûâíàÿ ðåëàêñàöèÿ ýòîé çàäà÷è ïðèìåò âèä
q
B u u
t
t T
*
, ,
min� �
�
�
�
�
�
��
�
�
�
�0
(42)
ïðè îãðàíè÷åíèÿõ
( , ) ,u x u t Tt t�
� �0 11 � , (43)
( , ) ,� �
� �u x u t Tt t
0 21 � , (44)
( , ) /u u
1 2� , (45)
� t t T
�0, , (46)
�
�
t B
t T
�, , (47)
�
�
t
t T
i
i
B
T i
�
�
� �(| | ), ,1 1 2. (48)
Îáîçíà÷èì � , , ,i i �1 2 , äâîéñòâåííûå ïåðåìåííûå äëÿ îãðàíè÷åíèé
(45), (48) è ðàññìîòðèì ôóíêöèþ Ëàãðàíæà
L u
B
u u
B
Tt
t T
i
t
t T
i
i
( , , , ) (( , ) / ) (|� �
�
� � � �
�
� � � � �
� �
� �1 2 | )�
�
�
�
�
�
�
�
�
�
� 1
1
2
i
.
Ïîëîæèì
� � �
�
( , ) min ( , , , )
, ,
�
u u
L u
0
(49)
ïðè îãðàíè÷åíèÿõ (43), (44), (46), (47).
Ïóñòü çàäàí øòðàôíîé êîýôôèöèåíò C â çàäà÷å (30)–(33). Íåòðóäíî âèäåòü,
÷òî, ïîëàãàÿ � 0 è âûáèðàÿ � èç óñëîâèÿ
�
�2 B
C� , ïîëó÷àåì
L u u u C t
t T
( , , , ) ( , )� � � �
�
�
� �
�
�
�
�
�
�
�
�
�2
1
2 2
,
ò.å. çàäà÷à (49), (43), (44), (46) ýêâèâàëåíòíà çàäà÷å (30)–(33) ïðè óêàçàííîì
âûáîðå çíà÷åíèé äâîéñòâåííûõ ïåðåìåííûõ.
Ïîëàãàÿ � � 0, ïîëó÷àåì L u
B
i
t
t Ti i
( , , , )� �
�
�� �
�
�
�
�
�
�
�
�
�
�
%
�%
�
�
%
�%
�
��
��
1
2
�
i i
i
B
T(| | )��
�
�
�
�
�
�
� 1
1
2
.
Îòêóäà ñëåäóåò, ÷òî, ïîäáèðàÿ ñîîòâåòñòâóþùèì îáðàçîì çíà÷åíèÿ , ïîëó÷àåì
çàäà÷ó (49), (43), (44), (46), ýêâèâàëåíòíóþ çàäà÷å, êîòîðàÿ ðåøàåòñÿ ïðè ðîáàñò-
íîì ðàçäåëåíèè äâóõ ìíîæåñòâ.
Òàêèì îáðàçîì, çàäà÷è, êîòîðûå ðåøàþòñÿ â ìåòîäå îïîðíûõ âåêòîðîâ è ïðè
ðîáàñòíîì ðàçäåëåíèè äâóõ ìíîæåñòâ, ÿâëÿþòñÿ ÷àñòíûì ñëó÷àåì çàäà÷è (49),
(43), (44), (46).
4. ÀËÃÎÐÈÒÌÛ ÐÅØÅÍÈß ÐÅËÀÊÑÈÐÎÂÀÍÍÎÉ ÇÀÄÀ×È
Çàäà÷à (26)–(29) âû÷èñëåíèÿ íèæíåé îöåíêè ìèíèìàëüíîãî ýìïèðè÷åñêîãî
ðèñêà ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì çàäà÷è âûïóêëîãî ïðîãðàììèðîâàíèÿ
f f x* min ( )� (50)
ïðè îãðàíè÷åíèÿõ
f x i mi ( ) , , ,
�0 1 � , (51)
ãäå x R n� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4 161
Äëÿ ðåøåíèÿ òàêèõ çàäà÷ â íàñòîÿùåå âðåìÿ èçâåñòíû ðàçëè÷íûå àëãîðèò-
ìû [13]. Îäíèì èç ïîäõîäîâ ÿâëÿåòñÿ ìåòîä íåãëàäêèõ øòðàôíûõ ôóíêöèé, â êî-
òîðîì çàäà÷à (50), (51) ñâîäèòñÿ ê ýêâèâàëåíòíîé çàäà÷å áåçóñëîâíîé âûïóêëîé
îïòèìèçàöèè ñ öåëåâîé ôóíêöèåé, èìåþùåé âèä f x h x( ) ( )� �� , ãäå �
0,
h x h x� �( ) max( , ( ))0 , h x f x i mi( ) max{ ( ), , , }� �1 � .
Èçâåñòíî (ñì., íàïðèìåð, [13]), ÷òî åñëè äëÿ çàäà÷è (50), (51) âûïîëíÿåòñÿ
óñëîâèå Ñëåéòåðà, òî ïðè äîñòàòî÷íî áîëüøîì çíà÷åíèè êîýôôèöèåíòà � ðåøå-
íèå çàäà÷è
f f x h x
x
* min ( ) ( )� � �{ }� (52)
ñîâïàäàåò ñ ðåøåíèåì çàäà÷è (50), (51). Äëÿ ïîèñêà ðåøåíèÿ çàäà÷è (52) ìî-
ãóò ïðèìåíÿòüñÿ ýôôåêòèâíûå ìåòîäû íåãëàäêîé îïòèìèçàöèè [13]. Ïðè òàêîì
ïîäõîäå òðåáóåòñÿ îïðåäåëåííûì îáðàçîì ïîäáèðàòü êîýôôèöèåíò �.
Ðàññìîòðèì äðóãîé ïîäõîä [14, 15] ê ñâåäåíèþ çàäà÷ (50), (51) ñ îãðàíè÷å-
íèÿìè ê çàäà÷àì áåçóñëîâíîé îïòèìèçàöèè. Îáîçíà÷èì S x R h xn� �
{ }: ( ) 0 .
Ïðåäïîëîæèì, ÷òî S — çàìêíóòîå âûïóêëîå ìíîæåñòâî, çàäàíà äîïóñòèìàÿ òî÷-
êà x S0 � òàêàÿ, ÷òî h x( )0 0� . Äëÿ x S& îáîçíà÷èì � S x( ) òî÷êó ïåðåñå÷åíèÿ îò-
ðåçêà [ , ]x x0 ñ ãðàíèöåé ìíîæåñòâà S . Îäíîìåðíûé ïîèñê äëÿ îïðåäåëåíèÿ � S x( )
ìîæåò áûòü ðåàëèçîâàí äîñòàòî÷íî ýôôåêòèâíî.
Ïóñòü çàäàíî íåêîòîðîå ÷èñëî E E f x, ( )� 0 , êîòîðîå áóäåì íàçûâàòü ïàðà-
ìåòðîì ïðîäîëæåíèÿ öåëåâîé ôóíêöèè. Ïîëîæèì
� �
�
E
S
S
x E f x E
x x
x x
( ) ( ( ( )) )
| | | |
| | ( ) | |
� � �
�
�
0
0
,
(53)
�
E
E
x
f x x S
x x S
( )
( ), ,
( ), .
�
�
&
�
�
�
åñëè
åñëè
(54)
Ðàññìîòðèì çàäà÷ó
* inf ( ):E E nx x R� �{ }. (55)
Èìåþò ìåñòî ñëåäóþùèå óòâåðæäåíèÿ.
Ëåììà 4 [15]. Ïóñòü E f
* , òîãäà
* *E f� è ðåøåíèÿ çàäà÷ (55) è (50),
(51) ñîâïàäàþò.
Òåîðåìà 3 [15]. Ïóñòü f h, — âûïóêëûå ôóíêöèè, ïðèíèìàþùèå êîíå÷íûå
çíà÷åíèÿ ïðè ëþáûõ x R n� . Òîãäà ñóùåñòâóåò êîíå÷íîå E * è äëÿ âñåõ E E� *
ôóíêöèÿ
E x( ) âûïóêëàÿ.
 ðàáîòå [15] òàêæå ïðèâîäÿòñÿ ñîîòíîøåíèÿ, ïîçâîëÿþùèå âû÷èñëÿòü ñóá-
ãðàäèåíò ôóíêöèè �E x( ) â ïðîèçâîëüíîé òî÷êå x S& .
Åñëè âåëè÷èíà E óäîâëåòâîðÿåò óñëîâèÿì E f
* è E E� * , òî äëÿ ðåøåíèÿ
çàäà÷è (55) ìîæåò ïðèìåíÿòüñÿ ëþáîé ñõîäÿùèéñÿ àëãîðèòì ìèíèìèçàöèè
âûïóêëûõ ôóíêöèé.
Ïðè íåèçâåñòíûõ f * è E * çíà÷åíèå E äîëæíî óòî÷íÿòüñÿ èòåðàòèâíî ïî
õîäó ðàáîòû àëãîðèòìà ìèíèìèçàöèè. Â [15] ïðèâåäåíû ïðîñòûå óñëîâèÿ, êîòî-
ðûå äîëæíû ïðîâåðÿòüñÿ íà êàæäîé èòåðàöèè. Óòî÷íåíèå çíà÷åíèÿ E ïðîâîäèò-
ñÿ, åñëè íà òåêóùåé èòåðàöèè ýòè óñëîâèÿ íå âûïîëíÿþòñÿ. Ïðè ýòîì åñëè óòî÷-
íåíèå (óìåíüøåíèå) çíà÷åíèÿ E ïðîâîäèòñÿ íà âåëè÷èíó ' '
� 0, ãäå ' — çà-
äàííûé ïàðàìåòð, òî òàêèå óòî÷íåíèÿ â ïðîöåññå ðàáîòû àëãîðèòìà áóäóò
ïðîâîäèòüñÿ êîíå÷íîå ÷èñëî ðàç. Ïîñëå ÷åãî àëãîðèòì ñõîäèòñÿ ê ðåøåíèþ
çàäà÷è (50)–(51).
Ðåçóëüòàòû âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ [15] ïîêàçàëè ýôôåêòèâíîñòü
ìåòîäà âûïóêëûõ ïðîäîëæåíèé. Ïðè ýòîì, îäíàêî, êàæäîå îáðàùåíèå ê ôóíêöèè
162 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4
E x( ) òðåáóåò âûïîëíåíèÿ äîñòàòî÷íî òðóäîåìêîé (ïî ñðàâíåíèþ ñ âû÷èñëåíè-
åì çíà÷åíèé ôóíêöèé f è h) ïðîöåäóðû îäíîìåðíîãî ïîèñêà.
Äëÿ çàäà÷è (26)–(29) ñ ó÷åòîì åå ñïåöèôèêè ïðîöåäóðà îäíîìåðíîãî ïîèñêà
òî÷êè íà ãðàíèöå äîïóñòèìîãî ìíîæåñòâà ìîæåò áûòü ðåàëèçîâàíà ñóùåñòâåííî
ýôôåêòèâíåå îáû÷íîé ïðîöåäóðû äèõîòîìèè.
Ïðåäñòàâèì âåêòîð â âèäå W W p� �0 �, ãäå W 0 — çàäàííàÿ äîïóñòèìàÿ òî÷-
êà, p — íàïðàâëåíèå ïîèñêà, è ïîäñòàâèì âûðàæåíèå äëÿ W â (27)–(29). Çíà÷åíèå �,
ïðè êîòîðîì (27) ïðåâðàùàåòñÿ â ðàâåíñòâî, íàõîäèòñÿ êàê ðåøåíèå êâàäðàòíîãî
óðàâíåíèÿ. Ðàññìîòðèì ïðîöåäóðó îïðåäåëåíèÿ çíà÷åíèÿ �, ïðè êîòîðîì òî÷êà
W W p� �0 � ëåæèò íà ãðàíèöå ìíîæåñòâà, îïèñûâàåìîãî íåðàâåíñòâàìè (28), (29).
Ïðåäñòàâèì ïîñëåäíèå â âèäå
f f m Mm
km
k Km
( ) ( ) ,� �(
�
�
� 0 , (56)
ãäå � �R, f km ( )� — âûïóêëûå êóñî÷íî-ëèíåéíûå ôóíêöèè,
f a b l Lkm
l l
km( ) max{ : }� �� � � . (57)
Çàìåòèì, ÷òî ñêàëÿðíûå ïðîèçâåäåíèÿ äëÿ îïðåäåëåíèÿ êîýôôèöèåíòîâ êàæ-
äîé ëèíåéíîé ôóíêöèè a bl l� � âû÷èñëÿþòñÿ òîëüêî îäèí ðàç.
Áóäåì ñ÷èòàòü, ÷òî L Lkm k m� ��) ) , åñëè km k m ) ). Äëÿ êàæäîé ôóíêöèè
f km ( )� ðàçîáüåì èíòåðâàë ( , )�* * íà îòðåçêè ( , )� �l l òàê, ÷òî ïðè � � ��( , )l l ìàê-
ñèìóì â (57) äîñòèãàåòñÿ íà ëèíåéíîé ôóíêöèè a bl l� � , l Lkm� . Äëÿ ýòîãî äîñ-
òàòî÷íî óïîðÿäî÷èòü ýëåìåíòû ìíîæåñòâà Lkm ïî âîçðàñòàíèþ êîýôôèöèåíòîâ
a l (òðóäîåìêîñòü O L Lkm km(| | log | | )� 2 ) è âû÷èñëèòü çíà÷åíèÿ � �l l, (òðóäîåì-
êîñòü O Lkm(| | )).
Îáîçíà÷èì L L k K m Mkm m� � � �{ }: , , T { }� �� l l L, , T { }� ��l l L, . Óïîðÿ-
äî÷èì ìíîæåñòâà T T, ïî âîçðàñòàíèþ ýëåìåíòîâ (òðóäîåìêîñòü O L L(| | log | | )� 2 ).
Äëÿ ïîèñêà ãðàíè÷íîé òî÷êè � èñïîëüçóåì èòåðàòèâíóþ ïðîöåäóðó, íà êàæ-
äîì øàãå n êîòîðîé
1) âûáèðàåòñÿ (ïðàâèëî âûáîðà îáúÿñíÿåòñÿ íèæå) òî÷êà �n ;
2) óòî÷íÿþòñÿ ìíîæåñòâà M è Lkm :
• åñëè max ( ):{ }f m Mm
n� � � 0, ò.å. � �� n , òî èç ìíîæåñòâà Lkm èñêëþ÷à-
þòñÿ âñå ýëåìåíòû l òàêèå, ÷òî � �� n ;
• åñëè max ( ):{ }f m Mm
n� � � 0, ò.å. � �� n , òî èç ìíîæåñòâà M èñêëþ÷àþò-
ñÿ âñå ýëåìåíòû m òàêèå, ÷òî f m
n( )� � 0, èç ìíîæåñòâà Lkm èñêëþ÷àþòñÿ
âñå ýëåìåíòû l òàêèå, ÷òî � �l n� ;
3) åñëè êàæäîå ìíîæåñòâî Lkm ñîñòîèò èç îäíîãî ýëåìåíòà, òî çàäà÷à ñâåäå-
íà ê ñèñòåìå ëèíåéíûõ íåðàâåíñòâ, òî÷êà � íàõîäèòñÿ ïðîñòî, ïðîöåäóðà çàâåð-
øàåòñÿ; â ïðîòèâíîì ñëó÷àå âûïîëíÿåòñÿ ïåðåõîä íà ï. 1).
Âûáîð òî÷êè �n âûïîëíÿåòñÿ èç óñëîâèÿ | : , |{ }� � �l l n l L� � � | : ,{� � �l l n�
l L� }| . Òðóäîåìêîñòü ïðåäëîæåííîé ïðîöåäóðû èìååò ïîðÿäîê O L L(| | log | | )� 2 .
ÇÀÊËÞ×ÅÍÈÅ
 ðàáîòå ðàññìîòðåíû çàäà÷è ïîñòðîåíèÿ ëèíåéíûõ êëàññèôèêàòîðîâ äëÿ ñëó-
÷àÿ ìíîãèõ êëàññîâ. Äëÿ ëèíåéíî íåðàçäåëèìûõ ìíîæåñòâ ñôîðìóëèðîâàíà
÷àñòè÷íî öåëî÷èñëåííàÿ çàäà÷à ìèíèìèçàöèè ýìïèðè÷åñêîãî ðèñêà. Ïîêàçàíî,
÷òî íåïðåðûâíàÿ ðåëàêñàöèÿ ñôîðìóëèðîâàííîé çàäà÷è îáîáùàåò èçâåñòíûå
ïîäõîäû ê ïîñòðîåíèþ ëèíåéíûõ êëàññèôèêàòîðîâ äëÿ ëèíåéíî íåðàçäåëèìûõ
ìíîæåñòâ. Ðàññìîòðåíû âîïðîñû èñïîëüçîâàíèÿ ìåòîäîâ íåãëàäêîé îïòèìèçà-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4 163
öèè äëÿ ðåøåíèÿ çàäà÷è âû÷èñëåíèÿ íèæíåé îöåíêè ìèíèìàëüíîãî ýìïèðè-
÷åñêîãî ðèñêà. Ïîêàçàíî, ÷òî ñïåöèôèêà çàäà÷è ïîçâîëÿåò ïîâûñèòü ýôôåêòèâ-
íîñòü ìåòîäîâ, èñïîëüçóåìûõ äëÿ ðåøåíèÿ âûïóêëûõ çàäà÷ îïòèìèçàöèè ñ
îãðàíè÷åíèÿìè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Z h u r a v l e v Y u . I . An algebraic approach to recognition or classification problems // Pattern
Recognition and Image Analysis. — 1998. — 8, N 1. — P. 59–100.
2. Ì å ñ ò å ö ê è é Ë . Ì . Ìàòåìàòè÷åñêèå ìåòîäû ðàñïîçíàâàíèÿ îáðàçîâ. — http://www.intuit.ru/
department/graphics/imageproc/.
3.  î ð î í ö î â Ê .  . Ìàøèííîå îáó÷åíèå. — http://www.machinelearning.ru/wiki/images/6/68/
voron-ML-Lin.pdf.
4. Ã ó ï à ë À . Ì . , Ñ å ð ã è å í ê î È . Â . Îïòèìàëüíûå ïðîöåäóðû ðàñïîçíàâàíèÿ. — Êèåâ:
Íàóê. äóìêà, 2008. — 232 ñ.
5. Ø ë å ç è í ã å ð Ì . , à ë à â à ÷  . Äåñÿòü ëåêöèé ïî ñòàòèñòè÷åñêîìó è ñòðóêòóðíîìó
ðàñïîçíàâàíèþ. — Êèåâ: Íàóê. äóìêà, 2004. — 545 ñ.
6. L a p t i n Y u . , V i n o g r a d o v A . Exact discriminant function design using some optimization
techniques // Classification, Forecasting, Data Mining International. Book Series “INFORMATION
SCIENCE & COMPUTING”, N 8, Sofia (Bulgaria), 2009. — P. 14–19.
7. L a p t i n Y u . P . , L i k h o v i d A . P . , a n d V i n o g r a d o v A . P . Approaches to construction
of linear classifiers in the case of many classes // Pattern Recognition and Image Analysis. — 2010.
— 20, N 2. — P. 137–145.
8. Ï å ò ó í è í Þ . È , Ø ó ë ü ä å ø î â Ã . À . Ïðîáëåìû ðàñïîçíàâàíèÿ îáðàçîâ ñ ïîìîùüþ
ëèíåéíûõ äèñêðèìèíàíòíûõ ôóíêöèé Ôèøåðà // Êèáåðíåòèêà. — 1979. — ¹ 6. —
C. 134–137.
9. Ð ó á ë å â Á .  . , Ï å ò ó í è í Þ . È . , Ë è ò â è í ê î Ï . à . Ñòðóêòóðà ãîìîòåòè÷íûõ ëèíåéíî
ðàçäåëèìûõ ìíîæåñòâ â n-ìåðíîì åâêëèäîâîì ïðîñòðàíñòâå. ×. 1, 2 // Êèáåðíåòèêà è
ñèñòåìíûé àíàëèç. ×. 1. — 1992. — ¹ 1. — C. 3–15; ×. 2. — 1992. — ¹ 2. — C. 23–33.
10. Ì å ò î ä è íåãëàäêî¿ îïòèì³çàö³¿ ó ñïåö³àëüíèõ çàäà÷àõ êëàñèô³êàö³¿ / Ï.². Ñòåöþê, Î.À. Áåðå-
çîâñüêèé, Ì.Ã. Æóðáåíêî, Ä.Î. Êðîïîòîâ. — Êè¿â, 2009. — 28 ñ. — (Ïðåïð. / ÍÀÍ Óêðà¿íè.
²í-ò ê³áåðíåòèêè ³ì. Â.Ì. Ãëóøêîâà; 2009–1).
11. B e n n e t t K . P . , M a n g a s a r i a n O . L . Robust linear programming discrimination of two
linearly inseparable sets // Optimiz. Methods and Software. — 1992. — N 5. — P. 23–34.
12. Æ ó ð á å í ê î Í . à . , Ñ à è ì á å ò î â Ä . Õ . Ê ÷èñëåííîìó ðåøåíèþ îäíîãî êëàññà çàäà÷
ðîáàñòíîãî ðàçäåëåíèÿ äâóõ ìíîæåñòâ // Ìåòîäû èññëåäîâàíèÿ ýêñòðåìàëüíûõ çàäà÷. — Êèåâ:
Èí-ò êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, 1994. — Ñ. 52–55.
13. S h o r N . Z . Nondifferentiable optimization and polynomial problems. — Dordrecht: Kluwer,
1998. — 394 p.
14. Ë à ï ò è í Þ . Ï . Îäèí ïîäõîä ê ðåøåíèþ íåëèíåéíûõ çàäà÷ îïòèìèçàöèè ñ îãðàíè÷åíèÿìè
// Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2009. — ¹ 3. — Ñ. 182–187.
15. Ë à ï ò è í Þ . Ï . , Ë è õ î â è ä À . Ï . Èñïîëüçîâàíèå âûïóêëûõ ïðîäîëæåíèé ôóíêöèé äëÿ
ðåøåíèÿ íåëèíåéíûõ çàäà÷ îïòèìèçàöèè // Óïðàâëÿþùèå ñèñòåìû è ìàøèíû. — 2010. —
¹ 6. — Ñ. 25–31.
Ïîñòóïèëà 14.07.2010
164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 4
|