17.09.2020 12:00
miwgan 0 836 Источник


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

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

Один из центральных элементов на первом экране (тот, который видит пользователь после авторизации) — это поисковые подсказки. В команде гео-поиска мы называем их «саджестами» (от англ. suggestion). Они предлагают пользователю конечные адреса маршрута (точки «Б») из его истории поездок в зависимости от текущего местонахождения пина (т.е. точки подачи) и времени дня без ввода поискового запроса. С помощью саджестов мы стараемся помочь пользователю сформировать заказ «в один клик». В актуальной версии клиентского iOS-приложения саджесты выглядят так:



Гео-поиск за счет алгоритмов формирования поисковой выдачи может влиять на одни из важнейших продуктовых метрик для клиентского приложения таких как время, потраченное на заказ такси (Time to order, или T2O), а также количество действий, которые потребовались клиенту, чтобы сформировать заказ (Actions to order, или A2O). Поэтому мы решили разработать алгоритм, который будет предсказывать наиболее вероятные конечные точки маршрута (точки «Б») при заданном местоположении и времени суток.

Эвристика


Один из backend-разработчиков команды гео-поиска (vasilesk, привет!) придумал достаточно простую эвристику для формирования саджестов, которая работала как для начальной точки «А», так и для конечной точки «Б». Сразу стоит оговориться, что эвристика работала не на истории поездок пользователя, а на истории нажатий на объекты поисковой выдачи, что повлекло за собой некоторые проблемы. Эти объекты мы называем «пиками» (от англ. pick). Эвристика выглядела следующим образом:

  1. Для текущего пользователя берем все его исторические пики.
  2. Фильтруем их, оставляя те, которые были с тем же таргетом (откуда/куда).
  3. Фильтруем пики, оставляя те, которые были в радиусе 300 метров от парной локации (то есть для таргета «куда» — 300 метров от «откуда», для таргета «откуда» — 300 метров от «куда»). Если нет парных координат, то считаем расстояние от GPS-координат пользователя.
  4. Фильтруем пики, оставляя те, которые были сделаны в будние дни, если сейчас будний день, или в выходные, если сейчас выходной.
  5. Фильтруем пики, оставляя те, которые были сделаны между 3:00 и 14:00, если сейчас этот временной промежуток, и аналогично для обратной ситуации.
  6. Вытаскиваем из пиков гео-респонсы (метаинформацию), склеиваем дубликаты, упорядочиваем по количеству пиков с таким гео-респонсом и времени пика по убыванию.
  7. Показываем первые три позиции пользователю.

Этот алгоритм работал некоторое время, и в целом был хорош для MVP (о метриках поговорим чуть позже), но обладал рядом недостатков. Помимо достаточно примитивной логики работы, он базировался не на поездках, а на пиках пользователя. Из-за этого порой у пользователей появлялась неочевидная выдача в поиске. А также ввиду «специфичного» способа хранения истории пиков было довольно сложно проводить быструю аналитику. Исходя из этого мы решили попробовать применить машинное обучение. Дальше мы рассмотрим формулировки задач ранжирования и сведем нашу задачу к бинарной классификации.

Постановка задачи ранжирования


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

$X$ — множество объектов.

$X^l = \{x_1, \dots, x_l \} $ — обучающая выборка. 

$i \prec j $ — правильный порядок на парах $(i, j)$

Задача: построить ранжирующую функцию $ a: X \rightarrow ? $, при которой 

$i \prec j ?  a(x_i) < a(x_j)$



Теперь сформулируем задачу ранжирования поисковой выдачи по запросу. От общей задачи ранжирования она отличается тем, что вместо общего множества объектов, которое нам нужно отсортировать, появляется два множества $D$ и $Q$ — множества документов и запросов.

$D$ — коллекция документов (ответов).

$Q$ — множество запросов.

$D_q \subseteq D$ — множество документов, найденных по запросу q.

$X = Q \times D$ — объектами являются пары «запрос, документ»: $x \equiv (q, d), q \in Q, d \in D_q$

$Y$ — упорядоченное множество рейтингов (оценок).

$y(q, d): X \rightarrow Y $ — оценки релевантности.

Чем выше оценка $y(q, d)$, тем релевантнее документ $d$ запросу $q$.

Правильный порядок определен только между теми документами, которые были найдены по одному и тому же запросу $q$: 

$(q, d) \prec (q, d') \Leftrightarrow y(q, d) < y(q, d')$


В нашей задаче рекомендаций конечных точек маршрута множество рейтингов бинарно. Для пользователя предложенный адрес может быть или релевантным, или нерелевантным (не берем в расчет случаи со сложным маршрутом с несколькими конечными точками). Если рассматривать задачу в контексте пользователя, то $q$ — запрос к сервису, который содержит в себе id клиента, гео-позицию, дату и время; $D_q$ — множество исторических конечных точек «Б» по поездкам пользователя (мы делаем предложения только на основании адресов прошлых поездок). И каждый допустимый ответ $d \in D_q$ на запрос $q$ может быть или релевантным для пользователя (из текущей точки и в текущее время пользователю нужно уехать именно сюда) или нерелевантным.

Для полноты картины осталось только описать процесс создания выборки пар «запрос-ответ» с таргетом. Рассмотрим для простоты одного клиента, у которого было 5 поездок. Проранжируем эти поездки от самой первой до последней. Для первой поездки мы не знаем ничего о поездках пользователя, поэтому предложить ему саджест с помощью описанного алгоритма машинного обучения мы не можем (тут работает эвристика для новых пользователей). Для второй поездки мы знаем конечный пункт назначения из первой поездки и можем предложить этот адрес пользователю в том случае, если он успешно пройдет процедуру постобработки (находится дальше 1 км от текущего местоположения, в том же регионе, и т.д.). Для третьей поездки у нас уже может быть от одного до двух возможных саджестов, если конечный адрес второй поездки совпал с конечным адресом первой и если конечные адреса были разными соответственно. Если саджест совпал с конечной точкой «Б» (то есть попал в один и тот же гексагон фиксированного размера), то в качестве таргета мы ставим 1, иначе — 0. По этому алгоритму мы формируем всевозможные пары вида «запрос-(возможный) ответ» для каждого клиента.

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

Метрики


В задачах ранжирования метрику, которая показывает долю правильных ответов из документов $D_q$ в топ $n$ списка ранжирования при запросе $q$, называют Precision@n. Нас интересуют Precision@1/2/3, поскольку общая доля кликов (Click Through Rate) на первые три позиции составляет около 95 %. При этом правильный конечный адрес только один (естественно, если пользователь хочет уехать в адрес из своей истории), следовательно, эта метрика как раз будет показывать долю случаев, когда правильная конечная точка «Б» попадает в топ 1/2/3 адресов, которые предложил наш алгоритм.

Напомним, что в нашей задаче $Y = \{0, 1\},\; y(q, d)$ — релевантность, $a(q, d)$ — искомая функция ранжирования. Тогда Precision@n можно записать как:

$P_n(q) = \frac{1}{n}\sum_{i=1}^{n} y(q, d_q^{(i)})$


Признаки и модель



Признаки для модели в нашей задаче можно разделить на несколько блоков:

  • Только для документа $d \in D_q$ (конечный адрес, точка «Б»).
  • Только для запроса $q$ (начальный адрес, точка «А»).
  • Общие для запроса и документа $(q, d)$ (маршрут из «А» в «Б»).
  • Общие для пользователя.

Приведем несколько примеров для каждого из них.

Примеры признаков только для документа (точка «Б»):

  1. Количество поездок в точку «Б» за последние K дней.
  2. Количество поездок в точку «Б» в разрезе дней недели и времени суток.
  3. Когда была совершена предыдущая поездка в точку «Б».
  4. Флаг, что предыдущая поездка была совершена в точку «Б».
  5. Является ли точка «Б» избранным адресом/домом/работой.

Примеры признаков только для запроса $q$ (точка «А» + дата/время):

  1. Флаг, новая ли текущая локация для пользователя.
  2. Когда была совершена предыдущая поездка из точки «А».
  3. Количество поездок из точки «А» за последние K дней.
  4. Количество поездок из точки «А» в разрезе дней недели и времени суток.
  5. Является ли точка «А» избранным адресом/домом/работой.
  6. День недели/время суток для запроса $q$.
  7. Дистанция до точки «Б».

Примеры признаков, общих для запроса и документа $(q, d)$ (маршрут из «А» в “Б”):

  1. Флаг, была ли ранее поездка по маршруту.
  2. Когда была совершена предыдущая поездка по маршруту.
  3. Отношение поездок по маршруту ко всем историческим поездкам.

Примеры признаков для пользователя:

  1. Количество поездок пользователя за последние K дней.
  2. Количество избранных и флаги наличия домашнего адреса и адреса работы.
  3. Статистики по историческим поездкам (среднее, квантили, медиана дистанции поездки, др.).

В итоге мы получили больше 100 признаков, которые описывают пару объектов «запрос-документ». Так как мы хотим максимизировать Precision@1/2/3, то логично, что нужно прогнозировать вероятность поездки пользователя в конкретный конечный пункт и ранжировать возможных кандидатов по полученной вероятности. Мы пробовали разные алгоритмы и разные функции потерь, и остановились на градиентном бустинге на деревьях и logloss’е. Результаты, которые были получены на момент использования эвристики:

Эвристика ML-алгоритм
Precision@1 0,657 0,789
Precision@2 0,719 0,872
Precision@3 0,761 0,923


Production


Естественно, что прежде чем придумывать какие-то сложные алгоритмы, фичи и обучать модели, нужно подумать о том, как это всё будет работать в бою под нагрузкой, при этом не забывая о масштабировании. Собравшись с командой backend-разработки, мы набросали примерную схему того, как должен выглядеть наш сервис. Обученную модель машинного обучения мы решили обернуть в async-await web-фреймворк Sanic, на который будет слать запросы сервис поиска. Помимо вертикального масштабирования мы реализовали возможность деплоя на несколько машин. Запросы к сервису будут отправляться на URL балансировщика нагрузки, и далее будет происходить проксирование на ту или иную машину алгоритмом Round-robin. После реализации первого прототипа сервиса мы поняли, что можем значительно сократить объем запросов в MySQL. Так как любой сдвиг пина с выбором точки подачи — это новый запрос на поиск, а значит и на наш сервис, то мы подумали, что можем хранить кэш с историей поездок пользователя в течение N минут с момента запроса в Redis. Благодаря этому мы сократили нагрузку на базу в три раза. В итоге схему сервиса можно представить так:



Запросы к сервису и его ответы мы храним в ElasticSearch, а метрики, которые отвечают за стабильность работы, мы передаем и мониторим в NewRelic.

Общий рабочий процесс нашего сервиса:

  1. Сервис поиска шлет запрос к сервису поисковых подсказок.
  2. Балансировщик выбирает одну из машин и передает на нее этот запрос.
  3. Внутри машины запрос передается на один из открытых worker’ов или встает в очередь.
  4. Внутри worker’a:
    1. Валидируем входящий запрос.
    2. Делаем запрос в Redis, если истории заказов по пользователю нет, то идем в MySQL и записываем полученные данные в Redis.
    3. Делаем базовую предобработку данных и собираем фичи для модели.
    4. Делаем predict_proba() по всем сформированным саджестам и сортируем их по «вероятности».
    5. Делаем дополнительную постобработку данных и формируем ответ.
    6. Возвращаем ответ в сервис поиска.

Что дальше?


Сейчас мы активно тестируем нашу модель с помощью switchback-тестирования, чтобы впоследствии сделать выводы и реализовать дополнительные надстройки в алгоритме для повышения качества ранжирования. В дальнейшем мы попробуем добавить дополнительные признаки в модель, а также совместно с дизайнерами продукта подготовить новое решение по «отображению» саджестов. Конечно же, было бы здорово, если бы наше приложение само понимало, откуда/когда/куда/на какой машине пользователь хочет уехать. Мы работаем во всех направлениях, чтобы заказ такси действительно совершался в один клик.