«Метод автоматического аннотирования новостных кластеров на основе тематического анализа ...»

Московский государственный университет имени М.В. Ломоносова

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

Алексеев Алексей Александрович

Метод автоматического аннотирования новостных кластеров на

основе тематического анализа

05.13.11 – Математическое и программное обеспечение вычислительных

машин, комплексов и компьютерных сетей

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научный руководитель доктор физ.-мат. наук профессор М.Г. Мальковский Москва – 2014 Оглавление ВВЕДЕНИЕ

1. АВТОМАТИЧЕСКОЕ АННОТИРОВАНИЕ

ЗАДАЧА АВТОМАТИЧЕСКОГО АННОТИРОВАНИЯ

1. 1.2 МЕТОДЫ АВТОМАТИЧЕСКОГО АННОТИРОВАНИЯ

1.2.1 Общая классификация методов

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

1.2.6 Стратегии отбора предложений при подготовке аннотаций... 1.3 ОЦЕНКА КАЧЕСТВА АВТОМАТИЧЕСКИХ АННОТАЦИЙ

1.3.1 Автоматические меры качества ROUGE

1.3.2 Метод «Пирамиды» (Pyramid Evaluation)

1.3.3 Сравнение различных методов оценки автоматических аннотаций

ВЫВОДЫ К ПЕРВОЙ ГЛАВЕ

1. 2. ЛЕКСИЧЕСКАЯ ВАРИАТИВНОСТЬ И ЕЕ МОДЕЛИРОВАНИЕ... ВАРИАТИВНОСТЬ В ТЕКСТАХ НА ЕСТЕСТВЕННОМ ЯЗЫКЕ

2.

ЦЕПОЧНЫЕ МЕТОДЫ СМЫСЛОВОЙ ГРУППИРОВКИ ЯЗЫКОВЫХ

2. ВЫРАЖЕНИЙ

2.2.1 Алгоритм построения лексических цепочек на основе тезауруса WordNet для английского языка

2.2.2 Алгоритм построения лексических цепочек на основе тезауруса РуТез для русского языка

ЛОКАЛЬНАЯ И ГЛОБАЛЬНАЯ СВЯЗНОСТЬ ТЕКСТА

2. 2.4 ПРЕДЛАГАЕМЫЙ МЕТОД ПОСТРОЕНИЯ ТЕМАТИЧЕСКИХ ЦЕПОЧЕК.......... 2.4.1 Формальная постановка задачи построения тематических цепочек

2.4.2 Характеристики схожести языковых выражений для построения тематических цепочек

2.4.3 Алгоритм построения тематических цепочек

АЛГОРИТМИЧЕСКАЯ СЛОЖНОСТЬ И ПРОИЗВОДИТЕЛЬНОСТЬ АЛГОРИТМА

2. ПОСТРОЕНИЯ ТЕМАТИЧЕСКИХ ЦЕПОЧЕК

ВЛИЯНИЕ ЛЕКСИЧЕСКОЙ ВАРИАТИВНОСТИ НА УСТАНОВЛЕНИЕ

2. СХОЖЕСТИ

ВЫВОДЫ КО ВТОРОЙ ГЛАВЕ

2.

3. ИНТЕГРАЦИЯ ТЕМАТИЧЕСКИХ ЦЕПОЧЕК В МЕТОДЫ

АВТОМАТИЧЕСКОГО АННОТИРОВАНИЯ

3.1 ИНТЕГРАЦИЯ В СУЩЕСТВУЮЩИЕ МЕТОДЫ АННОТИРОВАНИЯ............... 3.1.1 Учет TFIDF для многословных выражений

3.1.2 Интеграция в метод MMR

3.1.3 Интеграция в метод SumBasic

НОВЫЕ МЕТОДЫ АННОТИРОВАНИЯ НА ОСНОВЕ ПОСТРОЕННЫХ

3. ТЕМАТИЧЕСКИХ ЦЕПОЧЕК

3.2.1 Построение аннотации по тематическим цепочкам.................. 3.2.2 Построение аннотации по связям тематических цепочек.........

ОЦЕНКА АВТОМАТИЧЕСКИХ АННОТАЦИЙ И ОСНОВНЫЕ РЕЗУЛЬТАТЫ....

3. ВЫВОДЫ К ТРЕТЬЕЙ ГЛАВЕ

3.

4. СИСТЕМА АВТОМАТИЧЕСКОГО АННОТИРОВАНИЯ НА

ОСНОВЕ ТЕМАТИЧЕСКИХ ЦЕПОЧЕК

4.1 ОБЩЕЕ ОПИСАНИЕ ПРОГРАММНОГО КОМПЛЕКСА

4.1.1 Архитектурная схема

4.1.2 Входные данные: Структура и предварительная обработка.... МОДУЛЬ ПОСТРОЕНИЯ ТЕМАТИЧЕСКИХ ЦЕПОЧЕК

МОДУЛЬ АВТОМАТИЧЕСКОГО АННОТИРОВАНИЯ

МОДУЛЬ ОЦЕНКИ АВТОМАТИЧЕСКИХ АННОТАЦИЙ

ВЫВОДЫ К ЧЕТВЕРТОЙ ГЛАВЕ

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ 1

ПРИЛОЖЕНИЕ 2

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

Методы автоматического аннотирования исследовались в трудах российских и зарубежных ученых, таких как Барзилай Р., Добров Б.В., Лукашевич Н.В., Лун Х., МакКьюин К., Мальковский М.Г., Мани И., Машечкин И.В., Ненкова А., Петровский М.И., Севбо И.П., Тарасов С.Д., Шиффман Б., Эдмундсон Х. и многих других авторов. Спектр областей применения систем автоматического аннотирования является обширным и пользователей, до узкоспециализированных аналитических задач. Например, в рамках программы SUMMAC (TIPSTER Text Summarization Evaluation) [43] рассматривалась задача оценки релевантности текстового документа некоторой тематике. Данное исследование предполагало два варианта принятия решения экспертом:

на основании прочтения всего исходного документа;

на основании прочтения аннотации исходного документа.

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

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

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

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

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

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

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

потоков основаны на тематической кластеризации новостных сообщений, т.е.

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

совокупности связанных ситуаций (обладать основной темой кластера, [5], [78]). В описываемой ситуации есть набор участников, которые в исходном кластере:

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

Например, международный аэропорт «Внуково», расположенный в Москве, может упоминаться в рамках некоторого новостного кластера как московский международный аэропорт Внуково, московский аэропорт, столичный аэропорт, аэропорт Внуково, международный аэропорт и так далее.

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

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

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

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

Для достижения этой цели были решены следующие задачи:

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

3. разработка и реализация программного модуля для построения тематических цепочек новостного кластера;

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

Основные положения, выносимые на защиту:

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

существующих методах автоматического аннотирования;

3. На основе построенной модели предложены и реализованы два новых метода автоматического аннотирования;

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

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

Практическая значимость На основе предложенного алгоритма спроектирована и реализована многомодульная программная система со следующими функциональными возможностями:

построения тематических цепочек новостного кластера;

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

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

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

Апробация работы. Основные результаты работы докладывались на следующих конференциях и семинарах:

всероссийской научной конференции «Электронные библиотеки:

перспективные методы и технологии, электронные коллекции»

Образование» (Дубна, 25-30 января 2010 г.);

информации (CDUD), проходящему совместно с конференцией RSFDGrC (Москва, 25-30 июня 2011 г.);

семиотическое моделирование» (Казань, 24-27 февраля 2011 г.);

международной конференции «Диалог» (Московская область, 25мая 2011 г.);

летней школе по информационному поиску RUSSIR (Ярославль, международной конференции «Spring Researchers Colloquium on Databases and Information Systems» (Москва, 1 июня 2012 г.);

всероссийской научной конференции «Электронные библиотеки:

перспективные методы и технологии, электронные коллекции»

(Ярославль, 14-17 октября 2013 г.);

Кроме того результаты обсуждались на семинаре лаборатории анализа информационных ресурсов НИВЦ МГУ, на семинаре в НИУ ВШЭ и на регулярном семинаре ACM SIGMOD в Москве.

Публикации. Основные результаты по теме диссертации изложены в 14 печатных работах, в том числе 3 статьях в журналах из списка ВАК ([68], [72], [74]), 3 статьях, входящих в базу SCOPUS ([1], [3], [4]), 3 – в тезисах докладов ([66], [67], [75]) и 5 в других изданиях ([2], [69], [70], [71], [73]).

Все основные положения, выносимые на защиту, опубликованы в статье [68] журнала, входящего в список ВАК.

четырех глав, заключения и двух приложений. Полный объем диссертации составляет 122 страницы с 15 рисунками и 7 таблицами, объем приложений – 9 страниц. Список литературы содержит 82 наименования.

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

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

1.1 Задача автоматического аннотирования Задача автоматического аннотирования – создание краткой версии некоторого текстового документа или коллекции документов, отражающей наиболее значимую информацию исходного документа или документов ([40]). Традиционно в задаче автоматического аннотирования выделяют несколько независимых направлений классификации решаемых задач и типов порождаемых аннотаций ([48], [49], [55]).

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

посвящены аннотированию одного документа (Single-document summarization), то есть в качестве входных данных выступает единственный документ, такой как новостное сообщение, научная статья, лекция или т.п.

Позже, с развитием исследований в области автоматического аннотирования, а также возникновения большого числа новых источников информации и увеличения информационных потоков в целом, возник новый тип задачи автоматического аннотирования: подготовка обзорного реферата для аннотирования наиболее востребован при обработке большого количества текстовых документов, связанных некоторой сюжетной линией, темой или каким-либо другим параметром. Особую актуальность данному типу автоматического аннотирования придает развитие сети Интернет, содержащей огромное количество различных текстовых документов. Первые онлайн-системы многодокументного аннотирования применялись в задачах обработки потоков новостей, а именно формирования аннотаций для новостных кластеров [45]. Данная задача сохранила свою актуальность и решается в крупных коммерческих новостных агрегаторах, таких как Rambler.News, Yandex.News, Google.News и других.

Автоматические аннотации также различают по типу содержания.

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

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

Потребности пользователя в информации формируют ещё одну плоскость для классификации типов автоматических аннотаций. К текущему предоставление всеобъемлющей аннотации, охватывающей весь объем информации, содержащейся в исходном документе (документах). Данный тип аннотирования отвечает на вопрос «О чем этот документ (эти документы)?» и должен позволить пользователю быстро войти в тематику входной текстовой коллекции, в идеале полностью избавив пользователя от необходимости ознакамливаться с самими исходными документами.

В отличие от общего аннотирования, задачей аннотирования по (query-focused summarization) содержащей наиболее значимую информацию в соответствии с некоторым пользовательским запросом. Данный тип аннотирования отвечает на вопрос «Что в этом документе (этих документах) говорится о ?». Например, в задаче информационного поиска пользовательский запрос превращается поисковой системой в результирующий набор документов, краткая аннотация каждого из которых в результатах выдачи может помочь пользователю быстрее определить релевантность каждого из них. Для подготовки полезной аннотации в данном случае системе автоматического аннотирования необходимо учитывать также запрос пользователя, как дополнение к исходным текстовым документам (самодостаточных в случае общего аннотирования).

Задача подготовки обновленных аннотаций (update summarization) пользователя. Это вариация много-документного аннотирования, которая является чувствительной ко времени: обновленная аннотация должна сюжета, исключая информацию уже известную пользователю (информацию, с которой пользователь уже ознакомлен).

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

1. По принципу составления ([48], [49], [55]):

Экстрактивные аннотации (Extractive summaries) Аннотации в форме абстракта (Abstractive summaries) 2. По типу входной коллекции:

Формирование обзорного реферата – аннотации набора документов (Multi-document summarization) Индикативные аннотации (Indicative summaries) Информативные аннотации (Informative summaries) Аннотирование предложениями (Headline summarization) 5. По потребности пользователя:

Общее аннотирование (Generic summarization) Аннотирование по запросу (Query-focused summarization) Подготовка обновленных аннотаций (Update summarization) Необходимо отметить, что подавляющее число современных систем автоматического аннотирования работает на основе экстрактивного подхода ([41]), автоматической аннотации.

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

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

1.2.1 Общая классификация методов В настоящее время выделяют пять основных классов методов для решения задачи экстрактивного аннотирования ([40], [24]):

Использование частотных характеристик слов: аннотирование на основании ключевых слов – topic words (без применения обучения).

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

Методы, основанные на графах (без применения обучения). Суть III.

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

Подходы, основанные на машинном обучении (machine learning).

Данное направление методов автоматического аннотирования предсказания значимости предложений. Более подробное описание методов данного направления находится в Разделе 1.2.5;

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

1.2.2 Методы, основанные на частотных характеристиках слов Данный класс методов автоматического аннотирования объединяет в себе широкий спектр подходов, которые имеют значительное количество отличий, но при этом несут единую базу – выделение и использование аннотаций ([48], [49]).

1.2.2.1 Частоты и вероятности слов Использование частотности для определения значимости слов было предложено Луном в одной из первых работ по автоматическому аннотированию ([40]). Чем чаще слово употребляется в текстовой коллекции, тем более значимым для данной коллекции оно является. Первым шагом является кластеризация всех слов текстовой коллекции на два класса:

описательные (значимые) слова и слова не являющиеся ключевыми. При этом из потенциального списка значимых слов исключаются:

Стоп-слова - предлоги, союзы и так далее;

рассматриваемой предметной области (например, слово клетка в контексте текстов по биологии);

Следующим шагом эволюции автоматического аннотирования на основе ключевых слов стал уход от жесткого бинарного разбиения слов на «ключевые» и «неключевые» - переход к весам слов. В рамках данной модели каждое слово имеет некоторый вещественный вес, характеризующий значимость данного слова для рассматриваемой коллекции. Наиболее популярными моделями назначения весов являются вероятность слова и TF IDF. При этом результаты систем автоматического аннотирования на основании вещественных весов слов могут значительно отличаться в зависимости от выбора конкретных мер схожести ([50]).

Вероятность слова является простейшим вариантом использования частоты для определения значимости слова ([63]). Она вычисляется как отношения количества вхождений слова к общему количеству слов в документе или коллекции документов. Данная система весов является основой метода автоматического аннотирования SumBasic ([51], [62], [63]), который отбирает предложения для аннотации на основании средней вероятности слов, которые в него входят. Сам алгоритм состоит из пяти шагов. На первом шаге происходит расчет вероятностей слов исходного кластера p(wi) по следующей формуле:

где n – число появлений слова wi в исходной коллекции, N – общее число слов в данной коллекции. Каждому предложению sj на втором шаге назначается вес, равный средней вероятности слов в данном предложении:

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

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

Узким местом использования модели вероятностей слов является работа с общеупотребимыми словами. Данная проблема обычно решается использованием списков стоп-слов, но, очевидно, подобное решение не является универсальным. Система весов TF IDF (Term Frequency*Inversed Document Frequency) предлагает более гибкий вариант модели весов слов, основанной на использовании дополнительного корпуса для выявления общезначимых слов ([58]). Обычно в качестве подобного корпуса выступает большая коллекция документов той же тематики, что и рассматриваемая входная коллекция. Расчет TF IDF происходит по следующей формуле:

где c(w) – частота слова w в рассматриваемой коллекции, d(w) – число документов фоновой коллекции, где встретилось слово w и D – размер фоновой коллекции. Соответственно, ключевыми словами (словами, которые получают высокие веса) в данной модели являются те слова, которые часто встречаются в рассматриваемой коллекции и редко в фоновой. Данная модель относительно проста для расчета и в том или ином виде используется в большинстве существующих систем автоматического аннотирования ([25], [14], [12]).

1.2.3 Тематические модели для автоматического аннотирования 1.2.3.1 Лексические цепочки (Lexical Chains) Модели выделения значимой информации на основе пословного принципиальную проблему: объекты могут описываться в текстовых коллекциях не только одним словом, но и наборами связанных слов и выражений. Формирование лексических цепочек ([35], [38], [6], [7], [26]) цепочка представляет собой совокупность языковых выражений текста, близких по смыслу. Для построения лексических цепочек используются лингвистические ресурсы, называемые тезаурусами. Тезаурус в современной лингвистике - это особая разновидность словарей общей или специальной лексики, в которых указаны семантические отношения (синонимы, антонимы, паронимы, гипонимы, гиперонимы и т. п.) между лексическими единицами. Наиболее популярными ресурсами для построения лексических цепочек являются тезаурусы Wordnet [6] для английского языка и РуТез ([39], [80]) для русского языка.

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

Другое направление автоматического аннотирования на основе лексических цепочек связано с отбором предложений не по наиболее значимым лексическим цепочкам, а по их отношениям ([80]). Критерием включения предложения в результирующую аннотацию в данном случае является наличие двух (или более) наиболее значимых лексических цепочек обсуждение отношений между участниками ситуации, моделируемыми данными цепочками. Данный алгоритм автоматического аннотирования на основе тематического представления по тезаурусу РуТез показал лучшие результаты на первом крупномасштабном независимом тестировании методов автоматического аннотирования The TIPSTER Text Summarization Evaluation (SUMMAC, [42]):

1.2.3.2 Латентный семантический анализ (Latent Semantic Analysis, LSA) Латентный семантический анализ ([21]) представляет собой алгоритм неявного представления семантических особенностей текста на основании статистики совместной встречаемости слов. В работе [28] предложены варианты применения результатов работы алгоритма LSA для задач аннотирования одного документа и построения обзорных рефератов коллекций документов. Результат LSA используется для определения наиболее значимых топиков, не используя при этом вспомогательные лексические ресурсы (тезаурусы, словари и т.д.).

В основе алгоритма LSA лежит представление входной коллекции документов в виде матрицы A: строки матрицы соответствуют словам, встречающимся во входной коллекции, а столбцы – предложениям. Каждый элемент матрицы aij соответствует весу слова i в предложении j. Если слово отсутствует в соответствующем предложении, то значение элемента равно нулю; иначе вес слова равен весу TF IDF. После построения матрицы к ней применяется стандартное сингулярное разложение (Singular Value Decomposition, SVD), в результате которого может быть получено следующее представление для матрицы A:

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

1.2.3.3 Байесовские тематические модели (Bayesian Topic Models) Одной из наиболее сложных и, в то же время, активно развивающихся моделей для задачи автоматического аннотирования является использование байесовских моделей текстов ([15], [30], [20]). В данных моделях коллекция документов представляется как выборка пар документ-слово (d, w), d D (множество документов), w Wd (множество слов документа d), позволяя документу или слову относить сразу к нескольким темам с различными вероятностями. Каждая тема t T описывается неизвестным распределением p(W | t ) на множестве слов w W. Каждый документ d D описывается неизвестным распределением p(t | d ) на множестве тем В модели вероятностного латентно-семантического анализа (probabilistic latent semantic analysis, PLSA, [34]) вероятность появления пары «документ-слово» записывается тремя эквивалентными способами:

где p(t) - неизвестное априорное распределение тем во всей коллекции; p(d) априорное распределение на множестве документов; p(w) - априорное p(t|d) выражаются через p(t|w) и p(d|t) по формуле Байеса:

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

где ndw – число вхождений слова w в документ d; p( w | t ) и p(t | d ) - искомые матрицы вероятностей. Для решения данной оптимизационной задачи обычно применяется EM-алгоритм ([34]).

Проблемами модели PLSA являются линейный рост числа параметров с ростом коллекции документов и невозможность применения имеющихся формул при добавлении новых документов в коллекцию. Основные недостатки модели PLSA устранены в модели скрытого распределения Дирихле (Latent Dirichlet Allocation, LDA, [10], [11]), который основан на той же вероятностной модели:

но при этом также вводятся следующие дополнительные условия:

тем же вероятностным распределением, в качестве которого вероятностным распределением на нормированных векторах Наиболее популярным методом идентификации параметров модели LDA по коллекции документов является сэмплирование Гиббса ([29]).

Сформированные вероятностные распределения могут сравниваться различными мерами схожести, наиболее распространенной из которых является использование дивергенции (расстояния) Кульбака–Лейблера (Kullback–Leibler divergence).

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

Ранжирование и отбор предложений в итоговую аннотацию на основе байсовских моделей происходит с помощью итеративных локальнооптимизационных алгоритмов ([30]). В рамках каждой из итераций отбирается предложение, добавление которого приведет к наибольшему уменьшению КЛ-дивергенции между вероятностным распределением слов коллекции для аннотирования и текущим вариантом аннотации.

1.2.4 Теория графов для построения автоматических аннотаций ранжирования PageRank ([53]). В рамках данного подхода входная коллекция текстов представляется в виде полносвязного графа, вершины которого являются предложениями, а ребра между ними отражают веса схожести между данными предложениями. Предложения, имеющие сильные связи с результирующую аннотацию.

Рис. 2: Пример взвешенного графа сходства предложений Веса ребер полученного графа могут быть нормализованы до вероятностного распределения. В этом случае исследуемый граф становится Марковской цепью, а веса ребер соответствуют вероятностям перехода из одного состояния в другое. На Рис. 2 приведен пример подобного взвешенного графа сходства предложений для некоторого кластера документов (di – номер документа, sj – номер предложения в документе). На базе стандартных алгоритмов для случайных процессов могут быть получены вероятности нахождения в каждой из вершин графа. Вершины с высокой вероятностью соответствуют более значимым предложениям исходной коллекции и должны быть включены в результирующую аннотацию ([53]).

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

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

1.2.5 Использование машинного обучения Задача выбора значимых предложений в методах автоматического представляется как задача бинарной классификации: разбиение всех предложений входной коллекции на принадлежащие и не принадлежащие итоговой аннотации. Экспертные аннотации используется для обучения статистического классификатора, который, в свою очередь, рассматривает каждое предложение как набор потенциальных характеристик для выявления значимости. Для каждого предложения s вероятность его классификации P(s) как предложения для аннотации S (данную вероятность также называют уверенностью классификатора) является весом данного предложения. При заданном наборе из k характеристик Fj: j=1..k, данная вероятность может быть представлена как:

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

где P(s S ) является константой, а P( F j | s S ) и P( F j ) могут быть рассчитаны на основе обучающей коллекции.

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

Широким является спектр применяемых характеристик для установления значимости предложений ([65], [37]), наиболее популярными из которых являются такие характеристики, как: позиция предложения в документе (например, первые предложения новостных сообщений являются обычно наиболее информативными); позиция в абзаце (первые и последние предложения обычно являются более важными); длина предложения, схожесть предложения с заголовком документа; наличие именованных сущностей или предопределенных ключевых фраз и другие.

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

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

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

Метод Максимальной Граничной Значимости (Maximal Marginal Relevance, MMR, [14]) является наиболее популярной концепцией локальной предложений для формирования автоматической аннотации. В рамках каждой итерации алгоритма происходит ранжирование предложений– кандидатов и отбор одного предложения, получившего максимальный вес.

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

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

S – множество предложений кандидатов;

s – рассматриваемое предложение кандидат;

Е – множество предложений, уже отобранных в итоговую аннотацию.

Тогда на каждой итерации алгоритма в итоговую аннотацию будет отобрано предложение, удовлетворяющее следующему условию:

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

Существует ряд модификаций метод MMR для решения задач автоматического аннотирования, отличных от подготовки общих и запросориентированных аннотаций. Например, в работах [12] и [13] предложена модификация алгоритма MMR для создания обновлённых аннотаций ([18]):

Q – запрос пользователя к системе автоматического аннотирования;

s – рассматриваемое предложение кандидат;

H – рассмотренные документы (история документов, с которыми пользователь системы уже ознакомился);

f(H) –> 0 при увеличении H.

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

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

1. Sim1(s,Q): косинусная мера угла между векторами:

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

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

Автоматическая аннотация обладает рядом требований и ограничений, таких как максимизация информативности, минимизация повторов информации, ограничение на общую длину. Поиск точного решения в рамках данных ограничений является NP-трудной задачей ([44]), но приближенное решение программирования ([27]). Для оценки информативности предложений в методах аннотирования на основе глобальной оптимизации используются аналогичные жадным алгоритмам характеристики, такие как частота и позиция слов в документе, TF IDF, схожесть с входной коллекцией и т.д.

В работе [44] проводится исследование различных вариантов разрешения оптимизационных алгоритмов и демонстрируется, что точное решение оптимизационной задачи по выбору предложений может быть Программирования (Integer Linear Programing, ILP). В каноническом виде ILP представляет собой задачу максимизации функции линейного вида при заданном наборе ограничений – нахождение целочисленного вектора x = (х1, х2, …, хn), такого что функция вида z(x)=c1x1+ c2x2+ c3x3+ … + cnxn max (или min), и удовлетворяет системе линейных неравенств:

В работе [44] предлагается модель для применения ILP для решения задачи построения автоматических аннотаций. Пусть si флаг включения предложения i в результирующую аннотацию, Reli его значимость, а Redij избыточность по отношению к предложению j. Тогда общая постановка задачи ILP имеет следующий вид:

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

В работе [27] предложен альтернативный неявный вариант устранения избыточности, на основе общего покрытия концептов входной коллекции результирующей аннотацией. Пусть ci является флагом вхождения концепта (в качестве концептов могут рассматриваться как отдельные слова, так и более сложные конструкции, например, n-граммы слов) в итоговую аннотацию, wi его вес, Occij – флаг вхождения концепта i в предложение j.

Тогда результирующая модель ILP приобретает следующий вид:

Основной проблемой методов глобальной оптимизации является их сложность. С точки зрения времени работы жадные алгоритмы являются более эффективными, в большинстве случаев отрабатывая за константное время, независимо от объема входной коллекции. Приближенные решения обычно масштабируются линейно по объему входных данных, тем самым оставаясь доступными для практического применения. Сложность же точных алгоритмов глобальной оптимизации растет экспоненциально с ростом размера входной коллекции и сложно применимо на практике ([44]), однако изменение модели требований и ограничений может давать сравнительно масштабируемые результаты ([27]).

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

Критерий оценки (содержание, читабельность и т.д., [18], [47]) Область применения ([17], [52], [54]) Оценка систем автоматического аннотирования является сложной очередь ввиду минимальной трудоемкости) является использование набора автоматических мер качества ROUGE (см. Раздел 1.3.1), позволяющий производить автоматическую оценку большого количества автоматических аннотаций на базе нескольких экспертных аннотаций, составленных человеком. Метод «Пирамиды» (см. Раздел 1.3.2) также требует подготовки ручных аннотаций, но кроме того требуется дополнительная работа по выявлению ключевых фактов, которые вручную необходимо выделять и из автоматических аннотаций. Метод «Пирамиды» производит более глубокую оценку конкурсных аннотаций, но связан с большими трудозатратами.

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

1.3.1 Автоматические меры качества ROUGE Recall-Oriented Understudy for Gisting Evaluation (ROUGE, [36]) - набор мер качества и комплекс программ для оценки систем автоматического аннотирования и машинного перевода текстов. Основная идея метода заключается в сравнении генерированной аннотации с эталонной аннотацией, сделанной экспертом. Различные способы сопоставления автоматических аннотаций с экспертными аннотациями, соответствуют различным мерам качества ROUGE, к которым относятся:

ROUGE-N: сопоставление количества пересекающихся N–грамм слов. Наиболее распространенными являются меры качества ROUGE-1, ROUGE-2, однако также во многих работах приводятся оценки по ROUGE-3 и ROUGE-4;

подпоследовательностей (последовательность слов исходного предложения в порядке их вхождения), по отношению к общей длине предложений;

последовательностей (среднее расстояние появления в исходном находящихся на некотором расстоянии друг от друга (между первым и вторым словами биграммы могут находиться другие слова). В качестве параметра в данной мере качества выступает величина окна skip-биграммы - количество слов, которое может параметр порождает различные варианты меры качества, такие как ROUGE-S* (нет ограничения на количество слов внутри биграммы), ROUGE-S4 (максимум 4 слова) и так далее. Стоит отметить, что стандартная мера качества ROUGE-2 является частным случаем монограмм. Данное дополнение связано с узким местом меры качества ROUGE-S, связанной с получением нулевого веса для предложения, в котором слова находятся в обратном порядке, аннотации, так как все биграммы в данном случае будут Общая формула для мер качества ROUGE выглядит следующим образом:

Ai – оцениваемая обзорная аннотация i-того кластера.

Mij – ручные аннотации i-того кластера.

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

Китай и Тайвань установили авиасообщение после 60-летнего Эталонная аннотация, составленная экспертом:

авиасообщение между Тайванем и материковым Китаем.

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

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

1.3.2 Метод «Пирамиды» (Pyramid Evaluation) Метод пирамидной оценки автоматических аннотаций разработан Колумбийским университетом в 2005 году и применяется на конференциях DUC и TAC. Данный метод основан на ручном выделении экспертами «информационных единиц» из эталонных аннотаций - Summary Content Units (SCUs). Каждая SCU представляет собой квант информации, которая, по мнению эксперта, должна быть также отражена в автоматической аннотации.

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

[Суммарный _ вес _ всех _ SCU _ для _ данного _ топика] Пример SCU и её вхождений в текст:

SCU: Мини-субмарина попала в ловушку под водой.

1. мини-субмарина... была затоплена... на дне моря...

2. маленькая... субмарина... затоплена... на глубине 625 футов.

3. мини-субмарина попала в ловушку... ниже уровня моря.

4. маленькая... субмарина... затоплена... на дне морском...

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

1.3.3 Сравнение различных методов оценки автоматических аннотаций Развитие методов оценки автоматических аннотаций является неотъемлемой частью развития автоматического аннотирования. В настоящее время пакет автоматических мер качества ROUGE (см. главу 1.3.1) по существу является «золотым стандартом» в данной области, являясь, по сути, обязательным при представлении любых новых алгоритмов и результатов в области автоматического аннотирования. Метод пирамидной оценки автоматических аннотаций (см. Раздел 1.3.2) появился позже пакета ROUGE, но при этом быстро занял значимое место в сравнении различных методов автоматического аннотирования ([54]).

Для автоматизированных методов оценки качества автоматического аннотирования важной является корреляция с оценками экспертом. В работе [56] приводится оценка взаимной корреляции различных мер качества аннотаций (responsiveness). Сравнению подверглись следующие меры качества ROUGE: ROUGE-n (n = 1, 2, 3, 4), ROUGE-L, ROUGE-W-1.2, ROUGE-SU4 (см. Раздел 1.3.1). Процедура сравнения мер качества ROUGE основана на сопоставлении с ручными оценками автоматических аннотаций:

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

Основной характеристикой при оценке тестовых пар выступала prediction accuracy (точность предсказания), характеризующая процент согласованности данных тестовых сценариев (согласованность ручных и автоматических оценок на пространстве оценок по отдельным кластерам в разрезе пар конкурсных систем). В дополнение к характеристике accuracy были рассчитаны такие меры схожести, как precision, recall и balanced accuracy ([56]). В Табл. 1 приведены результаты оценки по всем указанным характеристикам:

Табл. 1: Результаты сравнения различных мер качества ROUGE по характеристикам Accuracy (A), Precision (P), Recall (R) и Balanced Accuracy В данной работе также произведено исследование вариантов комбинирования различных мер качества ROUGE. В Табл. 2 представлены результаты для различных комбинированных вариантов. Наиболее значимыми результатами данного исследования являются:

качество оценки автоматических аннотаций (качество моделирования автоматической оценки ручных оценок экспертов);

Релевантность различных мер качества ROUGE. В работе показано, что II.

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

Табл. 2: Результаты комбинирования различных мер качества ROUGE 1.4 Выводы к первой главе В данной главе приведено описание задачи автоматического аннотирования, основных подходов, применяемых моделей и методов для её решения, а также способов оценки и сравнения полученных автоматических аннотаций. Наиболее востребованной и значимой на практике является задача подготовки обзорного реферата для коллекции документов.

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

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

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

2.1 Вариативность в текстах на естественном языке Тексты на естественном языке обладают внутренней структурой и подчиняются определенным законам устройства ([22], [76]), а также имеют ряд специфических свойств. Одним из таких свойств является наличие вариативности – использование различных языковых выражений для определения одинаковых реальных физических явлений или сущностей.

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

Во-первых, выделяют различные цели использования вариативности. Одной из таких целей является референция - отнесенность языкового выражения к одному и тому же объекту действительности. Референция широко распространена в текстах на естественном языке и используется для диверсификации упоминания реальных сущностей в тексте с целью исключения повторов. Например, некоторый текст, посвященный решению правительства Киргизии о выводе авиабазы США со своей территории, содержит следующие варианты референции:

3 февраля президент Киргизии Курманбек Бакиев заявил о решении правительства прекратить деятельность авиабазы на территории республики… Президент не стал скрывать, что правительство страны принять такое решение.

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

Судьбу авиабазы США в "Манасе" решит парламент Парламент Киргизии в четверг примет окончательное Природа вариативности также может быть классифицирована по типу привязки к контексту. Употребление общеизвестных альтернативных равноценными названиями единственной страны, и в рамках реальных текстов могут употребляться различные варианты именования:

законодательный орган… Парламент Кыргызстана в четверг примет окончательное решение о судьбе авиабазы США… стали главной причиной побудившей правительство страны принять такое решение.

Также необходимо отметить, что употребление слова СТРАНА также в данном случае относится к общеизвестному типу вариативности, так как данный факт может быть проверен без анализа контекста (взят из предопределенных источников). В то же время может иметь место контекстная вариативность, разрешение которой невозможно без анализа контекста её употребления. Данный тип вариативности является наиболее сложным для установления системами автоматической обработки текстов.

Например, установление вариативности для выражений ОХРАННИК АВИАБАЗЫ и АМЕРИКАНСКИЙ ВОЕННЫЙ невозможно без глубокого смыслового анализа следующего фрагмента текста:

В декабре 2006 года 46-летний водитель … был расстрелян в упор охранником авиабазы Закари Хатфилдом …. Американский военный … также был тайно вывезен с территории страны и до сих пор не предстал перед судом.

Таким образом, общая классификация типов вариативности в текстах на естественном языке может быть представлена в следующем виде:

a. Референция (отнесенность языкового выражения к одному b. Контекстная вариативность (для установления необходим анализ контекста употребления вариативности) установления кореференции имен (построения референциальных цепочек).

Прежде всего, данная задача решается для установления референциальных отсылок для людей и организаций (Президент Российской Федерации Дмитрий Медведев, Президент Медведев, Дмитрий Медведев) ([23], [79]).

Обнаружение в текстах парафраз, т.е. альтернативных способов представления одной и той же информации в текстах, основан на анализе контекстов их употребления ([8]).

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

где W это количество различных контекстов, с которыми встречалось квазисинонимичности для выражений w1 и w2 предлагается вычислять на основе совместного учета количества и качества разделяемых контекстов, по следующей формуле (С – общие контексты выражений w1 и w2):

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

языковых выражений Группы близких по смыслу выражений в «цепочных» алгоритмах собираются в виде лексических цепочек. Лексическая цепочка представляет собой последовательность семантически связанных слов (повторы, синонимы, гипонимы, гиперонимы и др.) и является известным подходом для моделирования связности текста на естественном языке ([33], [38], [81]).

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

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

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

диссертации.

тезауруса WordNet для английского языка В работе [33] предлагается алгоритм построения лексических цепочек на основе тезауруса Wordnet для текстов на английском языке. Каждому слову в Wordnet может быть сопоставлено несколько синсетов – смысловых значений данного слова, а сами синсеты могут быть связаны различными отношениями (синонимия, часть-целое, род-вид и т.д.). Для построения лексических цепочек выделяют три типа отношений:

Экстра-сильные: повторение слова;

Сильные: наличие общего синсета или синсетов связанных горизонтальным отношением;

максимальной длиной и количеством, а также типом перегибов).

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

где C и k являются константами.

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

1. Поиск экстра-сильных отношений с существующими цепочками.

Если отношение найдено, рассматриваемое слово добавляется к данной цепочке (процедура добавления описана ниже). Если отношение не найдено – переход на следующий шаг;

ограничением на дистанцию поиска – не более 7 предложений;

ограничением на дистанцию поиска – не более 3 предложений;

4. Если необходимых отношений найдено не было, то создается новая цепочка – рассматриваемое слово со всеми его синсетами является её единственным элементом.

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

На Рис. 3 представлен пример построения лексической цепочки (4 шага работы алгоритма).

Рис. 3: Пример построения лексической цепочки 2.2.2 Алгоритм построения лексических цепочек на основе тезауруса РуТез для русского языка В работе [81] предложен метод построения тематической структуры текста на основе знаний тезауруса русского языка РуТез. Для построения тематического представления текста сеть понятий тезауруса автоматически разбивается на совокупности близких по смыслу понятий – тематические узлы. Алгоритм разбиения является жадным и состоит из следующих шагов:

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

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

3. Если нет, то образуется новый тематический узел, с центральным элементом Ci. В новый тематический узел вносятся все понятия документа, которые связаны с понятием Ci по непосредственным транзитивности и наследования.

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

a. Центры основных тематических узлов;

b. Другие понятия основных тематических узлов;

c. Центры локальных тематических узлов;

d. Другие понятия локальных тематических узлов;

e. Упоминавшиеся понятия, не вошедшие в предыдущие классы.

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

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

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

глобальная связность.

2.3 Локальная и глобальная связность текста Тексты на естественном языке обладают свойствами глобальной и локальной связности. Глобальная связность текста проявляется в том, что тематическая структура текста может быть представлена в виде иерархии ([22], [76]). Вершина данной иерархии представляет собой основную тему документа, в то время как нижние уровни соответствуют локальным или побочным темам текста. Локальная связность, или связность между соседними предложениями текста, часто осуществляется такими средствами, как анафорические отсылки, например, с помощью местоимений, или посредством повторения одних и тех же или близких по смыслу слов.

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

Под темой/подтемой при этом понимается предикат P(C1, …, Cn ). Его атрибуты C1,…,Cn будем называть тематическими элементами. Таким образом, если текст посвящен обсуждению взаимоотношений между тематическими элементами C1,…,Cn, то в предложениях текста должны обсуждаться детали этих отношений. С формальной точки зрения иерархия тематической структуры образует отношение частичного порядка на множестве тем и подтем исходного документа(ов) = {Pi (Ci_1, …, Ci_n )}, т.е. обладает свойствами:

иной подтемы основной темы текста: s Pi (Ci_1, …, Ci_n ), раскрывающей один из аспектов взаимоотношений тематических элементов Ci_1, …, Ci_n.

При этом отнесение к тематическим элементам Ci_1, …, Ci_n внутри s осуществляется с помощью конкретных языковых выражений, упомянутых в s Pilevel (Ci_1, …, Ci_n ) Pi level (Ci_1 {t i_1 }, …, Ci_n {t i_n }), t i_1,..., t i_n s Общая схема частично упорядоченного множества тем и подтем текста может быть представлена следующим образом:

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

Модель тематической структуры обладает следующими свойствами:

тематическим элементам Cm и Ck во всех предложениях s Раскрытие деталей отношений между тематическими элементами Из описанной модели следует важный практический вывод: если языковые выражения t1 и t2 часто встречаются в анализируемом тексте в одних и тех же простых предложениях, то это означает, что данный текст посвящен рассмотрению отношений между этими сущностями, т. е. t1 и t соответствуют разным тематическим элементам ([32], [38]). С другой стороны, если два языковых выражения t1 и t2 редко встречаются в одних и тех же предложениях текстов, но при этом часто упоминаются в соседних используются для осуществления локальной связности, то есть между ними имеется смысловая связь.

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

легла в основу ограничивающего фактора IsNSCriterion(ti,tj), который является управляющим в предлагаемом алгоритме построения модели участников ситуации новостного кластера (см. Раздел 2.4.2):

где count(A|B) – количество элементов A удовлетворяющих условию B (в данном случае предложений и пар предложений); NS (sk, sm ) - признак последовательного появления предложений sk и sm в одном из документов анализируемого новостного кластера. Необходимо отметить, что критерии, подобные критерию IsNSCriterion(ti,tj), не использовалась ранее для решения таких задач, как установление вариантов именования основных участников ситуации, построение рядов квазисинонимов, лексических цепочек и т.п.

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

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

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

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

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

Каждому участнику в тексте соответствует группа слов и многословных выражений. Предполагается, что в тексте имеется наиболее частотное (главное название участника) и разные варианты, поэтому группа слов и выражений, относящихся к одному участнику, строится в форме тематической цепочки с выделенным центральным элементом: tc {t main [, t1,..., t k ]}, ti – слово или многословное выражение;

основным результатом работы предлагаемого алгоритма [32], [38].

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

Данные предположения основаны на внутреннем устройстве и тематической структуре текстов на естественном языке [22], [33]. Новостной кластер не является связным текстом, но посвящен одной ситуации (или совокупности связанных ситуаций) и содержит большое количество Характеристики схожести языковых выражений, описанные в разделе 2.4.2, основаны на выявлении данных статистических особенностей.

2.4.1 Формальная постановка задачи построения тематических цепочек w {1.. V } - множество слов (Словарь размерности V);

документов, посвященных одному событию (новостной кластер);

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

TC {tci a }, aij {0, 1, 2}, где tсi - тематическая цепочка языковых выражений с выделенным центральным элементом (кластер языковых выражений);

Целевые показатели:

внутрикластерного расстояния;

межкластерного расстояния;

Ограничения:

выражение является элементом не более чем 2 и не менее одной тематической цепочки, либо центром ровно одной тематической tci : (tcij 0 tcik 0) IsNSCriterion (tcij, tcik ) true - выполнено ограничивающее условие на объединение языковых выражений в тематическую цепочку (см. Раздел 2.3).

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

соседнее прилагательное или существительное вправо или влево от исходного слова (контекстный параметр Near);

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

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

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

Контекстно-зависимые характеристики Количество вхождений в соседние предложения (Neighboring Sentence Feature, NSF). Данная характеристика основана на гипотезе глобальной связности текстов на естественном языке [22] и её следствии о том, что элементы одной тематической цепочки чаще появляются в соседних предложениях исходных документов, чем в одних и тех же предложениях.

AcrossVerb, Near, NotNear и NS и распределения их средних значений внутри исходного новостного кластера. Характеристика NSF дает численную оценку (характеристика NS) по отношению к количеству вхождений в одни и те же предложения исходного корпуса (характеристики AcrossVerb, Near и NotNear), и основана на следующем соотношении:

Общая формула вклада характеристики NSF в вес схожести пары выражений имеют следующую форму:

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

Характеристика NSF также является управляющей характеристикой, моделируя критерий лексической связности IsNSCriterion, описанный в Разделе 2.3. Это означает, что два выражения не могут быть включены в одну и ту же тематическую цепочку, если значение характеристики NSF имеет отрицательное значение. Подобная пара с отрицательным значением NSF не тематических цепочек.

Строгие контексты (Strict Context, SC). Данная характеристика основана на сравнении строгих контекстов употреблений слов – текстовых шаблонов. В качестве шаблонов рассматриваются 4-граммы, два выражения влево и вправо от рассматриваемого выражения:

где (tij-2, tij-1, tij+1, tij+2) является строгим контекстом выражения tij в некотором предложении si.

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

принадлежащее отрезку [0,1]. Вес характеристики вычисляется относительно веса пары с максимальным значением разделяемых строгих контекстов, пропорционально весу разделяемых строгих контекстов для текущей пары:

характеристикам предложения (Scalar Product Similarity, SPS). Каждый из контекстных параметров, описанных в разделе 2.4.2.1, представляет собой вектор частот V=(v1,.., vm), сопоставленных каждому слову или выражению для каждого контекстного параметра. Размерности vi данного вектора отражают частоту совместной встречаемости рассматриваемого выражения t или выражения по одному из контекстных параметров с остальными словами и выражениями, упомянутыми в новостном кластере.

После построения данные контекстные вектора могут сравниваться классическими мерами схожести (например, косинусная мера угла между рассматриваемых слов и выражений:

где Context={AcrossVerb, Near, NotNear, NS} – различные типы контекстов.

Значение характеристики SPS имеет вещественное значение, лежащее в пределах от 0 до 1, и вычисляется как косинусная мера схожести по всем контекстным характеристикам, ограниченная сверху значением 1.0.

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

Данная характеристика позволяет находить сходство между такими выражениями как Руководитель – Руководство, Президент России – Российский президент и так далее.

Общий вес характеристики BS имеет вещественное значение из отрезка [0, 1] и вычисляется на основе модифицированной меры Жаккара, классический вариант которой выглядит следующим образом:

где A и B сравниваемые множества, n(AB) и n(AB) – количество элементов в пересечении и объединении множеств A и B соответственно. В нашем выражений, а эквивалентными считаются слова, имеющие одинаковые начала. Общий вид модифицированной меры Жаккара для расчета характеристики BS имеет следующий вид:

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

Информация о схожести, описанная во внешнем ресурсе – тезаурусе РуТез (Thesaurus Similarity, TS). На текущий момент существует большое количество разнообразных предопределенных ресурсов, которые содержат в себе дополнительную информацию о связях слов и выражений. Данная информация может быть использована для построения тематических цепочек и сделать данное построение более стабильным и качественным. Более того, известно, что некоторые типы отношений между словами и выражениями широко используются для обеспечения связности реальных текстов (например, такие отношения как синонимия). Вычисление характеристики TS основано на использовании информации из тезауруса русского языка РуТез [39]. При этом в рассмотрение попадали как непосредственные связи объектов, так и «длинные» связи по транзитивным типам отношений.

Рассматриваются следующие типы связей: синонимия, часть – целое, род – вид.

Значение характеристики TS имеет вещественное значение от 0 до 1 и убывает с ростом длины пути по отношениям между объектами в тезаурусе:

где Nrel – длина пути по отношениям тезауруса (количество связей), {Reltype} – информация о типах связей по данному пути. Функция f (Nrel,{Reltype}) моделирует ослабление связи между выражениями при увеличении расстояния между ними в тезаурусе, с учетом различных типов отношений. В данной работе использовалась линейная модель падение схожести для всех типов связей в размере 0.2 для каждого перехода: TS 1 0.2 N rel.

Similarity, EOS). При анализе схожести тематических цепочек, включающих в себя несколько языковых выражений, важным фактором схожести является наличие общих языковых выражений. Данный фактор особенно важен на количество частично сформированных тематических цепочек, и большинство характеристики EOS является булевым и добавляет 1 балл в общий вес схожести пары в случае наличия одинаковых языковых выражений у характеристики EOS для тематических цепочек tci и tcj имеет следующий вид:

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

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

рядом друг с другом.

производится в порядке снижения коэффициента Near / (AсrossVerb + NotNear). При нахождении подходящей пары слов, они склеиваются в единый объект и все контекстные отношения пересчитываются. Процедура просмотра начинается заново и повторяется до тех пор, пока произведена хотя бы одна склейка. Псевдокод процедуры сборки многословных выражений:

Процедура: Сборка многословных выражений Вход: 1. Новостной кластер D в пословном представлении:

2. AcrossVerb(a1, a2) – количество вхождений слов или 3. Near(a1, a2) – количество вхождений слов или выражений 4. NotNear(a1, a2) – количество вхождений слов или 6. С1, C2, C3 – настраиваемые параметры алгоритма (задаются в интерфейсе программного комплекса) Выход: 1. Новостной кластер D с выделенными многословными // Инициализируем множество объектов отдельными словами T = W;

jointCount = MaxValue;

while(jointCount > 0) jointCount = 0;

// Произвести расчет AcrossVerb, Near, NotNear, Frequency в соответствии с текущими значениями T и D CalculateContextParametersAndFrequencies(D, T);

// Сформировать пары объектов // Отсортировать пары по убыванию ф-ции схожести Pairs.OrderByDescending(Near(ti, tj) – (AcrossVerb(ti, tj) + NotNear(ti, tj)));

foreach pair in Pairs if ( pair. Near C1 max( AcrossVerb (ti, t j T ) ) AND pair. Near AND pair. Near C2 ( pair. AcrossVerb pair.NotNear ) AND pair. Near C3 ( Frequency ( pair. t1 ) Frequency ( pair. t2 ) ) ) tnew = {pair.t1, pair.t2};

// Заменить все вхождения t1 и t2 рядом в D на tnew ChangeAllOccurrences (D, t1, t2, tnew);

end-if;

end-foreach;

end-while;

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

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

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

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

Так для кластера примера о закрытии авиабазы США на территории Киргизии лингвистом были сочтены значимыми следующие многословные выражения:

парламент Киргизии;

киргизский парламент;

денонсация соглашения;

решение правительства.

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

В Табл. 3 представлены результаты оценки точности построения многословных выражений на наборе тестовых новостных кластеров. Данные результаты свидетельствуют о том, что точность предложенного алгоритма находится на уровне ~90%. Для оценки полноты сборки многословных выражений лингвистом были выделены 70 наиболее важных многословных выражений. При этом 72.6% из них были также автоматически выделены предлагаемым алгоритмом, что подтверждает высокую полноту покрытия выделяемых многословных выражений.

синтаксических синтаксических Табл. 3: Результаты оценки точности сбора многословных выражений 2.4.3.2 Формирование тематических цепочек Алгоритм построения тематических цепочек является итеративным. На каждой итераций происходит объединение одной пары языковых выражений (установление семантической связи) или слияние двух тематических цепочек. Конструирование тематических цепочек из пар языковых выражений происходит в порядке убывания весов схожести пар языковых выражений. Общий вес схожести пары языковых выражений вычисляется как сумма весов по отдельным характеристикам схожести, описанным в разделе 2.4.2. Каждая пара получает вес, лежащий в пределах от (отсутствие схожести) до 6 (максимальная схожесть), получаемый на основе шести характеристик схожести, лежащих в пределах от 0 до 1.

Пример ранжирования пар в соответствии с описанным алгоритмом приведен в Табл. 4 (топ-5 пар по общему весу на первой итерации работы алгоритма).

BS TS NSF SC SPS

Пары Президент России – Президент Инвестиционная группа ГМК Норильский никель – Норильский никель Российская Федерация – Россия 0.80 1.00 0.00 0.00 0.51 2. Отставка – Отставка с Табл. 4: Пример ранжирования пар-кандидатов на основании характеристик моделировать структуру отношений между языковыми выражениями в текстах на естественном языке. В основе конструируемых тематических цепочек лежит гипотеза глобальной связности и её прямые следствия ([22], [76]), а также концепции подхода лексических цепочек ([38], [33], [81]).

Предлагаемая структура тематической цепочки обладает следующими свойствами:

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

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

Построение тематических цепочек состоит из следующих шагов:

Рассматривается пара текстовых выражений с наибольшим весом схожести среди всех пар-кандидатов;

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

В целом каждая итерация алгоритма состоит из трех основных шагов:

1. Ранжирование пар-кандидатов (на основании характеристик 2. Выбор пары для объединения (наибольший вес + удовлетворение 3. Процедура объединения (установление семантической связи) Итеративный процесс продолжается до тех пор, пока есть парыкандидаты для объединения с весом схожести выше установленного порога.

Псевдокод алгоритма построения тематических цепочек:

Процедура: Построение тематических цепочек Вход: 1. Новостной кластер D с выделенными многословными выражений – слов и многословных выражений) 2. Similarity_Score(tc1, tc2) – общий вес по характеристикам схожести для тематических цепочек tc1 и tc ограничивающего фактора (см. Раздел 2.3) 4. С1, C2, C3 – настраиваемые параметры алгоритма (задаются в интерфейсе программного комплекса) Выход: 1. Набор тематических цепочек TC новостного кластера D с выделенными центральными элементами – разметка для // Инициализируем множество тематических цепочек отдельными языковыми выражениями TC = T;

joinFlag = true;

while(joinFlag) joinFlag = false;

// Сформировать пары цепочек, удовлетворяющих ограничению Pairs = {(tci, tcj) | IsNSCriterion(tci, tcj)=true, tci, tcj TС};

// Отсортировать пары по убыванию схожести // Выбрать пару для объединения { tci, tcj } = Pairs[0];

// Объединение в случае достаточной схожести if ( Similarity_Score(tci, tcj) > C) if ( Frequency(tci) > Frequency(tcj) ) tcnew={tmain=tmain_i, ti1, …, tin, tj1, …, tjm};

TC.Remove(tci);

tcnew={tmain=tmain_j, ti1, …, tin, tj1, …, tjm};

TC.Remove(tcj);

// Произвести расчет характеристик для новой пары tcnew CalculateParameters (D, TС, tcnew);

TC.Add ( tcnew );

joinFlag = true;

end-if;

end-while;

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

Итерация 7: (Отставка) (Отставка с должности) Итерация 33: (Отставка, Отставка с должности) (Уход в отставку) Итерация 44: (Отставка, Отставка с должности, Уход в отставку) (Отставка президента) Итерация 61: (Уход с поста) (Уход в отставку) Итерация 62: (Отставка, Отставка с должности, Уход в отставку, Отставка президента) (Уход с поста, Уход в отставку) Итерация 102: (Отставка, Отставка с должности, Уход в отставку, Отставка президента, Уход с поста) (Пост) Итерация 103: (Пост, Отставка, Отставка с должности, Уход в отставку, Отставка президента, Уход с поста) (Должность) отставку, Отставка президента, Уход с поста, Должность) (Уход) Следующие тематические цепочки были получены в результате работы описанного алгоритма для кластера примера. Представлены 5 наиболее частотных тематических цепочек, в порядке убывания их частоты. Данные цепочки не подвергались какой-либо постобработке, центры тематических цепочек выделены жирным шрифтом:

Пост: уход с поста; должность; уход; отставка; отставка с должности; уход в отставку; отставка президента Алроса: президент Алроса; АК Алроса Компания: акция компании; владелец компании; объединение компаний;

акция; акционер компании; владелец; пакет акций; состав владельцев;

контрольный пакет акций; контрольный пакет; владение Ничипорук: Александр Ничипорук Якутия: президент Якутии; якутский; якутский президент Общая схема работы алгоритма построения тематических цепочек представлена на Рис. 6.

2.5 Алгоритмическая сложность и производительность алгоритма построения тематических цепочек Описанный алгоритм построения тематических цепочек состоит из двух основных этапов:

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

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

В рамках второго этапа происходит построение тематической цепочки из двух частей, для чего необходимо рассмотрение связей данных частей с другими языковыми выражениями. Таким образом, в худшем случае необходимо рассмотреть 2n связей, а алгоритмическая сложность второго этапа, соответственно, является линейной - O(2n). Практические результаты скорости работы модуля построения тематических цепочек (см. Раздел 4.2) для различных новостных кластеров подтверждают теоретическую оценку сложности:

Новостной кластер Табл. 5: Результаты скорости работы модуля построения тематических Общая сложность предложенного алгоритма построения тематических цепочек новостного кластера с m итерациями работы имеет следующий вид: