Эмпирическое обобщение и распознавание: классы задач, классы математических моделей и применимость теорий. Часть 1
Предложена классификация задач распознавания по их основным свойствам. Обосновывается целесообразность выбора методов решения, согласованных с особенностями классов задач....
Збережено в:
Дата: | 2010 |
---|---|
Автор: | |
Формат: | Стаття |
Мова: | Russian |
Опубліковано: |
Кримський науковий центр НАН України і МОН України
2010
|
Назва видання: | Таврический вестник информатики и математики |
Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/18183 |
Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
Цитувати: | Эмпирическое обобщение и распознавание: классы задач, классы математических моделей и применимость теорий. Часть 1 / В.И. Донской // Таврический вестник информатики и математики. — 2010. — № 1. — С. 15-23. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraineid |
irk-123456789-18183 |
---|---|
record_format |
dspace |
spelling |
irk-123456789-181832013-02-13T02:07:33Z Эмпирическое обобщение и распознавание: классы задач, классы математических моделей и применимость теорий. Часть 1 Донской, В.И. Предложена классификация задач распознавания по их основным свойствам. Обосновывается целесообразность выбора методов решения, согласованных с особенностями классов задач. Запропоновано класифікацію задач розпізнавання по їх основним властивостям. Обґрунтовується доцільність вибору таких методів рішення, які є узгодженими з особливостями класів задач. Classification of pattern recognition problems is offered. This classification is founded on the basic properties of pattern recognition problems. It is shown, a choice of methods of decisions must be coordinated with features of classes of pattern recognition problems. 2010 Article Эмпирическое обобщение и распознавание: классы задач, классы математических моделей и применимость теорий. Часть 1 / В.И. Донской // Таврический вестник информатики и математики. — 2010. — № 1. — С. 15-23. — Бібліогр.: 8 назв. — рос. 1729-3901 http://dspace.nbuv.gov.ua/handle/123456789/18183 519.95 ru Таврический вестник информатики и математики Кримський науковий центр НАН України і МОН України |
institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
collection |
DSpace DC |
language |
Russian |
description |
Предложена классификация задач распознавания по их основным свойствам. Обосновывается целесообразность выбора методов решения, согласованных с особенностями классов задач. |
format |
Article |
author |
Донской, В.И. |
spellingShingle |
Донской, В.И. Эмпирическое обобщение и распознавание: классы задач, классы математических моделей и применимость теорий. Часть 1 Таврический вестник информатики и математики |
author_facet |
Донской, В.И. |
author_sort |
Донской, В.И. |
title |
Эмпирическое обобщение и распознавание: классы задач, классы математических моделей и применимость теорий. Часть 1 |
title_short |
Эмпирическое обобщение и распознавание: классы задач, классы математических моделей и применимость теорий. Часть 1 |
title_full |
Эмпирическое обобщение и распознавание: классы задач, классы математических моделей и применимость теорий. Часть 1 |
title_fullStr |
Эмпирическое обобщение и распознавание: классы задач, классы математических моделей и применимость теорий. Часть 1 |
title_full_unstemmed |
Эмпирическое обобщение и распознавание: классы задач, классы математических моделей и применимость теорий. Часть 1 |
title_sort |
эмпирическое обобщение и распознавание: классы задач, классы математических моделей и применимость теорий. часть 1 |
publisher |
Кримський науковий центр НАН України і МОН України |
publishDate |
2010 |
url |
http://dspace.nbuv.gov.ua/handle/123456789/18183 |
citation_txt |
Эмпирическое обобщение и распознавание: классы задач, классы математических моделей и применимость теорий. Часть 1 / В.И. Донской // Таврический вестник информатики и математики. — 2010. — № 1. — С. 15-23. — Бібліогр.: 8 назв. — рос. |
series |
Таврический вестник информатики и математики |
work_keys_str_mv |
AT donskojvi émpiričeskoeobobŝenieiraspoznavanieklassyzadačklassymatematičeskihmodelejiprimenimostʹteorijčastʹ1 |
first_indexed |
2025-07-02T19:17:30Z |
last_indexed |
2025-07-02T19:17:30Z |
_version_ |
1836563930730725376 |
fulltext |
ÓÄÊ 519.95ÝÌÏÈ�È×ÅÑÊÎÅ ÎÁÎÁÙÅÍÈÅ È �ÀÑÏÎÇÍÀÂÀÍÈÅ:ÊËÀÑÑÛ ÇÀÄÀ×, ÊËÀÑÑÛ ÌÀÒÅÌÀÒÈ×ÅÑÊÈÕ ÌÎÄÅËÅÉ ÈÏ�ÈÌÅÍÈÌÎÑÒÜ ÒÅÎ�ÈÉ. ×ÀÑÒÜ I
Äîíñêîé Â.È.Òàâðè÷åñêèé íàöèîíàëüíûé óíèâåðñèòåò èì. Â.È. Âåðíàäñêîãî�àêóëüòåò ìàòåìàòèêè è èí�îðìàòèêèïð-ò Âåðíàäñêîãî, 4, ã. Ñèì�åðîïîëü, 95007, Óêðàèíàe-mail: donskoy�tnu.
rimea.uaAbstra
t. Classi�
ation of pattern re
ognition problems is o�ered. This
lassi�
ation is founded onthe basi
properties of pattern re
ognition problems. It is shown, a
hoi
e of methods of de
isions mustbe
oordinated with features of
lasses of pattern re
ognition problems.ÂâåäåíèåÑîâðåìåííîå ñîñòîÿíèå ðàñïîçíàâàíèÿ îáðàçîâ êàê íàóêè õàðàêòåðèçóåòñÿ ïîÿâ-ëåíèåì âïîëíå îáîñíîâàííûõ òåîðèé, èíîãäà áàçèðóþùèõñÿ íà ñóùåñòâåííî ðàçëè-÷àþùèõñÿ èñõîäíûõ ïðåäïîëîæåíèÿõ. Øèðîêî èçâåñòíû àëãåáðàè÷åñêàÿ òåîðèÿ ðàñ-ïîçíàþùèõ è êëàññè�èöèðóþùèõ àëãîðèòìîâ Þ. È. Æóðàâëåâà [4℄, ñòàòèñòè÷åñêàÿòåîðèÿ ðàñïîçíàâàíèÿ Â. Í. Âàïíèêà è À. ß. ×åðâîíåíêèñà [1,2℄, ñòàòèñòè÷åñêàÿ ïà-ðàìåòðè÷åñêàÿ òåîðèÿ, áàçèðóþùàÿñÿ íà áàéåñîâñêîì ïîäõîäå è âåäóùàÿ ñâîå íà÷àëîîò ðàáîò �. Ôèøåðà, ñòðóêòóðíî-ëèíãâèñòè÷åñêèå òåîðèè, MDL, äðóãèå òåîðèè è èõìîäè�èêàöèè. Çàêîíîìåðíî âîçíèêàåò âîïðîñ î ïðèìåíèìîñòè êàæäîé èç ðàññìàò-ðèâàåìûõ òåîðèé ê ðàçëè÷íûì çàäà÷àì è âûäåëåíèè â ýòîé ñâÿçè ñïåöè�è÷åñêèõêëàññîâ çàäà÷. Ñ óêàçàííûì âîïðîñîì òàêæå ñâÿçàíû âûáîð ìîäåëåé ðàñïîçíàâàíèÿ,ìåòîäîâ îáó÷åíèÿ è èõ îáîñíîâàíèå. Âûáîð ïîäõîäà ê ðåøåíèþ êîíêðåòíîé çàäà÷èðàñïîçíàâàíèÿ è åãî îáîñíîâàíèå � íåòðèâèàëüíàÿ ïðîáëåìà. Íî îíà, êàê ïðàâèëî,îñòàåòñÿ â òåíè; óñèëèÿ èññëåäîâàòåëåé íàïðàâëåíû íà ñîçäàíèå àëãîðèòìîâ îáó÷å-íèÿ è îöåíèâàíèå âåðîÿòíîñòè îøèáîê ðàñïîçíàâàíèÿ [1-4℄. Ñóùåñòâåí è ïåäàãîãè÷å-ñêèé àñïåêò ðàññìàòðèâàåìîé â íàñòîÿùåé ðàáîòå ïðîáëåìû: ïðåïîäàâàíèå ïðåäìåòà¾Ìàòåìàòè÷åñêèå ìåòîäû ðàñïîçíàâàíèÿ îáðàçîâ¿. Çäåñü íåèçáåæíî âîçíèêàåò âî-ïðîñ ñðàâíèòåëüíîãî àíàëèçà îáëàñòåé ïðèìåíèìîñòè ðàçëè÷íûõ òåîðèé.Ïðèâåäåííûå ñîîáðàæåíèÿ, âîçíèêøèå â ïðîöåññå íàó÷íîé è ïåäàãîãè÷åñêîé äå-ÿòåëüíîñòè â îáëàñòè ðàñïîçíàâàíèÿ îáðàçîâ, ïîáóäèëè àâòîðà ê íàïèñàíèþ íàñòîÿ-ùåé ñòàòüè. Öåëü ðàáîòû � èçëîæèòü è îáîñíîâàòü ïîäõîä ê îïðåäåëåíèþ îáëàñòåéïðèìåíèìîñòè (èëè íåïðèìåíèìîñòè) îñíîâíûõ òåîðèé îáó÷åíèÿ è ðàñïîçíàâàíèÿ.Ñîîòâåòñòâóþùèå îáëàñòè ïðåäñòàâëÿþò ñîáîé êëàññû çàäà÷ ðàñïîçíàâàíèÿ, îïðåäå-ëÿåìûå îáùíîñòüþ èõ îñíîâíûõ ñâîéñòâ. Áóäåì òàêæå íàçûâàòü òàêèå êëàññû çàäà÷ðàñïîçíàâàíèÿ ñåìåéñòâàìè, åñëè ñëîâî ¾êëàññ¿ áóäåò èñïîëüçîâàòüñÿ â êîíòåêñòåäëÿ îáîçíà÷åíèÿ ìíîæåñòâà îáúåêòîâ ãåíåðàëüíîé ñîâîêóïíîñòè.
16 Äîíñêîé Â.È.1. Êîíöåïòóàëüíàÿ ñõåìà ïîñòðîåíèÿ ïðàâèë ðàñïîçíàâàíèÿ èêëàññè�èêàöèÿ ðåøàåìûõ çàäà÷Íà ðèñ. 1 ïðèâåäåíà ñõåìà, ïðåäñòàâëÿþùàÿ ñâÿçü îáúåêòîâ è ïðîöåññîâ, ïðîèñ-õîäÿùèõ ïðè ïîñòðîåíèè ðåøàþùèõ ïðàâèë ðàñïîçíàâàíèÿ.Íà ýòîé ñõåìå óêàçàíûíåêîòîðûå ñâîéñòâà ðàññìàòðèâàåìûõ îáúåêòîâ.  ñîîòâåòñòâèè ñ êîíöåïòóàëüíîéñõåìîé âûäåëåí êðóã ïðèçíàêîâ, èñïîëüçóÿ êîòîðûå ìîæíî îïèñàòü êëàññû ðåøàå-ìûõ çàäà÷ ðàñïîçíàâàíèÿ.
�èñ. 1. Ñâÿçü îñíîâíûõ îáúåêòîâ è ïðîöåññîâ, ïðîèñõîäÿùèõ ïðè âû-áîðå ðåøàþùèõ ïðàâèë ðàñïîçíàâàíèÿÂûáîðî÷íîå ïðîñòðàíñòâî X ñîñòîèò èç îáúåêòîâ X = (x1; : : : ; xn), íàçûâàå-ìûõ äîïóñòèìûìè, êîìïîíåíòû êîòîðûõ (ïåðåìåííûå-ïðèçíàêè) ïðèíèìàþò çíà-÷åíèÿ èç ìíîæåñòâ Di, i = 1; : : : ; n. Ýòè ìíîæåñòâà ìîãóò áûòü íåïðåðûâíûìè,¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �1' 2010
Ýìïèðè÷åñêîå îáîáùåíèå è ðàñïîçíàâàíèå: êëàññû çàäà÷, êëàññû. . . 17äèñêðåòíûìè, ðàçíîòèïíûìè. Ïîëàãàåòñÿ ñóùåñòâóþùèì íåêîòîðûé íàáîð îñíîâ-íûõ ñâîéñòâ (ïðåäèêàòîâ) !j : D1 � � � � � Dn �! f0; 1g, j = 1; : : : ; s . Ìíîæå-ñòâà Kj = fX 2 X : !j(X) = 1g íàçûâàþò êëàññàìè; ~! = (!1(X); : : : ; !s(X)) �äâîè÷íûé âåêòîð, îïðåäåëÿþùèé ïðèíàäëåæíîñòü îáúåêòà êëàññàì. Çíà÷åíèÿýòîãî âåêòîðà ìîæíî ñ÷èòàòü íîìåðàìè êëàññîâ (ïðè ïåðåñåêàþùèõñÿ êëàññàõ-íîìåðàìè êîìáèíàöèé êëàññîâ). Âûáîðî÷íîå ïðîñòðàíñòâî X ÿâëÿåòñÿ ãåíåðàëü-íîé ñîâîêóïíîñòüþ îáúåêòîâ, èç êîòîðîé èçâëåêàåòñÿ êîíå÷íîå ïîäìíîæåñòâî îáú-åêòîâ fX1; : : : ; Xlg = ~Xl � âûáîðêà, êîòîðàÿ âìåñòå ñ ïîëó÷åííûìè íåêîòîðûì ñïî-ñîáîì çíà÷åíèÿìè ~!(X1); : : : ; ~!(Xl) îáðàçóåò òàáëèöó îáó÷åíèÿ. Òàáëèöà îáó÷åíèÿ �ýòî ñîâîêóïíîñòü ïàð f(Xq; ~!(Xq)); q = 1; : : : ; lg. Âûáîðî÷íîå ïðîñòðàíñòâî îáëàäàåòíàáîðîì ñâîéñòâ, êîòîðûå îòðàæàþòñÿ â òàáëèöå îáó÷åíèÿ.Âîîáùå ãîâîðÿ, íå èñêëþ÷åíî, ÷òî òàáëèöà îáó÷åíèÿ ìîæåò èìåòü ïðîïóñêè âäàííûõ è îøèáêè � êàê â çíà÷åíèÿõ ïðèçíàêîâ, òàê è â çíà÷åíèÿõ ïðèíàäëåæíîñòèêëàññàì. Çàäà÷à îáó÷åíèÿ ðàñïîçíàâàíèþ ñîñòîèò â íàõîæäåíèè ïî òàáëèöå îáó÷å-íèÿ ðåøàþùåé �óíêöèè, ïîçâîëÿþùåé ïðàâèëüíî (èëè ïðèáëèæåííî, íî êàê ìîæíîáîëåå òî÷íî) íàõîäèòü äëÿ ëþáîãî îáúåêòà X èç ãåíåðàëüíîé ñîâîêóïíîñòè çíà÷åíèåíîìåðà êëàññà ~!(X). Áóäåì, îáîáùàÿ, íàçûâàòü çàäà÷åé ðàñïîçíàâàíèÿ çàäà÷ó îáó÷å-íèÿ âìåñòå ñ çàäà÷åé èñïîëüçîâàíèÿ íàéäåííîé ðåøàþùåé �óíêöèè äëÿ îïðåäåëåíèÿíîìåðà êëàññà ~!(X) ïðîèçâîëüíîãî X 2 X. ñîîòâåòñòâèè ñ êîíöåïòóàëüíîé ñõåìîé, îñíîâíûå ñâîéñòâà çàäà÷ ðàñïîçíàâà-íèÿ ñâåäåíû â ïðåäñòàâëåííóþ íèæå òàáëèöó.  ñòîõàñòè÷åñêèõ çàäà÷àõ âñå äàííûå âòàáëèöå îáó÷åíèÿ ÿâëÿþòñÿ ñëó÷àéíûìè âåëè÷èíàìè, èçâëå÷åííûìè èç ãåíåðàëüíîéñîâîêóïíîñòè, âîîáùå ãîâîðÿ, ñ íåèçâåñòíûìè çàêîíàìè ðàñïðåäåëåíèÿ.  íåêîòîðûõñëó÷àÿõ ýòè çàêîíû ïîëíîñòüþ èëè ñ òî÷íîñòüþ äî ïàðàìåòðîâ àïðèîðíî èçâåñòíû. äåòåðìèíèðîâàííûõ çàäà÷àõ êàê îáúåêòû â ãåíåðàëüíîé ñîâîêóïíîñòè, òàê è âñÿèí�îðìàöèÿ â òàáëèöàõ îáó÷åíèÿ äîñòîâåðíû, íî âîçìîæíû ïðîïóñêè è/èëè îøèáêèâ äàííûõ, ñâÿçàííûå ñ ïðîöåññîì èõ èçâëå÷åíèÿ.  íåäåòåðìèíèðîâàííûõ çàäà÷àõ÷àñòü äàííûõ íå îïðåäåëåíà, è íåò íèêàêîé äîïîëíèòåëüíîé èí�îðìàöèè îá èõ âîç-ìîæíûõ çíà÷åíèÿõ.Ìîäåëü èçâëå÷åíèÿ îáó÷àþùåé âûáîðêè îïðåäåëÿåò ñõåìó å¼ âûáîðà èç ãåíåðàëü-íîé ñîâîêóïíîñòè. Íàïðèìåð, ñëó÷àéíûé è íåçàâèñèìûé âûáîð îáúåêòîâ, âûáîð ¾òè-ïè÷íûõ ïðåäñòàâèòåëåé â êàæäîì êëàññå¿. Ìîäåëü èçâëå÷åíèÿ âûáîðêè îïðåäåëÿåòòèïû âîçìîæíûõ îøèáîê â ïîëó÷åííîé òàáëèöå îáó÷åíèÿ. Îò äëèíû âûáîðêè çà-âèñèò êà÷åñòâî ïîñòðîåííîãî ðåøàþùåãî ïðàâèëà ðàñïîçíàâàíèÿ. Íå âñåãäà óäà¼òñÿïîëó÷èòü âûáîðêó, èìåþùóþ äîñòàòî÷íóþ äëÿ ïîëó÷åíèÿ æåëàåìîãî êà÷åñòâà ðàñ-ïîçíàâàíèÿ äëèíó. Èíîãäà èñïîëüçîâàíèå äëèííûõ âûáîðîê ìîæåò ïîâëå÷ü ïåðåíà-ñòðîéêó (over �tting) ðåøàþùèõ ïðàâèë. Áîëüøèå âûáîðêè öåëåñîîáðàçíî ðàçäåëÿòüíà äâå ÷àñòè: îáó÷àþùóþ, ïî êîòîðîé ïðîèñõîäèò èíäóêòèâíûé ñèíòåç ðåøàþùèõïðàâèë, è êîíòðîëüíóþ, ïî êîòîðûì îöåíèâàåòñÿ êà÷åñòâî âûáðàííîãî ðåøàþùåãîïðàâèëà. Êîíòðîëüíàÿ âûáîðêà íå ó÷àñòâóåò â îáó÷åíèè è îöåíèâàåò åäèíñòâåííîåðåøàþùåå ïðàâèëî, íàéäåííîå íà ïðåäâàðèòåëüíîì ýòàïå ñèíòåçà.
¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �1' 2010
18 Äîíñêîé Â.È.Ìåòîä îáó÷åíèÿ îïðåäåëÿåò, êàê èñïîëüçîâàòü òàáëèöó îáó÷åíèÿ äëÿ âûáîðàýêñòðåìàëüíîãî ïî êà÷åñòâó ðåøàþùåãî ïðàâèëà ðàñïîçíàâàíèÿ èç íåêîòîðîãî çà-�èêñèðîâàííîãî ñåìåéñòâà ïðàâèë. Ìåòîä ìîæåò ó÷èòûâàòü öåëûé ðÿä äåòàëåé èèñïîëüçîâàòü ðàçëè÷íûå ïðè¼ìû.  ÷àñòíîñòè, ìîæåò ó÷èòûâàòüñÿ ïîñëåäîâàòåëü-íîñòü ïðåäúÿâëåíèÿ îáúåêòîâ òàáëèöû îáó÷åíèÿ (åñëè îò ýòîé ïîñëåäîâàòåëüíîñòèìîæåò çàâèñåòü ðåçóëüòàò). Âîçìîæíî èñêëþ÷åíèå è äîáàâëåíèå îáúåêòîâ âûáîðêè âïðîöåññå îáó÷åíèÿ. Ñêîëüçÿùèé êîíòðîëü òàêæå ìîæåò ðàññìàòðèâàòüñÿ êàê ìåòîäîáó÷åíèÿ.Ïðàâèëî ðàñïîçíàâàíèÿ èçâëåêàåòñÿ â ïðîöåññå îáó÷åíèÿ èç íåêîòîðîãî çàðà-íåå çà�èêñèðîâàííîãî ñåìåéñòâà ïðàâèë. Ôèêñàöèÿ ýòîãî ñåìåéñòâà ïðîèñõîäèò ñó÷¼òîì âíåøíåé äîïîëíèòåëüíîé èí�îðìàöèè î çàäà÷å, íàïðèìåð, çàâåäîìîé ëèíåé-íîñòè äèñêðèìèíàíòíûõ �óíêöèé, êîòîðûå ÿâëÿþòñÿ ãåîìåòðè÷åñêèì ýêâèâàëåíòîìðåøàþùèõ ïðàâèë ðàñïîçíàâàíèÿ. Êà÷åñòâî èçâëå÷¼ííîãî ïðàâèëà ìîæåò îöåíèâàòü-ñÿ ðàçëè÷íûìè ñïîñîáàìè, íàïðèìåð, ÷èñëîì (÷àñòîòîé) îøèáîê íà îáó÷àþùåé âû-áîðêå, ÷èñëîì îøèáîê íà êîíòðîëüíîé âûáîðêå, äëèíîé àëãîðèòìè÷åñêîãî îïèñàíèÿíàéäåííîãî ðåøàþùåãî ïðàâèëà. Îêîí÷àòåëüíîå ðåøåíèå î ïðèåìëåìîñòè èçâëå÷åí-íîãî ïðàâèëà ðàñïîçíàâàíèÿ ïðèíèìàåòñÿ íà îñíîâå àíàëèçà âñåõ óêàçàííûõ ñâîéñòâçàäà÷è è çàäàâàåìûõ ïàðàìåòðîâ � òðåáóåìîé òî÷íîñòè, íà伿íîñòè, àëãîðèòìè÷å-ñêîé ñëîæíîñòè èçâëå÷¼ííîãî ïðàâèëà. Óêàçàííîå âûøå îêîí÷àòåëüíîå ðåøåíèå òåî-ðåòè÷åñêè ìîæåò ïðèíèìàòüñÿ àâòîìàòè÷åñêè, îïðåäåëÿÿ çàâåðøåíèå ïðîöåññà ðå-øåíèÿ çàäà÷è ðàñïîçíàâàíèÿ èëè ïðîäîëæåíèå ïîèñêà ñ âîçìîæíûìè èçìåíåíèÿìèâ âûáîðå �èêñèðóåìîãî ñåìåéñòâà ðåøàþùèõ ïðàâèë è äðóãèõ ñâîéñòâ. Îäíàêî òà-êîé àâòîìàòè÷åñêèé âûáîð â íàñòîÿùåå âðåìÿ íå ðàçðàáîòàí íà àëãîðèòìè÷åñêîìóðîâíå, ïîýòîìó îí ðåàëèçóåòñÿ èññëåäîâàòåëÿìè íà îñíîâå íåêîòîðûõ ñîîáðàæåíèé,ñ�îðìóëèðîâàííûõ â ïðîöåññå ðåøåíèÿ ïðàêòè÷åñêèõ çàäà÷ ðàñïîçíàâàíèÿ.Äàëåå ïðåäëàãàåòñÿ îïèñûâàòü êëàññû çàäà÷ ðàñïîçíàâàíèÿ â òåðìèíàõ çíà÷åíèéñâîéñòâ, êîòîðûå ïðåäñòàâëåíû â òàáëèöå, ïî ñõåìå:STD=V AR=SFM=SLen=ADI: (1)Çàïèñü âèäà (1) íàçûâàåòñÿ êîäîì çàäà÷è ðàñïîçíàâàíèÿ. Ïðè íåâîçìîæíîñòèõàðàêòåðèçàöèè íåêîòîðîãî ñâîéñòâà çàäà÷è â ñîîòâåòñòâóþùóþ ïîçèöèþ êîäà çàäà-÷è ñòàâèòñÿ ïðîïóñê. Ïðîïóñê îçíà÷àåò, ÷òî ñîîòâåòñòâóþùåå ñâîéñòâî ìîæåò áûòüëþáûì èç åãî ïåðå÷èñëåííûõ çíà÷åíèé â òàáëèöå, è íèêàêîé èí�îðìàöèè î ïðåäïî-÷òèòåëüíîì çíà÷åíèè íåò. Íàïðèìåð, çàïèñüD=D2=R2T=SS=�îïðåäåëÿåò äåòåðìèíèðîâàííóþ çàäà÷ó ðàñïîçíàâàíèÿ ñ áèíàðíûìè ïðèçíàêàìèè ñëó÷àéíûì, íåçàâèñèìûì è áåçîøèáî÷íûì èçâëå÷åíèåì íåáîëüøîãî ÷èñëà ïàð¾îáúåêò-êëàññ¿ â òàáëèöó îáó÷åíèÿ. Ïðè ýòîì äîïîëíèòåëüíàÿ èí�îðìàöèÿ äëÿ çà-äà÷è îòñóòñòâóåò. Êðîìå ýòîãî, â ñèíòàêñèñå êîäîâ áóäåì äîïóñêàòü ëîãè÷åñêèå ñâÿç-êè ¾È¿, ¾ÈËÈ¿, ¾ÍÅ¿ äëÿ êîìáèíèðîâàííîãî îïèñàíèÿ ñâîéñòâ çàäà÷. Íàïðèìåð,�L áóäåò îáîçíà÷àòü íåëèíåéíîñòü; R1T _ R2T � áåçîøèáî÷íûé âûáîð îáúåêòîâ èçãåíåðàëüíîé ñîâîêóïíîñòè ñ áåçîøèáî÷íîé èõ êëàññè�èêàöèåé ¾ó÷èòåëåì¿ èëè áåç-îøèáî÷íûé âûáîð ïàð ¾îáúåêò-íîìåð êëàññà¿ èç ãåíåðàëüíîé ñîâîêóïíîñòè ïàð.¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �1' 2010
Ýìïèðè÷åñêîå îáîáùåíèå è ðàñïîçíàâàíèå: êëàññû çàäà÷, êëàññû. . . 19Îáîçíà÷åíèå Íàèìåíîâàíèå Âîçìîæíûå çíà÷åíèÿ ñâîéñòâàñâîéñòâà ñâîéñòâà çàäà÷è: êîäû è ðàñøè�ðîâêèSTD Ñòîõàñòè÷íîñòü èëè S � ñòîõàñòè÷åñêàÿ íåïàðàìåòðè÷åñêàÿ;äåòåðìèíèðîâàííîñòü Sk � ñòîõàñòè÷åñêàÿ k-ïàðàìåòðè÷åñêàÿ;D � äåòåðìèíèðîâàííàÿ;ND � íåäåòåðìèíèðîâàííàÿ.V AR Äèñêðåòíîñòü èëè Dk � k-çíà÷íûå ïåðåìåííûå;íåïðåðûâíîñòü C � íåïðåðûâíûå ïåðåìåííûå;M � ñìåøàííûå ïåðåìåííûå.SFM Ìîäåëü èçâëå÷åíèÿ R1T � ñëó÷àéíûé, íåçàâèñèìûéè �îðìèðîâàíèÿ è áåçîøèáî÷íûé âûáîð îáúåêòîââûáîðêè èç ãåíåðàëüíîé ñîâîêóïíîñòèñ áåçîøèáî÷íûì (ïðè STD = D)óêàçàíèåì (ó÷èòåëåì) êëàññîâ,êîòîðûì ýòè îáúåêòû ïðèíàäëåæàò;R2F � ñëó÷àéíûé, íåçàâèñèìûéâûáîð ïàð ¾îáúåêò-íîìåð êëàññà¿èç ãåíåðàëüíîé ñîâîêóïíîñòè ïàðñ âîçìîæíûìè îøèáêàìè â ëþáûõèõ êîìïîíåíòàõ;ST � ñïåöèàëüíûì îáðàçîìîðãàíèçîâàííîå èçâëå÷åíèåíå ñîäåðæàùåé îøèáîê òàáëèöûîáó÷åíèÿ (íàïðèìåð, âûáîð òèïè÷íûõîáúåêòîâ èëè îïèñàíèåïðåöåäåíòîâ ýêñïåðòàìè);SF � ñïåöèàëüíûì îáðàçîìîðãàíèçîâàííîå èçâëå÷åíèå òàáëèöûîáó÷åíèÿ, âîçìîæíî ñ îøèáêàìè.SLen Äëèíà âûáîðêè SS � ìàëàÿ âûáîðêà,íå äîïóñêàþùàÿ ïîïëíåíèå;AS � âûáîðêà ñðåäíåé äëèíû;LS � áîëüøàÿ èëè ïîïîëíÿåìàÿ âûáîðêà.ADI Äîïîëíèòåëüíàÿ L � ëèíåéíîñòü; M � ìîíîòîííîñòü;èí�îðìàöèÿ CM � êîìïàêòíîñòü êëàññîâ;î çàäà÷å RR � íàëè÷èå îáëàñòåé çàïðåòàâ ïðèçíàêîâîì ïðîñòðàíñòâå;SI � äðóãàÿ ñïåöèàëüíàÿ èí�îðìàöèÿ.Êëàññ çàäà÷ ðàñïîçíàâàíèÿ D=� =R1T _ R2T _ ST=SS=��àññìîòðèì êëàññ çàäà÷ ðàñïîçíàâàíèÿ, îïðåäåëÿåìûé êîäîìD=� =R1T _R2T _ ST=SS=� :Çíà÷åíèå ïàðàìåòðà SLen = SS îïðåäåëÿåò ìàëóþ âûáîðêó. Ìàëîé ñ÷èòàåòñÿ âû-áîðêà, ïðè îáðàáîòêå êîòîðîé ñïîñîáàìè, îñíîâàííûìè íà ñòàòèñòè÷åñêèõ ìåòîäàõãðóïïèðîâêè íàáëþäåíèé è àïïðîêñèìàöèè, íåâîçìîæíî äîñòè÷ü çàäàííîé òî÷íîñòè¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �1' 2010
20 Äîíñêîé Â.È.è äîñòîâåðíîñòè. �àññìàòðèâàåìûå çàäà÷è � äåòåðìèíèðîâàííûå ñ òî÷íîé îáó÷àþ-ùåé òàáëèöåé: êàæäûé îáúåêò äîñòîâåðíî ïðèíàäëåæèò îäíîìó êëàññó (èëè îäíî-âðåìåííî íåñêîëüêèì êëàññàì, åñëè êëàññû ïåðåñåêàþòñÿ). Ïåðåñå÷åíèÿ êëàññîâ, íåòåðÿÿ îáùíîñòè, ìîæíî ñ÷èòàòü îòäåëüíî âûäåëåííûìè êëàññàìè.Âûáîð ìåòîäîâ è ìîäåëåé ðåøåíèÿ òàêèõ çàäà÷ îïðåäåëÿåòñÿ ñëåäóþùèìè ñî-îáðàæåíèÿìè. �àçáèåíèå èñõîäíîé âûáîðêè íà ñîáñòâåííî îáó÷àþùóþ è êîíòðîëü-íóþ ïðè ðåøåíèè çàäà÷ ðàññìàòðèâàåìîãî ñåìåéñòâà íåöåëåñîîáðàçíî ïî ñëåäóþùèìïðè÷èíàì. Òî÷íîñòü îöåíèâàíèÿ, íåäîñòèæèìàÿ íà ìàëîé âûáîðêå, òåì áîëåå áóäåòíåäîñòèæèìîé íà åå ÷àñòè; áåçîøèáî÷íîñòü èí�îðìàöèè â âûáîðêå è ìàëîå ÷èñëîïðåöåäåíòîâ äåëàåò íåöåëåñîîáðàçíûì îòêàç îò èñïîëüçîâàíèÿ âñåõ íà÷àëüíûõ äàí-íûõ ïðè îáó÷åíèè.Ïðè óäà÷íîì âûáîðå ñåìåéñòâà ðåøàþùèõ ïðàâèë â äåòåðìèíèðîâàííûõ çàäà÷àõèíîãäà ìîæíî óêàçàòü äîñòàòî÷íóþ äëèíó îáó÷àþùåé âûáîðêè äëÿ ïîëó÷åíèÿ òî÷íî-ãî è åäèíñòâåííîãî ðåøåíèÿ.  òàêîì ñëó÷àå íåêîððåêòíîñòü ïî Àäàìàðó, ñâîéñòâåí-íàÿ áîëüøèíñòâó çàäà÷ ðàñïîçíàâàíèÿ, íå áóäåò èìåòü ìåñòà. Ñêîëüçÿùèé êîíòðîëüíåöåëåñîîáðàçåí ïî ïðè÷èíå íåäîñòàòî÷íîé ïðåäñòàâèòåëüíîñòè íà÷àëüíûõ äàííûõ.Âûáîð ðåøàþùåãî ïðàâèëà, îøèáî÷íî êëàññè�èöèðóþùåãî õîòÿ áû îäèí îáú-åêò òàáëèöû îáó÷åíèÿ, ìîæåò ïîâëå÷ü áîëüøèå îøèáêè ïðè êëàññè�èêàöèè ïðîèç-âîëüíûõ äîïóñòèìûõ îáúåêòîâ. Ïîýòîìó ïðèìåíåíèå êîððåêòíûõ àëãîðèòìîâ è òîëü-êî èõ ïðèåìëåìî äëÿ ðåøåíèÿ çàäà÷ ðàñïîçíàâàíèÿ ðàññìàòðèâàåìîãî êëàññà. Äåé-ñòâèòåëüíî, äëÿ ðàññìàòðèâàåìûõ çàäà÷ íåêîððåêòíîñòü (íàëè÷èå íåêîòîðîãî ÷èñëàîøèáîê íà îáó÷àþùåé âûáîðêå) âëå÷¼ò íå ìåíüøåå ÷èñëî îøèáîê äëÿ èçâëå÷¼ííûõðåøàþùèõ ïðàâèë ïî âñåé ãåíåðàëüíîé ñîâîêóïíîñòè. Ïåðå÷èñëåííûå ñîîáðàæåíèÿîïðåäåëÿþò äëÿ êëàññà çàäà÷D=� =R1T _ R2T _ ST=SS=�ñòðàòåãèþ ïîèñêà ðåøàþùåãî ïðàâèëà, íå äîïóñêàþùåãî îøèáîê íà îáúåêòàõ òàáëè-öû îáó÷åíèÿ (êîððåêòíîãî íà âûáîðêå) ñ èñïîëüçîâàíèåì âñåé èìåþùåéñÿ âûáîðêèïðè îáó÷åíèè. Ïîñêîëüêó êîððåêòíûå íà âûáîðêå àëãîðèòìû îáó÷åíèÿ äîñòàâëÿþòíóëåâîå çíà÷åíèå ýìïèðè÷åñêèì �óíêöèîíàëàì êà÷åñòâà îáó÷åíèÿ, îòêàç îò ñêîëü-çÿùåãî êîíòðîëÿ ñòàíîâèòñÿ åùå áîëåå îáîñíîâàííûì.Ïðè êàêèõ æå óñëîâèÿõ óêàçàííàÿ ñòðàòåãèÿ äëÿ êëàññà çàäà÷D=� =R1T _ R2T _ ST=SS=�áóäåò óñïåøíîé: ïîñòðîåííîå ðåøàþùåå ïðàâèëî äåéñòâèòåëüíî áóäåò îáó÷åíî ðàñ-ïîçíàâàíèþ îáúåêòîâ, íå ïðèíàäëåæàùèõ òàáëèöå îáó÷åíèÿ?Ïðåäïîëîæèì, ðåøàþùåå ïðàâèëî áóäåò âûáèðàòüñÿ â ïðîöåññå îáó÷åíèÿ èç ñå-ìåéñòâà ïðàâèë S . Ñåìåéñòâî S îáû÷íî îïðåäåëÿåòñÿ ìåòîäîì ðåøåíèÿ çàäà÷è ðàñ-ïîçíàâàíèÿ (ìåòîäû ðåøåíèÿ çàäà÷ ðàñïîçíàâàíèÿ èíòåíñèâíî ðàçðàáàòûâàëèñü âòå÷åíèå ïðîøåäøåãî ïîëóâåêà; íàïðèìåð, øèðîêî ïðèìåíÿþòñÿ ìåòîä âû÷èñëåíèÿîöåíîê [4℄, ìåòîäû îáó÷åíèÿ íåéðîííûõ ñåòåé, ìåòîäû îáó÷åíèÿ íà îñíîâå ñèíòåçàðåøàþùèõ äåðåâüåâ è äðóãèå [5℄). Çàäà÷è ðàñïîçíàâàíèÿ, íå òåðÿÿ îáùíîñòè, ìîæ-íî èññëåäîâàòü äëÿ ñëó÷àÿ òîëüêî äâóõ êëàññîâ, ñîîòâåòñòâåííî, ñ íîìåðàìè 0 è1. Äàëåå áóäóò ðàññìàòðèâàòüñÿ çàäà÷è ñ äâóìÿ êëàññàìè (åäèíñòâåííûì îñíîâíûì¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �1' 2010
Ýìïèðè÷åñêîå îáîáùåíèå è ðàñïîçíàâàíèå: êëàññû çàäà÷, êëàññû. . . 21ñâîéñòâîì). Èñïîëüçóÿ òàáëèöó îáó÷åíèÿ f(Xq; ~!(Xq)); q = 1; : : : ; lg, ñîñòàâèì �óíê-öèîíàëüíóþ ñèñòåìó 8>>>><>>>>: f(X1) = �1;f(X2) = �2;: : : : : : : : : : : :f(Xl) = �l;f 2 S; (2)â êîòîðîé �q = !(Xq) ÿâëÿåòñÿ íóëåì èëè åäèíèöåé � íîìåðîì êëàññà äîïóñòèìîãîîáúåêòà Xq. �åøåíèåì �óíêöèîíàëüíîé ñèñòåìû (2), åñëè îíî ñóùåñòâóåò, ÿâëÿåòñÿëþáîå êîððåêòíîå íà îáó÷àþùåé âûáîðêå ðåøàþùåå ïðàâèëî (�óíêöèÿ) f � 2 S .Ïðîöåññ îáó÷åíèÿ, íàïðàâëåííûé íà ïîèñê êîððåêòíîãî íà âûáîðêå ðåøàþùåãî ïðà-âèëà, ìîæíî ðàññìàòðèâàòü êàê ïîèñê ðåøåíèÿ f � ñèñòåìû (2). Ïðè ýòîì ðåçóëüòàò,î÷åâèäíî, îïðåäåëÿåòñÿ âûáîðîì ñåìåéñòâà S, â ðàìêàõ êîòîðîãî èäåò ïîèñê. Âûáîðêîððåêòíîãî ðåøåíèÿ f � 2 S (ðåøàþùåãî ïðàâèëà) áóäåì íàçûâàòü òî÷íîé íàñòðîé-êîé íà âûáîðêó. Ïðåäïîëîæèì, äëÿ ëþáîé òàáëèöû îáó÷åíèÿ ñ ïðîèçâîëüíûì ¾ñòîëá-öîì¿ íîìåðîâ êëàññîâ ïðè âûáðàííîì ñåìåéñòâå S âîçìîæíà òî÷íàÿ íàñòðîéêà, ïðè-÷¼ì ñóùåñòâóåò íå åäèíñòâåííîå êîððåêòíîå (íà òàáëèöå îáó÷åíèÿ) ïðàâèëî f � 2 S,à îáó÷åíèå ïðîèñõîäèò ïî âñåé âûáîðêå è îöåíèâàåòñÿ �óíêöèîíàëîì ýìïèðè÷åñêîãîðèñêà ïî ýòîé æå ñàìîé âûáîðêå. Òîãäà íèêàêèõ ãàðàíòèé ïðàâèëüíîãî ðàñïîçíàâà-íèÿ ïðàâèëîì f � îáúåêòîâ, íå ó÷àñòâîâàâøèõ â îáó÷åíèè, íåò. Äåéñòâèòåëüíî, ïðèäîñòàòî÷íî ¾áîãàòîì¿ ñåìåéñòâå S ìîæíî ïîñòðîèòü äëÿ ëþáîãî êîíå÷íîãî ìíîæå-ñòâà, ñîäåðæàùåãî m äîïóñòèìûõ îáúåêòîâ, íå ó÷àñòâîâàâøèõ â îáó÷åíèè, êîððåêò-íóþ íà èñõîäíîé òàáëèöå îáó÷åíèÿ �óíêöèþ f � 2 S, îøèáàþùóþñÿ íà âñåõ ýòèõ mîáúåêòàõ. Äëÿ ýòîé öåëè êàæäîìó èç íèõ ñîïîñòàâëÿåòñÿ íåïðàâèëüíûé íîìåð êëàñ-ñà, è ïîëó÷åííàÿ òàáëèöà ñëèâàåòñÿ ñ òàáëèöåé îáó÷åíèÿ f(Xq; !(Xq)); q = 1; : : : ; lg .Åñëè â ñåìåéñòâå S íàéäåòñÿ êîððåêòíûé àëãîðèòì äëÿ òàêîé îáúåäèíåííîé òàáëèöûäëèíû l + m, òî îí áóäåò ïðèìåðîì ñëó÷àÿ, êîãäà óêàçàííàÿ ñòðàòåãèÿ îáó÷åíèÿ âðàññìàòðèâàåìîì êëàññå çàäà÷, íåñìîòðÿ íà òî÷íóþ íàñòðîéêó, äà¼ò íåïðèåìëåìûéðåçóëüòàò.  òàêîì ñëó÷àå ãîâîðÿò, ÷òî îáó÷àåìîñòü íå èìååò ìåñòà.Äðóãàÿ ñèòóàöèÿ âîçíèêàåò, êîãäà òî÷íàÿ íàñòðîéêà ïðè âûáðàííîì ñåìåéñòâå Sâîçìîæíà òîëüêî äëÿ íåêîòîðîãî ìíîæåñòâà äîïóñòèìûõ âûáîðîê, òàêèõ, â êîòîðûõâñå îáúåêòû â êàæäîì êëàññå îáëàäàþò íåêîòîðûìè îòëè÷àþùèìè èõ îò îáúåêòîâäðóãîãî êëàññà ñâîéñòâàìè. Òîãäà âîçìîæíîñòü ïîëó÷åíèÿ ðåøåíèÿ ñèñòåìû (2) ñðîñòîì äëèíû âûáîðêè l ñâÿçûâàåòñÿ èìåííî ñ ïðîÿâëåíèåì â âûáîðêå óêàçàííûõñâîéñòâ (çàêîíîìåðíîñòåé � ïî Êîëìîãîðîâó) è îáåñïå÷èâàåòñÿ ñóùåñòâîâàíèåì âêëàññå S ïðàâèëà, ñïîñîáíîãî ¾óëàâëèâàòü¿ ýòè ñâîéñòâà. Èìåííî íàëè÷èå çàêîíî-ìåðíîñòåé â ãåíåðàëüíîé ñîâîêóïíîñòè â ñâîþ î÷åðåäü âëå÷åò ïîÿâëåíèå â òàáëèöåîáó÷åíèÿ íå ëþáûõ èç 2n âîçìîæíûõ äâîè÷íûõ ¾ñòîëáöîâ¿ ~� = (�1; : : : ; �q; : : : ; �l),�q = !(Xq), q = 1; : : : ; l, à ¾ñòîëáöîâ¿ ëèøü èç íåêîòîðîãî, îïðåäåëåííîãî ñóùåñòâó-þùåé çàêîíîìåðíîñòüþ, ìíîæåñòâà.Äàëåå V CD(S) îáîçíà÷àåò åìêîñòü ñåìåéñòâà ðåøàþùèõ ïðàâèë (ðàçìåðíîñòüÂàïíèêà-×åðâîíåíêèñà [1,2℄) ¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �1' 2010
22 Äîíñêîé Â.È.Òåîðåìà 1. Åñëè V CD(S) � l, òî íàéä¼òñÿ âûáîðêà fX1; : : : ; Xlg = Xl òàêàÿ, ÷òîäëÿ ëþáîãî ~� ïî òàáëèöå ( ~Xl; ~�) âîçìîæíà òî÷íàÿ íàñòðîéêà.Äîêàçàòåëüñòâî. Cëåäóåò èç îïðåäåëåíèÿ V CD(S) � ¼ìêîñòè ñåìåéñòâà S �Òåîðåìà 2. Åñëè äëÿ ëþáîé âûáîðêè ~Xl ñóùåñòâóåò òàêîé áóëåâñêèé íàáîð ~�, ÷òîïî òàáëèöå( ~Xl; ~�) íåâîçìîæíà òî÷íàÿ íàñòðîéêà, òî V CD(S) < l.Äîêàçàòåëüñòâî. Äîñòàòî÷íî çàìåòèòü, ÷òî óòâåðæäåíèå òåîðåìû 2 ðàâíîñèëüíîóòâåðæäåíèþ òåîðåìû 1 �Ïîñëåäíÿÿ òåîðåìà äàåò íåîáõîäèìîå óñëîâèå îáó÷àåìîñòè äëÿ çàäà÷ ðàñïîçíà-âàíèÿ êëàññà D=� =R1T _ R2T _ ST=SS=�ïðè âûáîðå ñòðàòåãèè, íàïðàâëåííîé íà ïîñòðîåíèå êîððåêòíûõ íà îáó÷àþùèõ òàáëè-öàõ àëãîðèòìîâ: åìêîñòü ñåìåéñòâà ðåøàþùèõ ïðàâèë, èñïîëüçóåìîãî äëÿ íàñòðîé-êè, äîëæíà áûòü ìåíüøå äëèíû âûáîðêè. Çàìåòèì, ÷òî íåîòðèöàòåëüíàÿ âåëè÷èíàl � V CD(S) ìîæåò áûòü èñïîëüçîâàíà äëÿ ïîëó÷åíèÿ îöåíêè íåñëó÷àéíîñòè îáíà-ðóæåíèÿ çàêîíîìåðíîñòè ïî îáó÷àþùåé âûáîðêå [6℄. Óñëîâèå V CD(S) < l îáîñíî-âûâàåò âàæíîñòü çíàíèÿ åìêîñòè èñïîëüçóåìîãî äëÿ ðåøåíèÿ çàäà÷è ðàñïîçíàâàíèÿêëàññà.  ñâÿçè ñ ýòèì ñëåäóþùèé ðåçóëüòàò, ïðåäïîëàãàþùèé èñïîëüçîâàíèå õîðî-øî èçó÷åííûõ ìàòåìàòè÷åñêèõ ñâîéñòâ íåêîòîðûõ êëàññîâ �óíêöèé, ïðåäñòàâëÿåòñÿïîëåçíûì ïðè èçó÷åíèè V CD.Òåîðåìà 3. Ïóñòü �óíêöèîíàëüíàÿ ñèñòåìà (2) ïðè çà�èêñèðîâàííîì ñåìåé-ñòâå ðåøàþùèõ �óíêöèé S äëÿ ëþáîé âûáîðêè ~Xl è ëþáûõ äâîè÷íûõ çíà÷åíèÿõ�1; : : : ; �l = ~� ìîæåò èìåòü íå áîëåå îäíîãî ðåøåíèÿ, è ïðè ýòîì íàéäåòñÿ âûáîð-êà ~Xl òàêàÿ, ÷òî äëÿ ëþáîãî ~� ñóùåñòâóåò ðåøåíèå f1. Òîãäà V CD(S) = l.Äîêàçàòåëüñòâî. Ïîñêîëüêó ñóùåñòâóåò âûáîðêà fX1; : : : ; Xlg, äëÿ êîòîðîé �óíê-öèîíàëüíàÿ ñèñòåìà (2) èìååò ðåøåíèå ïðè ëþáîì äâîè÷íîì íàáîðå �1; : : : ; �l , âñåìåéñòâå S íàéäóòñÿ �óíêöèè, ðàçáèâàþùèå ýòó âûáîðêó íà äâà êëàññà âñåìè ñïî-ñîáàìè. Ïîýòîìó V CD(S) � l. Åñëè ê ëþáîé âûáîðêå fX1; : : : ; Xlg äëèíû l äîáàâèòüîäèí ïðîèçâîëüíûé íå ïðèíàäëåæàùèé åé ýëåìåíò Z èç ãåíåðàëüíîé ñîâîêóïíîñòèäîïóñòèìûõ îáúåêòîâ, òî ìíîæåñòâî ðåøåíèé �óíêöèîíàëüíîé ñèñòåìû8>>>>><>>>>>:
f(X1) = �1;f(X2) = �2;: : : : : : : : : : : :f(Xl) = �l;f(Z) = �;f 2 S; (3)ïðè ëþáîì � 2 f0; 1g áóäåò íå øèðå ìíîæåñòâà ðåøåíèé ñèñòåìû (2). Ïîýòîìó, âñèëó óñëîâèÿ òåîðåìû, ñèñòåìà (3) ìîæåò èìåòü íå áîëåå îäíîãî ðåøåíèÿ. Åñëè îíàíå èìååò ðåøåíèé, òî äëÿ âûáîðêè fX1; : : : ; Xl; Zg äëèíû l + 1 ïðè ïîìîùè �óíê-öèé ñåìåéñòâà S íåâîçìîæíî ïîëó÷èòü ðàçáèåíèå, ñîîòâåòñòâóþùåå áóëåâó íàáîðó�1; : : : ; �l; �. Åñëè æå ðåøåíèå f � ñèñòåìû (3) ñóùåñòâóåò, òî ïî óñëîâèþ òåîðåìû¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �1' 2010
Ýìïèðè÷åñêîå îáîáùåíèå è ðàñïîçíàâàíèå: êëàññû çàäà÷, êëàññû. . . 23îíî åäèíñòâåííîå äëÿ �óíêöèîíàëüíûõ ñèñòåì (2) è (3). Òîãäà � = f �(Z), íî ïðè ïî-ìîùè �óíêöèé ñèñòåìû S íåâîçìîæíî ïîëó÷èòü ðàçáèåíèå âûáîðêè fX1; : : : ; Xl; Zgäëèíû l + 1, ñîîòâåòñòâóþùåå áóëåâó íàáîðó �1; : : : ; �l; ��. Ó÷èòûâàÿ, ÷òî ïîñëåäíååçàêëþ÷åíèå ïîëó÷åíî â ðåçóëüòàòå ðàññìîòðåíèÿ ëþáîé âûáîðêè fX1; : : : ; Xlg äëèíûl, ïîëó÷àåì íåðàâåíñòâî V CD(S) � l, êîòîðîå âìåñòå ñ íåðàâåíñòâîì V CD(S) � läàåò ðåçóëüòàò: V CD(S) = l �Çàêëþ÷åíèå ñòàòüå ïðåäëîæåíà êëàññè�èêàöèÿ çàäà÷ ðàñïîçíàâàíèÿ ïî èõ îñíîâíûì ñâîé-ñòâàì. Îáîñíîâûâàåòñÿ öåëåñîîáðàçíîñòü âûáîðà ìåòîäîâ ðåøåíèÿ òàêèõ çàäà÷ â ñî-îòâåòñòâèè ñ îñîáåííîñòÿìè óêàçàííûõ êëàññîâ. Ïðåäñòàâëåíà ïåðâàÿ ÷àñòü èññëåäî-âàíèÿ â ýòîì íàïðàâëåíèè è ðàññìîòðåí äåòåðìèíèñòñêèé êëàññ çàäà÷D=� =R1T _R2T _ ST=SS=� :Äëÿ óêàçàííîãî êëàññà ïðèâåäåíî íåîáõîäèìîå óñëîâèå îáó÷àåìîñòè è îáîñíîâàíîïðèìåíåíèå êîððåêòíûõ àëãîðèòìîâ. Äàëüíåéøèå èññëåäîâàíèÿ â ýòîì íàïðàâëåíèèñâÿçàíû ñ èçó÷åíèåì äðóãèõ êëàññîâ çàäà÷ ðàñïîçíàâàíèÿ â ñîîòâåòñòâèè ñ èõ êëàñ-ñè�èêàöèåé. Ñïèñîê ëèòåðàòóðû1. Âàïíèê Â. Í. Âîññòàíîâëåíèå çàâèñèìîñòåé ïî ýìïèðè÷åñêèì äàííûì. � Ì.: Íàóêà, 1979. � 448
.2. Âàïíèê Â. Í., ×åðâîíåíêèñ À. ß. Òåîðèÿ ðàñïîçíàâàíèÿ îáðàçîâ. Ì.: Íàóêà, 1974. � 416 ñ.3. Âîðîíöîâ Ê. Â. Êîìáèíàòîðíûå îöåíêè êà÷åñòâà îáó÷åíèÿ ïî ïðåöåäåíòàì // Äîêë. �ÀÍ. �2004. � Ò.394, �2. � C. 175 �178.4. Æóðàâëåâ Þ.È. Îá àëãåáðàè÷åñêîì ïîäõîäå ê ðåøåíèþ çàäà÷ ðàñïîçíàâàíèÿ èëè êëàññè�èêàöèè// Ïðîáëåìû êèáåðíåòèêè. � Âûï.33. � Ì.: Íàóêà, 1978. � C. 5 � 68.5. Devroye L., Gyor� L., Lugosi G. A Probabilisti
Theory of Pattern Re
ognition. Springer-Verlag,NY, 1996. � 636 p.6. Donskoy V. I. The Estimations Based on the Kolmogorov Complexity and Ma
hine Learning fromExamples // Pro
eedings of the Fifth International Conferen
e "Neural Networks and Arti�
ialIntelligen
e"(ICNNAI'2008). � Minsk: INNS. � 2008. � �. 292 � 297.Ñòàòüÿ ïîñòóïèëà â ðåäàêöèþ 20.06.2010
¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �1' 2010
|