Представлення стереотипних ситуацій .
Лекція 3.4 .
Моделі подання знань
Моделі подання знань звичайно ділять на логічні й евристичні, відносячи до останніх продукційні, мережні, фреймові. Ґрунтуючись на цих моделях й їхніх певних сполученнях створено й використають багато мов подання знань.
Більшість моделей реальних систем є гібридними. У методичних цілях найвідоміші моделі класифікують в рамках наведеної схеми.
Продукційна система включає: базу правил IF-THEN, які вказують, які виводи мають бути зроблені або не зроблені в різних ситуаціях, глобальну базу даних і інтерпретатор правил.
База правил - область пам'яті, що містить базу знань у формі послідовності правил виду:
і; Q; P ; A ==> B ; N.
Тут і – им'я продукції, за допомогою якого дана продукція виділяється з усієї множини продукцій. Як ім'я може виступати деяка лексема, що відбиває суть даної продукції (наприклад, "покупка книги" або "набір коду замка"), чи порядковий номер продукції у множині, що зберігається в пам'яті системи.
Елемент Q характеризує сферу проблемної області застосування продукції. Поділ знань на окремі сфери дозволяє заощаджувати час на пошук потрібних знань.
Основним елементом продукції є її ядро: A ==> B. Інтерпретація ядра продукції може бути різною й залежить від умови А, що є ліворуч і праворуч від знака секвенції ==>. Звичайно, ядро продукції має смисл: ЯКЩО A, ТО B. Складніші конструкції ядра допускають у правій частині альтернативний вибір, наприклад, ЯКЩО А, ТО B1, ІНАКШЕ B2. Секвенція може тлумачитись у звичайному логічному змісті як знак логічного наслідку В із істинного А (якщо А не є істинним виразом, то про В нічого сказати не можна). Можливі й інші інтерпретації ядра продукції, наприклад A описує деяку умову, необхідну, щоб зробити дію В.
|
|
|
Елемент Р є зовнішня умова застосовності ядра продукції. Звичайно Р є логічним виразом (як правило, предикат). Коли Р приймає значення "істина", ядро продукції активізується. Якщо Р ложно, то ядро продукції не може бути використано. Наприклад, якщо в продукції "НАЯВНІСТЬ ГРОШЕЙ; ЯКЩО ХОЧЕШ КУПИТИ РІЧ X, ТО ЗАПЛАТИ В КАСУ ЇЇ ВАРТІСТЬ І ВІДДАЙ ЧЕК ПРОДАВЦЕВІ" умова застосовності ядра продукції ложна, тобто, грошей нема, то не застосовне ядро продукції.
Елемент N описує постумови продукції, що вказують зміни в базі знань після виконання продукції. Вони актуалізуються лише, якщо реалізувалось ядро продукції. Наприклад, після деякої покупки в магазині необхідно зменшити кількість речей такого типу на одиницю.
Якщо в пам'яті системи зберігається деякий набір продукцій, то вони утворюють систему продукцій. У системі продукцій повинні бути задані спеціальні процедури керування продукціями, за допомогою яких відбувається їхня актуалізація і вибір для виконання тої чи іншої продукції із числа актуалізованих.
|
|
|
Глобальна база даних - область пам'яті, що містить факти (опис початкових, поточних даних і станів системи). Бази даних мають різну форму, але можуть бути описані як масив, що містить ім'я даних, атрибути й значення атрибутів.
Інтерпретатор реалізує вивід заключень, користуючись базою правил і даних. Механізм виводу включає пошук у базі знань, виконання операцій над знаннями й формування виводів; звичайно реалізується певне сполучення прямих (висхідних, керованих даними) і зворотних (спадних чи орієнтованих на ціль) виводів.
У прямих виводах здійснюється рух до цілі з послідовним застосуванням правил до даних: вибирається один з елементів даних, що є в базі даних, і якщо при зіставленні цей елемент узгоджується з посилкою деякого правила, то згідно правилу робиться відповідний висновок, і породжується в базу даних та/або виконується дія (зазначена в правилі) над вмістом бази даних. Такі виводи послідовно породжують нові факти, поки не буде досягнута поставлена ціль.
Зворотними є виводи, при яких процес виводу йде від цілі до початкових даних, поки підціль (гіпотеза) не співпаде із початковими даними: якщо ціль погодиться з висновком правила, то посилка приймається за підціль.
|
|
|
Подання знань правилами й виводи на них легко розуміються, оскільки близькі силогізмам, а одноманітність форми забезпечує легку модифікацію системи продукцій введенням і/або видаленням правил незалежно від змісту інших.
Ці властивості - достоїнство при постановці простих, однорідних за змістом задач (у формі переходів між станами) та спричинюють падіння ефективності рішення проблем у складі кількох різнорідних задач. Навіть для простої проблеми важко побудувати систему керування знаннями як єдиним цілим, тому весь процес керування повинен контролюватись людиною.
Широке застосування систем, заснованих на правилах, обумовлено наступним.
§ Модульна організація. Завдяки цьому спрощується подання знань і розширення системи методом інкрементної розробки.
§ Наявність засобів пояснення. Оскільки антецеденти точно вказують умови активізації правила, за допомогою правил легко створювати засоби пояснення. Засіб пояснення дозволяє стежити за порядком запуску правил, тому дає можливість відновити хід міркувань, які привели до певного виводу.
|
|
|
§ Наявність аналогії з процесом пізнання людини. Відповідно до результатів Ньюелла і Саймона правила є природний спосіб моделювання процесу рішення задач. При розробці бази знань спрощується процес формалізації знань експертів, застосовуючи просте подання правил IF-THEN.
Правила належать до типу продукцій, ідея яких започаткована у роботах 1940-х років.
Продукційні системи Поста
В символьній логіці продукційні системи вперше були використані Е. Постом. Він довів, що будь-яка система математики чи логіки може бути оформлена у вигляді системи продукційних правил певного типу.
Крім того, продукційні правила використаються в лінгвістиці у формі правил підстановки для визначення граматики мови. Комп'ютерні мови звичайно визначаються за допомогою продукційних правил, відомих як нормальна форма Бекуса-Наура (BNF).
Основна ідея полягала в тім, що будь-яка математична або логічна система є набір правил щодо перетворення одного рядка символів в інший рядок символів. Тобто продукційне правило після одержання вхідного рядка (антецедента) здатне виробити новий рядок (консеквент). Така ідея є дійсною стосовно програм і експертних систем, у яких початковий рядок символів є вхідні дані, а вихідний рядок є результатом певних перетворень вхідних даних.
Продукційна система Поста складається із групи продукційних правил, наприклад
(1) двигун автомобіля не запускається → перевірити акумулятор
(2) двигун автомобіля не запускається → перевірити наявність бензину
(3) перевірити акумулятор AND акумулятор несправний → замінити акумулятор
(4) перевірити наявність бензину AND бензин відсутній → заповнити бак бензином
Якщо є рядок "двигун автомобіля не запускається", то можна використати правило (1) або (2) для вироблення рядків "перевірити акумулятор" й "перевірити наявність бензину". Але може бути застосовано лише одне з них, обоє правила послідовно або жодного з правил. Якщо є рядок "перевірити акумулятор", а також рядок "акумулятор несправний", то може бути застосоване правило (3) для вироблення рядка "замінити акумулятор".
На відміну від звичайної мови програмування, такої як С або С++, порядок, у якому записані правила, не має значення.
Основним обмеженням продукційних правил Поста з погляду програмування є відсутність стратегії керування щодо впорядкування виклику правил. Система Поста дозволяє застосовувати правила до рядків будь-якої форми, оскільки відсутня специфікація, що визначає, як повинні застосовуватись ті або інші правила.
Марковскі алгоритми
Наступний великий крок у розробці методів застосування продукційних правил зроблений на основі відкриття Маркова щодо визначення структури керування для продукційних систем.
Марковський алгоритм - це застосування впорядкованої групи продукцій до вхідного рядка в порядку пріоритету. Якщо правило з найвищим пріоритетом є непридатним, то виконується наступне правило і т.д.
Марковський алгоритм завершує роботу за умов:
§ остання з продукцій не застосовна до рядка,
§ виконано продукцію, що кінчається крапкою.
Марковскі алгоритми можуть застосовуватись також до підрядків рядків, починаючи зліва. Так, продукційна система з єдиного правила:
AB→HIJ
після її застосування до вхідного рядка G AB KAB виробляє новий рядок GHIJKAB. Оскільки тепер продукція застосовується до нового рядка, кінцевим результатом стає рядок GHIJKHIJ.
Окрім констант передбачено два типи змінних:
§ односимвольні змінні (a, b, c, …, x, y, z) представляють будь-який окремий символ;
§ грецькі букви α, β і т.д. використаються в рядках як спеціальні знаки пунктуації.
Сховані марковські моделі (Hidden Marcov Model – HMM) використаються в розпізнаванні образів, зокрема, розпізнаванні мови.
Rete -алгоритм
Марковскі алгоритми є цілком певна стратегія керування – згідно порядку розташування правил, яка не є досить ефективним способом реалізації систем з багатьма правилами. Якщо потрібно створити експертну систему для реальних задач із сотень чи тисяч правил, то проблема ефективності стає найважливішою.
Фактично потрібен алгоритм, що має повну інформацію про всі правила й може застосувати будь-яке з них, не вживаючи повний перебір.
Рішенням проблеми є rete -алгоритм, відкритий Ч. Форгі в університеті Карнегі-Меллона в 1979 році при розробці експертної системи ОРS.
При буквальній реалізації ЕС перевіряє застосовність кожного правила вивода до кожного факту бази знань, при необхідності виконує його й переходить до наступного правила, вертаючись у початок при вичерпанні всіх правил. Навіть для невеликого набору правил і фактів такий метод працює неприйнятно повільно.
Алгоритм Rete забезпечує більш високу ефективність. При використанні Rete ЕС будує спеціальний граф або префіксне дерево, вузлам якого відповідають частини умов правил. Шлях від кореня до листа утворює повна умова деякої продукції. У процесі роботи кожний вузол зберігає список фактів, що відповідають умові. При додаванні чи модифікації факту він прогоняється по дереву, при цьому відзначаються вузли, умовам яких даний факт відповідає. При виконанні повної умови правила, коли система досягає листа графа, правило виконується.
Rete -алгоритм заснований на використанні динамічної структури даних, подібної до В+ дерева, що автоматично реорганізується з метою оптимізації пошуку.
Висока швидкодія досягається для систем із прямим логічним виводом, завдяки зберіганню в оперативній пам'яті інформації про правила, що перебувають у мережі, та за рахунок обмеження обсягу роботи, необхідної для повторного обчислення конфліктної множини після запуску одного із правил.
Недолік алгоритму - великі потреби в пам'яті.
В основу rete -алгоритм а покладена структура даних, запропонована на підставі двох емпіричних спостережень:
§ Часова надмірність. Кожне з правил, звичайно змінює лише кілька фактів, а кожна з цих змін впливає тільки на кілька правил.
§ Структурна подоба. Однаковий шаблон часто виявляється в лівій частині більше чим одного правила.
У наші дні rete -алгоритм продовжує залишатись важливим засобом підвищення швидкодії в тих випадках, коли система містить багато правил.
У rete -алгоритм і в кожному циклі контролюються тільки зміни в узгодженнях, тому в кожному циклі "розпізнавання-дія" не доводиться погоджувати факти з кожним правилом. Завдяки цьому істотно підвищується швидкість узгодження фактів з антецедентами, оскільки статичні дані, які не змінюються від циклу до циклу, можуть бути зігноровані.
Загальні відомості про фундамент сучасних ЕС, заснованих на правилах.
Основні недоліки систем продукцій:
§ труднощі складання продукційного правила, адекватного елементу знання, тому що важко виразити складні правила;
§ неможливий виклик одного правила з іншого (зв'язок між правилами тільки через дані);
§ відсутність внутрішньої структури веде до нерозв'язності проблеми несуперечності бази знань;
§ нема залежності кроків виводу від стратегії вибору, що ускладнює їхню інтерпретацію.
Висновок: "Продукційним системам не вистачає строгої теорії. Поки в них панує евристика. При заданій моделі проблемної області у вигляді сукупності продукцій не можна бути впевненим у її повноті й несуперечності. Причина невдач створення теорії криється в розпливчастості поняття продукції, у тій інтерпретації, що приписується ядру, а також у різних способах керування системою продукцій" [72, с. 55]
Семантичні мережі
Семантичні мережі, або просто мережі, - це класичний спосіб подання пропозиційної інформації у штучним інтелекті. Пропозиційним твердженням (або висловленням) є речення, що може бути істинним або ложним, таким як "усі собаки - ссавці" й "трикутник має три сторони". Висловлення мають форму декларативних знань, оскільки в них стверджуються факти.
З погляду математики семантична мережа є позначений орієнтований граф.
Семантичні мережі вперше були розроблені в 1968 році Квілліаном для досліджень в області штучного інтелекту як спосіб опису людської пам'яті й мови. Відтоді семантичні мережі успішно застосовувались для рішення багатьох задач подання знань. Розуміння змісту за допомогою семантичних мереж дозволяє вийти за межі можливостей програмного забезпечення простих ЕС або ШІ.
Структура семантичної мережі відображається графічно за допомогою вузлів і з'єднуючих їхніх дуг. Вузли іноді йменуються об'єктами а дуги - зв'язками, або ребрами.
Зв'язки в семантичній мережі застосовуються для подання відношень, а вузли, як правило, служать для подання фізичних об'єктів, концептів або ситуацій. Нижче показана звичайна мережа (фактично орієнтований граф), у якій зв'язки позначають авіаційні маршрути між містами. Вузли позначені кружками, а зв'язки - лініями, що з'єднують вузли. Стрілки показують напрямок, або орієнтацію, літаків, що роблять польоти (саме тому граф, на якому зазначені напрямки, називається орієнтованим).
Мережа загального виду
На іншому малюнку зв'язками є відношення між членами деякої родини.
Для семантичних мереж відношення мають винятково важливе значення, оскільки надають знанням базову структуру. Без них знання стають лише колекцію незв'язаних даних. А при їхній наявності базові структури дозволяють виводити інші знання.
Семантична мережа
Так, на підставі заданої структури можна зробити висновок, що Ганна й Білл - бабуся й дідусь Джона, незважаючи на те, що це відношення явно не задано.
Семантичні мережі ще називають асоціативними мережами, оскільки одні вузли в таких мережах асоційовані або зв'язані з іншими. В оригінальній роботі Квілліана людська пам'ять моделювалась асоціативною мережею, де поняття були вузлами, а зв'язки показували їхнє з'єднання між собою. Згідно до цього, якщо при читанні слів речення стимулюється один вузол, то активізуються його зв'язки з іншими, і така активність поширюється по мережі. Якщо ж достатню активізацію одержує інший вузол, то у свідомості спливає концепція, представлена ним.
Наприклад, хоча людина знає тисячі слів, але в його свідомості активізуються лише слова тої пропозиції, що він читає.
До двох найпоширеніших зв'язок належать is-a (є екземпляром) та a-kind-of (останню записують як АКО – є підмножиною, підкласом). При цьому більш загальним є клас, на який указує стрілка АКО, і називається суперкласом. Якщо суперклас має зв'язок АКО, що вказує на інший вузол, то він одночасно є класом суперкласу, на який вказує стрілка АКО.
Всі об'єкти класу повинні мати деякі спільні атрибути, кожен з них набуває значення. Комбінація атрибута й значення називається властивістю. Так, дирижабль має такі атрибути, як розміри, вага, форма й колір. Значенням атрибута форми є еліпсоїд. Іншими словами, властивістю дирижабля є еліпсоїдальна форма.
У семантичних мережах можна також знайти зв'язки інших типів.
Повторення характеристик вузла в його нащадках називається спадкуванням. Якщо не стверджується зворотне, то вважається, що всі елементи деякого класу успадковують всі властивості своїх суперкласів. Спадкування є корисний засіб у поданні знань, оскільки дозволяє не дублювати загальні характеристики.
Зв'язки й спадкування є основою ефективних способів подання знань, даючи можливість показувати складні відношення за допомогою декількох вузлів і зв'язок.
Трійки "об'єкт-атрибут-значення"
Одна з проблем, пов'язаних із застосуванням семантичних мереж, полягає в тому, що не передбачені стандартні визначення для імен зв'язок. Наприклад, у деяких книгах зв'язку is-a використають для подання і індивідуальних, і загальних відношень, тобто окрім свого значення їй надають також значення зв'язки АКО.
Щоб охарактеризувати всі знання, представлені в семантичній мережі, можна скористатись трійкою "об'єкт-атрибут-значення" (ОАЗ), або просто триплетом; такі триплети використались в експертній системі MYCIN, призначеній для діагностування інфекційних захворювань. Подання у вигляді трійки ОАЗ є зручним способом оформлення списку наявних знань у формі таблиць, а також дозволяє легко перетворити отриману таблицю в комп'ютерний код по методу індукції правил.
Приклад таблиці із трійками ОАЗ має вигляд.
Трійки "об'єкт-атрибут-значення" лежать в основі особливо корисного способу подання фактів і шаблонів, застосовуваних для узгодження з фактами в антецеденті правила.
Фреймова система - модель подання знань, заснована на теорії М. Мінського, як один з підходів до опису знань, придатний для розуміння сцен і мови. У фреймовій системі одиниця подання інформації - об'єкт, називаний фреймом. Він є формою подання деякої ситуації, описуваної сукупністю понять і даних.
Визначення Мінського «Фрейм — це структура даних, що представляє стереотипну ситуацію… До кожного фрейма приєднується декілька видів інформації: про те, як використовувати фрейм. Частина про те, чого можна чекати далі. Частина про те, що слід робити, якщо ці чекання не підтвердяться».
Ця структура є деяким шаблоном, витягуваним з пам'яті при виникненні нової або зміні вмісту існуючої ситуації.
Кожен фрейм має ім'я, єдине у фреймовій системі, та певну внутрішню структуру на множині іменованих слотів, які також мають певну структуру даних.
Раз встановлену структуру фрейму можна міняти лише в деталях.
Ця модель заснована на властивості концептів мати аналогії та будувати ієрархічні структури відношень типу "абстрактне-конкретне". Її застосування обмежене випадками чіткої ієрархії між фрагментами даних або знань.
Прикладами можуть бути класифікації рослин, тварин, несправностей апаратури, захворювань людей в медичній діагностиці тощо.
Представлення стереотипних ситуацій .
Однією з ключових властивостей мови представлення знань є її виразність при описі типових ситуацій.
Емпіричні дослідження показали, що люди:
· при запам'ятовуванні організують знання в структури, відповідні типовим ситуаціям;
· без зусиль знаходять вірну інтерпретацію твердження в рамках існуючого контексту;
· при читанні модифікують структуру знань, підстроюючись під контекст сприйняття.
Сприйняття тексту:
· Якщо читаний текст погано структурований, одні й ті ж речення містять не зв'язані за змістом фрагменти, сприйняття значно ускладнюється, оскільки стає неможливим швидко встановити, до якої структури знання слід віднести ту або іншу фразу.
· В той же час більшість людей без зусиль сприймає добре структурований текст, навіть якщо цей текст містить велику кількість друкарських помилок.
Дата добавления: 2022-01-22; просмотров: 15; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!