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

санкт-петербургский государственный университет

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

кьщырбаев досым шмтович функциональная модель представления зе4нии

01. 01. 09 - математическая кибернетика

автореферат диссертации :~:а соискание ученой степени кандидата физико-математических наук

санкт-петербург 1992

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

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

доктор физико-математических на' профессор ГУЗОВ Виталий Алексее:

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

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

Ведущая организация: Санкт-Петербургский институт ин

мзтики и автоматизации РАН

Зашита состоится " ¿S " —«?_1992_г. а ^3

на заседании специаизированного совета К 053. 57.15 по лрису ученой степени кандидата физико-математических нау>: в Санкт-П бургском государственном университете по адресу: 190004, Санк тербург, В.О. , 10-я линия, дом 33, ауд. 88.

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

Автореферат разослан " Ujxjl^J^i 1992 г. Ученый секретарь

специализированного совета

Е ffi. Горько

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

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

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

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

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

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

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

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

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

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

- Б -

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

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

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

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

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

I

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

- Б -

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

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

В п.1.2 описаны процэссно-ориэнтировакные методы программирования. Общая схема процеосно-ориентированнсго подхода заключается з следующем. Бэ-первых, класс К исходных объектов отображается на класс Р параметризованных процессов

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

х1(А1,А2,... ,АН), х2(А1,А2,.. . ,уШ),. .. ,хп(А1,А2,... ,АЬ1).

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

- 7 -

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

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

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

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

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

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

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

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

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

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

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

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

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

- агрегирование, соответствующее связи "раг^оГ";

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

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

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

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

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

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

<тип_связи> <зершна-1> {(- <инфорыацня> -)> ! <вершина_дэйствия> "С<Еериины>> •£(- <информация> -)> ;; <определения_дейсгвкй> :: <опрэд_дэйствия> {<опред_действия>> ;; <опред_действия> ::

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

<последоват_слоз_определенных_в_ГРС+2Т_и_пользоЕателем> ;; <вершины> :: <вершина> -(<зершина>> ;; <вершина> :: <идентификатор> ;; <имя_сети> :: <идентификатор> ;; <ткп_свяэи> :: ^йапсе-оГ ! ! рагй-оГ !

тетЬег-оГ I Ьаэ-аШЧЬ ;; <информация> :: С<тип> <последователъность_данных_типа> <тип>] ! (/ <список> #) ;;

- 10 -

<тип> :: n! t! fl w! 1! g I г! o;;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) ?1з-а - устанавливает предков вершины 31 по связи вида

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

вершина

3) ?рагь8 - решает обратную задач;/', определяя из каких

объектов состоит я!;

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

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

п ?соптпобез ... эп.

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

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

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

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

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

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

slots: m course num group num

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

slots: 1 salary num subject vd adress residence

laboratory wd ... plan framsplan Cw computer science w] si! subject ; frameclass;

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

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

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

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

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

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

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

ПУБЛИКАЦИИ

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

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

N 2724 - В92.

tt host 16 room 25/2 t] si! tempadr ;;

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