О некоторых свойствах логико-вычислительной семантической сети

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

О некоторых свойствах логико-вычислительной семантической сети

А.Л. Яловец

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

Введение

При разработке моделей представления знаний (МПЗ), базирующихся на модели семантической сети Куиллиана (далее - модели Куиллиана), обычно решаются вопросы развития логических и/или вычислительных свойств модели Куиллиана. Основной целью данной статьи является краткая характеристика некоторых свойств логико-вычислительной семантической сети [Яловец, 2006], которую можно рассматривать как развитие модели Куиллиана в логическом и вычислительном аспекте. Для обсуждения таких свойств выполняется сравнительный анализ данной МПЗ с тремя известными МПЗ, каждую из которых можно рассматривать в качестве модели, являющейся развитием модели Куиллиана в логическом или вычислительном аспекте. В качестве таких МПЗ рассматриваются: пропозициональная семантическая сеть [Shapiro, 1991], блочная семантическая сеть [Hendrix, 1979] и процедурная семантическая сеть [Levesque et al., 1979]. Для сравнения свойств названных МПЗ приводятся конкретные примеры представления знаний.

1. Краткий обзор некоторых разновидностей модели семантической сети

1.1 Пропозициональная (propositional) семантическая сеть

(далее - ПССШ) предложена С.К.Шапиро (S.C.Shapiro) в рамках разработки системы представления знаний и рассуждений SNePS (Semantic Network Processing System). ПССШ [Shapiro, 1991] представляет собой помеченный связный направленный ациклический граф, в котором вершины представляют объекты, а помеченные дуги - бинарные отношения между объектами. Каждая вершина ПССШ реализует интенсиональное представление, что в данном случае означает, что вершина обозначает ментальный объект. Дуги ПССШ представляют не концептуальные, а структурные отношения между вершинами (связывающие утверждения о фактах с объектами, в них входящими). Концептуальные отношения представляются при помощи вершин. Различают пропозициональные вершины, вершины действия и индивидуальные вершины. В свою очередь, пропозициональные вершины подразделяются на простые и общие пропозициональные вершины, а также правила. Для пропозициональных вершин вводится нотация доверия путем добавления символа '!' в конец идентификаторов вершин и такие вершины рассматриваются как утверждаемые. Вывод на ПССШ заключается в вычислении вновь утверждаемых вершин из ранее утвержденных вершин. В SNePS поддерживается четыре метода вывода, соответственно основанные на связности, пути, вершинах и включении.

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

1.2 Блочная (partitioned) семантическая сеть

(далее - БСС) предложена Г.Г.Хендриксом (G.G.Hendrix). БСС [Hendrix, 1979] представляет собой помеченный связный направленный ациклический граф, в котором выделяются три типа структурных единиц: блоки, вершины и помеченные дуги. Вершины БСС представляют объекты, а помеченные дуги - бинарные отношения между объектами. Каждый блок имеет вершину входа и содержит одну или несколько вершин, связанных между собой помеченными дугами. Каждая вершина и дуга БСС принадлежит одному или нескольким блокам. Комбинацию нескольких блоков называют «видом». Разбиение БСС на блоки позволяет создавать иерархию видов, причем вид наследует информацию родительского вида. В БСС могут быть представлены блоки логических операций отрицания, дизъюнкции и импликации. Логическая операция конъюнкции реализуется при помощи механизма наследования. Одной из важных особенностей БСС является ее способность представления произвольно сгруппированных кванторов всеобщности и существования.

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

1.3 Процедурная (procedural) семантическая сеть

(далее - ПССЛ) предложена Г.Левеском и Дж.Милопулосом (H.Levesque, J.Mylopoulos). Под ПССЛ [Levesque et al., 1979] понимается ориентированный мультиграф, в качестве вершин которого выступают разнообразные классы, а в качестве дуг - отношения между ними. В основе концепции ПССЛ лежит так называемая процедурная семантика, для реализации которой используются такие термины как объект, класс, отношение и программа. В основе организации ПССЛ лежат два механизма абстракции: обобщение/специализация и агрегирование/декомпозиция. Первый механизм абстракции заключается в организации сети, предполагающей разбиение классов на подклассы с созданием таксономии классов, известной как is-a-иерархия. Второй механизм абстракции заключается в объединении в одну функциональную единицу (структуру) группы взаимосвязанных объектов, выступающих в качестве частей структуры, что приводит к организации сети в виде part-of-иерархии. Благодаря is-a- и part-of-иерархиям в ПССЛ обеспечивается реализация наследования свойств.

Применение ПССЛ для представления знаний имеет ряд преимуществ, связанных с интеграцией программ вдоль is-a- и part-of-иерархий. Вместе с тем, ПССЛ имеет свои недостатки, связанные с громоздкой структурой ПССЛ; сложностью добавления объектов и отношений в эту структуру; невозможностью представления логических операций; невозможностью выявления противоречий; трудностью различения экстенсионального и интенсионального представлений.

1.4 Логико-вычислительная семантическая сеть

(далее - ЛВС-сеть) предложена автором настоящей статьи. ЛВС-сеть [Яловец, 2006] представляет собой простой ациклический конечный однонаправленный связный граф, в котором каждой вершине ставится в соответствие четыре атрибута: идентификатор вершины, имя вершины (объекта), имя метода и тип вершины, а дуги отображают бинарные отношения, существующие между объектами. Если имя вершины, имя метода и тип вершины могут быть не уникальными в ЛВС-сети, то идентификатор каждой вершины ЛВС-сети является уникальным и формируется в результате конкатенации указателя типа вершины, имени вершины и имени метода [Яловец, 2006]. Дуги ЛВС-сети являются непомеченными и отображают семантические, логические и вычислительные отношения (связи), существующие между объектами. Логика, положенная в основу ЛВС-сети, построена на трех основных операциях: конъюнкции, полной дизъюнкции и отрицания. Отметим, что логическая операция полной дизъюнкции введена А.А.Зиновьевым в [Зиновьев, 2000]. Свойства данной операции подобны свойствам операции строгой дизъюнкции с тем отличием, что операция полной дизъюнкции является n-арной (где n ? 2). В ЛВС-сети логическая операция отрицания вводится как часть имени (частица либо приставка «не»), а логические операции конъюнкции и полной дизъюнкции вводятся через тип вершины (различаются И-вершины и ИЛИ-вершины). В ЛВС-сети обеспечивается представление как интенсионала (при помощи И-вершин), так и экстенсионала имен (при помощи ИЛИ-вершин). ЛВС-сеть позволяет представлять кванторы существования и всеобщности [Яловец, 2006]. Для ЛВС-сети разработаны метод прямого логического вывода [Яловец, 2000] и методы выявления и разрешения противоречий [Яловец, 2002]. Разработанные методы и модели реализованы в инструментальной среде представления и обработки знаний [Кондращенко и др., 2002].

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

1.5 Результаты сравнительного анализа МПЗ. В таблице 1 приведены результаты сравнительного анализа рассмотренных МПЗ.

Табл. 1

В таблице 1 символ “+” означает наличие свойства у МПЗ; символ - частичное наличие свойства; символ “-” - отсутствие свойства.

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

2. Сравнение свойств ЛВС-сети со свойствами других рассмотренных разновидностей модели семантической сети

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

Пример №1. В качестве примера представления знаний при помощи пропозициональной семантической сети (ПССШ), рассмотрим предложение «каждая женщина по возрасту либо младше 30 лет, либо старше 30 лет» (см. рис.1 (данный пример и рис.1 взяты нами из [Shapiro, 1991])).

Вершины, входящие в структуру ПССШ на рис.1, означают следующее [Shapiro, 1991]: V1 - произвольная женщина, v₁; P1 - высказывание, что v₁ является женщиной; P2 - возраст v₁; P3 - высказывание, что v₁ является младше 30 лет; P4 - высказывание, что v₁ является старше 30 лет; P5 - высказывание, что v₁ является либо младше 30 лет, либо старше 30 лет; M1! - правило, что каждая женщина либо младше 30 лет, либо старше 30 лет. Как следует из рис.1, для представления знаний при помощи ПССШ потребовалось 14 вершин.

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

Для представления знаний о рассматриваемом предложении при помощи ЛВС-сети (см. рис.2) потребовалось только 5 вершин. В качестве терминальных вершин ЛВС-сети выступают вершины Женщина и Возраст, связанные заходящими дугами с вершиной AND_COND Сравнение возраста;Ф Хбольше30. Данная вершина имеет указатель типа AND_COND (что означает, что эта вершина является условной И-вершиной); имя 'Сравнение возраста' и ей сопоставлено имя метода 'Ф Хбольше30', представляющего собой формулу X>30. В качестве фактического параметра данной формулы выступает вершина Возраст. В зависимости от значения имени вершины Возраст, формула X>30 может принять одно из двух булевых значений: 0 или 1 (0 - если неравенство не выполняется; 1 - в противном случае). В процессе логического вывода [Яловец, 2000] условные И-вершины обрабатываются таким образом, что вершина, выводимая из условной И-вершины, определяется в зависимости от результата выполнения формулы, сопоставленной условной И-вершине. Так, если в результате выполнения формулы получено значение 0, то выводимой вершиной будет вершина, идентификатор которой содержит постфикс _0; в противном случае - вершина, идентификатор которой содержит постфикс _1. Например, если в качестве значения имени вершины Возраст задано число 35, то результатом выполнения формулы X>30 будет 1, и выводимой вершиной будет вершина AND_Старше 30 лет_1 (т.е. будет выведена вершина с именем 'Старше 30 лет'). семантическая сеть вычислительный блочный

Таким образом, исходя из рассмотренного примера, можно говорить о большей выразительной мощности ЛВС-сети по сравнению с ПССШ.

Пример №2. В качестве примера представления знаний, выполненного при помощи процедурной семантической сети (ПССЛ), рассмотрим представление факториала (см. рис.3 [Вагин, 1988]).

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

На рис.3 показана функция FACTORIAL, в тело которой входят функции lessp (меньше, чем p), times (умножение) и sub1 (вычитание единицы). Процесс вычисления факториала произвольного числа n выполняется рекурсивно. Выход из процесса рекурсии происходит при условии (if), что успешно завершена операция проверки (test), что текущее значение n меньше (lessp), чем 2. Если данное условие не удовлетворяется, то выполняется функция times, содержащая два операнда (левый (left) и правый (right)), где в качестве левого операнда выступает текущее значение n, а в качестве правого операнда - вызов функции factorial со значением n, уменьшенным (sub1) на 1. Процесс вычисления факториала в ПССЛ основывается на использовании стека исполнения [Вагин, 1988].

Представление факториала при помощи ЛВС-сети показано на рис.4. Процесс вычисления факториала выполняется итерационно. В качестве исходных значений имен терминальных вершин Число и Результат задаются соответственно: число n, факториал которого необходимо вычислить, и 1. Присвоение имени вершины Результат значения 1 соответствует факту, что 0! = 1. Вершина AND_CONDПроверка условия;Ф Хравно0 является условной И-вершиной (см. пример №1), которой сопоставлено имя метода 'Ф Хравно0' (формула Х = 0). В качестве фактического параметра этой формулы выступает вершина Число. Случай, когда формула выполняется, соответствует ситуации завершения вычисления факториала. В этом случае формула Х = 0 принимает значение 1, и выводимой вершиной будет вершина AND_Исход_1;Ф Х, где в качестве фактического параметра формулы Х выступает вершина Результат.

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

Случай, когда формула Х=0 не выполняется, соответствует ситуации вычисления факториала. В этом случае результатом выполнения формулы Х=0 будет 0, что приведет к выведению вершины AND_Исход_0. Из данной вершины выводится вершина AND_Результат;Ф АВ. Данной вершине сопоставлено имя метода 'Ф АВ', что соответствует формуле А*В, где в качестве фактических параметров этих переменных выступают вершины Число и Результат. В результате выполнения формулы А*В вычисляется новое значение имени 'Результат'. Далее выводится вершина AND_Переопределение числа;Ф Хминус1, которой сопоставлена формула Х-1, где в качестве фактического параметра переменной Х выступает вершина Число. Далее выводится итерационная вершина AND_CYCLПереход_Число, обработка которой приводит к передаче управления вершине Число, имени которой присваивается значение, вычисленное в вершине AND_Переопределение числа;Ф Хминус1. Далее процесс вывода вновь переходит к терминальным вершинам, причем, как показано выше, имена этих вершин имеют переопределенные значения.

Процесс вычисления факториала завершается, когда значение имени вершины Число станет равным 0 (при этом значением имени вершины Результат будет вычисленное значение факториала для числа n). Тогда при выведении вершины AND_CONDПроверка условия;Ф Хравно0 результатом выполнения формулы Х=0 будет 1, и, как следствие, будет выведена вершина AND_Исход_1;Ф Х, имени которой, как показано выше, присваивается значение имени вершины Результат.

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

Пример №3. В качестве примера представления знаний, выполненного при помощи блочной семантической сети (БСС), рассмотрим построение таксономии классов животных (см. рис.5 (данный пример и рис.5 взяты нами из [Allen et al., 1982])).

На рис.5 показано, что Джордж1 (GEORGE1) является элементом класса Люди (PERSONS). В свою очередь, класс Люди находится в отношении включения с классами Двуногие животные (2-LEGGED ANIMALS) и Млекопитающие (MAMMALS). В то же время класс Собаки (DOGS) находится в отношении включения с классом Млекопитающие, а классы Двуногие животные и Млекопитающие находятся в отношении включения с классом Животные (ANIMALS).

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

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

Отметим, что в [Allen et al., 1982] данное представление рассматривается как пример правильного представления знаний в БСС. Однако анализ данной таксономии показывает, что при представлении знаний допущена ошибка, связанная с тем (см. рис.5), что между классами Двуногие животные и Млекопитающие не определены отношения (существующие в реальной действительности), что приводит к противоречию. Так, из того, что между названными классами не определены отношения, можно сделать вывод, что, с одной стороны, не существует млекопитающих, являющихся двуногими животными, с другой стороны, не существует двуногих животных, являющихся млекопитающими. Из этого можно сделать вывод, что люди, являясь млекопитающими, не являются ими, будучи двуногими животными, и, являясь двуногими животными, таковыми не являются, будучи млекопитающими. Получаем противоречие.

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

Данное противоречие (и способ его разрешения) удается установить при представлении таксономии в ЛВС-сети (см. рис.6). В результате верификации данной ЛВС-сети средствами системы СЛОГАН [Кондращенко, 2002] выявлен невод [Яловец, 2002], что означает, что в структуре ЛВС-сети диагностировано логическое противоречие. Для разрешения выявленного противоречия система рекомендует частично перестроить структуру ЛВС-сети и переопределить имя одной из ее внутренних вершин (исправленная таксономия представлена на рис.7).

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

Заключение

На основании выполненного сравнения свойств ЛВС-сети со свойствами трех известных сетевых МПЗ можно утверждать, что ЛВС-сеть не уступает по своим функциональным возможностям другим сравниваемым сетевым МПЗ. В частности, из рассмотренных примеров следует, что ЛВС-сеть позволяет: представлять как декларативные, так и процедурные знания; представлять логические операции; представлять как экстенсионал, так и интенсионал имен; выявлять и разрешать противоречия в представленных знаниях. Причем, как показано в табл.1, перечисленные свойства не ограничивают всех свойств, присущих ЛВС-сети. Вместе с тем, даже названные свойства одновременно не присущи ни одной из прочих рассмотренных сетевых МПЗ.

Список литературы

7. [Allen et al., 1982] Allen J.F., Frisch A.M. What's in a Semantic Network? // Proceedings of the 20th annual meeting on Association for Computational Linguistics. - Toronto (Canada). - 1982.

8. [Hendrix, 1979] Hendrix G.G. Encoding Knowledge in Partitioned Networks // Associative Networks: Representations and Use of Knowledge by Computers. - New York: Academic Press, 1979.

9. [Levesque et al., 1979] Levesque H., Mylopoulos J. A Procedural Semantics for Semantic Networks // Associative Networks: Representations and Use of Knowledge by Computers. - New York: Academic Press, 1979.

10. [Shapiro, 1991] Shapiro S.C. Cables, paths and “subconscious” reasoning in propositional semantic networks // Principles of Semantic Networks. - San Mateo: Morgan Kaufmann Publishers, 1991.

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