2. В чем сущность процесса извлечения ответа?

Во многих случаях процесс поиска доказательств формул, содержащих переменные относящиеся к квантору общности, связан также с поиском значений или частных случаев этих переменных. Иначе говоря, мы хотели бы знать, следует ли правильно построенная формула логически из Ф_о, и если да, то получить ответ при каких значениях х формула F(х) – истинна.

Задача нахождения доказательства для исходя из Ф_о является обычной задачей на доказательство теорем в исчислении предикатов, но нахождение удовлетворяющего теореме х требует построения процедуры «конструктивного» доказательства.

Процедура извлечения ответа состоит в преобразовании дерева опровержения (с NILL в корневой вершине) в модифицировании дерева доказательства с некоторым утверждением в корневой вершине.

Основные этапы процесса извлечения ответа.

1. С помощью некоторого процесса строится дерево опровержения на основе резолюции.

2. Вместо любых сколемовских функций, появляющихся в предложениях, являющихся отрицанием целевой формулы, подставляются новые переменные.

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

4. Строится модифицированное дерево доказательства, в котором повторяется применения каждого правила резолюции так же, как и в дереве опровержения.

5. Предложение, расположенное в корневой вершине модифицированного дерева, представляют ответное утверждение, извлеченное при таком процессе.

Билет №22

1. Опишите методику выработки заключения на основе вероятностных характеристик.

В общем случае есть множество гипотез и множество признаков. С каждой гипотезой связано 5 величин, каждая из которых является вероятностью (рис. 1.3).

Р(Н) - текущая вероятность того, что данная гипотеза является истинной.

Р_mах и Р_min пересчитываются после рассмотрения признаков. Pmax - текущая максимальная вероятность для данной гипотезы, которая могла бы быть достигнута, если бы все остающиеся свидетельства были бы в ее пользу. Pmin - соответственно, минимальная текущая вероятность, когда оставшиеся свидетельства против гипотезы. В конце, т.е. после учета всех признаков, все 3 характеристики (Pmax, P(H) и Pmin) должны сойтись в одной точке.

M₁ - критерий верхнего порога для принятия конкретной гипотезы. Определяется как величина, пропорциональная P_max еще до того, как начался учет свидетельств, т.е. априори задается пользователем (экспертом).

M₂ - критерий нижнего порога для отказа от конкретной гипотезы. Также определяется априори пользователем (экспертом).

Рис. 1.3. Выработка заключения

Если существует какая-нибудь гипотеза, P_min для которой на некотором шаге больше, чем P_max для любой другой гипотезы, то такая гипотеза наиболее вероятная.

Существуют два класса заключений: вероятные и неопределенные.

Вероятные: Те гипотезы, для которых P_min больше, чем М₁.

Неопределенные: Те гипотезы, для которых P_min меньше М₁, но P_max больше М₂. В этом случае необходимо продолжать рассматривать признаки.

Те гипотезы, для которых Pmax оказалось меньше М2, отбрасываются.

Рассмотрим один из возможных подходов к выработке заключения, опираясь на вышеописанные величины.

Методика вывода заключения на основе байесовского подхода

1. Для каждой гипотезы фиксируется ее текущая априорная вероятность (путем просмотра базы знаний).

2. Для каждого неучтенного свидетельства находится его цена. Если априорно задан порядок свидетельств, то этот пункт не выполняется.

3. Выбирается свидетельство с максимальной ценой. Если априорно задан порядок свидетельств, то выбирается очередное свидетельство.

4. Получить у пользователя ответ с учетом неопределенности по поводу выбранного свидетельства.

5. При заданном ответе сделать все пересчеты гипотез, к которым относится это свидетельство.

6. Вычисление для каждой гипотезы Pmax и Pmin.

7. Гипотезы для которых Pmax меньше М₂ отбрасываются.

8. Если существует гипотеза, для которой Pmin превышает Pmax для любой другой гипотезы, то существует наиболее вероятный результат, который и следует выдать пользователю. Переход к 10. Если такой гипотезы нет, то переход к 9.

9.Если еще не все свидетельства учтены, то рассчитанные в пункте 5 апостериорные вероятности гипотез фиксируются как текущие априорные вероятности. Переход к 2.

10. Вызывается из системы резюмирующая программа, которая опишет пользователю выводы, которые она сделала (о вероятных и наиболее вероятных событиях) и почему.