Лекция 6
1.2.1 Примеры стратегии вывода
Рассмотрим формализм нормальных алгоритмов Маркова, в котором правила вывода реализуются на основе операторов подстановки.
Пусть а и b - произвольные слова. Будем говорить, что слово а входит в слово b, если существуют такие слова с и d, что b = cad.
Основным правилом вывода является подстановка. Оператор подстановки а ® Ь используется для замены левого вхождения слова а на слово 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
Здесь внизу под стрелкой указан номер оператора.
В системах нормальных алгоритмов Маркова выводимость трактуется в конструктивном смысле - как получение из исходного слова (образца) других слов. Это - так называемый вывод по образцу (нашедший применение, например, в системах, использующих фреймы и семантические сети). Каноническая продукционная система Поста также является системой вывода по образцу.
Пусть x1, x2, ..., xn - попарно различные переменные, которые имеют области определения D1, D2, ..., Dm соответственно. Если переменная х связана некоторым значением из Dj, , то будем вместо х, писать .
Образец t это конструкция
t
где каждому xi, сопоставлен терм уi , являющийся либо самой переменной хi, (если она не связана), либо , если xi = .
Например,
t1 =
Пусть даны два образца t1 и t2. Будем говорить, что из t1 и t2 выводится образец t3, и писать это: , если выполнены следующие условия:
1) t1 и t2 содержат общие переменные
2) пусть xi - одна (любая) из общих переменных, тогда xi и в t1, и в t2 либо связана одним и тем же значением, либо как минимум одна из них не связана вовсе.
3) t3 образуется путем включения (без дублирования) всех переменных из t1 и t2. При этом если общая переменная xi связана, скажем в t1, значением хi = а, а в t2 свободна ( не связана), то в t3 xi будет иметь значение а. В этом случае говорят, что переменные в t3 наследуют значения соответствующих переменных в t1, t2.
Пример вывода по образцам t1, t2 образца t3.
t1 =
t2 =
из t1, t2 выводим образец t3
t3 =
Другой важной стратегией, используемой в машинах вывода, является Байесовская стратегия вывода, которая используется в системах, где детерминированность выводов является скорее исключением, чем правилом.
Байесовская стратегия вывода оперирует вероятностными знаниями. Ее основная идея заключается в оценке апостериорной вероятности гипотезы при наличии фактов, подтверждающих или опровергающих гипотезу. Пусть
Р(Н) = - априорная вероятность гипотезы Н при отсутствии каких- либо свидетельств;
Р(Н:Е) = - апостериорная вероятность гипотезы Н при наличии свидетельства Е.
Согласно теоремы Байеса:
(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) при наличии многих свидетельств E1, E2, ..., En принимает вид:
(1.31)
Таким образом, на основании формул (1.30) и (1.31) имеется возможность просто пересчитывать апостериорные вероятности гипотез на основании получаемых свидетельств. Теорема Байеса является основой механизма вывода в экспертных системах PROSRECTOR и HULK.
Рассмотрим пример использования стратегии Байеса. Пусть требуется провести дифференциальную диагностику между заболеваниями D1, D2, ..., Dn. Для простоты, пусть имеется три заболевания и четыре признака, по которым должен быть составлен диагноз.
Заболевания:
D1 - тетрадаФалло, D2 - дефект межпредсердечной перегородки, D3 - незараценный артериальный проток.
Признаки:
S1 - цианоз, S2 - усиление легочного рисунка, S3 - акцент II тона во втором межреберье слева, S4 - правограмма (ЭКГ).
Допустим, известны следующие условные и безусловные вероятности (табл. 1.2), полученные на основе накопленной статистики о больных данными заболеваниями.
Таблица 1.2
Dj | P(Dj) | P(S1/Dj) | P(S2/Dj) | P(S3/Dj) | P(S4/Dj) |
D1 | 0,35 | 0,9 | 0 | 0,05 | 0,6 |
D2 | 0,15 | 0,15 | 0,8 | 0,8 | 0,8 |
D3 | 0,50 | 0,10 | 0,95 | 0,90 | 0,10 |
Пусть у пациента налицо все четыре признака: S1, S2, S3, S4. Каков диагноз заболевания? На основе теоремы Байеса можно оценить апостериорные вероятности заболеваний в предположении, что признаки S1, S2, S3, S4 независимые. Найдем
(1.32)
Из условия независимости признаков имеем:
P(S1, S2, S3, S4|Di) = P(S1|Di) × P(S2|Di) × P(S3|Di) × P(S4|Di) (1.32)
Рассмотрим другой пример с шансами для оценки дождя на другой день, если сегодня сырой, облачный, ветренный сентябрьский день. Предположим имеется некоторая статистика, собранная по сентябрьским дням и сведенная в таблицу 1.3.
Оценим априорные шансы дождя на следующий день:
Теперь вычислим отношения правдоподобия с учетом свидетельств:
Таблица 1.3
Фактор, характеризующий текущий день | Значение | Число наблюденных дождливых следующих дней | Число наблюденных не дождливых следующих дней |
Влажность | высокая средняя умеренная | 35 12 6 _____ 53 | 18 42 60 _____ 120 |
Ясность | ясно пасмурно | 5 8 40 _____ 53 | 83 27 10 _____ 120 |
Ветренность | слабая средняя сильная | 19 27 7 _____ 53 | 52 44 24 _____ 120 |
Примечания: 1) общее число наблюденных сентябрьских дней - 173;
2) число дождливых дней - 53.
Далее, используя формулу (1.31), находим
О(дождь_завтра*) = 0.44 × 4.4 × 0.67 × 0.66 = 0.856
и с помощью формулы (1.29) рассчитываем вероятность дождя завтра, если сегодня облачная, сырая и ветреная погода:
Таким образом, байесовская стратегия позволяет корректировать вероятность гипотезы с учетом известных факторов.
1.2.2 Как функционирует машина вывода
Машина вывода является интерпретатором правил, который использует факты базы знаний для решения проблем. На входе машина вывода получает цель консультации.
На каждом шаге вывода машина вывода строит (наращивает) контекст (трассу вывода) и пытается подобрать правило, применимое к этому контексту. Контекст - это математическая структура, соответствующая образцу (см. предыдущий параграф), которому дополнительно придана цель вывода. При этом цель вывода может также задаваться в виде образца-цели.
Изменение контекста реализуется либо вследствие применения правил вывода, либо путем ввода фактов, запрашиваемых у пользователя. Например, пусть цель консультации - установить физические кондиции пациента. В этом случае, задавая вопросы типа
"Каков возраст пациента?"
"Каков вес пациента?"
"Потребляет ли пациент жиры?" и т.д.
Система создает контекст, представляющий множество переменных и их значений, например:
Возраст = 35
Вес = 85
Потребление жиров = 50 и т.д.
С другой стороны, контекст может быть наращен и с помощью правил. Например, если есть следующее правило:
ЕСЛИ (ВЕС = X) & (ВОЗРАСТ < 40), ТО
(ИДЕАЛЬНЫЙ_РОСТ = 100 + X),
то контекст будет расширен путем вычисления и добавления факта
ИДЕАЛЬНЫЙ_РОСТ = 185
Простейший алгоритм, осуществляющий построение трассы вывода, заключается в следующем:
1. Определить исходный контекст.
2. Занести все переменные исходного контекста в очередь переменных логического вывода, а их значения (если заданы) - в список переменных.
3. Просмотреть список переменных и найти ту переменную, имя которой стоит в начале очереди переменных логического вывода. Если переменная найдена, записать в указатель переменных условия, номер правила и число 1. Если переменная не найдена, перейти к шагу 6.
4. Присвоить значения непроинициализированным переменным условной части найденного правила (если такие есть). Имена переменных содержатся в списке переменных условия правила. Проверить все условия правила и в случае их истинности обратиться к части "ТО" правила.
5. Присвоить значение переменной, входящей в часть "ТО" правила, и поместить ее в конец очереди переменных логического вывода.
6. Удалить переменную, стоящую в начале очереди переменных логического вывода, если она больше не встречается в условной части какого-либо правила.
7. Закончить процесс рассуждений, как только опустеет очередь переменных, логического вывода. Если в очереди есть еще переменные, вернуться к шагу 3.
На машину вывода возлагаются следующие основные задачи:
1 .Построение трассы вывода.
2.Интерпретация правил вывода и их применение к текущему контексту.
3 . Повышение эффективности поиска.
Формальное понятие трассы вывода дается ниже. Задача построения трассы вывода заключается в отображении в памяти ЭВМ последовательности шагов вывода, применяемых правил и получаемых значений переменных. Множество значений переменных, известных на данном шаге вывода образует контекст. Цель построения трассы - возможность ее переопределения с некоторого ранее порожденного контекста, Создание текущего контекста связано с выбором правила вывода из множества альтернативных правил - вторая задача. От такого выбора в конечном итоге зависит эффективность системы (быстродействие ЭС), поэтому необходимы меры по обеспечению достаточной эффективности машины вывода.
Существует два базовых подхода к построению трассы вывода. Первый основан на логике решения в направлении "от того, что известно - к тому, что надо найти"; второй подход, наоборот, использует движение в обратном направлении: "от того, что надо найти - к тому, что известно" Первый подход характеризует системы с прямым выводом, второй - системы с обратным выводом. Обратный вывод применяется в тех случаях, когда цели известны и их сравнительно немного.
В системах диагностики чаще применяется прямой вывод, в то время как в планирующих системах более эффективен обратный. Кроме того, используется и комбинированный вывод, основанный на сочетании прямого и обратного поиска. Комбинированный вывод называется также циклическим.
Проблема организации трассы вывода напрямую связана с повышением эффективности поиска. Мы подробно исследуем эти вопросы в последующих разделах. Сейчас формализуем задачу организации трассы вывода. Для этого введем понятие дерева решения. Рассмотрим пятерку
<S0, SF, A, RA, RS>, (1.34)
где S0 - исходное состояние системы (объекта, модели);
SF - конечное (искомое) состояние системы (объекта, модели);
А - алгоритм отображения ;
RA - список ограничений на реализацию алгоритма А;
RS - список ограничений на 8у (критерий).
Состояние исследуемой системы (объекта) Sj, непосредственно достигаемое из Sk , назовем преемником Sk, а состояние Sk - предшественником Sj. Граф Г(S, p) с множеством вершин состояний Sj Î S и дуг p, связывающих предшественников и преемников, образует дерево решения с корнем S1 и листом SF если:
1) m-й ярус в Г образуют те преемники (m - 1)-го яруса (m = 1,2,...), которые не входят в ярусы (m - 2), (m - 3) и т.д.;
2) листьями в Г являются состояния, все преемники которых содержатся в верхних ярусах (исключение, возможно, составляет SF).
Возможными вариантами постановки задачи относительно (1.34) являются (1.5) - (1.8).
Все эти задачи так или иначе упираются в проблему отыскания маршрута М в Г(S, p), связывающего S0 и SF. Некоторая (любая) законченная часть этого маршрута называется трассой вывода. Очевидно, что эффективность стратегии вывода определяется в первую очередь тем, насколько "близко" она держится М и, во-вторых, насколько велики затраты (памяти и процессорного времени) для реализации этой стратегии вывода. В качестве одной из оценок эффективности стратегии поиска определена оценка меры близости трассы вывода и М в виде
(1.35)
где L - длина найденного пути к цели (длина М),
Если Вам понравилась эта лекция, то понравится и эта - 60. Организация пожарной охраны на предприятиях.
Т - общее число вершин, пройденных при поиске цели в Г(S, p).
Очевидно, что детерминированная оптимальная стратегия обеспечивает максимальную меру близости Р, равную 1. Повышение эффективности поиска по-разному достигается в существующих системах вывода:
(1) использование эвристических функций оценки;
(2) использование приоритетов для правил;
(3) использование метаправил (правил для правил).
Эти вопросы будут обсуждены позже.