Материал: Алгебра_кортежей

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

[{g1, g2, g4}, {m3}], [{g1, g3}, {m4}], [{g3, g4}, {m1}], [{g2, g4}, {m2, m3}], [{g1}, {m3, m4}], [{g3}, {m1, m4}], [{g4}, {m1, m2, m3}].

Каждый них соотносится с определенным формальным понятием, в чем можно убедиться, используя табл. 5.9. Таким образом, генерацию понятий ФАП можно свести к задаче преобразования D-системы в С-систему. Следовательно, АК может успешно применяться при построении решеток понятий и прикладных систем искусственного интеллекта, использующих этот аппарат.

5.3.4. Поисковые системы: математическая модель понятия "вопрос"

Вобщем случае вопрос содержит три компоненты [Гетманова, 1995]:

1)искомое знание; 2) то, что известно; 3) требование или намерение получить искомое знание (в естественном языке это выражается вопросительными местоимениями – кто, где, когда и т.д. – и знаком вопроса или интонацией в устной речи, а в инструментальных средствах вопросно-ответных систем в виде определенных команд). Другие необходимые компоненты упоминаются реже. К ним относятся: 4) предполагаемый источник искомых знаний и 5) точное указание на категории (множества, атрибуты), к которым относятся искомое знание и то, что известно. В вопросах на естественном языке эта компонента может отсутствовать, так как предполагается, что собеседник сам может ее без труда восстановить.

Различают несколько видов вопросов. В общем случае их можно разделить на две категории [Гетманова, 1995]: 1) уточняющие вопросы или ли-вопросы (Верно ли, что жирафы живут в Африке?) и 2) восполняющие вопросы, т.е. вопросы, начинающиеся с вопросительных местоимений "кто", "где", "когда" и т.д. Д.А. Поспелов дополняет эту классификацию еще тремя типами вопросов:

3)ПОЧЕМУ-вопросы; 4) ЗАЧЕМ-вопросы и 5) КАК-вопросы [Поспелов, 1989].

Кроме того, вопросы подразделяются на простые и сложные. В сложных

210

уточняющих вопросах то, что неизвестно, имеет вид условных предложений (например, "Правда ли, что если A то B?"). Для восполняющих вопросов то, что известно, может быть выражено в виде сложных предложений – такие вопросы можно разложить на множество простых вопросов.

Сложности начинаются при переходе от общения между людьми (здесь тоже есть свои трудности, например, найти "знатока" или правильно сформулировать вопрос, но на этих проблемах мы останавливаться не будем) к инструментальным вопросно-ответным системам (или подсистемам). Здесь основных трудности две:

1)разработать язык запросов, с помощью которого можно формулировать вопросы так, чтобы легко было перевести его с естественного языка на язык машинных команд;

2)структурировать многообразные источники информации таким образом, чтобы их можно было обрабатывать, используя язык запросов. В этом направлении создано немало оригинальных разработок (реляционная алгебра, языки баз данных, Semantic Web, различные поисковые системы, реляционноситуационный анализ текстов [Осипов, 2009]).

Существуют разнообразные поисковые или вопросно-ответные системы, основанные на следующих основных принципах:

1)информация, к которой поступают запросы, преобразуется таким образом, чтобы она была представлена в виде определенных структур. Речь идет, в основном, о таких структурах, как отношения (в частности, таблицы) или элементы определенных отношений, графы, сети (семантические, по сочетаемости и т.д.), частично упорядоченные множества (в частности, решетки), правила и т.д. Например, предложения естественного языка часто преобразуются в элементы определенных отношений. Так предложение "Студент Петров сдал экзамен по математике на отлично" может быть преобразовано в элемент отношения РЕЗУЛЬТАТЫ ЭКЗАМЕНОВ (Фамилия студента, Предмет, Оценка) и представлено в виде кортежа (Петров, математика, отлично).

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

211

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

Рассмотрим сначала восполняющие вопросы. Пусть задан произвольный АК-объект Q[XYZ] = [{a} {b} *]. В данном случае Q есть C-кортеж, в котором значения атрибутов X и Y определены, а атрибут Z может принимать любое значение в пределах своего домена. Этот АК-объект нетрудно сформулировать как вопрос: "Каково значение атрибута Z, если атрибуты X и Y заданы?". Такой вопрос имеет смысл, если в качестве исходной информации определено отношение R[…XYZ…]. Тогда ответ на вопрос можно найти, выполнив операцию R[…XYZ…] G Q[XYZ]. Может оказаться, что будет получен результат, в котором атрибут Z имеет более одного значения и, тем не менее, ответ на вопрос может быть получен. Усложнять восполняющие вопросы допустимо в следующих двух направлениях.

1) Вопрос может иметь более сложную форму. Например, требуется определить произвольное значение Z при заданных значениях X и Y или значение того же атрибута в диапазоне D при других значениях атрибутов X и Y. Пример такого вопроса можно представить как C-систему

Ответ на вопрос также находится с помощью обобщенного пересечения:

R[…XYZ…] G Q1[XYZ].

2) В исходной информации отсутствует отношение, в котором содержатся все атрибуты вопроса. В этом случае необходимо найти объекты, схемы отношений которых содержат подмножества атрибутов, содержащихся в схеме отношения вопроса, и вычислить их соединение. Приведем пример. Пусть в системе содержатся два отношения P[XYZ] и R[YVW], и требуется ответить на

212

вопрос, каковы значения атрибутов X и V, если Z = a. В заданных условиях сам вопрос на языке АК выражается как C-кортеж Q2[XVZ] = [ {a}], а отношение, содержащее все атрибуты вопроса, можно найти соединением отношений P[XYZ] и R[YVW]. В итоге для получения ответа на вопрос требуется выполнить следующие операции:

(P[XYZ] R[YVW]) G Q2[XVZ].

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

P[XYZ] G R[YVW] G Q2[XVZ].

Учитывая ассоциативность и коммутативность операции G, можно выбрать порядок вычислений, обеспечивающий существенное сокращение трудоемкости.

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

Рассмотрим уточняющие вопросы. В некоторых случаях они сводятся к восполняющим вопросам, например, когда речь идет о существовании какогото определенного факта. Однако в большинстве случаев уточняющие вопросы имеют более сложную структуру. Пусть в результате поиска по атрибутам, содержащимся в вопросе, получено некоторое отношение R, которое является подходящей для данного вопроса базой знаний, а Q – искомое знание в уточняющем вопросе типа "Верно ли, что Q?". Проанализируем два случая.

1)Уточняющий вопрос о существовании, содержащий в искомом знании более одного факта. В этом случае Q представлено АК-объектом, содержащим некоторое множество элементарных кортежей. Тогда ответ может быть получен после проверки обобщенного включения Q G R.

2)В качестве искомого знания в уточняющем вопросе содержится определенная закономерность, выразимая в виде АК-объекта Q. Тогда она должна соблюдаться для всех элементарных кортежей отношения R. Значит, положительный ответ на вопрос может быть получен, если при проверке подтвердится соотношение R G Q.

213

Заключение

Приятны завершенные труды.

Гомер.

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

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

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

Помимо логического вывода, АК служит для формализации и решения

214