Семантические сети

Управление разрешением конфликтов.

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

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

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

- принцип стопки книг,

- принцип наиболее длинного условия,

- принцип метапродукций,

- принцип приоритетного выбора;

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

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

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

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

1. Общие понятия и определения семантических сетей.

2. Способы описания семантических сетей и логический вывод.

1. Семантические сети не являются однородным классом моделей представления знаний. Часто общей основой отнесения схемы представления знаний к семантической сети является то, что она представляется в виде направленного графа, вершины которого соответствуют объектам (понятиям, сущностям предметной области), а дуги – отношениям или связям между ними. И узлы, и дуги, как правило, имеют метки (имена).

Объекты предметной области, отображаемые в семантической сети можно условно разделить на три группы: обобщенные, индивидные (конкретные) и агрегатные объекты.

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

Индивидный объект – каким-то образом выделенный единичный представитель (экземпляр) класса.

Агрегатным называется составной объект, образованный из других объектов, которые рассматриваются как его составные части. Например, изделие состоит из совокупности деталей, предприятие – из отделов, служб, цехов и т.д.

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

Наличие связи типа «род-вид» между обобщенными объектами А и В означает, что понятие А более общее, чем понятие В. Любой объект, отображаемый понятием В, отображается и понятием А, но не наоборот.

Связь «является представителем» существует обычно между обобщенным и индивидным объектом, когда индивидный объект выступает в роли представителя некоторого класса. Экземпляр может быть представителем нескольких обобщенных объектов, в этом случае ему присуще свойство нескольких обобщенных объектов, что соответствует множественному наследованию.

В ряде случаев между связями «род-вид» и «является представителем» не делают различий, отмечая, что эти связи задают отношение «общее-частное». Иногда это приводит к недоразумениям, поэтому для формализации таких связей используют отношения ako (a kind of) и is_a (is a member of the class).

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

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

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

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

- определять основной смысл текста путем поиска множества вершин пересечения,

- осуществлять выбор необходимого значения многозначного слова на основе кратчайшего пути от этого слова к другим словам рассматриваемого предложения (своего рода семантическая метрика),

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

Работы Симмонса и Филмора указали на важную роль глаголов при анализе смысла предложений естественного языка.

Предложение можно представить вершиной-глаголом и различными падежными связками (отношениями). Такую структуру называют падежной рамкой. Среди падежных отношений выделяют следующие:

- агент – отношение между событием и тем, кто (что) его совершает,

- объект – отношение между событием и тем, над чем выполняется действие,

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

- место, время совершения события.

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

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

- объекты-понятия – сведения о физических и абстрактных объектах предметной области,

- объекты-события – абстрактные или конкретные действия, которые могут привести к изменению состояния предметной области,

- объекты-свойства – уточняют понятие и событие, например, указывают характеристики понятий, фиксируют параметры событий и т.д.

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

1) лингвистические отношения,

2) логические отношения (отрицание, импликация, и т.д.),

3) теоретико-множественные отношения, которые включают в себя отношения типа «множество-подмножество»,

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

Особое место при этом занимают теоретико-множественные отношения, обладающие транзитивными свойствами.

Отношение R называется транзитивным, если для любых объектов α, β, γ, таких, что α находится в отношении R с β, и β в отношении R с γ, следует справедливость отношения α находится в отношении R с γ.

В базах знаний выделяют интенсиональные и экстенсиональные знания. Если имеется конечное множество атрибутов А, состоящее из элементов А1, А2…,Аn и конечное множество отношений R, то схемой, или интенсионалом отношения Ri, где i изменяется от 1 до n, называется набор пар вида INT(Ri)={…,[Aj,DOM(Aj)], …}, где DOM – множество возможных значений атрибута Aj.

Экстенсионал отношения Ri – множество фактов {F1,F2,…,Fp}, где F – факты отношения Ri, обычно задаваемые в виде совокупности пар <атрибут-значение>.

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

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

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

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

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

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

Пример:

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

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

Пример концептуального графа с обобщенным маркером:

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

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

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

1. Если вершина отмечена обобщенным маркером, то обобщенный маркер заменяют конкретным индивидным маркером (именным или числовым).

2. Тип вершины можно заменить соответствующими подтипами, обладающими необходимыми свойствами.

Операция объединения позволяет получать из двух графов один. Если на графе G1 имеется вершина-понятие V1, которая аналогична вершине-понятию V2 из графа G2, то можно сформировать новый граф V3, удалив V2. При этом все связи V2 необходимо переориентировать на V1.

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

Операция специализации позволяет сопоставлять две вершины концептуального графа и, если сопоставление успешно, выполнять объединение.

Совместное использование операций специализации и объединения обеспечивают реализацию механизма наследования. Например, заменив обобщенный маркер индивидным, свойство типа распространяется на конкретный индивидный объект. Если в ходе выполнения операция ограничения происходит замена типа на его подтип, то имеет место наследование «класс-подкласс».

Операции специализации и объединения конкретизируют исходный граф. Если граф G1 – конкретизация графа G2, то можно сказать, что верно и обратное (G2 есть обобщение G1).

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

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

Одним из самых простых средств вывода на семантических сетях является поиск по пересечению. Другим средством вывода является сопоставление с образцом.

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

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

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

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

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

Дата добавления: 2014-01-06