Алгоритм увеличения точности нейронных сетей и его приложения
 Скачать 3.63 Mb.
|
|
𝐸 (𝜕 𝑠 𝑣 𝜔𝑎 ) → 𝐸 (︀𝜕 𝑝 𝑧 𝜓𝑎 )︀ , то есть рассмотреть 𝐸 как функцию от матриц активностей на предпоследнем слое. Для общности, сразу рассмотрим два произвольных смежных слоя, связанных формулой (4.1.4) и два соответствующих им градиента 2 𝜕𝐸 𝜕 (𝜕 𝑠 𝑧 𝜃𝑎 ′ ) → 𝜕𝐸 𝜕 (𝜕 𝑝 𝑧 𝜅𝑎 ) Поставим задачу нахождения правого градиента, если известен левый. В самом общем виде можно записать 𝜕𝐸 𝜕 (𝜕 𝑝 𝑧 𝜅𝑎 ) = ∑︁ 𝑠,𝜃,𝑎 ′ 𝜕𝐸 𝜕 (𝜕 𝑠 𝑧 𝜃𝑎 ′ ) 𝜕 (︁ 𝜕 𝑠 𝑧 𝜃𝑎 ′ )︁ 𝜕 (𝜕 𝑝 𝑧 𝜅𝑎 ) (4.2.1) Согласно (4.1.4), 𝜕 𝑠 𝑧 𝜃𝑎 и 𝜕 𝑠 𝑧 𝜅𝑎 связаны формулой 𝜕 𝑠 𝑧 𝜃𝑎 = 𝑊 𝜃𝜅 × 𝜕 𝑠 𝜎 (𝑧 𝜅𝑎 ) . Чтобы вычислить 𝜕 (︁ 𝜕 𝑠 𝑧 𝜃𝑎 ′ )︁ /𝜕 (𝜕 𝑝 𝑧 𝜅𝑎 ) в общем виде, сформулируем ещё одно вспомога- тельное утверждение. Лемма. Если 𝜕 𝑠 = 𝜕 𝑝 𝜕 𝑞 то справедлива формула 𝜕 𝜕 (𝜕 𝑝 𝑧) 𝜕 𝑠 𝜎 (𝑧) = (︂𝑠 𝑝 )︂ 𝜕 𝑞 𝜎 ′ (𝑧) , где (︀ 𝑠 𝑝 )︀ есть произведение биномиальных коэффициентов (︂𝑠 𝑝 )︂ = ∏︁ 𝑖 𝑠 𝑖 ! 𝑝 𝑖 ! (𝑠 𝑖 − 𝑝 𝑖 )! 2 добавим штрих у 𝑎 чтобы избежать повторения индексов 91 Доказательство. Пусть 𝑝 соответствует ˜ 𝑝 , возможно не единственный. Пусть ˜ 𝑝 соот- ветствует блок 𝐵 . Рассмотрим подмножество 𝑃 𝐵 всех разбиений 𝐷 = {1, . . . , |𝑠|} , содержа- щих данный блок. Согласно формуле (4.1.14), 𝑃 𝐵 описывает все слагаемые 𝜕 ˜ 𝑠 𝜎 (𝑧) , которые умножаются на 𝜕 ˜ 𝑝 𝑧 , а значит при его вычеркивании получается искомая частная произ- водная. Если исключить блок 𝐵 из каждого элемента 𝑃 𝐵 , то получится множество ˚ 𝑃 𝐵 всех разбиений множества {1, . . . , 𝑛}∖𝐵 . Согласно (4.1.14), ˚ 𝑃 𝐵 описывает производную 𝜕 ˜ 𝑠−˜ 𝑝 𝜎 (𝑧) Её отличие от искомой производной в том, что после вычеркивания 𝐵 , количество блоков |𝜋| везде стало на единицу меньше. Чтобы это исправить, достаточно заменить 𝜎 на 𝜎 ′ . Имеем 𝜕 𝜕 (𝜕 ˜ 𝑝 𝑧) 𝜕 ˜ 𝑠 𝜎 (𝑧) = 𝜕 ˜ 𝑞 𝜎 ′ (𝑧) , так же заметим, что выбор ˜ 𝑝 однозначно фиксирует ˜ 𝑞 . Чтобы перейти к исходным перемен- ным осталось учесть комбинаторный коэффициент, который отражает количество разных ˜ 𝑝 , соответствующего одному 𝑝 Теперь мы можем упростить второй сомножитель в (4.2.1) 𝜕 (︁ 𝜕 𝑠 𝑧 𝜃𝑎 ′ )︁ 𝜕 (𝜕 𝑝 𝑧 𝜅𝑎 ) = 𝜕 (︁ ∑︀ 𝜅 ′ 𝑊 𝜃𝜅 ′ 𝜕 𝑠 𝜎 (︁ 𝑧 𝜅 ′ 𝑎 ′ )︁)︁ 𝜕 (𝜕 𝑝 𝑧 𝜅𝑎 ) = ∑︁ 𝜅 ′ 𝑊 𝜃𝜅 ′ 𝜕 (︁ 𝜕 𝑠 𝜎 (︁ 𝑧 𝜅 ′ 𝑎 ′ )︁)︁ 𝜕 (𝜕 𝑝 𝑧 𝜅𝑎 ) = = ∑︁ 𝜅 ′ 𝑊 𝜃𝜅 ′ (︂𝑠 𝑝 )︂ 𝜕 𝑠−𝑝 𝜎 ′ (𝑧 𝜅𝑎 ) 𝛿 𝜅 ′ 𝜅 𝛿 𝑎 ′ 𝑎 = 𝑊 𝜃𝜅 (︂𝑠 𝑝 )︂ 𝜕 𝑠−𝑝 𝜎 ′ (︁ 𝑧 𝜅𝑎 ′ )︁ 𝛿 𝑎 ′ 𝑎 При подстановке результата в (4.2.1) суммирование по 𝑎 ′ исчезает 𝜕𝐸 𝜕 (𝜕 𝑝 𝑧 𝜅𝑎 ) = ∑︁ 𝑠,𝜃,𝑎 ′ 𝜕𝐸 𝜕 (𝜕 𝑠 𝑧 𝜃𝑎 ) 𝑊 𝜃𝜅 (︂𝑠 𝑝 )︂ 𝜕 𝑠−𝑝 𝜎 ′ (︁ 𝑧 𝜅𝑎 ′ )︁ 𝛿 𝑎 ′ 𝑎 = = ∑︁ 𝑠 (︂𝑠 𝑝 )︂ 𝜕 𝑠−𝑝 𝜎 ′ (𝑧 𝜅𝑎 ) ∑︁ 𝜃 𝜕𝐸 𝜕 (𝜕 𝑠 𝑧 𝜃𝑎 ) 𝑊 𝜃𝜅 = = ∑︁ 𝑠 (︂𝑠 𝑝 )︂ 𝜕 𝑠−𝑝 𝜎 ′ (𝑧 𝜅𝑎 ) (︂ [︀𝑊 𝜃𝜅 ]︀ 𝑇 × 𝜕𝐸 𝜕 (𝜕 𝑠 𝑧 𝜃𝑎 ) )︂ , (4.2.2) здесь с помощью суммы по 𝜃 мы сформировали матричное произведение. Мульти-индекс 𝑠 пробегает все производные для которых компоненты 𝑠 − 𝑝 неотрицательны. С помощью градиента 𝐸 по активностям слоя 𝜃 можно вычислить градиент 𝐸 по весам матрицы 𝑊 𝜃𝜅 Рассмотрим замену 𝐸 (︁ 𝜕 𝑠 𝑧 𝜃 ′ 𝑎 )︁ → 𝐸 (︀𝑊 𝜃𝜅 )︀ , для которой можно записать 𝜕𝐸 𝜕𝑊 𝜃𝜅 = ∑︁ 𝑠,𝜃 ′ ,𝑎 𝜕𝐸 𝜕 (𝜕 𝑠 𝑧 𝜃 ′ 𝑎 ) 𝜕 (︁ 𝜕 𝑠 𝑧 𝜃 ′ 𝑎 )︁ 𝜕𝑊 𝜃𝜅 (4.2.3) 92 Используя формулу прямого распространения 𝜕 𝑠 𝑧 𝜃 ′ 𝑎 = 𝑊 𝜃 ′ 𝜅 × 𝜕 𝑠 𝜎 (𝑧 𝜅𝑎 ) , можно вычислить правый сомножитель в (4.2.3): 𝜕 (︁ 𝜕 𝑠 𝑧 𝜃 ′ 𝑎 )︁ 𝜕𝑊 𝜃𝜅 = 𝜕 𝑠 𝜎 (𝑧 𝜅𝑎 ) 𝛿 𝜃𝜃 ′ Подставим его в исходное выражение и аналогично сформируем матричное произведение 𝜕𝐸 𝜕𝑊 𝜃𝜅 = ∑︁ 𝑠,𝑎 𝜕𝐸 𝜕 (𝜕 𝑠 𝑧 𝜃𝑎 ) 𝜕 𝑠 𝜎 (𝑧 𝜅𝑎 ) = ∑︁ 𝑠 𝜕𝐸 𝜕 (𝜕 𝑠 𝑧 𝜃𝑎 ) × [𝜕 𝑠 𝜎 (𝑧 𝜅𝑎 )] 𝑇 (4.2.4) Градиент 𝐸 по векторам сдвига вычисляется элементарно 𝜕𝐸 𝜕𝑡 𝜅 = ∑︁ 𝑎 𝜕𝐸 𝜕𝑧 𝜅𝑎 4.3. Сложность Перейдём к подсчету количества арифметических операций: сложений и умножений, необходимых для вычисления формул предыдущего параграфа. 4.3.1. Прямой проход. Согласно формуле (4.1.4), для распространения производной 𝜕 𝑠 от слоя с |𝜅| нейронами к слою с |𝜃| нейронами требуется матричное умножение, состоя- щее из (2|𝜅| − 1)·|𝜃|·|𝑎| операций. Кроме того, член 𝜕 𝑠 𝜎 (𝑧 𝜅𝑎 ) требует некоторого количества поэлементных операций, число которых можно представить в виде |𝜅| · |𝑎| · 𝜌 , где 𝜌 есть ко- личество операций на каждый элемент матрицы 𝑧 𝜅𝑎 . Чтобы найти 𝜌 , достаточно посчитать арифметику, связанную с вычислением квадратных скобок выражений вида (4.1.9), (4.1.10) без учета верхних индексов. Каждое слагаемое в них есть произведение некоторой производ- ной 𝜎 на круглую скобку. Само вычисление 𝜎 𝜎 (𝑥) = 1 1 + 𝑒 −𝑥 содержит экспоненту и деление, а обе эти операции требуют значительного количества сло- жений и умножений, причём конкретное число зависит от реализации этих функций. Нас, однако, в первую очередь интересует насколько более затратным является обучение с про- изводными, а так как 𝜎 нужно будет вычислять в любом случае, то можно не учитывать связанную с этим арифметику. Что касается производных, то зная 𝜎 (𝑥) , их все можно вы- разить как полиномы от 𝜎 (𝑥) . Действительно, 𝜎 ′ = 𝑒 −𝑥 (1 + 𝑒 −𝑥 ) 2 = 1 1 + 𝑒 −𝑥 − 1 (1 + 𝑒 −𝑥 ) 2 = 𝜎 − 𝜎 2 93 𝑠 +, * 𝑠 +, * 𝑠 +, * 𝑠 +, * 0 0 (1, 1) 1 4 11 5 20 1 0 3 4 (3, 1) 19 (4, 1) 28 2 1 (2, 1) 6 (2, 2) 22 (3, 2) 54 Таблица 1. Количество сложений и умножений в круглых скобках выражений вида (4.1.10), (4.1.11) для разных 𝑠 Дифференцируя это выражение дальше и приводя подобные слагаемые чтобы уменьшить число операций, получаем: 𝜎 ′ = 𝜎 · (1 − 𝜎) , 𝜎 ′′ = 𝜎 ′ · (1 − 2𝜎) , 𝜎 ′′′ = 𝜎 ′ · (1 − 6𝜎 ′ ) , 𝜎 𝐼𝑉 = 𝜎 ′′ · (1 − 12𝜎 ′ ) , 𝜎 𝑉 = 𝜎 ′ − 30 (𝜎 ′′ ) 2 , 𝜎 𝑉 𝐼 = 𝜎 ′′ + (︀𝜎 𝐼𝑉 − 𝜎 ′′ )︀ (5 − 30𝜎 ′ ) . Вернёмся к подсчету числа операций. Количество слагаемых в квадратных скобках вида (4.1.10) равно порядку производной |𝑠| . Число арифметических операций без учета выраже- ний в круглых скобках для |𝑠| от 1 до 6 равно соответственно 3, 8, 13, 18, 23, 30. Теперь посчитаем количество операций в круглых скобках. Как следует из формулы (4.1.14), 𝑘 -я производная сигмоиды всегда умножается на сумму произведений 𝑧 с нижними индекса- ми, которые составляют все возможные разбиения 𝑠 на 𝑘 частей. В упрощенных выражениях вида (4.1.11), (4.1.12) некоторые разбиения приводили к одинаковым произведениям и мож- но было найти подобные слагаемые. Выражения вида (4.1.9) и (4.1.10) являются худшим в вычислительном смысле случаем, так как все разбиения различны. Таблица 1 содержит количество сложений и умножений, необходимых для вычисления круглых скобок для всех мульти-индексов производных, использованных в Главе 2. 4.3.2. Градиент весов. Выражение (4.2.4) есть сумма матричных произведений, каж- дое из которых требует (2|𝑎| − 1)·|𝜅|·|𝜃| операций. Сами сомножители уже были вычислены во время прямого либо обратного прохода. 4.3.3. Обратный проход. Формально, выражение (4.2.2) содержит сумму, которую нужно вычислять для каждой производной 𝑝 . Однако, вычисления для разных 𝑝 значи- тельно перекрываются. Не считая умножений на комбинаторные коэффициенты, каждое слагаемое есть поэлементное произведение двух матриц. Первая из них похожа на матри- цу 𝜕 𝑠 𝜎 (𝑧 𝜅𝑎 ) , вычисленную во время прямого распространения, с тем лишь отличием, что 94 𝑘 0 1 2 3 4 5 2Д аппроксимация 1% 2% 4% 6% 10% 17% 3Д автокодировщик 2% 4% 10% 15% 22% 30% уравнение Пуассона 7% 12% 19% 31% – – Таблица 2. Количество поэлементных операций как процент от матричных для одной эпохи обучения с 𝐸 𝑘 вместо 𝜎 написана 𝜎 ′ . Если вычислить член 𝜕 𝑠 𝜎 ′ (𝑧 𝜅𝑎 ) во время прямого распространения, когда круглые скобки выражений (4.1.10), (4.1.11) уже посчитаны, то их останется только умножить на более высокую производную 𝜎 . Для |𝑠| от 1 до 6 это потребует 0, 1, 3, 4, 7, 9 операций соответственно, плюс от 2 до 9 операций для повышения максимального поряд- ка производной 𝜎 на единицу (но только один раз для всего набора матриц). Что касается матричных произведений вида [︀𝑊 𝜃𝜅 ]︀ 𝑇 × 𝜕𝐸 𝜕 (𝜕 𝑠 𝑧 𝜃𝑎 ) , то их все нужно вычислить для 𝑝 = 0 , а для остальных 𝑝 использовать повторно. Оста- лось только учесть операции умножения на биномиальный коэффициент и суммирование по всем 𝑠 , для которых 𝑠 − 𝑝 ≥ 0 . Для рассмотренных задач максимальное число слага- емых равно 21. Удобно оценить отношение поэлементных операций к матричным как 𝜌 6𝜃 Для примеров из Главы 2 это значение никогда не превосходит 0.1, однако, такой подход требует промежуточного хранения величин 𝑧 𝜅𝑎 , 𝜕 𝑠 𝜎 (𝑧 𝜅𝑎 ) и 𝜕 𝑠 𝜎 ′ (𝑧 𝜅𝑎 ) . Из-за относительной малости количества поэлементных операций, было решено хранить только 𝑧 𝜅𝑎 , а остальные матрицы вычислять по мере надобности. Так мы снижаем требования по памяти в три раза, но лишь немного увеличиваем количество вычислений. Процент поэлементных операций с учётом этого усложнения представлен в Таблице 2. Чтобы вычислить число эпох, уравно- вешивающих количество арифметических операций, достаточно сравнить общее количество распространяемых производных, а затем немного скорректировать эту величину согласно Таблице 2. Напомним, что при обучении с исключением порядок 𝑘 постепенно понижается. 4.4. Реализация В настоящем параграфе описаны характерные особенности аппаратных и программ- ных платформ, которые используются для реализации алгоритма вычисления градиента. Акцент будет сделан только на те обстоятельства, от которых напрямую зависит вычисли- тельная эффективность. В конце приведены инструкции для использования программного комплекса «cpde-2», созданного с учётом всех описанных особенностей. 4.4.1. CUDA. CUDA (Compute Unified Device Architecture) это платформа [126], поз- воляющая использовать GPU (Graphics Processing Unit) марки NVIDIA для параллельных вычислений общего назначения. Она основана на модели SIMD (Single Instruction Mutiple Data), и как следует из названия, позволяет параллельно выполнять одинаковые инструк- ции над большим набором данных. Сами инструкции могут быть написаны на C/C++ и 95 Значение kind 0 1 2 3 Тип операции Host → Host Host → Device Device → Host Device → Device Таблица 3. Значения переменной kind в зависимости от источника при копи- ровании данных. встроены в основную программу, написанную на языке CUDA C/C++, который отличает- ся от C/C++ лишь наличием дополнительных конструкций, связанных с параллелизацией. Код программы подлежит компиляции с помощью nvcc (NVIDIA CUDA C/C++ Compiler) 3 , который доступен для различных операционных систем. Автор использовал CUDA 10.2 для Visual Studio 2017, но программа без изменений может быть скомпилирована и в других ОС. GPU (также называемый Device) является обособленной частью всей системы (Host) и это находит отражение при написании программ на CUDA. Так, nvcc отделяет код, вы- полняющийся на Host, и направляет его в системный компилятор, тогда как сам работает только с кодом для Device. Так как GPU имеет свои собственные микросхемы RAM, то перед вызовом функций, начальные данные должны быть записаны туда из Host RAM. Для этого используется встроенная функция cudaMemcpy (void* dst, const void* src, size count, cudaMemcpyKind kind), которая отличается от стандартной memcpy дополнительной переменной kind, определяющей откуда и куда копируются данные. Её возможные значения приведены в Таблице 3. Отметим, что в случае kind=0 можно воспользоваться обычной memcpy. Сами указатели на память у Device и Host имеют один и тот же тип float*, поэтому важно следить за тем, указывает ли конкретная переменная на Host или на Device, а если на Device то какой именно, так как видеокарт может быть несколько. Память на GPU выделяется с помощью функции cudaMalloc ( void** devPtr, size_t size ). Для освобождения памяти используется функция cudaFree ( void* devPtr ) Неудобство от обязательного переноса данных частично компенсируется возможностью вы- полнять его одновременно с операциями вычисления. При должной организации программы это позволяет целиком нивелировать потерю времени на копирование. Для этого необходимо выполнить несколько условий. Во-первых, память на Host должна быть выделена с помощью cudaHostAlloc (void** pHost, size_t size, unsigned int flags). 3 доступен также компилятор для FORTRAN 96 В отличии от стандартного выделения памяти, которая может физически находиться где угодно включая HDD (Hard Disk Drive), результатом вызова будет один последовательный блок ячеек RAM. Копирования из/в такую область могут происходить одновременно с вы- числением, если они вызываются командой cudaMemcpyAsync ( void* dst, const void* src, size_t count, cudaMemcpyKind kind, cudaStrem_t stream) , Причём переменная потока (stream) не совпадает аналогичной переменной, использованной для вызова вычисления. Обсудим принципы работы Device. Функции, выполняющиеся на нём, называются яд- рами (kernel). При запуске весь код ядра будет одновременно выполнятся большим количе- ством тредов (thread), каждый из которых будет исполняться на физически отдельном ALU (Arithmetic and Logic Unit) GPU. Треды объединяются в блоки (blocks), внутри которых всем тредам доступно некоторое количество общей (shared) памяти. Треды из разных блоков не имеют общей памяти кроме device RAM. В коде ядра доступны специальные переменные: од- на указывает на порядковый номер (id) выполняющего их треда, другая на номер его блока. С помощью них можно определять, над каким участком памяти нужно совершать действия. Для запуска ядра, кроме аргументов функции, нужно задать количество блоков и тредов на каждый блок, также можно задать номер потока. В данной работе нас будут интересо- вать только поэлементные операции, которые не требуют взаимодействия тредов, поэтому конкретная организация тредов и блоков нам не важна. Требуется лишь запустить ядро с таким количеством тредов и блоков, при котором все доступные ALU будут загружены, для примеров из Главы 2 достаточно 256 блоков по 256 тредов в каждом. Обсудим особенности чтения RAM. Каждый тред располагает некоторым количеством собственной памяти. Информация туда может быть загружена либо из общей памяти блока, либо из GPU RAM. Все треды блока дополнительно разбиты на связки (warp) по 32 штуки на основании своего id. Каждая связка всегда считывает память коллективным образом. Так, все 32 треда могут одновременно получить доступ к 32 значениям типа float32, находящихся в GPU RAM, при условии, что соседние треды считывают соседние адреса. Любой другой тип доступа негативно сказывается на производительности. Например, если один тред дол- жен считать одно значение типа float32, то остальные 31 в это время будут бездействовать. В этом случае теряется не только некоторое количество арифметических операций в секунду, но и почти вся пропускная способность памяти. Стоит отметить, что из-за большого ко- личества ALU, этой способности не всегда хватает, даже если доступ к памяти организован верно. Из-за этого, при написании алгоритмов на CUDA часто оценивают отношение количе- ства арифметических операций к количеству доступов к памяти. Чем больше эта величина, тем лучшую загруженность ALU можно гарантировать. В частности, для простых поэле- ментных функций, ядра лучше писать так, чтобы со всеми хоть раз считанными данными выполнялось максимальное количество операций. Например, все поэлементные выражения в формуле (4.2.2) рекомендуется исполнять одним ядром. 97 4.4.2. CUBLAS. В Разделе 4.3 мы установили, что при подсчёте градиента заметно большая часть вычислений приходится на матричные умножения. Опишем реализацию этой операции: 𝐶 𝑖𝑗 = 𝐴 𝑖𝑘 𝐵 𝑘𝑗 В самом тривиальном случае, каждый элемент 𝐶 𝑖𝑗 вычисляется отдельным тредом как ска- лярное произведение 𝑖 -й строки 𝐴 на 𝑗 -й столбец 𝐵 . В общем случае матрицы 𝐴 и 𝐵 могут храниться в памяти последовательно по строкам, либо по столбцам. Пусть |𝑖| = hA (height A), |𝑗| = wA (width A). При построчном хранении в соседних ячейках лежат соседние эле- менты одной строки 𝐴 𝑖𝑘 = A[i * wA + j]. При постолбцевом – соседние элементы одного столбца 𝐴 𝑖𝑘 = A[j * hA + i]. Очевидно, что нарушение правил доступа к памяти при вычислении 𝐶 𝑖𝑗 произойдет при любом способе хранения. Разрешить эту проблему можно предварительным транспонирова- нием одной из матриц. Это, однако, далеко не все необходимые оптимизации. Дело в том, |