В задачах искусственного интеллекта применяются различные модели представления знаний и методы вычислений — мягкие вычисления, генетические алгоритмы, нейросети, логические модели и другие подходы. Все эти методы основаны на символьных вычислениях и поэтому могут быть реализованы на основе языка PROLOG.
Здесь мы рассмотрим методы построения интеллектуальных систем на основе логического подхода, который наиболее близок природе логического программирования и часто применяется в экспертных системах.
В основе логического вывода лежит математическое понятие «формальная система (ФС)». ФС — это совокупность абстрактных объектов, связанных между собой определенными правилами. Вспомним определение. Формальная система F задана, если определена четверка:
F = (Al, Sn, Ax, Ru)
Al – алфавит – конечное множество символов;
Sn – синтаксис – процедура построения правильно построенных формул ФС;
Ax – аксиомы – совокупность правильных формул, заданных изначально;
Ru – правила вывода – конечное множество правил, позволяющих получать новые формулы из других формул ФС.
Всякая программа на языке ПРОЛОГ является ФС, которых в одной программе может быть несколько. В ПРОЛОГе важную роль играет понятие унификации, позволяющее более широко применять правила ФС за счет подстановки параметров. Хорошим примером ФС в программе является синтаксический анализатор на языке ПРОЛОГ().
ФС можно применить для порождения новых утверждений (прямой вывод) или для доказательства правильности утверждений (обратный вывод). В ПРОЛОГе можно реализовать оба варианта вывода, хотя обратный вывод реализуется непосредственно, поскольку заложен в структуру языка.
Язык логического программирования дает много интересных возможностей для решения интеллектуальных задач, т.е. требующих логического вывода для получения решения. Как правило, возможности языка по созданию различных типов прикладных систем демонстрируются на достаточно простых примерах, предназначенных больше для демонстрации парадигмы логического программирования, в учебных целях.
Для создания практически полезных прикладных систем требуется ряд свойств, отсутствующих в системе ПРОЛОГ, но которые можно в нее добавить.
На всякий случай, вспомним, что вычисление в логическом программировании состоит в поиске логического вывода. Этим термином именуют дерево, корнем которого является доказываемое утверждение, а остальные вершины содержат утверждения, связанные между собой логическим следованием. При этом терминальные вершины (листья) дерева должны быть исходными данными – утверждениями, сформулированными в условии задачи.
Построение дерева логического вывода состоит в поиске взаимосвязанных цепочек утверждений от листьев к вершине среди множества всех возможных путей от вершины к листьям. Это множество называют пространством поиска задачи.
Поиск может быть прямой – от данных к искомому и обратный – от искомого к данным. В первом подходе из условий задачи вычисляют то, что можно – новые утверждения, увеличивая тем самым количество известного о задаче.
Во втором подходе строятся гипотезы – строится последовательность, точнее дерево, гипотез, которое должна привести к известным данным.
Поскольку ПРОЛОГ основан на обратном выводе, сначала рассмотрим обратный вывод.
Для иллюстрации проблем, возникающих при построении неигрушечных экспертных систем, используем в качестве предметной области планиметрию, точнее говоря, ее небольшую часть, связанную с решением треугольников.
Рассмотрим конкретную задачу.
В равнобедренном треугольнике проведена высота из вершины, расположенной между равными сторонами. В образовавшемся внутреннем треугольнике снова проведена высота, затем в новом треугольнике еще высота, и т.д. всего – 10 высот. Известны длина основания треугольника AC и боковой стороны BC. Нужно решить любой треугольник, образованный проведенными высотами.
Представление основных объектов может быть таким:
Для простоты изложения рассмотрим вычисление второй высоты треугольника – DE. Запишем условия задачи средствами языка ПРОЛОГ:
s(1,exist(d,tri(a,b,c))).
s(2,height(seg(b,d),tri(a,b,c))).
s(3,height(seg(d,e),tri(b,c,d))).
s(4,height(seg(f,e),tri(b,e,d))).
s(5,height(seg(f,g),tri(f,e,d))).
s(6,height(seg(h,g),tri(f,g,e))).
s(7,height(seg(h,i),tri(g,h,e))).
s(8,height(seg(i,k),tri(h,i,e))).
s(9,height(seg(k,l),tri(i,k,e))).
s(10,height(seg(l,m),tri(l,k,e))).
s(11,height(seg(m,n),tri(m,l,e))).
s(12,equal(seg(a,b),seg(b,c))).
s(13,length(seg(a,b),10)).
s(14,length(seg(a,c),16)).
s(15,length(seg(d,e),x)).
Для обеспечения нумерации условий задачи предикаты записаны в дополнительных скобках в виде s(N,P).
Последняя строка в исходных данных задачи определяет цель – утверждение, которое необходимо доказать. В нашем случае цель length(seg(d,e),x) содержит переменную х, что позволяет – вычислить значение длины отрезка DE.
Одна из основных трудностей в применении ПРОЛОГа для реализации коммерческих систем – возникновение зацикливания программы в процессе вычислений. Причиной этого может быть не ошибка в программе, а рекурсивность свойств объектов предметной области и, соответственно – рекурсивность правил логического вывода.
Например, в правилах логического вывода для решения треугольников неизбежно происходит обращение к аналогичным правилам.
Пример 1, Вычисление длины отрезка в треугольнике.
Вычисление длины стороны треугольника через высоту и площадь:
length(seg(A,C),L):-
height(seg(B,D),tri(A,B,C)),
length(seg(B,D),L1),
area(tri(A,B,C),S1),
L is (2*S1)/L1.
Вычисление длины высоты треугольника через основание и площадь:
length(seg(B,D),L):-
height(seg(B,D),tri(A,B,C)),
length(seg(A,C),L1),
area(tri(A,B,C),S1),
L is (2*S1)/L1.
Для решения нашей задачи достаточно четырех правил для вычисления длины отрезка – вычисление длины отрезка, образованного высотой равнобедренного треугольника, теорема Пифагора, вычисление длины высоты через площадь и основание треугольника, получения значения от равного отрезка.
В процессе поиска решения все возникающие цели нумеруются. Все рассмотренные в процессе поиска решения цели образуют пространство поиска задачи, из которого лишь небольшая часть попадает в результирующее дерево логического вывода.
Решение — дерево логического вывода для нашей задачи можно записать в виде списка пронумерованных предикатов следующим образом:
Каждый предикат представляет собой цель, выведенную в процессе решения задачи и имеет номер, присвоенный ему в процессе вычислений. Справа, в квадратных скобках, записан список номеров предикатов, использованных в одноименном правиле для получения результата.
То же дерево в графическом представлении имеет следующий вид:
Как можно видеть из рисунка, все терминальные вершины дерева – утверждения из исходных данных.
Приведем текстовую интерпретацию полученного решения.
1)Для вычисления длины отрезка seg(d,e) (331) использовано правило: если искомый отрезок является высотой в треугольнике, то его длина равна площади треугольника деленной на основание и умноженной на два. Аргументы для этого правила получены из целей с номерами 66,332,3,
Площадь треугольника cdb равна 24 – цель 332. Длина основания bc равна 10 – цель 66. Искомая длина равна 2*(24/10) = 4.8. Отрезок de является высотой треугольника cdb – цель 3 (исходные данные).
2)Длина отрезка bc (66) вычислена из правила – если искомый отрезок равен другому отрезку с известной длиной, то искомая длина равна длина равного отрезка.
В нашем случае искомый отрезок bc равен отрезку ab – это задано в исходных данных – цель 12, длина отрезка ab задана в утверждении 13.
3) Площадь треугольника cdb (332) вычисляется по правилу для прямоугольных треугольников по длинам катетов, аргументы заданы целями 46,44, 333, 334.
Прямоугольность треугольника cdb (333) следует из того, что отрезок bd является высотой в треугольнике abc (2). Отсюда следует определение отрезков, которые являются катетами в этом треугольнике – bd и dc (334). Далее следует вычисление длин катетов (44) и (46).
4)Длина катета db (44) вычисляется через прямоугольный треугольник bdc из целей с номерами 77,66,46,45.
Цель 77 – применение теоремы Пифагора для вычисления отрезка db. Цель 66 – вычисление длины отрезка bc. Цель 46 – длина отрезка dc. Цель 45- наличие прямоугольного треугольника dbс с искомым отрезком db.
5)Длина катета dc (46) вычисляется из целей 14, 47 по правилу отрезка при медиане треугольника. Цель 14 задана в исходных данных – длина отрезка ac, на который опущена медиана bd (47). Применяется правило – высота в равнобедренном треугольнике, опущенная на его основание, является медианой.
Поскольку в приведенном примере данные получены в результате применения конкретной логической программы, можно предположить, что объем поиска составил 334 цели, из которых 13 составили необходимое решение задачи.
Для более сложного случая, например для вычисления десятой высоты в нашем треугольнике – отрезка LM, объем поиска составил 1667 целей, а в процессе поиска вывода было получено 138 утверждений, из которых далеко не все вошли в искомое решение. Незначительный объем поиска связан с тем, что было использовано всего четыре правила для вычисления длины отрезка.
Мы рассмотрели упрощенный пример для иллюстрации основных аспектов решения задач, требующих логического вывода. Если же попытаться описать все теоремы планиметрии для вычисления длины отрезка – подобие и равенство треугольников, тригонометрические функции, составные отрезки, объем необходимых вычислений возрастает на порядки и здесь понадобится иметь дополнительные возможности, чтобы справиться со всеми возникающими сложностями.
Для того, чтобы решать достаточно объемные интеллектуальные задачи недостаточно обычного языка ПРОЛОГ, поскольку в нем отсутствует ряд свойств, без которых сложно построить практически полезную программу. Эти усовершенствования системы языка ПРОЛОГ можно разделить на две группы – управление поиском вывода (логические) и технологические.
Необходимы следующие усовершенствования управления поиском:
Заключение
Мы рассмотрели основные аспекты построения формальной системы в виде программы для решения логических задач. ФС решает задачи путем полного перебора вариантов.
Если приведенным здесь способом описать правила для всех необходимых теорем планиметрии, пространство поиска будет неподъемным для среднего компьютера, а может быть и суперкомпьютера. Однако мы хорошо знаем, что толковый школьник решит почти любую решаемую задачу за приемлемое время, не выполняя слишком большого перебора.
Как он это делает? За счет анализа и планирования решения, намечая самые перспективные подходы и не рассматривая заведомо бесполезные. Знания, которыми он воспользуется для планирования решения, не являются геометрическими теоремами – это и есть те знания, которые называют экспертными – знания о методах поиска решения, которые обычно эксперт получает в процессе обучения и вырабатывает самостоятельно, в процессе приобретения опыта.
Вывод – одна ФС не является экспертной системой. Для ЭС нужно объединить несколько ФС. В дальнейшем рассмотрим более подробно, как это сделать.
Здесь мы рассмотрим методы построения интеллектуальных систем на основе логического подхода, который наиболее близок природе логического программирования и часто применяется в экспертных системах.
В основе логического вывода лежит математическое понятие «формальная система (ФС)». ФС — это совокупность абстрактных объектов, связанных между собой определенными правилами. Вспомним определение. Формальная система F задана, если определена четверка:
F = (Al, Sn, Ax, Ru)
Al – алфавит – конечное множество символов;
Sn – синтаксис – процедура построения правильно построенных формул ФС;
Ax – аксиомы – совокупность правильных формул, заданных изначально;
Ru – правила вывода – конечное множество правил, позволяющих получать новые формулы из других формул ФС.
Всякая программа на языке ПРОЛОГ является ФС, которых в одной программе может быть несколько. В ПРОЛОГе важную роль играет понятие унификации, позволяющее более широко применять правила ФС за счет подстановки параметров. Хорошим примером ФС в программе является синтаксический анализатор на языке ПРОЛОГ().
ФС можно применить для порождения новых утверждений (прямой вывод) или для доказательства правильности утверждений (обратный вывод). В ПРОЛОГе можно реализовать оба варианта вывода, хотя обратный вывод реализуется непосредственно, поскольку заложен в структуру языка.
Язык логического программирования дает много интересных возможностей для решения интеллектуальных задач, т.е. требующих логического вывода для получения решения. Как правило, возможности языка по созданию различных типов прикладных систем демонстрируются на достаточно простых примерах, предназначенных больше для демонстрации парадигмы логического программирования, в учебных целях.
Для создания практически полезных прикладных систем требуется ряд свойств, отсутствующих в системе ПРОЛОГ, но которые можно в нее добавить.
На всякий случай, вспомним, что вычисление в логическом программировании состоит в поиске логического вывода. Этим термином именуют дерево, корнем которого является доказываемое утверждение, а остальные вершины содержат утверждения, связанные между собой логическим следованием. При этом терминальные вершины (листья) дерева должны быть исходными данными – утверждениями, сформулированными в условии задачи.
Построение дерева логического вывода состоит в поиске взаимосвязанных цепочек утверждений от листьев к вершине среди множества всех возможных путей от вершины к листьям. Это множество называют пространством поиска задачи.
Поиск может быть прямой – от данных к искомому и обратный – от искомого к данным. В первом подходе из условий задачи вычисляют то, что можно – новые утверждения, увеличивая тем самым количество известного о задаче.
Во втором подходе строятся гипотезы – строится последовательность, точнее дерево, гипотез, которое должна привести к известным данным.
Поскольку ПРОЛОГ основан на обратном выводе, сначала рассмотрим обратный вывод.
Для иллюстрации проблем, возникающих при построении неигрушечных экспертных систем, используем в качестве предметной области планиметрию, точнее говоря, ее небольшую часть, связанную с решением треугольников.
Рассмотрим конкретную задачу.
В равнобедренном треугольнике проведена высота из вершины, расположенной между равными сторонами. В образовавшемся внутреннем треугольнике снова проведена высота, затем в новом треугольнике еще высота, и т.д. всего – 10 высот. Известны длина основания треугольника AC и боковой стороны BC. Нужно решить любой треугольник, образованный проведенными высотами.
Представление основных объектов может быть таким:
- seg(A,B) – отрезок с концевыми точками A и B;
- tri(A,B,C) – треугольник с вершинами А, В, С;
- length(seg(A,B),L) – длина отрезка;
- equal(tri(A,B,C),tri(X,Y,Z)) – равенство треугольников.
Для простоты изложения рассмотрим вычисление второй высоты треугольника – DE. Запишем условия задачи средствами языка ПРОЛОГ:
s(1,exist(d,tri(a,b,c))).
s(2,height(seg(b,d),tri(a,b,c))).
s(3,height(seg(d,e),tri(b,c,d))).
s(4,height(seg(f,e),tri(b,e,d))).
s(5,height(seg(f,g),tri(f,e,d))).
s(6,height(seg(h,g),tri(f,g,e))).
s(7,height(seg(h,i),tri(g,h,e))).
s(8,height(seg(i,k),tri(h,i,e))).
s(9,height(seg(k,l),tri(i,k,e))).
s(10,height(seg(l,m),tri(l,k,e))).
s(11,height(seg(m,n),tri(m,l,e))).
s(12,equal(seg(a,b),seg(b,c))).
s(13,length(seg(a,b),10)).
s(14,length(seg(a,c),16)).
s(15,length(seg(d,e),x)).
Для обеспечения нумерации условий задачи предикаты записаны в дополнительных скобках в виде s(N,P).
Последняя строка в исходных данных задачи определяет цель – утверждение, которое необходимо доказать. В нашем случае цель length(seg(d,e),x) содержит переменную х, что позволяет – вычислить значение длины отрезка DE.
Одна из основных трудностей в применении ПРОЛОГа для реализации коммерческих систем – возникновение зацикливания программы в процессе вычислений. Причиной этого может быть не ошибка в программе, а рекурсивность свойств объектов предметной области и, соответственно – рекурсивность правил логического вывода.
Например, в правилах логического вывода для решения треугольников неизбежно происходит обращение к аналогичным правилам.
Пример 1, Вычисление длины отрезка в треугольнике.
Вычисление длины стороны треугольника через высоту и площадь:
length(seg(A,C),L):-
height(seg(B,D),tri(A,B,C)),
length(seg(B,D),L1),
area(tri(A,B,C),S1),
L is (2*S1)/L1.
Вычисление длины высоты треугольника через основание и площадь:
length(seg(B,D),L):-
height(seg(B,D),tri(A,B,C)),
length(seg(A,C),L1),
area(tri(A,B,C),S1),
L is (2*S1)/L1.
Для решения нашей задачи достаточно четырех правил для вычисления длины отрезка – вычисление длины отрезка, образованного высотой равнобедренного треугольника, теорема Пифагора, вычисление длины высоты через площадь и основание треугольника, получения значения от равного отрезка.
В процессе поиска решения все возникающие цели нумеруются. Все рассмотренные в процессе поиска решения цели образуют пространство поиска задачи, из которого лишь небольшая часть попадает в результирующее дерево логического вывода.
Решение — дерево логического вывода для нашей задачи можно записать в виде списка пронумерованных предикатов следующим образом:
- (78) hypot(tri(d,b,c),seg(b,c)) [79]
- (45) exist_rect(tri(d,b,c),seg(d,b)) [2]
- (46) length(seg(d,c),8) [14,47]
- (66) length(seg(b,c),10) [13,12]
- (77) pif_length([seg(d,b),6],[[seg(d,c),8],[seg(b,c),10]]) [78]
- (47) median(tri(a,b,c),seg(b,d)) [2,48]
- (333) rectangle(tri(c,d,b),_2F28) [2]
- (334) catets(tri(c,d,b),[seg(b,d),seg(d,c)]) [78]
- (44) length(seg(d,b),6) [77,66,46,45]
- (46) length(seg(d,c),8) [14,47]
- (332) area(tri(c,d,b),24) [46,44,334,333]
- (66) length(seg(b,c),10) [13,12]
- (331) length(seg(d,e),4.8) [66,332,3]
Каждый предикат представляет собой цель, выведенную в процессе решения задачи и имеет номер, присвоенный ему в процессе вычислений. Справа, в квадратных скобках, записан список номеров предикатов, использованных в одноименном правиле для получения результата.
То же дерево в графическом представлении имеет следующий вид:
Как можно видеть из рисунка, все терминальные вершины дерева – утверждения из исходных данных.
Приведем текстовую интерпретацию полученного решения.
1)Для вычисления длины отрезка seg(d,e) (331) использовано правило: если искомый отрезок является высотой в треугольнике, то его длина равна площади треугольника деленной на основание и умноженной на два. Аргументы для этого правила получены из целей с номерами 66,332,3,
Площадь треугольника cdb равна 24 – цель 332. Длина основания bc равна 10 – цель 66. Искомая длина равна 2*(24/10) = 4.8. Отрезок de является высотой треугольника cdb – цель 3 (исходные данные).
2)Длина отрезка bc (66) вычислена из правила – если искомый отрезок равен другому отрезку с известной длиной, то искомая длина равна длина равного отрезка.
В нашем случае искомый отрезок bc равен отрезку ab – это задано в исходных данных – цель 12, длина отрезка ab задана в утверждении 13.
3) Площадь треугольника cdb (332) вычисляется по правилу для прямоугольных треугольников по длинам катетов, аргументы заданы целями 46,44, 333, 334.
Прямоугольность треугольника cdb (333) следует из того, что отрезок bd является высотой в треугольнике abc (2). Отсюда следует определение отрезков, которые являются катетами в этом треугольнике – bd и dc (334). Далее следует вычисление длин катетов (44) и (46).
4)Длина катета db (44) вычисляется через прямоугольный треугольник bdc из целей с номерами 77,66,46,45.
Цель 77 – применение теоремы Пифагора для вычисления отрезка db. Цель 66 – вычисление длины отрезка bc. Цель 46 – длина отрезка dc. Цель 45- наличие прямоугольного треугольника dbс с искомым отрезком db.
5)Длина катета dc (46) вычисляется из целей 14, 47 по правилу отрезка при медиане треугольника. Цель 14 задана в исходных данных – длина отрезка ac, на который опущена медиана bd (47). Применяется правило – высота в равнобедренном треугольнике, опущенная на его основание, является медианой.
Поскольку в приведенном примере данные получены в результате применения конкретной логической программы, можно предположить, что объем поиска составил 334 цели, из которых 13 составили необходимое решение задачи.
Для более сложного случая, например для вычисления десятой высоты в нашем треугольнике – отрезка LM, объем поиска составил 1667 целей, а в процессе поиска вывода было получено 138 утверждений, из которых далеко не все вошли в искомое решение. Незначительный объем поиска связан с тем, что было использовано всего четыре правила для вычисления длины отрезка.
Мы рассмотрели упрощенный пример для иллюстрации основных аспектов решения задач, требующих логического вывода. Если же попытаться описать все теоремы планиметрии для вычисления длины отрезка – подобие и равенство треугольников, тригонометрические функции, составные отрезки, объем необходимых вычислений возрастает на порядки и здесь понадобится иметь дополнительные возможности, чтобы справиться со всеми возникающими сложностями.
Для того, чтобы решать достаточно объемные интеллектуальные задачи недостаточно обычного языка ПРОЛОГ, поскольку в нем отсутствует ряд свойств, без которых сложно построить практически полезную программу. Эти усовершенствования системы языка ПРОЛОГ можно разделить на две группы – управление поиском вывода (логические) и технологические.
Необходимы следующие усовершенствования управления поиском:
- защита от зацикливания;
- сохранение созданного вывода;
- возможность работать с большими объемами правил;
- сохранение трассы поиска вывода в пространстве состояний предметной области для отладки;
- управление объемом вычислений для защиты от излишних неэффективных поисков при наличии ошибки или отсутствии решения;
- построение объяснения полученного решения.
Технологические усовершенствования: - интеграция с процедурными языками программирования;
- интеграция со средствами операционной системы;
- эффективность кода;
- возможность создания автономных программ.
Большинство современных систем языка ПРОЛОГ имеют компилятор и другие средства, которые обеспечивают возможность создания прикладных программ, применимых без интерпретатора языка ПРОЛОГ, совместно с программами на других языках программирования или автономно.
Для получения усовершенствований поиска необходимо в каждое правило ПРОЛОГа в прикладной программе вставить дополнительные проверки и, соответственно, дополнительные аргументы.
Чтобы не делать это вручную, можно использовать специальные инструментальные системы. Научно-производственная фирма «Semantics Research» разработала такую систему под названием Exxlog, которую можно скачать бесплатно на сайте компании(exxlog.ru).
Заключение
Мы рассмотрели основные аспекты построения формальной системы в виде программы для решения логических задач. ФС решает задачи путем полного перебора вариантов.
Если приведенным здесь способом описать правила для всех необходимых теорем планиметрии, пространство поиска будет неподъемным для среднего компьютера, а может быть и суперкомпьютера. Однако мы хорошо знаем, что толковый школьник решит почти любую решаемую задачу за приемлемое время, не выполняя слишком большого перебора.
Как он это делает? За счет анализа и планирования решения, намечая самые перспективные подходы и не рассматривая заведомо бесполезные. Знания, которыми он воспользуется для планирования решения, не являются геометрическими теоремами – это и есть те знания, которые называют экспертными – знания о методах поиска решения, которые обычно эксперт получает в процессе обучения и вырабатывает самостоятельно, в процессе приобретения опыта.
Вывод – одна ФС не является экспертной системой. Для ЭС нужно объединить несколько ФС. В дальнейшем рассмотрим более подробно, как это сделать.