Участница:OvsyannikovaSA/Стохастический градиентный спуск - История изменений

OvsyannikovaSA: /* Информационный граф */

2025-12-09T12:01:26Z

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

← Предыдущая версия		Версия от 12:01, 9 декабря 2025
Строка 151:		Строка 151:
	На схеме изображен информационный граф стохастического градиентного спуска с мини-батчами.		На схеме изображен информационный граф стохастического градиентного спуска с мини-батчами.

	[[file:Informational_graph_minibatch_SGD.png~~\|thumb~~\|center\|Информационный граф стохастического градиентного спуска с мини-батчами]]		[[file:Informational_graph_minibatch_SGD.png\|center\|Информационный граф стохастического градиентного спуска с мини-батчами]]
	Здесь приводится схема выполнения одной эпохи. Стрелки, изображающие обработку остальных объектов данного батча, опущены для улучшения читаемости схемы. После обработки одного батча с весами <math>w_i</math> производится шаг градиентного спуска, и следующий батч обрабатывается уже с весами <math>w_{i+1}</math>.		Здесь приводится схема выполнения одной эпохи. Стрелки, изображающие обработку остальных объектов данного батча, опущены для улучшения читаемости схемы. После обработки одного батча с весами <math>w_i</math> производится шаг градиентного спуска, и следующий батч обрабатывается уже с весами <math>w_{i+1}</math>.

OvsyannikovaSA: /* Схема реализации последовательного алгоритма */

2025-12-09T11:59:45Z

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

← Предыдущая версия		Версия от 11:59, 9 декабря 2025
Строка 127:		Строка 127:

	=== Схема реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
	[[Файл:Sequential SGD with mini-batches scheme.png~~\|мини~~\|Схема последовательной реализации стохастического градиентного спуска с мини-батчами]]		[[Файл:Sequential SGD with mini-batches scheme.png\|Схема последовательной реализации стохастического градиентного спуска с мини-батчами]]

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

OvsyannikovaSA: исправления неточностей

2025-12-09T08:33:29Z

исправления неточностей

Внесённые изменения

OvsyannikovaSA: добавлено: свойства алгоритма

2025-12-08T23:06:55Z

добавлено: свойства алгоритма

← Предыдущая версия		Версия от 23:06, 8 декабря 2025
Строка 251:		Строка 251:

	* История потерь (loss history, опционально): вектор, содержащий значение функции потерь, вычисленное после каждого шага SGD. Объем равен <math>(E \times N) / B</math>. Используется для анализа сходимости и отладки алгоритма.		* История потерь (loss history, опционально): вектор, содержащий значение функции потерь, вычисленное после каждого шага SGD. Объем равен <math>(E \times N) / B</math>. Используется для анализа сходимости и отладки алгоритма.

			===Свойства алгоритма===
			====Соотношение последовательной и параллельной сложности====

			Алгоритм SGD является последовательным по отношению к шагам обновления весов. Однако в рамках одного шага обновления (одного мини-батча) он обладает высоким ресурсом параллелизма.

			* Последовательная сложность одного шага SGD: <math>T_{seq} = O(B \cdot d)</math>, где <math>B</math> - размер батча, <math>d</math> - размерность весов.
			* Параллельная сложность одного шага SGD (высота ЯПФ): <math>H = O(\log_2 B + 1)</math>.

			Теоретический выигрыш от параллельной реализации (ускорение) составляет:

			<math>S = \frac{T_{seq}}{H} = \frac{O(B \cdot d)}{O(\log_2 B + 1)}</math>

			Теоретически, параллельная реализация обеспечивает значительное ускорение <math>O(B \cdot d)</math>, которое растет линейно с размером батча и размерностью задачи, если есть достаточное количество процессоров <math>P</math>.

			* Сложности параллелизации: главная сложность заключается в информационной зависимости между последовательными шагами обновления. Параллельная реализация дает выигрыш только внутри одного шага (градиент и обновление), но не может ускорить последовательность шагов, что является фундаментальным ограничением SGD.
			====Вычислительная Мощность====
			* Общее число операций (за одну эпоху): <math>O(N \cdot d)</math>, где <math>N</math> — общее число объектов.
			* Объем входных данных (матрица <math>X</math>): <math>O(N \cdot d)</math>.
			* Объем выходных данных (вектор весов <math>w</math>): <math>O(d)</math>.

			<math>W_{comp} = \frac{\text{Число операций}}{\text{Объем входных данных}} = \frac{O(N \cdot d)}{O(N \cdot d + d)}</math>

			При больших <math>N</math> <math>N \cdot d</math> доминирует в знаменателе. Таким образом, вычислительная мощность SGD составляет:

			<math>W_{comp} \approx O(1)</math>

			Вычислительная мощность SGD близка к константе (<math>O(1)</math>). Это означает, что число операций примерно равно объему исходных данных. Это значение относительно невысокое. Это свойство требует, чтобы алгоритм выполнялся "близко" к памяти с данными (например, на том же узле кластера), чтобы минимизировать накладные расходы на перемещение данных.
			====Устойчивость Алгоритма====

			Алгоритм SGD является '''стохастическим и неустойчивым''' в смысле получения одного и того же результата при каждом запуске.

			* Неустойчивость к входным данным: поскольку SGD использует только часть данных (мини-батч) для каждого шага, дисперсия в оценке градиента высокая. Это приводит к флуктуациям в траектории сходимости.
			* Ошибка округления: при использовании массового параллелизма (например, при суммировании градиентов от <math>B</math> примеров) на системах с массовым параллелизмом порядок выполнения ассоциативных операций (сложение) может меняться от запуска к запуску. Это приводит к неповторяемости результатов работы параллельных программ, что является серьезной проблемой на практике.

			====Сбалансированность вычислительного процесса====

			Алгоритм обладает хорошей сбалансированностью с точки зрения распределения нагрузки.

			На каждой итерации преобладают арифметические операции (умножение и сложение) при вычислении градиента. Соотношение между арифметическими операциями и обращениями к памяти (чтение/запись) определяется параметром <math>B \cdot d</math>, который обычно достаточно велик, что обеспечивает эффективную работу процессоров.

			Распределение нагрузки по <math>P</math> процессам на этапе вычисления градиента достигается просто: каждый процессор обрабатывает <math>\lceil B/P \rceil</math> примеров. Это обеспечивает высокую балансировку нагрузки.

			====Детерминированность====
			Алгоритм SGD является недетерминированным по следующим причинам:

			1. Порядок обработки мини-батчей: в классическом SGD набор мини-батчей на каждой эпохе случаен, что меняет структуру вычислительного процесса и итоговый результат.
			2. Изменение порядка ассоциативных операций: как было описано выше, изменение порядка суммирования градиентов в параллельной среде приводит к непостоянству ошибок округления, что является причиной недетерминированности конечного результата в параллельной реализации.

			====Дополнительные свойства====

			* Степень исхода вершины: высока для вектора весов <math>w</math>. На каждом шаге <math>w</math> используется для вычисления градиента для всех <math>B</math> примеров. На этапе реализации это требует эффективной рассылки вектора <math>w</math> всем параллельным процессам/потокам, работающим над батчем, и эффективного доступа к нему.
			* "Длинные" дуги: типичные "длинные" дуги в информационном графе SGD возникают при рассылке скалярных величин (таких как learning rate <math>\alpha</math> или текущие веса <math>w</math>) по всем итерациям цикла мини-батчей. В случае вектора весов (<math>w</math>), это рассылка всего вектора. Поскольку этот паттерн (рассылка) хорошо изучен и оптимизирован на практике, он обычно не вызывает серьезных проблем с размещением данных в иерархии памяти, но требует эффективной коммуникации.

	==Литература==		==Литература==

OvsyannikovaSA: добавлено: ресурс параллелизма алгоритма, входные и выходные данные алгоритма

2025-12-08T22:05:39Z

добавлено: ресурс параллелизма алгоритма, входные и выходные данные алгоритма

@@ Строка 153: / Строка 153: @@
 [[file:Informational_graph_minibatch_SGD.png|thumb|center|Информационный граф стохастического градиентного спуска с мини-батчами]]
 Здесь приводится схема выполнения одной эпохи. Стрелки, изображающие обработку остальных объектов данного батча, опущены для улучшения читаемости схемы. После обработки одного батча с весами <math>w_i</math> производится шаг градиентного спуска, и следующий батч обрабатывается уже с весами <math>w_{i+1}</math>.
 ==Литература==

OvsyannikovaSA: /* Информационный граф */

2025-11-27T17:22:11Z

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

← Предыдущая версия		Версия от 17:22, 27 ноября 2025
Строка 151:		Строка 151:
	На схеме изображен информационный граф стохастического градиентного спуска с мини-батчами.		На схеме изображен информационный граф стохастического градиентного спуска с мини-батчами.

	[[file:~~Informational graph minibatch SGD~~.png\|thumb\|center\|Информационный граф стохастического градиентного спуска с мини-батчами]]		[[file:Informational_graph_minibatch_SGD.png\|thumb\|center\|Информационный граф стохастического градиентного спуска с мини-батчами]]
	Здесь приводится схема выполнения одной эпохи. Стрелки, изображающие обработку остальных объектов данного батча ~~и всех других батчей~~ опущены, ~~чтобы не перегружать схему~~.		Здесь приводится схема выполнения одной эпохи. Стрелки, изображающие обработку остальных объектов данного батча, опущены для улучшения читаемости схемы. После обработки одного батча с весами <math>w_i</math> производится шаг градиентного спуска, и следующий батч обрабатывается уже с весами <math>w_{i+1}</math>.

	==Литература==		==Литература==
	Yujing Ma, Florin Rusu, Martin Torres. Stochastic Gradient Descent on Highly-Parallel Architectures [Электронный ресурс] // arXiv:1802.08800 [math.ST]. – 2018. – Режим доступа: https://arxiv.org/abs/1802.08800		Yujing Ma, Florin Rusu, Martin Torres. Stochastic Gradient Descent on Highly-Parallel Architectures [Электронный ресурс] // arXiv:1802.08800 [math.ST]. – 2018. – Режим доступа: https://arxiv.org/abs/1802.08800

	Sebastian Ruder. An overview of gradient descent optimization algorithms [Электронный ресурс] // arXiv:1609.04747 [math.ST]. – 2016. – Режим доступа: https://arxiv.org/abs/1609.04747		Sebastian Ruder. An overview of gradient descent optimization algorithms [Электронный ресурс] // arXiv:1609.04747 [math.ST]. – 2016. – Режим доступа: https://arxiv.org/abs/1609.04747

OvsyannikovaSA: информационный граф

2025-11-27T17:17:34Z

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

← Предыдущая версия		Версия от 17:17, 27 ноября 2025
Строка 100:		Строка 100:

	w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)		w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)

			6. Проверка критерия останова: проверка условий завершения итерационного процесса. Может быть проверкой номера эпохи, проверкой изменения функции потерь и т.п.

			флаг_стоп ← ПроверкаКритерияОстановки(номер_эпохи, номер_шага, значение_критерия, история)

	На макроуровне алгоритм можно описать так:		На макроуровне алгоритм можно описать так:
			{\| class="wikitable" style="background:#f9f9f9; border:2px solid #ccc; width:100%;"
			\|+ '''Макроструктура алгоритма'''
			\|-
			\| <syntaxhighlight lang="pseudo">
			w ← ИнициализацияПараметров(описание_модели, стратегия_инициализации)
			номер_эпохи ← 0
			повторять
			номер_эпохи ← номер_эпохи + 1
			D_perm ← ПеремешиваниеОбучающейВыборки(D, генератор_случайных_чисел)
			СписокБатчей ← ФормированиеМиниБатчей(D_perm, размер_батча)
			Для каждого B из СписокБатчей:
			g_B ← ВычислениеГрадиентаНаБатче(w, B)
			w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)
			флаг_стоп ← ПроверкаКритерияОстановки(номер_эпохи, значение_критерия, история)
			Пока флаг_стоп = ЛОЖЬ
			</syntaxhighlight>
			\|}



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

	=== Информационный граф ===		=== Информационный граф ===
			На схеме изображен информационный граф стохастического градиентного спуска с мини-батчами.

			[[file:Informational graph minibatch SGD.png\|thumb\|center\|Информационный граф стохастического градиентного спуска с мини-батчами]]
			Здесь приводится схема выполнения одной эпохи. Стрелки, изображающие обработку остальных объектов данного батча и всех других батчей опущены, чтобы не перегружать схему.
	==Литература==		==Литература==
	Yujing Ma, Florin Rusu, Martin Torres. Stochastic Gradient Descent on Highly-Parallel Architectures [Электронный ресурс] // arXiv:1802.08800 [math.ST]. – 2018. – Режим доступа: https://arxiv.org/abs/1802.08800		Yujing Ma, Florin Rusu, Martin Torres. Stochastic Gradient Descent on Highly-Parallel Architectures [Электронный ресурс] // arXiv:1802.08800 [math.ST]. – 2018. – Режим доступа: https://arxiv.org/abs/1802.08800

	Sebastian Ruder. An overview of gradient descent optimization algorithms [Электронный ресурс] // arXiv:1609.04747 [math.ST]. – 2016. – Режим доступа: https://arxiv.org/abs/1609.04747		Sebastian Ruder. An overview of gradient descent optimization algorithms [Электронный ресурс] // arXiv:1609.04747 [math.ST]. – 2016. – Режим доступа: https://arxiv.org/abs/1609.04747

OvsyannikovaSA: /* Макроструктура алгоритма */

2025-11-27T12:44:11Z

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

← Предыдущая версия		Версия от 12:44, 27 ноября 2025
Строка 63:		Строка 63:

	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
			Алгоритм стохастического градиентного спуска с мини-батчами представляется повторением следующих макроопераций:

			1. Инициализация параметров: задание начального приближения вектора параметров модели <math>w_0</math>. Может быть случайной инициализацией, загрузкой предварительно обученной модели и т.п.

			w ← ИнициализацияПараметров(описание_модели, стратегия_инициализации)

			2. Перемешивание обучающей выборки: получение случайной перестановки обучающей выборки в начале эпохи. Можно выполнять, например, алгоритмом Фишера-Йетса.

			Входные данные: <math>D=\{(x_i, y_i)\}_{i=1}^N</math> - обучающая выборка.

			Выходные данные: <math>D_{perm}</math> - перемешанная выборка.

			D_perm ← ПеремешиваниеОбучающейВыборки(D, генератор_случайных_чисел)

			3. Формирование мини-батчей: разбиение переставленной выборки на последовательность мини-батчей.

			Входные данные: <math>D_{perm}</math>

			Выходные данные: последовательность подмножеств <math>B_k\subset D, \; k=1,..., K, \; \cup_k B_k=D, B_k \cap B_j = \emptyset, k\neq j</math>.

			СписокБатчей ← ФормированиеМиниБатчей((X,y)_perm, размер_батча)

			4. Вычисление градиента на батче. Может включать вычисление значений модели на батче, матрично-векторные умножения, суммирование по объектам батча.

			Входные данные: текущие параметры <math>w</math>, мини-батч <math>B=\{(x_i, y_i)\}_{i\in I_B}</math>

			Выходные данные: <math>g_B</math> - градиент по параметрам на этом батче.

			g_B ← ВычислениеГрадиентаНаБатче(w, B)

			5. Обновление параметров: осуществление одного шага метода по вычисленному градиенту на батче.

			Входные данные: текущие параметры <math>w</math>, градиент на батче <math>g_B</math>.

			Выходные данные: новые параметры <math>w_{new}=w-\alpha g_B</math>.

			w ← ОбновлениеПараметров(w, g_B, гиперпараметры_шага)

			На макроуровне алгоритм можно описать так:

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

OvsyannikovaSA: /* Схема реализации последовательного алгоритма */

2025-11-27T11:07:48Z

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

← Предыдущая версия		Версия от 11:07, 27 ноября 2025
Строка 65:		Строка 65:

	=== Схема реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
			[[Файл:Sequential SGD with mini-batches scheme.png\|мини\|Схема последовательной реализации стохастического градиентного спуска с мини-батчами]]

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

OvsyannikovaSA: исправлено мат. описание алгоритма

2025-11-23T15:24:43Z

исправлено мат. описание алгоритма

← Предыдущая версия		Версия от 15:24, 23 ноября 2025
Строка 52:		Строка 52:
	</syntaxhighlight>		</syntaxhighlight>
	\|}		\|}
	~~Часто случайный выбор батча заменяют на линейный проход по всем данным.~~ Преимущество алгоритма заключается в частом обновлении градиента и возможности использовать эффективные матричные вычисления.		Преимущество алгоритма заключается в частом обновлении градиента и возможности использовать эффективные матричные вычисления.
	В этой работе мы сосредоточимся на реализации градиентного спуска с мини-батчами.		В этой работе мы сосредоточимся на реализации градиентного спуска с мини-батчами.

			Необходимо некоторым способом определить условия, при которых будет считаться, что алгоритм сошелся. Будем считать, что сходимость достигается за <math>E</math> итераций обработки всей выборки (будем называть одну итерацию '''эпохой''').

			В начале каждой эпохи будем случайно перемешивать выборку, а затем последовательно выбирать порции данных по <math>n</math> объектов. Это обеспечит локальность расположения в памяти последовательно идущих мини-батчей и сохранит логику случайного выбора мини-батчей. Таким образом, процедура случайного выбора мини-батча заменяется на линейный проход по всем данным.

	===Вычислительное ядро алгоритма===		===Вычислительное ядро алгоритма===
	Основное время работы алгоритма приходится на ~~выбор мини-батча и~~ вычисление градиента, которые повторяются, пока сходимость не будет достигнута.		Основное время работы алгоритма приходится на вычисление градиента, которые повторяются, пока сходимость не будет достигнута.

	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
Строка 67:		Строка 71:
	<math>n</math> - размер батча (<math>batch\_size</math>),		<math>n</math> - размер батча (<math>batch\_size</math>),

	<math>C</math> - сложность вычисления производной функции потерь на одном примере.		<math>C</math> - сложность вычисления производной функции потерь на одном примере,

	~~Будем считать, что сходимость достигается за~~ <math>E</math> ~~итераций обработки всей выборки (будем называть одну итерацию эпохой)~~.		<math>E</math> - число эпох.
	~~В начале каждой эпохи~~ будем ~~случайно~~ перемешивать выборку, а затем последовательно выбирать порции данных по <math>n</math> объектов. Это обеспечит локальность расположения в ~~памяти последовательно идущих мини-батчей и сохранит логику случайного выбора мини-батчей~~. Сложность случайного перемешивания выборки объема <math>N</math> алгоритмом Фишера-Йетса - <math>O(N)</math>.
			Как уже упоминалось, будем перемешивать выборку случайным образом в начале каждой эпохи. Сложность случайного перемешивания выборки объема <math>N</math> алгоритмом Фишера-Йетса - <math>O(N)</math>. Если отказаться от этого предположения, можно считать, что сложность выбора <math>n</math> случайных элементов - <math>O(n)</math>. Такая оценка будет верна, если в системе реализован произвольный доступ к памяти. Однако для больших выборок, не помещающихся целиком в памяти, произвольный доступ к элементам выборки не будет возможен.

	Сложность обработки одного батча - <math>O(n \cdot C)</math>.		Сложность обработки одного батча - <math>O(n \cdot C)</math>.
Строка 78:		Строка 83:
	Сложность одной эпохи с учетом перемешивания выборки - <math>O(N)+O(N\cdot C)=O(N\cdot C)</math>.		Сложность одной эпохи с учетом перемешивания выборки - <math>O(N)+O(N\cdot C)=O(N\cdot C)</math>.

	Сложность всего алгоритма с <math>E</math> эпохами - <math>O(E\cdot N\cdot C)</math>		Сложность всего алгоритма с <math>E</math> эпохами - <math>O(E\cdot N\cdot C)</math>.

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


	==Литература==		==Литература==