Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ
Посмотреть оригинал

Индексация и предварительный отбор фактов

Пусть базу фактов образуют триплеты вида «субъект — предикат — объект» либо «субъект — атрибут — значение», представление которых в нотации языка Prolog может выглядеть следующим образом:

где s — субъект; о — объект; predicate — предикат (отношение, связывающее субъект и объект), например parent (sergey, nikita).

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

где s — субъект; р — предикат (отношение, связывающее субъект и объект); о — объект; f — предикат языка Prolog, идентифицирующий данное утверждение как факт базы знаний.

Заметим, что логика первого порядка не допускает переменные предикаты и операции над ними.

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

Для множества термов Т = {г}, встречающегося в фактах, построим индекс в виде

где w — место данного терма в атоме (в качестве субъекта, предиката или объекта), w = (V; ’р' ’o’); {itw} — множество номеров фактов, имеющих терм t в роли w.

Резолюция правила заключается в установлении истинности условий и присвоении значений переменным.

Теперь, при обращении к правилу, тело которого состоит из множества условий ь с сД, примем

где Sj — субъект; pj — предикат, pj = t Oj — объект; (s; о) = (^; г; — переменная.

Поскольку в логике первого порядка не допускается использование переменных в качестве предиката, каждое из условий с} может иметь одно из четырех сочетаний термов и переменных: (t, t, t) (t, t, v) (г;, t, t) U v).

Для каждого из с; условий правила извлечение релевантных фактов для перечисленных сочетаний термов заключается в нахождении пересечений множеств индексов:

Каждой переменной используемой в j-м условии, из списков Ij можно поставить в соответствие множество кортежей {z, иг), где г — номер факта, щ — значение переменной vf извлекаемое из z-ro факта. Если переменная v используется более чем в одном условии правила, пересечение

множеств значений переменной во всех условиях С правила, в которых эта переменная используется, позволит сократить число фактов, требуемых для унификации этих условий. Для получения списка фактов Ivj, содержащих переменную v для j-го условия правила, где эта переменная встречается, достаточно выполнить операцию реляционного деления

Наконец, если в условии правила с} участвует более одной переменной, то пересечение списков

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

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

fn (1, sergey, has_sex, male). fn (2, nikita, has_sex, male). fn (3, sergey, is_a, person). fn (4, natalia, is_a, person),

fn (5, nikita, is_a, person). fn (6, nikita, has_sex, male). fn (7, natalia, has_sex, female).

fn (8, sergey, parent, nikita). fn (9, sergey, parent, andrey) . fn (10, natalia, parent, nikita). fn (11, natalia, parent, andrey). fn (12, nikita, parent, stepan).

fn (13, andrey, parent, egor) .

Построим для этих фактов индекс, как показано в формуле (3.1):

х (sergey, s, [1,3,8,9]). х (male, о, [1,2,6]). х (nikita, s, [2,5,6,12]). x (person, о, [3,4,5]). x (natalia, s, [4,7,10,11]). x (female, o, [7]). x (andrey, s, [13]) . x (nikita, o, [8,10]) . x (has_sex, p, [1,2,6,7]). x (andrey, o, [9,11]). x (is_a, p, [3,4,5]). x (stepan, o, [12]) . x (parent, p, [8,9,10,11,12,13]). x (egor, o, [13]) .

Создадим правила в виде г (conditionList, resultingList) с использованием переменных, начинающихся с вопросительного знака, где conditionList — список условий, resultingList — список триплетов результата. Первое правило устанавливает, что субъект является мужчиной, если он является человеком и имеет мужской пол:

г ([с ("?х", is_a, person), с ("?х", has_sex, male)],

[f ("?х", is_a, man)].

Используем индекс для отбора фактов и найдем пересечение значений переменной ?х, используемых во всех условиях:

[sergey, natalia, nikita] n [sergey, nikita, nikita] = [sergey, nikita].

Фильтруем списки фактов, требуемых для резолюции каждого условия правила, включая в них только значения термов, попавшие в пересечение (табл. 3.1). Для первого условия это факты [3, 5], а для второго — [1, 2, 6]. Таким образом, для резолюции правила требуется унифицировать условия правила с пятью фактами. Если не использовать индекс, то каждое условие правила нужно сопоставлять со всеми 13 фактами (всего 133 = 2197 сочетаний).

Таблица 3.1

Предварительный отбор фактов для правила ?х is a man

Параметр

Условие правила

первое

второе

Исходное условие

?х, is_a, person

?x, has_sex, male

Индекс для используемых термов

х (is_a, р, [3, 4, 5]). х (person, о, [3, 4, 5])

x (has_sex, p, [1, 2, 6, 7]). x (male, о, [1, 2, 6])

Пересечение по номерам

?х, s, [3, 4, 5]

?x, s, 11, 2, 6]

Значения переменной

?х = [sergey, natalia, nikita]

?x = | sergey, nikita, nikita]

Пересечение по значениям

[sergey, nikita]

Отфильтрованный индекс

?x, s, [3, 5]

?x,s, 11,2,6]

Создадим более сложное правило, определяющее отношение «прародитель» (grandparent):

г ([с ("?х", parent,"?у"), с <"?у", parent,"?z")],

[f ("?х", grandparent,"?z")].

Более одного раза в правиле встречается только переменная ?у; пересечение ее допустимых значений в первом и втором условиях равно

В качестве допустимых значений переменной мы получили список объектов, которые являются одновременно родителями и детьми. Прореживаем список фактов для первого условия [8, 9, 10, 11, 12, 13], оставляя в нем только факты, имеющие термы [;nikita, andrey) в качества объекта. Получаем список [8, 9, 10, 11]. Аналогично получаем список фактов [12, 13] для второго условия (табл. 3.2). Находим пересечение номеров фактов, соответствующих каждой из переменных, в каждом из условий. Для первого условия [8, 9, 10, 11, 12, 13] п 18, 9, 10, 111 = [8, 9, 10, 11], для второго — [12, 13] п [8, 9, 10, 11, 12, 13] = [12, 13]. Таким образом, мы добиваемся того, что каждому из условий правила в процессе унификации будут предъявляться только факты, гарантированно порождающие результаты.

Таблица 3.2

Предварительный отбор фактов для правила 2х grandparent ?z

Параметр

Условие правила

первое

второе

Исходное условие

«Тх», parent, «Ту»

«Ту», parent, «Tz»

Индекс для используемых термов

х (parent, р, [8, 9, 10, 11, 12, 13])

x (parent, p, [8, 9, 10, 11, 12, 13])

Пересечение по номерам

?x,s, 18, 9, 10, 11, 12, 13[). Ту, о, [8, 9, 10, И, 12, 13])

Ту, s, 18, 9, 10, 11, 12, 13|). Tz, o, [8, 9, 10, 11, 12, 13])

Значения переменной

[nikita, andrey, nikita, andrey, stepan, egor

[sergey, sergey, natalia, natalia, nikita, andrey]

Пересечение по значениям

[nikita, andrey [

Отф ил ьтро ванный индекс

[8, 9, 10, 11]

112, 13]

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

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы