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

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

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

Введение

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

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

• Текстовые данные: сам твит и заголовок страницы по URL в твите.
• Активность пользователей (ретвиты).
• Использовать последние две буквы возможного стема в качестве индекса, чтобы получить подходящее древо стема. Если ни у одного стема нет этих двух букв, перейти к следующей границе.

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

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

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

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

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

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

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

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

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

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

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

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

• быстрая красная лисица
• красная лисица перепрыгивает
• лисица перепрыгивает через
• перепрыгивает через ленивую
• через ленивую собаку.

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

• про сай пет
• род айт ете
• одв йто тер
• дви тов ерб
• виж ов_ рбу
• иже в_п бур
• жен _пе ург
• ени пет
• ние]

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

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

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

В этом разделе мы описываем машинное обучение ранжированию в тестах 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 ретвитов) и смешали различные виды характеристик и образцов для обучения.

Результаты TREC

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выводы

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

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