Концептуальный граф

В терминологии теории концептуальных графов выделяют два базовых элемента: концепты (англ. concepts) и отношения (англ. relations). Смысл отношения называется интенцией, а множество всех данных в базе — экстенсией. В то время как экстенсия менее релевантна для задачи поиска данных (поскольку для этого существуют эффективные языки — SQL, QBE), концептуальный граф фокусируется на связях между информацией, то есть на отношениях и их интенциях. Эти отношения используются как при формулировании запросов, так и при добавлении новых данных с целью сохранения логической целостности информации.

К базовому формализму КГ предъявляются следующие требования^[1]:

1. Интуитивность (familiar conventions) — обычный пользователь может формулировать запросы не вникая в технические детали СУБД.
2. Автоматический вывод — система способна делать выводы, которые явно не закодированы в ней.
3. Естественность — формализм записи должен напоминать семантику естественного языка.
4. Семантическая целостность — ограничения доменных значений используются для поддержания соответствия базы данных реальности.

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

Основным элементом КГ является концепт, который изображается в виде прямоугольника с названием типа концепта (sort label). Концепт — это абстрактный объект, олицетворяющий некоторую сущность (например: ЧИСЛО, ЧЕЛОВЕК или СЧЁТ). Аналогично типу данных в языках программирования, концепты представляют собой различные сущности. Следующим элементом являются концептуальные отношения или реляции, которые изображаются кружками. Каждому такому отношению соответствует хотя бы одно ребро (связь) с каким-либо концептом. Пример простого концептуального графа приведён на рисунке:

Пример простого концептуального графа.

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

В реальных ситуациях можно встретить концепты разной степени общности, причём элементы одних могут быть подмножествами других. Например, ЖИВОТНОЕ — подтип ОРГАНИЗМ. Такая связь называется отношением подтипа и выражает соотношение конкретизации между типами концептов. Конструкт концепта остаётся неизменным: независимо от того, представлены ли одинаковые данные, каждый тип — уникален. На множестве всех типов концептов вводится частичный порядок с использованием оператора ≤ аналогично частично упорядоченным множествам.

Два концепта могут иметь один или несколько общих подтипов (англ. common subsort). Например, для ЦЕЛОЕ-ЧИСЛО и ПОЛОЖИТЕЛЬНОЕ-ЧИСЛО общим подтипом будет ЦЕЛОЕ-ПОЛОЖИТЕЛЬНОЕ-ЧИСЛО. Таким образом, хотя оба исходных типа самостоятельны, их пересечение даёт более узкий концепт. Формально: общий подтип c для концептов a и b определяется как таковой, что тип(c) ≤ тип(a) и одновременно тип(c) ≤ тип(b), где функция тип возвращает sort label концепта.

Концепты и отношения моделируют базовую семантику предметной области. Существует набор правил построения концептуальных графов, выполнение которых гарантирует валидность (well-formed) графа:

1. Копирование — идентичная копия валидного КГ также валидна.
2. Отделение — любые связные графы, возникающие при удалении отношения из графа, остаются валидными (граф может распасться на части, но это не нарушает валидности).
3. Ограничение (рестрикция) — замена типа концепта на его подтип не нарушает валидности графа.
4. Объединение — если в двух КГ встречается один и тот же тип концепта, их можно объединить, переместив рёбра на общую вершину.

Правило рестрикции, применённое к концепту ЧЕЛОВЕК.

Данная иллюстрация показывает принцип рестрикции: из КГ, выражающего «человек идёт», получаем «мальчик идёт», заменяя концепт ЧЕЛОВЕК на подтип МАЛЬЧИК. Поскольку МАЛЬЧИК ≤ ЧЕЛОВЕК, граф остаётся валидным.

Правило объединения для двух концептуальных графов. Объединение происходит по концепту ХОДЬБА.

Иллюстрация демонстрирует объединение двух КГ, соответствующих фактам «мальчик идёт утром» и «мальчик идёт в школу», в общий граф с концептом ХОДЬБА; результат — «мальчик идёт утром в школу».

Правило отделения, применённое к отношению ВРЕМЯ.

На рисунке принцип отделения: из графа «мальчик идёт утром в школу» удалено отношение ВРЕМЯ, в результате чего УТРО становится независимым концептом.

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

Проекция двух КГ: результат внизу.

На иллюстрации проектируются графы «человек идёт» и «мальчик идёт утром в школу»; их общий подграф выражает «мальчик идёт».

В КГ, помимо общих концептов, используются и концепты с конкретным значением или квантификатором: они записываются как ТИП-КОНЦЕПТА: РЕФЕРЕНТ. Например, МАЛЬЧИК: * — произвольный мальчик; МАЛЬЧИК: Павел — конкретное лицо (в данном случае «Павел» называется дизъюнктор). Возможно также выделять множество значений: МАЛЬЧИК: {Пётр, Павел}. Для выражения обобщения используют квантификаторы: МАЛЬЧИК: ∀ — «все мальчики», МАЛЬЧИК: ∃ — «существует хотя бы один мальчик». Концепт с квантификатором называют квантифицированным. С точки зрения программирования концепты подобны типам данных, а граница «родовой/конкретный» задаёт допустимые значения, с учётом иерархии надтип-подтип. Кроме того, возможна реализация значения через дескриптор — вложенный КГ, поясняющий конкретный концепт (см. раздел о вложенных графах).

С помощью лямбда-выражений можно описывать более сложные отношения произвольной арности. Подобное выражение является макросом (шаблоном), который становится конкретным фактом после подстановки переменных.

Пример лямбда-выражения для унарного отношения.

Такая запись читается как «мальчик λ₁ идёт»; смысл возникает после подстановки значения, например λ₁=Павел — «мальчик Павел идёт». Если заменить ХОДЬБА: * на ХОДЬБА: λ₂, получится бинарная реляция для фактов вида: «мальчик Павел идёт медленно», где λ₁=Павел, λ₂=медленно.

Концептуальные графы могут быть относительно легко преобразованы в предикатную логику. Например, концепт МАЛЬЧИК: Павел можно записать как:

∃x Мальчик(x) ∧ Имя(x, Павел)

Каждое отношение становится n-арным предикатом.

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

∀x ∀y ∃z (z=разность(x,y))

Это описание утверждает, что для любых x и y существует z, являющееся их разностью. В форме КГ факт изображается следующим образом:

Пример функциональных зависимостей в КГ.

Особое внимание обращается на пунктирные линии между универсальными и существующими квантификаторами — они выражают зависимости: так называемые функциональные зависимости. Такая зависимость состоит из набора функциональных рёбер (англ. function links), соединяющих исходные концепты с целевыми. Каждая функциональная зависимость связана с процедурой доступа (англ. access procedure): если заданы значения исходных концептов, процедура позволяет вычислить значения целевых.

Функциональные зависимости и процедурность доступа — ключевой переход от КГ к поиску реальных данных в СУБД. Например, SQL-запрос:

select имя, фамилия, зарплата, начальник from сотрудники where отдел = 'кадровый'.

В КГ ОТДЕЛ — исходный концепт, а ИМЯ, ФАМИЛИЯ, ЗАРПЛАТА, НАЧАЛЬНИК — целевые концепты функциональной зависимости. Процедура доступа задаёт точный алгоритм поиска данных.

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

Пример вложенного КГ, задающего контекст. Источник: P. Кржемен, https://cw.fel.cvut.cz/wiki/_media/courses/a7b33sui/01-cg.pdf

Концептуальная схема — это КГ, содержащий определённые сочетания квантификаторов и функциональных зависимостей. Последние формируют структуру, позволяющую напрямую отображать схему на СУБД. При обработке пользовательского запроса система стремится перевести его (обычно с естественного языка) именно в концептуальную схему.

С точки зрения формализации используются два селектора: value и quant (значение и количество), которые могут применяться к любому концепту. Их свойства для некоторого концепта c:

1. Если value(c) и quant(c) не определены, c — родовой концепт.
2. Если только value(c) определено, а quant(c) — нет, c — константный концепт.
3. Если определено только quant(c), концепт — квантифицированный.
4. Одновременное определение value и quant невозможно.
5. Значение quant — одно из {∀, ∃, E, E-set}. Е означает ровно одно значение (иногда обозначается ∃!), E-set — множество конкретных значений, возможно пустое.
6. Функция permissible (разрешённое множество) определяет допустимые значения концепта (формально: для любого константного концепта value(c) ∈ permissible(тип(c))).
7. permissible согласуется с иерархией надтип-подтип: если один концепт подтип другого, его разрешённые значения — подмножество значений надтипа.

(Sowa, «Conceptual Graphs for a Data Base Interface», 1976)

Концептуальная схема

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

• Если концепт c — источник и не является целевым, quant(c) = ∀.
• Если одновременно источник и цель — quant(c) = E.
• Если только цель — quant(c) ∈ {E, E-set}.
• Если ни то ни другое — это родовой концепт.

(Sowa, 1976)

В случае базы с несколькими связанными таблицами, связи реализуются через внешние ключи. Таблица без ссылок на другие — обобщённый (квантифицированный) концепт. Концептуальные отношения отражают смыслы связей в данных; функциональные зависимости — физическую реализацию этих связей в СУБД через ключи.

Стандартный КГ допускает использование столь мощных выразительных средств, что возможна даже нераспознаваемость схемы (существует неразрешимость). Причина — чрезмерная выразительность множественных дескрипторов и множество элементов в качестве значений. Эту проблему Джон Соува решал, предложив simple conceptual graphs — ограниченный вариант без сложных дескрипторов и множественных константных значений^[2]. Эту концепцию затем развивали Мишель Шейн и Мари-Лор Мюнье.

Исследования в области КГ ведутся с момента их появления. Развивается как сам формализм, так и его отдельные компоненты и смежные задачи.

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

• Core CGs — безтиповая логика, охватывающая стандарт Common Logic, стандартизованный в ISO/IEC 24707.
• Extended CGs — дополнения (универсальный квантификатор, типовые метки, булевы контексты); мощность выражения не увеличивается, алгоритм взаимного преобразования Core/Extended CGs существует.
• CGs with contexts — поддержка метаязыков: контексты позволяют выводить утверждения об объектах из утверждений о метаобъектах.
• Research CGs — экспериментальные и разрабатываемые варианты КГ; успешные находки могут позже войти в стандарт.

Одним из направлений развития стало создание графических интерфейсов для визуального построения высказываний предикатной логики. Здесь формула в логике первого порядка представляется именованным графом с линейной записью. Формат обмена КГ — Conceptual Graph Interchange Format (CGIF) — стандартизован в ISO/IEC 24707:2007 как один из трёх диалектов Common Logic, объединяющих формализмы на базе логики.

На приведённой схеме прямоугольники — концептуальные узлы, овалы — узлы отношений. В CGIF такой граф запишется так:

[Cat Elsie] [Sitting *x] [Mat *y] (agent ?x Elsie) (location ?x ?y)

В квадратных скобках записываются данные концептов, в круглых — отношения; x и y — кореференционные метки, показывающие связи между узлами.

В формате Common Logic Interchange Format (CLIF) переменные x и y ассоциируются с переменными:

(exists ((x Sitting) (y Mat)) (and (Cat Elsie) (agent x Elsie) (location x y)))

Звёздочки в CGIF указывают на существование переменной (аналогичны существующим квантификаторам в CLIF); знаки вопроса — на связанные переменные. Указание универсального квантификатора записывается как @every*z (CGIF) или forall (z) (CLIF).

Правильность синтаксиса можно проверить, переписав граф в логическую запись и обработав её автоматически.

Другая ветвь развития опирается на экзистенциальные графы Чарльза Сандерса Пирса, которые были основой и для КГ Соува. Здесь КГ интерпретируются скорее как диаграммы, нежели как графы в строгом смысле. Проведение верификационных операций происходит именно в этих диаграммах.

Третье направление развития КГ связано с представлением знаний с помощью графов и логическими средствами проверки (GBKR). Это направление разработали Мишель Шейн и Мари-Лор Мюнье. Основные черты:

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

• CharGer — графический редактор КГ
• Prolog+CG — инференционный движок на языке Prolog
• Amine Platform — комплексная Java-платформа для создания интеллектуальных и мультиагентных систем, включающая Prolog+CG
• CoGui — Java-редактор для построения КГ
• WebKB — средство для представления знаний и извлечения информации
• Cogitant — C++-библиотеки для работы с КГ