Якщо є можливість, краще не розробляти експертні системи (с)
- 1. Загальні поняття
- 2. Короткий опис системи
- 3. Алгоритм роботи
- 4. Структура БЗ
- 4.1. Семантична мережа
- 4.2. Зв'язки семантичної мережі
- 4.2.1. Загальні поняття
- 4.2.2. Логічні зв'язки
- 4.2.3. Контекстні зв'язки
- 4.2.4. Продукційні зв'язки
- 4.3. Проходи в семантичній мережі
- 4.3.1. Прямий прохід
- 4.3.2. Зворотній прохід
- 5. Приклад
- 6. Література
У світі розроблено безліч експертних систем, в даному пості хотілося б розглянути структуру і логіку роботи однієї з стародавніх ЕС під назвою «PROSPECTOR».
1. Загальні поняття
Експертна система - комп'ютерна система, здатна частково замінити фахівця - експерта у вирішенні проблемної ситуації.
PROSPECTOR - геологорозвідувальна експертна система, призначена для геологічної розвідки родовищ корисних копалин.
2. Короткий опис системи
Система PROSPECTOR працює з нечіткими даними і нечіткими знаннями. Робота системи заснована на нечіткій логіці і добре застосовується для різних областей. Однак незважаючи на можливості використовуваної моделі, логіка роботи ЕС відрізняється від людської логіки і тому користувачеві може бути незрозумілий сенс питань системи. У зв'язку з цим, система, що конструюється на основі логіки системи PROSPECTOR повинна вміти пояснювати хід своїх «думок».
3. Алгоритм роботи
Робота системи - це діалогове вікно між системою і користувачем. Під час діалогу система отримує від користувача інформацію про спостереження на підставі яких робить певні висновки. Послідовність кроків виглядає так:
- Система вибирає спостереження, яке більшою мірою змінює шанси цільової гіпотези (в системі PROSPECTOR це наявність тих чи інших корисних копалин)
- Система «запитує» у користувача про наявність обраного спостереження
- Користувач «відповідає» системі про присутність спостереження, причому відповіддю є число в діапазоні від -5 до + 5, де -5 це «безумовно ні», + 5 це «безумовно так», а 0 означає «не знаю».
- Після отримання відповіді користувача, в семантичній мережі проходить хвиля змін: перераховуються шанси гіпотез, на які впливає спостереження.
- Якщо шанси цільової гіпотези влаштовують користувача, то система закінчує діалог, інакше крок 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 види зв'язків:
- Логічні
- Контекстні (концептуальні)
- Продукційні
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 і 3 відповідно, перехід до кроку 2.
4.3.2. Зворотній прохід
Використовується для знаходження питання системи (спостереження). Алгоритм складається з кроків:
- Знаходимо всі спостереження які впливають на цільову гіпотезу
- Для кожного спостереження встановлюємо значення ваги + 5 і -5.
- Виконуємо прямий прохід для чергового спостереження
- Обчислюємо відхилення значення шансу цільової гіпотези після прямого проходу
- Повертаємо значення терезів і шансів у вихідний стан
- Після виконання проходів для всіх спостережень виділяємо спостереження яке більшою мірою впливає (змінює) на цільову гіпотезу - це і є наступне питання системи.
5. Приклад
Припустимо є семантична мережа:
Цільовою є гіпотеза Н1
Крок 1: виконуємо зворотний прохід
У силу контекстного зв'язку між H2 і H3, необхідно спочатку отримати значення С для Н2, тому зворотний прохід буде виконуватися тільки для спостережень E1, E2 і Е4
В силу логічного зв'язку E1 і E2, значення С буде присвоюватися до самого зв'язку
Всього буде виконано 4 прямих проходи:
- Е1Е2 (С = + 5) -- > H1
- Е1Е2 (С = -5) -- > H1
- Е4 (С = + 5) -- > H1
- Е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: Виправив:
- логічні зв'язки, обчислення ваги (С)
- приклад (виправив некоректні обчислення)