Хабрахабр

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

Мы научились использовать саджест для того, чтобы предугадывать итоговый запрос пользователя и загружать поисковую выдачу до нажатия кнопки «Найти». Поисковые подсказки (саджест) — это не только пользовательский сервис, но ещё и очень мощная языковая модель, хранящая миллиарды поисковых запросов, поддерживающая нечёткий поиск, персонализацию и многое другое.

И, конечно, нам нужен был крутой классификатор, определяющий, нужно ли загружать поисковый запрос заранее: этот классификатор должен соблюдать баланс между ускорением загрузки, дополнительным трафиком и нагрузкой на Поиск. Внедрение этой технологии – пререндера – потребовало многих интересных решений в мобильной разработке, разработке поискового рантайма, логов, метрик. Сегодня я расскажу о том, как нам удалось создать такой классификатор.

1. Сработает ли идея?

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

Оказалось, что такой алгоритм работает неплохо и почти все запросы удаётся предзагрузить, однако соответственно возрастает нагрузка на поисковые бекенды и соответственно же возрастает пользовательский трафик. Самой простой идеей оказалась следующая: будем загружать выдачу по первой подсказке из поискового саджеста; когда подсказка меняется, мы выкидываем предыдущую загрузку и начинаем скачивать уже нового кандидата. Ясно, что такое решение внедрить не получится.

Самым простым решением будет классификатор, работающий прямо в рантайме по тем данным, которые и так есть у саджеста. Следующая идея тоже была достаточно простой: необходимо загружать вероятные поисковые подсказки не во всех случаях, а только тогда, когда мы в достаточной степени уверены, что они и правда нужны.

Эти факторы зависели от распределения вероятностей по множеству подсказок (идея: чем больше «вес» первой подсказки, тем более вероятно, что именно она и будет введена) и длины ввода (идея: чем меньше букв осталось ввести пользователю, тем безопасней предзагружать выдачу). Первый классификатор был построен с использованием всего десяти факторов. Нужные факторы для кандидата можно собрать, сделав один http-запрос в саджестовый демон, а таргеты строятся по простейшим логам: кандидат считается «хорошим», если итоговый запрос пользователя полностью с ним совпадает. Прелесть этого классификатора была ещё и в том, что для его построения не нужно было ничего релизить. Собрать такой пул, обучить несколько логистических регрессий и построить диаграмму рассеяния оказалось возможным буквально за несколько часов.

Важны всего два параметра, но это не точность и не полнота. Метрики для пререндера устроены не совсем так, как в обычной бинарной классификации.

таких, которые в итоге совпали с пользовательским вводом. Пусть $r$ — общее количество запросов, $p$ — общее количество всех пререндеров, $ep$ — общее количество удачных пререндеров, т.е. Тогда две интересные характеристики вычисляются следующим образом:

$overhead = \frac{r} - 1$

$efficiency = \frac{ep}{r}$

При этом для тех запросов, в которых пререндер сработал успешно, дополнительный трафик не был создан; для тех запросов, в которых пререндер сработал неуспешно, пришлось задать один дополнительный запрос; так что общее количество запросов в полтора раза больше исходного, «лишних» запросов 50% от исходного количества, поэтому $overhead = 0. Скажем, если совершается ровно один пререндер на один запрос, а успешными оказывается половина пререндеров, то эффективность пререндера составит 50%, и это означает, что удалось ускорить загрузку половины запросов. 5$.

Он выглядел вот так: В этих координатах я и нарисовал первый scatter plot.

Эти значения содержали изрядное количество допущений, но по крайней мере было уже понятно, что, скорее всего, хороший классификатор получится: ускорять загрузку для нескольких десятков процентов запросов, увеличивая нагрузку на несколько десятков процентов — интересный размен.

Действительно, оказалось, что очень сильным фактором является длина запроса: если пользователь уже почти ввёл первую подсказку, и она при этом достаточно вероятна, можно осуществить префетч. Интересно было наблюдать за тем, как срабатывает классификатор. Так что предсказание классификатора резко возрастает к концу запроса.

margin prefix candidate -180.424 м майл
-96.096 мо мос ру
-67.425 мос мос ру
-198.641 моск московское время
-138.851 моско московское время
-123.803 москов московское время
-109.841 московс московское время
-96.805 московск московское время
-146.568 московска московская олимпиада школьников
-135.725 московская московская олимпиада школьников
-125.448 московская московская олимпиада школьников
-58.615 московская о московская олимпиада школьников
31.414 московская об московская область
-66.754 московская область московская область карта
1.716 московская область з московская область запись к врачу

Дело в том, что пользователи всё-таки тратят некоторое время на то, чтобы нажать на кнопку «Найти» после ввода запроса. Пререндер будет полезен, даже если он произошёл в момент ввода самой последней буквы запроса. Это время тоже можно сэкономить.

2. Первое внедрение

Тот присылал, среди прочего, информацию о том, нужно ли предзагружать первую подсказку. Через некоторое время удалось собрать полностью работающую конструкцию: приложение ходило за поисковыми подсказками в демон саджеста. Приложение, получив соответствующий флаг, скачивало выдачу и, если пользовательский ввод в итоге совпадал с кандидатом, осуществляло рендеринг выдачи.

Изначально мы выкатили достаточно консервативные пороги для классификатора, однако даже они позволили мгновенно загружать почти 10% поисковых выдач. Классификатор к этому моменту обзавёлся новыми факторами, а моделью была уже не логистическая регрессия, а вполне себе CatBoost. нам удалось значительно сместить младшие квантили скорости загрузки выдачи, а пользователи заметили это и начали статистически значимо возвращаться в поиск: существенное ускорение работы поиска сказалось на том, как часто пользователи совершают поисковые сессии! Это был очень удачный релиз, т.к.

3. Дальнейшие улучшения

Внимательное изучение логов срабатываний показало, что есть несколько проблем. Хотя внедрение и оказалось удачным, решение было всё ещё крайне несовершенным.

  1. Например, может так оказаться, что по префиксу «янд» он предсказывает запрос «яндекс», по префиксу «янде» он не предсказывает ничего, а по префиксу «янде» он снова предсказывает запрос «яндекс». Классификатор нестабилен. Тогда наша первая прямолинейная реализация делает два запроса, хотя вполне могла обойтись и одним.

  2. Клик по пословной подсказке приводит к появлению в запросе дополнительного пробела. Пререндер не умею обрабатывать пословные подсказки. Это приведёт к плачевным последствиям: уже загруженный запрос «яндекс» будет выкинут, вместо него загрузится запрос «яндекс карты». Например, если пользователь ввёл «яндекс», его первой подсказкой будет запрос «яндекс»; но если пользователь воспользовался пословной подсказкой, вводом будет уже строка «яндекс », а первой подсказкой — «яндекс карты». После этого пользователь нажмёт на кнопку «Найти» и… будет дожидаться полной загрузки выдачи по запросу «яндекс».

  3. В саджесте работает поиск по неточному совпадению, так что кандидат может, например, содержать только одно слово из введённых пользователем; либо пользователь может совершить опечатку, и тогда первая подсказка никогда не совпадёт в точности с его вводом. В некоторых случаях у кандидатов нет никаких шансов стать успешными.

Особенно мне было обидно за проблему с пословными подсказками. Конечно, оставлять пререндер с такими несовершенствами было обидно, пусть даже он и полезен. Позор, не иначе. Я считаю внедрение пословных подсказок в мобильном поиске Яндекса одним из лучших своих внедрений за всё время работы в компании, а тут пререндер не умеет с ними работать!

Решение выбрали крайне простое: даже если классификатор вернул негативное предсказание, мы не прекращаем загрузку предыдущего кандидата. В первую очередь мы исправили проблему нестабильности классификатора. В то же время, это позволяет загружать выдачи быстрее, так как кандидат скачивается в тот момент, когда классификатор впервые сработал для него. Это помогает экономить дополнительные запросы, поскольку, когда этот же кандидат вернётся в следующий раз, не нужно будет качать соответствующую выдачу заново.

Саджестовый сервер является stateless-демоном, так что в нём тяжело реализовать логику, связанную с обработкой предыдущего кандидата для того же пользователя. Затем настал черед пословных подсказок. В итоге мы сделали так: клиент передаёт специальным параметром текст кандидата, который загружается прямо сейчас; если этот кандидат с точностью до пробелов похож на пользовательский ввод, мы отдаём его, даже если кандидат для текущего ввода поменялся. Осуществлять поиск подсказок одновременно для запроса пользователя и для запроса пользователя без концевого пробела означает фактически удвоить RPS на саджестовый демон, так что это тоже не было хорошим вариантом.

Довольно забавно, что до этого релиза префетчем пользовались только те пользователи, что заканчивали ввод своего запроса при помощи клавиатуры, без саджеста. После этого релиза наконец-то стало можно вводить запросы при помощи пословных подсказок и наслаждаться префетчем!

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

4. Что в итоге

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

Так что нам ещё предстоит работать над тем, чтобы лучше конвертировать мгновенные загрузки данных в мгновенные отрисовки поисковых выдач. К сожалению, мгновенно загруженные выдачи — это ещё не полный успех; загруженную выдачу нужно ещё отрендерить, что происходит не мгновенно.

Отсюда ещё один полезный урок: значительные улучшения в скорости работы сервиса могут статистически значимо влиять на его retention. К счастью, сделанные внедрения уже позволяют говорить о пререндере как о достаточно стабильно работающей фиче; мы дополнительно проверили внедрения, описанные в пункте 2: они все вместе тоже приводят к тому, что пользователи сами по себе начинают чаще совершать поисковые сессии.

На видео ниже можно посмотреть, как сейчас работает пререндер на моём телефоне.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть