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


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

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

Илья Зябрев, Олег Пожарков, Ирина Пожаркова, опубликовано в "Труды 13й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» - RCDL’2011", Воронеж, Россия, 2011.



Аннотация

Данная статья посвящена описанию спектрального подхода в задачах обработки текстовой информации и, в частности, для решения задач информационного поиска. Проведено сравнение спектральной модели (Spectral Language Model – SLM) с популяр-ными вероятностными моделями, такими как BM25 и DFR. Также представлена аппроксимированная спектральная модель, которая позволяет избавиться от главного недостатка SLM – громоздкой частотной базы.

1. Описание спектральной модели SLM

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

Поэтому в дальнейшем данная метрика была взята в качестве базовой для спектральной языковой модели – SLM:

Где:

Нормализованная частота

TF(L,d) - внутренняя частота леммы L в документе d;

len(d) – длина документа d;

M - число документов в коллекции;

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

На основе коллекций документов КМ.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 ранжирующих алгоритма:

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

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

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

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

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

  • для BM25:

  • для DFR:

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

Таблица 1. Результаты сравнения алгоритмов 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

Таблица 2. Результаты сравнения алгоритмов 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.

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

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

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

Лучший результат из исследованных нами функций показала степенная:

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

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

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

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

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

Evaluation\SystemsSLMaSLM
Average precision0,2560,258
Bpref0,5950,606
Bpref-100,6850,715
Precision(1)0,5220,539
Precision(10)0,510,522
Precision(5)0,5140,526
Reciprocal Rank0,530,535
R-precision0,320,321
NDCG@50,2820,284
DCG@50,9611,003
NDCG@100,3660,367
DCG@101,4511,514

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

Evaluation\SystemsSLMaSLM
Average precision0,2960,311
Bpref0,7480,779
Bpref-100,8580,893
Precision(1)0,5880,619
Precision(10)0,5760,602
Precision(5)0,580,608
Reciprocal Rank0,3570,371
R-precision0,5970,626
NDCG@50,4350,448
DCG@51,4061,451
NDCG@100,5240,545
DCG@102,0262,087

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

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

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

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

Литература

[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.

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

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

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

Spectral characteristics in problems of text information processing

Zyabrev Ilya, Pozharkov Oleg, Pozharkova Irina

Paper is devoted the description of the spectral approach in problems of the text information processing and, in particular, for the decision of information retrieval problems. Comparison of spectral model (SLM) with popular probability models, such as BM25 and DFR is spent. Also the approximated spectral model is presented.



Нравится


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

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


 

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

Design: af@altertrader.com