Работаем с 2009 года Более 300 успешных проектов Офис в москве и санкт-петербурге
+7(495)320-31-31

Поиск по микроблогам, Яндекс на TREC 2011

Эксперименты и улучшение функции ранжирования результатов поиска по микроблогам

Злата Обуховская, Константин Первышев, Андрей Стискин, Павел Сердюков Яндекс

Введение

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

По вопросам ранжирования мы решили полагаться на следующие источники информации:

Мы предположили, что количество ретвитов является хорошим социальным индикатором «интересности» документа и прогнозы по ретвиттингу будут важны для дальнейшего ранжирования. Но мы обнаружили проблему низкой полноты TF-поиска (TF – term frequency, частота повторения слова в наборе документов/одном документе. Рассчитывается как число вхождения слов по отношению к общему количество слов.), если он применяется к коротким твитам. Это побудило нас использовать гибкую модель важности слова и расширять запросы, во избежание нерелевантных результатов.

Поисковый фреймворк

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

Для начала нам потребовалось вычислить зависящую от времени, запроса и других факторов статистику без повторного индексирования данных на каждом заходе. Мы попытались ускорить процесс поиска и упростить введение новых характеристик в систему. В результате наш поисковый фреймворк смог определять характеристики пар запрос-твит во время полного сканирования корпуса твитов, обобщать их, если нужно и повторно использовать во время последующих сеансов сканирования. Таким образом процесс поиска состоял из фазы полного сканирования и фазы обобщения. Все тестовые темы обрабатывались параллельно друг другу, что занимало всего 4 минуты в кластере из 500 рабочих машин.

Характеристики

В этой части мы опишем характеристики и детали модели ранжирования. Результаты эксперимента описаны в разделах 4 и 5.

Характеристики запроса-документа и расширение запросов

Частотные (TF) текстовые характеристики плохо работают со статусами твиттера, так как твиты намного короче обычных веб-документов. Для того, чтобы получить максимум информации из текстовых характеристик, необходимо использовать расширение запросов.

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

[IDF – inverse document frequency, инверсия частоты слова в документах. Учёт IDF уменьшает вес слов в широком употреблении.]

[Триграм (в лингвистике) – разбиение фразы и/или слова на триграмматоны. Это особый случай N-грама, где N = 3. Часто используется для статистического анализа текста.

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

Словесный триграм «продвижение сайтов петербург» имеет следующий вид символьных триграмов:

Некоторые текстовые характеристики, использующие расширение:

ID Описание
0 SumIDF_Q Сумма IDF слов запроса
1 SumIDF_QEx Сумма IDF слов расширенного запроса
2 3Gram_Q Коэфф. Жаккара для наборов символьных триграмов документа и запроса
3 3Gram_QEx Коэфф. Жаккара для наборов символьных триграмов документа и расширенного запроса
4 NWords_Q Количество слов в запросе
5 NWords_QEx Количество слов в расширенном запросе
6 SumPRel_QEx Сумма показателей релевантности для слов, добавленных при расширении запроса

Таблица 1. Текстовые характеристики.

Мы использовали информацию из внешних источников для создания двух групп характеристик независимых от запросов. Помеченные * характеристики использовались в работе [2].

ID Описание
7 TweeLen* Число символов в твите
8 NExcl* Число вопросительных и восклицательных знаков в твите
9 NSmiles* Число смайликов в твите
10 NOutLinks* Число внешних ссылок в твите
11 NHTags* Число хештегов
12 AvgWordLen* Средняя длина слова (количество символов)
13 SelfCentrism* Число местоимений от первого лица (я, мне, меня, мой)
14 PosSent* Число положительных слов в документе
15 NegSent* Число негативных слов в документе
16 NStopword* Число стоп-слов
17 TextDiversity Отношение числа уникальных словесных триграмов к общему количеству слов в твите

Таблица 2. Информационные характеристики.

ID Описание
18 NFollowers* Число фолловеров пользователя
19 NTweets* Число твитов пользователя
20 NFollowees* Число взаимофолловеров (т.е. «друзей») пользователя
21 NListed* Число групп, в которых состоит пользователь
22 Verified* True, если аккаунт пользователя подтверждён
23 FollowersRatio Соотношение друзья/фолловеры
24 NLastStatRT Число ретвитов последнего статуса пользователя

Таблица 3. Социальные характеристики.

Функция ранжирования

В этом разделе мы описываем машинное обучение ранжированию в тестах TREC. Проводится анализ улучшений, введённых после распределения оценок NIST (Национального Института Стандартов и Технологий США). Так же рассматривается влияние наших прогнозов «интересности» (см. раздел 4.2) на качество ранжирования.
Мы используем Градиентные Древа Решений (GBDT, Gradient Boosted Decision Trees) для машинного обучения. Во всех тестах применялось расширение запросов.
Мы включили в зону (пул) обучения следующие условия: для каждой из 12 представленных NIST тем-образцов мы выбрали около 80 твитов, которые содержали хотя бы одну из текстовых характеристик, превышающих заданный предел. Всем твитам была дана оценка «релевантен» или «нерелевантен».

Тесты 1 и 2

Для обоих тестов мы подготовили регрессию текстовых характеристик (см. раздел 3.1). Первая и вторая попытки отличались числом итераций, проведённых алгоритмом обучения. Результаты показаны в Таблице 5.

Тесты 3 и 4

Мы использовали регрессию для Теста №3 и классификацию для Теста №4. В дополнение к текстовым характеристикам (см. раздел 3.1) мы добавили характеристики, основанные на прогнозах по ретвиттингу.

Наши предположения о ретвиттинге для прогнозов «интересности» даны в разделе 5.1.1.

Для создания предсказателей (анализаторов прогноза) ретвитов, мы подготовили несколько классификаторов с количественным классами ретвиттинга в качестве целей (0 соотв. 0 ретвитов, 1 соотв. 0-10 ретвитов, 2 соотв. >10 ретвитов) и смешали различные виды характеристик и образцов для обучения.

ID Вид характеристики Тип аккаунта Число фолловеров
25 Inf_nVer_L200 информационная не подтверждён <200
26 Inf_Ver_M200 информационная подтверждён >200
27 Soc_nVer_L500 социальная не подтверждён <500
28 Soc_Ver_M500 социальная подтверждён >500

Таблица 4. Предсказатели ретвитов.

Результаты TREC

Наши результаты в соответствии с NIST.

  Тест 1 Тест 2 Тест 3 Тест 4
P_30 (релевантные) 0.2027 0.2156 0.2190 0.2388
P_30 (высокорелевантные) 0.0667 0.0697 0.0515 0.0646

Таблица 5. Результаты тестов TREC.

Повышение качества

Получив от NIST оценок 50 тем твитов, мы смогли улучшить нашу функцию ранжирования. Используя положительные образцы из оценочных данных мы увеличили P_30 с 0.2388 до 0.2923 для релевантных твитов и с 0.0697 до 0.1011 для высокорелевантных твитов. Используя как положительные, так и негативные образцы, мы смогли повысить P_30 ещё больше.

Далее мы рассматриваем функцию ранжирования, которая была создана на основе случайных негативных образцов.Формула создавала на следующей основе: из 16 миллионов твитов были выбраны те, что содержали хотя бы одно слово из расширения темы. Из этих твитов в пул обучения были выбраны все релевантные твиты (1800 штук) и несколько случайных.

Для итоговой формулы была рассчитана оценка через 5-кратную перекрёстную проверку по 50 темам. Как видно из результатов, P_30 сильно зависит от числа негативных образцов (т.е. нерелевантных твитов) в пуле обучения:

Негативные образцы 50% 80% 94% 98.5%
P_30 (релевантные) 0.1998 0.2462 0.2827 0.2923
P_30 (высокорелевантные) 0.0697 0.0838 0.0919 0.1011

Наилучшее значение P_30 было получено при соответствии негативных образцов 98.5% от всех образцов.

Наша новая функция ранжирования имеет P_30 гораздо более высокий, чем раньше. Главной причиной является то, что во время официальных тестов, у нас было намного меньше негативных образцов (76%), чем необходимо для оптимальных значений. Кроме того, новая функция работала с 40 темами, а тесты – только с 12-ю.

Мы провели эксперименты для оценки зависимости P_30 от числа тем в пуле. Для 12 тем итоговый P_30 составлял 0.2684 и явно зависел от конкретных тем, формирующих пул обучения.

  P_10 P_30 P_50 P_100
Тест 1 0.3653 0.3122 0.2914 0.2308
Тест 2 0.4429 0.3469 0.2931 0.2276
Тест 3 0.2531 0.2252 0.2082 0.1749
Тест 4        
  NDCG_10 NDCG_30 NDCG_50 NDCG_100
Тест 1 0.3806 0.4004 0.4277 0.4625
Тест 2 0.4763 0.4529 0.4578 0.4865
Тест 3 0.2554 0.2860 0.3137 0.3530
Тест 4 0.3067 0.3228 0.3416 0.3753

Таблица 6. Качество функций ранжирования, подготовленных по оценкам NIST.

Дальнейшие эксперименты

План экспериментов

Для дальнейших экспериментов мы переработали алгоритм нашей поисковой системы. В данном разделе мы проводим эксперименты, используя простой метод поиска и поиск с расширеним запроса и внешних ссылок. Объединив характеристики, описанные в разделах 3 и 5.1.1, мы создали несколько функций ранжирования используя регрессию с ГДР (GBDT). В следующих разделах описаны подробности экспериментов и оценки качества.

Искусственные характеристики или предсказатели «интересности»

Отсутствие определённых меток навело нас на на мысль о майнинге данных из статусов твиттера. Ретвиттинг является хорошим социальным индикатором интересности твитов, поэтому мы используем число ретвитов для подготовки функции прогноза ретвиттинга по различных типам характеристик (см. раздел 3). Мы называем эти искуственно созданные характеристики «предсказателями интересности». Выходными данными предсказателей являются новые значения характеристик для подготовки итоговой функции ранжирования.
Очевидным выводом об использовании ретвитов в качестве меток было то, что данные об интересности могут быть в определённой степени зашумлены. Ведь возможно, что популярных пользователей ретвитят только из-за их популярности?

Мы попытались «очистить» данные, обучая «предсказателей» по определённым образцам. Образцы были созданы разделением всего корпуса на части по социальных характеристикам.

ID Тип характеристики Тип аккаунта Число фолловеров
29 Inf_Soc_nVer_M200 информационная, социальная не подтверждённый >200
30 Inf_Soc_nVer_L200 информационная, социальная не подтверждённый <200
31 Inf_Soc_nVer_M500 информационная, социальная не подтверждённый >500
32 Inf_Soc_nVer_L500 информационная, социальная не подтверждённый <500
33 Inf_Soc_nVer_M1000 информационная, социальная не подтверждённый >1000
34 Inf_Soc_nVer_L1000 информационная, социальная не подтверждённый <1000
35 Inf_Soc_Ver информационная, социальная подтверждённый  
36 Inf_nVer_M200 информационная не подтверждённый >200
37 Inf_nVer_L200 информационная не подтверждённый <200
38 Inf_nVer_M500 информационная не подтверждённый >500
39 Inf_nVer_L500 информационная не подтверждённый <500
40 Inf_nVer_M1000 информационная не подтверждённый >1000
41 Inf_nVer_L1000 информационная не подтверждённый <1000
42 Inf_Ver информационная подтверждённый  
43 Soc_nVer_M200 социальная не подтверждённый >200
44 Soc_nVer_L200 социальная не подтверждённый <200
45 Soc_nVer_M500 социальная не подтверждённый >500
46 Soc_nVer_L500 социальная не подтверждённый <500
47 Soc_nVer_M1000 социальная не подтверждённый >1000
48 Soc_nVer_L1000 социальная не подтверждённый <1000
49 Soc_Ver социальная подтверждённый  

Таблица 7. Предсказатели интересности.

Оценка качества

Мы оценили MAP, P_30 и BPREF при помощи программы оценки TREC, используя 5-кратную перекрёстную проверку на 50 темах. Все значения качества в последующих разделах усреднены по итерациям (фолдам).

Текстовые характеристики

В данном эксперименты мы подготовили функцию ранжирвания по текстовым (см. таблицу 1) характеристикам, не использующим расширение.

Набор характеристик P_30 MAP BPREF
0, 2, 4 0.4103 0.4112 0.1804
0 0.3677 0.3616 0.1006
2 0.1646 0.1503 0.0058
4 0.3044 0.3104 0.0763

Таблица 8. Без расширений, текстовые характеристики.

Социальные и информационные характеристики

Данный эксперимент измерял «силу» постоянных характеристик (см. раздел 3.2).

Набор характеристик P_30 MAP BPREF
7 0.1092 0.1190 0.0007
8 0.0333 0.0748 0.0007
9 0.0329 0.0818 0.0007
10 0.0333 0.0822 0.0007
11 0.2870 0.2656 0.0679
12 0.0639 0.0966 0.0014
13 0.0341 0.0793 0.0007
14 0.0192 0.0870 0.0003
15 0.0239 0.0675 0.0007
16 0.0412 0.0842 0.0007
17 0.0979 0.1240 0.0031
18 0.0364 0.0752 0.0010
19 0.0356 0.0740 0.0006
20 0.0247 0.0693 0.0007
21 0.0655 0.0895 0.0047
22 0.0652 0.0898 0.0011
23 0.0820 0.0950 0.0031
24 0.0382 0.0823 0.0007

Таблица 9. Без расширений, сила социальных и информационных характеристик.

Расширение запроса и внешних ссылок

Для последующих экспериментов мы использовали расширение запроса по псевдо-релевантной обратной связи (см. раздел 3.1). Так же мы выбрали заголовки 20% документов по ссылкам в твитах и создали на их основе псевдо-твиты.

Текстовые характеристики

При учёте силы характеристик (сравните Таблицу 10 с Т. 8) и числа релевантных документов в поисковых результатах (см. Таблицу 11), кажется, что расширение запросов не особо помогает находить релевантные документы, хотя характеристики, основанные ра расширениях (1, 3, 5, 6) помогают в ранжировании.

Набор характеристик P_30 MAP BPREF
0-6 0.4744 0.4810 0.2567
0 0.3646 0.3607 0.1052
1 0.3809 0.3559 0.0485
2 0.1773 0.1742 0.0105
3 0.1467 0.1465 0.0051
4 0.2761 0.2675 0.0809
5 0.2571 0.2244 0.0109
6 0.2344 0.2057 0.0066

Таблица 10. Текстовые характеристики с расширениями.

Число результатов 50 100 500 1000
С расширением 1005 1563 2421 2497
Без расширения 894 1397 2405 2497

Таблица 11. Число релевантных документов в выдаче, суммарно по 50 темам.

h3>Информационные и социальные характеристики

В данном эксперименте показано, насколько слабо характеристики (см. Таблицу 9) помогают в улучшении качества.

Набор характеристик P_30 MAP BPREF
0-6 0.4744 0.4810 0.2567
0-6, 7 0.5010 0.5069 0.2698
0-6, 8 0.4854 0.4906 0.2622
0-6, 9 0.4738 0.4821 0.2666
0-6, 10 0.4959 0.5025 0.3228
0-6, 11 0.4864 0.4876 0.2491
0-6, 12 0.5104 0.5171 0.3136
0-6, 13 0.4830 0.4858 0.2630
0-6, 14 0.4843 0.4914 0.2717
0-6, 15 0.4861 0.4899 0.2702
0-6, 16 0.5024 0.5035 0.2685
0-6, 17 0.4806 0.4852 0.2566
0-6, 18 0.5024 0.5026 0.2732
0-6, 19 0.5011 0.5005 0.2815
0-6, 20 0.4981 0.5003 0.2707
0-6, 21 0.5001 0.5022 0.2836
0-6, 22 0.4742 0.4826 0.2683
0-6, 23 0.4975 0.4990 0.2844
0-6, 24 0.4810 0.4848 0.2551

Таблица 12. Сила информационных и социальных характеристик с расширением.

Характеристики предсказателя

Предсказатели в Таблице 13 были подготовлены в виде регрессии для прогнозирования числа ретвитов. Но ни один из них не помог повысить качество.

Тип характеристик P_30 MAP BPREF
0-6 0.4744 0.4810 0.2567
0-6, 29-49 0.4711 0.4784 0.2545
0-6, 29 0.4648 0.4459 0.2023
0-6, 30 0.4575 0.4599 0.2346
0-6, 31 0.4596 0.4674 0.2600
0-6, 32 0.4684 0.4661 0.2403
0-6, 33 0.4618 0.4669 0.2659
0-6, 34 0.4616 0.4580 0.2375
0-6, 35 0.4646 0.4655 0.2620
0-6, 36 0.4535 0.4509 0.2111
0-6, 37 0.4635 0.4630 0.2396
0-6, 38 0.4557 0.4445 0.2213
0-6, 39 0.4599 0.4642 0.2461
0-6, 40 0.4451 0.4322 0.2061
0-6, 41 0.4530 0.4500 0.2224
0-6, 42 0.4518 0.4450 0.2166
0-6, 43 0.4647 0.4590 0.2456
0-6, 44 0.4601 0.4607 0.2537
0-6, 45 0.4604 0.4635 0.2606
0-6, 46 0.4625 0.4627 0.2360
0-6, 47 0.4602 0.4562 0.2590
0-6, 48 0.4574 0.4558 0.2466
0-6, 49 0.4551 0.4576 0.2324

Таблица 13. Сила предсказателей с расширениями.

Выводы

В данной статье мы поделились опытом создания поиска по микроблогам.

Расширения запросов не улучшили полноту выдачи, но текстовые характеристики с расширениями улучшили качество ранжирования. Характеристики не зависящие от запросов, а основанные на тексте самого документа и профиле автора дали требуемое улучшение качества. Использование ретвиттинга для прогнозирования интересности так же не особо помогло в задаче поиска и ранжирования. Несмотря на это, мы склоняемся к тому, что дальнейшие исследование корреляции между различными значениями, полученными из твиттера (например, корреляция между количеством фолловеров и ретвитов) дадут новые возможности в создании поиска по микроблогам.

Источники

[1] W. B. Croft, V. Larvrenko. Relevance-Based Language Models. Center for Intelligent Information Retrieval, Department of Computer Science, University of Massachusetts, Amherst, 2001.

[2] C. Castillo, M. Mendoza, B. Poblete. Information Credibility on Twitter. WWW 2011 Session: Information Credibility.

[3] M. Efron and G. Golovchansky. Estimation Methods for Ranking Recent Information. In SIGIR, 2011.

[4] N. Naveed, T. Gottron. J. Kunegis and A. Alhadi. Searching microblogs: coping with sparsity and document quality. In 20th ACM Conference on Information and Knowledge Management (CIKM 2011).

Перевод материала «Yandex at TREC 2011 Microblog Track» выполнил Роман Мурашов

Полезная информация по продвижению сайтов:

Перейти ко всей информации