LexRank

LexRank — это алгоритм автоматического реферирования текстов, основанный на методах машинного обучения и теории графов. Он относится к классу экстрактивных методов суммаризации, то есть выделяет наиболее значимые предложения из исходного документа и формирует из них краткое содержание (реферат). Алгоритм был предложен в 2004 году группой исследователей из Колумбийского университета (США) — Гюнешем Эрканом и Драгомиром Радевым.

Принцип работы

LexRank использует подход, аналогичный алгоритму PageRank, применяемому поисковой системой Google для ранжирования веб-страниц. В основе лежит построение графа, где вершинами являются предложения исходного текста, а рёбрами — связи между ними, определяемые мерой семантической близости (сходства).

Построение графа сходства

1. Токенизация и предобработка: Исходный текст разбивается на отдельные предложения. Каждое предложение проходит этапы нормализации: удаление стоп-слов (предлогов, союзов, частиц, не несущих смысловой нагрузки), приведение слов к начальной форме (стемминг или лемматизация).
2. Векторизация: Каждое предложение преобразуется в числовой вектор. Чаще всего используется модель TF-IDF (Term Frequency — Inverse Document Frequency). Вектор отражает частоту встречаемости каждого слова в предложении (TF) с поправкой на его редкость во всём корпусе предложений (IDF). Таким образом, редкие и характерные для темы слова получают больший вес.
3. Вычисление сходства: Для каждой пары предложений рассчитывается косинусное сходство (cosine similarity) между их векторами. Значение сходства лежит в диапазоне от 0 (полное отсутствие общих слов) до 1 (идентичные векторы).
4. Формирование графа: Создаётся взвешенный неориентированный граф. Вершины — предложения. Ребро между двумя вершинами проводится, если косинусное сходство между соответствующими предложениями превышает заданный порог (обычно 0,1–0,3). Вес ребра равен значению косинусного сходства.

Ранжирование предложений (алгоритм PageRank)

После построения графа к нему применяется итеративный алгоритм PageRank. Идея заключается в том, что «важность» (ранг) предложения определяется количеством и «важностью» предложений, которые на него ссылаются (то есть имеют с ним высокое сходство). Формула расчёта ранга предложения \( S(v_i) \) выглядит следующим образом:

\[ S(v_i) = (1 — d) + d \cdot \sum_{v_j \in In(v_i)} \frac{w_{ji}}{\sum_{v_k \in Out(v_j)} w_{jk}} S(v_j) \]

Где:

• \( S(v_i) \) — ранг предложения \( v_i \).
• \( d \) — коэффициент затухания (damping factor), обычно принимается равным 0,85 (как в оригинальном PageRank). Он моделирует вероятность перехода пользователя к случайному предложению, а не по ссылке.
• \( In(v_i) \) — множество предложений, имеющих рёбра к \( v_i \).
• \( Out(v_j) \) — множество предложений, к которым ведут рёбра от \( v_j \).
• \( w_{ji} \) — вес ребра между \( v_j \) и \( v_i \) (косинусное сходство).

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

Формирование реферата

Предложения сортируются по убыванию полученного ранга. В итоговый реферат включается заданное количество предложений с наивысшими баллами (например, 5–10% от исходного текста). При этом часто применяется эвристика для устранения избыточности: если два высокоранговых предложения практически идентичны по смыслу (их сходство превышает, например, 0,9), одно из них может быть исключено.

Отличия от TextRank

LexRank часто сравнивают с другим популярным графовым алгоритмом — TextRank (предложен в 2004 году Михалиной и Тарау). Основные различия:

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

Применение

LexRank нашёл широкое применение в системах автоматической обработки текста (NLP):

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

Ограничения и критика

Несмотря на эффективность, LexRank имеет ряд недостатков:

1. Зависимость от качества предобработки: Алгоритм чувствителен к выбору стоп-слов и методу стемминга/лемматизации. Ошибки на этом этапе могут снизить точность.
2. Чувствительность к порогу сходства: Неправильный выбор порога может привести либо к слишком разреженному графу (потеря связей), либо к слишком плотному (все предложения становятся одинаково «важными»).
3. Неспособность к генерации: LexRank, как экстрактивный метод, не может создавать новые фразы или перефразировать. Он лишь копирует существующие предложения, что может приводить к неграмматичным или нелогичным рефератам.
4. Игнорирование порядка предложений: Алгоритм не учитывает последовательность предложений в исходном тексте, что может нарушить логику изложения в итоговом реферате.
5. Склонность к длинным предложениям: Векторы длинных предложений содержат больше слов, что может приводить к искусственному завышению их косинусного сходства с другими предложениями и, как следствие, к более высокому рангу.

Реализации

Алгоритм LexRank реализован в нескольких популярных библиотеках для Python:

• Sumy: Простая библиотека для суммаризации текста, включающая реализацию LexRank.
• Gensim: Библиотека для тематического моделирования, содержит модуль summarization с реализацией LexRank (начиная с версии 0.13.0).
• LexRank (авторская реализация): Оригинальный код, опубликованный авторами алгоритма, доступен на GitHub.

Источники

1. Erkan, G., & Radev, D. R. (2004). LexRank: Graph-based Lexical Centrality as Salience in Text Summarization. Journal of Artificial Intelligence Research, 22, 457–479.
2. Mihalcea, R., & Tarau, P. (2004). TextRank: Bringing Order into Text. Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing (EMNLP), 404–411.
3. Manning, C. D., Raghavan, P., & Schütze, H. (2008). Introduction to Information Retrieval. Cambridge University Press. (Глава 21, посвящённая суммаризации).
4. Документация библиотек Sumy и Gensim (раздел, посвящённый суммаризации текста).