МЛР

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

Версия от 10:38, 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) \ \vdots f_i(x_l)$\;, \ \ y=$y_1 \ \vdots y_l$\;, \ \ \ \alpha=$\alpha_1 \ \vdots \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.$

Проблемы

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

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

Чем больше число обусловленности, тем ближе матрица F^TF к вырожденной и тем неустойчивее обратная к ней матрица. Плохая обусловленность матрицы: λ_min << λ_max. Матрицу принято считать плохо обусловленной, если её число обусловленности превышает 10³...10⁶.

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

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

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

Регуляризация. Накладываются дополнительные ограничения на норму вектора коэффициентов α. Примером могут служить гребневая регрессия или L₁-регуляризация)
Преобразование признаков. Исходные n признаков с помощью некоторых преобразований переводятся в меньшее число m новых признаков. В частности, линейные преобразования приводят к методу главных компонент.

Другой важной, но существенно более простой в плане решения проблемой является разнородность признаков. Если машстабы измерений признаков существенно (на несколько порядков) различаются, то появляется опасно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, α*). Также следует отметить, что ковариационная матрица F^TF после стандартизации становится корреляционной матрицей.