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

Полный текст

Введение В современных информационных системах все чаще возникает задача построения систем выбора персонализированных предложений. Это во многом связано с реализацией через интернет ряда товаров и услуг, откуда вытекает применение персонализации предложений для каждого пользователя в таргетированной рекламе и рекомендательных системах. Для решения подобных задач потенциально может быть применен целый спектр методов машинного обучения, таких как деревья решений, глубокие нейросети, метод опорных векторов, а также более специфичные подходы, такие как логистическая регрессия с вручную конструируемыми признаками или специализированными модификациями нейросетей [1]. Однако далеко не все вышеперечисленные методы могут быть применены в конкретных системах с учетом их специфики. Одна из существенных проблем - это ограничение на время ответа системы, которое напрямую зависит от времени получения прогноза. В качестве примера рассмотрим системы таргетированного показа рекламы. Среднее время ответа сервера по данным сервиса измерения скорости загрузки сайтов https://webo.in/ составляет 0,1 с у mail. ru и 0,15 с у yandex.ru. За ещё меньшее время должен быть обработан запрос на подбор рекламы, но будем считать, что это тоже 0,1 с. Предположим, на разные этапы обработки запроса (за исключением получения прогноза) уходит около 0,01 с. Остальное может быть расходовано на получение прогноза частоты кликов (будем считать, что это 0,1 - 0,01 = 0,09 с). Допустим, что в среднем приходится осуществить выбор из 50 баннеров (т. е. получить 50 оценок). Тогда время прогнозирования частоты кликов для каждой пары пользователь-баннер должно составлять не более 0,09/50 = 1,8 · 10-3 с (параллельно рассчитывать оценки для каждой пары пользователь-баннер нецелесообразно, поскольку потоки сервера обычно заняты обработкой других запросов). Это накладывает ограничения на используемые методы прогнозирования. В данной работе предложено моделировать систему выбора персонализированных предложений как систему массового обслуживания (СМО) для оценки применимости различных методов машинного обучения с точки зрения временных требований к системе. 1. Постановка задачи Будем считать, что запросы на показ рекламы (заявки) поступают с одинаковой интенсивностью λ. В таком случае поток заявок можно считать стационарным (вероятность появления определенного числа заявок на заданном интервале зависит только от продолжительности данного интервала), а сами заявки независимыми друг от друга (пользователи открывают страницы в интернете независимо друг от друга). Также будем предполагать, что на временном интервале достаточно малой длительности δt приходит только 1 заявка. Следовательно, в рассматриваемой системе поток заявок является простейшим, а промежуток времени между двумя заявками имеет экспоненциальное распределение с параметром λ. Таким образом, систему выбора персонализированных предложений можно рассматривать как многоканальную СМО без отказов (заявки не покидают очередь) с количеством обслуживающих устройств m. При этом имеется желательный лимит на суммарное время ожидания и обслуживания T (время пребывания заявки в системе). При функционировании системы требуется, чтобы доля необработанных за данное время запросов не превышала γ от общего числа запросов. Требуется оценить минимальное количество обслуживающих устройств m (серверов подбора рекламы), необходимых для обеспечения работы системы на заданном уровне. 2. Аналитическая модель рекламной системы как системы массового обслуживания Описанная выше СМО традиционно обозначается как M/M/m, время обслуживания заявки считаем распределенным по экспоненциальному закону с интенсивностью µ (среднее время обслуживания равняется 1/µ). Схема такой СМО представлена на рис. 1. Математическая модель данной СМО описана в литературе[1]. Воспользуемся данными результатами для анализа системы выбора персонализированных предложений. Будем рассматривать стационарный режим работы системы. Обозначим приведенную плотность потока заявок через . Будем считать, что , так как в противном случае рассматривать систему смысла не имеет. Рис. 1. Схема СМО M/M/m Figure 1. M/M/m QS scheme Вероятность того, что в системе нет ни одного запроса, равняется: . (1) Вероятность ожидания в системе равняется: (2) Плотность распределения времени ожидания в такой системе равняется [3]: (3) где - импульсная функция в начале координат (она появляется для нормировки плотности распределения вероятности). Плотность распределения для времени обслуживания традиционно равняется: (4) Требуется найти плотность распределения . Плотность распределения случайной величины, равной сумме двух независимых случайных величин, рассчитывается по правилу свертки[2]: (5) Возьмем данный интеграл для заданных плотностей распределения. Поскольку плотности распределения и имеют ненулевое значение только при положительных значениях аргумента (см. (3) и (4)), в выражении (5) ненулевое значение получается при и . Следовательно, пределы интегрирования по u следует изменить от 0 до t. Тогда получаем: Рассмотрим каждый интеграл в отдельности. Последнее равенство верно в силу симметричности свертки функций. Согласно фильтрующему свойству дельта функции [3], Рассмотрим второе слагаемое: Складывая оба полученных слагаемых, получаем, что плотность распределения времени пребывания заявки в системе равняется: Итого получаем, что плотность распределения времени ожидания и обслуживания равняется: Нетрудно проверить, что интеграл от данной функции по всем значениям t равняется 1. Для получения функции распределения данной случайной величины необходимо проинтегрировать ее плотность распределения: Поскольку плотность распределения имеет ненулевое значение при положительном значении аргумента, получаем, что пределы интегрирования следует изменить от 0 до t. Кроме того, для краткости записи, Согласно требованиям модели, за заданный лимит После небольших преобразований получаем Соответственно, требуется определить, при каком минимальном значении m выполняется данное неравенство. Ясно, что получить аналитическое выражение для m через известные параметры не удастся, однако на основании полученных выражений можно составить график доли запросов γ, которые не успели обработаться за заданное время, от количества серверов m. Затем с его помощью можно оценить необходимое число серверов для разной сложности модели прогнозирования. Однако следует отметить, что при моделировании системы выбора персонализированных предложений параметры m и принимают большие значения в несколько сотен, а то и тысяч (так как имеется минимум несколько десятков серверов, каждый из которых обрабатывает по паре десятков запросов). В результате вычисление и приводит к переполнению. Например, в языке python при использовании экспоненциальной формы представления чисел максимальное значение порядка степени составляет 307-308, т. е. максимально возможное представимое число имеет порядок 10307-308. Однако, к примеру, даже 200200 = 10log 200⋅200 ≈10460, т. е. наступает переполнение. Решение этой проблемы с помощью специализированных библиотек для работы с большими числами также не есть хороший путь, поскольку будут возрастать погрешности, тем более при реальном моделировании системы выбора персонализированных предложений числа получаются ещё значительно больше и можно все равно получить значение, бóльшее, чем максимально допустимое в библиотеке. По этой причине предлагается провести определенное преобразование формул (1) и (2). Изначально имеем: (6) Слагаемое в сумме можно вычислить следующим образом: При программной реализации модели такое выражение легко вычисляется в обычном цикле. Для суммирования достаточно написать еще один цикл. Таким образом, значение вероятности ожидания в системе предлагается вычислять по формулам (6) и (7). 3. Пример моделирования рекламной системы как системы массового обслуживания В качестве примера оценим количество обслуживающих устройств (серверов подбора рекламы), необходимых для удовлетворительной работы системы. Будем рассматривать 3 модели прогнозирования [4]: 1. Логистическая регрессия с хешированием комбинаций признаков (lr); 2. Нейросеть, перебирающая пары признаков (nn2) [3]; 3. Нейросеть, перебирающая тройки признаков (nn3) [3]. Зададим следующие значения параметров: - = 40000 запросов/с; - = 0,01 с; - = 0,0002×50 = 0,01 с; - = 0,00022×50 = 0,011 с; - = 0,0003×50 = 0,015 с; - 1/с; - T = 0,1 с. Параметр был рассчитан на основании данных из открытых источников [4] по аудитории крупнейших сайтов в РФ и по среднему количеству просматриваемых баннеров (для крупных проектов в интернете с миллионами пользователей эта цифра может достигать и сотен тысяч запросов в секунду). Время, затрачиваемое на работу моделей , , складывается из времени прогнозирования одного примера, умноженного на примерное число баннеров, из которых производится выбор (при моделировании будем считать, что это 50 баннеров). Время обслуживания складывается из времени, затрачиваемого на получение оценок для баннеров и прочие служебные операции . Интенсивность обслуживания µ обратно пропорциональна среднему времени обслуживания (обработки запроса). Будем считать, что для удовлетворительной работы системы выбора персонализированных предложений необходимо, чтобы не более 1 % запросов обрабатывались более времени T = 0,1 с. При моделировании изменялось количество обслуживающих устройств m и измерялось значение γ - доли запросов, которые обрабатывались более времени T. Результаты моделирования приведены на рис. 2. Рис. 2. Результаты моделирования системы выбора персонализированных предложений как СМО Figure 2. Results of modeling the system for selecting personalized offers as a QS По результатам моделирования видно, что 810- 815 обслуживающих устройств (около 82 серверов, обрабатывающих по 10 запросов одновременно) достаточно для обеспечения работы системы при использовании модели логистической регрессии (доля запросов, не успевших обработаться за 0,1 с, составляет около 0,7 %). При использовании нейросети с перебором пар признаков требуется 850-855 обслуживающих устройств (доля запросов, не успевших обработаться за 0,1 с, составляет около 0,9 %). При использовании модели нейросети с перебором троек признаков для стабильной работы требуется около 1020 обслуживающих устройств, но при этом доля запросов, не успевших обработаться за 0,1 с, все равно превышает лимит, составляя около 1,9 %). С учетом получаемой прибыли от работы каждой модели можно сделать вывод о целесообразности ее применения. Заключение Таким образом, предложенная в работе аналитическая модель системы выбора персонализированных предложений как СМО позволяет принимать решения относительно целесообразности использования того или иного алгоритма прогнозирования в системе. По результатам моделирования формируется картина затрат на оборудование при использовании каждой из моделей, необходимых для достижения целевого времени обработки заявок в системе (чтобы требуемая доля заявок была обслужена за заданный лимит времени). С учетом данных о прибыли системы при работе с каждой из моделей можно принять решение о том, какую модель стоит использовать на практике.

Об авторах

Юрий Сергеевич Федоренко

Московский государственный технический университет имени Н.Э. Баумана (национальный исследовательский университет)

Автор, ответственный за переписку.
Email: fedyura11235@mail.ru
SPIN-код: 1755-4017

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

Российская Федерация, 105005, Москва, 2-я Бауманская ул., д. 5, стр. 1

Список литературы