Файл: системи штучного інтелекту.doc

Рис. 8.2. Типова схема роботи продукційної системи

До робочої пам'яті заносяться факти, що задаються користувачем, а також його запити. Логічний блок зіставляє цю інформацію з правилами, що зберігаються в базі знань, і застосовує ті правила, які можуть бути зіставлені із вмістом робочої пам'яті. Наприклад, якщо в базі знань є продукції л^впв^с, _{т0 вони можугь} бути виконані, коли користувач ввів дані про Істинність фактуА

4 Пряме та зворотне виведення

Існують дві основні стратегії логічного виведення в продукційних системах:

• пряме;

• зворотне.

Пряме виведення на основі наявних правил передбачає аналіз: 1) усІх наслідків з фактів, 2) наслідків з наслідків і т. д. Процес продовжується, поки не буде встановлено істинність або хибнкггь запиту користувача.

Наприклад, нехай є продукції* *»^в ™ ⁸ ** ^с; користувач оголо

сив про Істинність факту A I спитав про Істинність C. Ланцюжок прямо го виведення матиме вигляд: з А виводиться В, з В виводиться C, отже, С—Істинне.

Пряме виведення не вважається ефективним через те, що може перебратися чимало безперспективних продукцій, І, відповідно, породжується дуже багато зайвих проміжних результатів. Експертні системи на основи прямого виведення використовуються, як правило, при плануванні і прогнозуванні.

При зворотному виведенні логічний блок починає роботу із запиту користувача, тобто з твердження, яке перевіряється. Розглядається одне з правил, на основі яких можна вивести це твердження, після чого перевіряється істинність лівої частини цього правила. Процес повторюється, доки не дійде до фактів, які вважаються істинними.

У нашому прикладі ланцюжок зворотного виведення матиме вигляд: "C виводиться з В, В виводиться з А, А Істинне, отже, і C істинне".

Як і у випадку прямого виведення, зворотне виведення може вимагати повторень у разі невдалої спроби, і тому є стратегією перебору

.Системи штучмио інтелекту Cypo*e|n

Зворотне виведення тІсно пов'язано з резолюцією, зокрема лінійною, | прологівським механізмом виконання програм.

.5. Типові дисципліни виконання продукцІй

Передусім ядра продукцІй прийнято поділяти на детерміновані ₍ небетермІнованІ. У детермінованих продукціях при виконанні лівої частини заожди виконується і права. У недетермінованих продунцІях права частина при виконанні лів₀і виконується необов'язково. Можливі, наприклад, такі інтерпретації недетермІнойаних продукцІй: "Якщо А то можливе 8“; або "Якщо А то В з певною вірогідністю".

Існують різні режими керування виконанням готових продукцІй, тобто продукдо ліві частини яких справедливі, I, вІдповЩно, ці продукції можуть бути виконані негайно

Можна виокремити такІ режими:

• режим негайного виконання;

• режим формування конфліктного набору.

У режимі негайного виконання, якщо знайдена перша-лІпша продукція, саме вон виконується невідкладно.

У режимі формування конфліктного набору знайдені готові продукції _Не виконуються відразу, а включаються до конфліктного набору — списку продукЩй готових до виконання. Лише після завершення формування конфліктного набору відбувається вирішення конфлікту, тобто вибір зі списку готових продукцІй ЯКОЇСЬ OflHfej Інша назва конфліктного набору "фронтготовихпродукцІй ".

Розглянемо деякі проблеми, пов'язані з конфліктними наборами.

Нехай маємо продукції:

1)4=ȣ

» 2)A=*C,

І А істинне.

ТодІ обидві продукції готові до виконання і утворюють конфліктний набір.

Якщо ядра продукцІй Інтерпретуються як Імплікації, проблема є менш гострою, Продукційна система є чистодекларативною. Після застосування 1),тобто виеедення5,д залишається Істинним, I ми завжди можемо використати продукцію 2). Таким чином порядок застосування продукцІйних правил може впливати лише на час роботи системи але не на істинність висновків.

Зовсім інша ситуація виникає, якщо ядра продукцІй інтерпретуються як "виконати таку-то дію". Тоді після виконання 1) ситуація може змінитися: А може перестати буги істинним, і тоді продукція 2) може стати недосяжною. Тому, якщо насправдІтреба було вибирати C, вибір встає помилкою, яку не завжди можна виправити.

Існують різні стратегії вирішення конфліктів, а також обмеження при включенні готових продукцій до конфліктного набору.

Розрізняють також централізоване I децентралізоване керування про-дукціями,

За централізованого керування продукційна система має центр керування, який вирішує, коли має спрацювати та чи інша продукція.

За децентралізованого керування кожна продукція може самостійно прийняти рішення про свій запуск. Один з типових механізмів, який застосовується при цьому, e механізм "класноїдошки". Таку назву має спеціальна область памяті, доступна для

74

( WMMH M іуЧИОМ? OTMM' ТЧ. C>*M* )tH різних продукцій. На ній продукції, що працюють парвлельно, знаходять іітформацяо. ще може Ініціювати fX запуск. Туди ж вони пишуть інформацію, що мож* вияеитжь корисною для інших продукціЙ,

Зрозуміло, що "класних дошок" може бути кілька; можуть бути введені леемі Ієрархії "класних дошок" I т. n. Огляд різних архітектур "класних дошок" можна зиаДти в (305).

%. Основні стратегії вирішення конфліктів у продукіцйиих системах

Очевидно, що найзагальнішим способом керування системою продукцій c комплексне планування її роботи, тобто прийняття рішень на основі аналізу scix Можливих дій та їх наслідків з погляду мети, що стоїть перед системою. Але зрозуміло, що вказаний принцип рІдко може бути застосований у повному обсязі, насамперед через експоненційне зростання можливих варіантів розвитку подій.

Існують стратегІЇ керування вирішенням конфліктів, мета яких — намагатися уникнути експоненційного вибуху. Подібні стратегії здебільшого можуть бути охарактеризовані як евристичні. В [129] описані деякі стратегії керування виконанням продукцій.

Принцип "стосу книг". Ґрунтується на Ідеї, що найкориснішою • та продукція, яка використовується найчастіше (так само, як у стосІ книг ті, якІ найчастіше користуються попитом, як правило, опиняються зверху). Відповідно, з фронту готових продукцій вибирається продукція з максимальною частотою використання. У (129) відмічено, що керування за принципом "стосу книг” доцільно застосовувати, якщо продукції відносно незалежні одна від одної, наприклад, коли кожна з них являє собою правило "ситуація А *> ДІя В".

Принцип найдовшої умови. 3 фронту готових продукцій вибирається та, для якої стала справедливою наЙдовша умова виконання. ІдеологКжою основою цього принципу є таке міркування, що часткові правила, застосовані до вузького класу ситуацій, є важливішими, ніж загальні правила для широкого класу ситуацій. Наприклад нехай єдві продукцІЇ:

1. Якщо А — nmax, mo А лІтае.

2. Якщо А — птах і А — пІнгвІн, то А нелІтае.

Якщо відомо, що А — пІнгвІн, то за принципом найдовшої умови слід вибирати (2),

У [129] відмічається, що принцип найдовшої умови доцільно застосувати, якщо продукції прив'язані до типових ситуацій, зв'язаних відношенням "часткове — загальне". До цього можна додати, що цей принцип заслуговує на особливу увагу при аналізі винятків. Так, у нашому прикладі правило (2) є винятком з правила (1); якби ми були впевнені, що (1) не має винятків, ми могли б застосувати це загальне правило у будь-якій ситуації. Легко бачити очевидні аналогії принципу найдовшої умови з принципом блокування наслідування, описаним у п. 5.6.

Принцип метапродукцІй. Ґрунтується на введенні до системи знань метапродукцій, тобто правил використання продукцій. Типовими мета-продукціями можуть бути правила, які визначають, що слІд робити, якщо до фронту готових продукцій ввійшли або не ввійшли ті чи інші конкретні продукції

.Системи штучного інтелекту: Cypo*aHi Принцип "класноїдошки". Конфлікти вирішуються на основі обміну Інформаціє^ використанням "класної дошки". Застосування "класної дошки" часто комбінується ₃ застосуванням метапродукцІй.

Принцип вибору за пріоритетом. Кожній продукції надається пріоритет, щ₀ вЩображаєїїважливІсть. ЦІ пріоритети можуть бути різними для кожного типу ситуац^ а також статичними і динамічними. Динамічні пріоритети змінюються з часом I можуте відображати, наприклад, ефективність використання продукцій у минулому або _Ча_с перебування продукції у фронті готових продукцій. Аналіз часу знаходження продукцц фронті готових продукцій цікавий тим, що на його основі можна дІйти дІаметральц₀ протилежних висновків. 3 одного боку, система керування продукці-ями може з часом підвищувати динамічний пріоритет, щоб будь^жа продукція колись була обов'язком виконана. 3 Іншого боку, система керування може дійти висновку, що, якщо продущ_я досі не виконувалась, то вона взагалі не потрібна, і, відповідно, не підвищити ft пріоритет, а, навпаки, знизити.

Керування за іменами. Базується на заданні для імен продукцій формальної граматики або іншої процедури, що забезпечує звуження фронту готових продукцщ ₍ вибір з нього чергової продукції для виконання.

ТЕМА; ЛОГІЧНЕ ВИВЕДЕННЯ ЗА НЕДОСТОВІРНИХ ЗНАНЬ

1. Поняття про неточнелоНчне виведення

Проблема недостовірних знань була в загальних рисах охарактеризована в роздд Часто буває так, що експерт не зовсім упевнений в тому чи іншому факті, але незважаючи на це, Інформація залишається цінною I повинна бути включена до бази знань.

Згідно з [129], висловлення називається неточним, якщо його істинність або хибність не можуть бути встановлені однозначно, тобто твердження не є ні абсолютно достовірним, ні абсолютно хибним.

Неточним виведенням називається логічне виведення в умовах неточності (недостовірностІ) знань.

Неточне виведення традиційно розглядається як самостійний напрям, хоча неточне твердження можна було б інтерпретувати як частковий випадок модального твердження.

Неточне виведення слід відрізняти від роботи з нечіткими знаннями, хоча останні також формально підпадають під сформульоване вище визначення.

.2. Деякі визначення з теорії ймовірностей

Багато методик недостовірного логічного виведення тісно пов'язано з апаратом теорії ймовірностей. Тому для розуміння цього розділу потрібно навести основні необхідні факти з теорії ймовірностей. Для ґрунтовнішого ознайомлення з основами теорії ймовірностей читачеві рекомендується звернутися до відомих підручників, наприклад [43, 85,143, 277].

Ймовірність події А (позначається P (A)) слід розум^и як міру достовірності деякої

події. Завжди виконується властивість<> є ? w) s і. при

цьому неможлива подія (подія, яка ніколи не може відбутися) має ймовірність 0, а достовірна подія — ймовірність 1. Дамо формалізованіші визначення.

Розглянемо множину елементарних наслідків & Елементарні наслідки розглядаються як можливі наслідки деякого експерименту, при цьому цІ наслідки вважаються рівноможливими та взаємовиключними. Тоді будь-яка подія А розглядається як пІдмножина множини елементарних наслідків. Подія А відбувається, якщо має місце будь^жий елементарний наслідок, що входить до множини А. Якщо елементарний наслідок входить до множини А, кажуть, що вІн є сприятливим для події А.

Ймовірність подїї А визначається як відношення кількості сприятливих наслідків до загальноїкІлькостІ елементарних наслідків.

На основі даного визначення в ряді випадків можна безпосередньо розрахувати ймовірності. Наведемо кілька прикладів.

Приклад 10.1. Підкидається гральний кубик, на кожній гранІ якого міститься певна кількість очок від 1 до 6. Яка ймовірність того, що випаде парна кількість очок?

Оскільки в результаті експерименту може випасти будь^жа кількість очок від 1 до 6, множина елементарних наслідків Q = (1, 2,3,4,5, 6}.

Сприятливими для події А є наслідки 2,4, 6, отже, А = (2,4,6}.

Маємо P (А) = 3/6 = 0.5.

Приклад 10.2. Підкидаються два гральних кубики. Яка ймовірність того, що сума очок, якІ випадуть на обох гранях, дорівнюватиме 5?

Експеримент полягає в підкиданні двох кубиків, і елементарний наслЩок e парою, кожний елемент якої задає кількість очок, що випала на відповідному кубику. Таким чином,

П= (11, 12, 13, 14, 15, 16,21, ...,61,62,63,65,66}; кількість елементарний наслЩків дорівнює 36.

Л = (14,41,23, 32).

Тоді P {A) = 4/36 = 1/9 * 0.11.

Подією, протилежною до події А (позначається А), називається та, яка полягає в тому, що подія А не відбуваєтьа*. Ha основі класичного визначення ймовірностей легко

переконатися ^{г (Я}* “ ¹ ~^{p w} в тому, що

(читачеві рекомендується довести це самостійно).

Ймовірність події, по суті, є частотою появи цІєї події. Це пЩкреслю-ється в такому визначенні.

Частотне визначення ймовірності. Нехай проводиться серія одно-типних експериментів I нехай К_А (гІ) — кількість випадків, в яких відбулася подія А, якщо було

_Р(Л>-ш*№. проведено ~" ⁿ n експериментів. Тоді

Наприклад, якщо проводиться 1000 експериментів, а ймовірність події I дорівнює

3, то подія А настане приблизно в 300 випадках. При цьому й зростанням кількості експериментів частина випадків, в яких відбува-ється дана подія, все більш

енаближається до ймовірності Введемо такI позначення;

P(AvB)-^ ймовірність того, що настане або подія Д або подія В, або /Д I В;' P{AnB)- — ймовірність того, що настануть [ Д / В, Тоді ^Я(^'^{и?) m}*W + >>W-P(Ana). Зокрема, якщоА IВ — несумісні (взаємовиключнІ) події, маємо Дуже важливим є поняття ^p ^ ^u ^ “ ^{P + P} ^ умовної ймовірності УмовноюймовірнІс-11о подіїА за умови В (позначається P (A \B) називається ймовІрнісг_ь появи А за умови, що подія В уже відбулася.

Справедливе співвідношення

r04nB)-P(B)P(Aty

Події A I В називаються незалежними, якщо поява А жодним чином не Залежить від появи В. Інакше кажучи, AIВ незалежні, якщо P(A\B) = P (А).

Кажуть, що подІЇ Н„ ..., Н„ утворюють повну групу подій, якщо вони взаємовиключними I сума їх ймовірностей дорівнює 1 (це означає, що і цих подій настане одна і тільки одна).

Якщо H,,..., Н„ — повна група подій, то для будь^кої події А справедливі співвідношення

rW-t,F(H,>t(M,)

nHM)-^pW^P{AH-y.

%P(ff,)P(AW,)

(формула повної ймоирностГ) ^№| та

Остання формула називається формулою Байєса І має дуже велике значення, оскільки дозволяє обчислювати апостеріорні ймовірності P (НЩ "гіпотез" Я, за умови що гіодІя А відбулася через апріорні ймовірності P (A\H). Більшість методик неточного логічного виведення так чи інакше пов'язані з формулою повної ймовірності та формулою Байєса.При неточному логічному виведенні з кожним твердженням (фактом або правилом виведення) пов'язується число, яке характеризує міру його надійності. Ця характеристика називається коефіцієнтом упевненості, або мірою достовірності. Розрахунок коефіцієнтів упевненості гісно пов'язаний з ймовірнісними методами, хоча ненадійність інформації далеко не завжди носить імовірнісний характер (див. n. 10.3).

Ноефіцієнти упевненості часто визначаються на основі експертних оцінок. Проте в ряді випадків коефіцієнт упевненості можна отримати шляхом статистичних досліджень. Якщо ж здійснюється логічне виведення, то коефіцієнт упевненості нерідко можна підрахувати, якщо вІдомі міри достовірності умови та правила виведення.

Чим надійнішою є Інформація, тим вищІ відповідні коефіцієнти упевненості. Часто використовується шкала, за якої коефіцієнт 1 відповідає достовірно істинній події, 0 - достовірно хибній, а 0.5 — повній невизначеності.

Але згадана шкала не є єдино можливою. Так, експертні системи MYCIN та EMYCIN, що є розвитком MYCIN (ці системи призначені для виявлення мікроорганізмів у крові) використовують шкалу, в якій достовірній істинносгі відповідає значення 1, достовірній хибності - значення — 1, а повній невизначеності — 0.

.3. "Об'єктивна" та "суб'єктивна" невизначеність

78

С'иотемн штучвого інтелекту. CypoeaHM.

Перелічимо деякі з можливих типів невизначеності. "Об’єктивна" невизначеність. Цей тип пов'язаний з принципово випадковим характером процесів, які прогнозуються. Наприклад, передбачається результат перебігу певної хвороби, а статистичний аналіз свідчить, що досі ефективність лікування становила 70 %. У такому разі робиться відповідний висновок: пацієнт буде вилікований з імовірністю 70 %.

Важливо розуміти, що "об’єктивна" невизначеність, як правило, пов'язана з впливом певних невідомих або неконтрольованих факторів і за своєю суттю являє собою ймовірність відповідної події.

Можна виокремити дві основні властивості "об'єктивної" невизна ченостІ:

• подія, для якої визначається коефіцієнт упевненості, ще не відбулася, але обов'язково настане момент, коли вона або відбудеться, або не відбудеться; пІсля цього міра достовірності стане дорівнювати відпо відно 1 або 0;

• якби було можливим провести серію експериментів за однакових

умов, то частина експериментів, в яких под|я відбулася 6, приблизно _м\дорівнювала б а; тут а — міра достовірності (фактично, ймовірність

подП).

"Суб'єктивна" невизначеність. Ми говоримо про цей тип невизначеності у разі, якщо подія, про яку йдеться, або вже відбулася, або не відбулася, і істинна міра достовірності дорівнює відповЩно або 1, або 0. Алі якщо ця істинна міра достовірності експертові невідома (він не знає, чи відбулася под|я, чи ні) або відома нечітко, то він дає власну оцінку міри надійності, і ця власна оцінка неминуче є суб'єктивною. Зрозуміло, що доцільність застосування ймовірнісних методів утакому разі є досить сумнівною.

Варто розрізняти два типи "суб'єктивної" невизначеності.

"Суб'єктивна" невизначеність при авторитетності джерела знонь. Авторитетність джерела знань означає, що експерт є людиною серйозною l відповідальною та його власній оцінці можна довіряти. Тому власна оцінка істинності твердження приймається як робоча і використовується при логічному виведенні. Авторитетними, якправило, є серйозні наукові праці, енциклопедПтощо.

"Суб'єктивна " невизначеність при неавторитетності джерела знань. V даному разі, незважаючи на ступінь упевненості "експерта", його оцінці довіряти не можна. Тут можна розглядати різноманітні випадки, наприклад:

• твердження є об'єктивно істинним, але "експерт" у ньому невпевнений і ступінь його кваліфікації не дозволяє йому адекватно сформулювати міру невпевненості;

• твердження є об'єктивно хибним, але "експерт" вважає його істинним і формулює як достовірне;

" • твердження є об'єктивно хибним, "експерт" усвідомлює його хибність, але повідомляє про істинність твердження з метою ввести в оману.

Часто доводиться мати справу з невизначеністю комбінованого типу, тобто з невизначеністю, що поєднує риси як "об'єктивної", так і "суб'єктивної" невизначеності. Один з найпростіших випадків подібного поєднання полягає в такому. Розглядаєтьс