Прикладная онтология на языке гиперграфов

Размещено на http://www.allbest.ru/

Прикладная онтология на языке гиперграфов

Г.К. Хахалин

Введение

В последнее время в искусственном интеллекте наметилась тенденция интегрирования различных подсистем в единую систему. Для этого придуман термин Artificial General Intelligence, что можно было бы перевести как Интегральный Искусственный Интеллект (ИИИ). В 2008 году была проведена в Мемфисе (США) первая международная конференция по этой тематике [1], в 2009 - намечена вторая.

В рамках аналогичного проекта предполагается интеграция в ИИИ разномодальных систем сенсорного, моторного и ментального характера [2]. На первом этапе - подсистем анализа и синтеза изображений, анализа и синтеза естественного языка и подсистемы решения задач с дальнейшим расширением функций анализа и синтеза речи, ответов на вопросы, объяснений собственного поведения, обучения и самообучения и т.д.

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

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

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

1. Язык представления знаний - семантический гиперграф

Для разных предметных областей и для разных задач существует спектр языков (моделей) представления знаний. Обзоры некоторых из них даны в [3]. На наш взгляд для системы ИИИ, охарактеризованной выше, наиболее адекватным языком представления знаний является язык гиперграфов в качестве расширения семантических сетей.

В общем случае гиперграф можно задать различными способами. Определим гиперграф согласно [4, 5]. Гиперграф H (V, E) есть пара, где V - множество вершин V = {v_i}, i I= {1, 2,…, n}, а E - множество ребер E = {e_j}, j J= {1, 2,..., m}; каждое ребро представляет собой подмножество V. Вершина v и ребро e называются инцидентными, если v e. Для v V через d(v) обозначается число ребер, инцидентных вершине v; d(v) называется степенью вершины v. Степень ребра e - число вершин инцидентных этому ребру, - обозначается через r(e). Гиперграф Н является r-однородным, если все его ребра имеют одинаковую степень r. Если каждое его ребро имеет степень равную 2, то гиперграф является графом.

Гиперграф (V', E`) называется подгиперграфом (V, E), если V' V, E` E и вершина v V' и ребро e E` инцидентны в (V', E`) тогда, и только тогда, когда они инцидентны в (V, E).

Гиперграфы бывают ориентированные и неориентированные. Рёбра неориентированного гиперграфа называются звеньями. В случае ориентированного гиперграфа (оргиперграфа) ребро e E называется гипердугой (для краткости дугой) и представляется как упорядоченная пара (h, T), где h V, T V\{h}, T . При этом вершина h называется началом дуги e, а каждая вершина из T -- конечной вершиной дуги e. Будем говорить, что дуга e исходит из вершины h и заходит в каждую из вершин множества T.

Введем понятие частично ориентированного гиперграфа. Гиперграф H = (V, E₁, E₂) называется частично ориентированным или квази ориентированным гиперграфом, если E₁ E & E₁ - множество ребер (звеньев), а E₂ E & E₂ - множество дуг и E₁ E₂ = E. Если E₁ = E & E₂ = , то гиперграф является неориентированным, а если E₂ = E & E₁ = , то гиперграф является (полностью) ориентированным. В зависимости от мощности множеств E₁ и E₂ вводятся соответствующие понятия. Если |E₁| = |E₂|, то гиперграф будет ориентированно-неориентированным. Если |E₁| |E₂|, то гиперграф будет почти неориентированным. Если |E₁| |E₂|, то гиперграф будет почти ориентированным.

Если элементам гиперграфа приписаны символы (или цепочки символов) из некоторого множества, то он является раскрашенным гиперграфом или гиперграфом с помеченными вершинами и ребрами. Цепочки символов - это имена понятий и отношений онтологии, представленной раскрашенным, частично ориентированным гиперграфом. Такой гиперграф будем называть семантическим гиперграфом.

2. Структура прикладной онтологии

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

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

О (X, R, I)

где

X - множество понятий проблемной среды (вершины гиперграфа), R - множество отношений между понятиями (дуги и ребра гиперграфа), а I - множество имен понятий и отношений в данной предметной области.

2.1 Определение понятий

Множество понятий проблемной среды разделяется на несколько подмножеств:

X = {X₁,.., X_k}

где

X₁ - это класс всех подклассов проблемной среды (в онтологии «Планиметрия» это класс Плоская Фигура). X₂ - это подклассы «структурных» понятий проблемной среды (Треугольник, Параллелограмм, Трапеция, Эллипс, Кольцо и др.), X₃ - классы «составляющих» структурные понятия (Сторона, Основание, Катет и др.), X₄ - свойства понятий (Периметр, Площадь, Длина и т.д.), X₅ - значение свойств (значение угла б_i, значение длины стороны l_j и др.). На семантическом гиперграфе (также как и на семантической сети) можно представлять и результаты арифметических, логических и других операций, поэтому в онтологии можно вводить соответствующие вершины (например, Разность, Сумма, а также формулы подсчета периметра, площади и т.п.). Конечно, интерпретация подобных вершин вместе с соответствующими отношениями будет отличаться от интерпретации других вершин. Следует отметить, что множество понятий X является открытым - его можно расширять по мере необходимости.

Класс Плоская Фигура, охватывающий все планиметрические фигуры, имеет подклассы, которые представляют более конкретные понятия, чем надкласс. Каждый подкласс может иметь свои подклассы. Например, класс Треугольник разделяется на подклассы Прямоугольный и Равнобедренный Треугольник. А Равносторонний Треугольник является подклассом класса Равнобедренный Треугольник.

Отношения между классами, подклассами и надклассами понятий организуются в виде таксономии или таксономической иерархии. Для представления таксономии используется отношение является_видом (AKindOf). Таксономический фрагмент онтологии, представляющий собой 2-однородный ориентированный гиперграф, представлен на рис. 1..

Размещено на http://www.allbest.ru/

Рис. 1. Таксономический фрагмент онтологии «Плоская геометрическая фигура»

2.2 Определение отношений

При разработке и при использовании любой онтологии необходимо определиться с перечнем используемых отношений. На сегодняшний день нет общепринятого полного перечня отношений за исключением десятка общезначимых отношений (например, A_Kind_Of, part_of, have_value, have_structure и др.). Тем не менее, всю совокупность отношений в онтологии стоит разделить на несколько подмножеств.

R = {R₁,…, R_m}

где

R₁ - общезначимые отношения (см. выше), R₂ - арифметические, R₃ - логические (И, ИЛИ, НЕ и др.) и т.д. и R_k - предметные для данного приложения отношения. Общезначимые отношения носят в основном декларативный характер: они служат для нахождения путей поиска требуемых знаний. Арифметические, логические, функциональные и предметные отношения задаются как декларативно, так и операционально. Последнее означает, что с именем данного отношения связана соответствующая процедура, с помощью которой осуществляется интерпретация высказывания в реальной или «виртуальной» среде. Например, отношение соприкасается_в_концевой_точке предполагает, что существует процедура, с помощью которой на входном изображении осуществляется поиск двух отрезков прямых, соприкасающихся друг с другом концевыми точками. К предметным отношениям онтологии «Планиметрия» также относятся отношения: образует, параллельно, перпендикулярно, вычисляется_по_формуле, совпадает, делит_пополам, исходит_из, является_внутренней_точкой и т.д.

Отметим, что множество R является открытым - в него можно добавлять необходимые подмножества.

2.3 Определение имен понятий и отношений

Имена понятий и отношений онтологии выбираются на основе терминологии, соответствующей естественно-языковым реалиям в данной области, чтобы упростить процесс разработки онтологии для эксперта и инженера по знаниям. Но и здесь процесс кодификации далек от завершения, поэтому каждый разработчик предметной онтологии по возможности использует общепринятую терминологию (в основном для имен понятий) и собственные предпочтения - для имен отношений. В планиметрии существует устоявшаяся терминология для обозначения понятий (еще со времен Древней Греции). И понятия обозначаются цепочками символов очень похожими на слова естественного языка, например, либо английского, либо русского. С наименованием отношений - вопрос сложнее, поэтому и разнобоя больше. Вообще процесс наименования определяется не только предметной областью и простотой разработки, но и вопросами хранения информации в памяти системы для различения однотипных понятий. Но этот вопрос при общем описании онтологии выходит за рамки данной работы. Для иллюстрации на рис. 1 понятия и отношения представлены «словами» английского языка, а на рис. 2 - «словами» русского языка.

2.4 Структуры понятий и ситуаций

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

Составные понятия, в которых используется отношение является_частью (Part_Of). Для таких понятий бывает достаточным просто перечисление частей, например, оглавление для трудов конференции или фрагмент онтологии для понятия Отрезок_Прямой во взаимоотношении с понятием Полупрямая, Прямая и видовыми концептами: Катет, Гипотенуза, Диагональ и др. семантический онтология гиперграф

Там, где важны еще и отношения между частями, служат структурные понятия. Для выделения структуры используется отношение имеет_структуру (Have_Str). Понятие Треугольник в виде семантического гиперграфа представлено на рис. 2. Здесь структура выделяется гипердугой (выделена пунктиром), где началом дуги является вершина, помеченная словом Треугольник, а конечными вершинами будут все вершины, охваченные пунктирной областью. Отметим, что некоторые целостные свойства понятия могут быть представлены как внутри структуры этого понятия, так и в виде интегрального его свойства. В данном примере внутренним свойством является зависимость сторон треугольника. Внутри пунктирной области выделяется неориентированный гиперграф с ребром, помеченным цепочкой символов F3 (формулой, определяющей взаимоотношения сторон треугольника). В целом гиперграф, изображенный на рис. 2, будет почти ориентированным, т.к. мощность ребер меньше мощности дуг, т.е. |E₁| |E₂|.

Размещено на http://www.allbest.ru/

Рис. 2. Фрагмент структуры понятия Треугольник

Полная структурная часть понятия может оказаться не столь наглядной, как хотелось бы. Для этого предусматривается возможность при разработке и отладке онтологии представлять эти структуры в виде нескольких стратов - структур, в которых присутствуют базовые элементы, а в остальных частях определены разные компоненты. На рис.2 для наглядности понятие Треугольник определено в виде структуры трех отрезков прямых, соединенных концевыми точками. Хотя полная структура понятия Треугольник дополнительно включает биссектрисы, медианы, высоты и углы треугольника.

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

2.5 Определение свойств и значений свойств

Большинство понятий онтологии обладает соответствующими свойствами: для понятия Треугольник это может быть Площадь, Периметр, для понятия Отрезок_Прямой - Длина и т.д. Каждое свойство может быть задано конкретным значением или способом (например, формулой, реализуемой с помощью присоединенной процедуры) вычисления значения данного свойства. На рис. 3 интегральными свойствами понятия Ромб являются Площадь и Периметр. Значения этих свойств для экземпляра понятия подсчитываются по формулам F14 и F12, которые вычисляются процедурами при означенном (конкретном, числовом) значении внутреннего свойства понятия Ромб: длины стороны. В представлении на языке семантического гиперграфа длина стороны связывается с понятиями Сторона (Side) отношением: имеет_длину (have_length).

Рис. 3. Фрагмент структуры понятия Ромб

Из описаний структур понятий и ситуаций (см. рис. 2, 3, 4) можно заметить, что для каждой из подсистем интегральной системы информация об объектах избыточна. Например, для «отделения» (распознавания) треугольника от четырехугольника достаточно для распознаваемого объекта извлечь данные о количестве отрезков. При анализе некоторого естественно-языкового текста нет необходимости иметь в структуре Треугольника описания медиан, биссектрис и других составляющих. Но если иметь в виду в совокупности все функции интегральной системы (не только распознавание, а и анализ, и синтез изображений, не только анализ естественно-языкового текста, но и его синтез, а также поиск решения задачи, ответы на вопросы и т.д.), то эта избыточность уже не кажется излишней.

3. Процедуры на прикладной онтологии

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

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

Важной особенностью представления знаний в онтологии - возможность для понятий задавать по умолчанию значения свойств. Это позволяет естественным образом вводить исключения. Значение по умолчанию перекрывается более конкретным значением. Например, площадь любого треугольника подсчитывается по формуле 1/2 ас h_ac (значение по умолчанию), а для прямоугольного треугольника площадь можно подсчитать по более простой формуле 1/2 ac bc (более конкретное значение).

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

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

При оперировании с конкретными экземплярами понятий реализуется процедура означивания. По входной информации все или некоторые переменные в описании понятия (включая и структуру) принимают конкретные значения. Некоторые переменные могут маркироваться знаком (например, знаком «?») - для них необходимо найти значение по условиям задачи. Например, если во входных данных относительно понятия Равнобочная Трапеция указаны длина одного из оснований и боковой стороны, то процедура означивания предполагает задание в обобщенной структуре этого понятия вместо переменных (длины основания и боковой стороны) их конкретных значений.

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

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

В описании понятия Треугольник никакой информации о «разности двух углов» и о «равенстве этой разности третьему углу» быть не может. А ситуация, описывающая данный текст должна ее включать. В этом случае подключаются процедуры дополнения, которые на основе присутствия знания в онтологии о понятии Разность (x, y) и о связи равно модифицируют описание ситуации введением соответствующих узлов и дуг, как это представлено на рис. 4. Данный рисунок иллюстрирует процедуры дополнения для понятий Треугольник и Квадрат и процедуры частичного означивания. Выделенные узлы и жирные связи отображают те объекты, которые представлены в тексте задачи. Знак вопроса при значениях понятий Угол определяет то, что эти значения необходимо найти в процессе решения геометрической задачи.

Рис. 4. Частично означенная структура ситуации «Треугольник и Квадрат» для геометрической задачи

При любом языке представления знаний необходимой процедурой является сопоставление описаний. Это либо сравнение по образцу (pattern matching), либо поиск изоморфизма гиперграфов. Последняя процедура, описанная в [8], предполагает сопоставление семантического представления геометрической фигуры или текста геометрической задачи со структурными фрагментами предметной онтологии. Результат подобного сопоставления представлен на рис. 4., где выделенные узлы сопоставлены с фрагментами семантического описания текста задачи: это понятия Треугольник (Triangle) и его Площадь (Area), углы треугольника, их значения и одна из сторон этого треугольника; понятия Квадрат (Square), его Площадь и Сторона (Side).

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

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

Line_Segment обратное отношение от a_kind_of одно из множества {Side, Median, Diagonal} enter_structure одно из множества {Triangle, Square}.

А при анализе фрагмента текста «сторона треугольника» путь поиска будет:

Side enter_structure Triangle.

Такое различие определяется тем, что зрительная система оперирует своими понятиями (отрезками, дугами, точками и т.п.), а естественно-языковая - своими (сторонами, катетами, диагоналями и т.д.). И эти множества не обязательно всегда и полностью совпадают.

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

Рис. 5. Изображение фигуры, иллюстрирующей текст геометрической задачи

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

Заключение

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

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

Литература

1. The First Conference on Artificial General Intelligence / P. Wang et al. (Eds.), AGI-08, 1-3 March, 2008, Memphis, USA. IOS Press, 2008.

2. Хахалин Г.К., Воскресенский А.Л. Мультизадачное использование прикладной онтологии // Труды XI национальной конференции по Искусственному Интеллекту с международным участием - КИИ-2008. М.: URSS, 2008, т.1, с. 112-123.

3. Башмаков И.А., Башмаков И.А. Интеллектуальные информационные технологии. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2006, 302 с.

4. ЗыковА.А. Гиперграфы // Успехи математических наук.1974. Т. 29, вып. 6. С. 89-154.

5. Визинг В.Г. О раскраске инциденторов в гиперграфе. Дискретный анализ и исследование операций, июль--сентябрь 2007, Серия 1, Том 14, № 3, 40-45.

6. Гладун А.Я., Рогушина Ю.В.. Онтологии в корпоративных системах. // Корпоративные системы, №1, 2006.

7. Боровикова О.И., Загорулько Ю.А. Подход к представлению знаний в многоязычных информационных системах // Труды XI национальной конференции по Искусственному Интеллекту с международным участием - КИИ-2008. М.: URSS, 2008, т. 3, с. 155-163.

8. Хахалин Г.К. Использование гиперграфов в лингвистической трансляции // Труды Международного семинара "Диалог'99" по компьютерной лингвистике и ее приложениям. - М., 1999, с. 315-320.

Размещено на Allbest.ru