ИЗВЛЕЧЕНИЕ И РАНЖИРОВАНИЕ КЛЮЧЕВЫХ ФРАЗ В ЗАДАЧЕ АННОТИРОВАНИЯ
С.В. Попова, И.А. Ходырев
УДК 004.912
ИЗВЛЕЧЕНИЕ И РАНЖИРОВАНИЕ КЛЮЧЕВЫХ ФРАЗ В ЗАДАЧЕ АННОТИРОВАНИЯ
С.В. Попова, И.А. Ходырев
Для решения задачи аннотирования проводится сравнительный анализ двух подходов ранжирования ключевых фраз. Первый основан на оценке веса извлекаемых фраз с помощью TextRank, второй основан на использовании tf-idf оценки. Исследование проведено на базе коллекции INSPEC dataset. Представлены описание экспериментов и сравнительные результаты. Экспериментально показано, что подход, основанный на использовании tf-idf, дает лучший результат. Ключевые слова: аннотирование, извлечение и ранжирование ключевых фраз, оценка качества аннотаций.
Введение
Тенденция к распространению электронных форматов представления научной информации сти-
мулирует активное развитие научного сектора Интернета. Выражено это появлением огромного числа
электронных публикаций и каталогов цитирования, доступных через сеть интернет, что, в свою очередь,
способствует развитию и научных электронных библиотек. Очевидно, что комфортная работа пользова-
теля с таким большим объемом информации невозможна без быстрого автоматического поиска нужных
материалов. Для решения этой задачи необходимы данные о смысловом содержании документа, пред-
ставленного в виде короткой аннотации. В работе под аннотацией понимается список ключевых
слов/словосочетаний (фраз), характеризующих электронный документ. Наборы ключевых фраз или слов
могут быть также использованы в задачах кластеризации и классификации, в задаче автоматического
построения/пополнения онтологий, в задаче определения основных трендов, в задаче поиска новой ин-
формации и т.д. Под аннотированием в работе будем иметь в виду автоматическое извлечение из текста
ключевых слов/словосочетаний (фраз).
Для решения задачи аннотирования выделяют два подхода. Первый использует обучающую вы-
борку, второй – нет.
В первом подходе задача сводится к разработке классификатора, определяющего для поступивше-
го на вход текста, какие из его частей являются ключевыми фразами, а какие нет [1, 2]. В работе [2]
предложен генетический алгоритм и параметризованная система по извлечению ключевых фраз
Extractor. Генетический алгоритм позволяет определить оптимальные значения параметров. В [1] исполь-
зован наивный байесовский классификатор. В [3] выполнена интеграция лингвистических данных в ма-
шинное обучение, показано преимущество использования информации о частях речи.
В рамках второго подхода наиболее популярным является метод, основанный на представлении
текста в виде графа, предложенный в работе [4]. Вершины графа – целостные части текста (отдельные
слова, n-граммы, предложения). Веса дуг графа характеризуют тип связи между вершинами по выбран-
ному принципу (например, встречаться вместе в окне размера n, т.е. на расстоянии не более n слов друг
от друга). В [4] в качестве вершин графа рассматриваются отдельные слова текста; вес дуги, соединяю-
щей две вершины-слова, показывает, сколько раз эти два слова встретились в тексте в окне n. Для оценки
веса каждой вершины-слова в [4] используется величина, основанная на модификации формулы
PageRank [5]:
S
(vi
)
(1
d
)
d
Vj
In (Vi
)
|
1 Out(v
j
)
|
S
(v
j
),
где In(vi ) – дуги, входящие в вершину vi ; Out(v j ) – дуги, исходящие из вершины v j . Представленная
выше формула была изменена [4] с учетом того, что каждая дуга имеет вес w :
S(vi ) (1 d ) d v j In(Vi )
wij .
wjk
vk Out (v j )
(1)
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
81
ИЗВЛЕЧЕНИЕ И РАНЖИРОВАНИЕ КЛЮЧЕВЫХ ФРАЗ В ЗАДАЧЕ АННОТИРОВАНИЯ
Формула (1) получила название TextRank. Данная формула в [4] используется для расчета весов
вершин-слов. Вершины-слова ранжируются по значению их веса, после чего отбирается только часть
вершин с наибольшим весом. В [4] отобранные таким образом слова склеивались в фразы. Два слова
объединяются в одну фразу, если в оригинальном тексте они непосредственно следуют друг за другом. В
работе [8], помимо слов, рассмотрены многословные части текста – тогда вершинами графа текста явля-
ются группы слов. В качестве таких групп слов, например, взяты n-граммы (последовательность из n
слов, следующих в тексте друг за другом), существительные фразы [8]. Для полученных многословных
вершин рассчитывался вес на основе (1), лучшие вершины отбирались как ключевые фразы. После этого
две последовательности слов склеивались в одну фразу, если они непосредственно следовали друг за
другом в оригинальном тексте. В противном случае группа слов, образующих вершину, рассматривалась
как самостоятельная фраза. Использование многословных частей текста при описанном выше подходе не
дает лучших результатов в сравнении с использованием слов [8].
Оценка веса части текста с помощью TextRank в задаче аннотирования получила дальнейшее разви-
тие. В работе [6] при построении графа учитывается содержание k ближайших документов. В [7] учитыва-
ется информация о семантической близости между построенными вершинами, дополнительно используют-
ся WordNet и Wikipedia. Полученные результаты являются одними из лучших в предметной области.
В данной работе задача извлечения ключевых фраз разделена на два этапа: 1) построение фраз-
претендентов; 2) оценка веса каждой фразы-претендента и выбор лучших k из них как ключевых фраз.
Также как и в работе [4], вес слов рассчитывается с помощью (1). Но, в отличие от [4], здесь не отбира-
ются слова с наивысшей величиной TextRank, которые затем склеиваются в фразы. Вместо этого все сло-
ва после предобработки склеиваются в фразы, после чего оценивается вес каждой фразы, и лучшие фра-
зы отбираются в качестве ключевых. Вес фразы считается равным весу лучшего слова (лучшее слово –
слово в фразе с набольшим весом).
В работе поставлена задача проверки адекватности оценки веса фразы на основе информации о
весах входящих в фразу слов, оцененных с помощью (1). Для сравнительного анализа в работе использо-
ван второй способ оценки весов слов и фраз соответственно [8]. Для этого использована популярная
оценка веса слова tf-idf [11], которая рассчитывается для каждого конкретного слова в каждом документе
как произведение частоты слова в данном документе tf на инвертированную частоту документов idf,
idf
log
N df
,
где N – множество документов, df – число документов, в которых хотя бы раз встретилось слово. Далее
будем обозначать вес слова vi в документе как (tf-idf)(vi). С помощью tf-idf оценивается вес каждого слова в документе. Вес фразы, построенной для текста, считается равным весу слова, входящего в фрау с максимальным значением tf-idf.
Для работы выбрана коллекция INSPEC dataset – одна из самых популярных в исследованиях по аннотированию текстов ключевыми фразами [3, 4, 7, 8, 10]. Коллекция содержит англоязычные аннотации к научным публикациям (abstracts, далее в тексте использован термин «абстракт», под которым понимается аннотация к научной публикации. Заметим, что термин «абстракт» использован во избежание путаницы, так как термин «аннотация» в работе используется для обозначения набора ключевых фраз документа). Коллекция состоит из трех подколлекций: training dataset (1000 документов), evaluation dataset (500 документов), testing dataset (500 документов). Каждый текст имеет «золотой стандарт», состоящий из фраз, отобранных для документа экспертом. Золотой стандарт включает в себя два подмножества аннотаций: contr set и unconter set. Аналогично [3, 4, 7, 8, 10], в работе использовано множество uncontr set. Подробное описание коллекции приведено в [3].
Оценка качества
Изначально для оценки качества извлеченных ключевых фраз использовалась оценка, основанная на F-score [3, 11], интегрирующая информацию о точности и полноте извлеченных фраз (Precision и Recall [11]). Однако данный способ оценки не накладывает четких ограничений на число извлеченных фраз. В работе [8] предложен подход, основанный на использовании R-Precision вместо F-score. R-Precision – значение Precision при условии, что число извлеченных ключевых фраз в точности совпадает с числом фраз в золотом стандарте. Для расчета R-Precision требуется информация о числе правильно извлечен-
ных фраз. Пусть Gt – множество автоматически извлеченных фраз из текста t , Ct – множество ключе-
вых фраз золотого стандарта для текста t (в золотой стандарт для каждого текста входят идеальные ан-
нотации, вручную построенные экспертом). Возникает вопрос, какие из фраз Gt принадлежат Gt Ct . В
большинстве работ по извлечению ключевых фраз используется точное совпадение. Тогда фраза k
(«продвинутый автоматический перевод») и фраза золотого стандарта g («автоматический перевод»)
82 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 1 (83)
С.В. Попова, И.А. Ходырев
распознаются как различные. Аналогично ситуация возникает, например, и для фраз «хороший автомобиль» и «хорошая машина». В [8] сравниваются способы определения правильности извлеченной фразы:
точное совпадение двух фраз (exact); совпадение двух фраз при наличии только морфологического различия (morph);
совпадение двух фраз, если фраза k содержит в себе фразу g (include);
совпадение двух фраз, если фраза g содержит в себе фразу k (part-of).
Показано, что использование part-of является неудачным. Для оценки совпадения двух фраз в [8] использовались exact и include+morph. В работе [9] расширено число способов оценки извлеченной ключевой фразы: BLEU, METEOR, NIST, ROUGE. Определено отношение, лучше отражающее подход экспертов к определению корректности фразы:
rp
| слова _ фразы Gt max{| слова _ фразы Gt
слова _ фразы Сt | |,| слова _ фразы Сt
|}
.
В данной работе для оценки качества результатов аннотирования используются метод и мера,
предложенные в работах [8, 9], что позволяет в дальнейшем использовать результаты, полученные в дан-
ной работе, для сравнительной оценки качества новых алгоритмов, также опирающихся на [8, 9].
Для оценки качества аннотирования используется R-Precision [8]. Для оценки качества каждой
конкретной извлеченной фразы рассматриваются три способа.
1. Случай exact. Здесь
| Gt Ct || {k Gt : g Ct exact(k, g) 1} | ;
где exact(k, g) 1 , если фразы k и g совпадают, exact(k, g) 0 – в противном случае.
2. Случай include. Здесь | Gt Ct || {k Gt : g Ct include(k, g) 1} ;
где include(k, g) 1 , если фраза k содержит в себе фразу g , иначе include(k, g) 0 .
3. Случай rp [9]. Здесь
|
Gt
Ct
|
|
1 Gt
|
kGt
max( | k g | gCt max(| k |,| g
|) )
.
Описание эксперимента
Для формирования исходных данных выполнена предобработка текстов. Каждый текст t представлен набором слов, из которого изъяты стоп-слова и все другие слова, кроме существительных и прилагательных [4]. Для определения части речи слов использован Stanford POS tagger tool [12]. Для каждого текста t построены фразы-претенденты: несколько слов из множества bt объединялись в одну фразу, если в t они непосредственно следовали друг за другом. В построенной фразе-претенденте не могло быть больше четырех слов [8]. В работе поставлена следующая задача: проанализировать способы ранжирования полученных фраз-претендентов, для отбора лучших n из них как ключевых фраз, где n | Ct | .
Примем следующие обозначения: (k) – вес фразы k , где k {s1, s2 ,...sn} ; si или sik – слова фра-
зы k ; TR(sik ) – вес слова sik , рассчитанный с использованием формулы (1). Для ранжирования фраз на основе TextRank и tf-idf вес фразы рассчитывался по формулам
(k
)
max si k
TR(si
),
(k
)
max si k
tf
ifd
(si
).
Для расчета TR(sik ) требуется определить способ оценки веса дуг wij , соединяющий вершины-
слова vi и v j . Рассмотрены варианты: 1. wij occur(vi , v j ) , где occur(vi , v j ) – число раз, когда слова vi и v j встретились вместе в тексте t в
окне n 2 (в работе [4] было показано, что такой размер окна является наилучшим);
2.
wij mi(vi , v j ) , где
mi(vi , v j
)
log
p(vi , v j ) N p(vi ) p(v j )
есть взаимная информация между
vi
и
vj ,
p(vi , v j )
–
число раз, когда слова vi и v j встретились вместе в текстах коллекции в окне 2, p(vi ) , p(v j ) – число
вхождений слов vi и v j в текстах коллекции, N – общее число словоформ в коллекции;
3. wij tf idf (vi ) tf idf (vj ) .
Также поставлен дополнительный эксперимент: для ранжирования на основе TextRank строился граф, вершинами которого являлись все слова коллекции после предобработки, а wij p(vi , v j ) . Отличие
от рассмотренного выше способа расчета весов вершин на основе формулы (1) – в том, что используется один граф для всей коллекции, а не отдельные графы для каждого текста.
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
83
ИЗВЛЕЧЕНИЕ И РАНЖИРОВАНИЕ КЛЮЧЕВЫХ ФРАЗ В ЗАДАЧЕ АННОТИРОВАНИЯ
Фразы ранжировались по значению весов. Лучшие n фраз с наибольшими значениями весов отбирались как ключевые фразы. На завершающей стадии эксперимента проводилась постобработка. Если для одного текста в качестве претендентов были получены две фразы, такие, что одна является частью другой, то оставлялась одна фраза наибольшего размера.
Результаты экспериментов и обсуждение
Результаты экспериментов представлены для трех подколлекций INSPEC dataset: test dataset, evaluate dataset, trial dataset (табл. 1–3). Приняты следующие обозначения: 1. ранжирование фраз с помощью TextRank:
TR for text – граф строился для каждого отдельного текста, wij occur(vi , v j ) ;
TR for text*mi – граф строился для каждого отдельного текста, wij mi(vi , v j ) ;
TR for text**tf-idf – граф строился для каждого отдельного текста, wij tf idf (vi ) tf idf (vj ) ;
TR collection – граф строился для всей коллекции, wij p(vi , vj ) ; 2. результаты ранжирования с помощью tf-idf.
INSPEC dataset test dataset
evaluate dataset
trial dataset
TR for text
0,22 0,21 0,21
TR for text*mi
0,21
0,20
0,19
TR for text**(tf-idf)
0,23
0,22
0,22
TR collection
0,19 0,17 0,16
tf-idf
0,28 0,26 0,26
INSPEC dataset test dataset
evaluate dataset
trial dataset
Таблица 1. R-Precision exact
TR for text TR for text* TR for text** TR collection
0,29 0,27 0,27 0,26 0,27 0,26
0,31 0,29 0,29
0,25 0,23
0,23
tf-idf
0,37 0.34 0.34
INSPEC dataset test dataset
evaluate dataset
trial dataset
Таблица 2. R-Precision include
TR for text TR for text* TR for text** TR collection
0,42 0,41 0,40 0,39 0,40 0,40
0,43 0,42 0,42
0,37 0,36 0,35
tf-idf
0,48 0.46 0.46
Таблица 3. R-Precision rp
Результаты показали, что ранжирование фраз, основанное на TextRank, уступает ранжированию на основе tf-idf. TextRank использует данные, собранные из одного текста. Такая ограниченность плохо сказывается на качестве аннотирования. Tf-idf интегрирует информацию о важности слов в отдельном тексте и информацию о распространенности слов в коллекции, позволяя отсеять общеупотребительные для коллекции слова, не потеряв важных для текста терминов. Интересно, что tf-idf хорошо работает для коллекций абстрактов, несмотря на то, что документы коллекции является короткими текстами, а используемая коллекция – сравнительно небольшая. Формула tf-idf требует сбора статистики по встречаемости слов, для чего обычно требуется большой объем текстовых данных. Вывод: важные слова часто повторяются в конкретной аннотации к научной статье и редки в других аннотациях (по другим темам). Такая закономерность позволяет собрать нужную статистику на небольшом наборе данных и обосновывает использование tf-idf.
Использование wij mi(vi , v j ) для TextRank не улучшает качества ранжирования по сравнению с
классическим вариантом wij occur(vi , v j ) . Некоторое улучшение достигается за счет использования для
оценки дуг wij tf idf (vi ) tf idf (vj ) . Использование взаимной информации между словами:
mi(vi , vj ) , не улучшает качества ранжирования в сравнении с tf-idf, несмотря на то, что данные собира-
ются по всей коллекции. При использовании mi оценивается не значимость отдельных слов, а значимость связей между словами. Эта мера имеет тенденцию к завышению значимости связей с/между редкими (случайными) словами. В работе при расчете mi не ставилось ограничение, которое позволило бы рассматривать связи только со словами, встретившимися в коллекции больше, чем l раз (в противном
84 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 1 (83)
С.В. Попова, И.А. Ходырев
случае вес связи был бы равен нулю). Полученный результат служит индикатором того, что в аннотациях к публикациям ключевые слова не бывают случайными (одиночными относительно коллекции).
Результаты, полученные в дополнительном эксперименте, могут считаться неудовлетворительными. Вероятно, это связано с тем, что теряется информация об особенностях отдельных текстов.
Еще одно интересное наблюдение касается способа оценки каждой автоматически извлеченной фразы. Рассматривалось три способа: exact, inclide, rp. Существует высокая корреляция между результатами, полученными для каждого из этих способов. Коэффициент корреляции Спирмена рассчитан для пар exact-include, include-rp, exact-rp и составил 0,98–0,99, для расчета коэффициентов использовано 15 наблюдений (Табл. 1 для exact, Табл. 2 для include, Табл. 3 для rp), корреляция значима на уровне 0,001. Была проверена корреляция между результатами, полученными в [8], где использовались такие способы оценки, как exact и include+morph. Получено значение 0,91, корреляция значима на уровне 0,001. Планируется провести дополнительные исследования, отвечающие на вопрос: «насколько высока вероятность того, что рассматриваемые способы могут быть взаимозаменяемыми», что позволит использовать единственный способ оценки качества.
Заключение
В работе представлены результаты серии экспериментов по извлечению ключевых слов на базе коллекции INSPEC datset с использованием Stanford POS tagger tool. Показано, что для данной коллекции tf-idf предложенный авторами способ ранжирования дает лучший результат, чем TextRank. Использование tf-idf требует сбора статистики по встречаемости слов, для чего обычно требуется большой объем данных. Экспериментально полученный результат показывает пригодность tf-idf для обработки небольших коллекций абстрактов. Это означает, что важные для текста слова часто повторяются в конкретном абстракте и редки в других абстрактах, что можно считать обоснованием использования tf-idf для небольших коллекций абстрактов. По результатам экспериментов сделан вывод, что в абстрактах ключевые слова имеют вхождение в коллекцию большее, чем 1–2 раза. Показано, что используемые в работе три способа оценки качества аннотирования могут оказаться взаимозаменяемыми.
Работа выполнена в рамках ФЦП «Научные и научно-педагогические кадры инновационной России» поисковые научно-исследовательские работы по лоту шифр «2011-1.2.1-302-031», государственный контракт № 16.740.11.0751.
Литература
1. Frank E., Paynter G.W., Witten I.H., Gutwin C., Nevill-Manning C.G. Domain-specific keyphrase extraction // Proc. of IJCAI. – 1999. – P. 688–673.
2. Turney P. Learning to Extract Keyphrases from Text. – NRC/ERB-1057. – 1999. – February 17. – 43 p. 3. Hulth A. Improved automatic keyword extraction given more linguistic knowledge // Proc. of the Conference
on Empirical Methods in Natural Language Processing. – 2003. – P. 216–223. 4. Mihalcea R., Tarau P. TextRank: Bringing order into texts // Proc. of the Conference on Empirical Methods
in Natural Language Processing. – 2004. – P. 404–411. 5. Brin S. and Page L. The anatomy of a large-scale hypertextual web search engine // Computer Networks and
ISDN Systems. – 1998. – V. 30. – № 1–7. – P. 107–117. 6. Wan Xiaojun and Jianguo Xiao Single document keyphrase extraction using neighborhood knowledge // Pro-
ceedings of the 23rd AAAI Conferenceon Artificial Intelligence. – 2008. – P. 855–860. 7. Tsatsaronis G., Varlamis I., Norvag K. SemanticRank: Ranking Keywords and Sentences Using Semantic
Graphs // Proc. of the 23rd International Conference on Computational Linguistics. – 2010. – P. 1074–1082. 8. Zesch T., Gurevych I. Approximate Matching for Evaluating Keyphrase Extraction // International Confer-
ence RANLP 2009. – Borovets, Bulgaria, 2009. – P. 484–489. 9. Su Nam Kim, Baldwin T., Min-Yen Kan. Evaluating N-gram based Evaluation Metrics for Automatic Key-
phrase Extraction // Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010). – Beijing, 2010. – P. 572–580. 10. Kazi Saidul Hasan, Vincent Ng. Conundrums in Unsupervised Keyphrase Extraction: Making Sense of the State-of-the-Art // Proceedings of Coling 2010. – Poster Volume, Beijing, 2010. – P. 365–373. 11. Manning C., Raghavan P., Schütze H. Introduction to Information Retrieval // Cambridge University Press. – 2009. – 581 p. 12. Интернет страница инструмента Standford POS tagging tool [Электронный ресурс]. – Режим доступа: http://nlp.stanford.edu/software/tagger.shtml, свободный. Яз. рус. (дата обращения 09.11.2012).
Попова Светлана Владимировна Ходырев Иван Александрович
– Санкт-Петербургский государственный университет, СанктПетербургский государственный политехнический университет, ст. преподаватель, svp@list.ru
– ООО «Висмарт», зам. генерального директора по науке, kivan.mih@gmail.com
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
85
УДК 004.912
ИЗВЛЕЧЕНИЕ И РАНЖИРОВАНИЕ КЛЮЧЕВЫХ ФРАЗ В ЗАДАЧЕ АННОТИРОВАНИЯ
С.В. Попова, И.А. Ходырев
Для решения задачи аннотирования проводится сравнительный анализ двух подходов ранжирования ключевых фраз. Первый основан на оценке веса извлекаемых фраз с помощью TextRank, второй основан на использовании tf-idf оценки. Исследование проведено на базе коллекции INSPEC dataset. Представлены описание экспериментов и сравнительные результаты. Экспериментально показано, что подход, основанный на использовании tf-idf, дает лучший результат. Ключевые слова: аннотирование, извлечение и ранжирование ключевых фраз, оценка качества аннотаций.
Введение
Тенденция к распространению электронных форматов представления научной информации сти-
мулирует активное развитие научного сектора Интернета. Выражено это появлением огромного числа
электронных публикаций и каталогов цитирования, доступных через сеть интернет, что, в свою очередь,
способствует развитию и научных электронных библиотек. Очевидно, что комфортная работа пользова-
теля с таким большим объемом информации невозможна без быстрого автоматического поиска нужных
материалов. Для решения этой задачи необходимы данные о смысловом содержании документа, пред-
ставленного в виде короткой аннотации. В работе под аннотацией понимается список ключевых
слов/словосочетаний (фраз), характеризующих электронный документ. Наборы ключевых фраз или слов
могут быть также использованы в задачах кластеризации и классификации, в задаче автоматического
построения/пополнения онтологий, в задаче определения основных трендов, в задаче поиска новой ин-
формации и т.д. Под аннотированием в работе будем иметь в виду автоматическое извлечение из текста
ключевых слов/словосочетаний (фраз).
Для решения задачи аннотирования выделяют два подхода. Первый использует обучающую вы-
борку, второй – нет.
В первом подходе задача сводится к разработке классификатора, определяющего для поступивше-
го на вход текста, какие из его частей являются ключевыми фразами, а какие нет [1, 2]. В работе [2]
предложен генетический алгоритм и параметризованная система по извлечению ключевых фраз
Extractor. Генетический алгоритм позволяет определить оптимальные значения параметров. В [1] исполь-
зован наивный байесовский классификатор. В [3] выполнена интеграция лингвистических данных в ма-
шинное обучение, показано преимущество использования информации о частях речи.
В рамках второго подхода наиболее популярным является метод, основанный на представлении
текста в виде графа, предложенный в работе [4]. Вершины графа – целостные части текста (отдельные
слова, n-граммы, предложения). Веса дуг графа характеризуют тип связи между вершинами по выбран-
ному принципу (например, встречаться вместе в окне размера n, т.е. на расстоянии не более n слов друг
от друга). В [4] в качестве вершин графа рассматриваются отдельные слова текста; вес дуги, соединяю-
щей две вершины-слова, показывает, сколько раз эти два слова встретились в тексте в окне n. Для оценки
веса каждой вершины-слова в [4] используется величина, основанная на модификации формулы
PageRank [5]:
S
(vi
)
(1
d
)
d
Vj
In (Vi
)
|
1 Out(v
j
)
|
S
(v
j
),
где In(vi ) – дуги, входящие в вершину vi ; Out(v j ) – дуги, исходящие из вершины v j . Представленная
выше формула была изменена [4] с учетом того, что каждая дуга имеет вес w :
S(vi ) (1 d ) d v j In(Vi )
wij .
wjk
vk Out (v j )
(1)
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
81
ИЗВЛЕЧЕНИЕ И РАНЖИРОВАНИЕ КЛЮЧЕВЫХ ФРАЗ В ЗАДАЧЕ АННОТИРОВАНИЯ
Формула (1) получила название TextRank. Данная формула в [4] используется для расчета весов
вершин-слов. Вершины-слова ранжируются по значению их веса, после чего отбирается только часть
вершин с наибольшим весом. В [4] отобранные таким образом слова склеивались в фразы. Два слова
объединяются в одну фразу, если в оригинальном тексте они непосредственно следуют друг за другом. В
работе [8], помимо слов, рассмотрены многословные части текста – тогда вершинами графа текста явля-
ются группы слов. В качестве таких групп слов, например, взяты n-граммы (последовательность из n
слов, следующих в тексте друг за другом), существительные фразы [8]. Для полученных многословных
вершин рассчитывался вес на основе (1), лучшие вершины отбирались как ключевые фразы. После этого
две последовательности слов склеивались в одну фразу, если они непосредственно следовали друг за
другом в оригинальном тексте. В противном случае группа слов, образующих вершину, рассматривалась
как самостоятельная фраза. Использование многословных частей текста при описанном выше подходе не
дает лучших результатов в сравнении с использованием слов [8].
Оценка веса части текста с помощью TextRank в задаче аннотирования получила дальнейшее разви-
тие. В работе [6] при построении графа учитывается содержание k ближайших документов. В [7] учитыва-
ется информация о семантической близости между построенными вершинами, дополнительно используют-
ся WordNet и Wikipedia. Полученные результаты являются одними из лучших в предметной области.
В данной работе задача извлечения ключевых фраз разделена на два этапа: 1) построение фраз-
претендентов; 2) оценка веса каждой фразы-претендента и выбор лучших k из них как ключевых фраз.
Также как и в работе [4], вес слов рассчитывается с помощью (1). Но, в отличие от [4], здесь не отбира-
ются слова с наивысшей величиной TextRank, которые затем склеиваются в фразы. Вместо этого все сло-
ва после предобработки склеиваются в фразы, после чего оценивается вес каждой фразы, и лучшие фра-
зы отбираются в качестве ключевых. Вес фразы считается равным весу лучшего слова (лучшее слово –
слово в фразе с набольшим весом).
В работе поставлена задача проверки адекватности оценки веса фразы на основе информации о
весах входящих в фразу слов, оцененных с помощью (1). Для сравнительного анализа в работе использо-
ван второй способ оценки весов слов и фраз соответственно [8]. Для этого использована популярная
оценка веса слова tf-idf [11], которая рассчитывается для каждого конкретного слова в каждом документе
как произведение частоты слова в данном документе tf на инвертированную частоту документов idf,
idf
log
N df
,
где N – множество документов, df – число документов, в которых хотя бы раз встретилось слово. Далее
будем обозначать вес слова vi в документе как (tf-idf)(vi). С помощью tf-idf оценивается вес каждого слова в документе. Вес фразы, построенной для текста, считается равным весу слова, входящего в фрау с максимальным значением tf-idf.
Для работы выбрана коллекция INSPEC dataset – одна из самых популярных в исследованиях по аннотированию текстов ключевыми фразами [3, 4, 7, 8, 10]. Коллекция содержит англоязычные аннотации к научным публикациям (abstracts, далее в тексте использован термин «абстракт», под которым понимается аннотация к научной публикации. Заметим, что термин «абстракт» использован во избежание путаницы, так как термин «аннотация» в работе используется для обозначения набора ключевых фраз документа). Коллекция состоит из трех подколлекций: training dataset (1000 документов), evaluation dataset (500 документов), testing dataset (500 документов). Каждый текст имеет «золотой стандарт», состоящий из фраз, отобранных для документа экспертом. Золотой стандарт включает в себя два подмножества аннотаций: contr set и unconter set. Аналогично [3, 4, 7, 8, 10], в работе использовано множество uncontr set. Подробное описание коллекции приведено в [3].
Оценка качества
Изначально для оценки качества извлеченных ключевых фраз использовалась оценка, основанная на F-score [3, 11], интегрирующая информацию о точности и полноте извлеченных фраз (Precision и Recall [11]). Однако данный способ оценки не накладывает четких ограничений на число извлеченных фраз. В работе [8] предложен подход, основанный на использовании R-Precision вместо F-score. R-Precision – значение Precision при условии, что число извлеченных ключевых фраз в точности совпадает с числом фраз в золотом стандарте. Для расчета R-Precision требуется информация о числе правильно извлечен-
ных фраз. Пусть Gt – множество автоматически извлеченных фраз из текста t , Ct – множество ключе-
вых фраз золотого стандарта для текста t (в золотой стандарт для каждого текста входят идеальные ан-
нотации, вручную построенные экспертом). Возникает вопрос, какие из фраз Gt принадлежат Gt Ct . В
большинстве работ по извлечению ключевых фраз используется точное совпадение. Тогда фраза k
(«продвинутый автоматический перевод») и фраза золотого стандарта g («автоматический перевод»)
82 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 1 (83)
С.В. Попова, И.А. Ходырев
распознаются как различные. Аналогично ситуация возникает, например, и для фраз «хороший автомобиль» и «хорошая машина». В [8] сравниваются способы определения правильности извлеченной фразы:
точное совпадение двух фраз (exact); совпадение двух фраз при наличии только морфологического различия (morph);
совпадение двух фраз, если фраза k содержит в себе фразу g (include);
совпадение двух фраз, если фраза g содержит в себе фразу k (part-of).
Показано, что использование part-of является неудачным. Для оценки совпадения двух фраз в [8] использовались exact и include+morph. В работе [9] расширено число способов оценки извлеченной ключевой фразы: BLEU, METEOR, NIST, ROUGE. Определено отношение, лучше отражающее подход экспертов к определению корректности фразы:
rp
| слова _ фразы Gt max{| слова _ фразы Gt
слова _ фразы Сt | |,| слова _ фразы Сt
|}
.
В данной работе для оценки качества результатов аннотирования используются метод и мера,
предложенные в работах [8, 9], что позволяет в дальнейшем использовать результаты, полученные в дан-
ной работе, для сравнительной оценки качества новых алгоритмов, также опирающихся на [8, 9].
Для оценки качества аннотирования используется R-Precision [8]. Для оценки качества каждой
конкретной извлеченной фразы рассматриваются три способа.
1. Случай exact. Здесь
| Gt Ct || {k Gt : g Ct exact(k, g) 1} | ;
где exact(k, g) 1 , если фразы k и g совпадают, exact(k, g) 0 – в противном случае.
2. Случай include. Здесь | Gt Ct || {k Gt : g Ct include(k, g) 1} ;
где include(k, g) 1 , если фраза k содержит в себе фразу g , иначе include(k, g) 0 .
3. Случай rp [9]. Здесь
|
Gt
Ct
|
|
1 Gt
|
kGt
max( | k g | gCt max(| k |,| g
|) )
.
Описание эксперимента
Для формирования исходных данных выполнена предобработка текстов. Каждый текст t представлен набором слов, из которого изъяты стоп-слова и все другие слова, кроме существительных и прилагательных [4]. Для определения части речи слов использован Stanford POS tagger tool [12]. Для каждого текста t построены фразы-претенденты: несколько слов из множества bt объединялись в одну фразу, если в t они непосредственно следовали друг за другом. В построенной фразе-претенденте не могло быть больше четырех слов [8]. В работе поставлена следующая задача: проанализировать способы ранжирования полученных фраз-претендентов, для отбора лучших n из них как ключевых фраз, где n | Ct | .
Примем следующие обозначения: (k) – вес фразы k , где k {s1, s2 ,...sn} ; si или sik – слова фра-
зы k ; TR(sik ) – вес слова sik , рассчитанный с использованием формулы (1). Для ранжирования фраз на основе TextRank и tf-idf вес фразы рассчитывался по формулам
(k
)
max si k
TR(si
),
(k
)
max si k
tf
ifd
(si
).
Для расчета TR(sik ) требуется определить способ оценки веса дуг wij , соединяющий вершины-
слова vi и v j . Рассмотрены варианты: 1. wij occur(vi , v j ) , где occur(vi , v j ) – число раз, когда слова vi и v j встретились вместе в тексте t в
окне n 2 (в работе [4] было показано, что такой размер окна является наилучшим);
2.
wij mi(vi , v j ) , где
mi(vi , v j
)
log
p(vi , v j ) N p(vi ) p(v j )
есть взаимная информация между
vi
и
vj ,
p(vi , v j )
–
число раз, когда слова vi и v j встретились вместе в текстах коллекции в окне 2, p(vi ) , p(v j ) – число
вхождений слов vi и v j в текстах коллекции, N – общее число словоформ в коллекции;
3. wij tf idf (vi ) tf idf (vj ) .
Также поставлен дополнительный эксперимент: для ранжирования на основе TextRank строился граф, вершинами которого являлись все слова коллекции после предобработки, а wij p(vi , v j ) . Отличие
от рассмотренного выше способа расчета весов вершин на основе формулы (1) – в том, что используется один граф для всей коллекции, а не отдельные графы для каждого текста.
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
83
ИЗВЛЕЧЕНИЕ И РАНЖИРОВАНИЕ КЛЮЧЕВЫХ ФРАЗ В ЗАДАЧЕ АННОТИРОВАНИЯ
Фразы ранжировались по значению весов. Лучшие n фраз с наибольшими значениями весов отбирались как ключевые фразы. На завершающей стадии эксперимента проводилась постобработка. Если для одного текста в качестве претендентов были получены две фразы, такие, что одна является частью другой, то оставлялась одна фраза наибольшего размера.
Результаты экспериментов и обсуждение
Результаты экспериментов представлены для трех подколлекций INSPEC dataset: test dataset, evaluate dataset, trial dataset (табл. 1–3). Приняты следующие обозначения: 1. ранжирование фраз с помощью TextRank:
TR for text – граф строился для каждого отдельного текста, wij occur(vi , v j ) ;
TR for text*mi – граф строился для каждого отдельного текста, wij mi(vi , v j ) ;
TR for text**tf-idf – граф строился для каждого отдельного текста, wij tf idf (vi ) tf idf (vj ) ;
TR collection – граф строился для всей коллекции, wij p(vi , vj ) ; 2. результаты ранжирования с помощью tf-idf.
INSPEC dataset test dataset
evaluate dataset
trial dataset
TR for text
0,22 0,21 0,21
TR for text*mi
0,21
0,20
0,19
TR for text**(tf-idf)
0,23
0,22
0,22
TR collection
0,19 0,17 0,16
tf-idf
0,28 0,26 0,26
INSPEC dataset test dataset
evaluate dataset
trial dataset
Таблица 1. R-Precision exact
TR for text TR for text* TR for text** TR collection
0,29 0,27 0,27 0,26 0,27 0,26
0,31 0,29 0,29
0,25 0,23
0,23
tf-idf
0,37 0.34 0.34
INSPEC dataset test dataset
evaluate dataset
trial dataset
Таблица 2. R-Precision include
TR for text TR for text* TR for text** TR collection
0,42 0,41 0,40 0,39 0,40 0,40
0,43 0,42 0,42
0,37 0,36 0,35
tf-idf
0,48 0.46 0.46
Таблица 3. R-Precision rp
Результаты показали, что ранжирование фраз, основанное на TextRank, уступает ранжированию на основе tf-idf. TextRank использует данные, собранные из одного текста. Такая ограниченность плохо сказывается на качестве аннотирования. Tf-idf интегрирует информацию о важности слов в отдельном тексте и информацию о распространенности слов в коллекции, позволяя отсеять общеупотребительные для коллекции слова, не потеряв важных для текста терминов. Интересно, что tf-idf хорошо работает для коллекций абстрактов, несмотря на то, что документы коллекции является короткими текстами, а используемая коллекция – сравнительно небольшая. Формула tf-idf требует сбора статистики по встречаемости слов, для чего обычно требуется большой объем текстовых данных. Вывод: важные слова часто повторяются в конкретной аннотации к научной статье и редки в других аннотациях (по другим темам). Такая закономерность позволяет собрать нужную статистику на небольшом наборе данных и обосновывает использование tf-idf.
Использование wij mi(vi , v j ) для TextRank не улучшает качества ранжирования по сравнению с
классическим вариантом wij occur(vi , v j ) . Некоторое улучшение достигается за счет использования для
оценки дуг wij tf idf (vi ) tf idf (vj ) . Использование взаимной информации между словами:
mi(vi , vj ) , не улучшает качества ранжирования в сравнении с tf-idf, несмотря на то, что данные собира-
ются по всей коллекции. При использовании mi оценивается не значимость отдельных слов, а значимость связей между словами. Эта мера имеет тенденцию к завышению значимости связей с/между редкими (случайными) словами. В работе при расчете mi не ставилось ограничение, которое позволило бы рассматривать связи только со словами, встретившимися в коллекции больше, чем l раз (в противном
84 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 1 (83)
С.В. Попова, И.А. Ходырев
случае вес связи был бы равен нулю). Полученный результат служит индикатором того, что в аннотациях к публикациям ключевые слова не бывают случайными (одиночными относительно коллекции).
Результаты, полученные в дополнительном эксперименте, могут считаться неудовлетворительными. Вероятно, это связано с тем, что теряется информация об особенностях отдельных текстов.
Еще одно интересное наблюдение касается способа оценки каждой автоматически извлеченной фразы. Рассматривалось три способа: exact, inclide, rp. Существует высокая корреляция между результатами, полученными для каждого из этих способов. Коэффициент корреляции Спирмена рассчитан для пар exact-include, include-rp, exact-rp и составил 0,98–0,99, для расчета коэффициентов использовано 15 наблюдений (Табл. 1 для exact, Табл. 2 для include, Табл. 3 для rp), корреляция значима на уровне 0,001. Была проверена корреляция между результатами, полученными в [8], где использовались такие способы оценки, как exact и include+morph. Получено значение 0,91, корреляция значима на уровне 0,001. Планируется провести дополнительные исследования, отвечающие на вопрос: «насколько высока вероятность того, что рассматриваемые способы могут быть взаимозаменяемыми», что позволит использовать единственный способ оценки качества.
Заключение
В работе представлены результаты серии экспериментов по извлечению ключевых слов на базе коллекции INSPEC datset с использованием Stanford POS tagger tool. Показано, что для данной коллекции tf-idf предложенный авторами способ ранжирования дает лучший результат, чем TextRank. Использование tf-idf требует сбора статистики по встречаемости слов, для чего обычно требуется большой объем данных. Экспериментально полученный результат показывает пригодность tf-idf для обработки небольших коллекций абстрактов. Это означает, что важные для текста слова часто повторяются в конкретном абстракте и редки в других абстрактах, что можно считать обоснованием использования tf-idf для небольших коллекций абстрактов. По результатам экспериментов сделан вывод, что в абстрактах ключевые слова имеют вхождение в коллекцию большее, чем 1–2 раза. Показано, что используемые в работе три способа оценки качества аннотирования могут оказаться взаимозаменяемыми.
Работа выполнена в рамках ФЦП «Научные и научно-педагогические кадры инновационной России» поисковые научно-исследовательские работы по лоту шифр «2011-1.2.1-302-031», государственный контракт № 16.740.11.0751.
Литература
1. Frank E., Paynter G.W., Witten I.H., Gutwin C., Nevill-Manning C.G. Domain-specific keyphrase extraction // Proc. of IJCAI. – 1999. – P. 688–673.
2. Turney P. Learning to Extract Keyphrases from Text. – NRC/ERB-1057. – 1999. – February 17. – 43 p. 3. Hulth A. Improved automatic keyword extraction given more linguistic knowledge // Proc. of the Conference
on Empirical Methods in Natural Language Processing. – 2003. – P. 216–223. 4. Mihalcea R., Tarau P. TextRank: Bringing order into texts // Proc. of the Conference on Empirical Methods
in Natural Language Processing. – 2004. – P. 404–411. 5. Brin S. and Page L. The anatomy of a large-scale hypertextual web search engine // Computer Networks and
ISDN Systems. – 1998. – V. 30. – № 1–7. – P. 107–117. 6. Wan Xiaojun and Jianguo Xiao Single document keyphrase extraction using neighborhood knowledge // Pro-
ceedings of the 23rd AAAI Conferenceon Artificial Intelligence. – 2008. – P. 855–860. 7. Tsatsaronis G., Varlamis I., Norvag K. SemanticRank: Ranking Keywords and Sentences Using Semantic
Graphs // Proc. of the 23rd International Conference on Computational Linguistics. – 2010. – P. 1074–1082. 8. Zesch T., Gurevych I. Approximate Matching for Evaluating Keyphrase Extraction // International Confer-
ence RANLP 2009. – Borovets, Bulgaria, 2009. – P. 484–489. 9. Su Nam Kim, Baldwin T., Min-Yen Kan. Evaluating N-gram based Evaluation Metrics for Automatic Key-
phrase Extraction // Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010). – Beijing, 2010. – P. 572–580. 10. Kazi Saidul Hasan, Vincent Ng. Conundrums in Unsupervised Keyphrase Extraction: Making Sense of the State-of-the-Art // Proceedings of Coling 2010. – Poster Volume, Beijing, 2010. – P. 365–373. 11. Manning C., Raghavan P., Schütze H. Introduction to Information Retrieval // Cambridge University Press. – 2009. – 581 p. 12. Интернет страница инструмента Standford POS tagging tool [Электронный ресурс]. – Режим доступа: http://nlp.stanford.edu/software/tagger.shtml, свободный. Яз. рус. (дата обращения 09.11.2012).
Попова Светлана Владимировна Ходырев Иван Александрович
– Санкт-Петербургский государственный университет, СанктПетербургский государственный политехнический университет, ст. преподаватель, svp@list.ru
– ООО «Висмарт», зам. генерального директора по науке, kivan.mih@gmail.com
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
85