Глава 4. Логический подход к построению систем ИИ Представление в компьютере неформальных процедур. Языки логического программирования Рефал, Пролог, К-системы. - презентация

1 Глава 4. Логический подход к построению систем ИИ Представление в компьютере неформальных процедур. Языки логического программирования Рефал, Пролог, К-системы. Элементы нечеткой логики. Представление в компьютере неформальных процедур. Языки логического программирования Рефал, Пролог, К-системы. Элементы нечеткой логики.

2 Неформальные процедуры Говоря о неформальных процедурах мы обычно хорошо понимаем, что имеется в виду, и без затруднений можем привести примеры таких процедур, связанных с пониманием текстов естественного языка, переводом с одного естественного языка на другой, информационным поиском по смыслу и т. д. Говоря о неформальных процедурах мы обычно хорошо понимаем, что имеется в виду, и без затруднений можем привести примеры таких процедур, связанных с пониманием текстов естественного языка, переводом с одного естественного языка на другой, информационным поиском по смыслу и т. д. Трудности возникают при попытке точного определения подобных процедур. Так, если рассматривать неформальные процедуры всего лишь как абстрактные функции, которые для каждого значения аргумента "выдают" некоторое значение, то категория неформальности вообще исчезает из рассмотрения. Трудности возникают при попытке точного определения подобных процедур. Так, если рассматривать неформальные процедуры всего лишь как абстрактные функции, которые для каждого значения аргумента "выдают" некоторое значение, то категория неформальности вообще исчезает из рассмотрения. Неформальная процедура это особый способ представления функций. Чтобы в какой-то степени приблизиться к этому "человеческому" способу представления функций, рассмотрим прежде всего традиционные алгоритмические модели и попытаемся понять, в чем состоит основная трудность их применения для имитации неформальных процедур. Неформальная процедура это особый способ представления функций. Чтобы в какой-то степени приблизиться к этому "человеческому" способу представления функций, рассмотрим прежде всего традиционные алгоритмические модели и попытаемся понять, в чем состоит основная трудность их применения для имитации неформальных процедур. Алгоритмические модели Алгоритмические модели Алгоритмические модели основаны на понятии алгоритма. Исторически первые точные определения алгоритма, возникшие в 30-х годах, были связаны с понятием вычислимости. С тех пор было предложено множество, как выяснилось, эквивалентных определений алгоритма. Алгоритмические модели основаны на понятии алгоритма. Исторически первые точные определения алгоритма, возникшие в 30-х годах, были связаны с понятием вычислимости. С тех пор было предложено множество, как выяснилось, эквивалентных определений алгоритма.

3 В практике программирования алгоритмы принято описывать с помощью алгоритмических языков программирования. Широко используются также разного рода блок-схемы алгоритмов, позволяющие представить алгоритмы в наглядном и общедоступном виде, не привлекая в тоже время сложных конструкций из конкретных языков программирования. В практике программирования алгоритмы принято описывать с помощью алгоритмических языков программирования. Широко используются также разного рода блок-схемы алгоритмов, позволяющие представить алгоритмы в наглядном и общедоступном виде, не привлекая в тоже время сложных конструкций из конкретных языков программирования. Чтобы оценить возможности использования алгоритмов для представления неформальных процедур, рассмотрим простую задачу. Чтобы оценить возможности использования алгоритмов для представления неформальных процедур, рассмотрим простую задачу. ЗАДАЧА. Описать процедуру, реализующую преобразование из именительного падежа в родительный для существительных следующих типов: ДОМ, МАМА, ВИЛКА, КИНО, НОЧЬ, ТОКАРЬ, КИЛЬ. ЗАДАЧА. Описать процедуру, реализующую преобразование из именительного падежа в родительный для существительных следующих типов: ДОМ, МАМА, ВИЛКА, КИНО, НОЧЬ, ТОКАРЬ, КИЛЬ. Решение 1 указано на Рис. 1 в виде блок схемы соответствующего алгоритма. Решение 1 указано на Рис. 1 в виде блок схемы соответствующего алгоритма.

4 Рис. 1. Решение 1. Алгоритм

5 С точки зрения программирования на алгоритмических языках достоинства подобного представления очевидны эта блок-схема без затруднений переводится в текст программы, например, на языке Ассемблера или С++. Однако само составление подобной блок-схемы при появлении существительных новых типов становится, очевидно, все более и более утомительным занятием. Для иллюстрации этого предположим, что дана С точки зрения программирования на алгоритмических языках достоинства подобного представления очевидны эта блок-схема без затруднений переводится в текст программы, например, на языке Ассемблера или С++. Однако само составление подобной блок-схемы при появлении существительных новых типов становится, очевидно, все более и более утомительным занятием. Для иллюстрации этого предположим, что дана ДОПОЛНИТЕЛЬНАЯ ЗАДАЧА. Расширить алгоритм, представленный на Рис. 1 на слова ВАСЯ, ВРЕМЯ, АКЦИЯ, ЗАДАЧА. ДОПОЛНИТЕЛЬНАЯ ЗАДАЧА. Расширить алгоритм, представленный на Рис. 1 на слова ВАСЯ, ВРЕМЯ, АКЦИЯ, ЗАДАЧА. Разумеется программист без особого труда составит соответствующую блок-схему алгоритма. И все же, если учесть, что подобные изменения и расширения алгоритма при программировании неформальных процедур происходят многократно (реальная сложность неформальной процедуры как раз и проявляется в практической невозможности предусмотреть заранее все случаи), следует признать, что, вполне правильное в статике, решение 1 в динамике неудачно! Разумеется программист без особого труда составит соответствующую блок-схему алгоритма. И все же, если учесть, что подобные изменения и расширения алгоритма при программировании неформальных процедур происходят многократно (реальная сложность неформальной процедуры как раз и проявляется в практической невозможности предусмотреть заранее все случаи), следует признать, что, вполне правильное в статике, решение 1 в динамике неудачно! Продукционные модели Продукционные модели В подобных случаях для обеспечения динамичности процессов модификации программ используются те или иные варианты таблиц решений. С учетом этого для исходной задачи более приемлемо решение 2: В подобных случаях для обеспечения динамичности процессов модификации программ используются те или иные варианты таблиц решений. С учетом этого для исходной задачи более приемлемо решение 2:

6 Таблица 1. Решение 2

7 Соответствующая таблица решений содержит две графы слева приведены описания ситуаций, справа соответствующие действия. Предполагается, что программист разработал интерпретирующую программу для подобных таблиц. Эта программа работает следующим образом. Для конкретного входного слова, пусть это будет для примера слово РОЗА, осуществляется последовательный просмотр ситуаций, указанных в таблице, и сравнение их со входным словом. Если слово соответствует некоторой ситуации, то выполняется действие, указанное для этой ситуации. Соответствующая таблица решений содержит две графы слева приведены описания ситуаций, справа соответствующие действия. Предполагается, что программист разработал интерпретирующую программу для подобных таблиц. Эта программа работает следующим образом. Для конкретного входного слова, пусть это будет для примера слово РОЗА, осуществляется последовательный просмотр ситуаций, указанных в таблице, и сравнение их со входным словом. Если слово соответствует некоторой ситуации, то выполняется действие, указанное для этой ситуации. Для слова РОЗА будет обнаружено соответствие с ситуацией "-А". В результате выполнения действия "-Ы" будет получено выходное слово РОЗЫ. Для слова РОЗА будет обнаружено соответствие с ситуацией "-А". В результате выполнения действия "-Ы" будет получено выходное слово РОЗЫ. Теперь значительно упрощается расширение на новые классы слов необходимо лишь обеспечить внесение вставок на нужное место в таблице решений. Теперь значительно упрощается расширение на новые классы слов необходимо лишь обеспечить внесение вставок на нужное место в таблице решений. Таблицы решений представляют собой частный случай так называемых продукционных систем. В этих системах правила вычислений представляются в виде продукций. Продукции представляют собой операторы специального вида и состоят из двух основных частей, для краткости называемых обычно "ситуация действие". Таблицы решений представляют собой частный случай так называемых продукционных систем. В этих системах правила вычислений представляются в виде продукций. Продукции представляют собой операторы специального вида и состоят из двух основных частей, для краткости называемых обычно "ситуация действие". "Ситуация" содержит описание ситуации, в которой применима продукция. Это описание задается в виде условий, называемых посылками продукции. "Действие" это набор инструкций, подлежащих выполнению в случае применимости продукции. "Ситуация" содержит описание ситуации, в которой применима продукция. Это описание задается в виде условий, называемых посылками продукции. "Действие" это набор инструкций, подлежащих выполнению в случае применимости продукции.

8 Режим возвратов Режим возвратов Таблица решений, приведенная на Таблица 1, иллюстрирует так называемую безвозвратную процедуру. В этом случае на каждом шаге выбирается единственное решение так, для слова РОЗА таким решением будет РОЗЫ проблема выбора решения не возникает. В общем случае неформальные процедуры являются многозначными. При этом используется так называемый режим возвратов. Таблица решений, приведенная на Таблица 1, иллюстрирует так называемую безвозвратную процедуру. В этом случае на каждом шаге выбирается единственное решение так, для слова РОЗА таким решением будет РОЗЫ проблема выбора решения не возникает. В общем случае неформальные процедуры являются многозначными. При этом используется так называемый режим возвратов. а). МАТЬ > ЛЮБИТ > ? а). МАТЬ > ЛЮБИТ > ? что делать? кого? что делать? кого? б). МАТЬ < ЛЮБИТ < ? б). МАТЬ < ЛЮБИТ < ? кого? что делать? кого? что делать? Пусть предложение начинается со слов МАТЬ ЛЮБИТ.... Проанализировав эти слова в первоначальном предположении именительного падежа для слова МАТЬ, система вправе построить структуру, представленную в случае а). Если следующее слово после слова ЛЮБИТ представляет собой существительное в винительном падеже, например, вся фраза имеет вид МАТЬ ЛЮБИТ СЫНА, то эта структура является окончательной. Если же фраза имеет вид МАТЬ ЛЮБИТ СЫН, то возникает противоречие или, как говорят, сигнал неуспеха очередное слово СЫН противоречит ожиданию прямого дополнения. В этом случае система должна вернуться на ближайший из предыдущих шагов, где можно принять другую альтернативу анализа. В данном примере это шаг анализа слова МАТЬ система должна принять теперь альтернативу винительного падежа для этого слова. Далее будет построена структура, указанная в случае б). Пусть предложение начинается со слов МАТЬ ЛЮБИТ.... Проанализировав эти слова в первоначальном предположении именительного падежа для слова МАТЬ, система вправе построить структуру, представленную в случае а). Если следующее слово после слова ЛЮБИТ представляет собой существительное в винительном падеже, например, вся фраза имеет вид МАТЬ ЛЮБИТ СЫНА, то эта структура является окончательной. Если же фраза имеет вид МАТЬ ЛЮБИТ СЫН, то возникает противоречие или, как говорят, сигнал неуспеха очередное слово СЫН противоречит ожиданию прямого дополнения. В этом случае система должна вернуться на ближайший из предыдущих шагов, где можно принять другую альтернативу анализа. В данном примере это шаг анализа слова МАТЬ система должна принять теперь альтернативу винительного падежа для этого слова. Далее будет построена структура, указанная в случае б).

9 Тривиальность рассмотренного примера убеждает в необходимости режима возвратов при реализации неформальных процедур. Тривиальность рассмотренного примера убеждает в необходимости режима возвратов при реализации неформальных процедур. Логический вывод Логический вывод Важность логического вывода становится очевидной уже при рассмотрении простейших информационно-логических процедур. Предположим, что некоторая база данных содержит сведения об отношениях "o ОТЕЦ у" и "х МАТЬ у". Чтобы обработать запросы типа: Важность логического вывода становится очевидной уже при рассмотрении простейших информационно-логических процедур. Предположим, что некоторая база данных содержит сведения об отношениях "o ОТЕЦ у" и "х МАТЬ у". Чтобы обработать запросы типа: ИВАНОВ А.И. ДЕД ПЕТРОВА В.А.? ИВАНОВ А.И. ДЕД ПЕТРОВА В.А.? ПЕТРОВ В.А. ВНУК ИВАНОВА А.И.? ПЕТРОВ В.А. ВНУК ИВАНОВА А.И.? необходимо либо ввести в базу данных также и сведения об отношениях "х ДЕД у" и "х ВНУК у", либо объяснить системе, как из отношений ОТЕЦ, МАТЬ извлечь искомую информацию. Реализация первой возможности связана с неограниченным ростом избыточности базы данных. Вторая возможность при традиционном алгоритмическом подходе требует написания все новых и новых программ для реализации новых типов запросов. необходимо либо ввести в базу данных также и сведения об отношениях "х ДЕД у" и "х ВНУК у", либо объяснить системе, как из отношений ОТЕЦ, МАТЬ извлечь искомую информацию. Реализация первой возможности связана с неограниченным ростом избыточности базы данных. Вторая возможность при традиционном алгоритмическом подходе требует написания все новых и новых программ для реализации новых типов запросов. Логический вывод позволяет расширять возможности "общения" наиболее просто и наглядно. Так, для приведенных типов запросов системе достаточно будет сообщить три правила: Логический вывод позволяет расширять возможности "общения" наиболее просто и наглядно. Так, для приведенных типов запросов системе достаточно будет сообщить три правила: 1. хДЕД у если хОТЕЦ а и аРОДИТЕЛЬ у 1. хДЕД у если хОТЕЦ а и аРОДИТЕЛЬ у 2. хРОДИТЕЛЬ у если хОТЕЦ у или хМАТЬ у 2. хРОДИТЕЛЬ у если хОТЕЦ у или хМАТЬ у 3. хВНУК у если уДЕД х 3. хВНУК у если уДЕД х

10 Эти правила содержат естественные и очевидные определения понятий ДЕД, РОДИТЕЛЬ, ВНУК. Поясним в чем состоит логический вывод для запроса "АДЕД В?" в предположении, что в базе данных имеются факты: АОТЕЦ Б и БМАТЬ В. При этом для упрощения опустим тонкости, связанные с падежными окончаниями. Пользуясь определением 1 система придет к необходимости проверки существования такого индивидуума а, что факты АОТЕЦ а и аРОДИТЕЛЬ В истинны. Если такой а существует, то АДЕД В, если не существует такого а, то А не является дедом В. Эти правила содержат естественные и очевидные определения понятий ДЕД, РОДИТЕЛЬ, ВНУК. Поясним в чем состоит логический вывод для запроса "АДЕД В?" в предположении, что в базе данных имеются факты: АОТЕЦ Б и БМАТЬ В. При этом для упрощения опустим тонкости, связанные с падежными окончаниями. Пользуясь определением 1 система придет к необходимости проверки существования такого индивидуума а, что факты АОТЕЦ а и аРОДИТЕЛЬ В истинны. Если такой а существует, то АДЕД В, если не существует такого а, то А не является дедом В. Зависимость продукций Зависимость продукций Продукционные системы, содержащие аппарат логического вывода, отличает высокая степень общности правил обработки данных. Однако именно эта общность приводит к ухудшению динамических свойств соответствующих продукционных программ, к трудностям их модификации и развития. Чтобы понять, в чем тут причина, обратимся снова к Таблица 1. Пока эта таблица содержит несколько строк, не представляет особого труда установление правильного порядка их следования, но если учесть, что реальное количество продукций в подобных задачах исчисляется сотнями и более, трудоемкость их правильного взаимного расположения становится очевидной. Практически, при программировании неформальных "человеческих" процедур, подобные таблицы можно вручную создавать и сопровождать для нескольких десятков продукций, максимум для продукций. Продукции зависимы, и за правильное выявление этой зависимости отвечает программист. Новые продукции необходимо вручную вставлять на нужное место. Продукционные системы, содержащие аппарат логического вывода, отличает высокая степень общности правил обработки данных. Однако именно эта общность приводит к ухудшению динамических свойств соответствующих продукционных программ, к трудностям их модификации и развития. Чтобы понять, в чем тут причина, обратимся снова к Таблица 1. Пока эта таблица содержит несколько строк, не представляет особого труда установление правильного порядка их следования, но если учесть, что реальное количество продукций в подобных задачах исчисляется сотнями и более, трудоемкость их правильного взаимного расположения становится очевидной. Практически, при программировании неформальных "человеческих" процедур, подобные таблицы можно вручную создавать и сопровождать для нескольких десятков продукций, максимум для продукций. Продукции зависимы, и за правильное выявление этой зависимости отвечает программист. Новые продукции необходимо вручную вставлять на нужное место.

11 Мы могли бы использовать в таблице решений только конкретные факты, например правила ДОМ --> ДОМА, МАМА --> МАМЫ и т. д., и динамичность соответствующей таблицы решений была бы восстановлена подобные правила можно было бы вводить в произвольном порядке! Однако цена подобной "динамичности" окажется непомерно высокой полный отказ от обобщенных правил. Мы могли бы использовать в таблице решений только конкретные факты, например правила ДОМ --> ДОМА, МАМА --> МАМЫ и т. д., и динамичность соответствующей таблицы решений была бы восстановлена подобные правила можно было бы вводить в произвольном порядке! Однако цена подобной "динамичности" окажется непомерно высокой полный отказ от обобщенных правил. Желательно восстановить динамичность продукционно-логических систем, сохранив при этом в полном объеме возможность использования обобщенных правил. Продукционная система должна взять на себя функции распознавания и интерпретации приоритета продукций программист должен только описывать ситуации и соответствующие им действия. Желательно восстановить динамичность продукционно-логических систем, сохранив при этом в полном объеме возможность использования обобщенных правил. Продукционная система должна взять на себя функции распознавания и интерпретации приоритета продукций программист должен только описывать ситуации и соответствующие им действия. Продукционные системы с исключениями Продукционные системы с исключениями Если отношение "правилоисключение" встроено в систему, она сама может понять, что преобразование ПАЛКА --> ПАЛКЫ незаконно. При этом система должна руководствоваться простым принципом: если применимо исключение, общее правило запрещено. Соответствующие системы будем называть системами с исключениями. Если отношение "правилоисключение" встроено в систему, она сама может понять, что преобразование ПАЛКА --> ПАЛКЫ незаконно. При этом система должна руководствоваться простым принципом: если применимо исключение, общее правило запрещено. Соответствующие системы будем называть системами с исключениями. Отношение "общее правило исключение" безусловно полезно для понимания системой уместности правил. Можно сказать, что это отношение устанавливает автоматически (по умолчанию) наиболее типичное для неформальных процедур взаимодействие правил: Отношение "общее правило исключение" безусловно полезно для понимания системой уместности правил. Можно сказать, что это отношение устанавливает автоматически (по умолчанию) наиболее типичное для неформальных процедур взаимодействие правил: ДОМА, МАМА --> МАМЫ и т. д., и динамичность соответствующей таблицы решений была бы восстановлена подобные правила можно было бы вводить в произвольном порядке! Однако цена подобной "динамичности" окажется непомерно высокой полный отказ от обобщенных правил. Желательно восстановить динамичность продукционно-логических систем, сохранив при этом в полном объеме возможность использования обобщенных правил. Продукционная система должна взять на себя функции распознавания и интерпретации приоритета продукций программист должен только описывать ситуации и соответствующие им действия. Желательно восстановить динамичность продукционно-логических систем, сохранив при этом в полном объеме возможность использования обобщенных правил. Продукционная система должна взять на себя функции распознавания и интерпретации приоритета продукций программист должен только описывать ситуации и соответствующие им действия. Продукционные системы с исключениями Продукционные системы с исключениями Если отношение "правилоисключение" встроено в систему, она сама может понять, что преобразование ПАЛКА --> ПАЛКЫ незаконно. При этом система должна руководствоваться простым принципом: если применимо исключение, общее правило запрещено. Соответствующие системы будем называть системами с исключениями. Если отношение "правилоисключение" встроено в систему, она сама может понять, что преобразование ПАЛКА --> ПАЛКЫ незаконно. При этом система должна руководствоваться простым принципом: если применимо исключение, общее правило запрещено. Соответствующие системы будем называть системами с исключениями. Отношение "общее правило исключение" безусловно полезно для понимания системой уместности правил. Можно сказать, что это отношение устанавливает автоматически (по умолчанию) наиболее типичное для неформальных процедур взаимодействие правил: Отношение "общее правило исключение" безусловно полезно для понимания системой уместности правил. Можно сказать, что это отношение устанавливает автоматически (по умолчанию) наиболее типичное для неформальных процедур взаимодействие правил:">

12 исключение "вытесняет" общее правило. исключение "вытесняет" общее правило. при пересечении разрешены оба правила. при пересечении разрешены оба правила. Разумеется, возможны ситуации, когда необходимо поступать наоборот: Разумеется, возможны ситуации, когда необходимо поступать наоборот: исключение не запрещает общего правила исключение не запрещает общего правила при пересечении одно из правил запрещено. при пересечении одно из правил запрещено. Пусть дано, например, общее правило х --> р 1 и его исключение Ах --> р 2. Таким образом, для произвольного слова необходима реакция р 1. Для слова же, начинающегося с буквы А, исполняется реакция р 2 по умолчанию для таких слов реакция р 1 незаконна. Пусть дано, например, общее правило х --> р 1 и его исключение Ах --> р 2. Таким образом, для произвольного слова необходима реакция р 1. Для слова же, начинающегося с буквы А, исполняется реакция р 2 по умолчанию для таких слов реакция р 1 незаконна. Предположим, однако, что по условию конкретной задачи для слов, начинающихся с А, реакция р 1 также допустима. В этом случае введение нового правила Ах --> р 1 снимает запрет на реакцию р 1 в ситуации Ах. Предположим, однако, что по условию конкретной задачи для слов, начинающихся с А, реакция р 1 также допустима. В этом случае введение нового правила Ах --> р 1 снимает запрет на реакцию р 1 в ситуации Ах. Аналогичный способ годится для пересечения правил. Аналогичный способ годится для пересечения правил. Таким образом, аппарат исключений позволяет устанавливать произвольные способы взаимодействия правил, в том числе и отличные от взаимодействия по умолчанию. Таким образом, аппарат исключений позволяет устанавливать произвольные способы взаимодействия правил, в том числе и отличные от взаимодействия по умолчанию. При развитии продукционной системы с исключениями программист сосредотачивает свое внимание на выявлении новых правил и на обобщении уже имеющихся. Аппарат исключений освобождает программиста от решения трудоемких вопросов согласования правил распознавание и интерпретация исключений осуществляется автоматически. При развитии продукционной системы с исключениями программист сосредотачивает свое внимание на выявлении новых правил и на обобщении уже имеющихся. Аппарат исключений освобождает программиста от решения трудоемких вопросов согласования правил распознавание и интерпретация исключений осуществляется автоматически. р 1 и его исключение Ах --> р 2. Таким образом, для произвольного слова необходима реакция р 1. Для слова же, начинающегося с буквы А, исполняется реакция р 2 по умолчанию для таких слов реакция р 1 незаконна. Пусть дано, например, общее правило х --> р 1 и его исключение Ах --> р 2. Таким образом, для произвольного слова необходима реакция р 1. Для слова же, начинающегося с буквы А, исполняется реакция р 2 по умолчанию для таких слов реакция р 1 незаконна. Предположим, однако, что по условию конкретной задачи для слов, начинающихся с А, реакция р 1 также допустима. В этом случае введение нового правила Ах --> р 1 снимает запрет на реакцию р 1 в ситуации Ах. Предположим, однако, что по условию конкретной задачи для слов, начинающихся с А, реакция р 1 также допустима. В этом случае введение нового правила Ах --> р 1 снимает запрет на реакцию р 1 в ситуации Ах. Аналогичный способ годится для пересечения правил. Аналогичный способ годится для пересечения правил. Таким образом, аппарат исключений позволяет устанавливать произвольные способы взаимодействия правил, в том числе и отличные от взаимодействия по умолчанию. Таким образом, аппарат исключений позволяет устанавливать произвольные способы взаимодействия правил, в том числе и отличные от взаимодействия по умолчанию. При развитии продукционной системы с исключениями программист сосредотачивает свое внимание на выявлении новых правил и на обобщении уже имеющихся. Аппарат исключений освобождает программиста от решения трудоемких вопросов согласования правил распознавание и интерпретация исключений осуществляется автоматически. При развитии продукционной системы с исключениями программист сосредотачивает свое внимание на выявлении новых правил и на обобщении уже имеющихся. Аппарат исключений освобождает программиста от решения трудоемких вопросов согласования правил распознавание и интерпретация исключений осуществляется автоматически.">