Об эффективности методов классификации, основанных на минимизации эмпирического риска
Задачу бінарної класифікації зведено до мінімізації опуклих функціоналів регуляризованого емпіричного ризику у репродуктивному гільбертовому просторі. Розв’язок цієї задачі шукається у вигляді лінійної комбінації ядерних опорних функцій (метод опорних векторів Вапника). Отримано оцінки ризику помилк...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2009 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/44404 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Об эффективности методов классификации, основанных на минимизации эмпирического риска / В.И. Норкин, М.А. Кайзер // Кибернетика и системный анализ. — 2009. — № 5. — С. 93-105. — Бібліогр.: 33 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859813212186214400 |
|---|---|
| author | Норкин, В.И. Кайзер, М.А. |
| author_facet | Норкин, В.И. Кайзер, М.А. |
| citation_txt | Об эффективности методов классификации, основанных на минимизации эмпирического риска / В.И. Норкин, М.А. Кайзер // Кибернетика и системный анализ. — 2009. — № 5. — С. 93-105. — Бібліогр.: 33 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Задачу бінарної класифікації зведено до мінімізації опуклих функціоналів регуляризованого емпіричного ризику у репродуктивному гільбертовому просторі. Розв’язок цієї задачі шукається у вигляді лінійної комбінації ядерних опорних функцій (метод опорних векторів Вапника). Отримано оцінки ризику помилкової класифікації як функції об’єму навчальної вибірки та інших параметрів моделі.
A binary classification problem is reduced to the minimization of convex regularized empirical risk functionals in a reproducing kernel Hilbert space. The solution is searched for in the form of a finite linear combination of kernel support functions (support vector machines of Vapnik). Risk estimates for a misclassification as a function of a training sample volume and other model parameters are obtained.
|
| first_indexed | 2025-12-07T15:20:56Z |
| format | Article |
| fulltext |
ÓÄÊ 519:234:24:85
Â.È. ÍÎÐÊÈÍ, Ì.À. ÊÀÉÇÅÐ
ÎÁ ÝÔÔÅÊÒÈÂÍÎÑÒÈ ÌÅÒÎÄÎÂ ÊËÀÑÑÈÔÈÊÀÖÈÈ,
ÎÑÍÎÂÀÍÍÛÕ ÍÀ ÌÈÍÈÌÈÇÀÖÈÈ ÝÌÏÈÐÈ×ÅÑÊÎÃÎ ÐÈÑÊÀ
Êëþ÷åâûå ñëîâà: ìàøèííîå îáó÷åíèå, êëàññèôèêàöèÿ, ðàñïîçíàâàíèå, ìèíèìè-
çàöèÿ ýìïèðè÷åñêîãî ðèñêà, ìåòîä îïîðíûõ âåêòîðîâ (SVM), ñîñòîÿòåëüíîñòü,
ñêîðîñòü ñõîäèìîñòè.
ÂÂÅÄÅÍÈÅ
 íàñòîÿùåé ðàáîòå îáñóæäàåòñÿ òåîðåòè÷åñêàÿ ýôôåêòèâíîñòü íåêîòîðûõ ìåòî-
äîâ (áèíàðíîé) êëàññèôèêàöèè, â ÷àñòíîñòè ìåòîäà îïîðíûõ âåêòîðîâ (Support
Vector Machine/Method — SVM) [1]. Çàäà÷à êëàññèôèêàöèè ðàññìàòðèâàåòñÿ
â ñòàíäàðòíîé äëÿ ñòàòèñòè÷åñêîé òåîðèè îáó÷åíèÿ ìîäåëè «îáó÷åíèÿ ñ ó÷èòå-
ëåì». Ïðåäïîëàãàåòñÿ, ÷òî èìååòñÿ îáó÷àþùàÿ âûáîðêà ïàðíûõ íàáëþäåíèé
{ }( , ), ,... ,y x i mi i �1 ðàçìåðà m , ãäå xi — âåêòîð ïðèçíàêîâ îáúåêòà i ñî çíà÷åíè-
ÿìè â ìíîæåñòâå X , yi — ìåòêà êëàññà èç äèñêðåòíîãî ìíîæåñòâà Y , êîòîðîìó
ïðèíàäëåæèò îáúåêò i.  ñòàòèñòè÷åñêîé òåîðèè îáó÷åíèÿ ñ÷èòàåòñÿ, ÷òî ïàðû
( , )y xi i ÿâëÿþòñÿ íåçàâèñèìûìè ñëó÷àéíûìè âåêòîðàìè ñ îáùèì íåèçâåñòíûì
âåðîÿòíîñòíûì ðàñïðåäåëåíèåì P íà ìíîæåñòâå Y X� . Ïîä çàäà÷åé êëàññèôèêà-
öèè ïîíèìàåòñÿ ïîñòðîåíèå íà îñíîâå îáó÷àþùåé âûáîðêè îòîáðàæåíèÿ (êëàñ-
ñèôèêàòîðà) èç X â Y .  êà÷åñòâå ìåðû ýôôåêòèâíîñòè êëàññèôèêàòîðà èñïîëü-
çóåòñÿ ñðåäíÿÿ âåðîÿòíîñòü îøèáî÷íîé êëàññèôèêàöèè êàê ôóíêöèÿ îáúåìà îáó-
÷àþùåé âûáîðêè è äðóãèõ ïàðàìåòðîâ ìîäåëè. Ýòà âåëè÷èíà íàçûâàåòñÿ
óñðåäíåííûì áàéåñîâñêèì ðèñêîì (â óçêîì ñìûñëå), è äëÿ íåãî ñóùåñòâóåò òåî-
ðåòè÷åñêèé ìèíèìóì. Äëÿ ðàöèîíàëüíîãî ìåòîäà êëàññèôèêàöèè ðèñê îøèáî÷-
íîé êëàññèôèêàöèè äîëæåí ñòðåìèòüñÿ ê òåîðåòè÷åñêîìó ìèíèìóìó ñ ðîñòîì
îáúåìà îáó÷àþùåé âûáîðêè, â ýòîì ñëó÷àå ãîâîðèì î ñõîäèìîñòè (ïî âåðîÿò-
íîñòè èëè ïî÷òè íàâåðíîå) ìåòîäà êëàññèôèêàöèè. Òàêèå ìåòîäû êëàññèôèêàöèè
íàçûâàþòñÿ ñîñòîÿòåëüíûìè, îäíàêî ñîñòîÿòåëüíîñòü ìîæåò èìåòü ìåñòî òîëüêî
äëÿ îïðåäåëåííûõ êëàññîâ ðàñïðåäåëåíèé îáó÷àþùåé âûáîðêè.
Îäíà èç ïðîáëåì ñòàòèñòè÷åñêîé òåîðèè êëàññèôèêàöèè çàêëþ÷àåòñÿ â òîì, ÷òî
òåîðåòè÷åñêîå ðàñïðåäåëåíèå ýëåìåíòîâ îáó÷àþùåé âûáîðêè íåèçâåñòíî, ïîýòîìó
íåëüçÿ ôîðìàëüíî ïðîâåðèòü, ïðèíàäëåæèò ëè ðàñïðåäåëåíèå äàííîé îáó÷àþùåé âû-
áîðêè ê òîìó èëè èíîìó êëàññó. Íåêîòîðûì ðàçðåøåíèåì ýòîé ïðîáëåìû ìîãëè áû
áûòü ìåòîäû êëàññèôèêàöèè, ñîñòîÿòåëüíûå íà ëþáîì ðàñïðåäåëåíèè îáó÷àþùèõ
äàííûõ. Òàêèå ìåòîäû åñòåñòâåííî íàçûâàòü óíèâåðñàëüíî ñîñòîÿòåëüíûìè [2]. Äîë-
ãîå âðåìÿ íå áûëî èçâåñòíî, ñóùåñòâóþò ëè óíèâåðñàëüíî ñîñòîÿòåëüíûå ìåòîäû
êëàññèôèêàöèè. Òîëüêî â 1977 ãîäó áûëî ïîêàçàíî [3], ÷òî ýòèì ñâîéñòâîì îáëàäàåò
èçâåñòíûé ñ 1951 ãîäà ìåòîä k -áëèæàéøèõ ñîñåäåé. Îäíàêî âûÿñíèëîñü [2], ÷òî óíè-
âåðñàëüíî ñîñòîÿòåëüíûå ìåòîäû ìîãóò ñõîäèòüñÿ (ñíèæàòü ðèñê îøèáî÷íîé êëàññè-
ôèêàöèè ñ ðîñòîì îáó÷àþùåé âûáîðêè) êàê óãîäíî ïëîõî íà íåêîòîðûõ ðàñïðåäåëå-
íèÿõ îáó÷àþùèõ äàííûõ è, ñëåäîâàòåëüíî, íå ñóùåñòâóåò óíèâåðñàëüíî íàèëó÷øåãî
(îïòèìàëüíîãî) ìåòîäà êëàññèôèêàöèè. Òàêèì îáðàçîì, óòâåðæäåíèÿ îá îöåíêàõ ñêî-
ðîñòè ñõîäèìîñòè ðèñêà îøèáî÷íîé êëàññèôèêàöèè ê íåóñòðàíèìîìó ìèíèìóìó èëè
îá îïòèìàëüíîñòè íåêîòîðîãî ìåòîäà êëàññèôèêàöèè ñïðàâåäëèâû òîëüêî äëÿ îïðå-
äåëåííîãî êëàññà ðàñïðåäåëåíèé îáó÷àþùèõ äàííûõ.
Ýòîò âûâîä îòíîñèòñÿ è ê ìåòîäàì ìèíèìèçàöèè ýìïèðè÷åñêîãî ðèñêà,
â ÷àñòíîñòè ê ìåòîäó îïîðíûõ âåêòîðîâ [1]. Åãî ëèíåéíûé âàðèàíò (ìåòîä îïòè-
ìàëüíûõ ðàçäåëÿþùèõ ïëîñêîñòåé) äåòàëüíî èññëåäîâàí â [4, 5], à íåëèíåéíûé (ìå-
òîä ïîòåíöèàëüíûõ ôóíêöèé) — â [6], íîâåéøèå âåðñèè (ìåòîäû îïîðíûõ âåêòî-
ðîâ — SVM) îïèñàíû â [1, 7, 8]. Â íàñòîÿùåå âðåìÿ SVM óñïåøíî êîíêóðèðóþò
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 93
© Â.È. Íîðêèí, Ì.À. Êàéçåð, 2009
ñ íàèáîëåå ðàçâèòûìè ñèñòåìàìè ìàøèííîé êëàññèôèêàöèè, ïîýòîìó îí ïðîäîëæà-
åò îñòàâàòüñÿ îáúåêòîì èíòåíñèâíîãî òåîðåòè÷åñêîãî àíàëèçà [8, 9]. Êëàññè÷åñêîå
îáîñíîâàíèå ìåòîäà áàçèðóåòñÿ íà ðàâíîìåðíîì ôóíêöèîíàëüíîì çàêîíå áîëüøèõ
÷èñåë, à ïîëó÷åííûå îöåíêè ñêîðîñòè ñõîäèìîñòè çàâèñÿò îò òàê íàçûâàåìîé
VC-åìêîñòè (Âàïíèêà–×åðâîíåíêèñà) êëàññà ðåøàþùèõ ôóíêöèé [1, 4, 5]. Îäíàêî
îöåíêà VC-åìêîñòè â îáùåì ñëó÷àå ïðåäñòàâëÿåò íåïðîñòóþ ïðîáëåìó, è áîëåå
òîãî, äàëåêî íå âñåãäà êëàññ äîïóñòèìûõ ôóíêöèé èìååò êîíå÷íóþ VC-åìêîñòü.
Õîòÿ íåêîòîðûå ÷àñòî èñïîëüçóåìûå ìèíèìèçèðóåìûå (êâàäðàòè÷íûå, àáñîëþòíî-
ãî îòêëîíåíèÿ) ôóíêöèîíàëû ýìïèðè÷åñêîãî ðèñêà îòðàæàþò êà÷åñòâî êëàññèôè-
öèðóþùåãî ïðàâèëà, èõ ñâÿçü ñ âåðîÿòíîñòüþ áåçîøèáî÷íîé êëàññèôèêàöèè íå
î÷åâèäíà. Âèä èìåþùèõñÿ îöåíîê ñêîðîñòè ñõîäèìîñòè â òåðìèíàõ äîâåðèòåëüíûõ
ãðàíèö äëÿ ðèñêà íå ïîçâîëÿåò ñðàâíèâàòü äàííûé ìåòîä ñ äðóãèìè, äëÿ êîòîðûõ
ýòè îöåíêè ïîëó÷åíû â òåðìèíàõ ñõîäèìîñòè ñðåäíåãî ðèñêà.
 íàñòîÿùåé ðàáîòå èññëåäóåòñÿ ìåòîä îïîðíûõ âåêòîðîâ äëÿ ðåøåíèÿ çàäà÷
áèíàðíîé êëàññèôèêàöèè ñ ïîçèöèé òåîðèè íåêîððåêòíûõ çàäà÷ è óñòàíàâëèâàþòñÿ
îöåíêè ñêîðîñòè ñõîäèìîñòè ìåòîäà ïðè äîâîëüíî îáùèõ ïðåäïîëîæåíèÿõ î ðàñ-
ïðåäåëåíèè îáó÷àþùèõ äàííûõ. Ýòè ïðåäïîëîæåíèÿ ñîñòîÿò â òîì, ÷òî íåêîòîðûå
õàðàêòåðèñòèêè ðàñïðåäåëåíèÿ äàííûõ (óñëîâíûå ìåäèàíû è ñðåäíèå) ïðèíàäëåæàò
îïðåäåëåííîìó ôóíêöèîíàëüíîìó ãèëüáåðòîâó ïðîñòðàíñòâó (ñ âîñïðîèçâîäÿùèì
ÿäðîì).  ñòàòüå óòî÷íÿåòñÿ ñâÿçü ìåæäó èñïîëüçóåìûìè ôóíêöèîíàëàìè ðèñêà è
âåðîÿòíîñòÿìè îøèáî÷íîé êëàññèôèêàöèè. Ïîëó÷åíû îöåíêè ñêîðîñòè ñõîäèìîñòè
âåðîÿòíîñòè îøèáî÷íîé êëàññèôèêàöèè ê ìèíèìóìó, çàâèñÿùèå îò ðàñïðåäåëåíèÿ
äàííûõ, íî íå çàâèñÿùèå îò VC-åìêîñòè ôóíêöèîíàëüíîãî ïðîñòðàíñòâà. Ïðè ýòîì
íå èñïîëüçóåòñÿ ðàâíîìåðíûé ôóíêöèîíàëüíûé çàêîí áîëüøèõ ÷èñåë. Ýòè îöåíêè
ñîäåðæàò íåèçâåñòíûå êîíñòàíòû, ïîýòîìó íåïðèãîäíû äëÿ êîëè÷åñòâåííûõ âûâî-
äîâ, îäíàêî ïîêàçûâàþò õàðàêòåð ñòðåìëåíèÿ ê òåîðåòè÷åñêîìó ìèíèìóìó ñðåäíåé
îøèáêè äàííîãî êëàññèôèêàòîðà. Êàê ïðàâèëî, ñêîðîñòü ñõîäèìîñòè èìååò ïîðÿ-
äîê const / m4 , ãäå m — ÷èñëî ýëåìåíòîâ â îáó÷àþùåé âûáîðêå.
Èçëîæåíèå ïîñòðîåíî ñëåäóþùèì îáðàçîì. Â ïåðâîì ðàçäåëå îáñóæäàþòñÿ
ìåòîäû êëàññèôèêàöèè, îñíîâàííûå íà àïïðîêñèìàöèè òî÷íîãî ðåøåíèÿ çàäà÷è
ìèíèìèçàöèè ðèñêà êëàññèôèêàöèè. Âî âòîðîì ðàçäåëå ðàññìàòðèâàåòñÿ àëüòåðíà-
òèâíûé ïîäõîä ê êëàññèôèêàöèè, à èìåííî, ïîêàçàíî, êàê çàäà÷à ìèíèìèçàöèè âå-
ðîÿòíîñòè îøèáî÷íîé êëàññèôèêàöèè ìîæåò áûòü ñâåäåíà ê çàäà÷å ìèíèìèçàöèè
âûïóêëîãî ôóíêöèîíàëà ðèñêà. Â òðåòüåì ðàçäåëå îïèñûâàåòñÿ ìåòîä ðåãóëÿðèçà-
öèè äëÿ ìèíèìèçàöèè âûïóêëûõ ôóíêöèîíàëîâ ýìïèðè÷åñêîãî ðèñêà, à â ÷åòâåð-
òîì — èññëåäóåòñÿ åãî ñõîäèìîñòü ïðè óâåëè÷åíèè ÷èñëà îáó÷àþùèõ ïðèìåðîâ.
 ïÿòîì ðàçäåëå ýòè ðåçóëüòàòû èíòåðïðåòèðóþòñÿ äëÿ çàäà÷ êëàññèôèêàöèè.  çà-
êëþ÷åíèè îáñóæäàþòñÿ îñíîâíûå îñîáåííîñòè ìåòîäà îïîðíûõ âåêòîðîâ â ñâåòå
ïîëó÷åííûõ â ñòàòüå ðåçóëüòàòîâ.
1. ÁÀÉÅÑÎÂÑÊÈÅ ÌÅÒÎÄÛ ÊËÀÑÑÈÔÈÊÀÖÈÈ
Ïóñòü äàííûå íàáëþäåíèé ïðåäñòàâëÿþò ñîáîé ñëó÷àéíûå ïàðû ( , )y x ñ ðàñïðå-
äåëåíèåì P , ïðè÷åì ñêàëÿðíàÿ âåëè÷èíà y Y� ìîæåò ïðèíèìàòü òîëüêî äèñêðåò-
íûå çíà÷åíèÿ (ìåòêè êëàññîâ), íàïðèìåð y Y� �{ }0 1, , à êîìïîíåíòû n -ìåðíîãî
âåêòîðà x X� (ïðèçíàêè) ìîãóò áûòü êàê äèñêðåòíûìè, òàê è íåïðåðûâíûìè. Çà-
äà÷à ñ s êëàññàìè ñòàíäàðòíûì îáðàçîì ñâîäèòñÿ ê ðåøåíèþ s çàäà÷ áèíàðíîé
êëàññèôèêàöèè, â êîòîðûõ îäèí êëàññ — ýòî îäèí èç èñõîäíûõ êëàññîâ, à âòî-
ðîé — âñå îñòàëüíûå. Äëÿ ëþáîé èçìåðèìîé ôóíêöèè f x X R( ): � 1 áèíàðíîå
êëàññèôèöèðóþùåå ïðàâèëî îïðåäåëÿåòñÿ ïî ôîðìóëå
(1)
94 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
�
�
�
�
.ñëó÷àåïðîòèâíîìâ0
,2/1)(,1
))((2/1
xf
xfI
Êà÷åñòâî êëàññèôèöèðóþùåãî ïðàâèëà I f1 2/ ( ( ))
èçìåðÿåòñÿ áàéåñîâñêèì ðèñ-
êîì, ò.å. âåðîÿòíîñòüþ P I f x y{ }1 2/ ( ( )) � îøèáî÷íîé êëàññèôèêàöèè, ãäå
y �{ }0 1, . Íàïîìíèì [2, ñ. 10], ÷òî áàéåñîâñêèé ðèñê äîñòèãàåò ìèíèìàëüíîãî
çíà÷åíèÿ P * íà ðåøàþùåì ïðàâèëå, çàäàâàåìîì ôóíêöèåé óñëîâíîé âåðîÿò-
íîñòè p x P y x1 1( ) |� �{ }, íî îíà íå èçâåñòíà.  ñëó÷àå ìíîãèõ êëàññîâ, êîãäà
y Y� �{ }0 1 2, , ,... , îïòèìàëüíàÿ áàéåñîâñêàÿ ñòðàòåãèÿ êëàññèôèêàöèè ñîñòîèò
â ìàêñèìèçàöèè ïî l �{ }0 1 2, , ,... óñëîâíîãî ðàñïðåäåëåíèÿ âåðîÿòíîñòåé p xl ( ) �
� �P y l x{ }| [10, ñ. 22], êîòîðîå, îäíàêî, òîæå íå èçâåñòíî.
Òàêèì îáðàçîì, îäèí âîçìîæíûé ïóòü ïîñòðîåíèÿ îïòèìàëüíûõ êëàññèôèêàòîðîâ
ñîñòîèò â àïïðîêñèìàöèè óñëîâíîé âåðîÿòíîñòè p x P y x1 1( ) |� �{ } â áèíàðíîì ñëó-
÷àå èëè ðàñïðåäåëåíèÿ p x P y l xl ( ) |� �{ }, l � 0 1, ,... , â îáùåì ñëó÷àå. Íàïðèìåð,
â ìåòîäå êëàññèôèêàöèè ïî k -áëèæàéøèì ñîñåäÿì [1, ðàçä. 5] îòáèðàåòñÿ k íà-
áëþäåíèé { }x i I xi k, ( )� , áëèæàéøèõ ê âåêòîðó ïðèçíàêîâ x , ñòðîèòñÿ èõ ðàñïðå-
äåëåíèå ïî êëàññàì è âåêòîð x îòíîñèòñÿ ê êëàññó ñ ìàêñèìàëüíîé ÷àñòîòîé.
Îáîçíà÷èì òàêîé êëàññèôèêàòîð g xk ( ) , åãî êà÷åñòâî èçìåðÿåòñÿ âåëè÷èíîé
âåðîÿòíîñòè îøèáî÷íîé êëàññèôèêàöèè L m E P g x y
k y x y x km m
( ) ( )( , ) ( , )� �� �{ } { }
1 1 � ,
à àñèìïòîòè÷åñêîå êà÷åñòâî — âåëè÷èíîé L L mk m k
* lim ( )� �
. Èçâåñòíî [1, ðàçä. 5],
÷òî P L P kek
* * * ( / )� � �1 1 äëÿ âñåõ ðàñïðåäåëåíèé è ÷åòíûõ k , ãäå e — îñíîâàíèå
íàòóðàëüíûõ ëîãàðèôìîâ. Êðîìå òîãî, ýòîò êëàññèôèêàòîð ÿâëÿåòñÿ óíèâåðñàëüíî ñî-
ñòîÿòåëüíûì, ò.å. L m Pk m( )
*( ) � ïðè m �
è k m m( ) / � 0 íåçàâèñèìî îò âåðîÿòíîñ-
òíîãî ðàñïðåäåëåíèÿ ýëåìåíòîâ âûáîðêè, õîòÿ ñêîðîñòü ñõîäèìîñòè L mk m( ) ( ) ê P *
ìîæåò áûòü ìåäëåííîé. Èíòåðåñíî îòìåòèòü, ÷òî ïðîñòåéøèé êëàññèôèêàòîð g x1 ( )
(êëàññèôèöèðóþùèé ïî îäíîìó áëèæàéøåìó ñîñåäó) ìîæåò áûòü â ñðåäíåì ëó÷øå íà
íåêîòîðûõ ðàñïðåäåëåíèÿõ äàííûõ, ÷åì áîëåå ñëîæíûå êëàññèôèêàòîðû g xk ( ) ñ k 1.
 [1] ïîêàçàíî, ÷òî íåëüçÿ ïîñòðîèòü óíèâåðñàëüíî ñîñòîÿòåëüíûé êëàññèôèêàòîð ñ
ôèêñèðîâàííîé ñêîðîñòüþ ñõîäèìîñòè âåðîÿòíîñòè îøèáî÷íîé êëàññèôèêàöèè ê òåî-
ðåòè÷åñêîìó ìèíèìóìó P * . Äëÿ ëþáîãî êëàññèôèêàòîðà ñêîðîñòü ñõîäèìîñòè ìîæåò
îêàçàòüñÿ êàê óãîäíî ìåäëåííîé ïðè ñîîòâåòñòâóþùåì âûáîðå ðàñïðåäåëåíèÿ èñõîä-
íûõ äàííûõ. Ïîýòîìó îöåíêè ñêîðîñòè ñõîäèìîñòè ìîãóò áûòü ïîëó÷åíû òîëüêî ïðè
äîïîëíèòåëüíûõ ïðåäïîëîæåíèÿõ î ðàñïðåäåëåíèè íàáëþäåíèé.
Çàìåòèì, ÷òî â áèíàðíîì ñëó÷àå p x P y x1 1( ) |� �{ } ÿâëÿåòñÿ ôóíêöèåé óñëîâ-
íîãî ñðåäíåãî (ðåãðåññèè), ïîýòîìó äëÿ åå îöåíêè ìîæíî ïðèìåíÿòü ñòàíäàðòíûå
ïîäõîäû ðåãðåññèîííîãî àíàëèçà, â ÷àñòíîñòè íåïàðàìåòðè÷åñêèå ìåòîäû [11].
Ïóñòü { }( , ), ,... ,y x i mi i �1 — îáó÷àþùàÿ âûáîðêà, �( , )
— íåêîòîðàÿ ôóíêöèÿ ðàñ-
ñòîÿíèÿ ìåæäó òî÷êàìè â ïðîñòðàíñòâå ïðèçíàêîâ X , k( )
— íåêîòîðàÿ îäíîìåð-
íàÿ ñèììåòðè÷íàÿ ïëîòíîñòü âåðîÿòíîñòåé, �m — ïîëîæèòåëüíûå ÷èñëà. Òîãäà
ÿäåðíàÿ îöåíêà Íàäàðàè–Âàòñîíà [11, ðàçä. 5] ôóíêöèè ðåãðåññèè p x1 ( ) â äàííîì
ñëó÷àå èìååò âèä
~ ( )
( , ) ( , )
:
/p x k
x x
k
x xi
mi y
i
m
i
1
1
�
�
�
��
�
�
��
�
�
��
�
�
�
�
�
�
�
�
� �
�
�
i
m
1
,
à ñîîòâåòñòâóþùèé áèíàðíûé êëàññèôèêàòîð çàäàåòñÿ ôîðìóëîé (1) ñ f x p x( ) ~ ( )� 1 .
 ðàáîòàõ [12–14] íåèçâåñòíîå óñëîâíîå ðàñïðåäåëåíèå âåðîÿòíîñòåé
{ }p x ll ( ), , , ...� 0 1 àïïðîêñèìèðóåòñÿ áàéåñîâñêîé îöåíêîé { }~ ( ), , ,...p x ll � 0 1 ïðè
(ñèëüíîì) ïðåäïîëîæåíèè óñëîâíîé íåçàâèñèìîñòè ïðèçíàêîâ (êîìïîíåíò ñëó÷àé-
íîãî âåêòîðà x äëÿ îáúåêòîâ èç ôèêñèðîâàííîãî êëàññà l ). Äëÿ òàêîãî êëàññèôèêà-
òîðà â [12–14] ïîëó÷åíû îöåíêè ñêîðîñòè ñõîäèìîñòè âèäà
B m E P p x y P C my x y x l lm m
( ) {arg max ~ ( ) } /( , ) ( , )}
*� � � �� �{ 1 1 � ,
ãäå C — óíèâåðñàëüíàÿ êîíñòàíòà, íå çàâèñÿùàÿ îò ðàñïðåäåëåíèÿ äàííûõ, è äî-
êàçàíà èõ íåóëó÷øàåìîñòü ïðè ñäåëàííûõ ïðåäïîëîæåíèÿõ ïî õàðàêòåðó çàâèñè-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 95
ìîñòè îò ðàçìåðà îáó÷àþùåé âûáîðêè m . Ñóùåñòâåííîå äëÿ ýòîé îöåíêè ïðåä-
ïîëîæåíèå î íåçàâèñèìîñòè ïðèçíàêîâ äåòàëüíî îáñóæäàåòñÿ â [10, ðàçä. 3.3].
 áèíàðíîì ñëó÷àå õîðîøî èçâåñòíî (ñì. [2, ñ. 16] è ññûëêè â ýòîé ðàáîòå), ÷òî
áàéåñîâñêàÿ îøèáêà êëàññèôèêàöèè âûðàæàåòñÿ ÷åðåç îøèáêó ~ ( ) ( )p x p x1 1� àï-
ïðîêñèìàöèè óñëîâíîé âåðîÿòíîñòè p x P y x1 1( ) |� �{ } ñëåäóþùèì îáðàçîì:
P I p x y P E p x p x{ }1 2 1 1 12/
*( ~ ( )) | ~ ( ) ( ) |� � � � . (2)
Çäåñü ñèìâîë E îáîçíà÷àåò ìàòåìàòè÷åñêîå îæèäàíèå ïî ìåðå P . Ýòà îöåíêà
äàåò ñòàòèñòè÷åñêîå îáîñíîâàíèå ìåòîäàì êëàññèôèêàöèè, îñíîâàííûì íà àï-
ïðîêñèìàöèè óñëîâíûõ âåðîÿòíîñòåé p x P y l xl ( ) |� �{ }, l � 0 1, .
2. ÑÂßÇÜ ÇÀÄÀ×È ÁÈÍÀÐÍÎÉ ÊËÀÑÑÈÔÈÊÀÖÈÈ Ñ ÎÏÒÈÌÈÇÀÖÈÅÉ
ÂÛÏÓÊËÛÕ ÔÓÍÊÖÈÎÍÀËÎÂ ÐÈÑÊÀ
Äðóãîé ïîäõîä ê ïîñòðîåíèþ ìåòîäîâ êëàññèôèêàöèè ñîñòîèò â ñâåäåíèè çàäà÷è
êëàññèôèêàöèè ê âûïóêëîé çàäà÷å îïòèìèçàöèè ôóíêöèîíàëà ðèñêà [9, ðàçä. 4.2].
Äàëåå ðàññìîòðèì ñëó÷àè, íå ïðåäñòàâëåííûå â îáçîðå [9]. Íàïðèìåð, èçâåñòíî
[2, ñ. 11] , ÷òî p x E y f xf1
2( ) min ( ( ))� �arg . Åñëè f x( ) — íåêîòîðîå ïðèáëèæåí-
íîå ðåøåíèå çàäà÷è ìèíèìèçàöèè êâàäðàòè÷íîãî ðèñêà, òî ñîîòâåòñòâóþùåå ðå-
øàþùåå ïðàâèëî îïðåäåëÿåòñÿ ïî ôîðìóëå (1), à îöåíêà êà÷åñòâà êëàññèôèêà-
öèè — ïî ôîðìóëå (2). Ýòîò ïîäõîä ê áèíàðíîé êëàññèôèêàöèè ïîäðîáíî îáñóæ-
äàåòñÿ â [15]. Êðîìå òîãî, â ñòàòèñòè÷åñêîé òåîðèè êëàññèôèêàöèè è îáó÷åíèÿ
èñïîëüçóþòñÿ ôóíêöèîíàëû ðèñêà âèäà
R f E y f x� �( ) max , | ( ) |� � �{ }0 , � � 0,
è, â ÷àñòíîñòè, R f E y f x L f0 1( ) | ( ) | ( )� � � [1]. Èõ ïðèìåíåíèå â êàêîé-òî ìåðå
îáîñíîâàíî îöåíêîé [2, ñ. 20]
P I f x y P I f x yf{ } { }1 2 1 2/ /( ( )) min ( ( ))� � � �
� � � �2( | ( ) | min | ( ) | )E y f x E y f xf , (3)
ãäå ìèíèìóìû áåðóòñÿ ïî ìíîæåñòâó áîðåëåâñêèõ ôóíêöèé íà X .
Ñëåäóþùàÿ òåîðåìà äàåò îöåíêó êà÷åñòâà êëàññèôèêàòîðà, ìèíèìèçèðóþùåãî
êâàäðàòè÷íûé ôóíêöèîíàë ðèñêà L f E y f x2
2( ) ( ( ))� � , îòëè÷íóþ îò (2).
Òåîðåìà 1. Ïóñòü F — ìíîæåñòâî áîðåëåâñêèõ ôóíêöèé íà x X� òàêîå, ÷òî
p x P y x F1 1( ) |� � �{ } . Òîãäà äëÿ ëþáîé ôóíêöèè f F( )
� èìååò ìåñòî îöåíêà
P I f x y P I f x yf{ } { }èçìåðèìà1 2 1 2/ /( ( )) min ( ( ))� � � ��
� � �2 2 2L f L ff F( ) min ( ) . (4)
Äîêàçàòåëüñòâî. Ïðåäñòàâèì
P I f x y E P I f x y xx{ }1 2 1 2/ /( ( )) { { ( ( )) | }}� � � ,
E f x y E E f x y xx( ( ) ) ( ( ) ) |� � �2 2{ { }},
ãäå P x{ }
| è E x{ }
| — óñëîâíàÿ âåðîÿòíîñòü è óñëîâíîå ìàòåìàòè÷åñêîå îæèäà-
íèå ïðè ôèêñèðîâàííîé êîìïîíåíòå x ñëó÷àéíîãî âåêòîðà ( , )y x ; Ex — ìàòåìà-
òè÷åñêîå îæèäàíèå ïî ðàñïðåäåëåíèþ êîìïîíåíòû x . Ðàññìîòðèì ôóíêöèè
p x P y x1 1( ) |� �{ }, p x P y x p x0 10 1( ) | ( )� � � �{ } è e h x E h y x( , ) ( ) |� �{ }2 .
Ñïðàâåäëèâû ñîîòíîøåíèÿ:
r h x P I h y x
p x p x h
p x h
( , ) ( ) |
( ) ( ), / ,
( ),
/� � �
� �
�
{ }1 2
0 1
1
1 1 2
1 2/ ;
�
�
�
e h x p x h p x h h h p x p x( , ) ( )( ) ( ( )) ( ) ( )� � � � � � � �1
2
1
2 2
1 11 1 2
96 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
� � � � � � �( ( )) ( )( ( )) ( ( )) ( )*h p x p x p x h p x e x1
2
1 1 1
21 ,
e x p x p x* ( ) ( ) ( )� 0 1 .
Îòñþäà ñëåäóåò, ÷òî äëÿ ëþáîãî h R� 1 âûïîëíåíî
r h x r p x x p x p x r x( , ) ( ( ), ) min ( ), ( ) ( )*� � �1 0 1{ } , (5)
e h x e p x x p x p x e x( , ) ( ( ), ) ( ) ( ) ( )*� � �1 0 1 . (6)
Åñëè p x1 1 2( ) /� , òî
r h x r x
h
p x p x h
( , ) ( )
, / ,
( ) ( ), / .
*� �
�
�
�
�
�
0 1 2
1 20 1
Åñëè p x1 1 2( ) / , òî
r h x r x
p x p x h
h
( , ) ( )
( ) ( ), / ,
, / .
*� �
� �
�
�
�
1 0 1 2
0 1 2
Ïóñòü p x1 1 2( ) /� . Ïðè h �1 2/ âûïîëíåíî r h x r x( , ) ( )*� � �0
� �2 1 2( ( , ) ( ) )* /e h x e x . Ïðè h 1 2/ èìååò ìåñòî
e h x e x h p x p x( , ) ( ) ( ( )) ( / )( ( ))*� � � � � �1
2
1
21 4 1 2
� � � �( / )( ( ) ( )) ( / )( ( , ) ( ))*1 4 1 40 1
2 2p x p x r h x r x .
Òàêèì îáðàçîì, ïðè p x1 1 2( ) /� è âñåõ h âûïîëíåíî
r h x r x e h x e x( , ) ( ) ( , ) ( )* *� � �2 . (7)
Äîêàçàòåëüñòâî ýòîãî íåðàâåíñòâà äëÿ ñëó÷àÿ p x1 1 2( ) / ïðîâîäèòñÿ àíàëîãè÷íî.
Ïîäñòàâëÿÿ â (5), (6), (7) çíà÷åíèå h f x� ( ) è âçÿâ ìàòåìàòè÷åñêîå îæèäàíèå
ïî x , äëÿ ëþáîé èçìåðèìîé ôóíêöèè f x( ) èìååì
P I f x y P I p x y P{ } {1 2 1 2 1/ /
*( ( )) ( ( )) } ,� � � �
E f x y E p x y{ } { }( ( ) ) ( ( ) )� � �2
1
2 ,
P I f x y P I p x y E f x y E{ } { } { } {1 2 1 2 1
22/ /( ( )) ( ( )) ( ( ) ) (� � � � � � p x y1
2( ) )� }.
Ïðè ïîëó÷åíèè ïîñëåäíåãî íåðàâåíñòâà èñïîëüçîâàëîñü íåðàâåíñòâî Èåíñåíà äëÿ
âîãíóòîé ôóíêöèè ( )
. Ïîýòîìó åñëè p F1 ( )
� , òî äëÿ ëþáîé ôóíêöèè
f F( )
� âûïîëíåíî
P I f x y P E f x y E f xf F{ } { } {1 2
22/
*
( )( ( )) ( ( ) ) min ( ( )� � � � � �
� y)2 },
÷òî è òðåáîâàëîñü äîêàçàòü.
Ðàññìîòðèì çàäà÷ó [2, ñ. 20]
L f E f x y f F1 ( ) | ( ) | inf� � � � , (8)
ãäå F — ìíîæåñòâî áîðåëåâñêèõ ôóíêöèé íà x X� òàêîå, ÷òî g F1 ( )
� , ãäå
g x
p x
p x
1
1
1
1 1 2
0 1 2
( )
, ( ) / ,
, ( ) / ,
�
�
�
�
�
p x P y x1 1( ) |� �{ }.
Ñëåäóþùàÿ òåîðåìà îáîáùàåò îöåíêó (3) è óñòàíàâëèâàåò ñâÿçü ìåæäó áàéå-
ñîâñêèì ðèñêîì è âûïóêëûì ôóíêöèîíàëîì L f E f x y1 ( ) | ( ) |� � .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 97
Òåîðåìà 2. Ïóñòü F — ìíîæåñòâî áîðåëåâñêèõ ôóíêöèé íà x X� òàêîå, ÷òî
g F1 ( )
� èëè �( )
�F , ãäå �( )
— ëþáàÿ óñëîâíàÿ ìåäèàíà ðàñïðåäåëåíèÿ P x{ }
|
ïðè ôèêñèðîâàííîì x . Òîãäà äëÿ ëþáîé ôóíêöèè f F( )
� èìååò ìåñòî îöåíêà
P I f x y P I f x yf{ èçìåðèìà1 2 1 2/ /( ( )) } min { ( ( )) }� � � ��
� � �2( ( ) min ( ))R f R ff F , (9)
ãäå R f L f E f x y( ) ( ) | ( ) |� � �1 .
Äîêàçàòåëüñòâî. Äëÿ ñëó÷àÿ, êîãäà F — ìíîæåñòâî âñåõ èçìåðèìûõ ôóíêöèé
íà x X� , óòâåðæäåíèå òåîðåìû èìååòñÿ â [2, ñ. 20] (áåç ìíîæèòåëÿ 2 â ïðàâîé ÷à-
ñòè (9)). Ïðåäñòàâèì
P I f x y E P I f x y xx{ } { { }}1 2 1 2/ /( ( )) ( ( )) |� � � ,
E f x y E E f x y xx| ( ) | { {| ( ) | }}|� � � .
Ðàññìîòðèì ôóíêöèè p x P y x1 1( ) |� �{ } è a h x E h y x( , ) | | |� �{ }. Ñïðàâåäëèâû
ïðåäñòàâëåíèÿ:
r h x P I h y x
p x h
p x h
( , ) ( ) |
( ), / ,
( ), / ,
/� � �
�
�
�
�{ }1 2
1
1
1 1 2
1 2�
a h x E h y x p x h p x h( , ) | | ( ) | | ( ( )) | ||� � � � � �{ } 1 11 1 .
Îáîçíà÷èì r x p x p x* ( ) min ( ), ( )� �{ }1 11 . Äëÿ ëþáîé óñëîâíîé ìåäèàíû �( )
èìå-
åò ìåñòî
�( )
, ( ) / ,
[ , ], ( ) / ,
, ( ) / ,
x
p x
p x
p x
�
�
�
�
�
�
�
�
1 1 2
0 1 1 2
0 1 2
1
1
1
è, â ÷àñòíîñòè, g x1 ( ) ÿâëÿåòñÿ óñëîâíîé ìåäèàíîé ðàñïðåäåëåíèÿ P ïðè ôèêñèðî-
âàííîì x . Îòñþäà ñëåäóåò, ÷òî äëÿ ëþáîãî h R� 1 âûïîëíåíî
r h x r p x x r x( , ) ( ( ), ) ( )*� �1 , (10)
a h x a x x r x( , ) ( ( ), ) ( )*� �� . (11)
Äîêàæåì íåðàâåíñòâî
r h x r x a h x r x( , ) ( ) ( ( , ) ( ))* *� � �2 . (12)
Ðàññìîòðèì ôóíêöèè
�( , )
, / ,
, / ;
p h
p h
p h
�
�
�
�
�
�
1 1 2
1 2
�( , ) | | ( ) | |
, ,
, ,
,
p h p h p h
p h h
p h ph h
h p h
� � � � �
� �
� � � �
�
1 1
0
2 0 1
�
�
�
�
�
� 1.
Ïîêàæåì, ÷òî ïðè p p� � �1 2 1/ âûïîëíåíî � �( , ) ( ( , ) )p h p p h p� � �2 . Äåé-
ñòâèòåëüíî,
� �( , ) ( ( , ) )p h p p h p h� � � � � �0 2 2 ïðè h � 0;
� �( , ) ( ( , ) ) ( )p h p p h p h p� � � � � �0 2 2 1 2 ïðè 0 1 2� �h / ;
� �( , ) ( ( , ) ) ( )p h p p p h p h p� � � � � � �1 2 2 2 1 2 ïðè 1 2 1/ � �h ;
� �( , ) ( ( , ) ) ( )p h p p p h p h p� � � � � � �1 2 2 2 2 ïðè 1� h .
Àíàëîãè÷íî ïðîâåðÿåòñÿ, ÷òî ïðè 1 1 2� � �p p/ âûïîëíåíî �( , ) ( )p h p� � �1
� � �2 1( ( , ) ( ))� p h p . Òàêèì îáðàçîì, íåðàâåíñòâî (12) äîêàçàíî.
Ïîäñòàâëÿÿ â (10), (11), (12) çíà÷åíèå h f x� ( ) è âçÿâ ìàòåìàòè÷åñêîå îæèäà-
íèå ïî x, äëÿ ëþáîé áîðåëåâñêîé ôóíêöèè f x( ) ïîëó÷àåì
98 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
P I f x y P I p x y P{ {1 2 1 2 1/ /
*( ( )) } ( ( )) } ,� � � �
E f x y E x y| ( ) | | ( ) |,� � ��
P I f x y P E f x y E x y{ }1 2 2/
*( ( )) ( | ( ) | | ( ) | )� � � � � �� . (13)
Èç (13) ñëåäóåò òðåáóåìîå íåðàâåíñòâî (9).
Òåîðåìà äîêàçàíà.
Òàêèì îáðàçîì, ìèíèìèçàöèÿ ôóíêöèîíàëà L f E f x y1 ( ) | ( ) |� � ïî ìíîæåñòâó
áîðåëåâñêèõ ôóíêöèé F òàêîìó, ÷òî g F1 ( )
� èëè �( )
�F , â ñèëó (9) àâòîìàòè÷åñ-
êè âåäåò ê ìèíèìèçàöèè ôóíêöèîíàëà áàéåñîâñêîãî ðèñêà.
Êàê èçâåñòíî, ìèíèìóì êâàäðàòè÷íîãî ôóíêöèîíàëà ðèñêà L f2 ( ) äîñòèãàåòñÿ
íà ôóíêöèè óñëîâíîãî ñðåäíåãî m x yP dy x
R
( ) ( | )� � 1 ðàñïðåäåëåíèÿ P . Äëÿ íåêâàä-
ðàòè÷íûõ ôóíêöèîíàëîâ ðèñêà ñîîòâåòñòâèå èõ ìèíèìóìîâ êàêèì-ëèáî õàðàêòå-
ðèñòèêàì ðàñïðåäåëåíèÿ ìåíåå î÷åâèäíî, íî â ñëó÷àå ôóíêöèîíàëà ñðåäíåãî àáñî-
ëþòíîãî îòêëîíåíèÿ, ÷àñòî èñïîëüçóåìîãî â òåîðèè ñòàòèñòè÷åñêîãî îáó÷åíèÿ,
òàêîå ñîîòâåòñòâèå ìîæåò áûòü óñòàíîâëåíî.
Òåîðåìà 3.  çàäà÷å ìèíèìèçàöèè ôóíêöèîíàëà ðèñêà
R f E f x y y f xx y( ) max ( )( ( ) ), ( ( ))( , )� � � �{ }1 � �
ïî âñåì èçìåðèìûì ôóíêöèÿì f x( ) ìèíèìóì äîñòèãàåòñÿ íà óñëîâíûõ � -êâàíòè-
ëÿõ ðàñïðåäåëåíèÿ P , ò.å. íà ôóíêöèÿõ q x( ) òàêèõ, ÷òî P y q x x{ }� �( ) | � .  ÷àñ-
òíîñòè, ïðè � � 0 5, ôóíêöèîíàë ðèñêà èìååò âèä R f E f x y( ) ( / ) | ( ) |� �1 2 è åãî
ìèíèìóì äîñòèãàåòñÿ íà óñëîâíûõ ìåäèàíàõ �( )x ðàñïðåäåëåíèÿ P x{ }
| .
Äàííîå óòâåðæäåíèå ïîëó÷åíî â [16, 17]; â êîíòåêñòå ñòîõàñòè÷åñêèõ ìèíè-
ìàêñíûõ çàäà÷ ýòîò ôàêò áûë óñòàíîâëåí â ðàáîòàõ [18, 19]; îí äåòàëüíî îáñóæäà-
åòñÿ â [20]. Îòìåòèì, ÷òî � -êâàíòèëü è ìåäèàíà ðàñïðåäåëåíèÿ, â îáùåì ñëó÷àå,
ìîãóò áûòü íå åäèíñòâåííûìè.
Åñëè åñòü àïðèîðíûå îñíîâàíèÿ ïîëàãàòü, ÷òî óñëîâíûå ìåäèàíû ðàñïðåäåëå-
íèÿ P( )
ïðèíàäëåæàò íåêîòîðîìó êëàññó ôóíêöèé, íàïðèìåð íåêîòîðîìó ãèëüáåð-
òîâó ïðîñòðàíñòâó H , òî â (8) ìîæíî ïîëîæèòü F H� .  ýòîì ñëó÷àå ãîâîðÿò îá îò-
ñóòñòâèè îøèáêè àïïðîêñèìàöèè (ìåäèàí) ôóíêöèÿìè èç H .  îáùåì ñëó÷àå îøèá-
êà àïïðîêñèìàöèè ñóùåñòâóåò, åå îöåíêè èìåþòñÿ â [2, 8, 11, 21].
 [1] ïðè ðåøåíèè çàäà÷ êëàññèôèêàöèè ÷àñòî èñïîëüçóþòñÿ � -íå÷óâñòâèòåëü-
íûå ôóíêöèîíàëû ðèñêà âèäà
R f E f x y� �( ) max , | ( ) |� � �{ }0 .
Ëåãêî âèäåòü, ÷òî ôóíêöèîíàë L f E f x y1 ( ) | ( ) |� � ñâÿçàí ñ R f� ( ) ñîîòíîøåíèåì
L f R f L f1 1( ) ( ) ( )� � �� � ðàâíîìåðíî ïî âñåì áîðåëåâñêèì ôóíêöèÿì f , ïîýòîìó
â óñëîâèÿõ òåîðåìû 2 èç (9) ñëåäóåò ñîîòíîøåíèå
P I f x y P I f x y R ff F f{ } { }1 2 1 2 2/ /( ( )) min ( ( )) ( ( ) min� � � � �� � � �F R f� �( )) 2 .
Èñïîëüçîâàíèå �-íå÷óâñòâèòåëüíûõ ôóíêöèîíàëîâ ðèñêà ïîçâîëÿåò óïðîñòèòü
êëàññèôèêàòîð [1], õîòÿ è óõóäøàåò òî÷íîñòü êëàññèôèêàöèè íà 2� .
 çàäà÷àõ êëàññèôèêàöèè ÷àñòî èñïîëüçóþòñÿ ôóíêöèîíàëû âèäà
R f E y f x( ) ( ( ))� �� [9], ãäå ìåòêè êëàññîâ y � �{ }1 , �( )
— íåêîòîðàÿ íåîòðèöà-
òåëüíàÿ âûïóêëàÿ íåóáûâàþùàÿ ôóíêöèÿ ïîòåðü òàêàÿ, ÷òî lim ( )t t��
�� 0 è
�( )0 1� . Ñ èõ ïîìîùüþ òàêæå óñòàíîâëåíû îöåíêè ðèñêà áåçîøèáî÷íîé êëàññè-
ôèêàöèè, àíàëîãè÷íûå îöåíêàì (4), (9).
Îòìåòèì, ÷òî â çàäà÷àõ êëàññèôèêàöèè ïðèçíàêîâîå ïðîñòðàíñòâî X ÷àñòî ÿâ-
ëÿåòñÿ äèñêðåòíûì, íàïðèìåð, îíî ìîæåò ñîñòîÿòü èç âåðøèí åäèíè÷íîãî êóáà
[6, ãë. III, §1.3].  ýòîì ñëó÷àå ôóíêöèÿ f x( ) , x X� , çàäàåòñÿ êîíå÷íûì, âîçìîæ-
íî î÷åíü áîëüøèì, ÷èñëîì çíà÷åíèé, ò.å. ÿâëÿåòñÿ âåêòîðîì áîëüøîé ðàçìåðíîñòè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 99
3. ÎÏÒÈÌÈÇÀÖÈß ÐÅÃÓËßÐÈÇÎÂÀÍÍÛÕ ÔÓÍÊÖÈÎÍÀËÎÂ
ÝÌÏÈÐÈ×ÅÑÊÎÃÎ ÐÈÑÊÀ È ÌÅÒÎÄ ÎÏÎÐÍÛÕ ÂÅÊÒÎÐÎÂ
 ðàçä. 2 ïîêàçàíî, ÷òî çàäà÷à áèíàðíîé êëàññèôèêàöèè ìîæåò áûòü ñâåäåíà
ê ìèíèìèçàöèè âûïóêëîãî ôóíêöèîíàëà ðèñêà.  îáùåì ñëó÷àå îíà èìååò âèä
R f Ec y f x f F( ) ( , ( )) min� � � , (14)
ãäå c y f x( , ( )) — íåêîòîðàÿ ôóíêöèÿ ïîòåðü, íàïðèìåð, c y f x y f x( , ( )) ( ( ))� � 2 ,
c y f x y f x( , ( )) | ( ) |� � , c y f x y f x( , ( )) max , ( )� �{ }0 1 ; F — äîïóñòèìûé êëàññ
ôóíêöèé. Îáîçíà÷èì F * ìíîæåñòâî ðåøåíèé çàäà÷è (14).  ïðåäûäóùåì ðàçäå-
ëå òàêæå ïîêàçàíî, ÷òî ìèíèìóì â òàêèõ çàäà÷àõ ìîæåò äîñòèãàòüñÿ íà íåêîòî-
ðîé õàðàêòåðèñòèêå ðàñïðåäåëåíèÿ ñëó÷àéíîãî âåêòîðà íàáëþäåíèé z y x� ( , ) , íà-
ïðèìåð ôóíêöèè óñëîâíîãî ñðåäíåãî p x1 ( ) èëè óñëîâíîé ìåäèàíå �( )x . Åñëè
åñòü îñíîâàíèÿ ïîëàãàòü, ÷òî ýòè õàðàêòåðèñòèêè ïðèíàäëåæàò íåêîòîðîìó êëàñ-
ñó ôóíêöèé F , íàïðèìåð ïîäìíîæåñòâó íåêîòîðîãî ãèëüáåðòîâà ïðîñòðàíñòâà
ôóíêöèé H , òî â (14) ìîæíî ñ÷èòàòü F H� .  ñòàòèñòè÷åñêîé òåîðèè îáó÷åíèÿ
èñïîëüçóþòñÿ ðàçíîîáðàçíûå êëàññû ôóíêöèé (êëàññè÷åñêèå ãèëüáåðòîâû ïðîñò-
ðàíñòâà ñ çàäàííûì áàçèñîì, íåéðîñåòåâûå ñóïåðïîçèöèè, äåðåâüÿ è äðóãèå [2])
è, â ÷àñòíîñòè, òàê íàçûâàåìûå ðåïðîäóêòèâíûå ãèëüáåðòîâû ïðîñòðàíñòâà ôóíê-
öèé Hk , ïîðîæäåííûå ÿäðîì k .
Îïðåäåëåíèå 1 (ðåïðîäóêòèâíîå ãèëüáåðòîâî ïðîñòðàíñòâî). Ãèëüáåðòîâî
ïðîñòðàíñòâî H Xk ( ) ôóíêöèé, îïðåäåëåííûõ íà çàìêíóòîì ìíîæåñòâå X R n� , íà-
çûâàåòñÿ ðåïðîäóêòèâíûì ãèëüáåðòîâûì ïðîñòðàíñòâîì (ÐÃÏ), åñëè ñóùåñòâóåò
ôóíêöèÿ äâóõ âåêòîðíûõ ïåðåìåííûõ k( , )
, îïðåäåëåííàÿ íà äåêàðòîâîì ïðîèçâå-
äåíèè X X� , îáëàäàþùàÿ ñëåäóþùèìè ñâîéñòâàìè:
à) k x H Xk( , ) ( )
� � �x X ;
á) f x f k x k( ) , ( , )� �
� �f H Xk ( ) , � �x X (ðåïðîäóêòèâíîå ñâîéñòâî ÿäðà).
Òåîðèÿ ÐÃÏ èçëîæåíà â ðàáîòàõ [7, 21, 22, 23].  ÷àñòíîñòè, èçâåñòíî, ÷òî
ìíîæåñòâî ôóíêöèé
�
�
�
�
!
"
#
�f x k x x
s s s( ) ( , ) èç ÐÃÏ H H Xk k� ( ) , ãäå { }xs — ïðî-
èçâîëüíûé êîíå÷íûé íàáîð òî÷åê èç X , { } s — ïðîèçâîëüíûé êîíå÷íûé íàáîð ÷è-
ñåë, ÿâëÿåòñÿ ïëîòíûì â H Xk ( ) .
 çàäà÷àõ êëàññèôèêàöèè ðàñïðåäåëåíèå P( )
íàáëþäåíèé îáû÷íî íå èçâåñòíî
ïîëíîñòüþ, à èìååòñÿ íàáîð íåçàâèñèìûõ íàáëþäåíèé { }z y x i mi i i� �( , ), ,... ,1
âåêòîðíîé ñëó÷àéíîé âåëè÷èíû z y x� ( , ) ñ ðàñïðåäåëåíèåì P( )
, êîòîðûé â ñòàòèñ-
òè÷åñêîé òåîðèè îáó÷åíèÿ íàçûâàåòñÿ îáó÷àþùåé âûáîðêîé. Ýòî ïîçâîëÿåò àï-
ïðîêñèìèðîâàòü íåèçâåñòíîå ðàñïðåäåëåíèå P( )
ýìïèðè÷åñêèì ðàñïðåäåëåíèåì
Pm ( )
, à ôóíêöèîíàë ðèñêà R f Ec y f x( ) ( , ( ))� ñ ôóíêöèåé ïîòåðü c y f( , ) — ýìïè-
ðè÷åñêèì ñðåäíèì (ýìïèðè÷åñêèì ðèñêîì)
~
( ) ( / ) ( , ( ))R f m c z f xm
i
m
i i�
�
�1
1
.
Çàäà÷à ìèíèìèçàöèè ôóíêöèîíàëà ðèñêà (14), âîîáùå ãîâîðÿ, ìîæåò áûòü íå-
êîððåêòíîé, ò.å. èìåòü íåîäíîçíà÷íûå ðåøåíèÿ, áûòü íåóñòîé÷èâîé ïî îòíîøåíèþ
ê âîçìóùåíèÿì ôóíêöèîíàëà.  ñòàòèñòè÷åñêîé òåîðèè îáó÷åíèÿ êëàññèôèêàöèè
èñõîäíûé ôóíêöèîíàë ðèñêà R f( ) çàìåíÿåòñÿ ñëó÷àéíûì ïðèáëèæåíèåì
~
( )R fm ,
ò.å. ðàññìàòðèâàåòñÿ åãî ñòîõàñòè÷åñêîå âîçìóùåíèå âèäà R f fm( ) ( )� � , ãäå
�m mf R f R f( )
~
( ) ( )� � . Ïîýòîìó äëÿ íàõîæäåíèÿ ïðèáëèæåííûõ ðåøåíèé ïðèìå-
íÿåòñÿ ìåòîä ðåãóëÿðèçàöèè Òèõîíîâà â ôóíêöèîíàëüíîì (ãèëüáåðòîâîì) ïðîñòðà-
íñòâå H [24, 25]. Ðàññìîòðèì ìåòîä ðåãóëÿðèçàöèè â ÐÃÏ ïðè îïðåäåëåííûõ (ýìïè-
ðè÷åñêèõ) ñëó÷àéíûõ âîçìóùåíèÿõ ôóíêöèîíàëà è äëÿ îáùèõ âûïóêëûõ (íå òîëüêî
êâàäðàòè÷íûõ) ôóíêöèîíàëîâ ðèñêà, êîòîðûé ñâîäèòñÿ ê ðåøåíèþ ñåìåéñòâà çàäà÷
ìèíèìèçàöèè ðåãóëÿðèçîâàííîãî ýìïèðè÷åñêîãî ðèñêà
~
( ) || || ( , ( )) || || infR f f
m
c y f x fm k i i
i
m
k f� � � �
�
��
2
1
21
Hk
, (15)
100 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
ãäå Hk — íåêîòîðîå ÐÃÏ, ïîðîæäåííîå ÿäðîì k . Îêàçûâàåòñÿ, ÷òî ðåøåíèå ðå-
ãóëÿðèçîâàííîé çàäà÷è (15) â ÐÃÏ ñâîäèòñÿ ê çàäà÷å êîíå÷íîìåðíîé îïòèìèçà-
öèè, à äëÿ êóñî÷íî-ëèíåéíûõ ôóíêöèé ïîòåðü — ê çàäà÷å êâàäðàòè÷íîé îïòèìè-
çàöèè ïðè ëèíåéíûõ îãðàíè÷åíèÿõ.  ñèëó òàê íàçûâàåìîé òåîðåìû î ïðåä-
ñòàâëåíèè ðåøåíèÿ â ÐÃÏ [7, Theorem 4.2, p. 90; 26] ðåøåíèå çàäà÷è (15) ñóùåñò-
âóåò è ìîæåò áûòü ïðåäñòàâëåíî â âèäå
f x k x xm
i
m
i i
( ) ( , )�
�
�
1
, (16)
ãäå m
i�{ } — íåêîòîðûé íåèçâåñòíûé íàáîð äåéñòâèòåëüíûõ ÷èñåë, { }xi —
èçâåñòíûé íàáîð òî÷åê íàáëþäåíèÿ. Ïîäñòàâëÿÿ âûðàæåíèå (16) â (15) è èñïîëü-
çóÿ ðåïðîäóêòèâíîå ñâîéñòâî ÿäðà, ïðèõîäèì ê ñëåäóþùåé êîíå÷íîìåðíîé çàäà-
÷å îïòèìèçàöèè:
R
m
c y k x x k xm
m
i j i j
j
m
i
m
i j( ) , ( , ) (
�
�
�
�
�
�
�
�
�
�
��
��
1
11
i j
i j
m
x m, ) min
,
�
�
�
1
. (17)
Åñëè ôóíêöèÿ ïîòåðü c y( , )
âûïóêëà è íåîòðèöàòåëüíà, à ìàòðèöà { }k x xi j( , )
ïîëîæèòåëüíî îïðåäåëåíà, òî ýòà çàäà÷à èìååò åäèíñòâåííîå ðåøåíèå fm
. Â ðå-
øåíèè çàäà÷è (17) â ñèëó íàëè÷èÿ êâàäðàòè÷íîãî øòðàôà â öåëåâîé ôóíêöèè
çíà÷èòåëüíàÿ ÷àñòü êîýôôèöèåíòîâ ðàçëîæåíèÿ (16) ìîæåò áûòü ðàâíà íóëþ.
Âåêòîðû xi , ñîîòâåòñòâóþùèå íåíóëåâûì êîýôôèöèåíòàì ðàçëîæåíèÿ (16), íàçû-
âàþòñÿ îïîðíûìè âåêòîðàìè, à â öåëîì ìåòîä êëàññèôèêàöèè, îñíîâàííûé íà
ðåøåíèè çàäà÷ (15)–(17), íàçûâàåòñÿ ìåòîäîì îïîðíûõ âåêòîðîâ [1, 7]).
Îòìåòèì, ÷òî äëÿ íåãëàäêèõ êóñî÷íî-ëèíåéíûõ ôóíêöèé ïîòåðü, íàïðèìåð,
c y f x y f x( , ( )) | ( ) |� � , c y f x y f x( , ( )) max , ( )� �{ }0 1 , çàäà÷à (17) ÿâëÿåòñÿ âûïóêëîé
è íåãëàäêîé, îäíàêî ñ ïîìîùüþ äîïîëíèòåëüíûõ ïåðåìåííûõ îíà ëåãêî ñâîäèòñÿ
ê çàäà÷å êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ ïðè ëèíåéíûõ îãðàíè÷åíèÿõ. Äåòàëè
÷èñëåííîé ðåàëèçàöèè ìåòîäà ìîæíî íàéòè, íàïðèìåð, â [7, 27].
4. ÑÕÎÄÈÌÎÑÒÜ ÌÅÒÎÄÀ ÎÏÎÐÍÛÕ ÂÅÊÒÎÐÎÂ
ÏÐÈ ÍÅÎÃÐÀÍÈ×ÅÍÍÎÌ ÐÎÑÒÅ ×ÈÑËÀ ÍÀÁËÞÄÅÍÈÉ
Ðàññìîòðèì àñèìïòîòè÷åñêèå ñâîéñòâà ïðè m �
è
� 0 ðåøåíèé f xm
( ) çàäà÷è
ìèíèìèçàöèè ðåãóëÿðèçîâàííîãî ýìïèðè÷åñêîãî ðèñêà (15).  ðàáîòàõ [1, 4, 5]
âîïðîñ ñõîäèìîñòè R f R fm f F( ) inf ( )
� � èññëåäîâàí â ïðåäïîëîæåíèè îãðàíè-
÷åííîé åìêîñòè êëàññà ôóíêöèé F . Ïðèìåíåííûé ïîäõîä îñíîâàí íà óñòàíîâ-
ëåíèè óñëîâèé ðàâíîìåðíîé ïî f F� ñõîäèìîñòè ýìïèðè÷åñêèõ àïïðîêñèìà-
öèé ôóíêöèîíàëà ðèñêà R f
m
c z f xm i i
i
m
( ) ( , ( ))�
�
�
1
1
ê åãî èñòèííîìó çíà÷åíèþ
R f Ec z f x( ) ( , ( ))� , ò.å. sup | ( ) ( ) |f F mR f R f� � �
0 ïðè m �
. Îäíàêî íå âñåãäà
ïîäõîäÿùèé êëàññ ôóíêöèé èìååò êîíå÷íóþ åìêîñòü (êîíå÷íóþ ðàçìåðíîñòü
â ñìûñëå Âàïíèêà–×åðâîíåíêèñà [4]). Áîëåå ñëàáûå òðåáîâàíèÿ äëÿ ðàâíîìåðíîé íà
êëàññå ôóíêöèé ñõîäèìîñòè ýìïèðè÷åñêèõ ñðåäíèõ ê ôóíêöèîíàëó ðèñêà ìîæíî
ñôîðìóëèðîâàòü â òåðìèíàõ ñëîæíîñòè êëàññà ïî Ðàäåìàõåðó [9, ðàçä. 3]. Çàìåòèì,
÷òî óñëîâèå ðàâíîìåðíîé ñõîäèìîñòè àïïðîêñèìàöèé R fm
( ) ê R f( ) íå ÿâëÿåòñÿ
íåîáõîäèìûì äëÿ ñõîäèìîñòè ìèíèìóìîâ [28]. Ïîýòîìó ñëåäóåì äðóãîìó ïîäõîäó,
îñíîâàííîìó íà ñâîéñòâå óñòîé÷èâîñòè ðåãóëÿðèçîâàííûõ ðåøåíèé f xm
( ) ïî îòíî-
øåíèþ ê îòäåëüíûì íàáëþäåíèÿì. Ïîäîáíûé ïîäõîä èñïîëüçîâàëñÿ â [7, ðàçä.
12.1; 29, 30, 31], ãäå èññëåäîâàëàñü ñõîäèìîñòü îöåíîê ðèñêà ïî âåðîÿòíîñòè. Â îò-
ëè÷èå îò ýòèõ ðàáîò â äàííîé ñòàòüå óñòàíàâëèâàþòñÿ óñëîâèÿ íà
� ( )m , ïðè êî-
òîðûõ îöåíêè f xm
m
( ) ( ) ðàâíîìåðíî ïî x X� ñõîäÿòñÿ ñ âåðîÿòíîñòüþ åäèíèöà ê
ìèíèìóìó f * ôóíêöèîíàëà ðèñêà R f( ) , èìåþùåìó ìèíèìàëüíóþ íîðìó. Â ýòîì
ñìûñëå ïîñòðîåííûå êëàññèôèêàòîðû àñèìïòîòè÷åñêè óñòîé÷èâû.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 101
Ïðåäïîëîæåíèå 1 (ñâîéñòâà ôóíêöèè ïîòåðü). Ôóíêöèÿ ïîòåðü c y( , )
íåîòðè-
öàòåëüíà, âûïóêëà è ëèïøèöåâà ïî âòîðîìó àðãóìåíòó ñ êîíñòàíòîé L y íà ìíîæåñ-
òâå $ � � �{ }f x f F x X( ) | , .
Ïðåäïîëîæåíèå 2 (ñâîéñòâà ÿäðà). Ïîðîæäàþùåå ÿäðî k( , )
óäîâëåòâîðÿåò
óñëîâèþ sup | ( , ) |x X k x x K� � � �
2 .
Î÷åâèäíî, ôóíêöèè ïîòåðü c y f y f( , ) | |� � , c y f y f( , ) max ,� �{ }0 1 óäîâ-
ëåòâîðÿþò ïðåäïîëîæåíèþ 1 ïðè ëþáîì ìíîæåñòâå $ , à ôóíêöèÿ c y f y f( , ) ( )� � 2
óäîâëåòâîðÿåò ýòîìó ïðåäïîëîæåíèþ ïðè îãðàíè÷åííîì ìíîæåñòâå $ . Îáîçíà÷èì
L Ly Y y� �max , C c yy Y� �max ( , )0 . (18)
Ñëåäóþùàÿ òåîðåìà äàåò îöåíêó íåîïòèìàëüíîñòè (â ñðåäíåì) ïðèáëèæåííûõ
ðåøåíèé fm
êàê ôóíêöèþ m è
. Ýòè îöåíêè ÿâëÿþòñÿ ñëó÷àéíûìè âåëè÷èíàìè ñî
çíà÷åíèÿìè â ôóíêöèîíàëüíîì ïðîñòðàíñòâå Hk è îïðåäåëåíû íà ñ÷åòíîì ïðîèçâå-
äåíèè èñõîäíîãî âåðîÿòíîñòíîãî ïðîñòðàíñòâà ( , , )X B PX .
Òåîðåìà 4 [32, 33]. Ïóñòü ðåøåíèå çàäà÷è (14) ñóùåñòâóåò, ôóíêöèè fm
ÿâëÿ-
þòñÿ ðåøåíèÿìè çàäà÷è (15). Òîãäà â ñäåëàííûõ ïðåäïîëîæåíèÿõ äëÿ ëþáîãî
� �
è m èìååò ìåñòî îöåíêà
E R f R f
C L f
m
LK LK C
m
fm m( ) ( )
|| || ( )
|| ||*
*
*
� �
�
�
�
�
2
2 5 2
k
2 , (19)
ãäå ìàòåìàòè÷åñêîå îæèäàíèå Em áåðåòñÿ ïî âñåì âûáîðêàì { }z zm1 ,... , ñ íåçà-
âèñèìûìè îäèíàêîâî ðàñïðåäåëåííûìè íàáëþäåíèÿìè, f * — ëþáîå ðåøåíèå
çàäà÷è (14), || || sup | ( ) |*f f xx X
�� , || ||*f k — íîðìà ôóíêöèè f * â ïðîñòðàíñ-
òâå Hk .
Òåîðåìà ãàðàíòèðóåò ñõîäèìîñòü â ñðåäíåì âåëè÷èíû R fm( )
ê ìèíèìàëüíîìó
çíà÷åíèþ R f( )* ïðè
( )m � 0 è m m
( ) � 0, êîãäà m �
.
Óêàæåì óñëîâèÿ ñèëüíîé ñîñòîÿòåëüíîñòè îöåíîê f xm
( ) , ò.å. èõ ðàâíîìåðíîé
ïî x X� ñõîäèìîñòè ê íåêîòîðîìó ìèíèìóìó f x* ( ) ôóíêöèîíàëà ðèñêà R ïðè
� �( )m 0 è m �
.
Îïðåäåëåíèå 2 [24]. Ðåøåíèå f F* *� çàäà÷è íàçûâàåòñÿ íîðìàëüíûì, åñëè
îíî èìååò ìèíèìàëüíóþ íîðìó, || || min || ||*
*f fk f F k�
�
.
Ñëåäóþùèå äâå òåîðåìû èç [32, 33] äàþò äîñòàòî÷íûå óñëîâèÿ ðàâíîìåðíîé
ñõîäèìîñòè ñ âåðîÿòíîñòüþ åäèíèöà ïðèáëèæåííûõ ðåøåíèé fm
m
( ) ê íîðìàëüíîìó
ðåøåíèþ f F* *� çàäà÷è (14), ò.å. lim sup | ( ) ( ) |( ) *
m x X m
mf x f x�
� � �
0.
Òåîðåìà 5 (äîñòàòî÷íûå óñëîâèÿ ñèëüíîé ñîñòîÿòåëüíîñòè ìåòîäà îïîðíûõ âåê-
òîðîâ). Ïóñòü ðåøåíèå çàäà÷è (14) ñóùåñòâóåò è âûïîëíåíû ïðåäïîëîæåíèÿ 1, 2. Ðàñ-
ñìîòðèì ñåìåéñòâî ðåøåíèé fm
m
( ) çàäà÷è (15), ïðè÷åì lim ( )m m�
�
0. Òîãäà åñëè
lim ( ) / lnm m m m�
�
2 , òî R f R fm
m( ) ( )( ) *
� . Åñëè lim ( ) /m m m�
4
/ ln m �
, òî R f R fm
m( ) ( )( ) *
� è ðåøåíèÿ fm
m
( ) çàäà÷è (15) ðàâíîìåðíî ïî x X�
ñõîäÿòñÿ ê íîðìàëüíîìó ðåøåíèþ f * çàäà÷è (14) ñ âåðîÿòíîñòüþ åäèíèöà ïðè
m � �
.
Òåîðåìà 6 (îöåíêà ñêîðîñòè ñõîäèìîñòè ìåòîäà îïîðíûõ âåêòîðîâ). Ïóñòü
â óñëîâèÿõ ïðåäûäóùåé òåîðåìû
�( ) (ln ) / /m m m� % 1 4 , % 0, 1 4 1/ � �� , òîãäà
ñïðàâåäëèâû óòâåðæäåíèÿ òåîðåìû 5 è èìååò ìåñòî îöåíêà
E R f R fm m
m( ) ( )( ) *
� �
�
�
�
�
�
2
2 5 2 2
4
2
C L f
m
LK LK C
m m
f m
k|| || ( )
(ln )
|| || (ln* *
%
%
%
�
)�
m4
. (20)
102 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
5. ÝÔÔÅÊÒÈÂÍÎÑÒÜ ÌÅÒÎÄÀ ÎÏÎÐÍÛÕ ÂÅÊÒÎÐÎÂ ÏÐÈ ÐÅØÅÍÈÈ
ÇÀÄÀ× ÁÈÍÀÐÍÎÉ ÊËÀÑÑÈÔÈÊÀÖÈÈ
Ñ ïîìîùüþ ðåøåíèÿ fm
çàäà÷è (15) ñîîòâåòñòâóþùèé áèíàðíûé êëàññèôèêàòîð
ñòðîèòñÿ ñëåäóþùèì îáðàçîì:
(21)
Äëÿ çàäàííîé îáó÷àþùåé âûáîðêè ýôôåêòèâíîñòü êëàññèôèêàòîðà èçìåðÿåòñÿ
âåëè÷èíîé âåðîÿòíîñòè îøèáêè êëàññèôèêàöèè
&m m f FP I f x y P I f x y
� � � ��{ } { }1 2 1 2/ /( ( )) min ( ( )) ,
êîòîðàÿ îöåíèâàåòñÿ ñâåðõó ÷åðåç ðàçíîñòè [ ( ) ( ) ]*R f R fm
� ñîãëàñíî íåðàâåíñò-
âàì (4), (9) èç òåîðåì 1, 2, ïðè óñëîâèè, ÷òî óñëîâíûå ìåäèàíû è ñðåäíèå ïðè-
íàäëåæàò äîïóñòèìîìó ìíîæåñòâó F çàäà÷è ìèíèìèçàöèè ðèñêà (14). Äëÿ ïîëó-
÷åíèÿ ñðåäíåé âåðîÿòíîñòè îøèáêè êëàññèôèêàöèè íåîáõîäèìî âçÿòü ìàòåìàòè-
÷åñêîå îæèäàíèå Em m&
ïî âñåì íåçàâèñèìûì îáó÷àþùèì âûáîðêàì { }( , )y xi i
îáúåìà m .  ñâîþ î÷åðåäü, ñðåäíåå çíà÷åíèå [ ( ) ( ) ]*E R f R fm m
� îøèáêè ìèíè-
ìèçàöèè ôóíêöèîíàëà ðèñêà ïî âñåì âîçìîæíûì îáó÷àþùèì âûáîðêàì îöåíèâà-
åòñÿ íåðàâåíñòâàìè (19), (20) èç òåîðåì 4, 6. Òàêèì îáðàçîì, ïðèõîäèì ê ñëåäó-
þùèì ðåçóëüòàòàì.
Òåîðåìà 7 (îöåíêà ýôôåêòèâíîñòè ìåòîäà îïîðíûõ âåêòîðîâ ïðè èñïîëüçîâà-
íèè íåãëàäêîãî ôóíêöèîíàëà ðèñêà L f1 ( )). Ïðåäïîëîæèì, ÷òî óñëîâíàÿ ìåäèàíà
f x* ( ) âåðîÿòíîñòíîãî ðàñïðåäåëåíèÿ P íåçàâèñèìûõ ýëåìåíòîâ îáó÷àþùåé âûáîðêè
{ }( , )y xi i ïðèíàäëåæèò ïîäìíîæåñòâó F íåêîòîðîãî ðåïðîäóêòèâíîãî ãèëüáåðòîâà
ïðîñòðàíñòâà Hk ñ ïîðîæäàþùèì ÿäðîì k . Äëÿ áèíàðíîãî êëàññèôèêàòîðà (21), ãäå
ôóíêöèÿ f xm
( ) ÿâëÿåòñÿ ðåøåíèåì çàäà÷è (15) ñ ôóíêöèåé ïîòåðü c y f y f( , ) | |� �
èëè c y f y f( , ) max ,� �{ }0 1 , ñðåäíÿÿ ïî âñåì îáó÷àþùèì âûáîðêàì { }( , )y xi i îáúåìà m
îøèáêà êëàññèôèêàöèè îöåíèâàåòñÿ ñëåäóþùèì îáðàçîì:
E
C L f
m
LK LK C
m
fm m k
&
�
�
�
�
�
4
2 2 5 2
2 2|| || ( )
|| ||
*
* .
Çäåñü êîíñòàíòû L C, îïðåäåëåíû â (18), êîíñòàíòà K îïðåäåëåíà â ïðåäïîëîæå-
íèè 2. Ïðè
( ) ln / /m m m� % 1 4 , % 0, ýòà îöåíêà ïðèíèìàåò âèä
E
C L f
m
LK LK C
m m
f
m m
k&
%
%
�
�
�
�
�
4
2 2 5 2 2 2
4
|| || ( )
(ln )
|| ||* * 2
4
%(ln )m
m
.
Òåîðåìà 8 (îöåíêà ýôôåêòèâíîñòè ìåòîäà îïîðíûõ âåêòîðîâ ïðè èñïîëüçîâà-
íèè êâàäðàòè÷íîãî ôóíêöèîíàëà ðèñêà L f2 ( )). Ïðåäïîëîæèì, ÷òî óñëîâíîå ñðåä-
íåå p x P y x E y x1 1( ) | |� � �{ } { } âåðîÿòíîñòíîãî ðàñïðåäåëåíèÿ P íåçàâèñèìûõ
ýëåìåíòîâ îáó÷àþùåé âûáîðêè { }( , )y xi i ïðèíàäëåæèò ïîäìíîæåñòâó F íåêîòî-
ðîãî ðåïðîäóêòèâíîãî ãèëüáåðòîâà ïðîñòðàíñòâà Hk ñ ïîðîæäàþùèì ÿäðîì k .
Äëÿ áèíàðíîãî êëàññèôèêàòîðà (21), ãäå ôóíêöèÿ f xm
( ) ÿâëÿåòñÿ ðåøåíèåì çàäà-
÷è (15) ñ êâàäðàòè÷íîé ôóíêöèåé ïîòåðü c y f y f( , ) ( ) ,� � 2 ñðåäíÿÿ ïî âñåì îáó-
÷àþùèì âûáîðêàì îáúåìà m îøèáêà êëàññèôèêàöèè îöåíèâàåòñÿ ñëåäóþùèì
îáðàçîì:
E
C L p
m
LK LK C
m
pm m k
&
�
�
�
�
�
�
�
�
�
�
�
2 2
2 5 21
1
2|| || ( )
|| || �
�
1 2/
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 103
��
�
�
�
�
.ñëó÷àåïðîòèâíîìâ0
,2/1)(,1
))((2/1
xf
xfI
m
m
Çäåñü êîíñòàíòû L C, îïðåäåëåíû â (18), êîíñòàíòà K îïðåäåëåíà â ïðåäïîëîæå-
íèè 2. Ïðè
( ) ln / /m m m� % 1 4 , % 0, ýòà îöåíêà ïðèíèìàåò âèä
E
C L p
m
LK LK C
m m
p
m m
k&
%
%
%
�
�
�
�
�
2
2 5 2 21
4
1
2
|| || ( )
(ln )
|| || ln
/
m
m4
1 2
�
�
�
�
�
�
�
�
.
ÇÀÊËÞ×ÅÍÈÅ
Èç ðåçóëüòàòîâ íàñòîÿùåé ñòàòüè ìîæíî ñäåëàòü íåñêîëüêî âûâîäîâ, êàñàþùèõñÿ
ïðèìåíåíèÿ ìåòîäà îïîðíûõ âåêòîðîâ äëÿ ðåøåíèÿ çàäà÷ áèíàðíîé êëàññèôèêàöèè.
Ïðè èñïîëüçîâàíèè ìåòîäà îïîðíûõ âåêòîðîâ âàæíî ïðàâèëüíî îïðåäåëèòü
êëàññ ôóíêöèé F è ïðîñòðàíñòâî H F' , êîòîðûì ïðèíàäëåæàò óñëîâíûå ìåäèàíû
è óñëîâíîå ñðåäíåå âåðîÿòíîñòíîãî ðàñïðåäåëåíèÿ ýëåìåíòîâ îáó÷àþùåé âûáîðêè.
 ýòîì ñëó÷àå ãîâîðÿò îá îòñóòñòâèè îøèáêè àïïðîêñèìàöèè ìåäèàíû è ñðåäíåãî
ôóíêöèÿìè èç F H( . Ïîñêîëüêó òåîðåòè÷åñêîå ðàñïðåäåëåíèå îáó÷àþùèõ äàííûõ
íåèçâåñòíî, à èìååòñÿ òîëüêî êîíå÷íàÿ âûáîðêà íàáëþäåíèé ñ ýòèì ðàñïðåäåëåíè-
åì, âûáîð ïðîñòðàíñòâà H è åãî ïîäìíîæåñòâà F äëÿ êîíêðåòíîé ðåàëèçàöèè ìåòî-
äà îïîðíûõ âåêòîðîâ íå ÿâëÿåòñÿ ôîðìàëèçîâàííûì àêòîì. Åñëè F H Hk� � —
íåêîòîðîå ÐÃÏ ôóíêöèé, òî ïîñòðîåíèå êëàññèôèêàòîðà ñâîäèòñÿ ê ðåøåíèþ
çàäà÷è êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ.
Ìåòîä îïîðíûõ âåêòîðîâ ÿâëÿåòñÿ ñîñòîÿòåëüíûì (â ñëó÷àå îòñóòñòâèÿ îøèá-
êè àïïðîêñèìàöèè), à èìåííî, ïðè âûáîðå ïàðàìåòðà ðåãóëÿðèçàöèè
( )m ñîãëàñíî
óñëîâèÿì lim ( )m m�
�
0 è lim ( )m m m�
�
âåðîÿòíîñòü îøèáî÷íîé êëàññè-
ôèêàöèè ñòðåìèòñÿ ê òåîðåòè÷åñêîìó ìèíèìóìó (â ñðåäíåì è ïî âåðîÿòíîñòè) äëÿ
ëþáîãî ðàñïðåäåëåíèÿ îáó÷àþùèõ äàííûõ. Îäíàêî ïîëó÷åííûå îöåíêè ñêîðîñòè
ñõîäèìîñòè ñðåäíåé îøèáêè êëàññèôèêàöèè ê ìèíèìóìó ñîäåðæàò íåèçâåñòíûå
êîíñòàíòû ( || ||*f
, || ||*f k , || ||p1
, || ||p
k1
2 ), çàâèñÿùèå îò âåðîÿòíîñòíîãî ðàñ-
ïðåäåëåíèÿ ýëåìåíòîâ îáó÷àþùåé âûáîðêè.
Ñêîðîñòü ñõîäèìîñòè ê ìèíèìóìó ñðåäíåé âåðîÿòíîñòè îøèáî÷íîé êëàññèôèêà-
öèè (ïðè óâåëè÷åíèè îáúåìà m îáó÷àþùåé âûáîðêè) ìåòîäîì îïîðíûõ âåêòîðîâ
ïðè èñïîëüçîâàíèè ôóíêöèîíàëà àáñîëþòíîãî îòêëîíåíèÿ L f1 ( ) èìååò ïîðÿäîê
const / m4 , à êâàäðàòè÷íîãî ôóíêöèîíàëà ðèñêà L f2 ( ) — ïîðÿäîê const / m8 . Îöåíêè
ñêîðîñòè ñõîäèìîñòè íå ñîäåðæàò â ÿâíîì âèäå ðàçìåðíîñòè ïðèçíàêîâîãî ïðîñòðà-
íñòâà (ðàçìåðíîñòè âåêòîðà x ), îäíàêî ýòà ðàçìåðíîñòü ìîæåò âõîäèòü â îöåíêè
÷åðåç êîíñòàíòó K , õàðàêòåðèçóþùóþ ïîðîæäàþùåå ÿäðî k ïðîñòðàíñòâà Hk .
Íàïðèìåð, äëÿ ïîëèíîìèàëüíîãî ÿäðà âèäà k x x x x q( , ) ( , )) � � � ) 1 , q �1, è n -ìåðíî-
ãî âåêòîðà x ñ áèíàðíûìè êîìïîíåíòàìè ñîîòâåòñòâóþùàÿ êîíñòàíòà èìååò âèä
K n q� �( )1 .  çàêëþ÷åíèå çàìåòèì, ÷òî ïðè áîëåå ñèëüíûõ ïðåäïîëîæåíèÿõ íà ðàñ-
ïðåäåëåíèå P îáó÷àþùèõ äàííûõ ñêîðîñòü ñõîäèìîñòè ìåòîäà îïîðíûõ âåêòîðîâ
ìîæåò áûòü çíà÷èòåëüíî âûøå, ÷åì â òåîðåìàõ 7, 8, íàïðèìåð ïîðÿäêà const / m [9].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. V a p n i k V . N . Statistical learning theory. — New York: Wiley, 1998. — 736 p.
2. D e v r o y e L . , G y o r f i�� L . , L u g o s i G . A probabilistic theory of pattern recognition. — New York:
Springer, 1996. — 634 p.
3. S t o n e C . Consistent nonparametric regression // Ann. Statistics. — 1977. — 5. — P. 595–645.
4.  à ï í è ê  . Í . , × å ð â î í å í ê è ñ À . ß . Òåîðèÿ ðàñïîçíàâàíèÿ îáðàçîâ. Ñòàòèñòè÷åñêèå ïðîáëå-
ìû îáó÷åíèÿ. — Ì.: Íàóêà, 1974. — 416 ñ.
5.  à ï í è ê  . Í . Âîññòàíîâëåíèå çàâèñèìîñòåé ïî ýìïèðè÷åñêèì äàííûì. — Ì.: Íàóêà, 1979. —
448 ñ.
6. Àé ç å ð ì à í Ì . À . , Á ð à â å ð ì à í Ý . Ì . , Ð î ç î í î ý ð Ë . È . Ìåòîä ïîòåíöèàëüíûõ ôóíêöèé
â òåîðèè îáó÷åíèÿ ìàøèí. — Ì.: Íàóêà, 1970. — 384 ñ.
104 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
7. S c h o e l k o p f�� B . , S m o l a A . J . Learning with kernels. Support vector machines, regularization, op-
timization, and beyond. — Cambridge (MA): MIT Press, 2002. — 626 p.
8. S t e i n w a r t I . , C h r i s t m a n n A . Support vector machines. — New York: Springer, 2008. — 602 p.
9. B o u c h e r o n S . , B o u s q u e t O . , L u g o s i G . Theory of classification: A survey of some recent
advances // ESAIM: Probability and Statistics. — 2005. — 9. — P. 323–375.
10. Ø ë å ç è í ã å ð Ì . , à ë à â à ÷  . Äåñÿòü ëåêöèé ïî ñòàòèñòè÷åñêîìó è ñòðóêòóðíîìó ðàñïîçíàâà-
íèþ. — Êèåâ: Íàóê. äóìêà, 2004. — 536 c.
11. G y o r f i�� L . , K o h l e r M . , K r z y z a k A . , W a l k H . A distribution free theory of nonparametric
regression. — New York; Berlin; Heidelberg: Springer, 2002. — 647 p.
12. Ã ó ï à ë A . M . , Ï à ø ê î Ñ . Â . , Ñ å ð ã è å í ê î È . Â . Ýôôåêòèâíîñòü áàéåñîâñêîé ïðîöåäóðû
êëàññèôèêàöèè îáúåêòîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1995. — ¹ 4. — Ñ. 76–89.
13. Ñ å ð ã è å í ê î È . Â . , Ã ó ï à ë À . Ì . Îïòèìàëüíûå ïðîöåäóðû ðàñïîçíàâàíèÿ è èõ ïðèìåíåíèå //
Òàì æå. — 2007. — ¹ 6. — C. 41–54.
14. Ã ó ï à ë À . Ì . , Ñ å ð ã è å í ê î È . Â . Îïòèìàëüíûå ïðîöåäóðû ðàñïîçíàâàíèÿ. — Êèåâ: Íàóê. äóì-
êà, 2008. — 232 ñ.
15. P o g g i o T . , S m a l e S . The mathematics of learning: Dealing with data // Notices Amer. Math. Soc. —
2003. — 50, N 5. — P. 537–544.
16. K o e n k e r R . , B a s s e t t G . W . Regression quantiles // Econometrica. — 1978. — 46. — P. 33–50.
17. K o e n k e r R . Quantile regression. — Cambridge; New York: Cambridge Univ. Press, 2005. — 366 p.
18. Å ð ì î ë ü å â Þ . Ì . , ß ñ ò ð å ì ñ ê è é À . È . Ñòîõàñòè÷åñêèå ìîäåëè è ìåòîäû â ýêîíîìè÷åñêîì
ïëàíèðîâàíèè. — Ì.: Íàóêà, 1979. — 254 ñ.
19. E r m o l i e v Y . M . , L e o n a r d i G . Some proposals for stochastic facility location models // Math.
Modelling. — 1982. — 3. — P. 407–420.
20. R u s z c z y n s k i A . , S h a p i r o A . (Eds.) Stochastic programming // Handbooks in OR & MS. — Am-
sterdam: Elsevier, 2003. — 10. — 682 p.
21. C u c k e r F . , S m a l e S . On the mathematiñal foundations of learning // Bull. Amer. Math. Soc. —
2001. — 89, N 1. — P. 1–49.
22. À ð î í ø à é í Í . Òåîðèÿ âîñïðîèçâîäÿùèõ ÿäåð // Ìàòåìàòèêà (Ïåðèîä. cá. ïåðåâîä. èíîñòð. ñòà-
òåé). — Ì.: Èçä-âî èíîñòð. ëèò., 1963. — 7, ¹ 2. — Ñ. 67–130.
23. B e r l i n e t A . , T h o m a s - A g n a n C . Reproducing kernel Hilbert spaces in probability and statistics.
— Dordrecht; Boston; London: Kluwer Acad. Publ., 2004. — 355 p.
24. Ò è õ î í î â À . Í . , À ð ñ å í è í Â . ß . Ìåòîäû ðåøåíèÿ íåêîððåêòíûõ çàäà÷. — Èçä. 3-å, èñïð. —
Ì.: Íàóêà, 1986. — 288 ñ.
25.  à ñ è ë ü å â Ô . Ï . Ìåòîäû ðåøåíèÿ ýêñòðåìàëüíûõ çàäà÷. Çàäà÷è ìèíèìèçàöèè â ôóíêöèîíàëüíûõ
ïðîñòðàíñòâàõ, ðåãóëÿðèçàöèÿ, àïïðîêñèìàöèÿ. — Ì.: Íàóêà, 1981. — 400 ñ.
26. W a h b a G . Spline models for observational data // CBMS-NSF Reg. Conf. Series in Applied Mathe-
matics. — Philadelphia (PA): SIAM, 1990. — 59. — 169 p.
27. K e y z e r M . A . Rule-based and support vector (SV-) regression/classification algorithms for joint pro-
cessing of census, map, survey and district data: (Working Paper) / Centre for World Food Studies. —
WP-05-01. — Amsterdam, 2005. — 88 p. (http://www.sow.vu.nl/pdf/wp05.01.pdf)
28. R o c k a f e l l a r R . T . , W e t s R . J . - B . Variational analysis. — Berlin: Springer, 1998. — 733 p.
29. B o u s q u e t O . , E l i s s e e f f A . Stability and generalization // J. Mach. Learn. Res. — 2002. — 2. —
P. 499–526.
30. S m a l e S . , Z h o u D . X . Shannon sampling. II: Connections to learning theory // Appl. Comput. Har-
mon. Anal. — 2005. — 19, N 3. — P. 285–302.
31. D e V i t o E . , C a p o n n e t t o A . , R o s a s c o L . Model selection for regularized least-squares algo-
rithm in learning theory // Found. Comput. Math. — 2005. — 5, N 1. — P. 59–85.
32. N o r k i n V . I . , K e y z e r M . A . On convergence of kernel learning estimators // Proc. of 20th EURO
Mini Conf. «Continuous Optimization and Knowledge-Based Technologies» (EUROPT-2008) / L. Sakala-
uskas, O.W. Weber and E.K. Zavadskas (Eds.). — Vilnius: Inst. of Math. and Inform., 2008. —
P. 306–310.
33. Í î ð ê è í  . È . , Ê à é ç å ð Ì . À . Îá àñèìïòîòè÷åñêîé ýôôåêòèâíîñòè ÿäåðíîãî ìåòîäà îïîðíûõ
âåêòîðîâ (SVM) // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2009. — ¹ 4. — Ñ. 81–97.
Ïîñòóïèëà 02.12.2008
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 105
|
| id | nasplib_isofts_kiev_ua-123456789-44404 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T15:20:56Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Норкин, В.И. Кайзер, М.А. 2013-06-01T08:24:18Z 2013-06-01T08:24:18Z 2009 Об эффективности методов классификации, основанных на минимизации эмпирического риска / В.И. Норкин, М.А. Кайзер // Кибернетика и системный анализ. — 2009. — № 5. — С. 93-105. — Бібліогр.: 33 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44404 519:234:24:85 Задачу бінарної класифікації зведено до мінімізації опуклих функціоналів регуляризованого емпіричного ризику у репродуктивному гільбертовому просторі. Розв’язок цієї задачі шукається у вигляді лінійної комбінації ядерних опорних функцій (метод опорних векторів Вапника). Отримано оцінки ризику помилкової класифікації як функції об’єму навчальної вибірки та інших параметрів моделі. A binary classification problem is reduced to the minimization of convex regularized empirical risk functionals in a reproducing kernel Hilbert space. The solution is searched for in the form of a finite linear combination of kernel support functions (support vector machines of Vapnik). Risk estimates for a misclassification as a function of a training sample volume and other model parameters are obtained. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Об эффективности методов классификации, основанных на минимизации эмпирического риска Про ефективність методів класифікації, що базуються на мінімізації емпіричного ризику On the efficiency of classification methods based on empirical risk minimization Article published earlier |
| spellingShingle | Об эффективности методов классификации, основанных на минимизации эмпирического риска Норкин, В.И. Кайзер, М.А. Системный анализ |
| title | Об эффективности методов классификации, основанных на минимизации эмпирического риска |
| title_alt | Про ефективність методів класифікації, що базуються на мінімізації емпіричного ризику On the efficiency of classification methods based on empirical risk minimization |
| title_full | Об эффективности методов классификации, основанных на минимизации эмпирического риска |
| title_fullStr | Об эффективности методов классификации, основанных на минимизации эмпирического риска |
| title_full_unstemmed | Об эффективности методов классификации, основанных на минимизации эмпирического риска |
| title_short | Об эффективности методов классификации, основанных на минимизации эмпирического риска |
| title_sort | об эффективности методов классификации, основанных на минимизации эмпирического риска |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/44404 |
| work_keys_str_mv | AT norkinvi obéffektivnostimetodovklassifikaciiosnovannyhnaminimizaciiémpiričeskogoriska AT kaizerma obéffektivnostimetodovklassifikaciiosnovannyhnaminimizaciiémpiričeskogoriska AT norkinvi proefektivnístʹmetodívklasifíkacííŝobazuûtʹsânamínímízacííempíričnogoriziku AT kaizerma proefektivnístʹmetodívklasifíkacííŝobazuûtʹsânamínímízacííempíričnogoriziku AT norkinvi ontheefficiencyofclassificationmethodsbasedonempiricalriskminimization AT kaizerma ontheefficiencyofclassificationmethodsbasedonempiricalriskminimization |