Поисковые подсказки (саджест) — это не только пользовательский сервис, но ещё и очень мощная языковая модель, хранящая миллиарды поисковых запросов, поддерживающая нечёткий поиск, персонализацию и многое другое. Мы научились использовать саджест для того, чтобы предугадывать итоговый запрос пользователя и загружать поисковую выдачу до нажатия кнопки «Найти».
Внедрение этой технологии – пререндера – потребовало многих интересных решений в мобильной разработке, разработке поискового рантайма, логов, метрик. И, конечно, нам нужен был крутой классификатор, определяющий, нужно ли загружать поисковый запрос заранее: этот классификатор должен соблюдать баланс между ускорением загрузки, дополнительным трафиком и нагрузкой на Поиск. Сегодня я расскажу о том, как нам удалось создать такой классификатор.
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. Дальнейшие улучшения
Хотя внедрение и оказалось удачным, решение было всё ещё крайне несовершенным. Внимательное изучение логов срабатываний показало, что есть несколько проблем.
-
Классификатор нестабилен. Например, может так оказаться, что по префиксу «янд» он предсказывает запрос «яндекс», по префиксу «янде» он не предсказывает ничего, а по префиксу «янде» он снова предсказывает запрос «яндекс». Тогда наша первая прямолинейная реализация делает два запроса, хотя вполне могла обойтись и одним.
-
Пререндер не умею обрабатывать пословные подсказки. Клик по пословной подсказке приводит к появлению в запросе дополнительного пробела. Например, если пользователь ввёл «яндекс», его первой подсказкой будет запрос «яндекс»; но если пользователь воспользовался пословной подсказкой, вводом будет уже строка «яндекс », а первой подсказкой — «яндекс карты». Это приведёт к плачевным последствиям: уже загруженный запрос «яндекс» будет выкинут, вместо него загрузится запрос «яндекс карты». После этого пользователь нажмёт на кнопку «Найти» и… будет дожидаться полной загрузки выдачи по запросу «яндекс».
-
В некоторых случаях у кандидатов нет никаких шансов стать успешными. В саджесте работает поиск по неточному совпадению, так что кандидат может, например, содержать только одно слово из введённых пользователем; либо пользователь может совершить опечатку, и тогда первая подсказка никогда не совпадёт в точности с его вводом.
Конечно, оставлять пререндер с такими несовершенствами было обидно, пусть даже он и полезен. Особенно мне было обидно за проблему с пословными подсказками. Я считаю внедрение пословных подсказок в мобильном поиске Яндекса одним из лучших своих внедрений за всё время работы в компании, а тут пререндер не умеет с ними работать! Позор, не иначе.
В первую очередь мы исправили проблему нестабильности классификатора. Решение выбрали крайне простое: даже если классификатор вернул негативное предсказание, мы не прекращаем загрузку предыдущего кандидата. Это помогает экономить дополнительные запросы, поскольку, когда этот же кандидат вернётся в следующий раз, не нужно будет качать соответствующую выдачу заново. В то же время, это позволяет загружать выдачи быстрее, так как кандидат скачивается в тот момент, когда классификатор впервые сработал для него.
Затем настал черед пословных подсказок. Саджестовый сервер является stateless-демоном, так что в нём тяжело реализовать логику, связанную с обработкой предыдущего кандидата для того же пользователя. Осуществлять поиск подсказок одновременно для запроса пользователя и для запроса пользователя без концевого пробела означает фактически удвоить RPS на саджестовый демон, так что это тоже не было хорошим вариантом. В итоге мы сделали так: клиент передаёт специальным параметром текст кандидата, который загружается прямо сейчас; если этот кандидат с точностью до пробелов похож на пользовательский ввод, мы отдаём его, даже если кандидат для текущего ввода поменялся.
После этого релиза наконец-то стало можно вводить запросы при помощи пословных подсказок и наслаждаться префетчем! Довольно забавно, что до этого релиза префетчем пользовались только те пользователи, что заканчивали ввод своего запроса при помощи клавиатуры, без саджеста.
Наконец, с третьей проблемой мы разобрались при помощи ML: добавили факторов про источники подсказок, совпадение с пользовательским вводом; кроме того, благодаря первому запуску мы смогли собрать побольше статистики и обучиться по месячным данным.
4. Что в итоге
Каждый из этих релизов давал рост количества мгновенно загружаемых выдач на десятки процентов. Самое приятное в том, что нам удалось улучшить показатели пререндера более чем в два раза, практически не трогая часть про machine learning, а лишь улучшая физику процесса. Это важный урок: зачастую качество классификатора не является самым узким местом в продукте, зато его улучшение является самой интересной задачей и поэтому разработка отвлекается именно на него.
К сожалению, мгновенно загруженные выдачи — это ещё не полный успех; загруженную выдачу нужно ещё отрендерить, что происходит не мгновенно. Так что нам ещё предстоит работать над тем, чтобы лучше конвертировать мгновенные загрузки данных в мгновенные отрисовки поисковых выдач.
К счастью, сделанные внедрения уже позволяют говорить о пререндере как о достаточно стабильно работающей фиче; мы дополнительно проверили внедрения, описанные в пункте 2: они все вместе тоже приводят к тому, что пользователи сами по себе начинают чаще совершать поисковые сессии. Отсюда ещё один полезный урок: значительные улучшения в скорости работы сервиса могут статистически значимо влиять на его retention.
На видео ниже можно посмотреть, как сейчас работает пререндер на моём телефоне.
Автор: Алексей Шаграев
