Некоторые положения и задачи теории шаблонов
В работе рассматриваются основные определения, положения и проблемы теории шаблонов. Вводятся новые типы шаблонов, приводятся некоторые свойства полиномиальных шаблонов. Выделяются новые задачи, которые играют важную роль при построении качественных решающих правил....
Збережено в:
| Дата: | 2009 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Кримський науковий центр НАН України і МОН України
2009
|
| Назва видання: | Кримський науковий центр НАН України і МОН України |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/18213 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Некоторые положения и задачи теории шаблонов / А.С. Анафиев // Таврический вестник информатики и математики. — 2009. — № 1. — С. 39-45. — Бібліогр.: 4 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-18213 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-182132011-03-19T12:04:17Z Некоторые положения и задачи теории шаблонов Анафиев, А.С. В работе рассматриваются основные определения, положения и проблемы теории шаблонов. Вводятся новые типы шаблонов, приводятся некоторые свойства полиномиальных шаблонов. Выделяются новые задачи, которые играют важную роль при построении качественных решающих правил. У роботі роглядаються основні означення, положення та проблеми теорії шаблонів. Вводяться нові типи шаблонів, наводяться деякі властивості поліноміальних шаблонів. Виділяються нові задачі, які грають важливу роль при побудові якісних вирішальних правил. The main definitions, positions and problems of template theory are considered. The new types of templates are introduced. Some properties of polynomial templates are considered. New tasks which play an important role of the construction of high-quality decision rules are emphasized. 2009 Article Некоторые положения и задачи теории шаблонов / А.С. Анафиев // Таврический вестник информатики и математики. — 2009. — № 1. — С. 39-45. — Бібліогр.: 4 назв. — рос. 1729-3901 http://dspace.nbuv.gov.ua/handle/123456789/18213 519.7 ru Кримський науковий центр НАН України і МОН України Кримський науковий центр НАН України і МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
В работе рассматриваются основные определения, положения и проблемы теории шаблонов. Вводятся новые типы шаблонов, приводятся некоторые свойства полиномиальных шаблонов. Выделяются новые задачи, которые играют важную роль при построении качественных решающих правил. |
| format |
Article |
| author |
Анафиев, А.С. |
| spellingShingle |
Анафиев, А.С. Некоторые положения и задачи теории шаблонов Кримський науковий центр НАН України і МОН України |
| author_facet |
Анафиев, А.С. |
| author_sort |
Анафиев, А.С. |
| title |
Некоторые положения и задачи теории шаблонов |
| title_short |
Некоторые положения и задачи теории шаблонов |
| title_full |
Некоторые положения и задачи теории шаблонов |
| title_fullStr |
Некоторые положения и задачи теории шаблонов |
| title_full_unstemmed |
Некоторые положения и задачи теории шаблонов |
| title_sort |
некоторые положения и задачи теории шаблонов |
| publisher |
Кримський науковий центр НАН України і МОН України |
| publishDate |
2009 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/18213 |
| citation_txt |
Некоторые положения и задачи теории шаблонов / А.С. Анафиев // Таврический вестник информатики и математики. — 2009. — № 1. — С. 39-45. — Бібліогр.: 4 назв. — рос. |
| series |
Кримський науковий центр НАН України і МОН України |
| work_keys_str_mv |
AT anafievas nekotoryepoloženiâizadačiteoriišablonov |
| first_indexed |
2025-07-02T19:18:41Z |
| last_indexed |
2025-07-02T19:18:41Z |
| _version_ |
1836564004597661696 |
| fulltext |
ÓÄÊ 519.7ÍÅÊÎÒÎ�ÛÅ ÏÎËÎÆÅÍÈß È ÇÀÄÀ×È ÒÅÎ�ÈÈ ØÀÁËÎÍÎÂ
Àíà�èåâ À.Ñ.Òàâðè÷åñêèé íàöèîíàëüíûé óíèâåðñèòåò èì. Â.È. Âåðíàäñêîãî�àêóëüòåò ìàòåìàòèêè è èí�îðìàòèêèïð-ò Âåðíàäñêîãî, 4, ã. Ñèì�åðîïîëü, 95007, Óêðàèíàe-mail: aydera�mail.ruAbstra
t. The main de�nitions, positions and problems of template theory are
onsidered. The newtypes of templates are introdu
ed. Some properties of polynomial templates are
onsidered. New taskswhi
h play an important role of the
onstru
tion of high-quality de
ision rules are emphasized.Ââåäåíèå�àññìîòðèì ñòàíäàðòíóþ ïîñòàíîâêó çàäà÷è îáó÷åíèÿ ïî ïðåöåäåíòàì. Äàíîìíîæåñòâî îáúåêòîâ X, ìíîæåñòâî îòâåòîâ Y è íåêîòîðàÿ íåïîëíàÿ èí�îðìàöèÿî öåëåâîé çàâèñèìîñòè f � : X ! Y ïðåäñòàâëåííàÿ â âèäå êîíå÷íîãî íàáîðà ïðåöåäåí-òîâ f(xi 2 X; yi 2 Y )gì=1, ãäå yi = f �(xi), i = 1::`. Ïðè ýòîì íàáîð fx1; : : : ; x`g � Xáóäåì íàçûâàòü îáó÷àþùåé âûáîðêîé è îáîçíà÷àòü X`.Çàäà÷à îáó÷åíèÿ ïî ïðåöåäåíòàì çàêëþ÷àåòñÿ â òîì, ÷òîáû âîññòàíîâèòü íåèç-âåñòíóþ öåëåâóþ çàâèñèìîñòü f � ìåæäó îáúåêòàìè è îòâåòàìè, ò.å. ïîñòðîèòü àëãî-ðèòì a� : X ! Y , êîòîðûé áóäåò óäîâëåòâîðÿòü ñëåäóþùèì òðåáîâàíèÿì.� Àëãîðèòì a�(x) äîëæåí âîñïðîèçâîäèòü íà îáúåêòàõ îáó÷àþùåé âûáîðêè çà-äàííûå îòâåòû: a(xi) = yi, i = 1::`. Ïðè÷åì, ðàâåíñòâî çäåñü ìîæíî ïîíèìàòüè êàê ïðèáëèæåííîå, â çàâèñèìîñòè îò ñïåöè�èêè çàäà÷è.� Íà àëãîðèòì a� ìîãóò íàêëàäûâàòüñÿ ðàçíîãî ðîäà àïðèîðíûå îãðàíè÷åíèÿ,òàêèå êàê, ëèíåéíîñòü, ìîíîòîííîñòü, ãëàäêîñòü è ò.ä., à òàêæå è èõ ñî÷åòàíèÿ.Áîëåå òîãî, ìîæåò áûòü çàäàíà íåêîòîðàÿ ìîäåëü äàííîãî àëãîðèòìà [1℄.� Àëãîðèòì a� äîëæåí äîñòàòî÷íî õîðîøî âîññòàíàâëèâàòü íåèçâåñòíóþ öåëå-âóþ çàâèñèìîñòü f � íå òîëüêî íà îáúåêòàõ îáó÷àþùåé âûáîðêè, íî è íà âñåììíîæåñòâå îáúåêòîâ X. Äðóãèìè ñëîâàìè, àëãîðèòì a� äîëæåí îáëàäàòü îáîá-ùàþùåé ñïîñîáíîñòüþ.Ïðè ýòîì �ðàçà ¾äîñòàòî÷íî õîðîøî âîññòàíàâëèâàåò¿ îçíà÷àåò, ÷òî èñêîìûéàëãîðèòì a� äîëæåí áûòü ëó÷øèì â íåêîòîðîì ñåìåéñòâå àëãîðèòìîâ îòíîñèòåëüíîíåêîòîðîãî çàðàíåå èçâåñòíîãî �óíêöèîíàëà êà÷åñòâà.Êðîìå ýòîãî, ïðè ðåøåíèè çàäà÷è îáó÷åíèÿ ïî ïðåöåäåíòàì çàðàíåå �èêñèðóåòñÿêëàññ ðåøàþùèõ ïðàâèë A, èç êîòîðîãî è áóäåò âûáèðàòüñÿ îïòèìàëüíûé àëãîðèòì,óäîâëåòâîðÿþùèé âûøåîïèñàííûì òðåáîâàíèÿì.Ïðè ýòîì, â áîëüøèíñòâå ñëó÷àåâ, êëàññ ðåøàþùèõ ïðàâèë A âûáèðàåòñÿ äîñòà-òî÷íî øèðîêèì, ÷òî ïðèâîäèò ê íåïðèìåíèìîñòè ìíîãèõ îöåíîê, íàïðèìåð, îöåíîêÂàïíèêà-×åðâîíåíêèñà [3℄, äëÿ îöåíêè êà÷åñòâà ïîëó÷åííîãî àëãîðèòìà è ïîëó÷å-íèÿ ¾ðåöåïòà¿ � êàê âûáèðàòü îïòèìàëüíîå (áëèçêîå ê îïòèìàëüíîìó) ðåøàþùååïðàâèëî â çàäàííîì ñåìåéñòâå A.
40 Àíà�èåâ À.Ñ.Äëÿ ñóæåíèÿ êëàññà ðåøàþùèõ ïðàâèë A ñ öåëüþ ïîñòðîåíèÿ áîëåå êà÷åñòâåí-íûõ ðåøàþùèõ ïðàâèë áûëà ïðåäëîæåíà òåîðèÿ øàáëîíîâ [2℄. �àññìîòðèì îñíîâíûåîïðåäåëåíèÿ è ïîëîæåíèÿ äàííîé òåîðèè.1. Íåêîòîðûå îïðåäåëåíèÿ è ïîëîæåíèÿ òåîðèè øàáëîíîâÎïðåäåëåíèå 1. Îïåðàòîð t : �! A áóäåì íàçûâàòü øàáëîíîì ìíîæåñòâà àëãî-ðèòìîâ A îòíîñèòåëüíî ïàðàìåòðè÷åñêîãî ìíîæåñòâà �. Åñëè ïðè ýòîì � = P k, òîøàáëîí t áóäåì íàçûâàòü k-ïàðàìåòðè÷åñêèì è îáîçíà÷àòü tk.Ïðèâåäåì çäåñü òàêæå îïðåäåëåíèå ìîäåëè àëãîðèòìîâ [1℄.Îïðåäåëåíèå 2. Ìîäåëüþ àëãîðèòìîâ íàçûâàåòñÿ ïàðàìåòðè÷åñêîå ñåìåéñòâîîòîáðàæåíèé A = f'(x; �) j � 2 �g, ãäå ' : X � �! Y � íåêîòîðàÿ �èêñèðîâàííàÿ�óíêöèÿ, � � ìíîæåñòâî äîïóñòèìûõ çíà÷åíèé ïàðàìåòðà �, íàçûâàåìîå ïðîñòðàí-ñòâîì ïàðàìåòðîâ èëè ïðîñòðàíñòâîì ïîèñêà.Äàííîå îïðåäåëåíèå ìîæíî ïåðå�îðìóëèðîâàòü, èñïîëüçóÿ ïîíÿòèå øàáëîíà.Îïðåäåëåíèå 3. Ìîäåëüþ àëãîðèòìîâ íàçûâàåòñÿ ïàðàìåòðè÷åñêîå ñåìåéñòâîîòîáðàæåíèé A = ff(x) j f = t(�); � 2 �g, ãäå t(�) � íåêîòîðûé �èêñèðîâàííûé øàá-ëîí, � � ìíîæåñòâî äîïóñòèìûõ çíà÷åíèé ïàðàìåòðà �.Çàäàâàÿ ìîäåëü àëãîðèòìà ñ ïîìîùüþ øàáëîíà, ìû àêöåíòèðóåì ñâîå âíèìà-íèå íà êîíñòðóêòèâíûõ îñîáåííîñòÿõ ðåøàþùèõ ïðàâèë è íà âîçìîæíîñòü ñóæåíèÿîáëàñòè íåîïðåäåëåííîñòè, çàäàâàåìîé ìîäåëüþ àëãîðèòìîâ. Ïðè ýòîì ïàðàìåòðè-÷åñêîå ìíîæåñòâî îïðåäåëÿåò êîëè÷åñòâî ïàðàìåòðîâ è èõ äîïóñòèìûå çíà÷åíèÿ, àøàáëîí ïîêàçûâàåò êàêèì îáðàçîì ñâÿçàíû ìåæäó ñîáîé ïàðàìåòðû è ïåðåìåííûå.Òîãäà âîçíèêàþò ñëåäóþùèå äâå èíòåðåñíûå çàäà÷è: ïåðâàÿ (ïðÿìàÿ) � êàê ìîæ-íî èñïîëüçîâàòü ñòðóêòóðó è âèä ñâÿçåé ìåæäó ïàðàìåòðàìè è ïåðåìåííûìè äëÿïîñòðîåíèÿ êà÷åñòâåííûõ ðåøàþùèõ ïðàâèë àäåêâàòíûõ äàííîé âûáîðêå; è âòîðàÿ(îáðàòíàÿ) � çàäà÷à íàõîæäåíèÿ ñòðóêòóðû âûáîðêè îïèñûâàåìîé â âèäå øàáëîíà.Òàêæå ìîæíî ðàññìàòðèâàòü ìîäåëü îòäåëüíîé �óíêöèè.Îïðåäåëåíèå 4. Òðîéêó Mf = h �; t; � i òàêóþ, ÷òî t(�) = f , ãäå t � øàáëîí ìíî-æåñòâà A îòíîñèòåëüíî ïàðàìåòðè÷åñêîãî ìíîæåñòâà � è � 2 �, áóäåì íàçûâàòü ìî-äåëüþ �óíêöèè f 2 A.Îïðåäåëåíèå 5. Ìíîæåñòâî�t(�) = ff 2 A jMf = h �; t;� igáóäåì íàçûâàòü îáðàçîì øàáëîíà t íà ìíîæåñòâå A îòíîñèòåëüíî ïàðàìåòðè÷åñêîãîìíîæåñòâà �.Îïðåäåëåíèå 6. Øàáëîí t íàçûâàåòñÿ óíèâåðñàëüíûì øàáëîíîì âûáîð-êè X` = (xi; yi)ì=1, åñëè 8f 2 �t è 8i = 1; ` âûïîëíÿåòñÿ f(xi) = yi.Áóäåì ãîâîðèòü, ÷òî øàáëîí t óäîâëåòâîðÿåò âûáîðêå X` = (xi; yi)ì=1, åñëè9f 2 �t òàêàÿ, ÷òî 8i = 1; ` âûïîëíÿåòñÿ f(xi) = yi.¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �1' 2009
Íåêîòîðûå ïîëîæåíèÿ è çàäà÷è òåîðèè øàáëîíîâ 41Çàìå÷àíèå.  íåêîòîðûõ çàäà÷àõ ðàâåíñòâî f(xi) = yi ìîæíî ïîíèìàòü êàê ïðè-áëèæåííîå.Îïðåäåëåíèå 7. Øàáëîí tmin íàçûâàåòñÿ ìèíèìàëüíûì øàáëîíîì äëÿ âûáîðêè X`,åñëè îí èìååò íàèìåíüøåå ÷èñëî ïàðàìåòðîâ ñðåäè âñåõ óäîâëåòâîðÿþùèõ âûáîð-êå X` øàáëîíîâ.Òîãäà ñòàíîâèòñÿ àêòóàëüíîé çàäà÷à ïîñòðîåíèÿ ìèíèìàëüíîãî èëè áëèçêîãîê ìèíèìàëüíîìó øàáëîíîâ óäîâëåòâîðÿþùèõ îáó÷àþùåé âûáîðêå! È êàêîâà ñëîæ-íîñòü îòûñêàíèÿ òàêèõ øàáëîíîâ äëÿ ðàçëè÷íîãî ðîäà çàäà÷ îáó÷åíèÿ ïî ïðåöåäåí-òàì.�àññìîòðèì íåñêîëüêî ðàçëè÷íûõ âèäîâ øàáëîíîâ.Îáîçíà÷èì ~�(k) = (�1; : : : ; �k).Îïðåäåëåíèå 8. Øàáëîí tk íàçûâàåòñÿ �-øàáëîíîì, åñëè åãî ìîæíî ïðåäñòàâèòüâ âèäåtk(~�(k)) = h�h1 � 1 �~�(k)� ; '1(x1; : : : ; xn)� ; : : : ; hm � m �~�(k)� ; 'm(x1; : : : ; xn)�� ;(1)ãäå1) x1; : : : ; xn � ñèìâîëû ïåðåìåííûõ �óíêöèé èç A;2) h � m-ìåñòíûé �óíêöèîíàëüíûé ñèìâîë;3) hj � 2-ìåñòíûé �óíêöèîíàëüíûé ñèìâîë;4) 'j � s-ìåñòíûå �óíêöèîíàëüíûå ñèìâîëû, j = 1; m, s 2 f0; : : : ; ng, ïðè÷åì'i 6= 'j, i 6= j, �óíêöèè 'j(x1; : : : ; xn) áóäåì íàçûâàòü ñâîéñòâàìè ìíîæå-ñòâà X âûäåëÿåìûå øàáëîíîì tk;5) j � p-ìåñòíûå �óíêöèîíàëüíûå ñèìâîëû, j = 1; m, p 2 f0; : : : ; kg.Ïðè ýòîì, åñëè m = k è j �~�(k)� = �j, j = 1; k, òî øàáëîí tk íàçûâàåòñÿ ïðîñòûì.Ïóñòü F àëãåáðàè÷åñêîå ïîëå ñ îïåðàöèÿìè ñëîæåíèÿ + è óìíîæåíèÿ � .Ïðîñòîé øàáëîí ñ h(z1; : : : ; zk) = z1 + : : :+ zk, hj(z1; z2) = z1 � z2 è �óíêöèÿìè-ñâîéñòâàìè 'j(x1; : : : ; xn) = xi1 � : : : � xir , j = 1; k, íàçûâàåòñÿ ïîëèíîìèàëüíûì øàá-ëîíîì ìíîæåñòâà �óíêöèé A = ff : Fn ! Fg íàä ïîëåì F îòíîñèòåëüíî ïàðàìåòðè-÷åñêîãî ìíîæåñòâà � = Fk.Ñîãëàñíî îïðåäåëåíèþ, êàæäûé ïîëèíîìèàëüíûé øàáëîí tk ìîæíî ïðåäñòàâèòüâ âèäåt(�1; : : : ; �k) = �1 � xi11 � : : : � xi1r1 + : : :+ �k � xik1 � : : : � xikrk = kXj=1 �j � xij1 � : : : � xijrj : (2)Ïðè÷åì ïðîèçâåäåíèÿ sj = xij1 � : : : � xijrj , j = 1; k, áóäóò ñâîéñòâàìè ìíîæåñòâà X,âûäåëÿåìûå øàáëîíîì t. ×èñëî rj áóäåì íàçûâàòü ðàíãîì ñâîéñòâà sj, à îòíîñèòåëüíîøàáëîíà t áóäåì ãîâîðèòü, ÷òî îí ïîðîæäåí ìíîæåñòâîì ñâîéñòâ S = fs1; s2; : : : ; skgè îáîçíà÷àòü t� S. ¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �1' 2009
42 Àíà�èåâ À.Ñ.Ïîëèíîìèàëüíûé øàáëîí íàä ïîëåì F áóäåì îáîçíà÷àòü tF, à ÷åðåç tk; r � k-ïàðà-ìåòðè÷å
êèé ïîëèíîìèàëüíûé øàáëîí, êîòîðûé ñïîñîáåí âûäåëÿòü èç ìíîæåñòâà Xòîëüêî ñâîéñòâà ðàíãà íå áîëüøå, ÷åì r.Ïîëó÷åíû ñëåäóþùèå îöåíêè ¼ìêîñòè êëàññà ðåøàþùèõ ïðàâèë ïîðîæäåííûõïîëèíîìèàëüíûìè øàáëîíàìè [2℄.Îïðåäåëåíèå 9. Ïîëÿ, ýëåìåíòû êîòîðûõ ìîæíî ïðåäñòàâèòü â âèäå logM-ðàçðÿä-íîãî äâîè÷íîãî êîäà, M <1, áóäåì íàçûâàòü M-ïîëÿìè. M-ïîëå, ñîäåðæàùååñÿ âîìíîæåñòâå ðàöèîíàëüíûõ (öåëûõ) ÷èñåë, áóäåì íàçûâàòüM-ïîëåì ðàöèîíàëüíûõ (öå-ëûõ) ÷èñåë.Òåîðåìà 1. Ïóñòü F íåêîòîðîå M-ïîëå, òîãäà ¼ìêîñòü êëàññà h(�Tk; rF ) îáðàçà ìíî-æåñòâà âñåõ k-ïàðàìåòðè÷åñêèõ ïîëèíîìèàëüíûõ øàáëîíîâ, ïîðîæäåííûõ ñâîé-ñòâàìè ðàíãà íå âûøå r, óäîâëåòâîðÿåò íåðàâåíñòâóh(�Tk; rF ) 6 min( k(r log(n + 1) + logM);k(n log(r + 1) + logM);P (r) logM );ãäå P (r) � ÷èñëî ñâîéñòâ ìíîæåñòâà X, âûäåëÿåìûå âñåìè øàáëîíàìè èç Tk; rF ,ðàíãà íå áîëüøå, ÷åì r.Ñëåäñòâèå 1. �ìêîñòü h(Pk; r(n)) êëàññà Pk; r(n) ïîëèíîìîâ íàä M-ïîëåì ðàöèî-íàëüíûõ ÷èñåë Q îò n ïåðåìåííûõ ñòåïåíè íå âûøå r
k îòëè÷íûìè îò íóëÿêîý��èöèåíòàìè óäîâëåòâîðÿåò íåðàâåíñòâóh(Pk; r(n)) 6 min( k(r log(n+ 1) + logM);k(n log(r + 1) + logM);(n+ r)!n!r! logM ):Ñëåäñòâèå 2. �ìêîñòü h(P 2k; r(n)) êëàññà P 2k; r(n) ïîëèíîìîâ Æåãàëêèíà îò n ïåðå-ìåííûõ ñòåïåíè íå âûøå r
k îòëè÷íûìè îò íóëÿ êîý��èöèåíòàìè óäîâëåòâîðÿ-åò íåðàâåíñòâóh(P 2k; r(n)) 6 min k(r log(n+ 1) + 1); k(n log(r + 1) + 1); rXi=0 Cin! :Êàê ïîêàçàíî â [2℄, ó÷åò ÷èñëà ïàðàìåòðîâ ïðè îöåíèâàíèè ¼ìêîñòè êëàññà ðåøà-þùèõ ïðàâèë ïîçâîëÿåò íàìíîãî óëó÷øèòü èçâåñòíûå îöåíêè. Êðîìå ýòîãî, äàííàÿòåîðåìà ïîä÷åðêèâàåò öåëåñîîáðàçíîñòü ïîñòðîåíèÿ ìèíèìàëüíûõ (ñ ìèíèìàëüíûì÷èñëîì ïàðàìåòðîâ) øàáëîíîâ.Ïðèâåäåì ÷èñëåííóþ îöåíêó çàâèñèìîñòè âåðîÿòíîñòè íåñëó÷àéíîé íàñòðîéêèíà âûáîðêó îò ÷èñëà ïàðàìåòðîâ k-ïàðàìåòðè÷åñêîãî ïîëèíîìèàëüíîãî øàáëîíà.Òåîðåìà 2. Äëÿ òîãî, ÷òîáû âåðîÿòíîñòü P(�tk ; `; Æ`) íàñòðîéêè íà êàêèå-íèáóäü`� Æ` ýëåìåíòîâ âûáîðêè X` äëèíû ` àëãîðèòìàìè ñåìåéñòâà �tk , � îáðàçà k-ïàðà-ìåòðè÷åñêîãî ïîëèíîìèàëüíîãî øàáëîíà, � áûëà ìåíüøå íåêîòîðîãî çàäàííîãî � > 0¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �1' 2009
Íåêîòîðûå ïîëîæåíèÿ è çàäà÷è òåîðèè øàáëîíîâ 43íåîáõîäèìî, ÷òîáû ÷èñëî ïàðàìåòðîâ k óäîâëåòâîðÿëî óñëîâèþk < 1log ` �`� Æ`+ log � � log �CÆ`` �
(`� Æ`)�� ;ãäå
(`� Æ`) = 11� 2�(`�Æ`)+1 ! 1 ïðè `� Æ`!1, Æ` � ÷èñëî îøèáîê, äîïóñêàåìûõíà îáó÷àþùåé âûáîðêå àëãîðèòìîì èç ñåìåéñòâà �tk ïîñòðîåííûì â ðåçóëüòàòåîáó÷åíèÿ.Äîêàçàòåëüñòâî. Ïî òåîðåìå 2.7 èç [2℄P(�tk ; `; Æ`) <
(`� Æ`) � CÆ`` � 2k(log `�1) � 2�R0(X`;�tk )èëè, ñîãëàñíî îïðåäåëåíèþ ñòåïåíè ÷àñòè÷íîé çàêîíîìåðíîñòè R0 [2℄,P(�tk ; `; Æ`) <
(`� Æ`) � CÆ`` � 2k(log `�1) � 2�(`�k�Æ`):Òîãäà, åñëè
(`� Æ`) � CÆ`` � 2k(log `�1) � 2�(`�k�Æ`) < �; (�)òî è P(�tk ; `; Æ`) < �. Èç (�) ñëåäóåò, ÷òîlog �
(`� Æ`) � CÆ`` � 2k(log `�1) � 2�(`�k�Æ`)� < log �;log �CÆ`` �
(`� Æ`)�+ log �2k(log `�1)�+ log �2�(`�k�Æ`)� < log �;log �CÆ`` �
(`� Æ`)�+ k(log `� 1)� (`� k � Æ`) < log �;k(log `� 1)� `+ k + Æ` < log � � log �CÆ`` �
(`� Æ`)� ;k log ` < `� Æ`+ log � � log �CÆ`` �
(`� Æ`)� :Îòêóäà ñëåäóåò óòâåðæäåíèå òåîðåìûk < `� Æ`+ log � � log �CÆ`` �
(`� Æ`)�log ` : �Ñëåäñòâèå 3. Äëÿ òîãî, ÷òîáû âåðîÿòíîñòü P(�tk ; `; 0) áåçîøèáî÷íîé íàñòðîéêèíà âûáîðêó X` äëèíû ` > 10 àëãîðèòìàìè ñåìåéñòâà �tk áûëà ìåíüøå íåêîòîðîãîçàäàííîãî � > 0 íåîáõîäèìî, ÷òîáû ÷èñëî ïàðàìåòðîâ k óäîâëåòâîðÿëî óñëîâèþk < `+ log �log ` :Äîêàçàòåëüñòâî. Ñëåäóåò èç òåîðåìû 2, ó÷èòûâàÿ, ÷òî Æ` = 0 è
(`) � 1 ïðè` > 10 [1℄. �¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �1' 2009
44 Àíà�èåâ À.Ñ.Êðîìå ýòîãî â [2℄ áûëà ïîëó÷åíà ÷èñëåííàÿ îöåíêà çàâèñèìîñòè âåðîÿòíîñòèíåñëó÷àéíîé íàñòðîéêè íà âûáîðêó îò ÷èñëà ïàðàìåòðîâ k-ïàðàìåòðè÷åñêîãî ïîëè-íîìèàëüíîãî øàáëîíà äëÿ áóëåâîãî ñëó÷àÿ (ðàññìàòðèâàåòñÿ áóëåâà âûáîðêà Xf̀0;1g).Ñëåäñòâèå 4. Äëÿ òîãî, ÷òîáû âåðîÿòíîñòü P(�tk ; `; Æ`) áåçîøèáî÷íîé íàñòðîé-êè íà âûáîðêó Xf̀0;1g äëèíû ` > 10 àëãîðèòìàìè ñåìåéñòâà �tk , � îáðàçà k-ïàðàìåòðè÷åñêîãî øàáëîíà íàä ïîëåì f0; 1g, � áûëà ìåíüøå íåêîòîðîãî çàäàííîãî� > 0, íåîáõîäèìî, ÷òîáû ÷èñëî ïàðàìåòðîâ k óäîâëåòâîðÿëî óñëîâèþk < `� log `+ log �:Ïðèâåäåì òàáëèöó, êîòîðàÿ ïîêàçûâàåò êàêèì äîëæíî áûòü ÷èñëî ïàðàìåòðîâ k,÷òîáû âåðîÿòíîñòü íåñëó÷àéíîé áåçîøèáî÷íîé íàñòðîéêè íà âûáîðêó Xf̀0;1g äëèíû `k-ïàðàìåòðè÷åñêèì ïîëèíîìèàëüíûì øàáëîíîì áûëà âûøå 90%.` k 610 320 1230 2240 3150 4160 51
` k 670 6180 7090 80100 901000 98710000 99832. Òåîðåìà ñóùåñòâîâàíèÿ ïîëèíîìèàëüíîãî øàáëîíàÒåîðåìà 3 (ñóùåñòâîâàíèÿ ïîëèíîìèàëüíîãî øàáëîíà). Äëÿ ïðîèçâîëüíîé êîððåêò-íîé âûáîðêè X` äëèíû ` ñóùåñòâóåò k-ïàðàìåòðè÷åñêèé ïîëèíîìèàëüíûé øàá-ëîí tkF, k 6 `, óäîâëåòâîðÿþùèé âûáîðêå X`.Çäåñü âîçíèêàþò ñëåäóþùèå èíòåðåñíûå çàäà÷è:� çàäà÷à ïîèñêà óñëîâèé ñóùåñòâîâàíèÿ è âèäà îáó÷àþùåé âûáîðêè X`, äëÿ êî-òîðîé íå ñóùåñòâóåò k-ïàðàìåòðè÷åñêîãî ïîëèíîìèàëüíîãî øàáëîíà ñ k < `ïàðàìåòðàìè óäîâëåòâîðÿþùåãî âûáîðêå X`;� çàäà÷à íàõîæäåíèÿ ìèíèìàëüíîãî k, ïðè êîòîðîì äëÿ âûáîðêè X` ñóùåñòâó-åò óäîâëåòâîðÿþùèé åé k-ïàðàìåòðè÷åñêèé ïîëèíîìèàëüíûé øàáëîí.Çàêëþ÷åíèå ðàáîòå ïðèâåäåíû îñíîâíûå îïðåäåëåíèÿ, ïîëîæåíèÿ è ïðîáëåìû òåîðèè øàá-ëîíîâ. Ââåäåíû íîâûå òèïû øàáëîíîâ, òàêèå êàê, óíèâåðñàëüíûå è �-øàáëîíû. Ïîëó-÷åíî óñëîâèå íà êîëè÷åñòâî ïàðàìåòðîâ k-ïàðàìåòðè÷åñêîãî ïîëèíîìèàëüíîãî øàá-ëîíà tk, ïðè êîòîðîì âåðîÿòíîñòü íàñòðîéêè íà âûáîðêó àëãîðèòìàìè ñåìåéñòâà �tkáóäåò ìåíüøå íåêîòîðîãî � > 0.Âûäåëåíû íîâûå çàäà÷è òåîðèè øàáëîíîâ, êîòîðûå èãðàþò âàæíóþ ðîëü ïðèïîñòðîåíèè êà÷åñòâåííûõ ðåøàþùèõ ïðàâèë è ñóæåíèè îáëàñòè íåîïðåäåëåííîñòèïðè ðåøåíèè çàäà÷ îáó÷åíèÿ ïî ïðåöåäåíòàì.¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �1' 2009
Íåêîòîðûå ïîëîæåíèÿ è çàäà÷è òåîðèè øàáëîíîâ 45Ñïèñîê ëèòåðàòóðû1. 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, 2008, - p.p. 292-297.2. Àíà�èåâ À.Ñ. Òåîðèÿ øàáëîíîâ â çàäà÷àõ îáó÷åíèÿ ïî ïðåöåäåíòàì è âûáîðà ìîäåëåé. Äèññåð-òàöèÿ íà ñîèñêàíèå ó÷åíîé ñòåïåíè êàíäèäàòà �èçèêî-ìàòåìàòè÷åñêèõ íàóê. � 2007. � 135 ñ.3. Âàïíèê Â.Í. Âîññòàíîâëåíèå çàâèñèìîñòåé ïî ýìïèðè÷åñêèì äàííûì. Ì.: Íàóêà, 1979. � 448 ñ.4. Âîðîíöîâ Ê.Â. Âû÷èñëèòåëüíûå ìåòîäû îáó÷åíèÿ ïî ïðåöåäåíòàì. Êóðñ ëåêöèé ïî ìàøèííîìóîáó÷åíèþ. � 2009 ã. � 42
.http://www.ma
hinelearning.ru/wiki/images/8/8d/Voron-ML-Intro.pdfÑòàòüÿ ïîñòóïèëà â ðåäàêöèþ 21.12.2008
¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �1' 2009
|