Гребневая регрессия (Ridge regression)

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

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

Решается задача регрессии. Применяется линейная модель (вообще говоря, один из признаков полагается константным для того, чтобы аппроксимирующая гиперплоскость не обязательно проходила через нуль, я не знаю, почему это практически всюду опускается): $f(x, \beta) = \langle\beta, x\rangle$. В изначальной постановке полагается, что вектор $\beta$ находится методом Обычных Наименьших Квадратов (ОНК): $\sum_{n = 1}^{N} (f(x_n, \beta) - y_n)^2 \longrightarrow \min_{\displaystyle \beta}$

Аналитическое решение данной задачи: $\beta^{*} = (X^TX)^{-1}X^TY$, однако при вырожденности матрицы $X^TX$ решение оказывается не единственным, а при ее плохой обусловленности — неустойчивым. Поэтому целесообразно ввести регуляризацию по параметру $\beta$, например, $L_2$.

Таким образом, приходим к следующей задаче минимизации (гребневая (ridge) регрессия):

$Q(\beta)= \left \| Y - X\beta \right \|^2 + \lambda\left \|\beta \right \|^2 \longrightarrow \min_{\displaystyle \beta}$

где $\left \|\beta \right \|^2 =\sum^{D}_{i=1} {\beta_i}^2,$ $\lambda$ — параметр регуляризации(неотрицательное число).

Вывод оптимальных весов

Для нахождения оптимальных весов продифференцируем функционал по $\beta$ и приравняем к 0:$\frac{\partial Q}{\partial \beta} = 2X^{T}(X\beta - Y) + 2\lambda\beta = 0$

$(X^{T}X + \lambda I)\beta = X^{T}Y$

$\beta^{*} =(X^{T}X + \lambda I)^{-1} X^{T}Y$ При увеличении параметра $\lambda$ решение становится более устойчивым, но с другой стороны — смещенным. При уменьшении — приходим к задаче ОНК без регуляризации: имеем шанс переобучиться. Поэтому нужно искать что-то посерединке.

Обобщение через ядра

Решение прямой (см. выше) задачи, как уже было получено: $\beta^{*} =(X^{T}X + \lambda I)^{-1} X^{T}Y$. Заметим, что в силу неотрицательной определенности матрицы $X^TX$ матрица $X^{T}X + \lambda I$ вообще положительно определена, поэтому прямое решение всегда существует и единственно. Сложность обучения: $O(D^2(N+D))$, сложность предсказания: $O(D)$.

Введем двойственные переменные. Для этого решим двойственную задачу, где решение прямой задачи будет представлено в виде некоторой линейной комбинации векторов обучающей выборки. Из условий стационарности $X^T(X\beta - Y) + \lambda \beta = 0$ следует $\beta = \frac{1}{\lambda}X^T(Y - X\beta) = X^T\alpha$, где вектор $\alpha = \frac{1}{\lambda}(Y - X\beta)$ — вектор двойственных переменных. Формула для предсказания: $\hat{y}(x) = x^T\beta = x^TX^T\alpha = \sum_{i=1}^N \alpha_i \langle x, x_i\rangle$. Найти двойственные переменные можно следующим образом: $\alpha = (XX^T + \lambda I)^{-1}Y$ . Это прямо следует из $\alpha = \frac{1}{\lambda}(Y - X\beta)$ при подстановке $\beta = X^T\alpha$. Сложность обучения: $O(N^2(D+N))$, сложность предсказания: $O(ND)$.

Заметим, что для нахождения двойственных переменных и предсказания по ним требуются лишь скалярные произведения векторов обучающей выборки, но тогда, используя общую парадигму ядерных обобщений методов, мы можем заменить скалярные произведения $\langle x, x' \rangle$ везде выше на ядерную функцию $K(x, x')$, получив следующие формулы: $\alpha = (G + \lambda I)^{-1}Y$, где $\{G\}_{i,j} = K(x_i, x_j)$ — матрица Грама, $\hat{y}(x) = \sum_{i=1}^N \alpha_i K(x, x_i)$ . Таким образом, решая задачу линейной регрессии можно получать нелинейные решения.