В число основных компонентов интеллектуального интерфейса между пользователем и ЭВМ входят решатели задач, позволяющие конечным пользователям решать прикладные задачи при минимальном объеме знаний о программировании. Эти задачи, как правило, плохо формализуемы, т. е. отсутствуют строгие аналитические методы их решения, и человек обычно использует интуитивные представления, эмпирические правила и эвристические соображения.
Работы в области создания решателей, реализующих некоторую формализованную схему рассуждений при том или ином способе представления знаний, ведутся активно и в нашей стране, и за рубежом. Они особенно активизировались в связи с реализацией в различных странах проектов ЭВМ пятого поколения. Разработка решателей - одно из мало проработанных звеньев этих проектов.
В настоящем разделе рассматриваются перспективные подходы к построению решателей задач конечного пользователя.
Логическое программирование
К дедуктивным подходам относится прежде всего логическое программирование, в котором для представления знаний используется формальный аппарат исчисления предикатов первого порядка и его расширения.
Под исчислением (или дедуктивной системой) понимается система, в которой существует некоторое число исходных объектов (аксиом) и некоторое число правил построения (правил вывода) новых объектов из исходных и уже построенных.
При этом в исчислениях (в отличие от алгоритмов) порядок применения правил вывода может быть произвольным. Можно считать, что исчисление предикатов является расширением классического исчисления высказываний, в котором высказывание рассматривается как единое целое, не обладающее внутренней структурой, а истинность или ложность высказывания фиксирована. В исчислении предикатов основным объектом является переменное высказывание (предикат), истинность или ложность которого зависит от значений входящих в него переменных. Так, истинность предиката
«х был физиком»
зависит от значения переменной х. Если х - это П. Капица, то предикат истинен, если х - М. Лермонтов, то он ложен.
Для обозначения области значений переменных в исчислении предикатов используются два квантора:
" - квантор всеобщности ;
$ - квантор существования .
Тогда утверждение
"х Р (х)
читается так: «для всех х имеет место Р (х)»,
а утверждение
$x Q (х)
как «существует х такое, что Q (х)», где Р (х) и Q (х) — предикаты.
В исчислении как высказываний, так и предикатов существует еще одно понятие - формула.
В исчислении высказываний формулы строятся индуктивным способом, используя логические связи:
& - конъюнкция,
V - дизъюнкция,
® - импликация),
ù (отрицание).
Исчисление предикатов включает в себя все формулы исчисления высказываний, а также формулы, содержащие кроме символов высказываний предикатные символы с кванторами. Например, утверждение
" x (Р (х) ® Q(x)
читается так: : «для любого х если Р(х), то имеет место и Q(x)».
Выделенное подмножество тождественно истинных формул, истинность которых не зависит от истинности входящих в них высказываний, называется
аксиомами.
В исчислении предикатов имеется множество правил вывода. В качестве примера приведем классическое правило modus ponens:, которое читается так::
«если истинна формула А и истинно, что из А следует В, то истинна формула В».
Это правило вывода формализует основной закон дедуктивных систем: из истинных посылок всегда следуют истинные заключения. Аксиомы и правила вывода исчисления предикатов первого порядка задают основу формальной дедуктивной системы, в которой происходит формализация схемы рассуждения в логическом программировании.
Решаемая задача представляется в виде утверждений (аксиом) F1, F2, ..., Fn исчисления предикатов первого порядка. Цель задачи В также записывается в виде утверждения, справедливость которого следует установить или опровергнуть на основании аксиом и правил вывода формальной системы. Тогда решение задачи (достижение цели задачи) сводится к выяснению логического следования (выводимости) целевой формулы В из заданного множества формул (аксиом)
F1, F2, ..., Fn. Такое выяснение равносильно доказательству общезначности (тождественно-истинности) формулы
F1& F2& ... &Fn ®B
или невыполнимости (тождественно-ложности) формулы
F1& F2& ... &Fn ®ù B
3.2. Принцип резолюций
Из практических соображений удобнее использовать доказательство от противного, т. е. доказывать невыполнимость формулы. На доказательстве от противного основано и ведущее правило вывода, используемое в логическом программировании, - принцип резолюций. При использовании его формулы исчисления предикатов с помощью несложных преобразований приводятся к так называемой дизъюнктивной форме, т. е. представляются в виде набора дизъюнктов.
под дизъюнктом понимается дизъюнкция литералов, каждый из которых является либо предикатом, либо отрицанием предиката.
Приведем пример дизъюнкта:
(" x) (Р (х, с1) V ù Q (х,с2)). (3.1)
Пусть предикат Р - уважать, предикат Q - знать, константа с1- Ключевский, а константа с2 - история. Тогда выражение (3.1) перепишется:
(" x) (уважать (х, Ключевский) V ù знать (х, история)). (3.2)
Дизъюнкты, используемые в логическом программировании, можно упростить следующим образом: кванторы всеобщности опустить, предикаты переписать в бес
скобочном виде, а связку V ù заменить на импликацию (®) или слово «если». Тогда выражение (3.2) примет такой вид:
х уважать Ключевский, если х знать историю,
что читается так: «каждый, кто знает историю, уважает Ключевского». Кроме того, дизъюнкты, все литералы которых отрицательны, обычно переписываются в эквивалентную форму отрицательной конъюнкции. Например, формула
(" x) ( ù Р (х, с1) V ù Р (х,с2))
перепишется в виде
(" x) ù (Р (х, с1) & Р (х,с2)) (3.3)
Если в формуле (3.3) принять, что предикат Р - это «знать», а константы с1 и с2 — это «физика» и «история» соответственно, то получим
(" x) ù (знать (х, физика) & знать (х, история)). (3.4)
Выражение (3.4) в упрощенном виде можно переписать как
? х знать физика & х знать история (3.4 а)
и прочитать как запрос: «кто знает физику и историю одновременно?».
Таким образом, и условия решаемых задач (факты), и целевые утверждения задач (запросы) можно выразить в дизъюнктивной форме логики предикатов первого порядка.
Вернемся к принципу резолюции. Главная идея этого правила вывода заключается в проверке того, содержит ли множество дизъюнктов R пустой (ложный) дизъюнкт l. При положительном ответе множество R (и соответствующая ему формула) невыполнимо (противоречиво). При отрицательном ответе выводятся новые дизъюнкты до тех пор, пока не будет получен пустой дизъюнкт, что всегда будет иметь место для противоречивого R. Таким образом, принцип резолюции можно рассматривать как правило вывода, с помощью которого порождаются новые дизъюнкты из R. В общем случае каждый шаг резолюции начинается с некоторой пары дизъюнктов (предков) такой, что некоторый литерал А в одном из дизъюнктов должен быть сделан дополнительным литералу В другого дизъюнкта из пары. Заметим, что дополнительными называются литералы А и ù А. Чтобы сделать литералы А и В дополнительными, необходимо провести их унификацию, т. е. сделать их идентичными с помощью некоторой подстановки q, называемой унификатором: А q = В q. Тогда говорят, что два выбранных литерала резольвируют. Затем с помощью правила резолюции выводится новый дизъюнкт - резольвента - следующим образом. Литералы дизъюнктов-предков, за исключением тех, которые резольвировали, объединяются и к результату применяется подстановка q.
Приведем пример:
первый предок (дизъюнкт): ù Петр уважает у
второй предок (дизъюнкт): х уважает Ивана, если отец (Иван)
уважает х
резольвирующие литералы: то, что подчеркнуто
унификатор: q = (х:=Петр, у: = Иван)
резольвента: ù отец (Иван) уважает Петр
Последнее утверждение (резольвента) читается как «отец Ивана уважает Петра?»
Правило резолюции обладает свойством полноты в том смысле, что с помощью него всегда можно найти пустой дизъюнкт, если исходное множество дизъюнктов R противоречиво. Однако вследствие неразрешимости логики предикатов первого порядка для выполнимого (непротиворечивого) множества дизъюнктов процедура, основанная на принципе резолюции, может работать бесконечно долго.
Обычно резолюция применяется алогическом программировании в совокупности с прямым или обратным методом рассуждения. Прямой метод (от посылок) из посылок А, А ® В выводит заключение В (правило modus ponens). Основной недостаток прямого метода рассуждения состоит в его ненаправленности: повторные применения метода обычно приводят к резкому росту промежуточных заключений, не связанных с целевым заключением.
Обратный метод (от цели) является направленным: из желаемого заключения В и тех же посылок он выводит новое подцелевое заключение А. Каждый шаг вывода в этом случае всегда связан с первоначально поставленной целью. Для использования правила резолюции необходимо, чтобы доказательство того, что данная посылка А влечет желаемое (целевое) заключение С, было переформулировано в утверждение, что А несовместимо с ùС. Например, чтобы доказать утверждение Р из посылок Q, Q ® Р, обратное рассуждение с помощью правила резолюции выводит ù Q (из ù Р и Q ® Р), а затем выводит пустой дизъюнкт (опровержение) (из ù Q и Q).
Модифицированный принцип резолюций
Существенный недостаток принципа резолюции заключается в формировании на каждом шаге вывода множества резольвент - новых дизъюнктов, большинство из которых оказываются лишними. В связи с этим разработаны различные модификации принципа резолюции, использующие более эффективные стратегии поиска и различного рода ограничения на вид исходных дизъюнктов. В этом смысле наиболее удачной и популярной системой является система ПРОЛОГ, которая использует специальные виды дизъюнктов, называемые дизъюнктами Хорна. Кратко рассмотрим эту систему, тем более что под логическим программированием в узком смысле слова обычно понимают программирование на языке ПРОЛОГ (PROgramming in LOGic).
дизъюнктами Хорна являются дизъюнкты, имеющие не более одного положительного литерала.
Они могут быть трех типов:
(1) допущениями без условий (или фактами)
В (t)
Например, Иван нравится история
(2) условными допущениями (или импликациями) - правилами
B (t) V ù A1 (t)V ù A2(t) V ù:V ... ùAn(t),
или в эквивалентной форме
B (t) ¬ A1 (t) & A2 (t) & ... & An (t),
Например, Петр уважает х, если х нравится логика & Петр знает х;
(3) отрицаниями
ù С1(t) V ù C2 (t) V ù ... V ù Ck (t) или
ù С1(t) & C2 (t) &... & Ck (t)
Например, ù (х нравится логика & х нравится математика).
Для реализации очень важен тот факт, что дизъюнкты Хорна обладают простой процедурной интерпретацией. Дизъюнкты типа (1) и (2) интерпретируются как процедуры, а типа (3) - как целевые утверждения. Так, дизъюнкт типа (2) интерпретируется как процедура с заголовком B (t), телом которой является вызов процедур A1 (t), A2 (t), ...,
An (t), а дизъюнкт типа (3) — как последовательность вызовов процедур С1(t), C2 (t),..., Ck г.*. Тогда каждый шаг обратного рассуждения есть управление вызовом процедуры, которое начинается с выделения вызова некоторой процедуры Ci {t) из текущей цели. Затем выделяется некоторая процедура, заголовок которой (положительный литерал, например B (t) в выражении (2)) унифицируется с помощью некоторой подстановки q с выбранным вызовом Ci {t) . Далее выделяется тело процедуры (в данном примере B (t)), представляющее собой, в свою очередь, последовательность вызова других процедур (в данном примере A1 (t), A2 (t), ..., An (t)). Унификатор q применяется к результату. Процесс итеративно повторяется. Аргументы литералов (предикатов) соответствуют параметрам вызванных процедур. Унификация интерпретируется как связь данных между вызовами и процедурами .
Процесс доказательства (или вычисления) целевого утверждения S в общем случае можно представить следующим образом.
Пусть целевое утверждение S имеет вид
¬ С1, ..., Сj, ..., Ck
и в нем выделен литерал Сj, и пусть существует правило
Г = В ¬ A1, А2, ..., А n.
Тогда если q-унификатор для литералов Сj и В, то говорят, что подцель S/ = ¬q ( С1, ..., Сj-1, A1, .... An, В, Cj+1, ..., Сl)
выводится из S с помощью правила Г и подстановки q.
Получение S/ из S является элементарным шагом в языке ПРОЛОГ. Он может завершиться и неудачей, так как может не существовать унификатора для Сj и В.
Выводом (вычислением) целевого утверждения S называется последовательность промежуточных подцелей S1, S2, ..., S m такая, что Si = S и Si+1 выводима из S.
Если из подцели Sm невыводима ни одна подцель, то вычисление считается конечным. При этом если Sm - не пустой дизъюнкт, то вывод является тупиковым, а если Sm - пустой дизъюнкт, то вывод является успешным и с ним связывается подстановка
q = qm-1, qm-2, ..., q2, q1,
где qi - подстановка, с помощью которой выводима подцель Si+1 из S.
Вывод цели удобно представлять в виде дерева И/ИЛИ с корнем в целевой вершине. Напомним, что под деревом понимается графовая структура (т. е. структура, которую можно изобразить в виде вершин и связей), любые вершины-потомки которой имеют не более одной вершины-предка. Вершине типа И дерева соответствует конъюнкция условий некоторого правила (т. е. A1, А2, ... , А n), вершине типа ИЛИ соответствует вариант, когда к одному и тому же заключению (резольвенте) приводят различные правила.
В любой системе логического программирования, в том числе и в системе ПРОЛОГ, реализуется некоторая стратегия обхода дерева поиска, т. е. используется та или иная встроенная в систему стратегия поиска решения задачи. В основном эти стратегии имеют последовательный характер. В последнее время начинают появляться реализации стратегий параллельного типа. Они резко повышают эффективность систем логического программирования.
Наиболее распространенной стратегией последовательного типа является стратегия «сначала в глубину». При этом дерево поиска упорядочивается с помощью двух линейных порядков: «слева направо» для литералов цели типа (3) и «сверху вниз» для правил типа (1), (2). Тогда на каждом шаге поиска выделенным оказывается первый слева литерал цели и к нему применяется первое сверху правило. При этом запоминаются всевозможные разветвления. Если поиск заходит в тупик, то происходит возврат к месту последнего разветвления с помощью механизма backtracking. Одновременно отменяются результаты всех подстановок, сделанных после этого разветвления. Возврат осуществляется также и при успешном исходе для получения других ответов. Работа заканчивается, когда список разветвлений пуст.
Основное достоинство этой стратегии - простота ее реализации, недостаток - большой перебор для некоторых классов подцелей. Кроме того, если дерево поиска содержит бесконечную ветвь, то попав в нее, система не выйдет оттуда и правильные ответы, находящиеся правее этой цели на дереве, не будут получены.
При стратегии «сначала в ширину» дерево поиска обходится ярус за ярусом сверху вниз. Она гарантирует нахождение решения, если оно существует. Однако стратегия требует значительно большего объема памяти и поэтому получила сравнительно небольшое распространение.
Одно из достоинств языков логического программирования состоит в том, что на их основе достаточно удобно реализовать стратегии параллельного типа, причем порядок обхода дерева не столь важен; существен лишь тот факт, что должно быть обойдено все дерево. Именно последнее обстоятельство и дает принципиальную возможность вести поиск параллельно. Обычно различают два типа параллелизма: ИЛИ -параллелизм, означающий одновременное применение для выделенной подцели из цели всех правил из базы знаний, и И -параллелизм, означающий параллельную обработку одновременно всех литералов (подцелей) целевого утверждения. Кроме того, параллелизм возможен и необходим при унификации (так как эта операция применяется часто). Наибольшие перспективы имеют именно параллельные стратегии, но для их эффективной реализации необходимы соответствующие процессоры, использующие принципы параллельной архитектуры.
0 коммент.:
Отправить комментарий