[Перевод] Введение в математическую оптимизацию на примере компании Recruit. Часть 3

yqn9coiaodwvlisw2dtrvxw5qng.png


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

❖ авторы Кейта Накамура, Кенго Хамада, Котаро Танахаси

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

Определение целей распространения подарочных сертификатов в Hot Pepper Beauty


Hot Pepper Beauty — это платформа, которая соединяет компании, связанные с красотой, и их клиентов. Она состоит из двух основных разделов: «Волосы», где пользователи могут записаться в салоны красоты и парикмахерские, а также «Релакс и красота», где пользователи могут забронировать места на посещение салонов, предоставляющих маникюрные услуги и наращивание ресниц.

ffwro7nqn5xrxzhx0blzzrkuzb4.png

Список основных услуг, которые можно заказать через Hot Pepper Beauty (Что такое Hot Pepper Beauty? | Цитаты из Hot Pepper Beauty)

Хотя многие клиенты Hot Pepper Beauty имели опыт использования услуг по уходу за волосами, было много пользователей, которые не имели опыта использования других услуг, представленных на платформе. С целью увеличения активности клиентов были разработаны подарочные сертификаты, которые можно использовать в определённых разделах.

hp5yz4exirsvftsgro_ljfwlvs4.png

Изображение подарочного сертификата, который можно использовать при покупке косметологических услуг (взято из «Я хочу знать о подарочных сертификатах»)

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

▍ Бизнес-задача


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

xpnnck2937luewpcfv9z8ufz09i.png


Для решения вышеуказанных вопросов необходима следующая информация:

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


Пример: клиент А.

┣ Количество посещений и потраченная сумма, когда дарится подарочный сертификат на ресницы (паттерн 1).

┣ Количество посещений и потраченная сумма, когда дарится подарочный сертификат на маникюр (паттерн 2).

┗ Количество посещений и сумма потраченных денег при вручении подарочных сертификатов на наращивание ресниц/ногтей (паттерн 3).

Количество бронирований и объём использования и т. д.

  • Бюджетные ограничения для данной кампании (общая сумма, потраченная пользователями, должна вписываться в бюджет кампании).


※Предположим, что каждый пользователь назначен ровно на один паттерн (в данном случае будет 11 паттернов).

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

ut5uohzrgmsbwuugrsaqy59ovw8.png


▍ Подход математической оптимизации


  • Подготовка исходных данных


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

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

  • Алгоритм


Это определение схемы можно рассматривать как проблему распределения — «раскрашивание квадратов» (распределение 0/1). Каждый квадрат связан с ограничивающим бюджетом и количеством бронирований в новом направлении, которое вы хотите максимизировать в этот раз.

Хотя эта разновидность проблемы распределения является NP-трудной, она относится к типу, который легко решается с помощью общего решателя в математической оптимизации. Однако в данном случае задача является очень большой из-за количества целей назначения, превышающего 30 миллионов, и попадает в случай, когда трудно найти решение с помощью решателя общего назначения. В этом случае был разработан специальный алгоритм для получения приближённого решения этой проблемы.

m_4x3ooi-cevmxzrr3qbmwt5lqi.png


▍ Эффекты от внедрения системы


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

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

Определение распределения мест для размещения коммерческих сообщений


Компания Recruit использует телевизионные ролики в качестве одного из своих рекламных носителей. Решение о том, какой коммерческий материал (т. е. тип рекламы) должен быть показан в каждом из ограниченных рекламных слотов, является очень сложным вопросом, оказывающим значительное влияние на эффективность рекламы.

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

vyddutb9npgztj7ilofcejahtnw.png

Зрители слева смотрят только рекламу с одинаковым материалом, а зрители справа — рекламу с разнообразным материалом. Результаты опроса показали, что реклама была более эффективной у зрителей справа

▍ Понимание проблем бизнеса


В этом разделе описывается подробная постановка задачи. После обсуждения того, что вы получите на выходе, объясняются конкретные требования.

В целом, рекламные ролики подаются в следующей последовательности:

  1. Определяется количество рекламных роликов, которые необходимо разместить, и размещается заказ в рекламном агентстве.
  2. Телеканал указывает слот (вещательная станция * время начала вещания), в котором будет транслироваться рекламный ролик.
  3. Принимается решение о том, какой материал рекламного ролика будет транслироваться в данном слоте.


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

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

Кроме того, необходимо соблюдать следующие ограничения:

  • Рекламные ролики могут быть размещены только в тех слотах, которые указаны телеканалом.
  • Гарантирует минимальный общий зрительский рейтинг (GRP) для каждого коммерческого материала.


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

jidvdr00nejodrqp3n4m9zmsx4a.png


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

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

Описанную до сих пор постановку задачи можно обобщить, как показано на схеме ниже.

xcy4_a4cd6pyuenrsaebbi2yyoi.png

▍ Подход математической оптимизации


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

Как следует формулировать проблемы развития, вытекающие из таких типичных проблем?

Одним из ответов на этот вопрос является знание типичных методов составления формул. Например, во вступительной статье профессора Тецуя Фудзие※ представлены различные техники составления формул. Используя типичную проблему в качестве основы, подход к использованию вышеупомянутых методов формулировки и их адаптации к практической проблеме является очень важным в применении.

※Тецуя Фудзие, «Введение в формулировку целочисленного программирования», Исследование операций, 57, 2012, 190 — 197.

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

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

▍ Последствия внедрения


По сравнению с обычным методом определения количества зрителей, распределение после оптимизации значительно улучшило объективную функцию «количество зрителей, просмотревших все рекламные материалы за период рекламной кампании». Кроме того, анкетный опрос, проведённый после кампании, также подтвердил повышение эффективности рекламы. Ожидается, что в будущем этот метод будет применяться к различным коммерческим структурам компании.

Заключение


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

Играй в нашу новую игру прямо в Telegram!

sz7jpfj8i1pa6ocj-eia09dev4q.png

© Habrahabr.ru