Быстрый морфологический алгоритм подбора неизвестного для поисковой системы слова с помощью словаря

Илья Сегалович (Яндекс, Москва)

Аннотация

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

Преамбула: нужна ли морфология поисковой системе?

Некоторые исследования в сфере информационного поиска показали, что при введении морфологического анализа эффективность поиска не изменяется или повышается слишком несущественно [harman1991]. И хотя полученные позже результаты показали явную пользу введения анализа даже в такие языки, который используют всего несколько словоформ (как, например, английский), по-прежнему открыт вопрос, нужен ли он вообще в поисковых системах. Google, поисковая система №1 в мире утверждает, что намеренно не использует стемминг (процесс нахождения основы слова, при этом основа – необязательно корень), чтобы обеспечить пользователей более точными результатами поиска [google1998]. Такая категорическая позиция была приемлема в конце 90-х, до того как анализ ссылок повысил точность веб-поиска. Но разве это означает, что стоит игнорировать полноту выдачи? Существует несколько аргументов, поддерживающих это утверждение. Число страниц, выдаваемых поисковиками, распределяется по закону Ципфа (закономерность распределения частоты слов языка: если все слова упорядочить по убыванию частоты, то частота n-ного слова обратно пропорциональна его порядковому номеру n). Это значит, что несмотря на то, что количество страниц в выдаче по популярным запросам очень велико, запросы с всего несколькими результатами остаются важными. К примеру, более 30% выдачи yandex.ru 06.09.2011 имели менее 100 документов и при этом только 5-10% запросов были написаны с ошибками.

Поведение пользователя, координирующее ранжирование и морфология

Следующим замечанием в пользу морфологической обработки в Сети является поведение и ожидание пользователей. Пользователи по-своему представляют работу поисковых систем [muramatsu2001] и обычно предпочитают координирующее ранжирование [heimstra2002]. Для удовлетворения ожиданий пользователя (здесь мы не считаем точность и полноту главными целями) поисковые системы в первую очередь ищут точное совпадение по фразам. Когда это невозможно (более 50% запросов не имеет совпадающих фраз в Сети вообще), поисковая система ранжирует результаты в соответствии с термином «близость» [muramatsu2001] таким образом, чтобы они оказались максимально релевантны запросу. Смотря на типичную выдачу поисковика, можно заметить, что результаты грубо отсортированы в убывающем порядке по «похожести» запроса и сниппетов (мета-тэгов description) веб-страниц. В то же время 75% поисковых запросов состоят более чем из одного слова [onestat2003]. Тогда почему «сходство» результатов и длинных запросов допускает вставку крупных групп символов (слов, предложений) между словами запроса, но не допускает незначительных изменений в окончаниях похожих слов (шапки, шапок, шапка)?

Введение и современные тенденции

Современные алгоритмы морфологического анализа основываются на Преобразователях Конечного Состояния разных видов (Finite State Transducers – FST, частный случай конечного автомата. Это абстрактный автомат без выходного потока, имеющий определённое количество состоняий. По состоянию определяется результат работы автомата.) В FST ([kimo1983], [kartunen1992], [mohri2000], [daciuk2000]) фонологические правила записаны вручную и каждому слову из словаря назначена соответствующая модель (флективная – модель словоизменения, деривационная – модель словообразования). Эти преобразователи выполняют как анализ, так и синтез словоформ. FST отличаются высокой скоростью и надёжностью. К сожалению, количество неизвестных лексических единиц, найденных в Сети с каждой сессией краулинга очень велико. Оно может быть оценено законом Хипса V_R = Kn^β, где V_R соответствует части словаря, представленной образцом текста размера n. K и β – коэффициенты, определяемые эмпирически. В Сети значение β ближе к 1.0, чем к 0.5 из-за случайных и специальных (например, мемы или сленг) грамматических ошибок, иностранных слов, неологизмов из блогов и т.д. Это означает, что словарь растёт сублинейно с ростом индекса. Проще всего, конечно, игнорировать слова, не входящие в главный словарь, в надежде, что его охвата будет достаточно [aport.ru].

С недавних пор проблема морфологического анализа неизвестных слов привлекает всё больше внимания, главным образом из-за успеха в бесконтрольном машинном обучении (unsupervised learning, система сама учится выполнять задачу без вмешательства человека) морфологии из корпуса языков. Корпус – систематизированная и размеченная по лингвистическим стандартам часть языка в виде информационно-справочной системы. [Jackubin1997] проанализировал статистику k-n пересечений (где k – длина предполагаемого окончания слова, обычно 3 буквы, а n – ширина контекстного «окна», обычно 2 слова) и получил отличные результаты по сравнению со знаменитыми самописными стеммерами Lovins и Porter ([lovins1968], [porter1980]). [gaussier1999] применил аналогичный подход (p-сходство – число общих букв в паре слов) для изучения деривационных морфологических семейств и даже деривационных древ. Более общие подходы анализа окончаний в корпусе представлены в [goldsmith2001] и [snover2002]. Они используют известный из теории информации принцип MDL (Minimum Description Length, минимальная длина описания) для создания набора стемов (неизменяемая основа слова без аффиксов и окончаний, выражающая его лексическое значение), словоизменительных парадигм (к примеру, таблиц склонения и спряжения) и приставок, которые могут быть закодированы в минимальном числе битов [goldsmith2001], таким образом делая морфологическое описание корпуса минимальным (Brent). Linguistica [goldsmith2011] также является публично доступной программой, которой мы позже воспользуемся в этой статье.

Ещё один перспективный метод [schone2001] использует контекст слов для поиска предполагаемых моделей слов, полученный только из анализа окончаний. Он использует основу ППМВ (PPMV, pair of potential morhopogical variants) – пар потенциальных морфологических вариантов и измеряет семантическое сходство между ними, под которым понимается нормализованная корреляция между их векторами в латентном семантическом пространстве (разложенная с помощью LSI матрица соседей «слово-в-слово»).

[LSI (latent sbantic indexing) или Латентное Семантическое Индексирование – это техника индексации и поиска, которая использует математический метод сингулярного разложения для идентификации шаблонов взаимодействия между выражениями и понятиями в текстах (вне систематизированного корпуса). LSI основан на том принципе, что слова, использующиеся в одинаковом контексте похожи по смыслу (значению). Ключевой особенностью LSI является возможность получения концептуального содержания текста, устанавливая ассоциации между теми понятиями, которые проявляются в похожих контекстах. Сингулярное разложение – это разложение (факторизация) прямоугольных комплексных или вещественных матриц, использующееся в прикладной математике.]

Все вышеупомянутые методы бесконтрольны в том смысле, что они не используют никаких предварительно введённых данных о языке и его морфологических моделях. К сожалению, есть как минимум два препятствия, которые не позволяют напрямую использовать бесконтрольные методы в поисковых системах. Первым является точность морфологии большинства используемых слов, которая обязана быть максимальной. Вторым является постоянный рост сложности обновления индекса: индекс распределяется между сотнями и тысячами компьютеров, поэтому морфологическая интерпретация новых слов, найденным в процессе краулинга, не должна меняться слишком часто, иначе потребуется ежедневное пропатчивание всего индекса. Следует заметить, что если у языка есть сформированный веб-корпус, достаточно большой, чтобы его нельзя было проигнорировать, то, скорее всего, уже существуют словари с информацией об этом корпусе. Например, широко распространённые программы проверки ошибок, использующие краткое описание всех возможных словоформ, такие как [ispell] или [aspell] имеют словари для 37 и 26 языков соответственно. Конечно же, задача создания компактного сборника всех возможных словоформ в языке – не совсем та же, что и задача описания всех слов и соответствующих лингвистических парадигм, однако эти словари успешно используются в поисковых системах ([mnogosearch], [glimpse], [aspseek] и т.д.). Важным замечанием о существующих словарях является то, что они всегда описывают наиболее часто используемые слова в языке. Мы предполагаем, что все комплексные и необычные (флективные/деривационные) модели всегда относятся к наиболее используемым словам языка – что, по своей сути является ещё одним законом Ципфа – «чем выше частота слова, тем больше число морфологически сложных форм, в которых оно будет использовано» [manning1999].

Идея использования относительно небольшого словаря для определения морфологии новых слов сама по себе не нова. Например, [woods1999] использовал ряд жёстких правил и небольшой словарь, чтобы расширить лексический охват. [mikheev1995] разработал технику автоматического сбора морфологии неизвестных слов при помощи общего (простого) словаря и частоты слов. Классический русский алгоритм морфологии [belongov1985] использует один и тот же словарь как для известных, так и для неизвестных слов, к тому же, все FST-машины позволяют запись всеобъемлющих (абсолютных) правил для слов вне словаря. В то время как процесс описания морфологии отдельного слова достаточно точен, всеобъемлющие правила довольно сложно создавать без ошибок. Вариант применения к корпусу однократной обучающей процедуры вместе с существующим морфологическим словарём для получения идентификатора морфологии представлен [kovalenko2002].

Метод, описанный здесь основывается на [segalovich1998] и использует очень простую идею морфологического сходства. Морфология неизвестного слова берётся из всех ближайших слов в словаре, где близость определяется количеством букв в конце слова. Отличие от подхода [belonogov1985] состоит в том, что выбирается не один вариант, а все возможные, имеющие одинаковую длину, и в отличие от [kovalenko2002] описанный метод использует для поиска гипотетических слов весь словарь, а не N последних букв стемов. Для создания подобного словаря нам не требуется знать морфемную структуру каждой отдельной морфологии, т.к. компилятор принимает входные данные в виде полного списка всех парадигм слова из словаря. Если доступны грамматические теги (см. определение ниже), то они так же принимаются. Такой словарь может не только анализировать известные слова, но так же и синтезировать все известные и предполагаемые словоформы. Алгоритмическая идея состоит в том, что во время анализа слова, когда мы пытались найти его точную форму в словаре, мы уже имеем достаточно информации (все буквы слова уже просмотрены), чтобы найти наиболее вероятный неточный эквивалент. Так же и FST-метод использует один заранее созданный алгоритм с точными всеобъемлющими правилами, но нам, в отличие от [Karttunen1992], эти правила не нужны. Наоборот, мы считаем такие правила вредоносными и полностью полагаемся на вероятностную природу анализа неизвестных слов. В этом и заключается идея алгоритма – использовать предопределённые правила там, где возможно (для всех известных слов) и вероятностный подход, когда конкретная интерпретация недоступна.

Интересным применением этого алгоритма является комбинированный словарь нескольких языков, который полезен в ситуациях, когда язык не определён: тогда словарь будет выбирать наиболее близкие морфологические интерпретации, основанные на похожести со всеми словами всех языков. (Такой комбинированный польско-английский словарь используется в нашем экспериментальном проекте yandex.pl как часть программы интерпретации запросов).

Конструктивные особенности

Существует ряд вопросов о морфологической модели и алгоритмах, на которые необходимо ответить до описания самого алгоритма. Все они происходят из природы информационного поиска, технических требований поисковых систем и задач на продвижение сайтов. Какой вид морфологического анализа использовать: флективный или деривационный? Требуются ли грамматические теги (POS, part-of-speech теги – метки признаков, определяющие к какой части речи относится слово) в качестве результата анализа? Нужны ли нам стемы или нормальные формы слова (другими словами – стемминг или лемматизация)? Как обрабатываются неизвестные слова? Нужно ли принимать во внимание контекст слов для улучшения анализа? Зависит ли анализ от корпуса и если да, то в какой степени? Чтобы полностью ответить на все эти вопросы, потребуется гораздо большая статья, но вкратце ответы такие: флективная, грамматические теги не требуются, лемматизация, контекст не используется. Краткое объяснение приводится ниже.

[Стемминг – процесс нахождения основы слова для данного исходного слова. Основа слова не всегда совпадает с корнем. Лемматизация – процесс привода словоформы к лемме. Лемма – нормальная (словарная, каноническая) форма слова (к примеру, в русском языке лемма существительного – именительный падеж, единственное число). Run – лемма лексемы (группы) слов run, runs, ran и running.]

Флективная морфология. Ради точности мы не хотим использовать деривационную морфологию, хотя разница между морфологиями едва различима; например, род существительного, уменьшительно-ласкательная форма.

Отсутствие грамматических (POS) тегов. У разных языков разная морфология со своей грамматикой и ПМ часто не может определить ни язык запросов (пользователи никогда не выбирают нужный), ни веб-страниц (учитывая мультиязыковые документы, технические документы и т.д.). Поэтому ключи индекса (массивы) должны отражаться только в виде текста без грамматических или языковых тегов.

Леммы, а не стемы. Стемминг объединяет не только различные части речи или деривационные формы (которые нам не нужны), но также и создаёт вредоносные ассоциации. Поэтому поисковым системам требуются словарные формы (леммы) как результат морфологического анализа. В свою очередь это открывает вопрос устранения различий между словоформами, если мы полностью уберём POS-тэги. Нужно учитывать разные части речи, см. stocking -> (от сущ. stock (склад) ИЛИ прилаг. stocking (хранящийся)).

Анализ контекста. Сам морфологический алгоритм не должен опираться на контекст слов или на допущение, что все слова (в запросе) будут находиться в том же порядке, что и в тексте. Если требования современных ПМ к скорости индексирования не допускают этого (обычная скорость 50-100 документов в секунду [najork2001]), то морфологический модуль вызывается в мультипоточной среде каждый раз, когда словоформа встречается в части текста.

Двусмысленность. Важно отметить, что неоднозначность слов не превышает 10-20% от размера индекса. К тому же, устранение лингвистической неоднозначности в коротких запросах невозможно (фактически, более выгодно использовать согласованное ранжирование (coordination ranking) при нелингвистической неоднозначности).

Алгоритм

Словарь представлен рядом (префиксных) древ [cormen1990] инвертированных стемов и древом всех возможных суффиксов (здесь: суффиксы = окончания). Связь между стемом и суффиксом берётся или из файла, если он явно указан, или же рассчитывается автоматически как длина общей части всех словоформ в парадигме [склонений или спряжений]. Далее следует описание алгоритма.

• Анализировать слово с правой стороны, используя древо всех возможных суффиксов. В результате получается набор всех возможных позиций границы стемасуффикса за один заход.
• Начиная с самых глубоких границ стема/суффикса выполнить шаги 3-7.
• Использовать последние две буквы возможного стема в качестве индекса, чтобы получить подходящее древо стема. Если ни у одного стема нет этих двух букв, перейти к следующей границе.
• Анализировать полученное древо стемов и попытаться найти конечный лист (terminal leaf) на границе слова, запоминая все точки ответвления в один заход.
• Слово из словаря. Если нашёлся конечный лист на границе слова, сравнить соответствующую флективную модель (её идентификатор хранится в древе стемов в виде специальной буквы после первой буквы стема) с суффиксом слова. Если они совпадают, это значит, что мы нашли слово в словаре.
• Неизвестное слово. Если конечного листа нет или флективная модель не соответствует суффиксу, выполнить следующие шаги.
• Просмотреть в объявленном порядке (траверсировать) все собранные ранее точки ответвлений в древе стемов, начиная с первой границы и найти все потенциальные стемы-кандидаты, которые могут быть моделями для данного неизвестного слова. Проверить все эти флективные модели по данному суффиксу.

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

Обучение. Эвристически в алгоритм были встроены следующие правила: финальный стем должен содержать гласную, стемы-модели должны по возможности иметь качественные POS-тэги, должна быть задана минимальная длина стема, должна быть задана минимальная длина общей части модели и неизвестного слова, парадигмы модели должны иметь минимальную частоту (например, встречаться минимум дважды в словаре).

Так же весьма полезно [segalovich1998] использовать статистику из корпуса для базовой лексической идентификации и удаления лишних морфологических вариантов: удалять леммы с парадигмами, полностью включённых в образцы других лемм (к примеру shmocking — (shmock | shmocking), shmockings — (shmocking), но из леммы нельзя исключать schmock или shmocked; или наоборот, если встречается shmocking, shmock и shmoked без shmockings, можно удалить лемму shmocking), предпочитать парадигмы с большим количеством лемм, предпочитать парадигмы, которые содержат леммы в корпусе, и т.д. Эти и другие выводы могут быть получены при изучении корпуса. В любом случае, в этой статье мы фокусируемся на качестве самой морфологии и не считаем фазу определения значений её частью.

Эксперимент

Несмотря на то, что наш словарь создан для нескольких языков (в теории – для всех, имеющих словари с полным описанием лингвистических парадигм, на практике – только для русского, польского и английского), мы решили проверить качество алгоритма на примере русского языка. Русский был выбран в первую очередь из-за того, что с его морфологией мало что может сравниться. За последние несколько лет появилось как минимум 3 новых программы, которые справлялись с русской морфологией. Новая версия стеммера от Porter [snowball] использует несколько правил на языке программирования “snowball”. “Linguistica” [goldsmith2001] изучает морфологию из корпуса. «Stbka» [kovalenko2002] – русско-украинский идентификатор морфологии, который был создан с помощью специально разработанного морфологического модуля, основанного на [Zaliznak1980] и собранной статистике из корпуса. Из-за того, что он создаёт несколько вариантов стемов для каждого слова, мы определяем две крайности: самый глубокий или же агрессивный анализ и поверхностный консервативный анализ. “Mystb” – описанный здесь алгоритм (изначально был создан в 1996 как стадия разработки поисковой машины Яндекса). Он использует полный словарь [Zaliznak1980] в качестве идентификационной основы, в описанном выше смысле.

Ещё одна часть эксперимента рассматривает корпус с каноническим отображением (canonical mapping, вручную размеченные нормальные/словарные варианты) словоформ. Для этой цели мы использовали недавно появившийся ruscorpora.ru [ruscorpora2003], в корпусе которого тогда было 1302329 разбитых по морфологическим категориям слов. Как и корпуса CELEX и Brown, он содержит леммы, POS и прочие грамматические тэги для каждого слова. Сейчас (прим. пер. на момент написания статьи) он содержит 130823 разных слов и состоит из двух частей. Вторая часть (834255 слов) получена с помощью независимой морфосинтаксической программы, а меньшая первая часть (468074) была ранее обработана mystb, так что мы не включаём её в исследование.

Не вполне ясно, как сравнивать качество морфологических обработчиков в рамках информационного поиска. Очевидным способом является сравнивать индексы стемминга – overstbming и understbming (слишком сильная разбивка стеммингом или же недостаточная, overstbming (OI) и understbming (UI) индексы), которые должны быть получены экспериментально, судя по [Paice1996]. Традиционным подходом является использование различной морфологии в одной и той же поисковой системе и последующее сравнение изменений точности и полноты выдачи. Однако это не отразит эффективность метода, потому что, во-первых, в контексте данной работы полнота и точность не настолько важны, а, во-вторых, потому что различные ПМ будут использовать морфологию по-разному. Другим способом является сравнение отображения (PPMV [Shone2000]) с каноническим словарным отображениям, например, заданным вручную в размеченном корпусе. Но этот метод сильно зависит от грамматической модели, выбранной редакторами корпуса – например, спорные различия деривации от флективности (в русском языке лингвисты часто дискутируют о причастиях и глаголах, наречиях и прилагательных, и т.д.). Идеальным вариантом было бы сравнение семантического сходства между вариантами PPMV. Семантическое сходство часто рассматривается как контекстная взаимозаменяемость [manning1999] и было использовано подобным образом в [Shone2000], чтобы отсеять неверные PPMV. К сожалению, во флективных языках (латинский, немецкий, русский, семитские языки) сам контекст синтаксически зависим от рассматриваемой словоформы, что делает невозможным использование контекстных слов без какой-либо морфологической обработки. Ещё одной проблемой этого подхода является то, что каким бы большим не был корпус, он не содержит достаточно статистической информации, чтобы применять полученную семантику в масштабах Веба.

Мы предлагаем ещё один вариант измерения семантического сходства вариантов PPMV. Если две разных словоформы достаточно похожи, то они должны быть похожи и в пределах выдачи поисковой системы. Современные поисковики плотно используют статистику слов: обычно они стараются определить семантику как можно точнее социометрическими способами (например, через анализ ссылок) и используя любые доступные источники информации. Так же важны для поисковой системы данные, что при использовании других форм заданного слова, результаты будут на удивление релевантны. Рассмотрим пример на английском. Допустим, у нас есть два стеммера: №1 сопостовляет stockings со stock, а №2 сопостовляет stocking со stocking, а stocks со stock. Взяв первые N (30) результатов из выдачи Google, мы увидим, что stock и stocks имеют множество общих хостов (например, nasdaq.com), так же как и PPMV stocking/stockings (например, stockingstore.com). PPMV стеммера №1 (stockings/stock), конечно же, не имеет общих хостов. Таким образом, мы будем называть семантическим сходством двух разных запросов количество общих хостов первых 30 результатах в обоих списках выдачи. Но какие запросы следует использовать? В идеале, мы должны выбрать, например, 3 самых популярных запроса, содержащих определённую словоформу и сравнить их выдачу с аналогичными запросами-PPMV. В этом случае мы увидим реальную степень похожести и, кроме того, более точно узнаем, что пользователи подразумевают под какой-либо словоформой (определим её «значение»). Чтобы упростить задачу, мы использовали запросы, состоящие только из одного слова.

Мы применили всевозможные стеммеры к корпусу ruscorpora.ru и сравнили полученные PPMV от каждого стеммера с нормальными (каноническими) PPMV из корпуса. PPMV в нашем случае – это все пары, которые соответствуют данной текстовой информации – лемме или стему. Чтобы уменьшить образец выборки, мы оставили только те словоформы, которые встречаются в корпусе с частотой от 10 до 100, т.е. являются наиболее близкими к специфике темы.

После этого мы убрали все канонические PPMV, т.е. те, которые были взяты напрямую из мэппинга ruscorpora.ru. Таким образом, мы получили список и добавленных и удалённых PPMV для каждого стеммера. Задачей является измерение максимального эффекта (как положительного, так и отрицательного) влияния стеммера на поисковую систему. Фактически, мы используем корпус как источник новых слов и PPMV (так же как в процессе ежедневного краулинга) и используем семантическое сходство всего индекса, чтобы определить насколько не подходят PPMV, добавленные отдельным стеммером и насколько хороши те PPMV, которые стеммер исключил, по сравнению с каноническими PPMV. Мы взяли 30 наиболее часто встречающихся словоформ и их PPMV из обоих списков добавленных и удалённых (или же потерянных) записей каждого стеммера. Частота была взята из поискового лога яндекса (51387 слов, которые имеют частоту выше 100 в месяц за июль 2002).

Скорость вычислений

Все рассмотренные алгоритмы были написаны на C++ без использования виртуальных функций и шаблонов. Используя Pentium 4 1600 MHz, мы измерили скорость расчётов для 1 миллиона уникальных словоформ. Результаты показаны в таблице:

Выводы

В эксперименте мы постарались показать, что использование целого доступного словаря в качестве принципа автозаполнения превосходит использование морфологии, взятой исключительно из корпуса и заданные человеком правила вместе взятые. Несмотря на то, что число пар PPMV, выданных Mystb больше, чем в других алгоритмах, они намного точнее и нерелевантные хосты встречаются гораздо реже, к тому же, число потерянных хостов минимально. Метод с морфологией, взятой исключительно из корпуса (Linguistica) показал наихудшие результаты по парам PPMV и низкое число их семантических связей. Агрессивный анализ Stbka и Snowball выдал похожие результаты, несмотря на то, что Snowball – ряд созданных правил, а stbka – алгоритм, работающий с разбором окончаний в корпусе.