Викиконспекты - Вклад участника [ru]

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

2019-03-11T15:30:58Z

217.66.156.131: Решение МНК через сингулярное разложение

'''Линейная регрессия''' (англ. ''linear regression'') — метод восстановления зависимости одной (объясняемой, зависимой) переменной <tex> y </tex> от другой или нескольких других переменных (факторов, регрессоров, независимых переменных) <tex> x </tex> с линейной функцией зависимости. Данный метод позволяет предсказывать значения зависимой переменной <tex> y </tex> по значениям независимой переменной <tex> x </tex>.

== Задача ==

==== Дано ====

* <tex> f_1(x), \dots ,f_n(x) </tex> - числовые признаки
* модель многомерной линейной регрессии:
<center> <tex> f(x,\alpha) = \sum\limits_{j=1}^n \alpha_j f_j(x) </tex>, </center>
где <tex> a \in R^n </tex>
* обучающая выборка: множество из пар <tex>(x_i, y_i)_{i=1 \dots n}</tex>
* <tex> x_i </tex> - объекты из множества <tex> X = R^n </tex>
* <tex> y_i </tex> - объекты из множества <tex> X = R </tex>

==== Матричные обозначения ====

Перейдем к матричным обозначениям:

<tex>
\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}

</tex>

, где
* <tex> F </tex> - матрица объектов-признаков, где строки соответствуют объектам а столбцы - признакам
* <tex> y </tex> - вектор ответов, или целевой вектор
* <tex> \alpha </tex> - вектор коэффициентов

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

В этих трех векторно-матричных обозначениях очень удобно расписать постановку задачи наименьших квадратов:

<tex> Q(\alpha, X^l) = \sum\limits_{i=1}^n (f(x_i, \alpha) - y_i)^2 = || F\alpha - y ||^2 \rightarrow \underset{\alpha}{min} </tex>

Необходимо найти вектор <tex> \alpha </tex> при известной матрице <tex> F </tex> и известном вектор-столбце <tex> y </tex>.

== Решение ==

=== Нормальная система уравнений ===

Запишем необходимые условия минимума в матричном виде.

<tex> \frac{\partial Q }{\partial \alpha } (\alpha) = 2F^T (F\alpha - y) = 0 </tex>

Отсюда следует нормальная система задачи МНК:

<tex> F^T F \alpha = F^T y </tex>,

где <tex> F^T F - n \times n </tex> матрица

Мы получили систему уравнений, откуда можем выразить искомый вектор <tex> \alpha </tex>.

==== Решение системы ====
<tex> \alpha^* = (F^T F)^{-1} F^T y = F^+ y </tex>.

Значение функционала: <tex> Q(\alpha^*) = ||P_F y - y||^2 </tex>,

где <tex> P_F = F F^+ = F (F^T F)^{-1} F^T </tex> - ''проекционная матрица''

==== Проблемы ====

В случае мультиколлинеарности (столбцы матрицы <tex> F </tex> линейно-зависимы) нам не удастся найти обратную матрицу к <tex> F^T F </tex> (она будет вырождена).

Если же столбцы матрицы <tex> F </tex> почти линейно-зависимы, то у нас возникнет масса вычислительных проблем с обращением этой матрицы.

=== Сингулярное разложение ===

Воспользуемся понятием [https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BD%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5/ сингулярного разложения ], которое позволяет произвольную прямоугольную матрицу представить в виде произведения трех матриц:

<tex> F = V D U^T </tex>.

Основные свойства сингулярного разложения:

* <tex> l \times n </tex>-матрица <tex> V = (v_1, \dots, v_n) </tex> ортогональна, <tex> V^T V = I_n </tex>, <br> столбцы <tex> v_j </tex> — собственные векторы матрицы <tex> F F^T </tex>;
* <tex> n \times n </tex>-матрица <tex> U = (u_1, \dots, u_n) </tex> ортогональна, <tex> U^T U = I_n </tex>, <br> столбцы <tex> u_j </tex> — собственные векторы матриц <tex> F^T F </tex>;
* <tex> n \times n </tex>-матрица <tex> D </tex> диагональна, <tex> D = diag(\sqrt{\lambda_1}, \dots, \sqrt{\lambda_n}) </tex>, <br> <tex> \lambda_j \geq 0 </tex> — собственные значения матриц <tex> F^T F </tex> и <tex> F F^T </tex>, <br> <tex> \sqrt{ \lambda_j } </tex> — сингулярные числа матрицы <tex> F </tex>.

=== Решение МНК через сингулярное разложение ===

<tex> 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 </tex>;

<tex> \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) </tex>;

<tex> 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) </tex>;

<tex> || \alpha^* ||^2 = ||D^{-1} V^T y||^2 = \sum\limits_{j=1}^n \frac{ 1 }{ \lambda_j } (v_j^T y)^2 </tex>.

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

2019-03-11T15:13:57Z

217.66.156.131: /* Решение */

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

2019-03-11T15:11:28Z

217.66.156.131: /* Сингулярное разложение */