Граф вычислений

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Статья написана с использованием LLM gemini 3.1 pro и проверена участником Oleg Aleksandrov 02:23, 14 июля 2026 (MSD)

Граф вычислений (англ. computational graph) — математическая абстракция, представляющая собой Ориентированный ациклический граф (англ. directed acyclic graph, DAG), в котором узлы (вершины) соответствуют математическим операциям или переменным, а направленные рёбра задают поток данных (как правило, Тензоров, англ. tensors) между ними.

В глубоком обучении графы вычислений служат алгоритмической базой для реализации автоматического дифференцирования (англ. automatic differentiation) и алгоритма обратного распространения ошибки (англ. backpropagation).

Содержание

1 Математическая формулировка
- 1.1 Прямой и обратный проходы
2 Применение в архитектурах машинного обучения
3 Ограничения и вычислительная сложность
- 3.1 Пространственная сложность и чекпоинтинг
- 3.2 Вычислительная неустойчивость
4 Альтернативы и сравнение подходов
5 Оптимизация: статические и динамические графы
6 Литература

Математическая формулировка

Граф вычислений определяется как ориентированный ациклический граф $G = (V, E)$ . Процесс вычисления функции $y = f(x_1, \dots, x_d)$ задаётся последовательностью промежуточных переменных $v_1, \dots, v_N$ :

Базовые переменные (входы графа): $v_i = x_i$ для $i = 1, \dots, d$ . В задачах ML это батчи входных данных, обучаемые веса модели и гиперпараметры.
Промежуточные узлы: $v_i = \phi_i(v_{Pa(i)})$ для $i = d+1, \dots, N$ , где $\phi_i$ — элементарная дифференцируемая операция, а $Pa(i)$ — множество узлов-родителей.
Выходной узел: $y = v_N$ . При обучении моделей это скалярная функция потерь (англ. loss function).

Прямой и обратный проходы

Прямой проход (Forward Pass) оценивает значения узлов $v_i$ в топологическом порядке от входов к выходу. Асимптотическая сложность прямого прохода составляет $O(|V| + |E|)$ .

Обратный проход (Backward Pass) вычисляет производные целевой переменной $y$ по каждому узлу графа. Вводится сопряженная переменная (англ. adjoint) $\bar{v}_i = \frac{\partial y}{\partial v_i}$ . Известно, что для выхода $\bar{v}_N = 1$ . Далее применяется многомерное Цепное правило (англ. chain rule) в обратном топологическом порядке: $\bar{v}_i = \sum_{j \in Ch(i)} \bar{v}_j \frac{\partial v_j}{\partial v_i}$ где $Ch(i)$ — дочерние узлы $v_i$ , а $\frac{\partial v_j}{\partial v_i}$ — Якобиан локальной операции.

Применение в архитектурах машинного обучения

Графы вычислений используются не только для базового обновления весов в сетях прямого распространения, но и определяют логику работы сложных архитектур:

Генеративно-состязательные сети (GAN): Требуют поддержки двух взаимодействующих графов — генератора и дискриминатора. При обновлении весов генератора градиенты протекают через граф дискриминатора, веса которого в этот момент аппаратно «заморожены» (например, через флаг `requires_grad=False`).
Мета-обучение (MAML): Алгоритмы Model-Agnostic Meta-Learning включают сам шаг градиентного спуска в граф вычислений. Это требует дифференцирования процесса обучения и вычисления производных высших порядков. Современные AD-системы строят вторичный граф поверх обратного прохода, вычисляя произведения Гессиана на вектор (Hessian-vector products) без явного формирования полной матрицы Гессе.
Мультиагентное обучение с подкреплением (MARL): В моделях с дифференцируемой коммуникацией агенты обмениваются непрерывными векторами сообщений. Ошибка от действий одного агента распространяется сквозь общий граф коммуникации, напрямую обновляя веса других агентов.
Модели диффузии (Diffusion Models): Граф описывает марковский процесс добавления и удаления шума, разворачивающийся на сотни временных шагов (time steps), что требует интеграции специализированных решателей SDE/ODE в систему автоматического дифференцирования.

Ограничения и вычислительная сложность

Практическое применение обратного режима AD сталкивается с аппаратными и математическими ограничениями.

Пространственная сложность и чекпоинтинг

Для вычисления производной обратный проход обращается к промежуточным активациям, сохранённым во время прямого прохода. Следовательно, потребление памяти растёт линейно с глубиной графа $O(N)$ . В больших языковых моделях (LLM) это вызывает исчерпание памяти ускорителей. Проблема решается методом контрольных точек градиента (англ. gradient checkpointing). В памяти фиксируются только ключевые узлы графа; промежуточные активации удаляются и перевычисляются «на лету» при обратном проходе. Это снижает затраты памяти до $O(\sqrt{N})$ за счёт увеличения времени вычислений примерно на 20–30%.

Вычислительная неустойчивость

В глубоких или развёрнутых во времени рекуррентных сетях последовательное умножение матриц Якоби приводит к затуханию (vanishing) или взрыву (exploding) градиентов. Для стабилизации графа применяются сквозные связи (skip connections, как в ResNet и Transformer), создающие короткие пути для градиентов в обход нелинейностей, а также усечение градиентов (gradient clipping) для предотвращения числового переполнения.

Альтернативы и сравнение подходов

Построение графа вычислений в машинном обучении (Reverse-mode AD) принято сравнивать с тремя другими методами вычисления производных.

Метод	Принцип	Преимущества	Ограничения в ML
Символьное дифференцирование	Алгебраическая манипуляция формулами (SymPy, Mathematica) для получения аналитического выражения.	Отсутствие ошибок округления.	Проблема экспоненциального разбухания (expression swell). Формула производной для глубокой сети не поместится в оперативную память. Сложность работы с ветвлениями.
Численное дифференцирование	Метод конечных разностей: $\frac{f(x+h) - f(x)}{h}$ .	Тривиальная реализация, используется для верификации (gradient checking).	Требует $O(d)$ вызовов функции, где $d$ — число параметров (достигает миллиардов). Высокая погрешность.
Прямой режим AD	Распространение производных вместе со значениями от входов к выходам через дуальные числа.	Константное потребление памяти (не требует сохранения активаций).	Вычисляет градиент только по одному входу за проход. Для функции потерь $f: \mathbb{R}^N \to \mathbb{R}$ требует $N$ проходов.
Обратный режим AD (Графы вычислений)	Прямой проход для вычисления активаций, обратный проход для вычисления градиентов.	Оценивает градиенты по всем $N$ параметрам за один обратный проход.	Требует $O(N)$ памяти для хранения промежуточных вычислений.

Оптимизация: статические и динамические графы

Исторически библиотеки глубокого обучения разделялись на использующие статические графы (Define-and-Run, например, TensorFlow 1.x, Theano) и динамические (Define-by-Run, например, PyTorch, Chainer). Современные фреймворки объединяют эти подходы: разработчик пишет код в императивном динамическом стиле, а JIT-компиляция (например, `torch.compile` или XLA) транслирует его в оптимизированный статический граф перед выполнением.

Ключевые методы низкоуровневой оптимизации графа:

Слияние операторов (Operator Fusion): Если в графе последовательно расположены узлы умножения матриц, сложения с вектором смещения и функции активации ReLU, компилятор объединяет их в одно специализированное ядро (kernel) для GPU. Это исключает накладные расходы на чтение и запись промежуточных тензоров в медленную глобальную память ускорителя (HBM).
Удаление мертвого кода (Dead Code Elimination): Топологический анализ графа выявляет подграфы, которые не влияют на целевую функцию потерь, и исключает их из вычислений.
Оптимизация пулов памяти (Memory Pooling): Анализируя жизненный цикл переменных в статическом графе, планировщик фреймворка переиспользует одни и те же адреса памяти для тензоров, не пересекающихся во времени.

Литература

Linnainmaa, S. Taylor expansion of the accumulated rounding error // BIT Numerical Mathematics. — 1976. — Т. 16. — № 2. — С. 146—160.
Rumelhart, D. E., Hinton, G. E., Williams, R. J. Learning representations by back-propagating errors // Nature. — 1986. — Т. 323. — С. 533—536.
Goodfellow, I., Bengio, Y., Courville, A. Deep Learning. — MIT Press, 2016. — ISBN 978-0262035613
Griewank, A., Walther, A. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, Second Edition. — SIAM, 2008. — ISBN 978-0-89871-659-7
Baydin, A. G., Pearlmutter, B. A., Radul, A. A., Siskind, J. M. Automatic Differentiation in Machine Learning: a Survey // Journal of Machine Learning Research. — 2018. — Т. 18. — № 153. — С. 1—43.
Abadi, M. et al. TensorFlow: A System for Large-Scale Machine Learning // 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). — 2016. — С. 265—283.
Paszke, A. et al. PyTorch: An Imperative Style, High-Performance Deep Learning Library // Advances in Neural Information Processing Systems 32 (NeurIPS). — 2019. — С. 8024—8035.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%93%D1%80%D0%B0%D1%84_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9»

Версия 21:58, 13 июля 2026 (править) Oleg Aleksandrov (Обсуждение \| вклад) (Новая: '''Граф вычислений''' (англ. computational graph) — математическая абстракция, представляющая собой [[Ориентиров...) ← К предыдущему изменению		Текущая версия (22:23, 13 июля 2026) (править) (отменить) Oleg Aleksandrov (Обсуждение \| вклад)
Строка 1:		Строка 1:
		+	{{well\|Статья написана с использованием LLM '''gemini 3.1 pro''' и проверена участником [[Участник:Oleg Aleksandrov\|Oleg Aleksandrov]] 02:23, 14 июля 2026 (MSD)}}
		+
	'''Граф вычислений''' (англ. computational graph) — математическая абстракция, представляющая собой [[Ориентированный ациклический граф]] (англ. directed acyclic graph, DAG), в котором узлы (вершины) соответствуют математическим операциям или переменным, а направленные рёбра задают поток данных (как правило, [[Тензор]]ов, англ. tensors) между ними.		'''Граф вычислений''' (англ. computational graph) — математическая абстракция, представляющая собой [[Ориентированный ациклический граф]] (англ. directed acyclic graph, DAG), в котором узлы (вершины) соответствуют математическим операциям или переменным, а направленные рёбра задают поток данных (как правило, [[Тензор]]ов, англ. tensors) между ними.