ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 1, с. 118-127
= ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ
УДК 658.012011.56
ВЕРОЯТНОСТНАЯ ЛОГИКА НА ОСНОВЕ АЛГЕБРЫ КОРТЕЖЕЙ
© 2007 г. Б. А. Кулик
Санкт-Петербург, Институт проблем машиноведения РАН Поступила в редакцию 10.01.06 г.
Известное в искусственном интеллекте понятие "вероятностная логика" нуждается в более строгом обосновании. Предлагается новый подход к построению вероятностной логики на основе разработанной автором алгебры кортежей. Дается краткое введение в алгебру кортежей и обобщаются ее свойства, обеспечивающие эффективное распараллеливание при машинной реализации алгоритмов решения задач логического анализа систем. Рассматриваются методы решения прямой и обратной задач вероятностного моделирования логических систем.
Введение. Алгебра кортежей (АК), в основе которой лежат известные свойства декартовых произведений [1], была разработана для решения некоторых задач искусственного интеллекта, в частности, для моделирования логических систем и уменьшения трудоемкости алгоритмов логического вывода [2, 3]. Основы АК и возможности ее использования при вероятностном моделировании изложены в [4-6]. Дальнейшие исследования этой системы показали, что класс решаемых на ее основе задач может быть существенно расширен. Кроме того, структуры АК сравнительно легко программируются и обладают естественным параллелизмом, поэтому их применение в программно-аппаратном обеспечении логического и логико-вероятностного анализа систем позволяет существенно уменьшить расходы на разработку программ и требуемые вычислительные ресурсы.
В статье дается краткое введение в АК с учетом корректировки некоторых ранее введенных терминов, а также рассматриваются ее возможности при решении обратной задачи логико-вероятностного анализа, т.е. восстановления вероятностных распределений простых событий на основе данных о вероятностях сложных событий. Подобные задачи были поставлены в рамках вероятностной логики [7-9].
1. Основные понятия и структуры АК. АК содержит ряд определений и более 30 теорем, с помощью которых решаются следующие задачи:
1) обосновывается ее изоморфизм с такими системами, как теория многоместных отношений и исчисление высказываний и предикатов;
2) осуществляется погружение этой системы в вероятностное пространство;
3) разрабатывается алгоритмическая база для решения разнообразных задач логического анализа систем (логического вывода, поиска кор-
ректных гипотез и "скрытых аксиом", вероятностного анализа и т.д.).
Чтобы не обращаться к первоисточникам [2-6], здесь вкратце приведены основные понятия и соотношения АК, необходимые для понимания вероятностных соотношений. Кроме того, написание этого раздела вызвано некоторым, на взгляд автора, более удачным, изменением в прежней терминологии.
В основе АК лежит понятие гибкого универсума. Пусть задана совокупность различных множеств, называемых сортами. Каждому сорту приписывается некоторое множество имен (атрибутов) (в предыдущих публикациях по АК вместо этого термина использовался не совсем удачный термин "координата"). Доменом каждого атрибута является множество, равное соответствующему сорту. В математической логике доменам атрибутов отвечают области определения переменных. Гибкий универсум состоит из совокупности частных универсумов - декартовых произведений доменов для заданной последовательности атрибутов. Последовательность атрибутов, определяющих данный частный универсум, называется схемой отношения.
АК содержит всего 5 структур (АК-объек-тов): элементарный кортеж; С-кортеж; С-систе-ма; ^-кортеж и ^-система. АК-объекты, сформированные в одном и том же частном универсуме, называются однотипными.
Предположим, что задан частный универсум в виде декартова произведения = Х1 х Х2 х ... х Хп произвольных множеств. Наглядно 5 можно представить как пространство признаков с атрибутами X. Домены этих атрибутов соответствуют шкалам признаков. Тогда в пространстве 5 можно сформировать следующие подструктуры:
1) проекции - подпространства, в которых используются только отдельные атрибуты из множества атрибутов, образующих 5;
2) декартовы произведения в заданной схеме отношения: образующими компонентами этих декартовых произведений служат некоторые подмножества множеств X, представленных в заданной схеме отношения.
Рассмотрим примеры этих подструктур. Пусть 5 = Xх У х 2, гдеX = {а, Ь, с, й}, У = {/, g, к}, 2 = {а, Ь, с}. Проекциями данного пространства могут быть декартовы произведения X х У, X х 2 и т.д. или одиночные множества, например X. Для простоты будем считать, что в этой системе каждому сорту соответствует единственный атрибут.
В пределах пространства 5 или какой-либо его проекции можно задать соответствующие подструктуры в виде декартовых произведений. Например, в 5 в качестве такой подструктуры выступает декартово произведение R[XУZ] = {Ь, й} х х {/ к} х {а, Ь}. Здесь выражение [XУZ] является схемой отношения. Нетрудно убедиться, что R с 5 (свойство декартовых произведений). Аналогично некоторое подмножество элементарных кортежей проекции У х 2 представимо как декартово произведение Q[УZ] = {/ g} х {а, с}. Декартовы произведения отражают множества элементарных кортежей - эти множества при необходимости можно перечислить, хотя при выполнении операций со структурами АК это необязательно.
Элементарный кортеж - элемент декартова произведения или его проекции, т.е. последовательность из элементов, каждый из которых принадлежит домену соответствующего атрибута. Например, декартово произведение Q[УZ] = {/ g} х х {а, с} содержит следующее множество элементарных кортежей: {(/, а), (/, с), а), с)}.
С-кортежем называется кортеж, заданный в полном пространстве или в какой-либо его проекции, с компонентами, образованными подмножествами соответствующих доменов атрибутов. С-кортеж интерпретируется как декартово произведение этих компонент, т.е. как некоторое множество элементарных кортежей. Для обозначения С-кортежей используются прямые скобки. Например, приведенные выше отношения R и Q можно представить как С-кортежи: R[XУZ] = [{Ь, й} {/, к} {а, Ь}]; Q[УZ] = [{/, g} {а, с}].
С-кортеж, у которого имеется хотя бы одна пустая компонента, является пустым. В АК, если речь идет о моделях исчисления высказываний или предикатов, это утверждение принято в качестве аксиомы, для которой имеется соответствующая интерпретация, основанная на свойствах декартовых произведений.
Чтобы обобщить операции, которые часто приходится выполнять со структурами с разными схемами отношений, вводятся фиктивные компоненты. Они бывают двух видов, одна из них используется в С-кортежах и обозначается "*". Другую фиктивную компоненту (0), участвующую в
^-кортежах, рассмотрим позднее. Фиктивные компоненты "*" обозначают множества, равные доменам соответствующих атрибутов, их можно вставить в определенный С-кортеж вместо отсутствующих атрибутов и тем самым ввести в него новые атрибуты. Например, С-кортеж Q[УZ] = [{/ g} {а, с}] записываются в схеме отношения [XYZ] в виде С-кортежа [*{ /, g} {а, с}], используя фиктивную компоненту. Поскольку фиктивная компонента в Q отвечает атрибуту X, то справедливо равенство [*{/, g} {а, с}] = [{а, Ь, с, й} {/, g} {а, с}].
Пересечение однотипных С-кортежей осуществляется покомпонентно: результатом этой операции является С-кортеж, содержащий пересечения компонент исходных С-кортежей, относящихся к одному и тому же атрибуту, например [{Ь, й} {/, к} {а, Ь}] п [* {/ g} {а, с}] = [{Ь, й} {/} {а}].
Результатом пересечения С-кортежей может оказаться пустое множество (пустой С-кортеж) [{Ь, й} {/ к}, {а, Ь}] п [*^} {а, с}] = 0, так как пересечение вторых компонент этих С-кортежей образует пустое множество.
Многие отношения, заданные как подмножества декартова произведения, не всегда удается отобразить с помощью единственного С-кортежа. Поэтому целесообразно ввести универсальную структуру, полученную объединением С-кортежей. С-системой называется структура, являющаяся объединением произвольного числа однотипных С-кортежей. С-системы так же, как и С-кортежи, ограничиваются прямыми скобками. Например, для заданного выше пространства 5 можно определить некоторое отношение Р как С-систему
Р[ XУZ] =
{а, й} * {Ь, с} { Ь, й} {/, к } {а, с } {Ь, с} {g} {Ь }_
Проверка включения одного С-кортежа (Ст) в другой (Сп) осуществляется покомпонентно: Ст = Сп тогда и только тогда, когда все компоненты Ст включены в соответствующие компоненты Сп. На основе свойств декартовых произведений можно определить условия, при которых объединение двух С-кортежей Ст и Сп преобразуется в один С-кортеж. Этих условий два:
1) если Ст с Сп, то Ст и Сп = Сп';
2) если Ст и Сп отличаются только в одной (7 -й) компоненте, то Ст и Сп выражается как один С-кортеж, сохраняющий неизменными все компоненты за исключением 7-й, которая становится равной объединению соответствующих компонент из
Ст и Сп.
Зная, как получить пересечение С-кортежей, можно сформулировать алгоритм для отыскания пересечения С-кортежа с С-системой и С-систе-мы с С-системой. Для этого нужно представить
С-кортежи как обычные множества, элементами которых являются однотипные элементарные кортежи. Тогда С-система, содержащая С-кортежи А, В, ..., Ь, - объединение этих множеств. Исходя из этого, используя законы алгебры множеств, в частности законы дистрибутивности, нетрудно сформулировать алгоритмы вычисления пересечений соответствующих структур.
Алгоритм 1. Расчет пересечения С-корте-жа Р с С-системой Q:
1) вычислить пересечения С-кортежа Р с каждым С-кортежем из Q;
2) из полученных результатов исключить пустые С-кортежи;
3) из оставшихся кортежей сформировать С-сис-тему;
4) конец алгоритма.
Алгоритм 2. Оценка пересечения С-систе-мы Р с С-системой Q;
1) вычислить пересечения каждого С-кортежа из Р с каждым С-кортежем из Q;
2) из полученных результатом исключить пустые С-кортежи;
3) из оставшихся кортежей сформировать С-сис-тему;
4) конец алгоритма.
В качестве примера рассмотрим пересечение двух С-систем, заданных на определенном ранее пространстве 5 (это означает, что символ "*" на вто
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.