3 Исследование и построение решения задачи
3.1 Обзор модифицируемой системы
Рисунок иллюстрирует общую схему работы модифицируемой системы.
Рисунок . Общая схема работы системы автоматического реферирования ИСП РАН
В процессе построения риторического дерева текста система сначала осуществляет объединение элементарных сегментов в рамках предложений. Затем из RST-деревьев предложений строятся риторические деревья абзацев текста. Наконец, над набором RST-деревьев абзацев формируется единая риторическая структура всего текста.
Первый этап проводится непосредственно при определении границ клауз, выступающих в роли элементарных сегментов, и основывается на синтаксическом подчинении: отношение между ядром и спутником соответствует отношению между синтаксически главной и зависимой клаузами. Каждый этап, кроме первого, представляет собой последовательное применение к набору риторических сегментов эвристик-коннекторов. Такие эвристики строят набор объемлющих риторических структур над входным набором RST-деревьев путем объединения некоторых из них. В архитектуре системы коннекторы представлены классами, реализующими интерфейс IRSTreesConnector:
Рисунок . Архитектура подсистемы, ответственной за объединение риторических деревьев
Как видно из диаграммы на Рисунок , IRSTreesConnector оперирует списками экземпляров класса AbstractRSNode. Данный класс – представление узла риторического дерева, будь то элементарный сегмент (клауза, Clause) или же риторическое отношение (RSRelation): симметричное (ParatacticRelation) или асимметричное (HypotacticRelation). Рисунок . Модель данных модифицируемой системы иллюстрирует описанную иерархию.
Рисунок . Модель данных модифицируемой системы
Система использует три эвристики для объединения RST-деревьев (см. Рисунок ): CoreferencesConnector, LinkingWordsConnector и WeighByKeywordsConnector. Первая основана на поиске кореферентных – ссылающихся на один и тот же объект или явление – слов в объединяемых сегментах. LinkingWordsConnector с помощью эмпирического словаря ищет вхождения фраз и выражений, сигнализирующих наличие определенных риторических отношений. Наконец, WeighByKeywordsConnector использует информацию о содержании в сегментах ключевых слов, т.е. слов, в совокупности наиболее полно отражающих суть текста. Последняя эвристика используется для вывода отношений между абзацами, первые две – между предложениями в рамках абзацев.
Для того, чтобы с помощью заданного набора эвристик-коннекторов вывести ровно одно RST-дерево над входным набором, используется метод linkRSTrees класса RSTreesLinker. При этом сначала вызывается операция connectRSTrees, реализация которой в классе RSTreesLinker последовательно применяет ко входному набору RST-деревьев все коннекторы, ассоциированные с данным экземпляром класса. Если в результате остается два и более RST-деревьев, они объединяются с помощью паратактической связи (метод drawTreesInOne класса AbstractRSTreesLinker).
Исходя из особенностей архитектуры системы, для решения поставленной задачи разумно построить механизм объединения RST-деревьев на основе машинного обучения в виде класса, реализующего интерфейс IRSTreesConnector.
3.2 Выбор схемы построения RST-дерева
В качестве схемы построения RST-дерева было решено использовать жадный иерархический алгоритм аналогично системе duVerle и Predinger. Данный алгоритм прост в реализации и при этом имеет ряд преимуществ по сравнению с shift-reduce подходом Marcu и схемами поиска наиболее вероятного разбора, представленными в работах Marcu, Corston-Oliver и LeThanh.
К недостаткам подхода Marcu, основанного на обкатанной для синтаксических анализаторов схеме сдвиг-свертка, можно отнести его локальность: для принятия решения о следующем действии алгоритм просматривает три дерева в стеке и один сегмент на входе. Проводя аналогию с синтаксическим анализом, можно вспомнить, что применимость разбора с предпросмотром в один символ сужает класс используемых языков (грамматик). Перенос соответствующих требований на риторическую структуру не очевиден. В частности, при просмотре вперед только одного сегмента можно потерять информацию о содержащем его абзаце. Более корректный подход требовал бы предпросмотра всех оставшихся сегментов, что для данного алгоритма накладно. В свою очередь, иерархический подход duVerle, несмотря на свою простоту, на каждом шаге использует информацию о возможностях проведения отношений для каждого текущего сегмента.
Конечно, RST-дерево, построенное жадным алгоритмом, может не являться наиболее вероятной риторической структурой текста. Использование одного из алгоритмов поиска наиболее вероятной риторической структуры могло бы решить эту проблему, однако, судя по результатам обзора, временные потери при этом значительно перекрывают выигрыш в качестве.
Как и duVerle и Predinger, мы будем использовать два классификатора: один для возможности какого-либо отношения и один для его конкретизации. При этом, учитывая специфику поставленной задачи, второй классификатор ограничится исключительно распределением ядер и спутников, т.е. для данной пары сегментов будет выбирать из трех возможных отношений: ядро-спутник (nucleus-satellite, NS), спутник-ядро (SN) или ядро-ядро (NN).
При этом, в отличие от подхода duVerle и Predinger, мы будем более строго учитывать авторскую организацию текста, последовательно применяя описанный выше алгоритм сначала в рамках отдельных предложений, затем в рамках абзацев и, наконец, на уровне всего текста. Похожий подход использовал, хоть и эвристически, LeThanh. DuVerle и Predinger использовали для учета текстовой организации дополнительный набор признаков, утверждая, что предложения и особенно абзацы часто могут быть разнесены по различным RST-поддеревьям в риторическом представлении текста. Данное утверждение представляется нам весьма спорным, тем более при учете того, что наиболее весомым признаком в структурном классификаторе duVerle оказалась именно принадлежность сегментов к одному предложению (см. [29]).
3.3 Выбор механизмов классификации
Оба классификатора было решено реализовывать на основе машин опорных векторов. Исследования Reitter и duVerle показали хорошую применимость SVM к задаче классификации риторических отношений. Возможность использования SVM для определения вероятностей принадлежности объекта к классу согласуется с предполагаемым алгоритмом построения RST-дерева. В соответствии с ограничениями по времени построения RST-деревьев мы будем использовать линейные SVM-классификаторы. В работе [2946] показано, что точность линейных классификаторов в данной задаче незначительно уступает классификаторам с полиномиальным ядром, обеспечивая при этом существенный выигрыш по времени.
3.4 Признаки
3.4.1 Длины сегментов.
Как отмечалось у Reitter и duVerle, можно предполагать корреляцию между длинами сегментов и типами риторических отношений между ними. Например, спутник асимметричного отношения CONTRAST обычно короче ядра. Ввиду вышесказанного, логично выделить несколько признаков, характеризующих размеры сегментов в различных единицах, в частности, в словах или элементарных сегментах.
3.4.2 Сигнальные фразы
Ключевые или сигнальные слова и фразы так или иначе использует каждая из рассмотренных работ, потому как являются наиболее явными показателями наличия риторических отношений. Наша работа не станет исключением. У нас имеются списки, содержащие по несколько десятков сигнальных фраз для русского и английского языков. Для каждой такой сигнальной фразы введем в качестве булевых признаков ее наличие/отсутствие среди первых/последних 3 слов каждого сегмента.
3.4.3 Синтаксические признаки
Используемый нами синтаксический анализатор позволяет для каждого предложения получить синтаксическое дерево зависимостей, выделяя для каждого слова ее часть речи, специфичные для части речи характеристики формы слова, а также синтаксическую функцию (subject, object, etc.). Будем кодировать эти свойства как бинарные признаки вида <свойство>_is_<значение>, например, POS_is_Noun, NounType_is_Common, SyntacticFunction_is_Subject.
Использование SVM требует конечности вектора признакового пространства, потому мы не можем выделять такие признаки для каждого слова в сегменте. Аналогично Marcu и duVerle, мы будем рассматривать префиксы и суффиксы сегментов конечной длины (3 слова). При наложении префикса и суффикса сегмента друг на друга признаки для общих слов будут дублироваться. Также вместо формализма доминантных множеств мы будем кодировать тот же набор признаков для 5 верхних слов соответствующего синтаксического дерева зависимостей (при его обходе в ширину). Если кодирование префиксов и суффиксов преследует примерно те же цели, что и кодирование сигнальных фраз, т.е. поиск и анализ связующих сегменты конструкций (как уже отмечалось многими исследователями, значимые риторические сигналы находятся на концах сегментов), то кодирование верхушки синтаксического дерева позволяет учесть наиболее общую синтаксическую структуру сегмента.
Для составных сегментов, покрывающих несколько ЭДЕ, может иметься несколько синтаксических деревьев. В таких случаях синтаксические признаки будут извлекаться для первого и последнего ЭДЕ сегмента. Соответственно, для сегментов-ЭДЕ все признаки будут дублироваться.
3.4.4 Лексические классы
Для слов из предыдущего пункта будем кодировать в той же манере их лексические классы. Это позволит достичь большего уровня абстракции от конкретных слов и эффективнее использовать данные для обучения. Для выделения лексических классов будем использовать возможности синтаксического анализатора ABBYY Compreno.
3.4.5 Риторическая структура
В процессе построения риторических деревьев высших порядков необходимо учитывать риторическую структуру нижележащих. Для каждого сегмента будем выделять как признаки тип верхнего риторического отношения в его RST-дереве (три булева признака: _is_NS, _is_SN, _is_NN), а также размеры сегментов-потомков в ЭДЕ по отношению к размеру в ЭДЕ сегмента родительского.
Дополнительно будем дублировать признаки 1-4 для первой и последней ЭДЕ, принадлежащих promotion set рассматриваемого сегмента.
3.5 Обучение и тестирование
3.5.1 Данные
3.5.1.1 RST
RST Discourse Treebank [35], составленный в 2001 году усилиями Carlson, Marcu и Okurowski, является на настоящий момент наиболее объемным корпусом англоязычных текстов, аннотированных экспертами в соответствии с RST. Он содержит 385 статей из Wall Street Journal, сопровождаемых полнотекстовыми риторическими деревьями. Корпус распространяется через Linguistic Data Consortium [36] бесплатно для его членов, для остальных, однако, использование корпуса стоит хороших денег. Ввиду этого в настоящей курсовой работе было решено отказаться от использования RST-DT и обратить внимание на небольшой, но свободно распространяемый Discourse Relations Reference Corpus.
Discourse Relations Reference Corpus [31] Taboada и Renkema содержит 65 текстов на английском языке: 14 примеров разборов с сайта RST [11], 21 текст из RST-DT и 30 текстов из SFU Review Corpus [37]. Корпус распространяется бесплатно через сайт RST. Там же доступны файлы разборов текстов, полученные с помощью программы RSTTool [38] (утилита для автоматизации процесса RST-аннотирования). Разборы поставляются в форматах .rs2, .rs3 (форматы, основанные на XML) и .lisp (рекурсивное преставление дерева в синтаксисе языка Lisp) и имеют прозрачную структуру для анализа.
DRRC предполагается использовать для обучения англоязычных классификаторов и оценки качества выводимых системой RST-деревьев. Пары смежных сегментов из текстов корпуса, явно связанные некоторым риторическим отношением, будут служить обучающими примерами как для классификатора, оценивающего наличие или отсутствие риторической связи (такой пример соответствует «положительному» классу – риторическая связь присутствует), так и для классификатора, оценивающего конкретный вид риторического отношения (пример соответствует одному из классов NS, SN и NN).
Для обучения первого классификатора также необходимо некоторое количество примеров риторически не связанных сегментов. При извлечении таких примеров из обучающей выборки RST-деревьев мы будем руководствоваться следующим правилом: непересекающиеся сегменты текста X и Y могут считаться риторически не связанными, если в RST-дереве текста не имеется такого отношения R между сегментами P и Q, X P и Y Q, что в поддеревьях для P и Q сегменты, содержащие X и Y, всегда являются ядрами отношений. В частности, два элементарных сегмента X и Y риторически не связаны, если в RST-дереве текста не найдется риторического отношения, для аргументов которого X и Y являются наиболее значимыми ЭДЕ (т.е. входят в соответствующие promotion set’ы). Легко видеть, что данное определение отсутствия риторической связи согласуется с принципом строгой композиции Marcu. При подготовке обучающих данных на каждый пример наличия отношения мы будем извлекать одну пару риторически не связанных сегментов – это всегда возможно, поскольку «отрицательных» примеров в каждом тексте значительно больше, чем «положительных».
3.5.1.1 Рефераты
Для оценки качества системы реферирования мы располагаем корпусом текстов на основе материалов конференции DUC-2001. Корпус составлен из текстов новостных статей, взятых из таких газет как Wall Street Journal, San Jose Mercury News и др. К конференции было подготовлено в общей сложности 60 наборов текстов: 30 тренировочных и 30 тестовых, - содержащих каждый от 6 до 14 статей. Каждая статья содержит в среднем 800 слов (порядка 37 предложений) и сопровождается тремя экспертными аннотациями (abstracts) размером около 100 слов. Мы располагаем тестовым подмножеством оригинального корпуса (всего 311 статей), далее будем называть его DUC-Abstracts. Также имеется 147 статей из тренировочной части корпуса с аннотациями типа extract (наборы информативных предложений; средний размер – 160 слов), составленными Mary Ellen Okurowski и John M. Conroy на основе abstract-аннотаций. На этот набор мы будем ссылаться как на DUC-Extracts.
3.5.2 Метрики тестирования
3.5.2.1 Оценка деревьев
Для оценки корреляции RST-деревьев, построенных системой, с экспертными мы будем использовать метрики PARSEVAL (PARSing EVALuation). Данный набор метрик изначально использовался для оценки качества синтаксических парсеров и по аналогии был перенесен Marcu ([24]) на анализатор риторический.
Риторические деревья рассматриваются как наборы узлов (составляющих). Составляющая RST-дерева – элементарный сегмент или риторическое отношение. Мы будем называть составляющую в RST-дереве, полученном системой, правильной, если она присутствует в экспертном RST-дереве. В частности, правильность составляющей-отношения означает, что в экспертном дереве те же сегменты текста соединены тем же риторическим отношением.
Метрики PARSEVAL описывают три понятия: размеченные точность, полнота и F-мера. Размеченная точность – отношение числа правильных составляющих в RST-дереве, построенном системой, к общему числу составляющих в этом дереве. В свою очередь, размеченная полнота – отношение числа правильных составляющих в RST-дереве системы к общему числу составляющих в экспертном дереве. Наконец, размеченная F-мера – среднее гармоническое размеченных точности и полноты.
3.5.2.2 Оценка рефератов
Корреляцию получаемых системой рефератов с экспертными аннотациями мы будем оценивать с помощью метрик ROUGE (Recall-Oriented Understudy for Gisting Evaluation) – фактически, эти метрики являются на сегодняшний день стандартом оценки качества автоматически генерируемых рефератов. Метрики ROUGE основаны на подсчете количества перекрывающихся n-грамм в автоматическом и экспертном рефератах. Мы будем использовать ROUGE-N c N = 1,2, ROUGE-L и ROUGE-W-1.2.
ROUGE-N определяется как полнота набора n-грамм автоматически сгенерированного реферата по отношению к набору экспертных аннотаций данного текста и рассчитывается по формуле
|
(1)
|
где ReferenceSummaries – экспертные аннотации, n – длина n-грамм gramn и Countmatch(gramn) возвращает максимальное число n-грамм gramn, встречающихся как в автоматически сгенерированном, так и в экспертных рефератах.
Метрика Rouge-L вместо числа совпадающих n-грамм использует длину наибольшей общей подпоследовательности (с пропусками) автоматической и экспертной аннотаций. Rouge-W представляет собой взвешенный вариант Rouge-L, дающий преимущество непрерывным подпоследовательностям. Конкретные формулы для расчета этих метрик можно найти в [18]. Там же на основе данных конференций DUC 2001-2003 гг. показано, что выбранные метрики хорошо коррелируют с экспертными оценками рефератов.
3.5.3 Оптимизация пространства признаков
Хотя применимость выделенных нами признаков к классификации риторических отношений обоснована в работах Marcu и duVerle, заострение внимания на направленности отношений без учета их конкретных классов может привести к появлению среди признаков бесполезных и избыточных. Например, выше уже упоминалась о корреляции такого признака, как соотношение длин участвующих в отношении сегментов, с типом отношения между ними. При этом, однако, для некоторых отношений сателлит обычно короче ядра (CONCESSION), для других – длиннее (ELABORATION), а для третьих распространены оба случая (LISTING). Соответственно, данный признак слабо информативен, если дело касается исключительно направленности отношений (по крайней мере, в отрыве от остальных признаков). Для устранения таких признаков и обоснования релевантности остальных необходимо организовать отбор наиболее информативных признаков из рассмотренных выше. Сокращение размерности признакового пространства также позволит нам улучшить временные характеристики работы нашего алгоритма.
Чтобы получить данные о релевантности конкретных признаков и не привязываться к механизму классификации, решено было реализовать фильтрацию признаков по порогу некоторой статистики. В качестве последней использована простая в реализации хи-квадрат оценка. Для данных признака f и класса c хи-квадрат статистика рассчитывается как
|
(2)
|
где A – число примеров класса c, где f =1;
B – число примеров, не принадлежащих c, где f =1;
C – число примеров класса c, где f =0;
D – число примеров, не принадлежащих c, где f =0;
m = A+B+C+D – общее число примеров.
В качестве оценки признака мы брали максимальную по модулю оценку среди всех классов:
|
(3)
|
Заметим, что данные формулы оперируют исключительно бинарными признаками, поэтому для их использования все признаки, принимающие вещественные значения, были приведены к набору бинарных. Например, такой признак, как относительная длина сегмента, принимающий значения из полуинтервала (0, 1], был преобразован в набор булевых признаков следующего вида: относительная длина сегмента принадлежит полуинтервалу (0, 0.1], относительная длина сегмента принадлежит полуинтервалу (0.1, 0.2] и т.д. Размерность признакового пространства обоих классификаторов после бинаризации составила 19325 признаков.
Мы воспользовались корпусом DRRC для сбора обучающих данных и вычислили на его основе хи-квадрат оценки информативности всех используемых признаков для каждого из классификаторов.
Пять наиболее релевантных признаков для классификатора, отвечающего за оценку наличия или отсутствия риторической связи, составили:
Признак
|
|
Входные сегменты состоят из одинакового числа ЭДЕ
|
57.805
|
Число ЭДЕ в первом сегменте больше, чем во втором
|
22.600
|
Лексический класс слова, расположенного в вершине синтаксического дерева последней значимой клаузы первого сегмента, – SITUATIONAL AND ATTRIBUTIVE
|
18.085
|
Лексический класс первого слова первой значимой клаузы первого сегмента - SITUATION
|
17.362
|
Лексический класс последнего слова первой клаузы первого сегмента – VERBAL COMMUNICATION
|
15.968
|
Пять наиболее релевантных признаков для классификатора, предсказывающего тип риторического отношения, составили:
Признак
|
|
Лексический класс предпоследнего слова первой клаузы первого сегмента – INTELLECTUAL ACTIVITY
|
118.677
|
Лексический класс третьего слова первой клаузы первого сегмента –COMMUNICATIONS
|
116.281
|
Часть речи второго слова последней клаузы первого сегмента – деепричастие
|
116.280
|
Лексический класс первого слова последней клаузы второго сегмента – FEELING AS CONDITION
|
92.828
|
Лексический класс слова, расположенного третьим при обходе в ширину синтаксического дерева последней клаузы второго сегмента, - ENTITY BY FUNCTION AND PROPERTY
|
81.296
|
Посредством кросс-валидации мы установили оптимальные пороговые значения статистики равными 7.341 для первого классификатора и 71.206 для второго, что привело к сокращению размерности признаковых векторов соответственно до 465 и 72 признаков.
|
