БЫСТРЫЙ ЛОГИЧЕСКИЙ ВЫВОД В СРЕДЕ ПРОГРАММИРОВАНИЯ VISUAL PROLOG
БЫСТРЫЙ ЛОГИЧЕСКИЙ ВЫВОД В СРЕДЕ ПРОГРАММИРОВАНИЯ …
УДК 004.89
БЫСТРЫЙ ЛОГИЧЕСКИЙ ВЫВОД В СРЕДЕ ПРОГРАММИРОВАНИЯ VISUAL PROLOG
И.А. Бессмертный
В статье обсуждается реализация логического вывода в системах искусственного интеллекта, построенных на продукционной модели знаний, с использованием теоретико-множественных операций в среде программирования Visual Prolog. Предлагается набор предикатов, реализующих быстрое выполнение операций реляционной алгебры. Приводятся результаты натурных экспериментов, подтверждающих существенное, не менее чем на три порядка, ускорение логического вывода для баз знаний с большим числом фактов. Ключевые слова: искусственный интеллект, реляционная алгебра, Prolog
Введение Язык программирования Prolog, имеющий встроенный механизм исчисления предикатов MODUS PONENS, является привлекательным инструментом для построения систем искусственного интеллекта, поскольку конструкции на языке Prolog максимально приближены к логическим выражениям, которыми может быть описана решаемая проблема. Обратной стороной изящности Prolog-программ является их низкая производительность в связи с тем, что резолюция цели достигается путем «наивного» логического вывода, т.е. перебора всех возможных вариантов, а значит, обхода всех ветвей на дереве решений. 50 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)
И.А. Бессмертный
Существующие методы ускорения логического вывода в системах искусственного интеллекта, построенных на продукционной модели знаний, связаны с предварительной обработкой правил. Наиболее известным является алгоритм Rete [1], в котором для каждого условия правила строится список фактов, удовлетворяющих данному условию. Списки фактов образуют префиксное дерево, которое должно создаваться для каждого правила. Таким образом, быстродействие обеспечивается многократным дублированием фактов. Узким местом алгоритма Rete является необходимость обновления всех префиксных деревьев при каждой модификации базы фактов, что обусловливает ограниченное применение алгоритма.
В работе [2] предлагается индексация и предварительный отбор фактов, релевантных правилам. Эффективность данного подхода существенно зависит от доли фактов, участвующих в каждом правиле: чем она выше, тем меньше выигрыш от использования индексов.
Необходимость в создании машины логического вывода (интеллектуального агента) предусмотрена в концепции Глобальной семантической сети (Semantic Web) [3], которая базируется на продукционной модели знаний. При этом набор операций над фактами, предусматриваемый в языках представления правил, в частности, SWRL, является ограниченным, поскольку элементами правил (атомами) могут быть только C(x), P(x, y), sameAs(x, y) или differentFrom(x, y), где С – свойство, P – отношение, x, y – переменные [4]. Как показано в работе [2], интерпретация правил может быть заменена операциями реляционной алгебры над кортежами значений переменных, хранящихся в фактах. Хранение фактов и логический вывод могут быть перенесены в среду систем управления базами данных (СУБД). Использование СУБД для построения систем искусственного интеллекта порождает новые проблемы: необходимость трансляции правил в язык запросов SQL, преобразования имен и др. В этой связи представляет интерес логический вывод с использованием реляционных операций в среде языка программирования Prolog как наиболее удобной для манипулирования знаниями.
Реализация быстрых реляционных операций в среде Visual Prolog
Набор базовых операций реляционной алгебры включает в себя пересечение X Y (INTERSECT), вычитание X Y (DIFFERENCE), объединение X Y (UNION), соединение (JOIN), проекцию, дополнение (NOT) и фильтрацию (WHERE) [5]. Реализация над двумя списками X={x} и Y={y} операций пересечения, разности и объединения предполагает в среднем развертывание nxny/2 вершин дерева поиска (список Y сканируется до первого появления искомого значения), где nx, ny – количество фактов в множествах X и Y соответственно. Для операции соединения развертывается nxny вершин, поскольку соединение представляет собой декартово произведение с фильтрацией. Операции дополнения и фильтрации в языке SWRL являются простыми, поскольку здесь не допускается вложенный поиск, и требуют развертывания только nx вершин.
Ниже приведен текст предиката list:: intersection, входящего в состав библиотеки list языка Visual Prolog 7.2 (http://www.visual-prolog.com/). Здесь и далее вместо множеств мы будем говорить о списках. Во-первых, список – это агрегат данных, которым манипулирует Prolog; во-вторых, списки допускают повторяющиеся значения, сохранение которых необходимо в некоторых операциях.
predicates
intersection: (Elem* ListA, Elem* ListB) Elem* IntersectionAB.
clauses
intersection([],_) = [].
intersection([X|Xs],Ys) = [X|intersection(Xs,Ys)]:-
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
51
БЫСТРЫЙ ЛОГИЧЕСКИЙ ВЫВОД В СРЕДЕ ПРОГРАММИРОВАНИЯ …
isMember(X,Ys), !.
intersection([_|Xs],Ys) = intersection(Xs,Ys). Предикат list::isMember вызывает извлечение в среднем ny/2 элементов списка Y,
для каждого элемента списка X, что и обусловливает низкую скорость работы данного предиката.
Отсортируем списки X={x} и Y={y} по возрастанию значений. В этом случае оба списка можно обрабатывать совместно, и дерево поиска будет состоять из nx+ny вершин. Таким образом, ожидаемое ускорение обусловлено переходом от квадратичной к линейной зависимости сложности поиска от числа фактов. Предикат нахождения пересечения отсортированных списков intersectSorted представлен ниже.
predicates
intersectSorted : (Elem* ListX, Elem* ListY) Elem* IntersectionXY.
clauses
intersectSorted([],_) = [] :-!.
intersectSorted(_,[]) = [] :-!.
intersectSorted([Y|Xs],[Y|Ys]) = [Y|intersectSorted(Xs,[Y|Ys])] :-!.
intersectSorted([X|Xs],[Y|Ys]) = intersectSorted([X|Xs],Ys) :- X>Y,!.
intersectSorted([_|Xs],[Y|Ys]) = intersectSorted(Xs,[Y|Ys]). Похожим образом реализуется операция вычитания множеств X Y differenceSorted:
predicates
differenceSorted : (Elem* ListX, Elem* ListY) Elem* ListXExceptListY.
clauses
differenceSorted([],_) = [] :-!.
differenceSorted(R,[]) = R :-!.
differenceSorted([X|Xs],[X|Ys]) = differenceSorted(Xs,[X|Ys]) :-!.
differenceSorted([X|Xs],[Y|Ys]) = [X|differenceSorted(Xs,[Y|Ys])] :- X Elem* UnionXY.
clauses
unionSorted([],R) = R :-!.
unionSorted(R,[]) = R :-!.
unionSorted([X|Xs],[X|Ys]) = unionSorted(Xs,[X|Ys]) :-!.
unionSorted([X|Xs],Ys) = [X|unionSorted(Xs,Ys)]. Наиболее часто в процессе интерпретации условий правил требуется соединение
двух множеств кортежей (x1, x2, xm) и (y1, y2, ..., yk) по совпадению значений переменных xi = yj. В реляционной алгебре данной функции соответствует операция INNER JOIN. Количество развертываемых вершин дерева поиска для данной операции в случае наивного вывода составляет nxny ,а для соединения отсортированных списков
N = nx + ny+ SUM(nxinyj, xi=yj, (nxi >1 nyj >1)),
(1)
где nxi, nyj, – количество повторяющихся значений в первом и втором списке соответ-
ственно. Если пренебречь возможностью повторения одних и тех же значений в обоих
списках (nxi>1 nyj>1), а также случаями (nxi >1 nyj=0) и (nxi=0 nyj>1), то формулу (1) можно упростить:
N = nx + ny+ dx+ dy,
(2)
52 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)
И.А. Бессмертный
где dx, dy, – число дубликатов значений в списках X и Y соответственно. Ниже представлен текст предиката, реализующего данную операцию над двумя множествами кортежей {(x1, x2)} и {(y1, y2)} по совпадению x1 = y1.
predicates
innerJoinSorted:(t{X,X}* ListX, t{X,X}* ListY, t{X,X,X}* JoinXY) t{X,X,X}* JoinXYfinal. innerJoinSorted1:(t{X,X}, t{X,X}*, t{X,X}*, t{X,X,X}*) procedure (i,i,o,o).
clauses innerJoinSorted([], _, Final) = Final :- !. innerJoinSorted([t(X1,X2)|Xresidue],Y,In)=innerJoinSorted(Xresidue,YtoLookUp,Out) :innerJoinSorted1(t(X1, X2), Y, YtoLookUp, XY), Out = list::append(XY, In).
innerJoinSorted1(_, [], [], []) :- !. innerJoinSorted1(t(X1,_X2),[t(Y1,Y2)|Yresidue], [t(Y1,Y2)|Yresidue],[]) :-X1 Y1, !, innerJoinSorted1(t(X1,X2), Yresidue, YlookUp, XY).
innerJoinSorted1(t(X1,X2),[t(Y1,Y2)|Yresidue],[t(Y1,Y2)|YlookUp], [t(X1,X2,Y2)|XY]) :innerJoinSorted1(t(X1,X2),Yresidue,YlookUp,XY).
В табл. 1 обобщены данные о каждой из реляционных операций и их сложности, измеряемой числом развертываемых вершин дерева поиска.
Операция
Пересечение X Y Разность X Y Объединение X Y =(X-Y)+(Y-X)+(X Y) Соединение
Оператор в СУБД
Встроенный предикат в
Visual Prolog
INTERSECT list::intersection
MINUS list::difference
UNION
list::union
JOIN
отсутствует
Сложность встроенного предиката
nxny/2 nxny/2 nxny/2
nxny
Сложность быстрого предиката
nx + ny nx + ny nx + ny
nx + ny+ dx+ dy
Таблица 1. Сложность операций реляционной алгебры
Исследование быстродействия
Для исследования быстродействия использовались множества положительных чисел, полученные с помощью генератора случайных чисел. Предикат, формирующий список положительных чисел, представлен ниже.
predicates
generate : (positive, positive, positive*) procedure (i,i,o).
clauses
generate(0,_,[]) :- !.
generate(N,Range,[Num1|Residue]) :- Num1=math::random(Range),
generate(N-1,Range,Residue). Наивный логический вывод был реализован итеративными предикатами, приведенными ниже. Здесь f1(X), f2(X) и f(X) – исходные и результирующий факт соответственно.
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
53
БЫСТРЫЙ ЛОГИЧЕСКИЙ ВЫВОД В СРЕДЕ ПРОГРАММИРОВАНИЯ …
% Пересечение
isec() :- f1(X), f2(X), assert(f(X)), fail.
isec(). % Вычитание
idiff() :- f1(X), not(f2(X)), assert(f(X)), fail.
idiff(). % Соединение
ijoin() :- f1(t(X1,X2)), f2(t(X1,Y2)), assert(f3(t(X1,X2,Y2))), fail.
ijoin(). Приведенные в табл. 2 и на рис. 1 результаты натурных экспериментов пока-
зывают, что логический вывод с использованием реляционных операций над отсортированными множествами на три-четыре порядка быстрее наивного вывода, в то время как предикаты реляционной алгебры дают ускорение не более, чем на порядок по сравнению с наивным выводом.
Число фактов Время сортировки списков, с Время сортировки кортежей, с Пересечение списков, наивный вывод, с Пересечение списков, библ.предикат, с Пересечение быстрый предикат, с Объединение списков, библ.предикат, с Объединение списков, быстрый предикат, с Вычитание списков, быстрый предикат, с Соединение кортежей, наивный вывод, с Соединение кортежей, быстрый предикат, с
100000 3,1 3,73 360 1400 0,08 2020 0,09 0,09 316 0,26
200000 4,5 6,5 1536 6530 0,15 7203 0,28 0,17 1804 0,55
400000 14,4 18,11 5800 22605 0,33 22563 0,56 0,36 6600 1,4
800000 30,6 36
1600000 65,89 75
0,73
1,13 1,2 23400 2,5
1,41
2,13 2,34
5,4
Таблица 2. Результаты натурных экспериментов
100000
Время сортиров ки списков , с
10000 1000 100
Время сортиров ки кортежей, с Пересечение списков , наив ный в ыв од, с Пересечение списков , библ.предикат, с Пересечение быстрый предикат, с
Время, с
10
1
0,1
0,01 100000
200000
400000
800000
Число фактов
1600000
Объединение списков , библ.предикат, с Объединение списков , быстрый предикат, с Вычитание списков , быстрый предикат, с Соединение кортежей, наив ный в ыв од, с Соединение кортежей, быстрый предикат, с
Рис.1. Результаты натурных испытаний методов логического вывода
54 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)
И.А. Бессмертный
Сортировка стандартным предикатом list::sort демонстрирует высокую скорость,
поэтому даже если считать, что сортировка выполняется перед каждой реляционной
операцией, выполнение таких операций над отсортированными списками более чем на
два порядка быстрее, чем наивный логический вывод.
Предложенные здесь Prolog-предикаты не требуют больших объемов оперативной
памяти, поскольку во всех предикатах хвостовая рекурсия (tail recursion) отсутствует.
Объем памяти, занимаемый тестовой программой за вычетом памяти для хранения базы
фактов, в течение всего процесса обработки тестовых фактов не превышает 10 Мб.
Натурные испытания позволили также проверить применимость формул, приве-
денных в табл. 1, для оценки времени вывода в предположении о том, что время вывода
T = tN,
(3)
где t – время развертывания одной вершины дерева поиска, N – число вершин. Рис. 2 и
3 демонстрируют, что данная формула может применяться как для наивного логическо-
го вывода, так и для операций реляционной алгебры, причем время t составляет поряд-
ка 4 10-8с для наивного вывода, 2,85 10-7с для стандартных предикатов, реализующих
реляционные операции, и 4,4 10-7с для быстрых предикатов.
Время, с
1,6
1,4
1,2
1 0,8 Измеренное время, с
Расчетное время, с 0,6
0,4
0,2
0
100000 150000 200000 300000 400000 600000 11628000000000000000
Число фактов
Рис. 2. Сравнение измеренного и расчетного времени вывода для операции быстрого пересечения
25000
20000
Время,с
15000 10000
Измеренное в ремя, с Расчетное в ремя, с
5000
0 100000 150000 200000 300000 400000 600000
Число фактов
Рис. 3. Сравнение измеренного и расчетного времени вывода для операции list::intersection
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
55
БЫСТРЫЙ ЛОГИЧЕСКИЙ ВЫВОД В СРЕДЕ ПРОГРАММИРОВАНИЯ …
Заключение
Замена наивного логического вывода операциями реляционной алгебры дает возможность решить проблему комбинаторной сложности задач поиска в системах искусственного интеллекта, построенных на продукционной модели знаний и, в частности, для создания интеллектуальных агентов для поиска решений в Глобальной семантической сети. В данной работе доказано, что среда программирования Prolog позволяет создавать эффективные предикаты, реализующие реляционные операции с высокой скоростью. На базе подхода, испытанного на базовых операциях реляционной алгебры, могут быть разработаны простые и эффективные предикаты для прочих операций, необходимость в которых может появиться при разработке интеллектуальных агентов для Глобальной семантической сети. Предикаты для операций реляционной алгебры, апробированные в среде Visual Prolog, могут быть перенесены на другие диалекты языка Prolog.
Литература
1. Forgy C.L. RETE: A fast algorithm for the many pattern / many object pattern match problem // Artificial Intelligence. – 1982. – Vol. 19. – Р. 17–37.
2. Бессмертный И.А. Теоретико-множественный подход к логическому выводу в базах знаний // Научно-техн. вестник СПбГУ ИТМО. – 2010. – № 2. – С. 43–49.
3. Berners-Lee T., Hendler J., Lassila O. The Semantic Web // Scientific American Magazine. – May, 2001.
4. SWRL: A Semantic Web Rule Language. Combining OWL and RuleML. W3C Member Submission 21 May 2004 [Электронный ресурс]. – Режим доступа: http://www.w3.org/Submission/SWRL/, своб.
5. Дейт Дж. Введение в системы баз данных. – 8-е изд. – М.: Вильямс, 2006. – 1328 с.
Бессмертный Игорь Александрович
– Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кандидат технических наук, доцент, igor_bessmertny@hotmail.com
56 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)
УДК 004.89
БЫСТРЫЙ ЛОГИЧЕСКИЙ ВЫВОД В СРЕДЕ ПРОГРАММИРОВАНИЯ VISUAL PROLOG
И.А. Бессмертный
В статье обсуждается реализация логического вывода в системах искусственного интеллекта, построенных на продукционной модели знаний, с использованием теоретико-множественных операций в среде программирования Visual Prolog. Предлагается набор предикатов, реализующих быстрое выполнение операций реляционной алгебры. Приводятся результаты натурных экспериментов, подтверждающих существенное, не менее чем на три порядка, ускорение логического вывода для баз знаний с большим числом фактов. Ключевые слова: искусственный интеллект, реляционная алгебра, Prolog
Введение Язык программирования Prolog, имеющий встроенный механизм исчисления предикатов MODUS PONENS, является привлекательным инструментом для построения систем искусственного интеллекта, поскольку конструкции на языке Prolog максимально приближены к логическим выражениям, которыми может быть описана решаемая проблема. Обратной стороной изящности Prolog-программ является их низкая производительность в связи с тем, что резолюция цели достигается путем «наивного» логического вывода, т.е. перебора всех возможных вариантов, а значит, обхода всех ветвей на дереве решений. 50 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)
И.А. Бессмертный
Существующие методы ускорения логического вывода в системах искусственного интеллекта, построенных на продукционной модели знаний, связаны с предварительной обработкой правил. Наиболее известным является алгоритм Rete [1], в котором для каждого условия правила строится список фактов, удовлетворяющих данному условию. Списки фактов образуют префиксное дерево, которое должно создаваться для каждого правила. Таким образом, быстродействие обеспечивается многократным дублированием фактов. Узким местом алгоритма Rete является необходимость обновления всех префиксных деревьев при каждой модификации базы фактов, что обусловливает ограниченное применение алгоритма.
В работе [2] предлагается индексация и предварительный отбор фактов, релевантных правилам. Эффективность данного подхода существенно зависит от доли фактов, участвующих в каждом правиле: чем она выше, тем меньше выигрыш от использования индексов.
Необходимость в создании машины логического вывода (интеллектуального агента) предусмотрена в концепции Глобальной семантической сети (Semantic Web) [3], которая базируется на продукционной модели знаний. При этом набор операций над фактами, предусматриваемый в языках представления правил, в частности, SWRL, является ограниченным, поскольку элементами правил (атомами) могут быть только C(x), P(x, y), sameAs(x, y) или differentFrom(x, y), где С – свойство, P – отношение, x, y – переменные [4]. Как показано в работе [2], интерпретация правил может быть заменена операциями реляционной алгебры над кортежами значений переменных, хранящихся в фактах. Хранение фактов и логический вывод могут быть перенесены в среду систем управления базами данных (СУБД). Использование СУБД для построения систем искусственного интеллекта порождает новые проблемы: необходимость трансляции правил в язык запросов SQL, преобразования имен и др. В этой связи представляет интерес логический вывод с использованием реляционных операций в среде языка программирования Prolog как наиболее удобной для манипулирования знаниями.
Реализация быстрых реляционных операций в среде Visual Prolog
Набор базовых операций реляционной алгебры включает в себя пересечение X Y (INTERSECT), вычитание X Y (DIFFERENCE), объединение X Y (UNION), соединение (JOIN), проекцию, дополнение (NOT) и фильтрацию (WHERE) [5]. Реализация над двумя списками X={x} и Y={y} операций пересечения, разности и объединения предполагает в среднем развертывание nxny/2 вершин дерева поиска (список Y сканируется до первого появления искомого значения), где nx, ny – количество фактов в множествах X и Y соответственно. Для операции соединения развертывается nxny вершин, поскольку соединение представляет собой декартово произведение с фильтрацией. Операции дополнения и фильтрации в языке SWRL являются простыми, поскольку здесь не допускается вложенный поиск, и требуют развертывания только nx вершин.
Ниже приведен текст предиката list:: intersection, входящего в состав библиотеки list языка Visual Prolog 7.2 (http://www.visual-prolog.com/). Здесь и далее вместо множеств мы будем говорить о списках. Во-первых, список – это агрегат данных, которым манипулирует Prolog; во-вторых, списки допускают повторяющиеся значения, сохранение которых необходимо в некоторых операциях.
predicates
intersection: (Elem* ListA, Elem* ListB) Elem* IntersectionAB.
clauses
intersection([],_) = [].
intersection([X|Xs],Ys) = [X|intersection(Xs,Ys)]:-
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
51
БЫСТРЫЙ ЛОГИЧЕСКИЙ ВЫВОД В СРЕДЕ ПРОГРАММИРОВАНИЯ …
isMember(X,Ys), !.
intersection([_|Xs],Ys) = intersection(Xs,Ys). Предикат list::isMember вызывает извлечение в среднем ny/2 элементов списка Y,
для каждого элемента списка X, что и обусловливает низкую скорость работы данного предиката.
Отсортируем списки X={x} и Y={y} по возрастанию значений. В этом случае оба списка можно обрабатывать совместно, и дерево поиска будет состоять из nx+ny вершин. Таким образом, ожидаемое ускорение обусловлено переходом от квадратичной к линейной зависимости сложности поиска от числа фактов. Предикат нахождения пересечения отсортированных списков intersectSorted представлен ниже.
predicates
intersectSorted : (Elem* ListX, Elem* ListY) Elem* IntersectionXY.
clauses
intersectSorted([],_) = [] :-!.
intersectSorted(_,[]) = [] :-!.
intersectSorted([Y|Xs],[Y|Ys]) = [Y|intersectSorted(Xs,[Y|Ys])] :-!.
intersectSorted([X|Xs],[Y|Ys]) = intersectSorted([X|Xs],Ys) :- X>Y,!.
intersectSorted([_|Xs],[Y|Ys]) = intersectSorted(Xs,[Y|Ys]). Похожим образом реализуется операция вычитания множеств X Y differenceSorted:
predicates
differenceSorted : (Elem* ListX, Elem* ListY) Elem* ListXExceptListY.
clauses
differenceSorted([],_) = [] :-!.
differenceSorted(R,[]) = R :-!.
differenceSorted([X|Xs],[X|Ys]) = differenceSorted(Xs,[X|Ys]) :-!.
differenceSorted([X|Xs],[Y|Ys]) = [X|differenceSorted(Xs,[Y|Ys])] :- X Elem* UnionXY.
clauses
unionSorted([],R) = R :-!.
unionSorted(R,[]) = R :-!.
unionSorted([X|Xs],[X|Ys]) = unionSorted(Xs,[X|Ys]) :-!.
unionSorted([X|Xs],Ys) = [X|unionSorted(Xs,Ys)]. Наиболее часто в процессе интерпретации условий правил требуется соединение
двух множеств кортежей (x1, x2, xm) и (y1, y2, ..., yk) по совпадению значений переменных xi = yj. В реляционной алгебре данной функции соответствует операция INNER JOIN. Количество развертываемых вершин дерева поиска для данной операции в случае наивного вывода составляет nxny ,а для соединения отсортированных списков
N = nx + ny+ SUM(nxinyj, xi=yj, (nxi >1 nyj >1)),
(1)
где nxi, nyj, – количество повторяющихся значений в первом и втором списке соответ-
ственно. Если пренебречь возможностью повторения одних и тех же значений в обоих
списках (nxi>1 nyj>1), а также случаями (nxi >1 nyj=0) и (nxi=0 nyj>1), то формулу (1) можно упростить:
N = nx + ny+ dx+ dy,
(2)
52 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)
И.А. Бессмертный
где dx, dy, – число дубликатов значений в списках X и Y соответственно. Ниже представлен текст предиката, реализующего данную операцию над двумя множествами кортежей {(x1, x2)} и {(y1, y2)} по совпадению x1 = y1.
predicates
innerJoinSorted:(t{X,X}* ListX, t{X,X}* ListY, t{X,X,X}* JoinXY) t{X,X,X}* JoinXYfinal. innerJoinSorted1:(t{X,X}, t{X,X}*, t{X,X}*, t{X,X,X}*) procedure (i,i,o,o).
clauses innerJoinSorted([], _, Final) = Final :- !. innerJoinSorted([t(X1,X2)|Xresidue],Y,In)=innerJoinSorted(Xresidue,YtoLookUp,Out) :innerJoinSorted1(t(X1, X2), Y, YtoLookUp, XY), Out = list::append(XY, In).
innerJoinSorted1(_, [], [], []) :- !. innerJoinSorted1(t(X1,_X2),[t(Y1,Y2)|Yresidue], [t(Y1,Y2)|Yresidue],[]) :-X1 Y1, !, innerJoinSorted1(t(X1,X2), Yresidue, YlookUp, XY).
innerJoinSorted1(t(X1,X2),[t(Y1,Y2)|Yresidue],[t(Y1,Y2)|YlookUp], [t(X1,X2,Y2)|XY]) :innerJoinSorted1(t(X1,X2),Yresidue,YlookUp,XY).
В табл. 1 обобщены данные о каждой из реляционных операций и их сложности, измеряемой числом развертываемых вершин дерева поиска.
Операция
Пересечение X Y Разность X Y Объединение X Y =(X-Y)+(Y-X)+(X Y) Соединение
Оператор в СУБД
Встроенный предикат в
Visual Prolog
INTERSECT list::intersection
MINUS list::difference
UNION
list::union
JOIN
отсутствует
Сложность встроенного предиката
nxny/2 nxny/2 nxny/2
nxny
Сложность быстрого предиката
nx + ny nx + ny nx + ny
nx + ny+ dx+ dy
Таблица 1. Сложность операций реляционной алгебры
Исследование быстродействия
Для исследования быстродействия использовались множества положительных чисел, полученные с помощью генератора случайных чисел. Предикат, формирующий список положительных чисел, представлен ниже.
predicates
generate : (positive, positive, positive*) procedure (i,i,o).
clauses
generate(0,_,[]) :- !.
generate(N,Range,[Num1|Residue]) :- Num1=math::random(Range),
generate(N-1,Range,Residue). Наивный логический вывод был реализован итеративными предикатами, приведенными ниже. Здесь f1(X), f2(X) и f(X) – исходные и результирующий факт соответственно.
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
53
БЫСТРЫЙ ЛОГИЧЕСКИЙ ВЫВОД В СРЕДЕ ПРОГРАММИРОВАНИЯ …
% Пересечение
isec() :- f1(X), f2(X), assert(f(X)), fail.
isec(). % Вычитание
idiff() :- f1(X), not(f2(X)), assert(f(X)), fail.
idiff(). % Соединение
ijoin() :- f1(t(X1,X2)), f2(t(X1,Y2)), assert(f3(t(X1,X2,Y2))), fail.
ijoin(). Приведенные в табл. 2 и на рис. 1 результаты натурных экспериментов пока-
зывают, что логический вывод с использованием реляционных операций над отсортированными множествами на три-четыре порядка быстрее наивного вывода, в то время как предикаты реляционной алгебры дают ускорение не более, чем на порядок по сравнению с наивным выводом.
Число фактов Время сортировки списков, с Время сортировки кортежей, с Пересечение списков, наивный вывод, с Пересечение списков, библ.предикат, с Пересечение быстрый предикат, с Объединение списков, библ.предикат, с Объединение списков, быстрый предикат, с Вычитание списков, быстрый предикат, с Соединение кортежей, наивный вывод, с Соединение кортежей, быстрый предикат, с
100000 3,1 3,73 360 1400 0,08 2020 0,09 0,09 316 0,26
200000 4,5 6,5 1536 6530 0,15 7203 0,28 0,17 1804 0,55
400000 14,4 18,11 5800 22605 0,33 22563 0,56 0,36 6600 1,4
800000 30,6 36
1600000 65,89 75
0,73
1,13 1,2 23400 2,5
1,41
2,13 2,34
5,4
Таблица 2. Результаты натурных экспериментов
100000
Время сортиров ки списков , с
10000 1000 100
Время сортиров ки кортежей, с Пересечение списков , наив ный в ыв од, с Пересечение списков , библ.предикат, с Пересечение быстрый предикат, с
Время, с
10
1
0,1
0,01 100000
200000
400000
800000
Число фактов
1600000
Объединение списков , библ.предикат, с Объединение списков , быстрый предикат, с Вычитание списков , быстрый предикат, с Соединение кортежей, наив ный в ыв од, с Соединение кортежей, быстрый предикат, с
Рис.1. Результаты натурных испытаний методов логического вывода
54 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)
И.А. Бессмертный
Сортировка стандартным предикатом list::sort демонстрирует высокую скорость,
поэтому даже если считать, что сортировка выполняется перед каждой реляционной
операцией, выполнение таких операций над отсортированными списками более чем на
два порядка быстрее, чем наивный логический вывод.
Предложенные здесь Prolog-предикаты не требуют больших объемов оперативной
памяти, поскольку во всех предикатах хвостовая рекурсия (tail recursion) отсутствует.
Объем памяти, занимаемый тестовой программой за вычетом памяти для хранения базы
фактов, в течение всего процесса обработки тестовых фактов не превышает 10 Мб.
Натурные испытания позволили также проверить применимость формул, приве-
денных в табл. 1, для оценки времени вывода в предположении о том, что время вывода
T = tN,
(3)
где t – время развертывания одной вершины дерева поиска, N – число вершин. Рис. 2 и
3 демонстрируют, что данная формула может применяться как для наивного логическо-
го вывода, так и для операций реляционной алгебры, причем время t составляет поряд-
ка 4 10-8с для наивного вывода, 2,85 10-7с для стандартных предикатов, реализующих
реляционные операции, и 4,4 10-7с для быстрых предикатов.
Время, с
1,6
1,4
1,2
1 0,8 Измеренное время, с
Расчетное время, с 0,6
0,4
0,2
0
100000 150000 200000 300000 400000 600000 11628000000000000000
Число фактов
Рис. 2. Сравнение измеренного и расчетного времени вывода для операции быстрого пересечения
25000
20000
Время,с
15000 10000
Измеренное в ремя, с Расчетное в ремя, с
5000
0 100000 150000 200000 300000 400000 600000
Число фактов
Рис. 3. Сравнение измеренного и расчетного времени вывода для операции list::intersection
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 3(67)
55
БЫСТРЫЙ ЛОГИЧЕСКИЙ ВЫВОД В СРЕДЕ ПРОГРАММИРОВАНИЯ …
Заключение
Замена наивного логического вывода операциями реляционной алгебры дает возможность решить проблему комбинаторной сложности задач поиска в системах искусственного интеллекта, построенных на продукционной модели знаний и, в частности, для создания интеллектуальных агентов для поиска решений в Глобальной семантической сети. В данной работе доказано, что среда программирования Prolog позволяет создавать эффективные предикаты, реализующие реляционные операции с высокой скоростью. На базе подхода, испытанного на базовых операциях реляционной алгебры, могут быть разработаны простые и эффективные предикаты для прочих операций, необходимость в которых может появиться при разработке интеллектуальных агентов для Глобальной семантической сети. Предикаты для операций реляционной алгебры, апробированные в среде Visual Prolog, могут быть перенесены на другие диалекты языка Prolog.
Литература
1. Forgy C.L. RETE: A fast algorithm for the many pattern / many object pattern match problem // Artificial Intelligence. – 1982. – Vol. 19. – Р. 17–37.
2. Бессмертный И.А. Теоретико-множественный подход к логическому выводу в базах знаний // Научно-техн. вестник СПбГУ ИТМО. – 2010. – № 2. – С. 43–49.
3. Berners-Lee T., Hendler J., Lassila O. The Semantic Web // Scientific American Magazine. – May, 2001.
4. SWRL: A Semantic Web Rule Language. Combining OWL and RuleML. W3C Member Submission 21 May 2004 [Электронный ресурс]. – Режим доступа: http://www.w3.org/Submission/SWRL/, своб.
5. Дейт Дж. Введение в системы баз данных. – 8-е изд. – М.: Вильямс, 2006. – 1328 с.
Бессмертный Игорь Александрович
– Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кандидат технических наук, доцент, igor_bessmertny@hotmail.com
56 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 3(67)