Вариации регрессии

Регрессия (англ. Regression) — метод моделирования зависимости между зависимой переменной [math]y[/math] и одной или несколькими независимыми переменными [math]x_1, x_2, \dots, x_n[/math]. В случае нескольких независимых переменных регрессия называется множественной (англ. multivariate regression). Цель регрессионного анализа состоит в том, чтобы оценить значение непрерывной выходной переменной по значениям входных переменных.

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

Линейная регрессия (англ. linear regression) — разновидность регрессии для моделирования линейной зависимости между зависимой и независимой переменными.

Логистическая регрессия

Логистическая регрессия (англ. logistic regression) — разновидность регрессии для прогнозирования вероятности некоторого события по значениям независимых переменных. Зависимая переменная [math]y[/math] в этом случае принимает значения [math]0[/math] или [math]1[/math] (рассматриваемое событие не произошло или произошло соответственно).

Гребневая регрессия (ридж-регрессия)

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

Мотивация

Определение:

Мультиколлинеарность (англ. multicollinearity) — наличие линейной зависимости между независимыми переменными регрессионной модели. Различают полную коллинеарность и частичную или просто мультиколлинеарность — наличие сильной корреляции между независимыми переменными.

Рассмотрим пример линейной модели: [math]y = b_1 x_1 + b_2 x_2 + b_3 x_3 + \varepsilon[/math]. Пусть имеет место зависимость [math]x_1 = x_2 + x_ 3[/math]. Добавим к первому коэффициенту произвольное число [math]a[/math], а из двух других коэффициентов это же число вычтем. Получаем (без случайной ошибки):

[math]y = (b_1 + a)x_1 + (b_2 - a)x_2 + (b_3 - a)x_3 = b_1 x_1 + b_2 x_2 + b_3 x_3 + a(x_1 - x_2 - x_3) = b_1 x_1 + b_2 x_2 + b_3 x_3[/math]

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

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

Описание

Напомним задачу многомерной линейной регрессии:

Рассматривается линейная зависимость [math]f(x, \beta) = \langle \beta, x \rangle[/math].

Находим вектор [math]\beta^*[/math], при котором достигается минимум среднего квадрата ошибки:

[math]Q(\beta) = ||F \beta - y||^2[/math]

[math]\beta^*=\arg \min\limits_\beta Q(\beta)[/math]

Методом наименьших квадратов находим решение:

[math]\beta^* = (F^T F)^{-1} F^T y[/math]

В условиях мультиколлинеарности матрица [math]F^T F[/math] становится плохо обусловленной.

Для решения этой проблемы наложим ограничение на величину коэффициентов [math]\beta[/math]: [math]||\overrightarrow{\beta}||_2^2 \leq t^2[/math].

Функционал [math]Q[/math] с учетом ограничения принимает вид:

[math]Q_{\lambda}(\beta) = ||F \beta - y||^2 + \lambda ||\beta||^2[/math],

где [math]\lambda[/math] — неотрицательный параметр.

Решением в этом случае будет

[math]\beta^* = (F^T F + \lambda I_n)^{-1} F^T y[/math]

Это изменение увеличивает собственные значения матрицы [math]F^T F[/math], но не изменяет ее собственные вектора. В результате имеем хорошо обусловленную матрицу.

Диагональная матрица [math]\lambda I_n[/math] называется гребнем.

Примеры кода

Пример кода для Scikit-learn

# импорт библиотек
from sklearn.datasets import make_regression
from sklearn.linear_model import Ridge
from sklearn.model_selection import train_test_split

# генерируем данные для X и y
X, y = make_regression(n_samples=10000, noise=100, random_state=0)

# разделение данных на train и test
train_X, test_X, train_y, test_y = train_test_split(X, y, test_size=0.3, random_state=3)

ridge_regression = Ridge(alpha=0.1)  # alpha — величина регуляризации

# обучение
ridge_regression.fit(train_X, train_y)

# предсказание результата
print(ridge_regression.predict(test_X))

# вывод точности предсказания
print(ridge_regression.score(test_X, test_y))

Точность предсказания для данного датасета и параметров:

>>> 0.8171822749108134

Пример на языке Java

Пример гребневой регрессии с применением smile.regression.RidgeRegression

Maven зависимость:

 <dependency>
   <groupId>com.github.haifengl</groupId>
   <artifactId>smile-core</artifactId>
   <version>1.5.2</version>
 </dependency>

 import smile.data.NominalAttribute;
 import smile.data.parser.DelimitedTextParser;
 import smile.regression.RidgeRegression;

 var parser = new DelimitedTextParser();
 parser.setDelimiter(", ");
 parser.setResponseIndex(new NominalAttribute("class"), 0);
 var dataset  = parser.parse("dataset.csv");
 var lambda   = 0.0057d;
 var ridgeClf = new RidgeRegression(dataset.x(), dataset.y(), lambda);
 ridgeClf.predict(testX);

Лассо-регрессия

Рис.1. Сравнение Лассо- и Ридж- регрессии, пример для двумерного пространства независимых переменных.
Бирюзовые области изображают ограничения на коэффициенты [math]\beta[/math], эллипсы — некоторые значения функции наименьшей квадратичной ошибки.

Метод регрессии лассо (англ. LASSO, Least Absolute Shrinkage and Selection Operator) похож на гребневую регрессию, но он использует другое ограничение на коэффициенты [math]\beta[/math]: [math]||\overrightarrow{\beta}||_1 \leq t[/math]

Функционал [math]Q[/math] принимает следующий вид:

[math]Q_{\lambda}(\beta) = ||F \beta - y||^2 + \lambda ||\beta||[/math]

Основное различие лассо- и ридж-регрессии заключается в том, что первая может приводить к обращению некоторых независимых переменных в ноль, тогда как вторая уменьшает их до значений, близких к нулю. Рассмотрим для простоты двумерное пространство независимых переменных. В случае лассо-регрессии органичение на коэффициенты представляет собой ромб ([math]|\beta_1| + |\beta_2| \leq t[/math]), в случае ридж-регрессии — круг ([math]\beta_1^2 + \beta_2^2 \leq t^2[/math]). Необходимо минимизировать функцию ошибки, но при этом соблюсти ограничения на коэффициенты. С геометрической точки зрения задача состоит в том, чтобы найти точку касания линии, отражающей функцию ошибки с фигурой, отражающей ограничения на [math]\beta[/math]. Из рисунка 1 интуитивно понятно, что в случае лассо-регрессии эта точка с большой вероятностью будет находиться на углах ромба, то есть лежать на оси, тогда как в случае ридж-регрессии такое происходит очень редко. Если точка пересечения лежит на оси, один из коэффициентов будет равен нулю, а значит, значение соответствующей независимой переменной не будет учитываться.

Примеры кода

Пример кода для Scikit-learn

# импорт библиотек
from sklearn.datasets import make_regression
from sklearn.linear_model import Lasso
from sklearn.model_selection import train_test_split

# генерируем данные для X и y
X, y = make_regression(n_samples=10000, noise=100, random_state=0)

# разделение данных на train и test
train_X, test_X, train_y, test_y = train_test_split(X, y, test_size=0.3, random_state=3)

lasso_regression = Lasso(alpha=0.1) # alpha — величина регуляризации

# обучение
lasso_regression.fit(train_X, train_y)

# предсказание результата
print(lasso_regression.predict(test_X))

# вывод точности предсказания
print(lasso_regression.score(test_X, test_y))

Точность предсказания для данного датасета и параметров:

>>> 0.8173906804156383

Пример на языке Java

Пример Лассо-регрессии с применением smile.regression.LASSO

Maven зависимость:

 <dependency>
   <groupId>com.github.haifengl</groupId>
   <artifactId>smile-core</artifactId>
   <version>1.5.2</version>
 </dependency>

 import smile.data.NominalAttribute;
 import smile.data.parser.DelimitedTextParser;
 import smile.regression.LASSO;

 var parser = new DelimitedTextParser();
 parser.setDelimiter(", ");
 parser.setResponseIndex(new NominalAttribute("class"), 0);
 var dataset = parser.parse("dataset.csv");
 var lasso   = new LASSO(dataset.x(), dataset.y(), 10);
 lasso.predict(testX);

Байесовская регрессия

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

[math]f(x, \beta) = \langle \beta, x \rangle + \varepsilon[/math], где [math]\varepsilon \sim N(0, \sigma^2)[/math].

Решением этой задачи мы и будем заниматься в этом разделе.

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

Байесовская линейная регрессия (англ. Bayesian linear regression) — подход в линейной регрессии, в котором предполагается что шум распределен нормально.

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

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

Запишем правдоподобие:

[math]p(y|x, \beta, \sigma^2) = N(x \beta, \sigma^2)[/math],

где [math]p(y|x, \beta, \sigma^2)[/math] — плотность распределения значения [math]y[/math] из датасета, которая, как мы ранее предположили, соответствует нормальному распределению с центром в точке [math]x \beta[/math] (значение для [math]y[/math], предсказанное алгоритмом).

Будем также предполагать, что данные независимы:

[math]p(y|x, \beta, \sigma^2) = \prod\limits_{i=1}^n N(x_i \beta, \sigma^2)[/math]

Поскольку нас интересует только максимум, положим [math]\sigma = 1[/math]:

[math]\arg\max p(y|x, \beta) = \arg\max \prod\limits_{i=1}^n N(x_i \beta, 1)[/math]

Прологарифмируем это выражение:

[math]\arg\max \ln p(y|x, \beta) = \arg\max \ln \prod\limits_{i=1}^n N(x_i \beta, 1) \\ = \arg\max \ln {\left( \frac{1}{(\sqrt{2 \pi})^n} \exp{\left(-\frac{1}{2} \sum\limits_{i-1}^n (y_i - x_i \beta)^2\right)}\right )} \\ = \arg\max - \sum\limits_{i=1}^n (y_i - x_i \beta)^2 \\ = \arg\min \sum\limits_{i=1}^n (y_i - x_i \beta)^2[/math]

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

Пример кода для Scikit-learn

# импорт библиотек
from sklearn.datasets import make_regression
from sklearn.linear_model import BayesianRidge
from sklearn.model_selection import train_test_split

# генерируем данные для X и y
X, y = make_regression(n_samples=10000, noise=100, random_state=0)

# разделение данных на train и test
train_X, test_X, train_y, test_y = train_test_split(X, y, test_size=0.3, random_state=3)

bayesian_regression = BayesianRidge()

# обучение
bayesian_regression.fit(train_X, train_y)

# предсказание результата
print(bayesian_regression.predict(test_X))

# вывод точности предсказания
print(bayesian_regression.score(test_X, test_y))

Точность предсказания для данного датасета и параметров:

>>> 0.8170548749907206

Логическая регрессия

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

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

Пусть [math]x_1, x_2, \dots, x_k[/math] — двоичные независимые переменные, и пусть [math]y[/math] — зависимая переменная. Будем пытаться натренировать модели регрессии вида [math]g(E(y)) = b_0 + b_1 L_1 + \dots + b_n L_n[/math], где [math]L_j[/math] — булева функция от переменных [math]x_i[/math] (например [math]L_j = (x_2 \lor \overline{x_4}) \land x_7[/math]). Для каждого типа модели необходимо определить функцию, которая отражает качество рассматриваемой модели. Например, для линейной регрессии такой функцией может быть остаточная сумма квадратов. Целью метода логической регрессии является минимизация выбранной функции качества посредством настройки параметров [math]b_j[/math] одновременно с булевыми выражениями [math]L_j[/math].

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

Может показаться не совсем понятным, как же применить регрессию к булевым выражениям. Рассмотрим в общих чертах алгоритм логической регрессии. Логическая регрессия, как и другие методы регрессии, перебирает различные выражения в попытках минимизировать функцию потерь. Для [math]k[/math] переменных можно составить [math]2^{2^k}[/math] различных выражений. Нужно найти более эффективный метод для поиска наилучшего выражения, чем простой перебор всех вариантов.

Любое логическое выражение можно представить в виде дерева, где в узлах расположены операции, а листья представляют собой переменные. Будем называть такие деревья логическими деревьями (англ. logic trees). Будем называть соседями (англ. neighbours) логического дерева такие деревья, которые могут быть получены из него за один шаг. Допустимые шаги проиллюстрированы на рисунке 3.

Рассмотрим самый простой алгоритм поиска наилучшего дерева — жадный поиск (англ. greedy search).

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

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

См. также

• Общие понятия
• Линейная регрессия
• Логистическая регрессия
• Обзор библиотек для машинного обучения на Python
• Байесовская классификация
• Уменьшение размерности

Источники информации

• 10 типов регрессии — какой выбрать?
• machinelearning.ru — Линейная регрессия (пример)
• machinelearning.ru — Ридж-регрессия
• Лекции по алгоритмам восстановления регрессии К. В. Воронцов
• Ridge and Lasso Regression: A Complete Guide with Python Scikit-Learn
• Habr — Базовые принципы машинного обучения на примере линейной регрессии
• Documents on Logic Regression

Smile, Ridge Regression

Smile, LASSO regression