Как с помощью A-B-платформы найти лучшее решение, если вариантов слишком много, чтобы тестировать все?. bayesian optimization.. bayesian optimization. recsys.. bayesian optimization. recsys. анализ больших данных.. bayesian optimization. recsys. анализ больших данных. Машинное обучение.. bayesian optimization. recsys. анализ больших данных. Машинное обучение. оптимизация.. bayesian optimization. recsys. анализ больших данных. Машинное обучение. оптимизация. Статистика в IT.. bayesian optimization. recsys. анализ больших данных. Машинное обучение. оптимизация. Статистика в IT. эксперименты.

Как найти сокровище, если вариантов, где оно может быть, очень много?

Привет, Habr! Меня зовут Костя Козлов, я работаю в команде анализа и валидации экспериментов A/B-платформы Ozon. В предыдущей статье коллеги рассказали, как создать высокопроизводительную платформу сплитования пользователей на группы и стенд метрик. В этой статье расскажу, как построить поверх этого инструмент, который автоматически оптимизирует бизнес-метрики продукта на основе «умного» перебора возможных вариантов его параметров.

Статья будет касаться всех кейсов, где необходимо найти оптимальные по бизнес-метрикам непрерывные параметры системы на данных из онлайн-экспериментов. Например, у вас есть алгоритм рекомендаций товаров, и вы хотите на основе настройки его параметров вырастить число заказов, не уронив при этом рекламную выручку.

Разберём всё в двух частях:

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

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

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

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

В простейшем случае оптимизации одной метрики у нас есть зависимость её математического ожидания от набора параметров алгоритма с каким-то шумом (Формула 1). Также матожидание метрики будет зависеть от дня недели (например, средняя выручка на пользователя в субботу может быть больше средней выручки на пользователя в понедельник). Для того чтобы устранить влияние времени, часть пользовательского трафика нужно направлять в контрольную группу с каким-то исходным рекомендательным алгоритмом и оптимизировать прирост метрики относительно её значения в контрольной группе. Также важно оценивать дисперсию нашей метрики, чтобы учитывать её в оптимизационном алгоритме (Формула 2).

Формула 1. Матожидание метрики. Его распределение зависит как непрерывная функция от набора параметров размерности и времени со случайным шумом .

$begin{array}{rcl}m=f(x; t) + mathcal{N} (0, sigma^{2}), x=(x_{1}, ... x_{n})\end{array}$

Формула 2. Аплифт метрики. В нашей постановке он не зависит от времени. $m_{i}^{t}$ – значение метрики в тестовой группе; $m_{i}^{с}$ – значение метрики в контрольной группе; $sigma_{i}^{с}$ – значение стандартного отклонения метрики в контрольной группе.

$frac{m_{i}^{t} - m_{i}^{c}}{sigma_{i}^{c}}$

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

Рисунок 1. Постановка задачи. Необходимо исследовать новые наборы параметров системы таким образом, чтобы улучшать некоторые метрики, не ухудшая другие.

Например, мы хотим подобрать новые параметры рекомендательного алгоритма с помощью оптимизации аплифтов бизнес-метрик таким образом, чтобы:

Вырастить среднее число кликов на товары.
Не уронить среднюю выручку.
Не уронить среднюю рекламную выручку.

Оптимизация

Общий подход

Оптимизационную процедуру можно разбить на следующие шаги:

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

Таким образом, с течением времени, алгоритм будет выбирать всё более и более оптимальные с точки зрения бизнес-метрик параметры рекомендательного алгоритма.

Оценка дисперсии в метриках

В оптимизации важно учитывать не только прирост метрики относительно контрольного варианта, но и то, насколько измеряемая метрика шумная, то есть насколько широкое у неё распределение среднего. За счёт деления приростов метрик на стандартное отклонение удаётся привести все метрики, участвующие в оптимизации, в единую шкалу, независимую от «шума» (Формула 2). Одним из самых популярных методов оценки дисперсии (или стандартного отклонения) в метриках является пуассонсовский бутстрап. Его схема подробно описана в статье. Суть его такова:

У нас есть набор с пользовательскими агрегатами в контрольной группе (например, статистика по GMV за день для каждого пользователя).
Для каждого пользователя генерируется случайное число из распределения Пуассона с параметром . Это число соответствует тому, сколько раз пользователь будет учитываться в бутстрапной выборке.
Процесс повторяется много раз, чтобы получить много бутстрапных выборок.
Для каждой бутстрапной выборки считается значение метрики из пользовательских агрегатов.
Далее мы считаем стандартное отклонение на выборке из средних бутстрапных выборок. Эта статистика показывает, насколько метрика волатильная.

Составляющие оптимизатора: модель-оценщик и стратегия выбора параметров

Оптимизационный алгоритм можно разделить на две главные его составляющие:

Модель-оценщик. Это может быть любой алгоритм машинного обучения (МО) или статистическая модель, но часто используют регрессию гауссовского процесса (ГП). Почему часто выбирают ГП: 1) модель не накладывает ограничение на вид функции зависимости таргета от входных данных, позволяет аппроксимировать любую непрерывную функцию; 2) модель возвращает стандартное отклонение прогноза. Подробнее о регрессии гауссовского процесса можно почитать в разделе Регрессия гауссовского процесса. Это даёт больше гибкости, поскольку мы можем учитывать в выборе параметров «уверенность» модели-оценщика. Модель-оценщик может оценивать как один таргет, так и несколько. Подробнее с разновидностями оценщиков можно ознакомиться в Таблице 1.
Стратегия выбора параметров на основе предсказаний модели-оценщика. Помимо предсказаний прироста метрик относительно контрольной группы, она может учитывать, например, прогноз доверительного интервала предсказания. С примерами стратегий можно ознакомиться в Таблице 2. Перед применением стратегии можно заранее фильтровать варианты (например, убирать из пула варианты, где хотя бы один из аплифтов в метриках отрицательный). Учёт стандартных отклонений прогнозов в стратегиях позволяет одновременно выбирать оптимальные варианты (эксплуатировать) и выделять часть пользовательского трафика на потенциально эффективные наборы параметров (исследовать).

Таблица 1. Описание моделей-оценщиков.

Модель/Система моделей	Таргет (Что прогнозирует оценщик) и его описание
Модель ГП с одним выходом	$begin{array}{rcl}y=sum_{i=1}^{G} w_{i}frac{m_{i}^{t} - m_{i}^{c}}{sigma_{i}^{c}} + sum_{j=1}^{P} w_{j}mathbf{1}[ frac{m_{j}^{t} - m_{j}^{c}}{sigma_{j}^{c}} leq 0] frac{m_{j}^{t} - m_{j}^{c}}{sigma_{j}^{c}}\end{array}$ В этом случае таргет модели ГП — производная величина, получающаяся линейной комбинацией аплифтов отдельных метрик с весами. При этом в зависимости от типа метрики (на рост или защитная ), её вклад по-разному учитывается в таргете. Если метрика на рост , то она будет учитываться с каким-то весом независимо от значения аплифта. Если метрика защитная, то она будет учитываться в таргете, только если значение аплифта — отрицательное. Если значение аплифта — положительное, то вклад защитной метрики будет равен нулю. В итоге оптимизация такого таргета, будет сонаправлена оптимизации метрик на рост. При этом благодаря «штрафу» в защитных метриках, оптимизатор не должен показывать параметры, которые заведомо их ухудшают.
Несколько независимых моделей ГП с одним выходом	$begin{array}{rcl}&{y_{i}=frac{m_{i}^{t} - m_{i}^{c}}{sigma_{i}^{c}}}_{i=1}^{N}\end{array}$ В этом случае таргет одной модели ГП — аплифт одной метрики. Таким образом, мы обучаем столько моделей ГП, сколько метрик мы учитываем в оптимизации (). Получая для каждого потенциального набора параметров оценки аплифтов отдельных метрик и их доверительные интервалы, мы можем более гибко выбирать варианты, в отличие от метода с одной моделью ГП.
Одна модель ГП с несколькими выходами	$begin{array}{rcl}&{y_{i}=frac{m_{i}^{t} - m_{i}^{c}}{sigma_{i}^{c}}}_{i=1}^{N}\end{array}$ В этом случае используется multi-output модель ГП (с несколькими выходами). Она одна прогнозирует аплифты и их стандартные отклонения для каждой метрики, участвующей в оптимизации. В отличие от системы независимых моделей, единая модель позволяет учитывать в прогнозе корреляции между метриками.

Модель/Система моделей

Таргет (Что прогнозирует оценщик) и его описание

Модель ГП с одним выходом

$begin{array}{rcl}y=sum_{i=1}^{G} w_{i}frac{m_{i}^{t} - m_{i}^{c}}{sigma_{i}^{c}} + sum_{j=1}^{P} w_{j}mathbf{1}[ frac{m_{j}^{t} - m_{j}^{c}}{sigma_{j}^{c}} leq 0] frac{m_{j}^{t} - m_{j}^{c}}{sigma_{j}^{c}}\end{array}$

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

Несколько независимых моделей ГП с одним выходом

$begin{array}{rcl}&{y_{i}=frac{m_{i}^{t} - m_{i}^{c}}{sigma_{i}^{c}}}_{i=1}^{N}\end{array}$

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

Одна модель ГП с несколькими выходами

$begin{array}{rcl}&{y_{i}=frac{m_{i}^{t} - m_{i}^{c}}{sigma_{i}^{c}}}_{i=1}^{N}\end{array}$

В этом случае используется multi-output модель ГП (с несколькими выходами). Она одна прогнозирует аплифты и их стандартные отклонения для каждой метрики, участвующей в оптимизации. В отличие от системы независимых моделей, единая модель позволяет учитывать в прогнозе корреляции между метриками.

Таблица 2. Описание стратегий выбора параметров на основе предсказаний моделей-оценщиков.

Стратегия	Формула и пояснение
Upper Confidence Bound (UCB)	$sum_{i=0}^{N} w_{i}UCB_{i}(x)=sum_{i=0}^{N} w_{i}(mu_{i}(x) + alpha sigma_{i}(x)) rightarrow max$ Стратегия выбирает набор параметров с высоким прогнозом аплифта (). При этом среди одинаковых по прогнозу аплифта наборов параметров, стратегия будет выбирать тот, который имеет большее стандартное отклонение прогноза (). Политика может масштабироваться на несколько метрик () благодаря их линейному суммированию с весами .
Thompson Sampling (TS) из нормального распределения	$sum_{i=0}^{N} w_{i}TS_{i}(x) rightarrow max$ $TS_{i} (x) sim mathcal{N} (mu_{i}(x), sigma_{i}^{2}(x))$ Стратегия семплирует для каждого возможного набора параметров аплифт метрик () из оценок матожидания и стандартного отклонения. После этого выбираются наборы параметров с максимальным семплированным значением. Стратегия также может масштабироваться на несколько метрик за счёт их линейной комбинации с весами. Семплировать возможно не только из нормальных распределений (например, как в статье коллег из Оzon Банка), однако в нашей постановке средние значения метрик распределены нормально вследствие Центральной предельной теоремы (ЦПТ).

Стратегия

Формула и пояснение

Upper Confidence Bound (UCB)

$sum_{i=0}^{N} w_{i}UCB_{i}(x)=sum_{i=0}^{N} w_{i}(mu_{i}(x) + alpha sigma_{i}(x)) rightarrow max$

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

Thompson Sampling (TS) из нормального распределения

$sum_{i=0}^{N} w_{i}TS_{i}(x) rightarrow max$

$TS_{i} (x) sim mathcal{N} (mu_{i}(x), sigma_{i}^{2}(x))$

Стратегия семплирует для каждого возможного набора параметров аплифт метрик () из оценок матожидания и стандартного отклонения. После этого выбираются наборы параметров с максимальным семплированным значением. Стратегия также может масштабироваться на несколько метрик за счёт их линейной комбинации с весами. Семплировать возможно не только из нормальных распределений (например, как в статье коллег из Оzon Банка), однако в нашей постановке средние значения метрик распределены нормально вследствие Центральной предельной теоремы (ЦПТ).

Регрессия гауссовского процесса

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

Рисунок 2. Влияние входной дисперсии измерения функции на аппроксимацию с использованием регрессии гауссовского процесса (ГП).

Системный дизайн оптимизатора

Использование функционала платформы экспериментов для разделения трафика по вариантам параметров

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

Платформа сплитования пользователей, упрощённо говоря, делит пользователей на группы (варианты) по следующей формуле:

$begin{array}{rcl}Group=hash(UserID + salt) % 100 \end{array}$

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

Вариант №1 (50% аудитории)

Вариант №2 (50% аудитории)

{

"coefficient_1": 1,

"coefficient_2": 2

}

{

"coefficient_1": 3,

"coefficient_2": 4

}

Таким образом, половина пользователей попадёт в Вариант №1 и для них применится алгоритм с набором параметров (1, 2), а оставшаяся половина пользователей будет видеть рекомендации на основе алгоритма с параметрами (3, 4). Если во время эксперимента поменять значения параметров в его варианте, то пользователи сразу начнут видеть обновлённые рекомендации.

Кажется, что можно создать один эксперимент с различными вариантами (наборами параметров) и каждый день обновлять значения параметров в них в соответствии с тем, как говорит нам оптимизатор. Однако из-за того, что группа получается из деления хеша на 100, такой способ не позволяет полноценно исследовать пространство поиска из-за ограничения на число вариантов в одном эксперименте (не больше 100 вариантов).

Но что делать, если мы хотим за один день раздать пользователям больше 100 уникальных вариантов? Можно создавать параллельные эксперименты (один эксперимент — один параметр). Тогда в одном эксперименте пользователю присвоят значение одного параметра, в другом эксперименте значение другого и т. д. В итоге пользователи будут делиться на бакеты (каждому бакету соответствует свой набор параметров).

Эксперимент №1 (Вариант №2)	Эксперимент №2 (Вариант №1)	Итоговые настройки алгоритма рекомендаций для пользователя, который попал в Вариант №2 Эксперимента №1 и в Вариант №1 Эксперимента №2
`{` `"coefficient_1": 3` `}`	`{` `"coefficient_2": 2` `}`	`{` `"coefficient_1": 3,` `"coefficient_2": 2` `}`

Эксперимент №1 (Вариант №2)

Эксперимент №2 (Вариант №1)

Итоговые настройки алгоритма рекомендаций для пользователя, который попал в Вариант №2 Эксперимента №1 и в Вариант №1 Эксперимента №2

{

"coefficient_1": 3

}

{

"coefficient_2": 2

}

{

"coefficient_1": 3,

"coefficient_2": 2

}

В такой схеме теоретическое максимальное число происследованных наборов параметров за один день будет равно:

$begin{array}{rcl}100^{N} \end{array}$

где — число параметров в оптимизации.

Таким образом, возможно создать параллельно экспериментов с разной (солью), где — число подбираемых параметров (на Рисунке 3 = 2). Тогда каждый пользователь попадёт в свой бакет, соотвествующий определённому набору параметров. Запустим эти эксперименты на два дня, — за это время будут исследованы все наборы параметров. Дополнительно создадим ещё один эксперимент с вариантами, — его мы будем использовать в последующие дни оптимизационного запуска, показывая каждый день вариантов, которые оптимизатор посчитал «хорошими». Поверх описанных выше экспериментов необходимо создать ещё один A/B-тест, который позволит разделить всех пользователей эксперимента на контрольный (где будет применяться логика, относительно которой будут считать аплифты), тестовый (где применяется оптимизатор) и индифферентный трафик (не участвующие в тесте пользователи). Схематично разделение трафика изображено на Рисунке 3. Каждый уникальный цвет на диаграмме характеризует отдельный эксперимент (сплитование трафика). В первые два дня создаются два перекрывающихся эксперимента с тремя вариантами в каждом (выделены зелёным и жёлтым цветом). Каждый эксперимент соответствует одному параметру. Перекрытие вариантов в экспериментах приводит к формированию 9 бакетов с различными наборами параметров. Далее метрики, собранные в отдельных бакетах, используются для обучения модели-оценщика. По истечении двух дней со старта оптимизации алгоритм выбирает топ-3 наборов параметров, которые вставляются в конфигурацию нового эксперимента. Далее процедура обновления «лучших» наборов в нём происходит с периодичностью в один день. Контрольная группа необходима для расчёта аплифта и устранения временной компоненты в оптимизационной задаче. Схема оптимизации подробно расписана на Рисунке 4.

Рисунок 3. Схема разделения трафика в экспериментах на примере проведения двумерной оптимизации.

Такая архитектура даёт несколько преимуществ:

Масштабируемость в расчётах метрик. Поскольку оптимизатор «завязан» на инфраструктуре стенда метрик, то в оптимизации можно использовать любые метрики, подневные агрегаты которых уже рассчитываются в нём (более 1000 уникальных метрик).
Уверенность в корректном сплитовании трафика. Поскольку сплит-сервис, лежащий в основе A/B-платформы, постоянно валидируется на предмет потенциальной некорректной работы, его использование обеспечивает надёжный контроль над сплитованием трафика.
Удобное заведение пайплайна оптимизации. Для запуска требуется лишь создать эксперименты через UI платформы A/B-тестов и прокинуть конфигурацию с настройками оптимизационного алгоритма (например, стратегию выбора параметров на основе предсказаний модели-оценщика или метрики, участвующие в оптимизации).

Компоненты системы

Оптимизатор состоит из следующих частей:

Пакет сервиса на Python. В нём реализована вся логика — от сбора метрик по бакетам из стенда и проведения бутстрапа и заканчивая обучением и инференсом моделей ГП, а также общением по API с A/B-платформой.
База данных (БД) сервиса на HDFS. В ней хранится статистика о запусках, метриках в бакетах, значениях исследуемых параметров и оценок моделей.
База данных в Clickhouse. Дубликат БД сервиса на HDFS, позволяющий интегрироваться с Grafana для мониторинга оптимизационных запусков.
Airflow DAG. Планировщик джоб для ETL-процессов, получения оценок и выбора вариантов.

Рисунок 4. Оптимизационный пайплайн. Раз в день Airflow DAG собирает метрики за прошедший день, производит их бутстрапирование, переобучает модели ГП и выбирает параметры на следующий день.

Вывод

Иногда нужно подобрать параметры системы так, чтобы улучшить бизнес-метрики, но равномерное сплит-тестирование пользователей по вариантам (наборам параметров) может быть невозможно в силу экономических причин (необходимо заранее отключать невыгодные варианты). Число потенциальных вариантов также теоретически бесконечно в силу вещественности отдельных параметров в них. Существуют методы на основе моделей-оценщиков, позволяющие на основе анализа данных метрик прогнозировать их прирост относительно контрольного варианта в зависимости от параметров и выбирать оптимальные решения. Эти методы можно масштабировать на все сервисы, которые используют платформу А/B-тестирования.

Литература

Здесь представлена литература, которая может быть полезна тем, кто интересуется онлайн-экспериментами и оптимизацией.

Тюнинг систем: экспериментирование для инженеров от A/B-тестирования до байесовской оптимизации. Свит Дэвид.
Учебник по машинному обучению. Глава 3.3. Подбор гиперпараметров. Федотов Станислав, Синицин Филипп.
Using Bayesian optimization for balancing metrics in recommendation systems. Yunbo Ouyang, Viral Gupta, Kinjal Basu, Cyrus Diciccio, Brendan Gavin, and Lin Guo.
Байесовская оптимизация с примерами из библиотек Python. Куан Нгуен.

Автор: konstkozlov

Источник

Запись добавлена: 23.03.2026 в 15:22
Оставлено в

Как с помощью A-B-платформы найти лучшее решение, если вариантов слишком много, чтобы тестировать все?

Меню навигации

На главную

Главное

Рубрики

Методики

Информация