Многомерная линейная регрессия

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
м (→Метод наименьших квадратов как функционал качества: орфография)
Строка 1: Строка 1:
-
'''Многомерная линейная регрессия''' по сути есть [[Линейная регрессия (пример)|линейная регрессия]], в которой объекты <tex>x</tex> и ответы <tex>y</tex> являются векторами.
+
Многомерная линейная регрессия &mdash; это [[линейная регрессия]] в n-мерном пространстве (объекты и признаки являются n-мерными векторами).
 +
== Многомерная линейная регрессия ==
 +
Имеется множество объектов <tex>X = \mathbb{R} ^n</tex> и множество ответов <tex>Y = \mathbb{R}</tex>. Также имеется набор <tex>n</tex> вещественнозначных признаков <tex>f_j(x), \ j=1, \ \ldots , \ n</tex>. Введём матричные обозначения: матрицу информации <tex>F</tex>, целевой вектор <tex>y</tex>, вектор параметров <tex>\alpha</tex> и диагональную матрицу весов:
 +
:<tex>F=\(f_1\ \dots\ f_n\)\;,\ \ f_i=\(f_i(x_1)<br>\ \vdots<br>f_i(x_l)\)\;, \ \ y=\(y_1<br>\ \vdots<br>y_l\)\;, \ \ \ \alpha=\(\alpha_1<br>\ \vdots<br>\alpha_n\)\ ,\ \ W=diag(\sqrt{\lambda _1},\ \ldots,\ \sqrt{\lambda _l})</tex>
-
==Примеры задач==
+
Алгоритм:
-
Многомерная линейная регрессия широко применяется в задачах прогнозирования [[Временной ряд|временных рядов]], где объекты и ответы являются рядами. В частности, в методе [http://en.wikipedia.org/wiki/Echo_state_network рекуррентной нейросети с откликом].
+
:<tex>a(x)\ =\ \sum_{j=1}^n\alpha_jf_j(x)\ =\ F\alpha</tex>.
-
== Обозначения ==
+
Оценим качество его работы на выборке <tex>X^l = (x_i,\ y_i)_{i=1}^l \in X*Y</tex> [[Метод наименьших квадратов| методом наименьших квадратов]]:
-
Пусть имеется набор <tex>n</tex> вещественнозначных признаков <tex>f_j(x), j=1,...,n</tex>. Введём матричные обозначения: матрицу информации <tex>F</tex>, целевой вектор <tex>y</tex>, вектор параметров <tex>\alpha</tex> и диагональную матрицу весов <tex>W</tex>:
+
:<tex>Q(\alpha, X^l)\ =\ \sum_{i=1}^lw_i(a(x_i) - y_i)^2 \rightarrow \min_{\alpha \in \mathbb{R}^n}</tex>, или, в матричных обозначениях,<br />
-
::<tex>F=\(f_1(x_1)\ \ \ldots\ \ f_n(x_1)<br>\ \vdots\ \ \ \ \ \ \ \ \ \ \ddots\ \ \ \ \vdots<br>f_1(x_l)\ \ \ldots\ \ f_n(x_l)\)\;, \ \ \ y=\(y_1<br>\ \vdots<br>y_l\)\;, \ \ \ \alpha=\(\alpha_1<br>\ \vdots<br>\alpha_n\)\;, \ \ \ W=\(\sqrt{w_1}\ \ \ \ \ \ \ \ 0\ <br>\ \ \ \ \ \ \ddots<br>\ 0\ \ \ \ \ \ \ \ \sqrt{w_l}\)\;.</tex>
+
:<tex>Q(\alpha)\ =\ \parallel W(F\alpha\ -\ y)\parallel^2 \rightarrow \min_{\alpha \in \mathbb{R}^n}</tex>.
-
== Метод наименьших квадратов как функционал качества ==
+
Задача с произвольной матрицей весов легко приводится к единичной матрице весов заменой <tex>F' = WF\ ,\ y' = Wy\ </tex>:
-
Задача минимизации функционала качества [[Метод наименьших квадратов| метода наименьших квадратов]]
+
:<tex>Q(\alpha)\ =\ \parallel F'\alpha\ -\ y'\parallel^2\ =\ (F'\alpha\ -\ y')^\top(F'\alpha\ -\ y')</tex>.
-
::<tex>Q(\alpha, X^l) = \sum_{i=1}^l\mathbf{w}_i(f(x_i, \alpha)-y_i)^2\longrightarrow\min</tex>
+
-
существенно упрощается, если модель алгоритмов линейна по параметрам <tex>\alpha \in \mathbb{R}^n</tex>:
+
-
::<tex>f(x,\alpha) = \sum_{j=1}^n\alpha_jf_j(x)</tex>.
+
-
В матричных обозначениях функционал среднего квадрата ощибки принимает вид
+
Таким образом, в дальнейшем будем рассматривать только задачу с единичными весами.
-
::<tex>Q(\alpha)\ =\ \parallel W(F\alpha\ -\ y)\parallel^2</tex>.
+
-
Функционал с произвольными весами легко преводится к функционалу с единичными весами путём несложной предварительной обработки данных <tex>F' = WF\ ,\ y' = Wy\ </tex>:
+
-
::<tex>Q(\alpha)\ =\ \parallel F'\alpha\ -\ y'\parallel^2\ =\ (F'\alpha\ -\ y')^\top(F'\alpha\ -\ y')</tex>
+
-
==Литература==
+
Найдём минимум <tex>Q(\alpha)</tex> по ''α'':
-
# {{книга
+
:<tex>\frac{\partial Q (\alpha)}{\partial \alpha} = 2 F^T (F\alpha - y) = 0\ \Rightarrow\ (F^TF)\alpha = F^Ty</tex>.<br />
-
|автор = Воронцов К.В.
+
Если <tex>rank(F^TF) = n</tex>, то можно обращать матрицу <tex>F^TF\ \text{:}\ \alpha^* = (F^TF)^{-1}F^Ty = F^+y</tex>, где введено обозначение <tex>F^+ = (F^TF)^{-1}F^T</tex>.
-
|заглавие = Лекции по алгоритмам восстановления регрессии
+
 
-
|год = 2007
+
 
-
|ссылка = http://www.ccas.ru/voron/download/Regression.pdf
+
В таком случае функционал качества записывается в более удобной форме:<br />
-
}}
+
:<tex>Q(\alpha^*) = \parallel F(F^TF)^{-1}F^Ty - y \parallel ^2 = \parallel P_{_F}y - y \parallel^2</tex>, где <tex>P_F</tex> &mdash; проекционная матрица:<br />
 +
<tex>P_{_F} y</tex> — вектор, являющийся проекцией <tex>y</tex> на <tex>\mathfrak{L}(f_1,\ \dots,\ f_n)</tex>.
 +
 
 +
Теперь рассмотрим [[сингулярное разложение]] матрицы F:<br />
 +
:<tex>F\ =\ VDU^T</tex>.
 +
В таких обозначениях:<br />
 +
:<tex>F^+\ =\ (F^TF)^{-1}F^T\ =\ (UDV^TVDU^T)^{-1}UDV^T\ =\ (UDDU^T)^{-1}UDV^T\ =\ U^{-T}D^{-2}U^{-1}UDV^T\ =\ U^{-T}D^{-2}DV^T</tex>, а так как <tex>U^{-1}\ =\ U^T</tex>, то <tex>F^+\ =\ UD^{-1}V^T\ =\ \sum_{j=1}^{n}{ \frac{1}{\sqrt{\lambda _j}}u_j v_j^T }</tex> в силу диагональности матрицы ''D''.
 +
 
 +
А решение метода наименьших квадратов запишется в следующем виде:<br />
 +
:<tex>\alpha ^*\ =\ F^+y\ =\ \sum_{j=1}^{n} \frac1{\sqrt{\alpha _j}} u_j(v_j^T,\ y);</tex><br />
 +
А так как <tex>\parallel \alpha \parallel^2 \ =\ \alpha ^T \alpha</tex>, то <br />
 +
:<tex>\parallel \alpha ^*\parallel^2 \ =\ \parallel UD^{-1}V^Ty \parallel^2 \ =\ y^TVD^{-T}U^TUD^{-1}V^Ty\ =\ y^TVD^{-2}V^Ty\ =\ \parallel D^{-1}V^Ty \parallel^2\ =\ \sum_{j=1}^{n} \frac1{\alpha _j} (v_j^T,\ y)^2.</tex>
 +
 
 +
==Проблемы==
 +
===Мультиколлинеарность===
 +
Основной проблемой многомерной линейной регресии является вырожденность, или, в более общем случае, [[мультиколлинеарность]] матрицы F<sup>T</sup>F, которую приходится обращать. Подобные проблемы возникают, когда среди признаков f<sub>j</sub>(x) есть почти линейно зависимые.<br />
 +
Мультиколлинеарность матрицы определяется её ''числом обусловленности'':
 +
:<tex>\mu (F^TF)\ =\ \parallel F^TF \parallel * \parallel (F^TF)^{-1} \parallel \ =\ \frac{\lambda _{max}}{\lambda _{min}}</tex>, где λ &mdash; собственные значения матрицы F<sup>T</sup>F.
 +
 
 +
Чем больше число обусловленности, тем ближе матрица F<sup>T</sup>F к вырожденной и тем неустойчивее обратная к ней матрица. Плохая обусловленность матрицы: λ<sub>min</sub> << λ<sub>max</sub>. Матрицу принято считать плохо обусловленной, если её число обусловленности превышает 10<sup>3</sup>...10<sup>6</sup>.
 +
 
 +
Последствия:<br />
 +
# Разброс значений α<sub>j</sub>. Появляются большие положительные и большие отрицательные коэффициенты α<sub>j</sub>. По абсолютной величине коэффициента становится невозможно судить о степени важности признака f<sub>j</sub> . Коэффициенты утрачивают интерпретируемость.
 +
# Неустойчивость решения α* при (кажущейся) устойчивости Fα*. Малые изменения данных, например, шум или добавление нового объекта, могут сильно изменить вектор коэффициентов.
 +
# Отсюда следует опасность переобучения, так как снижается обобщающая способность алгоритма.
 +
 
 +
Для борьбы с мультиколлинеарностью применяются существуют методы:
 +
# ''[[Регуляризация]]''. Накладываются дополнительные ограничения на норму вектора коэффициентов α. Примером могут служить [[гребневая регрессия]] или [[Лассо Тибширани|L<sub>1</sub>-регуляризация]])
 +
# ''Преобразование признаков''. Исходные n признаков с помощью некоторых преобразований переводятся в меньшее число m новых признаков. В частности, линейные преобразования приводят к [[метод главных компонент|методу главных компонент]].
 +
# ''Отбор признаков''. Производится явный перебор всевозможных подмножеств признаков. Для линейной регрессии удаётся строить эффективные методы, совмещающие перебор подмножеств с оптимизацией коэффициентов. К таким методам относятся, опять-таки, лассо Тибширани и [[ортогонализация Грама–Шмидта]].
 +
 
 +
===Разный масштаб признаков===
 +
Другой важной проблемой многомерной линейной регрессии является разнородность признаков. Если машстабы измерений признаков существенно (на несколько порядков) различаются, то появляется опасноcть, что будут учитываться только «крупномасштабные» признаки. Чтобы этого избежать, делается ''стандартизация'' матрицы F:<br />
 +
:<tex>f_{ij}\ =\ (f_{ij} - \overline{f_j})/{\sigma _j},\ j=1...n,\ i=1...l</tex>,<br />
 +
где <tex>\overline{f_j}=\frac1l \sum_{i=1}^{l}f_{ij}</tex> &mdash; выборочное среднее, а <tex>\sigma _j^2=\frac1l \sum_{i=1}^{l}(f_{ij}\ -\ \overline{f_j})^2</tex> &mdash; выборочная дисперсия. При этом после стандартизации исходных данных то же самое преобразование необходимо будет применять ко всем объектам, подаваемым на вход алгоритма α*(x) = f(x, α*). Также следует отметить, что ковариационная матрица F<sup>T</sup>F после стандартизации становится корреляционной матрицей.
==См. также==
==См. также==
-
* [[Метод наименьших квадратов]]
+
[[Регрессия|Линейная регрессия]]<br />
-
* [[Регрессионный анализ]]
+
[[Метод главных компонент]]<br />
 +
[[Гребневая регрессия]]<br />
 +
[[Сингулярное разложение]]
-
[[Категория:Регрессионный анализ]]
+
{{ЗаданиеВыполнено|Касперский Иван|Константин Воронцов|{{дата|6|1|2009}}}}

Версия 18:56, 8 января 2010

Многомерная линейная регрессия — это линейная регрессия в n-мерном пространстве (объекты и признаки являются n-мерными векторами).

Содержание

Многомерная линейная регрессия

Имеется множество объектов X = \mathbb{R} ^n и множество ответов Y = \mathbb{R}. Также имеется набор n вещественнозначных признаков f_j(x), \ j=1, \ \ldots , \ n. Введём матричные обозначения: матрицу информации F, целевой вектор y, вектор параметров \alpha и диагональную матрицу весов:

F=\(f_1\ \dots\ f_n\)\;,\ \ f_i=\(f_i(x_1)<br>\ \vdots<br>f_i(x_l)\)\;, \ \ y=\(y_1<br>\ \vdots<br>y_l\)\;, \ \ \ \alpha=\(\alpha_1<br>\ \vdots<br>\alpha_n\)\ ,\ \ W=diag(\sqrt{\lambda _1},\ \ldots,\ \sqrt{\lambda _l})

Алгоритм:

a(x)\ =\ \sum_{j=1}^n\alpha_jf_j(x)\ =\ F\alpha.

Оценим качество его работы на выборке X^l = (x_i,\ y_i)_{i=1}^l \in X*Y методом наименьших квадратов:

Q(\alpha, X^l)\ =\ \sum_{i=1}^lw_i(a(x_i) - y_i)^2 \rightarrow \min_{\alpha \in \mathbb{R}^n}, или, в матричных обозначениях,
Q(\alpha)\ =\ \parallel W(F\alpha\ -\ y)\parallel^2 \rightarrow \min_{\alpha \in \mathbb{R}^n}.

Задача с произвольной матрицей весов легко приводится к единичной матрице весов заменой F' = WF\ ,\ y' = Wy\ :

Q(\alpha)\ =\ \parallel F'\alpha\ -\ y'\parallel^2\ =\ (F'\alpha\ -\ y')^\top(F'\alpha\ -\ y').

Таким образом, в дальнейшем будем рассматривать только задачу с единичными весами.

Найдём минимум Q(\alpha) по α:

\frac{\partial Q (\alpha)}{\partial \alpha} = 2 F^T (F\alpha - y) = 0\ \Rightarrow\ (F^TF)\alpha = F^Ty.

Если rank(F^TF) = n, то можно обращать матрицу F^TF\ \text{:}\ \alpha^* = (F^TF)^{-1}F^Ty = F^+y, где введено обозначение F^+ = (F^TF)^{-1}F^T.


В таком случае функционал качества записывается в более удобной форме:

Q(\alpha^*) = \parallel F(F^TF)^{-1}F^Ty - y \parallel ^2 = \parallel P_{_F}y - y \parallel^2, где P_F — проекционная матрица:

P_{_F} y — вектор, являющийся проекцией y на \mathfrak{L}(f_1,\ \dots,\ f_n).

Теперь рассмотрим сингулярное разложение матрицы F:

F\ =\ VDU^T.

В таких обозначениях:

F^+\ =\ (F^TF)^{-1}F^T\ =\ (UDV^TVDU^T)^{-1}UDV^T\ =\ (UDDU^T)^{-1}UDV^T\ =\ U^{-T}D^{-2}U^{-1}UDV^T\ =\ U^{-T}D^{-2}DV^T, а так как U^{-1}\ =\ U^T, то F^+\ =\ UD^{-1}V^T\ =\ \sum_{j=1}^{n}{ \frac{1}{\sqrt{\lambda _j}}u_j v_j^T } в силу диагональности матрицы D.

А решение метода наименьших квадратов запишется в следующем виде:

\alpha ^*\ =\ F^+y\ =\ \sum_{j=1}^{n} \frac1{\sqrt{\alpha _j}} u_j(v_j^T,\ y);

А так как \parallel \alpha \parallel^2 \ =\ \alpha ^T \alpha, то

\parallel \alpha ^*\parallel^2 \ =\ \parallel UD^{-1}V^Ty \parallel^2 \ =\ y^TVD^{-T}U^TUD^{-1}V^Ty\ =\ y^TVD^{-2}V^Ty\ =\ \parallel D^{-1}V^Ty \parallel^2\ =\ \sum_{j=1}^{n} \frac1{\alpha _j} (v_j^T,\ y)^2.

Проблемы

Мультиколлинеарность

Основной проблемой многомерной линейной регресии является вырожденность, или, в более общем случае, мультиколлинеарность матрицы FTF, которую приходится обращать. Подобные проблемы возникают, когда среди признаков fj(x) есть почти линейно зависимые.
Мультиколлинеарность матрицы определяется её числом обусловленности:

\mu (F^TF)\ =\ \parallel F^TF \parallel * \parallel (F^TF)^{-1} \parallel \ =\ \frac{\lambda _{max}}{\lambda _{min}}, где λ — собственные значения матрицы FTF.

Чем больше число обусловленности, тем ближе матрица FTF к вырожденной и тем неустойчивее обратная к ней матрица. Плохая обусловленность матрицы: λmin << λmax. Матрицу принято считать плохо обусловленной, если её число обусловленности превышает 103...106.

Последствия:

  1. Разброс значений αj. Появляются большие положительные и большие отрицательные коэффициенты αj. По абсолютной величине коэффициента становится невозможно судить о степени важности признака fj . Коэффициенты утрачивают интерпретируемость.
  2. Неустойчивость решения α* при (кажущейся) устойчивости Fα*. Малые изменения данных, например, шум или добавление нового объекта, могут сильно изменить вектор коэффициентов.
  3. Отсюда следует опасность переобучения, так как снижается обобщающая способность алгоритма.

Для борьбы с мультиколлинеарностью применяются существуют методы:

  1. Регуляризация. Накладываются дополнительные ограничения на норму вектора коэффициентов α. Примером могут служить гребневая регрессия или L1-регуляризация)
  2. Преобразование признаков. Исходные n признаков с помощью некоторых преобразований переводятся в меньшее число m новых признаков. В частности, линейные преобразования приводят к методу главных компонент.
  3. Отбор признаков. Производится явный перебор всевозможных подмножеств признаков. Для линейной регрессии удаётся строить эффективные методы, совмещающие перебор подмножеств с оптимизацией коэффициентов. К таким методам относятся, опять-таки, лассо Тибширани и ортогонализация Грама–Шмидта.

Разный масштаб признаков

Другой важной проблемой многомерной линейной регрессии является разнородность признаков. Если машстабы измерений признаков существенно (на несколько порядков) различаются, то появляется опасноcть, что будут учитываться только «крупномасштабные» признаки. Чтобы этого избежать, делается стандартизация матрицы F:

f_{ij}\ =\ (f_{ij} - \overline{f_j})/{\sigma _j},\ j=1...n,\ i=1...l,

где \overline{f_j}=\frac1l \sum_{i=1}^{l}f_{ij} — выборочное среднее, а \sigma _j^2=\frac1l \sum_{i=1}^{l}(f_{ij}\ -\ \overline{f_j})^2 — выборочная дисперсия. При этом после стандартизации исходных данных то же самое преобразование необходимо будет применять ко всем объектам, подаваемым на вход алгоритма α*(x) = f(x, α*). Также следует отметить, что ковариационная матрица FTF после стандартизации становится корреляционной матрицей.

См. также

Линейная регрессия
Метод главных компонент
Гребневая регрессия
Сингулярное разложение


Данная статья была создана в рамках учебного задания.
Студент: Участник:Касперский Иван
Преподаватель: Участник:Константин Воронцов
Срок: 6 января 2009


В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта MachineLearning.ru.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%B0%D1%8F_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F»