Минимизация эмпирического риска и задачи построения линейных классификаторов

Розглянуто задачі побудови лінійних класифікаторів для класифікації багатьох множин. У випадку лінійно роздільних множин наведені формулювання є узагальненням раніше відомих. Для лінійно нерозділимих множин природним критерієм вибору класифікатора є мінімізація емпіричного ризику. Розглядаються част...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2011
Автори:	Лаптин, Ю.П., Журавлев, Ю.И., Виноградов, А.П.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Назва видання:	Кибернетика и системный анализ
Теми:	Системный анализ
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/84224
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Минимизация эмпирического риска и задачи построения линейных классификаторов / Ю.П. Лаптин, Ю.И. Журавлев, А.П. Виноградов // Кибернетика и системный анализ. — 2011. — Т. 47, № 4. — С. 155-164. — Бібліогр.: 15 назв. — рос.

Репозитарії

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

Минимизация эмпирического риска и задачи построения линейных классификаторов

Репозитарії

Схожі ресурси