Гребінна регресія (Ridge regression), Машинне навчання вікі, FANDOM powered by Wikia

Постановка задачі

Вирішується завдання регресії. Застосовується лінійна модель (взагалі кажучи, одна з ознак вважається константною для того, щоб апроксимуюча гіперплощина не обов'язково проходила через нуль, я не знаю, чому це практично усюди опускається): \rangle$. У початковій постановці вважається, що вектор $ \beta $ знаходиться методом Звичайних Найменших Квадратів (ОНК): $ \sum_^ (f(x_n, \beta) - y_n)^2 \longrightarrow \min_ $

Аналітичне рішення даної задачі: $ \beta^ = (X^TX)^X^TY$ , проте при виродженості матриці $ X^TX $ рішення виявляється не єдиним, а при її поганій обумовленості - нестійким. Тому доцільно ввести регуляризацію за параметром $\beta$, наприклад, $L_2$.

Таким чином, приходимо до наступного завдання мінімізації (гребенева (ridge) регресія):

$ Q(\beta)= \left \ Y - X\beta \right \^2 + \lambda\left \\beta \right \^2 \longrightarrow \min_ $

де $ \left \\beta \right \^2 =\sum^_ ^2, $ $ \lambda $ - параметр регуляризації (невід'ємне число).

Виведення оптимальних ваг

Для знаходження оптимальних ваг продиференціюємо функціонал по $ \ beta $ і прирівняємо до 0: $ \ frac = 2X (X \ beta - Y) + 2 \ lambda \ beta = 0 $

$ (X^X + \lambda I)\beta = X^Y $

$ \beta^ =(X^X + \lambda I)^ X^Y $ При збільшенні параметра $ \lambda $ рішення стає більш стійким, але з іншого боку - зміщеним. При зменшенні – приходимо до завдання ГНК без регуляризації: маємо шанс перенавчитися. Тому треба шукати щось посередині.

Узагальнення через ядра

Розв'язання прямої (див. вище) задачі, як було отримано: $ \beta^ =(X^X + \lambda I)^ X^Y $ .Зауважимо, що з невід'ємної визначеності матриці $ X^TX $ матриця $ X^X + lambda I $ взагалі позитивно визначена, тому пряме рішення завжди існує і єдино. Складність навчання: $ O (D ^ 2 (N + D)) $ , Складність передбачення: $ O (D) $ .

Введемо подвійні змінні. Для цього вирішимо двоїсту задачу, де розв'язання прямої задачі буде представлено у вигляді деякої лінійної комбінації векторів навчальної вибірки. З умов стаціонарності $ X^T(X\beta - Y) + \lambda \beta = 0 $ слідує $ \beta = \fracX^T(Y - X\beta) = X^T\alpha $ , де вектор $ \ alpha = \ frac (Y - X \ beta) $ - Вектор подвійних змінних. Формула для передбачення: $ \hat(x) = x^T\beta = x^TX^T\alpha = \sum_^N \alpha_i \langle x, x_i\rangle $ . Знайти подвійні змінні можна так: $ \alpha = (XX^T + \lambda I)^Y $ . Це прямо випливає з $ \ alpha = \ frac (Y - X \ beta) $ при підстановці $ \ beta = X ^ T \ alpha $ . Складність навчання: $ O (N ^ 2 (D + N)) $ , Складність передбачення: $ O (ND) $ .

Зауважимо, що для знаходження подвійних змінних і передбачення по них потрібні лише скалярні твори векторів навчальної вибірки, але тоді, використовуючи загальну парадигму ядерних узагальнень методів, ми можемо замінити скалярні твори $ \ langle x, x' \ rangle $ скрізь вище на ядерну функцію K(x, x') $ , отримавши наступні формули: $ \alpha = (G + \lambda I)^Y $ , де $ \_ = K(x_i, x_j) $ - матриця Грама, $ \hat(x) = \sum_^N \alpha_i K(x, x_i) $ . Отже, вирішуючи завдання лінійної регресії можна одержувати нелінійні рішення.

---