14.12.2021 17:32
Takagi 6 1200 Источник


Всем привет!


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


Статьи цикла:
1) Методы автоматического реферирования: постановка задачи и методы без учителя ⬅️
2) Методы автоматического реферирования: экстрактивные методы


Это первая статья цикла, посвящённая самой задаче и методам без учителя, которым не нужен эталонный корпус рефератов: методу Луна, TextRank, LexRank, LSA и MMR.


Задача


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


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


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


За рубежом существовало несколько конференций по проблемам автоматического реферирования, самая известная из которых — DUC, Document Understanding Conferences. Сейчас основное специализированное место для обсуждения исследований по автоматическому реферированию — это семинар NewSum, New Frontiers in Summarization, в рамках конференции EMNLP.


Кроме того, регулярно проводятся дорожки по разным смежным задачам. Во-первых, с 2014 по 2019 проводилась дорожка CL-SciSumm по автоматическому реферированию научных документов. Во-вторых, в 2017 и 2020 проводилась дорожка WebNLG по преобразованию триплетов RDF в тексты и наоборот. Это можно рассматривать как специфический тип автоматического реферирования. В-третьих, в 2021 году была дорожка AutoMin в рамках конференции Interspeech, посвящённая автоматическому реферированию расшифровок аудиозаписей встреч.


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


  • Генерация заголовков новостей
  • Генерация текстов по таблицам или триплетам
  • Реферирование стенограмм встреч
  • Реферирование под поисковый запрос
  • Реферирование книг
  • Подбор ключевых слов для текстов

Кроме того, есть очень похожая задача: симплификация, упрощение текстов. По этой задаче на конференции Диалог-2021 была отдельная дорожка, RuSimpleSentEval. Её суть в том, что нужно упростить предложение с помощью удаления ненужных подробностей или упрощения лексики.


Классификация методов автоматического реферирования


По возможности использовать новые слова:


  • Экстрактивные (экстрагирующие, квазиреферативные, extractive)
  • Абстрактивные (абстрагирующие, реферативные, abstractive)

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


По необходимости наличия эталонных рефератов:


  • С учителем
  • Без учителя

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


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


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


Метод Луна


Метод Луна — первый эвристический метод автоматического реферирования. Он был описан в 1958 году в статье Ханса Петера Луна и реализован на IBM 704. В качестве примеров работы алгоритма в этой статье приведены автоматические рефераты для научной статьи из The Scientific American и новостной статьи из The New York Times.


В современных терминах алгоритм звучит так:


  • Вычисляем значимые слова документа:
    • Делаем стемминг или лемматизацию слов: разные словоформы одной леммы должны считаться как одно слово.
    • Считаем частоты слов, формируем список слов по убыванию частоты.
    • Убираем стоп-слова: частотные слова, у которых нет отдельной смысловой нагрузки, например предлоги и частицы.
    • Убираем слишком редкие слова, например такие, которые встречаются только 1 раз, либо убираем какой-то перцентиль слов по частоте.
    • Все оставшиеся слова считаем значимыми.
  • Считаем значимость для предложений:
    • Предложение делим на промежутки, которые начинаются и заканчиваются значимыми словами. В промежутке могут быть и незначимые слова, но не более 4 подряд.
    • Значимость промежутка — квадрат количества значимых слов в промежутке, делённый на размер промежутка.
    • Значимость предложения — максимум из значимостей промежутков.
  • Берём в качестве реферата предложения со значимостью выше определённого порога.

Пример вычисления значимости предложения приведён на рисунке ниже. Красным обозначены стоп-слова, фиолетовым — незначимые слова, а зелёным — значимые слова.



Несмотря на свою простоту, метод Луна до сих используется в современных программных комплексах автоматического реферирования. В частности, он есть в sumy.


TextRank


TextRank — один из самых популярных методов автоматического реферирования. В его основе представление текста в виде неориентированного графа с последующим применением на этом графе алгоритма PageRank. В качестве вершин графа берутся предложения текста, в качестве веса рёбер — схожесть предложений. Схожесть вычисляется по формуле ниже, где $S_i$ — набор слов i-го предложения, а $S_j$ — набор слов j-го предложения. Можно заметить, что она симметрична и считается за линейное время от количества слов.


$\text{sim}_{ij} = \frac{|\{w | (w \in S_i) \land (w \in S_j)\}|}{\log(|S_i|) + \log(|S_j|)} $


PageRank вершины определён по формуле ниже, где $P(S_i)$ — PageRank i-го предложения, $\text{sim}_{ij}$ — схожесть $S_i$ и $S_j$, $\mathbb{S}$ — множество всех предложений, d — коэффициент демпфирования (по умолчанию 0.85). Мы считаем, что схожие $S_j$ влияют на $S_i$ сильнее, чем далёкие.


$P(S_i) = \frac{(1 - d)}{|\mathbb{S}|} + d \cdot (\sum_{S_j \in \mathbb{S}} \frac{\text{sim}_{ij}}{\sum_{S_k\in \mathbb{S}} \text{sim}_{kj}} \cdot P(S_j))$


Это определение, очевидно, рекурсивно. Можно представить его в матричном виде, и в таком случае значения $P(S_i)$ для предложений — элементы первого собственного вектора модифицированной матрицы смежности. Их можно найти с помощью метода степенных итераций. Коэффициент демпфирования здесь нужен для тех же целей, что и в оригинальном PageRank — для лучшей сходимости метода и моделирования "случайных переходов". В результате мы получаем значения, которые отражают важность предложений.


Построение начальной матрицы смежности выполняется за $O(|\mathbb{S}|^2)$ вычислений схожести, каждая итерация степенного метода — за $O(|\mathbb{S}|^2)$ времени, так как мы перемножаем матрицу $|\mathbb{S}| \times |\mathbb{S}|$ на вектор длины $|\mathbb{S}|$. Скорость сходимости метода определяется модулем второго собственного значения матрицы.


TextRank хорош тем, что не требует никаких сложных лингвистических моделей, знаний предметной области или языка. Его можно очень широко применять, как минимум в качестве базового метода. Он реализован в огромном числе программных пакетов, например в sumy, pytextrank, textrank.


LexRank


LexRank — модификация TextRank, использующая меру схожести на основе TF-IDF и зануляющая рёбра графа с весом ниже определённого порога $t$.


Схожесть предложений определяется формулами ниже.


$tf_w^i = \frac{\{|{w_k | (w_k \in S_i) \land (w_k = w)}\}|}{|S_i|}$


$idf_w = \log(\frac{|\mathbb{S}|}{|\{S_i | w \in S_i\}|})$


$sim_{ij} = \frac{\sum_{w \in \{S_i \cup S_j\}} tf_w^i \cdot tf_w^j \cdot (idf_w)^2 }{\sqrt{\sum_{w \in S_i} (tf_w^i \cdot idf_w)^2} \cdot \sqrt{\sum_{w \in S_j} (tf_w^j \cdot idf_w)^2}}$


Такая схожесть позволяет меньше учитывать общеупотребительные частотные слова, и больше учитывать специфические термины. Кроме того, если она ниже порога, то мы считаем, что предложения не связаны. Для работы метода необходимо посчитать IDF на всём текстовом корпусе, что затрудняет его применение в отдельных случаях. В остальном этот метод аналогичен TextRank. Доступен в sumy, lexrank.


Латентно-семантический анализ


Латентно-семантический анализ — метод на основе сингулярного разложения матрицы инцидентности предложений и слов.


Пусть нам дана матрица инцидентности предложений и слов $A$, то есть $\text{A}_{ij}$ — частота i-го слова в j-ом предложении. Делаем её сингулярное разложение, описываемое формулой ниже, где $\Sigma$ — диагональная матрица с неотрицательными элементами, у которой элементы, лежащие на диагонали — это сингулярные числа, а матрицы U и V — это две унитарные матрицы, состоящие из левых и правых сингулярных векторов соответственно.


$A = U\Sigma V^T$


При этом i-ый столбец матрицы $V^T, \psi_i = [v_{i1}, v_{i2} \ldots v_{ir}]^T$ соответствует i-ому предложения текста, его элементы — величине присутствия в этом предложении одной из тематик, а диагональные элементы матрицы $\Sigma$ — "силе" тематики.


То есть k-ый правый сингулярный вектор соответствует k-ой тематике, а когда мы берём максимальное значение в этом векторе — мы берём предложение, которое лучше всего описывает эту тематику.


В итоге алгоритм сводится к тому, что мы оставляем сколько-то самых значимых тематик, исходя из элементов $\Sigma$, и проходимся по столбцам матрицы $V$, перемножая квадраты элементов матрицы $\Sigma$ и квадраты соответствующих элементов столбца. Предложения с максимальной суммой по всем значимым тематикам включаем в реферат. Этот метод хорош тем, что мы явно используем разбивку документа по тематикам. Доступен в sumy.


MMR


MMR (Maximal Marginal Relevance) — техника для реферирования по запросу, которая максимизирует похожесть фрагментов реферата на запрос и минимизирует похожесть на уже выбранные в реферат фрагменты.


Метод описывается формулой ниже. На вход подаются запрос Q, множество всех фрагментов R, множество уже выбранных фрагментов S. Мы ищем новый фрагмент из $R\setminus S$ так, чтобы он был максимально похож на запрос, и минимально похож на уже выбранные фрагменты.


$ MMR_{\alpha}(Q, R, S) = \max_{S_i \in R\setminus S} \left(\alpha (\text{sim}_1(S_i, Q)) - (1-\alpha)\max_{S_j \in S} \text{sim}_2(S_i, S_j) \right)$


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


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


Заключение


Все методы, описанные выше, довольно старенькие, но от того не менее полезные. Многие из них позволяют доработку с помощью современных моделей. Например, можно заменить подсчёт схожести в TextRank на косинусное сходство между любыми текстовыми эмбеддингами вроде USE или LaBSE.


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


Сопроводительный код в Colab: ссылка.


В следующих статьях цикла мы рассмотрим намного более хайповые вещи: рекуррентные сети, модели на основе трансформеров: кодировщики, декодировщики и sequence-to-sequence модели, такие как BERT, GPT, BART, T5 и PEGASUS, а также обязательно затронем вопросы об оценке качества автоматического реферирования. Надеюсь, что этот мини-обзор был полезен, увидимся в следующих статьях!

Комментарии (6)


  1. dimnsk
    14.12.2021 20:57
    #23821023

    а может вместо формул
    приводить простейшие примеры на Python (colab) ?


    1. Takagi Автор
      14.12.2021 21:01
      #23821037
      +2

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


    1. Takagi Автор
      15.12.2021 22:19
      #23826269
      +2

      Собственно код с объяснениями для всех методов, кроме MMR. В том числе для TextRank поверх LaBSE.


  1. Gorodecki
    14.12.2021 22:40
    #23821385

    Илья, спасибо! Особенно полезно про фишку соединения TextRank + энкодеров. Жду следующей статьи про метрики!


  1. nikolay_karelin
    14.12.2021 23:05
    #23821457

    Обзор хороший. Было бы классно и всю диссертацию увидеть...


    1. Takagi Автор
      14.12.2021 23:09
      #23821477
      +1

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