Эмпирическое обобщение и распознавание: классы задач, классы математических моделей и применимость теорий. Часть 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 Ukraine
id 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