Конвенциональные грамматики и их применение для исследования свойств продукционных систем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ

ГЛАВА I. ФОРМАЛЬНЫЕ ГРАММАТИКИ И ПРОДУКЦИОННЫЕ

СИСТЕМЫ.

1.1. Некоторые задачи искусственного интеллекта и их связь с продукционными системами

1.2. Обзор существующего положения

1.3. Некоторые нерешенные проблемы

1.4. Постановка задачи.

ГЛАВА П. КОНВЕНЦИОНАЛЬНЫЕ ГРАММАТИКИ.

2.1. Целенаправленность и управление выводом в грамматиках

2.2. Основные оцределения.

2.3. Иерархические свойства языков, порожденных к-грамматиками.

2.4. Грамматическая сложность к-грамматик и языков.

2.4.1. Оцределения

2.4.2. Независимость

2.4.3. Теоремы

2.5. Выводы.

ГЛАВА Ш. ОБОБЩЕННЫЕ КОНВЕНЦИОНАЛЬНЫЕ ГРАММАТИКИ

З.Х. Обучение и индуктивный вывод.

3.2. Основные определения.

3.3. Исследование грамматической сложности ок-грамматик и языков

3.4* Выводы

В последние годы проявляется тенденция к использованию вычислительных машин в областях, связанных не с классическими вычислениями, а с обработкой разного рода символьной информации. В частности, подобные задачи возникают в тех системах, работа которых основывается на знаниях, хранимых в памяти вычислительных систем. Это требует создания специальных средств для представления знаний и манипулирования ими. В настоящее время в качестве языков для представления знаний, как правило, используются либо логические исчисления, либо сетевые представления различного типа (семантические сети [13J , фреймы ЕЗ] , сценарии С34J ). В качестве языков манипулирования данными в подавляющем большинстве случаев используются различного рода цродукционные системы СИ] , Г 37J .

Продукционные системы являются естественным развитием модели формальных грамматик, созданных еще во второй половине 50-х годов Н.Хомским [9] . Другим источником возникновения современных продукционных систем является теория секвенциальных систем, которая развивалась еще в работах Э.Поста, а затем была использована в ставших классическими исследованиях Э.Ньюэлла и ГЧСаймона С33] .

Однако, имевшиеся до настоящего'времени исследования в области классификации типов формальных грамматик и секвенциальных систем, а также в области анализа и синтеза этих средств не могут быть прямо использованы для формализации существующих сейчас языков манипулирования знаниями. Это связано с тем, что продукционные системы, использованные для этих целей, имеют ряд отличительных особенностей (например, наличие управления при выборе продукций) , которые не позволяют использовать для них ранее построенные модели.

Это определяет актуальность данного исследования, в результате которого предлагается новая формальная модель продукционных систем, более адекватная реально существующим системам.

Таким образом, объектом исследования диссертации являются продукционные системы, применяемые цри решении задач, связанных с обработкой символьной информации. Такие системы в настоящее время активно используются при машинном доказательстве теорем, в системах принятия решений по управлению в сложных системах, в разного рода экспертных системах и в системах планирования целесообразного поведения роботов.

Целью работы является исследование нового предложенного в ней класса формальных грамматик, элементы которого названы конвенциональными грамматиками (в сокращении к-грамматиками). Эти грамматики позволяют формализовать процесс целенаправленного выбора грамматических правил для достижения поставленной цели. В ходе работы было проведено сравнение предложенной в диссертации модели с ранее известными моделями грамматик.

При решении рассматриваемых проблем были использованы методы математической логики, формальных грамматик и теории формальных языков.

Научная новизна работы заключается в следующем:

1) Предложен новый класс формальных грамматик (к-граммати-ки), у которых в отличии от ранее известных грамматик в продукциях в явном виде включены условия их применимости.

2) Для к-грамматик исследована проблема выводимости, дван анализ порождаемых ими языков и построена классификация этих грамматик, аналогичная известной ранее классификации грамматик Хомского.

- 6

3) Проведено сравнение соответствующих одинаковым по классификации уровням к-грамматик и классических грамматик. В результате этого сравнения установлено соотношение между языками, порождаемыми соответствующими по классификации грамматиками.

4) Доказан ряд теорем, позволяющих установить соотношение между различными типами к-грамматик с точки зрения мощности порождаемых ими языков.

5) Даны некоторые оценки сложности, связанные с необходимым числом продукционных правил, объемом памяти для хранения промежуточных результатов вывода и с необходимым для определения данной к-грамматики числом символов.

Практическая ценность результатов исследования к-грамматик заключается в теоретически обоснованном познании некоторых возможностей увеличения эффективности продукционных систем, играющих в настоящее время ключевую роль в архитектуре экспертных систем Г183 . Исследованные в работе к-грамматики при их применении в системах, использующих продукционные модели, могут позволить уменьшить необходимый объем памяти для хранения промежуточных результатов или вспомогательных информации.

Результаты работы докладывалист на:

1) международной конференции"Искусственный интеллект и информационно-управляющие системы роботов" в Смоленицах (ЧССР) в июле 1980г.;

2) семинаре по теории автоматов на . кафедре, вычислительной математики и вычислительной техники Естествознательного факультета Университета им. Л.Этвеша в Будапеште (ВНР) в апреле 1981г.;

3) международной конференции по теории автоматов,; языков и математических систем в Шалготаряне (ВНР) в мае 1984г.;

4) конференции молодых математиков и программистов Унив. им. Л.Этвеша в Будапеште. (ВНР) в мае 1984г.;

5) кафедре теоретической кибернетики Математико-физического факультета Унив. им.Коменского в Братиславе (ЧССР) в 1983 и 1984 годах;

6) семинаре лаборатории теории и проектирования больших систем ВЦ Ш СССР в 1981, 1983 и 1984 годах.

По теме диссертации автором опубликовано II работ: С203 - [29] и работа [321 .

Диссертация состоит из введения, трех глав, заключения и списка литературы.

Основные выводы настоящей работы можно сформулировать следующим образом:

1) Приведены определения двух специальных классов грамматик, которые в работе названы к-грамматиками и ок-грамматиками. Эти новые виды грамматик необходимы для возможности включения в грамматические модели продукционных систем таких их важных свойств, как целенаправленность вывода и возможность обучения за счет индуктивного вывода.

2) Формальное описание свойства целенаправленности и способности к обучению дало возможность доказать ряд теорем, на основе которых можно утверждать, что при наличии в формальной грамматике средств, обеспечивающих целенаправленность вывода и обучаемость, происходит понижение некоторых характеристик, связанных с оценками сложности продукционных систем.

3) Введен набор грамматических мер сложности для к-грамматик и ок-грамматик и доказана их взаимная независимость.

4) Проведена аналогия между к-грамматиками и ок-грамматика-ми и одной из психологических моделей человеческих рассуждений. Показано, что при использовании к-грамматик и ок-грамматик существенно снижаются требования к объему необходимой долговременной памяти и числу необходимых для определения данного языка (поведения) символов определенного сорта (нетерминальных символов соответствующей грамматики).

В заключение работы выскажем некоторые соображения о возможных путях дальнейшего развития исследований в этой области.

1) Обобщением той модели целенацравленности, которая введена в настоящей работе, является, например, такая модель, в которой определение вывода в к-грамматике изменено следующим образом: вхождение -частей цродукций к-грамматики цроверяется на каждом шаге вывода не только в активизированной на данном шаге цепочке, но и во всех цепочках, которые были использованы для ее вывода из начального символа данной к-грамматики.

2) Учитывая большой практический интерес, связанный с использованием иерархических продукционных систем (в которых, грубо говоря, меняется интерпретация символов по ходу вывода), было бы желательно исследовать соответствующие системы к-грамматик или ок-грамматик. Выбор на каждом шаге вывода той или иной грамматики системы этом случае зависел бы от выполнения связанного с ней условия применимости.

3) Порождающая сила грамматик, о которых мы говорили в двух предшествующих пунктах, по-видимому, не будет цревышать порождающую силу обычных грамматик. Возможно, что для них удастся понизить значения некоторых мер сложности по сравнению с к-граммати-ками и ок-грамматиками, исследованными в данной работе.

ЗАКЛЮЧЕНИЕ

1. Гладкий А.В. Формальные грамматики и язчки. М.: Наука, 1973, 368с.

2. Козелецкий Ю. Психологическая теория решений. М.: Наука, 1979, 504с.

3. Минский М. Фреймы для представления знаний. М.: Энергия, 1979, 151с.

4. Стоцкий Э.Д. Управление выводом в формальных грамматиках. Проблемы передачи информации, 1971, том 7, вып. 3, с.87-102.

5. Стоцкий Э.Д. Условные грамматики с рассеянным контекстом. Доклады Академии наук СССР (Математика), 1972, том 207, № 4, с. 796-799.

6. Тихомиров O.K. Информационная и психологическая теория мышления. В: Хрестоматия по общей психологии (Психология мышления). М.: Издательство московского университета, 1981, с. 328-331.

7. Фу К. Структурные методы в распознавании образов. М.: Мир, 1977, 319с.

8. Хант Э.Б. Искусственный интеллект. М: Мир, 1978, 558с.

9. Chomsky N. Syntactic Structures. The Hague: Mouton and Co., Publishers, 1957

10. Chomsky N. The logical basis of linguistic theory.1.: Proc. of the Ninth Intern. Congress of Linguists. The Hague: Mouton and Co., Publishers, 1964

11. Davis R., King J. An overview of production systems. In: Machine Intelligence vol. 8 /Elcock E. W., Michie D., eds./. Chichester: E. Horwood, 1977,p. 300-332

12. Feldman J. Some decidability results on grammatical inference and complexity. Information and Control 20,1972, p. 244-262

13. Findler N. V. /ей,/ Associative Networks — Representation and Use of Knowledge by Computers. New York: Academic Press, 1979. 462p.

14. Gold M. E. Language identification in the limit. Information and Control 10, 1967, p. 447-474

15. Gruska J. Some classification of context-free languages. Information and Control 14, 1969, p. 152-179

16. Gruska J. Descriptional complexity of context-free languages. In: Proceedings of Symposium Mathematical Foundations of Computer Science '73. Bratislava: Computing Research Center United Nations D. P.,1973, p. 71-83

17. Gruska J. Descriptional complexity /of languages/: A short survey. In: Proceedings of Symposium Mathematical Foundations of Computer Science '76. Lecture Notes in Computer Science vol. 45. Berlin Heidelberg -- New York: Springer-Verlag, 1976, p. 65-80

18. Hayes-Roth F., Waterman D. A., Lenat D. B. /eds./ Building Expert Systems. Reading, Massachusetts: Addison-Wesley Publishing Company, 1983. 444p.

19. Hopcroft J. E., Ullman J. D. Formal Languagesand their Relations to Automata. Reading, Massachusetts: Addison-Wesley Publishing Company, 1969. 242p.

20. Kelemen J. Prolegomena to a computational study of cognition. Automata Theoretic Lettersvol 1/1981. Budapest: Lorand Eotvos University, 1981. 34p.

21. Kelemen J. Remarks on Knowledge representation /extended abstract/. In: Proceedings of International Conference on Artificial Intelligence and Information-Control Systems of Robots. Smolenice /CSSR/, June 30 July 4, 1980, p. 124-127

22. Kelemen J. Umeld inteligencia ako- teoretick^ discipline. 1п^гтаспё эу^ёту 9, No. 4, 1980, p. 305-316

23. Kelemen J. Three computational problems concerning knowledge. Computers and Artificial Intelligence 1, No. 2, 1982, p. 163-169

24. Kelemen J. Cognition and computation — An essay on artificial intelligence. Studia psychologica 23, No. 3, 1981, p. 205-213

25. Kelemen J., Kalas I. Podstata a prostriedky ramco-vej reprezent£cie poznatkov. Informacr^ зу81ёшу 11, No. 2, 1982, p. 103-114

26. Kelemen J. Gnozeologicky status vypoctovych teoril myslenia /poznamka к tёme umeld inteligencia/. Filozofia 38, No. 4, 1983, p. 476-485

27. Kelemen J. Poznatkovё inzinierstvo, expert-пё sys-tёmy а umel£ inteligencia. In: Vyssl formy pou2i-vdnl po61ta68. Praha: D&n techniky 6SVTS, 1983, p. 33-451

28. Kelemen J. Conditional grammars — motivations, definition and some properties. In: Proceedingsof Conference on Automata, Languages and Mathematical Systems. Salgotarj^n /Hungary/, May 21 23, 1984

29. Kelemen J. A grammatical model of goal-direstness and learning in cognition. In: Proceedings of International Conference of Young Programmers and Mathematicians. Budapest, May 24- 25, 1984

30. Knuth D. E. Big omicron and big omega and big theta. SIGACT News vol. 8, 1976, p. 18-24

31. Mikulecky P., Kelemen J. Supervising expert systems: An attempt to organise certain mathematical software intelligently. In: Proceedings of Berliner Informatik-Tage '82. Berlin /GDR/: Humboldt Uni-versitat, 1982, p. 313-325

32. Newell A., Simon H. A. Human Problem Solving. Englewood Cliffs, N. J.: Prentice-Hall Publishing Company, 1972. 920p.

33. Schank R. C., Abelson R. P. Scipts, Plans, Goals and Understanding. New York: Lawrence Erlbaum Associates, 1977

34. Simon H. A. Models of Discovery. Dordrecht: D. Reidel Publishing Company, 1977. 456p.

35. Simon H. A. Information processing models of cognition. Annual Revue of Psychology, vol. 30, 1979, p. 363-396

36. Waterman D. A., Hayes-Roth F. /eds./ Pattern-Directed Inference Systems. New York: Academic Press, 1978. 658 p.

37. Wilson К. V. From Associations to Structure: The Course of Cognition. Amsterdam: North-Holland, 1980. 338 p.

38. Winograd Т. Frame representation and the declarative-procedural controversy. In: Representation and Understanding — Studies in Cognitive Science /Bobrow D. G., Collins A., eds./. New York: Academic Press, 1975, p. 185-210