автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Система индуктивного вывода на основе модифицированного GUHA-метода



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

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

БРАТУСЬ Олександр Васильевич

УДК 681.3.16

СИСТЕМА 1НДУКТИВНОГО ВИВОДУ НА ОСНОВ! МОДИФ1КОВАНОГО

ОиНА-МЕТОДУ

К. 73. V/

ЧЭ-ЬО&гОЗ— математичне та программе забезпечення обчислювальних машин 1 систем

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

КиТв — 1996

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

Робота виконана в 1нститут1 шбернетики ¡м. В. М. Глуш-кова HAH Украши та Науково-учбовому ueHTpi ирикладно! шформатики.

Науков! KepiBHHKH: доктор техшчних наук СТУКАЛО О. С.

доктор ф{зико-математичних наук, ГУПАЛ А. М.

ОфщЬш опоненти: доктор ф1зико-математичних наук

кноповп.с.,

кандидат ф{зико-математичних наук РЕЗНИЧЕНКО В. А.

Провщна оргашзащя: Юй'вський ушверситет

¡м. Т. Шсвчеика.

Захист вщбудеться » ^^¡/' ^ ' 199 ^ р. о —

год. на зас1данн1 спещал13овано! вчено! ради Д 01.39.02 при IncTHTyTi к!'бернетики ¡м. В. М. Глушкова HAH УкраГни за адресою:

252022 Knie 22, проспект Академша Глушкова, 40.

3 дисертащею можна ознайомитися в науково-техшчному apxißi {нституту.

Автореферат розюланий «-»-199 р.

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

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

Эггзтзнз

- 1 -

-ргжпиа робеет

тает. Досв1д створенял та вастосуванмн Штеяектуальннх прикладных систем виявив особднву рсиь внань про предмотну область. Трядиц1йно првдбания знань 8д1йс?эяеть-ся за схемою "експерти-> 1нденери за знаниями-> база знань", яка складае до 90£ партост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ш!с» га вйразэдгяйия. Розроблена система Ш313.Прак,пккз эастосування система зд!йснено у ыежах таких дсговор1в:

1. "Створекня скстеки 1м1тед1йксго вдделюванкя селекц1й-иого лрсцесу !{омялэкско-с?1й!с:х сор'Пз ооимо? яаеншЦ". Ежозпкк - {кститут пзхисту росдин Укра!нсько1 скадемП агрертм наук (УААН), !&рон1зський 1нститут пшз/шЩ УААН.

2. " Рсеро51з гистеш арогяозузання эторкнна! структур« 61 як1з". Згмовикк - Гкститут шлекулярко! 61сиог11 НаШонадь-но'1 згсадемИ наук УграЧни.

3. " розробка 1м1тач1йно1 модел1 функцЮнування ыстгл коедаптацП, зизначсняя умоэ. як1 характеризуй«. стан р1вно-

ваги в агробЮценоэах". Замовник - 1нститут захисту рослин.

4. " Розробка система прогнозування ст1йкост1 с/г куль. тур за спектром гл1ад1на". Замовник - 1нститут захисту рослин.

5. " Розробка принцип!в та метод!в планування створення еколог1чно-пласгичних сорт!в зернових та круп'яних культур з використанням лог1чного 1м!тац1йного моделювання процесу се-лекцП на ПЕОМ". Замовнкк - ДКНТ Укра1ни.

б.. " розробка метод1в, алгоритм1в та програм автоматизо-ваного формування баз и знань за клШкою 1 патогенезом В1Л". Замовник - 1нститут к1бернетики 1м. В.М.Глуикова HAH УкраЧни.

Пу(ШкацП" та апробацН роб!т. За темою дисертацП опу-бл)ковано 16. роб1т. Загальн1 - положения допов1дались та обго-воршались на зас1данн1 Коордшгац! иного ком!тету э обчислю-вэльноЧ техн!ки (ККОТ) по експертних системах у 1985 р. (м.Баку) - кер. Г.С.Поспелов; на зас1данн1 ККОТ по екслертних системах у 1986 р. (м.Ташкент) - кер. Г.С.Поспелов; на респу-б.я1канському сем1нар1 "Математичне забезпечення автоматизова-цм;< систем обробки даних та пакет!в програм" Науково? ради АН УРСР з проблеми "К!бернетика" в 1S86 р. (м.Ки!в) - кер. I.B. Серг!енко.

Структура та обсяг робота. Дисертад!я склагаеться 1з вступу, трьох глав, висновку та списку л1тератури, який rlc-тять 51 найменуванн>;.

3uiCT робот»

У вступ1 обгрунтоауеться актуадьнЮть теми дисертацП. Формулюеться ц!ль досл1дження та наводиться короткий зм!ст дисертацП за главами.

Досв1д побудування та використання Лнтелектуальних систем виявив особливу роль знань. Здобуття анань е трудоемким процесом, який дорого коштуе. Треба створити процедуру автоматичного здобуття знань !з емп!р»чних даних. Процедура повинна мати показник " варт1сть - ефективн1сл> ", який задо-вольняе користувача.

У nepaifl глав! анал!зуються вшоги, яким повинна в1дпо-в1дати процедура автоматичного здобуття знань. Внд1ляються так1 ochobhI вимоги:

авгоматичне породження вс!х эяань в деяк1й мов1;

статистична оц!нка кожного знания;

- 3 -

визначення "суттеврго" знапня;

в1дб1р ус!к "суттевкх" значь;

1нтерпретац1я yclx "сутгсвих" аналь. Таким чином, принцип автоматичного придбання знань формулю-еться як " все суттеве Дал! анал1зуютася методи автоматичного придбання знань, як1 1снуютъ. Разначаеться, що один is метод1в, в1домий як GUHA-метод. наиб 1 ль и повйо в1дпоп1дае наведешь вимогач. Наводиться коротке викладения ШНА-методу.

У друг!й глаз! доводиться, що р!шення в роаум1ня1 6UHA -методу не в!дпов1дае принципу "все суттеве" в частц1 "все". Вводиться поняття "критичний базис". Доводиться, що результат роботи 1ндуктивно1 процедури у виг ляд 1 ¡критичного базису в!д-пов!дае принципу "все суттеве". .Доводиться стверджсн.чя по оп-тим1зац11 побудови критичного базису. Обумовлюеться процедура 1нтерпретац11 критичного базису.

Прийнято обчислення з квантором acoulaui'1 Ф1шера, тобто кванторн1 формули 1нтёрпретуються за доломогсю точного крите-plio перев!рки на незалеянЮть двох ознак (критер!й Ф1шера). Модел1 обчислення: М - < Mod, fi,.... fn >, де Mod - несуча мнсаотна, к!нцева i непуста; fi : Mod -> Vi (i-l,n) - yuapHi воображения модел!; Vi - {1,2,.,.. ki, Un> -.множила значены Un - невизначене значения. Мова обчислення складазться з таких символ!в: Fi,..., Fn - функцЮнальн! символи; х - вид1лена зм!нка; &, (К) - лог1чн! операцП; ~с( - квантор Ф1шера. Л1терал обчислення маг вигляд (K)Fi(x), де К е непуста п1дмножина Vj. 1нтерпретэц1я л!терала : для дов!льного об'екта о 8 Mod I(K)Fi(x)|Со] - 1, ягацо fi(o) належить К, I(K)Fi(х)|[о] - Un. якщо fi(о) - Un. I (K)Fi(x)| [o'l - 0, якщо f i (о) не наделить К. В1дкрит1 вид!лен1 Формули мають вигляд Р(х) - S-CKj Ti (х). I не м1стить однакових елемент!в.

I

ИнтерпретаЩя формули: для дов!льного об'екта о a Mod

|Р(х) | [о] - 0, ягсцо хоча б один л!терал РОО

не1стинний на об'ект! о» |Р(х)|Со] - Un, якяр хоча б один л!терал Р(х)

' невизначенщ; на об'ект! о та нема не!с-тинних л!терал1в, |Р(х)| ЮЗ - 1, якщо вс1 л!тераяи Р(х) 1стшш1 на об'ект! о.

В подальшому визначення smIhhoI х та модел1 М будемо опускати.

Шашачешш я1д$орнудя. Нехай PI - &(К()Fi, Р2 - &(Nj)Fj, тод1

1 j

PI e Шдформулою P2, яшдо I - п1дмнсякина J, Kf Шдшюкина tu для дов1лыюго i з I. Кванторна формула мае вигляд (~«)(Р1,Р2) або Р1~<хР2, де РЗ 1 Р2-в1дкрит1 вид!лен! формули обчислення. 1итерпретад1к кванторно! фэрмули: |Р1~йР2| - 1 тод! 1 т1льки тод1, кади miiUr. к)

Fish (PI. Р2) - £ q(l,r,k.m) < of, де

i-s

О < а < 0.5 - piBOHb прийпйпя Ппотези; s - cardio : |PlS-P2|to] - l>; г - cardio : |Р1|[о] « 1>; к - cardio : |P2|Col - 1}; ш - cardi Mod > - гагальна к!льк!сть об'ект1в Mod; q(i.r.K.m) - rlkl (iR-г) I (ш-k) 1/Ы11 (r-i) I (k-i)! (nn-i-r-k)l. IPl~«P2i - 0. яга» Flsh(Pl,P2) > a. Значения Flsh(Pl,P2) - а* називаеться критичнки pIbhgw формули ( Ппотези ) Р1-<хР2 .

GUHA-негод для еш1рично! модел1 М, формули PI га значения а з Интервалу (0. 0.5] видае р!шония у вигляд! базису та доповпеиня.

йсначсги/я базисной Сорнулк. Для даних (M.Pl.cü форх!ула Р базиспа, якщо

¡Р1-чхР| - 1 ( Flsh(Pl.P) < й ), IPl-чйЗ! - 0 ( Flsh(Pl.Q) > ос )« де Q - оудъ-яка непуста пЗдформула Р.

ВидЬгешш Оазису повинно в!дпов1даги шщ!лешш еэшшюс. суттсвкх знань з дотршанням принципу " все суттсве". По!сзг.е-ко, то базис у визначеин! ШНА-методу не в1дпов1дае даному

принципу в частил! " все ".

Нехай для (М, Р1, <х) Р - баэисна формула, тод1

а) Р1бЬ(Р1,Р) <, «

б) Р1я11(Р1,0) > а, де 0 - будь-яка непуста тдформула Р. Виберемо СГ - п!дФормулу Р. таку, що Г1з!т(Р1- и' (, О.Ь. Тод1 для (М. Р1, сГ) формула Р не буде базисною, оск1льки пункт б) для С" не Суде виконаний, а сама вираз

- аГ > а" нев1рний.

Зазначимо, що зг1дно э б) сГ > <х. Таким чином, базис для (М, Р1, а" > а) не м1стить формулу Р, яка була базисном для б!льш суворого критер1п а < сГ. 3 послаблениям критер1ю Формула Р стала " несуттевгяо " Ппотевою, хоча факт послабления критер1» н!як не повинен вести до втрати гШотеэ, пк1 Сули "суттевими" при б1лыл суворому критерП. Вазио повинен м1с-тити " вс1 суттеп1" г!потёзи незалежно в1д завдання значения критер1ю. Критер1й повинен зд1йснювати лише функЩю граничного дов!рчого р!вня за оценкою гШотез. Таким чином, базис у вианаченн! США-методу не в1дпов1даз основному принципу 1н-дукцП в частин! " все ". МодифИсуемо М0![яття базису.

аштчегаш критячяо! блпясно! формул«. Для даних (М,Р1,а) формула Р е критична баэисна формула, над

ПбЬ(Р1,Р) - сг* (. а,

Р1зЬ(Р1.0) > «*. да Ц - будь-яка непуста п1дФормула формули Р , а* - критшшпй р1вень (формули Р1~аР. Зрозум1ло, що критична баэисна формула е базисною у визпаченн! ШНА-методу, ягацо зам!сть а взяти и а-.

Внзначонпя крьтггчного базпсу. Для даних (М, Р1, а) мно-яина критичних базисних формул називаеться критичним базисом та позначаеться (Р1> .

Таордакмшя I. Нехай для (М. Р1, а) формула Р 8 критично» базисном формулою. Тод1 Р - критична Оаэксна формула для (М, Р1, сГ) , де сГ налезть 1итервалу [а, О.б].

йюдая.

а) Р1зЬ(Р1,Р) - а* < аС, оск1яьки «л < .-4 , а <

б) Г1зЬ(Р1.4) > ( за »»значениям С1 - п!д|»рмуда Р ).

Твердкеиня покаауб.у^ критичний базис аадовольияв ооио»•

:юму принципу 1ндукцП а частин! " псе Для новиоЧ ыдш>-з 1 дностI принципу " не1стиняе " знания ( Мишина доноангпнн ) ошшочазтьел з р!шешш. Д1йено, баэис, вгШго з теорН^ олНА •

- б -

методу, Бизначае всю множину р!шень. Тагам чином, 1нтерпрета-ц1я рliaeiüiíi обов'яаковэ починаеться в 1нтерпретац11 базису,та лице noriw оалучазлъси знания з мнсжини доповнення. Постанов-13 ¡задач! абдуктивного вкводу дозволяеть обиежитись знаниями критичного базису.

Таким чаном, р!шення у вигляд1 критичного базису в!дпо-bi.nas осковакм вимогам задач! адобуття елань -"все суттеве".

Вианачення критичного базису в пор!ваяин! в 6UHA-методой тигчагае бХльше часу на його побудозу. Проблема часово! спти-Mlaauíl ста<5 суттевою. Наступи! твердження дозвсшшть шр1-тт ruó проблему.

Твбрддошю upo josßaicTe cjwynnici'i формул. Hexañ М - модель, а - значения критерш, PI и Р - формули. ЯЙЦО ДЛЯ фОрмуЛИ Pl-üP В МОД&Л1 М ВИКОНЭНО

q(r«in(r,k), г, к, ш) > а , тод! для будь-яко! формули Q, ü;o iíiCí'üTb формулу Р , формула PWQ хибна в модел1 Ы . Оияяшзм е •( к >'г , q(r. г, г, и) < л>.

йункц1я q(min(r,k), г, k, «О при к > г монотонно ¡¡poetes по к, а при к С г - монотонно 8ншсуеться го к. .úíouobok э леми:

(run q(min(r»k), г, к, ш) - q(r, г, г, го).

к

Дагчэдоиня Ееер/гешш. Нехай формула PImxP харакгери-öyeneÄ ü мод ел 1 Ы числами г, к . При створенн! в1дкрити,ч формул вигляду Q число г не зм1нюеться, а число к може лиае Бменаитиоя. ЗПдно з умовами, q(ffl!n(r,k),r,k,m) > а. Це означав, то Fish (PI, Р) > tí, тобто формула РЬоР хибка в иодел1 М. Пехай к < г , тодi при створенн! формул вигляду Q значения qOüínír.k), г, к, го) для формуя Pl~«Q, згЗдно а лемоо,Суде зростати, тобто ьс! формули вигляду PI-«Q хибн1 в модел1 Ы. Нехай к > г , »од! при cißopeHHl формул вигляду Q еначення q(min(r,k). г, к, т) дли формул PbaQ, зг1дко з л смою, буде еменшуватися. Зг!дио в висновтом леми цо значения на ноже бути мешаш, nix значения q(r, г, г, т), тобто, яыдр q(r, г, г, m) > а , вс! формули у вигляд1 Pl~aQ хибн1 в моде-л! U. Якщо q(r, г, г. т) < «, híakjw висновк!в не робигьс«, ■roö'fo умова ( к > г . q(г, г. г, т) < « } е вишооченням. Твердлення доведено.

Твердеет« про иеобх1дп1 ^гз црягдестх форкул. Для (М, Р1, <*) формула Р е криткчноя базиснса формулой, ятео капуста мносюша

{ о : !Р11 СоЗ - О . |Р| [оЗ - О . ¡о] - 1 аСю 1'л>, дв О - будь-яка непуста п!дформула Р, цо в1др!зняеться в!д Р одним л1тералом.

Яоаедвяка. За визначеюгям, Р е критичкои базисной формулою, я то ПбГЦРХ.О) > «*, де о - будь-яка непуста Шдформула Р, ое* - 1фитичний р!веш> формули Р1-«Р.

Яа^о вилучити п1д Р одни л!терал, еначення Пай ам1 питься тод1 1 т1льки тод1, ¡юли непуста множена

< о : ¡Р|Со] - О , |0|Со) - 1 >, &Со непуста множна

< о : |Р|Го] - Ул. !Щ[о] - 1 У, де 3 е Р без л!тералу.

Значения Пб^ зб1лъ2уетьсз, я то при В'длученн! л1тералу

в!д Р к1льк!сть об'екПв, де г!по?еза Р1-ой} спростозуетьс.ч, аростзе за рахунок об'е:ст1в, де Ппотеза Р1~«Р Шдтвердкугть-ся. Така множила е т1дькк

{ о : |Р11Со] - О . ¡Р|СоЗ - О , 101 Го] - 1 або Ш >. Тьердтекия доведено.

Обчислювальиа складнЮть внх!дного еиНА-методу в пол!ко-м1альною.

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

Процедура дойуктгганого вгао;пу

Нехай для сатирично! модел! Я задана формула Р1 - &1.1,яка не виконуеться на ¡годному об'ект! XI ( Р1 описуе ун1кальну ситуац!ю ), та задано р!ве;гь а. Для отркмзккл знань про уи1-кальну ситуац1ю вона розбиваегься на фрагмент«. про як! ио~ жливо здобути внання за допомогс'Ю проаедури 1ндуктиьяого виводу.В даному випадку окремий Фрагмент описуеться одним л1те-ралсм з Р1, оск!льки окремий л!?ерал виконуеться на б!лья1й к!лькост1 об'ект!в мож-'л М, н!д коя'юикц1л з двох та б1льше л!терал!в, 1 за тагссм фрагментом мояна рдсбути найб1льэ пов.ч1 знания. Тагам чином, на вх!д iвдyк,?;¡Eнo,¡ процедури податься М, Ь, р!вень а га вкзначаеться крктичний базис . ДаИ формуеться наб1р знань про вс1 фрагмента ун!калъно1 снтуацП. 0ск1льки Р1 б кон'юнкЩя л1терал1в. для отримання внань про

Р1 )ютр5бно виконати операц!ю кон'юнкцП вс1х й.Г/. Ця опера-Шя зд1йсггоеться за допомогом процедури дедуктивного виводу.

Дедуктивний вив1д дае Мишину формул, отриманих ваас-л!док незаперечного перехрестя вс!к критнчних базис!в {Ц}.

Процедура абдуктевтаго шкоду Нехай предметна область представлена навчаючою виб1ркою та задано наб!р значень деяких параметрШ предметно! область Необх!дно вивестн наб!р значень рештк параметра. Формально процедура абдуктивного виводу описуе.ться таким чином. Для дало! мод ел 1 М та в!дкрито1 ЕИД1лено1 формули Р1 (л!терали сформован! з п1дмножиш1 ззданкх пзрачетр!в) потр!бпо вивести Р2 (л!терали сформован! з п!дмнс«ини П£раметр!в, як! необх!д-ло визначитя ).

Опишсмо процедуру виводу рй по заданих Р! , Ы , а. Для дано"! емШрпчно! модел! М , формули Р1 - (! проб1гея не-пусту множину I) та р!вня « процедура абдуктивного виводу ви-конуе 1ндукц!ший крок. Для кожного л!тералу будуеться кри-тичнлй базис <1.4} ( 1.1~а(Ц>), який костить знания про визна-чаюч1 параметра;

дедукцХйний крок. Застосовусться дедуктивно правило виводу: якщо Ц^оКЬ^ , то &{Ц). Формальне правило абдуктив-иого виьоду

¡ияпши словами, якщо задана формула Р1 - ац та для кожного л1тералу энайдеио критичний базис на р1вн! й, 70

формула Р2 наложить МЦК

Доотои1рп1ст{. процедур» абдуктш¡¡«го шгводу Процедура абдуктивного виводу будуе ишхину Кожна

формула з &{Ц> е непуста кои'юшаЦя формул, кокна з яких налегать Т!ЛЬКИ одн1й мнсотш! и.1>. оц!нивеи шов1рн!сть виводу кэ>;;;:о'{ формули в £СЬ1 >, метла обмежитн шоаину формул, що ви-

еодятьсй.

Для оц!нки ймов1рност1 абдуктивного виводу звернемося ва результатах« з математично] статистики в частин1 визначокня критер1ю одночасного виконання сукупност! г1потез. Пехай для лер ч<1рго» к Пиотез в к критерПв.Иехай в!дпов1дн! статистики стохястичио пезалежн! .ПотрЮно визначиго критер!й одночасного

викокания вс1х к rlmrrea. Один э п!дход1ь дооб'еднапня не-в ал ежи их критерИв аасновуеться на тому факт!, шр ящо 1-й !фитер1й мае розм1р «i, то ймов1рн!сть Е1дхмлення хоча б одн1е! s г1потез за умови, то вс1 вони правдив1. дор!вгеос к

1 - П (1 - ai). (1)

1-1

Ее сп1вв!дноаення залиааеться наблкжеко правдивлм тачол для залежних критерШ. Щодо абдуктивного виводу ц! результати ма-ють так© значения: нехай Lj-rtiQi- фсрмули, 1стинн! в код ел 1 М, де «s е критичшш р!венъ, тод! формула &Qi оцгюоеться по сп1в-вШюшешпо (1). Для впорядкування формул, як! виводяться по значению ощнки, достатнъо впсрядкувати ^ормули критичного базису по значении критичного р!вкя.

Достов!рн!сть процедура абду.ктивног о с и воя у оЩкюеться таким чином. Нехай для дано! емп1ричноК табл:щ1 (модель М) виэначено иаб1р заданих (формула Pl) та ,наб1р вкзначаючих (формула Р2) пара,«гтр1в, тобто визначеко клее задач корксту-вача. Шдставо» до прийняття результат! в /роботн сбдуктивно1 процедури служить ступ!нь з'ясування кожного спостереяеяня гих!дно! еми1рично1 таблиц!. В назому випадку процедур! виво-ду пропонуються вс! спостерекеяня (а свае частика, яка в1дпо-Bisee Pl) та вих!диа емп1рична таблица (модель М) без даяоео спостережоння.Користувач зздае обмежеяня на к!льк1сть формул, як! виводяться. Результат роОоти процедури вкводу пор!внтеть-ся з усуиутим спостереженням (а частияою, яка п1дпов1дав Р2) та Шдрачовуеться число в!рно виведених параметр!в. У п ^сумках визначаеться досугов !рн!сть виводу.

V çpwriH txxdI гзгеортsqiï описуеться система LOGIS. Отриман! результати були використан1 при створен«! программ»! система LOGÎS. Абрев1атура L0GÎS утворена s LGQ1C та STATISTIC. 0ск1льки предметна область представляешься даниш, система створена в середовад! oaaieï s СУЕЛ. а сама СУБД F0XFR0 для IBM PC. Вс! процедури, як! реал1зують 1ндуктивний, дедуктивний, абдуктивний вквояи. були nepeimcaai ыоъио прикладного програмування FOXPRO. LCG'S р&ал!зована у вигвдЦ систем меню та дсволяс користувачу 1н!ц1ал1зувати предметну облаем, редагувати и1формац!в про предметиу область, вкр!-шуватн в!дпов1дн! задач! та отркмувати ав!ти.

Риси систем» LOGIS :

1. Дннам1чне вилучешш знань. Рсач1зац1я швидко! проце-дури i иду истинного виводу дозволяв добувати знания динам!чно и1д потреби конкретно! задач! 1 вилучаг проблему створення 1 ведения Саз и знань.

2. Ефективна а1стуал1аа«1я внань. Знания добувкоться без-посередньо э даних. Лог1чиа кш1я даних, на як1й працое процедура Индуктивного виводу, визначаеться самими даними i значениями шкал та формуеться азтомзгнчно кожного разу при вибо-pl предметно! облает!. Таким чином, аг.туал1зац!я даних та рлсап автоматично веде до актуал1эанП знань.

3. Автоматично настроювання на розв'язування класу задач.

4. Незалелш1сть в!д експерт1в. Баэи Даних розповсюджен1 в багатьох галузях людсько! д!яльност1. Шсля введения даних 1.0015 автоматично налагоджуеться нё роэь'яеування класу задач та виконуе певн1, обгрунтован1 внводи, тобто мае добрий по-кааник в1дноиення варт1сть/ефективн1сть.

Постановка та розв'кзаивя практичшос задач Класи$1пац1я опузц1й

ОагтаноЕка з@яач1, Предметна область представлена таблицею емп1ричних даних ( модель M ). Мпожша параметр!в, як! аадан! ( формула Р2 ). BMliçye вс! параметри, крш видзленого ( формула Р1 ). Треба визначити значения вид!леного параметру (в1д 1 до к).

Розв'язашга задач!. Спочатку Бизначаеться, належить задана ситуаЩя первому класу чи Hi.

Пехай для даних M 1 Р2 в1домо значения Pl. Задамо на вх!д 1пдуктивно! процедури значения < М, (1)Р2, 0.5 > та < М, ("1)Р2, 0.5 >. Отримаемо два критичних базиси <(1)Р2> та {("l)Pg}. Кожник базис е naGip формул, копна формула мае св!й критер1й. Розм1стимо критерП вс1х формул обох базис1в в порядку еросташш в1д eti до «ед. Ви01р aj (i-i,N) визначае <(1)Р2} та <("1)Р2>, тобто визначае результат пор1вкяння оц1-нок {(1)Р2) та {(~1)Р2>. 0ск1льки значения Р1 в1дома, кокне оначення «j (1-1,mj визначаз д1йсний або хибний результат 1шасиф1кацП, ОО'еднання сус1дн1х значень надаз систему 1нтервал1в значень а. Кожен 1нтервал зачинений зл1ва i в1дчи-нений справа. Bitôip будь-якого a a одного iнтерааду дае одна-ковий результат класиф1кацП (д!йсний або хибний). Д1хотом1ч-

ний г.1дх!д надав однакову ц!нн!сть 1нтервалам д]йсцого та хибного результатов. Якщо знати, що а належить Ытервалу хиб-но'1 класиф!кацП, тод1 отрицаний результат треба зм!шии на протиледний. Оятачальне значения и для класиф!кац!1 "перший -не перииД " вианачаеться настугшим чином, усунеыо 1з емн1рич-¡ю'! таСлиц1 перщий рядок та ад1йснимо класиф1кац!ю цього рядка. Отримаемо систему 1нтервал1в однакових результат!в класи-ф!кацП Таким чином, отримаемо системи 1нтервал!в для ьо!х рядк1в таблиц!. Якщо вибрати будь-яке аначенкя «.манта д!зна-тнся, ск1лькн рядк!в таблиц! класиф!кова«1 в1рно, а ск!яыш нев1ряо. Якщо перебрати вс! значения л1вих мед 1нтерьалI в. то знайдемо значения да надае максимальну достоа!рн!сть кла-скф1кац11 " перший - не перший ". Дад1 ;зд1йснюсться 1слаоиф1-кац1я " другий - не другий " ..." к не к".

Пр13(язд практичного яастосувлннл. Процедура вшсораста-на в задач! прогнозувашга вторишю! структури б!лк1в. Б:1лок е посл!довн!сть будь-якой довяини, що стмадаеться з 20 л!гер (ач!кскисдотн! валишки). Визначити вторннну структуру бш-са -це означав кдасифпсувати кожний ам!нокислотний ьаяишои в за-лежност1 в!д сус1дн!х ам!нокислотиих эалипк1в. е багато мето-д!в для роэв'язання ц1е! задач!. Пайкраща достов!рн!сть -70.4.%. Застосування залропонованоК процедури надало достов!р-Н1сть 70.8%.

йзязчл абдукх?шного виводу Постановка задач!. Предметна область представлена таблицею емн1ричних даних ( Модель М ). Множила задания параметр!б (формула Р1) та множила визначаючих параметр!в (формула Р2) авляють собою клас задач виводу Р2 по Р1.

Приклад практичного зазгосуизння. На основ! аанрононова-но'1 процедури створено АРМ селекц!онера озимо! пшениц!. !!ав-чаюча виб!рка - результат схрещування материнсько! та бать-к!всько! форм озимо! пшениц! отримано в Мирон!вському 1 петиту т! пшениц!. В рамках АРМ вир!шуються так1 задач!:

за заданный значениями материнсько! ! батьк1всько'1 форм вивести значения г!бриду;

за заданный значениями г1бриду 1 одн1е! 8 Сатьк1воьких форм вивести значения друго! батьк1всько1 форми;

за заданиями значениями г1брзду вивести значении гшч. к!вських форм.

- 12 -

Економ1чна ефективн1сть застосувашш АРМ ирдо виведення одного сорту озимо! пшениц! становись 171 тис. долар!в. Ра-хунки виконан1 фах!вцями 1нституту захисту рослин.

Задача влводу »кжращшшх пкостей

Посхакозка задач!. Нехай е N спостережень М параметр!в предметно! облает1 та вид1лен1 ц!льови параметри. Треба виз-начити умови досягнення сигуац!! з комплексом пол1пшених значень ц1лъових параиетр1в.

Риав'язатая зздзч!. Для цього необх1дно знайти причини вм1ия значень ц1льових параметр!в в залежност! в!д зм1н значень !ншкх параметр!в. Перетворшо таблиц» спостережень в таблиц» з в!дпов!дною семантикою.

Рогглянемо результат пор!вкяння будь-яккх двох спостере-жень предметно! облает1 (1-го та 3-го ). Домовимося, що спо-стерелення в меншим номером мае семантику "було", а спостере-ження э б1льшим номером мае семантику "стало". Тод! результат пор1ьняння е спостереження 8 семантикою " було -> стало ". Бор1вншчи койше спостереження з ус!ма наступними номером спостерекеннями, отримуемо повну таблиц» пор!внял;, чх спосге-режель предметно! област1. Таблицл мае зм1ст:" Эм1т нец1лъо-вих параметр!в вйзивають 8м1ни ц!льових параметр!в". Якщо параметр к1льк1сно! прчродк, результат пор1вняння е результатом в!дн1ма1шя в1д значения "стало" значения "було". Параметр жкалюеться з вид!ленням шкал категорП "аменшшюсь" та категорП "зб! ль шилось". Якщо параметр як1сний, результат пор1в-нйшя кодуеться "к1-к2", де к1 1 к2 - номери икал параметра в даному пор1вняпн!. Параметр шкалюеться з вид!ленням категор1й або по частил! "було", або по частин! "стало", або "було-стало". Дал! ро8В*язуегься задача абдуктивного виводу. Користу-вач задав вх!дну ситуаШю.зазначаючи шкали зм!ни Щльових параметр^, Т1Ш самим визначае задачу "Як1 зм!нн нец!льовк; параметра треба утворитн, щеб отримати аавдання зм!нн Щльових парашгр!в ?". Процедура виводить обмежену к!лы'.1сть альтернатив 8м1нй неШльовик нараметр!в. Користувач зазначаз епостерехеннв, до якого потр1био эастосувати виведен! зм!гш. Обчислюються абсолатн! значена»! нец1льоаих параметр!з, як! повишИ привнести до комплексного покращешш ци&овкх пара-мэтр! в.

- 15 -

Привад щкагекчпсго агиссувакия. Ця процедура Суда ви-торнстана для виэначеиня складу герб!циду о високои сфегстив-н5стю. Для трьох компокент!в герб!цвду ( метафос, децис, Фос-Фам!д) була иадана таблиця експеримент1в. Налагодяшшя процедури проведено а достов1рн!стю 83Х. Отркмано 9 альтернатив, як i напали 6 формул сумЗш1. Польов! випробувалия дали прогно-зовану ефективп1сть для двох формул.

Прогноз розшгп^у д;л:зм1ч1!оК сютгеют

Постановка задач!. Кехай е Н спостереженъ М Паракетр1в предметно! област1, зроблених з однаковим 1нтервалом часу. Треба спрогнозувати М+1 спостереження.

Розз'гзаэтпя задач!. Перетворюемо вих!дну таблица спосте-режепь в таблица темп1в, тобто в!л кожного 1 рядка в1дн!мемо i-i рядок (i - l.N). Кожиий (ij) елемент таблиц! темп!в мае семантмсу: " Зм!нення вначення d-ro параметра при переход! системи в1д (i-l)-ro спостереження до 1-го спостередення".Таблица темп1в мае !Ы рядк1в. Усунеыо в!д ц!е! таблиц! перший рядок. Отркмаемо таблиц» в N-2 рядк!в. Призднаемо до вих!дно! таблиц! текп!в в N-1 рядк1в таблкию темп!в в R-2 рядк!в. Кот-ний i-mi рядок подв1йно'1 таблиц! темп1в мае семантику " &¡S -> üi+iS", де AjS - шЛнення значень параметр!в системи при переход! в!д (i-í)-ro спостережегат до 1-го спостереження (&i+iS -апалог!чно ). Остаин!й рядок подвШо! таблиц! теми!в м!сткть половину елемент!в, як! створюють вх!д до процедур» абдукткв-ного виводу разом э подв!йною таблицею темп1в. Отркмаемо темп» гм!нения значень параметр!з системи при переход1 системи в!д К-го спостереження до (N+i)-ro спостереження.

Крзсиад практичного згстосузлшот. В 1906 р. за вамовлен-ням УправлПшя !нформацП Ради Министр1в СРСР була розробдена та впроваджена Д!алогова система прогкоаувааиа развитку дина-xíiuHKx систем.

U глепозку джертгаП наведен! Щдсумкя роботи.

Созови i £хгз*/г5тз.тн [хгСстя.

::злропо;газако та теоретично сбгруптозано поияття '"критич-;-:кй базис" для отримаиня найб!лыа важяивих Ппотва.

Доведен! твердження ¡подо ефективно! кобудови форкул в гфитичного базису.

Т юретично обгрунтована процедура гбдуктквкого пиволу. стриман! статксткчн! оц!ики результат!з аЗдугагивкого виводу.

- 14 -

Розроблена процедура виявлення оптимального значения параметра абдуктивного виводу, яке надае максимальну достов!р-н!сть виводу.

Сформульовано клас задач користувача, створена програмна система LOGIS для розв'язування такого роду задач.

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

Основ»! положения дисертацП олубяЬшван! е тагак працяи:

1. Братусь А.В. Преобразование эмпирической информации в систему логических высказываний// Докл.. АН УССР, Сер. А.-1987.-N5.-C.72 - 74.

2. Братусь А.В. Об одной модели пакетов прикладных программ сложной структуры// Машинные методы обработки информации для задач управления.-Киев:Ин-т кибернетики им.В.М.Глущ-коза АН УССР. 1986.-С.17 - 21.

3. Братусь А.В. Имитационное моделирование систем на основе логических выводов// Докл. АН УССР. Сер. А.-1987.-N10.-С.62 - 64.

4. Сергиенко И.В., Гупал A.M., Братусь А,В. LOGIS-систе-ма, реализующая статистический абдуктивный вывод на эмпирических данных// Кибернетика.-1995.-N 3.-С.160 - 173.

5. Вагис А.Г.. Братусь А.В.. Василенко В.И. Реализация экспертной система на основе логической имитации.-Киев, 1987.-22с.-(Препр./АН УССР. Ин-т кибернетики им. В.М.Глушкова,57).

6. Вагис А.Г., Братусь А.В., Василенко В.И. Экспертная система на основе образцов и логической имитации// Тез. докл. XII семинара "Прикладная информатика автоматизированных систем проектирования, управления, программированной эксплуатации".-Калининград, 1987.-С.123.

7. Lesovol М., Smelyanets V., Aifaoui A., Vasilenko V, Bratus A. Logical simulation of processes at forming of winter wheat geraplasfli with complex resistance to insect pests and pathogens (P.l)// Arch. Phytopath. Pflanz.- 1994.-29.-P.153 - 164.

8. Lesovol M., Smelyanets V., Aifaoui A., Vasilenko V, Bratus A. Logical simulation of processes at forming of

winter wheat germplasm with complex resistance to Insect pests and pathogens (P.2)// Ibid.-P.263 - 283.

9. Chaschln N. A., Malchenko S.Z., Br at us A. V. Anew method for the prediction of secondary protein structures with using of selfstudying expert system// Blolnformatics in the 90's Final programme and abstracts, November 20-22,1991.~ Maastricht (Netherlands),1S91. - P.13.

10. Chaschln N.A., Malchenko S.Z., Bratus A.V. The Design of Model Proteins with the predefined structure. Protein engineering and beyond// Miami Short Reports.-1993.-3.-P.10.

Внесск автора дисертацШго! роботи в сп1льних публ$кац1ях:

4 - обгрунтовано понятгя "критичшш базкс", розроблена процедура 1ндуктивного виводу, отриман1 статистичн1 оц1нки абдуктивного виводу;

5.6 - доведен1 твердження щодо ефективно! побудови критичного базису;

7,8,9,10 - программа обробка та 1нтерпретац1я дапих. на-даних замовником.

Вратусь А.В. Система индуктивного вывода на основе модифицированного GUHA-метода. Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.03 - математическое и программное обеспечение вычислительных машин и систем. Институт кибернетики им. В.М. Глушкова НАН Украины, Киев, 1996.

Предлагается процедура логического вывода, состоящая из процедур индуктивного и дедуктивного вывода. Приводятся статистические оценки результатов вывода. Описываются примеры практического применения процедуры.

The logical inference procedure, composed from inductive and deductive Inference procedures Is suggested. Probability evaluation of inference result Is given. Practical examples are considered.

Югочов Гслова:

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

Л1ди. до друку C2.IC.X. Соркаг £0x8-1/16 lanlp т'сч. 's I. о;«, друк. Ум. друк. прк. 0,33. Ум. 'Тпрбо-вГдб. 1,05.

О^л.-вид. ярк. 1,0. Сам. 4С~). Trpnx ICQ аргм. _

РедокцТйно-аидавничи,! о1дд!л з гюлХгряфхЧНОю д1льницою 1нст1'гугу ¡Цборпетгкг Ii-whI 3 М.Глушкопа ПАН Укра1ни 25CÜJ2 Kala 2J, проспект Ака.дсм1ка Тлужонн, 40