О скорости сходимости субградиентного метода с изменением метрики и его приложения в схемах нейросетевых приближений | Вестн Том. гос. ун-та. Математика и механика. 2018. № 55. DOI: 10.17223/19988621/55/3

О скорости сходимости субградиентного метода с изменением метрики и его приложения в схемах нейросетевых приближений

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

On the convergence rate of the subgradient method with metric variation and its applications in neural network approxima.pdf В задачах обучения по прецедентам (см., например, [1]) при небольших по размеру обучающих выборках и неизвестном виде математической модели возникает необходимость поиска соответствующего описания в виде искусственной нейронной сети (ИНС) [1-4]. При этом структура модели должна быть достаточной сложной для качественного описания данных и достаточно простой для обеспечения хороших обобщающих свойств [1]. Подобные проблемы возникают в различных практических приложениях аппарата ИНС [5-7]. Для устранения избыточного описания нейросети используют различные способы регуляризации [1, 8-12]. В задачах обучения ИНС при небольших обучающих выборках [1-4, 6, 7, 13] используют, как правило, сети с небольшим числом слоев, а в качестве методов обучения применяют методы сопряженных градиентов (МСГ) [13], квазиньютоновские (КНМ) [14, 15] и Левенберга - Марквардта (ЛМ) [16]. Учитывая неприменимость этих методов для решения негладких задач, слабую устойчивость методов ЛМ [13] и МСГ в условиях плохой обусловленности и росте размерности задачи представляется актуальным исследование методов обучения ИНС, имеющих высокую скорость сходимости как на гладких, так и негладких овражных функциях, в том числе и невыпуклых. К числу методов, обладающих возможностями минимизации негладких и, в том числе, невыпуклых функций, относятся релаксационные субградиентные методы (РСМ). Свойствами скорости сходимости, близкими свойствам метода сопряженных градиентов, обладают РСМ, предложенные в работах [17-22]. Существенного повышения эффективности РСМ удалось достичь в результате создания методов негладкой оптимизации с изменением метрики пространства [17, 23, 24]. В данной работе теоретически и экспериментально рассмотрен релаксационный субградиентный метод с двухранговой коррекцией матриц метрики (СМДМ) [23], который при исключении операции сжатия пространства эквивалентен r-алгоритму Н.З. Шора [17]. В статье установлено, что на сильновыпуклых функциях с липшицевым градиентом [14] метод сходится линейно. В силу инвариантных свойств алгоритма, полученная оценка справедлива и в системе координат с наилучшими для оценки скорости сходимости пропорциями констант сильной выпуклости и Липшица. Проведенный вычислительный эксперимент подтверждает близость свойств методов СМДМ и КНМ на квадратичных функциях и эффективность метода при минимизации негладких функций с высокой степенью вытяну-тости поверхностей уровня. Использование ИНС при небольших по размеру обучающих выборках наталкивается на проблемы выбора хорошего начального приближения и быстро наступающего переобучения в случае излишнего числа нейронов. Предложен новый эффективный способ выбора начального приближения ИНС. Использование регуляризации позволило исключить эффекты переобучения и эффективно удалять малозначимые нейроны и связи внутри нейронов. Возможности эффективного решения подобных задач обеспечены методом СМДМ. В статье приведены примеры решения задач обучения ИНС. 2. О скорости сходимости субградиентного метода с изменением метрики Рассматривается задача минимизации дифференцируемой функции f(х), х е Rn , где Rn - конечномерное евклидово пространство. Обозначим (х, у) -скалярное произведение векторов, ||х|| = -у/(х, х) - норму вектора. Для произвольной симметричной строго положительно определенной матрицы И размера n х n будем использовать обозначение И > 0 . Условие А. Будем предполагать, что функция f (х), х е Rn, дифференцируема и сильновыпукла с константой l > 0 [14]: f(X + (1 -Х)у) < Xf (х) + (1 -X)f(y)-lX(1 -Х)\\х-у||2/2, 0 1 - c при c > 0: ( II ll2 Л \ - Uyi ( i2\\ ||2 Л l IIУк|I Vk+1 < Vk < Vk exp LI g 112 2||„ ||2 kll У L2 I g kll У Рекуррентное использование последнего неравенства приводит к оценке (10). Теорема доказана. В следующей теореме обосновывается линейная скорость сходимости метода СМДМ. Теорема 2. Пусть функция f (x) удовлетворяет условию A . Тогда для последовательности {fk }, k = 0,1,2,..., заданной процессом (3) - (6), с ограниченной начальной матрицей H 0 m0 < (H0z,z)/(z,z) (Hkg(xk), g(xk)). Отсюда, с учетом неравенства Sp(Ak) > Mk, где Mk - максимальное собственное значение матрицы Ak , получим 1+ (15) Sp(Ak)(Hkyk, ук) > Sp(Ak)(Hkg(xk), g(xk)) > > Sp(Ak), -(g(xk )k, g(xk)) > (g(xkX g(xk)). Mk Неравенство (15) на основании последней оценки преобразуется к виду Sp(Ak+j) < Sp(Ak) 2 ,4 Ibkl I2 1 + (a2 -1) (16) llg (xk )|f На основе соотношения между среднеарифметическим и среднегеометрическим собственных значений матрицы A > 0 имеем Sp(A)/n > [det(A)]1n. Отсюда > Sp(Ak+1) > (det(Ak+1))1/n = [(a2p2)k + detA]1 и из(16) получим k Sp( Л) п 1 + (а2 -1) llg (X )112 i=0 Последнее неравенство на основе соотношения 1 + p < exp(p) преобразуем к виду > (a^pWn(det(A0))1/n. (17) llg (X Ж J i=0 2 n В силу условия (13) Sp(A0)/n < 1/m0, (det(A0))11 n > 1/M0. Логарифмируя (17), с учетом последних неравенств, найдем yJyjL > 2(k + 1)ln(aP) + lnK /M0) Щ\g(X )f n(a2 -1) (a2 -1) , что вместе с (10) доказывает (14). Теорема доказана. Полученные оценки скорости сходимости не объясняют факт высокой скорости сходимости метода СМДМ, например, на квадратичных функциях. Для обоснования наличия ускоряющих свойств у метода нам необходимо показать его инвариантность относительно линейного преобразования координат, а затем использовать оценку (14) в системе координат, в которой отношение l / L максимально. Подобная возможность существует, например, в случае квадратичных функций, где это отношение будет равно 1. Пусть задано линейное преобразование координат X = Px , X, х e Rn, где X -переменные новой системы координат, Р - невырожденная матрица размера nxn. Образуем функцию f (X) = f (P-1X) = f ( x) . Здесь и далее черта сверху - признак принадлежности одноименной переменной новой системе координат. Обозначим P- = (PT )-1. Установим соответствие между характеристиками процесса (3) - (5), применяемого для минимизации функций f (X) и fX). Лемма 1. Пусть начальные условия процесса (3) - (5), применяемого для минимизации функций f (X) и f (х) , связаны равенствами X0 = PX0, H0 = PH0 PT . (18) Тогда характеристики этих процессов связаны соотношениями f(Xk) = f (Xk), Xk = PXk , g(Xk) = P-Tg (Xk) , Hk = PHkPT ( k = 0,1,2,...). (19) Доказательство. Для производных функций f (X) и f (x) справедлива взаимосвязь g (X) = P ~Tg ( x) . Отсюда и предположения (18) следует (19) при k = 0. Предположим, что равенства (19) выполнены при всех k = 0,1,.,i. Покажем их выполнимость при k=i+1. Из (3) при k = i после умножения на Р слева с учетом доказанных равенств (19) получим PXi+1 = Pxt - Y,PH,PTP-Tg(X) = х- -YHg(х-). (20) (a2 -1)] SP( A0)exp Отсюда, согласно определению функции f, на этапе одномерной минимизации (4) выполняется равенство yt = yt. Поэтому правая часть (20) - реализация шага (3) в новой системе координат. Следовательно: Pxt+1 = Х+^ g(Xt+1) = P_Tg(xi+1) и У = g(x+1) - g(X ) = P- . (21) Помножая (5) слева на Р, а справа на PT, с учетом (21) получим PHMPT = P^PT - (1 - J_) ШгРТР ТУгУТгРP i+1 г ( а2) (Уг, P PHtP P Уг) - (1 - ±) PH1PT^Tp1pT P-1PHJ PT = р2 (Рг, p-lPHkpTp-TPt) = H -(i-_1л Hp!H _(1 - 1 HiPtpJHJ ' а2 (H&,У) p2 (Hp, pt) ' где правая часть есть реализация формулы (5) в новой системе координат. Поэтому PHi+1PT = Hi+1. Следовательно, равенства (19) будут справедливы и при k = i + 1. Продолжая процесс индукции, получим доказательство леммы. Обозначим через lP, LP соответственно константы сильной выпуклости и Липшица для функции f (x). Введем функцию K(P) = lP / LP . Обозначим V матрицу преобразования координат такую, что K(V) > K(P) для произвольных невырожденных матриц Р. Теорема 3. Пусть функция f (x) удовлетворяет условию A . Тогда для последовательности {fk }, k = 0,1,2,..., заданной процессом (3) - (6), с ограниченной начальной матрицей H0 (13) имеет место оценка 2(k +1) ln(qp) ln(m / M) и(а2 -1) (а2 -1) _ 1(2 hk+1 l/L оценка (22) оказывается предпочтительнее. Такая ситуация возникает, например, при минимизации квадратичных функций, матрицы вторых производных которых имеют большой разброс собственных значений. Второе слагаемое оценки (22) характеризует этап настройки матрицы СМДМ-алгоритма. При больших значениях а настройка матрицы протекает интенсивнее. Таким образом, при конечных значениях параметра растяжения пространства алгоритм СМДМ на сильно выпуклых функциях, без предположения существования вторых производных, обладает ускоряющими свойствами сравнительно с методом скорейшего спуска. 3. Результаты вычислительного эксперимента 1. Исследование скорости сходимости алгоритма СМДМ. Предварительный вычислительный эксперимент имеет целью сравнить скорости сходимости квазиньютоновского метода Бройдена - Флетчера - Гольдфарба - Шанно (BFGS) [15] и СМДМ и на квадратичных функциях с высокой степенью обусловленности (ц = 1010). Вторая часть эксперимента состоит в соотнесении скорости сходимости СМДМ на квадратичных и негладких функциях с равной степенью вытянуто-сти функции: n f1(x) = £x2 • (1 + (i -1)(105 -1)/(n -1))2, x0il = 1, x* = 0, i = 0,1,2,...,n , i=1 f2(x) = X|x,.|-(1 + (i -1)(105 - 1)/(n-1)), х0,г = 1, x*= 0, i = 0,1,2,.,n . i=1 Обозначим it - число итераций метода, а nfg -количество вычислений функции и градиента, требуемые для достижения заданной точности ^ - f * < е . Результаты для методов приведены в табл. 1. Таблица 1 Результаты сходимости методов на сложных функциях Функция f (е =10-10) f (е =10-5) f = f1 + f( е =10-5) Методы BFGS (it/nfg) СМДМ (it/nfg) СМДМ (it/nfg) СМДМ (it/nfg) n = 500 543/993 755 / 1267 2747/ 4883 2596 / 4600 n = 1000 1049/1974 1330 / 2144 5451 / 9159 5178 / 8305 n = 5000 5100 / 9873 5411 / 8321 20073 / 29607 18328 / 26514 Метод BFGS является конечным на квадратичных функциях с числом итераций, равным размерности задачи. Стратегии методов BFGS и СМДМ различные. В квазиньютоновских методах важна точность одномерного поиска, а в релаксационных субградиентных алгоритмах наоборот, чем больше окрестность поиска, тем эффективнее выбор направления для последующего выхода из этой окрестности. Результаты табл. 1 свидетельствуют о практической идентичности методов на квадратичных функциях с высокой степенью обусловленности и высокой эффективности СМДМ при минимизации сложных негладких функций f2 и f3. В представленных ниже сценариях обучения ИНС требуется высокая точность решения задач негладкой минимизации. Данный эксперимент дает определенные гарантии возможности СМДМ решать подобные задачи. 2. Задача аппроксимации двухслойной ИНС сигмоидального типа. ИНС представляют собой мощный инструмент аппроксимации и находят применение в различных областях, в том числе и при решении уравнений математической физики [6, 7]. Требования к аппарату приближения - это надежность и качество приближения. Ниже будут изложены способы решения подобных проблем, где важную роль играет исследованный выше релаксационный субградиентный метод с двухранговой коррекцией матриц метрики СМДМ. Рассмотрим задачу аппроксимации w* = argmin E(a,w,D), w E(a, w, D) = Xx,^d (у - f (x, w))2 + Xk=1 aR (w), (23) где D = {(хг, yi )| х' е RP, yi е R1}, i = 1,..., Ж} - данные наблюдения, Ri (w) - различные виды регуляризаторов; a' - параметры регуляризации, f (х, w) - аппроксимирующая функция; х е RP - вектор данных; w е Rn - вектор настраиваемых параметров, р и n - их размерности. В качестве регуляризаторов можно использовать следующие: R2(w) = Xn=1 w'2 [8], R1(w) = Xnjw' | [26], RY(w) = Xnj\wj + е)У (s = 10-6, у = 0.7) [9]. Использование R2 приводит к подавлению в большей мере больших компонент вектора w, R1 - больших и малых, а Ry - преимущественно малых. Подобное свойство Ry позволяет сводить к нулю слабые компоненты, несущественные для описания данных. В задачах приближения ИНС в отсутствие помех мы будем использовать регуляризатор Ry . В задаче аппроксимации сетью прямого распространения требуется по данным D обучить двухслойную сигмоидальную нейронную сеть следующего вида (оценить ее неизвестные параметры w): f (х, w) = w02) +X m=1 w(2) ф (Si ) , 9(s) = s /(1+ | s |) , Si = w^ +XpP=1 i = 1,2,...,m , (24) где Xj - компоненты вектора хеRP , w=((w(2^,i = 0,...,m),(w?-1, j=0,...,р, i=1,...,m)) - набор неизвестных параметров, которые необходимо оценить методом наименьших квадратов (23), ф^) - функция активации нейрона, m - число нейронов. Для решения задач (23) используем субградиентный метод СМДМ. 3. Оптимизационный алгоритм нахождения начального приближения ИНС. Начальное приближение в задаче обучения ИНС играет решающую роль. В литературе по нейронным сетям [2, 3] предлагается задавать начальные значения параметров нейронов w случайным образом. Рассмотрим процесс задания начальных параметров сети, в котором каждому нейрону отводится зона активного приближения данных и при этом зоны нейронов покрывают область данных. Рабочие области нейронов ф(s) в (24) имеют характер активной зависимости только в некоторой окрестности значений s = 0, а при значительных отклонениях значений s от нуля значения ф^) близки к своим асимптотам, принимающим значения {-1, 1}. Важно иметь такие параметры нейронов w, которые обеспечивают для векторов области данных х е RP принадлежность рабочей области хотя бы одного нейрона. При произвольном задании начальных параметров в задаче минимизации (23) зачастую оказывается, что рабочие области нейронов охватывают только часть области аппроксимации либо выходят за ее пределы, образуя локальные минимумы, выход из которых нельзя осуществить приемами локальных изменений текущего приближения. Даже если предположить, что рабочие области нейронов расположены правильно, нельзя гарантировать, что их положение сохранится при дальнейшем решении задачи обучения. Расположение нейронов в точках с высокой концентрацией данных также не обеспечивает сохранения этого положения, поскольку при дальнейшем обучении нейроны могут покинуть изначально заданные области. Поэтому требуется дополнительная привязка рабочих областей нейронов посредством обучения нейросети при фиксированных центрах. В этом случае нейрон сможет покинуть свой регион только в случае, когда в этом регионе будет обеспечена уже имеющаяся точность приближения данных. В следующем алгоритме предлагается найти приближение ИНС, т.е. параметры нейронов при фиксированном положении рабочих областей нейронов с помощью заданных центров ci e Rp, i = 1,2,...,m, в области аппроксимации х e Rp , определяемой данными. В этом случае в (24) будут использоваться выражения si =X-cj W^ i = и,..m , w = ((w(2), i = 0,...,m), (w£\ j = 1,...,p, i = 1,...,m)) . (25) Центры ci можно найти некоторым алгоритмом кластеризации данных х' e Rp, i = 1,...,N, что полезно и с точки зрения расположения нейронов в областях с высокой плотностью данных. В этой работе использовался максиминный алгоритм [27], в котором в качестве первых двух центров выбираются две максимально удаленные друг от друга точки данных. Каждый новый центр получается выбором точки данных X , расстояние от которой до ближайшего известного центра максимально. Оптимизационный алгоритм нахождения начального приближения ИНС (ОНП). 1. Задать данные D, число нейронов m

Ключевые слова

метод, субградиент, минимимизация, скорость сходимости, нейронные сети, регуляризация, method, subgradient, minimization, rate of convergence, neural networks, regularization

Авторы

ФИООрганизацияДополнительноE-mail
Крутиков Владимир НиколаевичКемеровский государственный университет доктор технических наук, профессор кафедры прикладной математикиkrutikovvn@rambler.ru
Самойленко Наталья СергеевнаКемеровский государственный университет аспирантка кафедры прикладной математикиnostienataly@mail.ru
Всего: 2

Ссылки

Воронцов К.В. Курс лекций «Математические методы обучения по прецедентам» URL: http://www.machinelearning.rU/wiki/images/6/6d/Voron-ML-1.pdf
Хайкин С. Нейронные сети: полный курс. М. : Вильямс, 2006. 1104 с.
Осовский С. Нейронные сети для обработки информации. М.: Горячая линия - Телеком, 2016. 448 с.
Горбань А.Н. Обучение нейронных сетей. М.: Изд-во СССР - США СП «Параграф», 1990. 160 с.
Бурнаев Е.В., Приходько П.В. Об одной методике построения ансамблей регрессионных моделей // Автомат. и телемех. 2013. Вып. 10. С. 36-54.
Горбаченко В.И., Жуков М.В. Решение краевых задач математической физики с помощью сетей радиальных базисных функций // Журнал вычислительной математики и математической физики. 2017. Т. 57. № 1. С. 133-143.
Кретинин А.В. Метод взвешенных невязок на базе нейросетевых пробных функций для моделирования задач гидродинамики // Сиб. журн. вычисл. матем. 2006. Т. 9. № 1. С. 23-35.
Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1986.
Крутиков В.Н., Арышев Д.В. Алгоритм последовательного отсева неинформативных переменных линейной модели // Вестник Кемеровского государственного университета. 2004. № 3(7). С. 124-129.
Li Wang, Ji Zhu, Hui Zou. The doubly regularized support vector machine // Statistica Sinica. V. 16. No. 2. P. 589-615.
Tatarchuk A., Mottl V., Eliseyev A., Windridge D. Selectivity supervision in com-bining pattern-recognition modalities by feature- and kernel-selective Support Vector Machines // Proc. of the 19th Int. Conf. on Pattern Recognition, Vol. 1-6, IEEE, ISBN 978-1-4244-21749. 2008. P. 2336-2339.
Tatarchuk A., Urlov E., Mottl V., Windridge D. A support kernel machine for supervised selective combining of diverse pattern-recognition modalities // Multiple Classifier Systems. Lecture Notes In Computer Science. V. 5997. Berlin; Heidelberg: Springer-Verlag, 2010. P. 165-174.
Алкезуини М.М., Горбаченко В.И. Совершенствование алгоритмов обучения сетей радиальных базисных функций для решения задач аппроксимации // Модели, системы, сети в экономике, технике, природе и обществе. 2017. № 3 (23). C. 123-138.
Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
Дэннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. М.: Мир, 1988.
Marquardt D.W. An algorithm for least-squares estimation of nonlinear parameters // J. Society for Industrial and Applied Mathematics. 1963. V. 11. No 2. P. 431-441.
Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979.
Wolfe Ph. Note on a method of conjugate subgradients for minimizing nondifferentiable functions // Math. Program. 1974. V. 7. No. 1. P. 380-383.
Lemarechal C. An extension of Davidon methods to non-differentiable problems // Math. Program. Study. 1975. V. 3. P. 95-109.
Нурминский Е.А., Тьен Д. Метод сопряженных субградиентов с ограниченной памятью // Автомат. и телемех. 2014. № 4. P. 67-80; Autom. Remote Control. 2014. V. 75. No. 4. P. 646-656.
Крутиков В.Н., Вершинин Я.Н. Многошаговый субградиентный метод для решения негладких задач минимизации высокой размерности // Вестник Томского государственного университета. Математика и механика. 2014. № 3. С. 5-19.
Крутиков В.Н., Вершинин Я.Н. Субградиентный метод минимизации с коррекцией векторов спуска на основе пар обучающих соотношений // Вестник Кемеровского государственного университета. 2014. T.1. № 1 (57). С. 46-54. DOI: https://doi.org/10.21603/ 2078-8975-2014-1-46-54
Крутиков В.Н., Горская Т.А. Семейство релаксационных субградиентных методов с двухранговой коррекцией матриц метрики // Экономика и мат. методы. 2009. Т. 45. Вып. 4. С. 37-80.
Крутиков В.Н., Петрова Т.В. Релаксационный метод минимизации с растяжением пространства в направлении субградиента // Экономика и мат. методы. 2003. Т. 39. Вып. 1. С. 106-119.
Карманов В.Г. Математическое программирование. М.: Наука, 1980. 256 с.
Tibshirani R.J. Regression shrinkage and selection via the lasso // J. Royal Statistical Society. Series B (Methodological). 1996. V. 58. No. 1. P. 267-288.
Ту Дж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978.
Conn A.R., Gould N.I.M., Toint P.L. Trust regions methods. Society for Industrial and Applied Mathematics, 2000. 959 p.
Гудфеллоу Я., Бенджио И., Курвилль А. Глубокое обучение. - М.: ДМК Пресс, 2017. 652 с.
Sutskever I., Martens J., Dahl G., Hinton G. On the importance of initialization and momentum in deep learning // Proc. 30th Int. Conf. on Machine Learning. V. 28. Atlanta, Georgia, 2013. P. 1139-1147.
 О скорости сходимости субградиентного метода с изменением метрики и его приложения в схемах нейросетевых приближений | Вестн Том. гос. ун-та. Математика и механика. 2018. № 55. DOI: 10.17223/19988621/55/3

О скорости сходимости субградиентного метода с изменением метрики и его приложения в схемах нейросетевых приближений | Вестн Том. гос. ун-та. Математика и механика. 2018. № 55. DOI: 10.17223/19988621/55/3