PROSPECTOR зсередини

Якщо є можливість, краще не розробляти експертні системи. Гарне вийшло початок курсу «Експертні системи»
У світі розроблено багато експертних систем, в цьому пості хотілося б розглянути структуру та логіку роботи однієї з древніх ЕС під назвою «ГЕОЛОГА».

1. Загальні поняття

Експертна система — комп'ютерна система, здатна частково замінити фахівця — експерта у вирішенні проблемної ситуації.

PROSPECTOR — геологорозвідувальна експертна система, призначена для геологічної розвідки родовищ корисних копалин.

2. Короткий опис системи

Система PROSPECTOR працює з нечіткими даними і нечіткими знаннями. Робота системи заснована на нечіткій логіці і добре застосовується для різних областей. Однак незважаючи на можливості використовуваної моделі, логіка роботи ЕС відрізняється від людської логіки і тому може бути незрозумілий сенс питань системи. У зв'язку з цим, система, конструйована на основі логіки системи PROSPECTOR повинна вміти пояснювати хід своїх «думок».

3. Алгоритм роботи

Робота системи являє собою діалог між системою і користувачем. В ході діалогу система одержує від користувача інформацію про спостереженнях на підставі яких робить певні висновки. Послідовність кроків виглядає так:
  1. Система вибирає спостереження, яке більшою мірою змінює шанси цільової гіпотези (в системі PROSPECTOR це наявність тих або інших корисних копалин)
  2. Система «запитує у користувача про наявність вибраної спостереження
  3. Користувач «відповідає» системі про присутність спостереження, причому відповіддю є число в діапазоні від -5 до +5, де -5 це «безумовно ні», +5 це «точно так», а 0 означає «не знаю».
  4. Після отримання відповіді, у семантичній мережі проходить хвиля змін: перераховуються шанси гіпотез, на які впливає спостереження.
  5. Якщо шанси цільової гіпотези влаштовують користувача, то система закінчує діалог, інакше крок 1.


4. Структура БЗ

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

4.1. Семантична мережа
Елементами семантичної мережі є гіпотези, спостереження і зв'язку між ними. Для прикладу семантична мережа може виглядати так:


Щодо один одного, гіпотези теж є спостереженнями. Наприклад, H2 — це спостереження для гіпотези Н1.

У семантичній мережі допустимі наступні відносини:
  • Гіпотеза може залежати від декількох спостережень
  • Спостереження може впливати на декілька гіпотез
Кожна гіпотеза має шанси (О) і вага ©.

Вага — це значення, що отримується від користувача на питання системи (для спостережень), іншими словами можна сказати, що вага — це ступінь можливості даного спостереження.

Шанс — це ступінь вірності цієї гіпотези (по суті та ж сама ймовірність). Формула залежності виглядає так:



Для гіпотез шанси обчислюються за формулою:



До початку використання ЕС, всі гіпотези мають, спочатку задані експертом, апріорні шанси, всі ваги (З) гіпотез і спостережень дорівнюють 0.

4.2. Зв'язку семантичної мережі
4.2.1. Загальні поняття
Кожна зв'язок вузлів (гіпотез і спостережень) в семантичній мережі має коефіцієнти LS і LN.

LS — це коефіцієнт достатності:

LN — це коефіцієнт необхідності:


При різних значеннях, коефіцієнти можуть мати різний зміст:
  • LS = LN — спостереження Е ніяк не впливає на гіпотезу Н.
  • LS = 1 — наявність спостереження Е не впливає на гіпотезу Н.
  • LN = 1 — відсутність спостереження Е не впливає на гіпотезу Н.
  • LS > 1 — спостереження Е сильно впливає на гіпотезу Н (чим більше значення, тим більше впливає).
  • LN < 1 — гіпотеза Н сильно потребує спостереження Е (чим менше значення, тим більше потребує).
Виходячи з 4 і 5 пунктів, можна зробити висновок, що в ЕС має сенс тільки пара коефіцієнтів:
LS > 1, LN < 1 — потребує і впливає

У системі можливі 3 види зв'язків:
  1. Логічні
  2. Контекстні (концептуальні)
  3. Продукційні
4.2.2. Логічні зв'язки
Логічні зв'язки — це операції математичної логіки «І», «АБО», «НЕ». Зв'язку накладають обмеження на гіпотези, які можна інтерпретувати так:
  • Для існування гіпотези Н1 повинні бути визначені обидва спостереження Е1 і Е2 (зв'язок «І»). Всі спостереження для даної зв'язку задаються одночасно.
  • Для існування гіпотези Н1 має бути визначено хоча б одне спостереження Е1 або Е2 (зв'язок «АБО»).
Коефіцієнти LS і LN встановлюються для всієї зв'язку, а не для кожного спостереження.

Вага також встановлюється для зв'язку і обчислюється за формулою:
  • Для «І»: З = max (C1, C2, ..., CN)
  • Для «АБО»: З = min (C1, C2, ..., CN)
  • Для «НЕ»: З = —
4.2.3. Контекстні зв'язки
Дані зв'язки вказують які питання повинні задаватися в першу чергу.

Наприклад, на малюнку ліворуч, перш ніж система задасть питання щодо гіпотези Н3, необхідно, щоб вага (З) гіпотези Н2 знаходився в інтервалі від 0 до 5 включно, тобто було дано позитивну відповідь щодо гіпотези Н2.

Дані зв'язку не мають коефіцієнтів достатності (LS) і необхідності (LN).

4.2.4. Продукційні зв'язку
Зв'язок виду «Якщо… то ...». Для зв'язків даного типу, ваги обчислюються шляхом розв'язання системи рівнянь:


Для H1 максимальний і мінімальний коефіцієнти дорівнюють:


Припустимо:
  • для спостереження Е1: З = 2, LS = 50, LN = 0.4
  • для спостереження Е2: З = -3, LS = 20, LN = 0.8
Таким чином ми отримуємо коефіцієнти:


Отримавши коефіцієнти ми можемо обчислити функцію залежності коефіцієнта k (формула 2) від ваги спостережень. Графік функції k представлений нижче:

Функція k не є прямою, тому для згладжування використовується логарифмування (зворотна операція зведення в ступінь):


Вирішивши систему рівнянь ми отримуємо функцію F:


Після знаходження функції F не важко порахувати значення для гіпотези Н1:


Нижче представлені графіки отриманої функції F (синій) і функції k (формула 2) (червоний):

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

4.3. Проходи в семантичній мережі
Прохід — зміна ваг семантичної мережі. Поділяються на два види: прямий і зворотний.

4.3.1. Прямий прохід
Прямий прохід виконується, коли користувач вносить нову інформацію про спостереженнях і необхідно перерахувати шанси гіпотез згідно з новими даними. Алгоритм прямого проходу включає в себе кроки:
  1. Встановлюємо для спостереження отримане від користувача значення ваг З
  2. Піднімаємося вгору по ієрархії до батьківського гіпотези (якщо батька немає, то вихід)
  3. Обчислюємо значення ваги (З) і шанси (Про) для гіпотези за формулами 1 і 3 відповідно, перехід до кроку 2.


4.3.2. Зворотний прохід
Використовується для знаходження питання системи (спостереження). Алгоритм складається з кроків:
  1. Знаходимо всі спостереження які впливають на цільову гіпотезу
  2. Для кожного спостереження встановлюємо значення ваги +5 та -5.
  3. Виконуємо прямий прохід для чергового спостереження
  4. Обчислюємо відхилення значення шансу цільової гіпотези після прямого проходу
  5. Повертаємо значення ваг і шансів у початковий стан
  6. Після виконання проходів для всіх спостережень виділяємо спостереження який більшою мірою впливає (змінює) на цільову гіпотезу — це і є наступний питання системи.


5. Приклад

Припустимо є семантична мережа:


Цільовою є гіпотеза Н1

Крок 1: виконуємо зворотний прохід

чинності контекстної зв'язку між H2 і H3, необхідно спочатку отримати значення для Н2, тому зворотний прохід буде виконуватися тільки для спостережень E1, E2 і Е4

чинності логічного зв'язку E1 і E2, значення буде присвоюватися до самої зв'язку

Всього буде виконано 4 прямих проходу:
  1. Е1Е2(З=-5) --> H1
  2. Е1Е2(С=+5) --> H1
  3. Е4(З=-5) --> H1
  4. Е4(С=+5) --> H1
Обчислюємо значення і Про для гіпотези Н2 для 1 варіанту (Е1Е2: З=-5):

1) Обчислюємо вага (З) і шанси (Про) для Н2:

Коефіцієнт зв'язків для гіпотези Н2 дорівнює:
k = k(E1&E2) * k(E4)

Отже:
kmax = LS(E1&E2) * LS(E4) = 400 * 10 = 4000
kmin = LN(E1&E2) * LN(E4) = 0.34 * 0.1 = 0.034

Вирішуємо систему рівнянь з пункту 4.2.4 формула 3:

отримуємо

Підставимо значення к = 400, отримуємо З = 3.02, Про = 2800

2) Обчислюємо вага (З) і шанси (Про) для Н1:

Коефіцієнт зв'язків для гіпотези Н1 дорівнює:
k = k(H2) * k(H3)

Отже:
kmax = LS(H2) * LS(H3) = 50 * 500 = 25000
kmin = LN(H2) * LN(H3) = 0.3 * 0.9 = 0.27

Вирішуємо систему рівнянь з пункту 4.2.4 формула 3:

отримуємо

Підставимо значення до = 50, отримуємо З = -0.41, Про = 31.86

e = abs(Oa — Op) = 31.86 — 3 = 28.86

Аналогічним шляхом знаходимо відхилення для інших варіантів і отримуємо:
  • E1E2 при C = -5, e = 28.86
  • E1E2 при C = +5, e = 2.04
  • E4 при C = +5, e = 0.12
  • E4 при C = -5, e = 1.89


За отриманими даними, наступними питаннями системи будуть E1 і E2 (в силу логічної зв'язки «І» користувач повинен внести дані для двох спостережень відразу).

Крок 2: отримуємо дані від користувача

Припустимо що користувач вніс дані для E1: З = 3, для E2: З = -4

Крок 3: виконуємо прямий прохід

1) Обчислюємо коефіцієнти (k), ваги (З) і шанси (O) для Н2:

Для зв'язку E1E2 — H2:
k = 400 ^ (3/5) = 36.41
C = 0.96
O = 254.87

Для зв'язку Н2 — Н1:
k= 50 ^ (0.96 / 5) = 2.12
C = -3.16
O = 6.36

Після виконання прямого проходу отримуємо семантичну мережу:


Якщо шанси альтернативи влаштовують, то закінчуємо. Інакше апостеріорні шанси (Op) стають апріорними (Oa) і переходимо до кроку 1.

6. Література

www.computing.surrey.ac.uk/ai/PROFILE/prospector.html
aitopics.org/sites/default/files/classic/Machine_Intelligence_10/MI10-Ch15-Gaschnig.pdf

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.