Содержание к диссертации
Введение
ГЛАВА I. Формальные грамматики и продукционные системы 9
1.1. Некоторые задачи искусственного интеллекта и их связь с продукционными системами . 9
1.2. Обзор существующего положения 10
1.3. Некоторые нерешенные проблемы . 11
1.4. Постановка задачи 12
ГЛАВА II. Конвенциональные грамматики 13
2.1. Целенаправленность и управление выводом в грамматиках 13
2.2. Основные определения 13
2.3. Иерархические свойства языков, порожденных к-грамматиками 18
2.4. Грамматическая сложность к-грамматик и языков 30
2.4.1. Определения 30
2.4.2. Независимость 33
2.4.3. Теоремы 40
2.5. Выводы 34
ГЛАВА III. Обобщенные грамматики . 57
3.1. Обучение и индуктивный вывод 57
3.2. Основные определения 58
3.3. Исследование грамматической сложности ок-грамматик и языков 60
3.4. Выводы 63
Заключение 65
Литература 67
- Некоторые задачи искусственного интеллекта и их связь с продукционными системами
- Некоторые нерешенные проблемы
- Иерархические свойства языков, порожденных к-грамматиками
- Исследование грамматической сложности ок-грамматик и языков
Введение к работе
В последние годы проявляется тенденция к использованию вычислительных машин в областях, связанных не с классическими вычислениями, а с обработкой разного рода символьной информации. В частности, подобные задачи возникают в тех системах, работа которых основывается на знаниях, хранимых в памяти вычислительных систем. Это требует создания специальных средств для представления знаний и манипулирования ими. В настоящее время в качестве языков для представления знаний, как правило, используются либо логические исчисления, либо сетевые представления различного типа (семантические сети [13J , фреймы ЕЗ] , сценарии С341 ). В качестве языков манипулирования данными в подавляющем большинстве случаев используются различного рода продукционные системы СИ] , 37] .
Продукционные системы являются естественным развитием модели формальных грамматик, созданных еще во второй половине 50-х годов Н.Хомским [9] . Другим источником возникновения современных продукционных систем является теория секвенциальных систем, которая развивалась еще в работах Э.Поста, а затем была использована в ставших классическими исследованиях Э.Ньюэлла и Г,Саймона С33] .
Однако, имевшиеся до настоящего'времени исследования в области классификации типов формальных грамматик и секвенциальных систем, а также в области анализа и синтеза этих средств не могут быть прямо использованы для формализации существующих сейчас языков манипулирования знаниями. Это связано с тем, что продукционные системы, использованные для этих целей, имеют ряд отличительных особенностей (например, наличие управления при выборе продукций) , которые не позволяют использовать для них ранее построенные модели.
Это определяет актуальность данного исследования, в результате которого предлагается новая формальная модель продукционных систем, более адекватная реально существующим системам.
Таким образом, объектом исследования диссертации являются продукционные системы, применяемые при решении задач, связанных с обработкой символьной информации. Такие системы в настоящее время активно используются при машинном доказательстве теорем, в системах принятия решений по управлению в сложных системах, в разного рода экспертных системах и в системах планирования целесообразного поведения роботов.
Целью работы является исследование нового предложенного в ней класса формальных грамматик, элементы которого названы конвенциональными грамматиками (в сокращении к-грамматиками). Эти грамматики позволяют формализовать процесс целенаправленного выбора грамматических правил для достижения поставленной цели. В ходе работы было проведено сравнение предложенной в диссертации модели с ранее известными моделями грамматик.
При решении рассматриваемых проблем были использованы методы математической логики, формальных грамматик и теории формальных языков.
Научная новизна работы заключается в следующем:
Предложен новый класс формальных грамматик (к-граммати-ки), у которых в отличии от ранее известных грамматик в продукциях в явном виде включены условия их применимости.
Для к-грамматик исследована проблема выводимости, дван анализ порождаемых ими языков и построена классификация этих грамматик, аналогичная известной ранее классификации грамматик Хомского.
Проведено сравнение соответствующих одинаковым по классификации уровням к-грамматик и классических грамматик. В результате этого сравнения установлено соотношение между языками, порождаемыми соответствующими по классификации грамматиками.
Доказан ряд теорем, позволяющих установить соотношение между различными типами к-грамматик с точки зрения мощности порождаемых ими языков.
Даны некоторые оценки сложности, связанные с необходимым числом продукционных правил, объемом памяти для хранения промежуточных результатов вывода и с необходимым для определения данной к-грамматики числом символов.
Практическая ценность результатов исследования к-грамматик заключается в теоретически обоснованном познании некоторых возможностей увеличения эффективности продукционных систем, играющих в настоящее время ключевую роль в архитектуре экспертных систем ГІ83 . Исследованные в работе к-грамматики при их применении в системах, использующих продукционные модели, могут позволить уменьшить необходимый объем памяти для хранения промежуточных результатов или вспомогательных информации.
Результаты работы докладывалист на:
международной конференции"Искусственный интеллект и информационно-управляющие системы роботов" в Смоленицах (ЧССР) в июле 1980г.;
семинаре по теории автоматов на . кафедре, вычислительной математики и вычислительной техники Естествознательного факультета Университета им. Л.Этвеша в Будапеште (ВНР) в апреле 1981г.;
международной конференции по теории автоматов,; языков и математических систем в Шалготаряне (ВНР) в мае 1984г.;
конференции молодых математиков и программистов Унив. им. Л.Этвеша в Будапеште. (ВНР) в мае 1984г.;
кафедре теоретической кибернетики Математико-физического факультета Унив. им.Коменского в Братиславе (ЧССР) в 1983 и 1984 годах;
семинаре лаборатории теории и проектирования больших систем ВЦ Ж СССР в 1981, 1983 и 1984 годах.
По теме диссертации автором опубликовано II работ: С203 - [29] и работа L32] .
Диссертация состоит из введения, трех глав, заключения и списка литературы.
В первой главе дается общая характеристика работы: обосновывается ^актуальность исследуемых проблем (раздел I.I), приводится обзор современного состояния проблематики (раздел 1.2), сформулированы некоторые нерешенные проблемы (в разделе 1.3) и сформулирована основная цель работы (раздел 1.4).
Во второй главе показано значение целенаправленности вывода в грамматиках (раздел 2.1), определяется понятие конвенциональной грамматики (к-грамматики), являющиеся формализацией свойства целенаправленности вывода и некоторые другие основные понятия, касающиеся к-грамматик (в разделе 2.2), исследуются иерархические свойства языков, порожденных к-грамматиками (раздел 2.3) и грамматическая сложность к-грамматик и языков (раздел 2.4). В разделе 2.5 приведены основные выводы.
В третьей главе приведено одно из возможных обобщений к-грамматик, мотивировкой к которому является свойство обучаемости продукционных систем. Мотивировка приведена в разделе 3.1. В этом разделе установлена связь между проблемами индуктивного вывода и обобщенными конвенциональными грамматиками і
(ок-грамматиками), формальное определение которых приведено в разделе 3,2. Основной темой раздела 3,3 является исследование грамматической сложности языков, определяемых ок-грамматиками. Выводы главы приведены в разделе 3.4.
В конце работы приведены заключительные выводы по результатам диссертации и некоторые соображения о возможности дальнейшего обобщения модели.
Список литературы включает 39 наименований литературных источников.
Диссертационная работа была выполнена в рамках заочной аспирантуры автора в ВЦ АН СССР в Москве.
Некоторые задачи искусственного интеллекта и их связь с продукционными системами
В последующие три десятилетия известную популярность приобрели попытки объяснить схемы человеческих рассуждений или особенности человеческого поведения с помощью понятий, относящихся к вычислениям и вычислительным машинам. Практическую пользу исследований такого рода мы уже отметили во введении. Но попытки объяснить некоторые аспекты человеческих рассуждений в терминах манипуляций с символами привели, как замечает Г.Саймон в Г36] , и к многим интересным результатам в области психологии, и информационная теория мышления стала доминирующей в области когнитивной психологии.
О.К.Тихомиров [6J считает главной предпосылкой объяснения схемы человеческих рассуждений на уровне обработки информации положение, что сложные процессы рассуждения составляются из элементарных процессов манипулирования символами. Требование изучать рассуждение "на уровне элементарных информационных процессов" фактически расшифровывается как требование объяснить человеческое мышление исключительно в системе понятий, описывающих работу вычислительного устройства.
Первой серьезной попыткой такого рода является модель Э. Ньюэлла, Г.Саймона и их сотрудников, описанная в завершенной форме в книге Г 33 Л .
Элементарные информационные процессы представляются авторами [33J в виде продукционных правил , описывающих каким образом одна цепочка символов ассоциирует или порождает другую. Конечные множества таких продукционных правил были с математической точки зрения исследованы уже в первой половине нашего века в качестве моделей вычислений (алгоритмов) Э.Постом и А.А.Марковым и до сих пор применяются и в области экспериментальных работ, связанных с искусственным интеллектом (см. например, ГІ8] , Г 37 J ). Их называют обычно: продукционные системы (ПС).
Э.Ньюэлл и Г.Саймон предполагают ( Г33] , стр. 804-805) возможность соотнесения психологического понятия кратковременной памяти и динамической части ПС (цепочки символов, которая переписывается) и психологического понятия долговременной памяти и самой ПС (множества продукционных правил). Подобное соотнесение можно найти и в книге Ю.Козелецкого [2J (гл. 2.4).
Можно аргументировать с психологической точки зрения пользу разьиения множества символов, фигурирующих в ПС, на два непересекающихся множества - множества терминальных и нетерминальных символов. Такую агрументацию можно найти, например, в книге К.В.Уил-сона Г38J (стр. 74). Терминальными можно считать, например, такие символы, у которых возможна с точки зрения психологии их сенсорная или моторная интерпретация, а нетерминальными те, у которых возможна только "концептуальная" интерпретация.
Основная схема моделирования рассуждений на уровне обработки символов, которую можно описать с помощью ПС, приобретает таким образом вид грамматики в смысле математически определенного объекта Г I ] , ГІ9 3 .
В пользу удобства грамматической модели можно, кроме уже сказанного, привести и некоторые дальнейшие аргументы. Так например, ПС и формальные грамматики представляют секвенционную модель обработки символов. Такой же вид обработки предполагается и у человека на основании многих психологических исследований, связанных с человеческим мышлением. Аргументацию в пользу такой психологической гипотезы или ее более широкую трактовку можно найти в С 33 J (гл. 5.1), LZ1 (гл. 2.5) и в работе М.Минского С31 (гл. 1.2).
Вторая причина заключается в том, что применение правил ПС или формальной грамматики происходит недетерминированно в том смысле, что правила не применяются в какой-то определенной очереди. Грамматики определяют, благодаря этому свойству, не цепочку, а множество цепочек - язык. Таким образом, как это заметил уже Н.Хомский СЮ J , они выражают то, что может быть построено на их основе, а не то, что уже построено.
Третья причина - это известная связь формальных грамматик с вычислительными устройствами (машина Тьюринга и различные виды автоматов). С точки зрения искусственного интеллекта это имеет большое значение потому, что для моделей, создаваемых в рамках искусственного интеллекта, желательна не только связь с человеческим мышлением, но и возможность исследования вопросов, касающихся потенциальной возможности хотя бы частичной реализации этих моделей на вычислительных машинах.
Модель человеческих рассуждений на уровне, о котором мы говорили в разделе 1.2, не является подходящей для объяснения ряда свойств интеллектуального поведения человека. Приведем примеры этого.
Большое число эмпирических наблюдений экспериментальной психологии говорит в пользу целенаправленности процесса человеческого рассуждения. Этот процесс происходит так, что из всех возможных действий по переработки символьной информации выбираются только те, применение которых имеет смысл в данной проблемной среде, для достижения цели. Психологически обоснованные аргументы в пользу целенаправленности можно найти, например, в книге LZ1 (стр. 41) или [35J (стр. 217).
Второе важное свойство интеллекта - это способность обучения. Для нас особенно интересным является вопрос об обучении, связанном с проведением индуктивных выводов на основе построения граммати (см. например, работы [12] , Г14J , или хороший обзор Э.Б.ХантаГбЛ , раздел 7.1). К.В.Уилсон показывает в С 38] (гл. 5) возникновение таких подходов именно из психологических результатов. В главе Ш настоящей работы мы сделаем попытку трактовки проблематики обучения в смысле индуктивного вывода грамматик с другой точки зрения.
Некоторые нерешенные проблемы
Кроме свойства целенаправленности, которое мы использовали определяя к-грамматики, другим важным свойством человеческих рассуждений является способность человека при их проведении генерировать пропущенные ранее шаги вывода, формулировать новые системы продукций для достижения целей вывода, видоизменять имевшиеся ранее продукции и т.п. Часто все эти возможности характеризуют терминалом "способность к обучению", а в ряде случаев отождествляют эту способность со схемой индуктивных выводов. Для формальных грамматик проблема обучения сводится обыкновенно к задаче восстановления (или индуктивного вывода) грамматик. (М.Э.Голд [14] , Дж.Фелдман CI2] ). Обзор некоторых достижений в этой области дает книга Г 8] или книга [ 7J . Психологические аспекты этой проблемы обсуждаются в С 38] .
Формально задача восстановления или индуктивного вывода для грамматик состоит в построении конструктивной процедуры,восстанавливающей продукционные правила неизвестной грамматики (обычно заданного типа) на основе конечной последовательности слов из символов терминального алфавита, которые обладают определенными свойствами.
М.Голд ГІ4] показал, что если грамматика & имеет тип I, то ее можно восстановить при помощи машины Тьюринга на основании такой выборки цепочек, которая содержит как элементы из языка 1_ (&) так и элементы из его дополнения (т.е. из множества Т - L (0 ) ), и на основании информации о принадлежности -каждой входящей в последовательность цепочки к L ( или к его дополнению. Теорему Голда можно (без доказательства) найти и в Г81 или в m .
Интерпретация этого факта психологами и лингвистами заключается в том, что, предполагая у человеческого сознания способности машины Тьюринга, можно формально объяснить его способность обучению грамматическим правилам на основе текстов родного языка.
Вопрос, которым мы будем заниматься в этой главе, другой. Нас интересует, каким образом можно смоделировать феномен совершенствования способности адекватно использовать содержание долговременной памяти, или, говоря в терминах данной работы, грамматических продукций. Во второй главе мы ввели f1 -части в левые части продукций. Этим мы добились целенаправленности вывода, но взамен получили весьма жесткую систему, в которой каждая продукция применяется лишь при удовлетворении одного, соответствующего ей и неизменного условия. Для моделирования возможности "способности к обучению" необходимо отказаться от этой жесткости. Решение этой проблемы мы видим в задании - -частей продукций с помощью языков. Из этого вытекает одна из возможностей формализации способности к обучению: Языки, использучемые в качестве р -частей продукций, могут быть определены грамматиками, которые были восстановлены с помощью индуктивного вывода на основе заданной последовательности обычных однословных р» -частей. Обобщенной конвенциональной грамматикой (или ок -грамматикой) будем называть четверку где значение /V, Т и 3 такое же как и в определении 2.2.1 , а г - конечное непустое множество, элементы которого называются продукциями (или правилами) ок-грамматики . Продукции ок-грамматики имеют следующую общую форму: Выражение ot Ф {2 определяет шаг вывода в ок-грамма-тике ( . В тех случаях, когда это не приводит к недоразумениям, буква (ь в будет опускаться. Определение вывода в ок-грамматике совпадает с определением вывода в к-грамматике (см. определение 2.2,3). Будем различать классы ок-грамматик: типа 0 (Оок-грам-матики), І (Іок-грамматики), 2 (2ок-грамматики) и 3 (Зок-грамма-тики) в согласии с формой продукций (см. определение 3.2.4) и с типом языков V .Следовательно, ок-грамматика имеет тип ), если все её продукции имеют вид, соответствующий типу t в смысле определения 2.2.4 и все языки в Г -частях продукций Р также имеют тип zf . Легко видеть, что к-грамматики являются частным случаем ок-грамматик: и, следовательно, иерархия Хомского для языков, определенных обычными грамматиками, не имеет места для ок-грамматик (по крайней мере, по причине, о которой говорит теорема 2.3,2). 3.3, Исследование грамматической сложности ок-грамматик и языков Таким же образом, как это было сделано для к-грамматик в 2.4.1, можно определить меры грамматической сложности /%яА. , fai&L и 6у1гиь& и для ок-грамматик. Определения их мы повторять не будем. Они получаются из определений 2.4,1, 2.4,2 и 2.4.6 про стой заменой к-грамматик ок-грамматиками. Так как не исключена возможность бесконечности Р -частей продукций ок-грамматик, то определение меры j может не иметь смысла.
Иерархические свойства языков, порожденных к-грамматиками
Теорема 3.3» I говорит о том, что каждый язык можно при сохранении условий теоремы определить ок-грамматикой с одноэлементным множеством нетерминальных символов. Это возможно благодаря языку, служащему условной частью ( V -частью) последней из продукций ок-грамматики из доказательства теоремы 3.3,1. Рассматривая эту продукцию, можно заметить, что эффективность в отношении к грамматической мере сложности ЇЇгЛ- достигается за счет включения ок-грамматикой определяемого языка в определение порождающей его ок-грамматики. Приведем аргументы в пользу того, что и такой патологический на первый взгляд факт имеет в определенном смысле свою интерпретацию в психологии и тоже в области представления знаний в системах искусственного интеллекта. Система обработки символов, которую моделирует ок-грамматика, как бы перенесла необходимое "знание" о своем поведении из долговременной памяти в свою какого-то рода "процедуральную" часть, позволяющую ей решить проблему принадлежности слов в данные языки. Для языков типа I иерархии Хомского такая задача, как известно, разрешима.
Теорема 3.3,2 интерпретируется подобным же образом. Обе эти теоремы интересно сравнить с эмпирическими выводами, касающимися декларативно-процедуральной контраверзы в области представления знаний в системах искусственного интеллекта, о которой подробно говорит Т.Виноград Г39І . Подробное сравнение такого рода мы здесь делать не будем. Теоремы 3.3.4 и 3.3.5 интерпретируются также, как было этому в предыдущей главе. Основные выводы настоящей работы можно сформулировать следующим образом: 1) Приведены определения двух специальных классов грамматик, которые в работе названы к-грамматиками и ок-грамматиками. Эти новые виды грамматик необходимы для возможности включения в грамматические модели продукционных систем таких их важных свойств, как целенаправленность вывода и возможность обучения за счет индуктивного вывода. 2) Формальное описание свойства целенаправленности и способности к обучению дало возможность доказать ряд теорем, на основе которых можно утверждать, что при наличии в формальной грамматике средств, обеспечивающих целенаправленность вывода и обучаемость, цроисходит понижение некоторых характеристик, связанных с оценками сложности продукционных систем, 3) Введен набор грамматических мер сложности для к-грамма-тик и ок-грамматик и доказана их взаимная независимость. 4) Проведена аналогия между к-грамматиками и ок-грамматиками и одной из психологических моделей человеческих рассуждений. Показано, что при использовании к-грамматик и ок-грамматик существенно снижаются требования к объему необходимой долговременной памяти и числу необходимых для определения данного языка (поведения) символов определенного сорта (нетерминальных символов соответствующей грамматики). В заключение работы выскажем некоторые соображения о возможных путях дальнейшего развития исследований в этой области. 1) Обобщением той модели целенаправленности, которая введе на в настоящей работе, является, например, такая модель, в кото рой определение вывода в к-грамматике изменено следующим образом: вхождение -частей продукций к-грамматики проверяется на каждом шаге вывода не только в активизированной на данном шаге цепочке, но и во всех цепочках, которые были использованы для ее вывода из начального символа данной к-грамматики. 2) Учитывая большой практический интерес, связанный с использованием иерархических продукционных систем (в которых, грубо говоря, меняется интерпретация символов по ходу вывода), было бы желательно исследовать соответствующие системы к-грамматик или ок-грамматик. Выбор на каждом шаге вывода той или иной грамматики системы этом случае зависел бы от выполнения связанного с ней условия применимости. 3) Порождающая сила грамматик, о которых мы говорили в двух предшествующих пунктах, по-видимому, не будет превышать порождающую силу обычных грамматик. Возможно, что для них удастся понизить значения некоторых мер сложности по сравнению с к-граммати-ками и ок-грамматиками, исследованными в данной работе.
Исследование грамматической сложности ок-грамматик и языков
В пользу удобства грамматической модели можно, кроме уже сказанного, привести и некоторые дальнейшие аргументы. Так например, ПС и формальные грамматики представляют секвенционную модель обработки символов. Такой же вид обработки предполагается и у человека на основании многих психологических исследований, связанных с человеческим мышлением. Аргументацию в пользу такой психологической гипотезы или ее более широкую трактовку можно найти в С 33 J (гл. 5.1), LZ1 (гл. 2.5) и в работе М.Минского С31 (гл. 1.2).
Вторая причина заключается в том, что применение правил ПС или формальной грамматики происходит недетерминированно в том смысле, что правила не применяются в какой-то определенной очереди. Грамматики определяют, благодаря этому свойству, не цепочку, а множество цепочек - язык. Таким образом, как это заметил уже Н.Хомский СЮ J , они выражают то, что может быть построено на их основе, а не то, что уже построено.
Третья причина - это известная связь формальных грамматик с вычислительными устройствами (машина Тьюринга и различные виды автоматов). С точки зрения искусственного интеллекта это имеет большое значение потому, что для моделей, создаваемых в рамках искусственного интеллекта, желательна не только связь с человеческим мышлением, но и возможность исследования вопросов, касающихся потенциальной возможности хотя бы частичной реализации этих моделей на вычислительных машинах.
Модель человеческих рассуждений на уровне, о котором мы говорили в разделе 1.2, не является подходящей для объяснения ряда свойств интеллектуального поведения человека. Приведем примеры этого.
Большое число эмпирических наблюдений экспериментальной психологии говорит в пользу целенаправленности процесса человеческого рассуждения. Этот процесс происходит так, что из всех возможных действий по переработки символьной информации выбираются только те, применение которых имеет смысл в данной проблемной среде, для достижения цели. Психологически обоснованные аргументы в пользу целенаправленности можно найти, например, в книге LZ1 (стр. 41) или [35J (стр. 217).
Второе важное свойство интеллекта - это способность обучения. Для нас особенно интересным является вопрос об обучении, связанном с проведением индуктивных выводов на основе построения граммати (см. например, работы [12] , Г14J , или хороший обзор Э.Б.ХантаГбЛ , раздел 7.1). К.В.Уилсон показывает в С 38] (гл. 5) возникновение таких подходов именно из психологических результатов. В главе Ш настоящей работы мы сделаем попытку трактовки проблематики обучения в смысле индуктивного вывода грамматик с другой точки зрения.
В следующих двух главах мы покажем возможность таких модификаций классической грамматической модели, которые позволят включить в рамки формальных исследований как свойство целенаправленности (в главе П), так и способность к обучению(в главе Ш). Нашей основной целью будет показать значение упомянутых выше свойств для повышения эффективности реализации на ЭШ процессов дедуктивного вывода, имитирующих человеческие рассуждения.
В разделе 1.3 мы писали об ограничении классической грамматической модели интеллектуальных процессов, которое проявляется в связи с целенаправленностью человеческих выводов. Действительно, продукционные правила формальных грамматик чувствительны только к вхождению их левых частей в цепочки, которые обрабатываются с их помощью, и не позволяют учитывать какие-либо иные условия их применимости.
В литературе можно найти довольно широкий диапазон подходов к удалению этого недостатка, основанных на управлении выводом в формальных грамматиках. С некоторыми подходами к решению этой проблемы нас знакомит работа [4] . В следующих разделах мы определим новую модификацию формальных грамматик с управляемым выводом - конвенциональные грамматики (к-грамматики) - которых находятся в близком отношении к условным грамматикам, введенным в рассмотрение М.В.Ломковской Г4] , [53 . В настоящей работе мы не будем заниматься спецификацией этого отношения, считая этот вопрос стоящим вне основных целей данной работы.
Похожие диссертации на Конвенциональные грамматики и их применение для исследования свойств продукционных систем
