Реферат на тему:
Представлення неточних знань та стратегії неточного виводу в умовах
невизначеності
Вступ
.
. Відомі підходи до вирішення такого типу задач за допомогою систем, що
засновані на базах знань (ЗБЗ-системи). В цьому випадку задача
конфігурування зводиться до задачі перетворення ситуацій (ЗПС), яка
формулюється наступним чином:
вихідна ситуація;
множина цільових ситуацій.
є шлях вирішення.
Однією з перших ЗБЗ-систем для вирішення задач КСО була система R1 [1],
відома також як XCON.
База знань системи R1 містила біля 3000 продукційних правил і
забезпечувала конфігурування обчислювальних комплексів в корпорації
DIGITAL. Експерименти по конфігуруванню обчислювальних комплексів
проводились також в Інституті кібернетики НАН України[2]. Нині розробка
систем конфігурування для ринкової економіки набуває особливої
актуальності. Системи конфігурування забезпечують не тільки зменшення
часу на підбір конфігурації комплексу, а й виключають необхідність
участі висококваліфікованого персоналу в цьому процесі.
Нові можливості систем конфігурування з’явились у зв’язку з розвитком
засобів представлення знань, комп’ютерної графіки, торгівлі в
INTЕRNET’і.
Засоби представлення знань в системі СИКОН містять факти, об’єкти і
правила. Включення в систему представлення знань об’єктів з механізмом
успадкування властивостей дозволяє реалізувати ієрархічну організацію
знань і спростити формулювання цілей до конструкцій типу:
Конфігурувати комп’ютер з процесором PENTIUM III;
Конфігурувати віконний комплекс з алюмінійового сплаву.
Об’єкти в системі знань системи СИКОН можуть представляти як чіткі, так
і нечіткі поняття. Для останніх визначається функція належності до класу
об’єктів. Об’єми таких понять розглядаються як нечіткі множини.
Можливість представлення нечітких понять дозволяє формулювати нечіткі
цілі типу:
Конфігурувати комп’ютер високої продуктивності &
невисокої вартості & середнього об’єму пам’яті.
Машина виводу системи СИКОН включає стратегії нечіткого і ймовірностного
виводу з механізмами перерахування значень функцій належності і факторів
невизначеності в результаті застосування правил до нечітких та
невизначених фактів.
Сиситема СИКОН орієнтована на використання на персональних комп’ютерах
під WINDOW-95-2000, а також на робочих станціях під UNIX. Система має
розвинутий богатовіконний інтерфейс, який дозволяє одночасне простеження
баз фактів, об’єктів та правил.
Звіт складається із двох частин . В першій частині обговорюються
питання представлення точних знань і стратегії точного виводу. В другій
частині обговорються питання неточного представлення знань і стратегії
неточного виводу.
Представлення точних знань і стратегії точного виводу.
Точна інформація представляється в системі СИКОН з допомогою фактів,
об”єктів і продукційних правил.
Факти.
Факти є одною з основних форм високого рівня для представлення
інформації і зберігаються в двух форматах: впорядкованому і
невпорядкованому. Впорядкований факт складається з послідовностей
областей, які розділяються пробілами і обмежуються відкриваючою та
закриваючою дужками. Перша область впорядкрваного факту спеціфікує
“відношення”, яке застосовується до інших областей. Наприклад,
твердження (тато Івана Микола) означає, що Микола є татом Івана.
Впорядковані факти кодують інформацію позиційно. Невпорядковані (або
deftemplate) факти забезпечують користувача можливістю абстрагувати
структуру факта шляхом встановлення імені кожної області (або слоту). На
відміну від впорядкованих фактів слоти deftamplate-фактів можуть бути
обмежені типом, значенням або числовим інтервалом. Наприклад:
(класs (вчитель “Марина Іваненко”) (студентів 30) (кімната “45”))
Об”єкти.
Об”єкти в системі СИКОН розділяються на дві категорії: примітивні типи і
приклади класів. На об”єкти примітивного типу зсилаються просто задаючи
їх значення. Вони створюються і викреслюються автоматично по мірі
необхідності. Об”єкти примітивного типу не мають імен або слотів, а їх
класи являються напередвизначеними в системі.
На приклади класу зсилаються по імені або по адресу і вони створюються і
викреслюються механізмом повідомлень (messages) та спеціальними
функціями. Властивості об”єкту, який є прикладом класу виражаються
множиною слотів, які об”єкт отримує від свого класу. Клас є стереотип
для представлення загальних властивостей і поведінки об”єкту, який є
прикладом цього класу. Поведінка об”єкту описується в термінах
процедурного коду, який називається message-handler. Сам message-handler
приєднується до класу об”єктів. Маніпуляції з об”єктами виконуються
шляхом передачі їм повідомлення з допомогою функції SEND. Приклад класу
створюється з допомогою сонструкції defclass.
Як простий приклад ми визначим клас СКАНЕР, який є підкласом
комп”ютерної периферії (ПЕР), і двох прикладів класу СКАНЕР –
Astra-2100U та Astra-2200. Ми також визначимо message-handler, який буде
друкувати слоти активного прикладу (того, якому посилається
повідомлення):
(defclass СКАНЕР(is a ПЕР)
(slot розв”язність (create-accessor read-write)) (slot
формат(create-accessor read-write))
(slot глибина кольору(create-accessor read-write)))
(definstance СКАНЕР-objects
(Astra-2100U of СКАНЕР (формат А4) (розв”язність 600*1200)
(глибина кольору 36 bit))
(Astra-2200 of СКАНЕР (формат A4) (розв”язність 600*1200) (глибина
кольору 36 bit)))
(defmessage-handler СКАНЕР Print-slots (PP instance))
(SEND Astra-2200 of СКАНЕР Print-slots)
Message handler Print-slots буде працювати для всіх підкласів, які ми
можемо визначити для класу СКАНЕР. Головна різниця між об”єктом і
невпорядкованим фактом заключається в понятті успадкування
(inheritance). Успадкування дозволяє описати властивості та поведінку
класу в термінах інших класів. Система СИКОН підтримує множинне
успадкування : клас може прямо успадковувати слоти і message handlrer’и
від більше чим від одного класу.
Продукційні правила.
Синтаксис
(defrule [] []
* ; антецедент або Ліва Частина (ЛЧ)
=> *) ; консеквент або Права Частина
(ПЧ)
Символ “*” в визначенні означає один або множину елементів зв”язаних
кон”юнкцією, текст після символу “;” означає коментар.
Правило є сукопність умов (ЛЧ) і дій (ПЧ), які повинні бути здійснені
при виконанні умов. Умовний елемент лівої частини правила називається
також паттерном ( patterns). Стрілка (=>) відділяє ЛЧ від ПЧ. Правила
визначаються з допомогою конструкції defrule.
Виконання правил (або запалення) базується на існуванні або неіснуванні
паттернових сутностей(фактів або об”єктів). Машина виводу системи СИКОН
робить спроби порівняти паттерни ЛЧ з паттерновими сутностями поточного
стану системи і застосовує дію правої частини. Дія правила є функція,
яка типово не повертає значення, а здійснює деяку корисну дію, таку як
затвердити (assert) або викреслити (retract).
Приклад правила:
(defrule приклад-правила (рефріжератор світло включене) (рефріжератор
двері відчинені)
=> (assert (рефріжератор їжа зіпсована)))
Стратегія розв”язування конфліктів.
Якщо всі паттерні правила порівнюються з паттерновими сутностями
поточного стану системи, правило активується і ставиться на порядок
денний (agenda). Порядок денни є сукупністю активацій тих правил, які
порівнялись з паттернами сутності. Окрема підмножина правил може бути
згрупована в модулі з допомогою конструкцій defmodule. Кожний модуль
має свій порядок денний. Коли є багато активацій на порядку денному
машина виводу визначає яку активацію слід запалити. Термін запалення
означає, що СИКОН вибрала відповідне правило для виконання з порядку
денного. Порядок денний діє подібно стеку. СИКОН впорядковує активації
на порядку денному в термінах зростаючого пріорітету. СИКОН завжди
виконує дію правої частини верхнього правила на порядку денному. Це
правило потім видаляється з порядку денного і виконується дія нового
верхнього правила порядку денного. Цей процес продовжується поки не
залишиться ні однієї активації або не зустрінеться команда зупинитись.
Впорядкування на порядку денному базується на таких факторах:
Заново активоване правило розміщається вище всіх правил з нижчим
пріорітетом та нижче всіх правил з вищим пріорітетом;
Серед правил рівного пріорітету використовується поточна стратегія
розв”язування конфліктів, яка визначає розміщення серед інших правил
рівного пріорітету.
СИКОН забезпечує сім стратегій розв”язування конфліктів подібних
стратегіям системи OPS5 [3]. Поточна стратегія може бути установлена
використовуючи команду set-strategy (яка буде перевпорядковувати
порядок денний з допомогою нової стратегії).
Представлення неточних знань і стратегії неточного виводу.
В реальному світі існує багато знань, які є неточні, невизначені,
двозначні і ймовірностні по своїй природі. Багато із сучасних БПЗ-систем
використовують різні підходи для керування невизначенністю знань, такі
як фактори визначенності [4] , Байєсовські моделі або моделі
Дебстера-Шафера [5]. Деякі системи, такі як Fault [6], Flops [7], FRIL
[8] та FLISP [9] підтримують нечіткий вивод, але вони не можуть керувати
невизначенністю. Нечіткість і невизначенність- це два неточних поняття,
які використовуються в системі СИКОН. Далі ми будемо обговорювати
загальну теорію нечіткості і невизначенності та їх вплив на оцінку
правил.
Нечіткість.
Нечіткість [10] має місце, коли границі інформації не ясно визначені.
Представлення цього типу інформації в системі СИКОН базується на теорії
нечітких множин [11]. В цій теорії належність елемента множині може бути
частковим з відповідною ступінню (можливість).
в інтервалі [0,1], яке представляє ступінь належності x нечіткій
множині A. Наприклад, нечіткий термін молодий міг би бути визначеним за
допомогою нечіткої множини представленої в таблиці 1 і на малюнку 1.
Ступінь належності
25 1.0
30 0.8
35 0.6
40 0.4
45 0.2
50 0.0
Табл. 1. Нечіткий термін МОЛОДИЙ. Мал. 1.
Розподіл можливості
Значення ступені належності відповідає розподілу можливості терміну
МОЛОДИЙ. Всі нечіткі змінні повинні бути визначені перед використанням
в конструкціяхтипу deftemplates таким чином:
)) ; список первинних
термінів
– специфікація нечітких термінів(таких як гарячий,холодний,теплий),які
вико-
), з допомогою стандартної функції, або як лінгвістичний вираз, що
використовує наперед визначені терміни з допомогою бінарних операторів
and і or.
Приклад :
(deftemplate вік ; визначення нечіткої змінної ’вік’
0 120 років ; універс
((молодий (25 1) (50 0)) ; опис теміну МОЛОДИЙ
(старий (50 0) (65 1)))) ; опис теміну СТАРИЙ
Нечіткий слот має форму
Slot (type FUZZY-VALUE )
Факти з нечіткими слотами називаються нечіткими фактами. Нечіткі факти
можуть бути визначені, порівняні як паттерни в правилі, і затверджені
таким же чином як і звичайні факти.
Приклади:
(deftemplate персона
(slot ім’я (type SYMBOL))
(slot зріст (type FUZZY-VALUE нч-зріст))
(slot вага (type FUZZY-VALUE нч-вага))
(defrule велика персона
(персона (ім’я ?n)
(вага важкий)
(зріст високий)) => (print t ?n “є велика персона”))
Невизначеність.
Невизначеність має місце, коли хтось не має абсолютної впевненості про
частину інформації. Ступінь невизначеності звичайно представляється
точним числовим значенням на шкалі від 0 до 1. Невизначені факти мають в
системі СИКОН таку форму: (факт) [CF фактор визначеності]. CF діє як
обмежувач між фактом і фактором визначеності, а [ ] показують
опціональну частину. Наприклад (прогноз СОНЯЧНИЙ) CF 0.8 є факт, який
показує, що погода буде сонячною з визначеністю 80%. Але якщо CF
пропущений, тоді СИКОН вважає, що погода буде сонячною з визначеністю
100%.
Фактор визначеності може бути також зв’язаний з усім правилом, як
показує такий приклад:
(defrule літаюча-тварина
(declare (CF 0.95)) ; об’являє фактор визначеності правила
(тип тварини птиця)
=> (assert(тварина може літати)))
Невизначеність і нечіткість можуть мати місце одночасно, наприклад:
(deffact Нечіткий І Невизначений Факт (похибка_швидкість
більше_або_менше нуль) CF 0.9)
(defrule Невизначене_правило (declare (CF 0.8)) (вік_ Джона
молодий )
=> (assert (Джон відвідує школу)))
де похибка_швидкість і вік_ Джона є нечіткі змінні, нуль і молодий є
нечіткими термінами, більше_або_менше – модифікація нечіткого терміну,
а 0,9 і 0,8 є фактори визначеності, які зв’язані відповідно з фактом і
правилом.
Стратегії виводу.
Оцінка правила залежить від числа різних факторів, таких як : нечітка
змінна
знаходиться в антецедентній чи консеквентній частині правила; нечіткий
факт, який був затверджений, має ту ж нечітку змінну, що й вже існуючий
нечіткий факт і т.д. В цьому розділі будуть обговорюваться алгоритми для
оцінки факторів визначеності і нечітких об’єктів в правилах.
2.3.1Прості правила.
Розглянемо просте правило, яке має форму
if A then C CFr
A’ CFf
– – – – – – – – – – – – – –
C’ CFc
де:
A є антецедент правила; A’ є факт бази даних, з яким проводиться
порівняння антецеденту;
C є консеквент правила; C’ є фактично підрахований консеквент;
CFr є фактором визначеності правила; CFf є фактор визначеності факту;
CFc є підрахований фактор визначеності консеквенту.
Визначається три типи простих правил: CRISP, FUZZY-CRISP, та
FUZZY-FUZZY. Якщо антецедент правила не містить нечіткого об’єкту, тоді
ти правила є CRISP, незважаючи на те чи містить консеквент нечіткий
факт. Якщо лише антецедент містить нечіткий факт, тоді тип правила є
FUZZY-CRISP. Якщо антецедент і консеквент містять нечіткі факти, тоді
тип правила є FUZZY-FUZZY.
Якщо тип правила є CRISP, тоді A’ повинен бути рівним A для того, щоб
це првило запалити. В цьому випадку заключення C’ доррівнює C, і CFc =
CFr * CFf.
Якщо тип правила є FUZZY-CRISP, тоді A’ повинен бути нечітким фактом з
тими ж нечіткими змінними, що описані в A для того, щоб виконувалось
порівняння і правило було розміщене на порядку денному.
не повинні бути рівними, а повинні перетинатись. Наприклад, нечіткі
факти (температура висока) та (тиск високий) не порівнюються, тому що
нечіткі змінні температура і тиск не одні і ті ж. Однак, якщо дані
нечіткі факти (тиск низький), (тиск середній) і (тиск високий), як
показано на мал.2, ясно, що (тиск низький) і (тиск середній)
перетинаються і порівнюються, в той час, як (тиск низький) and (тиск
високий) не порівнюються.
тиск
мал. 2 Порівняння нечітких фактів.
(з яким порівнюється факт A’).
Міра подібності базується на мірі можливості P і мірі необхідності N.
Вона обчислюється у відповідності з формулою, що приведена в [12]
в іншому випадку
, яка описується такою функцією належності:
.
є нечіткою множиною, яка представляє значення нечіткого консеквента.
.
Фактор визначеності заключення обчислюється так CFc = CFr * CFf.
Приклад правила типу FUZZY-FUZZY:
(defrule правило- fuzzy-fuzzy ; антецедент і консеквент- є
нечіткі об’єкти.
(температура висока)
(assert (зміна- температури мала)))
(температура середня) ; факт з бази даних.
Графічна ілюстрація порівняння нечіткого факту та нечіткого паттерну,
генерація нечіткого заключення показані на мол.3.
Нечіткі множини Нечітка множина консеквенту
Затверджена
нечітка множина
Z
Температура середня зміна невелика
зміна
Температура висока
затверджена ???
Мал.3.Композиційне правило виводу(max-min)
??? використовуються для того, щоб показати невідомий лінгвістичний
вираз.
Складні правила
з неявною кон’юнкцією між ними. Вони трактуються як множина правил з
єдиним консеквентом. Якщо консеквентне твердження є нечіткий факт,
нечітке значення обчислюється за допомогою слідуючого базового
алгоритму, що приведений в [14]:
CF
– – – – – – – – – – – – – – – – – –
CFc
показує перетин двох нечітких множин, а функція належності визначається
так
then C.
then C.
Фактор визначеності заключення обчислюється відповідно з моделлю системи
MYCIN’S
) * CFr.
Приведений вище алгоритм може застосовуватись повторно, щоб управляти
будь-якою комбінацією антецедентних паттернів, тобто
) *CFr.
Загальний вклад
-значення нечіткого факту, що затверджений .
Невизначеності також агрегуються, формуючи загальну невизначеність за
такою формулою CFg = maximum(CFf, CFc).
Можливо затверджувати факт в правій частині правила зі специфічним
фактором визначеності. Замітимо, що фактор визнпченості буде також
обчислюватись відповідно з природою правила і будь-яким глобальним
вкладом. Обчислений фактор визначеності потім буде перемножатись з
фактором визначеності, який заданий в стверджувальному виразі.Це
корисний метод, який встановлює зважений фактор визначеності для правила
з багатьма консеквентами.
2.5.Дефазифікація
Виходом нечіткого виводу є нечітка множина, яка описує нечіткий розподіл
заключення. Однак, в деяких випадках, таких як застосування в
управлінні, потрібно вибирати єдину точку, яка відображатиме найкраще
значення множини. Цей процес редукції нечіткої множини в єдину точку
називається дефазифікацією. Широко застосовується метод, який обчислює
центр ваги (або момент) всієї множини. Метод центру ваги може бути
формально записаний так
,
– універс.
В системі СИКОН нечітка множина визначається множиною точок, що
розглядаються за допомогою лінійних сегментів. Тоді інтеграл редуцюється
до простого сумування
– загальне число точок.
Інший метод концентрує увагу на значеннях, в яких розподіл можливостей
досягає максимуму. Якщо максимальне значення досягається більш, ніж в
одній точці, тоді береться середнє значення всіх максимумів.
Неоднозначність має місце, коли максимальне значення трапляється вздовж
плато, а не як серія індивідуальних піків.
References
J.Mc Dermott. R1: a rule-base configurer of computer systems. Artificial
Intelligence, vol.19, n1, 1982.
В.П. Гладун, Н.И.Галаган, И.Г.Биба, А.Ф.Кургаев. Об автоматизации
решения задач комплектации состава технических средств
проблемно-ориентированного комплекса. Управляющие системы и машины, N5,
1982.
C.L.Forgy. Rete: a fast algorithm for many pattern many object pattern
match problem. Artificial Intelligence, vol. 19, pp 12-37, 1982.
E.H.Shortliffe. Computer-based medical consultation: MYCIN. American
Elsevier, New York, 1976.
G.Shafer. A Mathematical Theory of Evidence. Princeton University Press,
Princeton, Nj 1976.
T.Whalen, B.Scott, and F.Ganoe. Fault diagnosis in fuzzy network,
Proceeding of the International Conference on Cybernetics and Society,
IEE Press, New York, 1982.
J.Buckley and W.Siler. Fuzzy Operators for possibility interval sets.
Fuzzy Sets and Systems, 22: 215-227; 1987.
J.F.Baldwin. Evidential support logic programming. Fuzzy Sets and
Systems, 24: 1-26; 1987.
Z.A.Sosnovsi. FLISP – language for processing fuzzy data. Fuzzy Sets and
Systems, 37: 23-32; 1990.
Earl Cox. The fuzzy system Handbook. AP.Professional, 1995.
L.A.Zadeh. Fuzzy sets. Information and Control, 8: 338-383; 1965.
M.Cayrol., H.Farency, and H.Prade. Fuzzy pattern matching. Kybernetes,
11: 103-106; 1982.
L.A.Zadeh. The concept of a linguistic Variable and its Application to
Approximate Reasoning. New York, 1973.
T.Walen and B.Scott. Issues in fuzzy production systems. International
Jornal of Man-Machine Studies, 19: 57; 1983.
PAGE
ступінь
1.0
0 10 20 30 40 50 ВІК
(тиск низький)
(тиск середній)
(тиск високий)
Нашли опечатку? Выделите и нажмите CTRL+Enter
