1 Постановка задачи
Целью данной работы является разработка и реализация алгоритма построения риторического дерева текста на основе машинного обучения.
Программная реализация разрабатываемого метода должна быть встроена в рассмотренную выше систему ИСП РАН вместо используемого на текущий момент эвристического алгоритма либо в комбинации с ним.
Разрабатываемый алгоритм принимает на вход исходный текст после синтаксического анализа составляющих его предложений. Алгоритм должен использовать данные, полученные в результате синтаксического анализа, для обучения и собственно построения RST-деревьев. Результатом работы алгоритма является древовидное представление риторической структуры текста в формате, определяемом исходной системой.
Разрабатываемый алгоритм должен обеспечивать лучшее качество выводимых с его помощью риторических структур по сравнению с используемой на текущий момент эвристикой. Качество RST-деревьев следует оценивать следующим образом:
Через сравнение их структуры с риторическими деревьями, построенными вручную (внутренняя оценка). Для этого можно использовать метрики PARSEVAL [30].
Через сравнение получаемых с их помощью рефератов с модельными аннотациями, построенными вручную, посредством уже упоминавшихся метрик ROUGE (внешняя оценка).
Улучшение качественных характеристик построения системой RST-деревьев после ее модификации с помощью разрабатываемого алгоритма не должно сопровождаться существенным увеличением времени ее работы. Текущая версия системы строит RST-дерево текста за линейное время от его размера в словах. Разрабатываемый алгоритм должен обеспечить сохранение линейного характера этой зависимости.
2 Обзор существующих решений
В процессе построения RST-дерева текста можно выделить два последовательных этапа. Первый из них – сегментация – представляет собой процесс определения границ элементарных сегментов (также их называют элементарными дискурсивными единицами, ЭДЕ), которые будут служить листовыми узлами риторического дерева. Второй этап заключается в построении иерархической структуры над набором элементарных сегментов.
В роли элементарных сегментов зачастую выступают клаузы [32], так что первый этап построения RST-дерева может быть переформулирован как процесс выделения в тексте границ клаузы. Использование средств синтаксического анализа предложений позволяет добиться высокой точности в данной задаче, как показывают исследования [20, 23]. Простая эвристика, используемая в модифицируемой нами системе, основана на достаточно компетентном синтаксическом анализе предложений (используется парсер ABBYY Compreno) и в модификации не нуждается. Ввиду вышесказанного, в дальнейшем мы сосредоточимся на втором этапе процедуры построения RST-деревьев, предполагая анализируемый текст уже корректно разбитым на элементарные сегменты. Соответственно, в обзоре методов построения RST-деревьев сегментации также будет уделено существенно меньшее внимание.
В оставшейся части главы сначала будут кратко рассмотрены известные нам эвристические методы построения RST-деревьев, не использующие машинное обучение, а затем будет дан более детальный обзор техник, так или иначе его использующих. В конце главы будут сделаны выводы о применимости рассмотренных методов к использованию в модифицируемой системе.
2.1 Эвристические подходы
Первые методы автоматического построения риторических деревьев, не накладывающие ограничений на вид подаваемых им на вход текстов, основывались на использовании вручную составленных наборов правил.
Marcu, 1997
Данная работа [21] может считаться одной из первых в области. В ее основе лежит определение допустимой риторической структуры текста, позволяющее для заданного набора ограничений построить все допустимые RST-деревья текста и выбрать из них наиболее правдоподобную.
Допустимая риторическая структура текста по Marcu должна удовлетворять следующим свойствам:
ЭДЕ являются непересекающимися фрагментами текста.
Риторические отношения имеют место между смежными сегментами различных размеров.
Отношения могут быть разделены на два класса: симметричные и асимметричные; симметричные отношения связывает одинаково значимые для авторских целей сегменты, асимметричные имеют место между сегментом-ядром, имеющим значение с авторской позиции, и сегментом-спутником, используемым для улучшения понимания читателем содержимого сегмента-ядра и самостоятельно не имеющим функциональной ценности.
В большинстве случаев риторическая структура текста может быть представлена в виде двоичного дерева.
Если некоторое риторическое отношение имеет место между двумя сегментами в составе RST-дерева текста, то это отношение имеет место между наиболее значимыми ЭДЕ в составе рассматриваемых сегментов. Набор наиболее значимых ЭДЕ для заданного сегмента называется promotion set и определяется рекурсивно как объединение наиболее значимых ЭДЕ его непосредственных потомков-ядер в RST-дереве; promotion set элементарного сегмента состоит из него самого. Это правило Marcu называет критерием строгой композиции (strong compositionality criterion).
Последнее свойство является здесь ключевым: оно позволяет генерировать все допустимые риторические деревья заданного текста по набору ограничений на риторические отношения между составляющими его элементарными сегментами. Соответствующий алгоритм описан в [33]. С каждым допустимым RST-деревом текста связывался некоторый эвристический весовой коэффициент, после чего выбиралось наиболее весомое дерево.
Для формулирования гипотез о возможных риторических отношениях между элементарными сегментами текста Marcu использовал сигнальные/ключевые слова и фразы (cue words) – специальные конструкции в тексте, обычно союзы и вводные слова, используемые для связывания аргументов риторических отношений и тем самым являющиеся сильными индикаторами их наличия. С помощью набора правил на основе регулярных выражений, полуавтоматически составленного в результате анализа большого корпуса примеров использования сигнальных фраз, Marcu определял границы связываемых таким образом сегментов и предполагаемые типы риторических отношений между ними.
Corston-Oliver, 1998
В целом данный подход [22] аналогичен использованному в предыдущей работе. Corston-Oliver при этом использовал более сложные наборы правил для каждого отношения, использующие как сигнальные фразы, так и другие синтаксические критерии. Часть правил, связанных с конкретным отношением, определяла набор необходимых условий для проведения этого отношения. Оставшиеся эвристики взвешивались для обеспечения возможности выбора между несколькими риторическими отношениями, для которых выполнены необходимые условия. Весовые коэффициенты первоначально определялись интуитивно и корректировались затем методом проб и ошибок. Автор также использовал механизм бэктрекинга [34] для сокращения пространства поиска оптимального RST-дерева.
LeThanh, 2004
LeThanh, Abeysinghe и Huyck в работе [23] представили систему построения качественных RST-деревьев на уровне всего текста без использования машинного обучения, задавшую стандарт качества среди полнотекстовых риторических анализаторов вплоть до появления работы duVerle (ниже).
Построение RST-дерева текста происходит здесь в два этапа. На первом этапе выявляется риторическая структура отдельных предложений, на втором происходит поиск наилучшего способа объединения полученных поддеревьев для получения полной RST-иерархии текста. Выделение элементарных дискурсивных единиц в составе предложения осуществляется с помощью набора правил, основанных на синтаксической структуре предложения и присутствии сигнальных фраз. Также, помимо местоположения границ ЭДЕ, эти правила позволяют выявить, какие именно группы ЭДЕ разделяет каждая граница, и инициировать риторическое отношение между ними. Тип и направления отношения определяются на основе различных факторов, включающих синтаксис, сигнальные фразы (в том числе специальные существительные и глаголы), а также средства семантического согласования (например, синонимия). Далее простая эвристика используется для объединения полученного набора отношений в RST-дерево предложения.
Получив риторические представления для каждого предложения, система начинает поиск оптимальной структуры для всего текста. На каждом шаге система оперирует некоторым набором уже построенных поддеревьев, соответствующих непересекающимся сегментам текста. Система далее определяет все возможные способы их однократного соединения, руководствуюсь следующими двумя принципами: связываемые сегменты должны быть соседними в тексте и находиться в рамках одной и той же минимальной объемлющей конструкции авторской организации текста (абзаца, параграфа и т.д.). На основе информации о возможных соединениях определяется набор риторических отношений, которые можно построить на данном шаге. Каждое возможное отношение получает оценку, равную суммарному весу голосующих за него эвристик. В качестве последних используются те же признаки, что и для построении RST-деревьев предложений, с эмпирически определенными весами. К оценке отношения также добавляется коэффициент, который тем больше, чем ниже уровень организации текста, в рамках которого происходит соединение сегментов. Используя оценки для возможных отношений, система выбирает одно из них для реализации и соответствующим образом обновляет набор риторических деревьев. Новый набор получает вес, равный сумме веса предыдущего набора деревьев и оценки использованного риторического отношения. Задача алгоритма – начиная с набора RST-деревьев предложений, имеющего нулевой вес, вывести требуемое количество покрывающих текст риторических иерархий (не обязательно одну) с наибольшим весом. Для оптимизации процесса перебора используется лучевой поиск и промежуточное сохранение выводимых отношений.
Авторы осуществили многоуровневую оценку качества работы системы на 20 документах из RST Discourse Treebank [35]. Использовались наборы из 14 и 22 риторических отношений. Авторы заявляют о F-мере 53% для отношений в рамках предложений (60% для определения направлений отношений, т.е. распознавания ядер и сателлитов) и 39,9% (47,1%) в рамках текста. Конкретный метод вычисления F-мер из текста статьи не ясен. Авторы сравнивали качество своей системы на уровне предложений с анализатором SPADE (ниже), на уровне всего текста – с системой Marcu (1997). В обоих случаях рассматриваемая система показала лучшие результаты.
2.2 Подходы с использованием машинного обучения
Marcu, 1999
Фактически, первая попытка использовать машинное обучение в риторическом анализе.
В работе [24] Marcu предложил использовать для построения риторических деревьев shift-reduce алгоритм, использующий для выбора следующего действия механизм деревьев решений. Набор действий состоял из операции SHIFT, помещающей следующий элементарный сегмент на вершину стека, и операций REDUCE, объединяющих два верхних RST-поддерева в стеке в одно. Для каждого типа риторического отношения и для каждого возможного распределения ролей (ядро-спутник) вводилась своя операция REDUCE. Итого, на каждом шаге алгоритм выбирал из 103 действий (1 SHIFT и 102 REDUCE).
Marcu использовал алгоритм C4.5 для построения решающего дерева, классифицирующего shift-reduce действия, на основе следующих классов признаков:
Структурные признаки
Признаки, отражающие число RST-деревьев в стеке и число оставшихся элементарных сегментов на входе.
Признаки, описывающие структуру первых трех деревьев в стеке в терминах типа охватываемых ими текстовых единиц (предложений, абзацев, заголовков), а также их риторическую структуру на верхнем уровне (число непосредственных потомков корневого узла, классы соответствующих отношений).
Лексические и синтаксические признаки (для первых трех деревьев в стеке и первого элементарного сегмента на входе)
Собственно слова и POS-теги первых и последних двух лексем охватываемых сегментов.
Признаки, отражающие наличие в охватываемых сегментах потенциальных сигнальных (ключевых) фраз и их расположение (в начале, в середине, в конце).
История парсера: 5 последних действий
Признаки на основе мер семантической близости: для первых трех деревьев в стеке и первого элементарного сегмента на входе семантическая близость охватываемых сегментов (как bag-of-words, составленных из слов элементарных сегментов, входящих в promotion set дерева) на основе косинусной меры, а также метрик Wordnet, оценивающих степень синонимии и т.д.
В бинарном представлении всего 2789 признаков на обучающий/тестовый пример.
Для обучения и тестирования Marcu использовал вручную размеченный корпус из 90 текстов (нет в свободном доступе). Впервые для оценки качества парсера применялись замеченные точность и полнота - метрики, оценивающее сходство RST-деревьев, выводимых парсером, с деревьями, построенными экспертами. Размеченная точность (полнота) – отношение числа корректно размеченных риторическими отношениями составляющих в RST-дереве, построенном парсером, к числу всех составляющих в этом (экспертном) дереве. Парсер достигал 70% точности и 80% полноты для направлений отношений и 60% точности и полноты для типов отношений. Экспертные верхние границы составляли здесь 77 и 63 % соответственно.
Marcu, Echihabi, 2002
Marcu и Echihabi в работе [25] предложили использовать наивный байесовский классификатор для выявления таких групп риторических отношений, как CONTRAST, CAUSE-EXPLANATION-EVIDENCE, CONDITION и ELABORATION, между предложениями и клаузами.
Данные для обучения и тестирования генерировались автоматически посредством извлечения из большого текстового корпуса – порядка 41,000,000 предложений - пар смежных предложений или клауз, содержащих характерные для одной из групп отношений союзы или вводные слова. К примеру, если предложение начиналось со слова but, оно извлекалось вместе с непосредственно предшествующим предложением, и пара помечалась отношением CONTRAST. Таким путем авторы получили в среднем по 2,000,000 примеров отношений каждой группы. В качестве отрицательных примеров авторы случайным образом извлекали из текстов корпуса пары не являющихся соседними предложений (NO-RELATION-SAME-TEXT), а также пары предложений из разных текстов (NO-RELATION-DIFFERENT-TEXT), по 1,000,000 на каждый класс.
Для каждой пары риторических отношений авторы обучили на извлеченных данных наивный байесовский классификатор. Признаками для каждой пары предложений служили всевозможные пары слов, взятых по одному из каждого предложения. Авторы предположили, что некоторые такие пары слов могут быть хорошими индикаторами для определенных риторических отношений. При этом ключевые слова и фразы, использовавшиеся для извлечения риторических отношений из текстового корпуса, перед обучением классификаторов были удалены из обучающей выборки. Все парные классификаторы тестировались на наборах данных с равным – по 5,000 – количеством примеров каждого класса и показали точность выбора между двумя отношениями от 65 до 93%. Авторы также обучили общий байесовский классификатор для всех шести рассматриваемых классов отношений, который при аналогичном тестировании показал точность 49,7%.
Далее авторы предложили использовать в качестве признаков для обучения и классификации пары наиболее информативных слов предложений – глаголов и существительных, а также характерных для рассматриваемых отношений союзов и вводных слов. Эксперименты на основе синтаксически размеченного текстового корпуса BLIPP (1,800,000 предложений) позволили добиться примерно той же точности парных классификаторов при значительно меньшем объеме обучающей выборке - 100,000 примеров на каждый класс.
SPADE
Soricut и Marcu в работе [20] представили вероятностный подход к построению риторических деревьев в рамках отдельных предложений с использованием их синтаксической и лексической структуры. Система впоследствии получила название SPADE –Sentence-level PArsing for DiscoursE. Вероятностная модель сначала используется для определения границ элементарных дискурсивных единиц в составе предложения. Затем SPADE использует динамическое программирование, чтобы сопоставить предложению его наиболее вероятную риторическую структуру. Вероятности потенциальных RST-деревьев для заданного предложения определяются с помощью признаков, выводимых из представления синтаксической структуры текста в виде лексикализованной иерархии составляющих.
В качестве таковых признаков авторы вводят доминантные множества (dominance sets). Для заданного предложения доминантное множество определяется как набор узлов его иерархии составляющих, являющихся корневыми узлами соответствующих иерархий для содержащихся в предложении элементарных дискурсивных единиц, взятых вместе с их непосредственными родительскими узлами (за исключением корневой составляющей для всего предложения). Другими словами, доминантное множество предложения состоит из всех «точек присоединения» иерархий составляющих отдельных ЭДЕ друг к другу.
Авторы использовали RST Discourse Treebank для обучения и тестирования моделей, используя как полный (110 отношений), так и сокращенный (18) наборы риторических отношений. Для оценки производительности использовалась F-мера точности и полноты по метрике PARSEVAL. Система продемонстрировала F-меры 49% и 45,6% для сокращенного и полного наборов риторических отношений соответственно, что в сравнении с парсером Marcu (2000) – state-of-art на тот момент – дало выигрыш порядка 10%. Использование экспертного синтаксического анализа и выделения ЭДЕ позволило поднять F-меры для сокращенного и полного наборов отношений до 75,5% и 70,3% соответственно. При этом в терминах неразмеченной риторической структуры (без учета типов отношений) система достигла близкого к экспертному результата (96,2%).
Reitter, 2003
В данной работе [26] впервые было предложено использование машин опорных векторов для (SVM) для классификации риторических отношений. Reitter обосновывал выбор SVM следующими причинами:
• высокое качество классификации, показываемое SVM во многих приложениях;
• возможность мультиклассовой классификации (один против всех);
• большая размерность (>5000) множества признаков и их взаимосвязанность;
• относительно малый размер доступной тренировочной выборки (<1000).
Использовались следующие классы признаков:
• Присутствие в сегменте ключевых слов и их относительные позиции в сегменте. Набор ключевых слов автоматически извлекался из тренировочного корпуса посредством фильтрации по частям речи.
• Характеристики именных фраз.
• Вхождения в сегмент определенных знаков пунктуации.
• Части речи слов на границах сегментов.
• Лексическая схожесть сегментов.
• Отношение длин сегментов в словах.
Для обучения и тестирования классификатора использовались RST Discourse Treebank, а также вручную составлений корпус из новостных статей на немецком языке. Рассматривался сокращенный набор отношений RST-DT. Reitter заявляет о 61,8%-ной точности мультиклассовой классификации на тестовом подмножестве RST-DT и 39,1%-ной для своего корпуса.
duVerle, 2009
duVerle и Prendinger в работе [27] решили опустить этап сегментации и сконцентрировался на втором этапе парсинга дискурса, мотивируя это решение тем, что текущие state-of-the-art результаты в автоматическом сегментировании (Marcu и LeThanh) значительно ближе к экспертным по сравнению с качеством собственно RST-деревьев.
Развивая идеи Reitter, авторы использовали механизм SVM как для оценки вероятности наличия некоторого риторического отношения между заданными сегментами, так и для предположений о конкретном типе и направленности этого отношения, что вкупе с наивным агломеративным алгоритмом построения RST-иерархии позволило получать корректные риторические структуры за линейное время.
Авторы обучили два SVM-классификатора – бинарный для наличия/отсутствия и мультиклассовый для типов и направлений отношений – на данных RST-DT. Для второго классификатора использовался набор из 18 отношений, что вместе со всеми возможными комбинациями расстановки ролей ядро-спутник для двух сегментов давало 41 класс. Начиная с набора атомарных риторических деревьев, соответствующих элементарным сегментам, алгоритм итеративно выбирал наилучшую пару соседних сегментов для соединения (на основе оценок, полученных с помощью первого классификатора), определял тип отношения и роли объединяемых сегментов с помощью второго классификатора, добавлял в набор новое RST-поддерево и обновлял оценки первого классификатора. С учетом того, что для объединения рассматривались только смежные поддеревья, на каждой итерации требовалось пересчитать первым классификатором не более двух оценок, что давало существенный выигрыш в плане временной сложности. С последним оставшимся в наборе RST-деревом алгоритм заканчивал работу.
Как и в предыдущих работах (Soricut and Marcu, Reitter, LeThanh), duVerle работал исключительно с бинарными RST-деревьями. Не бинарные многоядерные отношения при обучении трансформировались в наборы вложенных одно в другое бинарных.
Оба классификатора использовали широкий набор признаков. Авторы исходили из предположения устойчивости SVM к влиянию неинформативных признаков при больших (~105) размерностях признакового пространства. Ниже представлены классы использованных признаков:
1. Авторская организация текста: признаки, отражающие принадлежность рассматриваемых сегментов к одному предложению или абзацу, а также длины сегментов в словах, ЭДЕ и т.д.
2. Лексические и пунктуационные признаки: вместо того, чтобы кодировать присутствие определенных сигнальных фраз, авторы автоматически собрали с помощью тренировочного корпуса словарь часто используемых n-грамм (n = 1, 2, 3), и кодировали их присутствие среди первых и последних n токенов каждого сегмента. В качестве токенов учитывались не только слова, но и знаки пунктуации, а также маркеры границ предложений и абзацев (в этом основное отличие метода от использования явного списка сигнальных фраз, как, например, у Marcu). Существенно лучшие результаты метода по сравнению с поиском сигнальных фраз в bag-of-words-представлении сегментов подтвердили гипотезу о том, что сильные риторические сигналы обычно расположены на границах сегментов.
3. Синтаксические признаки: в дополнение к предыдущему пункту, а также для достижения большей независимости от конкретного лексического контента, авторы кодировали части речи первых и последних трех слов каждого сегмента. Использование более длинных префиксов/суффиксов не оправдало себя.
4. Доминантные множества: ряд признаков, эмулирующих использование идеи доминантных множеств Soricut и Marcu. Данные признаки актуальны только для сегментов размером меньше одного предложения.
5. Признаки, эксплуатирующие критерий строгой композиции: дублирование признаков классов 1-4 для наиболее значимых ЭДЕ рассматриваемых сегментов.
6. Внутренняя риторическая структура: признаки, отражающие строение RST-поддеревьев рассматриваемых сегментов.
Впоследствии система duVerle и Prendinger обзавелась собственным механизмом сегментации (тоже, кстати, основанном на SVM) и получила название HILDA [29]. На данный момент эта система является state-of-art среди полнотекстовых риторических парсеров.
2.3 Выводы
В рамках рассматриваемой задачи внедрение любой из вышеописанных техник требует модификаций.
Основным недостатком подходов на основе правил является трудоемкость составления этих самых правил. Так, внедрение подхода Marcu требует составления регулярных выражений для каждой потенциальной сигнальной фразы. Учитывая тот факт, что модифицируемая система должна адекватно работать с несколькими языками, необходимо иметь свои наборы правил (в частности, регулярных выражений) для каждого языка. То же самое применимо к схемам Corston-Oliver (причем здесь эвристики значительно сложнее) и LeThanh (здесь конкретный вид используемых правил неизвестен). Подходы на машинном обучении в этом плане проявляют большую гибкость, так как в общем случае можно переобучить модель для нужного языка. Также стоит отметить, что все три рассмотренных нами подхода так или иначе используют перебор допустимых RST-деревьев, что может критически увеличить временную сложность модифицируемой системы – текущая ее версия строит RST-дерево заданного текста за один проход.
Среди рассмотренных нами работ, так или иначе использующих машинное обучение, предлагается лишь два полнотекстовых парсера – shift-reduce алгоритм Marcu и HILDA. Работа Reitter описывает лишь классификатор риторических отношений, метод же построения риторических деревьев на его основе не был реализован. Тем не менее, похожий механизм классификации отношений используется системой HILDA. Работы Marcu, Echihabi и Soricut, Marcu направлены на построение RST-деревьев исключительно в рамках предложений, так что их внедрение требует дополнительного механизма построения риторической структуры всего текста (например, переборной схемы из рассмотренных абзацем выше). Также следует отметить, что в обеих работах используются вероятностные подходы, для качественной работы которых необходимо значительное количество обучающих данных. Marcu и Echihabi предлагают решение данной проблемы, однако обобщающая способность моделей, обученных на таких данных, сомнительна. Еще одна проблема – использование формализма доминантных множеств (Soricut, Marcu) требует дополнительных накладных расходов по преобразованию грамматик зависимостей, используемый синтаксическим анализатором ABBYY Compreno, к лексикализованным грамматикам составляющих.
Shift-reduce алгоритм Marcu и алгоритм duVerle наиболее близки к решению поставленной нами задачи. Поскольку оба алгоритма строят RST-дерево заданного текста в один проход, внедрение любого из них позволит сохранить линейность времени работы системы. Обе работы, однако, описывают не конкретные наборы используемых признаков, а их классы (с примерами). Соответственно, их реализация требует более детальной спецификации признакового пространства.
Следует отметить, что все рассмотренные выше работы не делают предположений о целях, для достижения которых строятся RST-деревья. Такой подход обеспечивает универсальность, но может быть недостаточно эффективен в рамках поставленной задачи. Алгоритм взвешивания, использующийся в модифицируемой нами системе, учитывает только направленность отношений в RST-дереве текста и игнорирует их конкретный класс. Иначе говоря, разумно ограничиться ровно двумя классами риторических отношений (симметричные/асимметричные). Для работ, использующих машинное обучение, это позволит более эффективно использовать имеющиеся обучающие данные, однако неизбежно приведет к появлению неинформативных признаков. Для их элиминации либо корректировки требуется дополнительный анализ.
|
