1 Институт проблем машиноведения РАН (Санкт-Петербург) АЛГЕБРАИЧЕСКИЙ ПОДХОД К ИНТЕЛЛЕКТУАЛЬНОЙ ОБРАБОТКЕ ДАННЫХ И ЗНАНИЙ д. ф.-м. н. Кулик Борис Александрович, к. т. н. Зуенко Александр Анатольевич, д. т. н., проф. Фридман Александр Яковлевич Институт информатики и математического моделирования технологических процессов КНЦ РАН (Апатиты) работа выполнена в рамках исследований по гранту РФФИ , программе фундаментальных научных исследований Отделения нанотехнологий и информационных технологий РАН (проект 2.3 в рамках текущей Программы) и Программе 15 Президиума РАН (проект 4.3 "Интеллектуальные базы данных")

2 План доклада 1. Логический анализ: алгебраический подход и теория формальных систем (ТФС) 2. Алгебра кортежей (АК): основные определения 3. Представление в АК основных видов данных и знаний 4. Новые возможности логического анализа в АК 5 Семантический анализ информации 6. Методы снижения трудоемкости в АК 7. Метрические аспекты АК 8. Выводы 2

Моделирование логики рассуждений (методы логического анализа) Силлогистика Аристотеля, до начала XIX века Алгебраический подход, cередина XIX века (Буль, де Морган, Венн, Жергонн, и др.) Теория формальных систем, конец XIX – начало XX века (Гильберт, Витгенштейн, Рассел и др.) Эра компьютеров, совмещение процедурного и декларативного подходов в инструментальных средствах ИИ

Столкновение подходов к логическому анализу (эра компьютерной техники) Д. Гильберт, конец XIX и начало XX века Теория формальных систем Алгебраический подход Дж. Буль, середина XIX века

5 Эволюция методов обработки в интеллектуальных системах Теория формальных системАлгебраический подход Базы знанийБазы данных Реляционные отношенияПредикаты, семантические сети и др. представления отношений + = Общая теория многоместных отношений (АК) Обоснованные методы логического вывода Анализ матричных свойств обрабатываемых объектов

6 Сравнение формального и алгебраического подходов Формальный подход 1.Алфавит. 2.Синтаксические правила. 3.Аксиомы. 4.Правила вывода. Алгебраический подход 1.Носитель. 2.Совокупность операций и отношений 3.Основные законы, связывающие операции и отношения Известны математические объекты, которые можно представить и как формальные и как алгебраические системы, например, булева система – булева алгебра; кольцо; решетка и т.д.

7 Сравнительная характеристика подходов ТФСАлгебраическийКритерии 1. Наличие унифицированного языка представления данных и знаний ?+ 2. Наличие развитых методов логического анализа при реализации БЗ Пригодность для организации систем управления БД + 4. Решение проблемы экспоненциальной катастрофы Удобство анализа параметров исследуемой системы - + -

8 План доклада 1. Логический анализ: алгебраический подход и теория формальных систем (ТФС) 2. Алгебра кортежей (АК): основные определения 3. Представление в АК основных видов данных и знаний 4. Новые возможности логического анализа в АК 5 Семантический анализ информации 6. Методы снижения трудоемкости в АК 7. Метрические аспекты АК 8. Выводы 8

9 Классическое определение отношения (множество элементарных кортежей) = XY мужмашина мужчасы мужбрюки мужгитара женакольцо женасумка женасапоги

10 = Отношения в алгебре кортежей (компактное представление отношений) { муж }{} машина,часы,брюки,гитара × = XY мужмашина мужчасы мужбрюки мужгитара женакольцо женасумка женасапоги жена }{ × кольцо,сумка,сапоги {}

11 Определение алгебры кортежей Алгебра кортежей (АК) – это алгебраическая система. Носитель АК: произвольная совокупность многоместных отношений, определенных в одном гибком универсуме и выраженных в специфических структурах: – C кортеж; – C-система; – D-кортеж; – D система. называемых АК-объектами. Каждый АК-объект можно интерпретировать как множество элементарных кортежей. Операции АК: – операции алгебры множеств (,, \ ) и дополнение ( ) – операции с атрибутами: переименование атрибута; перестановка атрибутов; добавление нового фиктивного атрибута (+Atr); элиминация атрибута ( Atr). Отношения алгебры множеств:,,. Производные операции: соединение ( ) и композиция ( ) отношений Обобщенные операции и отношения ( G, G, \ G, G, G )

12 Первая особенность АК: компактное представление отношений (С-кортеж) C-кортеж R[XY...Z] = [A B... C], где A, B,..., C – компоненты C-кортежа; A X, B Y,..., C Z, т.е. подмножества доменов соответствующих атрибутов. Интерпретация – декартово произведение множеств: R[XY...Z] = [A B... C] = A B... C. Пример: XYZ acb adb afb ccb cdb cfb R [XY...Z] = [{a,c} {c,d,f} {b}] = {a,c} × {c,d,f} × {b} =

13 Свойства C-кортежей C-кортеж интерпретируется как декартово произведение компонент. В математической логике C-кортежу соответствует конъюнкция: P(x) Q(y) R(z) Изображение С-кортежа: Пересечение C-кортежей: [A B... C] [A 1 B 1... C 1 ] = [A A 1 B B 1... C C 1 ]. Проверка включения: [A B... C] [A 1 B 1... C 1 ], если и только если A A 1, B B 1, …, C C 1.

14 C-система -- это объединение C-кортежей с одинаковой схемой отношения. Пример: В математической логике C-кортежу [P Q R ] соответствует конъюнкт P(x) Q(y) R(z), где P(x), Q(y), R(z) – некоторые предикаты, а P, Q, R – множества их выполняющих подстановок. C-системе можно сопоставить ДНФ: (P 1 (x) Q 1 (y) R 1 (z)) (P 2 (x) Q 2 (y) R 2 (z)). Первая особенность АК: компактное представление отношений (С-система)

15 Изображение C-системы

16 1.Полная компонента – равна домену соответствующего атрибута. Используется в C кортежах и C-системах. 2.Пустая компонента - используется в D-кортежах и D-системах Например, для X = {a, b, c, d}, Y = {f, g, h}, Z={a, b, c}: Q[XYZ] = [ {f, g} {a, c}] = [{a, b, c, d} {f, g} {a, c}] - здесь – это множество, равное домену атрибута X. Если T = [{b, d} * {a, b}], то = ]{a, c} {c}[. Пусть A – произвольная компонента атрибута X, а - его полная компонента. Тогда А = A; A = ; = ; =. Первая особенность АК: компактное представление отношений (фиктивные компоненты)

17 Дополнение C-кортежа: D-кортеж – сокращенное обозначение диагональной C системы. В математической логике D-кортежу ]P Q R[ в схеме отношения [XYZ] соответствует дизъюнкция: P(x) Q(y) R(z). Дополнением C-кортежа [ {,,,, } {,, } ] является D-кортеж ] {,, } {, } [ (на схеме не закрашен) или C-система Вторая особенность АК: операция дополнения отношений (D-кортеж)

18 R =, В математической логике D-системе соответствует КНФ. В частности, дополнением C-кортежа Q[XYZ] = [A C] является D-кортеж [XYZ] = ] [ Вторая особенность АК: операция дополнения отношений (D-система) Дополнение C-системы ( ) - это пересечение D-кортежей с идентичными схемами отношений. На рисунке C-система R закрашена, а D-система не закрашена.

19 Операции с атрибутами 1.Переименование атрибутов (только для атрибутов одного сорта). 2.Перестановка атрибутов – эквивалентное преобразование АК-объекта). 3.Добавление фиктивного атрибута (+Atr) – равносильное по смыслу преобразование при условии, что добавляемый атрибут не содержится в схеме отношения данного АК-объекта. Соответствует правилу обобщения исчисления предикатов: из формулы A выводимо x(A) (при условии, что x не является свободной переменной в A ) 4. Элиминация атрибута (– Atr) – интерпретирует операции навешивания кванторов в исчислении предикатов. Пусть T C – С-кортеж или C-система, а T D – D-кортеж или D-система, содержащие атрибут X. Тогда – X(T C ) равносильно x(T C ); – X(T D ) равносильно x(T D ). Третья особенность АК: работа с отношениями, заданными в разных декартовых произведениях

20 Перестановка атрибутов Добавление фиктивного атрибута Элиминация атрибута Третья особенность АК: работа с отношениями, заданными в разных декартовых произведениях (примеры операций с атрибутами)

21 Третья особенность АК: работа с отношениями, заданными в разных декартовых произведениях (некоторые производные операции ) Пусть заданы две структуры R 1 [V] и R 2 [W]. Здесь V и W являются множествами атрибутов и V W. Эти множества можно разложить на непересекающиеся подмножества X, Y, Z с помощью следующих операций: X = W\V; Y = W V; Z = V\W. Тогда V = Y Z и W = X Y. С учетом этого данные отношения можно переписать так: R 1 [V] = R 1 [YZ] и R 2 [W] = R 2 [XY]. Операция соединения: R 1 [YZ] R 2 [XY] = +X(R 1 ) +Z(R 2 ) = x(R 1 ) z(R 2 ). Операция композиции: R 1 [YZ] R 2 [XY] = – Y(+X(R 1 ) +Z(R 2 )) = – Y(R 1 R 2 ) = = y( x(R 1 ) z(R 2 )). Q[YZ] = P[XY] = Схемы отношений у P и Q разные, но их можно привести к одной Q 1 [XYZ] = x(Q[YZ]) = Вычислив их пересечение, получим соединение отношений P 1 [XYZ] = z(P[XY]) = P Q =

22 Назовем операции алгебры множеств с АК объектами с предварительным добавлением недостающих фиктивных атрибутов обобщенными операциями и отношениями алгебры множеств в АК и обозначим их соответственно,,,, и т.д. Примером обобщенной операции является соединение отношений P[XY] Q[YZ] = +Z(P[XY]) +X(Q[YZ]) то же самое, что P[XY] G Q[YZ]. Введение обобщенных операций и отношений позволяет определить алгебру отношений с произвольным составом атрибутов как алгебру множеств. Треть я особенность АК: работа с отношениями, заданными в разных декартовых произведениях (обобщенные операции и отношения) XY ab ad G XZ ak al = [{a},{b,d}] G [{a},{k,l}] X YX Z = [{a},{b,d},*] X Y Z [{a},*,{k,l}] = X Y Z = [{a},{b,d},{k,l}] X Y Z = XYZ abk abl adk adl

23 Гибкий универсум Пусть X 1, X 2, …, X n – множество атрибутов. Тогда X 1 X 2 … X n – пространство атрибутов или универсум; [X i X j … X k ] (i, j, …, k 1 ÷ n) – схема определенного отношения; X i X j … X k – частный универсум; Гибкий универсум – это произвольная совокупность частных универсумов для системы, определенной на пространстве X 1 X 2 … X n. Однотипные АК-объекты - разные АК-объекты с одной и той же схемой отношения. Интерпретация Частный универсум X i X j … X k в исчислении предикатов соответствует общезначимой формуле F(x i, x j, …, x k ), где x i, x j, …, x k – переменные, областями значений которых являются домены атрибутов X i X j … X k. Таким образом, совокупность частных универсумов в АК соответствует классу общезначимых формул в исчислении предикатов.

24 Основные теоремы АК (здесь нумерация теорем в соответствии с представляемой ниже книгой) Теорема 2.1. Алгебра кортежей для однотипных АК-объектов изоморфна алгебре множеств Пусть заданы однотипные C-кортежи P = [P 1 P 2 … P n ] и Q = [Q 1 Q 2 … Q n ]. Теорема 2.2. P Q = [P 1 Q 1 P 2 Q 2 … P n Q n ]. Примеры: [{b, d} {f, h} {a, b}] [ {f, g} {a, c}] = [{b, d} {f} {a}]; [{b, d} {f, h} {a, b}] [ {g} {a, c}] = [{b, d} {a}] =. Теорема 2.3. P Q, если и только если P i Q i для всех i = 1, 2, …, n. Теорема 2.4. P Q [P 1 Q 1 P 2 Q 2 … P n Q n ], причем равенство возможно лишь в двух случаях: P Q или Q P; P i = Q i для всех соответствующих пар компонент, за исключением одной пары. Теорема 2.7. Для произвольного C-кортежа P = [P 1 P 2 … P n ] его дополнение равно D-кортежу = ] … [. Часть теорем АК (всего 30 теорем) предусматривают выполнение операций алгебры множеств с однотипными АК-объектами. Для работы с АК-объектами, имеющими разные схемы отношений, вводятся операции с атрибутами.

25 План доклада 1. Логический анализ: алгебраический подход и теория формальных систем (ТФС) 2. Алгебра кортежей (АК): основные определения 3. Представление в АК основных видов данных и знаний 4. Новые возможности логического анализа в АК 5 Семантический анализ информации 6. Методы снижения трудоемкости в АК 7. Метрические аспекты АК 8. Выводы 25

26 Моделирование графов Пример вычисления степени графа G 2 [XY] = G [XY] G [XY] = Y(G[XY] G[YZ]) : Сначала вычисляем соединение графа с собой: = Затем элиминируем атрибут Y: G 2 = Транзитивное замыкание графа G, содержащего n вершин, можно построить с помощью следующей последовательности операций: G + = G G 2 G 3 … G k, где k n. … G[XY] =

27 Семантические сети Исходная сеть Правило и факты Результат R 1 [XY] = R 2 [XY] = R 3 [XY] = [{K} {L}]; R 4 [XY] = [{A} {A}]. – Левая часть правила: (R 1 [XY] [{D} ]) (R 2 [YZ] [ {K}]) = = [{D} {F, G, H} {K}]. – Правая часть правила: [{F, G, H} {M}].

28 Экспертные системы Базы знаний экспертных систем (ЭС) содержат модели и правила. Известно четыре типа моделей: логические модели, предикаты, семантические сети и фреймы. Рассмотрим предикаты и правила. Предикаты по сути являются отношениями или элементами отношений. Например, набор предикатов ЭС isa(a 1, S 1 ); isa(a 2, S 1 ); isa(a 3, S 1 ); isa(a 4, S 2 ); prop(S 1, c 1, d 1 ); prop(S 1, c 2, d 2 ); prop(S 2, c 1, d 3 ). является представлением двух отношений: бинарного isa и трехместного prop. В структурах АК предикаты можно выразить как C-системы: isa[XY] = ; prop[YZV] = Пусть задано следующее правило вывода: ЕСЛИ isa[XY] И prop[YZV] ТО property[XZV] и факты, X = a 1 и V = d2, тогда мы можем выразить их в виде запроса Q[XV] = [{a 1 } {d 2 }]. Алгоритм реализации правила с учетом фактов: isa[XY] G prop[YZV] G Q[XV].

29 АК и логические исчисления (структуры) Алгебра кортежейИсчисление предикатов элементарный кортежвыполняющая подстановка логической формулы C-кортежКонъюнкция одноместных предикатов D-кортежДизъюнкция одноместных предикатов C-системаДизъюнктивная нормальная форма (ДНФ) D-системаКонъюнктивная нормальная форма (КНФ) пустой АК-объекттождественно ложная формула АК-объект, равный частному универсуму тождественно истинная формула (тавтология) непустой АК-объектвыполнимая формула

30 АК и логические исчисления (операции) Алгебра кортежейИсчисление предикатов +Y(R) для всех АК-объектов R[X 1 X 2 … X n ] +Y(R) = y(R) –X(R) для C-систем R[…X…] (без пустых компонент в X) x(P) –X(R) для D-систем R[…X…] (без полных компонент в X) x(P) обобщенное пересечение G операция конъюнкции обобщенное объединение G операция дизъюнкции обобщенное включение одного АК объекта в другой (A G B) отношение выводимости (с учетом теоремы дедукции A B)

31 План доклада 1. Логический анализ: алгебраический подход и теория формальных систем (ТФС) 2. Алгебра кортежей (АК): основные определения 3. Представление в АК основных видов данных и знаний 4. Новые возможности логического анализа в АК a) проверка правильности следствия b) генерация возможных следствий с) поиск абдуктивных заключений 5 Семантический анализ информации 6. Методы снижения трудоемкости в АК 7. Метрические аспекты АК 8. Выводы 31

32 Новый подход к логическому выводу (методы АК) Существующие системы логического вывода: исчисления гильбертовского типа (Д. Гильберт и В. Аккерман) натуральное исчисление (Г. Генцен) принцип резолюции (М. Девис и Х. Патнем ) Теорема 1. Пусть даны формулы F 1,..., F n и формула G. Тогда G есть логическое следствие F 1,..., F n тогда и только тогда, когда формула ((F 1... F n ) G) общезначима. Теорема 2. Пусть даны формулы F 1,..., F n и формула G. Тогда G есть логическое следствие F 1,..., F n тогда и только тогда, когда формула (F 1... F n G) противоречива. Логический вывод в АК: Метод 1. Пусть даны АК-объекты F 1,..., F n и G. Тогда G есть следствие F 1,..., F n тогда и только тогда, когда (F 1 G... G F n ) и (F 1 G... G F n ) G G. Метод 2. Пусть даны АК-объекты F 1,..., F n и G. Тогда G есть следствие F 1,..., F n тогда и только тогда, когда (F 1 G... G F n ) и F 1 G... G F n G =.

33 Новый подход к логическому выводу (интерпретация логического вывода ) Теорема 4.1. Если для логических формул A и B имеется интерпретация в виде множеств S A и S B, то общезначимость импликации A B равносильна выполнению отношения S A S B. Семантика следствия Предлагаемый подход позволяет по новому осмыслить суть логического следования в классической логике. Известно, что справедливость отношения A B означает, что B является необходимым условием или свойством A. Из соотношения (1) ясно, что логическое следствие является корректным не только потому, что получено на основе правил вывода, смысл которых не всегда понятен, но еще и потому, что является необходимым условием существования антецедента.

34 Новый подход к логическому выводу (типы задач) Пусть задана система аксиом (посылок) A 1, A 2, …, A n и возможное следствие B. Два типа задач: 1) Задача проверки правильности следствия. Процедура доказательства производится как проверка правильности обобщенного включения (A 1 G … G A n ) G B. 2) Задача вывода следствий с учетом ограничений. Для решения этой задачи сначала вычисляется АК-объект A = A 1 G … G A n, после чего производится выбор таких B i, для которых соблюдается A G B i. К ограничениям относятся состав и возможное число атрибутов в следствии Для вывода возможных следствий в АК используется следующий алгоритм 1.Преобразовать АК-объект A = A 1 G … G A n в C-систему. 2.Выбрать из A некоторую совокупность неполных проекций (для любой проекции P i (A) справедливо A G P i (A) ). 3.Сформировать с учетом ограничений проекции, содержащие хотя бы одну неполную проекцию. 4.Для АК-объектов, полученных на предыдущих шагах, построить покрывающие их АК-объекты. Любой АК-объект, полученный на шагах 1-4, является следствием.

35 Новый подход к логическому выводу (проверка правильности следствия: пример) Задача: Проверить корректность правила дилеммы Решение: Верхняя часть правила методами АК преобразуется в C-систему Up[ABC] =, нижняя часть правила равна C-кортежу Down[C] = [{1}] или после добавления фиктивных атрибутов Down[ABC] = [ * * {1}] Проверка показывает, что Up[ABC] G Down[C].

36 Новый подход к логическому выводу (вывод следствий: пример) Задача: Вывести из заданной системы посылок все следствия с учетом ограничений на состав переменных Решение: Система посылок представима в виде С-системы Up[ABC] =, Здесь полными являются только проекции: [X A ] и [X B ], так как содержат все значения атрибутов. Ответ: Up[С] = Up[AC] = Up[BC]= С, Up[AB] = = A B

37 Задача о преступлении Папа Карло (B) Карабас-Барабас (A) Кот Базилио (C) Карабас-Барабас: Я совершил это, Папа Карло не виноват Папа Карло: Карабас-Барабас не виноват, Преступление совершил Кот Базилио Кот Базилио : Я не виноват, виноват Карабас-Барабас Правду говорит только один, остальные лгут. Кто преступник? Карабас-Барабас: P1[ABC] = P 1 1 P 1 2 = [{1} * *] [* {0} *] = [{1} {0} *] ; Папа Карло: P2[ABC] = P 2 1 P 2 2 = [{0} * *] [* * {1}] = [{0} * {1}] ; Кот Базилио: P3[ABC] = P 3 1 P 3 2 = [* * {0}] [{1} * *] = [{1} * {0}]. На естественном языке : На языке АК : Гипотезы : 1) Карабас-Барабас – честный ( P1 ) 2) Папа Карло – честный ( P2 ) 3) Кот Базилио – честный ( P3 )

38 Задача о преступлении Гипотеза 1 ( Карабас-Барабас – честный) : Гипотеза 2 ( Папа Карло – честный) : Гипотеза 3 ( Кот Базилио – честный) : Гипотеза отвергается Виновен Кот Базилио, честный – Папа Карло, а чиновник – Карабас-Барабас. Гипотеза отвергается

39 Задача Царевна и Змей-Горыныч Подсказка 1: На второй дороге нет Змея, а третья – не приведет обратно Подсказка 2: Первая дорога не приведет обратно, а на второй - нет Змея M 1 = [ {Ц, О} {Ц, З}] M 2 = [{Ц, З} {Ц, О} ]

40 Задача Царевна и Змей-Горыныч К царевне ведет вторая дорога Гипотеза 1 ( первое утверждение верно, а второе - нет) : Гипотеза 2 ( второе утверждение верно, а первое - нет) : К царевне ведет вторая дорога

41 Задача о турнире волшебников Гарри (A)Рон (B) Гермиона (С)Драко (D) Грифиндор: Гарри – первый а Рон – второй M1[ABCD] = M11 M12 = [{1} * * *] [* {2} * *] Слизерин: Гарри – второй, а Гермиона – третья M2[ABCD]=M21 M22=[{2} * * *] [* * {3} *] Уффендуй: Гермиона - четвертая, а Драко – второй M3[ABCD] =M31 M32 =[* * {4} *] [* * * {2}] На естественном языке На языке АК Судья: В каждом заявлении одно высказывание истинное, а другое – ложное.

42 Задача о турнире волшебников С учетом замечаний судьи, посылки примут вид: M12 M11 Грифиндор: = Уффендуй: M32 M31 = [* {2} * *] = [{1} * * *] = Слизерин: M22 M21 = [* * {3} *] = [{2} * * *] = [* * * {2}] = [* * {4} *] = P1= P2= P3= P1 P2 P3= = = = Выполним пересечение посылок M12 M11 Грифиндор: = Ответ: 1-й - Гарри, 2-й - Драко, 3-я – Гермиона, 4-й – Рон.

43 К оллизии Коллизии – это ситуации, которые возникают в модифицируемых рассуждениях при вводе новых знаний (гипотез) и распознаются как нарушение некоторых формально выраженных правил или ограничений, регулирующих целостность или смысловое содержание системы. Виды коллизий в системах типа силлогистики: парадокса, когда из посылок следует суждение типа "всем A не присуще A" (A ) и, значит, объем термина A пустой; цикла, когда в системе множеств выводится соотношение A В … A, что означает эквивалентность терминов, входящих в данный цикл; неадекватности, когда следствия системы рассуждений не соответствуют бесспорным фактам или обоснованным утверждениям.

44 Коллизии в системах типа силлогистики: пример Даны посылки: 1. Все мои друзья хвастуны и не скандалисты 2. Все хвастуны не уверены в себе. 3. Все не скандалисты уверены в себе. Необходимо проанализировать посылки на наличие коллизий Из заданных посылок следует утверждение "Все мои друзья не мои друзья", показывающее, что множество моих друзей пусто (коллизия парадокса). Полученный может вывод не соответствовать действительности – коллизия неадекватности

45 Коллизии в системах типа силлогистики: решение примера

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

47 Алгоритм вывода абдуктивного заключения 1.Вычислить «остаток» R = A B ; 2.Построить промежуточный объект R i такой, чтобы соблюдалось R R i ; 3.Вычислить H i = (тогда R i далее можно обозначить как ) ; 4.Вычислить H i A и выполнить проверку на наличие коллизий; если коллизии обнаружены, то возвратиться к шагу 2, иначе конец алгоритма. A B U R B U R RiRi HiHi RiRi HiHi A Новые возможности АК: модифицируемые рассуждения

48 Новые возможности АК: пример 1 Восстановим недостающую посылку в правиле дилеммы Пусть даны 2 посылки A C и A B и следствие C. Необходимо найти недостающую посылку, чтобы следствие выводилось. Преобразуем формулы в структуры АК. A C соответствует P 1 [X A X B X C ] =. A B соответствует P 2 [X A X B X C ] =. C соответствует B[X A X B X C ] = [ * * {1}]. Используем алгоритм. 1.R = (P 1 P 2 )\B = P 1 P 2 = [{0} {1} {0}]. 2.Выберем проекцию [ X B X C ] (такого сочетания нет в посылках), получим R i [ X B X C ] = [{1} {0}]; [ X B X C ] = ]{0} {1}[, что соответствует формуле B C.

49 Новые возможности АК: пример 2 База знаний диагностики автомобиля [ Д.А. Страбыкин, Н.М. Томчук ] Если из выхлопной трубы ЧЕРНЫЙ ДЫМ, то БОГАТАЯ СМЕСЬ или РАННЕЕ ЗАЖИГАНИЕ. x 6 (x 2 x 3 ). Если СИНИЙ ДЫМ, то ПОВЫШЕННЫЙ РАСХОД МАСЛА. x 7 x 5. Если выхлопная ТРУБА ЧЕРНАЯ, то БОГАТАЯ СМЕСЬ или РАННЕЕ ЗАЖИГАНИЕ или ПОВЫШЕННЫЙ РАСХОД МАСЛА. x 1 (x 2 x 3 x 5 ) Если ПОВЫШЕННЫЙ РАСХОД МАСЛА, то ИЗНОС МАСЛОСЪЕМНЫХ КОЛПАЧКОВ или ИЗНОС ПОРШНЕВЫХ КОЛЕЦ или ИЗНОС ЦИЛИНДРОВ. x 5 (x 8 x 9 x 10 ) Если НОРМАЛЬНАЯ КОМПРЕССИЯ, то нет ИЗНОСА ПОРШНЕВЫХ КОЛЕЦ и нет ИЗНОСА ЦИЛИНДРОВ x 4 ( x 9 x 10 ) Заключение: Если НОРМАЛЬНАЯ КОМПРЕССИЯ и выхлопная ТРУБА ЧЕРНАЯ и СИНИЙ ДЫМ, то ИЗНОС ПОРШНЕВЫХ КОЛЕЦ. (x 3 x 1 x 7 ) x 9

50 Продолжение примера 2 Эту БЗ можно представить как КНФ A = которую преобразуем в D-систему Заключение выразим как D-кортеж B[X 1 X 4 X 7 X 9 ] = ]{0} {0} {0} {1}[.

51 Продолжение примера 2 Алгоритм « наращивания » R 1) оставить в качестве одну из неполных проекций; 2) выбрать в качестве любую проекцию при условии, что в ее состав входит, по крайней мере, одна неполная проекция; 3) для выбранного по предыдущим правилам АК-объекта построить покрывающий его неполный АК объект. Доказано, что данный алгоритм предусматривает все возможные случаи « наращивания » R.

52 Иллюстрация алгоритма наращивания на примере 2 В качестве примера выберем проекцию [X 1 X 9 ], которая после сокращений будет равна C-кортежу R i [X 1 X 9 ] = [{1} {0}]. Тогда можно сформировать следующие формулы для : 1) (соответствует C кортежу R i ); 2) ; 3). (формулы 2 и 3 соответствуют АК объектам, которые покрывают C-кортеж R i ) и т.д.

53 План доклада 1. Логический анализ: алгебраический подход и теория формальных систем (ТФС) 2. Алгебра кортежей (АК): основные определения 3. Представление в АК основных видов данных и знаний 4. Новые возможности логического анализа в АК 5 Семантический анализ информации 6. Методы снижения трудоемкости в АК 7. Метрические аспекты АК 8. Выводы 53

54 Логико-семантический анализ через призму АК

55 Подход к семантическому анализу на основе АК Этапы традиционного семантического анализа: 1) отбор основополагающих понятий данной предметной области, предварительная классификация отобранных понятий; 2) дальнейшая систематизация, установление иерархических связей между некоторыми понятиями; 3) установление отношений между понятиями в рамках некоторого заранее заданного списка значимых отношений, включая специфичные для данной предметной области отношения; 4) формализация информации с использованием установленных отношений в виде семантических графов, семантических сетей, онтологий и предикатов; 5) использование языка исчисления предикатов в качестве языка семантического анализа. Проблемы традиционного семантического анализа: 1)сложность совмещения логического вывода и недедуктивных (в том числе, модифицируемых) рассуждений в одной программной среде; 2)трудность выявления противоречий в знаниях и других нарушений ограничений целостности и/или смыслового содержания системы знаний (коллизий).

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

57 Семантика: «нелогичное» правило вывода В семантических сетях и экспертных системах часто используют правило вывода типа Если P 1 и P 2 и…и P n, то Q. Например, если Мать (x,y) и Родитель (y,z), то Бабушка(x,z). В АК такие правила определены с помощью формулы P 1 G P 2 G … G P n, Q По сути здесь не просто логический вывод, а создание нового отношения, смысл которого определен левой частью правила. («Бабушка – это женщина, дети которой имеют детей» или по Толковому словарю Ожегова«Мать отца или матери» -) С учетом этого нами предложено называть такого рода правила семантическими правилами.

58 Вопросы и вопросно-ответные системы Типы вопросов 1) Уточняющие вопросы или ли-вопросы: Верно ли, что жирафы живут в Африке? 2) Восполняющие вопросы: Кто …? Где …? Когда …? и т.д. 3) ПОЧЕМУ-вопросы 4) КАК-вопросы 5) ЗАЧЕМ-вопросы Гетманова А.Д. Учебник по логике. М.: "Владос", Поспелов Д. А. Моделирование рассуждений.– М.: Радио и связь, Принципы работы вопросно-ответных систем 1 ) Структурирование исходной информации и вопросов к ней. Используемые структуры: отношения (в частности, таблицы) или элементы отношений, графы, сети (семантические, по сочетаемости и т.д.), частично упорядоченные множества (в том числе решетки), правила. Все перечисленные структуры можно представить в виде отношений. 2) Формально выраженные запросы должны легко переводиться на естественный язык ; инициировать процедуру поиска с учетом многообразия структур подготовленной к обработке информации.

59 Структура вопроса Восполняющие вопросыАК: структура вопроса Ответ на вопрос Каково значение атрибута Z в отношении R[XYZ], если X = a и Y = b заданы? Q[XYZ] = [{a} {b} ]R[XYZ] G Q[XYZ] Каково значение атрибута Z в отношении R[XYZ], если X = a и Y = c, либо X = a или b, Y = e, а Z находится в диапазоне D? Q 1 [XYZ] = R[XYZ] G Q 1 [XYZ] Даны отношения P[XYZ] и R[YVW]. Каковы значения атрибутов X и V, если извесно, что Z=a? Q 2 [XVZ] = [ {a}] P[XYZ] G R[YVW] G Q 2 [XYZ] Остальные типы вопросов в стадии разработки

60 План доклада 1. Логический анализ: алгебраический подход и теория формальных систем (ТФС) 2. Алгебра кортежей (АК): основные определения 3. Представление в АК основных видов данных и знаний 4. Новые возможности логического анализа в АК 5 Семантический анализ информации 6. Методы снижения трудоемкости в АК 7. Метрические аспекты АК 8. Выводы 60

61 Трудоемкость операций в АК = {a,b,c} × {b,c} × {b,c,f} {a,b,c,d} × {a,c,d} × {b,c,d} = ??? XYZ abb abc abf acb acc acf cbb cbc cbf ccb ccc ccf dbb dbc dbf dcb dcc dcf XYZ aab aac aad acb acc acd adb adc add bab bac bad bcb bcc bcd bdb bdc bdd cab cac cad ccb ccc ccd cdb cdc cdd dab dac dad dcb dcc dcd ddb ddc ddd 1 Способ. Вычисления в элементарных кортежах число операций = = Способ. Вычисления в АК-объектах C[XYZ] D[XYZ] = = [{a,b,c} {b,c} {b,c,f}] [{a,b,c,d} {a,c,d} {b,c,d}]= =[{a,b,c} {a,b,c,d} {b,c} {a,c,d} {b,c,f} {b,c,d}]= = [{a,b,c} {c} {b,c}]. число операций = = 27

62 Вычислительная сложность наиболее трудоемких действий при реализации операций АК ДействиеC-кортежC-системаD-кортежD-система Проверка принадлежности элементарного кортежа++++ Проверка включения C- кортежа в +++ Проверка включения C- системы в +++ Проверка включения D- кортежа в +++ Проверка включения D- системы в З наком «+» помечены алгоритмы, которые являются полиномиальными. Пустые клетки соответствуют алгоритмам, сложность которых оценивается экспонентой (NP-трудные алгоритмы). Вычислительная сложность алгоритмов на структурах АК полностью соответствует вычислительной сложности алгоритмов решения типовых задач логического анализа, поскольку структуры АК полиномиально сводимы к логическим структурам.

63 Матричные свойства АК-объектов как средство ускорения логического вывода Основные определения Бесконфликтным атрибутом D-системы называется атрибут, в котором пересечение всех непустых компонент непусто. Бесконфликтным блоком D-системы называется ее вертикальный блок, содержащий только бесконфликтные атрибуты. Монотонным атрибутом D-системы называется бесконфликтный атрибут, не содержащий пустых компонент. Монотонным блоком D-системы называется бесконфликтный блок, не содержащий D-кортежей со всеми пустыми компонентами. Пример: Т[XYZ] = C =[XYZ] = [{ A } { c }]

64 Матричные свойства АК-объектов (продолжение) Новые классы КНФ Теорема 6. Если D-система Q содержит монотонный блок, то она непуста. Пусть Q =, T 11 – подматрица Q, не содержащая D-кортежей со всеми пустыми компонентами, T 21 – подматрица Q с D-кортежами, содержащими только пустые компоненты. Теорема 7. Если в D-системе Q имеется бесконфликтный блок, то Q непуста, если и только если при разложении ее в блочную матрицу непустой является D система, представленная блоком T 22. Пример: Q = =

65 Ортогонализация Используется как для сокращения трудоемкости операций, так и при анализе измеримых систем (см. ниже) В логике ортогональными называются функции вида F 1 F 2 … F n, у которых любая пара (F i, F j ) функций не имеет общих выполняющих подстановок. Ортогональная С-система – это С-система, у которой пересечение любой пары С-кортежей пусто. Основные теоремы ортогонализации для АК-объектов с произвольными компонентами Пусть Q 1, Q 2,..., Q m-1, Q m – произвольные множества. Теорема 5. D-кортеж вида ] Q 1 Q 2... Q m-1 Q m [ преобразуется в эквивалентную ортогональную C-систему. Теорема 6. Если P и Q – ортогональные C-системы, то их пересечение либо пусто, либо состоит из одного C-кортежа, либо является ортогональной C системой.

66 Возможности распараллеливания вычислений OP1OP2OP3 =

67 План доклада 1. Логический анализ: алгебраический подход и теория формальных систем (ТФС) 2. Алгебра кортежей (АК): основные определения 3. Представление в АК основных видов данных и знаний 4. Новые возможности логического анализа в АК 5 Семантический анализ информации 6. Методы снижения трудоемкости в АК 7. Метрические аспекты АК 8. Выводы 67

68 Метрические аспекты АК: квантование интервалов Аксиомы меры множеств A и B: 1) 0; 2) ( A, B) (A B) = (A) + (B) (A B). Если атрибуты С-системы (С-кортежа) содержат интервалы числовой оси, то они разбиваются на элементарные интервалы, пересечение любой пары которых либо пусто, либо имеет единственную точку сочленения. Кванты - точки и открытые интервалы такого разбиения. Точка определяется как вырожденный интервал с нулевой мерой. Кванты несовместны. Пример: E 3 = {c, d, e, f, (c, d), (d, e), (e, f)} E i =, (E i ) = Теорема 5.1. Если каждая компонента C-кортежа имеет конечную меру, то мерой C-кортежа является произведение мер его компонент. Теорема 5.2. Мера ортогональной C-системы равна сумме мер содержащихся в ней C-кортежей.

69 Метрические аспекты АК: свойства АК-объектов Для АК-объектов, погруженных в вероятностное пространство или в любое другое нормированное пространство с мерой каждого атрибута, равной 1: мера полной компоненты ( ) в C-кортежах и C-системах равна 1; мера любого частного универсума равна 1; мера любого АК-объекта есть число в интервале [0, 1]; мера пустого АК-объекта равна 0; для произвольного АК-объекта A мера его дополнения равна 1 – (A); для пары АК-объектов A и B (A G B) = (A) + (B) – (A G B); в любом АК-объекте после разбиения каждой компоненты на элементарные кванты мера компоненты есть сумма мер квантов, в ней содержащихся. В двумерном пространстве:

70 Вероятностный анализ в АК Дана схема типа «мостик» и каждый элемент X i имеет 2 состояния (0 или 1) В ЛВМ: F = (X 1 X 4 ) (X 2 X 5 ) (X 2 X 3 X 4 ) (X 1 X 3 X 5 ) Для этих формул после ортогонализации можно построить вероятностную функцию. Но если элементы имеют более двух состояний, то в этом случае ортогонализация средствами ЛВМ проблематична. В АК это намного проще. Ортогонализация этой структуры выполняется с помощью простого универсального алгоритма R 1 = Пример структуры типа «мостик», в которой элементы имеют 3 состояния: В структурах АК: R F =

71 Уравнение регрессии Если АК-объект преобразован в ортогональную С-систему, то в вероятностном пространстве его можно представить как уравнение регрессии, в котором переменными являются вероятности элементарных событий, а значением функции – вероятность события, заданного этим АК объектом. Пример 1 – система с двумя состояниями АК-объект Уравнение регрессии p 1 (1–p3)+(1–p 2 )p 3 +(1–p 1 )p 2. Пример 2 – система с тремя состояниями АК-объект Уравнение регрессии (p(a 1 ) + p(a 2 ))(1– p(b 2 ))+(1– p(a 1 ) – p(a 2 ))(p(b 1 )+ p(b 2 )).

72 Вероятностная логика В логико-вероятностных методах (ЛВМ) решается прямая задача расчета вероятности: – заданы вероятности элементарных событий в атрибутах; – необходимо вычислить вероятность события, выраженного АК-объектом (или соответствующей ему логической формулой). В вероятностной логике решается обратная задача расчета вероятности: – заданы вероятности сложных событий; – необходимо вычислить вероятности других сложных событий. При использовании АК в этом случае промежуточным этапом вычисления является вычисление вероятностей элементарных событий или некоторых сложных событий, которые в данной системе можно использовать в качестве атомов.

73 Задача 1 (Nilsson N. J. Probabilistic Logic // Artificial Intelligence, 28, 1986, pp ): Дано: p(A) = p 1 и p(A B) = p 2. Найти: оценку p(B). Решение в структурах АК: Используем универсум A B = {0, 1} 2. Тогда A = [1 ]; B = [ 1]; A B = B = ]0 1[ =. Получаем систему из двух уравнений p(A) = p 1 ; (1 – p(A)) + p(A) p(B) = p 2. Из этой системы несложно вывести p(B) = У Н. Нильсона ответ p 2 + p 1 – 1 p(B) p 2.

74 Задача 2

75 Продолжение задачи 2

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

77 Заключение Разработанная алгебра кортежей и ее методы: позволяют унифицированно обрабатывать данные и знания, представленные в виде совокупности многоместных отношений с различными схемами; ускоряют выполнение процедур логического вывода за счет: 1) удобства распараллеливания вычислений, 2) использования матричных свойств отношений, а также новых структурных и статистических классов КНФ с полиномиально распознаваемым свойством выполнимости; дают возможность по-новому организовывать процедуры логического вывода; позволяют моделировать модифицируемые рассуждения, не нарушая законов классической логики.

78 Дальнейшие направления исследований моделирование интеллектуальных динамических систем в рамках ситуационного подхода; контекстно-ориентированные системы управления базами данных и знаний; исследование дополнительных возможностей погружения структур АК в измеримые пространства; моделирование пространственно-временных рассуждений.

79 Кулик Б.А. Система логического программирования на основе алгебры кортежей // Известия РАН. Техническая. кибернетика С Кулик Б.А. Новые классы КНФ с полиномиально распознаваемым свойством выполнимости // Автоматика и телемеханика С Кулик Б.А. Представление логических систем в вероятностном пространстве на основе алгебры кортежей. 1. Основы алгебры кортежей //Автоматика и телемеханика С. 126–136. Кулик Б.А., Наумов М. В. Представление логических систем в вероятностном пространстве на основе алгебры кортежей. 2. Измеримые логические системы // Автоматика и телемеханика С. 169–179. Фридман А.Я. Ситуационный подход к моделированию промышленно-природных комплексов и управлению их структурой. Труды IV международной конференции "Идентификация систем и задачи управления". Москва, января 2005 г. ИПУ РАН, 2005 г. - С Зуенко А.А., Фридман А.Я. Логический вывод при семантическом анализе нерегламентированных путевых запросов. // Одиннадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2008 (28 сентября - 3 октября 2008 г., Дубна, Россия): Труды конференции. Т.1. – М.: ЛЕНАНД, – С Зуенко А.А., Фридман А.Я. Контекстный подход в системах сопровождения открытых моделей предметной области // Искусственный интеллект и принятие решений С Зуенко А.А., Фридман А.Я. Развитие алгебры кортежей для логического анализа баз данных с использованием двуместных предикатов // Известия РАН. Теория и системы управления – С Зуенко А.А., Кулик Б.А., Фридман А.Я. Анализ корректности запросов к базам данных систем концептуального моделирования средствами алгебры кортежей / Искусственный интеллект. Интеллектуальные системы (ИИ-2009) // Материалы Х Международной научно-технической конференции. - Таганрог: Изд-во ТТИ ЮФУ, С Список литературы

80 Новая книга Спасибо за внимание! Вопросы?