Современные аспекты представления текстов при анализе естественного языка: классические и альтернативные подходы

Введение

В computer science из года в год все более популярной становится тема обработки естественного языка. Из-за огромного количества задач, где требуется подобный анализ, сложно переоценить необходимость автоматической обработки текстовых документов.

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

Отметим, что приводимые подходы применимы не только к текстам, а вообще к любым объектам, которые можно представить в виде символьных последовательностей, например, какие-нибудь макромолекулы (ДНК, РНК, протеины) из генетики. Всего мы рассмотрим 4 метода:

1. Признаковое описание.
2. Попарное наложение (выравнивание) текстов.
3. Формирование профиля и скрытой марковской модели.
4. Представление фрагментами.

Итак, приступим.

Признаковое описание

Признаковое описание — подход, который можно назвать классическим при анализе естественного языка. Он подразумевает, что из анализируемых текстовых документов выделяется определенное количество признаков, например, слов, или пар подряд идущих слов (так называемых биграмм). Признаки можно фильтровать, например, по частоте встречаемости в наборе документов, или же убирать из их списка те, которые не представляют интереса — например, предлоги или союзы («стоп-слова»). Далее каждый документ характеризуется количеством вхождений в него данных признаков, или же, например, их наличием/отсутствием, что удобно представлять в виде вектора, где каждый элемент соответствует определенному признаку. Их порядок, естественно, должен быть фиксирован заранее. Отметим, что важной задачей является выявление одних и тех же признаков в разной форме — например, удобно считать, что «Катей» и «Катя» — это один и тот же признак. Для этого применяют процессы стеммирования, при котором рассматриваются только основы слов (чаще всего, корни, а приставки, суффиксы, окончания отбрасываются) или лемматизирования, когда все слова приводятся к «нормальной форме», например, в русском языке существительные удобно приводить к форме именительного падежа в единственном числе. Второй процесс почти всегда сложнее, часто нужно иметь базу словоформ (без них, например, для слова «люди» не получить нормальную форму «человек»), тогда как для первого процесса для многих языков достаточен список правил преобразования слов.

Например, пусть нам дан текст, взятый из прекрасного стихотворения Н. Гумилева «Жираф»:

Послушай: далеко, далеко, на озере Чад
Изысканный бродит жираф.

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

(слушать, далеко, озеро, Чад, изысканный, бродить, жираф)

Предлог «на» не берем как стоп-слово. Если теперь представить первую строку данного нам текста в векторной форме на основе вышеприведенного списка, мы получим следующий вектор:

(1, 2, 1, 1, 0, 0, 0)

Полученные вектора можно объединять в матрицу, измерять различные расстояния (коих существует великое множество) между ними, применять к ним техники преобразования частот (TF-IDF, например — но в этом случае для адекватной его работы количество признаков и документов должно быть достаточным).

Наложение последовательностей, формирование профилей

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

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

Фрагментное представление

И, наконец, последний подход, на котором мы и остановим внимание, это фрагментное описание текстов. В этом подходе используются так называемые аннотированные суффиксные деревья. Аннотированное суффиксное дерево (АСД) — это структура данных, используемая для вычисления и хранения всех фрагментов текста совместно с их частотами. Она задаётся как корневое дерево (то есть одна вершина в нем выделена и именуется корнем), в котором каждый узел соответствует одному символу и помечен частотой того фрагмента текста, который кодирует путь от корня до данного узла.
При использовании АСД весь текст разбивается на строки — цепочки символов. Как правило, одна строка формируется из 2-4 подряд идущих слов. Пример АСД для короткой строки показан на рисунке ниже.

Суффиксом длины строки длины ( ), состоящей из символов , называется подстрока . Например, для строки суффиксом длины 2 будет являться подстрока . Приведем неформальное описание алгоритма построения АСД по заданной строке .

1. Инициализировать пустую структуру для хранения АСД — . Эта структура должна иметь возможность хранить дерево с символами и числами (их частотой) в узлах.
2. Найти все суффиксы строки: .
3. Для каждого суффикса ищем в такой путь от корня, что совпадение с началом суффикса максимально по длине — . Для всех символов, попавших в совпадение , увеличиваем частоту соответствующих узлов на 1.
4. Если совпадение по длине меньше , значит, суффикс не пройден до конца. Тогда в необходимо создать новые узлы, присвоив им частоту 1.

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

Введем понятие условной вероятности узла в АСД с корневой вершиной . Частоту узла обозначим через . Тогда условная вероятность узла равна:

где — предок узла в дереве . Для тех вершин, для которых предком является корневая вершина , формула принимает вид:

где множество есть ничто иное, как множество всех узлов на первом уровне дерева.

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

Тогда оценка степени вхождения строки в дерево определяется как

При сравнении степеней вхождения строки в два и более АСД формулу необходимо модифицировать, поделив на длину найденного вхождения.

Если потренироваться и вычислить по этой формуле степени вхождения в АСД некоторых строк в приведенное на рисунке выше дерево, то мы получим следующую табличку:

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

Преимущества фрагментного представления

Отметим преимущества этого подхода по сравнению с признаковым методом. Признаковые подходы гораздо хуже чувствуют глубокую «структуру» текста, даже при использовании в качестве признаков биграмм (или даже более длинных последовательностей слов — триграмм, и т. д., что, кстати, очень сильно увеличивает размерность векторов). Кроме того, для фрагментного подхода не требуется производить приведение слов к нормальным формам (если оно, конечно, использует только правила преобразования, а не базы словоформ) — если слово входит в АСД, то и его основа, очевидно, расположится в АСД на какой-нибудь ветви. Но самое главное — это то, что фрагментный подход терпим к незначительным ошибкам в текстах. Безусловно, есть и специальные методы, позволяющие учить этому и признаковые подходы, но это часто очень усложняет алгоритмы. Объясним подробнее на примере конкретного примера из нашей компании.

Технология контекстного таргетинга товаров партнерских магазинов в SlickJump базируется на вероятностной тематической модели LDA (скрытое размещение Дирихле), работающей с признаками. Вообще вероятностное тематическое моделирование — это отдельная обширная и интересная тема, в нее лезть мы если и будем, то не в этой статье. Отметим лишь, что такой подход позволяет решать задачу нахождения степеней близости документов (т.е. контекста и предлагаемых товаров), причем решать ее для огромного числа документов — а товаров партнерских магазинов в базах нашей компании более 2 млн.

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

Пусть у нас есть баннеры магазина электроники, предлагающие модные аксессуары для смартфонов со скидками. И форум о мобильной технике в качестве рекламной площадки. Рекламодатель указывает список ключевых слов для своих баннеров или предоставляет сделать это нам (что удобно, когда число баннеров исчисляется тысячами, у нас есть соответствующий функционал). Мы должны подобрать релевантные контексту (как правило, веб-странице, сообщению на форуме и т.д.) баннеры. Сравним две модели контекстного таргетинга: LDA (на основе признаков) и нашу модель на основе АСД, и узнаем, будут ли найдены релевантные баннеры при двух разных ситуациях: когда люди пишут правильно и когда они допускают ошибки.
Если бы все люди писали без ошибок, никаких проблем с контекстным таргетинга никогда бы не возникало. Если есть ключевое слово «зарядное устройство», а в тексте сообщений где-то указано «зарядка», то никаких проблем с таргетингом не возникнет благодаря процессу нормализации признаков. Скриншот ниже показывает, что обе модели нашли релевантные баннеры.

А вот если человек написал hts вместо htc (хоть и примитивный пример, но классика жанра), все намного интереснее. Попробуем найти баннеры, релевантные данному слову. Модель LDA, основанная на признаковом подходе без специальных приспособлений, не найдет ничего (или ничего адекватного, что тоже плохо). А метод, основанный на АСД, выдает прекрасный результат, даже несмотря на то, что в слове целая одна ошибка на всего три буквы. Это продемонстрировано на скриншоте ниже, где показаны соответствующие названия товаров, найденных по запросу.

Заключение

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

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

Список литературы для чтения по теме

1. Маннинг К. Д., Рагхаван П., Шютце Х. Введение в информационный поиск. М.: Вильямс, 2011
2. Миркин, Б. Г. Методы кластер-анализа для поддержки принятия решений: обзор. М.: Издательский дом Национального исследовательского университета «Высшая школа экономики», 2011
3. Миркин Б. Г., Черняк Е. Л., Чугунова О. Н. Метод аннотированного суффиксного дерева для оценки степени вхождения строк в текстовые документы. Бизнес-информатика. 2012. Т. 3. № 21. С. 31-41.
4. Дубов М. С., Черняк Е. Л. Аннотированные суффиксные деревья: особенности реализации. В кн.: Доклады всероссийской научной конференции АИСТ-2013 / Отв. ред.: Е. Л. Черняк; науч. ред.: Д. И. Игнатов, М. Ю. Хачай, О. Баринова. М.: Национальный открытый университет «ИНТУИТ», 2013. С. 49-57.
5. Mirkin B. G., Core Concepts of Data Analysis. Springer, 2012
6. Коршунов А, Гомзин А. Тематическое моделирование текстов на естественном языке. Труды ИСП РАН. 2012. №. С.215-244.
7. Steven Bird, Ewan Klein, Edward Loper. Natural Language Processing with Python. OReilly Media, 2009

Автор: dmitsf

Источник