7.4.5. Язык SNARK — пример языка первого порядка

Язык SNARK построен на логике первого порядка и представлении знаний в реляционной форме. В противоположность системе MYCIN, которая ограничивается пропозициональным исчислением, здесь предусматривается постоянное использование переменных. Фраза человек” означает в SNARK “для каждого х, который является человеком”. Точная форма связанного с этим силлогизма имеет вид

SNARK из факта “природа (Сократ) человек” выводит факт

Это правило выполняется для всех тех х, для которых природа человек.

Используемые отношения являются по соглашению бинарными. В записи правил переменные фигурируют в скобках.

Система предусматривает также возможность “вложенного” определения свойств, как во фразе

Ссылки на объекты производятся не с помощью имен, а только через совокупность связанных с ними свойств. Таким образом, геологический объект размещенный под слоем С, имеющим рифтовую природу и возраст, превышающий 100 лет, будет описан следующим образом:

В SNARK могут быть выражены чисто математические отношения. Например, свойство транзитивности понятия “под”:

Из этих свойств следует, что язык SNARK является языком, близким к семейству языков Пролога, но отличается тем, что

в нем используется не резолюция, а естественная дедукция и он не ограничен предложениями Хорна. Порядок посылок, как и порядок правил, не имеет значения. Однако такая гибкость ввода знаний достигается ценой угрозы комбинаторного взрыва. Действительно, подготовительной операцией для оценки является замена переменной правила множеством объектов базы фактов. Угроза комбинаторного взрыва устраняется с помощью стратегии динамической оценки правил, идея которой заключается в том, что оценка начинается с известных в данный момент величин и последующего распространения символьных значений (гл. 8.).

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

Вычисление неопределенных интегралов в системе SNARK

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

Пример 1

(см. скан)

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

Пример 2

(см. скан)

Отметим следующее:

1. Вызов этих правил происходит только по необходимости, т. е. когда по крайней мере одна из посылок соответствует одному из заключений предыдущих правил.

2. Переменная играет роль глобальной переменной. С ее помощью описываются все обрабатываемые объекты и выполняются на них ссылки. Такое возможно только при благоприятных обстоятельствах, которые встречаются не во всех приложениях.

3. Некоторые посылки играют роль определений. Их описание включает слово ПУСТЬ. В этом случае оценка правила начинается с части ПУСТЬ, а часть ЕСЛИ тестируется, только когда известны аргументы.

4. В базе фактов также присутствуют переменные величины (в математическом смысле слова).

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

Пример

(см. скан)

Два последних действия выполняются следующим образом:

а) Везде в выражении применять два правила

б) Проверить, что после этой операции интегрируемая величина не содержит переменную х.

При сравнении с классическим программированием обнаруживается следующее:

1. Не надо упорядочивать правила.

2. Правила независимы: они связаны только с помощью промежуточных утверждений над единственной глобальной переменной — интегрируемым выражением, которое может видоизменяться по ходу решения; например, или

3. Одному и тому же интегралу могут соответствовать несколько правил. Начальный выбор правила определяется с помощью приоритета, связанного со сложностью выражения под знаком суммы. В случае неудачи делается другой выбор.

4. Полный набор правил для исчисления интегралов содержит 86 правил стратегического характера, 368 правил вычислений тригонометрических, степенных и логарифмических выражений.

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

6. Язык SNARK позволяет описывать как очень общие правила (приведенный выше случай), так и весьма специфические, например:

Роль переменных в системе SNARK

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

1) индексация содержимого базы (связный список);

2) параметризация правил (передача аргументов);

3) вызов цели (подпрограммы);

4) управление деревом поиска (приведение в порядок стека) Рассмотрим эти роли более подробно.

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

Рис. 7.12. Объект в базе фактов SNARK.

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

Вызов подпрограммы. Конкретный результат работы правила зависит от значений переменных, и его получение может быть связано с вызовом новой цели. Например, запись “замена переменной позволяет запомнить возможную цель замены переменной. Данное обстоятельство будет затем учтено каким-либо другим правилом. Это представляет собой оригинальный метод вызова процедуры, поскольку в любой момент могут конкурировать между собой несколько целей-процедур. Тогда окончательный выбор осуществляется с помощью правил более высокого уровня (метаправил), которые учитывают трудности достижения различных целей.

Управление деревом поиска. По природе решаемые задачи требуют возврата назад в процессе решения. Это происходит в тех случаях, когда правило выполняется слишком рано, неудачно определен набор переменных или поставленная задача не имеет решения и надо проверить другие возможности. Мы снова приходим к управлению классическим деревом, которое иногда осуществляется с помощью рекурсивных программ. В этом случае глубина рекурсии заранее неизвестна и может достигать очень больших значений. Индексация переменных позволяет осуществить управление гораздо проще: задание конкретного набора выполняемых правил определяет параметр индексации,

основанный на всех фактах, известных на данный момент. Рассмотрим, например, выражение которое после замены переменной обозначим через Если впоследствии решение задачи зашло в тупик, информация о теряется и поиск возобновляется от первоначального выражения. В этом случае стратегию использования дерева поиска можно определить с помощью метаправил и отдать предпочтение выражению наименьшей сложности, т. е. управление поиском осуществляется извне программы (“режим попыток” (Nilsson, 80), (Farenny, 85)).

С помощью логики первого порядка системы SNARK можно, например, за несколько дней составить и реализовать блок правил для формального интегрирования. Время вычисления интеграла в среднем составляет 1 с на ЭВМ типа ИБМ 370/168 для интегралов вида

Выигрыш во времени реализации по сравнению с классическими методами очевиден. За с может быть выведена в среднем тысяча фактов.

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

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

В разд. 7.6 мы попытаемся сформулировать преимущества и недостатки декларативного подхода к созданию экспертных систем по сравнению с обычным процедурным подходом, используемым специалистами по информатике. В разд. 7.7 рассмотрены выражения, с помощью которых осуществляется управление самим языком: фундаментальное отличие экспертных систем от систем с правилами перезаписи состоит в метазнании.