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


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

Использование спектральных характеристик лексем для улучшения поисковых алгоритмов.

Илья Зябрев, Олег Пожарков, Ирина Пожаркова, опубликовано в "Труды РОМИП 2010".Казань, 2010", с 40-48



Аннотация

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

1. Введение

В задачах лингвистического моделирования одной из проблем является оценивание «важности» лексических единиц. На текущий момент наиболее популярной и широко используемой для этих целей метрикой является IDF (Inverse Document Frequency), а также различные функции от нее. Основным недостатком данной оценки является ее независимость от частоты слова внутри документа. Частично данная проблема решается использованием TF*IDF, где TF - относительная частота слова внутри оцениваемого документа, но при этом частота слова в других документах не учитывается. Нами в [1] была предложена спектральная метрика Inverse Conditional Lemm Frequency (ICLF), учитывающая внутренние частоты слов во всех документах коллекции, что предположительно должно было повысить качество оценивания лексем. Однако данное предположение основывалось только на теоретических рассуждениях, поэтому в этом году было принято решение провести сравнительный анализ поисковых алгоритмов, основанных на классических (IDF) и спектральных (ICLF) метриках.

2. Описание алгоритма

2.1 Спектральные характеристики лексем

В [1] были предложены спектральные характеристики лексических единиц, в частности:

Обратная условная частота

где D – количество документов коллекции.

CLF(L,v) – число документов коллекции, в которые лемма L входит v раз.

В дальнейшем была предложена новая условная характеристика, основанная на внутренней относительной частоте слова:

Спектральная характеристика лексемы (Spectral Lexeme Metrics)

где RCLF(L,v) – число документов коллекции, в которых лемма L имеет относительную частоту равную v.

Относительная частота

где TF(L,d) - внутренняя частота леммы L в документе d,
len(d) – длина документа d.

На основе коллекций документов КМ.ru-2007 и BM.web-2007 для каждой леммы, входящей в их состав, нами были построены базы значений спектральных характеристик ICLF и SLM. Т.к. относительная внутренняя частота, которая является аргументом SLM – непрерывная, то, чтобы ограничить размерность базы, мы разбили диапазон значений от 0 до 0,5 на 500 равных интервалов и один добавочный интервал для случаев, когда значение RTF превышает 0,5, что случается крайне редко. Значение 500 интервалов было выбрано из соображений обеспечения достаточной разрешающей способности по относительной частоте при небольшом объеме базы. Скорее всего, такое разбиение не является оптимальным, однако позволяет решать поисковые задачи.

SLM, по сравнению с обычной ICLF, косвенно учитывает еще и длину документов, что позволяет использовать ее в новом качестве. В частности, было предложено использовать ее как самостоятельную ранжирующую характеристику наряду с ВМ25. Рассмотрим особенности поведения SLM в сравнении с BM25 на одной и той же лемме местоимения «Я» (рисунок 1).

На рисунке 1 приведены в едином масштабе графики log(SLM) (сплошная линия), BM25 при фиксированной длине документа равной средней длине по коллекции (пунктирная линия) и ВМ25 при длине документа равной половине средней (штриховая линия) леммы «Я» при изменении относительной частоты слова от 0 до 0,5.

Рисунок 1. Графики log(SLM) и ВМ25 леммы «Я»

Как видно, в целом характер поведения у функций является схожим: резкий рост при увеличении относительной частоты на малых значениях и постепенное его замедление на высоких. Однако график log(SLM) имеет ломаный вид, т.к. локально незначительное увеличение частоты может привести к уменьшению значения функции. На других леммах наблюдается аналогичная картина. Таким образом, log(SLM) имеет схожее с ВМ25 поведение, однако при этом учитывает особенности распределения внутренних частот лемм по коллекции документов. Поэтому была выдвинута гипотеза о том, что ранжирующие формулы, построенные на основе условных обратных частот, дадут более качественное решение поисковых задач. Для проверки гипотезы было реализовано 3 версии поискового алгоритма.

2.2 Описание ранжирующих алгоритмов

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

Где kdoc=1, ktitle=2, kbegin=1,5, kprox=1,2, kphrase=10 – коэффициенты, значения которых одинаковы для всех трех реализаций алгоритма;
q - запрос, d – оцениваемый документ;
Mdoc(q,d) – вклад всего документа в его ранг;
Mtitle(q,d) – вклад заголовка документа;
Mbegin(q,d) – вклад начальной части документа;
Mprox(q,d) – вклад «кучности» [3] документа;
Mphrase(q,d) – вклад полноты содержания запроса в документе.

Каждая из указанных характеристик, за исключением полноты содержания запроса, вычисляется для различных реализаций алгоритма по-разному.

Базовый алгоритм. Первые три характеристики вычисляются по формуле ВМ25 [4].

где IDF(L) – обратная частота леммы L,
AvgLen – средняя длина документа в коллекции.

Кучность оценивается по формуле из [3]

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

Полнота содержания запроса в документе - дискретная величина, которая определяется следующим образом:

  • Mphrase(q,d)=4, если запрос содержится полностью в документе, при этом леммы слов запроса идут в документе подряд.
  • Mphrase(q,d)=3, если запрос содержится полностью в документе, при этом леммы слов запроса находятся в одном предложении документа.
  • Mphrase(q,d)=2, если запрос содержится полностью в документе и указанные выше условия не соблюдаются.
  • Mphrase(q,d)=1, во всех остальных случаях.

Модификация алгоритма с использованием ICLF. Все формулы получены из (2)-(3) заменой IDF(L) на ICLF(L):

Модификация алгоритма с использованием SLM.

3. Анализ результатов

Проверка алгоритмов проводилась на двух дорожках:

Ниже представлены результаты по коллекции KM.RU (таблицы 1-4)

Таблица 1. Результаты оценки KM.ru relevance minus and

xxx-1xxx-2xxx-3xxx-4BM25SLMICLF
Precision(10)0,5100,5230,4730,4550,5160,5180,501
PFound0,5300,5330,4910,4770,5460,5550,537
Graded NDCG@100,5130,5180,4550,3990,4960,5040,490
NDCG@50,2270,2350,2190,1960,2490,2540,246
Reciprocal Rank0,6250,6180,5690,5870,6590,6800,667
Graded DCG@105,6875,6465,2285,0855,5795,7215,721
Precision(5)0,5590,5670,5230,4990,5810,5890,564
Precision(1)0,5480,5340,4930,5210,5750,6030,616
Bpref-100,5280,5330,4740,3850,5120,5160,485
Bpref0,4550,4730,4030,3360,4590,4590,431
DCG@51,6451,6621,5371,4841,7081,7481,695
Recall0,7770,7780,7610,6110,7240,7280,712
NDCG@100,3160,3280,3090,2710,3350,3400,327
Graded NDCG@50,5010,5070,4330,3920,4900,5030,486
Precision0,2670,2640,2170,1920,2520,2520,242
Average precision0,4810,4900,4310,3500,4680,4730,451
DCG@102,3842,4312,2172,1442,4352,4682,402
Graded DCG@54,0373,9503,6033,5053,8594,0494,010
R-precision0,4410,4560,4090,3470,4580,4490,424

Таблица 2. Результаты оценки KM.ru relevance minus or

xxx-1xxx-2xxx-3xxx-4BM25SLMICLF
Precision(10)0,6010,6010,5290,4790,5640,5690,558
PFound0,5990,5990,5340,4980,5690,5760,572
Graded NDCG@100,5130,5180,4550,3990,4960,5040,490
NDCG@50,2150,2200,2020,1590,2030,2050,211
Reciprocal Rank0,7130,7230,6370,6140,7090,7230,731
Graded DCG@105,6875,6465,2285,0855,5795,7215,721
Precision(5)0,6430,6430,5600,5100,6090,6200,616
Precision(1)0,6400,6520,5730,5510,6630,6850,697
Bpref-100,5540,5550,4870,3670,4870,4840,474
Bpref0,5040,5120,4390,3410,4590,4570,444
DCG@51,9011,9061,6621,5241,8181,8621,865
Recall0,7520,7490,7370,5740,6330,6360,630
NDCG@100,3060,3090,2830,2230,2820,2850,284
Graded NDCG@50,5010,5070,4330,3920,4900,5030,486
Precision0,3490,3450,2900,2460,3190,3200,313
Average precision0,5100,5160,4560,3380,4520,4530,443
DCG@102,7982,8032,4652,2412,6522,6932,668
Graded DCG@54,0373,9503,6033,5053,8594,0494,010
R-precision0,5000,5120,4510,3560,4550,4490,433

Таблица 3. Результаты оценки KM.ru relevance plus and

xxx-1xxx-2xxx-3xxx-4BM25SLMICLF
Precision(10)0,3630,3580,3160,3260,3470,3530,342
PFound0,4350,4270,3790,3880,4200,4370,436
Graded NDCG@100,5130,5180,4550,3990,4960,4900,504
NDCG@50,3290,3140,2780,2660,3160,3360,323
Reciprocal Rank0,4930,4700,4430,4570,5030,5400,532
Graded DCG@105,6875,6465,2285,0855,5795,7215,721
Precision(5)0,4370,4280,3630,3580,3720,3950,400
Precision(1)0,3720,3490,3490,3490,3720,4420,419
Bpref-100,5390,5320,4810,4590,5140,5220,522
Bpref0,4330,4220,3830,3560,4160,4370,409
DCG@51,2511,2141,0631,0461,0911,1861,179
Recall0,8470,8470,8190,7500,8160,8120,814
NDCG@100,4160,4010,3680,3690,4150,4350,416
Graded NDCG@50,5010,5070,4330,3920,4900,4860,503
Precision0,1190,1190,1120,1060,1040,1010,103
Average precision0,4850,4740,4360,4000,4550,4660,457
DCG@101,7211,6841,5021,5201,6081,6891,639
Graded DCG@54,0373,9503,6033,5053,8594,0104,049
R-precision0,4360,4180,3810,3560,4390,4560,438

Таблица 4. Результаты оценки KM.ru relevance plus or

xxx-1xxx-2xxx-3xxx-4BM25SLMICLF
Precision(10)0,4270,4300,4100,3940,4420,4460,448
PFound0,4890,4880,4450,4500,4860,5020,500
Graded NDCG@100,5130,5180,4550,3990,4960,5040,490
NDCG@50,3010,2980,2560,2420,2820,2850,284
Reciprocal Rank0,6000,5780,5070,5280,5750,6160,615
Graded DCG@105,6875,6465,2285,0855,5795,7215,721
Precision(5)0,4990,5070,4540,4330,4930,5040,499
Precision(1)0,5370,5070,4180,4330,4930,5370,537
Bpref-100,5200,5120,4760,4270,4860,4860,484
Bpref0,4660,4540,4000,3430,4430,4380,434
DCG@51,4951,4911,3121,2761,4451,5011,487
Recall0,7590,7470,7800,6470,7300,7280,732
NDCG@100,3860,3820,3530,3300,3720,3770,383
Graded NDCG@50,5010,5070,4330,3920,4900,5030,486
Precision0,1900,1860,1660,1470,1800,1770,177
Average precision0,4850,4740,4270,3650,4510,4510,447
DCG@102,0692,0601,9041,8452,0762,1292,131
Graded DCG@54,0373,9503,6033,5053,8594,0494,010
R-precision0,4750,4610,4140,3610,4450,4440,437

В таблицах жирным выделены ячейки с лучшими результатами и оценки, по которым алгоритм, построенный на базе SLM, был лучшим среди всех представленных систем. Как видно, по многим оценкам данный алгоритм стал первым, в частности по pfound алгоритм был лучшим в 3 из 4 случаев. В целом тестируемые системы показали следующий результат среди всех участников: по 24 оценкам лучшим была SLM-версия алгоритма, по 10 – ICLF-версия, по 1 – BM25. При этом по большинству оценок (более 80%) реализация системы на SLM была лучше, чем базовая версия алгоритма на ВМ25.

На коллекции BY.web-2007 по 82 оценкам из 84 (более 97%) алгоритм с использованием SLM был лучше исходной системы и в 2 результат был одинаковым. ICLF-реализация в аналогичном сравнении была лучше по 54 оценкам из 84 (более 65%).

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

На основе полученных результатов можно сделать вывод, что гипотеза о более качественном решении поисковых задач при использовании ранжирующих формул, построенных на базе спектральных характеристик, подтверждается. Так как простая замена BM25 на log(SLM) дает увеличение большинства оценок. В частности, согласно окончательным результатам по коллекции KM.ru наблюдается максимальное увеличение оценки на 18,75% (Precision-1 relevance plus AND), максимальное ухудшение оценки -2,68% (Precision relevance plus AND). По окончательным результатам для коллекции BY.web наблюдается максимальное увеличение оценки на 14,4% (Precision-10 relevance plus and). Данные результаты позволяют охарактеризовать спектральные характеристики лексем как хорошую замену классическим BM25 и IDF.

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

Литература

[1] Зябрев И.Н., Пожарков О.В. Спектральное оценивание лексических единиц в задачах лингвистического моделирования.

[2] Зябрев И.Н., Пожарков О.В. Метод контекстно-зависимого аннотирования документов на основе спектральных оценок лексем. Труды ROMIP 2009.Санкт-Петербург: НУ ЦСИ. 2009, с 167-174.

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

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

Spectral characteristics of lexemes using for search algorithms improvement

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

Paper is devoted spectral characteristics of lexical units using as a basis for search algorithms for improvement of their quality. Comparison results of search model basis on ВМ25 with its updatings by replacement classical frequency characteristics by the spectral are presented.



Нравится


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

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


 

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

Design: af@altertrader.com