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


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

Спектральный подход к решению задач информационного поиска

Константин Василенко, Илья Зябрев, Олег Пожарков, Ирина Пожаркова, опубликовано в "Информатизация образования и науки", №1(13), Москва, Россия, январь 2012.



Аннотация

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

1. Введение

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

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

2. Описание спектральной языковой модели (SLM)

Имеется множество слов L(L1,L2,...,LN) и множество документов коллекции D(d1,d2,…,dM), N и M – соответственно их мощности. Здесь и далее под словом понимается его каноническая форма (лемма). Для каждой пары слово-документ определена нормализованная частота:

– nTF(Li, dj) = TF(Li, dj)/Len(dj), где TF(Li,dj) – частота слова Li в документе dj;

– Len(dj) – длина документа dj в словах, i = 1…N, j = 1…M.

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

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

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

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

- DF(L) – документальная частота леммы L, число документов, в которых встречается L. Является базовой характеристикой в большинстве моделей информационного поиска.

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

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

где L - леммы слов запроса.

Для исследования основных свойств SLM нами была сформирована коллекция ATR.RU-2010 из русскоязычных веб-документов на основе метода случайного сэмплирования индекса [2] поисковых систем. Использованный метод позволяет из огромного количества документа построить репрезентативную выборку относительно небольшого размера, что позволяет проводить исследования без привлечения мощных вычислительных кластеров. В частности, мощность коллекции ATR.RU-2010 составила чуть более 10 миллионов документов. Для лемм всех встречающихся в коллекции слов были построены частотные спектры. Всего с учетом сокращений, аббревиатур и слов иностранных языков в частотную базу было занесено более 900 000 лемм.

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

На рис. 1 представлен фрагмент спектров русскоязычного местоимения «Я» и слова «То», построенные по нормализованной частоте. На рис. 2 изображены графики SLM, соответствующие этим спектрам. Слова «Я» и «То» имеют очень близкие значения DF, различающиеся менее чем на 0,2%

Рис. 1. Графики спектров слов «Я» (nSF) и «То» (nSF2) при nTF из (0;0,2]. Шкала ординат в логарифмическом масштабе

Рис. 2. Графики SLM слов «Я» (SLM) и «То» (SLM2) при nTF из (0;0,2]

Как видно из графиков, nSF немонотонно убывает, а SLM соответственно возрастает. На практике такое поведение означает, что в целом документы с большей частотой слова будут иметь больший вес. Однако при небольшой разнице между частотами может иметь место обратная ситуация, когда документ с меньшей частотой слова получит больший вес. В частности, из графика спектра слова «Я» (рис. 1) явно видно, что документов, в которых данное слово имеет нормализованную частоту равную 0,001, меньше чем документов с nTF=0,002. Соответственно и вес документов с nTF=0,001 будет больше.

Слова «Я» и «То» имеют очень близкие значения документальных частот, т.е. число документов в которых они встречаются. Данная характеристика является фундаментальной для различных вероятностных моделей, т.к. на ее основе вычисляются веса слов. Значения документальных частот слов «Я» и «То» отличаются менее чем на 0,2%. Т.е. с точки зрения таких IR-моделей, как BM25 и DFR, данные слова при одинаковых значениях nTF будут равнозначны. Однако, как видно из графиков, при использовании спектральной модели вклады этих слов в релевантность документа будут существенно отличаться. Данное свойство SLM является одним из самых значимых.

Подчеркнем основные свойства спектральной модели и ее отличия от других IR моделей.

  • Модель основана на реальных вероятностных распределениях слов по документам коллекции, а не на теоретических, как во многих других моделях. Благодаря этому нет необходимости выбирать теоретическое распределение, как например в DFR моделях.
  • Использование вероятностного подхода определяет непараметрический характер модели и, как следствие, отсутствие необходимости в ее обучении или настройке.
  • Немонотонность изменения значений частотного спектра с ростом нормализованной частоты.
  • При решении поисковых задач на основе SLM вклад слова в релевантность документа определяется уникальным для каждого слова спектром, в отличие от большинства IR-моделей, в которых разные слова при одинаковых значениях частотных характеристик равнозначны.

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

3. Сравнительный анализ SLM с другими вероятностными IR-моделями (DFR и BM25)

Для независимого оценивания спектральной модели в рамках Российского семинара по оценке методов информационного поиска [7] было проведено сравнение двух поисковых алгоритмов: на базе SLM и BM25 [6]. Первоначально в качестве исходного был использован метод на основе BM25, получивший самые высокие оценки на РОМИП-2009 [5]:

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

kdoc, ktitle, kbegin, kprox- коэффиценты;

BM25doc(q,d) – вклад всего документа в его вес, вычисленный по формуле BM25;

BM25title(q,d) – вклад заголовка документа, вычисленный по формуле BM25;

BM25begin(q,d) – вклад начальной части документа, вычисленный по формуле BM25;

Mprox(q,d) – вклад «кучности» [5] документа:

где P(L,d) – позиция леммы слова L в документе d. Под леммой в информационном поиске понимается каноническая форма слова. LMD(p, L, d) – расстояние от позиции p до ближайшей слева леммы L в документе d;

RMD(p, L, d) – расстояние от позиции p до ближайшей справа леммы L в документе d,

Ранжирующий алгоритм на основе SLM был получен из базового путем замены слагаемых BM25 на SLM [6]:

Mdoc(q,d) – вклад всего документа в его вес;

Mtitle(q,d) – вклад заголовка документа;

Mbegin(q,d) – вклад начальной части документа;

Mprox(q,d) – вклад «кучности» [5] документа:

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

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

Evaluation\SystemBM25SLM
Average precision0,4550,466
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

Таким образом, простая замена BM25 на SLM в ранжирующем алгоритме дала прирост качества решения задачи информационного поиска. Однако в сравнении, проведенном на РОМИП-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, что считается существенной разницей. На рис. 3 представлен график TREC для ответов по алгоритму R1.

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

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

4. Аппроксимированная SLM

В целом полученные результаты позволяют говорить о том, что спектральная модель, по крайней мере на русскоязычных документах, дает более качественное решение поисковых задач по сравнению с другими методами. Однако спектральная модель обладает существенным недостатком – очень большой размер частотной базы. Если в большинстве вероятностных моделей на каждое слово в частотную базу заносится не более двух параметров, то здесь их число существенно больше. Один из способов уменьшения базы это выбор большего шага частотной дискретизации. Однако данный метод не решает полностью проблему размера частотной базы, т.к. уже при шаге больше 0,01, что соответствует разбиению области значений на 100 интервалов, наблюдается снижение качества решения задач на основе SLM.

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

Для сравнительного анализа было выбрано две функции, которые с высокой точностью аппроксимируют частотный спектр:

Соответствующие им аппроксимированные SLM (aSLM) с переходом к другим константам имеют вид:

На основе метода наименьших квадратов для каждого слова были получены и занесены в базу значения параметров. На рис. 4,5 изображены графики базовой SLM и аппроксимированных для местоимения «Я».

Рис. 4. Графики базовой SLM и аппроксимированной SLM функцией (11) местоимения «Я»

Рис. 5. Графики базовой SLM и аппроксимированной SLM функцией (12) местоимения «Я»

Как видно, визуально приближение исходной спектральной модели функциями (9)-(12) довольно хорошее. aSLM1 лучше аппроксимирует исходную модель на низких частотах, а aSLM2 – на высоких. Для того, чтобы оценить насколько использование аппроксимации ухудшает качество решения поисковых задач нами было проведено исследование, аналогичное сравнительному анализу SLM с другими вероятностными моделями. Результаты оценок представлены в табл. 4–5.

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

Evaluation\SystemsSLMaSLM1aSLM2
Average precision0,2560,2580,250
Bpref0,5950,6060,560
Bpref-100,6850,7150,681
Precision(1)0,5220,5390,520
Precision(10)0,510,5220,506
Precision(5)0,5140,5260,507
Reciprocal Rank0,530,5350,528
R-precision0,320,3210,319
NDCG@50,2820,2840,276
DCG@50,9611,0030,954
NDCG@100,3660,3670,365
DCG@101,4511,5141,432

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

Evaluation\SystemsSLMaSLM1aSLM2
Average precision0,2960,3110,305
Bpref0,7480,7790,773
Bpref-100,8580,8930,884
Precision(1)0,5880,6190,609
Precision(10)0,5760,6020,596
Precision(5)0,580,6080,599
Reciprocal Rank0,3570,3710,369
R-precision0,5970,6260,619
NDCG@50,4350,4480,447
DCG@51,4061,4511,448
NDCG@100,5240,5450,541
DCG@102,0262,0872,083

Из таблиц видно, что aSLM1 по обоим алгоритмам улучшает качество решения поисковых задач: по алгоритму R1 в среднем на 1%, по алгоритму R2 в среднем на 5%. aSLM2 по алгоритму R1 – ухудшает оценки качества поиска в среднем на 2%, а по R2 – улучшает в среднем на 3%. Таким образом, использование аппроксимированной модели на основе функции (11) не только не ухудшает качество решения поисковой задачи, но и незначительно его улучшает. При этом объем частотной базы сокращается на два порядка.

Аппроксимированная SLM, построенная на основе функции (12) показала себя несколько хуже. Это связано с тем, что на низких частотах ее расхождение с SLM больше, чем у aSLM1. При этом, большинство документов из таблиц релевантности имели малые значения nTF слов запроса. Поэтому разница в ранжировании документов по алгоритму R1 по сравнению с базовой моделью была существенна для того, чтобы результаты ухудшились. Однако, обучение алгоритма позволило улучшить качество ранжирования на основе aSLM1. Была сформулирована гипотеза о том, что более высокие оценки аппроксимированной SLM по сравнению с исходной связаны с монотонностью aSLM. Проверка данного предположения требует дополнительных исследований.

5. Заключение

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

Литература

[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] Bar-Yossef, Z. and Gurevich, M. 2006. Random sampling from a search engine's index. In Proceedings of the 15th International Conference on World Wide Web (Edinburgh, Scotland, May 23 - 26, 2006). WWW '06. ACM Press, New York, NY, 367-376.

[3] Harter S. Variations in relevance assessments and the measurement of retrieval Effectiveness. Journal of the American Society for Information Science, 47(1):37-49,1996.

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

[5] Сафронов А.В. HeadHunter на РОМИП-2009. Труды ROMIP 2009.Санкт-Петербург: НУ ЦСИ. 2009, с 63-70.

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

[7] http://www.romip.ru.

SPECTRAL METHOD OF INFORMATION RETRIEVAL PROBLEMS SOLUTION

Vasilenko Konstantin, Zyabrev Ilya, Pozharkov Oleg, Pozharkova Irina

Article is devoted the description of spectral language model (SLM) and to its comparison with models most often used in information retrieval. The approximated spectral language model (aSLM) is described, and also its comparison with base model SLM from the point of view of information retrieval problems solution quality is spent.



Нравится


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

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


 

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

Design: af@altertrader.com