Содержание к диссертации
Введение
Глава 1. Структура и основные принципы построения семантических сетей 9
1.1. Ассоциативная память и ассоциативные сети 9
1.2. Эволюция семантических сетей 10
1.2.1. Разработка методов представления знаний с помощью сетей .10
1.2.2. Уровни представления базисных элементов в семантических сетях 21
1.3. Неоднородные семантические сети 32
1.4. Отношения в семантических сетях 36
1.4.1. Бинарные отношения и их свойства 36
1.4.2. Правила связывания переменных 39
Глава 2. Алгебраические свойства отношений в неоднородных семантических сетях 41
2.1. Классификация отношений по свойствам рефлексивности, симметричности и транзитивности 41
2.1.1. Отношения, определяемые своими свойствами 41
2.1.2. Выделение базисных отношений 56
2.2. Отношения в неоднородных семантических сетях 57
2.2.1. Вершины, определяемые набором атрибутов 57
2.2.2. Классификация отношений, выраженных через атрибуты 60
2.3. Построение матриц совместности 72
2.3.1. Определение вектора совместности бинарных отношений 73
2.3.2. Матрицы совместности отношений, порожденных атрибутами событий 75
2.3.3. Комбинации отношений из 1R 89
2.3.4. Функциональные отношения 98
Глава 3. Алгебраические операции и ассоциативные отношения на вершинах НСС 100
3.1. Типы отношений в неоднородной семантической сети 100
3.2. Операция слияния узлов семантической сети 101
3.2.1. Представление в НСС комбинаций бинарных отношений и отношений большей арности 101
3.2.2. Плюральная решетка 103
3.2.3. Пополнение множества вершин семантической сети плюральными объектами 104
3.2.4. Использование слияний вершин для представления неполной информации 108
3.3. Некоторые приложения плюральной теории 114
Глава 4. Динамическое формирование отношений ВНСС 117
4.1. Dom- и Im-слияния отношений 117
4.2. Dom- и Im-вложения отношений 122
4.3. Алгебраические свойства операций Dom- и Im-слияния 127
4.4. Свойства отношений Dom- и Im-вложения 130
4.5. Полурешетки D и АО и их свойства 136
4.6. Квазирешетка QL 138
Глава 5. Динамическая семантическая сеть 140
5.1. Построение динамической семантической сети 140
5.1.1. Метки событий сети 140
5.1.2. Архитектура динамической сети 142
5.2. Правила замыкания и перехода 144
5.2.1. Процедура замыкания ф 145
5.2.2. Процедура перехода \|/ 147
5.2.3. Траектория системы 149
5.3. Возмущения и устойчивость системы 150
5.4. Пример. Динамика экологической системы 151
Заключение 158
Список литературы 160
- Разработка методов представления знаний с помощью сетей
- Отношения в неоднородных семантических сетях
- Представление в НСС комбинаций бинарных отношений и отношений большей арности
- Алгебраические свойства операций Dom- и Im-слияния
Введение к работе
Актуальность работы. В настоящее время существует большой класс интеллектуальных систем, использующих в качестве модели знаний семантические сети. С помощью семантических сетей оказалось возможным описать большой класс семантических связей между объектами в различных предметных областях. Это явилось основой для построения моделей знаний, в частности, в областях с плохой структурой.
Основными преимуществами семантических сетей являются возможность построения иерархий класс-подкласс и часть-целое, с помощью которых осуществляется наследование свойств; использование имплицитной информации; определение различных отношений на вершинах сети путем пометки соответственных дуг - в неоднородных семантических сетях; возможность приписывания концептам множества атрибутов и для каждого имени атрибута - задания множества допустимых значений; построение структурных отношений на концептах с общими атрибутами.
С помощью семантических сетей построен ряд интеллектуальных систем для представления семантики естественного языка, понимания текстов на естественном языке. Создан ряд обучающих систем по географии, астрономии, космонавтике. Системы, основанные на семантических сетях, используются для моделирования в области экологии, оценки состояния природных ресурсов, социологии и других областях.
Однако большинство исследований в настоящее время посвящено прикладному применению семантических сетей. Уделяется недостаточно внимания исследованию их теоретических аспектов. Появление динамических систем, основанных на знаниях, сделало необходимым изучение динамических формальных структур в семантических сетях.
С этой целью предложена семантическая сеть, в которой изменение состояния системы может моделироваться изменением топологии сети. Разработан способ построения динамической неоднородной семантической сети и алгоритм изменения ее топологии. Для этого введены новые операции, которые позволяют склеивать вершины и дуги сети. Применение таких операций возможно как на этапе разработки, так и в процессе вывода. Предложенный метод позволяет представлять неполную и недоопределенную информацию.
Динамические сети позволяют естественным образом интегрировать различные парадигмы моделирования. С помощью таких сетей станет возможным решить большой класс задач, не формализуемых в рамках статических сетей. Область применения динамических сетей -моделирование сложных систем, законы поведения которых не имеют аналитического описания, а задаются лишь эмпирическими правилами, изменяющимися в зависимости от состояния системы.
Цель и задачи работы. Основной целью данной работы является разработка метода построения неоднородных семантических сетей с изменяющейся топологией для представления знаний в интеллектуальных системах, исследование алгебраических свойств основных классов отношений и операций преобразования топологии семантических сетей. Для этого были решены следующие задачи:
классификация и построение базиса структурных отношений на основе их свойств рефлексивности, симметричности и транзитивности и матрицы совместности;
разработка основ плюральной теории и ее использование для представления неполной и недоопределенной информации;
исследование операций преобразования топологии неоднородных семантических сетей;
построение динамической семантической сети (ДНС);
- разработка алгоритма функционирования системы, основанной на
ДНС, с заданным порождающим множеством событий.
Предмет исследования - представление зналий в моделировании открытых систем, не имеющих исчерпывающего априорного описания, законы поведения которых задаются не только набором формул, но и множеством эмпирических правил и связей.
Объектом исследования являются базы знаний, представленные двухкомпонентной неоднородной семантической сетью. В основу исследований положены операции изменения топологии семантических сетей, их алгебраические свойства и способы отражения изменений системы с помощью слияния узлов и дуг сети.
Научная новизна работы. В работе получены следующие новые научные результаты:
определена матрица совместности как дополнительная характеристика бинарных отношений;
предложен способ нахождения этой матрицы для комбинации нескольких отношений;
определена операция слияния вершин семантической сети;
определены операции Dom- и Im-слияния на множестве бинарных отношений;
исследованы свойства операций преобразования топологии семантических сетей;
показана применимость этих операций для задач вывода в динамических семантических сетях и моделирования поведения;
описан алгоритм функционирования системы, представленной двухкомпонентной ДНС;
сформулировано достаточное условие устойчивости полученной системы.
Апробация работы. Основные результаты работы докладывались и обсуждались на международной конференции «Интеллектуальное управление: новые интеллектуальные технологии в задачах управления ЮТ'99» в Переславле-Залесском (1999), на VII национальной конференции по искусственному интеллекту в Переславле-Залесском (2000), на международной научно-технической конференции и молодежной научной конференции "Интеллектуальные САПР" в Дивноморске (2000), на IX Международной конференции «Знание - Диалог - Решение KDS-2001» в Санкт-Петербурге (2001). Доклад «Метод представления плюральных конструкций в неоднородных семантических сетях» был удостоен гранта на XXVIII Международной конференции и Дискуссионном научном Клубе "Новые технологии в науке, образовании, телекоммуникации и бизнесе" IT+SE'2001 в Гурзуфе (2001).
Основное содержание работы.
В первой главе по этапам прослеживаетЬя развитие семантических сетей с момента зарождения до настоящего времени. Основное внимание уделяется теоретическим разработкам, которые повлияли на современное состояние семантических сетей. Кроме того, в этой главе приводятся определения и соглашения, используемые в работе.
Вторая глава посвящена исследованию и классификации бинарных отношений с различными комбинациями свойств рефлексивности, симметричности и транзитивности. В этой главе введен дополнительный критерий - матрица совместности, - который наряду с вышеперечисленными свойствами позволяет однозначно определить любое отношение в неоднородной семантической сети, имеющее место между событиями с общими атрибутами. Разработаны правила сложения матриц совместности для построения комбинаций отношений.
В третьей главе определяется операция слияния вершин семантической сети, и исследуются ее свойства. Доказывается, что с ее
помощью становится возможным без потери информации понижать арность отношений, и, в частности, заменять n-арные отношения бинарными; заменять комбинацию нескольких бинарных отношений одним; представлять неполную и недоопределенную информацию; вводить объемно неопределенную информацию.
В четвертой главе определяются две новые операции на отношениях семантической сети - операции Dom- и Im-слияния, - которые позволяют склеивать несколько разных отношений в одно новое. Вводятся соответствующие им два отношения частичного порядка: Dom- и Im-вложения. Доказан ряд теорем об алгебраических свойствах этих операций и отношений; о взаимном выражении отношений Dom- и Im-вложения; о необходимых и достаточных условиях того, что одно отношение является Dom- (или Im-) частью другого.
В пятой главе строится динамическая семантическая сеть с переменной топологией, обладающая континуальной компонентой. На каждом такте дискретного времени топология сети изменяется посредством применения операций слияния вершин и Dom- и Im-слияния отношений. Разработан алгоритм функционирования такой системы. Он представляет собой цикл, состоящий из двух частей - процедуры синхронного замыкания и процедуры перехода в следующее состояние. Задается также условие выхода из цикла. Вводятся понятия возмущения и устойчивости траектории динамической сети; доказывается достаточное условие устойчивости описанной системы. В качестве примера описывается система, описывающая гидрологические, гидробиологические и биологические процессы в Азовском море. Строится алгоритм работы такой системы, и приводятся примеры применения каждой из операций на вершинах и дугах сети, описанных в предыдущих главах.
Разработка методов представления знаний с помощью сетей
Всеми признано, что идея представления человеческих знаний с помощью семантических сетей впервые представлена в работах Р. Куиллиана. Он предложил ассоциативную сетевую модель «семантической памяти» в 1966 году. Задачей такой сети было формальное представление «объективной» части значений слов, с тем, чтобы было возможно «человекоподобное» использование этих значений. Система Куиллиана состояла из узлов, взаимосвязанных с помощью разнообразных ассоциативных связей. Такое представление отражает организацию обычного толкового словаря. Узлы рассматриваются как понятия слов, а связи, указывающие из одного узла в другой, образуют определение, точно так же, как составлены словарные определения - из последовательности слов, определяемых где-то еще в этом же томе. В этой структуре каждый понятийный узел рассматривается как глава плоскости, которая сохраняет это определение.
Модель семантической памяти Куиллиана может служить системой обобщенного дедуктивного представления знаний. Было предложено несколько примеров техники вывода, основанных на понятии поиска пересечения: даны два слова, возможные связи между ними могут быть выявлены путем не направляемого поиска в области, окружающей плоскости этих слов. Этот поиск производится с помощью распространения в сети сигнала активизации определенного вида. Поиск расходится по связям от двух начальных плоскостей ко всем плоскостям, к которым ведут указатели, пока не найдется точка пересечения. Пути от узлов-источников к точке контакта двух «сфер активности», сформированных процедурой поиска, будут определять потенциальную связь между двумя понятиями слов. В таком случае, информация, введенная в одной структуре ссылок, может быть использована для ответа на запросы, заданные в другой системе. Использование имплицитной информации, информации, не занесенной в явном виде, является одной из наиболее важных особенностей такой модели памяти.
Причина того, что некоторые неявные свойства могут быть выведены из такой памяти, частично заключается в использовании связи класс-подкласс. Понятие может быть определено в терминах более общего понятия и некоторого определяющего свойства, которое является комбинацией атрибута и определенного значения этого атрибута. При таком представлении, свойства, истинные для класса предполагаются истинными и для всех его подклассов. Таким образом, семантическая сеть представляет комбинацию двух важных типов особенностей памяти -таксономическую иерархию надкласс-подкласс и описание свойств (пары атрибут-значение) для каждого класса.
В проекте TLC - "Teachable Language Comprehender" [84] -ассоциативная модель памяти используется как основа базы знаний для чтения текстов. В TLC свойства концептов формально определяются как атрибут, значение и, возможно, некоторые «подсвойства». Свойства используются в определениях единиц информации (units), которые представляют собой понятия объектов, событий, идей, утверждений и т.д. Юнит определяется через свой надкласе и набор детализирующих свойств. Для чтения в TLC применена описанная выше технология пересечения, чтобы найти связь между словами, встретившимися в тексте.
Но успех TLC в чтении текстов был довольно ограничен. Неспособность достигнуть понимания, по крайней мере, частично объяснялась недостаточным набором типов связей, а также тем фактом, что в процессе поиска не принимались в расчет разнообразные значения связей. Однако эти работы легли в фундамент .всех дальнейших исследований в области семантических сетей [91, 92, 93].
Семантические сети, описанные в [62], являются прямыми предвестниками современных сетей. В этой работе сеть рассматривается как простая иерархия классов понятий, таких как Животное, Птица, Канарейка. К каждому узлу присоединен набор свойств, определяющих соответствующее ему понятие («имеет кожу», «имеет крылья», «желтого цвета»). Поскольку более общие свойства хранятся на более высоких уровнях иерархии, можно предположить, что вывод утверждения «Канарейка имеет кожу» займет больше времени, чем «Канарейка желтого цвета». В этой работе впервые сформировалось понятие наследования свойств в семантических сетях. Кроме того, здесь же возникло понятие семантического расстояния между понятиями, то есть, количество связей, которые нужно пройти между двумя узлами.
Другой значительный проект, возникший непосредственно из TLC [59, 60], состоит в использовании семантических сетей как структурированных данных в реализованной обучающей программе-инструкции. Программа SCHOLAR имеет базу знаний, которая описывает в сетевых терминах географию Южной Америки. Студент может участвовать в смешанном диалоге с системой, спрашивая и отвечая на вопросы о базе данных. Система SHOLAR внесла важный вклад в развитие семантических сетей. Здесь впервые возникло различие между концептуальными (понятийными) единицами, такими, как «долгота» и единицами-экземплярами, такими, как «Аргентина». В этой же работе связям впервые были присвоены имена. Еще одним важным прецедентом в SCHOLAR стало добавление в декларативную структуру процедур. Функции, ассоциированные с юнитами, используются для активного вывода свойств, которые не были установлены как декларативные факты.
Работа С. Филлмора [66] по лингвистическим case-структурам сфокусировала внимание на глаголах. В этой работе при обработке естественного языка с помощью семантических сетей, предложение рассматривается как модальность вкупе с высказыванием, где модальность включает в себя такую информацию, как время, настроение, стиль, вид; а высказывание есть глагол и множество заполняемых случаев (cases). Тот факт, что свойства в семантических сетях объединяются вокруг узлов, сделал узлы идеальным местом для прикрепления к ним случаев. Если представить узел, как глагольный концепт, ассоциированные с ним пары атрибут/значение легко могут быть заменены парами случай/заполнитель.
В статье "What s in a link" [95] Вудс поднял вопрос о логической адекватности записи семантических сетей. В ранних разработках авторы при описании семантических сетей часто полагались на интуицию. И с повышением сложности представления, делалось все больше разного рода необоснованных допущений. Вудс указывает на интенсиональную природу большинства объектов, представляемых в сетях. Он призывает принимать во внимание саму семантику представления и отдавать отчет о деталях, которые раньше отбрасывались «под покровительством интуиции».
Отношения в неоднородных семантических сетях
Пусть W = S, - неоднородная семантическая сеть, где множество S есть множество вершин семантической сети, представляющих собой имена предметов и процессов окружающего мира. Элементы множества S будем называть событиями. - семейство отношений на S. Имена S є S могут быть как индивидными, так и общими. Индивидное имя обозначает конкретный объект действительности, общее имя обозначает неопределенный объект или множество объектов. Отношения на этих видах вершин существенно отличаются друг от друга. Свойства отношений на индивидных именах будут подробно рассмотрены в следующей главе. На данном этапе остановимся на классе отношений на вершинах сети, обозначающих общие имена. Выделим для изучения те из них, которые определяются внутренней структурой объектов, принадлежащих этим отношениям. Рассмотрим семантическую сеть с множеством вершин S, элементы которого есть общие имена. Каждому имени соответствует набор признаков того понятия, которое это имя определяет.
Этот набор должен быть достаточным как для отличия его от других имен, так и для соотнесения с действительностью [39]. Любая вершина, в таком случае, будет однозначно определяться набором своих свойств с заданным диапазоном значений для каждого из них. Зададим некоторое (определяемое предметной областью) семейство множеств V={Dh D2, ..., Dn}, где каждое множество Dj называется множеством атрибутов, а всякому объекту ставится в соответствие определенное подмножество А кортежей из декартова произведения Dk=DiixDj2x ... xDik (k n) некоторых множеств из V, называемое его экстенсионалом или объемом. Совокупность индексов множества атрибутов события i= i1,i2,...ik называется его содержанием. Эти индексы не обязательно различны. Будем отождествлять индексы множеств из V с именами соответствующих множеств. Имя события S будем считать функцией как его объема, так и содержания: S=S(i,A). Проекцию рг((А) на множество Д- є V будем называть областью значений і-го признака события S; если область значений состоит из одного элемента, то ее будем называть значением г -го признака события S. Определение 2.2. Если S,A - событие, то всякое 5єА будем называть экземпляром события S,A . Экземпляр 8єА события S,A является множеством { ibd1 ! i2,d2 )..., ihdk }, в котором первый элемент каждой пары есть индекс некоторого множества из V, а второй элемент - значение признака события с этим индексом. Рассмотрим неоднородную семантическую сеть, все вершины которой есть объекты с внутренней структурой, описанные выше. Она имеет следующий вид: Отношения из "R - это отношения, в которые вступают события за счет пересечения своих объемов и содержаний. То есть, две вершины принадлежат некоторому отношению R є , если они имеют общие атрибуты. На совокупности экземпляров событий определим некоторые операции.
Представление в НСС комбинаций бинарных отношений и отношений большей арности
Здесь вершины Si и S2 связанны с общей вершиной So одним и тем же отношением R. Формальная запись такого участка будет представлена в виде конъюнкции: R(Sb S0) & R(S2, So). Тот факт, что отношение R и узел So являются общими для первого и второго конъюнкта никак специально не подчеркивается.
На рисунке 3.2 представлено тернарное отношение Q, которое связывает три вершины графа: Sb S2 и S3.
Такое отношение нельзя реализовать в традиционной семантической сети. Наиболее широко используемый метод в этом случае, разложение тернарного отношения в конъюнкцию двух бинарных. Такое разложение почти всегда является причиной потери части смысла. Иногда вообще нет способа адекватно разложить многоместное отношение в конъюнкцию двуместных.
В [77] описан пример разложения тернарного отношения «Скомбинированы для лечения», которое связывало два лекарства и заболевание, на два бинарных: «скомбинировано с» и «лечит». Ясно, что такое разбиение не полностью соответствует исходному отношению.
В качестве второго примера рассмотрим следующее высказывание: «Прямые а и Ъ пересекаются в точке С» (і). Это высказывание эквивалентно тернарному отношению, связывающему две вершины «Прямая а» и «Прямая Ь» с третьей, представленной концептуальным отношением «Пересекаются в точке С». Такая конструкция не может быть разбита на конъюнкцию двух высказываний «Прямая а пересекается в точке С» и «Прямая Ъ пересекается в точке С», которые сами по себе не имеют смысла. Предикатор «пересекаются» является двух- и более местным. Поэтому «и» в выражении (і) не является булевым.
Построим аппарат, который дает возможность без потери информации преобразовывать многоместные отношения подобного рода в бинарные.
Приведенные выше примеры показывают необходимость введения дополнительной операции на множестве вершин семантической сети, которая позволяла бы «склеивать» несколько вершин в одну [14, 15].
Эта необходимость приводит нас к мереологической парадигме. Одним из основных понятий здесь является понятие слияния двух объектов а и Ь, что означает а и Ь, «взятые вместе» [82]. Это слияние (назовем его а 1=1 Ь), является просто еще одним объектом, связанным с аи Ъ посредством отношения part-whole: «[». Это отношение является частичным порядком. Операции У и [ определяются друг через друга следующим образом:
Введем в рассмотрение домен, который содержит не только обычные элементы, но и их слияния. Причем слияние слияний не повышает уровня включения, а остается снова слиянием элементов.
Пусть S 0 - такой домен, который содержит как единичные так и плюральные объекты, не делая между ними различия, и 1=1 - операция слияния на S, которая называется операцией индивидного суммирования. Далее, пусть [ - отношение part-whole, определенное в (3.1) и А -множество [-минимальных элементов в S, называемых атомами в S. Определим для данного элемента а главный идеал а, как множество элементов «меньше» а:
Алгебраические свойства операций Dom- и Im-слияния
В последнее время при разработке интеллектуальных систем предпочтение отдается динамическому моделированию. Существует ряд предметных областей, структура которых не имеет априорного описания, а законы поведения имеют вид эмпирических правил. Это, а также наличие качественных параметров и экспертных оценок, присутствие неопределенности в информации предполагает использование систем, состоящих из двух компонент - дискретной и континуальной [24, 35]. Обе компоненты таких систем интегрированы в базе знаний, представленной в нашем случае неоднородной функциональной семантической сетью.
Отличительной особенностью рассматриваемой системы является тот факт, что не только континуальная, но и дискретная компонента базы знаний описывают процессы, изменяющиеся во времени. Динамика дискретной части такой системы будет заключаться в изменении топологии сети - слиянии и расщеплении ее узлов и дуг. Операции слияния вершин семантической сети может использоваться как при построении базы знаний, так и в процессе вывода.
В семантической сети задается выделенная переменная t, принимающая значения из некоторого линейно-упорядоченного множества Т, которое будем называть дискретным временем системы
Если узел Sj указывает на событие, имеющее начало и конец во времени, будем называть его процессом. Начало и конец всякого процесса явно указываются в сети с помощью соответствующих маркеров. Достоверное событие, не имеющее маркеров начала и конца (или имеющее только маркер начала), будем называть фактом. Процесс в момент времени, больший маркера начала и меньший маркера конца, также будем называть фактом.
Во время функционирования системы события приобретают разный статус. Может быть фактом не только истинность, но и ложность какого-либо события. Определенный процесс может еще не начаться или уже закончиться. Все эти различия должны быть зафиксированы для получения адекватного результата.
Для этого будем использовать пометку сети, в которой каждому событию приписывается метка, которая определяет его настоящий статус. - Априорно все события в сети имеют метку Is_Unknown. - Факты помечаются меткой Is_Yes. - Отрицание события помечается меткой Is_No. - Поскольку многие отношения из 1R имеют модальность, возможные факты будем помечать отдельной меткой Is_MYes. - Метка возможного отрицания Is_MNo. - Процессы, в момент времени, больший маркера начала и меньший маркера конца, как и факты, помечаются также Is_Yes. - Процессы, маркер конца которых меньше текущего времени tk, и которые имели место, помечаются Is_Yes(n), где п 0 - разность между концом процесса и текущим временем. - Процессы, маркер конца которых меньше текущего времени tk, и о которых известно, что они не происходили, помечаются Is_No(n). - События и процессы, маркер начала которых больше текущего времени tk, будут иметь метку Is_Yes(n), где п 0 - разность между началом процесса и текущим временем. - Аналогично определяются события и процессы, для которых / известно, что они не будут иметь места в будущем: Is_No(n). - Если необходимо, вводятся дополнительно Is_MYes(n) и Is_MNo(n) для положительных и отрицательных п.
