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

STUD NET

АЛГОРИТМЫ ОПТИМИЗАЦИИ ПАРАМЕТРОВ С ВЫЧИСЛЕНИЕМ ПРОИЗВОДНОЙ ПЕРВОГО ПОРЯДКА В ЛИНЕЙНЫХ МЕТОДАХ

МАШИННОГО ОБУЧЕНИЯ

FIRST ORDER OPTIMIZATION ALGORITHMS APPLIED IN LINEAR MACHINE LEARNING METHODS

УДК 004.021 DOI: 10.24411/2658-4964-2020-10013 Корсун Анастасия Сергеевна, студент магистратуры,2 курс, институт Информационных технологий, РТУ МИРЭА Россия, г. Москва

Korsun Anastasia Sergeevna, magister student, 2 year, Institute of informational Technologies, RTU MIREA, Russia, Moscow

Аннотация: Статья посвящена исследованию алгоритмов оптимизации параметров моделей машинного обучения. Конкретно рассматривается группа алгоритмов с вычислением производной первого порядка как наиболее распространенных алгоритмов на практике. Основная задача исследования -привести математическое обоснование использования того или иного алгоритма. Приведенные в статье доводы полезны для понимания математического аппарата машинного обучения.

Ключевые слова: алгоритм, производная первого порядка, градиентный спуск, машинное обучение, оптимизация параметров.

Annotation: The article is dedicated to the study of algorithms for optimizing the parameters of machine learning models. Specifically, it covers a group of algorithms based on first-order derivative calculation as the most common algorithms in practice. The main task of the research is to provide a mathematical justification for the use of a particular algorithm. The arguments given in this article are useful for understanding the mathematical apparatus of machine learning.

Key words: algorithm, first-order derivative, gradient descent, machine learning, parameter optimization.

В основе многих численных методов машинного обучения лежат алгоритмы нахождения глобального минимума функции потерь G. Алгоритм оценивает погрешность функции при текущих значениях параметров модели и на основе этой оценки обновляет их, проводит оптимизацию. Наиболее распространены алгоритмы локальной оптимизация с вычислением

производных первого порядка [1]. В их основе лежит принцип, при котором направление, в котором будет проводиться поиск минимума функции G на i+1-м шаге алгоритма, определяется антиградиентом функции G на i-м шаге, а величина погрешности определяется методом наименьших квадратов. Вычисленный градиент функции G используется для оптимизации аппроксимирующей функции K, путем обновления ее коэффициентов на i-й итерации по формуле:

kf+1) = k

где:

x - объект выборки;

y - значение вектора целевой переменной;

t - номер итерации алгоритма;

j - номер признака объекта;

а - шаг алгоритма;

k - коэффициент функции F;

F - функция преобразования x в y.

При этом обновление весов может производиться как на основе ошибки по всей обучающей выборке (Batch optimization), так и на основе ошибки, вычисленной при обучении на одном объекте выборки (стохастический градиентный спуск). Для Batch optimization обновления весов k функции К производится с помощью выражения:

k

где:

x - объект выборки;

y - значение вектора целевой переменной; t - номер итерации алгоритма; j - номер признака объекта; а - шаг алгоритма;

k - коэффициент аппроксимирующей функции К; К - функция преобразования x в y.

Процедура повторяется до сходимости [2]. При стохастическом градиентном спуске для вычисления производных на каждом шаге алгоритма применяется лишь один объект выборки, для обновления весов k используется выражение:

k

где:

x - объект выборки;

y - значение вектора целевой переменной;

t - номер итерации алгоритма;

j - номер признака объекта;

а - шаг алгоритма;

k - коэффициент функции F;

F - функция преобразования x в y.

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

e

где:

x - объект выборки; t - номер итерации алгоритма; i - номер объекта выборки; а - шаг алгоритма; k - коэффициент функции F, 0 - вектор весов kj, j £{0..ш}; - число.

Подобный подход способствует более быстрому поиску локального минимума функции G, т.к. чем меньше величина ошибки, тем на меньшее число корректируются коэффициенты. Вариация SGD - Momentum. Его основное отличие от SGD заключается в том, что он определяет направление градиента на текущем шаге не только на основе погрешности текущего шага, но и на основе антиградиента предыдущего шага. Веса функции К обновляются по правилу:

e(t+1) = e(t) - nVQ(k) + aAk ,

где:

t - номер итерации алгоритма; а - шаг алгоритма на итерации t+1; П - шаг алгоритма на итерации t, k - коэффициент функции K, 0 - вектор весов kj, j £{0..m}, Q - функция потерь.

Перечисленные выше алгоритмы, хоть и эффективны, не дают возможность контролировать шаг алгоритма. Один из алгоритмов оптимизации, дающих над ним контроль - AdaGrad. Он позволяет

адаптировать величину шага на каждом из объектов выборки. Чем чаще обновляется коэффициент функции К при каком-либо признаке, тем на меньшее число он обновляется при последующей итерации. Соответственно, для коэффициентов, обновляющихся на малое число, шаг алгоритма возрастает. На ^ой итерации градиент функции потерь определяется как:

9г = Шв\

где:

0 - вектор весов ^ j £{0.^}, Q - функция потерь.

Ведем квадратную матрицу размера jxj как сумму внешних произведений градиента и транспонированного градиента на итерациях 1...т:

С= ^=19ь9Тг ,

где:

- gт градиент, вычисленный по выражению

Полученная матрица содержит квадраты обновлений коэффициентов F. На ее диагонали содержатся значения, на которые требуется умножать соответствующие коэффициенты F на каждой итерации алгоритма. Коэффициенты при этом обновляются по правилу:

е

где:

x - объект выборки; t - номер итерации алгоритма; П - шаг алгоритма на итерации ^ g- элемент матрицы (6), 0 - вектор весов к], j e{0..m}.

Основной недостаток алгоритма - элементы матрицы (6) могут принять сколь угодно большое значение, приводя к переобучению предиктивной модели. В связи с этим алгоритм затруднительно использовать на выборках с большим числом объектов. Решает эту проблему алгоритм RMSPшp.

В нем в матрице (6) регулирующим параметром под корнем выступает не сумма квадратов обновлений коэффициента, а квадрат среднего значения величины его обновления и(0Д) за все время обучения алгоритма [3]. Коэффициенты при этом обновляются в соответствии с выражением:

0

где:

x - объект выборки;

t - номер итерации алгоритма; П - шаг алгоритма на итерации t, k - коэффициент функции F, g- элемент матрицы (), 0 - вектор весов kj, j £{0..m}, Q - функция потерь.

Последний из рассмотренных алгоритмов - Adam. Он близок по своей сути к RMSProp [4], отличие состоит с в том, что при обновлении весов функции F учитывается не только центрированная дисперсия их значений:

me'+1) - P1me') +

где:

t - номер итерации алгоритма;

p1 - шаг алгоритма на итерации t для центрированной дисперсии, 0 - вектор весов kj, j £{0..m}, Q - функция потерь, но и нецентрированная:

vet+1) - P2vet)+(i-P2)(veQ(t))2,

где:

t - номер итерации алгоритма;

p2 - шаг алгоритма на итерации t для нецентрированной дисперсии, 0 - вектор весов kj, j £{0..m}, Q - функция потерь.

Значения этих параметров требуется калибровать: если изначально задать им слишком малое значение, время обучения алгоритма может сильно увеличиться. Поэтому эти значения искусственно увеличиваются в начале обучения алгоритма. Веса обновляются по правилу:

e

где:

t - номер итерации алгоритма;

me - значение, вычисляемое с помощью выражения (), и0 - значение, вычисляемое с помощью выражения (), 0 - вектор весов kj, j £{0..m}, s - константа.

Главный недостаток по сравнению с RMSProp - более высокая стоимость вычислений.

Вывод: на настоящий момент реализовано большое число алгоритмов с вычислением производной первого порядка, большинство из которых реализованы в библиотеках машинного обучения для различных языков разработки. При этом, чем совершеннее алгоритм, тем выше его сложность и тем больше вычислительных и временных ресурсов требует построенная на его основе предиктивная модель. Выбор того или иного алгоритма основывается в первую очередь на сложности обрабатываемых данных, а также на основе выбранного метода машинного обучения. Окончательное решение принимается на основе результатов обучения предиктивной модели и анализе полученных результатов.

Использованные источники:

1. Ginrich, Linear Regression. [Электронный ресурс]. URL: http://uregina.ca/~gingrich/regr.pdf

2. Блог Дениса Баженова. [Электронный ресурс]. URL: // http://bazhenov.me/blog/2012/07/21/classification-performance-evaluation.html

3. Лекции по Методам оптимизации, ФКН ВШЭ. [Электронный ресурс]. URL: // http: //www. machinelearning. ru/wiki/images/3/3 f/MO 17_seminar7. pdf

4. Блог Себастьяна Рудера. [Электронный ресурс]. URL: https://ruder.io/optimizing-gradient-descent/

Использованные источники:

1. Гинрич, Линейная регрессия. [Электронный ресурс]. URL: http: //uregina. ca/~gingrich/regr.pdf

2. Блог Дениса Баженова. [Электронный ресурс]. URL: // http://bazhenov.me/blog/2012/07/21/classification-performance-evaluation.html

3. Лекции по Методам оптимизации, ФКН ВШЭ. [Электронный ресурс]. URL: // http: //www. machinelearning.ru/wiki/images/3/3 f/MO 17_seminar7. pdf

4. Блог Себастьяна Рудера. [Электронный ресурс]. URL: https://ruder.io/optimizing-gradient-descent/