Санкт-Петербургский государственный университет
Математическое обеспечение и администрирование информационных
систем
Информационные системы и базы данных
Назаренко Владимир Владимирович
Эффективная параллельная реализация нейронной
сети
Бакалаврская работа
Научный руководитель:
ст. преп. Ярыгина А. С.
Рецензент:
ст. преп. Немешев М. Х.
Санкт-Петербург
2016
SAINT-PETERSBURG STATE UNIVERSITY
Software and Administration of Information Systems
Information Systems and Databases
Vladimir Nazarenko
Efficient parallel implementation of neural network
Bachelor’s Thesis
Scientific supervisor:
Senior Assistant Professor Anna Yarygina
Reviewer:
Senior Assistant Professor Marat Nemeshev
Saint-Petersburg
2016
Содержание
1 Введение
2 Постановка задачи
3 Обзор используемых понятий
3.1
3.2
3.3
3.4
Рекуррентная нейронная сеть . . . . . . .
Целевые функции . . . . . . . . . . . . .
Алгоритмы оптимизации . . . . . . . . .
3.3.1 Градиентный спуск . . . . . . . . .
3.3.2 Расширенный фильтр Калмана . .
3.3.3 Алгоритм l-BFGS . . . . . . . . . .
Вычисление градиента целевой функции
3.4.1 Обратное распространение ошибки
3.4.2 Рекуррентное обучение в реальном
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
сквозь время
времени . . .
4 Платформа для параллельных вычислений CUDA
5 Существующие реализации
5.1
5.2
5.3
5.4
5.5
CURRENNT . . . . . . . . .
Реализация Michal Cernansky
Caffe . . . . . . . . . . . . . .
Nvidia CuDNN . . . . . . . .
Microsoft CNTK . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
3
3
3
5
7
8
8
8
9
9
11
12
12
13
14
14
14
14
6 Реализация
7 Эксперименты
14
15
8 Заключение
9 Приложение
19
23
7.1
7.2
Сравнение скорости тренировки . . . . . . . . . . . . . . . .
Сравнение качества тренировки . . . . . . . . . . . . . . . .
1
16
18
1
Введение
В настоящее время нейронные сети используются в широком спектре задач от распознавания текста на изображениях до детектирования частиц в
коллайдерах[1]. Такая универсальность возможна благодаря свойству нейронной сети инкапсулировать нелинейные зависимости и наличию эффективных алгоритмов тренировки нейронной сети.
Одно из ключевых свойств нейронной сети это тип связи между её нейронами; различают:
∙ Сети прямого распространения (простой перцептрон, свёрточные нейронные сети)[2],
∙ Рекуррентные нейронные сети[3],
∙ Самоорганизующиеся карты[4] и другие.
В данной работе рассматриваются только рекуррентные нейронные сети с двумя вариантами рекуррентных слоёв: простой рекуррентный слой
и слой LSTM(long short-term memory). Рекуррентные нейронные сети за
счёт наличия связей между нейронами скрытого слоя могут превосходить
сети прямого распространения в качестве работы, что и наблюдается на
некоторых классах задач[5, 6]. Как правило, рекуррентные нейронные сети выигрывают у сетей прямого распространения в случае, когда данные
получены из какого-либо последовательного процесса, что имеет место в
задачах распознавания речи, автоматического перевода и генерации текста.
Тем не менее рекуррентные сети сложнее в применении, так как обычно
требуют большего количества тренировочных данных и имеют более сложную структуру, что в том числе влечёт серьёзное увеличение времени, необходимого для обучения по сравнению с сетями прямого распространения.
Кроме того, структура рекуррентных сетей задаёт некоторые ограничения
на распараллеливание в связи наличием рекуррентных связей в слоях[7],
но не исключает его.
Так как в процессе тренировки и использования натренированной нейронной сети интенсивно используются операции над матрицами и векторами, эти процессы могут быть существенно ускорены с использованием
графического процессора (GPU) для вычислений, в частности с использованием платформы Nvidia CUDA[8], для которой такие операции имеют
эффективные массово-параллельные реализации, что и продемонстрировано в работах[9, 10].
На сегодняшний день количество публично доступных параллельных
реализаций рекуррентных нейронных сетей невелико[11, 7, 12, 13, 14], при
этом исходный код некоторых из них закрыт.
2
2
Постановка задачи
В рамках работы были поставлены следующие задачи:
∙ рассмотрение и сравнение существующих параллельных реализаций
рекуррентных нейронных сетей,
∙ выделение плюсов и минусов реализаций, их систематизация,
∙ параллельная реализация нейронной сети, учитывающая достоинства
и недостатки предыдущих реализаций.
3
Обзор используемых понятий
В задаче обучения с учителем для того, чтобы модель, и в частности нейронная сеть, была практически полезной, то есть аппроксимировала какуюто функциональную зависимость из реального мира, её необходимо тренировать, то есть выбирать оптимальные параметры на основе имеющихся
данных.
Организация процесса тренировки требует принятия нескольких решений, существенно влияющих на время, необходимое для тренировки, и качество полученных результатов, а именно:
∙ выбор целевой функции,
∙ выбор алгоритма оптимизации,
∙ выбор алгоритма вычисления градиента целевой функции.
Далее мы сначала дадим общее определение рекуррентной нейронной
сети, затем представим некоторые альтернативные возможности выбора
элементов реализации рекуррентной нейронной сети и её тренировки. Для
простоты определений, все понятия будем давать для нейронной сети, решающей задачу классификации. Тем не менее определения легко переформулировать, например, для задачи регрессионного анализа.
3.1 Рекуррентная нейронная сеть
Рекуррентная нейронная сеть это нейронная сеть, хотя бы в одном слое
которой присутствуют рекуррентные связи, то есть связи между нейронами
одного и того же слоя. Такие слои естественно называть рекуррентными.
Как и любая нейронная сеть, рекуррентная нейронная сеть может состоять из практически любой комбинации слоёв, где активации предыдущего слоя являются входными данными для последующего слоя.
3
Далее рассмотрим простой рекуррентный слой (SRL), в котором каждый нейрон имеет в точности одну связь с собой.
Существуют и другие разновидности рекуррентных слоёв, из которых
наиболее часто используется LSTM-слой. Описывать его в этой работе мы
не будем, читатель может найти информацию о нём в работе[15]. Далее
под рекуррентным слоем будем понимать либо простой рекуррентный слой,
либо LSTM-слой.
Также часто используются двунаправленные слои. Так как суть рассуждений для двунаправленных слоёв остаётся такой же, как и для однонаправленных, мы не будем давать определение двунаправленных слоёв, а
лишь сошлёмся на работу[16].
В отличие от нейронной сети прямого распространения рекуррентная
нейронная сеть работает не с парой значений вида (входное значение, выходное значение), а с временным рядом, представляющими собой последовательность значений вида (входное значение, выходное значение, индекс
элемента в последовательности), где индекс элемента в последовательности
– целочисленное неотрицательное значение, которое можно интерпретировать как дискретное время. Формально, тренировочная последовательность имеет вид (𝑥, 𝑦), где
∙ 𝑥 = [𝑥(0), . . . , 𝑥(𝑇 )], 𝑥(𝑡) – вектор признаков,
∙ 𝑦 = [𝑦(0), . . . , 𝑦(𝑇 )], 𝑦(𝑡) = [𝑦1 (𝑡) . . . 𝑦𝑁 (𝑡)],
где 𝑦𝑘 (𝑡) = 1 и ∀𝑗 ̸= 𝑘 (𝑦𝑗 (𝑡) = 0), где 𝑘 – номер класса, которому
соответствует набор признаков 𝑥(𝑡),
∙ 𝑇 – длина последовательности, 𝑡 – индекс последовательности, время.
Далее для примера рассмотрим рекуррентную нейронную сеть Элмана. Если не оговорено иное, то под рекуррентной нейронной сетью будем
понимать именно рекуррентную сеть Элмана. Тем не менее все последующие рассуждения с некоторыми дополнениями применимы и для более
сложных рекуррентных нейронных сетей.
Нейронная сеть Элмана
Нейронная сеть Элмана, или простой рекуррентный перцептрон, – это одна
из простейших конфигураций рекуррентной нейронной сети, состоящая из
трёх слоёв:
∙ входной слой,
∙ простой рекуррентный слой,
∙ выходной слой.
4
Задаётся такая сеть следующими соотношениями (с использованием
обозначений из таблицы 1)[17]:
𝑛𝑒𝑡(1) (𝑡) = 𝑉 𝑥(𝑡) + 𝑈 𝑠(𝑡 − 1),
(3.1.1)
𝑠(𝑡) = 𝑓 (𝑛𝑒𝑡(1) (𝑡)),
(3.1.2)
𝑛𝑒𝑡(2) (𝑡) = 𝑊 𝑠(𝑡),
(3.1.3)
𝑜(𝑡) = 𝑔(𝑛𝑒𝑡(2) (𝑡)).
(3.1.4)
Обозначим также за ℎ𝜔 (𝑥, 𝑡) = 𝑜(𝑡) активации выходного слоя на шаге 𝑡 рекуррентной нейронной сети при условии, что 𝑥 – входная последовательность при конкретном значении 𝜔 = (𝑈, 𝑉, 𝑊 ). Также обозначим
ℎ𝜔 (𝑥) = [ℎ𝜔 (0, 𝑥) . . . ℎ𝜔 (𝑇, 𝑥)].
Таблица 1: Основные обозначения
Символ
Значение
𝑡
Индекс элемента последовательности (время)
𝑓, 𝑔
Функции активации
𝑥(𝑡)
Входной вектор размерности N
𝑠(𝑡)
Вектор скрытого слоя размерности M
𝑜(𝑡)
Вектор выходного слоя размерности K
𝑉 ∈ [𝑀 × 𝑁 ],
Матрицы
𝑈 ∈ [𝑀 × 𝑀 ],
весов
𝑊 ∈ [𝐾 × 𝑀 ]
На рис.1 и рис.2 можно видеть схематичное изображение рекуррентной
сети и так называемое "развёрнутое" изображение нейронной сети.
3.2 Целевые функции
Целевая функция это вещественнозначная, имеющая непрерывную производную функция 𝑄(𝜔, 𝑥, 𝑦) = 𝑙(ℎ𝜔 (𝑥), 𝑦). При правильном выборе целевой
функции задача тренировки нейронной сети сводится к задаче оптимизации целевой функции. Вариантов выбора отображения 𝑙 существует очень
много и разные целевые функции зачастую приводят к разным результатам, более того, некоторые целевые функции ориентированы на специальные классы задач. Приведём некоторые примеры.
5
x(t)
y(t)
s(t)
V
W
U
s(t-1)
Рис. 1: Схема рекуррентной нейронной сети
Среднеквадратичное отклонение (MSE)
Среднеквадратичное отклонение – это одна из наиболее часто используемых целевых функций в задачах линейной регрессии. Выглядит она следующим образом:
𝑇
1 ∑︁
𝑙(ℎ𝜔 (𝑥), 𝑦) =
||ℎ𝜔 (𝑥, 𝑡) − 𝑦(𝑡)||2 .
𝑇 1
Перекрёстная энтропия (cross-entropy loss)
Перекрёстная энтропия – одна из простейших целевых функций, используемых при решении задач классификации. Задаётся она следующим выражением:
𝑇
1 ∑︁
𝑙(ℎ𝜔 (𝑥), 𝑦) =
< 𝑦(𝑡), log ℎ𝜔 (𝑥, 𝑡) > .
𝑇 1
Связанная временная классификация
Более сложным примером целевой функции является связанная временная
классификация (CTC)[18], используемая, например, в распознавании речи
и символьных последовательностей.
Предположим, что мы выполняем на последовательности классификацию среди 𝑛 классов. При решении задачи распознавания речи это может
быть, например, разметка звуковой дорожки на произнесённые буквы в
каждом интервале. Выходной слой в таком случае представляет собой 𝑛
6
нейронов, каждый из которых соответствует отдельному классу. В выходной слой нейронной сети добавим ещё один нейрон – он будет соответствовать паузе. В качестве функции активации выходного слоя для нормализации рекомендуется использовать softmax, тогда мы можем говорить о
вероятностях
𝑒𝑥𝑝(ℎ𝜔 (𝑥, 𝑡)𝑘 )
,
𝑃 𝑟(𝑘, 𝑡|𝑥) = ∑︀
𝑘 ′ 𝑒𝑥𝑝(ℎ𝜔 (𝑥, 𝑡)𝑘 ′ )
где 𝑘 – класс, 𝑥 – входная последовательность, 𝑡, как и ранее, индекс
временного шага.
CTC-разметка 𝑎 – это последовательность длины 𝑇 из символов и пауз.
Тогда вероятность, что входной последовательности будет соответствовать
конкретная разметка, примем равной
𝑃 𝑟(𝑎|𝑥) =
𝑇
∏︁
𝑃 𝑟(𝑎𝑡 , 𝑡|𝑥),
𝑡=1
считая, что вероятности появления символов в строке независимы.
Далее предположим, что у нас в тренировочном множестве каждой
входной последовательности 𝑥 соответствует её транскрипция (строка) 𝑦 * .
По этой строке мы генерируем все возможные разметки. Например, строке
abc при 𝑇 = 5 могут соответствовать разметки (a, -, b, c, -), (a, -, -, b, c) и
другие, где “-” – пауза. Обозначим как a(𝑦 * ) оператор, генерирующий все
возможные разметки по транскрипции.
Тогда можем вычислить
*
𝑃 𝑟(𝑦 |𝑥) =
∑︁
𝑃 𝑟(𝑎|𝑥).
𝑎∈a(𝑦 * )
Целевой функцией будет являться
𝑙(ℎ𝜔 (𝑥), 𝑦 * ) = −𝑙𝑜𝑔𝑃 𝑟(𝑦 * |𝑥).
3.3 Алгоритмы оптимизации
Пусть Ψ : |Ψ| = 𝑆 – тренировочное множество, т.е. набор тренировочных
последовательностей. Рассмотрим среднее значение функции ошибки на
тренировочном
если принять веса нейронной сети равными 𝜔 ,
∑︀𝑆 множестве,
1
𝑖 𝑖
𝐿(𝜔) = 𝑛 𝑖=1 𝑄(𝜔, 𝑥 , 𝑦 ). Получаем составную целевую функцию, которую и будем минимизировать.
Также нам потребуется вычислять ∇𝐿(𝜔), для этого можно использовать как BPTT(3.4.1), так и RTRL-алгоритм(3.4.2).
7
3.3.1 Градиентный спуск
Градиентный спуск и его модификации на сегодняшний день чаще всего
применяется для тренировки рекуррентных нейронных сетей в виду простоты реализации, низкой вычислительной сложности и эффективности
некоторых модификаций. В листингах 1,2 и 3 (в приложении) приведены
некоторые часто используемые варианты градиентного спуска.
3.3.2 Расширенный фильтр Калмана
Фильтр Калмана это относительно давно известная техника оптимизации
линейных динамических систем. В работе[11] и предшествующих ей работах Michal Cernansky предпринята попытка расширить понятие фильтра Калмана и применить его к обучению рекуррентных нейронных сетей.
Описание алгоритма представлено в листинге 4.
3.3.3 Алгоритм l-BFGS
Алгоритм l-BFGS (limited-memory Broyden – Fletcher – Goldfarb – Shanno
algorithm)[19] является приближением алгоритма BFGS с линейной относительно длины входных данных асимптотикой используемой памяти.
Введём некоторые обозначения:
𝜔𝑘 – вектор, содержащий в себе все веса нейронной сети на 𝑘 -м шаге
алгоритма.
𝑠𝑘 = 𝜔𝑘+1 − 𝜔𝑘
𝑦𝑘 = ∇𝐿(𝜔𝑘+1 ) − ∇𝐿(𝜔𝑘 )
𝜌𝑘 =
1
𝑦𝑘𝑇 𝑠𝑘
Данный алгоритм относится к квази-линейным. Он не только учитывает производную целевой функции, но и аппроксимирует её гессиан, что
приводит к ускорению сходимости. Псевдокод алгоритма представлен в листинге 5.
Кроме того, одной из важных частей алгоритма является линейный поиск, который должен опираться на условия Вольфе[19]. Один из примеров
такого линейного поиска представлен в листинге 6.
8
3.4 Вычисление градиента целевой функции
3.4.1 Обратное распространение ошибки сквозь время
Одним из наиболее часто используемых методов вычисления градиента
функции ошибки является так называемый метод обратного распространения ошибки сквозь время (BPTT). Суть метода в том, что мы "разворачиваем" рекуррентную сеть и считаем градиенты с помощью обычного
метода распространения ошибки.
o(t)
o(1)
o(2)
o(3)
o(t)
hidden
layer
hidden
layer
hidden
layer
hidden
layer
hidden
layer
x(t)
x(1)
x(2)
x(3)
x(t)
Рис. 2: "Развёрнутая" нейронная сеть
Ниже представлены вычисления градиентов функции ошибок от матриц параметров.
Используя цепное правило, получаем:
𝜕𝑜(𝑡)
𝜕𝑜(𝑡) 𝜕𝑛𝑒𝑡(2) (𝑡)
=
,
𝜕𝑤𝑖𝑗
𝜕𝑛𝑒𝑡(2) (𝑡) 𝜕𝑤𝑖𝑗
(3.4.1)
𝜕𝑜(𝑡)
𝜕𝑜(𝑡) 𝜕𝑛𝑒𝑡(2) (𝑡) 𝜕𝑠(𝑡)
=
,
𝜕𝑣𝑖𝑗
𝜕𝑛𝑒𝑡(2) (𝑡) 𝜕𝑠(𝑡) 𝜕𝑣𝑖𝑗
(3.4.2)
𝜕𝑜(𝑡)
𝜕𝑜(𝑡) 𝜕𝑛𝑒𝑡(2) (𝑡) 𝜕𝑠(𝑡)
=
.
𝜕𝑢𝑖𝑗
𝜕𝑛𝑒𝑡(2) (𝑡) 𝜕𝑠(𝑡) 𝜕𝑢𝑖𝑗
(3.4.3)
Согласно 3.1.3, 3.1.4:
⎤
∇𝑔1
𝜕𝑜(𝑡)
= 𝐽𝑔 (𝑛𝑒𝑡(2) (𝑡)) = ⎣ ... ⎦ (𝑛𝑒𝑡(2) (𝑡)),
(2)
𝜕𝑛𝑒𝑡 (𝑡)
∇𝑔𝑁
⎡
⎤
0
⎢ .. ⎥
. ⎥
𝜕𝑛𝑒𝑡(2) (𝑡) ⎢
⎢
⎥
= ⎢𝑠𝑗 (𝑡)⎥ ← (𝑖).
⎢ .. ⎥
𝜕𝑤𝑖𝑗
⎣ . ⎦
0
⎡
Таким образом, 3.4.4 и 3.4.5 влекут
9
(3.4.4)
(3.4.5)
[︁
]︁
𝜕𝑜(𝑡)
(2)
(2)
′
′
= 𝑠𝑗 (𝑡) 𝑔1 (𝑛𝑒𝑡𝑖 (𝑡)) . . . 𝑔𝑛 (𝑛𝑒𝑡𝑖 (𝑡)) .
𝜕𝑤𝑖𝑗
Из 3.1.3 очевидно следует
𝜕𝑛𝑒𝑡(2) (𝑡)
= 𝑊.
𝜕𝑠(𝑡)
Используя предыдущие тождества, введём обозначение
𝜕𝑜(𝑡) 𝜕𝑛𝑒𝑡(2) (𝑡)
𝛿(𝑡) =
= 𝐽𝑔 (𝑛𝑒𝑡(2) (𝑡))𝑊.
(2)
𝜕𝑛𝑒𝑡 (𝑡) 𝜕𝑠(𝑡)
Тогда 3.4.2 и 3.4.3 можно переписать в виде
𝜕𝑠(𝑡)
𝜕𝑜(𝑡)
= 𝛿(𝑡)
,
𝜕𝑣𝑖𝑗
𝜕𝑣𝑖𝑗
𝜕𝑜(𝑡)
𝜕𝑠(𝑡)
= 𝛿(𝑡)
.
𝜕𝑢𝑖𝑗
𝜕𝑢𝑖𝑗
Снова используя цепное правило, получаем:
(3.4.6)
(3.4.7)
(3.4.8)
(3.4.9)
(3.4.10)
𝑡
𝜕𝑠(𝑡) ∑︁ 𝜕𝑠(𝑡) 𝜕𝑠(𝑡 − 𝜏 )
=
,
𝜕𝑣𝑖𝑗
𝜕𝑠(𝑡
−
𝜏
)
𝜕𝑣
𝑖𝑗
𝜏 =0
(3.4.11)
𝜕𝑠(𝑡)
= 𝐽𝑓 (𝑛𝑒𝑡(1) (𝑡))𝑈 * · · · * 𝐽𝑓 (𝑛𝑒𝑡(1) (𝑡 − 𝜏 + 1))𝑈 ∀𝜏 > 0, (3.4.12)
𝜕𝑠(𝑡 − 𝜏 )
⎡
⎤
0
⎢
..
⎥
.
⎢
⎥
𝜕𝑠(𝑡 − 𝜏 )
⎢
⎥
(1)
= 𝐽𝑓 (𝑛𝑒𝑡 (𝑡 − 𝜏 )) ⎢𝑥𝑗 (𝑡 − 𝜏 )⎥ ← (𝑖).
(3.4.13)
⎢
⎥
𝜕𝑣𝑖𝑗
.
..
⎣
⎦
0
Аналогично,
𝑡
𝜕𝑠(𝑡) ∑︁ 𝜕𝑠(𝑡) 𝜕𝑠(𝑡 − 𝜏 )
=
,
𝜕𝑢𝑖𝑗
𝜕𝑠(𝑡
−
𝜏
)
𝜕𝑢
𝑖𝑗
𝜏 =0
⎡
⎤
0
⎢
..
⎥
.
⎢
⎥
𝜕𝑠(𝑡 − 𝜏 )
⎢
⎥
(1)
= 𝐽𝑓 (𝑛𝑒𝑡 (𝑡 − 𝜏 )) ⎢𝑠𝑗 (𝑡 − 𝜏 − 1)⎥ ← (𝑖).
⎢
⎥
𝜕𝑢𝑖𝑗
..
⎣
⎦
.
0
10
(3.4.14)
(3.4.15)
3.4.2 Рекуррентное обучение в реальном времени
Для простоты рассмотрим ещё более простую рекуррентную нейронную
сеть – сеть Элмана без выходного слоя, то есть активациями выходного
слоя в такой сети будут являться активации скрытого слоя.
Оставшиеся матрицы весов, (𝑈, 𝑉 ) соберём в одну матрицу Ω ∈ [𝑀, 𝑁 +
𝑀 ]. Рекуррентное обучение в реальном времени (RTRL) основывается на
несколько ином взгляде на рекуррентную нейронную сеть. Во-первых, объединим весовые матрицы из таб.1 в одну – Ω ∈ [𝑀, 𝑁 + 𝑀 + 𝐾]. Также
обозначим 𝑧(𝑡) = [𝑥(𝑡), 𝑠(𝑡)]. Введём множества индексов 𝐼, 𝐽 и проиндексируем ими соответственно 𝑥(𝑡), 𝑠(𝑡). Тогда такую сеть можно описать двумя
выражениями:
𝑛𝑒𝑡(𝑡) = Ω𝑧(𝑡),
(3.4.16)
(3.4.17)
𝑜(𝑡 + 1) = 𝑓 (𝑛𝑒𝑡(𝑡)).
На этапе тренировки нейронной сети для некоторых активаций, а именно
активаций выходного слоя у нас заданы целевые значения 𝑑𝑘 (𝑡).
Продифференцируем выходы сети по весам:
𝜕𝑜𝑘 (𝑡 + 1)
= 𝑓𝑘′ (𝑛𝑒𝑡𝑘 (𝑡))
𝜕𝜔𝑖𝑗
[︃
]︃
∑︁
𝑙∈𝑈 ∪𝐼
𝜔𝑘𝑙
𝜕𝑧𝑙 (𝑡)
+ 𝛿𝑖𝑘 𝑧𝑗 (𝑡) .
𝜕𝜔𝑖𝑗
(3.4.18)
Так как входные активации не зависят от весов,
𝜕𝑧𝑙 (𝑡)
= 0 ∀𝑙 ∈ 𝐼.
(3.4.19)
𝜕𝜔𝑖𝑗
Также можем считать, что данные в начальный момент времени не
зависят от весов, то есть
𝜕𝑜𝑘 (0)
= 0.
(3.4.20)
𝜕𝜔𝑖𝑗
Используя выражение 3.4.20 как базу рекурсии на основании выражений 3.4.18, 3.4.19 получаем рекуррентную формулу:
[︃
]︃
∑︁
𝜕𝑜𝑘 (𝑡 + 1)
𝜕𝑜𝑙 (𝑡)
= 𝑓𝑘′ (𝑛𝑒𝑡𝑘 (𝑡))
𝜔𝑘𝑙
+ 𝛿𝑖𝑘 𝑧𝑗 (𝑡) .
(3.4.21)
𝜕𝜔𝑖𝑗
𝜕𝜔𝑖𝑗
𝑙∈𝑈
∑︀
𝜕𝑦𝑘 (𝑡+1)
Таким образом число ∆𝜔𝑖𝑗 = 𝑘∈𝑈 𝜕𝜔
задаём оптимальное измене𝑖𝑗
ние веса. По-настоящему оптимальным это изменение будем в случае, если
такие изменения будут накапливаться со всех элементов тренировочной последовательности, но в данном алгоритме изменения сразу прибавляются
к весам и следующие итерации работают с уже обновлёнными весами. Это
позволяет очень существенно распараллелить алгоритм.
11
К сожалению, как отмечено в работе[3], данный алгоритм слабо применим на практике из-за его большой ресурсоёмкости.
4
Платформа для параллельных вычислений
CUDA
Так как некоторые работы[9, 10] свидетельствуют о том, что тренировка
нейронной сети может быть существенно ускорена с использованием GPU,
рассмотрим одну из популярных платформ для реализации математических вычислений на GPU общего назначения: NVIDIA CUDA[8]. Достоинства этой платформы заключаются в её широкой распространённости и
простоте использования. Также NVIDIA и сторонние разработчики предлагают удобные и эффективные библиотеки операций линейной алгебры.
В данной работе интенсивно использовались две из них: Thrust и CUDA
BLAS.
Thrust.
Библиотека NVIDIA Thrust позволяет эффективно реализовывать операции над векторами на графическом процессоре в терминах функционального программирования, то есть операций map, reduce и других.
К сожалению, геометрических операций над векторами в этой библиотеке
практически нет. Авторы ограничились реализацией скалярного произведения.
CUDA BLAS.
Библиотека CUDA BLAS позволяет осуществлять большой спектр операций линейной алгебры на графическом процессоре. К
недостаткам можно отнести разве что нестандартное расположение матриц
в памяти (column wise), что в некоторых случаях приводит к необходимости реаллокации матриц.
5
Существующие реализации
Непараллельная реализация рекуррентной нейронной сети не является
сложной задачей[20], но, к сожалению, такая реализация обладает плохой масштабируемостью и не подходит для больших задач. Параллельная
реализация сложнее в исполнении в виду наличия временных зависимостей в рекуррентных нейронных сетях, но такая реализация необходима
для больших задач.
На данный момент существует ряд крупных параллельных реализаций
рекуррентных нейронных сетей.
12
5.1 CURRENNT
Библиотека CURRENNT[7] представляет собой полноценный инструмент
для создания, конфигурирования и тренировки нейронных сетей, в том
числе рекуррентных. В данной реализации представлены
∙ LSTM и двунаправленный LSTM слои,
∙ Слои прямого распространения с различными функциями активации,
∙ Различные выходные слои, представляющие собой различные функции ошибок,
∙ Единственный алгоритм тренировки – стохастический градиентный
спуск с моментом.
Распараллеливание в этой библиотеке реализовано на двух уровнях:
∙ на уровне матричных и векторных операций средствами библиотек
NVIDIA Thrust и CUDA BLAS,
∙ тренировкой нейронной сети на нескольких последовательностях одновременно.
Архитектура CURRENNT
CURRENNT имеет модульную архитектуру (рис.3, рис.6), что даёт простор
для расширения функциональности. Такая структура позволяет добавлять
в код реализацию новых методов тренировки сети, новых тренируемых
слоёв, новых функций ошибки.
Рис. 3: Иерархия оптимизаторов CURRENNT
Библиотеку можно условно поделить на несколько частей:
∙ Модуль вычисления операций линейной алгебры. Операции линейной
алгебры реализованы в трёх вариантах – с помощью библиотеки cuda
blas, с помощью библиотеки cuda thrust и в виде кода для исполнения на CPU. К сожалению, ни одна из этих реализаций не может
эффективно перемножать матрицы, размер которых больше размера
памяти графического процессора, но эту функциональность несложно добавить.
∙ Модуль построения нейронной сети в виде композиции слоёв.
13
∙ Модуль тренировки нейронной сети. В данный момент реализован
только стохастический градиентный спуск
∙ Модуль работы с датасетом. Поддерживается распространённый формат netCDF.
5.2 Реализация Michal Cernansky
Данная реализация[11] является результатом цикла работ по применению
фильтраций Калмана к тренировке нейронных сетей. К сожалению, эта
реализация носит лишь демонстрационный характер. Хоть она и является
параллельной, эффективной её назвать сложно, так как тренировка нейронной сети с помощью фильтра Калмана требует большого количества
перемножений плотных матриц большой размерности.
5.3 Caffe
Библиотека Caffe[14] на данный момент не поддерживает рекуррентные
нейронные сети, но заслуживает упоминания как одна из самых известных. Кроме того, авторами заявлено добавление поддержки рекуррентных
нейронных сетей в будущем.
5.4 Nvidia CuDNN
Nvidia CuDNN[13] это специализированная библиотека для ускорения тренировки нейронных сетей на графическом процессоре. Содержит также
примитивы для рекуррентных сетей. Данная библиотека не является полноценной реализацией и не имеет открытого исходного кода в отличие от
всех других представленных решений.
5.5 Microsoft CNTK
Библиотека Microsoft CNTK[12] представляет собой высокоэффективный
фреймворк, способный осуществлять конфигурацию и тренировку различных типов нейронных сетей, в том числе рекуррентных, но он не является
самостоятельной, а опирается на библиотеку CuDNN.
6
Реализация
В процессе уточнения задачи было решено вместо создания собственной
реализации с нуля расширить функционал библиотеки CURRENNT[7].
14
На момент написания работы в этой реализации были представлены
LSTM и двунаправленный LSTM слои, стохастический градиентный спуск
с моментом и множество вспомогательных инструментов.
Решено было добавить:
∙ простой рекуррентный слой,
∙ двунаправленный рекуррентный слой,
∙ алгоритм тренировки l-BFGS.
К сожалению, добавить алгоритм l-BFGS без модификаций изначального
кода библиотеки CURRENNT не удалось, так как интерфейс оптимизатора не позволял в течение одной итерации просматривать набор данных
несколько раз, что необходимо для работы алгоритма линейного поиска.
Таким образом, пришлось расширить интерфейс оптимизатора, добавив
в него метод ComputeForwardBackwardPassOnTrainset, вычисляющий градиент и значение функции ошибки на части тренировочного множества в
случае стохастической тренировки и на всех тренировочных данных иначе.
В процессе разработки выяснилось, что путём внесения небольших модификаций в упомянутые алгоритмы можно существенно увеличить качество работы нейронной сети. Так для l-BFGS был добавлен стохастический
режим, когда обновление весов делается после просмотра части тренировочных последовательностей, а не всего датасета. Такой модифицированный алгоритм будем называть sl-BFGS в простой рекуррентный слой была
добавлена нормализация градиента, чтобы избежать возникшей проблемы
экспоненциального роста градиента. Эти модификации существенно повлияли на эффективность алгоритмов.
7
Эксперименты
Тестирование и сравнение реализаций проводилось на датасете TIMIT[21];
с помощью рекуррентных нейронных сетей различных конфигураций на
этом датасете решалась задача классификации на 39 классах. Размерность
пространства признаков – 75. Длины последовательностей варьируются от
85 до 760. В тренировочном множестве содержится 4620 последовательностей, в тестовом – 1680.
Эксперименты проводились на виртуальном сервере amazon g2.2xlarge
с графическим вычислителем NVIDIA GRID K520, совместимым с CUDA
3 и обладающим 4гб видеопамяти.
В связи с недоступностью или неприменимостью остальных реализаций, эксперименты проводились с использованием расширенной библиотеки CURRENNT. В экспериментах затронуты реализованные авторами
15
библиотеки градиентный спуск с моментом и LSTM-слой, а также реализованные в рамках данной работы простой рекуррентный слой и алгоритм
sl-BFGS.
Во всех конфигурациях, протестированных в ходе экспериментов, нейронная сеть помимо входного и выходного слоёв включала в себя один или
более рекуррентных слоёв и слой прямого распространения с функцией
активации softmax размерности 39. Далее мы будем указывать только конфигурации рекуррентных слоёв, так как остальные слои оставались неизменными в ходе экспериментов. Используемый алгоритм оптимизации, тип
и размерности рекуррентных слоёв варьировались. Кроме того, для оптимизатора sl-BFGS варьировался также размер хранилища, так как этот
параметр влияет на среднюю скорость одной итерации тренировки[19].
7.1 Сравнение скорости тренировки
Сначала мы зафиксировали две конфигурации нейронной сети:
∙ сеть с одним простым рекуррентным слоем размерности 100,
∙ сеть с одним LSTM-слоем размерности 50.
Для обеих конфигураций мы запустили 100 итераций тренировки нейронной сети алгоритмом sl-BFGS с размером хранилища 15. Результаты этого
эксперимента можно увидеть на рис. 4. Такие размерности слоёв были выбраны, так как количества оптимизируемых параметров в них соизмеримы
(17600 у SRL против 26350 у LSTM). Несмотря на этот факт, легко видеть,
что простой рекуррентный слой даёт гораздо менее точные предсказания,
чем LSTM-слой. Это связано с неспособностью модели запоминать дальние
зависимости[15], которые скорее всего присутствуют в выбранном датасете,
так как длина последовательностей достаточно велика.
Показательно сравнить скорость тренировки нейронной сети с помощью
стохастического градиентного спуска с моментом и с помощью sl-BFGS.
Так как подбор оптимальных параметров не является целью данной работы, были использованы стандартные конфигурации оптимизаторов и изменялись лишь число и размеры слоёв нейронной сети. Так для градиентного
спуска с моментом использовались скорость обучения 10−5 и момент 0.5,
стандартные параметры, стандартная конфигурация для sl-BFGS взята из
[19].
На рисунке 5 изображёно изменение ошибки на тестовом множестве в
процессе тренировки при тренировке нейронной сети с помощью стохастического градиентного спуска (SGD) и с помощью sl-BFGS, конфигурации
которых описаны выше. Заметно, что алгоритм sl-BFGS в начале процесса тренировки сходится быстрее благодаря использованию аппроксимации
производных второго порядка.
16
Рис. 4: Тренировка рекуррентных слоёв
70
LSTM
SRL
Ошибка(%)
60
50
40
30
20
0
20
40
60
Итерация
80
100
Рис. 5: Тренировка нейронной сети алгоритмами sl-BFGS и SGD
70
sl-BFGS
SGD
Ошибка(%)
60
50
40
30
20
0
20
40
60
Итерация
17
80
100
Таблица 2: Среднее время итерации (в секундах)
Конфигурация сети SGD sl-BFGS5 sl-BFGS15
LSTM20
LSTM50
LSTM100
LSTM20+LSTM20
SRL40
SRL100
SRL200
SRL40+SRL40
10.283
10.262
24.52
10.293
10.223
10.326
12.314
10.218
10.78
17.39
29.96
14.23
10.57
13.75
20.90
14.17
11.04
17.62
29.86
14.53
10.56
13.90
20.97
14.84
Также было измерено время одной итерации в различных конфигурациях. Результаты можно видеть в таблице 2. В этой таблице sl-BFGS5 и
sl-BFGS15 соответствую алгоритму sl-BFGS с размерами хранилища 5 и 15
соответственно. LSTM20+LSTM20 означает, что в качестве рекуррентных
слоёв были использованы два LSTM-слоя, каждый размерности 20.
Можно заметить, что итерация алгоритма sl-BFGS в среднем длится
дольше итерации градиентного спуска. Связано это с необходимостью выполнения дополнительных матричных операций. Более того, время итерации sl-BFGS варьируется в широких пределах, так как в этом алгоритме
используется линейный поиск. Ещё можно заметить, что тренировка нейронной сети с простым рекуррентным слоем занимает меньше времени, что
логично, поскольку структура простого рекуррентного слоя гораздо проще,
чем структура LSTM-слоя.
Также на сети, содержащей один LSTM-слой размерности 50 были проведены замеры среднего времени итерации при различном количестве последовательностей, обрабатываемых параллельно. Результаты представлены в таблице 3. Легко видеть, что увеличение числа последовательностей,
обрабатываемых параллельно приводит к существенному ускорению процесса тренировки нейронной сети.
7.2 Сравнение качества тренировки
Наконец, рассмотрим точность классификации на тестовом множестве при
помощи нейронных сетей различных конфигураций, натренированных различными алгоритмами классификации за 100 итераций. Заметно, что нейронные сети одной конфигурации, натренированные разными алгоритмами
почти всегда дают идентичные результаты. Существенное различие качества зафиксировано только для случая двух простых рекуррентных слоёв
размерности 40.
18
Таблица 3: Зависимость времени итерации (в секундах) от числа последовательностей, обрабатываемых параллельно
# последовательностей SGD sl-BFGS
10
20
50
100
16.811
10.6
8.844
8.2222
33.344
20
16.578
15.211
Таблица 4: Точность на тестовом множестве после 100 итераций алгоритма
тренировки
Конфигурация сети SGD sl-BFGS5 sl-BFGS15
LSTM20
LSTM50
LSTM100
LSTM20+LSTM20
SRL40
SRL100
SRL200
SRL40+SRL40
8
66.07
71.06
74.33
68.22
44.14
53.52
56.28
41.11
66.28
70.69
72.45
68.18
46.74
54.58
56.3
49.04
66.63
71.03
73.08
68.3
46.92
54.43
56.33
48.43
Заключение
Таким образом в ходе работы были рассмотрены различные подходы к
построению и тренировке рекуррентных нейронных сетей, проведён анализ существующих параллельных реализаций рекуррентных нейронных сетей. В одну из таких параллельных реализаций добавлена новая функциональность, а именно простой рекуррентный слой и алгоритм тренировки
l-BFGS.
В ходе экспериментов выяснилось, что на выбранном наборе данных
эффективнее проводить тренировку нейронной сети с помощью стохастического градиентного спуска, нежели с помощью алгоритма sl-BFGS, так
как время одной итерации sl-BFGS существенно превосходит время итерации стохастического градиентного спуска, нивелируя выигрыш в увеличении точности после каждой итерации.
Также данная работа ещё раз иллюстрирует превосходство нейронных
сетей с LSTM-слоями над сетями на основе простого рекуррентного слоя,
обусловленное способностью LSTM-слоя моделировать отдалённые зависимости в данных. Тем не менее, простой рекуррентный слой используется
в современных исследованиях[18] ввиду низкого времени тренировки, так
что выполненная реализация может оказаться полезной.
Хотя работа над поставленными задачами закончена, исследование
19
можно продолжить, например, реализовав дополнительные алгоритмы тренировки, например AdaGrad, который, согласно работе[22], показывает более высокую скорость тренировки, чем стохастический градиентный спуск
на рекурретных нейронных сетях.
20
Список литературы
[1] Bernard Widrow, David E. Rumelhart, and Michael A. Lehr. Neural
networks: Applications in industry, business and science. Commun. ACM,
37(3):93–105, March 1994.
[2] Anil K Jain, Jianchang Mao, and KM Mohiuddin.
networks: A tutorial. Computer, (3):31–44, 1996.
Artificial neural
[3] Ilya Sutskever. Training recurrent neural networks. PhD thesis, University
of Toronto, 2013.
[4] Fernando Baçao, Victor Lobo, and Marco Painho. Self-organizing maps as
substitutes for k-means clustering. In Computational Science–ICCS 2005,
pages 476–483. Springer, 2005.
[5] MN Karim and SL Rivera. Comparison of feed-forward and recurrent
neural networks for bioprocess state estimation. Computers & chemical
engineering, 16:S369–S377, 1992.
[6] Martin Sundermeyer, Ilya Oparin, Jean-Luc Gauvain, Ben Freiberg, Ralf
Schluter, and Hermann Ney. Comparison of feedforward and recurrent
neural network language models.
In Acoustics, Speech and Signal
Processing (ICASSP), 2013 IEEE International Conference on, pages
8430–8434. IEEE, 2013.
[7] Felix Weninger. Introducing currennt: The munich open-source cuda
recurrent neural network toolkit. Journal of Machine Learning Research,
16:547–551, 2015.
[8] John Nickolls, Ian Buck, Michael Garland, and Kevin Skadron. Scalable
parallel programming with cuda. Queue, 6(2):40–53, March 2008.
[9] Kyoung-Su Oh and Keechul Jung. Gpu implementation of neural networks.
Pattern Recognition, 37(6):1311–1314, 2004.
[10] Boxun Li, Erjin Zhou, Bo Huang, Jiayi Duan, Yu Wang, Ningyi Xu, Jiaxing
Zhang, and Huazhong Yang. Large scale recurrent neural network on gpu.
In Neural Networks (IJCNN), 2014 International Joint Conference on,
pages 4062–4069. IEEE, 2014.
[11] Michal Čerňanský. Training recurrent neural network using multistream
extended kalman filter on multicore processor and cuda enabled graphic
processor unit. In Cesare Alippi, Marios Polycarpou, Christos Panayiotou,
and Georgios Ellinas, editors, Artificial Neural Networks – ICANN 2009,
volume 5768 of Lecture Notes in Computer Science, pages 381–390.
Springer Berlin Heidelberg, 2009.
21
[12] Chris Basoglu Guoguo Chen Scott Cyphers Amit Agarwal, Eldar Akchurin
et al. An introduction to computational networks and the computational
network toolkit. Technical Report MSR-TR-2014-112, August 2014.
[13] Sharan Chetlur, Cliff Woolley, Philippe Vandermersch, Jonathan Cohen,
John Tran, Bryan Catanzaro, and Evan Shelhamer. cudnn: Efficient
primitives for deep learning. arXiv preprint arXiv:1410.0759, 2014.
[14] Yangqing Jia, Evan Shelhamer, Jeff Donahue, Sergey Karayev, Jonathan
Long, Ross Girshick, Sergio Guadarrama, and Trevor Darrell. Caffe:
Convolutional architecture for fast feature embedding. arXiv preprint
arXiv:1408.5093, 2014.
[15] Sepp Hochreiter and Jürgen Schmidhuber.
Neural computation, 9(8):1735–1780, 1997.
Long short-term memory.
[16] Mike Schuster and Kuldip K Paliwal. Bidirectional recurrent neural
networks. Signal Processing, IEEE Transactions on, 45(11):2673–2681,
1997.
[17] Paul J Werbos. Backpropagation through time: what it does and how to
do it. Proceedings of the IEEE, 78(10):1550–1560, 1990.
[18] Alex Graves and Navdeep Jaitly. Towards end-to-end speech recognition
with recurrent neural networks. In Proceedings of the 31st International
Conference on Machine Learning (ICML-14), pages 1764–1772, 2014.
[19] Jorge Nocedal and Stephen Wright. Numerical optimization. Springer
Science & Business Media, 2006.
[20] Alex Graves. Rnnlib: A recurrent neural network library for sequence
learning problems. http://sourceforge.net/projects/rnnl/.
[21] John S Garofolo, Lori F Lamel, William M Fisher, Jonathan G Fiscus, and
David S Pallett. Darpa timit acoustic-phonetic continous speech corpus
cd-rom. nist speech disc 1-1.1. NASA STI/Recon Technical Report N, 93,
1993.
[22] Hieu Pham, Zihang Dai, and Lei Li. On optimization algorithms for
recurrent networks with long short-term memory. Momentum, 1:0–6.
22
9
Приложение
Алгоритм 1 Градиентный спуск
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
𝑗←0
инициализировать 𝜔0 , 𝛼
repeat
𝐺𝑟𝑎𝑑𝑖𝑒𝑛𝑡 ← O
𝑁 ←0
(𝑥𝑘 , 𝑦𝑘 ) из тренировочного множества
𝐺𝑟𝑎𝑑𝑖𝑒𝑛𝑡 ← 𝐺𝑟𝑎𝑑𝑖𝑒𝑛𝑡 + ∇𝜔𝑗 𝑄(𝜔𝑗 , 𝑥𝑘 , 𝑦𝑘 )
𝑁 ←𝑁 +1
for
do
end for
𝜔𝑗+1 = 𝜔𝑗 − 𝛼 𝑁1 𝐺𝑟𝑎𝑑𝑖𝑒𝑛𝑡
𝑗 ←𝑗+1
until convergence
Алгоритм 2 Стохастический градиентный спуск
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
𝑗←0
инициализировать 𝜔0 , 𝛼
repeat
𝑁 ←0
𝜖0 ← 𝜔𝑗
(𝑥𝑘 , 𝑦𝑘 ) из тренировочного множества
𝜖𝑘 ← 𝜖𝑘−1 − 𝛼∇𝜖𝑘−1 𝑄(𝜖𝑘−1 , 𝑥𝑘 , 𝑦𝑘 )
𝑁 ←𝑁 +1
for
end for
𝜔𝑗+1 = 𝜖𝑁
𝑗 ←𝑗+1
until convergence
23
do
Алгоритм 3 Пакетный градиентный спуск
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
𝑗←0
инициализировать 𝜔0 , 𝛼
repeat
𝑁 ←0
for 𝑖 = 1..|𝜔 | do
𝑔←0
for (𝑥 , 𝑦 ) из тренировочного множества do
𝑗
𝑘
𝑘
𝑔 ← 𝑔 + ∇𝜔𝑗𝑖 𝑄(𝜔𝑗 , 𝑥𝑘 , 𝑦𝑘 )
𝑁 ←𝑁 +1
end for
𝜔 ←𝜔 −𝛼
end for
𝑖
𝑗
𝑖
𝑗
1
𝑁𝑔
𝜔𝑗+1 ← 𝜔𝑗
𝑗 ←𝑗+1
until convergence
Алгоритм 4 Тренировка рекуррентной нейронной сети с помощью фильтра Калмана
1: Выбрать начальный вектор весов 𝜔0 ;
2: 𝑘 ← 0;
3: 𝑃 (0) ← диагональная матрица размера (𝑀 * 𝑁 + 𝑀 * 𝑀 + 𝐾 * 𝑀 ) × 𝐾 ,
на диагонали которой стоят довольно большие числа (порядка 100);
4:
5:
6:
7:
8:
repeat
for (𝑥, 𝑦) из тренировочного множества do
𝑤(0)
ˆ
←𝜔
for 𝑡 = 0 . . . 𝑇 do
𝑘
𝐻(𝑡) ← 𝜕𝜕𝑜(𝑡)
;
𝑤(𝑡)
^
𝐾(𝑡) = 𝑃 (𝑡)𝐻(𝑡)[𝐻(𝑡)𝑇 𝑃 (𝑡)𝐻(𝑡)]−1
𝜉(𝑡) ← 𝑦(𝑡) − 𝑜(𝑡)
𝑤(𝑡
ˆ + 1) = 𝑤(𝑡)
ˆ + 𝐾(𝑡)𝜉(𝑡)
𝑃 (𝑡 + 1) = 𝑃 (𝑡) − 𝐾(𝑡)𝐻(𝑡)𝑇 𝑃 (𝑡)
9:
10:
11:
12:
13:
14:
15:
16:
17:
end for
𝜔 ← 𝑤(𝑇
ˆ + 1)
end for
𝜔
←𝜔
until convergence
𝑘
𝑘+1
𝑘
24
Алгоритм 5 l-BFGS для нейронной сети
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
Выбрать начальный вектор весов 𝜔0 , выбрать число 𝑚 > 0 – размер
хранилища
k ← 0;
repeat
if 𝑘 = 0 then
𝐻 ← 𝐼;
else
0
𝑘
𝛾𝑘 =
𝑠𝑇𝑘−1 𝑦𝑘−1
;
𝑇 𝑦
𝑦𝑘−1
𝑘−1
𝐻𝑘0 ← 𝛾𝑘 𝐼 ;
end if
q ← ∇𝐿(𝜔 );
for 𝑖 = 𝑘 − 1, 𝑘 − 2, . . . , 𝑘 − 𝑚 do
𝑘
𝛼𝑖 ← 𝜌𝑖 𝑠𝑇𝑖 𝑞 ;
𝑞 ← 𝑞 − 𝛼 𝑖 𝑦𝑖 ;
end for
𝑟 ← 𝐻 𝑞;
for 𝑖 = 𝑘 − 𝑚, 𝑘 − 𝑚 + 1, . . . , 𝑘 − 1 do
0
𝑘
𝛽 ← 𝜌𝑖 𝑦𝑖𝑇 𝑟;
𝑟 ← 𝑟 − 𝑠𝑖 (𝛼𝑖 − 𝛽);
end for
𝑝𝑘 ← −𝑟;
𝛼𝑘 ← LineSearch(l, 1, 𝑝𝑘 , 𝜔𝑘 );
𝜔𝑘+1 ← 𝜔𝑘 + 𝛼𝑘 𝑝𝑘 ;
𝑘>𝑚
Удалить пару (𝑠𝑘−𝑚 , 𝑦𝑘−𝑚 ) из хранилища;
if
then
end if
Вычислить и сохранить в хранилище пару
(𝑠𝑘 = 𝜔𝑘+1 − 𝜔𝑘 , 𝑦𝑘 = ∇𝐿(𝜔𝑘+1 ) − ∇𝐿(𝜔𝑘 ));
𝑘 ←𝑘+1
until convergence
Алгоритм 6 Линейный поиск с возвратом
function
(l, 𝛼, p, 𝜔 )
1:
2:
3:
4:
5:
6:
7:
BacktrackingLineSearch
𝑘←0
𝛼0 ← 𝛼
not (𝑙(𝜔 + 𝛼𝑘 𝑝) ≤ 𝑙(𝜔) + 𝑐1 𝛼𝑘 ∇𝑙(𝜔)𝑇 𝑝
and |∇𝑙(𝜔 + 𝛼𝑘 𝑝)𝑇 𝑝| ≥ 𝑐2 |∇𝑙(𝜔)𝑇 𝑝|)
𝛼𝑘+1 ← 𝛼𝑚𝑘
while
do
end while
end function
25
Рис. 6: Иерархия слоёв CURRENNT
26
Отзывы:
Авторизуйтесь, чтобы оставить отзыв