Просмотр кода страницы Участник:V.P.Zykov/Стохастический градиентный спуск для линейной регрессии

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Задача регрессии <ref>Draper, N. R.; Smith, H. (1998). Applied Regression Analysis (3rd ed.). John Wiley. ISBN 978-0-471-17082-2</ref> в машинном обучении — это задача предсказания непрерывных значений на основе входных данных. Регрессия используется для моделирования зависимости между независимыми переменными (признаками) и зависимой переменной (целевой переменной), которая представляет собой вещественную величину. Предполагается, что нам даны значения целевой переменной на некоторых обучающих объектах (обучающая выборка). Нужно научиться получать значения целевой переменной для новых объектов. Для этого будем подбирать функцию, которая будет хорошо приближать целевую переменную на обучающей выборке. Функцию ищется в классе линейных. Будем подбирать её так, чтобы она минимизировала квадратичную функцию потерь с <math>l_2</math>-регуляризацией. Для этого функционал оптимизируется методом стохастического градиентного спуска <ref>Spall J. C. Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control. — Hoboken, NJ: Wiley, 2003. — ISBN 0-471-33052-3 </ref>.

=== Математическое описание алгоритма ===
Пусть рассматриваемые объекты <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 > 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 > 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>.

Этот метод оптимизации должен хорошо распараллеливаться, поскольку в вычислении градиентов присутствует умножение матриц, также можно пробовать считать градиенты по объектам независимо на разных потоках.


=== Вычислительное ядро алгоритма ===


=== Макроструктура алгоритма ===


=== Схема реализации последовательного алгоритма ===


=== Последовательная сложность алгоритма ===

=== Информационный граф ===



=== Ресурс параллелизма алгоритма ===

=== Входные и выходные данные алгоритма ===

=== Свойства алгоритма ===

== Программная реализация алгоритма ==


=== Особенности реализации последовательного алгоритма ===


=== Локальность данных и вычислений ===


=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===


== Литература ==
<references />

[[en:Description of algorithm properties and structure]]