МЛР

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
{{Задание|Касперский Иван|Константин Воронцов|{{дата|6|1|2009}}, а сейчас {{дата}}}}
{{Задание|Касперский Иван|Константин Воронцов|{{дата|6|1|2009}}, а сейчас {{дата}}}}
-
Многомерная линейная регрессия — это [[регрессия]] в 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>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\)\ .</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>
Алгоритм:
Алгоритм:
Строка 9: Строка 9:
Оценим качество его работы на выборке <tex>X^l = (x_i,\ y_i)_{i=1}^l \in X*Y</tex> [[Метод наименьших квадратов| методом наименьших квадратов]]:
Оценим качество его работы на выборке <tex>X^l = (x_i,\ y_i)_{i=1}^l \in X*Y</tex> [[Метод наименьших квадратов| методом наименьших квадратов]]:
-
:<tex>Q(\alpha, X^l)\ =\ \sum_{i=1}^l(a(x_i) - y_i)^2 \rightarrow \min_{\alpha \in \mathbb{R}^n}</tex>, или, в матричных обозначениях,<br />
+
:<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>Q(\alpha)\ =\ \parallel (F\alpha\ -\ y)\parallel^2 \rightarrow \min_{\alpha \in \mathbb{R}^n}</tex>.
+
:<tex>Q(\alpha)\ =\ \parallel W(F\alpha\ -\ y)\parallel^2 \rightarrow \min_{\alpha \in \mathbb{R}^n}</tex>.
-
Найдём минимум <tex>Q(\alpha)</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>\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>.
Если <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>.
Строка 31: Строка 36:
А так как <tex>\parallel \alpha \parallel^2 \ =\ \alpha ^T \alpha</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>
:<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>
-
<references/>
+
==Проблемы==
 +
Основной проблемой многомерной линейной регресии является вырожденность, или, в более общем случае, [[мультиколлинеарность]] матрицы 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}</tex>

Версия 10:21, 5 января 2010

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

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

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


Многомерная линейная регрессия — это линейная регрессия в 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).

Оценим качество его работы на выборке 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 новых признаков. В частности, линейные преобразования приводят к метод главных компонент.

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

f_{ij}\ =\ (f_ij - \overline{f_j})/{\sigma _j}
Источник — «http://recognition.su/wiki/index.php?title=%D0%9C%D0%9B%D0%A0»
Личные инструменты