Алгоритмические аспекты определения функций глубины в процедуре выбора оптимальной гипотезы для задач классификации данных
Исследуются проблемы выбора оптимальной гипотезы в задачах классификации на основе класса гипотез, распределенного относительно апостериорной вероятности. Предложен метод, базирующийся на концепции относительного взвешенного среднего значения и функциях глубины, которые выполняются в пространстве фу...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2016 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/142015 |
| 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: | Алгоритмические аспекты определения функций глубины в процедуре выбора оптимальной гипотезы для задач классификации данных / А.А. Галкин // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 43-55. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860253339451654144 |
|---|---|
| author | Галкин, А.А. |
| author_facet | Галкин, А.А. |
| citation_txt | Алгоритмические аспекты определения функций глубины в процедуре выбора оптимальной гипотезы для задач классификации данных / А.А. Галкин // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 43-55. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Исследуются проблемы выбора оптимальной гипотезы в задачах классификации на основе класса гипотез, распределенного относительно апостериорной вероятности. Предложен метод, базирующийся на концепции относительного взвешенного среднего значения и функциях глубины, которые выполняются в пространстве функций классификации. Разработаны алгоритмы для аппроксимации относительной глубины данных и относительного взвешенного среднего значения, обеспечивающие полиномиальные приближения к полупространственным аналогам.
Досліджуються проблеми вибору оптимальної гіпотези в задачах класифікації на основі класу гіпотез, розподіленого відносно апостеріорної ймовірності. Запропоновано метод, який базується на концепції відносного зваженого середнього значення та функціях глибини, що виконуються у просторі функцій класифікації. Розроблено алгоритми для апроксимації відносної глибини даних та відносного зваженого середнього значення, що забезпечують поліноміальні наближення до напівпросторових аналогів.
The paper analyzes optimal hypothesis selection in classification problems based on the hypothesis class distributed with respect to the posterior probability. A method is proposed that is based on the concept of a relative weighted average value and depth functions operating in the space of classification functions. Algorithms are constructed to approximate the relative depth of the data and relative weighted average value providing polynomial approximation to the half-space analogs.
|
| first_indexed | 2025-12-07T18:46:02Z |
| format | Article |
| fulltext |
ÓÄÊ 519.7
À.À. ÃÀËÊÈÍ
ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅ ÀÑÏÅÊÒÛ ÎÏÐÅÄÅËÅÍÈß ÔÓÍÊÖÈÉ
ÃËÓÁÈÍÛ Â ÏÐÎÖÅÄÓÐÅ ÂÛÁÎÐÀ ÎÏÒÈÌÀËÜÍÎÉ ÃÈÏÎÒÅÇÛ
ÄËß ÇÀÄÀ× ÊËÀÑÑÈÔÈÊÀÖÈÈ ÄÀÍÍÛÕ
Àííîòàöèÿ. Èññëåäóþòñÿ ïðîáëåìû âûáîðà îïòèìàëüíîé ãèïîòåçû â çàäà-
÷àõ êëàññèôèêàöèè íà îñíîâå êëàññà ãèïîòåç, ðàñïðåäåëåííîãî îòíîñèòåëüíî
àïîñòåðèîðíîé âåðîÿòíîñòè. Ïðåäëîæåí ìåòîä, áàçèðóþùèéñÿ íà êîíöåïöèè
îòíîñèòåëüíîãî âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ è ôóíêöèÿõ ãëóáèíû, êîòî-
ðûå âûïîëíÿþòñÿ â ïðîñòðàíñòâå ôóíêöèé êëàññèôèêàöèè. Ðàçðàáîòàíû àë-
ãîðèòìû äëÿ àïïðîêñèìàöèè îòíîñèòåëüíîé ãëóáèíû äàííûõ è îòíîñèòåëü-
íîãî âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ, îáåñïå÷èâàþùèå ïîëèíîìèàëüíûå
ïðèáëèæåíèÿ ê ïîëóïðîñòðàíñòâåííûì àíàëîãàì.
Êëþ÷åâûå ñëîâà: âçâåøåííîå ñðåäíåå çíà÷åíèå, ôóíêöèÿ îòíîñèòåëüíîé
ãëóáèíû, îïòèìàëüíàÿ ãèïîòåçà Áàéåñà.
ÂÂÅÄÅÍÈÅ
Íàðÿäó ñ îòêðûòûìè ïðîáëåìàìè ìàøèííîãî îáó÷åíèÿ îäíîé èç àêòóàëüíûõ
çàäà÷ ìíîãîìåðíîé êëàññèôèêàöèè ÿâëÿåòñÿ âûáîð îïòèìàëüíîé ãèïîòåçû.
Ñóùåñòâóþùèå ìåòîäû ðåøåíèÿ äàííîé ïðîáëåìû èìåþò îãðàíè÷åíèÿ îòíîñè-
òåëüíî âîñïðîèçâîäèìîñòè ðåçóëüòàòîâ, ÷òî îáóñëîâëåíî ñòîõàñòè÷íîñòüþ â ïðî-
ãíîçíûõ ìîäåëÿõ. Êðîìå òîãî, ïðè èñïîëüçîâàíèè áîëüøèíñòâà òàêèõ ìåòîäîâ
äîñòàòî÷íî ðàñïðîñòðàíåííûì ôàêòîðîì ÿâëÿåòñÿ âîçìîæíîñòü ïðèìåíåíèÿ ãèïî-
òåçû òîëüêî èç çàäàííîãî êëàññà, ÷òî âûçâàíî õàðàêòåðíûìè ïðàêòè÷åñêèìè îãðà-
íè÷åíèÿìè. Ó÷èòûâàÿ íåäîñòàòêè ñóùåñòâóþùèõ ìåòîäîâ, â äàííîé ñòàòüå ïðåä-
ëàãàåòñÿ íîâûé ìåòîä ðåøåíèÿ ïðîáëåìû âûáîðà îïòèìàëüíîé ãèïîòåçû äëÿ ýô-
ôåêòèâíîãî îáîáùåíèÿ íà îñíîâå àïîñòåðèîðíîé âåðîÿòíîñòè.  êà÷åñòâå êðèòåðèÿ
äëÿ âûáîðà ãèïîòåçû èñïîëüçóåòñÿ êîíöåïöèÿ ãëóáèíû äàííûõ, â êîòîðîé äëÿ íà-
õîæäåíèÿ íàèáîëåå ãëóáîêîé ôóíêöèè ïðèìåíÿþòñÿ ñîîòâåòñòâóþùèå ìåòîäû àï-
ïðîêñèìàöèè. Ñ ó÷åòîì ïîëó÷åííûõ ðåçóëüòàòîâ èññëåäîâàíû àëãîðèòìè÷åñêèå àñ-
ïåêòû îïðåäåëåíèÿ ôóíêöèé ãëóáèíû è ïðåäëîæåíû àëãîðèòìû äëÿ ðàâíîìåðíîé
àïïðîêñèìàöèè ãëóáèíû íà îáùåì êëàññå ôóíêöèé, à òàêæå àëãîðèòìû äëÿ àï-
ïðîêñèìàöèè âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ.
ÔÓÍÊÖÈÈ ÃËÓÁÈÍÛ Â ÏÐÎÖÅÄÓÐÅ ÂÛÁÎÐÀ ÎÏÒÈÌÀËÜÍÎÉ ÃÈÏÎÒÅÇÛ
Ñóòü íîâîãî ìåòîäà çàêëþ÷àåòñÿ â àíàëèçå ôóíêöèé ãëóáèíû, ôóíêöèîíèðóþ-
ùèõ â ñîïðÿæåííîì ïðîñòðàíñòâå (ïðîñòðàíñòâå ôóíêöèé êëàññèôèêàöèè),
âìåñòî èõ èññëåäîâàíèÿ â ïðîñòðàíñòâå õàðàêòåðèñòèê.  äàííîì ñëó÷àå ôóíê-
öèÿ ãëóáèíû, îïðåäåëÿþùàÿ ñîãëàñîâàííîñòü ôóíêöèè h ñî âçâåøåííûì ìàæî-
ðèòàðíûì ãîëîñîâàíèåì íà z, âñåãäà áóäåò èìåòü âûñîêóþ ñòåïåíü ñîãëàñî-
âàííîñòè ñ åå ôóíêöèåé ïðîãíîçèðîâàíèÿ â êëàññå H.
Ðàññìîòðèì ìîäåëü z�Z. Îòíîñèòåëüíàÿ ãëóáèíà ôóíêöèè h îòíîñèòåëüíî P
îïðåäåëÿåòñÿ êàê
E h z P c z h z
c
P
P
( | ) [ ( ) ( )]� �
�
,
ãäå H — êëàññ ôóíêöèé, P — âåðîÿòíîñòíàÿ ìåðà íà H. Çàìåòèì, ÷òî â îáùåì
ñëó÷àå îòíîñèòåëüíàÿ ãëóáèíà ôóíêöèè h îòíîñèòåëüíî P îïðåäåëÿåòñÿ êàê
E h E h z P c z h z
z z c
P
Z
P
Z P
inf inf( ) ( | ) [ ( ) ( )]� � �
� � �
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 43
� À.À. Ãàëêèí, 2016
Ââåäåì ïîíÿòèå îòíîñèòåëüíîãî âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ íà îñíîâå
êëàññà ôóíêöèé H , íà êîòîðîì îïðåäåëåíà âåðîÿòíîñòíàÿ ìåðà P. Ïðè óñëîâèè,
÷òî E h E hP P( ) ( )*� , âåëè÷èíà h* ÿâëÿåòñÿ îòíîñèòåëüíûì âçâåøåííûì ñðåäíèì
çíà÷åíèåì íà H îòíîñèòåëüíî P � �h H. Îòìåòèì, ÷òî âçâåøåííîå ñðåäíåå çíà÷å-
íèå âñåãäà ñóùåñòâóåò äëÿ êàæäîé âåðîÿòíîñòíîé ìåðû P òîëüêî ïðè óñëîâèè,
÷òî êëàññ H çàìêíóò. Íåñìîòðÿ íà òî ÷òî èíôèìóìîì ïî âñåì òî÷êàì z�Z ÿâëÿ-
åòñÿ ãëóáèíà E hP ( ) è áîëüøèíñòâî èññëåäóåìûõ ìîäåëåé èìåþò äîñòàòî÷íî
áîëüøóþ ãëóáèíó, áóäåì äîïóñêàòü ñóùåñòâîâàíèå ìîäåëåé z�Z, èìåþùèõ
íåáîëüøóþ ãëóáèíó.
Äàëåå ïðåäïîëîæèì, ÷òî � — âåðîÿòíîñòíàÿ ìåðà íà Z, à � � 0. Äëÿ îñëàá-
ëåíèÿ èíôèìóìà â îïðåäåëåíèè ãëóáèíû ââåäåì ïîíÿòèå �-ýôôåðåíòíîé ãëóáèíû h
îòíîñèòåëüíî P è �, îïðåäåëÿåìîå êàê
E h E h z
Z Z z ZP
Z Z
Pinf� �
� �
,
, ( ) \ '
( ) sup ( | )�
� �
,
ãäå H — êëàññ ôóíêöèé, P — âåðîÿòíîñòíàÿ ìåðà íà H. Îòìåòèì, ÷òî ôóíê-
öèÿ �-ýôôåðåíòíîé ãëóáèíû óñòàíàâëèâàåò âûñîêóþ ñòåïåíü ñîãëàñîâàííîñòè
â êëàññå H ôóíêöèè h íà âñåì ìíîæåñòâå ìîäåëåé ñ âåðîÿòíîñòíîé ìàññîé �.
Ðàññìîòðèì ÷àñòíûé ñëó÷àé, êîãäà êëàññ ãèïîòåç ñîñòîèò èç ëèíåéíûõ êëàñ-
ñèôèêàòîðîâ. Áóäåì èñïîëüçîâàòü ëèíåéíûå ïîðîãîâûå ôóíêöèè, ÿâëÿþùèåñÿ
ìîäèôèêàöèåé ëèíåéíûõ êëàññèôèêàòîðîâ äëÿ îïðåäåëåíèÿ ôàêòà ñóùåñòâî-
âàíèÿ ôóíêöèè ãëóáèíû, à òàêæå òîãî, ÷òî ïîëóïðîñòðàíñòâåííàÿ ãëóáèíà —
÷àñòíûé ñëó÷àé îòíîñèòåëüíîé ãëóáèíû [1].
Îïðåäåëèì åäèíè÷íóþ ñôåðó êàê W { R }� � �z zr : | | | | 1 , ãäå H R� r è Z W R� �
òàêèå, ÷òî h�H âûïîëíÿåòñÿ íà z z zb� �( , )� Z ñ h z h z zb( ) ( )� �
sign � . Â äàííîì
ñëó÷àå ìîäåëü z�Z ìîæíî îïðåäåëèòü êàê êîìáèíàöèþ íàïðàâëåíèÿ zb è ñìå-
ùåíèÿ z �.
Òåîðåìà 1. Ïóñòü H — êëàññ ëèíåéíûõ ïîðîãîâûõ ôóíêöèé íà Z, ãäå
Z W R� � . Ïóñòü v h( ) — òàêàÿ ôóíêöèÿ ïëîòíîñòè, ÷òî v h
Y
h( ) exp ( ( ))�
1
� , ïðè
êîòîðîé P ÿâëÿåòñÿ âåðîÿòíîñòíîé ìåðîé íà H, à � ( )h — âûïóêëîé ôóíêöèåé.
Êðîìå òîãî, ïóñòü h hh
* [ ]� �� P . Òîãäà èìååò ìåñòî íåðàâåíñòâî E h eP ( ) /* � 1 .
Äîêàçàòåëüñòâî. Î÷åâèäíî, ÷òî P ÿâëÿåòñÿ ëîãàðèôìè÷åñêè âîãíóòîé ôóíê-
öèåé òîãäà è òîëüêî òîãäà, êîãäà v — ëîãàðèôìè÷åñêè âîãíóòàÿ ôóíêöèÿ. Ïî-
ñêîëüêó â óñëîâèÿõ òåîðåìû v h( ) — ëîãàðèôìè÷åñêè âîãíóòàÿ ôóíêöèÿ, òî P òàê-
æå ëîãàðèôìè÷åñêè âîãíóòàÿ ôóíêöèÿ. Èñïîëüçóÿ òåîðåìó î «ìåäèàííîì èçáèðà-
òåëå», ìîæíî óòâåðæäàòü, ÷òî � z E h z eP ( | ) /� 1 , åñëè h — öåíòð òÿæåñòè P. Îòñþäà
ñëåäóåò, ÷òî öåíòð òÿæåñòè P èìååò ãëóáèíó íå ìåíåå 1/ e, ãäå e — ÷èñëî Ýéëåðà.
Èòàê, öåíòð òÿæåñòè íàõîäèòñÿ â H , ïîñêîëüêó H R� r .
Òåîðåìà äîêàçàíà.
Îòìåòèì, ÷òî èñïîëüçîâàíèå âûïóêëûõ îöåíî÷íûõ ôóíêöèé � ( )h �
� �
�
� j h z x d hi i
i
m
( ( ), ) ( )
1
, â êîòîðûõ êàê ôóíêöèÿ ïîòåðü, òàê è ôóíêöèÿ ðåãóëÿðèçà-
öèè âûïóêëûå, èìååò øèðîêîå ðàñïðîñòðàíåíèå â ìàøèííîì îáó÷åíèè [2]. Ïîý-
òîìó íàèáîëåå ãëóáîêàÿ òî÷êà, êîòîðàÿ ÿâëÿåòñÿ âçâåøåííûì ñðåäíèì çíà÷åíè-
åì, èìååò ãëóáèíó íå ìåíåå 1/ e.
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
ÈÑÑËÅÄÎÂÀÍÈÅ ÔÎÐÌÛ ÔÓÍÊÖÈÉ ÃËÓÁÈÍÛ
Ïîêàæåì, ÷òî åñëè êëàññ ôóíêöèé H çàìêíóòûé, òî âçâåøåííîå ñðåäíåå çíà÷å-
íèå ñóùåñòâóåò, à óðîâíåâûå ìíîæåñòâà ôóíêöèé ãëóáèíû âûïóêëûå.
Ïðîâîäÿ èññëåäîâàíèå â ðàìêàõ ôóíêöèîíàëüíûõ êëàññîâ, ðàññìîòðèì êëàññ
ôóíêöèé H , ãäå c h hm, , ,1 � �H. Ïðè óñëîâèè, åñëè � z ñóùåñòâóåò òàêîå
l m�1, ,� , ÷òî c z h zl( ) ( )� , ìîæíî óòâåðæäàòü, ÷òî c íàõîäèòñÿ â âûïóêëîé
îáîëî÷êå h hm1, ,� .
Ëåììà 1. Åñëè c íàõîäèòñÿ â âûïóêëîé îáîëî÷êå h hm1, ,� , òî
E c E h
l
lP P( ) min ( )� ,
ãäå H — êëàññ ôóíêöèé ñ âåðîÿòíîñòíîé ìåðîé P. Êðîìå òîãî, åñëè � — ìåðà
íà Z, òî
E c E h
l
m
lP P
� �
�
�
,
,
( ) min ( )� ,
ãäå � � 0.
Äîêàçàòåëüñòâî. Îïðåäåëèì óñëîâèå, ïðè êîòîðîì ôóíêöèÿ c íàõîäèòñÿ
â âûïóêëîé îáîëî÷êå h hm1, ,� . Ïîñêîëüêó äëÿ êàæäîãî z ñóùåñòâóåò òàêîå l, ÷òî
c z h zl( ) ( )� , èìååì
E c z E h z E hl
l
lP P P( | ) ( | ) min ( )� � ,
îòêóäà ñëåäóåò E c E h
l lP P( ) min ( )� .
Ïðåäïîëîæèì, ÷òî � � �{ }P P
z E c z E c: ( | ) ( ),� � è � �l lz h z c z� � �{ }: ( ) ( ) äëÿ
� � 0 è l m�1, ,� ñîîòâåòñòâåííî.
Ìîæíî óòâåðæäàòü, ÷òî � l l� �� , ïîñêîëüêó ôóíêöèÿ c íàõîäèòñÿ â âû-
ïóêëîé îáîëî÷êå h hm1, ,� . Ñëåäîâàòåëüíî, èìååò ìåñòî íåðàâåíñòâî
� � �( ) ( )� �l
l
� � � .
 ðåçóëüòàòå ïîëó÷àåì
E c E h E hm
l
l
m
lP P P
� �
�
�
�
�
,
, ,
( ) ( ) min ( )� � ,
ïîñêîëüêó ñóùåñòâóåò òàêîå l, ÷òî � �( ) /�l m� . Ëåììà äîêàçàíà.
Äàëåå èññëåäóåì óñëîâèÿ ñóùåñòâîâàíèÿ âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ,
êîãäà êëàññ ôóíêöèé ÿâëÿåòñÿ çàìêíóòûì.
Îòìåòèì, ÷òî êëàññ ôóíêöèé H çàìêíóòûé, åñëè äëÿ êàæäîé ïîñëåäîâàòåëü-
íîñòè h h1 2, , ...�H ñóùåñòâóåò òàêîå h*� H, ÷òî äëÿ êàæäîãî z�Z, åñëè
lim ( )
m
mh z
��
ñóùåñòâóåò, òî h z h z
m
m
* ( ) lim ( )�
��
.
Òåîðåìà 2. Åñëè êëàññ ôóíêöèé H çàìêíóòûé, òî âçâåøåííîå ñðåäíåå çíà÷å-
íèå H ñóùåñòâóåò îòíîñèòåëüíî ïðîèçâîëüíîé âåðîÿòíîñòíîé ìåðû P.
Äîêàçàòåëüñòâî. Ïóñòü h* �H — ãðàíèöà ðÿäà h h1 2, , ... Ïðåäïîëîæèì òàê-
æå, ÷òî ñóùåñòâóåò òàêîå hm , ÷òî E h E mmP ( ) /�
1 , ãäå E E hh� sup ( )P . Ìîæíî
óòâåðæäàòü, ÷òî E h EP ( )* � . Îäíàêî, ïîñêîëüêó E ÿâëÿåòñÿ ñóïðåìóìîì çíà÷å-
íèé ãëóáèíû, âûïîëíÿåòñÿ íåðàâåíñòâî E h EP ( )* � .
Îòìåòèì, ÷òî � �z Z è �M ñóùåñòâóåò òàêîå m M� , ÷òî h z h zm
* ( ) ( )� . Ïî-
ýòîìó, åñëè E h EP ( )* � , ñóùåñòâóåò òàêîå z, ÷òî E h z EP ( | )* � .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 45
Òàêèì îáðàçîì,
E h E h z E h z Em mk kP P P( ) ( | ) ( | )*� � � ,
ïîñêîëüêó ñóùåñòâóåò òàêàÿ ïîäïîñëåäîâàòåëüíîñòü mk ��, ÷òî h z h zmk
( ) ( )*� .
Çàìåòèì, ÷òî, òàê êàê lim ( )
k
mE h E
k��
�P , ïîëó÷åííûé ðåçóëüòàò ÿâëÿåòñÿ ïðîòè-
âîðå÷èåì.
Èñõîäÿ èç òîãî, ÷òî E h z EP ( | )* � � z, èìååò ìåñòî êîíå÷íîå íåðàâåíñòâî
E h EP ( )* � .
Òåîðåìà äîêàçàíà.
ÑÎÃËÀÑÎÂÀÍÍÎÑÒÜ ÃÈÏÎÒÅÇÛ ÂÇÂÅØÅÍÍÎÃÎ ÑÐÅÄÍÅÃÎ ÇÍÀ×ÅÍÈß.
Ñ ó÷åòîì òîãî, ÷òî îöåíêà ìàêñèìóìà àïîñòåðèîðíîé âåðîÿòíîñòè îïðåäåëåíà
òîëüêî â âåðøèíå ðàñïðåäåëåíèÿ, îíà ìîæåò áûòü íåäîñòîâåðíîé. Äàëåå ïðî-
àíàëèçèðóåì ñëó÷àé, êîãäà íà êàæäîé ìîäåëè îöåíêà ìàêñèìóìà àïîñòåðèîð-
íîé âåðîÿòíîñòè íå ñîãëàñîâûâàåòñÿ ñ îïòèìàëüíîé ãèïîòåçîé Áàéåñà, â òî
âðåìÿ êàê ãèïîòåçà âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ ñîãëàñîâûâàåòñÿ ñ íåé íà
êàæäîì øàãó [3]. Êðîìå òîãî, îïòèìàëüíàÿ ãèïîòåçà Áàéåñà òàêæå ÿâëÿåòñÿ
âçâåøåííûì ñðåäíèì çíà÷åíèåì, ïîñêîëüêó îíà ÷ëåí êëàññà ãèïîòåç. Îòñþäà
ñëåäóåò, ÷òî îöåíêà ìàêñèìóìà àïîñòåðèîðíîé âåðîÿòíîñòè íå ìîæåò áûòü
ïðîãíîçèðóåìîé.
Ïðåäïîëîæèì, ÷òî ìíîæåñòâî èç M äèñêðåòíûõ ýëåìåíòîâ, ïðîèíäåêñèðî-
âàííûõ öåëûìè ÷èñëàìè 1, ,� M , ÿâëÿåòñÿ âûáîðî÷íûì ïðîñòðàíñòâîì Z, ò.å.
Z { }� 1, ,� M . Êëàññ ôóíêöèé H ñîñòîèò èç M �2 ôóíêöèè, ãäå ôóíêöèè hi îïðå-
äåëÿþòñÿ ñëåäóþùèì îáðàçîì: � �i M{ }1, ,� h zi ( ) �1, åñëè z i� , è h zi ( ) � 0
â ïðîòèâíîì ñëó÷àå. Òàêæå êëàññ ôóíêöèé H ñîäåðæèò ïîñòîÿííûå ôóíêöèè h0 è
hM �1, ïðèíèìàþùèå çíà÷åíèÿ 0 è 1 ñîîòâåòñòâåííî äëÿ êàæäîãî âõîäà.
Ðàññìîòðèì àïîñòåðèîðíóþ âåðîÿòíîñòü
P{ }h
Y
M � �
1
1 2� /
, P{ }h
Y
0
2
�
� /
, P{ }h
Y
z �
1 �
� �i z, P{ }h
Y
i �
�
,
ãäå 0 1 2� �� / è M �
2
1
�
.
Òàêèì îáðàçîì, îöåíêîé ìàêñèìóìà àïîñòåðèîðíîé âåðîÿòíîñòè ÿâëÿåòñÿ
hM �1. Îäíàêî ñîãëàñíî P âåðîÿòíîñòü òîãî, ÷òî ìåòêîé i (� i) ÿâëÿåòñÿ x �1, ðàâíà
2
3
2
�
Y
, à â ñëó÷àå x � 0 ðàâíà
M
Y
�
�
�
�
�
�
1
2
�
. Â ðåçóëüòàòå ìîæíî óòâåðæäàòü, ÷òî
îöåíêà Áàéåñà — ôóíêöèÿ h0 , ïîñêîëüêó â ñîîòâåòñòâèè ñ P ìåòêà x � 0 èìååò
áîëåå âûñîêóþ âåðîÿòíîñòü, ÷åì ìåòêà x �1.
Îòìåòèì, ÷òî îïòèìàëüíàÿ ãèïîòåçà Áàéåñà òàêæå ÿâëÿåòñÿ âçâåøåííûì
ñðåäíèì çíà÷åíèåì, ïîñêîëüêó íàõîäèòñÿ â êëàññå H .  äàííîì ñëó÷àå íà öåëîì
âûáîðî÷íîì ïðîñòðàíñòâå îöåíêà ìàêñèìóìà àïîñòåðèîðíîé âåðîÿòíîñòè íå ñî-
ãëàñîâûâàåòñÿ ñî âçâåøåííûì ñðåäíèì çíà÷åíèåì ñ îïòèìàëüíîé ãèïîòåçîé
Áàéåñà.
Ìèíèìèçàöèÿ àïîñòåðèîðíîé âåðîÿòíîñòè — áîëåå ýôôåêòèâíàÿ îöåíêà,
÷åì ìàêñèìèçàöèÿ àïîñòåðèîðíîé âåðîÿòíîñòè. Ýòî îáóñëîâëåíî òåì, ÷òî îïòè-
ìàëüíàÿ ãèïîòåçà Áàéåñà h0 èìååò ìèíèìàëüíóþ ïëîòíîñòü â ðàñïðåäåëåíèè P.
Êðîìå òîãî, àïîñòåðèîðíóþ âåðîÿòíîñòü ìîæíî ïîëó÷èòü â ðåçóëüòàòå âûïîëíå-
46 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
íèÿ ñëåäóþùåé ïðîöåäóðû. Ïðåäïîëîæèì òàêóþ àïðèîðíóþ âåðîÿòíîñòü íà H ,
÷òî �( ) /h Mi � �1 2, à òàêæå òàêîé çàøóìëåííûé àíàëîã, ÷òî äëÿ i M�1, ,� ðå-
çóëüòàò hi ìåíÿåòñÿ ñ âåðîÿòíîñòüþ 0 1 2� �� / , òîãäà êàê äëÿ h0 è hM �1 ðåçóëüòàò
ìåíÿåòñÿ ñ âåðîÿòíîñòüþ � � 2.
 õîäå èññëåäîâàíèÿ áûëî óñòàíîâëåíî, ÷òî ïîðîãîâàÿ òî÷êà ãèïîòåçû âçâå-
øåííîãî ñðåäíåãî çíà÷åíèÿ îãðàíè÷åíà ïî íèæíåé ãðàíèöå ôóíêöèåé îò åå
ãëóáèíû.
Äàëåå ïðîâåäåì ñðàâíåíèå ïîðîãîâîé òî÷êè ãèïîòåçû âçâåøåííîãî ñðåäíåãî
çíà÷åíèÿ è ïîðîãîâîé òî÷êè îöåíêè ìàêñèìóìà àïîñòåðèîðíîé âåðîÿòíîñòè.
Ïîëàãàåì, ÷òî ïîðîãîâàÿ òî÷êà îöåíêè ìàêñèìóìà àïîñòåðèîðíîé âåðîÿòíîñòè
ðàâíà íóëþ äëÿ íåïðåðûâíûõ êëàññîâ.
Ïðåäïîëîæèì, ÷òî P — òàêàÿ ìåðà Ëåáåãà, ÷òî v ÿâëÿåòñÿ ôóíêöèåé ïëîò-
íîñòè P è îãðàíè÷åíà íåêîòîðûì áåñêîíå÷íûì N . Çàìåòèì, ÷òî òàêîå ïðåäïîëî-
æåíèå ñäåëàíî â öåëÿõ ýôôåêòèâíîãî îïðåäåëåíèÿ îöåíêè ìàêñèìóìà àïîñòåðè-
îðíîé âåðîÿòíîñòè. Êðîìå òîãî, ðàññìîòðèì P ñ ôóíêöèåé ïëîòíîñòè
� �v h N( ) 1, åñëè h h� 0 , è �v h v h( ) ( ) â ïðîòèâíîì ñëó÷àå, ãäå h0 �H. Îòìåòèì,
÷òî îöåíêà ìàêñèìóìà àïîñòåðèîðíîé âåðîÿòíîñòè äëÿ P ðàâíà h0 , â òî âðåìÿ
êàê îáùåå ðàññòîÿíèå âàðèàöèè ìåæäó P è P ðàâíî íóëþ [4]. Â ðåçóëüòàòå äëÿ
îïðåäåëåíèÿ h0 â êà÷åñòâå îöåíêè ìàêñèìóìà àïîñòåðèîðíîé âåðîÿòíîñòè ìîæíî
ââåñòè íóëåâóþ ìåðó P �h0 . Îòñþäà ñëåäóåò âûâîä, ÷òî ïîðîãîâàÿ òî÷êà îöåíêè
ìàêñèìóìà àïîñòåðèîðíîé âåðîÿòíîñòè ðàâíà íóëþ.
ÀËÃÎÐÈÒÌÛ ÎÏÐÅÄÅËÅÍÈß ÔÓÍÊÖÈÉ ÃËÓÁÈÍÛ
Ïðåäëàãàåòñÿ ýôôåêòèâíûé àëãîðèòì îöåíêè ãëóáèíû, êîòîðûé ïðèíèìàåò
â êà÷åñòâå âõîäà äâå âûáîðêè: W z zg� { }1, ,� è Q h hm� { }1, ,� , ïåðâàÿ èç êî-
òîðûõ ÿâëÿåòñÿ âûáîðêîé òî÷åê èç ãåíåðàëüíîé ñîâîêóïíîñòè Z, à âòîðàÿ —
âûáîðêîé ôóíêöèé èç êëàññà ôóíêöèé H. Íà ïåðâîì ýòàïå àëãîðèòì îöåíèâàåò
ãëóáèíó çàäàííîé ôóíêöèè h íà ýëåìåíòàõ z zg1, ,� , çàòåì èñïîëüçóåò ìèíè-
ìàëüíîå çíà÷åíèå â êà÷åñòâå îöåíêè îáùåé ãëóáèíû. Îòìåòèì, ÷òî ãëóáèíà
ýëåìåíòà zi îöåíèâàåòñÿ ïóòåì ïîäñ÷åòà êîìïîíåíò ôóíêöèé h hm1, ,� . Èòàê,
ïðèâåäåì àëãîðèòì îöåíêè ãëóáèíû, âõîäîì êîòîðîãî ÿâëÿåòñÿ âûáîðêà
W z zg� { }1, ,� , ãäå zi �Z, âûáîðêà Q h hm� { }1, ,� , ãäå hl �H, è ôóíêöèÿ h,
à âûõîäîì — ôóíêöèÿ E h
Q
W ( ), êîòîðàÿ ÿâëÿåòñÿ ïðèáëèæåíèì äëÿ ãëóáèíû h:
1) äëÿ i g�1, ,� âû÷èñëèòü E h z
m
Q i h z h zl l i i
( | ) ( ) ( )� ��1
1 ; 2) âîçâðàòèòü
E h E h z
Q
W
i i( ) min ( | )� . Îòìåòèì, ÷òî ýìïèðè÷åñêîé ãëóáèíîé h ÿâëÿåòñÿ çíà-
÷åíèå E h
Q
W ( ), êîòîðîå âîçâðàùåíî àëãîðèòìîì îöåíêè ãëóáèíû. Êðîìå
òîãî, äàííûé àëãîðèòì ïîçâîëÿåò ïîëó÷èòü ýôôåêòèâíûå îöåíêè èñòèííîé
ãëóáèíû [5].
Ïðåäïîëîæèì, ÷òî C — íåêîòîðîå ìíîæåñòâî ïîäìíîæåñòâ â Z, à � — âå-
ðîÿòíîñòíàÿ ìåðà, îïðåäåëåííàÿ íà ãåíåðàëüíîé ñîâîêóïíîñòè Z. Ìîæíî îïðåäå-
ëèòü �-ñåòü êàê òàêîå êîíå÷íîå ïîäìíîæåñòâî G
Z, ÷òî � �d C, åñëè � �( )d � ,
òî G d� � .
Äàëåå ïðèâåäåì òåîðåìó î ðàâíîìåðíîé ñõîäèìîñòè ãëóáèíû, ÷òî ÿâëÿåòñÿ
âàæíûì ôàêòîðîì ïðè íàõîæäåíèè âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ. Èç òåîðåìû
ñëåäóåò, ÷òî ýìïèðè÷åñêàÿ ãëóáèíà — ýôôåêòèâíàÿ îöåíêà èñòèííîé ãëóáèíû,
åñëè hl îòáèðàþòñÿ èç âåðîÿòíîñòíîé ìåðû P, à zi — èç ðàñïðåäåëåíèÿ ïî Z. Êðî-
ìå òîãî, äàííàÿ îöåíêà ðàâíîìåðíî ýôôåêòèâíà íà âñåõ ôóíêöèÿõ h�H.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 47
Òåîðåìà 3. Ïóñòü � — âåðîÿòíîñòíàÿ ìåðà íà Z, � �, � 0, à P — âåðîÿòíîñòíàÿ
ìåðà íà H. Ïóñòü ôóíêöèÿ h� (� �h H) òàêîâà, ÷òî h z� ( ) �1, åñëè E h zP ( | ) �
� E h
P
� �, ( ), è h z� ( ) �
1 â ïðîòèâíîì ñëó÷àå. Îïðåäåëèì f r t
t
ii
r
( , ) �
�
�
��
�
�
���� 0
, åñëè
r t� , è f r t t( , ) � 2 â ïðîòèâíîì ñëó÷àå. Òàêæå ïðåäïîëîæèì, ÷òî ïðè óñëîâèè,
÷òî H� èìååò êîíå÷íóþ ðàçìåðíîñòü Âàïíèêà–×åðâîíåíêèñà r� �,
H { } H� �� �h h . Åñëè W è Q âûáðàíû ñëó÷àéíûì îáðàçîì èç �g è Pm ñîîòâåò-
ñòâåííî, ãäå g � 8 / �, òî ñ âåðîÿòíîñòüþ
1 2 2 22 1 2
g m f r g gexp ( ) ( , ) /� �
èìååò ìåñòî íåðàâåíñòâî
� �
�
� � �h E h E h E h E h
Q
WH P P P
, ( ) ( ) ( ) ( ), ,� � �� � �0 ,
ãäå E h
Q
W ( ) — ýìïèðè÷åñêàÿ ãëóáèíà, êîòîðàÿ âû÷èñëÿåòñÿ ïî àëãîðèòìó èçìå-
ðåíèÿ ãëóáèíû.
Äîêàçàòåëüñòâî. Êàê áûëî ïîêàçàíî, ñ âåðîÿòíîñòüþ, áîëüøåé èëè ðàâíîé
1 2 21 2
f r g g( , ) /� , ñëó÷àéíàÿ âûáîðêà W zi i
g� �{ }
1
ÿâëÿåòñÿ �-ñåòüþ äëÿ { } Hh h� � .
Èñïîëüçóåì h� äëÿ îáîçíà÷åíèÿ êàê ôóíêöèè, òàê è ïîäìíîæåñòâà Z, âêëþ÷àþ-
ùåãî âñå z�Z, äëÿ êîòîðûõ E h z E hP P
( | ) ( )
,� � �
.
Ìîæíî óòâåðæäàòü, ÷òî � �h H èìååò ìåñòî âûðàæåíèå ! �i g[ , , ]1 �
s t z hi. . � � , òàê êàê � �h H âûïîëíÿåòñÿ íåðàâåíñòâî � ��( )h � . Ïîñêîëüêó
E h z E hiP P
( | ) ( ),� � � , ÷òî ñëåäóåò èç z hi � � , ïîëó÷àåì � �h H
E h E h z E h
i
iP P
( ) min ( | ) ( ),� � � �
ñ âåðîÿòíîñòüþ 1 2 21 2
f r g g( , ) /� ïðè ñëó÷àéíîì âûáîðå z zg1, ,� .
Äàëåå, èñïîëüçóÿ íåðàâåíñòâî Õ¸ôäèíãà äëÿ ôèêñèðîâàííûõ zi , èìååì
P
m
h h z h h z
h h
l l i i
m1
1
1 1
, ,
| : ( ) | : ( )
�
�
�"
"
" "
"
"�
#
$
%
&
'
(� �{ } �
2 2 2exp ( )m� ,
ãäå h hm1, ,� — íåçàâèñèìàÿ îäèíàêîâî ðàñïðåäåëåííàÿ âûáîðêà èç P.
Èòàê, � i ïîëó÷àåì
1
1 1
m
h h z h h zl l i i| : ( ) | : ( )�
� �"
"
" "
"
"�� �{ H }
ñ âåðîÿòíîñòüþ 1 2 2
g mexp ( )� .
Êðîìå òîãî, � i èìååò ìåñòî íåðàâåíñòâî
1
1 1
m
h h z h h zl l i i| : ( ) | : ( )�
� �
"
"
" "
"
"�� �{ H } .
Ó÷èòûâàÿ ïîëó÷åííûå ðåçóëüòàòû, ìîæíî óòâåðæäàòü, ÷òî � �h H
E h E h
Q
W ( ) ( ),� �
P
� � �
48 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
ñ âåðîÿòíîñòüþ íå ìåíåå 1 2 2 22 1 2
g m f r g gexp ( ) ( , ) /� � ïðè ñëó÷àéíîì âû-
áîðå z zg1, ,� è h hm1, ,� .
Çàìåòèì, ÷òî ñ âåðîÿòíîñòüþ 1 â âûáîðêå íå áóäåò ñóùåñòâîâàòü òàêîãî i,
÷òî E h z E hiP P
( | ) ( ),� 0 � . Îòñþäà ñëåäóåò, ÷òî � �h H E h
P
0, ( )� �
� E h
Q
W ( ), à òàê-
æå âûïîëíÿåòñÿ íåðàâåíñòâî E h E hP P
( ) ( ),� 0 � .
Òåîðåìà äîêàçàíà.
Èñõîäÿ èç òåîðåìû 3, ìîæíî ñäåëàòü âûâîä, ÷òî ðàñ÷åòíàÿ ãëóáèíà ðàâíî-
ìåðíî ñõîäèòñÿ ê èñòèííîé ãëóáèíå.
Òåîðåìà 4. Ïóñòü h� òàêîå, ÷òî h z� ( ) �1, åñëè E h z EP ( | )� , è h z� ( ) �
1
â ïðîòèâíîì ñëó÷àå � �h H. Òàêæå ïðåäïîëîæèì, ÷òî E E hh� �sup H P ( ) è
H { }
P
� � � �� �h
h E h E: ( ), . Òîãäà ðàçìåðíîñòü Âàïíèêà–×åðâîíåíêèñà H� îãðàíè÷åíà
ñâåðõó ðàçìåðíîñòüþ Âàïíèêà–×åðâîíåíêèñà H.
Äîêàçàòåëüñòâî. Äëÿ êàæäîé ïîñëåäîâàòåëüíîñòè x n� ){ }1 ! hx òàêîå, ÷òî
hx
� ãåíåðèðóåò ìåòêè x íà z zn1, ,� ïðè óñëîâèè, ÷òî z zn1, ,� ìîäèôèöèðîâà-
íû H� . Íåîáõîäèìî ïîêàçàòü, ÷òî âûáîðêà ìîäèôèöèðîâàíà H, ïîñêîëüêó ôóíê-
öèè hx è hx' ãåíåðèðóþò ðàçëè÷íûå ìåòêè íà z zn1, ,� � �x x'.
Ïðåäïîëîæèì, ÷òî x x� ', xi �1è x i' �
1. Îòñþäà ñëåäóåò, ÷òî zi òàêîå, ÷òî
E h z E E h zx
i
x
iP P( | ) ( | )'� � .
Ïðè óñëîâèè h z h zx
i
x
i( ) ( )'� èìååì E h z E h zx
i
x
iP P( | ) ( | )'� . Çàìåòèì, ÷òî
äàííûé ðåçóëüòàò âûòåêàåò èç îïðåäåëåíèÿ ãëóáèíû íà òî÷êå zi .
Èòàê, âûáîðêà z zn1, ,� ÿâëÿåòñÿ ìîäèôèöèðîâàííîé H, èñõîäÿ èç åå ìîäè-
ôèêàöèè H� . Ïîýòîìó ìîæíî ñäåëàòü âûâîä, ÷òî ðàçìåðíîñòü Âàïíèêà–×åðâî-
íåíêèñà H� îãðàíè÷åíà ðàçìåðíîñòüþ Âàïíèêà–×åðâîíåíêèñà H.
Òåîðåìà äîêàçàíà.
ÀËÃÎÐÈÒÌ ÏÐÈÁËÈÆÅÍÈß ÂÇÂÅØÅÍÍÎÃÎ ÑÐÅÄÍÅÃÎ ÇÍÀ×ÅÍÈß
Ïðîàíàëèçèðîâàâ ìåòîäû îïðåäåëåíèÿ ãëóáèíû, óñòàíîâèëè, ÷òî ðàñ÷åòíàÿ
ãëóáèíà ïðèíèìàåò òî÷íûå çíà÷åíèÿ ðàâíîìåðíî äëÿ âñåõ ôóíêöèé h�H
ñ äîñòàòî÷íî áîëüøîé âåðîÿòíîñòüþ ïðè óñëîâèè, ÷òî âûáîðêè W è Q áîëü-
øèå. Êðîìå òîãî, èìååì h E hh� �arg H Pmax ( ), îòêóäà ñëåäóåò, ÷òî îòíîñèòåëü-
íîå âçâåøåííîå ñðåäíåå çíà÷åíèå ÿâëÿåòñÿ ôóíêöèåé h, êîòîðàÿ ìàêñèìèçèðó-
åò ãëóáèíó.
Íà îñíîâå ïîëó÷åííûõ ðåçóëüòàòîâ ñòðîèì àëãîðèòì äëÿ ïðèáëèæåíèÿ îòíî-
ñèòåëüíîãî âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ, à òàêæå àëãîðèòì äëÿ íàõîæäåíèÿ
ôóíêöèè h, ìàêñèìèçèðóþùåé ýìïèðè÷åñêóþ ãëóáèíó, ò.å. h E hh Q
W� �arg Hmax ( ).
Èòàê, ïðåäïîëîæèì, ÷òî W zi i
g� �{ }
1
. Îòìåòèì, ÷òî ôóíêöèÿ ñ áîëüøîé ýì-
ïèðè÷åñêîé ãëóáèíîé áóäåò ñîãëàñîâûâàòüñÿ ñ áîëüøèíñòâîì õàðàêòåðèñòèê
äàííûõ òî÷åê. Îäíàêî èíîãäà èìåþò ìåñòî ñëó÷àè, êîãäà òàêîé ôóíêöèè íå ñó-
ùåñòâóåò è âîçíèêàåò íåîáõîäèìîñòü íàõîæäåíèÿ ãèïîòåçû, êîòîðàÿ íå ñîãëàñî-
âûâàåòñÿ ñ áîëüøèíñòâîì õàðàêòåðèñòèê íà ñîîòâåòñòâóþùèõ ìîäåëÿõ [6]. Â òà-
êèõ ñëó÷àÿõ ýìïèðè÷åñêàÿ ãëóáèíà áóäåò ïðèíèìàòü áîëüøåå çíà÷åíèå, åñëè
áîëüøèíñòâî õàðàêòåðèñòèê íà òàêèõ ýëåìåíòàõ äàííûõ äîìèíèðóåò ñ íåáîëü-
øèì îòðûâîì. Äëÿ ðåøåíèÿ äàííîé ïðîáëåìû èñïîëüçóåì âûáîðêó ôóíêöèé
Q hl l
m� �{ }
1
äëÿ âû÷èñëåíèÿ áîëüøèíñòâà õàðàêòåðèñòèê êàæäîãî zi è ÷àñòü si
ôóíêöèé, êîòîðûå íå ñîãëàñîâûâàþòñÿ ñ áîëüøèíñòâîì õàðàêòåðèñòèê.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 49
Ïðåäëîæåííûé ïîäõîä áàçèðóåòñÿ íà íàõîæäåíèè ôóíêöèè, êîòîðàÿ ñîãëà-
ñîâûâàåòñÿ ñ áîëüøèíñòâîì õàðàêòåðèñòèê âñåõ ýëåìåíòîâ â W. Ïðè óñëîâèè,
åñëè òàêîé ôóíêöèè íå ñóùåñòâóåò, óäàëÿåì ýëåìåíò äàííûõ, äëÿ êîòîðîãî si
ïðèíèìàåò íàèáîëüøåå çíà÷åíèå, è íàõîäèì ôóíêöèþ, êîòîðàÿ ñîãëàñîâûâàåòñÿ
ñ áîëüøèíñòâîì õàðàêòåðèñòèê äðóãèõ ýëåìåíòîâ äàííûõ. Ïðîöåäóðà âûïîëíÿ-
åòñÿ äî òåõ ïîð, ïîêà íå áóäåò íàéäåíà ñîãëàñîâàííàÿ ôóíêöèÿ. Äàííàÿ ôóíêöèÿ
ÿâëÿåòñÿ ìàêñèìèçèðóþùåé îöåíêîé E h
Q
W ( ), ïîýòîìó â àëãîðèòìå ïðèáëèæåíèÿ
âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ òàêàÿ ïðîöåäóðà óñêîðÿåòñÿ ñ ïîìîùüþ
äâîè÷íîãî ïîèñêà [7].
Îòìåòèì, ÷òî ìåòîä äâîè÷íîãî ïîèñêà óìåíüøàåò ñëîæíîñòü àëãîðèòìà äî
O mg g g g gq( ( ) ( ))� �log log , â òî âðåìÿ êàê ëèíåéíûé ïîèñê òðåáóåò
O mg g g g q( ( ) )� � �log 1 îïåðàöèé. Óêàçàííàÿ ñëîæíîñòü îáåñïå÷èâàåòñÿ ïðè
óñëîâèè, ÷òî àëãîðèòì ñîãëàñîâàííîñòè òðåáóåò O g q( ) îïåðàöèé äëÿ íåêîòîðîãî q
ïðè ðàáîòå íà âûáîðêå ðàçìåðà g.
Äàëåå ïðåäñòàâëåí àëãîðèòì ïðèáëèæåíèÿ âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ,
ïðåèìóùåñòâîì êîòîðîãî ÿâëÿåòñÿ èñïîëüçîâàíèå ìîäåëè ñîãëàñîâàííîñòè âìåñ-
òî ìîäåëè ìèíèìèçàöèè ýìïèðè÷åñêîé îøèáêè. Îòìåòèì, ÷òî óñëîâèåì âûïîë-
íåíèÿ àëãîðèòìà ïðèáëèæåíèÿ âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ ñ÷èòàåòñÿ ëèøü
äîñòóï ê ìîäåëè, êîòîðàÿ ñïîñîáíà íàõîäèòü ñîãëàñîâàííóþ ãèïîòåçó, åñëè òàêî-
âàÿ ñóùåñòâóåò. Óêàçàííàÿ îñîáåííîñòü àëãîðèòìà ïîçâîëÿåò óìåíüøèòü
ñëîæíîñòü ìèíèìèçàöèè è àïïðîêñèìàöèè ýìïèðè÷åñêîé îøèáêè.
Àëãîðèòì ïðèáëèæåíèÿ âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ ìîæíî ïðåäñòàâèòü
ñëåäóþùèì îáðàçîì. Íà âõîä àëãîðèòìà ïîäàåòñÿ âûáîðêà W z zg
g� �{ } Z1, ,�
è âûáîðêà Q h hm
m� �{ } H1, ,� , ãäå hl �H. Òàêæå èìååò ìåñòî àëãîðèòì *, âîç-
âðàùàþùèé ñîãëàñîâàííóþ ôóíêöèþ, åñëè òàêîâàÿ ñóùåñòâóåò. Íà âûõîäå ïîëó-
÷àåì ôóíêöèþ h�H, ïðèáëèæàþùóþ îòíîñèòåëüíîå âçâåøåííîå ñðåäíåå çíà÷å-
íèå ñ åãî îöåíêîé ãëóáèíû E h
Q
W ( ).
Àëãîðèòì ñîñòîèò èç ñëåäóþùèõ øàãîâ: 1) � �i g1, ,� âû÷èñëÿåì � i
� �
� �
1
1
m
l h zl i| : ( ) |{ } è si i i�
� �min ,{ }� �1 ; 2) êëàññèôèöèðóåì z zg1, ,� òàêèì îá-
ðàçîì, ÷òî s s sn1 2� � �� ; 3) � �i g1, ,� ïóñòü xi �1, åñëè � i
� � 05. , è ïóñòü
xi �
1 â ïðîòèâíîì ñëó÷àå; 4) èñïîëüçóåì äâîè÷íûé ïîèñê äëÿ íàõîæäåíèÿ i* ,
ÿâëÿþùåãîñÿ íàèìåíüøèì èç i, äëÿ êîòîðîãî àëãîðèòì * ìîæåò íàéòè ñîãëàñî-
âàííóþ ôóíêöèþ h íà âûáîðêå W z xi
t t t i
g� �{ }( , ) ; 5) åñëè i* �1, âîçâðàùàåì h è
ãëóáèíó E s�
1 1, èíà÷å âîçâðàùàåì h è ãëóáèíó E s
i
�
* 1.
Îòìåòèì, ÷òî ïðîöåäóðà îïðåäåëåíèÿ ãèïîòåçû, àïïðîêñèìèðóþùåé ãèïîòå-
çó ñ ìèíèìàëüíîé ýìïèðè÷åñêîé îøèáêîé, ÿâëÿåòñÿ NP-ñëîæíîé çàäà÷åé [8].
Îäíàêî ñîãëàñîâàííóþ ãèïîòåçó ìîæíî íàéòè çà ïîëèíîìèàëüíîå âðåìÿ íà îñíî-
âå ëèíåéíîãî ïðîãðàììèðîâàíèÿ ñ èñïîëüçîâàíèåì ëèíåéíîãî êëàññèôèêàòîðà.
ÀÍÀËÈÇ ÀËÃÎÐÈÒÌÀ ÏÐÈÁËÈÆÅÍÈß ÂÇÂÅØÅÍÍÎÃÎ ÑÐÅÄÍÅÃÎ ÇÍÀ×ÅÍÈß
Ëåììà 2. Ãèïîòåçà h è ãëóáèíà E âñåãäà áóäóò âîçâðàùàòüñÿ àëãîðèòìîì ïðè-
áëèæåíèÿ âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ.
Äîêàçàòåëüñòâî. Íåîáõîäèìî ïîêàçàòü, ÷òî ! i òàêîå, ÷òî àëãîðèòì * áóäåò
âîçâðàùàòü ôóíêöèþ ñîãëàñîâàííîñòè h îòíîñèòåëüíî W i , ò.å. óñòàíîâèòü, ÷òî
äâîè÷íûé ïîèñê áóäåò âñåãäà íàõîäèòü i g* � .
50 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
Ìîæíî óòâåðæäàòü, ÷òî, ïîñêîëüêó W z xg
g g� { }( , ) , âûáîðêà áóäåò ñîäåð-
æàòü òîëüêî îäèí ýëåìåíò äàííûõ zg ñ òàêîé ìåòêîé xg , ÷òî ïî êðàéíåé ìåðå ïî-
ëîâèíà ôóíêöèé â Q òàêîâû, ÷òî h z xl g g( ) � . Îòñþäà ñëåäóåò, ÷òî ñóùåñòâóåò
ôóíêöèÿ h, ñîãëàñîâàííàÿ ñ äàííîé âûáîðêîé. Ëåììà äîêàçàíà.
Äàëåå ïðèâîäèì òåîðåìó, äîêàçûâàþùóþ êîððåêòíîñòü ãëóáèíû, âû÷èñëåííîé
ñ ïîìîùüþ àëãîðèòìà ïðèáëèæåíèÿ âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ.
Òåîðåìà 5. Ïóñòü ãèïîòåçà h è ãëóáèíà E âîçâðàùàþòñÿ àëãîðèòìîì ïðè-
áëèæåíèÿ âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ. Òîãäà E E h
Q
W� ( ).
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî X c i c z xi i( ) : ( )� �{ } ÿâëÿåòñÿ ìíîæåñò-
âîì îáðàçîâ, íà êîòîðîì ôóíêöèÿ ñîãëàñîâûâàåòñÿ ñ ìåòêîé. Ðàñ÷åòíàÿ ãëóáèíà
ôóíêöèè îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:
E c s s
Q
W
i X c
i
i X c
i( ) min min ( ), min
( ) ( )
�
�
�
�
�
�
�
� +
1 .
Ìîæíî ïðåäïîëîæèòü, ÷òî i i i X c� � �min : ( ){ } è i i i X c+ � +max : ( ){ }. Â ðå-
çóëüòàòå îïðåäåëåíèå ðàñ÷åòíîé ãëóáèíû ïðåäñòàâèì â âèäå
E c s s
Q
W
i i( ) min (( ), )�
� +
1 ,
ó÷èòûâàÿ óïîðÿäî÷åííîñòü si . Çàìåòèì, ÷òî si+
�1, åñëè X c( ) âêëþ÷àåò âñå i,
è si+
� 0, åñëè X c( ) ïóñòî.
Äàëåå ïðåäïîëîæèì, ÷òî ãèïîòåçà h è âû÷èñëèòåëüíàÿ ãëóáèíà E âîçâðàùà-
þòñÿ àëãîðèòìîì ïðèáëèæåíèÿ âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ.  ñëó÷àå, êîãäà
i* �1 , è ïðè óñëîâèè, ÷òî i* ÿâëÿåòñÿ èíäåêñîì, êîòîðûé âîçâðàùàåòñÿ äâîè÷-
íûì ïîèñêîì, âåëè÷èíû X h g( ) [ , , ]� 1 � è E h s
Q
W ( ) �
1 1 ïðèíèìàþò òî÷íûå çíà-
÷åíèÿ, âîçâðàùåííûå àëãîðèòìîì ïðèáëèæåíèÿ âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ.
Èíà÷å, åñëè i* �1, òî i X h* ( )
+1 ïðè óñëîâèè, ÷òî [ , , ] ( )*i g X h�
.
 ðåçóëüòàòå, ïîñêîëüêó � i' èìååò ìåñòî íåðàâåíñòâî 1 0 5
�si ' , (ñ ó÷åòîì
s
i*
.
�1
05), òî÷íûì çíà÷åíèåì, âîçâðàùåííûì àëãîðèòìîì ïðèáëèæåíèÿ âçâå-
øåííîãî ñðåäíåãî çíà÷åíèÿ, ÿâëÿåòñÿ E h s
Q
W
i
( ) *�
1
.
Òåîðåìà äîêàçàíà.
Êàê áûëî ïîêàçàíî, ýìïèðè÷åñêàÿ ãëóáèíà ôóíêöèè — ýòî ôóíêöèÿ ìíî-
æåñòâà òî÷åê, íà êîòîðûõ îíà ñîãëàñîâûâàåòñÿ ñ áîëüøèíñòâîì îáðàçîâ. Äëÿ äî-
êàçàòåëüñòâà òîãî ôàêòà, ÷òî ìàêñèìàëüíàÿ îöåíêà ýìïèðè÷åñêîé ãëóáèíû âîç-
âðàùàåòñÿ àëãîðèòìîì ïðèáëèæåíèÿ âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ, èìååò ìåñ-
òî ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 6. Ïóñòü h — ôóíêöèÿ, âîçâðàùåííàÿ àëãîðèòìîì ïðèáëèæåíèÿ
âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ. Òîãäà
h E h
h Q
W�
�
arg max
H
( ).
Äîêàçàòåëüñòâî. Ïðè óñëîâèè, åñëè i* �1, ýìïèðè÷åñêàÿ ãëóáèíà h ìàê-
ñèìàëüíà. Îòñþäà ñëåäóåò, ÷òî i* �1 è E h s
Q
W
i
( ) *�
1
, ãäå i* — çíà÷åíèå, âîç-
âðàùåííîå äâîè÷íûì ïîèñêîì, à h — ôóíêöèÿ, âîçâðàùåííàÿ ìîäåëüþ ñîãëàñî-
âàííîñòè.  ñëó÷àå, åñëè ! �i i* òàêîå, ÷òî c z xi i( ) � , âûïîëíÿåòñÿ íåðàâåíñòâî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 51
E c s s E h
Q
W
i i Q
W( ) ( )*� � �
1 1
,
ãäå c�H. Ó÷èòûâàÿ òîò ôàêò, ÷òî ýòàï äâîè÷íîãî ïîèñêà â àëãîðèòìå ïðèáëè-
æåíèÿ âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ ìîæåò ñãåíåðèðîâàòü i*
1 èëè áîëüøåå
ìíîæåñòâî, íåîáõîäèìî, ÷òîáû c z x
i i
( )* *
�
1 1
� �i i* , ãäå c z xi i( ) � . Â ðå-
çóëüòàòå èìååì E c s E h
Q
W
i Q
W( ) : ( )*� �
1
.
Òåîðåìà äîêàçàíà.
Ñëåäóþùàÿ òåîðåìà ÿâëÿåòñÿ îñíîâíûì ðåçóëüòàòîì îöåíêè ïðèáëèæåíèÿ
âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ.
Òåîðåìà 7. Èìåþò ìåñòî òàêèå ñâîéñòâà àëãîðèòìà ïðèáëèæåíèÿ âçâåøåí-
íîãî ñðåäíåãî çíà÷åíèÿ:
1) ïðåäïîëîæèì, ÷òî � �, � 0; ìîæíî óòâåðæäàòü, ÷òî ñ âåðîÿòíîñòüþ íå ìåíåå
1 2 2 22 1 2
g m f r g gexp( ) ( , ) /� �
ôóíêöèÿ h, âîçâðàùåííàÿ àëãîðèòìîì ïðèáëèæåíèÿ âçâåøåííîãî ñðåäíåãî çíà-
÷åíèÿ, òàêîâà, ÷òî
E h E c E c
c H c H
P P Psup sup� � � � �, ,( ) ( ) ( )�
�
� �
0 2 2 ,
ãäå r — ìèíèìóì ìåæäó ðàçìåðíîñòüþ Âàïíèêà–×åðâîíåíêèñà H è ðàçìåð-
íîñòüþ Âàïíèêà–×åðâîíåíêèñà êëàññà H� , âûáîðêà W âçÿòà èç �g , òàê ÷òî
g � 8 / �, à âûáîðêà Q — èç Pm ;
2) åñëè h — ôóíêöèÿ, âîçâðàùåííàÿ àëãîðèòìîì ïðèáëèæåíèÿ âçâåøåííîãî
ñðåäíåãî çíà÷åíèÿ, òî h E hh Q
W� �arg Hmax ( );
3) åñëè h è E — âûõîäû àëãîðèòìà ïðèáëèæåíèÿ âçâåøåííîãî ñðåäíåãî çíà-
÷åíèÿ, òî E E h
Q
W� ( );
4) àëãîðèòì âñåãäà áóäåò îñòàíàâëèâàòüñÿ è âîçâðàùàòü ôóíêöèþ h�H è ýì-
ïèðè÷åñêóþ ãëóáèíó E .
Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà ï. 1 ïðåäïîëîæèì, ÷òî E E hh� sup ( ),
P
0 � ,
ãäå h — ìàêñèìàëüíàÿ îöåíêà E h
Q
W ( ). Êàê áûëî ïîêàçàíî, ñ âåðîÿòíîñòüþ
1 2 2 22 1 2
g m f r g gexp( ) ( , ) /� �
èìååì
E h E c E c E
Q
W
c Q
W
c
( ) max ( ) ( ),� �
�
sup
P
0 � � �
ïðè óñëîâèè, åñëè r, êàê ìèíèìóì, ìåíüøå ðàçìåðíîñòè Âàïíèêà–×åðâîíåíêè-
ñà H è ðàçìåðíîñòè Âàïíèêà–×åðâîíåíêèñà H� . Êðîìå òîãî, î÷åâèäíî, ÷òî
E h E h
Q
W ( ) ( ),� �
P
� � �, åñëè E h E
P
� �, ( )� . Îòñþäà ñëåäóåò, ÷òî ñïðàâåäëèâûì ÿâ-
ëÿåòñÿ íåðàâåíñòâî E h E
P
� �, ( ) � èëè E h E h E
Q
W
P
� � � �, ( ) ( )�
�
2 .
Äîêàçàòåëüñòâî ïï. 2–4 ñëåäóåò èç ðåçóëüòàòîâ òåîðåìû 6, òåîðåìû 5 è ëåì-
ìû 2 ñîîòâåòñòâåííî.
Òåîðåìà äîêàçàíà.
52 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
ÀËÃÎÐÈÒÌÛ ÏÎËÓÏÐÎÑÒÐÀÍÑÒÂÅÍÍÎÉ ÃËÓÁÈÍÛ È ÏÎËÓÏÐÎÑÒÐÀÍÑÒÂÅÍÍÎÃÎ
ÂÇÂÅØÅÍÍÎÃÎ ÑÐÅÄÍÅÃÎ ÇÍÀ×ÅÍÈß
Çàêëþ÷èòåëüíûé ýòàï èññëåäîâàíèÿ ñîñòîèò â îïðåäåëåíèè òîãî, êàê
ðàçðàáîòàííûå àëãîðèòìû ìîæíî ïðèìåíèòü ê çàäà÷àì âû÷èñëåíèÿ ôóíêöèè
ïîëóïðîñòðàíñòâåííîé ãëóáèíû è íàõîæäåíèÿ ïîëóïðîñòðàíñòâåííîãî âçâå-
øåííîãî ñðåäíåãî çíà÷åíèÿ. Ïîñêîëüêó ïîëóïðîñòðàíñòâåííàÿ ãëóáèíà ìîæåò
ðàññìàòðèâàòüñÿ êàê ÷àñòíûé ñëó÷àé îòíîñèòåëüíîé ãëóáèíû, àëãîðèòì îöåíêè
ãëóáèíû è àëãîðèòì ïðèáëèæåíèÿ âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ ìîãóò èñ-
ïîëüçîâàòüñÿ äëÿ âû÷èñëåíèÿ ïîëóïðîñòðàíñòâåííîé ãëóáèíû è àïïðîêñèìà-
öèè ïîëóïðîñòðàíñòâåííîãî âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ ñîîòâåòñòâåííî.
Ïðåäïîëîæèì, ÷òî èìååò ìåñòî âûáîðêà h hm1, ,� ýëåìåíòîâ äàííûõ â R r ,
à òàêæå âûáîðêà íàïðàâëåíèé è ñìåùåíèé èíòåðåñà [9], ò.å. âûáîðêà òàêèõ zi ,
÷òî zi � �W R, ãäå W — åäèíè÷íàÿ ñôåðà.  äàííîì ñëó÷àå ýëåìåíòû ïðåäñòàâ-
ëåíû â âèäå êîìáèíàöèè r-ìåðíîãî åäèíè÷íîãî âåêòîðà zi
b è ñìåùåíèÿ zi
�.
Àëãîðèòì îöåíêè ïîëóïðîñòðàíñòâåííîé ãëóáèíû ïîçâîëÿåò èñïîëüçîâàòü
äàííûå âûáîðêè äëÿ îöåíêè ïîëóïðîñòðàíñòâåííîé ãëóáèíû ýëåìåíòà h r�R .
Àëãîðèòì ïðèáëèæåíèÿ ïîëóïðîñòðàíñòâåííîãî âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ
ïîêàçûâàåò, êàê ïðèìåíÿòü äàííûå âûáîðêè äëÿ ïðèáëèæåíèÿ ïîëóïðîñòðàíñòâåí-
íîãî âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ. Çàìåòèì, ÷òî ðàçìåðíîñòü Âàïíèêà–×åðâî-
íåíêèñà äëÿ äàííûõ çàäà÷ ðàâíà r.
Ñ ó÷åòîì òîãî, ÷òî çàäà÷à âû÷èñëåíèÿ ïîëóïðîñòðàíñòâåííîé ãëóáèíû òðå-
áóåò íàõîæäåíèÿ èíôèìóìà ïî âñåì âîçìîæíûì íàïðàâëåíèÿì, àëãîðèòì ïðè-
áëèæåíèÿ íàõîäèò ìèíèìóì íà ìíîæåñòâå âñåõ âîçìîæíûõ íàïðàâëåíèé â âû-
áîðêå W.  äàííîì ñëó÷àå âûáîð zi
b ïðîâîäèòñÿ ðàâíîìåðíî èç åäèíè÷íîé ñôåðû
ïðè ãåíåðàöèè âûáîðêè. Çàìåòèì, ÷òî âûáîð zi
� â ïðåäëîæåííûõ àëãîðèòìàõ ñëå-
äóåò ïðîâîäèòü ñëó÷àéíûì îáðàçîì. Îäíàêî, êîãäà zi
b ôèêñèðîâàí, íàõîæäåíèå
ìèíèìàëüíîé ãëóáèíû ïî âñåì âîçìîæíûì íàïðàâëåíèÿì zi
� âîçìîæíî äëÿ ñëó-
÷àÿ ëèíåéíûõ ôóíêöèé. Äàííóþ ïðîöåäóðó ìîæíî âûïîëíèòü ïóòåì ïîäñ÷åòà
÷èñëà hl òàêèì îáðàçîì, ÷òî h z h zl i
b
i
b� � � (èëè h z h zl i
b
i
b� � � ), ïîñëå ÷åãî
íåîáõîäèìî âûáðàòü ìèíèìàëüíîå çíà÷åíèå.
Èòàê, íà âõîä àëãîðèòìà îöåíêè ïîëóïðîñòðàíñòâåííîé ãëóáèíû ïîäàþòñÿ:
âûáîðêà W z zg� { }1, ,� òàêàÿ, ÷òî zi �W, âûáîðêà Q h hm� { }1, ,� òàêàÿ, ÷òî
hl
r�R , è ýëåìåíò äàííûõ h r�R . Íà âûõîäå àëãîðèòìà ïîëó÷àåì E h
Q
W ( ), ÷òî ÿâ-
ëÿåòñÿ ïðèáëèæåíèåì äëÿ ãëóáèíû h. Àëãîðèòì îöåíêè ïîëóïðîñòðàíñòâåííîé
ãëóáèíû ñîñòîèò èç ñëåäóþùèõ øàãîâ: 1) äëÿ i g�1, ,� âû÷èñëèòü
E h z
m
h h z h z h h z h zQ i l l i i l l i i( | ) min (| : | , | : | )� � � � � � �
1
; 2) âîçâðàòèòü E h
Q
W ( ) �
� min ( | )i iE h z .
Àëãîðèòì ïðèáëèæåíèÿ ïîëóïðîñòðàíñòâåííîãî âçâåøåííîãî ñðåäíåãî çíà-
÷åíèÿ ïîçâîëÿåò îïðåäåëèòü ìíîæåñòâî ñëó÷àéíûõ íàïðàâëåíèé z zg1, ,� . Ïðè
ýòîì âçâåøåííîå ñðåäíåå çíà÷åíèå h äîëæíî çàíèìàòü öåíòðàëüíîå ìåñòî â êàæ-
äîì íàïðàâëåíèè. Êðîìå òîãî, ïðîåêöèÿ h äîëæíà èìåòü áîëüøóþ îäíîìåðíóþ
ãëóáèíó, ò.å. áûòü áëèçêîé ê âçâåøåííîìó ñðåäíåìó çíà÷åíèþ ïðîåêöèè ïðè
ïðîåêòèðîâàíèè h hm1, ,� è h íà zi . Ïîýòîìó ïåðâûé øàã çàêëþ÷àåòñÿ â íàõîæ-
äåíèè h ñ ìàêñèìàëüíî âîçìîæíîé ãëóáèíîé â êàæäîì íàïðàâëåíèè.  ñëó÷àå,
êîãäà òàêîãî h íå ñóùåñòâóåò, íåîáõîäèìî óìåíüøèòü òðåáîâàíèå ãëóáèíû
â êàæäîì íàïðàâëåíèè è ïîâòîðèòü ïðîöåäóðó äëÿ íàõîæäåíèÿ ñîîòâåòñòâóþùåãî h.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 53
Àëãîðèòì ïðèáëèæåíèÿ ïîëóïðîñòðàíñòâåííîãî âçâåøåííîãî ñðåäíåãî çíà-
÷åíèÿ ïðèíèìàåò íà âõîäå âûáîðêó W z zg� { }1, ,� òàêóþ, ÷òî zi �W, è âûáîðêó
Q h hm� { }1, ,� òàêóþ, ÷òî hl
r�R . Êðîìå òîãî, èìååì ëèíåéíûé ïðîãðàììíûé
àëãîðèòì *, êîòîðûé íàõîäèò ýëåìåíò äàííûõ (åñëè òàêîâîé ñóùåñòâóåò), ÷òî ñî-
ãëàñîâûâàåòñÿ ñ îãðàíè÷åíèÿìè íà çàäàííîì ìíîæåñòâå ëèíåéíûõ îãðàíè÷åíèé [10].
Íà âûõîäå àëãîðèòìà ïîëó÷àåì ýëåìåíò äàííûõ h r�R è åãî îöåíêó ãëóáèíû E h
Q
W ( ).
Àëãîðèòì ïðèáëèæåíèÿ ïîëóïðîñòðàíñòâåííîãî âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ
ñîñòîèò èç ñëåäóþùèõ øàãîâ: 1) äëÿ i g�1, ,� è l m�1, ,� âû÷èñëÿåì h zl i� ;
2) ïóñòü w wi i
m1, ,� ÿâëÿþòñÿ êëàññèôèöèðîâàííûìè çíà÷åíèÿìè h zl i� ; 3) èñïîëü-
çóåì äâîè÷íûé ïîèñê äëÿ íàõîæäåíèÿ íàèìåíüøåãî t m� 0 2, , /� , äëÿ êîòîðîãî *
ìîæåò íàéòè òàêîå h, ÷òî � i wi
m
t
2
%
$%
(
'(
� h z wi i
m
t
� �
#
%%
&
((
�
2
; 4) âîçâðàòèòü òàêîå h, êî-
òîðîå ïîëó÷åíî ñ ïîìîùüþ àëãîðèòìà * äëÿ íàèìåíüøåãî t íà øàãå 3.
ÇÀÊËÞ×ÅÍÈÅ
 äàííîé ðàáîòå ïðåäëîæåí è èññëåäîâàí íîâûé êîìïëåêñíûé ìåòîä ðåøåíèÿ
ïðîáëåìû âûáîðà îïòèìàëüíîé ãèïîòåçû íà îñíîâå àïîñòåðèîðíîãî äîâåðèÿ
â êëàññå ãèïîòåç äëÿ çàäà÷ êëàññèôèêàöèè äàííûõ. Â ðàìêàõ èññëåäîâàíèÿ
ââåäåíî ïîíÿòèå îòíîñèòåëüíîé ãëóáèíû, îò êîòîðîãî íàïðÿìóþ çàâèñèò îáîá-
ùåíèå êëàññèôèêàòîðà. Ñóùåñòâåííîå çíà÷åíèå â ðåøåíèè ïðîáëåìû âûáîðà
îïòèìàëüíîé ãèïîòåçû èìåëà êîíöåïöèÿ îòíîñèòåëüíîãî âçâåøåííîãî ñðåäíåãî
çíà÷åíèÿ äëÿ íàèáîëåå ãëóáîêîãî êëàññèôèêàòîðà.  ïðîöåññå èññëåäîâàíèÿ
ïðîàíàëèçèðîâàíû ïîðîãîâûå ñâîéñòâà âçâåøåííîãî ñðåäíåãî çíà÷åíèÿ, â ðå-
çóëüòàòå ÷åãî óñòàíîâëåíà èõ çàâèñèìîñòü îò ãëóáèíû äàííûõ. Íà îñíîâå ïî-
ëó÷åííûõ ðåçóëüòàòîâ ïîñòðîåíû ýôôåêòèâíûå àëãîðèòìû äëÿ ðàâíîìåðíîãî
èçìåðåíèÿ îòíîñèòåëüíîé ãëóáèíû è íàõîæäåíèÿ îòíîñèòåëüíîãî âçâåøåííîãî
ñðåäíåãî çíà÷åíèÿ. Ïðåäëîæåííûå àëãîðèòìû ïîçâîëÿþò àïïðîêñèìèðîâàòü
ïîëóïðîñòðàíñòâåííóþ ãëóáèíó è ïîëóïðîñòðàíñòâåííîå âçâåøåííîå ñðåäíåå
çíà÷åíèå çà ïîëèíîìèàëüíîå âðåìÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. J o r n s t e n R . , V a r d i Y . , Z h a n g C . H . A robust clustering method and visualization tool
based on data depth // Statistical data Analysis. — 2002. — P. 354–365.
2. C h a c o n J . I . , D u o n g T . , W a n d M . P . Asymptotics for general multivariate kernel density
derivative estimators // Statistics. — 2011. — 21. — P. 810–837.
3. S e e g e r M . PAC-Bayesian generalisation error bounds for gaussian process classification // The
Journal of Machine Learning Research. — 2003. — 3. — P. 237–268.
4. H e r b r i c h R . , G r a e p e l T . , C a m p b e l l C . Bayes point machines // The Journal of
Machine Learning Research. — 2001. — 1. — P. 247–271.
5. D a v i e s P . L . , G a t h e r U . Breakdown and groups // The Annals of Statistics. — 2005. — 33,
N 3. — P. 981–1027.
6. F i n e S . , G i l a d - B a c h r a c h R . , a n d S h a m i r E . Query by committee, linear separation
and random walks // Theoretical Computer Science. — 2002. — 284, N 1. — P. 27–49.
7. B e n - D a v i d S . , E i r o n N . , L o n g P . M . On the difficulty of approximately maximizing
agreements // Journal of Computer and System Sciences. — 2003. — 66, N 3. — P. 499–511.
8. R o u s s e e u m P . J . , S t r u y f A . Characterizing angular symmetry and regression symmetry //
Journal of Statistical Planning and Inference. — 2004. — 122. — P. 163–170.
54 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
9. O j a H . , P a i n d a v e i n e D . Optimal signed-rank tests based on hyperplanes // Journal of
Statistical Planning and Inference. — 2005. — 135. — P. 307–321.
10. H o l m e s C . C . , A d a m s N . M . A probabilistic nearest neighbor method for statistical pattern
recognition // Journal of the Royal Statistical Society. — 2002. — 64. — P. 295–306.
Íàä³éøëà äî ðåäàêö³¿ 09.03.2016
Î.À. Ãàëê³í
ÀËÃÎÐÈÒ̲×Ͳ ÀÑÏÅÊÒÈ ÂÈÇÍÀ×ÅÍÍß ÔÓÍÊÖ²É ÃËÈÁÈÍÈ Ó ÏÐÎÖÅÄÓв ÂÈÁÎÐÓ
ÎÏÒÈÌÀËÜÍί òÏÎÒÅÇÈ ÄËß ÇÀÄÀ× ÊËÀÑÈÔ²ÊÀÖ²¯ ÄÀÍÈÕ
Àíîòàö³ÿ. Äîñë³äæóþòüñÿ ïðîáëåìè âèáîðó îïòèìàëüíî¿ ã³ïîòåçè â çàäà÷àõ
êëàñèô³êàö³¿ íà îñíîâ³ êëàñó ã³ïîòåç, ðîçïîä³ëåíîãî â³äíîñíî àïîñòåð³îðíî¿
éìîâ³ðíîñò³. Çàïðîïîíîâàíî ìåòîä, ÿêèé áàçóºòüñÿ íà êîíöåïö³¿ â³äíîñíîãî
çâàæåíîãî ñåðåäíüîãî çíà÷åííÿ òà ôóíêö³ÿõ ãëèáèíè, ùî âèêîíóþòüñÿ
ó ïðîñòîð³ ôóíêö³é êëàñèô³êàö³¿. Ðîçðîáëåíî àëãîðèòìè äëÿ àïðîêñèìàö³¿
â³äíîñíî¿ ãëèáèíè äàíèõ òà â³äíîñíîãî çâàæåíîãî ñåðåäíüîãî çíà÷åííÿ, ùî
çàáåçïå÷óþòü ïîë³íîì³àëüí³ íàáëèæåííÿ äî íàï³âïðîñòîðîâèõ àíàëîã³â.
Êëþ÷îâ³ ñëîâà: çâàæåíå ñåðåäíº çíà÷åííÿ, ôóíêö³ÿ â³äíîñíî¿ ãëèáèíè,
îïòèìàëüíà ã³ïîòåçà Áàºñà.
O.A. Galkin
ALGORITHMIC ASPECTS OF DETERMINING THE DEPTH FUNCTIONS IN SELECTING
THE OPTIMAL HYPOTHESIS FOR DATA CLASSIFICATION PROBLEMS
Abstract. The paper analyzes optimal hypothesis selection in classification
problems based on the hypothesis class distributed with respect to the posterior
probability. A method is proposed that is based on the concept of a relative
weighted average value and depth functions operating in the space of
classification functions. Algorithms are constructed to approximate the relative
depth of the data and relative weighted average value providing polynomial
approximation to the half-space analogs.
Keywords: weighted average value, relative depth function, optimal Bayesian
hypothesis
Ãàëêèí Àëåêñàíäð Àíàòîëüåâè÷,
êàíäèäàò ôèç.-ìàò. íàóê, àññèñòåíò êàôåäðû Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Òàðàñà
Øåâ÷åíêî, å-mail: galkin.o.a@gmail.com.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 55
|
| id | nasplib_isofts_kiev_ua-123456789-142015 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T18:46:02Z |
| publishDate | 2016 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Галкин, А.А. 2018-09-20T17:53:27Z 2018-09-20T17:53:27Z 2016 Алгоритмические аспекты определения функций глубины в процедуре выбора оптимальной гипотезы для задач классификации данных / А.А. Галкин // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 43-55. — Бібліогр.: 10 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/142015 519.7 Исследуются проблемы выбора оптимальной гипотезы в задачах классификации на основе класса гипотез, распределенного относительно апостериорной вероятности. Предложен метод, базирующийся на концепции относительного взвешенного среднего значения и функциях глубины, которые выполняются в пространстве функций классификации. Разработаны алгоритмы для аппроксимации относительной глубины данных и относительного взвешенного среднего значения, обеспечивающие полиномиальные приближения к полупространственным аналогам. Досліджуються проблеми вибору оптимальної гіпотези в задачах класифікації на основі класу гіпотез, розподіленого відносно апостеріорної ймовірності. Запропоновано метод, який базується на концепції відносного зваженого середнього значення та функціях глибини, що виконуються у просторі функцій класифікації. Розроблено алгоритми для апроксимації відносної глибини даних та відносного зваженого середнього значення, що забезпечують поліноміальні наближення до напівпросторових аналогів. The paper analyzes optimal hypothesis selection in classification problems based on the hypothesis class distributed with respect to the posterior probability. A method is proposed that is based on the concept of a relative weighted average value and depth functions operating in the space of classification functions. Algorithms are constructed to approximate the relative depth of the data and relative weighted average value providing polynomial approximation to the half-space analogs. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Алгоритмические аспекты определения функций глубины в процедуре выбора оптимальной гипотезы для задач классификации данных Алгоритмічні аспекти визначення функцій глибини у процедурі вибору оптимальної гіпотези для задач класифікації даних Algorithmic aspects of determining the depth functions in selecting the optimal hypothesis for data classification problems Article published earlier |
| spellingShingle | Алгоритмические аспекты определения функций глубины в процедуре выбора оптимальной гипотезы для задач классификации данных Галкин, А.А. Кибернетика |
| title | Алгоритмические аспекты определения функций глубины в процедуре выбора оптимальной гипотезы для задач классификации данных |
| title_alt | Алгоритмічні аспекти визначення функцій глибини у процедурі вибору оптимальної гіпотези для задач класифікації даних Algorithmic aspects of determining the depth functions in selecting the optimal hypothesis for data classification problems |
| title_full | Алгоритмические аспекты определения функций глубины в процедуре выбора оптимальной гипотезы для задач классификации данных |
| title_fullStr | Алгоритмические аспекты определения функций глубины в процедуре выбора оптимальной гипотезы для задач классификации данных |
| title_full_unstemmed | Алгоритмические аспекты определения функций глубины в процедуре выбора оптимальной гипотезы для задач классификации данных |
| title_short | Алгоритмические аспекты определения функций глубины в процедуре выбора оптимальной гипотезы для задач классификации данных |
| title_sort | алгоритмические аспекты определения функций глубины в процедуре выбора оптимальной гипотезы для задач классификации данных |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/142015 |
| work_keys_str_mv | AT galkinaa algoritmičeskieaspektyopredeleniâfunkciiglubinyvprocedurevyboraoptimalʹnoigipotezydlâzadačklassifikaciidannyh AT galkinaa algoritmíčníaspektiviznačennâfunkcíiglibiniuproceduríviboruoptimalʹnoígípotezidlâzadačklasifíkacíídanih AT galkinaa algorithmicaspectsofdeterminingthedepthfunctionsinselectingtheoptimalhypothesisfordataclassificationproblems |