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

V.P.Zykov в 21:16, 5 ноября 2024

2024-11-05T21:16:47Z

← Предыдущая версия		Версия от 21:16, 5 ноября 2024
Строка 20:		Строка 20:
	<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>.		<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>.

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

V.P.Zykov в 21:11, 5 ноября 2024

2024-11-05T21:11:20Z

← Предыдущая версия		Версия от 21:11, 5 ноября 2024
Строка 3:		Строка 3:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	Задача регрессии в машинном обучении — это задача предсказания непрерывных значений на основе входных данных. Регрессия используется для моделирования зависимости между независимыми переменными (признаками) и зависимой переменной (целевой переменной), которая представляет собой вещественную величину. Предполагается, что нам даны значения целевой переменной на некоторых обучающих объектах (обучающая выборка). Нужно научиться получать значения целевой переменной для новых объектов. Для этого будем подбирать функцию, которая будет хорошо приближать целевую переменную на обучающей выборке. Функцию ищется в классе линейных. Будем подбирать её так, чтобы она минимизировала квадратичную функцию потерь с <math>l_2</math>-регуляризацией. Для этого функционал оптимизируется методом стохастического градиентного спуска.		Задача регрессии <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>.


	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===

V.P.Zykov в 20:58, 5 ноября 2024

2024-11-05T20:58:57Z

← Предыдущая версия		Версия от 20:58, 5 ноября 2024
Строка 3:		Строка 3:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	Задача регрессии в машинном обучении — это задача предсказания непрерывных значений на основе входных данных. Регрессия используется для моделирования зависимости между независимыми переменными (признаками) и зависимой переменной (целевой переменной), которая представляет собой вещественную величину. Предполагается, что нам даны значения целевой переменной на некоторых обучающих объектах (обучающая выборка). Нужно научиться получать значения целевой переменной для новых объектов. Для этого будем подбирать функцию, которая бы хорошо ~~приближала~~ целевую переменную на обучающей выборке. Функцию ~~будем подбирать из класса~~ линейных. Будем подбирать её так, чтобы она минимизировала квадратичную функцию потерь. Для этого ~~будем оптимизировать этот~~ функционал методом стохастического градиентного спуска.		Задача регрессии в машинном обучении — это задача предсказания непрерывных значений на основе входных данных. Регрессия используется для моделирования зависимости между независимыми переменными (признаками) и зависимой переменной (целевой переменной), которая представляет собой вещественную величину. Предполагается, что нам даны значения целевой переменной на некоторых обучающих объектах (обучающая выборка). Нужно научиться получать значения целевой переменной для новых объектов. Для этого будем подбирать функцию, которая будет хорошо приближать целевую переменную на обучающей выборке. Функцию ищется в классе линейных. Будем подбирать её так, чтобы она минимизировала квадратичную функцию потерь с <math>l_2</math>-регуляризацией. Для этого функционал оптимизируется методом стохастического градиентного спуска.


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

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


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

V.P.Zykov: Новая страница: «== Свойства и структура алгоритма == === Общее описание алгоритма === Задача регрессии в маш...»

2024-11-05T19:45:08Z

Новая страница: «== Свойства и структура алгоритма == === Общее описание алгоритма === Задача регрессии в маш...»

Новая страница

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

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

Задача регрессии в машинном обучении — это задача предсказания непрерывных значений на основе входных данных. Регрессия используется для моделирования зависимости между независимыми переменными (признаками) и зависимой переменной (целевой переменной), которая представляет собой вещественную величину. Предполагается, что нам даны значения целевой переменной на некоторых обучающих объектах (обучающая выборка). Нужно научиться получать значения целевой переменной для новых объектов. Для этого будем подбирать функцию, которая бы хорошо приближала целевую переменную на обучающей выборке. Функцию будем подбирать из класса линейных. Будем подбирать её так, чтобы она минимизировала квадратичную функцию потерь. Для этого будем оптимизировать этот функционал методом стохастического градиентного спуска.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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