Линейная регрессия (англ. linear regression) — метод восстановления зависимости одной (объясняемой, зависимой) переменной [math] y [/math] от другой или нескольких других переменных (факторов, регрессоров, независимых переменных) [math] x [/math] с линейной функцией зависимости. Данный метод позволяет предсказывать значения зависимой переменной [math] y [/math] по значениям независимой переменной [math] x [/math].
Задача
Дано
- [math] f_1(x), \dots ,f_n(x) [/math] - числовые признаки
- модель многомерной линейной регрессии:
[math] f(x,\alpha) = \sum\limits_{j=1}^n \alpha_j f_j(x) [/math],
где [math] a \in R^n [/math]
- обучающая выборка: множество из пар [math](x_i, y_i)_{i=1 \dots n}[/math]
- [math] x_i [/math] - объекты из множества [math] X = R^n [/math]
- [math] y_i [/math] - объекты из множества [math] X = R [/math]
Матричные обозначения
Перейдем к матричным обозначениям:
[math]
\underset{l \times n}{F} =
\begin{pmatrix}
f_1(x_1) & \dots & f_n(x_1) \\
\dots & \dots & \dots \\
f_n(x_1) & \dots & f_n(x_l)
\end{pmatrix}
,
\underset{l \times 1}{y} =
\begin{pmatrix}
y_1 \\
\dots \\
y_l
\end{pmatrix},
\underset{n \times 1}{\alpha} =
\begin{pmatrix}
\alpha_1 \\
\dots \\
\alpha_l
\end{pmatrix}
[/math]
, где
- [math] F [/math] - матрица объектов-признаков, где строки соответствуют объектам а столбцы - признакам
- [math] y [/math] - вектор ответов, или целевой вектор
- [math] \alpha [/math] - вектор коэффициентов
Постановка задачи
В этих трех векторно-матричных обозначениях очень удобно расписать постановку задачи наименьших квадратов:
[math] Q(\alpha, X^l) = \sum\limits_{i=1}^n (f(x_i, \alpha) - y_i)^2 = || F\alpha - y ||^2 \rightarrow \underset{\alpha}{min} [/math]
Необходимо найти вектор [math] \alpha [/math] при известной матрице [math] F [/math] и известном вектор-столбце [math] y [/math].
Решение
Нормальная система уравнений
Запишем необходимые условия минимума в матричном виде.
[math] \frac{\partial Q }{\partial \alpha } (\alpha) = 2F^T (F\alpha - y) = 0 [/math]
Отсюда следует нормальная система задачи МНК:
[math] F^T F \alpha = F^T y [/math],
где [math] F^T F - n \times n [/math] матрица
Мы получили систему уравнений, откуда можем выразить искомый вектор [math] \alpha [/math].
Решение системы
[math] \alpha^* = (F^T F)^{-1} F^T y = F^+ y [/math].
Значение функционала: [math] Q(\alpha^*) = ||P_F y - y||^2 [/math],
где [math] P_F = F F^+ = F (F^T F)^{-1} F^T [/math] - проекционная матрица
Проблемы
В случае мультиколлинеарности (столбцы матрицы [math] F [/math] линейно-зависимы) нам не удастся найти обратную матрицу к [math] F^T F [/math] (она будет вырождена).
Если же столбцы матрицы [math] F [/math] почти линейно-зависимы, то у нас возникнет масса вычислительных проблем с обращением этой матрицы.
Сингулярное разложение
Воспользуемся понятием сингулярного разложения , которое позволяет произвольную прямоугольную матрицу представить в виде произведения трех матриц:
[math] F = V D U^T [/math].
Основные свойства сингулярного разложения:
- [math] l \times n [/math]-матрица [math] V = (v_1, \dots, v_n) [/math] ортогональна, [math] V^T V = I_n [/math],
столбцы [math] v_j [/math] — собственные векторы матрицы [math] F F^T [/math];
- [math] n \times n [/math]-матрица [math] U = (u_1, \dots, u_n) [/math] ортогональна, [math] U^T U = I_n [/math],
столбцы [math] u_j [/math] — собственные векторы матриц [math] F^T F [/math];
- [math] n \times n [/math]-матрица [math] D [/math] диагональна, [math] D = diag(\sqrt{\lambda_1}, \dots, \sqrt{\lambda_n}) [/math],
[math] \lambda_j \geq 0 [/math] — собственные значения матриц [math] F^T F [/math] и [math] F F^T [/math],
[math] \sqrt{ \lambda_j } [/math] — сингулярные числа матрицы [math] F [/math].
Решение МНК через сингулярное разложение
[math] F^+ = (U D V^T V D U^T)^{-1} U D V^T = U D^{-1} V^T = \sum\limits_{j=1}^n \frac{ 1 }{ \sqrt{ \lambda_j } } u_j v_j [/math];
[math] \alpha^* = F^+ y = U D^{-1} V^T y = \sum\limits_{j=1}^n \frac{ 1 }{ \sqrt{ \lambda_j } } u_j (v_j^T y) [/math];
[math] F \alpha^* = P_F y = (V D U^T) U D^{-1} V^T y = V V^T y = \sum\limits_{j=1}^n v_j (v_j^T y) [/math];
[math] || \alpha^* ||^2 = ||D^{-1} V^T y||^2 = \sum\limits_{j=1}^n \frac{ 1 }{ \lambda_j } (v_j^T y)^2 [/math].
