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

■Л 4 ; ^

САНКТ-ПЕТЕРБУРГСКИЙ Г0СУДАРСТ23ННШ УНИВЕРСИТЕТ

на правах рукописи

ЩВДРБАЕВ ДОСШ ХШГГОБИЧ ФУНКЦИОНАЛЬНАЯ ШДЕЛЬ ПРЕДСТАВЛЕНИЯ ЗНАНИИ

□1. 01.09 - математическая кибернетика

АВТОРЕФЕРАТ ДНССврТНЦИЗ! К2 СС15СКЗКН9 СТЭПЭНИ

кандидате физико-математических кзук

САНКТ-ПЕТЕРБУРГ 1992

Работа выполнена на кафедре технологии программирования факультета прикладной математики - процессов управления Санкт-Петербургского государственного университета.

доктор физико-математических наук, профессор ТУБОБ Виталий Алексеевич

доктор технических каук, профессор Е2ЛЕПИН Рональд Аполлонович. кандидат физико-матеыатических нау ЯЗЕВ Алексей Шхайлович.

Санкт-Петербургский институт ннфор

Зашита состоится

43

ка заседании специаиаироаанкого совета К 053.57.16 по присужде ученой степени кандидата физико-математических наук в Санкт-Пете бургском государственном университете по адресу: 150004, Санкт-Е тербург, В. О., 10-я линия, дом 23, ауд. 88.

С диссертацией можно ознакомиться з Еаучной библиотеке уни верситета ( Санкт-Петербург, Университетская набережная, дом 7/9

Автореферат разослан " Ученый секретарь специализированного совета

Научньй руководитель:

Официальные оппоненты:

Ведущая организация:

1992 г.

В. 0. Горьковой

РОСОИ^-АЯ

С-Г-УЛ ■ V ?-.Я

- з -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность Представление зкзккй как методология моделирования и формализации концептуальных знаний, ориентированное на компьютерную обработку, является наряду с задачами приобретения и обработки знаний одной из основных и важных тем, относящихся к инженерии знаний. Б задачах искусственного интеллекта сформулированы два основных направления решения данной проблемы: когнитивное, основанное на принципах организации человеческой памяти и логическое, использующее строгую математическую формализацию и логическую полноту. Но с развитием каждого из указанных подходов выявились их недостатки и ограниченность, вследствие чего возникает проблема совмещения различных подходов, фи этом необходимо либо введение многоуровневой архитектуры, имеющей на каждом уровне свой язык, либо создание иной модели знаний, позволяющей адекватным образом реализовывать основные конструкции известных моделей и совмещать их в рамках одной системы. В качестве такой модели представления знаний была выбрана функциональная модель, основанная на процессно-ориеятированных методах программирования, предложенных В. А. Тузовым. В основе этой модели лекит принцип активизации, сущность которого заключается в том, что исходные данные (знания) отображаются не на пассивные структуры - списки, деревья, и т.д., а на активные - функции, суперпозиции функций, и т.д. Ери этом актуальным становится выбор адекватных средств представления знаний, использующих функциональную модель и удовлетворяющих основным свойствам знания как специфического типа информации. В

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

Целью работы является :

- развитие процессно-ориентированных методов программировав предложенных В. А. Тувовыы, 'применительно к представлению и обработ знаний ;

- исследование возможности создания адекватного средства пре стазлекия знаний, позволянпэго объединить преимущества известных моделей к методов ;

- исследование возможности реализации функциональной модели представления семантической сети у. фрейма ;

- исследование вопросов, связанных с механизмом наследования и управления выводом н функциональной модели семантической сети и фреймах.

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

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

- Б -

мущэства данного подхода при создании систем представления знаний, использувщих совмещение когнитивного представления знаний и логического вывода.

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

Аппробация работы. Основные результаты работы были опубликованы в работах С 1,2 3, докладывались и обсуядались на научных семинарах и заседаниях кафедры технологии программирования и лаборатории функциональных методов программирования факультета прикладной математики - процессов управления Санкт-Петербургского государственного университета, на 1-ой Всесоюзной конференции по Форту: "itopT и его расширения в системах управления" ( г.Ленинград, 17-19 апреля 1991 г. ).

Структура и объем работы. Диссертация излоглена на 113 страницах и состоит из введения, четырех глав, заключения, приложения и списка литературы, содержащего 107 названий.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

I

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

- в -

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

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

В п.1.2 описаны процессно-ориенткрованные методы программирования. Сбшэя схема процессно-ориенткровакного подхода заключается в следующей. 5о-первых, класс X исходных обьэктоз отображается на класс Р параметризованных процессов:

Т : X -> Р С У1,У2,... ,УМ ) , где Ух - формальные параметры данного класса объектов. Ео-вто-рых, каждой функции Г(х1,х2,...,хп) (х^Х) ставится в соответствие набор операций А1,А2,... ,АИ, которые являются фактическими параметрами, определяющими п процессов:

Х1(А1,А2,... ,АН), Х2(А1,А2,... ,АН),... , ХП(А1,А2,... ,АК).

Параллельное выполненние этих процессов вычисляет значение функции Г. Их запуск и завершение осуществляется главным процессом, описание которого и является описанием функции Т : : Т (: А1 А2 ... АЫ :) < инициализации <запуск> <ааверЕениэ> ; Данный подход в лаконичной форме можно представить соотношением :

- 7 -

Данные + Активизация = Программа.

В п. 1.3 приводится процессно-ориентироЕанный способ реализации функциональной модели представления знаний. Знания в функциональной модели могут как сами обрабатывать информацию, так и служить объектом обработки со стороны других знаний. Эта двойственность предполагает наличие двух форм представления знания как процесса: внешний (пассивную), используемую как информация для других знаний и внутреннюю (активную), являющуюся записью процесса, готового к выполнению.

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

Примеры пассивной формы представления: (# сеть фреймы продукции #) - список; [п 123 345 567 п] - массив чисел; [t Автореферат диссертации t] - текст; [f 1 2 dup rot - + . f] - функция на Sopre.

Список преобразуется в активную форму в процессе компиляции, после чего он представляет собой суперпозицию функций, содержащую обращения к переменным типа defer : wd, num. Is, tx, ref, arrnum, arcfa и т. д. Каждый элемент списка связывается с такого типа параметром, преобразуясь а структуру вида:

(")М 1 <тедо злемента> Р, где (")М является левым параметром, оставляющем на стеке адрес элемента и передающим управление на правый параметр Р, 1 - есть

- а -

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

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

Вторая глава посвящэка вопросам представления семантических сетей на основе функциональной модели.

В п. 2.1 дается характеристика существующих моделей сетей. Поскольку характер сети определяется природой вершин и типами отношений, определенных между ними, то используя функциональную модель можно обобщить понятие сети, допустив в ней произвольные типы отношений. Однако семантика отношений и процедурные знания пользователь должен определять сам. Это вытекает из уникальности знаний и отношений мееду ними.

Б п. 2. 2 представлена функциональная модель семантической сети. Дается обоснование выбора семантической сети в качестве объекта моделирования, приводится синтаксис языка описания сети, вводятся типы отношений, допустимых в ней. В данной модели рассмотрены отношения пяти типов:

- классификация, обеспечивающая тип связи 'Чг^апсе-оГ1;

- обобщение, устанавливающее отношение "^э-а";

- агрегирование, соответствуют?© связи "раг1:-оГ";

- ассоциация, реализующая отношения вида "тетЬег-оГ";

- обладание, позволяющее приписывать объектам свойства с помощью связи "Ьаз-аЬЬПЬ^е".

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

фрагмент описания синтаксиса функциональной модели семантической сети:

<семантическая_сеть> ::

япе^ <имя_сети> <определения_вершин> Бпе^ ;; <определения_вершин> :: <определения_объектов» !

<определения_действий> ;; <определения_обгектов> :: <опред_об,ьекга> -С<опред_об,ьекта>> ;; <опред_объекта> :: : <вершка>

<тип_связи» <зёршкна-1» {(- <информация» -)> ! <вершинз_дейстэкя> {<вершины> > -С(- <информация» -)3- ;; <определенкя_д5йствий> :: <опред_действия> -С<опред_дейстзия>> ;; <опред_действия> ::

Г: <вершина> <описание_дейстзкя> {(- <информация» -)> ;; <описакие_дейстзия> ::

<последоват_слов_определекных_в_РРС+2Т_и_г.сльзователе$.1> ;; <вершины> :: < вершина» -С < вершина» > ;; <вершина» :: <идентификатор» ;; <имя_сети> :: <идентификатор» ;; <тип_свяаи> :: 1пз1апсе-оГ ! ¿з-а ! раК-оГ !

тетЬег-оГ I Ьа5-а1;1;г1Ь ;; <информация» :: [<тип> «последовательность ^анных_,гипа> <тил>] ! (# <список» #) ;;

- 10 -

<тип> :: ni t I f I w ! 11 g! г! о ; ;

На функциональной модели сети определены операции:

- установление связи между вершнами;

- аннулирование связи;

- определение контуров и циклов в сети;

- определение вершин, достижимых из заданной вершины ( транзитивное замыкание ) ;

- определение всех вершин, ссылающихся на заданную вершину;

- определение вершин достижимых из заданной вершины в обратном направлении ( обратное транзитивное замыкание );

- копирование, распечатка сети и ряд других.

Бее операции определены как для работы с конкретными типами отношений, так и с произвольными. Это позволяет осуществлять поиск объектов по требуемому типу отношений и тем самым реализовать механизм наследования.

IL 2.3 посвящен описанию реализации функциональной модели семантической сети на языке системы ZT (система обработки слож-ноорганиэованной информации В. LТузова), являющимся расширением языка Forth FPC.

Третья глава посвящена управлению выводом в семантических сетях и способам реализации запросов в ней. В п. 3.1 рассмотрены алгоритмы, использующие логическую парадигму представления семантических сетей:

- алгоритм дедукции на раскрашенных сетях, описываемых хорнов-скими дизъюнктами;

- алгоритм, связанный с трансформацией сети;

- алгоритм нахождения пути в сети.

В б. 3. 2 предложен способ реализаций аапросов в функциональной модели сети. Суть предложенного алгоритма состоит в том, что иэ веек параметров отношений определяются только требуемые, после чего управление' передается на главный процесс, реализующий запрос. Этот процесс подает семантическую езть на интерпретацию, в результате чего отработают параметры отношений, определенные пользователем. В данной модели сети определены следующие виды запросов:

1) '?is-a. б! - устанавливает предков вершины по связи вида

•Чз-а";

2) ?раг1-оГ - определяет, частью какого объекта является

вершина б1;

3) ?ра^э з1 - решает обратную задачу, определяя иа каких

объектов состоит б1;

4) ?-> - устанавливает тип связи между двумя вершинам!. Аналогично строятся запросы и по другим видам отношений:

1пз1апсе-оГ, тетЬег-оГ, ¡таэ-а^ггЬ. В п. 2.3 рассмотрен способ вывода, именуемый перекрестным поиском. Этот способ означает поиск отношений между концептуальными объектами и ответ на запрос путем обнаружения вершины, связывающей вершины, фигурирующие в запросе. Для этого для каждой вершины определяется множество вершин, достижимых из вершины или ссылающихся на вершину и ищется пересечение этих множеств. Запрос формируется в следующем виде:

п ?аотпос1еБ б 1 б з" ... бп. Обобщением этого метода является способ сопоставления частей сетевой структуры, изучении которого посвящен п. 3. 4. Он основан

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

В четвертой глазе рассмотрены вопросы, связанные с представлением знаний фреймами М. 1&!нского. Фрейм есть сеть состоящая из терминальных слотов, содержащих конкретную информацию и процедур, обеспечивающих обработку информации и выполнение запросов к другим фреймам. Между фреймом и слотами установлен тип отношений "целое - часть". В свою очередь фреймовая система является частным случаем семантической сети и представляет собой иерархическую структуру с классификационными и обобщающими свойствами типа " абстрактное - конкретное " и "целое -часть". Фиксированная структура фрейма позволяет существенно упростить обработку знаний, представленных межфреймовой сетью.

В п. 4.1 приводится описание процессно-ориентироЕанной модели фреймовой сети, а в п. 4.2 рассматриваются вопросы наследования, управления выводом, динамического порождения фреймов-экземшш-

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

slots: n name Is age num sex wd residence tx occupation vd ... sin fr На следующих ступенях иерархии располагаются фреймы-шаблоны класса. Здесь конкретизируется отдельные слоты верхнего уровня и могут вводятся новые, характеризующие данный шаблон. : student_men is-a people

slots: m course num ^roup num

marks Is ... slm tx tempadr residence [v student of S. -?. Univ. w] si! occupation vd: male si! sex ; : teacher is-a people

slots: 1 salary num subject wd adress residence

laboratory vd . .. plan framsplan [vf computer science v] si! subject ; frameclass;

Вместе с шаблоном будет создан одноименный класс параметров, содержащий как новые слоты, так и слоты предка, например: cl: <teacher +class <people salary subject ... plan cl; Иерархическая стуктура фреймов при тагам подходе адекватным образом поддерживается иерархией параметров. Это позволяет довольно просто реализовать механизм наследования и управление выводом

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

Экземпляры класса можно порождать динамически: make-instance azazello student

1. На основе процессно-ориентированных методов программирования разработана функциональная модель представления знаний.

2. Предложен способ реализации семантических сетей на основе функциональной модели знаний.

3. Описаны алгоритмы реализации управления выводом в семантической сети.

4. Представлена процессно-ориентированная модель представления фреймов.

ПУБЛИКАЦИИ

1. Кыдырбаев Д. X Процессно-ориентированный подход к представлению знаний /СПбГУ - С.-П.: 1992. - 9 с. - Деп. в ВИНИТИ 3.08.1992 -N 2502 - Е92.

2. Кыдырбаев Д. X. Ероцессно-ориентированное представление сетей /СПбГУ - С. -П.: 1992. - 9 с. - Деп- в ВИНИТИ 07.09.1992 -

N 2724 - В92.

[t host 16 room 25/2 t] slf tempadr ;;

ОСНОВНЫЕ РЕЗУЛЬТАТЫ.