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

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

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

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

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

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

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

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

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

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

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

В этих координатах я и нарисовал первый 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. Первое внедрение

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

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

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

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

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

   
   

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

   
   

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

   
   

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

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

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

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

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

4. Что в итоге

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

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

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

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