автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Исследование индуктивных методов вывода знаний в экспертных системах

Нацюнальна акаделпя наук Укра'пш 1нститут мбернетики ¡меш В. М. Глушкова

РГЕ

"5 CEI1 m<t

ол

На правах рукопису

ЦВеТКОВ Олександр Михаилович

ДОСЛЩЖЕННЯ 1НДУКТИВНИХ M ET ОД IB ВИВОДУ ЗНАНЬ В ЕКСПЕРТНИХ СИСТЕМАХ

05.13.16 — застосування обчислювальнси техн'жи, математич-ного моделювання та математичних метод!в в наукових дослщженнях

Автореферат дисертаци на здобуття наукового ступеня кандидата 4пзико-математичних наук

Khïb 1994

Дисертащею е р^копис.

Робота виконана в Науково-учбовому центр1 прикладно! ¡н-форматики HAH УкраГни.

Науковий KepiBHUK: доктор ф1зико-математичних наук

ГУПАЛ Анатолш Михайлович

Офщшш опоненти: член-кореспондент HAH Украши, доктор

ф1зико-математичних наук МАР'ЯНОВИЧ Тадеуш Павлович,

кандидат ф13ико-математичних наук ГАЛАГАН Микола 1ванович

Провщна установа: Кишський ушверситет iMeHi

Т. Г. Шевченка.

Захист в1дбудеться » —19'/ р. о-

год. на заадант спещал1зовано1 вчено'1 ради Д 016.45.01 при 1нститут1 юбернетики iMeHi В. М. Глушкова HAH Укра'ши за адресою:

252650 К.и1в МСД 22, проспект Академжа Глушкова, 40.

3 дисерташею можна ознайомитися у б1блютеш 1нституту

Автореферат розюланий «—-- 19 99 р.

Учений секретар спещал1зовано1 вченоУ ради

СИНЯВСЬКИЙ В. Ф.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ i

Актувльн! с?ь проблеми. В даний час при .досуйдженнях з1 штучного 1нгелекту сформувався потукшгй самост!йний напрямок - розробка i використання експертних систем. Иого мета полягаз у розробЩ систем, спромокних вир1шувати вахк1 для ладани-експерта задач! за допомогою обчислювально! техн1кя. У б!льшост1 випадк1в експерн1 системи розв'язують задач1, що 1х зажко формал! зувати, чи задач1, як1 не малть алгоритм!чного розв'язання.

Клас ВЕЖКоформал! зованкх задач волод1в одн!шо чи дек1лькома 1з наступних характеристик: задача не може бути виранена у числов!й форм1, немоклкво точно визначити ц1льову функц1ю, не 1снув алгоритм!чного розв'язку задач!, алгорита1 чний розв'язок 1снуз, алэ недосяжнлй внасл!док обмеженоет1 pecypclB.

Отримання знань е основним етапом у розробц1 будь-яко! ексшртно1 системи. Процвс отримання знань для б1лыпост1 д1ючих екешртних систем мокна розпод1лити на три егапи: отримання знань в1д експерта, орган!зац1я знань; що забззшчуз ефективну роботу системи, та представления знань. Очевидно, що найб1льш вузьким м1сцем у цьому процес! в добування знань в1д експерт1в. Основна складн1сть полягав у тому, що експерт досить часто не в змоз1 коректно сформулювати пршщипи, котрими в1н користувався при розв'язанн1 задач1. Тому для сучасного р1вня розвитку експертних систем особливо актуальна проблема побудови кетод1в автоматично! генераЩ! знань. У рамка:, систем штучного 1нтелэкту цей напрямок отримав наззу - машине навчання (machine learning), !накше - 1ндуктизний вив1д. Основна мета цих метод1в - отримання знань про предметну область (р1зного роду эалежностей, причинко-наагЛдкових зв'язк1в) на ochobI анал!зу приклад!в 1з ц1з! предметно! о0ласт1.

Мета роботи :

- розробка 1 досл1дкення метод1в 1ндуктквного виводу з точки зору теорП складност1 та И використання у практатних застосуваннях;

- розроска матод1в представления даних для задач, малинного навчшшя.

На.укоза новизна. 3 математично! точки зору, найб1льш' розробленими для розв'язання задач Индуктивного виводу в Мбтоди црикладно! статистики - факторий 1 дискрим1нантний енал!з, метода перев1рки статистичних ппотез. Незвакеючи на глибоку теоретичну 1 практичну розробку, застосування чисто стетестячних метод! в в експертыих системах далеко не завзди приноссть оч!куван1 результата. Цэ пов'язано з рядом причин: коректне застосування статистичних мэтод1в вимагез виконвння невних умов на початкових даних (нормалынстъ розгодШв, р1вн1сть ковар1ад1йних матрнць та" 1н.), котр1 часто порушуються на реальних наборах даних, кр!м того, на великих наборах приклад1в статистичн! метода вшагаить значнах обчислгавальних ресурс1в.

У завропонован1й робот1 розрослен1 1 обгрувтоваШ мэтода 1 ндуктквного виводу, як1 можуть працювати з дэв1льними наборами початкових даних. Принципово вовоа моклив1стю запрогонованих метод! в в спромоаШсть породаення нових атрибупв, тобто зм!ни початкового . простору ошс1в задач1. Досл1дкення в обласи теорИ символьних о0*ект1в привели до ново1 лог1чно1 трактовки понятая "гарна гтотеза".

Загальна методика досл!днень. Йатематичнш шгаршш, який використовувався у робои, е математичка лоПка, теор1я ймов1рностей 1 теор1я оптиШзацП.

Практична ц1ннють результат! в доел! давнъ. Результата досл1даенъ кожуть Оути Оезпосередньо ' викоргстзн! для розв'язання задач 1з галузей матвр1алознавс!гва (прогнозування властивостей нових .матер1вл1в, визначення олтзгаальша парамвгр1в технолог1 чних процес1в), медацики (постановка д1агнозу за спостережуваними симптомами), солэкцп, захисту рослин 1 багатьох 1нших. Ряд практичних приклад, в описано у трет1й глэв1 дисертацП, додаэться в1дпов1дш1й акт упровадкення.

АпробаШя робота. Результат,: дпеертац! йно! роботи вккладалися 1 оЗговорювалися ни се;.::нарах 1 конференШях:

1. М1жнародна конференция "1нтелектуал1зац1я систем баз даних" (Кал1н1нград, 1992р. ).

2. М1жнародний науково-техн1чний сем!нар "Теоретичн1 1 прикладн1 пробдеми ■ ■ моделювання предметних областей у системах баз даних 1 знань" (Туапсе, 1992, 1993pp.).

3. Науков1 семишри Кауково-учОового центру прикладно1 1нформатики АН Укра1нн у 1991-1994р.

Публ!кац! I. Ochobhi результата дасертацП опубл1кован! у роботах [1-9].

Структура 1 обсяг роботи. ДисертаШйна робота склада-еться з1 вступно! частини, трьох глав, захлючно! частини, двох додатк1в та списку л1тературл (77 найменувань). ООсяг робота складае 180 стор1нок машинописного тексту.

ОСНОВНШ ЗМ1СГ РОБОТИ • ДисертаШйна робота присвячэяа розробц1 та реал1зац11 метод! в 1ндуктивного виводу знань. При цьому автором впконана нэступна робота:

- систематизована 1 доопрацьована теор1я • снмволышх об'ект1в, що е дом1нуючох> в област1 представления знань у задачах машинного навчання, на ochobI розвитку теорП повних сищзольних oO'sktIb розрсблен! в1дпов1да! влгорятми;

- запропонован1 1 реал1зоЁан1 алгоритма 1ндуктивного виводу, як! спро.уонн1. модкф!кувати дерева рШень по м1р1 надходаення нсвих навчшочих приклад1в. виконаШ ощнки складносП;

- представлен! метода "п1др!залня" дерев ривпъ, що п!двщтть яхють кл8сяф1кац11 нових приклад1в, проведено nopl еняеня ' з !снушими алгоритмами, що показало перевагу розробленкх кетод1в в якост1 прогнозу на 5-Ю в1дсотк1в;

- розроблен! алгоритми "конструктивно!" 1ндукцИ на деревах р!шень, доведен! тэореми, що Шдтверджують доц1льн1сть застосування даних алгоритм!в;

запропонозано ряд метод!в, що дозволять використовувата експертн1 знання у процес! !ндукы11;

- розроблбн! алгоритма иобудови так зезних лист1в р!шень для багатозначного в:иадку, доведена теорема про

пол!ном!вльну складн! сть наьчання клзсу k-JIP(n), який м1 стать листи ршень, кокний терм яких склэдаеться не б1лыпе Hls з к -repule на mhokikI п змШних;

для kokíToThkx алгоритм! з запропоновано нове Пйретвор&ннй, якэ дозволяв будуютл 0лизьк1 до м1н1мальних кои1тети лШйних нер'вностей;

- программ ревизована сСолонка система 1ндуктивного виводу, яка дозволяв за дспоу.огою розроОлених мэто,д1в розв'язуазата широкий клас задач, И опис надаеться у Додатку. 2.

Запропонован! метода перов1рен1 на пракгичних задачах, надаеться в1дпов!дний акт упроваднекня.

У вступи!й частив! дасертацП обгрунтовувться ■ актуальн1сть теми, навалено ряд основних роб1т з ule! тематики 1 коротко викладен1 ochobhí результата.

У гдвв1 1 шсткться огляд сучвсного ствну теоретичних розрсОок в област1 1ндуктивного виводу функц1й, наводяться ochobhI означения i теорэми.

У глав! 2 проведена розроОка метод1в представления знань та алгоритм!в 1ндукгквного виводу. Представлено пор1вняльний анал1з запропонованих алгоритм! в на приклад1 задач1 лрогнозування по наданому хШчному окладу зварювально-технолопчних властивостей покритих електрод1в. Ця та ряд 1нших задач докладно розглядаються у трет1й глаз1 роботи.

У розд! л! 2.1 розвинена теор1я символьних об'ект1в, на ocsoBl яко1 запропоновано новий алгоритм 1ндуктивного виводу.

Символьной оО'ект визначаеться як кон'юнкЩя значень, цо приймазться змилшми. Зм1нна у - це в1дображэння у:п *• 0. Д0 п - мнохина об' ект1 в 1 0 - мнозшна спостережуваних значань у. Заувакимо, цо кожний рядок у масив1 даних, що ошсуе oO'skt, мокэ Оути вираненкй кон'юнкц1ею лог1чних твердаень, котру ми назвемо под! ею. Таким чином, множила о розглядагться як мнскика 6.-61« ктзрких оЗ'ект1в. Нехай - 3V.1HH1, як! БизниЧбн: из мпзкян! о 1 кабувеють значения 1з <^,..,0 » ühoshh:. г: роэглядаяюя як

Шдмножича П' ~ 01 Х...К 0р множини ус1х можливих елементарних о0'вкт1в. Елеменгэрнв под1я визначазться як е1 = = , ДО О-.. тоОто як предикат вигляду "зм1нна у набувае свого значения 1з Цэ означав, що 1у± - У1] -лопчнэ об'вднання под1й 1у± = {у^}] для ус1х у У±. Розкирення е1 визначавться як |е1|п = Сш с о: у±М е У.^).

Означения 7. ОО'ект-тверднення - це кон'юнкШя под1й типу = У^З.тобто а = [</1 = * [уд => У^].

Означения 8. Множина об'ект1в 1з о, що задовольняз оО'ект-твордаення а позначаеться |а|п 1 утворюв розширення а у п: |а|н = (ы е о: Для 1=1.....q}.

Елвментарний об'бкт утворювться 1з елемент1в п в1добраванням п •* Б : 7-Ы = = у^ш)] Гур=ур(и) 3.

Для спровдння позначень припустимо, що визначено мноянну символьних об'вкПв Б на множин! о, яка описувться зк1зщп;га у1: п - о±. Покладемо, що 5 - кножина об'екив-твердквнь. Еяементарний символьний об'ект,

побудований на основ1 елэмент1в п, такок налекить Б. Розширення символьного об'вкта в е 5 у множин! о позначаеться з' 1 складаеться 1з елементарних об'ект1в у М е Б таких, що € п налекить розпшренкю в у я. 1шпши словами,

з' = {7Ы ев;»( 181п}*

Означения 9. (Означения порядку). V в1, в2 € Б з^ вг тод1 1 Пльки тод1, коли в^ £ в'г.

Означения 10. (Означения сл!детва 1 узагальнення). . V в1, з2 е Б говоримо, шо а, походить 1з з2 1 що С1льш загальний, н1ж а^ тод! 1 йльки тод!, коли а, < в2.

Озшчеиня 11. (Означения об'еднвння 1 перетину символьных об'ект! в).' Визначико з, и зг (в1дпов1дно в, (1 еа) як кон'хшкц1ю ус1х символьних 0<3'6КТ1В 1з Б, розширення ЯКО! ШСТИТЬ В^ 1 В2 (В1ДПОВ1ДНО м!ститься водночас у в\ А в'£).

Теорема 8.

1. Об'еднання 1 перетин символьних оо'ект1в 1снув завади 1 в ксмутативним 1 асоц1 ативним, тому справедлив!

так1 в1дношення:

з1 П (з2 и в3) = (в, П а.) и (з, П в3);

в, и (Вг П в3) - (Sn и Вг) П (s1 U Вэ).

2. тз а = 81 u е2 не виилквее, що в' » s^ U s^. а ■ильки що (я^ и ор es'. 3 i нее го с5оку, коли s = з1 П s2, то з' =» з', П в'г.

НохзЯ задат оимвольний об'акт в 1 ä(s) - множила елементарних под1й, кон'кнкгйя аах визначае а. Такой нехай с (а) - шюкина yeíx елемэнтернхх под!Я, розши] ння як"х М1стять s' 1 бс - ков'юнкШя ус-ix елеменИв 1з c(s).

Теорема 9.

и й{в°) - с(р) 1 (s°)' =з'.

2. s° = { ü T(Wl): ы1 € |a|n>.

3. s° = С Л eL: eL s с(э) }.

Оэщдченля 12. Важлив!сть об'екта в е Б стасуеться plsimuea пом!к об'еднанням розиирень елементарних под1й, що визначають в, Ще^з)), 1 його розширенням в' - fl(e¿(s)).

TOÖTO

H(s) ж card о cardL ( UCe¿íe)) - Л(е^(з)).

0зн8чення 13. Простота символьного об'екта s е S - це наймешэ число Si (а) елементарних под1й, такие, то розагирення 1х кон'юнкцП зб1гаеться з розширенням в. Об'ект я зветься простим, ком card d(a) = S±(s).

Означенна 14. Сшвольний об'ект а в повним тод! 1 Ильки куц, доли с(э) = Ü(8).

Теореыа 10.

1. V s € S. 8° - повний (кбто d(a°) c(s°)).

2. Коли символышй об'ект в -' об'еднання чи перетин, симзолших od'eKTlB, тод! з - говниЯ.

п0бн1 симеольн1 об'екти узагальнюють визначення "понятая" у машинному навчашй як "висловлюЕання, що описув дэяку загапьну 1нформац1ю про оь екти, як1 каркать до дшюго класу". Тому повн! симзолый об'екти мочеуть вистудати як зм1стоьн1 предотавники в1дпов!дних кла&в ■ у задачах машинного навчання. Загальна схема алгоритму опиоуетьоя таким чином:

1. На ОСКОВ1 1с"увчнх даних визначити тили символьних об'ект! в. У найпросПшому випадку - Цб елементарн1 под11 ЕНГДЯДУ lyL = Vi3.

2. Визпачити для кожного класу об'ектя, що знаходяться у в1днош9кн1 частковог- порядку, та 1зо.льовач! елемвити.

3. За допо. огою огорашй об'едншшя для 1зольов£»на елемент! в 1 переткну д. л об'ект!в, що знаходяться у в1дношенн! чвсткоеого порядку, для кожного класу породит» множили повних об'ект!Е.

4. На основ! тестуючо1 множили приклад! в для кокного класу визначити лайкра^. Шдмножини повних об'якт!в, котр1 у подалыгому застосовужться як продотавники в1дпов1дних клас!в при розв'язанн1 задач нласиф1кац11.

У оозд!л! 2.2 розглянуто алгоритме,' в cckobí яких лекитъ побудованв зв тими чи 1шш.к принципами дерево р1шень.

. Формально дерево р1шень визначшться як структура, стзорена 1з:

а) .листових вуэл1в (чи вузл!в в1дпов1д!), як! утримують назву класу;

0) нелистовкх вузл1в (чи ву-Шв piшення), як1 утримуюта етрибутний тест, шлъних з !шюши вузлеми у в!дпов1дност1 si значениями тестуемого атрибута.

Ховний приклад опксувтъсл списком пар атрибут-значения 1 приписувться до того чи 1ншого класу. Множину атрибут! в. що використовуеться для опису цриклзд1в, позначимо через А, а - конкретний атрибут, as A, 1£U|A|. де |А| - число атрибут! в. Для кожного атрибута а множину моклизих вначень позначимо через V±, конкретна значения атрибута, де

1 |V I - число значень, котро моке набувати

атрибут а1.

Алгоритм побудови дерева ршень представлений у розд!л! 2.2.1 1 складазтъся !з двох крок1в:

1. Кож ус! приклада належать одному класу, тод! дерево р1шэнь - листаний вузол, що утрямув !м'я класу.

2. У противному вииадку:

а) визначветъся як атрибут з наЯшншою Е-м1роя;

б) для кожного значения Ybeat ± атрибута а^^ рекурсивно будуються дерева на основ! при:слад1в, ¡цо мають значения vbas(. атрибута abe¡jt.

E-Hipa обчислюеться наступшпл -ииом. Для дэнсго вузла

нехай:

р - число позитивних пршслад1в;

п - число нбгативних прккладцв;

p1;J- число позитивних приклад1в 1з значениям у±3 атрибута aJ_.

n1;J- число кегативних приклад1в 1з значениям атрибута

I^i' р. .+ п..

Е(п ) = У-У-Ü- Кр,,.п,,).

1 J=1 р + п 13

Г о, при х ш о,

Kar.y) ~ \ О, при у - О,

_ JL- 1ой S— - JL-io* -И— в 1шомУ I. х+у ь х+у х+у & х+у випадку.

. Е-функц1я - це теорегико-1нформац1йна м1ра, що заснована на ентропП. Ця функц1я оЩнгое м1ру невизначепосг1 у клвсиф1кац11 при використанн! вибраного атрибута у вузл1 р1шення. Е-метрика волод1е даяким недол1ком, вона дае при побудов1 дереза перевагу атрибутам з б1льшим числом монливих значень. Полишений вар1ант метрики, який переборна цей недол!к, зветься метрикой в1дношення 1 мае вигляд

Kp.ip-ECc^)

Ег(а1)=

iv(a4)

-00

Д9

якщо Kp.iO-EiB^^g, у противному випадку,

Шо ) « _ Г "ij log "1д Kal' jfe, P + n p + n

Ш

8- 5 (1(р,п)-Е(а1)).

Даний алгоритм дозволяе побудувати для несуперечно! множики приклад1в повне дерево, тобто дерево, на основ1 котрого коасний приклад 1з початково! мнолшни буде КЛ8СИф1ХУВ37ИСЯ в1рно.

При навчаян1 на б1льших к!лькостях приклад].в очевидна необх1дн1сть побудови 1нкрементних алгоритм! в. На в!дм1Ну

з1д алгоритмов, котр! будукть нэбори лрЕвил на ссноь! вс1е1 мнокини прлклад1в, 1,..<рэмоитн1 алгорижи продать у режим лочергового нада~>дкення приклщць. При иодаоджеш:! нового пржла"у, коли несбхш.^. наб1р правил коригувться з яаймэншиш ватратами.

У розд! л! 2.2.2 запропоксвако чотири 1нкрэментних алгоритма. В1дпов1дн1 оц1ики склздност! наводэн1 в таблиц!, де <1 - число атрибупв, Ь - максимальна к!льк1атъ знааднь атрибут! в, п - число лавчвючих приклад! в.

'Габлиця

Алгоритм Дрэст1 оперецИ Обчиолення Е-м!рк

1БЗ 0(пс12) 0(Ъй) 1БЗ* 0(п2 ■ с!2) 0(п-Ьа) 1Б5Н ' ССп-й-Ь4) С{п-Ьа) _1Б5_____0(П-Ьй)__о;п-аг)__

В осганн1 роки було розроблено дек1лька метод! в "п1др1зашш" дерев р1 шень. Щ п1дходи р1зняться звстосуванням рЬних криторПв, як1 вшористовуються при п1др1закн! деревз, ко створве деяку складн1сть для " 1х пор1вняння.

У роздШ 2.3.3 представлено новиЯ п1дх!д до "п1др1занняп дерев р!шень. шо базуеться на м1н1м1защ1 помилки класкф! каи11 методу 1 модиф!кованому бзйеоовському п1дход1 до оиДнкн ймов!ряостей.

3 використаяням т-1мсв1рно1 оц1нки "статична помилка" у даному вузл1

« 1 П + РаоШ я - П0 + <1 -рас)И

. Еа = 1 ~ N + т = -!ПГ т

де

N - сумарке число приклад1в у вузл1; То - число приклад! в класу С, по мИ:1м!зуе 2я; для даного га рао - апр1орна ймов1рн!сть класу 0; ш - параметр методу.

Динам!чиз помилка сбчислтеться з врахуванням ощнкк помилок кл0сиф:кац11 Шддерзвами:

Еъ = ^ РА .

де р1 - йтлов! рн! сть того, со сб'ект буде помилково

класиф! ковано i-м п!ддеревом, , - помилка для 1-го Шддеровв.

Запрогонований алгоритм застосовуз правило: коли у даному вузл1 динам1чна помилка б! дыне, н1к статична помилка, то вузол п!др1заеться.

Виб!р конкретного значения параметра m заложить в1д ступеня запумленост1 почагкових даних ■ 1 моке запроповоэувазкся експертом у дан! я предмета! й облает! йбо визначатися в автоматичному режим! , максим1зуючи' точн!сть класиф! кац11 на нэзалэкному набор! даних (тестов1й мнокин1).

При побудов1 дерев р!шекь на предмет!шх областях з досить великою к!льк1стю атрибут! в це мове призводити до знач-.ого розростання дерева.- Одним з шлях1в переборення ц!е! складаост! е конструктивна 1ндукц1я, тобто автоматично породження нових атрибут1в.

У роэд1л! 2.2.4 запропоновано ряд нових алгоритм1в конструктивно! 1НДУКЦ11, ЯК1 використовують ДИЗ'ЮНКТИЕНе породження нових атрибут! в у вузлах. дерева р!шень.

Нехай V - миозина 1з п булевих атрибут1в 1 С - множила ус!х кон'юякшй, заснованих атрибутами 1з V. Представимо диз'юнктивну нормаяьну форму (ДНФ) над множкною V у вигляд1 Г « С, + С„ + ...+ С , де G.ç 0 1 m - позитивно число. Для'

i с. ш 1

кожного i, 1«1<и. позначимо через V множину атрибут1в у тармх С± ! через К± - число елемент1в ц!е! множили.

Озкачоння 16. í в цДНФ формулою, коли для козгного 1<1, JM, W3. V{Ci)nV(CJ)=£0}.

Без втрати сп!льност1 припустимо, то U±™10i = V. Значения функцП 1 на конкретному набор! значень позначимо через

Нехай Г - дерево pi топь над множинов зм!нних 7. Кокний наб1р значень атрибупв визначаз шлях 1з кореневого вузла Г до листових вузл1в. Позначимо через L(x) листовий вузол ! нахай TU) - нлас, котрим позначено листовий вузол. Будемо говорит, що Т екв! валентно 1, коли на кожноод забор! значень атрибут! в вжонуаться Т(дг) = Их).

Toopoua 11. Нехай f - цДН5 формула над шокйною зн1ншк 7. Нудь-яке дерево ргш-энь, еквивал'-нгнб Г, маз .не менше

к1 • кд. • кт лисп в.

Показником спромониост1 породкення нових атрибут1в (ПОЛНА) для даного понятая мокэ служита в1дношення числа можливих нових атрибут!в до загального числа. вузл1в дерева, що представляв поняття.

1з попередньо! гооремк вшгливвз:

Теорема 12. ц-к-^егта-! ДНФ, представлена у вигляд! 61 парного дерева, маз не мешпе н1к 1к лист! в 1 1к -1 тестових вузл1в 1 ПС1ТНА не мента ни 1 - 1к/(1к- 1).

Класичн1 системы 1ндукишного виводу застосовують для представления приклад1з прост1шу мову представления знань типу атрибут-значения. Ала к очевидно, гцо використання знань про предаетну область можэ ютотнкм чином вплинути на як1сть отриманил гЮТтез 1 обмекити необх1дний переб1р.

У розд! л! 2.2.5 як . мова представления г!пстез вико-ристовуеться нерекурсивна мова тип1зованих . хорновських клас1в з запереченням, тобто ппотези, я«1 магать вигляд А ♦ 10,..,Ъп , де А - атом (продикатаий символ над термом) Ь1 - л1терал (атом з/без запереченням). Шд тип1зован1стю мови маеться на уваз1, що для кожного аргументу визначено тип, тобто мнокина його можливих значень. Це можв бути дискретний наб1р, неперервний 1нтервал 1 т.д. Позитивн1 1 негативн1 приклади описумться у вигляд1 в1дношень пом1и атрибутами об'екта, знания про предаетну область складаетъся 1з предакатних визначэнь у форм1 хорновських клас1в ё запереченням (можливо, рекурсивних).

Основна 1дея полягав в об'вднавн1 метод1в 1ндуктивного виводу а б1льш широкими момивостями мов представления знань типу предикатно1 лог1ки першого порядку, що дозволяв на етап1 1ндукц11 використовувати експертн1 знания.

На першому кроц1 алгоритму знания про предай гну область, позитивн1 1 негативн1 приклади перетворюються у представления атриОут-значення. Один 13 в1домих алгоритма 1ндуктиеного виводу генеруе наб1р правил у вигляд п1сля чого Ш правила перетворюються знову у предикату ■ форму. Знания про предаетну область визнзчсють в1даогаення пом!ж атрибутами I описукш/'Я предикатаими визначоннями.

В1др!зняються утал1тн! предккати та уткл! тн! функц!!. Уткл1тна фукгац я - це предикатнэ визначення з вказ!вкою еххдних 1 вих1дн::х аргумент!в, угсл1тний предикат припускав :-;аявн1сть т!лы;и вх1дкиу. аргумент! в.

Ух.л1тн1 предиката можуть бути гашегричними в1 двоено деякях пар аргумент!в одного типу. Для прикладу. б1нарний предикат q (Х,У) таметричшй но X 1 У, коли X, У напекать до одного типу Т 1 с(Х,У)=д(У,Х) для ус!х значень X 1 У. На аргументах одного типу визна-гаеться сшегричний утил!тний предикат "р1Бн1сть" { = ).

Запрспонозигяй п1дх1д мае ряд пэреваг у лор1внянн1 з чисто 1ндуктквники алгоримзш. Пс-перше, допускееться опис приклад1в у виг.т;яд1 в1дноЕень, що с1лые зрозум1ло 3 точки зору екстарга, гго-друге, на ■ етап! 1вдкц!1 можуть використовуватася знания про предметну область, що у кГнцегому п1дсумку приводить до отркмання С1льш эагальних опис!з. -

Одним 1з теорзтичних папрямл1в в облает! машинного ' навчшшя $ Еизначення максимально шкливих клас1в понять, котр! допусжають наьчашш на сснов1 приклад!в за приАнятний час. Зручним представлениям для булзвих функц1й е так ;..шн! листа р1шень.

У розд!л! 2.3.1 понятая листа р1п:онь узатальнено на багатом!рний вкладок, модиф1ковано та проведено розробку в1дпов1дних алгоритм!в. Некий N - мнокпна атрибут!в; о1- 1-й атрибут, Л±~ мнокика гначень 1-го -отркбута. |А;1| -

к1 лысеть р1 зня значэнь атрибута с^; а±}- знечэння 1-го атрибута ¿-го об'скта, да КЛОп, п - число об'ект1в, як! с:п;:ую: ъ понятая. Кожний об'аст приписуетьсл до одного 1з клас!в ?к<:Р, КШ, де 1 - число клас1з. Очевидно, що 1<ш. Кокний об'ект з в1дпов1дкш клвсом оветься прик.;адом Б. Назвемо К-КНЗ кон'юнктиьну нормальну форму, кожний клао р.ко1 ст.чгь не б1лыид к л1тэрагцв, вишовШю к-ДНФ -д;:з'>я1ктивку нормальну форму, кожний терм яко! м1стить не С1льые к л1терал1в. К-с1аиве-КК:> означав КНФ, що складаеться но (ильше Н1к 1з К ¡и.оС!в, й-^ета-ДКО - ДНФ, яка складаеться не б!льзо к! г; 1з К тег.л!в. В1дм1тимо, що 'к-гепп-ДНФ в

п1дмнокиною к-КНФ 1 к-с1Еизе-КШ - п1дмношнои к-ДНФ.

Означения 17. /лет р1шень - це список . I пар (f1 ,v1),.., (I ,т j, до коаний 1±- це терм 1з <исла

W = яч= 0(nk), K02ÍH9 у - значения 1з Р 1 остения фуннц1я

í - nocTiíbía фун::ц1я "1сгина". У зкпадку, коли v^rfO. 1 >, певним способом визяачвйтъся булава функЩя: для кожного набору лгеХп L(x) дор!вкюв v^, дэ J - най7.мнший !нг;экс, такий, що f (а:)^!. Лист р1ыень формал1зуз правило типу 11-then-eis9íí...ela<?.. ГГозначиио лист р!шень, що складевться 1з тори! в доеккни, меншо1 .чй р1вно1 к ка множил 1з п зм1нних, через к-ЛР(п). Аналог1чно k-ДНФ 1 k-КНФ на miiokiihI 1з п зм1нних позначимо через к-ДНФ(п) 1 к-КНФ(п), через к-ДР{п) - дерево р1шенъ з довжшгою шляху в1д кореневого до листовкх вузл1в не б1лы£вы к.

Для 61 парного випадау спрвведлив1 наступш теореми:

Теорема 13. Для OíkSn к-КНФ (n) 1 к-ДНФ (n) s строгими Шдмножинами к-ЛР(п).

Теорема 14. „ля С^кСп к-с1аизе-КНФ(п) i к-гегш-ДНФ(п) - строп шданожини к~ЛР(п).

Теорема 16. Для O^k^n 1 п>2 (к-КНФ (n) U к-ДНФ (п)) -строга п1дмяожина к-ЛР(п).

Теорема 16. Для 0¡a<n к-ДР(п) - строга п1дмножина к-ЛР(п).

Задача нввчаючого алгоритму - вибрато 1з простору г1потез F ту ппотезу (функШю), котра в1дпов1даз навченому . гоняет». Весь проси р У можна разбита по числу зм1нних, що визначають понятая P=U ™ Р . Взагал! навчазочий алгоритм

починав функцЮнувпння з невеликого п, зб1льшу:очи його за необх! дн1 стю. СкледнЮть навч-ння понятно, котре вибиравться 1з Рп, залетать в!д розм!ру ? . Показником тако1 складносп мокв слукити величина Á=log|Pn|.

Означения 18. Прост 1 р ? називаеться пол1ном1алъно-визначеним, коли юнують алгоритм А 1 пол1ном р(л,.гп). так1, що для даного числа n 1 множили 1з т приклад! в понятая S, А за час р(л,п,т) генерус функцШ в1дпов!дяу S, якщо твка

1снуе.

Нехай Yn=C¡/1,..,уп) - множина зм1нних, y*-(y*,..,'jn) -

нонкретниа наб!р зкаченъ зм1нлих {у(,.. ,уп). Покладзмо, що ка множат зизначено йкоырим розиод1л 1 назчаюча множила приклод1в формузться у В1ДПОВ]ДНОСТ! з «р . Щрою якост1 алгоритму А в йг,юв1рн1сть того, що новий приклад, вибраши! у в1дпов!дноот1 з '¡З , будэ класифИсуважся нов!рно. Длл формат звцП визначимо розходкепня ТЩ поыХа: двома фуккшями Г 1 б на як ймов1ря1сть того, що X I 2 р1зн1:

Коли 1 - "Р1рнь фудкц!л", то визначаз помилку

класиф1кац11 при вккоркстанн! фушцП е. Ми Оудемо створювати алгортми,' геаэруюч1 функц11, як1 втанэтазть понятая з вибраною ран1ше помилкою класиф1кацЛ е, 0^1. Однак ми не кохеко вкмагати в1д таких алгорИ5м1в оириманзя баз:ачо1 точносй заввди. Для формат зац11 "н&йгХршого вкладку" у вибор1 пршиад!в у з1дпоз1дност! з фп взэдемо параметр у, 0^1 1 вимагатимемо, щоб з Ймсз1рн1ств ' не меншою 1-7 алгоритмы гекорували пстрХбн! р! нения.

Означения 19. Простер Р називветься таким, що пол1ном1ально яазчаетюя, коли 1енуе алгоритм А 1 пол1ном так! що для ус1х П, с 1 у, уо1х ймов!рних розпод1л1в Рп на У 1 ус1х функЩй 1€РП, А з ймов1рк1стю Ее мекшои, н1:а 1-7 на основ! мжшгаи навчяачих приклад! в рОЗМ1рОМ Ш=3(А. , 1/в,1/т), Еибрачо! у Б1ДО0В1ДН0СТ1 3 генеруе функцШ 8€?п. таку, що нэГ<г.

Теорема 17. Клас к-Л?(п) е таким, що тл1ном1ьльно нввчаеться.

У тюзд!л! 2.3.2 запролоновано ¿за алгоритма "п!др1зшня" лист1 з р1шб^, ¡до тдвищують Функцюналш! мо£'ливоот1 в!дпов1дша метод1в.

у ?озд!л! 2.4 розглянуто гелетичн1 алгоритма, когхр1 заснованх на стандартах моделях спадковост! та ех- люц11 1з облает! популяц!йно1 генетики I е модельнкм вт1ленням природних механизм! в адаптации Описан! 1 дослШоШ днэрелв з^экт.шност! генетичшх оператор!в - кросинговера. мутацП та 1нварсП, розроблена окспернментапъна система Сепа1;, що

засновала на гоштичних алгоритмах. Система використонув модель представления знань теп:' "атрибут - значения" 1 генеруз правила „нгллду "колк У.чова, то .Не в!дм1ну в1д б1.*ьшост1 аналог! чних систем Сепаг дозволяв гекеруватк правила рхзно! довлжни, що факт^чко вШнюе ггочаткозий прлст1р представлэшя. 0трпман1 таким чином вкзначальн1 фрагмента пот 1м розгллдвються як нов! атрибута 1 Еикоркстовуються для побудови дерев р1 нэнь. Система дозволяо прослдкуеата роль оператора 1нверс1! у побудов! "гарких" правил ! мае можлквост! для гнучкого регулювання ймсв!рнсст! ззстосування оператора мутацП.

Для р1иення задач машинного кавчання такой можуть сути Еикористан1 теоретично добре розроблен! компота! метода. Дллг побудови ком!тэта з м!н1мальним числом член1в застосовуэгься ' метод згортання 3. Н. Черникова. Одкак практична використання цього методу для систем з великим числам нер1зкостей обмэкене через значку обчишшвальну складн1сть. Б1лыг-> застосовуютызя на практиц! алгоритш, як1 ви.эристоаують зниквння розм1рност1 простору.

У роздщ 2.5 зшропоновено нове перетворення, яке дозволяз будуЕатн кш1тети, близък! до сптимальних, за прийнятний чео. Для сжстеми шр'вноотэй (с^,х)>0 , де J - мкокина Шдекс]в, в!добразення

визначазться матрицею р 1з сговпцями 1 1 1, що м!нШзу<з

г

I

р=1

i=t

ckifi

i=i

cpiri

IWi Л

1=1

1=1

Opi1!

до i^lJ'l - 1, р^к, 1C€J1.

Проведено пор1внялышй анал1з ком1тетних алгоритм!в, як1 використовуить р ! зн1 пэретворешя, який показаз практичну ц1нн1сть запропоиовяного перетворення.

У глав! 3 описуззтьея пракгкчн! засгосування запропонованих у poöoTl метод!з 1едуктивного виводу. Bel розрахунки вшонувались з використанням розроблених автором система 1ндуктиЕного виводу п!д нззвою АБС 1 сиотеми ТОРСЗ,

ор1ентованих на IBM FC/AT. УсШптэ резв'язувалися задач1 нрогнозуванкя властивостей нових ~ наплавочких матер1ал1в, зздач1 1з гатуз: гахисту рослин та задач! прогкозуьання органолептачнкх локазжшив йезалкогольних HaiiulB.

оснсвкг вишэзки

Основа! результата роСога полягають у настухшому:

розроблен! та досл1даен1 алгоритма 1ндуктибксго внводу знаяь, як! заонован1 на тгобудов! деров 1 лист1в р1шень;

- розроблен1 алгоритми "конструктивно!" !ндукд11 на деревах р!шень, як1 дозволяють автоматично будувати нов! атрибута, ¡до найкредим чнном охшеують нредметну область;

- запропоновано метода;, як1 дозволяють використовувати зкспортн1 знания у "грацэс! !ндукц11;

- вс1 розроблбн1 метода програмно реал1зоЕан1 у вигляд1 оболонкк окспертно! систеюг 1ндуктивнего виводу;

- доведано теорвми про складна гь в1дпов1дтп: метод1в;

- розроблена теор!я сикволыпес об'окИв, яка дозволяв дата лог! мну трактовку понято "гарна Ппотеза".

Бастосування у системах лиучного 1нтелекту метод! в 2"-',токатично1 генорац11 знань суттвво п'дзкдуз 1х функц!ональШ можливосп, присксрюе при цьому процео утворення в1дпов1днах баз знань.

Запропонован1 у дасертац1йк1й робот! метода дозеолили yenirara риршшти щлий ряд пракгичьтя задач 1з р1аних предоотних областей (бЮлогП, зшэтгу рослин та 1к.}.

1. Гупал А. Л1, Цгеткоз А. М Разработка алгоритмов индуктивного вывода знаний с использованием деревьев решений//УСиМ.— 1992.— №5, —С. 27—31.

2. Гупал А. М., Цветков А. М. Разработка алгоритмов индуктивного вывода знаний с использованием листьев решений/'/Материалы 1-го меж-дунар. науч.-техн. семинара «Теоретические и прикладные проблемы моделирования предметных областей». — Киев.— 1992. — С. 64—69.

3. Гупал А. М., Цветков А. М. Разработка и реализация алгоритмов индуктивного вывода // Использование математических методов и ЭВМ в системах управления и проектирования.— Киев: Ин т кибернетики им.

B. М. Глушкова АН Украины, 1991, —С. 33—37.

4. Цветков А. М. Инкрементные алгоритмы построения деревьев решений // Материалы 2-го междунар. науч.-техн. семинара «Теоретические и прикладные проблемы моделирования семинара «Теоретические и прикладные проблемы моделирования предметных областей». — Киев.— 1993.—

C. 129—133.

5. Цветков А. М. Использование экспертных знаний в процессе индукции // Там же. — С. 62—66.

6. Гупал А. М„ Цветков А. М. Об одном методе индуктивного вывода, основанном на комитетных конструкциях // Кибернетика и системный анализ, —1992.—№ 5. _С. 159—161. ■

7. Цветков А. А\. Разработка алгоритмов индуктивного вывода, основанных на построении деревьев решении // Там же.— 1993. — №3.— С. 174—178.

8. Гупал А. М., Цветков А. М., Пономарев А. А. Об одном методе индуктивного вывода, основанном на «подрезании» деревьев решений//Там же. — 1993,— .V» 5, — С. 174—178.

9. Гупал А. М., Цветков А. М., Пономарев А. А. Методические указания по изучению экспертных систем. — Киев, 1993. — 48 С.

Пип. до яруку 14.07.94. Формат 60><84/16. Пап!р друк. №2. Офс. друк, Ум. друк. арк. 0,93. Ум. фарбо-В1дб. 1,05. Обл.-вид. арк. 1,0. Тираж 100 прим. Зам. 794.

Редакцшно-видавничий В|'дд1л з по.'п'граф1чною дьчышцею 1нституту гибернетнки ¡меш В. М. Глушкова HAH УкраТни 252650 Ки1в МСД 22, проспект Академка Глушкова, 40.