Данная статья посвящена описанию спектрального подхода в задачах обработки текстовой информации и, в частности, для решения задач информационного поиска. Проведено сравнение спектральной модели (Spectral Language Model - SLM) с популярными вероятностными моделями, такими как BM25 и DFR. Также представлена аппроксимированная спектральная модель, которая позволяет избавиться от главного недостатка SLM - громоздкой частотной базы.
1. Описание спектральной модели SLM В задачах обработки текстовой информации важнейшей проблемой является «взвешивание» лексических единиц. На текущий момент наиболее популярной и широко используемой для этих целей метрикой является IDF (Inverse Document Frequency) и различные функции от нее. Один из основных недостатков данной оценки – ее независимость от частоты слова внутри документа. Частично данная проблема решается использованием TF*IDF, где TF - относительная частота слова внутри оцениваемого документа, но при этом частота слова в других документах не учитывается. В [3] были предложены характеристики, основанные на распределении частот слова по всей коллекции, которые, в частности, позволили повысить качество решения поисковых задач. Наиболее эффективной с этой точки зрения оказалась характеристика, основанная на нормализованной частоте леммы слова.
Поэтому в дальнейшем данная метрика была взята в качестве базовой для спектральной языковой модели – SLM:
M
SF (L, nTF(L, d ))
) ,
(
На основе коллекций документов КМ.ru-2007 и BY.web-2007 для лемм всех слов были построены частотные базы, которые в дальнейшем использовались для исследования свойств спектральных характеристик, а также для их сравнения с другими частотными метриками.
Подчеркнем основные свойства спектральной модели, которые были выявлены на основе исследований.
1. Характеристика основана на эмпирических вероятностных распределениях слов по документам коллекции, а не на теоретических, как во многих других вероятностных подходах к взвешиванию слов, например в DFR [1].
2. Вес слова определяется уникальным для каждого слова спектром, в отличие от большинства других характеристик, в которых разные слова при одинаковых значениях TF и DF характеристик равнозначны.
3. Немонотонность изменения значений частотного спектра с ростом нормализованной частоты.
Так как для методов информационного поиска, составляющих одну из важнейших областей обработки текстовой информации, существуют доступные массивы данных (коллекции документов и таблицы релевантностей), позволяющие объективно оценить и сравнить различные технологии, то основные исследования спектральных характеристик были сосредоточены именно в области поисковых технологий. 2. Сравнение SLM с другими вероятностными моделями
В [4] на поисковой дорожке РОМИП-2010 было проведено сравнение двух поисковых методов: алгоритма на основе BM25 [2], показавшего лучшие результаты на предыдущем семинаре [5] и его модификации, путем замены BM25 на SLM. В результате, практически по всем оценкам качества, ответы SLM-алгоритма оказались лучше BM25-алгоритма. Т.е. простая замена BM25 на SLM в ранжирующем алгоритме дала прирост качества решения задачи информационного поиска. Однако, в сравнении, проведенном на РОМИП-2010, модели BM25 и SLM использовались лишь в виде отдельных факторов, вычисленных по различным структурным элементам документов. Поэтому, для того чтобы сравнить модели без учета влияния других параметров, было проведено дополнительное исследование моделей на основе таблиц релевантностей РОМИП за 2007– 2010 гг.
Для каждой сравниваемой модели (DFR, BM25, SLM) было использовано по 2 ранжирующих алгоритма:
– оценка релевантности документа определяется только по исследуемой модели
R1(q, d ) = ∑ M doc (q, d ) , (
L∈q
где q – запрос, d – оцениваемый документ.
– оценка релевантности документа определяется
по различным структурным элементам документа
R2(q, d ) = kdoc M doc (q, d ) +
+ktitleM title (q, d ) + kbeginM begin (q, d )
,
(
– Mdoc(q, d) – вклад всего документа в оценку его релевантности; – Mtitle(q, d) – вклад заголовка документа; – Mbegin(q, d) – вклад начальной части документа; – для SLM: M (q, d ) = ∑ SLM (L, d ) ;
L∈q – для BM25: M (q, d ) = ∑ BM 25(L, d ) ;
L∈q – для DFR: M (q, d ) = ∑ DFR(L, d) .
L∈q Полученные по каждому алгоритму ответы на запросы оценивались по таблицам релевантностей. Результаты оценок представлены в табл. 1–2. Таблица 1 Результаты сравнения алгоритмов R1
0,835 0,330 0,282 0,961 0,366 1,451 SLM 0,296 0,748 0,858 0,588 0,576 0,58 0,357 0,597 0,435 1,406 0,524 2,026 Таблица 2 Результаты сравнения алгоритмов R2 Как видно из таблиц, по обоим алгоритмам лучшие результаты по всем оценкам получила спектральная модель. В среднем оценки SLM выше на 10% по сравнению с BM25 и на 13% по сравнению с DFR, что считается существенной разницей. На рис. 1 представлен график TREC для ответов по алгоритму R1.
Рисунок 1. График TREC ответов по алгоритму
R1.
Из графика также видно, что точность результатов поиска при одинаковых значениях полноты у алгоритма на основе SLM выше, по сравнению с DFR и BM25. шее. Для того, чтобы оценить, насколько использование аппроксимации ухудшает качество решения поисковых задач, было проведено исследование, аналогичное сравнительному анализу SLM с другими вероятностными моделями. Результаты оценок представлены в таблицах 3–4. Таблица 3 Результаты сравнения алгоритмов R1
Таблица 4 Результаты сравнения алгоритмов R2 Evaluation\Systems 3. Аппроксимированная SLM
В целом полученные результаты позволяют говорить о том, что спектральная модель, по крайней мере на русскоязычных документах, дает более качественное решение поисковых задач по сравнению с другими методами. Однако спектральная модель обладает существенным недостатком – очень большой размер частотной базы. Если в большинстве вероятностных моделей на каждое слово в частотную базу заносится не более двух параметров, то здесь их число существенно больше. Один из способов уменьшения базы - выбор большего шага частотной дискретизации. Однако данный метод не решает полностью проблему размера частотной базы, т.к. уже при шаге больше 0,01, что соответствует разбиению области значений на 100 интервалов, наблюдается снижение качества решения задач на основе SLM.
Проведенные исследования показали, что спектры слов можно аппроксимировать с минимальными потерями качества решения поисковых задач функцией от 3 аргументов aSF(nTF,a,b) где a и b – параметры, которые определяются для каждого слова на основе метода наименьших квадратов. При этом сохраняется свойство уникальности спектра слов, а размер частотной базы существенно сокращается: на каждое слово необходимо хранить по 2 параметра.
Лучший результат из исследованных нами
функций показала степенная:
aSF(nTF, a,b) = a ⋅ nTFb . (
Рисунок. 2. Графики базовой SLM и аппроксимированной SLM местоимения «Я».
Как видно, визуально приближение исходной
спектральной модели функцией (
Из таблиц видно, что aSLM по обоим
алгоритмам улучшает качество решения поисковых задач:
по алгоритму R1 в среднем на 1%, по алгоритму R2
в среднем на 5%. Таким образом, использование
аппроксимированной модели на основе функции (