Примеры стратегии вывода

Рассмотрим формализм нормальных алгоритмов Маркова, в котором правила вывода реализуются на основе операторов подста­новки.

Пусть а и b - произвольные слова. Будем говорить, что слово а входит в слово b, если существуют такие слова с и d, что b = cad.

Основным правилом вывода является подстановка. Оператор под­становки а ® b используется для замены левого вхождения слова а на слово b. Для того, чтобы применить оператор а ® b к слову e, необ­ходимо, чтобы е содержало а. В последнем случае будем говорить, что выполнены условия применимости оператора а ® b. Из множества операторов, для которых выполнены условия применимости, всегда выбирается один оператор (например, первый по порядку). Отметим, что вывод считается детерминированным, если всякий раз условия при­менимости выполняются не более чем для одного правила вывода. Алгоритм завершает работу, если либо нет выполнимых операторов, либо выполняется специальный оператор конца (стоп-оператор).

Пример.

(1) a ® bc

(2)c ® ebcc

(3)c ® d

(4)d ® e

(5)b ® e

(6) есс ® d.

e - символ пробела.

Рассмотрим, как преобразуется в этой системе слово cad:

cad ® ebccad ® eccad ® dad ® ad ® bcd ® cd ® ebccd ® eccd ® dd ® d ® e

Здесь внизу под стрелкой указан номер оператора.

В системах нормальных алгоритмов Маркова выводимость трак­туется в конструктивном смысле - как получение из исходного слова (образца) других слов. Это - так называемый вывод по образцу (на­шедший применение, например, в системах, использующих фреймы и семантические сети). Каноническая продукционная система Поста так­же является системой вывода по образцу.

Пусть x₁, x₂, ..., x_n - попарно различные переменные, которые име­ют области определения D₁, D₂, ..., D_m соответственно. Если переменная х связана некоторым значением из D_j, , то будем вместо х, писать .

Образец t это конструкция

t

где каждому x_i, сопоставлен терм у_i , являющийся либо самой перемен­ной х_i, (если она не связана), либо , если x_i = .

Например,

t₁ =

Пусть даны два образца t₁ и t₂. Будем говорить, что из t₁ и t₂ выводится образец t₃, и писать это: , если выполнены следующие условия:

1) t₁ и t₂ содержат общие переменные

2) пусть x_i - одна (любая) из общих переменных, тогда x_i и в t₁, и в t₂ либо связана одним и тем же значением, либо как минимум од­на из них не связана вовсе.

3) t₃ образуется путем включения (без дублирования) всех перемен­ных из t₁ и t₂. При этом если общая переменная x_i связана, скажем в t₁, значением х_i = а, а в t₂ свободна ( не связана), то в t₃ x_i будет иметь значение а. В этом случае говорят, что переменные в t₃ наследуют значения соответствующих переменных в t₁, t₂.

Пример вывода по образцам t₁, t₂ образца t₃.

t₁ =

t₂ =

из t₁, t₂ выводим образец t₃

t₃ =

Другой важной стратегией, используемой в машинах вывода, является Байесовская стратегия вывода, которая используется в систе­мах, где детерминированность выводов является скорее исключением, чем правилом.

Байесовская стратегия вывода оперирует вероятностными знания­ми. Ее основная идея заключается в оценке апостериорной вероятности гипотезы при наличии фактов, подтверждающих или опровергающих гипотезу. Пусть

Р(Н) = - априорная вероятность гипотезы Н при отсутствии каких- либо свидетельств;

Р(Н:Е) = - апостериорная вероятность гипотезы Н при наличии свидетельства Е.

Согласно теоремы Байеса:

(1.26)

и

где Р(Н*)оценивает новую вероятность гипотезы Н с учетом свиде­тельства Е.

Введем отношение правдоподобия ОП(Н:Е),

(1.27)

а также формулу для вычисления шансов O(H),

(1.28)

Из (1.28) нетрудно обратным преобразованием получить

(1.29)

Теперь формула Байеса (1.8) на языке шансов принимает следую­щий вид:

O(H*) = O(H) OП(H:E),(1.30)

где O(Н*) - новая оценка шансов для гипотезы Н с учетом свидетельст­ва Е.

Формула (1.30) при наличии многих свидетельств E₁, E₂, ..., E_n при­нимает вид:

(1.31)

Таким образом, на основании формул (1.30) и (1.31) имеется воз­можность просто пересчитывать апостериорные вероятности гипотез на основании получаемых свидетельств. Теорема Байеса является основой механизма вывода в экспертных системах PROSRECTOR и HULK.

Рассмотрим пример использования стратегии Байеса. Пусть требуется провести дифференциальную диагностику между заболева­ниями D₁, D₂, ..., D_n. Для простоты, пусть имеется три заболевания и че­тыре признака, по которым должен быть составлен диагноз.

Заболевания:

D₁ - тетрадаФалло, D₂ - дефект межпредсердечной перегородки, D₃ - незараценный артериальный проток.

Признаки:

S₁ - цианоз, S₂ - усиление легочного рисунка, S₃ - акцент II тона во втором межреберье слева, S₄ - правограмма (ЭКГ).

Допустим, известны следующие условные и безусловные вероят­ности (табл. 1.2), полученные на основе накопленной статистики о боль­ных данными заболеваниями.

Таблица 1.2

Пусть у пациента налицо все четыре признака: S₁, S₂, S₃, S₄. Каков диагноз заболевания? На основе теоремы Байеса можно оценить апо­стериорные вероятности заболеваний в предположении, что признаки S₁, S₂, S₃, S₄ независимые. Найдем

(1.32)

Из условия независимости признаков имеем:

P(S₁, S₂, S₃, S₄|D_i) = P(S₁|D_i) × P(S₂|D_i) × P(S₃|D_i) × P(S₄|D_i) (1.32)