Разработка и сравнение методов сведения задачи оценки эффекта от воздействия к задаче регрессии

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Пермский филиал федерального государственного автономного образовательного учреждения высшего образования «Национальный исследовательский университет «Высшая школа экономики»

Факультет экономики, менеджмента и бизнес-информатики

РАЗРАБОТКА И СРАВНЕНИЕ МЕТОДОВ СВЕДЕНИЯ ЗАДАЧИ ОЦЕНКИ ЭФФЕКТА ОТ ВОЗДЕЙСТВИЯ К ЗАДАЧЕ РЕГРЕССИИ

Выпускная квалификационная работа

по направлению подготовки 38.04.05 «Бизнес-информатика»

образовательная программа «Информационная аналитика в управлении предприятием»

Кучумов Артем Ильдусович

Пермь, 2019 год



Аннотация

воздействие эффект оценка регрессия

Автор работы - Кучумов Артем Ильдусович, студент 2 курса группы ИАУП-17-1 НИУ ВШЭ-Пермь. Тема работы - разработка и сравнение методов сведения задачи оценки эффекта от воздействия к задаче регрессии

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



Оглавление

Аннотация

Введение

Глава 1. Обзор семейств методов оценки эффекта от воздействия

1.1 Задача оценки эффекта от воздействия

1.2 Методы сведения к задаче регрессии

1.2.1 Методы выделения переменной

1.2.2 Методы трансформации

1.3. Прямое вычисление оценки

1.3.1 Методы, основанные на деревьях

1.3.2 Ансамблевые методы

1.4 Выводы

Глава 2. Методы решения задачи регрессии

2.1 Линейная регрессия

2.2 Метод опорных векторов

2.3 Деревья решений

2.4 Случайный лес

2.5 Градиентный бустинг

Глава 3. Программная реализация библиотеки pyuplift

3.1 Диаграмма пакетов

3.2 Диаграммы классов

Глава 4. Тестирование разработанных методов

4.1 Оценка качества моделей

4.1.1 Средний эффект от воздействия

4.1.2 Стандартные методы машинного обучения

4.2 Набор синтетических данных

4.2.1 Описание данных

4.2.2 Результаты сравнения

4.3 Набор данных Hillstrom Email Marketing

4.3.1 Преобразование данных

4.3.2 Результаты сравнения

4.4 Выводы

Заключение

Список источников

Приложение A. Исходный код вычисления предсказательной точности модели на синтетическом наборе данных

Приложение B. Исходный код вычисления эффектов от воздействия рекламы мужских товаров

Приложение C. Исходный код вычисления эффектов от воздействия рекламы женских товаров



Введение

Каждый год крупные компании тратят большие суммы денег на маркетинговые исследования. Согласно исследованиям компании «Gartner» https://www.gartner.com/marketing/research/the-2018-2019-cmo-spend-survey-spotlight.html, в среднем компании тратят около 11% годового дохода на маркетинг. Так компании, которые имеют доход более 10 миллиардов долларов в год, в среднем тратят 11.6% своего годового дохода на маркетинг, а компании, чей годовой доход находится между 500 миллионами и 1 миллиардом долларов тратят на маркетинг около 8.5% своего годового дохода. Некоторые маркетинговые исследования оправдывают вложения, а некоторые нет. Поэтому подготавливая очередную маркетинговую кампанию хотелось бы иметь возможность оценить её возможную эффективность. Подобно маркетингу в других сферах деятельности есть похожие задачи, которые требуют априорной оценки, например, какую выручку принесет задуманная акция в некоторой телекоммуникационной компании или сети ресторанов. Подобного рода задачи можно объединить под одним название - задача оценки эффекта от воздействия.

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

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

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

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

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

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

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

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

Рассмотреть методы решения задачи регрессии.

Линейная регрессия;

Метод опорных векторов;

Деревья решений;

Случайный лес;

Градиентный бустинг.

Реализовать методы сведения задачи оценки эффекта от воздействия к задаче регрессии.

Метод двух моделей;

Воздействие как признак;

Эконометрический метод;

Кадит моделирование;

Метод Лаи (с использованием весов и без);

Метод Кейна (с использованием весов и без);

Рефлективный метод;

Пессимистичный метод;

Метод Джасковски.

Провести тестирование реализованных методов на синтетических и реальных наборах данных.

Сделать выводы о проделанной работе.



Глава 1. Обзор семейств методов оценки эффекта от воздействия

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

Простота реализации.

Разработанность предлагаемых методов.

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

1.1. Задача оценки эффекта от воздействия

Начнем с того, что опишем задачу эффекта от воздействия. Есть некоторый эксперимент, в рамках которого проводится ряд наблюдений. Каждое наблюдение характеризуется некоторым набором признаков (обозначим его - X), которые обычно представлены в виде матрицы. Также каждое наблюдение имеет некоторый исход (обозначим его - Y), который обычно представляется в виде вектора. Во время наблюдения на испытуемых может быть оказано некоторое воздействие (обозначим его - T), которое обычно представляется в виде вектора. В данной работе для простоты понимания воздействие будет принимать два значения: 1 и 0. 1 - воздействие было оказано и 0 - воздействие не было оказано. В сложных экспериментах, воздействие может принимать любые значения.

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

1.2 Методы сведения к задаче регрессии

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

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

1.2.1 Методы выделения переменной

1.2.1.1 Метод двух моделей

Начнем с метода, который был исторически первым. Метод двух моделей [6]. Метод двух моделей использует две независимых модели решения задачи регрессии, которые используются для предсказания эффекта от воздействия. Подробно опишем алгоритм работы метода двух моделей. На первом шаге исходная выборка данных делится на две подвыборки. Деление исходной выборки происходит по значениям переменной воздействия Т. Первая подвыборка - это данные наблюдений, в которых было оказанное некоторое воздействие (т.е. воздействие не равно нулю). Вторая подвыборка - это данные наблюдений, в которых не оказывалось воздействие (т.е. воздействие равно нулю).

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

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

Алгоритм 1.1. Обучение метода двух моделей

X_с_возд := получить_Х_с_воздействием(X, Y, T) Y_с_возд := получить_Y_с_воздействием(X, Y, T) X_без_возд := получить_Х_без_воздействия(X, Y, T) Y_без_возд := получить_Y_без_воздействия(X, Y, T) модель_с_возд := построить_модель(X_с_возд, Y_с_возд) модель_без_возд := построить_модель(X_без_возд, Y_без_возд)

Алгоритм 1.2. Предсказание эффекта методом двух моделей

эффект_с_возд := предсказать_эффект(модель_с_возд, Xтест) эффект_без_возд := предсказать_эффект(модель_без_возд, Xтест) эффект_от_возд := эффект_с_возд - эффект_без_возд

Данный метод показывает отличные результаты на простых данных [7, 8], но если применить его к сложным данным, то результаты получаются далекими от идеального. В своей работе Рекдлиф и Сюрри [9] подробно разбирают причины, почему алгоритм работает плохо на данных, которые имеют сложные зависимости.

1.2.1.2 Воздействие как признак

Следующий метод, который мы рассмотрим называется воздействие как признак [10]. В данном методе мы используем воздействие как обычный признак, который, в нашем случае, может принимать два значения: 1 - если воздействие было и 0 - если воздействия не было. Подробно опишем алгоритм работы метода.

На первом шаге подготавливаем расширенную матрицу. Расширенная матрица получается путем добавления столбца с воздействием T к исходной матрице признаков Х. Далее обучаем модель решения задачи регрессии на расширенной обучающей выборке данных .

На следующем шаге вычислим эффект от воздействия. Для этого, необходимо взять расширенную тестовую выборку данных и заменить значение воздействия в каждом наблюдении на единицы и предсказать, с помощью обученной модели, некоторое значение v1. В данном случае, мы получаем значение, которое получилось бы, если на пользователя было оказано воздействие. Далее, возьмем ту же самую расширенную тестовую выборку данных и заменим значение воздействия в каждом наблюдении на нуль и предскажем, с помощью обученной модели, некоторое значение v2. Значение v2 - это значение, которое получилось бы, если на пользователя не было оказано воздействие. Разность вычисленных значений v1 и v2 будет являться эффектом от воздействия. Алг. 1.3 на псевдокоде описывает алгоритм построения регрессионной модели. Алг. 1.4 на псевдокоде описывает предсказание эффекта от воздействия.

Алгоритм 1.3. Обучение метода воздействие как признак

:= добавить_столбец(X, T) модель := обучить_модель(модель, , Y)

Алгоритм 1.4. Предсказание эффекта методом воздействие как признак

столбец := создать_столбец(1, количество_строк(Х)) := добавить_столбец(X, столбец) эффект_с_возд := предсказать_эффект(модель, ) столбец := создать_столбец(0, количество_строк(Х)) := добавить_столбец(X, столбец) эффект_без_возд := предсказать_эффект(модель, ) эффект_от_возд := эффект_с_возд - эффект_без_возд

1.2.1.3 Эконометрический метод

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

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

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

Алгоритм 1.5. Обучение эконометрического метода

:= получить_матрицу_спец_вида(X, T) модель := обучить_модель(модель, , Y)

Алгоритм 1.6. Предсказание эффекта эконометрическим методом

столбец := создать_столбец(1, количество_строк(Х)) := получить_матрицу_спец_вида (X, столбец) эффект_с_возд := предсказать_эффект(модель, ) столбец := создать_столбец(0, количество_строк(Х)) := получить_матрицу_спец_вида (X, столбец) эффект_без_возд := предсказать_эффект(модель, ) эффект_от_возд := эффект_с_возд - эффект_без_возд

1.2.1.4 Кадит моделирование

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

где

- это вероятность того, что наблюдение подверглось воздействию.

- это вероятность того, что наблюдение не подвергалось воздействию.

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

1.2.2 Методы трансформации

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

Начнем с того, что выделим категории, к которым может относится клиент. Назовем первую категорию CR - постоянные клиенты. Данная категория людей периодически пользуется предоставляемой услугой. Если попытаться воздействовать на таких людей, то результата останется прежним.

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

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

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

1.2.2.1 Метод Лаи

В своей работе Лаи [18] предлагает формулу вычисления эффекта от воздействия, исходя из следующих соображений. Представители второй CN и третьей TN категорий считаются положительными целями т.к. в сумме они содержат людей, на которых нужно воздействовать (т.е. эффект от воздействия будет положительным). Первая CR и четвертая TR категории относятся к нежелательным целям т.к. оказывая влияние на них мы либо получим нулевой, либо отрицательный эффект. Эффект от воздействия будет вычисляться по следующей формуле:

где

- это вероятность того, что наблюдение х принадлежит к второй CN или третьей TN категории.

- это вероятность того, что наблюдение х принадлежит к четвертой TN или первой CR категории.

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

где

- это вероятность того, что наблюдение х принадлежит к второй CN или третьей TN категории.

- это вероятность того, что наблюдение х принадлежит к четвертой TN или первой CR категории.

- это доля наблюдений в обучающей выборке, которые принадлежат к второй CN или третьей TN категории.

- это доля наблюдений в обучающей выборке, которые принадлежат к четвертой TR или первой CR категории.

1.2.2.2 Метод Кейна

Альтернативой метода Лаи служит метод Кейна. В своей работе [21] Кейн предложил обобщенный метод Лаи. Идея метода остается прежней разница лишь в формуле. Формула метода Кейна выглядит следующим образом:

где

- это вероятность того, что наблюдение х принадлежит к четвертой TR категории.

- это вероятность того, что наблюдение х принадлежит ко второй CN категории.

- это вероятность того, что наблюдение х принадлежит к третьей TN категории.

- это вероятность того, что наблюдение х принадлежит к первой CR категории.

Позже, по аналогии с методом Лаи, был предложен взвешенный метод Кейна, формула которого выглядит следующим образом:

где

- имеют те же значения, что и в предыдущей формуле.

- это доля наблюдений в обучающей выборке, на которых было оказано воздействием.

- это доля наблюдений в обучающей выборке, на которых не было оказано воздействие.

1.2.2.3 Рефлективный метод

Следующей метод, который будет рассмотрен, называется рефлективный метод [19]. Рефлективный метод напоминает метод двух моделей, который был описан ранее, т.к. также использует две модели для предсказаний. Первая модель Mr предсказывает наблюдения, эффект от воздействия, на которых будет. Вторая модель Mn предсказывает наблюдения, эффект от воздействия, на которых не будет. Формулы для вычисления рефлективного метода выглядят следующим образом:

где

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

- это вероятность того, что наблюдение х принадлежит к четвертой TR категории.

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

- это вероятность того, что наблюдение х принадлежит ко второй CN категории.

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

- это вероятность того, что наблюдение х принадлежит к третьей TN категории.

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

- это вероятность того, что наблюдение х принадлежит к первой CR категории.

1.2.2.4 Пессимистичный метод

Пессимистичный метод [19] использует взвешенный метод Лаи и рефлективный метод. Данная комбинация дает более точный и устойчивый метод. Формула пессимистичного метода выглядит следующим образом:

где

- это предсказанный эффект от воздействия взвешенным методом Лаи для наблюдения х.

- это предсказанный эффект от воздействия рефлективным методом для наблюдения х.

1.2.2.5 Метод Джасковски

Последний метод, который мы рассмотрим - это Джасковски [20] метод. В рамках метода Джасковски вводиться новая переменная, которая может принимать только два значения: 0 и 1. Новая переменная будет равна 1, если во время наблюдения было оказано воздействие и это воздействие дало некоторый эффект или если не было оказано воздействие и эффект оказался нулевым, в остальных случаях 0. Таким образом, значение 1 считает позитивным исходом, 0 - негативным. Формулу трансформации можно записать следующим образом:

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

где

- это вероятность того, что наблюдение х принимает значение Z=1.

1.3 Прямое вычисление оценки

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

1.3.1 Методы, основанные на деревьях

Начнем с методов, которые основаны на деревьях решений. Большинство методов, данной категории алгоритмов, адаптируют хорошо известные алгоритмы построения деревьев решений, такие как CART [11], C4.5 [12] и CHAID [13]. Так же, как и в классических деревьях решений, в данных алгоритмах присутствуют некоторые критерии разбиения вершин и метод сокращения длины дерева (прунинг).

1.3.1.1 Метод Редклифа и Сарри

Начнем с метода [22], который, для построения деревьев решений, может использовать CART или C4.5 алгоритм. Данный метод итеративно строит дерево до тех пор, пока не встретит критерий остановки. Критерии остановки бывают разные. Самые популярные из них это глубина дерева, количество элементов в вершине и точность предсказания получившегося дерева. При построении дерева, на каждом шаге происходит разбиение вершины по некоторому критерию. Опишем один из них. Согласно критерию, необходимо максимизировать разницу между дочерними узлами и минимизировать разницу в размере между дочерними узлами, чтобы получить лучшее разбиение. Второй критерий основан на значимости разбиения. Вершина дерева разбивается случайным образом и вычисляется эффект от воздействия для получившегося дерева. Далее вычисляется эффект от воздействия на простой модели, например, на линейной регрессии. На последнем шаге, с помощью Т-критерия Стьюдента, оценивается качество разбиения.

1.3.1.2 Метод Хансотии и Ракстэйлса

Хансотия и Ракстэйлс [7, 23] предложили метод, который основан на методе двух моделей, который был описан ранее. Но, как уже говорилось раньше, метод двух моделей работает не лучшим образом. Хансотия и Ракстэйлс решили улучшить данный метод используя CHAID-подобный алгоритм построения деревьев решений. На каждом шаге, мы максимизируем разницу эффекта между дочерними вершинами. В сравнении с предыдущим методом, данный метод значительно проще и менее изысканный.

1.3.2 Ансамблевые методы

Далее рассмотрим ансамблевые методы. Ансамблевые методы были предложены относительно недавно [9, 14, 15]. В своей работе Рекдлиф и Сюрри [9] предлагает адоптированный bagging meta learning подход [16], с целью улучшения стабильности работы результирующей модели, а также усиление обобщающих свойств модели.

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

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

1.4 Выводы

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

Таблица 1.1 Результаты сравнения семейств методов оценки эффекта от воздействия

	Простота реализации	Проработанность предлагаемых методов
Сведение задачи оценки эффекта от воздействия к задаче регрессии	+	+
Прямое вычисление оценки	-	±



Глава 2. Методы решения задачи регрессии

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

2.1 Линейная регрессия

Начнем с самого базового метода - линейная регрессия. Линейная регрессия - это метод аппроксимации линейной зависимости между входными и выходными переменными https://wiki.loginom.ru/articles/linear-regression.html. Результатом аппроксимации является некоторое вещественное число. В самом простом случае, связь ищется между одной входной и одной выходной переменными. Такую регрессию можно назвать простой, а формула её будет выглядеть следующим образом:

y = ax + b

где

a и b - вещественные числа.

х - входная переменная.

y - выходная переменная.

Значение a и b являются параметрами и находятся с помощью минимизации функции потерь. В качестве функции потерь, чаще всего, используется метод наименьших квадратов.

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

y = b0 + b1x1 + b2x2 + … + bnxn,

где

n - количество параметров.

bi - i-й коэффициент модели.

хi - i-я входная переменная.

Значения параметров bi находятся с помощью тех же методов, что и в случае простой регрессии.

К достоинствам линейной регрессии можно отнести:

Скорость и простота получения модели.

Хорошо изученный подход.

Интерпретируемость модели.

Существует много процессов, которые хорошо описываются линейной регрессией.

К недостаткам линейной регрессии можно отнести:

Неспособна описать сложные нелинейные зависимости.

Отсутствие каких-либо гарантий точности. Модель может хорошо работать на одном наборе данных и ужасно на другом наборе.



2.2 Метод опорных векторов

Метод опорных векторов (Support Vector Machines) - это очень мощная и универсальная модель машинного обучения, способная выполнять линейную или нелинейную классификацию, регрессию и даже выявлять выбросы [25]. Каждый объект данных можно представить в виде вектора в N-мерном пространстве. Если говорить про задачу классификации, то метод опорных векторов переводит данные в более высокую размерность и находит такую гиперплоскость, которая оптимальным образом разбивает данные на несколько классов. Оптимальным называется такое разбиение, которое дает наибольшее расстояние между гиперплоскостями.

Задача регрессии немного отличается и заключается в инвертировании цели: вместо попытки приспособиться к самой широкой из возможных полосе между двумя классами, одновременно ограничивая нарушения зазора, регрессия SVM пробует уместить как можно больше образцов на полосе наряду с ограничением нарушений зазора (т.е. образцов вне полосы). Ширина полосы управляется гиперпараметром [25].

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

К достоинствам метода опорных вектором можно отнести следующее:

Наличие регуляризации, которая позволяет бороться с переобучением модели.

Если решение имеется, то оно единственное. Как следствие, более эффективная работа алгоритмов оптимизации.

К недостаткам можно отнести:

Метод опорных векторов неустойчив по отношению к шуму в исходных данных.

Долго обучается на больших объемах данных.

Тяжело понять и интерпретировать получившуюся модель.

Тяжело подобрать разделительную функцию.

2.3 Деревья решений

Деревья решений - метод машинного обучения, который представляет собой древовидную структуру в листьях которой находятся значения, а в остальных узлах - условия перехода https:// dyakonov.org/2018/07/30/байесовский-подход. Деревья решений позволяют решать задачи классификации и регрессии.

Рис. 2.1. Пример дерева решений

На рис. 2.1 приведен пример дерева решения предсказания стоимости дома на наборе данных «The Boston Housing Dataset https://www.cs.toronto.edu/~delve/data/boston/bostonDetail.html». Узлы дерева содержат условия перехода, листья - значения целевой функции (в нашем случае это стоимость дома). Для построения деревьев решений используются следующие алгоритмы: ID3, C4.5, CART и другие.

К достоинствам можно отнести следующее:

Деревья решений просты для понимания, интерпретации и визуализации.

Быстрое построение.

Возможность работы как с категориальными признаками, так и с интервальными.

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

К недостаткам можно отнести:

Часто может найти только локальный минимум.

Подверженность к переобучению.

2.4 Случайный лес

Случайный лес - алгоритм машинного обучения, который для предсказания использует ансамбль решающих деревьев [17]. Ансамблирование - это построение множества моделей и усреднение их результатов с помощью некоторого метода https://habr.com/ru/post/116385.

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

К достоинствам можно отнести следующее:

Нечувствителен к монотонным преобразованиям значений признаков.

Универсальный. Дает хорошие результаты на большом количестве задач.

Оценка важности признаков.

Легко масштабируется и распараллеливается.

Отличные результаты при работе с большими размерностями.

К недостаткам можно отнести:

Размер результирующей модели. Для использования случайного леса требуется хранить в памяти N деревьев.

Склонен к переобучению в случае зашумленных данных.

Сложно интерпретировать полученную модели.

2.5 Градиентный бустинг

Градиентный бустинг - алгоритм машинного обучения, который использует ансамблирование слабых предсказывающих деревьев решений [26]. Алгоритм построения такого ансамбля выглядит следующим образом. На первом шаге происходит построение некоторого дерева решений. Затем считается разность между предсказанием построенного дерева умноженного на скорость обучения (в английском языке это называется learning rate) и реальным значением. По полученной разнице строиться следующее дерево. Построение происходит до тех пор, пока ошибка не станет уменьшаться. Известные реализации градиентного бустинга:

XGBoost https://xgboost.readthedocs.io;

CatBoost https://catboost.ai (от Яндекса);

LightGBM https://lightgbm.readthedocs.io (от Microsoft).

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

К достоинствам можно отнести следующее:

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

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

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

К недостаткам можно отнести:

Тяжело распараллеливается.

Слабая устойчивость к переобучению.

Тяжело интерпретировать полученную модель.



Глава 3. Программная реализация библиотеки pyuplift

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

Разработанная библиотека должна включать:

Рассмотренные методы оценки эффекта от воздействия.

Метод вычисления среднего эффекта от воздействия.

Генератор синтетических данных.

Набор вспомогательных утилит.

3.1 Диаграмма пакетов

На рис. 3.1 представлена диаграмма пакетов. Корнем библиотеки является пакет «pyuplift», который содержит базовый, для всех моделей вычисления эффекта от воздействия, класс «BaseModel» (файл base.py). Также данный пакет содержит 6 подпакетов:

«transformation»;

«variable_selection»;

«datasets»;

«metrics»;

«model_selection»;

«utils».

Пакет «transformation» содержит набор классов, которые представляют собой реализацию группы методов трансформации данных. Базовом классом для всех методов трансформации данных является класс «TransformationBaseModel» (файл base.py). К методам трансформации данных относятся:

Метод Лаи (файл lai.py);

Метод Кейна (файл kane.py);

Метод Джасковски (файл jaskowski.py);

Рефлективный метод (файл reflective.py);

Пессимистичный метод (файл pessimistic.py).

Рис. 3.1 Диаграмма пакетов библиотеки pyuplift

Пакет «variable_selection» содержит набор классов, которые представляют собой реализацию группы методов выделения переменной. К представителям данной группы относятся:

Метод кадит моделирования (файл cadit.py);

Метод воздействие как признак (файл dummy.py);

Эконометрический метод (файл econometric.py);

Метод двух моделей (файл two_model.py).

Пакет «datasets» содержит утилиты для загрузки подготовленных ранее наборов данных. На данный момент доступно два набора данных: Criteo Uplift Prediction (файл criteo_uplift_prediction.py), Hillstrom Email Marketing (файл hillstrom_email_marketing.py) и один генератор синтетических данных (файл linear.py).

Пакет «metrics» содержит метрики оценки качества предсказанных результатов. В данной реализации доступна только метрика оценки среднего эффекта от воздействия (файл average_effect.py).

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

Пакет «utils» содержит утилиты, которые используются в других пакетах, например, утилита для разархивирования файлов (файл retriever.py) или утилита для скачивания данных из удаленных источников данных (файл downloader.py).

3.2 Диаграммы классов

На рис. 3.2 представлена диаграмма классов для группы методов выделения переменной. Вершинной в иерархии классов является абстрактный класс «BaseModel». Данный класс является родителем для всех классов, которые вычисляют оценку эффекта от воздействия. Класс «BaseModel» имеет два абстрактных метода «fit» и «predict». Метод «fit» предназначен для построения модели машинного обучения. Метод «predict» предназначен для предсказания результата на обученной модели. От класса «BaseModel» наследуются три класса: «Dummy», «Econometric» и «TwoModel», которые реализуют метод воздействие как признак, эконометрический метод и метод двух моделей соответственно.

Рис. 3.2 Диаграмма классов методов выделения переменной

Класс «Dummy» реализует два метода: «fit» и «predict», а также, в качестве атрибута, содержит модель для решения задачи регрессии «model». Класс «Cadit» реализует два публичных метода «fit» и «predict» и один приватный метод - «__get_z_values», а также в качестве атрибута содержит модель для решения задачи регрессии «model». Класс «Econometric» имеет похожу структуру, что и класс «Dummy». Отличие заключается в том, что класс «Econometric» содержит приватный метод «__get_matrix», который преобразует исходные данные к необходимому для использования виду. Класс «TwoModel» реализует методы «fit» и «predict», а также содержит две модели для решения задачи регрессии: «no_treatment_model» и «has_treatment_model».

На рис. 3.3. представлена диаграмма классов для группы методов трансформации. Для выделения общей логики был создан абстрактный класс «TransformationBaseModel», который является наследником «BaseModel» класса. Класс «TransformationBaseModel» содержит четыре метода: «is_tr», «is_tn», «is_cr», «is_cn», которые проверяют, принадлежит ли наблюдение к категории TR, TN, CR, CN соответственно.

Класс «Kane» содержит четыре атрибута:

«model» - классификационная модель.

«use_weights» - индикатор, который регулирует использование весов.

«control_count» - количество элементов в тренировочной выборке, которые относятся к контрольной группе.

«treatment_count» - количество элементов в тренировочной выборке, которые относятся к группе воздействия.

Помимо этого, данный класс реализует методы «fit» и «predict» и два приватных метода: «__encode_data», «__init_weights». В данном классе, и во всех последующих, метод «__encode_data» преобразует данные к необходимому формату. Метод «__init_weights» инициализирует атрибуты «control_count» и «treatment_count» в случае, если атрибут «use_weights» принимает значение «True».

Рис. 3.3 Диаграмма классов методов трансформации

Класс «Lai» содержит четыре атрибута: «model», «use_weights», «p_tr_or_cn» и «p_tn_or_cr». Атрибуты «model» и «use_weights» имеют такое же предназначение, что и в классе «Kane». Остальные два атрибута представляют собой веса. Помимо этого, класс содержит четыре метода: «fit», «predict», «__encode_data» и «__init_weights».

Класс «Reflective» содержит пять атрибутов: классификационная модель «model» и четыре веса «p_tlr», «p_clr», «p_cln», «p_tln». Помимо этого, класс содержит четыре метода: «fit», «predict», «__encode_data» и «__init_weights».

Класс «Jaskowski» содержит один атрибут «model» и три метода: «fit», «predict» и «__encode_data». Класс «Pessimistic» содержит два атрибута «w_lai_model» и «reflective_model», которые представляют собой экземпляр класса «Lai» с параметров «use_weights» равным «True» и экземпляр класса «Reflective». Помимо этого, класс содержит четыре метода: «fit», «predict»



Глава 4. Тестирование разработанных методов

Тестирование проводиться на двух наборах данных: синтетический набор и набор данных Hillstrom Email Marketing https://blog.minethatdata.com/2008/03/minethatdata-e-mail-analytics-and-data.html. В тестировании будут участвовать следующие методы оценки эффекта от воздействия:

Эконометрический метод;

Воздействие как признак;

Метод двух моделей;

Кадит моделирование;

Метод Лаи (с весами и без);

Метод Кейна (с весами и без);

Рефлективный метод;

Пессимистичный метод;

Метод Джасковски.

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

Далее в работе будет использовать понятие модели, поэтому введем понятие модели. Модель - это определенная сущность, которая состоит из метода оценки эффекта от воздействия и метода решения задачи регрессии (классификации).



4.1 Оценка качества моделей

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

4.1.1 Средний эффект от воздействия

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

Предсказываем эффект от воздействия на тестовом наборе данных для каждого наблюдения.

Упорядочиваем наблюдения тестового набора данных по предсказанному эффекту.

Берем первые N% процентов (в нашем случае N=30) наблюдений из отсортированного набора данных.

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

Вычитаем среднее значение с воздействием из среднего значения без воздействия.

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



4.1.2 Стандартные методы машинного обучения

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

Предсказываем эффект от воздействия на тестовом наборе данных для каждого наблюдения.

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

В качестве функции оценки качества модели можно использоваться такие популярные функции, как RMSE (Root Mean Square Error), Mean Absolute Error (MAE) или определить свою функцию ошибки. Главным недостатком стандартных методов оценки качества является то, что их можно применять только в случае, когда заранее известен эффект от воздействия.

4.2 Набор синтетических данных

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

Тестирование моделей будет проходить на трех наборах данных с различным уровнем шума. В качестве метрики предсказательной точности моделей будет использоваться RMSE. Данный способ тестирования позволит понять поведение моделей в зависимости от уровня шума в данных. Алгоритм тестирования будет выглядеть следующим образом:

Сгенерировать набор данных с определенным уровнем шума.

100 раз повторить следующие шаги:

Случайным образом разделить сгенерированный набор данных на обучающую и тестовую выборки данных.

Для каждой тестируемой модели проделать следующие шаги:

Обучить модель на обучающей выборке данных.

Предсказать эффект от воздействия на тестовой выборке данных.

Вычислить качество модели используя метрику RMSE.

Исходный код тестирования синтетических данных находится в приложении А.

4.2.1 Описание данных

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

где

X1 - значения, полученные из нормального распределения с математическим ожиданием равным 0 и среднеквадратичным отклонением равным 1.

X2 - значения, полученные из нормального распределения с математическим ожиданием равным 0 и среднеквадратичным отклонением равным 0.1.

X3 - значения, полученные из нормального распределения с математическим ожиданием равным 0 и среднеквадратичным отклонением равным 1.

E - шум в данных, полученный из нормального распределения с математическим ожиданием равным 0 и среднеквадратичным отклонением равным 0, 0.1 и 1.

T - воздействия, полученные из равномерного распределения. 0 - отсутствие воздействия. 1 - наличие воздействия.

- промежуточные значения функции.

Генерация целевой функции будет производиться по следующей формуле:

где

eps - граничное значение, которое равно 0.01.

Y - значения целевой функции.

На рис. 4.1 представлены примеры сгенерированных наблюдений.

Рис. 4.1. Пример сгенерированных данных

На рис. 4.2. представлено распределение значений Y. Как можно заметить, большая часть значений равны нулю (более 50%). Такой эффект получен намеренно т.к. в реальных данных процент нулевых значений может достигать 95 и более.

Рис. 4.2. Распределение значений функции

4.2.2 Результаты сравнения

На рис. 4.3 представлены распределения (посредством «ящиков с усами») значений RMSE метрики на синтетическом наборе данных с шумом равным 0. Как можно заметить, только четыре модели показывают слабые результаты. К ним относятся:

Метод Лаи (случайный лес);

Метод Джасковски (случайный лес);

Метод Кейна (случайный лес);

Метод кадит моделирования (случайный лес).

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

Рис. 4.3. RMSE на синтетическом наборе данных и шумом равным 0

На рис. 4.4 представлены распределения значений RMSE метрики на синтетическом наборе данных с шумом равным 0.1. Как можно заметить, добавление небольшого шума не сильно изменило результаты по сравнению с предыдущим тестом.

Рис. 4.4. RMSE на синтетическом наборе данных и шумом равным 0.1

На рис. 4.5 представлены распределения значений RMSE метрики на синтетическом наборе данных с шумом равным 1. Добавление шума существенно отразилось на качестве предсказаний трех моделей:

Эконометрический метод (случайный лес);

Метод двух моделей (случайный лес);

Метод кадит моделирования (случайный лес);

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

...