Участник:Margarita/Градиентный спуск - История изменений

Margarita: /* Масштабируемость алгоритма и его реализации */

2017-11-30T10:11:17Z

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

← Предыдущая версия		Версия от 10:11, 30 ноября 2017
Строка 105:		Строка 105:
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===

	В качестве примера рассмотрим функцию <math>f(x) = \langle x,x \rangle</math>, где <math>x = (x_1, \ldots, x_n)</math>. Будем изменять размерность пространства от <math>2^{14}</math> до <math>2^{18}</math>, а число процессоров от <math>2</math> до <math>128</math>.		В качестве примера рассмотрим функцию <math>f(x) = \langle x,x \rangle</math>, где <math>x = (x_1, \ldots, x_n)</math>. Коэффициент <math>\alpha_k</math> будем вычислять по следующему правилу: <math>\alpha_k = \frac{1}{2}\alpha_{k-1}</math>.

			Будем изменять размерность пространства от <math>2^{14}</math> до <math>2^{18}</math>, а число процессоров от <math>2</math> до <math>128</math>.

	[[file:Gradscale.png\|thumb\|center\|700px\|Масштабируемость алгоритма]]		[[file:Gradscale.png\|thumb\|center\|700px\|Масштабируемость алгоритма]]

Margarita: /* Масштабируемость алгоритма и его реализации */

2017-11-30T09:27:25Z

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

← Предыдущая версия		Версия от 09:27, 30 ноября 2017
Строка 104:		Строка 104:

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

			В качестве примера рассмотрим функцию <math>f(x) = \langle x,x \rangle</math>, где <math>x = (x_1, \ldots, x_n)</math>. Будем изменять размерность пространства от <math>2^{14}</math> до <math>2^{18}</math>, а число процессоров от <math>2</math> до <math>128</math>.

	[[file:Gradscale.png\|thumb\|center\|700px\|Масштабируемость алгоритма]]		[[file:Gradscale.png\|thumb\|center\|700px\|Масштабируемость алгоритма]]

			Из графика видно, что время работы программы обратно пропорционально числу процессоров, что согласуется с теоретическими результатами.

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

Margarita: /* Последовательная сложность алгоритма */

2017-11-30T09:01:21Z

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

← Предыдущая версия		Версия от 09:01, 30 ноября 2017
Строка 61:		Строка 61:
	</math>		</math>

	для этого потребуется <math>n</math> делений, где <math>n</math> — размерность пространства.		для этого потребуется <math>n</math> делений, где <math>n</math> — размерность пространства.
	Пусть сложность вычисления коэффициента <math>\alpha_{k}</math> равна <math>p_{\alpha}</math>. Умножение <math>\alpha_{k} \nabla f(x_0)</math> даёт ещё <math>n</math> умножений. В итоге получаем:		Пусть сложность вычисления коэффициента <math>\alpha_{k}</math> равна <math>p_{\alpha}</math>, а сложность вычисления функции <math>p_{f}</math>. Умножение <math>\alpha_{k} \nabla f(x_0)</math> даёт ещё <math>n</math> умножений. В итоге получаем:
	:<math>		:<math>
	\begin{align}		\begin{align}
	P(n, p_{\alpha}) = 2n + p_{\alpha}.		P(n, p_{\alpha}, p_{f}) = 2n + p_{\alpha} +2p_{f},
	\end{align}		\end{align}
	</math>		</math>
			где <math>f = f(n)</math>.

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

Margarita: /* Масштабируемость алгоритма и его реализации */

2017-11-30T08:45:07Z

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

← Предыдущая версия		Версия от 08:45, 30 ноября 2017
Строка 104:		Строка 104:
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===

	[[file:Gradscale.png\|thumb\|center\|700px\|~~Рисунок 2.~~ Масштабируемость алгоритма]]		[[file:Gradscale.png\|thumb\|center\|700px\|Масштабируемость алгоритма]]

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

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

2017-11-30T08:44:56Z

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

← Предыдущая версия		Версия от 08:44, 30 ноября 2017
Строка 71:		Строка 71:
	=== Информационный граф ===		=== Информационный граф ===

	[[file: InfoGr.png\|thumb\|center\|700px\|~~Рисунок 1.~~ Информационный граф.]]		[[file: InfoGr.png\|thumb\|center\|700px\|Информационный граф.]]

	Синие вершины графа — итерационное вычисление последовательности <math>x_{k-1}, x_k, x_{k+1}</math>.		Синие вершины графа — итерационное вычисление последовательности <math>x_{k-1}, x_k, x_{k+1}</math>.

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

2017-11-30T08:44:37Z

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

← Предыдущая версия		Версия от 08:44, 30 ноября 2017
Строка 71:		Строка 71:
	=== Информационный граф ===		=== Информационный граф ===

	[[file: InfoGr.png\|~~400px~~]]		[[file: InfoGr.png\|thumb\|center\|700px\|Рисунок 1. Информационный граф.]]

	Синие вершины графа — итерационное вычисление последовательности <math>x_{k-1}, x_k, x_{k+1}</math>.		Синие вершины графа — итерационное вычисление последовательности <math>x_{k-1}, x_k, x_{k+1}</math>.

Margarita: /* Масштабируемость алгоритма и его реализации */

2017-11-30T08:43:56Z

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

← Предыдущая версия		Версия от 08:43, 30 ноября 2017
Строка 103:		Строка 103:

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

			[[file:Gradscale.png\|thumb\|center\|700px\|Рисунок 2. Масштабируемость алгоритма]]

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

Margarita: /* Общее описание алгоритма */

2017-11-29T18:55:54Z

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

← Предыдущая версия		Версия от 18:55, 29 ноября 2017
Строка 17:		Строка 17:
	Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.		Градиентный спуск — это метод нахождения локального экстремума функции с помощью движения вдоль направления градиента. На каждой итерации для минимизации функции в направлении градиента используются методы одномерной оптимизации.

	Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки ~~путем~~ минимизации функции цены.		Градиентный спуск активно применяется в области машинного обучения, так как часть процесса машинного обучения — это поиск максимальной точности или минимизация частоты ошибок. Метод градиентного спуска используется для поиска минимальной ошибки путём минимизации функции цены.

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

Margarita: /* Последовательная сложность алгоритма */

2017-11-29T18:21:07Z

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

← Предыдущая версия		Версия от 18:21, 29 ноября 2017
Строка 57:		Строка 57:
	:<math>		:<math>
	\begin{align}		\begin{align}
	f'(x_0) ≈ \frac{f(x_0) - f(x_0 ~~+ \delta~~) )}{\delta},		f'(x_0) ≈ \frac{f(x_0 + \delta) - f(x_0))}{\delta},
	\end{align}		\end{align}
	</math>		</math>
Строка 68:		Строка 68:
	\end{align}		\end{align}
	</math>		</math>

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

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

2017-11-29T18:20:15Z

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

← Предыдущая версия		Версия от 18:20, 29 ноября 2017
Строка 73:		Строка 73:
	[[file: InfoGr.png\|400px]]		[[file: InfoGr.png\|400px]]

	Синие вершины графа — ~~последовательные значения~~ <math>x_{k-1}, x_k, x_{k+1}</math>.		Синие вершины графа — итерационное вычисление последовательности <math>x_{k-1}, x_k, x_{k+1}</math>.

	Зелёные вершины графа — численное вычисление частных производных.		Зелёные вершины графа — численное вычисление частных производных.