На правах рукописи

ТОЛПЕГИН Павел Владимирович

АВТОМАТИЧЕСКОЕ РАЗРЕШЕНИЕ КОРЕФЕРЕНЦИИ

МЕСТОИМЕНИЙ ТРЕТЬЕГО ЛИЦА

РУССКОЯЗЫЧНЫХ ТЕКСТОВ

Специальность 05.13.17 – Теоретические основы

информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва – 2008

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

Научный руководитель: доктор физико-математических наук, профессор Рязанов Владимир Васильевич

Официальные оппоненты:

доктор технических наук Зеленков Юрий Григорьевич доктор технических наук, профессор Местецкий Леонид Моисеевич

Ведущая организация: Институт системного анализа Российской академии наук (ИСА РАН)

Защита диссертации состоится “_” _ 2008 г. в час. на заседании диссертационного совета Д 002.017.02 Вычислительного центра им. А.А. Дородницына Российской академии наук по адресу: 119333, Москва, ул. Вавилова, д. 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан “_”2008 г.

Ученый секретарь диссертационного совета, В.В. Рязанов д.ф.-м.н., проф.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В представленной работе исследуется одна из центральных проблем автоматической обработки текстов (АОТ) – проблема автоматического разрешения анафорических связей. Предлагаются алгоритмы установления кореферентных связей, приводятся практические результаты для информационно-новостных текстов. Функциональная сторона разрешения анафоры, как этапа ЕЯ-анализа, заключается в установлении зависимостей между объектами (именными и другими группами), расположенными в простых предложениях (клаузах) на протяжении единицы текста. Указанная проблема разрабатывалась и решалась на примерах больших корпусов ЕЯтекстов с использованием методов математической теории распознавания.

Работа с корпусами текстов представляется актуальной по ряду причин. Во-первых, в 60 – 90-е гг. XX в. различные виды знаний закладывались в ЭВМ вручную в форме частных правил, при этом не использовались средства их автоматического извлечения из корпусов текста.

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

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

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

и с с л е д о в а н и я послужили труды отечественных и зарубежных ученых в области математической и прикладной лингвистики, машинного перевода Л.Н. Иорданской, Дж. Николс, Е.В. Падучевой, Е.В. Рахилиной, А.С. Чехова, А.Д. Шмелева, М.И. Откупщиковой, Р. Миткова, В.Г. Гака, И.А. Муравьевой, О.Ю. Богуславской, Ю.С. Мартемьянова, А.В. Гулыги, Е.М. Вольф, З.М. Шаляпиной, И.И. Ревзина, работы в области машинного обучения и распознавания образов Ю.И. Журавлева, В.Л. Матросова, К.В. Рудакова, В.В. Рязанова, О.В. Сенько, исследования специалистов в области искусственного интеллекта и автоматической обработки текстов Д.А. Поспелова, Г.С. Осипова, В.Ф. Хорошевского, Ю.Г. Зеленкова, А.Н. Аверкина, А.И. Эрлиха и др.

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

задачи исследования:

– систематизация формальных средств выражений анафорических связей и зависимостей для местоимений третьего лица;

референциальный выбор;

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

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

– создание экспериментальной программной среды для аккумуляции статистической информации о референциальном выборе реального антецедента для местоимения третьего лица;

– создание корпуса русскоязычных ЕЯ-текстов, размеченных экспертом на предмет кореферентных связей между анафором и антецедентом, а также размеченных автоматически морфологическими, синтаксическими и первично-семантическими анализаторами;

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

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

признаковое пространство при определении кореферентных связей; свойства признаков, генерируемых упомянутыми методами и алгоритмами; модели распознавания кореферентных связей.

новостных изданий. Общий объём автоматически проанализированных текстов составил более 140 Мбайт.

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

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

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

На защиту выносятся следующие положения:

1. методы анализа неразмеченных корпусных ресурсов (источников большого объёма ЕЯ-текстов) и результаты их применения в задаче разрешения анафорических связей местоимений;

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

одушевлённости для валентностей русскоязычных глаголов;

– алгоритм синтаксической деривации;

– алгоритм определения конфликтующих антецедентов;

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

антецедентом и алгоритм некореферентности местоимений;

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

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

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

7. модель подготовки и обработки размеченных ЕЯ-текстов с целью выявления закономерностей и значимых систем признаков;

8. результаты испытания модели на размеченном корпусе информационно-новостных текстов (свыше 2000 фрагментов текстов объёмом, превышающим 3 Мбайт).

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

(1) международной конференции «Диалог 2006» – Компьютерная лингвистика и интеллектуальные технологии (Бекасово, 31 мая – 4 июня 2006 г.);

(2) 10-ой национальной конференции по искусственному интеллекту с международным участием КИИ-06 (Обнинск, 25-28 сентября 2006 г.);

(3) научно-технической конференции «Информационные технологии в бизнесе» (Москва, ГУ ВШЭ, 2006);

(4) международной конференции «Диалог 2007» – Компьютерная лингвистика и интеллектуальные технологии (Бекасово, 30 мая – 3 июня 2007 г.);

(5) 7-ой международной конференции «Информационное общество, интеллектуальная обработка информации, информационные технологии», 24-26 октября 2007 г. НТИ-2007. (Москва, ВИНИТИ РАН).

П у б л и к а ц и и. По теме диссертации опубликовано 18 работ, общим В А К М и н о б р н а у к и Р о с с и и – журнал «Информационные технологии»

(№№ 8,9, 2006 г.).

поддержаны:

(1) конкурсом в е д у щ и х н а у ч н ы х ш к о л «НШ-5833.2006.1»

алгоритмического аппарата для решения сложных задач интеллектуального анализа данных, распознавания и прогнозирования» (исполнитель проекта);

«Разработка, создание и внедрение процедуры апостериорной оценки качества поиска на основе поведения пользователей» (рук. проекта);

(3) г р а н т о м Р Ф Ф И № 06-06-80464-а 2006 г.: «Разработка и реализация методов семантического и прагматического анализов ЕЯ-текстов русского языка» (рук. проекта);

«Формирование нечётких мер для валентностей русскоязычных глаголов»

(рук. проекта).

С т р у к т у р а р а б о т ы. Диссертация состоит из введения, четырех глав и заключения. Основной текст изложен на 179 стр. при общем объёме 241 стр., включая 3 приложения и библиографию из 181 наименования.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Приводится понятие первично-семантического графа, который строится автоматически для каждого отдельного предложения. Первичносемантический граф G – это граф, строящийся на этапе первичного семантического анализа [Сокирко, 2005], ориентированное дерево, вершиной которого является глагольная группа (root), узлами которого являются члены предложения, а ребрами – валентные связи. Рассматривались следующие основные свойства узлов графа G: wi.morpho – морфологические характеристики (кроме одушевлённости); wi.inf – начальная форма; wi.anim – одушевлённость; wi.top – управляющий узел. Понятие первичносемантического графа является базовым во многих задачах АОТ.

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

Разрешение анафорических связей (связи местоимения с расположенными до него по тексту объектами Мира) является главным этапом при построении когнитивной карты и при семантическом связывании серии предложений.

Вводится перечень видов знаний, применяемых для разрешения местоимённой анафоры (морфологические, синтаксические, семантические, знания дискурса, знания о Мире).

В [Aone и Bennett, 1995, 1996] предложена идея разрешения анафоры с использованием алгоритмов распознавания образов – MLR (Machine learning resolver). Задача выявления кореферентной связи между заданным анафором Анф и некоторым ГАj при известном списке конкурирующих гипотетических антецедентов ГА1, ГА2, …, ГАj решалась в два этапа. Сначала происходило распознавание наличия кореферентной связи между анафором и каждым отдельным ГАi, i=1,2, …,l, с помощью решающего дерева (алгоритм C4. [Quinlan, 1993]) по признаковым описаниям соответствующих пар. Далее применялись эвристические логические правила для выбора реального антецедента. В случае если пара является кореферентной, решающее дерево возвращает тип анафорической связи.

Обучение осуществлялось только для тех местоимений, которые были идентифицированы программой автоматически. Корпус для обучения содержал 1971 анафор, 1359 из которых были идентифицированы программой. Полнота работы системы (отношение числа корректно разрешённых задач установления кореференции к общему числу местоимений, идентифицированных системой в тексте) варьирует от 67,53 до 70,2%, точность (доля правильно определённых кореферентных связей) – от 83,49 до 88,55%.

Система RESOLVE [McCarthy и Lehnert, 1995] также использовала алгоритм С4.5 – решающие деревья. Вектор признаков, применяемый при обучении, формировался в отдельности для кореферентных и некореферентных пар. Выборка состояла из 322 объектов первого класса (кореферентные пары) и 908 объектов второго класса (некореферентные пары). Признаки содержали информацию о референции к имени собственному, о дублирующих референциях к одной и той же именной группе, метрические признаки (осуществляется ли кореференция к ГА, находящемуся в том же предложении, что и рассматриваемый Анф).

Корпусные признаки и признаки одушевлённости не использовались.

Точность и полнота системы составили 85,8 и 92,4% соответственно.

Подходы [Soon, Ng, Lim, 1999] и [Soon и др., 2001], основанные на алгоритмах С4.5 и С5, соответственно, дополнительно использовали определение семантических классов слов и их групп на основе словаря WordNet. Вектор признаков строился для пар и включал метрические показатели, признак согласованности в роде и числе, семантический класс, показатель имени собственного. Точность и полнота составили 68 и 52%.

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

Во второй главе («Вычисление признаков в задаче установления кореферентных связей») приводится описание методов генерации новых признаков с применением корпусно-ориентированных средств и алгоритмов поиска оптимальных признаковых подпространств. Это позволяет расширить исходное признаковое пространство за счёт анализа корпусов текстов и частично компенсировать нехватку данных, относящихся к компетенции семантики, логики, знаний о Мире. Отсутствие комплексных семантических и онтологических ресурсов продиктовало необходимость в использовании корпуса текста большого объёма, размеченного синтаксическими связями, в качестве источника дополнительной информации. В основу подхода по формированию корпусных признаков положена идея оценки степени встречаемости глагольной группы и гипотетического антецедента в синтаксически размеченном корпусе [Ido Dagan и Alon Itai, 1990, 1991].

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

Иллюстрация корпусного признака:

В автомобиль? Иван? встроил блокиратор? коробки переключения По данным поиска шаблона «ГАi»+«ГГ» в имеющемся неразмеченном корпусе текстов «угнать автомобиль» встречается в 124 раза чаще, чем «угнать блокиратор». А «угнать Ивана» – в 43 раза реже, чем «угнать автомобиль». Соответствующие частоты используются для вычисления серии корпусных признаков.

Вычисление признаков в задаче установления кореферентных связей с (1) Корпусные признаки основаны на оценке степени встречаемости глагольной группы (ГГ), управляющей анафором, попарно с каждым из гипотетических антецедентов (ГАi) в н е р а з м е ч е н н о м корпусе текстов.

Были предложены следующие к о р п у с н ы е п р и з н а к и, реализующие идею сочетаемости ГГ и ГАi:

предлогом н а р а с с т о я н и и д о t с л о в, в прямом или обратном порядке, без ограничений на морфологию;

находится в падеже анафора;

контактно в прямом или обратном порядке с уточняющим (присвязочным) словом.

одушевлённости» валентностей русскоязычных глаголов.

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

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

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

Например, для предложения «Фёдор вышел на террасу» анализатор возвращает следующую структуру:

№ предложения; № узла; wi; wi.inf;wi.morpho+wi.anim; № управляющего узла; valk 1;0; ФЕДОР;ФЕДОР;С,имя,од,мр,им,ед,;1;SUB;

1;1; ВЫШЕЛ;ВЫЙТИ;Г,дст,нп,св,прш,мр,ед,;ROOT;;

1;2;НА ТЕРРАСУ;ТЕРРАСА;С,но,жр,вн,ед,;1;TRG-PNT;

Для каждого идентифицированного глагола vj (vj.morpho=ГЛАГОЛ) устанавливаются подчинённые ему существительные {wi: valk(vj, wi)} путём обхода первично-семантического графа как ориентированного дерева. Для каждого wi определяются морфологические характеристики, в частности – морфологическая одушевлённость. Таким образом, раздельный подсчёт числа одушевлённых (од) и неодушевлённых (но) wi для рассматриваемого входного условия {vj, valk} или {vj, valk, wi.morpho} позволяет сформировать оценки степени одушевлённости и алгоритмы их вычисления.

Оценка степени встречаемости неодушевлённости для глагола в рамках заданной валентности:

val (v j, wi ) = valk, wi.top = v j.

Оценка степени встречаемости неодушевлённости для глагола в рамках заданных валентности и морфологических характеристик:

суммирование по i: val (v j, wi ) = valk, wi.top = v j, ( wi.morpho = v j.morpho).

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

i: val (v j, wi ) = val k, wi.top = v j.

µ 2 (vi, valk, w j.morpho) и µ 3 (v i, val k, w j.morpho) используются для расширенного признакового пространства в качестве числовых признаков с индексами BJ61, BK62, BL63. На базе указанных числовых признаков формировались бинарные признаки (BY76, BZ77, CA78): значение признака устанавливалось равным «1» в случае достижения признаком максимального значения среди антецедентов для рассматриваемого анафора, и равным «0» – в противном случае.

Для ранее приведённого контекста, местоимения она и её находятся в разных валентных зависимостях от глагола любить: SUB и CONTEN соответственно. Оценка степени одушевлённости µ1 для этого глагола и валентности SUB составляет 70%, а для валентности CONTEN – 39%.

Данный признак является важным для установления кореферентности следующих пар: она и Маша, её и машина.

В процессе практической реализации метода «начитано» 80 Мбайт ЕЯтекстов, по которым автоматически сформирован словарь, содержащий глаголы с оценкой одушевлённости.

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

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

конфликтующими.

Узлы w1 и w2 семантического графа G являются конфликтующими и значение признака CJ87 для каждого узла устанавливается равным «1», если выполнены следующие условия:

1. w1.morpho=w2.morpho – у рассматриваемых узлов совпадают род и число, и, таким образом, они могут одновременно выступать в качестве кандидатов для кореференции;

2. w1.morpho=w2.morpho=СУЩ;

3. valk(w1, w2) – между узлами существует связь.

При невыполнении хотя бы одного из условий значений признака CJ устанавливается равным «0».

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

(1) Два узла w2 и w3 ориентированного дерева G являются с о п о д ч и н ё н н ы м и, если valx(w1, w2) и valy(w1, w3). Для участия в референциальном выборе допускаются существительные, совпадающее в роде и числе с анафором, не соподчинённые рассматриваемому анафору, а также причастия или прилагательные, совпадающее в роде и числе с анафором, не имеющие зависимых существительных (напр., отдыхающие).

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

антецедентом.

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

два местоимения не могут быть кореферентны, если они являются соподчинёнными. Граф для предложения «Она её любит»:

SUB CONTEN

Нахождение оптимального признакового пространства В настоящей работе задача установления кореференции сводится к стандартным задачам распознавания. Пусть задано множество M={S} объектов S. Известно, что M является объединением непересекающихся подмножеств K i, i = 1, l, называемых классами: M = U K i, K i I K j =. Дана начальная информация I0 о разбиении на классы в виде обучающей выборки S m +1,..., S m K i, i = 1, l, m0=0, ml=m. Считаем, что заданы признаковые описания I ( S i ) = ( x1 ( S i ), x2 ( S i ),..., xn ( S i )), I (S ) объектов S i, S с помощью набора n числовых признаков, характеризующих различные свойства объектов.

Требуется ответить на вопросы: S K j ?, j = 1, l.

Совокупность векторов-строк описаний объектов из обучающего множества M0 может быть записана в виде таблицы Tmnl, называемой стандартной таблицей обучения, где m – число объектов обучающего множества, n – размерность признакового пространства, l – число классов.

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

На базе новостных лент двух информационных агентств сформировано две обучающие выборки S1ini (2167 объект класса K1 и 11238 объектов класса K2) и S2ini (127 объектов класса K1 и 1239 объектов класса K2).

(а) поиск признакового подпространства на базе метода достоверных статистических разбиений Произведена оценка индивидуальной способности каждого из признаков по разделению объектов двух классов из таблицы TMNL. Оценка производилась с использованием метода оптимальных статистически достоверных разбиений [Журавлёв и др., 2006] по исходной выборке S1ini.

Для каждого признака X находится такая пороговая точка, которая наилучшим образом разделяет объекты классов K1 и K2 на выборке S1ini. Для 1 – доля объектов класса K1 в S1ini;

1 – доля объектов класса K1 в подмножестве S ini с X;

12 – доля объектов класса K1 в подмножестве m1 – число объектов S1ini с X.

Для каждого признака оценивалась статистическая значимость различий в распределениях объектов классов K1 и K2, выявляемых с помощью оптимальных разбиений. Для этих целей использовался перестановочный тест. Пусть требуется оценить статистическую значимость закономерности с пороговым значением opt вместе с оптимальным (максимальным) значением Fopt функционала F. Генерировалось множество из 100 случайных выборок {S1r,..., S100 }, совпадающих по числу объектов с S1ini.

В каждой из выборок Sir осуществляется случайная перестановка меток классов. Для полученной выборки S'ir ищется оптимальное пороговое значение opt вместе с оптимальным значением Fopt функционала F. Данные вычисления повторяются 100 раз.

В качестве меры статистической значимости закономерности (p– значения) принимается доля выборок из {S1r,..., S100 }, для которых Fopt > Fopt.

(б) выделение значимых признаков на основе тупиковых тестов Использовались результаты работы стохастического варианта метода «Голосование по тупиковым тестам». В качестве входных данных использовались выходные параметры найденных тупиковых тестов случайных подтаблиц таблицы Tm,n,l: вес и участвовавшие признаки.

Проведена серия из 40 опытов на обучающей выборке S1ini.

Определение степени значимости признаков Xi и их ранжирование производилось по формуле:

N – общее число вхождений признака в тупиковые тесты единичной длины;

W – число признаков, участвующих в данном тупиковом тесте для тестов неединичной длины;

Y – общее число вхождений признака в тупиковые тесты неединичной длины;

wi ( X i ), w j ( X i ) – веса тупиковых тестов.

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

Пусть N(i,j) – число одновременных вхождений признаков Xi, Xj в одну закономерность по множеству логических закономерностей P, найденных по логической корреляцией признаков Xi и Xj.

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

В качестве меры корреляционной близости рассмотрим критерий, основанный на полуметрике:

В качестве алгоритма кластеризации для заданной полуметрики r(i,j) и фиксированного числа кластеров использовалась иерархическая группировка, в которой расстояние между кластерами определялось согласно функции:

После нахождения 1 t n кластеров в сокращенную подсистему признаков включаются наиболее информативные признаки, по одному из каждого кластера. Предложенным образом находятся подсистемы из t наиболее информативных и некоррелированных признаков.

В третьей главе («Модели распознавания кореферентной связи») приводится постановка общей задачи для определения кореферентной связи между анафором и антецедентом, модель MB распознавания кореференции, модель DSE распознавания кореференции.

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

Пусть некоторому анафору Анф соответствует совокупность гипотетических антецедентов ГА1, ГА2, …, ГАl, один из которых является истинным ( АнфГАi : coref ( Анф, ГАi ) = 1, i 1,..., l, j i, coref ( Анф, ГА j ) = 0 ). В качестве объектов S будем рассматривать совокупности (S =). Пусть паре соответствует признаковое описание x(Анф, ГАi) = (c1(Анф, i), c2(Анф, i), …, cn(Анф, i)), ct(Анф, i) – значение признака номер t относительно пары.

Признаковым описанием I (S ) объекта S будем считать вектор строку I (S ) =(x(Анф, ГА1), x(Анф, ГА2), …, x(Анф, ГАl)) размерности n l. В качестве множества M рассматриваем множество всех совокупностей S=, допустимых в русском языке. Разбиение на классы определяется реальным антецедентом соответствующего анафора.

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

находятся множества совокупностей Mi={S=}, i=1,2,…,L. Признаковые описания объектов множества Ml и образуют таблицу обучения T M,nl,l для задачи распознавания с l классами. По данным обучающим таблицам строятся стандартные алгоритмы распознавания Аl с l классами, l=2,3,…,L.

Пример 3. Схема референциального выбора для трёх кандидатов Пусть задан некоторый анафор Анф. Определяется соответствующее ему число l гипотетических антецедентов. Кореферентная связь анафора с одним из них устанавливается в результате решения задачи распознавания алгоритмом Аl. Данную модель распознавания кореференции обозначим MB (общая модель).

В таблице 1 приведены результаты распознавания в модели МВ, где в качестве стандартного алгоритма распознавания Аl использовался метод опорных векторов.

Табл. 1.

выборка распознавания, % объектов Учитывая наличие 168 объектов, для которых в качестве альтернативы был всего лишь один кандидат, который выбирался исходя из условий построения системы, совокупная точность алгоритма референциального выбора, построенной на базе модели распознавания, составила 68,24%.

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

Далее в главе описана модель распознавания кореференции, основанная на решении специальной дихотомической задачи распознавания в пространстве признаковых описаний I ( S i ) = ( x1 ( S i ), x2 ( S i ),..., xn ( S i )) и задач распознавания в пространстве оценок (модель DSE).

В качестве множества M={S} допустимых объектов S возьмем допустимые наборы, где ГАi – произвольный гипотетический антецедент для анафора Анф. Первый класс K1 образуют наборы, в которых ГАi – реальный антецедент, i=1,2,…,L (K1={S}: coref(Анф, ГАi)=1), K2 = M\K1). Признаковым описанием S является x(Анф, ГАi) = (c1(Анф, i), c2(Анф, i), …, cn(Анф, i)).

Три вектора признаков для примера 3:

поставить в соответствие таблицу Tm*,n, 2, где m* = M i i (для простоты будем обозначать далее данную информацию как I0). При этом число отнесения S по начальной информации Tm*,n, 2 к одному из двух классов обозначим как задача 0. Отнесение S в один из классов соответствует ответу на вопрос, имеется или нет кореференция анафора с соответствующим ГА. Данный ответ не может считаться окончательным, поскольку в задаче рассматривается вопрос связи анафора с каждым из ГА независимо друг от друга. Таким образом, после решения задачи 0 требуется разработка уточненного алгоритма кореференции, учитывающего информацию о связи анафора с группой ГА в дискурсе.

Пусть построен некоторый стандартный алгоритм распознавания A=R хr для решения задачи 0, где R – распознающий оператор, r – решающее правило. R( I 0, x( Анф, ГАt )) = (at1, at 2 ), где at1, at 2 – оценки, вычисляемые распознающим оператором за первый и второй классы, соответственно.

Сформулируем новую задачу распознавания 0 *. Множество допустимых объектов M * = {S *} формируется по результатам применения распознающего оператора к признаковым описаниям x(Анф, ГА1), x(Анф, ГА2), …, x(Анф, ГАl) (где l – число ГА некоторого Анф), соответствующих Здесь M – совокупность объектов S * = (a, a, a21, a2 2,..., ai1, ai 2 ). Разбиение на классы множеств M i* задается порядковыми номерами реальных антецедентов, соответствующих исходному для S * элементу S =. Задачу распознавания объектов из M i* обозначим как i0 * а соответствующую начальную (обучающую информацию) как I 0i *.

Алгоритмы решения задачи i0 * обозначим A* и будем искать их в виде стандартных распознающих алгоритмов A*=R*хr*. Рассматривались два варианта их построения.

1. Алгоритмы решения задач i0 * с решающим правилом максимума 2. Алгоритмы решения задач i0 * как стандартные алгоритмы В данном случае для заданной задачи i0 * рассматриваются стандартные методы построения распознающих операторов и решающих правил для различных базисных моделей: алгоритмы вычисления оценок, голосование по тупиковым тестам, метод опорных векторов и др.

ГА3=топора ГА2=Раскольников ГА1=к дому В четвертой главе («Программный комплекс распознавания кореферентных связей и результаты практических применений») приводится технологическая карта программного комплекса распознавания кореферентных связей, результаты практических применений моделей распознавания кореференции MB и DSE и результаты поиска оптимального признакового пространства.

Для решения задачи распознавания был создан программный комплекс распознавания кореферентных связей, включающий программы подготовки и обработки ЕЯ-текстов, сервисные и вспомогательные программы, программную систему распознавания по прецедентам «РАСПОЗНАВАНИЕ».

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

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

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

– обучающую выборку S1tr, по 1000 объектов из K1 и K2;

– контрольную выборку S1contr, включающую не вошедшие в S1tr объекты S1ini (1186 объектов из класса K1 и 10219 объектов из класса K2).

Для распознавания выбирались 11, 42, 61 и 84 лучших признаков по функционалу F.

Для решения задачи распознавания использовались методы, вошедшие в систему интеллектуального анализа данных «РАСПОЗНАВАНИЕ»

[Журавлев, Рязанов, Сенько, 2006]:

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

– линейный дискриминант Фишера;

– линейная машина;

– метод АВО (алгоритмы вычисления оценок), вариант метода с голосованием по всевозможным опорным множествам (подмножествам используемых при распознавании признаков);

– метод опорных векторов (SVM), вариант метода с гауссианой размера 6,0 в качестве ядерной потенциальной функции;

– логические закономерности;

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

Определение кореферентного антецедента в модели DSE В табл. 2 приведены результаты распознавания контрольных выборок S contr и S2ini алгоритмами решения задач i0 * с решающим правилом максимума оценок. Столбцы (1) распознавание связей для пар (Анфx, ГАi) – модель MB; (2) оценка результата работы решающего правила по числу верно установленных кореферентных связей в дискурсе для анафора – модель DSE, стандартный распознающий алгоритм А* с решающим правилом максимума оценки.

Табл. 2. Точность распознавания модели с правилом максимума оценок Результаты решения задач i0 * с применением стандартных алгоритмов распознавания в пространствах оценок представлены в таблице 3.

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

Табл. 3. Точность распознавания задач i0 * методом опорных векторов задача число классов задачи распознавания, признаков Схема. Технологический процесс подготовки и разметки ЕЯ-текстов Учитывая наличие 168 объектов, для которых в качестве альтернативы был всего лишь один кандидат, который выбирался исходя из условий построения системы, совокупная точность алгоритма референциального выбора, построенной на базе модели распознавания, составила 83,05%.

Результаты решения задач i0 * с применением Метода опорных векторов в пространствах оценок показало большую точность (83,05%), чем решающее правило максимума оценок (79,8% ).

Найдены оптимальные признаковые подпространства при использовании методов достоверных статистических разбиений, тупиковых тестов и логических корреляций. Оценки точности распознавания для различных признаковых подпространств приведены на рис.1. Следует отметить, что в оптимальные признаковые подпространства входила значительная часть корпусных признаков (BH59, BG58, CB79 и другие);

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

На рис.1 приводится оценка точности распознавания в скользящем контроле S1tr – подвыборки обучающей выборки S1ini, содержащей в каждом классе по 1000 случайным образом выбранных объектов.

точность, % Рис. 1. Эффективность выбора оптимального признакового пространства Исследуются изменения в точности распознавания выборки S1tr при ранжировании числа признаков тремя различными способами: на базе метода достоверных статистических разбиений, на основе тупиковых тестов, на основе логических корреляций. Результаты расчетов показали предпочтительность применения метода достоверных статистических разбиений, использование оптимальных признаковых подпространств из 20признаков практически не снижало точность распознавания.

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

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

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

Серия экспериментов по анализу сформированной статистической выборки показала т о ч н о с т ь в 8 3, 0 5 % (модель DSE, распознавание в пространстве оценок) и 7 7, 9 % (модель DSE, с решающим правилом приблизительно на 20% выше, чем аналогичный результат, признаков.

По итогам анализа контекстов причина ошибок в т о ч н о с т и обусловлена:

(1) ошибкой анализаторов в снятии морфологической и синтаксической омонимии – 9,45%;

(2) отсутствием глубинных семантических знаний, не относящихся к знаниям о Мире, или знаний об узкоспецифичной области – 4,4%;

(3) недостатком статистических данных, получаемых теориями фокуса и центрирования – 2,7%;

(4) ошибками неопределенного или иного рода – 0,4%.

П о л н о т а (отношение числа анафорических местоимений третьего лица, для которых экспертом было успешно проведено связывание с реальным антецедентом, к общему числу анафорических местоимений третьего лица) с о с т а в и л а 7 9, 2 % на тестовой выборке. 20,8% ошибок п о л н о т ы работы системы вызваны:

(1) накапливающейся ошибкой в снятии омонимии используемыми анализаторами. Так, например, «Полевой», являясь реальным антецедентом, определялся не как имя собственное мужского рода, а как прилагательное женского рода. Следовательно, в рассматриваемом дискурсе невозможно было осуществить связывание анафора и антецедента. При анализе таких местоимений как его, их и др., которые имеют морфологическую омонимию, гипотетические антецеденты выбирались в соответствии с родом (и числом), идентифицированным анализатором, что также влияло на полноту – 16,45%;

(2) ограничением в q=2 предложения – как область поиска антецедента, т.е. реальный антецедент мог существенно предшествовать анафору по тексту – 2,8%;

(3) употреблением излишних местоимений – 0,2%;

(4) ошибками иного рода – 1,35%.

Если на начальном опыте при анализе процента ошибок точности (38%) на обучающей выборке отмечалось влияние выразительных средств языка, то анализ значимости новых признаков показал, что в в е д ё н н ы е корпусные признаки занимают места с номерами 4, 5, 9, 10, 13, 16, 28, 33 в перечне из 94 позиций, ранжированном выявил контекстный анализ, большей частью компенсируют нехватку семантики, логики и знаний о Мире, что является новым в развитии рассматриваемой проблемы.

Признаки, связанные с одушевлённостью, занимают менее высокие позиции: 14, 57, 68, 73. Симптоматично, что не столь высокая эффективность признаков одушевлённости как у корпусных признаков объясняется не таким частым появлением контекстов, в которых одушевлённость играет решающую роль. Гипотетические антецеденты могут быть одинаково одушевлённым или неодушевлёнными, однако после применения «прогнозируемой» одушевлённости.

Вместе с тем, если корпусные признаки «строились» на объёме текста порядка 20 Тбайт, то оценки степени одушевлённости – на тексте около Мбайт по причине значительной вычислительной сложности эксперимента.

Различия в объёмах входных данных при построении мер оказали влияние на их полноту. При создании обучающей выборки Str три оценки одушевлённости «отказались» возвратить значение за отсутствием таковой в 15,8; 16,5 и 16,5% случаев, т.е. полнота мер №№ 1-3 составила 84,2; 83,5 и 83,5% соответственно.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. разработаны общая модель распознавания кореференции (MB) и модель распознавания кореференции, основанная на решении специальной дихотомической задачи распознавания в пространстве признаковых описаний и задач распознавания оценок (DSE). Полнота и точность модели DSE составили 79,2% и 83,05% соответственно;

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

а. алгоритм составления оценок степени встречаемости одушевлённости для валентностей русскоязычных глаголов;

б. алгоритм синтаксической деривации;

в. алгоритм определения конфликтующих антецедентов;

г. алгоритм некореферентности анафора с гипотетическим д. алгоритм некореферентности местоимений;

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

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

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

5. создан комплекс программ для ЭВМ, обеспечивающих предобработку ЕЯ-текстов и вычисление числовых величин признакового пространства.

1. Толпегин П.В. Информационно-поисковая система своими руками. XXIX Международная молодежная научная конференция «Гагаринские чтения», т. 5, М.: ИЦ «МАТИ», 2003, с. 16- 2. Толпегин П.В. Словоформы Русского Языка для Информационно-Поисковой Системы. Свидетельство Роспатента о регистрации базы данных № 2003620059, 3. Толпегин П.В. Программа искусственной генерации словоформ английского языка. Свидетельство Роспатента о регистрации программы для ЭВМ № 2003610875, 4. Толпегин П.В. Программа искусственной генерации словоформ русского языка. Свидетельство Роспатента о регистрации программы для ЭВМ № 2003610874, 5. Толпегин П.В. Программа поиска и восстановления словоформ по базе данных. Свидетельство Роспатента о регистрации программы для ЭВМ № 2003610871, 6. Толпегин П.В. Текстовый поиск по сходству. XXX Международная молодежная научная конференция «Гагаринские чтения», т. 5., М.: ИЦ «МАТИ», 2004, с. 62- 7. Толпегин П.В. Технологические приемы построения текстовых информационно-поисковых систем. М.:

Издательский центр «МАТИ», 2004, с. 1- 8. Толпегин П.В. Агентно-ориентированный подход к построению корпоративных систем безопасности с применением методов классификации и распознавания. XXXI Международная молодежная научная конференция «Гагаринские чтения», т. 4., М.: ИЦ «МАТИ», 2005, с. 38- 9. Толпегин П.В. Машинное обучение в референциальном анализе русских естественно-языковых текстов.

Международная молодежная научная конференция XXXII «Гагаринские чтения», т. 4., М.: «МАТИ», 2006, с. 48- 10. Толпегин П.В., Ветров Д.П., Кропотов Д.А. Алгоритм автоматизированного разрешения анафоры местоимений третьего лица на основе методов машинного обучения. Компьютерная лингвистика и интеллектуальные технологии: Труды международной конференции «Диалог 2006» (Бекасово, 31 мая – 4 июня 2006 г.) / Под ред. Н.И. Лауфер, А.С. Нариньяни, В.П. Селегея. – М.: Изд-во РГГУ, 2006, 648 с.:

ил. с. 504- 11. Толпегин П.В. Информационные технологии анализа русских естественно-языковых текстов. Часть I. // Информационные технологии. – 2006. – №8. – С. 41- 12. Толпегин П.В. Информационные технологии анализа русских естественно-языковых текстов. Часть II. // Информационные технологии. – 2006. – №9. – С. 2- 13. Толпегин П.В., Ветров Д.П., Кропотов Д.А. Прагматический анализ с применением подходов к автоматизированному созданию онтологической базы данных. Десятая национальная конференция по искусственному интеллекту с международным участием КИИ-06 (25-28 сентября 2006 г., Обнинск):

Труды конференции. В 3-т. Т.2. – М.: Физматлит, 2006, с. 498 – 14. Толпегин П.В. Новые методы и алгоритмы автоматического разрешения референции местоимений третьего лица русскоязычных текстов. М.: КомКнига, 2006, – 88 с.

15. Толпегин П.В. Автоматизированная межклаузная референция в задаче когнитивного анализа текстов.

Информационные технологии в бизнесе: Тезисы докладов научно-технической конференции студентов, аспирантов и молодых специалистов. – М.: Государственный университет – Высшая школа экономики.

2006, с. 115- 16. Толпегин П.В. Роль корпусных ресурсов поисковых систем в формировании признакового пространства для разрешения местоименной анафоры. Материалы 7-ой международной конференции Информационное общество, интеллектуальная обработка информации, информационные технологии.

24-26 октября 2007 г. НТИ-2007 М.: ВИНИТИ РАН, с. 314- 17. Толпегин П.В. Формирование нечетких мер валентностей русскоязычных глаголов. Отчет конкурса «Интернет-математика» ООО «Яндекс», 2007, [Электрон. документ].

(http://download.yandex.ru/IMAT2007/tolpegin.pdf) 18. Толпегин П.В. Разработка и реализация методов семантического и прагматического анализов ЕЯтекстов русского языка (грант № 06-06-80464-а). ВЦ РАН. Москва. Информационный бюллетень РФФИ №14. М.: Наука,