Извлечение ответа из опровержения, основанного на резолюции. Этапы процесса извлечения ответа

Извлечение ответа – это преобразование дерева опровержения в дерево доказательства с некоторым утверждением в корневой вершине. Это утверждение может быть использовано в качестве ответа. Дерево доказательств – это доказательство методом резолюции, которое основано на аксиомах и тавтологиях [11].

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

Этапы извлечения ответа:

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

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

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

D. Модификация дерева опровержений в дерево доказательств при неизменном множестве унификаторов.

E. Получение ответа в корневой вершине.

В качестве примера рассмотрим следующую логическую задачу:

“Если Джим ходит туда же, куда ходит Джон, и если Джон находится в школе, то где Джим?”

Задача содержит два утверждения, которые в предикатной форме имеют следующий вид:

,

,

где х – названия мест, в которых могут находится Джон и Джим.

Целевая функция, соответствующая вопросу, имеет вид:

,

что буквально можно трактовать следующим образом:

«существует место X, такое, что в нем находится Джим».

Дерево опровержения строится обычным образом и показано на рис.38.1.

Рис.38.1. Дерево опровержения

Дерево доказательств показано на рис.38.2 и строится следующим образом:

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

o Вычисляются резолюции, аналогично дереву опровержений.

o В корневой вершине формируется ответ.

Рис.38.2. Дерево доказательств

39. Теоремы Гёделя, Тарского и Черча о неполноте формальных систем

Общее представление о перспективах и рамках развития систем искусственного интеллекта в области формализации знаний и формальных методов получения новых знаний дают теоремы Гёделя, Тарского и Черча.

Первая теорема Гёделя (1931 год): Невозможно формализовать полностью любую систему знаний. Если доказано, что какая-либо формальная система знаний непротиворечива, значит она не полна.

Эта теорема фактически утверждает, что человеческое мышление полностью формализовать невозможно, так как существует неисчерпаемое поступательное развитие формальных представлений об окружающем человеке мире.

Вторая теорема Гёделя: Невозможно доказательство непротиворечивости формальной системы средствами той же системы.

Теорема Тарского (1935 г.): Существуют формальная системы, для которых всякая интерпретация приводит к выражениям, одновременно истинным и недоказуемым.

Гёдель: “То, что истинно, всегда недоказуемо, то есть понятие истинности неформализуемо”.

Теорема Черча (1936 г.): Исчисление предикатов первого порядка неразрешимо, то есть существуют неразрешимые формальные системы.

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

Экспертные системы

Экспертная система — это программа (на современном уровне развития техники), которая заменяет эксперта в той или иной области [21].

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

Цель таких систем состоит в том, чтобы объединить в одной ЭС знания нескольких экспертов, и получить в результате систему, которая может то, чего ни один из ее создателей не может. В настоящее время сложилась определенная технология разработки ЭС, которая включает следующие шесть этапов: идентификация, концептуализация, формализация, выполнение, тестирование и опытная эксплуатация.

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

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

Структурный подход к построению модели предметной области предполагает выделение следующих когнитивных элементов знаний:

1. Понятия. 2. Взаимосвязи. 3. Метапонятия. 4. Семантические отношения.

Выделяемые понятия предметной области должны образовывать систему, под которой понимается совокупность понятий, обладающая следующими свойствами: уникальностью (отсутствием избыточности); полнотой (достаточно полным описанием различных процессов, фактов, явлений и т.д. предметной области); достоверностью (валидностью — соответствием выделенных единиц смысловой информации их реальным наименованиям) и непротиворечивостью (отсутствием омонимии).

Последним этапом построения модели предметной области при концептуальном анализе является установление семантических отношений между выделенными понятиями и метапонятиями. Установить семантические отношения — это значит определить специфику взаимосвязи, полученной в результате применения тех или иных методов. Для этого необходимо каждую зафиксированную взаимосвязь осмыслить и отнести ее к тому или иному типу отношений.

Обобщенная структурная схема экспертной системы приведена на рис.39.1. В режиме пополнения знаний система опрашивает эксперта, задавая ему последовательность вопросов и получая на них ответы и пояснения. Если экспертов несколько, то система их ранжирует по уровню компетентности, что бы при возникновении противоречий в их знаниях можно было сформулировать однозначный ответ. В режиме консультации пользователь задает системы вопросы и получает ответы и пояснения. Система диалога обеспечивает формализованный ввод информации и визуализирует результаты работы экспертной системы. Лексический анализатор осуществляет контроль правильности вводимой информации и сообщает в возникающих ошибках. Логический анализатор реализует обработку данных, привлекая необходимые процедуры из базы знаний.

Рис.39.1. Структура экспертной системы

Существует около 200 базовых отношений, например, "часть — целое", "род — вид", "причина — следствие", пространственные, временные и другие отношения. Для каждой предметной области помимо общих базовых отношений могут существовать и уникальные отношения.