Файл: Методыискусственногоинтеллекта.pdf

1.2. Системы, основанные на правилах, или продукционные системы
41
Вернемся в «Мир кубиков» и опишем прямую систему правил для робота — строителя башен; вначале неформально.
Правило первое. Если кубик находится на земле и если он не находится под другим кубиком, то выполнить следующие действия:
поднять его и поставить на любой кубик, не находящийся под другим кубиком; поместить в рабочую память факты из множества добав- ляемых фактов и удалить факты из множества удаляемых фактов примененного правила.
Правило второе. Если кубик находится на земле и если он не на- ходится под другим кубиком и если некоторый кубик не находится под кубиком и находится на некотором другом кубике, то выполнить сле- дующие действия: поднять кубик, находящийся на земле, и поместить его на кубик, находящийся на другом кубике; поместить в рабочую память факты из множества добавляемых фактов и удалить факты из множества удаляемых фактов примененного правила.
Для решения этой задачи можно было бы построить систему и из одного правила. Однако это привело бы к серьезному усложнению этого правила и увеличению вычислительных трудностей на этапе исполнения. Кроме того, трудно было бы продемонстрировать возмож- ности стратегии управления.
Перейдем к уточнению вида правил для решения этой задачи.
Обозначим правила через П1 и П2, т. е.
П1 = hC
1
, A
1
, D
1
i,
где
C
1
= {Em(y), Em(x), Er(x)},
A
1
= {On(x, y)},
D
1
= {Em(y), Er(x)},
и
П2 = hC
2
, A
2
, D
2
i,
где
C
2
= {Em(x), Er(x), Em(y), On(y, z)},
A
2
= {On(x, y)},
D
2
= {Er(x), Em(y)}.
Стратегия управления, которая потребуется для решения этой задачи, описана в п. 1.2.3. Напомним ее.
Шаг 1. Выбрать очередное правило из множества правил.
Шаг 2. Проверить выполнимость условия правила в текущем состоя- нии рабочей памяти.

42
Гл. 1. Методы представления знаний
Шаг 3. Если условие правила выполнено, поместить правило в кон- фликтное множество.
Шаг 4. Если множество применимых правил исчерпано, выбрать ка- кое-либо правило из конфликтного множества правил и приме- нить его.
Шаг 5. Перейти к шагу 1.
В нашем примере к начальному состоянию применимо лишь первое правило (так как в начальном состоянии таблица On пуста и, сле- довательно, формула On(x, y) невыполнима), поэтому в начальном состоянии конфликтное множество состоит из одного лишь правила и проблемы выбора не возникает. При установлении выполнимости формул Em(y), Em(x), Er(x) в условия первого правила вместо сво- бодных переменных в формулы условия будут подставлены значения
(например, m1 вместо y и m2 вместо x). Соответствующие подстановки будут выполнены также в формулы из множеств A и D. Атомарные формулы из множеств A и D превратятся в формулы без свободных переменных, т. е. в добавляемые и удаляемые факты, а именно, фор- мулы On(x, y) из множества добавляемых фактов и Em(y) и Er(x)
из множества удаляемых фактов примут вид On(m
2
, m
1
), Em(m
1
),
Er(m
2
), соответственно. Применение правила состоит в том, что пер- вая пара, т. е. (m
2
, m
1
), будет помещена в таблицу On, значения пе- ременных из второй и третьей формул, т. е. m
1
и m
2
, соответственно,
будут удалены из таблиц Em и Er. Таким образом, «Мир кубиков»
будет модифицирован и в рабочей памяти появится описание второго состояния.
К этому второму состоянию оказываются применимы оба правила.
так как множество применимых правил будет теперь состоять из двух правил, то необходимо уточнить шаг 4 стратегии управления, т. е.
значение слов «какое-либо правило».
Если попытаться промоделировать стратегию управления «вруч- ную», то нетрудно убедиться, что на втором шаге следует приме- нить второе правило. Чтобы обеспечить строительство одной башни
(а не нескольких), второе же правило следует применять и на всех последующих шагах. Второе правил отличается от первого б´ольшим количеством атомарных формул в условии. Таким образом, возникает следующий эмпирический принцип выбора: всякий раз, когда к некото- рому состоянию применимо более одного правила, должно выбираться правило, более точно учитывающее особенности текущего состояния;
таким правилом, очевидно, является то правило, условие которого более детально описывает состояние.
Поскольку степень детальности описания состояния определяется количеством атомарных формул в условии правила, то стратегия раз-

1.3. Cемантические сети для представления знаний
43
решения конфликтного множества, которую следует здесь применить,
имеет в своей основе следующую эвристику:
«Выбрать из множества применимых правил то правило, условие
которого содержит наибольшее число предикатных символов».
Именно так следует в данном случае модифицировать шаг 4 стра- тегии управления.
Применение сформулированной эвристики приведет к выбору вто- рого правила и на всех последующих шагах.
Процесс завершится либо по исчерпании применимых правил, либо по достижении целевого состояния. Заметим, что собственно алгоритм строительства башни задан не был. Этот алгоритм получается выписы- ванием последовательности правил, решающей поставленную задачу.
К системам правил мы будем возвращаться и в дальнейшем; им будет уделено достаточно много места в четвертой главе; пока же рассмотрим иной способ представления знаний, называемый семанти- ческими сетями.
1.3. Cемантические сети для представления знаний
Семантическая сеть наряду с системами правил является весьма распространенным способом представления знаний в интеллектуаль- ных системах. Особое значение этот способ представления знаний приобретает в связи с развитием сети интернет. Кроме ряда особен- ностей, позволяющих применять семантические сети в тех случаях,
когда системы правил не применимы, семантические сети обладают следующим важным свойством: они дают возможность соединения в одном представлении синтаксиса и семантики или синтаксическо- го и семантического аспектов описаний знаний предметной области.
Происходит это благодаря тому, что в семантических сетях наряду с переменными для обозначения тех или иных объектов (элементов множеств, некоторых конструкций из них) присутствуют и сами эти элементы и конструкции; присутствуют и связи, сопоставляющие тем или иным переменным множества допустимых интерпретаций. Эти об- стоятельства позволяют во многих случаях резко уменьшить реальную вычислительную сложность решаемых задач.
1.3.1. Простые и расширенные семантические сети. Понятие семантической сети возникло в 1966 г. в работах М. Р. Квиллиана [11]
при попытке описания семантики глагола с помощью графа специаль- ного вида. Это описание было составлено из вершин, в которых нахо- дились лексические единицы анализируемого предложения, и «ассоци- ативных» дуг, служащих для описания ссылок одних вершин на дру- гие. Для таких описаний М. Р. Квиллиан ввел термин «семантическая

44
Гл. 1. Методы представления знаний
память». Каждой вершине в семантической памяти соответствовала некоторая «страница», содержащая определение соответствующего вер- шине понятия. Каждый из указателей относился к одному из следую- щих типов: подкласс, дизъюнкция, конъюнкция, свойство, субъект.
Такие структуры обладали некоторыми дедуктивными свойствами,
порождаемыми отношениями «подкласс» и «свойство». Один из ме- ханизмов вывода в семантической сети Квиллиана состоял в распро-
странении активности и поиске по пересечению. Пути от начальных вершин к общей вершине определяют некоторое отношение между двумя лексическими единицами. Иначе говоря, речь шла об обнаруже- нии неявно (имплицитно) заданной информации для дальнейшего ее использования в интеллектуальной системе.
Роберт Ковальский из Эдинбурга в 1979 г. [12] ввел понятия про-
стых и расширенных семантических сетей, использовав клаузальную логику для их определения.
Для рассмотрения семантических сетей такого вида вернемся к язы- ку исчисления предикатов первого порядка, а именно, к его клаузаль-
ной форме.
Клауза есть выражение вида
B
1
, B
2
, ... , B
m
← A
1
, ... , A
n
, где
B
1
, B
2
, ... , B
m суть атомарные формулы, n > 0 и m > 0.
Атомарные формулы A
1
, ... , A
n суть совместные посылки клаузы,
а B
1
, B
2
, ... , B
m суть альтернативные заключения. (Множество клауз совместно, если оно истинно в одной из моделей языка.)
Если клауза содержит переменные x
1
, x
2
, ..., x k
, то она со- ответствует формуле с квантором всеобщности: ∀x
1
, ∀x
2
, ..., ∀x k
(B
1
∨ B
2
∨ ... ∨ B
m
, если A
1
∧ ... ∧ A
n
).
Если n = 0,
то клаузу следует интерпретировать так:
∀x
1
, ∀x
2
, ..., ∀x k
(B
1
∨ B
2
∨ ... ∨ B
m
). Если m = 0, то интерпретация такова: ¬∃x
1
, ¬∃x
2
, ..., ¬∃x k
(A
1
∧ ... ∧ A
n
).
Если n = m = 0, то клауза является тождественно ложным выска- зыванием и записывается .
Если клауза содержит не более одной атомарной формулы в заклю- чении, т. е. m 6 1, то клауза называется клаузой Хорна или Хорновской клаузой.
Простая семантическая сеть может рассматриваться как форма записи утверждений клаузальной логики без свободных переменных.
Например, клауза P (a, b) ← в языке простых семантических сетей изображается как дуга, помеченная меткой P и направленная из a в b:
Рис. 1.3

1.3. Cемантические сети для представления знаний
45
В расширенных семантических сетях, как и в простых, вершины сопоставляются индивидам, а ребра — бинарным отношениям.
Однако вершины в расширенных семантических сетях могут соот- ветствовать константным символам, переменным или термам, содержа- щим функциональные символы. Атомарные формулы, соответствующие условиям клауз описываются с помощью двойных дуг, а заключения —
одинарных. Клаузы, содержащие более одной атомарной формулы,
можно выделять как подсети. Например, расширенная семантическая сеть на рис. 1.4. описывется множеством клауз:
Джону нравится Мэри ←;
Джон является человеком ←;
Мэри нравится Джон, Мэри нравится Боб ← Мери нравится x;
Бобу нравится y ← y нравится логика.
Рис. 1.4
Помимо изобразительных возможностей, семантические сети об- ладают более серьезными достоинствами. То обстоятельство, что вся информация об индивиде представлена в единственном месте — в од- ной вершине — означает, что вся эта информация непосредственно доступна в этой вершине, что, в свою очередь, сокращает время поиска,
в частности, при выполнении унификации и подстановки в задачах логического вывода.
Существует еще одна, более тонкая особенность расширенных се- мантических сетей — они позволяют интегрировать в одном пред-
ставлении синтаксис и семантику (т. е. интерпретацию) клаузальных форм. Это позволяет в процессе вывода обеспечивать взаимодействие синтаксических и семантических, теоретико-модельных подходов, что,
в свою очередь, также является фактором, зачастую делающим вывод практически более эффективным.
1.3.2. Универсум Эрбрана и семантические сети. Здесь мы развернем тезис, сформулированный в последнем абзаце предыдуще- го раздела. Пусть задано некоторое множество клауз. Попытаемся
«экономным» способом построить для него модель. Это означает, что следует выбрать некоторый универсум и указать соответствие меж-

46
Гл. 1. Методы представления знаний
ду константами и иными конструкциями языка и объектами этого универсума и конструкциями из них. Следуя принципу экономии, мы не будем вводить специальных имен для элементов модели, поэтому выберем в качестве универсума такое множество, которое включает
все константы, встречающиеся в множестве клауз, и все термы,
построенные из них с помощью функциональных символов, встре-
чающихся в множестве клауз. Такое множество называется универ-
сумом Эрбрана.
Иначе говоря, интерпретация I есть в данном случае тождественное отображение из множества термов в себя. Далее, доведя принцип экономии до конца, мы используем n-местные предикатные символы,
встречающиеся в клаузах, для обозначения соответствующих им при отображении I n-арных отношений над элементами универсума.
Рассмотрим простой пример.
Пусть задано множество высказываний:
Всякий человек, который является хозяином собак, не является
хозяином кошек.
Джон является хозяином Линды.
Петя является хозяином Мурки.
Введем бинарные предикатные символы: P — быть хозяином и Q —
не быть хозяином. Тогда клаузальная форма этих утверждений имеет следующий вид:
Q(человек, кошка) ← P (человек, собака);
P (Джон, Линда) ←;
P (Петя, Мурка) ←.
Для полноты картины введем еще один предикатный символ,
означающий принадлежность экземпляра (примера) общему поня- тию. В теории интеллектуальных систем его принято обозначать ISA
(«is a» — третье лицо единственного числа английского глагола to be):
ISA(Джон, человек) ←;
ISA(Петя, человек) ←;
ISA(Линда, собака) ←;
ISA(Мурка, кошка).
Иногда этот предикатный символ используется в инфиксной нота- ции, например, «Джон ISA человек», но это не имеет существенного значения.
Представим теперь описанную ситуацию в виде расширенной се- мантической сети (рис. 1.5).
На рис. 1.5 каждому предикатному символу соответствует свой тип линии, а именно:
P —
;
ISA —
;
Q —

1.3. Cемантические сети для представления знаний
47
Рис. 1.5
Направление стрелки указывает порядок следования аргументов в формуле.
Если сопоставить этот рисунок со сказанным об универсуме Эрбра- на, то легко видеть, что закрашенные вершины соответствуют элемен- там, а пары (Петя, Мурка), (Джон, Линда) — элементам отношений универсума Эрбрана, а именно — отношению P . Что касается пар
(Мурка, кошка), (Линда, собака), (Петя, человек) и (Джон, человек),
принадлежащих отношению ISA, то они связывают синтаксис с семан- тикой или синтаксические элементы «Кошка», «Собака» и «Человек»,
являющиеся именами общих понятий, с примерами этих понятий.
Оставив более детальное изучение полезных свойств универсума
Эрбрана для последующих глав, используем нотацию расширенных семантических сетей для ответа на вопрос: «Является ли Джон хо- зяином Мурки?» Для решения этой задачи вначале совместим пары
закрашенных вершин с парами незакрашеных по ISA ребрам, при этом метка ребра пары закрашенных вершин должна совпадать с меткой ребра пары незакрашенных вершин. Затем проделаем такую же опе- рацию с интересующими нас целевыми вершинами (т. е. совместим их с незакрашенными вершинами по ISA-связям), в результате чего немедленно получим, что Джон не является хозяином Мурки. Этот простой пример есть пример вывода на расширенной семантической сети.
В 1986 г. В. Н. Вагин [13] предложил раскрашенные семантические сети. В отличие от расширенных семантических сетей в раскрашеных семантических сетях вершины соответствуют клаузам, их условиям,
заключениям и предикатным символам, в них входящим, а ребра свя- зывают условия и заключения клауз с вершинами, соответствующими клаузам. Далее, атомарные формулы, входящие в условия и заключе- ния, соединяются ребрами с вершинами, соответствующими условиям

48
Гл. 1. Методы представления знаний
и заключениям, и, наконец, индивидные символы соединяются ребрами с вершинами, соответствующими атомарным формулам. Кроме того,
введены специальные правила раскраски семантических сетей. Они таковы: для каждой клаузы A ← B условие и заключение «раскра- шиваются» различными цветами. Это правило распространяется также на тот случай, когда как условие, так и заключение состоят более чем из одной атомарной формулы. Раскрашенные сети позволяют более эффективно, чем предыдущие представления, организовать процесс параллельной дедукции. Более подробную информацию о них можно почерпнуть из литературы, указанной в конце книги.
В 1987 г. автор этих строк ввел понятие неоднородных семантиче- ских сетей [14].
Приведем краткое описание этого способа представления знаний.