Главная   О компании   Разработки   АТ.Трейдинг  


АТ.Поиск   Сервисы   Форум

Сравнительный анализ спектральной языковой модели с другими моделями информационного поиска

И. Н. Зябрев, К. Н. Василенко, О. В. Пожарков, И. Н. Пожаркова, опубликовано в Вестник «СибГАУ» №3(36). Красноярск, 2011, стр. 26-29.



Проведено сравнение спектральной языковой модели (SLM) с наиболее широко используемыми в информационном поиске моделями, такими как DFR (Difference From Randomness) и BM25 с точки зрения оценки качества решения поисковых задач.

Данная статья посвящена сравнительному анализу качества решения поисковых задач на основе различных языковых моделей. Классическая задача информационного поиска формулируется в следующем виде. Существует множество (коллекция) документов D (d1,d2,…dM), M – его мощность и формализованный запрос q, выражающий информационные потребности пользователя поисковой системы. Требуется найти документы коллекции D, удовлетворяющие запросу q. Решение задачи обычно представляет собой список документов Drel, в порядке убывания их степени соответствия запросу (релевантности).

В настоящее время большинство алгоритмов оценки релевантности документов построено на основе таких моделей как BM25 [2] и DFR [1]. К основным достоинствам данных моделей можно отнести довольно высокое качество решения поисковых задач, малую вычислительную сложность и небольшой размер частотной базы, необходимой для вычисления оценок релевантности документов. Среди наиболее существенных недостатков большинства моделей информационного поиска, и в частности BM25 и DFR, стоит выделить унифицированное взвешивание отдельных слов документа, которое приводит к тому, что слова, имеющие одинаковые частоты в оцениваемом документе и во всей коллекции, будут давать одинаковый вклад в оценку релевантности, несмотря на их различную информационную значимость. Спектральная языковая модель (SLM) [3] учитывает распределение слов по всем документам коллекции и этим существенно отличается от указанных моделей, позволяя учитывать статистическую значимость слов при оценке релевантности (взвешивании) документа. Для того чтобы оценить, как такое свойство модели влияет на качество решения поисковых задач, был проведен сравнительный анализ SLM и наиболее широко используемых в данный момент вероятностных моделей: BM25 и DFR.

Описание спектральной языковой модели (SLM). Имеется множество слов W(w1,w2,...,wN) и множество документов коллекции D(d1,d2,…dM), N и M – соответственно их мощности. Для каждой пары слово-документ определена нормализованная частота:

  • nTF(wi, dj) = TF(wi, dj)/len(dj), где TF(wi,dj) – частота слова wi в документе dj;
  • len(dj) – длина документа dj в словах, i = 1..N, j = 1..M.

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

  • SF(w, TF) = {D:nTF(w, dj) = F}, где {*} – оператор мощности множества.

Множество спектральных частот, определенных над областью значений

образует частотный спектр слова.

Базовой характеристикой, на основе которой решаются задачи информационного поиска в различных моделях, является вес слова w в документе d. В спектральной модели она определяется по формуле:

Оценка релевантности документа d относительно запроса q определяется по формуле:

где L - лемма (каноническая форма) слова запроса.

Так как nTF величина непрерывная, то для построения базы нормализованных частот область значений была разбита на интервалы длиной 0,001. Такая избыточная разрешающая способность была выбрана с целью решения в дальнейшем задачи оптимального разбиения на интервалы. Последующие исследования показали, что уменьшение интервала разбиения или усреднение значений спектральных частот из окрестности nTF заданной ширины приводит к ухудшению результатов поиска, однако даже при увеличении шага дискретизации до 0,01 качество решения поисковых задач остается достаточно высоким по сравнению с другими моделями.

Сравнение SLM с вероятностными моделями BM25 и DFR. Для независимого оценивания спектральной модели в рамках Российского семинара по оценке методов информационного поиска было проведено сравнение двух поисковых алгоритмов: на базе SLM и BM25[3]. По каждому из них были получены ответы на более чем 40 тысяч предложенных запросов по коллекции из 5 миллионов документов. Оценка ответов проводилась асессорами по методу общего котла. Алгоритм на основе SLM показал практически по всем видам оценок существенно лучшие результаты по сравнению с BM25 (Табл. 1).

Таблица 1. Результаты сравнения ранжирующих алгоритмов на РОМИП-2010

Evaluation\SystemBM25SLM
Bpref0,4160,437
Bpref-100,5140,522
Precision(1)0,3720,442
Precision(10)0,3470,353
Precision(5)0,3720,395
Reciprocal Rank0,5030,54
R-precision0,4390,456
NDCG@50,3160,336
DCG@51,0911,186
NDCG@100,4150,435
DCG@101,6081,689

Однако в сравнении, проведенном на РОМИП-2010, участвовали модели BM25 и SLM не в чистом виде, т. к. для улучшения качества ранжирования использовался аддитивный алгоритм оценки релевантности документа с использованием весов, вычисленных по различным структурным элементам документов. Поэтому чтобы исключить влияние подобных факторов, было проведено дополнительное исследование моделей на основе таблиц релевантностей РОМИП за 2007–2010 гг.

Для каждой модели (DFR, BM25, SLM) в сравнении было использовано по 2 ранжирующих алгоритма:

  • оценка релевантности документа определяется только по исследуемой модели

    где q – запрос, d – оцениваемый документ.

  • оценка релевантности документа определяется по различным структурным элементам документа

    где kdoc, ktitle, kbegin – коэффициенты, полученные на основе машинного обучения. Обучение проводилось независимо для каждой модели на основе таблиц релевантностей.

  • Mdoc(q, d) – вклад всего документа в оценку его релевантности;
  • Mtitle(q, d) – вклад заголовка документа;
  • Mbegin(q, d) – вклад начальной части документа;
  • для SLM:

  • для BM25:

  • для DFR:

Полученные на запросы ответы по каждому алгоритму оценивались по таблицам релевантостей. Результаты оценок представлены в табл. 2–3.

Таблица 2. Результаты сравнения алгоритмов R1

Evaluation\SystemsDFRBM25SLM
Average precision0,2240,2260,256
Bpref0,5510,5550,595
Bpref-100,640,6430,685
Precision(1)0,4540,4720,522
Precision(10)0,4420,460,51
Precision(5)0,4440,4640,514
Reciprocal Rank0,4580,480,53
R-precision0,280,2960,32
NDCG@50,2420,2570,282
DCG@50,8350,8630,961
NDCG@100,330,3390,366
DCG@101,3061,3151,451

Таблица 3. Результаты сравнения алгоритмов R2

Evaluation\SystemsDFRBM25SLM
Average precision0,260,2660,296
Bpref0,6780,6850,748
Bpref-100,7820,7880,858
Precision(1)0,5220,5380,588
Precision(10)0,5120,530,576
Precision(5)0,5140,530,58
Reciprocal Rank0,3220,340,357
R-precision0,5260,5420,597
NDCG@50,3790,3870,435
DCG@51,2031,2311,406
NDCG@100,4670,4780,524
DCG@101,7721,8022,026

Как видно, по обоим алгоритмам лучшие результаты по всем оценкам получила спектральная модель. В среднем оценки SLM выше на 10 % чем у BM25 и на 13 % чем у DFR, что считается существенной разницей. На рис. 1 представлен график TREC для ответов по алгоритму R1.

Рис. 1. График TREC ответов по алгоритму R1

Из графика также видно, что точность результатов поиска при одинаковых значениях полноты у алгоритма на основе SLM выше, по сравнению с DFR и BM25.

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

Проведенные исследования говорят о том, что спектральный подход в оценивании релевантностей документов дает более качественное решение поисковых задач в сравнении с другими методами. Кроме того, SLM является непараметрической моделью, т. е. не требует настройки или машинного обучения, в отличие от многих других моделей, используемых в задачах информационного поиска. Однако спектральная модель обладает существенным недостатком – очень большой размер частотной базы. Если в большинстве вероятностных моделей на каждое слово в частотную базу заносится не более двух параметров, то здесь их число существенно больше. Одним из способов уменьшения базы может быть выбор большего шага дискретизации. Однако проведенные исследования показали, что спектры слов можно аппроксимировать с минимальными потерями качества решения поисковых задач функцией от 3 аргументов, в частности функцией вида

где a и b – параметры, которые определяются для каждого слова на основе метода наименьших квадратов. При этом, сохраняется свойство уникальности спектра слов, а размер частотной базы существенно сокращается: на каждое слово необходимо хранить по 2 параметра.

Библиографические ссылки

[1] Amati, G. Probabilistic models of information retrieval based on measuring the divergence from randomness / G. Amati and C. J. Van Rijsbergen, The Information Retrieval Group, 20(4):357-389, 2002.

[2] Robertson S.,Walker S., Hancock-Beaulieu M., Gatford M. Okapi at TREC-3. In Proceedings of the Third Text Retrieval Conference. 1994.

[3] Зябрев И.Н., Пожарков О.В., Пожаркова И.Н. Использование спектральных характеристик лексем для улучшения поисковых алгоритмов.. Труды РОМИП 2010. Казань: Казан. ун-т: С. 40–48, 2010.

THE COMPARATIVE ANALYSIS OF SPECTRAL LANGUAGE MODEL WITH OTHER INFORMATION RETRIEVAL MODELS

Zyabrev I.N., Vasilenko K.N., Pozharkov O.V., Pozharkova I.N.

Comparison of spectral language model (SLM) with models most widely used in information retrieval, such as DFR (Difference From Randomness) and BM25 by quality estimation of the search problems decision.



Нравится


Поисковые исследования:

Алгоритмы ранжирования Яндекса:


 

Copyright AlterTrader Research Ltd. 2004-2017.
All Rights Reserved.

Design: af@altertrader.com