21. Поиск в семантической сети.

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

Пример 1. Автомобили Нива и Волга движутся навстречу друг к другу по направлению к городу Томску.

//рисунок (10)

Теперь приведем формальное определение. Семантической сетью называется пятерка ((X, O), A, R, f, g),

где (X,0) – простой ориентированный граф (X – множество вершин, O – множество ребер, т.е. фактически упорядоченных пар вершин),

A – множество понятий и имен,

R – множество отношений,

f: X→A – функция разметки вершин (каждой вершине ставится в соответствие одно и только понятие),.

g: O → P(R)/ǿ (11)– функция разметки ребер (каждому ребру ставится в соответствие непустое подмножество понятий).

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

Пример 2. Пусть есть следующее изображение:

//рисунок (12)

Его можно смоделировать с помощью следующей семантической сети:

//рисунок (13)

Здесь, А={КВ, МТ, БТ}, R={в, к, п}.

КВ – квадрат, МТ – малый треугольник, БТ – большой треугольник, в – выше, к – касаться, п – правее.

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

Алгоритмы поиска в семантической сети применимы и в ИПС.

Структура интеллектуальной системы доступа к данным на основе семантической сети.

Так называемая, интеллектуальная система доступа к данным, по сути, является разновидностью ИПС. Ее структурная схема дана на рис. ?.

//рисунок – структура (14)

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

Задача поиска кратчайшего обхода образца в семантической сети.

Семантическая сеть ((X₁, O₁), A₁, R₁, f₁, g₁) называется подсетью семантической сети ((X, O), A, R, f, g), если

A) X₁ X, O₁ O (множества вершин и ребер подсети являются подмножествами соответствующих ребер сети);

B) x_i, x_j X₁ [((x_i, x_j) O)→((x_i, x_j) O₁)] (если две вершины, присутствующие в подсети соединены ребром в сети, то это ребро присутствует и в подсети);

С) x_i X₁ f₁(x_i)=f(x_i) (в подсети сохраняется разметка вершин);

D) (x_i, x_j) O₁ g₁((x_i, x_j))=g((x_i, x_j)) (в подсети сохраняется разметка ребер).

Примечание. Из определения видно, что подсеть фактически можно задать подмножеством вершин, т.к. ребра и разметка сохраняются.

Запрос к семантической сети представляется также в виде семантической сети.

Пример. Изображение.

//изобр. аналогично примеру 2 в пункте 4.5.1 (15 – аналог 12)

Сеть.

//сеть аналогично примеру 2 в пункте 4.5.1 (16 – аналог 13)

Запрос. Какие фигуры находятся правее и касаются квадрата, находящегося, в свою очередь, правее и касающегося треугольника.

//запрос (17)

Формально вводится отображение φ(a):a - > P(A) , которое задает множество суперпонятий, например

T→{МТ, БТ}, ГФ→{КВ, МТ, БТ},

т.е. понятию «Т» (треугольник) соответствуют понятия MT (малый треугольник) и БT (большой треугольник), все квадраты и треугольники соответствуют понятию «ГФ» (геометрическая фигура).

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

Отображение h_Y: X₁→X₂ называется частичным изоморфизмом семантической сети ((X₁, O₁), A₁, R₁, f₁, g₁) на семантическую сеть ((X, O), A, R, f, g) с критериальным множеством Y X, если для x_i, x_j X₁ выполняются следующие условия:

A) (x_i, x_j) O₁ => (h_Y(x_i), h_Y(x_j)) O (каждому ребру в исходной сети должно соответствовать ребро в образе);

B) f₁(x_i)<>a₀ => f(h_Y(x_i)) φ(f₁(x_i)) ( a₀ – это вершина, помеченная вопросом, остальные вершины должны задавать некие суперпонятия, которые должны содержать по крайней мере те понятия, которыми помечены их образы);

С) g₁(x_i, x_j) g(h_Y(x_i), h_Y(x_j)) (если в исходной сети ребро помечено некими метками, то соответствующее ребро в образе должно содержать, по крайней мере, те же метки);

D) Если x_i, x_j Y X1 => [(hy(x_i)=hy(x_j))→(x_i=x_j)]. (разные вершины исходной сети, принадлежащие критериальному множеству Y отображаются в разные образы).

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

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

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

Пример маршрута и изображения

//пример (18)

маршрут

1 -4 – 6 + 4 + z

изображение 1

МТ к^Т КВ п^Т КВ п КВ п БТ

изображение 2

МТ к^Т КВ в^Т КВ п КВ к БТ

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

//пример полного обхода образца, изображения полн обхда и изобр маршр полного обх полнм обх не явл (19)

2 + 3 – 2 + 1 – 2 - полный обход образца,

КВ к ? п^Т КВ п Т к^Т КВ – изображение полного обхода образца.

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

Пример.

КВ к ? к^Т КВ п Т п^Т КВ

//полный обход образца и покрываемый им маршрут

Доказана следующая теорема. Если некоторая подсеть релевантна образцу в соответствии с критерием h_p, то она релевантна ему и в соответствии с критерием h_Y, при пустом критериальном множестве (Y=ǿ (20) ) .

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