Сделай Сам Свою Работу на 5

Алгоритмы метода сопряженных градиентов

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

Если в обучающих алгоритмах градиентного спуска, управление сходимостью осуществляется с помощью параметра скорости настройки, то в алгоритмах метода сопряженных градиентов размер шага корректируется на каждой итерации. Для определения размера шага вдоль сопряженного направления выполняются специальные одномерные процедуры поиска минимума. В состав ППП Neural Network Toolbox включено 5 специализированных М-функций для организации одномерного поиска: scrchbac, scrchbre, srchcha, srchgol, scrchhyb.

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

Все алгоритмы метода сопряженных градиентов на первой итерации начинают поиск в направлении антиградиента

(3.22)

Когда выбрано направление, требуется определить оптимальное расстояние (шаг поиска), на величину которого следует изменить настраиваемые параметры:

(3.23)

Затем определяется следующее направление поиска как линейная комбинация нового направления наискорейшего спуска и вектора движения в сопряженном направлении:

(3.24)

Различные алгоритмы метода сопряженного градиента различаются способом вычисления константы bk.

Ниже описаны 4 алгоритма метода сопряженных градиентов.



Алгоритм CGF

Алгоритм CGF, реализующий метод Флетчера – Ривса [12, 18], использует следующее выражение для вычисления константы метода:

. (3.25)

В данном случае константа равна отношению квадрата нормы градиента на текущей
к квадрату нормы градиента на предыдущей итерации.

Вновь обратимся к сети, показанной на рис. 3.8, но будем использовать функцию
обучения traincgf:

net = newff([–1 2; 0 5],[3,1],{'tansig','purelin'},'traincgf');

Функция traincgf характеризуется следующими параметрами, заданными по умолчанию:

net.trainParam

ans =

epochs: 100

show: 25

goal: 0

time: Inf

min_grad: 1.0000e–006

max_fail: 5

searchFcn: 'srchcha'

scale_tol: 20

alpha: 0.0010

beta: 0.1000

delta: 0.0100

gama: 0.1000

low_lim: 0.1000

up_lim: 0.5000

maxstep: 100

minstep: 1.0000e–006

bmax: 26

Здесь epochs – максимальное количество циклов обучения; show – интервал вывода информации, измеренный в циклах; goal – предельное значение критерия обучения; time – пре­дельное время обучения; min_grad – минимальное значение градиента; max_fail – макси­маль­но допустимый уровень превышения ошибки контрольного подмно­жест­ва по срав­не­нию с обучающим; searchFcn – имя функции одномерного поиска; scale_tol – коэф­фи­ци­ент для вычисления шага tol процедуры одномерного поиска tol = delta/scale_tol; alpha – коэффициент, определяющий порог уменьшения критерия качества; beta – коэффициент, определяющий выбор шага; delta – начальный шаг разбиения интервала; gama – параметр, регулирующий изменение критерия качества; low_lim – нижняя граница изменения шага; up_lim – верхняя граница изменения шага; maxstep – максимальное значение шага; minstep – минимальное значение шага; bmax – максимальное значение шага для процедуры srchhyb.

Установим следующие значения параметров:

net.trainParam.epochs = 300;

net.trainParam.show = 5;

net.trainParam.goal = 1e–5;

p = [–1 –1 2 2;0 5 0 5];

t = [–1 –1 1 1];

net = train(net,p,t); % Рис.3.12

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

Рис. 3.12

a = sim(net,p)

a = –1.0015 –0.9978 0.9999 0.9986

Алгоритм Флетчера – Ривса CGF работает намного быстрее, чем градиентный алгоритм CGM с выбором параметра скорости настройки, а иногда и быстрее, чем алгоритм Rprop, как в рассматриваемом случае; хотя на практике это зависит от конкретной задачи. Алгоритмы метода сопряженных градиентов требуют не намного больше памяти, чем градиентные алгоритмы, поэтому их можно рекомендовать для обучения нейронных
сетей с большим количеством настраиваемых параметров.

Демонстрационная программа nnd12cg иллюстрирует работу алгоритмов минимизации на основе метода сопряженных градиентов.

Алгоритм CGP

Другой вариант алгоритма сопряженного градиента – это алгоритм CGP Полака – Рибейры (Polak – Ribiére) [12, 18]. Для этого алгоритма константа метода bk выражается следующим образом:

. (3.26)

Таким образом, коэффициент равен скалярному произведению приращения градиента на текущий градиент, деленному на квадрат нормы градиента на предыдущей итерации.

Вновь обратимся к сети, показанной на рис. 3.7, но будем использовать функцию обучения traincgp:

net = newff([–1 2; 0 5],[3,1],{'tansig','purelin'},'traincgp');

Функция traincgp характеризуется теми же параметрами, заданными по умолчанию, что и функция traincgf.

Изменим установку следующих параметров:

net.trainParam.epochs = 300;

net.trainParam.show = 5;

net.trainParam.goal = 1e–5;

p = [–1 –1 2 2;0 5 0 5];

t = [–1 –1 1 1];

net = train(net,p,t); % Рис.3.13

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

Рис. 3.13

a = sim(net,p)

a = –1.0014 –1.0015 0.9977 0.9983

Характеристика сходимости алгоритма CGP во многом похожа на характеристику алгоритма CGF. На практике трудно предсказать, какой алгоритм лучше применить для решения конкретной задачи. Однако требования по памяти для алгоритма CGP несколько больше, поскольку требуется на каждой итерации 4 вектора, в то время как для алгоритма CGF – только 3.

Алгоритм CGB

Для всех алгоритмов метода сопряженных градиентов направление поиска периодически переустанавливается на направление антиградиента, или, иными словами, выполняется рестарт. Это происходит в тех случаях, когда возникают проблемы со сходимостью. Например, если количество итераций превысило число настраиваемых параметров сети, либо возникли иные условия, свидетельствующие о плохой сходимости. Одна из таких стратегий рестарта реализована в алгоритме CGB, предложенном Биеле (Beale) и Пауэллом (Powell) [2, 33]. Согласно этой стратегии рестарт выполняется, если текущее и предшествующее направления градиентов слабоортогональны, и это условие определяется следующим образом:

. (3.27)

Рассмотрим работу этого алгоритма на примере нейронной сети (см. рис. 3.8)

net = newff([–1 2; 0 5],[3,1],{'tansig','purelin'},'traincgb');

Функция traincgb характеризуется теми же параметрами, заданными по умолчанию, что и функция traincgf.

Изменим установку следующих параметров:

net.trainParam.epochs = 300;

net.trainParam.show = 5;

net.trainParam.goal = 1e–5;

p = [–1 –1 2 2;0 5 0 5];

t = [–1 –1 1 1];

net = train(net,p,t); % Рис.3.14

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

Рис. 3.14

a = sim(net,p)

a = –1.0015 –1.0038 1.0045 1.0004

Характеристики алгоритма CGB в данном случае превосходят показатели сходимости алгоритма CGP, хотя для другой задачи или других начальных параметров это может оказаться не так. С точки зрения требований к оперативной памяти для алгоритма CGB требуется 6 векторов, в то время как для алгоритма CGP – 4.

Алгоритм SCG

Все рассмотренные выше алгоритмы, основанные на методе сопряженных градиентов, реализуют на каждой итерации процедуру одномерного поиска. Эта дорогостоящая
в вычислительном отношении процедура требует на каждой итерации несколько раз вычислять реакцию сети. Алгоритм SCG, предложенный Моллером (Moller) [29], позволяет избежать излишних затрат. Этот алгоритм объединяет идеи метода сопря­жен­ных гради­ентов с квазиньютоновыми методами, и в частности использует подход, реализо­ванный в алгоритме LM Левенберга – Марквардта.

Вновь обратимся к сети, показанной на рис. 3.7, но будем использовать функцию
обучения trainrp:

net = newff([–1 2; 0 5],[3,1],{'tansig','purelin'},'trainscg');

Функция trainrp характеризуется следующими параметрами, заданными по умолчанию:

net.trainParam

ans =

epochs: 100

show: 25

goal: 0

time: Inf

min_grad: 1.0000e–006

max_fail: 5

sigma: 5.0000e–005

lambda: 5.0000e–007

Первые 6 параметров рассматривались ранее. Поясним назначение последних двух параметров; параметр sigma управляет весом аппроксимированной матрицы Гессе, параметр lambda позволяет учесть степень неточности аппроксимации.

Изменим установки некоторых параметров:

net.trainParam.epochs = 300;

net.trainParam.show = 10;

net.trainParam.goal = 1e–5;

p = [–1 –1 2 2;0 5 0 5];

t = [–1 –1 1 1];

net = train(net,p,t); % Рис.3.15

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

Рис. 3.15

a = sim(net,p)

a = –1.0007 –1.0012 0.9986 1.0018

Алгоритм SCG может потребовать большего числа итераций, чем другие алгоритмы метода сопряженных градиентов, но при этом количество вычислений на каждой итерации существенно сокращено. Требования по памяти для алгоритма SCG примерно такие же, как и для метода CGF.

Квазиньютоновы алгоритмы

Алгоритм BFGS

Альтернативой методу сопряженных градиентов для ускоренного обучения нейронных сетей служит метод Ньютона. Основной шаг этого метода определяется соотношением

(3.28)

где – вектор настраиваемых параметров;– матрица Гессе вторых частных производных функционала ошибки по настраиваемым параметрам; – вектор градиента функционала ошибки. Процедуры минимизации на основе метода Ньютона, как правило, сходятся быстрее, чем те же процедуры на основе метода сопряженных градиентов.
Однако вычисление матрицы Гессе – это весьма сложная и дорогостоящая в вычислительном отношении процедура. Поэтому разработан класс алгоритмов, которые основаны на методе Ньютона, но не требуют вычисления вторых производных. Это класс квазиньютоновых алгоритмов, которые используют на каждой итерации некоторую приближенную оценку матрицы Гессе.

Одним из наиболее эффективных алгоритмов такого типа является алгоритм BFGS, предложенный Бройденом, Флетчером, Гольдфарбом и Шанно (Broyden, Fletcher, Goldfarb and Shanno) [9]. Этот алгоритм реализован в виде М-функции trainbfg.

Вновь обратимся к сети, показанной на рис. 3.7, но будем использовать функцию
обучения trainbfg:

net = newff([–1 2; 0 5],[3,1],{'tansig','purelin'},'trainbfg');

Параметры функции trainbfg практически совпадают с параметрами функции traincgf, за исключением используемой программы одномерного поиска, которая в данном случае заменена М-функцией srchbac.

Установим параметры обучающей процедуры по аналогии с предшествующими примерами:

net.trainParam.epochs = 300;

net.trainParam.show = 5;

net.trainParam.goal = 1e–5;

p = [–1 –1 2 2;0 5 0 5];

t = [–1 –1 1 1];

net = train(net,p,t); % Рис.3.16

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

Рис. 3.16

a = sim(net,p)

a = –1.0011 –1.0001 0.9999 1.0003

Алгоритм BFGS требует большего количества вычислений на каждой итерации
и большего объема памяти, чем алгоритмы метода сопряженных градиентов, хотя, как правило, он сходится на меньшем числе итераций. Требуется на каждой итерации хранить оценку матрицы Гессе, размер которой определяется числом настраиваемых параметров сети. Поэтому для обучения нейронных сетей больших размеров лучше использовать алгоритм Rprop или какой-либо другой алгоритм метода сопряженных градиентов. Однако для нейронных сетей небольших размеров алгоритм BFGS может оказаться эффективным.

Алгоритм OSS

Алгоритм OSS (One Step Secant), или одношаговый алгоритм метода секущих плоскостей, описан в работе Баттити (Battiti) [1]. В нем сделана попытка объединить идеи метода сопряженных градиентов и схемы Ньютона. Алгоритм не запоминает матрицу Гессе, полагая ее на каждой итерации равной единичной. Это позволяет определять новое направление поиска не вычисляя обратную матрицу.

Вновь обратимся к сети, показанной на рис. 3.7, но будем использовать функцию обучения trainoss:

net = newff([–1 2; 0 5],[3,1],{'tansig','purelin'},'trainoss');

Функция trainoss характеризуется теми же параметрами, заданными по умолчанию, что и функция trainbfg.

Установим параметры обучающей процедуры по аналогии с предшествующими примерами:

net.trainParam.epochs = 300;

net.trainParam.show = 5;

net.trainParam.goal = 1e–5;

p = [–1 –1 2 2;0 5 0 5];

t = [–1 –1 1 1];

net=train(net,p,t); % Рис.3.17

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

Рис. 3.17

a = sim(net,p)

a = –1.0020 –0.9988 0.9994 1.0002

Этот алгоритм требует меньших объемов памяти и вычислительных ресурсов на цикл по сравнению с алгоритмом BFGS, но больше, чем алгоритм CGF. Таким образом, алгоритм OSS может рассматриваться как некий компромисс между алгоритмами методов сопряженных градиентов и Ньютона.

Алгоритм LM

Алгоритм LM Левенберга – Марквардта [17] реализует следующую стратегию для оценки матрицы Гессе. В предположении, что функционал определяется как сумма квадратов ошибок, что характерно при обучении нейронных сетей с прямой передачей, гессиан может быть приближенно вычислен как

, (3.29)

а градиент рассчитан по формуле

(3.30)

где – матрица Якоби производных функционала ошибки по настраиваемым параметрам; e – вектор ошибок сети. Матрица Якоби может быть вычислена на основе стандартного метода обратного распространения ошибки, что существенно проще вычисления матрицы Гессе.

Алгоритм LM использует аппроксимацию гессиана следующего вида:

(3.31)

Когда коэффициент m равен 0, мы получаем метод Ньютона с приближением гессиана в форме (3.29); когда значение m велико, получаем метод градиентного спуска с маленьким шагом. Поскольку метод Ньютона имеет большую точность и скорость сходимости вблизи минимума, задача состоит в том, чтобы в процессе минимизации как можно быстрее перейти к методу Ньютона. С этой целью параметр m уменьшают после каждой успешной итерации и увеличивают только тогда, когда пробный шаг показывает, что функционал ошибки возрастает. Такая стратегия обеспечивает уменьшение ошибки после каждой итерации алгоритма.

Вновь обратимся к сети, показанной на рис. 3.8, но будем использовать функцию обучения trainlm:

net = newff([–1 2; 0 5],[3,1],{'tansig','purelin'},'trainlm');

Функция trainlm характеризуется следующими параметрами, заданными по умолчанию:

net.trainParam

ans =

epochs: 100

goal: 0

max_fail: 5

mem_reduc: 1

min_grad: 1.0000e–010

mu: 0.0010

mu_dec: 0.1000

mu_inc: 10

mu_max: 1.0000e+010

show: 25

time: Inf

В этом перечне появилось несколько новых параметров. Параметр mu – начальное значение для коэффициента m. Это значение умножается либо на коэффициент mu_dec, когда функционал ошибки уменьшается, либо на коэффициент mu_inc, когда функционал ошибки возрастает. Если mu превысит значение mu_max, алгоритм останавливается. Параметр mem_reduc позволяет экономить объем используемой памяти, что обсуждается ниже.

Установим параметры обучающей процедуры по аналогии с предшествующими
примерами:

net.trainParam.epochs = 300;

net.trainParam.show = 5;

net.trainParam.goal = 1e–5;

p = [–1 –1 2 2;0 5 0 5];

t = [–1 –1 1 1];

net = train(net,p,t); % Рис.3.18

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

Рис. 3.18

a = sim(net,p)

a = –1.0000 –0.9998 1.0000 0.9999

Как видим, здесь потребовалось всего 3 цикла обучения. Этот алгоритм, видимо,
является самым быстродействующим и пригоден для обучения больших нейронных сетей с несколькими сотнями настраиваемых параметров. Этот алгоритм имеет очень эффективную реализацию в системе MATLAB, являющейся интерпретатором векторной машины, где операция скалярного произведения реализуется с высокой точностью и быстродействием на математическом сопроцессоре компьютера. Поэтому достоинства алгоритма Левенберга – Марквардта становятся еще более ощутимыми при работе в среде системы MATLAB.

Демонстрационный пример nnd12m иллюстрирует применение алгоритма LM.

Экономия памяти. Главный недостаток алгоритма LM состоит в том, что он требует
памяти для хранения матриц больших размеров. Например, размер матрицы Якоби состав­ляет Q´n, где Q – число обучающих наборов и n – число параметров сети. Это означает, что при оценке гессиана согласно соотношению (3.28) потребуются значительные ресурсы для ее хранения и вычисления. Как это часто делается при работе с матрицами, выполним ее декомпозицию, т. е. представим ее в виде разбиения на несколько подматриц. Допустим, что выделены 2 подматрицы; тогда соотношение (3.28) может быть записано в виде:

. (3.32)

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

При применении М-функции trainlm с помощью параметра mem_reduc можно указывать, на какое число подматриц разбивается исходная матрица. Если параметр mem_reduc равен 1, то используется полная матрица Якоби; если mem_reduc = 2, то матрица Якоби разбивается
по строкам на 2 части и сначала обрабатывается одна половина, а затем вторая. Это экономит половину объема памяти, требуемой для вычисления полного якобиана. Что же касается быстродействия, то оно будет частично потеряно. И если вам доступна достаточная оперативная память, то лучше устанавливать параметр mem_reduc равным 1. Это особо касается системы MATLAB, которая позволяет извлечь все преимущества при использовании математического сопроцессора. Если же все-таки имеющаяся память оказалась исчерпанной, то следует назначить параметр mem_reduc равным 2 и выполнить расчеты заново. Если и при этом памяти
не будет достаточно, следует еще увеличить значение этого параметра.



©2015- 2020 stydopedia.ru Все материалы защищены законодательством РФ.