PROSPECTOR зсередини

PROSPECTOR зсередини

Якщо є можливість, краще не розробляти експертні системи (с)

У світі розроблено безліч експертних систем, в даному пості хотілося б розглянути структуру і логіку роботи однієї з стародавніх ЕС під назвою «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 = 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 встановлюються для всього зв'язку, а не для кожного спостереження.

Вага також встановлюється для зв'язку і обчислюється за формулою:

  • Для «І»: С = min (C1, C2, …, CN)
  • Для «АБО»: С = max (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 (для С (Е1Е2) = + 5), отримуємо С (Н2) = 3.02, О (Н2) = 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:

отримуємо

Обчислюємо значення k (для С (Н2) = 3.02):

k = 50 ^ (3.02 / 5) = 10.62

Отримуємо С (Н1) = -1.75, О (Н1) = 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 (вибирається С = min (3, -4) в силу логічного «І»):

k = 0.34 ^ (4/5) = 0.42

C (Н2) = -1.77

O (Н2) = 2.94

Для зв'язку Н2 - Н1:

k = 0.3 ^ (1.77 / 5) = 0.65

C (Н1) = -3.24

O (Н1) = 1.95

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

Якщо шанси альтернативи влаштовують, то закінчуємо. Інакше апостериорні шанси (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

UPD: Виправив:

- логічні зв'язки, обчислення ваги (С)

- приклад (виправив некоректні обчислення)

Image