Выявление анафорических отношений при автоматическом анализе текста

УДК 004.912: 303.7

ВЫЯВЛЕНИЕ АНАФОРИЧЕСКИХ ОТНОШЕНИЙ ПРИ АВТОМАТИЧЕСКОМ

АНАЛИЗЕ ТЕКСТА К.К. Боярский, Е.А. Каневский, А.В. Степукова

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

Введение

Анафора представляет собой явление, при котором смысл одного элемента текста (линейно вторичного, анафора) определяется смыслом другого элемента того же текста (линейно первичного, антецедента). Анафорические связи являются обязательным условием связности текста. Автоматическое разрешение анафорических отношений в естественно-языковых текстах является одной из центральных проблем в автоматической обработке текстов. Однако, несмотря на то, что проблема анафоры достаточно разработана в теоретическом плане [1-3], практически она далека от разрешения. Развитых открытых разработок систем автоматического разрешения анафоры для русского языка на сегодняшний день не существует.

За основу системы автоматического выявления анафор был взят семантико-синтаксический анализатор 8ет8ш, разрабатываемый в СПб ЭМИ РАН совместно с СПб НИУ ИТМО [4]. На вход анализатора подается текст на русском языке. Запускается морфологический анализ, использующий три словарных базы: лемм, фразеологизмов и сочетаемости предлогов [5]. Затем с помощью системы продукционных правил анализатор строит дерево разбора предложения. Была проведена работа по расширению набора правил для пост-анализа анафорических отношений.

Структура правил

Каждое правило состоит из нескольких частей: имени правила, описания переменных, условной и исполнительной частей [6]. В имени правила содержится информация о типе правила (главное или зависимое), а также направление разбора предложения - справа налево или слева направо. В описании переменных указывается «область действия» переменной (работает ли она в границах сегмента или способна выходить за них), а также позиция переменной в предложении (например, начало, центр или конец сегмента, положение переменной относительно других переменных). Условная часть правил строится по схеме П\.ЛЪеп...ЕкеП\..ТЪеп...Е18е...ЕМП\ Разрешено использование операторов конъюнкции & и дизъюнкции ОЯ. Проверяться может морфологическая информация (род, число предполагаемого антецедента), синтаксическая информация (принадлежность слова сегменту определенного типа, позиция слова в дереве зависимостей или в предложении), а также семантическая (принадлежность слова определенному семантическому классу по классификатору). Если все условия удовлетворены, выполняются команды исполнительной части. В отличие от главного правила, которое перебирает все слова подряд, зависимое правило может рекурсивно вызывать само себя, каждый раз сдвигая позицию исходной переменной в указанном направлении. Благодаря этому можно осуществлять поиск антецедента в заданной области, если его точная позиция неизвестна.

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

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

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

определенных зависимых; принадлежность хозяина местоимения и антецедента определенному семантическому классу по классификатору.

Местоимение этот

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

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

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

Очень часто при местоимении этот употребляется не повтор слова-антецедента, а какое-либо обобщающее понятие. При этом антецедент может вообще находиться в другом предложении. Например:

Дельфины^] превосходно ориентируются в воде. Удивительна ловкость этих животных^]. Для решения задачи используются следующие особенности анализатора SemSin: возможность анализировать связный текст не только в пределах предложения, но и в пределах целого абзаца, а также подключение семантической информации, хранящейся в классификаторе [5, 7]. Основное правило выглядит следующим образом: <Этот>

#Z1=#Z1; #Z2=InLink(#Zl); #Z3=SegPrev(#Z2); #Z4=Ante(#Z2); #Y5=#Z3-1; #Y6=#Z1-1; If IsLemma(#Z1)="ЭТОТ" & InLinkName(#Z1)="Какой" & CurPos(#Z4)<0 & CurPos(#Y5)>0 Then

СаЖикШ^/^ЭтотЬ"); ElseIf IsLemma(#Z1)='^TOr' & InLinkName(#Z1)="Какой" & CurPos(#Z4)<0 & CurPos(#Y5)< 0 Then

CallRule(U,#Y6," SR: Этот1-"); EndIf </>

Здесь в первой строке после заголовка определены переменные. В данном случае #Z1 указывает на слово «этих», #Z2 - «животных», #Y6 - «ловкость». Остальные переменные не означены. При выполнении условий запускается зависимое правило: ^:Этот1->

#Z1=#Z1; #Z2=gCurPos; #Z3=InLink(#Z2); #Y4=#Z1-1; If IsCommonLemma(#Z1,#Z3)=1 Then Coref(#Z3,#Z1);

ElseIf IsPos(#Z1)="СУЩ" & SubClass(#Z1,#Z3) & NoWay(#Z1,#Z3) Then Coref(#Z3,#Z1);

Else

CallRule(U,#Y4," SR: Этот1-"); EndIf

</>

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

Оказывается, еще при жизни мамы отец увлекался одной мечтательницей и сумасбродкой, княгиней Столбуновой-Энрици[1]. У этой особы[1] от отца есть мальчикщ, ему[2] теперь десять лет, его[2] зовут Евграф. (Б. Пастернак).

При анализе этого текста используется тот факт, что все слова, обозначающие фамилию, имя или отчество, находятся в подклассе «Человек_Личность», к которому относится слово особа. Отметим, что в приведенном примере имеется еще вторая кореферентная группа мальчик - ему - его.

Возвратные местоимения

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

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

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

Местоимения собою, своим находятся в главном предложении, антецедент - подлежащее гость.

Кто-то[1], сопровождавший Гинца и в эту минуту взявший на себя[1] задачу председателя, призывал к порядку. (Б. Пастернак).

Местоимение себя находится в причастном обороте, его антецедент - определяемое слово.

Совершив свой[1] дорожный туалет с довоенным удобством, доктор[1] вернулся в купе к утреннему завтраку... (Б. Пастернак).

Местоимение свой находится в деепричастном обороте, его антецедент - подлежащее слова-хозяина деепричастия.

Местоимение который

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

Студенты проходили практику в том цехе[1] завода, который[1] недавно был реконструирован.

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

По сути дела все это началось задолго до того дня и даже задолго до письма[1], которое[1] так подействовало на моего отца. (В. Белоусова).

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

Личные местоимения

При поиске антецедентов личных местоимений учитываются и морфологические, и синтаксические, и семантические критерии. Здесь мы исходим из предположения, что личное местоимение и его антецедент могут находиться в одном сегменте лишь в ситуациях сочинения: когда местоимение и его антецедент являются зависимыми - непосредственно или опосредованно - сочиненных предикатов [1]. Исходя из этого, сначала проверяются модели анафоры с сочинением, а затем, если антецедент не найден, производится поиск в предшествующих сегментах. Рассмотрим пример анафоры с сочинением.

Учительница ставила табурет[1] у доски и забиралась на него[1] в присутствии всего класса, чтобы достать спрятанную с вечера карту (А. Геласимов).

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

В ряде случаев установить антецедент местоимения таким образом не удается. Например:

Рассказчик стоит вне «ринга»[1], потом подходит к нему[1] и после небольшой паузы шагает внутрь. (Е. Гришковец).

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

Рассказчик

Однор Однор^

ПОДХОДИТ

/ \ Когда Куда ' \

ринга

потом

шагает

/ \ \

Союз Когда Куда 4 \

к 1 и после

1 Дат Род

1 +

нему паузы 1

Какой

+

небольшой

внутрь

стоит.

X I

Субъект Где

/ I

вне

I

Род

I

ринга

Корсф

Рис. 1. Поиск антецедента при наличии сочинительной связи

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

Притяжательные местоимения

Рассмотрим достаточно простое предложение:

От Волынина^] Владимир получил экземпляр его[1] книги об африканских бабочках с дарственной надписью.

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

От Волынина Владимир_ получил экземпляр^его книги

экземпляр

.............получил

Субъект Откуда Винч

Владимир От

I

Род

I

Волынина

Рис. 2. Поиск антецедента притяжательного местоимения

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

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

Это сказал новый папа[1] перед тем, как уйти в богато обставленные апартаменты Ватикана, совсем не похожие на его[1] простую квартиру в Буэнос-Айресе. (Новостная лента).

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

Осенью, когда хомяК[1] собирает на зиму запасы, в камерах его[1] норы находят до 10 кг различных хлебных злаков. (В. Свирчевский).

ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ ИССЛЕДОВАНИЯ ТОПОЛОГИИ.

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

Кирилловская церковь[1] и ее^ двор, где бродили больные в сером, глубоко взволновали меня. (Л. Вертинская).

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

Если Женя[1] видела, что не нравится какому-нибудь мужчине[2], ей[1] и в голову не приходило пытаться завоевать его[2] внимание. (А. Берсенева).

Дополнение правил поиска антецедентов ограничениями на допустимые классы позволяет существенно повысить точность разбора. На корпусе в 600 предложений антецедент правильно устанавливался от 70% (для личных и притяжательных местоимений) до 93% (для местоимения который). Отметим, что часть ошибок была вызвана тем, что в НКРЯ, как правило, приводятся отдельные предложения, а не связные абзацы.

Заключение

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

Литература

1. Падучева Е.В. Высказывание и его соотнесенность с действительностью. - М., Наука, 1985. - 272 с.

2. Тестелец Я.Г. Введение в общий синтаксис. - М.: Изд-во РГГУ, 2001. - 800 с.

3. Кобзарева Т.Ю. Проблема кореференции в рамках поверхностно-синтаксического анализа русского языка // Компьютерная лингвистика и интеллектуальные технологии. Труды Международной конференции Диалог'2003. - М., 2003 [Электронный ресурс]. - Режим доступа: http://www.dia1og-21.гц/АгсЫуе/2003/КоЬ7агеуа.Ь1т, свободный. Яз. рус. (дата обращения 15.08.2013).

4. Каневский Е.А., Боярский К.К. Семантико-синтаксический анализатор 8ет8ш // Международная конференция по компьютерной лингвистике «Диалог-2012», Бекасово, 30 мая-3 июня 2012 г. [Электронный ресурс]. - Режим доступа: http://www.dia1og-21.ru/digest/2012/?type=doc., свободный. Яз. рус. (дата обращения 15.08.2013).

5. Боярский К.К., Каневский Е.А., Стафеев С.К. Использование словарной информации при анализе текста // Научно-технический вестник информационных технологий, механики и оптики. - 2012. -№ 3 (79). - С. 87-91.

6. Боярский К.К., Каневский Е.А. Язык правил для построения синтаксического дерева // Интернет и современное общество: Материалы XIV Всероссийской объединенной конференции «Интернет и современное общество». - СПб: ООО «МультиПроджектСистемСервис» - 2011. - С. 233-237.

7. Тузов В.А. Компьютерная семантика русского языка. - СПб: Изд-во СПбГУ, 2004. - 400 с.

Боярский Кирилл Кириллович - Санкт-Петербургский национальный исследовательский университет

информационных технологий, механики и оптики, кандидат технических наук, доцент, Воуапп9@уаМех.ги Каневский Евгений Александрович - Санкт-Петербургский экономико-математический институт РАН, ве-

дущий научный сотрудник, кандидат технических наук, капеу@етгп%г.ги

Степукова Александра Владимировна - Санкт-Петербургский государственный университет, студент,

icarus_89@mai1.ru

УДК 681.3

ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ ИССЛЕДОВАНИЯ ТОПОЛОГИИ ПОВЕДЕНИЯ И КЛАССИФИКАЦИИ ЭЛЕМЕНТАРНЫХ СЕТЕЙ ПЕТРИ С ПОМОЩЬЮ ВЫЧИСЛЕНИЯ ИХ ГРУПП ГОМОЛОГИЙ

Т.А. Тришина

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