Математическое и программное обеспечения обучения и оценки рекомендательных систем на основе синтетических данных тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Лысенко Антон Викторович

• Лысенко Антон Викторович
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Лысенко Антон Викторович

Реферат

Synopsis

Введение

Глава 1. Рекомендательные системы и симуляторы

1.1 Классификация рекомендательных систем

1.2 Проблемы обучения рекомендательных систем на данных

1.3 Симуляторы взаимодействий пользователей с рекомендательной системой

1.4 Задачи обучения, оценки, сравнения и реинжиниринга рекомендательных систем

1.5 Выводы к первой главе

Глава 2. Моделирование синтетических профилей

пользователей рекомендательных систем

2.1 Общая постановка метода

2.2 Алгоритм синтеза данных

2.3 Задание сценариев поведения пользователей

2.4 Алгоритмы подготовки данных

2.5 Выводы к второй главе

Глава 3. Моделирование пользовательского отклика с учетом

внешних факторов

3.1 Общая постановка метода

3.2 Многокомпонентная функция отклика

3.3 Использование многокомпонентного отклика для сценарного моделирования

3.4 Учет внешних факторов в отклике пользователя

3.5 Выводы к третьей главе

Глава 4. Симулятор взаимодействия пользователей с рекомендательными системами

Стр.

4.1 Симулятор и методика его применения

4.2 Оценка применимости для обучения рекомендательных систем

4.3 Оценка применимости для оценки рекомендательных систем

4.4 Оценка применимости для сравнения рекомендательных систем

4.5 Оценка эффективности симулятора

4.6 Выводы к четвертой главе

Заключение

Список сокращений

Словарь терминов

Список рисунков

Список таблиц

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

Приложение А. Вычислительные ресурсы для экспериментов

Приложение Б. Основные публикации автора по теме

диссертации

Реферат

Актуальность темы. Рекомендательные системы предназначены для предоставления пользователю подходящих предложений на основе доступных данных объектов контента (например, книгах, фильмах, и пр.), данных о пользователе (например, поле, возрасте, жанровых предпочтениях) и истории взаимодействия пользователя с контентом. Рекомендательные системы являются важной частью крупных систем электронной коммерции, таких как Amazon, eBay, Netflix и Google за рубежом, а также Яндекс, Озон и Сбер в РФ. Внедрение рекомендательных систем осложняется проблемой "холодного старта", связанной с высокой стоимостью и рисками обучения алгоритма системы в реальных условиях, недостаточностью ретроспективных данных для обучения и тестирования системы, а также нестационарностью данных, в том числе, в силу взаимовлияния пользователей и рекомендательных систем.

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

1 Transfer learning

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

Степень разработанности проблемы. Задача обучения и тестирования рекомендательных систем с применением синтетических данных является относительно новой, и основные работы по этой теме приходятся на период с 2016 года по настоящее время. Среди авторов можно выделить, например E.Ie и др., а также S.Yao и др., которые независимо занимаются данной проблемой в компании Google и разрабатывают симуляторы для разных целей: первые для работы с RL-алгоритмами, а вторые - для изучения долгосрочных эффектов от использования рекомендательных систем. J.-C. Shi и др. занимаются разработкой симулятора для использования в индустрии (компания Taobao). Множество работ посвящено исследованию эффектов длительного взаимодействия рекомендательных систем с пользователями; работы коллектива G.Adomavicius и др. занимают особое место по степени проработанности этой проблемы. В 2021 году K. Balog и др. провели первый воркшоп по применению симуляторов к системам получения информации в целом, обсуждая также опыт работы в части рекомендательных систем. Среди российских исследователей можно отдельно отметить группу Д. Бугайченко (ПАО "Сбербанк"), имеющей практический опыт обучения рекомендательных систем на синтетических данных. В свою очередь, автор диссертации позиционирует свои исследования в рамках научной школы А. Бухановского, в которой создавались симуляторы синтетических данных для обучения СППР в различных областях (гидрометеорология, здравоохранение, безопасность), но ранее не затрагивалась проблема моделирования взаимодействия пользователя с рекомендательной системой.

Объект исследования. Рекомендательные системы на основе данных.

Предмет исследования. Технологии генерации синтетических данных для обучения систем искусственного интеллекта.

Цель работы. Повышение эффективности2 разработки и обучения рекомендательных систем на ограниченных объемах данных за счет использования синтетических данных.

Введение диссертации (часть автореферата) на тему «Математическое и программное обеспечения обучения и оценки рекомендательных систем на основе синтетических данных»

Задачи работы.

1. Аналитический обзор методов моделирования взаимодействия пользователей и рекомендательных систем с целью выбора направления исследований.

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

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

4. Проектирование и программная реализация открытой библиотеки - си-мулятора взаимодействия пользователей с рекомендательной системой на основе разработанных методов и алгоритмов.

5. Апробация симулятора на практических задачах обучения, оценки и сравнения рекомендательных систем, и оценка эффективности применения.

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

На защиту выносятся:

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

2 Критерием эффективности является снижение времени разработки и обучения по сравнению с традиционным подходом к созданию рекомендательных систем на данных

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

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

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

Соответствие паспорту специальности 1.2.1.

1. П.7. Разработка специализированного математического, алгоритмического и программного обеспечения систем искусственного интеллекта и машинного обучения. Методы и средства взаимодействия систем искусственного интеллекта с другими системами и человеком-оператором;

2. П.14. Методы и средства формирования массивов условно-реальных данных и прецедентов, необходимых для решения задач искусственного интеллекта и машинного обучения.

Теоретическая значимость. Расширение возможностей обучения, тестирования и сравнения рекомендательных систем в условиях малых или устаревших объемов данных.

Практическая значимость. Разработана библиотека с открытым исходным кодом на языке Python для моделирования взаимодействия пользователей с рекомендательными системами, включающая в себя:

1. Модуль генерации синтетических профилей пользователей и предложений контента.

2. Модуль функций отклика пользователей.

3. Модуль обучения, сравнения и тестирования рекомендательных систем.

На основе библиотеки создан фреймворк Sim4Rec4 для моделирования взаимодействий пользователей с рекомендательной системой (вошел в экосистему открытого кода ПАО "Сбербанк").

Получено свидетельство о регистрации программы для ЭВМ.

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

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях:

— 8th International Young Scientists Conference in Computational Science, Ираклион, 2019.

— CIKM 2019 - The 28th ACM International Conference on Information and Knowledge Management, Пекин, 2019.

— X конгресс молодых ученых (КМУ), Санкт-Петербург, 2021.

— 10th International Young Scientists Conference in Computational Science, онлайн, 2021.

— 11th International Young Scientists Conference in Computational Science, Санкт-Петербург, 2022.

Внедрение результатов работы. Результаты использованы в Национальном центре когнитивных разработок (центре НТИ при Университете ИТМО) при выполнении следующих проектов:

— Исследование и апробация подходов реализации математической модели симулятора для моделирования воздействий на синтетические профили клиентов рекомендательными алгоритмами и метода его применения к оценке качества онлайн рекомендательных систем, ПАО "Сбербанк", 2022 г.

4https://github.com/sb-ai-lab/Sim4Rec

— Интеллектуальные технологии больших данных для поддержки принятия решений в финансовой сфере на основе предсказательного моделирования (РНФ 30029), Российский научный фонд, 2017-2023 г.

— Исследование и разработка прикладных сервисов анализа и предсказательного моделирования финансовых процессов на основе больших данных, ПАО "Банк "Санкт-Петербург", 2017-2023 г.

Личный вклад автора. Из работ, которые выполнены в соавторстве, в диссертацию были включены результаты, которые представляют личный вклад автора. Личный вклад автора заключается в разработке методов и алгоритмов, программной реализации библиотеки для генерации синтетических мультимо-дальных данных [1]. В работах [2] и [3] автор разработал алгоритмы генерации отклика в транзакционных данных и реализовывал эксперименты. В работе [4] автором был разработан способ оценки качества симуляторов для рекомендательных систем, а также была выполнена программная реализация симулятора.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и 2 приложений. Полный объём диссертации составляет 242 страницы, включая 67 рисунков и 9 таблиц. Список литературы содержит 82 наименования.

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

Основное содержание работы

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

Первая глава содержит описание рекомендательной системы и применяемых алгоритмов для рекомендации контента какой-либо природы пользователям. Рекомендательные системы представляют собой программы, которые нацелены на определение интересных конечному пользователю объектов контента. Цель рекомендательной системы заключается в определении для пользователя наиболее релевантного контента т.е. выбор aigmaxvey R(y), где R : V ^ R функция релевантности. Далее, основываясь на информации о подходящих объектах контента формируется выдача контента пользователю, которая, строго говоря, может преследовать не только цель рекомендации наиболее релевантного контента, но и, например, удержание пользователя в сервисе, что не обязательно предполагает оптимальный контент.

На сегодняшний день существует множество рекомендательных алгоритмов, которые могут использовать разный принцип построения рекомендаций и использовать разную информацию о контенте и пользователях: алгоритмы коллаборативной фильтрации, User kNN, Item kNN, а также алгоритмы, использующие скрытое пространство пользователей и контента, построенного через факторизацию матрицы откликов, например, ALS, FunkSVD и другие. Существуют также алгоритмы, учитывающие дополнительную информацию о пользователях и контенте, например, алгоритмы, основанные на Байесовском подходе [5], алгоритмы, использующие обучение с подкреплением [6], или же алгоритмы, основанные на моделях глубокого обучения [7; 8]. Существуют также гибридные и ансамблевые варианты рекомендательных алгоритмов (например [9]), использующие сразу несколько подходов, которые могут закрыть слабые места друг друга.

Однако, разработка и исследование рекомендательных систем остаются нетривиальными задачами и по сей день. Обусловлено это несколькими факторами: начиная с проблемы "холодного старта" [10] и недостаточности данных для каждого пользователя, заканчивая расхождением между метриками при

оффлайн и онлайн тестировании одной рекомендательной системы [11]. Среди основных проблем разработки и исследования можно выделить следующие:

— Сложность, высокая стоимость и риск обучения и тестирования РС в реальной среде;

— Недостаток исторических данных для оффлайн-обучения и оффлайн-тестирования РС;

— Наличие ограничений конфиденциальности для реальных данных;

— Необходимость анализа "что-если" при обучении и тестировании РС, основанного на предположениях о поведении пользователя;

— Присутствие смещения в исторических данных (например, популярности или положительного отношения пользователей), используемых для оффлайн-обучения и оффлайн-тестирования РС;

— Несогласованность метрик качества РС при оффлайн и онлайн тестировании.

Одним из перспективных подходов для решения этих проблем является использование синтетических данных и моделирование взаимодействий пользователей с рекомендательной системой [12—15]. Заменяя настоящих пользователей синтетическими и моделируя их поведение, можно построить искусственную среду, в которой взаимодействие пользователей с рекомендательной системой будет симулироваться. Совокупность моделей и правил (фреймворки), обеспечивающие такого вида моделирование, называются симуляторами и зачастую сопровождаются программными решениями. Так, симуляторы для рекомендательных систем позволяют:

— Дополнить или заменить реальные данные синтетическими аналогами;

— Обучать и тестировать РС в симулированной среде, преодолевая проблему недостатка данных [16] и избегая сложных и рискованных онлайн-экспериментов [13];

— Обеспечивать конфиденциальность реальных данных;

— Обучать и тестировать существующие и новые РС в различных условиях и сценариях поведения пользователей [17];

— Изучать и контролировать влияние смещения исторических данных и долгосрочных эффектов взаимодействия пользователей и РС [18—20].

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

мой во времени, что может быть невозможно при использовании существующих накопленных данных. Проблема использования существующих данных состоит в первую очередь в том, что разрабатывая или тестируя новый алгоритм, мы вынуждены опираться на данные, накопленные с использованием другого алгоритма, что, однако, может быть оправдано, только если поведение этих двух алгоритмов схоже, и поведение пользователей в накопленных данных будет отражать потенциальное их поведение в новой системе [13]. Используя же симулятор, можно не ограничиваться какими-либо траекториями пользователя, а создавать каждый раз новые, подразумевая какую-либо пользовательскую модель поведения. Аспектом, заменяемым симулятором, может быть не только пользователь - заменить можно и контент, а также какие-либо другие свойства среды. Обычно, в литературе по симуляторам для рекомендательных систем выделяют следующие компоненты [21]:

— Пространство пользователей;

— Пространство контента;

— Функция отклика (пользовательский отклик);

— Динамическое изменение среды;

— Другие параметры среды (число рекомендаций, ...).

В качестве задач, которые решаются с использованием симуляторов:

— Обучение РС;

— Оценка РС;

— Сравнение нескольких РС;

— Реинжиниринг РС.

Из анализа существующих решений в области моделирования взаимодействий пользователей с рекомендательными системами видно, что решения так или иначе фокусируются на конкретных задачах, не предоставляя возможности решать одним симулятором несколько задач: от обучения системы для использования в реальной среде до исследования различных сценариев поведения пользователей, похожих при этом на существующие. Таким образом, разработка симулятора, способного обеспечить уменьшение simulation to reality gap и одновременно способного задать разные сценарий поведения (свойства и отклик пользователя) является актуальной задачей.

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

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

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

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

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

В качестве требований для генератора данных, разрабатываемого в рамках данного исследования, были предъявлены следующие требования:

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

2. Обучение и вывод генеративной модели осуществляется на основе ано-нимизированных данных;

3. Генератор синтетических пользователей должен позволять генерировать пользователей с заданными свойствами.

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

Мультимодальность обеспечивает возможность моделировать отдельные множества атрибутов пользователя при условии наличия других, что позволяет генерировать профили с заданными характеристиками. Использование же модели глубокого обучения для генерации данных обусловлено высокой способностью таких моделей моделировать совместное распределение в данных, что подтверждается различными работами, посвященными генерации различного типа данных [22—24].

Мультимодальный вариационный автокодировщик. В случае работы с мультимодальными данными, применяется метод, описанный в работе [22], и предполагается, что х1,х2,...,хм представляют собой N условно независимых модальностей, при условии существования общей скрытой переменной 2. В итоге генеративная модель имеет следующую структуру: р&(х1,х2,...,хм, г) = р(х)рв(х1\г)рв(х2\г)...рв(х^\х). Благодаря такой факторизации можно пренебречь отсутствующими модальностями при оценке маргинальной вероятности. На схеме 1 представлена иллюстрация мультимодальной архитектуры с двумя модальностями.

Дополнительные параметры ц и а0 представляют собой априорные значения для аппроксимации совместного апостериорного распределения в модели "произведение экспертов" (РоЕ). Затем РоЕ комбинирует ц и а следующим образом: ц = (а Цг7*)Ег Тг)-1 и а = (^г Тг)-1, где Тг = Ц-1 - это обратная ковариация ¿-ой модальности.

Также была выполнена реализация ещё одного мультимодального автокодировщика, но с разделенным скрытым пространством на общее для всех модальностей и отдельное для каждой, реализуя выделение общих и раз-

X11 X21

X12 У,2 X22

0 U3 X23

X1n un 0

Рисунок 1 — Схематичное описание MVAE, состоящего из двух модальностей. Здесь Ei, щ, dj обозначают г-ую сеть вывода (г-ый энкодер) с её вариационными параметрами, а Цо и do представляют собой априорные параметры. Произведение экспертов (PoE - Product of Experts) объединяет все вариационные параметры наиболее оптимальным образом. Для каждого пользователя щ входные данные представлены в виде вектора X1 и X2¿, либо пустого множества, если модальность отсутствует

дельных признаков генеративной моделью. В данном исследовании она будет упоминаться как MEMVAE.

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

1. Разбиение данных на модальности (рассмотрение данных с точки зрения одной модальности является частным случаем);

2. Выбор нужной модели среди MVAE и MEMVAE исходя из данных и предварительных оценок качества моделей на них;

3. Обучение модели на представленных модальностях;

4а. Семплирование из нормального распределения М(0 ,Ej) шумовых векторов, размерностью d, совпадающей со скрытым пространством модели (дополненных нулевыми векторами на каждую модальность в случае MEMVAE);

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

получение общего представления (дополненного нулевыми векторами в случае МЕМУЛЕ для отсутствующих модальностей);

5. Декодирование интересующих модальностей соответствующими декодерами (в случае обычной генерации всех модальностей);

6. Приведение типов данных в соответствии со схемой, предоставленной во время обучения.

Выбор между генеративными моделями МУЛЕ и МЕМУЛЕ является ситуативным и зависит от рассматриваемых данных. Так, для некоторых наборов данных нельзя однозначно ответить про качество получаемых синтетических профилей, поскольку одна модель может превосходить в качестве другую для одних атрибутов или метрики, и в то же время проигрывать в качестве для другого аспекта.

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

Формально для генерации пользователей с заданными характеристиками используется генеративная модель, учитывающая только одну модальность, и генерирующая остальные модальности ре(х2,х3,... ,хм\х1) = \х1)ре (х2\г )ре(х3\г) ...ре(хм \г), где х1,х2,...,хм представляют соответствующие модальности. В качестве и ре предстают соответствующие энкодеры и декодеры моделей: если речь идет о, например, дф(г\х1), то используется энкодер первой модальности для получения г, а ре(хг\г) (декодер ¿-ой модальности) декодирует нужную часть профиля.

В качестве верификации и валидации работы генератора синтетических профилей в условиях генерации профилей с заданными свойствами был проведен эксперимент по сценарному моделированию пользовательской популяции с использованием набора данных Моу1еЬепэ, о котором более подробно можно прочитать в четвертой главе. В рассматриваемых данных, в профилях пользователей содержится вектор, отражающий долю фильмов каждого жанра среди всех оцененных ими фильмов. Сам эксперимент заключается в обучении и тестировании рекомендательной системы ИСБ на синтетических данных пользователей двух различных групп: пользователей, чьи интересы в жанрах достаточно разнообразны (в распределении жанров нет доминирующего

0.5

0.2

0.1

0.7 -

0.6 -

0.5 -

0.4 -

о.з -

0.2 -

0.1 -

II о.о -

9 3

а)

б)

Рисунок 2 — Усредненные значения встречаемости фильмов различных жанров среди пользователей из кластера с разнообразным набором жанров (а); с узким

набором жанров (б)

жанра), а также пользователи, с одним доминирующим жанром. Обе группы генерируются моделью МУЛЕ, где первая получается путем генерации из шума М(0, Е), а вторая с помощью условной генерации, где в качестве характеристик подается жанровый вектор, с повышенным предпочтением в определенном жанре. Усредненные значения жанровых векторов описанных групп можно увидеть на рисунке 2.

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

weight_c3

Рисунок 3 — Кривая, построенная по значениям NDCG@10 для различных соотношений кластеров пользователей (шаг 0.1), для синтетических данных на основе MovieLens: значение 0.0 для weight_с3 означает, что вся выборка пользователей состоит из группы с узким жанровым предпочтением, и 1.0 соответствует обратной ситуации. Черным обозначена линия тренда

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

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

Список литературы диссертационного исследования кандидат наук Лысенко Антон Викторович, 2023 год

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

1. Lysenko A., Deeva I., Shikov E. MVAESynth: a unified framework for multimodal data generation, modality restoration, and controlled generation // Procedia Computer Science. — 2021. — Т. 193. — С. 422—431.

2. Lysenko A., Shikov E., Bochenina K. Temporal point processes for purchase categories forecasting // Procedia Computer Science. — 2019. — Т. 156. — С. 255—263.

3. Lysenko A., Shikov E., Bochenina K. Combination of individual and group patterns for time-sensitive purchase recommendation // International Journal of Data Science and Analytics. — 2020. — С. 1—10.

4. Performance Ranking of Recommender Systems on Simulated Data / E. Stavinova [и др.] // Procedia Computer Science. — 2022. — Т. 212. — С. 142— 151.

5. BPR: Bayesian personalized ranking from implicit feedback / S. Rendle [и др.] // arXiv preprint arXiv:1205.2618. — 2012.

6. DRN: A deep reinforcement learning framework for news recommendation / G. Zheng [и др.] // Proceedings of the 2018 world wide web conference. — 2018. — С. 167—176.

7. Wide & deep learning for recommender systems / H.-T. Cheng [и др.] // Proceedings of the 1st workshop on deep learning for recommender systems. — 2016. — С. 7—10.

8. Zheng L, Noroozi V., Yu P. S. Joint deep modeling of users and items using reviews for recommendation // Proceedings of the tenth ACM international conference on web search and data mining. — 2017. — С. 425—434.

9. Wang H., Wang N., Yeung D.-Y. Collaborative deep learning for recommender systems // Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. — 2015. — С. 1235—1244.

10. Lika B., Kolomvatsos K., Hadjiefthymiades S. Facing the cold start problem in recommender systems // Expert systems with applications. — 2014. — Т. 41, № 4. — С. 2065—2073.

11. Do offline metrics predict online performance in recommender systems? / K. Krauth [и др.] // arXiv preprint arXiv:2011.07931. — 2020.

12. SimuRec: Workshop on synthetic data and simulation methods for recommender systems research / M. D. Ekstrand [и др.] // Proceedings of the 15th ACM Conference on Recommender Systems. — 2021. — С. 803— 805.

13. Bernardi L., Batra S., Bruscantini C. A. Simulations in Recommender Systems: An Industry Perspective // arXiv preprint arXiv:2109.06723. — 2021.

14. Kiyohara H., Kawakami K., Saito Y. Accelerating Offline Reinforcement Learning Application in Real-Time Bidding and Recommendation: Potential Use of Simulation // arXiv preprint arXiv:2109.08331. — 2021.

15. Report on the 1st simulation for information retrieval workshop (Sim4IR 2021) at SIGIR 2021 / K. Balog [и др.] // ACM SIGIR Forum. Т. 55. — ACM New York, NY, USA. 2022. — С. 1—16.

16. DataGenCARS: A generator of synthetic data for the evaluation of context-aware recommendation systems / M. del Carmen Rodriguez-Hernandez [и др.] // Pervasive and Mobile Computing. — 2017. — Т. 38. — С. 516—541.

17. Recsim: A configurable simulation platform for recommender systems / E. Ie [и др.] // arXiv preprint arXiv:1909.04847. — 2019.

18. Measuring recommender system effects with simulated users / S. Yao [и др.] // arXiv preprint arXiv:2101.04526. — 2021.

19. Keeping dataset biases out of the simulation: A debiased simulator for reinforcement learning based recommender systems / J. Huang [и др.] // Proceedings of the 14th ACM Conference on Recommender Systems. — 2020. — С. 190—199.

20. Understanding longitudinal dynamics of recommender systems with agent-based modeling and simulation / G. Adomavicius [и др.] // arXiv preprint arXiv:2108.11068. — 2021.

21. Siren: A simulation framework for understanding the effects of recommender systems in online news environments / D. Bountouridis [и др.] // Proceedings of the conference on fairness, accountability, and transparency. — 2019. — С. 150—159.

22. Wu M., Goodman N. Multimodal generative models for scalable weakly-supervised learning // Advances in neural information processing systems. — 2018. — Т. 31.

23. Neural text generation with unlikelihood training / S. Welleck [и др.] // arXiv preprint arXiv:1908.04319. — 2019.

24. Taigman Y., Polyak A., Wolf L. Unsupervised cross-domain image generation // arXiv preprint arXiv:1611.02200. — 2016.

25. Chaney A. J. Recommendation system simulations: A discussion of two key challenges // arXiv preprint arXiv:2109.02475. — 2021.

26. Ценностно-ориентированное моделирование принятия экономических решений в условиях нестационарности внешней среды / В. Ю. Гулева [и др.] // Научно-технический вестник информационных технологий, механики и оптики. — 2023. — Т. 23, № 1. — С. 121—135.

27. Dynamic Classification of Bank Clients by the Predictability of Their Transactional Behavior / A. Bezbochina [и др.] // International Conference on Computational Science. — Springer. 2022. — С. 502—515.

28. DeepFM: a factorization-machine based neural network for CTR prediction / H. Guo [и др.] // arXiv preprint arXiv:1703.04247. — 2017.

29. Marshall M. Aggregate Knowledge raises $5 M from Kleiner, on a roll // Venture Beat. — 2006. — December 10.

30. The YouTube video recommendation system / J. Davidson [и др.] // Proceedings of the fourth ACM conference on Recommender systems. — 2010. — С. 293—296.

31. Gomez-Uribe C. A., Hunt N. The netflix recommender system: Algorithms, business value, and innovation // ACM Transactions on Management Information Systems (TMIS). — 2015. — Т. 6, № 4. — С. 1—19.

32. Leonard D. Spotify is perfecting the art of the playlist // Bloomberg Businessweek. — 2016.

33. Campos P. G., Diez F., Cantador I. Time-aware recommender systems: a comprehensive survey and analysis of existing evaluation protocols // User Modeling and User-Adapted Interaction. — 2014. — Т. 24. — С. 67—119.

34. Improving recommendation lists through topic diversification / C.-N. Ziegler [h gp.] // Proceedings of the 14th international conference on World Wide Web. — 2005. — C. 22—32.

35. Hurley N., Zhang M. Novelty and diversity in top-n recommendation-analysis and evaluation // ACM Transactions on Internet Technology (TOIT). — 2011. — T. 10, № 4. — C. 1—30.

36. Dean S., Rich S., Recht B. Recommendations and user agency: the reachability of collaboratively-filtered information // Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency. — 2020. — C. 436—445.

37. AliExpress Learning-To-Rank: Maximizing online model performance without going online / G. Huzhang [h gp.] // IEEE Transactions on Knowledge and Data Engineering. — 2021.

38. Wang W. Learning to recommend from sparse data via generative user feedback // Proceedings of the AAAI Conference on Artificial Intelligence. T. 35. — 2021. — C. 4436—4444.

39. Slokom M. Comparing recommender systems using synthetic data // Proceedings of the 12th ACM Conference on Recommender Systems. — 2018. — C. 548—552.

40. Dankar F. K., Ibrahim M. Fake it till you make it: Guidelines for effective synthetic data generation // Applied Sciences. — 2021. — T. 11, № 5. — C. 2158.

41. Feedback loop and bias amplification in recommender systems / M. Mansoury [h gp.] // Proceedings of the 29th ACM international conference on information & knowledge management. — 2020. — C. 2145—2148.

42. Cooper M. D. A simulation model of an information retrieval system // Information Storage and Retrieval. — 1973. — T. 9, № 1. — C. 13—32.

43. Mostafa J., Mukhopadhyay S., Palakal M. Simulation studies of different dimensions of users' interests and their impact on user modeling and information filtering // Information Retrieval. — 2003. — T. 6. — C. 199— 223.

44. The arcade learning environment: An evaluation platform for general agents / M. G. Bellemare [h gp.] // Journal of Artificial Intelligence Research. — 2013. — T. 47. — C. 253—279.

45. Openai gym / G. Brockman [и др.] // arXiv preprint arXiv:1606.01540. — 2016.

46. Usersim: User simulation via supervised generativeadversarial network / X. Zhao [и др.] // Proceedings of the Web Conference 2021. — 2021. — С. 3582— 3589.

47. Virtual-taobao: Virtualizing real-world online retail environment for reinforcement learning / J.-C. Shi [и др.] // Proceedings of the AAAI Conference on Artificial Intelligence. Т. 33. — 2019. — С. 4902—4909.

48. Accordion: a trainable simulator for long-term interactive systems / J. McInerney [и др.] // Proceedings of the 15th ACM Conference on Recommender Systems. — 2021. — С. 102—113.

49. Understanding echo chambers in e-commerce recommender systems / Y. Ge [и др.] // Proceedings of the 43rd international ACM SIGIR conference on research and development in information retrieval. — 2020. — С. 2261—2270.

50. T-RECS: A simulation tool to study the societal impact of recommender systems / E. Lucherini [и др.] // arXiv preprint arXiv:2107.08959. — 2021.

51. Zhou M., Zhang J., Adomavicius G. Longitudinal Impact of Preference Biases on Recommender Systems' Performance // Kelley School of Business Research Paper. — 2021. — № 2021—10.

52. Autorec: Autoencoders meet collaborative filtering / S. Sedhain [и др.] // Proceedings of the 24th international conference on World Wide Web. — 2015. — С. 111—112.

53. Item-based collaborative filtering recommendation algorithms / B. Sarwar [и др.] // Proceedings of the 10th international conference on World Wide Web. — 2001. — С. 285—295.

54. Effects of online recommendations on consumers' willingness to pay / G. Adomavicius [и др.] // Information Systems Research. — 2018. — Т. 29, № 1. — С. 84—102.

55. Channamsetty S., Ekstrand M. D. Recommender Response to Diversity and Popularity Bias in User Profiles. // FLAIRS Conference. — 2017. — С. 657— 660.

56. Pradel B., Usunier N., Gallinari P. Ranking with non-random missing ratings: influence of popularity and positivity on evaluation metrics // Proceedings of the sixth ACM conference on Recommender systems. — 2012. — C. 147—154.

57. Exploring the filter bubble: the effect of using recommender systems on content diversity / T. T. Nguyen [h gp.] // Proceedings of the 23rd international conference on World wide web. — 2014. — C. 677—686.

58. Sunstein C. R. Going to extremes: How like minds unite and divide. — Oxford University Press, 2009.

59. Munn L. Alt-right pipeline: Individual journeys to extremism online // First Monday. — 2019.

60. Recogym: A reinforcement learning environment for the problem of product recommendation in online advertising / D. Rohde [h gp.] // arXiv preprint arXiv:1808.00720. — 2018.

61. Krismawintari N. P. D., Komalasari Y., Utama I. Decision model of use e-money in Covid-19 pandemic situation // Technium Soc. Sci. J. — 2020. — T. 10. — C. 280.

62. Consumption dynamics in the covid crisis: real time insights from French transaction bank data / D. Bounie [h gp.] // Covid Economics. — 2020. — T. 59. — C. 1—39.

63. Sun L, Erath A. A Bayesian network approach for population synthesis // Transportation Research Part C: Emerging Technologies. — 2015. — T. 61. — C. 49—62.

64. Hidden Markov Model-based population synthesis / I. Saadi [h gp.] // Transportation Research Part B: Methodological. — 2016. — T. 90. — C. 1—21.

65. Generative adversarial nets / I. Goodfellow [h gp.] // Advances in neural information processing systems. — 2014. — T. 27.

66. Kingma D. P., Welling M. Auto-encoding variational bayes // arXiv preprint arXiv:1312.6114. — 2013.

67. Rezende D., Mohamed S. Variational inference with normalizing flows // International conference on machine learning. — PMLR. 2015. — C. 1530— 1538.

68. Ho J., Jain A., Abbeel P. Denoising diffusion probabilistic models // Advances in neural information processing systems. — 2020. — T. 33. — C. 6840—6851.

69. Patki N., Wedge R., Veeramachaneni K. The Synthetic data vault // IEEE International Conference on Data Science and Advanced Analytics (DSAA). — 10.2016. — C. 399—410.

70. Rezende D. J., Mohamed S., Wierstra D. Stochastic backpropagation and approximate inference in deep generative models // International conference on machine learning. — PMLR. 2014. — C. 1278—1286.

71. Kingma D. P., Salimans T, Welling M. Variational dropout and the local reparameterization trick // Advances in neural information processing systems. — 2015. — T. 28.

72. Daunhawer I., Sutter T, Vogt J. E. Improving Multimodal Generative Models with Disentangled Latent Partitions. —.

73. Memory-efficient embedding for recommendations / X. Zhao [h gp.] // arXiv preprint arXiv:2006.14827. — 2020.

74. Ozsoy M. G. From word embeddings to item recommendation // arXiv preprint arXiv:1601.01356. — 2016.

75. Grohe M. word2vec, node2vec, graph2vec, x2vec: Towards a theory of vector embeddings of structured data // Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. — 2020. — C. 1—16.

76. Harder F., Adamczewski K., Park M. Dp-merf: Differentially private mean embeddings with randomfeatures for practical privacy-preserving data generation // International conference on artificial intelligence and statistics. — PMLR. 2021. — C. 1819—1827.

77. Aridor G., Goncalves D., Sikdar S. Deconstructing the filter bubble: User decision-making and recommender systems // Proceedings of the 14th ACM Conference on Recommender Systems. — 2020. — C. 82—91.

78. Chaney A. J., Stewart B. M, Engelhardt B. E. How algorithmic confounding in recommendation systems increases homogeneity and decreases utility // Proceedings of the 12th ACM conference on recommender systems. — 2018. — C. 224—232.

79. Collaborative filtering with noisy ratings / D. Li [h gp.] // Proceedings of the 2019 SIAM International Conference on Data Mining. — SIAM. 2019. — C. 747—755.

80. Jakomin M, Curk T., Bosnie Z. Generating inter-dependent data streams for recommender systems // Simulation Modelling Practice and Theory. — 2018. — T. 88. — C. 1—16.

81. Stormer H. Improving e-commerce recommender systems by the identification of seasonal products // Twenty second Conference on Artificial Intelligence. — Citeseer. 2007. — C. 92—99.

82. Keerthika K., Saravanan T. Enhanced product recommendations based on seasonality and demography in ecommerce // 2020 2nd International Conference on Advances in Computing, Communication Control and Networking (ICACCCN). — IEEE. 2020. — C. 721—723.

Приложение А Вычислительные ресурсы для экспериментов

- ОРИ: Ме1(Я) Соге(ТМ) 17-9700 ОРИ @ 3.00GHz

- ИЛМ: 32 GB

- GPU: ОТГОТЛ GeFoгce КТХ 2070 БИРЕК

Приложение Б Основные публикации автора по теме диссертации

CrossMark

Available online at www.sciencedirect.com

ScienceDirect

Procíídia Compter Science 156 (2019) 255-263

Procedía

Computer Science

www.elsevier.com/locate/procedia

8th International Young Scientist Conference on Computational Science

Temporal point processes for purchase categories forecasting

Anton Lysenkoa'*, Egor Shikova, Klavdiya Bocheninaa

aITMO University, 49 Kronverkskiy pr., St Petersburg 197101, Russia

Abstract

Forecasting events in banking sphere is very popular topic nowadays because there is much amount of data collected by different information sy^enm such as banks and the avairrbУity of data brings the opportun^y to make many interesting applications for preslictive modele based on this data. For example, you can personalize offem based on forecastmg custnmer needs, by predicting; the expected time and category of nmxt purchase taking into account the transaction history oW a customer. One of the approach to mame a oredictife and generatSfe model for tuis task is temporal point procerses, which in widely used to make preslrctinns or random evente. The problem that comes with building such models is ohat while learning on a set df clients the resulting model neneralizes the behavim of all rources and make; the averaged psedictions such that we tooe any individualrty of a client that we make a prediction on. In this sturdy, we propoea the models based on the iemporal point proceises fiamawork with seme ideas to solve the sssuo described eariier - first is to learn on different activity populations, and the second is based on model individual scaling. Each of the innovations provides an improvement in the error metrics compared to the original model.

© 2019 Thf Authors. Publi^ed by Ebfvifr Ltd.

This is an open access article under the CC BY-NC-ND license (httfs:/ioreatiuehnmmanr.orgiiifrstreolOy-nc-dc44.0/) T;fr-rfvtfw under refponsibihSy o° the scientific eomDirief of tht Milntf rnfetonnlYouno gcieotseCoofteenccon Computational peifnef.

Keywords: events fnrecnstmg;tempnrnl point prncesses;purchnse fnrecnstiag;trnasnctinanl data

1. Intoduction

The availability of technical capabilities for the aggregation of large amounts of data in corporate information systems leads to the possibility of constructing predictive models of customer behavior on the history of their activities. For example, in the banking sector, you can personalize offers based on forecasting customer needs (expected time and category of purchase of the next customer transaction). Such knowledge can allow the bank to anticipate the clients wishes - to provide information about current discounts on a certain category of goods, predict cash flow in a sales and service point, etc. Also, based on payment activity forecasts, bonus programs are developed together with trade and service enterprises. Therefore, the development and study of the effectiveness of methods for predicting customer spending chains is an important topic for research.

* Corresponding author. E-mail address: [e-mail]

1877-0509 © 2019The Authors. Published by Elsevier Ltd.

This is an open access article under theCC BY-NC-ND license (nttps://oreayivocommons.orgniiceoies/°y-nc-nd/4.0/)

Peer-review under responsibility of the scientific committee of the 8th International Young Scientist Conference on Computational Science.

10.1016/j.procs.2019.08.201

256 Anton Lysenko et at. /Procedia Computer Science 156 (2019) 255—263

So, in this study we've developed a generative model of client spending, which allows predicting the occurrence and time of spending in various categories based on the client's transaction history. This problem can be formalized in the following way:

Let [t0 ,T ) be the obesrvation window with some amount of transactions of every customer in every category.

Each customer u is represented by a sequence of transaction timestamps Tu = {ti,..., tn} and their associated categories (interchangeably called dimensions) Cu = {c1,..., cn} (for example, gas stations, restaurants, etc.).

We need to construct a model that can forecast time and category of the new transaction ofthe client in such way that they would most similar to the real ones.

There exists different approaches to solving this problem. First of all, the time can be simply divided into a set of intervals, and static latent feature models can be applied [2], [5]. However, such models have several disadvantages: first, it is not clear how to choose the interval length parameter; second, different users may have very different time-scales; third, the history of last spendings cannot be incorporated into the model.

The point process-based models can overcome this limitations. By nature, they generate continuous timestamps and the length between them can vary depending on the client' activity. Also, the excitation factors can be added to take into account the last client transactions.

However, the problem arising in our case is that the 3-dimensional matrix (client, category, time) describing the process is highly sparse and many elements are non-observed. Several ways to solve this issue are possible. Approaches based on client-category-time co-occurrence matrix factorization may be viable [6]. However, some authors [3] argue that these methods tend to oversmooth distributions resulting in excessively high probabilities of unseen client-category-time combinations.

In paper [4], the authors decided not to use any client-specific parameters resulting in a model with only 390 parameters for i0 categories. But the problem of the aforementioned model is that it creates an average client if we mix clients with different activity levels during the learning process. It means that for clients with low-level activity the simulation will generate more points, than they really may have, and for clients with high-level activity - not enough.

This issue shown in Fig. ia illustrates the problem when we overgenerate points, and Fig. ib show the vise versa situation with Hawkes process learned on the whole dataset.

time (s) time Is)

(a) (b)

Fig. 1: Different patterns of generating events: (a) overgenerating;(b) insufficient generating. Blue dots are true history and red are generated points To solve this issue we present some methods described below.

2. Model

We developed a model consisting of the inhomogeneous Poisson process and the Hawkes process with the exponential kernel based on the temporal point processes framework. The first one includes time-varying features, such as time of day, day of the week, etc. The second one is responsible for excitation effects of past purchases which makes the intensity function depend on history. Moreover, it can provide mutual-excitement of the events of different types. For example, buying at a clothing store increases the probability of visiting a restaurant. As initial features, the timestamps and categories of customer transactions were injected to the input of the model.

Anton Lysenko et al. /Procedia Computer Science 156 (2019) 255—263 257

The point process is described in term of conditional intensity function which is a stochastic model for the next event time given the history of the events before. History is given as ordered sequence Ht = {ti, t2,..., tn} where ti > ti_1 and tn < t if we talking about one dimensional time point process. For addition, every time point can include some mark such as type of event, which in our scenario is a category of transaction. By that the conditional intensity function is described as follows:

wa i• P{event in (t, t + h]|Ht}

A (t) = lim ---, (1)

h^0+ h

conditioned by history before t. It means that conditional intensity function gives the probability of event appearance in a small time window (t, t + h].

2.1. Poisson process

The simplest process is the homogenous Poisson process that has only one parameter - A0. This process does not depend on the history or anything else and just represents the constant intensity function A(t) = A0, where A0 > 0. As we create a model with separate intensity for each category, the category that is intensity stands for will be denoted with subscript d e {1,..., D}. By itself, the homogenous Poisson process does not make much sense because in our case it just evaluates the average frequency of clients purchases and as output gives constant intensity for any client with any history. To capture some features from given time t we developed the inhomogeneous Poisson process, like it was done in [4], which is presented below.

Ad (t) = Ado + ^ ßdjfj-

jF

(2)

Table 1: Time features that are captured by inhomogenous Poisson process

Index j Time feature

0-23 Hour of a day

24 Monday-Thursday

25 Friday

26 Saturday and Sunday

27 First day of a month

The F is a set of indicator functions that capture time features such as weekends, current hour and etc. The list of those features is presented in table 1. This approach makes sense if we will look at the hour and weekday distributions of the dataset at Figs. 2b and 2c. Following this model if we want to get the probability of an event in Friday at 15 p.m., for example, the sum up the coefficients u with indexes 15 and 25, and the base rate A0.

But the problem is that the inhomogeneous Poisson process cannot capture the history of past events, which means that for every client we will predict results with the same coefficients, so we cannot measure the individuality. To make the model more individual for each client we can use so-called self-exciting Hawkes process.

2.2. Hawkes process

Hawkes process is also called self-exciting or mutual-exciting because it can capture a history of some events in different types(categories) and how events in different categories excite each other in term of probability. Formally the Hawkes process conditional intensity function looks like A*(t) = A0(t) + 2t,eHt tp(t _ t'), where superscript * means that intensity is conditioned by the history Ht. In our work, we used the exponential kernel with parameter fidd and

258 Anton Lysenko et al. /Procedia Computer Science 156 (2019) 255—263

add which are DxD matrix. We can interpret those parameters as matricies where (i, j) element is responsible on how the process deal with pair (ith category event, jth category event). Parameter ¡3 is responsible for the magnitude of the exponential intensity part, and alpha is responsible for decay speed of exponent i.e. how long previous events influence the intensity. As a result, the conditional intensity function of the Hawkes process looks like in formula 3 (left). Combining the inhomogeneous Poisson process with the Hawkes process we get the conditional intensity function like in formula 3 (right).

= ¿d0 + ^ Yj Pdd e-

add' (t-t0

d' = 1 d(t')=d' t'—Ht

rd(t) = Àd0 +2] Vdjfj + Yj Yj Pdd'e

add' (t-t0

(3)

fj—F

= 1 d(t')=d' t'—Ht

d

2.3. Intensity scaling

As it was mentioned, the Poisson process by itself doesn't hold any individuality in u values of the client that we want to predict time and category on. Hawkes process can capture the history of the client, but in practice, it is not enough because using history brings any individuality only in short time, which depends on the parameter a. For example, if we set a = 1 /3600 for some pair (i, j) the history will work only for one hour after the last event occurred, and for the rest of time till next event, the process will look like just inhomogenous Poisson process.

We can interpret intensity as a number of events occurred in the observed time period. So by that, to bring more individuality for the models we can scale the intensity by some coefficient for each category, using the client's history. It makes sense because we keep all generalized behavior of the clients that we trained a model on, but at the same time, we capture the transaction frequency of concrete client. To do so, we take our original conditional intensity function ¿¿it) and multiply it by coefficient by the following rule:

' nd

X*d(t) = ÇdWt), & =~ (4)

nd

•y* client s y transactions i[t — d] . y transactions i[t — d]

nd = #clients * (T -10) ' nd = (T -10) (5)

where t0 is the start of the observed period, and T is the end. 3. Data

3.1. Description

Our bank-partner has provided a large amount of anonymized data with the clients transactional history of about ~ 138,000 clients over the period of one year starting from January. Each transaction is represented by a unique customer identifier, date and time of the transaction, the amount in rubles and category.

For category separation, the MCC (Merchant category code) codes are used in the banking sphere to mark the category of bank operation. MCC code is 4-digit code that classifies the category of bank transaction e.g. 5814 stands for one of Russian popular pizza delivery service, and 3011 is one of airlines services. There are more than 436 unique MCC codes in the dataset and it becomes a problem because if we want to predict a category for next client's purchase we must predict a concrete service, not a generalized category like grocery or shopping. To generalize the categories we used the short representation of the MCC - 2-digit code. So by that, if we deal for example with different grocery markets we can represent it by one code.

Anton Lysenko et al. /Procedia Computer Science 156 (22019) 255—263

259

(a)

(b)

(c)

Fig. 2: (a) Distribution of the client's activity - the number of transaction on the OX, the number of clients on OY. (b) and (c) Distributions of the number of transactions by hours and by weekdays respectively

After the aforementioned MCC codes transformation, we've got 87 unique categories. They included some popular categories like clothes, shopping, etc. and some rare categories like buying a new house or car. For our test purposes, we have chosen only the top 10 categories by the number of occurrences, which are shown in table 2.

Table 2: Purchase categories used.

N Category name Average monthly Fraction

number of trans- clients

actions transaction

category

1 Gas stations 1.58 0.43

2 Medical goods 1.56 0.62

3 Clothing and Accessories - middle segment 1.07 0.45

4 Personal services - other 0.97 0.43

5 Alcohol 0.60 0.20

6 Grocery 16.2 0.95

7 Restaurant 5.46 0.77

8 Special shops - other 0.84 0.37

9 Taxi and public transport 2.39 0.44

10 Financial services 4.05 0.84

of with

Clients' behavior differs from one to another - some of them have very low transaction activity (from 20 to 50 transactions over a year), but some have up to 3500 transactions over a year which means, that they can perform near the 10 transactions per day. For this study we used only active clients with more than 5 transactions per month on average. Distribution of clients activity by the number of transactions over a year is shown in Fig. 2a.

3.2. Filtering

To work with the dataset, first of all, we need to check if there are unstable clients, that, for example, hold banking card just to receive money on payday or card expired just after several days after our observation period starts. The first filtering step was to remove all transactions that are not in the top 10 categories - those are about 10% of the whole dataset. Next step comes with an issue with bank operation timing - as the dataset was observed we found out that there are transactions with 00:00:00 time. The partner bank can perform the delayed transactions when they complete only by the end of the day. All transactions that have "zero time" was removed from dataset as they are only about 7% of whole data. The next step was to remove clients, that are probably started to use a card not from the beginning of the observed period or their card has expired before the observed period ended and etc. For this propose we have left only clients with at least one transaction before February and at least one after November. And for the last filtering step, we took clients with at least 20 transactions over the observed period just to make sure that all the clients are active enough. After all previous filtering, our dataset contained 50,488,819 transactions from 116610 unique clients in ten most active categories.

260 Anton Lysenko et at. /Procedia Computer Science 156 (2019) 255—263

4. Learning and prediction

4.1. Learning

To estimate the parameters of the Poisson and Hawkes processes we can use maximum likelihood estimation over conditional intensity function as the intensity can be interpreted as the probability of an event in a small time window. Both models are parametrized by Ao (Dx1 base rates) and M (Dx#time features rates for time features) and the Hawkes process additionally is parametrized by B (DxD excitation matrix). We took add as a hyperparameter because learning it could increase learning time in a hundred times. By that, the resulting log-likelihood functions is shown in (6), where integral term is a survival term, y is the L2 reguralizer hyperparameter and 0 is a set of all learnable parameters.

n D

L({(ti,di),...,(tn,dn)}) = Yj log(4ft)(t<)) I 4(T)dr-y||0||2 (6)

The likelihood function over entire dataset is a sum of likelihood over every client. Using that we can split the evaluation of likelihoods among multiple CPU cores and then just aggregate results.

Resulting log-likelihood function is optimized by the L-BFGS-B algorithm since we can put the limits on the parameters such as all parameters in the model cannot be less than zero. Training both models scales linearly of the dataset size. Time, which was taken to run the L-BFGS-B on 100 iterations is approximately 2 hours for the Poisson process and 7 hours for the Hawkes process.

4.2. Learn on the activity groups

To solve the problem of an "averaged client" we tried to split the original dataset into several groups by the clients' activity. The dataset was split into seven groups such as every group has approximately uniform or normal (if possible) distribution over clients activity. The description of the aforementioned groups is given in table 3.

Table 3: Activity groups

Number of transactions Number of clients in a group

20 - 250 18253

250 -400 48261

400 -600 33156

600 -750 9331

750 - 1000 5308

1000- 1600 4308

1600+ 1111

4.3. Prediction

Both models as output can generate next event time and category, and the sequences of the events by predicting the events one right after another, taking previously as a history. To generate a time of the next event the Ogata's modified thinning algorithm [1] was used in case of Hawkes process and algorithm for simulation inhomogeneous Poisson process [1] for the other one. In both cases the following prediction algorithm for time and category was used:

We implemented the evaluation of the median of the 100 runs to take the most probably time prediction (1), and then we predict category based on that time by the multinomial distribution. To generate a sequence of the events we can just run the algorithm 1 multiple times, each time starting from the last event time.

Anton Lysenko et al. /Procedia Computer Science 156 (2019) 255—263 261

Algorithm 1 Prediction time and category of the next event

1: procedure predict(î0, history)

2: time [100]

3: for integer i in 100 do

4: time[i] = simulate one event by Ogata's/Poisson simulation algorithm

5: end for

6: t = median(time)

7: c = multinomial({A0(t),..., A*D(t)})

8: Return (t, c)

9: end procedure

5. Results

After evaluation parameters via maximizing the log-likelihood, we can interpret those parameters in the following way. Every udj shows how the wall-clock time influences the probability to make a purchase at this time. Fig. 3b shows the estimated parameter u values, and we can watch the similarity between the resulting intensity and the hour distribution of the original dataset. As for the parameter ¡3 - it can be interpreted as how the purchase in one category influences the probability of the purchase in another. The top five ¡3 values are shown in table 4, where it's clearly seen that at most scenarios, categories highly increase the chance of itself to be performed next.

The general plot of the resulting Hawkes process with inhomogeneous Poisson process conditional intensity function is shown in Fig. 3a.

Table 4: Top five betas values.

From category

To category

Restaurant Household goods Special shops - other

Clothing and Accessories - middle segment Grocery

Restaurant Household goods Special shops - other

Clothing and Accessories - middle segment Finantial services

3.70e-05 2.25e-05 1.99e-05 1.72e-05 1.57e-05

time (s) time Is)

(a) (b)

Fig. 3: Intensity functions. (a) Conditional intensity functions for the first five categories marked with different colors;(b) estimated n parameters for the Medical goods category.

To assess the quality of the constructed models, the accuracy of time prediction and the category of generated events were evaluated separately. The quality metrics that were used are the absolute time error averaged across all clients and the fraction of correctly predicted event categories to the total number of predicted events. These metrics

262 Anton Lysenko et at. /Procedia Computer Science 156 (2019) 255—263

were calculated for the Poisson process and the Hawkes process with variations in the dimension of the data and hyperparameters of the models.

Through all metrics we can see, that Hawkes process is doing better than inhomogeneous Poisson one in both metrics. This is because Hawkes process can capture the history of previous transactions and is more flexible to capture the patterns of transactions.

5.1. Time error

To make error evaluations first we divided the dataset into two parts: training and test data. The training set consisted of transactions during the period of the beginning of January till the end of October, and the test set consisted of all the rest period - November and December. All the models were trained on the training data and then each prediction was made started from the last client's transaction till the end of October. So if, for example, a client has transactions at the 30th of October and at the 1st of November right after previous one, we took the time of first mentioned transaction and tried to predict the next. In other words, we predict the interarrival time of the events, and then predict category based on the predicted time. The error metric, that was used for time error - MAE (mean absolute error).

All the error and accuracy evaluations were performed on all of the groups, which are mentioned in table 3. To not mess up with results on every group, we've shown the results only on the smallest (1600+) and the biggest (250-400) groups, but all other groups have similar results: models without modifications are better to predict the category, than models which were trained on separate groups, but have more time error. Models with coefficient f modification are better than the other two cases in time error and category prediction.

In the tables 5 and 6 Poisson/Hawkes is a model, which was trained on an entire dataset without modification (coefficient f). Grouped model is a model, which was trained on particular dataset (pointed in column "Test dataset") from table 3. And the f coefficient model is a model with intensity scaling modification, trained on the entire dataset.

Table 5: Time error models results

Model Test dataset MAE (hours) MAE (best category) MAE (worst category)

Poisson 250-400 38.8 h 25.6 h 86.6 h

Poisson grouped 250-400 38.4 h 25.2 h 85.8 h

Poisson f coeff. 250-400 37.2 h 24.1 h 84.5 h

Hawkes 250-400 36.7 h 24.1 h 86.4 h

Hawkes grouped 250-400 37.2 h 23.9 h 83.1 h

Hawkes f coeff. 250-400 35.3 h 22.8 h 81.7 h

Poisson 1600+ 20.3 h 4.5 h 48.3 h

Poisson grouped 1600+ 18.6 h 5.5 h 47.2 h

Poisson f coeff. 1600+ 18.5 h 7.8 h 55.0 h

Hawkes 1600+ 19.3 h 4.8 h 46.2 h

Hawkes grouped 1600+ 18.2 h 5.1 h 49.3 h

Hawkes f coeff. 1600+ 17.1 h 4.3 h 53.3 h

All the results, that were obtained during the time error evaluation, are given in table 5. The results show that for every model's modifications and dataset to learn on, the Hawkes process always beats the Poisson process in time and accuracy. Firstly, we evaluated the error and accuracy of the original Poisson and Hawkes processes without any modifications. Then we've tried to evaluate MAE and accuracy on the seven groups, that are described in table 2. At last, we evaluated metrics for the models with the modification described in section Intensity scaling. We can see, that it results in less MAE comparing to both tests done earlier. By this modification, we keep the generalization ability with learning on the entire dataset, but at the same time, we capture the client's frequency of purchasing and scale up the intensity.

5.2. Accuracy

For measure how good our models predict the category, we used the accuracy score metric. Results, given in table 6, shows, than an average accuracy for the model with f coefficient modification beats all previous. It can be explained

Anton Lysenko et al. /Procedía Computer Science 156 (2019) 255—263 263

Table 6: Accuracy models results

Model Test dataset Accuracy Acc. (best category) Acc. (worst category)

Poisson 250-400 27.4% 43.3% 3.2%

Poisson grouped 250-400 24.7% 52.7% 2.1%

Poisson f coeff. 250-400 32.5% 53.3% 6.9%

Hawkes 250-400 31.2% 47.4% 4.1%

Hawkes grouped 250-400 29.9% 51.8% 3.6%

Hawkes f coeff. 250-400 38.6% 54.1% 7.8%

Poisson 1600+ 24.0% 46.0% 0.0%

Poisson grouped 1600+ 23.7% 35.2% 0.0%

Poisson f coeff. 1600+ 31.5% 47.0% 3.2%

Hawkes 1600+ 34.2% 46.4% 0.1%

Hawkes grouped 1600+ 27.9% 46.1% 0.0%

Hawkes f coeff. 1600+ 41.8% 59.1% 4.5%

in terms of generalization ability if we train on the whole dataset and the fact, that intensities are scaled, which cause more adequate category estimation via multinomial distribution. For the same reasons models, that were trained on the part of the dataset, have less average accuracy, than the original models without any modifications.

6. Conclusion

The time-sensitive purchase categories forecasting is the key to the optimization of personalized offers for customers. To tackle this problem a generative model of client spending has been proposed, which allows predicting the occurrence and time of spending in various categories based on the client's transaction history. Our model is interpretable and provides insights on the dynamics of the consumer's purchase behavior. Different variants of the model were tested, the model incorporating not only the inhomogeneous Poisson process but also the Hawkes process has shown the best results in terms of both error of time prediction and the accuracy of category prediction. Splitting into groups with a separate model for each group increased time metric, but decreased accuracy for most groups. Intensity scaling has resulted in improved both metrics for the general model and the group models.

Acknowledgements

This research is financially supported by The Russian Science Foundation, Agreement 17-71-30029 with co-financing of Bank Saint Petersburg.

References

[1] Daley, D.J., Vere-Jones, D., 2007. An introduction to the theory of point processes: volume II: general theory and structure. Springer Science & Business Media.

[2] Koren, Y., 2009. Collaborative filtering with temporal dynamics, in: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM. pp. 447-456.

[3] Kotzias, D., Lichman, M., Smyth, P., 2018. Predicting consumption patterns with repeated and novel events. IEEE Transactions on Knowledge and Data Engineering PP, 1-1. doi:10.1109/TKDE.2018.2832132.

[4] Manzoor, E., Akoglu, L., 2017. Rush!: Targeted time-limited coupons via purchase forecasts, in: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM. pp. 1923-1931.

[5] Rendle, S., Freudenthaler, C., Schmidt-Thieme, L., 2010. Factorizing personalized markov chains for next-basket recommendation, in: Proceedings of the 19th international conference on World wide web, ACM. pp. 811-820.

[6] Wang, Y., Du, N., Trivedi, R., Song, L., 2016. Coevolutionary latent feature processes for continuous-time user-item interactions, in: Advances in Neural Information Processing Systems, pp. 4547-4555.

Combination of individual and group patterns for time-sensitive purchase recommendation

Anton Lysenko ITMO University 49 Kronverkskiy prospect Saint-Petersburg, Russian Federation [e-mail]

Egor Shikov ITMO University 49 Kronverkskiy prospect Saint-Petersburg, Russian Federation [e-mail]

Klavdiya Bochenina

ITMO University 49 Kronverkskiy prospect Saint-Petersburg, Russian Federation [e-mail]

Abstract

Due to the availability of large amounts of data recom-mender systems have quickly gained popularity in the banking sphere. However, time-sensitive recommender systems, which take into account the temporal behavior and the recurrent activities of users to predict the expected time and category of next purchase, are still an active field of research. Many researchers tend to use population-level features or their low-rank approximations because the client's purchase history is very sparse with few observations for some time intervals and product categories. But such approaches inevitably lead to a loss of accuracy. In this paper we present a generative model of client spending based on the temporal point processes framework, which takes into account individual purchase histories of clients. We also tackle the problem of poor statistics for people with low transactional activity using effective intensity function parametrizations, and several other techniques such as smoothing daily intensity levels and taking into account population-level purchase rates for clients with a small number of transactions. The model is highly interpretable and its training time scales linearly to millions of transactions and cubically to hundreds of thousands of users. Different temporal-process models were tested, our model with all the incorporated modifications has shown the best results in terms of both error of time prediction and the accuracy of category prediction.

Keywords

Point processes; Transactional data; Mixture models; Recommendation; Machine learning

1. INTRODUCTION

Banks have been using corporate databases for a long time, which led to the accumulation of a large amount of different data on the purchasing behavior of customers. Thanks to this, as well as the development of machine learning algorithms, banks have moved from using simple models, such as LRFM (length, recency, frequency, and monetary) model to more complex recommendation models. Typically, these models were used to back up bonus programs developed together with trade and service enterprises for a long fixed period, such as a month. However, the use of time-limited offers can be much more profitable. They may sound as follows: "Hurry up and spend 100 dollars at our partner's restaurant and get double cash-back. The offer is valid until 10 p.m. April the 5th !!!". The efficiency of limited-time

offers is explained by the psychological phenomenon known as loss aversion, which refers to people's tendency to prefer avoiding losses to acquiring equivalent gains. The customer is offered a limited time to make a purchase in a certain category. This offer can be delivered via the bank's mobile application in the form of a coupon. To do this, it is necessary to develop a recommendation system that would predict: 1) the time of the next purchase of the client 2) the most likely categories of purchase.

The problem of predicting the return time can be solved using classical methods, dividing the time into intervals. First of all, the time can be simply divided into a set of intervals, and static latent feature models can be applied [1], [2]. However, such models have several disadvantages: first, it is unclear how to choose the interval length parameter; second, different users may have very different time-scales; third, the history of last spendings cannot be incorporated into the model.

The point process-based models [3] can overcome these limitations. By nature, they generate continuous times-tamps and the length between them can vary depending on the client's activity. Also, the excitation factors can be added to take into account the last client transactions.

A ÉÈ

—H-¿-1-1-U-

Monday

-h

Tuesday

Wednesday

Figure 1: A fragment of the customer's purchase history. Our model is intended for predicting the category and time of spending based on the client's transaction history.

This problem can be formalized in the following way: Let [to ,T ) be the observation window with some number of transactions of every customer in every category. For each customer u we have a set of timestamps representing the history of transactions Tu = {ti,...,tn} and their associated categories Cu = {ci,...,cn} (for example, gas stations, restaurants, transport, etc.).

We need to build a model capable of predicting the time t and category c of the next transaction of the client and the sequence of transactions as well.

In solving this problem, the following features should be taken into account:

• The transaction history of the absolute majority of

4 5

clients is highly sparse and many elements (client, category, time) are non-observed.

• The last spendings are quite important and should be taken into account.

• The level of transactional activity of clients differs a lot.

• There are millions of transactions in the dataset, which opens up the question of scalability.

In paper [4], the authors decided not to use any client-specific parameters resulting in a model with only 390 parameters for 10 categories. This approach uses population-generalized consumption levels, and the transactional history of a particular customer is applied only through the introduction of the terms responsible for self-excitation. Therefore, it is obvious that the forecasts will be biased towards the average level of activity for the dataset, which will lead to big errors for customers with a small daily number of transactions.

Approaches based on client-category-time co-occurrence matrix factorization may be viable [5]. However, some authors [6] argue that these methods tend to oversmooth distributions resulting in excessively high probabilities of unseen client-category-time combinations.

In most works, the authors pay great attention to the factor associated with mutual-excitement. However, we believe that members associated with the inhomogeneous Poisson process, who is responsible for the "timetable" and their modification can bring the best results, should have a greater impact on our dataset.

Since the results of this study were planned to be used for the recommendation system in the bank, we set ourselves the task to build an interpretable model and refrained from using neural net approaches [7],[8],[9],[10]. The model presented below is a generative model of client spending and allows to generate purchasing activity of the population, which is also of interest for the study.

2. MODEL

2.1 Temporal point processes

The temporal point process is usually represented via its conditional intensity function, which can be interpreted as the probability of an event to occur in a small time window. Formally, given the history of previous events at point t as Ht = {ti,t2, ...,tn}, where ti < ti+1 and tn < t, the intensity function looks as follows:

V(t) =

lim

h—>-+0

P(event in (t,t + h]H h

(1)

where each point in a history Ht can be marked with some event category as a pair (ti,di), which in our scenario is transaction category, and the asterisk means that the intensity function is conditioned by the history of events.

The simplest process is the homogeneous Poisson process, which intensity function is represented only by baserate Ao > 0. It is constant through the whole non-negative domain, which means that the probability of an upcoming event is independent of any conditions. By itself, the homogeneous Poisson process does not make much sense because in our case it just evaluates the average frequency of clients

purchases and as output gives constant intensity for any client with any history. To capture some time dependencies we can use the inhomogeneous Poisson process, which is described below.

2.2 Inhomogeneous Poisson process

With inhomogeneous Poisson process we allow the intensity function to vary according to a deterministic function of t, with bounding A(t) > 0,t > 0. In our case, as the t domain refers to time, we can capture the time dependence with the set of indicator functions F and some weights to each of the time feature, described in Table 1. As a result, we obtain the following intensity function for category d:

(2)

Ad (t) = Ad0 + ^^ ^dj fj ,

fj eF

which means that the intensity at some point t0 is defined by the sum of base-rate Ao and every ^dj, that is active at the to, e.g., if we want to get the intensity at 1:30pm on Friday, we sum up ^d,i3 and ¡¿d,25 with Ad0. This makes sense because if we will look at the weekday and the hour distributions of our dataset, presented in Fig. 6a and Fig. 6b, we can see the dependence of current time.

Table 1: Time features that are captured by inhomogenous Poisson process

Index j Time feature

0-23 Hour of a day

24 Monday-Thursday

25 Friday

26 Saturday and Sunday

By training this model we are making all the parameters (A and M) shared no matter what client we predict for. To do this we evaluate the log-likelihood, which looks as follows:

L({(ti, di),(tn,dn)}) = YJ MAd(ti)(ti))-

D r T

D r

0

0

(3)

Ad(T)dT - yPII2,

where the 7 is a L2 regularization parameter and 0 = {A, M}. We do it for each of the clients in the training set and then taking the average as a function for maximization. This method brings the possibility to parallelize the learning process well by computing each log-likelihood separately and then just take the average.

But the problem of estimating the parameters in such a way is that it takes much time even if we parallelise it. It takes about ten hours to get the likelihood converged for the data set with the size of 115,000+ clients with 47+ million transactions in total. As it was said earlier, the homogeneous Poisson process intensity function base-rate is just average frequency of clients' purchases, and one can see the only difference between the homogeneous and inhomogeneous one at the Figs. 2a and 2b - the latter one is partly constant on some intervals. So, by that we are coming to another approach to learning of the model - estimate average frequencies on that intervals and as a result we must obtain the same result, as learning via the maximization of the the log-likelihood. To estimate a parameter of the concrete interval,

we must calculate the duration of this interval, combining all non-mutual exclusive time features that are active at the interval.

For example, to estimate the intensity at Friday 2 pm, we calculate the duration of the intersection of the time intervals — all Fridays and all 2 pm wall-clock values and then divide the number of transactions at Friday 2pm by obtained duration value. Formally, we say, that

P>d,14 + 25 + A¿o :

#transactions E {Friday n 2pm}

Sq f FridayC\2pm )d>T

(4)

and if we go in such way with all of non mutual exclusive combinations we get the algebraic system of linear equations, which is consistent. Starting from the pair of (Monday-Thursday, 12 pm) and going down to the last pair (Saturday-Sunday, 11 pm) we obtain the following system of equations:

g { Mon- ThuCil 2pm }

/0T f Mot i-Tfittnl2mp(r

#trc xnsactiot ise{Mon-Thunlam}

So fMor i-Thunlam(T

ransactic >nse{Sat — Sunr\llpm}

Hd, 0 + fid, 24 + AdO fJ>d,l + fid, 24 + AdO

Hd, 23 + fid, 26 + AdO =

JO 'aat-auni inprnv

(5)

where T is the end of the observation period. By solving it we get our vector-parameter M for category d. This approach speeds up learning time significantly — the boost is about 30 times over likelihood maximization, and this opens new opportunities for creating models, which is described in the next sections.

(a)

(b)

time (s)

(c)

Figure 2: Intensity functions for homogeneous Poisson (a), inhomogeneous (b) and Hawkes (c) processes.

While having a pretty big dataset with many transactions for each client we developed a model, where we do not learn the parameters on the whole clients set, but rather we learn them, when we want to make prediction for particular client by using the approach of solving the linear system equation. This means that we are now conditioned on the client's history with inhomogeneous Poisson process.

2.3 Intensity factorization

Since the 3-dimensional matrix (client, category, time) describing the process is highly sparse and many elements are unobserved, we also tried to do the following factorization, laying out the client's preference for certain categories and his schedule:

¡i(client, category, time) = {¿(client, category)-¡¿(client, time)

(6)

As an input for prediction, we take the history as one of the arguments, with the sequences of timestamps and related categories Ht = {(£i, d\),..., (tn, dn)}. To not suffer from the case, when the client has not much statistics on some categories we decided to calculate the parameters that are shared for all categories, but are scaled to their frequencies. Formally, by getting the vector of parameters 0 = {Ao,/^o, ■■■,{*>26}, calculated without relation to the categories; to bring those vectors for all categories separately,

we multiply 9 by

for each category c. By doing

that we obtain the same pattern of purchasing through the time features, which is not the best solution, if we got a relatively big history of every category, but it works well, if the client has not many statistic on the purchasing. The resulting functions for every category are presented in Fig. 3a.

2.4 Intensity smoothing

Here we assume that there is some variation in intensity caused by small statistics for some users. And a person can make a purchase a little earlier or a little later. The logic is this: let's assume that a client has some transactions at 11 a.m., and no transactions at 12 a.m. Therefore, his n(12a.m.) would be zero, which can often be wrong, especially if the customer does not buy a lot. So, we mix the intensities of the adjacent clocks into the intensity of each hour.

Hi

(1 - e) • fa + e

¡J>i-1 + ¡¿i+i 2