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. Е1E2(С=+5) --> H1
2. Е1E2(С=-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: Исправил:
— логические связи, вычисление веса (С)
— пример (исправил некорректные вычисления)