Участник:V.P.Zykov/Стохастический градиентный спуск для линейной регрессии
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Задача регрессии [1] в машинном обучении — это задача предсказания непрерывных значений на основе входных данных. Регрессия используется для моделирования зависимости между независимыми переменными (признаками) и зависимой переменной (целевой переменной), которая представляет собой вещественную величину. Предполагается, что нам даны значения целевой переменной на некоторых обучающих объектах (обучающая выборка). Нужно научиться получать значения целевой переменной для новых объектов. Для этого будем подбирать функцию, которая будет хорошо приближать целевую переменную на обучающей выборке. Функцию ищется в классе линейных. Будем подбирать её так, чтобы она минимизировала квадратичную функцию потерь с [math]l_2[/math]-регуляризацией. Для этого функционал оптимизируется методом стохастического градиентного спуска [2].
1.2 Математическое описание алгоритма
Пусть рассматриваемые объекты [math]x[/math] принадлежат пространству [math]\mathbb{R}^n[/math]. Предположим, что нам дана обучающая выборка [math]\{x_i, y_i\}_{i=1}^l, \; y_i = y(x_i)[/math], где [math]y: \mathbb{R}^n \rightarrow \mathbb{R}[/math] - неизвестная зависимость.
Будем моделировать эту зависимость линейной функцией [math]f_{w}(x) = w_1 \cdot x_1 + \ldots w_n \cdot + x_n + w_0 = \langle w, \, x \rangle + w_0[/math]. Будем минимизировать функционал
[math]Q(w) = \dfrac{1}{l}\sum\limits_{i=1}^l L_i (w) + \tau ||w||^2_2 = \dfrac{1}{l}\sum\limits_{i=1}^l (y_i - f_w(x_i))^2 + \tau ||w||^2_2 = \dfrac{1}{l} ||Xw - y||^2_2 + \tau ||w||^2_2[/math].
Здесь мы расположили объекты по срокам в матрицу [math]X \in \mathbb{R}^{l \times(n+1)}[/math], добавив к ним константный признак [math]1[/math], [math]w \in \mathbb{R}^{n+1}[/math] - вектор параметров модели, [math] y \in \mathbb{R}^{l} [/math] - вектор целевой переменной на обучающей выборке, [math] \tau \gt 0 [/math] - параметр регуляризации. Заметим, что, вообще говоря, мы можем найти явное решение задачи [math]Q(w) \rightarrow \min\limits_w[/math], но оно будет содержать обратные матрицы, т.е. оно будет неэффективно вычисляться. Поэтому будем оптимизировать функционал методом стохастического градиентного спуска:
[math]w^{k+1} = w^k - \dfrac{\alpha}{k^{\beta}} \dfrac{\partial{\tilde{Q}_k}}{\partial w} (w^k)[/math], где [math]\alpha \gt 0, \beta \geqslant 0[/math] - параметры метода;
[math]\tilde{Q}_k = \dfrac{1}{|B_k|}\sum\limits_{i \in B_k} L_i (w) + \tau ||w||^2_2 [/math], [math]B_k \subseteq \{1, \ldots, l \} [/math] - батч объектов (свой на каждой итерации [math]k[/math]);
[math]\dfrac{\partial{\tilde{Q}_k}}{\partial w} (w) = \dfrac{2}{|B_k|} \tilde{X}^T_k (\tilde{X}_k w - \tilde{y}_k) + 2 \tau w[/math], где [math]\tilde{X}_k \text{ и } \tilde{y}_k[/math] - части [math]X \text{ и } y[/math], соответствующие объектам, попавшим в текущий батч [math]B_k[/math].
Этот метод оптимизации должен хорошо распараллеливаться, поскольку градиенты по объектам можно считать независимо разными потоками.
