Тематическое представление новостного кластера как основа для автоматического аннотирования © А.А. Алексеев Московский государственный университет имени М.В. Ломоносова, г. Москва a.a.alekseevv@gmail.com тему новостного кластера, и, значит, повысить каче- Аннотация ство различных операций с новостными кластерами, например, автоматическое аннотирование, опреде- В работе предложен метод извлечения це- ление новизны информации и др. почек семантически близких слов и выра- жений, описывающих различных участни- В данной работе предлагается модель представ- ления содержания новостного кластера, описываю- ков сюжета – тематических узлов. Метод щая основных участников ситуации с учетом вариа- основан на объединении различных факто- тивности их именования – тематическое представ- ров схожести, включающих структурную ление новостного кластера. Мы рассмотрим методы организацию новостных кластеров, анализ контекстов вхождения языковых выраже- улучшения качества извлечения основных участни- ний, а также информацию из предопреде- ков новостного события, что включает нахождение совокупности слов и выражений, с помощью кото- ленных ресурсов. Контексты слов исполь- рых тот или иной значимый участник события име- зуются в качестве базиса для извлечения новался в документах новостного кластера. Метод многословных выражений и построения те- основан на совместном использовании совокупно- матических узлов. Оценка предложенного алгоритма произведена в задаче построения сти факторов, в том числе разного рода контекстов обзорных рефератов новостных кластеров. употребления слов в документах кластера, инфор- мации из предопределенных источников (тезаурус 1 Введение русского языка), а также особенностях построения текстов на естественном языке. Современные технологии автоматической обра- Статья организована следующим образом: после ботки новостных потоков основаны на тематической обзора существующих подходов, приведенного в кластеризации новостных сообщений, т. е. выделе- разделе 2, в разделе 3 обсуждается теоретическая нии совокупностей новостей, посвященных одному основа предлагаемого алгоритма, в частности, мо- и тому же событию – новостных кластеров [17]. дель связанного текста. Подробное описание пред- Кластер документов должен соответствовать лагаемого алгоритма и интеграция результатов ра- ситуации или совокупности связанных ситуаций боты алгоритма в методы автоматического анноти- (основная тема кластера) [2, 17]. В описываемой рования представлены в разделах 4 и 5 соответ- ситуации есть набор участников, которые в исход- ственно. Оценка полученных результатов произве- ном кластере: дена в разделе 6. Все примеры взяты из новостного  могут быть выражены не только словами, но кластера, посвященного смене руководства алмазо- и словосочетаниями, добывающей компании «Алроса», содержащего 12  могут выражаться не одним, а совокупностью новостных документов. различных выражений; так, акции некоторой компании могут выражаться в текстах одного 2 Обзор существующих методов новостного кластера как собственно акции Проблема определения вариативности именова- компании, контрольный пакет акций, кон- ния в текстах является актуальной для различных трольный пакет, акционер компании, владе- задач автоматической обработки естественного язы- лец компании, состав владельцев и др. ка. С формальной точки зрения данная проблема Можно предположить, что качественное выделе- является задачей группирования набора языковых ние участников ситуации, включая различные вари- выражений входной текстовой коллекции на тема- анты их наименования в различных документах кла- тические группы, относящиеся к одинаковым сущ- стера, может помочь лучше определять основную ностям. Существует ряд различных подходов со схожими постановками задач, наиболее близкими из которых являются: Труды 15-й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и  построение лексических цепочек; технологии, электронные коллекции» — RCDL-2013,  построение референциальных цепочек; Ярославль, Россия, 14-17 октября 2013 г. 173  вероятностные тематические модели (в част- дуемой коллекции. При этом подобный статистиче- ности, LDA). ский вывод обычно не учитывает информацию о Лексическая цепочка представляет собой после- существующих лексических отношениях между довательность семантически связанных слов (повто- словами и внутреннем устройстве текстов на есте- ры, синонимы, гипонимы, гиперонимы и др.) и яв- ственном языке. Результаты работы алгоритмов, ляется известным подходом к моделированию связ- основанных на подобных моделях, имеют вероят- ности текста на естественном языке [10, 14, 21]. Ал- ностный результат и трудно интерпретируемы. горитмы построения лексических цепочек основаны на использовании информации о связях между сло- 3 Тематическое представление вами и выражениями, описанных в некотором зара- Как известно, текст обладает такими свойствами, нее определенном ресурсе, например, тезаурусе ан- как глобальная и локальная связности. Глобальная глийского языка WordNet и тезаурусе русского язы- связность текста проявляется в том, что его содер- ка РуТез. жание может быть представлено в виде иерархиче- С целью выделения наиболее значимых для со- ской структуры пропозиций [5]. Самая верхняя про- держания текста лексических цепочек рассматрива- позиция представляет собой основную тему доку- ются различные параметры лексических цепочек, мента, а пропозиции нижних уровней представляют такие, как частотность ее элементов, текстовое по- собой локальные или побочные темы документа. крытие и другие. В лексических цепочках выделя- Локальная связность, т. е. связность между со- ются наиболее частотные элементы цепочки в каче- седними предложениями текста, часто осуществля- стве наиболее важных тематических элементов тек- ется такими средствами, как анафорические отсыл- ста. ки, например, с помощью местоимений, или посред- Использование лексических цепочек является из ством повторения одних и тех же или близких по существующих подходов идейно наиболее близким смыслу слов (лексическая связность). к предлагаемому в данной статье. Основные отли- Пропозиция основной темы документа, т. е. вза- чия предлагаемого подхода заключаются в расши- имоотношения участников основной темы, должна рении рассмотрения с одного документа на коллек- находить свое отражение в конкретных предложе- цию документов, а также в использовании совокуп- ниях текста, которые должны раскрывать и уточнять ности различных факторов для группирования се- взаимоотношения между тематическими элемента- мантически близких слов и выражений (а не только ми. Если текст посвящен обсуждению взаимоотно- информации, описанной в предопределенном ресур- шений между тематическими элементами C1, , Cn, се). то в предложениях текста должны обсуждаться де- Частично проблему разного именования имено- тали этих отношений. Это проявляется в том, что ванных сущностей снимают посредством установ- сами тематические элементы C1, , Cn или их лекси- ления кореференции имен (референциальных це- ческие представители должны встречаться как раз- почек), прежде всего, для людей и организаций ные актанты одних и тех же предикатов в конкрет- (Президент Российской Федерации Дмитрий Мед- ных предложениях текста. ведев, Президент Медведев, Дмитрий Медведев) Исходя из данных идей, для выявления участни- [19]. ков ситуации, описываемой в исходном новостном На конференциях TDT и ACE рассматривалась кластере, мы сделали ряд следующих предположе- задача по извлечению и прослеживанию упомина- ний: ний сущностей по цепочкам кореференции (Entity 1) взаимодействие участников описывается в Detection and Tracking) [6]. Специфика данной зада- предложениях текста, поэтому чем чаще слова (или чи заключается в обнаружении ограниченного набо- выражения) встречаются в одних и тех же предло- ра типов сущностей, существующих в реальном ми- жениях текста, тем больше вероятность того, что эти ре. слова (или выражения) относятся к разным участни- Вероятностные тематические модели, такие, кам ситуации; как Latent Dirichlet Allocation [2, 3, 7], основаны на 2) каждому участнику в тексте соответствует предположении, что документы на естественном группа слов и выражений; предполагается, что в языке являются комбинацией различных тем (топи- тексте имеются наиболее частотное (главное назва- ков), в то время как каждая тема (топик) является ние участника) и разные варианты, поэтому группа вероятностным распределением над словами. В по- слов и выражений, относящихся к одному участни- добных моделях обычно рассматриваются два веро- ку, строится в форме узла, т. е. главное выражение и ятностных распределения: относящиеся к нему выражения – тематический  Темы (Топики) vs Документы (распределение узел; тем (топиков) по документам коллекции); 3) тематическое представление в предлагаемом  Слова vs Темы (Топики) (распределение слов подходе представляет собой совокупность выявлен- по темам (топикам)). ных тематических узлов и отношений между ними Восстановление информации об исходном рас- [9, 14]. пределении тем (топиков) основано на итеративном Данные предположения основаны на внутреннем применении статистических методов (например, устройстве и тематической структуре текстов на Семплинга Гиббса [7]), использующих информацию естественном языке [5, 10]. Более подробная ин- о совместном появлении слов в документах иссле- 174 формация о сделанных предположениях, а также повторяется до тех пор, пока произведена хотя бы описание проведенных экспериментов по проверке одна склейка. сделанных гипотез, представлены в работе [1]. Но- В результате данной процедуры собираются та- востной кластер не является связным текстом, но кие выражения, как президент компании, междуна- посвящен одной ситуации (или совокупности свя- родные экономические отношения, председатель занных ситуаций) и содержит большое количество совета директоров, контрольный пакет акций и документов, что влечет за собой усиление всех ста- т. д. тистических особенностей. 4.3 Характеристики для определения 4 Алгоритм построения тематического семантических связей представления Для определения семантически связанных выра- жений и последующего построения тематических 4.1 Контексты употребления слов узлов используется набор из шести основных харак- Важным фактором для построения тематическо- теристик схожести. Некоторые из данных характе- го представления являются контексты, в которых ристик являются контекстно-зависимыми и вычис- употребляются слова и выражения. Для получения ляются непосредственно на основании рассматрива- контекстов слов предложения разбиваются на фраг- емого новостного кластера, в то время как другие менты между знаками препинания. Выделяются определяются на основании формальной схожести следующие типы контекстов в рамках таких фраг- выражений и информации из заранее определенных ментов: ресурсов. Каждая характеристика добавляет некото- рый балл в общий вес схожести пары выражений,  соседнее прилагательное или существительное независимо от других характеристик схожести. В вправо или влево от исходного слова (Near); следующей секции будет дано подробное описание  во фрагментах, в которых есть глаголы, фикси- алгоритма расчета весов схожести пар выражений. руются прилагательные и существительные, между Контекстно-зависимые характеристики: которыми и исходным словом встречается глагол (AcrossVerb); Количество вхождений в соседние предложения (Neighboring Sentence Feature, NSF). Данная харак-  прилагательные и существительные, встреча- теристика основана на гипотезе глобальной связно- ющиеся во фрагментах предложений с данным сло- сти текстов на естественном языке [5] и её след- вом, не разделенные глаголом и не являющиеся со- ствии о том, что элементы одного тематического седними к исходному слову (NotN). узла чаще появляются в соседних предложениях Кроме того, для всех прилагательных и суще- исходных документов, чем в одних и тех же пред- ствительных запоминаются слова, встречающиеся в ложениях. соседних предложениях (NS). Предложения для вы- Характеристика NSF вычисляется на основе кон- числения этого показателя берутся не полностью, текстных параметров AcrossVerb, Near, NotNear и учитываются фрагменты предложений с начала и до NS и распределения их средних значений внутри фрагмента, содержащего глагол (включительно), что исходного новостного кластера. Характеристика позволяет извлекать из соседних предложений NSF дает численную оценку соотношения количе- наиболее значимые слова. ства вхождений в соседние предложения (характе- ристика NS) по отношению к количеству вхождений 4.2 Сборка многословных выражений в одни и те же предложения исходного корпуса (ха- Важной основой извлечения многословного вы- рактеристики AcrossVerb, Near и NotNear) и основа- ражения из текста документа является частотность на на следующем соотношении: его встречаемости в тексте. Однако кластер пред- C  NS  2  AcrossVerb  Near  NotNear  . (2) ставляет собой структуру, в которой многие цепоч- Общая формула вклада характеристики NSF в вес ки слов повторяются многократно. Поэтому основ- схожести пары выражений имеют следующую фор- ным критерием для выделения многословных выра- му: жений является значительное превышение встреча- емости слов непосредственно рядом друг с другом  C  NSF  Min 0.5 , , (3) по сравнению с раздельной встречаемостью во  Avg(C )  фрагментах предложений [18]: где AVG(C) является средним значением C среди Near > 2 * (AcrossVerb + NotN). (1) всех положительных значений в рамках всего кла- Кроме того, используются ограничения по ча- стера. стотности встречаемости слов рядом друг с другом. NSF также является управляющей характеристи- Просмотр подходящих пар слов (выражений) для кой. Это означает, что два выражения не могут быть склейки производится в порядке снижения коэффи- включены в один и тот же тематический узел, если циента Near / (AcrossVerb + NotN). При нахождении значение характеристики NSF имеет отрицательное подходящей пары слов они склеиваются в единый значение. Подобная пара с отрицательным значени- объект, и все контекстные отношения пересчитыва- ем NSF не имеет общего веса и не рассматривается ются. Процедура просмотра начинается заново и алгоритмом построения тематических узлов. Стоит 175 отметить, что подобная характеристика не исполь- Руководитель – Руководство, Президент России – зовалась раньше для подобных задач, таких, как Российский президент и т. д. определение вариантов именования основных Общий вес характеристики BS имеет веществен- участников ситуации, построение рядов квазисино- ное значение из отрезка [0,1] и вычисляется по сле- нимов, а также лексических цепочек. дующей формуле (в случае, если есть слова с одина- Строгие контексты (Strict Context, SC). Данная ковыми началами, иначе вес равен нулю): характеристика основана на сравнении строгих кон- BS  1.0  0.1 * N diff , текстов употреблений слов – текстовых шаблонов. В где Ndiff – число слов с различными началами. качестве шаблонов рассматриваются 4-граммы: по Информация о схожести, описанная во внешнем два слова справа и слева от рассматриваемого вы- ресурсе – тезаурусе РуТез (Thesaurus Similarity, TS). ражения. Чем больше одинаковых шаблонов разде- На текущий момент существует большое количе- ляет пара-кандидат, тем больше схожесть по данной ство разнообразных предопределенных ресурсов, характеристике. Контексты с недостающей инфор- которые содержат в себе дополнительную информа- мацией (или неполные 4-граммы контекстов, в цию о связях слов и выражений. Данная информа- начале и конце предложений) получают меньший ция может быть использована для построения тема- вес, чем целые шаблоны. тических узлов и сделать данное построение более Вес шаблона строгого контекста рассчитывается стабильным и качественным. Более того, известно, следующим образом: каждое слово n-граммы шаб- что некоторые типы отношений между словами и лона контекста имеет вес, равный 0.25. Например, n- выражениями широко используются для обеспече- грамма (*, *, состоит, из) будет иметь вес 0.5, а n- ния связности реальных текстов (например, такие грамма (новостной, кластер, состоит, из) будет отношения, как синонимия). Вычисление характе- иметь вес, равный 1.0, что является максимальным ристики TS основано на использовании информации весом полного шаблона n-граммы. из тезауруса русского языка РуТез [13]. При этом в Значение характеристики SC имеет веществен- рассмотрение попадали как непосредственные связи ное значение, принадлежащее отрезку [0,1]. Вес ха- объектов, так и «длинные» связи по транзитивным рактеристики вычисляется относительно веса пары с типам отношений. Рассматриваются следующие максимальным значением разделяемых строгих кон- типы связей: синонимия, часть – целое, род – вид. текстов, пропорционально весу разделяемых стро- Значение характеристики TS имеет веществен- гих контекстов для текущей пары. ное значение от 0 до 1 и вычисляется обратно- Схожесть контекстов употребления по внут- пропорционально расстоянию между объектами в ренним характеристикам предложения (Scalar тезаурусе: Product Similarity, SPS). Каждый из контекстных параметров, описанных в разделе 4.1, представляет TS  1.0  0.2 * N rel , собой вектор частот, сопоставленных с каждым сло- где Nrel – длина пути по отношениям тезауруса (ко- вом или выражением. Размерности данного вектора личество связей). отражают частоту совместной встречаемости рас- Наличие одинаковых языковых выражений (Em- сматриваемого слова или выражения со всеми bedded Objects Similarity, EOS). При анализе схоже- остальными словами и выражениями, упомянутыми сти комплексных тематических узлов, включающих в новостном кластере. После построения данных несколько языковых выражений, важным фактором контекстных векторов они могут быть сопоставлены схожести является наличие общих языковых выра- классическими метриками схожести, например, та- жений у двух различных узлов. Данный фактор осо- кой, как косинусная мера угла между векторами. бенно важен на поздних итерациях работы алгорит- Характеристика SPS может быть рассмотрена как ма, когда имеется значительное количество сформи- более сглаженная и гибкая характеристика по отно- рованных тематических узлов и остальные характе- шению к характеристике SC, так как обе данных ристики схожести уже проработаны. Значение дан- характеристики основаны на контекстах употребле- ной характеристики является булевым и может до- ния слов и выражений. бавлять 1 балл в общий вес схожести пары в случае Значение характеристики SPS имеет веществен- наличия одинаковых языковых выражений. ное значение, лежащее в пределах от 0 до 0.5 (поло- Общий вес схожести пары рассматриваемых винный вес характеристики), и вычисляется как ко- объектов вычисляется как сумма весов по отдель- синусная мера схожести по всем контекстным ха- ным характеристикам схожести, описанным выше. рактеристикам (AcrossVerb, Near и NotNear), огра- Таким образом, каждая пара получает вес, лежащий ниченная сверху значением 0.5. в пределах от 0 (отсутствие схожести) до 5 (макси- Контекстно-независимые характеристики: мальная схожесть), получаемый на основе шести характеристик (3 контекстно-зависимых и 3 кон- Формальное сходство (Beginning Similarity, BS). текстно-независимых), лежащих в пределах от 0 до Рассмотрение формального сходства выражений 1 (SC, BS, TS, EOS) и от 0 до 0.5 (NSF, SPS). Пример является естественным путем обнаружения семан- ранжирования пар в соответствии с описанным ал- тически связанных объектов. На текущий момент горитмом приведен в Таблица 1 (топ-5 пар по обще- используется простая метрика схожести – одинако- му весу на первой итерации работы алгоритма, ха- вые начала слов. Данная характеристика позволяет рактеристика EOS равна нулю для всех пар на пер- находить сходство между такими выражениями, как вой итерации). 176 Context- SC В целом каждая итерация алгоритма состоит из Features Context-dependent Pairs independent OR трех основных шагов: BS TS NSF SC SPS E 1. ранжирование пар-кандидатов; Президент России – Пре- 0.90 1.00 0.00 0.50 0.34 2.74 2. выбор пары для объединения (наибольший зидент РФ вес + удовлетворение ограничений); 3. процедура объединения. Инвестгруппа– Инвестицион- 0.90 1.00 0.20 0.00 0.32 2.42 Итеративный процесс продолжается до тех пор, ная группа пока есть пары-кандидаты для объединения с весом схожести выше заданного порога. Например, тема- ГМК Нориль- тический узел с центральным элементом Пост про- ский никель – Норильский 1.00 1.00 0.20 0.00 0.11 2.31 ходит следующие этапы в процессе построения (по- никель казаны пары с максимальным весом схожести на разных итерациях; более частотный элемент пары Российская Федерация – 0.90 1.00 0.00 0.00 0.25 2.15 является первым элементом): Россия Итерация 7: (Отставка)  (Отставка с должности) Отставка – Отставка с 0.90 1.00 0.20 0.00 0.00 2.10 Итерация 33: (Отставка, Отставка с должно- должности сти)  (Уход в отставку) Таблица 1: Пример ранжирования пар-кандидатов Итерация 44: (Отставка, Отставка с должно- сти, Уход в отставку)  (Отставка президен- 4.4 Алгоритм построение тематического та) представления на основе совокупности факторов Итерация 61: (Уход с поста)  (Уход в от- ставку) Алгоритм построения тематического представ- ления конструирует тематические узлы из пар вы- Итерация 62: (Отставка, Отставка с должно- ражений в порядке убывания их схожести. Предла- сти, Уход в отставку, Отставка президента) гаемая структура тематического узла обладает сле-  (Уход с поста, Уход в отставку) дующими свойствами: Итерация 102: (Отставка, Отставка с долж-  текстовое выражение может принадлежать к ности, Уход в отставку, Отставка президента, одному или двум тематическим узлам; разрешение Уход с поста)  (Пост) множественной принадлежности обеспечивает воз- Итерация 103: (Пост, Отставка, Отставка с можность представления различных аспектов ис- должности, Уход в отставку, Отставка прези- ходного текстового выражения, а также его лекси- дента, Уход с поста)  (Должность) ческой многозначности; Итерация 104: (Пост, Отставка, Отставка с  каждый тематический узел имеет главный эле- должности, Уход в отставку, Отставка прези- мент – центр тематического узла, который может дента, Уход с поста, Должность)  (Уход) принадлежать только к одному тематическому узлу; Следующие тематические узлы были получены в центр тематического узла является наиболее частот- результате работы описанного алгоритма для кла- ным элементом среди всех элементов тематического стера примера. Представлены 5 наиболее частотных узла. тематических узлов в порядке убывания частоты. Построение тематического представления состо- Данные узлы не подвергались какой-либо постобра- ит из следующих шагов: ботке, центры тематических узлов выделены жир-  рассматривается пара текстовых выражений с ным шрифтом: наибольшим весом схожести среди всех пар- кандидатов; Пост: уход с поста; должность; уход; отстав-  более частотный элемент пары поглощает ме- ка; отставка с должности; уход в отставку; нее частотный элемент вместе со всеми его тексто- отставка президента выми вхождениями и контекстными характеристи- Алроса: президент Алроса; АК Алроса ками и становится представителем данной пары тек- Компания: акция компании; владелец компании; стовых выражений – центром нового тематического объединение компаний; акция; акционер компа- узла; нии; владелец; пакет акций; состав владельцев;  менее частотный элемент рассматриваемой па- контрольный пакет акций; контрольный пакет; ры может в дальнейшем аналогичным образом при- владение соединиться к другому тематическому узлу;  объединение тематических узлов, состоящих Ничипорук: Александр Ничипорук из нескольких элементов, происходит аналогично Якутия: президент Якутии; якутский; якут- объединению одиночных текстовых выражений; ский президент центр более частотного тематического узла стано- вится центром нового, объединенного тематическо- го узла. 177 5 Порождение аннотаций на основе стве метрик Sim1 и Sim2 использовалась косинусная тематического представления мера угла между векторами. Тематическое представление содержит в себе 5.2 Метод SumBasic дополнительную информацию о внутреннем SumBasic – алгоритм для общего многодоку- устройстве исходного новостного кластера, которая ментного аннотирования [14, 15]. В его основе ле- может быть использована для улучшения автомати- жит эмпирическое наблюдение о том, что более ча- ческих операций над текстовыми данными. Одной стотные слова рассматриваемого кластера докумен- из таких задач является задача автоматического ан- тов с большей вероятностью попадают в экспертные нотирования, т. е. подготовки краткого изложения аннотации, нежели слова с низкой частотностью. содержания исходного документа(ов). Решение дан- Алгоритм SumBasic строится на базе частотного ной задачи в значительной степени связано с нали- распределения слов в исходном документе и состоит чием информации о различном именовании одних и из пяти шагов. На первом шаге происходит расчет тех же участников ситуации, описанной во входных вероятностей слов исходного кластера p(wi): документах, так как практически невозможно по- p(wi ) = n/N, строить полную и не избыточную аннотацию без учета вариативности упоминаний наиболее значи- где n – число появлений слова wi в исходной кол- мых сущностей. В данном разделе описаны как су- лекции, N – общее число слов в данной коллекции. ществующие известные методы аннотирования Каждому предложению Sj на втором шаге назнача- (MMR, SumBasic), так и новые подходы, основан- ется вес, равный средней вероятности слов в данном ные на тематическом представлении. Все представ- предложении: p( wi ) ленные подходы используются для оценки качества weight ( S j )   wi  S j |  wi | wi  S j  | . построенного тематического представления путем его интеграции в исходную структуру данных алго- На третьем шаге предложение с наибольшим весом ритмов аннотирования. отбирается в итоговую аннотацию. После этого на шаге 4 происходит пересчет вероятностей всех слов, 5.1 Метод Maximal Marginal Relevance (MMR) входящих в отобранное предложение, по следую- Метод Maximal Marginal Relevance для задачи щей формуле: многодокументного аннотирования является клас- p new (w i ) = p old (w i )  p old (w i ) . сическим не порождающим (выбирающим для ан- На пятом шаге проверяется общая длина получив- нотации целые предложения из исходных докумен- шейся аннотации, и если она не превосходит задан- тов) методом аннотирования, который основан на ного порога, то происходит переход к шагу 2. концепции Maximal Marginal Relevance для инфор- мационного поиска [4]. В оригинале данный алго- 5.3 Аннотирование на основе тематического ритм является запрос-ориентированным, но суще- представления РуТез ствует также вариант и для общего аннотирования, когда в качестве запроса для аннотирования высту- В работе [20] предложен метод аннотирования на пает исходных корпус документов. основе тематического представления, построенного Критерий MMR заключается в том, что лучшее на базе тезауруса русского языка РуТез. Одной из предложение для аннотации должно быть макси- ключевых задач данного алгоритма является обес- мально релевантным исходному набору документов печение одинаково высокого качества как полноты и максимально отличным от всех предложений, уже изложения информации, представленной в автома- отобранных в итоговую аннотацию. тической аннотации, так и её связности. Аннотация строится итеративно на основании Алгоритм аннотирования на основе тематическо- списка ранжированных предложений. Предложение го представления на базе РуТез является итератив- с максимальным значением MMR выбирается на ным, на каждой итерации отбирается по одному каждой итерации алгоритма: предложению. Поставленные цели по комбинации   полноты и связности конечной аннотации решаются MMR  arg max   Sim1 s, Q   1     max Sim 2 s, s j  за счет наложения ограничений на этапе отбора sS  s j E  предложений, а именно: где S – множество предложений-кандидатов в анно-  для обеспечения полноты изложения инфор- тацию, E – множество отобранных в аннотацию; λ – мации предложение-кандидат должно содержать представляет собой интерполяционный коэффици- новый (ещё не упомянутый в отобранных предло- ент между релевантностью отбираемых предложе- жениях) тематический узел; ний и их не избыточностью; Sim1 – метрика схоже-  для обеспечения связности предложение- сти между предложением и запросом для аннотиро- кандидат должно содержать уже упомянутый в ото- вания (например, косинусная мера угла между век- бранных предложениях тематический узел. торами, широко применяемая в информационном Из всех предложений, удовлетворяющих данным поиске); Sim2 может быть такой же, как Sim1 , или условиям, отбирается предложение с наибольшим другой метрикой схожести. В нашей работе в каче- весом тематических узлов – отражение основной темы исходного новостного кластера. 178 Алгоритм аннотирования на основе тематическо- каждой итерации отбирается предложение, содер- го представления на базе РуТез интересен нам в жащее наиболее обсуждаемую и неупомянутую в контексте его основы – тематического представле- отобранных предложениях пару, а также обладаю- ния. Оно имеет схожую структуру с тематическим щее наибольшим общим весом тематических узлов: представлением, описанным в данной работе. При   этом оно построено с использованием только одной характеристики – информации о наличии связей в s i  max   weight (ТУ _ REL _ NEW j )  .  ТУ _ REL _ NEW s   j i  тезаурусе РуТез. В данной работе добавлен ряд но- Итеративный процесс отбора предложений для вых факторов, которые призваны обогатить полу- аннотации в обоих алгоритмах продолжается до тех ченное тематическое представление, а также повы- пор, пока не будет превышен заданный порог по сить его качество. количеству слов. Во всех генерируемых аннотациях данный порог равен 100 словам – стандартный раз- 5.4 Собственные методы аннотирования на мер аннотации для подобных задач на соревновани- основе тематического представления ях мирового уровня (DUC, TAC). Документы новостного кластера содержат в себе описание некоторого события (ситуации) или ряда 6 Оценка качества аннотаций связанных событий (ситуаций). Основная цель ав- томатического аннотирования заключается в наибо- 6.1 Методы оценки автоматических аннотаций лее полном отражении значимых фактов, относя- ROUGE и Пирамид щихся к данному событию (ситуации) и описанных в исходной коллекции документов. Событие (ситуа- Оценка качества порождаемых аннотаций явля- ция), в свою очередь, характеризуется набором её ется достаточно сложной процедурой. Несомненно, участников. Под «фактом» в данном случае пони- наиболее правдоподобные оценки можно получить маются описание взаимоотношений между некото- при помощи ручной оценки путём привлечения рыми участниками события (ситуации) или же дета- большого количества экспертов. Но данный метод лизация описания отдельного её участника. является очень дорогим и трудоёмким. Поэтому Тематический узел предлагаемого тематического используются автоматические методы оценки каче- представления является воплощением некоторого ства аннотаций ROUGE [12] и формализованный участника события (ситуации) и в идеале должен метод Пирамид. содержать всевозможные варианты именования Метод ROUGE основан на автоматическом срав- данного участника в рамках исходного новостного нении порожденной аннотации с эталонными анно- кластера. Таким образом, в основе предлагаемых тациями, созданными экспертами. Существуют раз- методов аннотирования лежит учет наиболее значи- личные модификации алгоритма, связанные с раз- мых взаимоотношений тематических узлов постро- личными способами сравнения: сравнение n-грамм енного тематического представления – учет взаимо- (ROUGE-N); сравнение максимальных общих по- отношений основных участников события (ситуа- следовательностей (ROUGE-L и ROUGE-W); срав- ции). Предлагается два итеративных метода анноти- нение пропусков монограмм и биграмм (ROUGE-S и рования, отличающихся стратегией учета значимо- ROUGE-SU). В статье [12] показано, что все основ- сти отношений между тематическими узлами. На ные ROUGE-метрики являются значимыми, так как каждой итерации в обоих подходах отбирается по в зависимости от специфики конкретной задачи одному предложению. каждая из метрик может иметь наилучшую корреля- В качестве основы для расчета значимости от- цию с ручными аннотациями. ношений между тематическими узлами в первом В основе метода Пирамид также лежит сравне- алгоритме (OurSummary_Nodes) выступает значи- ние автоматических аннотаций с эталонными анно- мость самих тематических узлов. Каждый тематиче- тациями. Но в отличие от метода ROUGE данное ский узел имеет вес, равный суммарной частоте его сравнение происходит не в автоматическом режиме, элементов. На каждой итерации в итоговую аннота- а в ручном, на основании формализованного алго- цию отбирается предложение, содержащее три ритма сравнения. Эксперты выделяют из эталонных наиболее значимых и ещё не упомянутых тематиче- аннотаций все «информационные единицы» (Sum- ских узла (ТУ_NEW): mary Content Units, SCU) – факты, описанные в ан- нотации. Каждая информационная единица получа-  desc weight(ТУ _ NEW j )  si  max   weight (ТУ _ NEW j )  .  ТУ _ NEW s , i 1..3  ет вес пропорционально количеству упоминаний в экспертных аннотациях. Далее полученные инфор-  j i  мационные единицы вручную ищутся в автоматиче- В рамках второго предлагаемого алгоритма ан- ских аннотациях. Итоговая оценка аннотации равна нотирования (OurSummary_Relations) критерием для общему весу упомянутых информационных единиц отбора предложения выступает наличие наиболее по отношению к суммарному весу информационных обсуждаемой и ещё не упомянутой пары тематиче- единиц, извлеченных для данного новостного кла- ских узлов. Для каждой пары тематических узлов стера. предварительно рассчитывается количество вхож- В данной работе оценка качества аннотаций по- дений в одни и те же предложения исходного но- строена на оценке методом ROUGE и дополнитель- востного кластера – «обсуждаемость» пары. На ной оценке методом Пирамид. 179 6.2 Автоматические аннотации и их оценка  SumBasic с добавлением информации из по- строенного тематического представления Для оценки качества автоматических аннотаций (SumBasic+Groups); были подготовлены 11 новостных кластеров по раз-  аннотирование на основе тематического пред- личным тематикам, собранные на основе пословной ставления на базе тезауруса РуТез (ThematicLines); модели представления данных [17]. Независимые  собственный алгоритм аннотирования на осно- эксперты-лингвисты подготовили от 2 до 4 ручных ве построенного тематического представления, по аннотаций для каждого из данных кластеров. Все тематическим узлам (модификации с и без учета автоматические аннотации прошли единообразную IDF, OurSummary_Nodes_WithIDF и обработку для автоматической оценки программ- OurSummary_Nodes соответственно); ным пакетом ROUGE [12]:  собственный алгоритм аннотирования на осно-  ограничение аннотаций длиной свыше 100 ве построенного тематического представления, по слов (рассмотрение только первых 100 слов); связям тематических узлов (модификации с и без  приведение слов к соответствующим леммам; учета IDF, OurSummary_Relations_WithIDF и  исключение стоп-слов и незначащих частей OurSummary_Relations соответственно) речи;  транслитерация всех русскоязычных слов (па- 6.3 Результаты кет ROUGE работает только с латинскими символа- В результате работы программного пакета ми); ROUGE каждая автоматическая аннотация получает  преобразование автоматических аннотаций в набор результатов по различным метрикам сопо- необходимый для пакета ROUGE входной формат ставления автоматических аннотаций с аннотация- (см. документацию пакета). ми, составленными экспертами. По причине значи- Всего в оценке участвовали 11 различных моди- мости различных ROUGE-метрик для задач с раз- фикаций алгоритмов: личной спецификой (см. раздел 6.1) в качестве ос-  классический пословный MMR в модификаци- новного параметра для сравнения автоматических ях с учетом и без учета IDF (MMR_WithIDF и аннотаций была взята средняя позиция в результа- MMR_WithoutIDF соответственно); тах по всем основным ROUGE-метрикам.  MMR с добавлением информации из постро- енного тематического представления (модификации с и без учета IDF, MMR_WithIDF+Groups и MMR+Groups соответственно);  классический пословный SumBasic; Метод ROUGE-1 ROUGE-2 ROUGE-L ROUGE-S ROUGE-SU Avg MMR + Groups 0,62499 (1) 0,41633 (1) 0,6021 (1) 0,35529 (1) 0,36649 (1) 1,0 OurSummary_Nodes 0,58652 (2) 0,36154 (3) 0,5645 (2) 0,32113 (2) 0,33203 (2) 2,2 OurSummary_Nodes_WithIDF 0,58497 (3) 0,33918 (5) 0,55745 (3) 0,30124 (3) 0,31283 (3) 3,4 MMR_WithIDF 0,57623 (4) 0,38116 (2) 0,55503 (4) 0,29792 (4) 0,30971 (4) 3,6 MMR_WithoutIDF 0,56784 (5) 0,34595 (4) 0,55124 (5) 0,26092 (6) 0,27349 (6) 5,2 ThematicLines 0,53416 (6) 0,33364 (6) 0,51238 (6) 0,2713 (5) 0,28243 (5) 5,6 OurSummary_Relations 0,53141 (7) 0,2892 (7) 0,50422 (7) 0,25382 (7) 0,26509 (7) 7,0 SumBasic + Groups 0,52255 (8) 0,22881 (10) 0,493 (9) 0,24356 (8) 0,25525 (8) 8,6 SumBasic 0,51847 (9) 0,24735 (9) 0,49786 (8) 0,23064 (9) 0,24257 (9) 8,8 OurSummary_Relations_WithIDF 0,45494 (10) 0,24856 (8) 0,43768 (10) 0,19419 (11) 0,20492 (11) 10,0 MMR_WithIDF + Groups 0,44475 (11) 0,22238 (11) 0,42318 (11) 0,20627 (10) 0,21648 (10) 10,6 Таблица 2: Результаты оценки автоматических аннотаций методом ROUGE В Таблица 2 приведены итоговые результаты Метод Оценка по Пирамидам оценки всех исследуемых модификаций алгоритмов MMR + Groups 0,645 (1) по всем основным ROUGE-метрикам, а также агре- гирующая оценка, по которой выполнена сортиров- MMR_WithIDF 0,617 (2) ка. OurSummary_Nodes 0,602 (3) Для проведения дополнительной оценки каче- SumBasic + Groups 0,575 (4) ства автоматических аннотаций лучших и наиболее значимых для нас методов (с и без интеграции по- SumBasic 0,567 (5) строенного тематического представления) была Таблица 3: Результаты оценки методом Пирамид проведена альтернативная оценка полученных анно- На основе результатов оценки полученных анно- таций методом Пирамид [8]. Результаты данной таций методами ROUGE и Пирамид необходимо оценки представлены в Таблице 3. отметить, что: 180  наилучший результат показал метод аннотиро- [5] Dijk van T. Semantic Discourse Analysis // вания, основанный на построенном тематическом Handbook of Discourse Analysis / Teun A. van представлении; Dijk, (Ed.), vol. 2. London: Academic Press, 1985.  добавление тематических узлов к обоим базо- pp. 103-136. вым методам улучшило результаты исходных мето- [6] Doddington G., Mitchell A., Przybocki M., дов; Ramshaw L., Strassel S., Weishedel R. The  предлагаемое тематическое представление по- Automatic Content Extraction (ACE): Task, Data, казало более высокий результат в аннотировании, Evaluation // Proceedings of Fourth International чем тематическое представление только на основе Conference on Language Resources and тезауруса. Evaluation, 2004. [7] Griffiths T., Steyvers M. Finding scientific topics 7 Заключение // Proceedings of the National Academy of Sciences of the United States of America, Vol. В статье предложен алгоритм выявления семан- 101, No. Suppl. 1, 2004. pp. 5228-5235. тически связанных слов и выражений, описываю- [8] Harnly A., Nenkova A., Passonneau R., Ram-bow щих различных участников ситуации новостного O. Automation of summary evaluation by the кластера – тематических узлов. Предложенный ал- pyramid method // Proceedings of the International горитм основан на совместном использовании ха- Conference on Recent Advances in Natural рактеристик схожести различной природы. В до- Language Processing, 2005. полнение к известным контекстным характеристи- [9] Hasan R. Coherence and Cohesive harmony // кам схожести, таким, как анализ жестких контекстов (шаблонов) употребления слов и выражений, ис- Understanding reading comprehension / J. Flood, пользуется характеристика, основанная на внутрен- editor, Newark, 1984. pp. 181-219. нем устройстве текстов на естественном языке – [10] Hirst G., St-Onge D. Lexical Chains as анализ встречаемости в соседних предложениях representation of context for the detection and кластера по отношению к встречаемости в одних и correction malapropisms // WordNet: An тех же предложениях. В едином алгоритме объеди- electronic lexical database and some of its нены характеристики следующих различных типов: applications / C. Fellbaum, editor. Cambrige, MA: The MIT Press, 1998.  формальное сходство слов и выражений; [11] Li J., Sun L., Kit C., Webster J. A Query-Focused  информация из предопределенных ресурсов Multi-Document Summarizer Based on Lexical (тезаурус русского языка РуТез [13]); Chains // Proceedings of the Document  контекстные характеристики схожести. Understanding Conference, 2007. Оценка предложенного алгоритма производилась [12] Lin C.-Y. ROUGE: a package for automatic в контексте применения полученного тематического evaluation of summaries // Proceedings of the представления к задаче автоматического аннотиро- Workshop on Text Summarization Branches Out вания. Полученные результаты подтверждают, что (ACL’2004), Barcelona, Spain, 2004. pp. 74-81. информация, заложенная в построенных тематиче- [13] Loukachevitch N., Dobrov B. Evaluation of ских узлах, позволяет улучшать качество алгорит- Thesaurus on Sociopolitical Life as Information мов много документного аннотирования. Retrieval Tool // Proceedings of Third International Conference on Language Resources Литература and Evaluation, Vol.1, 2002. pp. 115-121. [1] Alekseev A., Loukachevitch N. Use of Multiple [14] Loukachevitch N. Multigraph representation for Features for Extracting Topics from News lexical chaining // Proceedings of SENSE Clusters // Труды конференции workshop, 2009. pp. 67-76. SYRCODIS’2012, 2012. pp. 3-11. [15] Nenkova A., Vanderwende L. The impact of [2] Allan J. Introduction to Topic Detection and frequency on summarization // Microsoft Research Tracking // Topic detection and tracking, Kluwer Technical Report, MSR-TR-2005-101, 2005. Academic Publishers Norwell, MA, USA, 2002. [16] Vanderwende L., Suzuki H., Brockett C., Nenkova pp. 1-16. A. Beyond SumBasic: Task-focused [3] Blei D., Ng A., Jordan M. Latent Dirichlet summarization with sentence simplification and Allocation // Journal of Machine Learning lexical expansion // Information Processing and Research, 3, 2003. pp. 993-1022. Management Journal, Volume 43 Issue 6, [4] Carbonell J., Goldstein J. The use of MMR, diver- November, 2007. pp. 1606-1618. sity-based reranking for reordering documents [17] Добров Б.В., Павлов А.М. Исследование and producing summaries // Proceedings of the качества базовых методов кластеризации 21st Annual International ACM SIGIR новостного потока в суточном временном Conference on Research and Development in окне // Труды конференции RCDL’2010, 2010. Information Retrieval, Melbourne, Australia, [18] Добров Б.В., Лукашевич Н.В., Сыромятни- 1998. pp. 335-336. ков С.В. Формирование базы терминологических словосочетаний по 181 текстам предметной области // Труды пятой большого лингвистического ресурса // всероссийской научной конференции Компьютерная лингвистика и «Электронные библиотеки: Перспективные интеллектуальные технологии: труды методы и технологии, электронные Международной конференции Диалог’2000, коллекции», 2003. с. 201-210. 2000. c. 252-258. [19] Ермаков А.Е. Референция обозначений персон и организаций в русскоязычных текстах СМИ: Thematic representation of a news cluster эмпирические закономерности для as a basis for summarization компьютерного анализа // Компьютерная лингвистика и интеллектуальные технологии: Aleksey A. Alekseev труды Международной конференции In this paper we consider a method for extraction of Диалог’2005, 2005. various references of a concept or a named entity men- [20] Лукашевич Н.В., Добров Б.В. Автоматическое tioned in a news cluster. The method is based on the аннотирование новостного кластера на основе structural organization of news clusters and exploits тематического представления // comparison of various word contexts. The word con- Компьютерная лингвистика и texts are used as a basis for multiword expression ex- интеллектуальные технологии: труды traction and main entity detection. At the end of cluster Международной конференции Диалог’2009, processing we obtain groups of thematically-related Вып. 8 (15), 2009. c. 299-305. elements, in which the main element of a group is de- [21] Лукашевич Н.В., Добров Б.В. Исследование termined. Evaluation of the proposed algorithm is per- тематической структуры текста на основе formed in news cluster summarization task. 182