Линейная регрессия — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(См. также)
Строка 81: Строка 81:
 
Если же столбцы матрицы <tex> 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> 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>.
 
 
=== Решение МНК через сингулярное разложение ===
 
  
 
Найдем псевдо-обратную матрицу: <br> <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^T </tex>.
 
Найдем псевдо-обратную матрицу: <br> <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^T </tex>.

Версия 18:17, 19 марта 2019

Линейная регрессия (англ. 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] F^+ [/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] 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^T [/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] 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].

В 3-х из 4-х формул сингулярные числа оказались в знаменателе. Если имеются сингулярные числа приближающиеся к 0, то мы получаем проблему мультиколлинеарности. Близкие к 0 собственные значения или сингулярные числа — показатель того, что среди признаков есть почти линейно-зависимый.

Проблема мультиколлинеарности и переобучения

Если имеются сингулярные числа, близкие к 0, то:

  • матрица [math] \sum = F^T F [/math] плохо обусловлена;
  • решение становится неустойчивым и неинтерпретируемым, слишком большие коэффициенты [math] || \alpha_j || [/math] разных знаков;
  • возникает переобучение:
    на обучении [math] Q( \alpha^*, X^l ) = ||F \alpha^* - y||^2 [/math] мало;
    на контроле [math] Q( \alpha^*, X^k ) = ||F' \alpha^* - y'||^2 [/math] велико.

Стратегии устранения мультиколлинеарности и переобучения:

  • отбор признаков, то есть выкидываем те признаки, которые могут оказаться линейно-зависимыми:
    [math] f_1, \dots, f_n \rightarrow f_{j_1} \dots, f_{j_m}, m \leq n [/math];
  • регуляризация (накладываем дополнительные ограничения на вектор коэффициентов):
    [math] || \alpha || \rightarrow min [/math];
  • преобразование признаков, чтобы в новом признаковом пространстве признаков оказалось меньше, но они хорошо восстанавливали бы исходные:
    [math] f_1, \dots, f_n \rightarrow g_1 \dots, g_m, m \ll n [/math].

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

import matplotlib.pyplot as plt
from sklearn import datasets, linear_model

# generate dataset
X, y = datasets.make_regression(n_samples=1_000, n_features=1, noise=8, shuffle=True)

# test and train data sizes
train_size = 700
test_size = 300

# split the data into training/testing sets
X_train = X[:-train_size]
X_test = X[-test_size:]

# split the targets into training/testing sets
y_train = y[:-train_size]
y_test = y[-test_size:]

# create linear regression object
regr = linear_model.LinearRegression()

# train the model using the training sets
regr.fit(X_train, y_train)

# make predictions using the testing set
y_pred = regr.predict(X_test)

# plot outputs
plt.scatter(X_test, y_test, color='red', s=5)
plt.plot(X_test, y_pred, color='blue', linewidth=2)
 
plt.xticks(())
plt.yticks(())

plt.show()

Возможный результат исполнения программы:

Linear regression example.png

См. также

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