SEO-Константа
Яндекс.Директ + оптимизация
Создание поиска по микроблогам – сложная задача во многих аспектах. Одной из её проблем является конструирование надёжной архитектуры поисковой системы. В нашей работе мы сконцентрировались на а) поиске твитов (коротких записей в сервисе 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 твитов, которые содержали хотя бы одну из текстовых характеристик, превышающих заданный предел. Всем твитам была дана оценка «релевантен» или «нерелевантен».
Для обоих тестов мы подготовили регрессию текстовых характеристик (см. раздел 3.1). Первая и вторая попытки отличались числом итераций, проведённых алгоритмом обучения. Результаты показаны в Таблице 5.
Мы использовали регрессию для Теста №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. Предсказатели ретвитов.
Наши результаты в соответствии с 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 темам.
В данном эксперименте показано, насколько слабо характеристики (см. Таблицу 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. Сила предсказателей с расширениями.
В данной статье мы поделились опытом создания поиска по микроблогам.
Расширения запросов не улучшили полноту выдачи, но текстовые характеристики с расширениями улучшили качество ранжирования. Характеристики не зависящие от запросов, а основанные на тексте самого документа и профиле автора дали требуемое улучшение качества. Использование ретвиттинга для прогнозирования интересности так же не особо помогло в задаче поиска и ранжирования. Несмотря на это, мы склоняемся к тому, что дальнейшие исследование корреляции между различными значениями, полученными из твиттера (например, корреляция между количеством фолловеров и ретвитов) дадут новые возможности в создании поиска по микроблогам.
Перевод материала «Yandex at TREC 2011 Microblog Track» выполнил Роман Мурашов
Полезная информация по продвижению сайтов:
Перейти ко всей информации