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

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

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

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

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

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

1 4 АВГ 2014

Москва-2014

005551775

005551775

Работа выполнена на кафедре алгоритмических языков факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

Научный руководитель:

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

Ведущая организация:

доктор физико-математических наук, профессор, зав. каф. алгоритмических языков ВМиК МГУ имени М.В. Ломоносова, Мальковский Михаил Георгиевич

Фомичев Владимир Александрович доктор технических наук, профессор, НИУ ВШЭ, факультет бизнес-информатики, профессор кафедры инноваций и бизнеса в сфере информационных технологий

Васильев Виталий Геннадьевич кандидат технических наук, доцент, ООО «ЛАН-ПРОЕКТ», научный консультант

Казанский (Приволжский) Федеральный Университет

Защита состоится 19 сентября 2014 г. в 11 часов на заседании диссертационного совета Д.501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет Вычислительной математики и кибернетики, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за 2 дня до указанной даты по тел. (495) 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ имени М.В. Ломоносова http://www.cmc.msu.ru в разделе «Наука» - «Работа диссертационных советов» - «Д 501.001.44».

Автореферат разослан «¿7/» августа 2014 года.

Ученый секретарь диссертационного

совета Д 501.001.44, к. т. н., в. н. с. В.А.

Общая характеристика работы

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

Методы автоматического аннотирования исследовались в трудах российских и зарубежных ученых, таких как Барзилай Р., Добров Б.В., Лукашевич Н.В., Лун X., МакКьюин К., Мальковский М.Г., Мани И., Машечкин И.В., Ненкова А., Петровский М.И., Севбо И.П., Тарасов С.Д., Фомичев В .А., Шиффман Б., Эдмундсон X. и многих других авторов. Спектр областей применения систем автоматического аннотирования обширен, от бытовых информационных потребностей обычных пользователей до узкоспециализированных аналитических задач. Например, в рамках исследовательской программы SUMMAC1 (США) установлено, что время принятия аналитиком решения о релевантности текстового документа некоторой тематике может быть сокращено в 2 раза за счет использования аннотации исходного документа, без статистически значимого ухудшения точности данного решения. Подготовка обзорных рефератов для коллекции документов уже давно является одним из ключевых элементов в организации

1 http://www.itl.nist.gov/iaui/894.02/related nroiects/tipster summac/

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Предложен метод применения построенной модели в существующих методах автоматического аннотирования; .

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

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

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

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

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

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

• автоматическая оценка конкурсных аннотаций.

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

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

• всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» (Казань, 13-17 октября 2010 г.);

• международной конференции «Математика. Компьютер. Образование» (Дубна, 25-30 января 2010 г.);

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

• международной конференции «Системный анализ и семиотическое моделирование» (Казань, 24-27 февраля 2011 г.);

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

• летней школе по информационному поиску RUSSIR (Ярославль, 6-10 августа 2012 г.);

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

• всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» (Ярославль, 14-17 октября 2013 г.);

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

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

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

Публикации. Основные результаты по теме диссертации изложены в 14 печатных работах, в том числе 3 статьях в журналах из списка ВАК ([1], [2], [3]) и 3 статьях, входящих в базу SCOPUS ([4], [5], [6]).

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

Содержание работы

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

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

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

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

S = arg шах /(S*) a Length(S*) < L

s*<=s

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

5 = {i = [w1,..,wm]lm>l},

где we W-словарь, т - количество слов в предложении seS.

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

• языковых выражениях T = {t, =[w11,.. ,wtn\\n>\,i = \..M)

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

• соответствии языковых выражений Г сущностям исходной коллекции.

Вторая глава посвящена проблеме вариативности терминов в текстах на естественном языке, описываются существующие методы выявления различных типов вариативности, а также вводится формальная модель совокупности участников ситуации, описываемой в текстовой коллекции, с учетом вариативности их упоминаний - тематических цепочек. Предлагаемые модель и алгоритм построения тематических цепочек основаны на свойствах глобальной и локальной связности текстов на естественном языке. Ван Дейк и Кинч2 описывают тематическую структуру текста как иерархическую, в том смысле что тема всего текста описывается посредством более конкретных подтем, которые в свою очередь могут быть охарактеризованы посредством еще более конкретных подтем текста и т.д. Под темой/подтемой при этом понимается предикат Р(Cj,...,Сп) , его атрибуты С; ...,Сп будем называть тематическими элементами. Каждое предложение s связного текста посвящено раскрытию той или иной подтемы Pi уровня level основной темы текста: s Р/*1*' ..., С?"51), раскрывающей

и /-ilevel level

один из аспектов взаимоотношении тематических элементов ,...,CLll . При этом отнесение к тематическим элементам ....С^ внутри s осуществляется с помощью конкретных языковых выражений, упомянутых в s:

« j v т»^«' //-«level /-ч level \ ji.Vvf/ .•^V.rvcl f^leveli /-»level v r*leveii\ «.level ilevel „

(CL1 '■••.CLn )=° (CL1 -^Uu }'••• .cu -^{tLn }), tu .....tLl es

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

2 Дейк В., Кинч В. Стратегии понимания связного текста // Новое в зарубежной лингвистике, Выпуск 23, Москва, 1988. - С. 153-211.

Из описанной модели следует важный практический вывод: если языковые выражения t, и t2 часто встречаются в анализируемом тексте в одних и тех же простых предложениях, то это означает, что данный текст посвящен рассмотрению отношений между этими сущностями, т. е. f; и t2 соответствуют разным тематическим элементам. С другой стороны, если два языковых выражения U и t2 редко встречаются в одних и тех же предложениях текстов, но при этом часто упоминаются в соседних предложениях, то это дает возможность предположить, что они используются для осуществления локальной связности, то есть между ними имеется смысловая связь.

Гипотеза о совместной встречаемости связанных языковых выражений легла в основу ограничивающего фактора IsNSCriterion(thtj), который является управляющим в предлагаемом алгоритме построения тематических цепочек: count{{sk,sm)If, e лtj esm лNS(sk,sm))>C• count {s11, e5 лtj es)

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

• ТС = {tc, еам},а^е {0,1,2}, М = |Г| , где ic,- тематическая цепочка

языковых выражений с выделенным центральным элементом (кластер языковых выражений);

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

• Vi: count {[tcy = 2]) = 1 - каждая тематическая цепочка содержит один и только один центральный элемент;

-и-

• Vj:(sum1,..,sumM) = YJtc^rctcij: l^sunij <,2 - каждое языковое

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

• Vic,: > 0 л tcik > 0) => IsNSCriterion(icff, ic№) = true - выполнено

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

В диссертации предложен алгоритм построения тематических цепочек, объединяющий характеристики схожести различной природы - контекстно-зависимых и контекстно-независимых признаков. Каждая характеристика имеет вещественный вес в диапазоне [0,1].

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

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

C(ti ,tj) = NS(ti ,tj)~ 2 • (AcrossVerb(t, ,tj) + Near it,tj) + NotNear (J,, t}))

C(t-,t•)

weightNSF(ti,t.) = min(l,—- ' / )

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

Строгие контексты (Strict Context, SC). Данная характеристика основана на сравнении строгих контекстов употреблений слов - текстовых шаблонов. В качестве шаблонов рассматриваются 4-граммы, два выражения влево и вправо от рассматриваемого выражения: st = (tn,..,tlhl,tihX, ttj,tij+1,tij+2,..), где (tij-2, tij-u tjj+i, tij+2) является строгим контекстом выражения ty в некотором предложении s,-. Итоговая схожесть по характеристике SC для выражений t, и tj имеет следующий вид:

. , , . ^llempteTEMPIATES (Г, )r\TEMPLATES(,t,) (tempi)

weight sc(tntj) =-^-——--

«ш (,„) weight (tempi)

Схожесть контекстов употребления no внутренним характеристикам предложения (Scalar Product Similarity, SPS). Анализу подвергаются вектора контекстов сравниваемых языковых выражений, сравнение производится по классической косинусной мере:

V AcrossVerb _ / AcrossVerb AcrosjVerb\

I ~~ VVi_l > •• i vi_m '

VNear r .Sejr Near\ —--- —--*

= (V; 1 . ...V, m ) (yConteX 1 у Con,Ms

t ^ ~ ' fa ( \

V.N°'Ncar = (v,"0,'".., vffMr) Wel!8JJrSPS tl,tl " I yc^ I. I I

V™ = (vNS vNS )

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

Контекстно-независимые характеристики Формальное сходство (Beginning Similarity, BS). Рассмотрение формального сходства выражений является естественным путем обнаружения семантически-связанных объектов. В существующей реализации используется простая мера схожести - одинаковые начала слов. Сопоставление языковых выражений происходит на основе модифицированной меры Жаккара:

-г nPU ПУ

weighty(/,.,/у) = nVOrÁh utj) + k

lo, ni,) = 0.

rpunword(.t,r\tJ)>0,k = 3,

t,J¡e.T

ИнсЬоумаиия о схожести, описанная во внешнем ресурсе - тезаурусе РуТез (Thesaurus Similarity, TS). Анализ информации из внешнего ресурса -тезауруса РуТез, а именно, следующих видов связей: синонимия, часть -целое, род - вид. Вес схожести убывает с ростом длины пути по отношениям и имеет следующий вид:

где Nre¡ - длина пути по отношениям тезауруса (количество связей), {Rel^J -информация о типах связей по данному пути.

Наличие одинаковых языковых выражений (Embedded Objects Similarity, EOS). При анализе схожести тематических цепочек, включающих в себя несколько языковых выражений, важным фактором схожести является наличие общих языковых выражений:

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

weight^,t}) = f.a^tj) = /(N^tjURzlryJt^tj)})

t,Jj<ET

Near > 2 • (AcrossVerb + NotNear).

Например, тематическая цепочка с центральным элементом пост проходит следующие этапы в процессе построения:

Итерация 7: (Отставка) (Отставка с должности)

Итерация 33: (Отставка, Отставка с должности) (Уход в отставку)

Итерация 44: (Отставка, Отставка с должности, Уход в отставку) <г (Отставка президента)

Итерация 61: (Уход с поста) <г (Уход в отставку)

Итерация 62: (Отставка, Отставка с должности, Уход в отставку, Отставка президента) <г (Уход с поста, Уход в отставку)

Итерация 102: (Отставка, Отставка с должности, Уход в отставку, Отставка президента, Уход с поста) <г (Пост)

Итерация 103: (Пост, Отставка, Отставка с должности, Уход в отставку, Отставка президента, Уход с поста) <г (Должность)

Итерация 104: (Пост, Отставка, Отставка с должности, Уход в отставку, Отставка президента, Уход с поста, Должность) <г (Уход)

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

Ппсшедуца: Построение тематических цепочек

V Вход: 1. Новостной кластер D с выделенными языковыми выражениями Т 2. Similarity_Score(tcj, tc2) - общий вес по характеристикам схожести для тематических цепочек tcj и tc2 3. IsNSCriterion(tch tc2) - признак выполнения ограничивающего фактора 4. Си Съ Сз - параметры алгоритма

V Выход: 1. Набор тематических цепочек ТС новостного кластера D

// Инициализируем множество тематических цепочек отдельными языковыми выражениями ТС = Т; joinFlag = true; while(joinFlag) joinFlag = false; // Сформировать пары цепочек, удовлетворяющих ограничению Pairs = {(К» Щ) 1 IsNSCriterion(tCi, tcj)=true, tcu tcj e TC};

// Отсортировать пары по убыванию схожести Pairs. OrderByDescending(Similarity_Score(tCu tcj) );

II Выбрать пару для объединения {tcu Щ} = Pairs[0];

II Объединение в случае достаточной схожести if (Similarity_Score(tcb tcj) > С) if (Frequency(tci) > Frequency(tcj))

tCnevj~{tmain—tmain_i> Uh ■■■ i Un> tjli ••■ > tjm}>

TC.Remove(tCi);

else

tCnew—{tmain—tmainJ> tilt ••• i Un> tjh ■■■ > tjmh TC.Remove(tcj); end-if;

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

ТС.Add (tc„ew); joinFlag = true; end-if;

end-while;____

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

Лемма. Последовательное применение операций добавления многословного выражения /му/е^),™)^^ и установления схожести /тс^.^^с,^,^2)при выполнении условия на установление схожести для одной из частей

многословного выражения (*)3 приводит к увеличению косинусной меры схожести между предложениями

Wwi.wJ.^ACw,1 6i2)A(w) es2)=>3fc\(w>} ей0л(04 etc)v(w) etc)) (*)

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

В третьей главе описывается алгоритм интеграции построенной модели тематических цепочек в существующие методы автоматического аннотирования Maximal Marginal Relevance4 (MMR) и Sumbasic5. Интеграция заключается в двухступенчатом переходе от пространства отдельных слов (bag-of-words model) к пространству языковых выражений: Слова -> Объекты (слова + мног.выр.) Тематические цепочки I. Замена слов на многословные выражения. Добавление информации о многословных выражениях - переход от слова к объекту (отдельные слова или многословные выражения); П. Добавление информации о принадлежности объектов тематическим цепочкам. В рамках предлагаемой модели тематических цепочек каждый объект может принадлежать к одной или двум цепочкам. Каждая тематическая цепочка имеет вес, равный сумме частот его элементов:

weight {tc) = 2 freqteeiem.i)

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

3 Добавление многословного выражения w'w) в предложение s, в случае вхождения компонентов данного выражения vvj и w' в предложение s2 требует установления дополнительной связи нового выражения w)w) с одним из его компонентов

* Carbonell J., Goldstein J. The use of MMR, diversity-based reranKng for reordering documents and producing summaries И Proceedings of ACM SIGIR' 1998, Australia, pp. 335 - 336

5 Nenkova, A. and L. Vanderwende. The impact of fiequency on summarization // Microsoft Research Technical Report, MSR-TR-2005-101,2005

построении данной тематической цепочки) к максимально возможному баллу схожести:

) = ^ ^ шах {51гт1агИу{Ке1ет п(сгт1ег))

'С**,

Кроме того, на основе сконструированных тематических цепочек предлагаются два новых метода автоматического аннотирования:

• Отбор предложений на основе участников ситуации (по тематическим цепочкам):

s, => max

^ desc weight(tcnm,) ^

£weight (tcnm j)

tcnew jESj, j-1.3

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

max (weight {tcrelnJ)

tcrd _itewe&usler

где tcrei = (tCi, tc2j - пара тематических цепочек; weight(tcrei) - число вхождений пары в одни и те же предложения кластера; /сге;_леи, -новая пара тематических цепочек, не упомянутая в одних и тех же предложениях, уже отобранных в аннотацию.

Оценка качества полученных автоматических аннотаций, а именно, сравнение модификаций методов с интеграцией и без интеграции построенных тематических цепочек является мерой качества самих тематических цепочек. Для проведения оценки были подготовлены 11 новостных кластеров различной тематики (спорт, политика, происшествия), построенных на основе пословной модели. К каждому кластеру профессиональными лингвистами были подготовлены от 2 до 4 ручных аннотаций. Всего оценке подверглись 10 модификаций методов (классические методы аннотирования 4, 5, 9; классические методы с интеграцией тематических цепочек 1, 7, 10; новые методы аннотирования на основе тематических цепочек 2,3, б, 9 с учетом и без учета IDF).

Метод 1 2 L s SU Avg

1. MMR + Groups 0.62499 (1) 0.41633 (1) 0.60210 (1) 0.35529 (1) 0.36649 (1) 1.0

2. OurSummary (Nodes) 0.58652 (2) 0.36154(2) 0.56450 (2) 0.32113(2) 0.33203 (2) 2.0

3. OurSummary (Nodes) with IDF 0.58497(3) 0.33918(4) 0.55745 (3) 0.30124 (3) 0.31283(3) 3.2

4. Classic MMR 0.55917 (4) 0.34539 (3) 0.54012 (4) 0.29428 (4) 0.30519(4) 3.8

5. ThematicLines 0.53416 (5) 0.33364 (5) 0.51238 (5) 0.27130 (5) 0.28243 (5) 5.0

6. OurSummary (Relations) 0.53141 (6) 0.28920 (6) 0.50422 (6) 0.25382 (6) 0.26509 (6) 6.0

7. SumBasic + Groups 0.52255 (7) 0.22881 (9) 0.49300 (8) 0.24356 (7) 0.25525 (7) 7.6

8. SumBasic 0.51847(8) 0.24735 (8) 0.49786 (7) 0.23064 (8) 0.24257 (8) 7.8

9. OurSummary (Relations) with IDF 0.45494 (9) 0.24856(7) 0.43768 (9) 0.19419(10) 0.20492 (10) 9.0

10. MMR with IDF + Groups 0.44475 (10) 0.22238 (10) 0.42318 (10) 0.20627(9) 0.21648 (9) 9.6

Табл. 1: Результаты оценки методом ROUGE

Процедура оценки состояла из двух этапов. Сначала все модификации методов были оценены автоматическими мерами качества официального пакета ROUGE6. В Табл. 1 представлены результаты ROUGE по основным мерам качества (Avg - средняя позиция по всем мерам качеств).

Наиболее значимыми являются следующие результаты:

I. Интеграция построенных тематических цепочек в классические методы автоматического аннотирования MMR и SumBasic улучшает качество исходных методов;

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

Для подтверждения результатов оценки методом ROUGE лучшие и наиболее приоритетные модификации методов были дополнительно оценены методом «Пирамиды»7 (Табл. 2).

6 Lin C.-Y. ROUGE: a Package for Automatic Evaluation of Summaries // Proceedings of ACL'2004, pp. 74-81

7 Harnly A., Nenkova A., Passonneau R., Rambow O. Automation of summary evaluation by the pyramid method // Proceedings of RANLP'2005, Bulgaria, 2005

Метод Score

MMR + Groups 0.645 (1)

OurSummary (Nodes) 0.602 (2)

Classic MMR 0.578 (3)

SumBasic + Groups 0.575 (4)

SumBasic 0.567 (5)

Табл. 2: Результаты оценки методом «Пирамиды» Результаты оценки методом «Пирамиды» подтверждают факты, установленные при оценке методом ROUGE, а именно, улучшение качества методов автоматического аннотирования при интеграции в них построенных тематических цепочек на основе совокупности разнородных факторов.

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

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

• автоматического аннотирования, реализующий более 10 различных методов аннотирования;

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

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

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

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

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

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

Основные публикации автора по теме диссертации

Издания из списка ВАК:

[1] Алексеев А.А. Тематический анализ новостного кластера как основа для автоматического аннотирования // Программная инженерия. - 2014. - № 3. -С. 41-48.

[2] Алексеев А.А., Лукашевич Н.В. Комбинирование признаков для извлечения тематических цепочек в новостном кластере // Труды Института системного программирования РАН. - 2012. - Т. 23. - С. 257-276.

[3] Алексеев А.А., Лукашевич Н.В. Автоматическое извлечение сущностей на основе структуры новостного кластера // Искусственный интеллект и принятие решений. - 2011. - № 4. - С. 51-59.

Издания из списка SCOPUS:

[4] Alekseev A.A., Loukachevitch N.V. Use of Multiple Features for Extracting Topics from News Clusters // Proceedings of the Spring Researchers Colloquium on Databases and Information Systems. - 2012. - P. 3-11.

[5] Alekseev A.A., Loukachevitch N.V. The automatic retrieval of news entities based on the structure of a news cluster // Scientific and Technical Information Processing. - 2012. - Vol. 39, № 6. - P. 303-309.

[6] Alekseev A.A., Loukachevitch N.V. Automatic Entity Detection Based on News Cluster Structure // Proceedings of the International Workshop on Concept Discovery in Unstructured Data. - 2011. - P. 1-10.

Другие публикации:

[7] Алексеев A.A., Мальковский М.Г. Автоматическое аннотирование новостного кластера на основе тематического анализа // Тезисы докладов конференции «Тихоновские чтения». - М.: МГУ, 2013. - С. 55.

[8] Алексеев А.А. Тематическое представление новостного кластера как основа для автоматического аннотирования // Труды всероссийской конференции RCDL. - 2013. - С. 359-369.

Напечатано с готового оригинал-макета

Подписано в печать 07.07.2014 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 159.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.