Научный семинар НИЯУ МИФИ, 17 марта 2010 года Руководитель группы разработки качества поиска Андрей Стыскин Современные проблемы Интернет поиска

Что представляет из себя современный Интернет поиск?

Задачи Интернет поиска: Ответ на заданные вопросы: Навигационный поиск (найти место в интернете, телефон организации) Тематический поиск (получить информацию об объекте или явлении) Транзакционный поиск (где купить, скачать) Ответ на недозаданные вопросы и неправильно заданные вопросы Саджест Опечатки

SERP

Саджест Инструмент угадывания запроса по нескольким первым буквам

Колдунщики

Измерение качества поиска

Классический подход Полнота/точность MAP Dcg/ndcg

Поисковое поведение - первые 5 секунд

Поисковое поведение

Метрика удовлетворенности пользователя Pfound Мы пытаемся посчитать вероятность того, что пользователь найдет ответ на свой вопрос

Google vs Яндекс

Обучение ранжированию (Learning To Rank)

Подбор формулы У нас есть набор четверок {оценка, запрос, документ, набор факторов} Факторы: текстовая релевантность (TF*IDF, BM25), линковая релевантность, статическая релевантность (PageRank), запросные Нам нужно аппроксимировать оценку зная значения факторов – задача регрессии Нам нужно максимизировать Pfound - стохастический алгоритм Differential Evolution

О чём не будет в презентации: Методов Learning To Rank (вопросов оцененности, обучения на частично определенных данных, обучения на пользовательских данных) Лингвистики Вопросов текстового/линкового/статического ранжирования Вопросов, связанных с обходом Интернет

Тематические поиски

Какие бывают вертикальные поиски? Быстрый поиск Музыка/Видео/Картинки Задача разнообразия

Проблемы обычного ранжирования Свежесть Важно не количество ссылок, а производная Нет многих статических факторов, которые зависят от времени Нет сигнала в базе ассесоров (невоспроизводимость вчерашних событий в базе)

Решение Свежесть База быстрых документов Быстрые факторы (Яндекс.Бар, ICQ, ссылки из блогов) Расчет вероятности потребности в свежих результатах: соотношение найденного в быстрой базе к Веб-базе Смешивание (о модели смешивания чуть позже)

Проблемы обычного ранжирования Музыка/Видео Скорость обхода Интернет (из-за бана роликов) Специальные факторы (число просмотров)

Решение Музыка/Видео Специализированный поиск Классификатор запросов Подмешивание результатов

Запросные классификаторы Классификатор запросов Маркеры Переформулировки/Перезадания Словари исполнителей/произведений Высокая точность, низкая полнота (до 30%-40%)

Классификаторы по выдаче Обучим наивный Байесов классификатор В качестве обучающей выборки возьмем запросы, классифицированные точным классификатором, против всех остальных Признаки: домены сайтов, присутсвующие в top10 (либо кликнутые домены) Обучим классификатор и подберем порог срабатывания, чтобы обеспечить лучшую F- меру на размеченном множестве Точность: 75% на классе музыкальных запросов Полнота: 75%

Постановка проблемы Задача разнообразия Один и тот же подход и в задаче категоризации, и в задаче разнообразия Рассматриваем 2 типа запросов (объект) (объект) (потребность) Пример Sony Ericsson w800i Sony Ericsson w800i цены

Некоторые потребности свидетельствуют о принадлежности к категории Категория «телеканалы»: телепрограмма онлайн трансляция телеканал Уточнения-«свидетели» отличаются от важных потребностей: телепрограмма – и то, и другое канал – ни то, ни другое Итого: список «свидетелей» тоже можно получать в полуавтоматическом режиме; это другой список Уточнения – «свидетели» Задача разнообразия

Собираем новые объекты, используя «свидетелей» Полуавтоматический режим: выделяем потенциальных «свидетелей» (аналогично tf*idf) вручную фильтруем, разбиваем на группы; используем правило «по одному свидетелю хотя бы из 2 групп» высокая точность, маленькая полнота проблема омонимов («Нирвана» - фильм или группа? «Обитаемый остров» - книга или фильм?) Итого: machine learning здесь сложен, но это не страшно: получается и вручную Категоризация Задача разнообразия

фильм музыкальное произведение музыкант или группа книга писатель или поэт город страна автомобиль банк ресторан еда (блюдо) организация компьютерная игра гаджет (телефон, mp3-плеер) мультфильм заболевание лекарство радиостанция телеканал софт ник жж-блоггера знаменитый человек товар или торговая марка тема для реферата Категоризация Задача разнообразия

32931 объект (примерно половина – из двух обширных категорий «товар» и «тема для реферата») >8% запросов из потока распознаются как [(объект известной категории)] >3% запросов распознаются как [(объект) (известная потребность)] высокая точность («на глаз») низкая полнота (опять же, «на глаз») некоторые категории таким способом не выделяются, т.к. невозможно найти «свидетелей». Пример: футбольные клубы, футболисты Итоги Задача разнообразия

у пользователя в голове ровно одна из множества потребностей но при этом выделяемые потребности могут перекрываться («саундтрек» и «скачать mp3», «википедия» и «биография») сайты и страницы отвечают сразу на несколько потребностей с разной точностью (например, морда городского портала); иногда только на одну (например, страница с рецептом блюда), но для нас это не является специальным случаем пользователи высказывают свои потребности в явном виде в формате [(объект) (важная потребность)] с репрезентативной относительной частотой (предположение откровенности) Матмодель Задача разнообразия

Зная вероятности p ik, с которыми k-тая страница выдачи (из N) отвечает на i-тую потребность, можем вычислить аналог pfound, взвешенный по частотам потребностей w i. В процессе вычисления на k-том шаге будут известны plook ik и pfound ik. Ответом будет Теорема. В предположении, что нам известны p ik и w i, в идеальной выдаче на каждом шаге k сумма максимальна. Для сравнения, если максимизировать по pfound без разнообразия, максимальной на каждом шаге будет сумма Схема доказательства. Сравниваем две выдачи, отличающиеся перестановкой соседних позиций Матмодель Задача разнообразия

Вопросы? Предложения?

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

Руководитель группы разработки качества поиска +7 (495) Андрей Стыскин