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


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

Метод контекстно-зависимого аннотирования документов на основе спектральных оценок лексем.

Илья Зябрев, Олег Пожарков, опубликовано в "Труды РОМИП'2009.Санкт-Петербург: НУ ЦСИ.2009", с 167-174



Аннотация

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

1. Введение

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

Исходные данные:

  • Запрос Q – множество лексем запроса qi
  • Документ D – множество лексем документа di
  • Аннотация А – множество лексем аннотации ai

Ограничения:
В данном случае вводятся ограничения на длину аннотации в 300 символов:

где length(ai) – длина лексемы или разделителя аннотации.

Требуется сформировать множество А, удовлетворяющее введенным ограничениям и отражающее содержание документа D относительно запроса Q.

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

Нами задача получения множества А решалась в следующем виде:

Множество лексем документа разбивается на фрагменты F. Для этого используются следующие способы:

  • Метод скользящего окна с длиной, заданной в количестве предложений. Fi={Pk}, где P - множество предложений документа D, k=i,i+1,..i+L-1, L - заданная длина скользящего окна. Т.е. каждое предложение является фрагментом, за исключением случаев, когда предложение не укладывается в ограничения (1). Подмножества F не пересекаются.
  • Метод скользящего окна с длиной, заданной в количестве слов. Fi={dk}, где k=i,i+1,..i+L-1, где L - заданная длина скользящего окна. Данный метод применяется в том случае, если предложение не укладывается в ограничение (1). Подмножества F в данном случае пересекаются.

На основе анализа критериев качества аннотирования были формализованы частотно-зависимые метрики ранжирования фрагментов, для вычисления которых используются характеристики, описанные в [1]:

Внутренняя частота леммы IF(L,d) - число вхождений леммы L в документ d.

Условная частота леммы - число документов, удовлетворяющих заданным условиям. В контексте данной работы используются следующие условия:

  • Лемма L имеет встречаемость IF(L,d)=v:
    CLF(L,v)=card(d|IF(L,d)=v), где card(d|A) - число документов коллекции, удовлетворяющих условию A, v – целое число.
  • Лемма L имеет встречаемость IF(L,d)>=v
    CLF2(L, v)=card(d|IF(L,d)>=v)

Абсолютная частота слова AF(L) – число вхождений леммы некоторого слова во все документы коллекции.

где N – мощность множества документов коллекции.

Относительная условная частота леммы RCLF – отношение условной частоты леммы некоторого слова к его абсолютной частоте:

Абсолютная документальная частота слова DF(L) – число документов, в которые лемма L входит не менее 1 раза DF(L)=CLF2(L,1)

Обратная условная частота леммы:

На основе (2) были сформулированы следующие оценки для ранжирования фрагментов:

Мера вхождения запроса во фрагмент

где qj- лемма j-го слова запроса Q.

Мера вхождения фрагмента в запрос

где fi,j- лемма j-го слова фрагмента Fi.

Так как сформировано две метрики фрагментов, то для критериального оценивания и последующего ранжирования необходимо ввести свертку. Будем использовать свертку вида:

где a1, a2, b1, b2 – коэффициенты, которые в дальнейшем определяются на основе экспертных оценок по обучающей выборке.

Согласно вычисленным оценкам производится ранжирование множества фрагментов по возрастанию FMi, в результате чего получается множество RF. Из полученного списка путем последовательного выбора формируется аннотация:

Из коллекций документов KM.ru 2007 и BY.web 2007 была сформирована обучающая выборка, на основе которой в дальнейшем для различных наборов коэффициентов формулы свертки (5) были построены аннотации. С целью сокращения объема обрабатываемых данных было сформировано ограниченное множество значений коэффициентов, каждое из подмножеств которого обладает определенными особенностями. Далее экспертами была оценена каждая из аннотаций, полученная на всем множестве параметров формулы свертки. Результаты оценивания сведены в таблицу (Таблица 1).

Номер набораa1b1a2b2Средняя оценка экспертов
1234
111110,30,30,50,3
2111A2,82,52,33,3
311-110,20,20,30,2
411-1B2,32,22,21,7
51A110,40,30,30,2
61A1A4,94,72,95,2
71A-110,20,30,30,2
81A-1B53,55,95,1
9-11115,43,866,7
10-111A9,17,17,28,1
11-11-115,33,84,55,5
12-11-1B9,79,28,49,8
13-1B114,33,62,92,8
14-1B114,64,25,65,2
15-1B-1154,54,34,6
16-1B-1B6,13,23,85,3

Коэффициент А=10-18, коэффициент В=10-6, коэффициенты А и В применяются для того, чтобы нормализовать значение соответствующего слагаемого в тех случаях, когда необходимо уменьшить его влияние на конечный результат.

Коэффициент согласия экспертов 0,92, т.е. довольно высокий. Причем максимальные оценки у наборов 10 и 12, каждый из которых имеет свои особенности ранжирования фрагментов документа. Так набор 10 отдает предпочтение фрагментам текста, максимально соответствующим запросу и при этом максимально развернутым. Набор 12 также дает наивысшие оценки фрагментам текста, максимально соответствующим запросу, но, в отличие от предыдущего набора, наиболее лаконичным. Причем на некоторых документах оба метода дают один и тот же результат аннотирования. Т.к. нельзя однозначно отдать предпочтение одному из наборов, было принято решение использовать оба по следующему алгоритму. Фрагменты документа для аннотации выбираются поочередно из ранжированных списков, полученных по каждому из наборов, начиная с 12 до тех пор, пока выполняются ограничения по длине аннотации. Если соответствующие элементы списков совпадают, то фрагмент выбирается однократно, чтобы не было дублирующихся предложений.

Таким образом, предлагаемый алгоритм контекстно-зависимого аннотирования можно разбить на следующие шаги:

1. Фрагментация исходного документа:

2. Оценивание фрагментов документа по формулам:

3. Построение ранжированных списков по возрастанию критериев FM1 и FM2:

4. Построение аннотации путем последовательного выбора элементов списков RF1,RF2 до тех пор, пока выполняется ограничение (1), исключая повторное включение фрагментов текста.

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

Особенностями предложенного алгоритма являются использование частотно-зависимых оценок лексем [1] и использование двух методов ранжирования фрагментов документа, имеющих принципиальное отличие друг от друга, что дает возможность получить более содержательную аннотацию по сравнению с алгоритмом, использующим один метод. Стоит отметить, что параметры алгоритма ранжирования получены на небольшой обучающей выборке и основаны на мнении четверых экспертов. При формализации критериев качества построения аннотации появится возможность машинного обучения алгоритма на большой выборке документов и множестве значений параметров, не ограниченном представленными выше наборами. В частности для решения этой задачи можно использовать генетические оптимизационные алгоритмы.

Литература

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

Context-depended annotation method based on spectral estimations of lexemes

Zyabrev I.N., Pozharkov O.V.

The paper describes context-depended annotation method based on spectral estimations of documents lexemes. Also presents algorithm and results of its learning on basis expert estimation.

P.S. Данный алгоритм аннотирования тестировался на "Дорожке контекстно-зависимого аннотирования текстовых документов" Российского семинара по Оценке Методов Информационного Поиска (РОМИП) в 2009 и 2010 годах. В 2009 году получены средние результаты из-за ряда алгоритмических недоработок, связанных с обработкой текстовой информации. В 2010 году все недоработки были устранены, и алгоритм показал лучшие среди всех представленных систем результаты по всем оцениваемым характеристикам, что говорит о целесообразности использования предлагаемого подхода для решения задач лингвистического моделирования, в частности в области контекстно-зависимого аннотирования.



Нравится


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

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


 

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

Design: af@altertrader.com