The use of the hypergraphs in linguistic translation g. K. Khakhalin

Техники
THE USE OF THE HYPERGRAPHS IN LINGUISTIC TRANSLATION

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

Вход и выход лингвистического транслятора (ЛТ) имеют разные характеристики. Свойства ЕЯ, с одной стороны, и требования к семантическим описаниям, с другой стороны. Они различны по своей сути. ЕЯ обладает в большом количестве т.н. “неопределенностями”, например, избыточностью, омонимичностью, некомплетивностью, референциальностью, идеоматичностью, вариабельностью конструкций ЕЯ-предложений, всевозможными искажениями (ошибки) и т.д. Требования же к семантическому представлению ситуаций почти противоположны: описания должны обладать однозначностью, определенностью, полнотой, точностью и т.п.

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

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

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

Дадим определение гиперграфа [2]. Гиперграф H (V, ). задается множеством V, элементы которого называются вершинами, и семейством  подмножеств V, называемых ребрами гиперграфа. Гиперграф можно отобразить на плоскости, сопоставляя вершинам точки плоскости (или “кружочки”), а ребрам — связные области, охватывающие вершины, инцидентные этим ребрам. Например, гиперграф H с множеством вершин V = {v₁, v₂,..., v₆} и семейством ребер  = {E₁={v₁}, E₂={v₁, v₃}, E₃={v₁, v₂, v₃}, E₄=E₅={v₂, v₄}, E₆={v₃, v₄, v₅}, E₇=} можно изобразить на плоскости, как показано на рис. 1.

Рис. 1. Общее изображение гиперграфа

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

Рис. 2. Рис. 3.

Рис. 2. Гиперграф для выделения фрагмента предложения:

Рис. 3. Гиперграф для выделения “связки” в сложноподчиненном предложении, например:

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

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

Изоморфизм для простоты изложения рассмотрим применительно к графам [3]. Пусть заданы два графа G₁(Y) и G₂(Z), где Y (соответственно Z) - множество вершин первого (второго) графа. Положим |Y| = n, |Z| = m, где |T| - количество элементов в множестве T. Предположим, что графы неориентированные с раскрашенными вершинами и ребрами. Цвет вершины y_i из графа G₁ обозначим V(y_i) (i = 1,...,n), аналогично для графа G₂ обозначим V(z_j) (j = 1,...,m). Окраску ребра, соединяющего y_i и y_j, обозначим r(y_i,y_j), соответственно r(z_l,z_m).

Задача поиска изоморфизма сводится к следующему: найти множество вершин Y₁ и Z₁ такое, что:

|Y₁| = |Z₁|,

Y₁  Y и Z₁  Z,

G₁(Y)  G₂(Z).

Здесь G₁(Y)  G₂(Z) означает, что эти подграфы изоморфны с учетом окраски вершин и ребер, причем порядок вершин во множествах Y₁ и Z₁ определяет этот изоморфизм.

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


Рис. 5. Два графа с окрашенными вершинами и ребрами

Задача отыскания изоморфизмов имеет обычно множество решений. Например:

Решение 1: Y₁ = {y₁, y₂}, Z₁ = {z₃, z₄}. Решение 2: Y₁ = { y₁, y₂, y₃}, Z₁ = {z₃, z_1, z₂}.

Изоморфизм |Y₁| = |Z₁| = t  min {|Y₁| = |Z₁|} называется t-изоморфизмом. Задача нахождения максимального изоморфизма (с максимальным t) является конечной задачей и поэтому, естественно, может быть решена методом полного перебора; однако можно найти изоморфизм графов через поиск внутренне устойчивого множества графа, построенного по определенным правилам из исходных графов.

Пусть дан граф G(P,M), где P - множество вершин этого графа, а M - матрица смежности. Подмножество вершин этого графа называется внутренне устойчивым, если эти вершины являются попарно несмежными [4].

Задача определения изоморфизма графов сводится к задаче отыскания внутренне устойчивого множества (ВУМ) некоторого другого графа. Для заданных графов G₁(Y) и G₂(Z) граф G (P, M) составляется по следующим правилам:

1) P={y_i z_j / y_i  Y, z_j  Z, V(y_i ) = V(z_j )}.

2) Вершины (y_i, z_j ) и (y_k,z_l) в графе смежны, если отображения y_i  z_j и y_k  z_l противоречат друг другу, т.е. если:

а) i=k или

б) j=l или

в) r (y_i, y_k)  r (z_j, z_l).

Графы G₁(Y) и G₂(Z) t-изоморфны тогда и только тогда, когда в графе G (P, M) существует t несмежных между собой вершин, причем, если вершины (y_i1, z_j1), (y_i2, z_j2),..., (y_it, z_jt) несмежные, то можно положить Y₁ = {y_i1,..., y_it} и Z₁ = { z_j1,..., z_jt}.

Так, для графов, изображенных на рис. 5.,

P={p₁ = (y₁, z₁), p₂ = (y₁, z₃), p₃ = (y₁, z₄), p₄ = (y₂, z₁), p₅ = (y₂, z₃), p₆ = (y₂, z₄), p₇ =(y₃, z₂)}.

Граф G (P, M) для этого случая изображен на рис. 6.

Рис. 6. Граф для отыскания внутренне устойчивого множества

Первое решение - это 2-изоморфизм, определенный отображениями y₁ z₃ и y₂  z₄. Второе решение определяют отображения y₁ z₃, y₂  z₁, y₃  z₂, что дает 3-изоморфизм.

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

3. Общая характеристика гиперграфового представления.

Не трудно заметить, что гиперграфовое представление имеет аналогии с семантическими сетями и с фреймами, но фреймы, как психологическая модель памяти, формально мало обоснованы, а семантические сети до сих пор не имеют стандартного определения, хотя и возникли из формального понятия сети, которое по определению связано с гиперграфом. Гиперграф же имеет четкое формальное определение и теоретически обоснованную процедуру сопоставления (поиска изоморфизма). Если “умело” пользоваться, то ее можно применять в достаточно широких пределах. Сопоставление дает спектр результатов в зависимости от структур гиперграфов, степени вершин и ребер, их окраски и порядка выбора вершин с одинаковой степенью связности в графе с ВУМ при поиске конкретного изоморфизма. То есть такая процедура дает возможность варьировать параметрами при сопоставлении и получать разные результаты исходя из внешних критериев.

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

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

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

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

Восстановление эллипсисов, разрешение анафор и другие подобные задачи лингвистической трансляции решаются за счет выделения требуемого контекста (следовательно, соответствующего гиперграфа) и поиска аналогичного ему в предыдущей или последующей (см., например, относительно “прерванных” высказываний в [5]) части текста.

Заключение

Первоначально гиперграфы и процедуры их сопоставления использовались при решении задач распознавания образов и формирования понятий [6, 7]. В последующем это представление было реализовано в лингвистическом трансляторе, который работал в нескольких экспериментальных системах: в системе доступа к базам данных на ЕЯ, в оболочке машинного переводчика, в системе поиска информации в непрепарированных ЕЯ-текстах по определенным пользователем семантическим описаниям, в системе индексирования ЕЯ-текстов на примере медицинских диагнозов и в системе синтеза графических изображений типа “ТЕКСТ->РИСУНОК. Краткое описания систем и примеры обрабатываемых транслятором различных типов ЕЯ-предложений приведены в [8].

1. Нариньяни А.С. Искусственный интеллект: стагнация или новая перспектива? Труды VI национальной конференции по Искусственному Интеллекту с международным участием - КИИ-98, 5-11 октября. Пущино, Россия, т.1, 1998, с. 15-29.

2. Berge C. Isomorphism problems for hypergraphs. Lecture Notes in Mahtematics. 411. Hypergraph Seminar. 1972. Spring-Verlag, 1974, p. 1-12.

3. Зыков А.А. Основы теории графов. М., Наука, 1987, 384 с.

4. Берж К. Теория графов и ее приложение, М., Изд. ИЛ, 1962, 320 с.

5. Леонтьева Н.Н. Семантический анализ прерванных высказываний на материале массива официальных документов. Труды Международного семинара Диалог'97 по компьютерной лингвистике и ее приложениям (под ред. А.С. Нариньяни). - М., 1997, с. 175-180.

6. Власов А.В., Гинзбург Б.Д., Хахалин Г.К. Процедура построения графа с “внутренне устойчивым множеством” применительно к процессу построения понятия. Вопросы радиоэлектроники. Сер. Общетехническая, вып. 8, 1975, с. 56-61.

7. Байков А.М., Гриднев А.А., Хахалин Г.К. Алгоритм идентификации описаний и его реализация на ЭВМ. - "Вопросы радиоэлектроники", сер. ЭВТ, 1978, вып. 5, с. 54-62.