Software & Systems

В современном мире все большую роль играют интеллектуальные системы (ИнтС) [1].

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

ИнтС=РИС+ПИС+ИнИн+АП, (1)

где РИС – рассуждатель интеллектуальной системы, состоящий из генератора гипотез, доказателя теорем и вычислителя; ПИС – поисковая информационная система, которая доставляет информацию, релевантную цели рассуждения; ИнИн – интеллектуальный интерфейс; АП – подсистема автоматического пополнения базы данных и базы знаний из текстов, образующих информационную среду для ИнтС [1]. В системах, основанных на достоверном выводе, важной частью РИС является подсистема дедуктивного логического вывода. Эта подсистема может активно использоваться и подсистемой АП.

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

Структура базы знаний и переменныена множествах отображений

База знаний задается в логике предикатов первого порядка [1,2]. В синтаксис базы знаний были внесены изменения, которые не соответствуют логике первого порядка, а сводимы к ней. Так, в некоторых прикладных задачах возникает необходимость в обобщении элементов множества отображений или создании отображений на этом множестве. Пример такого описания: «для всех допустимых кодов операций КОП процессора, найдется (определена) функция дешифрации DC, результат вычисления которой определяет корректный алгоритм P выполнения закодированной операции на множестве входных сигналов Y и внутреннего состояния процессора S»: . Данное выражение не является выражением исчисления предикатов первого порядка, так как под знаком квантора существования находится имя функциональной буквы (DC). Тем не менее, без потери смысла данное выражение может быть преобразовано к выражению вида: , где f можно определить как функцию, выполняющую некоторое преобразование DC на множестве аргументов Y, S. Данное выражение является выражением исчисления предикатов первого порядка, и после исключения кванторов существования алгоритмом Сколема [3] может быть приведено к виду .

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

Приведем несколько правил нахождения производных:

 (2)

Введем обозначения для данного примера. Функциям предметной области поставим в соответствие одноименные функциональные буквы. Операцию умножения “*” обозначим функциональной буквой mul. Константа “x” будет обозначать переменную, по которой происходит дифференцирование. Отрицание обозначим функциональной буквой neg. Единице соответствует “1”.

Также известно правило нахождения производной суперпозиции функций одного аргумента:

. (3)

С учетом сказанного можно записать правила поиска производных в классическом исчислении предикатов первого порядка (рис.1):

1) dFdx(“x”, “1”)

2) "x dFdx(x, xx) –> dFdx(neg(x), neg(xx))

3) "x dFdx(x, xx) –> dFdx(sin(x), mul(cos(x), xx))

4) "x dFdx(x, xx) –> dFdx(cos(x), mul(neg(sin(x)), xx))

5) "x dFdx(x, xx) –> dFdx(exp(x), mul(exp(x), xx))

Рис. 1. Правила поиска производных в исчислениипредикатов

Здесь предикат dFdx при записи dFdx(A,B) обозначает, что B является производной A по x (точнее, по “x”). Правило поиска производной суперпозиции функций пришлось вносить в правило для производной каждой функции. Другой вариант (требующий внесения множества символов-отношений во множество D) может выглядеть следующим образом:

1) dFdx(“x”, “1”)

2) "S dFdS(f(“neg”, S), f(“neg”, S))

3) "S dFdS(f(“sin”, S), f(“cos”, S))

4) "S dFdS(f(“cos”, S), f(“neg”, f(“sin”, S)))

5) "S dFdS(f(“exp”, S), f(“exp”, S))

6) "S,func dFdS(f(F, S), dfds) & dFdx(S, dsdx) ®

 dFdx(f(F, S), mul(dfds, dsdx))

Рис. 2. Вариант правил поиска производных

Здесь предикат dFdS при записи dFdS(A,B) обозначает, что B является частной производной по выражению S выражения A, что соответствует сомножителю  в приведенной формуле поиска производной суперпозиции функций. В данном случае именам функций предметной области соответствуют символы дополнительного множества констант, полученного из множества функциональных букв. А функции соответствует вновь введенное отображение f. Данное представление позволяет получить результат, но внесенные изменения в представлении скажутся и на формуле заключения: dFdx(f(“exp”,f(“sin”,“x”)),Rez).

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

В данном случае не создавались отображения на множестве отображений, поэтому введенная на новом множестве переменная func будет принимать значения только из нового множества дополнительных констант (“neg”,“sin”,“cos”,“exp”). Поэтому можно упростить запись правил, определив лишь переменные, принимающие значения из множества отображений (рис. 3).

1) dFdx(“x”, “1”)

2) "S dFdS(neg(S), neg(S))

3) "S dFdS(sin(S), cos(S))

4) "S dFdS(cos(S), neg(sin(S)))

5) "S dFdS(exp(S), exp(S))

6) "x,_F dFdS(_F(S), dfds) & dFdx(S, dsdx) ->

 dFdx(_F(S), mul(dfds, dsdx))

Рис. 3. Правила поиска производных после введенияпеременных, принимающих значения на множествеотображений

Здесь _F обозначение переменной, принимающей значения на множестве отображений. Таким образом, в данном примере достигнуто максимальное соответствие описания задачи в предметной области и в логике предикатов. Формулу "x,_F dFdS(_F(S), dfds) & dFdx(S, dsdx) ®® dFdx(_F(S), mul(dfds,dsdx)) можно интерпретировать так: «для всех х и функций _F справедливо, что если найдется частная производная dfds функции _F по S (предикат dFdS) и найдется производная S по x (предикат dFdx), то производная F(S) по x будет определяться как произведение dfds и dsdx».

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

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

·    сокращаются объемы базы знаний по сравнению с вариантом описания в классическом исчислении предикатов;

·    не требуется дополнительных преобразований базы знаний (по сравнению со вторым примером базы знаний, приведенном на рисунке 2) при тех же возможностях обобщения.

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

·-появляется возможность извлекать из баз знаний дополнительную информацию об определенных в ней функциональных зависимостях;

·-в большинстве случаев для извлечения такой информации не потребуется модификация базы знаний, представленная на рисунке 2. Это значит, что можно использовать готовые базы знаний в логике предикатов первого порядка.

Внутреннее представление данныхи алгоритмы их обработки

Формулы базы знаний приводятся к конъюнктивной нормальной форме. Основным элементом внутреннего представления базы знаний является дизъюнкт (дизъюнкция литералов, литерал – это атом, перед которым может стоять знак отрицания). Различаются области видимости дизъюнктов. Так, для дизъюнктов, если они находятся в общей области видимости, могут существовать общие переменные. За основу взят обобщенный метод параллельного дедуктивного логического вывода. В методе используется процедура деления дизъюнктов [3,5] (рис. 4). Упрощенно ее можно представить следующим образом: пусть получен наиболее общий унификатор  в процессе унификации N литералов делимого X и M литералов делителя Y. Если рассматривать делимое и делитель не как дизъюнкты, а как множества литералов, то в результате получим следующие непересекающиеся множества литералов: , , .

Если наиболее общий унификатор не был найден, то это соответствует тому, что MCD=Æ, MRX=X, MRY=Y. Множество  есть множество литералов X, в котором все переменные заменены в соответствии с унификатором .

В дедуктивном выводе X – дизъюнкт базы знаний; Y – выводимое заключение. Множество MRX важно для организации дедуктивного вывода, MCD – для построения цепочки рассуждений, MRY используется в абдуктивных методах [3]. Наиболее общий унификатор  важен для фиксации значений, полученных переменными в процессе вывода.

Результаты работы системы

Результатами работы системы дедуктивного логического вывода являются:

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

·    если заключение выводимо, то дополнительно доступно для анализа множество решений (подстановок), в которых фиксируются значения, полученные той или иной переменной в процессе логического вывода;

·    кроме того, если заключение выводимо, доступно для анализа множество цепочек рассуждений (аргументов). Цепочка рассуждения представима в виде списка, содержащего пары кортежей следующего состава: <индекс дизъюнкта в базе знаний, индекс литерала в дизъюнкте, шаг логического вывода>. В данном списке фиксируются все пары литералов, входящие во множество MCD процедуры деления дизъюнктов.

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

В заключение отметим, что на данный момент реализована последовательная версия алгоритма. Использованный метод логического вывода обладает значительным ресурсом OR-AND параллелизма, за счет которого может быть сокращено время вывода. Для этого целесообразно использование многопроцессорных систем с общей памятью, а при решении задач большой размерности – системы с распределенной памятью (кластерные системы). При ориентации на кластерные системы временные затраты на выполнение операций логического вывода на изолированном узле будут значительно превышать затраты на передачу данных, а также будет возможность использовать все ресурсы узла кластера (который в современных системах представляет собой, как правило, многопроцессорную систему с общей памятью) для параллельного решения части задачи.

Список литературы

1.   Вагин В.Н., Головина Е.Ю., Загорянская А.А., Фоми-на М.В. Достоверный и правдоподобный вывод в интеллектуальных системах. – М.: Физматлит, 2004. – 704 с.

2.   Люгер Джордж Ф. Искусственный интеллект: стратегии и методы решения сложных проблем. 4-е изд. / Пер. с англ. – М.: Издат. дом «Вильямс», 2003. – С.5-217.

3.   Страбыкин Д.А. Логический вывод в системах обработки знаний. - СПб., 1998. – 164 с.

4.   Шихов М.М. Использование дополнительного типа переменных для унификации функторов в исчислении предикатов. // Сб. матер. Всеросс. науч.-технич. конф.: Наука-производство технология-экология. –Киров: Изд-во ВятГУ, 2006. – Т. 1.– С. 227.

5.                                                Шихов М.М. Оптимизация унификации термов и согласования решений в логическом выводе делением дизъюнктов. // Там же. - 2007. – Т. 1.– С. 351.