авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 10 |

«Федеральное агентство по образованию САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ А.Н.ВАСИЛЬЕВ, Д.А.ТАРХОВ НЕЙРОСЕТЕВОЕ ...»

-- [ Страница 4 ] --

2.5. Динамическая кластеризация и сети Кохонена В данном параграфе рассматриваются модификации алгоритмов кластеризации, применимые в ситуации, когда классифицируемая выборка меняется со временем [111]. Мы будем рассматривать различные варианты таких задач, начиная с простейших. При этом основное внимание обращается на формирование структуры соответствующих сетей Кохонена. Построенные алгоритмы используются далее для динамического формирования структуры нейронных сетей в процессе моделирования меняющейся со временем выборки и решения ряда других задач моделирования, которые обсуждаются в следующих параграфах.

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

Второй вариант заключается в том, что ось времени рассматривается в качестве одной из координат.

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

Алгоритм 2.10. Обучение сети Кохонена в случае кластеров, следующих друг за другом.

1. В качестве начальных значений весов первого нейрона берём координаты первого входного вектора.

2. Подаём по-очереди некоторое заранее заданное число N1 входных векторов и проводим обучение этого нейрона.

3. Следующий входной вектор берём в качестве начальных весов нового нейрона и продолжаем подавать последующие векторы на предыдущий нейрон без обучения, одновременно обучая новый.

4. Если для N1 новых векторов хотя бы один раз победителем окажется старый нейрон, то новый нейрон ликвидируется и на соответствующих ему входных векторах обучается предыдущий нейрон.

5. Следующий входной вектор берём в качестве начальных весов очередного нейрона и шаги 3 и 4 повторяем.

Рис.2.10. Блок-схема алгоритма обучения сети Кохонена в случае кластеров, следующих друг за другом Третий вариант возникает тогда, когда одному моменту времени соответствует не один, а целый набор входных векторов, и нас интересует динамика кластеров, т.е. изменение их центров, размеров и т.п.

Самая простая процедура обучения сети Кохонена, соответствующей данному случаю, такова. Берём веса первого нейрона в фиксированный момент времени w1 (t ) и ищем ближайший к нему нейрон в следующий момент и обозначаем его веса w1 (t + 1), делаем то же самое для весов второго нейрона и т.д. Если число нейронов постоянно, и мы считаем, что кластеры (и веса нейронов) от одного момента времени к другому меняются мало, то при работе с весами w 2 (t ) мы можем исключить из рассмотрения w1 (t + 1) и для каждого следующего нейрона ближайший нейрон будем искать на множестве, которое на один элемент меньше, чем для предыдущего.

Если действовать таким образом, то для последнего нейрона с весами w m (t ), где m – число нейронов в сети, останется только один нейрон, но его веса могут быть весьма далёкими от w m (t ). Более правильный подход – искать || w (t ) w (t + 1) || по всем перестановкам номеров j1, j2,..., jm, минимум i j (i ) j (i ) применяя специальные методы дискретной оптимизации для того, чтобы избежать прямого перебора. Однако эти методы весьма трудоёмки, и необходимость применять их для каждого момента времени заставляет ограничиваться маленькими сетями.

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

Алгоритм 2.11. Алгоритм сопоставления нейронов сети Кохонена в разные моменты времени.

1. Проводим обучение сети Кохонена отдельно для каждого момента времени.

2. Для каждого вектора весов w i (t ) ищется ближайший вектор w j (i ) (t + 1), а для каждого вектора w j (t + 1) ищется ближайший w i ( j ) (t ).

3. Если получается взаимно однозначное соответствие, то задачу можно считать решённой.

4. Если какой-то вектор весов w i (t ) соответствует двум и более векторам w j (t + 1), то можно предположить, что кластер разделился.

5. Если этот вектор не является ближайшим ни для какого вектора w j (t + 1), то можно предположить, что кластер исчез.

6. Возможны и более сложные ситуации: например, для вектора w1 (t ) ближайшим является вектор w1 (t + 1), для вектора w1 (t + 1) – вектор w 2 (t ), а для вектора w 2 (t ) – вектор w 2 (t + 1). Для того чтобы в этой ситуации сделать определённый вывод, надо найти минимальную из величин || w1 (t ) w1 (t + 1) ||2 + || w 2 (t ) w1 (t + 1) ||2, || w1 (t ) w1 (t + 1) ||2 + || w 2 (t ) w 2 (t + 1) ||2, || w 2 (t ) w1 (t + 1) ||2 + || w 2 (t ) w1 (t + 1) ||2.

Более точно сопоставить кластеры можно, учитывая, что расстояние между кластерами не вполне определяется расстояниями между их центрами.

При этом естественно учесть элементы классов, например, заменяя на шаге || w i (t ) w j (t + 1) ||2 || w i (t ) x j (t + 1) ||2, величину на x j M j ( t +1) || xi (t ) w j (t + 1) ||2, || xi (t ) x j (t + 1) ||2 или max || xi (t ) x j (t + 1) ||, x j M j ( t +1) xi M i ( t ) x j M j ( t +1) xi M i ( t ) xi M i ( t ) где M i (t ) – кластер с номером i, соответствующий моменту времени t.

Рис.2.11. Блок-схема алгоритма сопоставления нейронов сети Кохонена в разные моменты времени Более простая ситуация возникает, если отказаться от параллельной кластеризации для всех моментов времени и производить её последовательно.

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

В результате эволюция кластеров будет происходить естественным образом.

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

Применение динамической кластеризации. Динамическая кластеризация может быть использована в следующем алгоритме.

Алгоритм 2.12. Генетический алгоритм построения коллектива нейронных сетей прямого распространения с временными задержками.

1. Исходная выборка в каждый момент времени ( x1 ( n), y1 ( n)), ( x 2 (n), y2 (n)),..., ( x N ( n), y N (n)) кластеризуется.

2. Производим сопоставление кластеров (нейронов сети Кохонена), соответствующих друг другу в разные моменты времени.

3. На каждом кластере в первый момент обучается своя нейронная сеть, при этом для подбора её структуры может использоваться некоторый генетический алгоритм.

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

5. Шаги 2-4 повторяются необходимое число раз.

Рис.2.12. Блок-схема генетического алгоритма построения коллектива нейронных сетей прямого распространения с временными задержками Заметим, что указанный алгоритм может быть применён к формированию динамических нейронных сетей различной архитектуры. Кроме того, следует отметить хорошие возможности для его распараллеливания и выполнения в распределённой форме (о распределённых вычислениях см. главу 3).

Алгоритм 2.13. Двойной генетический алгоритм построения коллектива нейронных сетей прямого распространения с временными задержками.

1. Исходная выборка в начальный момент времени ( x1 (1), y1 (1)), (x 2 (1), y2 (1)),..., (x N (1), y N (1)) кластеризуется.

2. На каждом кластере обучается своя нейронная сеть, при этом для подбора её структуры может использоваться некоторый генетический алгоритм.

3. Повторяем шаг 1 для следующего момента времени и производим сопоставление кластеров.

4. Рассматриваем веса получившейся сети как начальные значения весов сети для второго момента времени и повторяем шаг 2.

5. Производим мутации (добавляются и исключаются точки кластеров и веса связей между моментами времени, осуществляем сдвиг нейронов по времени), транслокации (кластеры обмениваются точками, обмениваются связи их нейронов, соответствующие разным временным отсчётам) и скрещивание (сети, соответствующие двум кластерам объединяются и дообучаются, если это необходимо).

6. К каждой сети относятся те наблюдения, для которых она даёт минимальную ошибку. Если к какой-либо сети относится слишком мало точек, то она исчезает из популяции, а относящиеся к ней точки распределяются снова по тому же принципу между оставшимися сетями 7. Шаги 3-6 повторяются последовательно для всех моментов времени.

Рис.2.13. Блок-схема двойного генетического алгоритма построения коллектива нейронных сетей прямого распространения с временными задержками 2.6. RBF-сети с временными задержками Целью данного параграфа является обсуждение различных форм RBF сетей с временными задержками и алгоритмов их формирования. Применяемые формы RBF-сетей существенно зависят от решаемых задач моделирования.

Первая форма временных RBF-сетей позволяет моделировать ситуации, когда происходят некоторые события, влияние которых ослабевает со временем. При этом формула (1.42) преобразуется в формулу m y = w j j ( x c j, t t j ). (2.3) j = Здесь в качестве i может быть взята, например, функция Гаусса j ( t t j ) j x c j. (2.4) e При этом моменты времени t j, когда происходят упомянутые события, можно трактовать по-разному:

1) t j – заранее известные фиксированные моменты времени. В этом случае остальные коэффициенты можно находить с помощью обычных процедур оптимизации или каким-либо другим образом, типичным для RBF сетей. Приведём пример алгоритма такого рода, опирающийся на идеи алгоритма 2.5.

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

1. Начинаем с кластеризации выборки в моменты времени t j по какому-либо алгоритму, например, строим сеть Кохонена одним из представленных ранее алгоритмов.

2. Производим сопоставление кластеров, полученных на предыдущем шаге с помощью какого-либо метода из предыдущего параграфа.

3. Для каждого кластера (который уже соответствует всем моментам t j ) строим его аппроксимацию своей базисной функцией, т.е. по точкам, j -й кластер, определяем w j, j (и jl или jls, если вошедшим в рассматривается соответствующая сеть, см. замечание ниже) и c j.

4. Для остальных моментов времени, не совпадающих ни с одним из t j, вычисляем ошибки аппроксимации.

5. Минимизируем ошибки аппроксимации, подбирая параметры сетей.

Найденные ранее параметры используются в качестве начальных значений.

6. Если используется генетический алгоритм, производим мутации (добавляются и исключаются точки кластеров), транслокации (кластеры обмениваются точками) и скрещивание (сети, соответствующие двум кластерам объединяются и дообучаются, если это необходимо).

Вычисляем ошибки аппроксимации n (t ) для всех моментов 7.

времени t, соответствующих выборке.

Повторяем шаги 1 – 7 для выборки {x n (t ), n (t )}.

8.

9. Повторяем процесс, пока ошибки не станут достаточно малыми.

Рис.2.14. Блок-схема алгоритма кластеризации ошибок для известных моментов событий 2) Заранее неизвестные моменты времени t j, как и c j, находятся с помощью какой-либо процедуры кластеризации.

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

1. Начинаем с кластеризации всей выборки {x n (t ), yn (t )} по какому либо алгоритму.

2. Для каждого кластера строим его аппроксимацию своей базисной функцией, т.е. по точкам, вошедшим в j -й кластер, определяем момент t j и веса w j, j (и jl или jls ) и c j как центр кластера. При этом возможна ситуация, когда моменты t распределены непрерывно, тогда t j находим как среднее время, отвечающее кластеру, или с помощью некоторой процедуры оптимизации вместе с остальными параметрами. Если моменты t распределены дискретно, то среднее время, отвечающее кластеру, можно округлить до ближайшего целого момента или построить процедуру перебора ближайших моментов с подбором остальных параметров и выбором нужного варианта.

3. Дообучаем сеть по некоторому алгоритму нелинейной оптимизации (см. главу 3).

Вычисляем ошибки аппроксимации n (t ).

4.

Повторяем шаги 1-4 для выборки {x n (t ), n (t )}.

5.

6. Повторяем процесс, пока ошибки не станут достаточно малыми.

Рис.2.15. Блок-схема алгоритма кластеризации ошибок для неизвестных моментов событий Параметры t j, j, c j и w j находятся с помощью минимизации 3) функционала ошибки. При этом для градиента функционала получаются формулы, аналогичные формулам для стационарного случая, и мы можем применить для обучения сети какой-нибудь градиентный алгоритм. Если моменты t распределены дискретно, то можно совместить переборный или генетический алгоритм выбора t j с обычным алгоритмом подбора j, c j и w j.

Для определения структуры сети можно применить какой-либо из генетических алгоритмов.

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

Если событие вызвано внешними причинами, никак не проявлявшимися до его наступления, и влияние этого события затухает со временем, то в качестве базисной может быть использована функция e j j ( t t j ) x c j при t t j j = (2.5) при t t j Медленнее убывает функция Коши, которую можно использовать только по времени e j x c j при t t j j = 1 + j (t t j ) 2. (2.6) при t t j или и по пространству, и по времени 1 + x c 2 + (t t )2 при t t j j =. (2.7) j j j j при t t j Эти асимметричные функции допускают такие же три варианта работы с параметрами t j, что и представленные выше симметричные функции. Отличие будет состоять только в том, что моменты t j будут связаны не с серединами временных интервалов, в которых расположены рассматриваемые кластеры, а с их началом.

Разумеется, можно использовать и двусторонний вариант функции Коши, так же, как это было сделано с функцией Гаусса (2.4).

Аналогично тому, как это было сделано в предыдущей главе, можно рассмотреть анизотропный случай. Если анизотропия проявляется только в k jl ( xl c jl )2 j (t t j ) неравноправии координат, то вместо (2.4) можно взять j = e,а l = если характерные направления расположены не вдоль координатных осей, то k k jls ( xl c jl )( xs c js ) j (t t j ) придётся рассматривать функции j = e. Аналогичные s =1 l = преобразования можно применить к формулам (2.5)-(2.7).

К временным сетям можно применить почти такой же алгоритм построения коллектива сетей, какой был приведён для статических сетей.

Отличие состоит в применении динамической кластеризации и определении неизвестных моментов времени, соответствующих центрам кластеров.

Алгоритм 2.16. Алгоритм построения коллектива RBF-сетей.

1. Начинам с кластеризации всей имеющейся выборки {x n (t ), yn (t )} по какому-либо алгоритму, при этом кластеры могут пересекаться.

2. Для каждого кластера строим его аппроксимацию своей базисной функцией, т.е. по точкам, вошедшим в j -й кластер, определяем t j, w j, j (и jl или jls ) и c j.

3. Из базисных функций образуем некоторый набор (популяцию) RBF сетей, суммируя базисные функции, соответствующие близким кластерам. При этом одна базисная функция может войти в сумму для нескольких сетей.

4. К каждой RBF-сети из популяции относятся те наблюдения, для которых она даёт минимальную ошибку. Если к какой-либо сети относится слишком мало точек, то она исчезает из популяции.

5. Сети обучаются каждая на своих данных.

6. Производятся мутации: добавляются и исключаются точки кластеров, временные моменты t j сдвигаются на один такт, два близких кластера, соответствующие одной сети, объединяются в один. Производятся транслокации: кластеры обмениваются точками, меняется тип базисных функций (с Гауссовой – на Коши или двусторонней – на одностороннюю и наоборот), базисные функции, соответствующие близким моментам, обмениваются коэффициентами. Производится скрещивание: сети, соответствующие двум близким группам кластеров, объединяются и дообучаются, если это необходимо.

7. К точкам, для которых не существует сети, дающей достаточно малую ошибку, применяем шаги 1-6.

8. Шаг 7 повторяется до тех пор, пока не будут исчерпаны все точки выборки, т.е. для любой точки выборки найдётся сеть, дающая в этой точке достаточно малую ошибку.

9. Строится вспомогательная сеть, которая определяет, к какой RBF сети относится произвольная точка области, в которой располагается выборка.

Рис.2.16. Блок-схема алгоритма построения коллектива RBF-сетей Вторая форма временных RBF-сетей предназначена для моделирования динамики систем с несколькими взаимодействующими центрами. Для неё формула (2.3) заменяется формулой m y = w j (t ) j ( x c j (t ), j (t )), (2.8) j = где j можно, например, взять в виде j ( t ) x c j ( t ) j = e (2.9) Другие приведённые выше базисные функции допускают аналогичное изменение.

Дальше возникает задача определения параметров w j (t ), c j (t ), j (t ). Её решения имеют много общего с алгоритмами из предыдущего параграфа.

Самый простой подход состоит в том, чтобы искать эти параметры для каждого момента времени отдельно. После того, как они найдены, можно попытаться установить соответствие между отдельными функциями так же, как это делалось в предыдущем параграфе.

Более аккуратный подход – найти параметры для первого момента времени, взять их в качестве начальных приближений для следующего момента, уточнить каким-либо итерационным алгоритмом и т.д. Ещё более перспективный, хотя и более сложный подход – строить нейронную сеть, которая позволит определить значения параметров в некоторый момент времени по их значениям в предыдущие моменты. Такого рода нейронные сети изучаются в следующем параграфе. Резюмирует вышесказанное следующий алгоритм.

Алгоритм 2.17. Последовательный алгоритм динамической кластеризации с прогнозом.

1. Исходную выборка в начальный момент времени ( x1 (1), y1 (1)), (x 2 (1), y2 (1)),..., (x N (1), y N (1)) подвергаем кластеризации, например, обучаем сеть Кохонена по какому-либо алгоритму из предыдущей главы.

2. Для каждого кластера строим его аппроксимацию своей базисной функцией, т.е. по точкам, вошедшим в j -й кластер, определяем w j (1), j (1) (и jl (1) или jls (1) ) и c j (1).

3. Рассматриваем веса получившейся сети как начальные значения весов сети для второго момента времени.

4. Минимизируем ошибку аппроксимации, уточняя параметры сети.

5. Повторяем шаги 3 и 4, а возможно, и шаги 1 и 2 для следующего момента времени.

Одновременно с шагом 5 начинаем строить прогноз w j ( k + 1), 6.

j (k + 1) и c j (k + 1) по w j (1),..., w j (k ), j (1),..., j ( k ) и c j (1),..., c j (k ) с помощью авторегрессии или одной из сетей, представленных в следующем параграфе.

7. Сравниваем ошибку, полученную с помощью сети с параметрами, определяемыми на шаге 2, с ошибкой, которую даёт сеть с параметрами, найденными на шаге 6.

8. Если прогнозные параметры оказались точнее, для следующих моментов повторяем шаги 3, 4 и 6.

Реализация рассмотренного алгоритма затруднена тем, что приходится строить прогноз достаточно большого числа параметров – для каждого кластера это будут w j ( k + 1), j (k + 1) и c j (k + 1). Решить эту проблему можно введя параметризацию этих переменных. Можно задать w j (t ) в виде некоторых конкретных функций, например вейвлетов [130, 165, 179, 184], параметры которых подбираются в процессе обучения. Аналогичным образом можно поступить и по отношению к переменным j (t ) и c j (t ). При этом предыдущий алгоритм остаётся практически неизменным, только шаг 6 и последующее повторение шага 4 сводится к определению и уточнению параметров упомянутых выше функций.

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

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

1) Сеть – и структура и веса – фиксируется заранее, само обучение не происходит, результат работы сети – просто результат её функционирования.

Такой подход является типичным для рекуррентных сетей, его ярким примером может служить применение сетей Хопфилда к задачам комбинаторной оптимизации [166].

2) Задан ряд временных последовательностей: как входных, так и соответствующих им выходных – надо обучить сеть строить по входной последовательности выходную.

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

Алгоритм 2.18. Генетический алгоритм определения структуры сети с обратными связями по набору выборок.

1. Выбираем вспомогательный функционал (критерий или критерии МГУА) и в соответствии с ним производим манипуляции с выборкой, например, разделяем на две подвыборки. Для данного вида сетей особую роль приобретают критерий баланса прогнозов, сценарный критерий и критерий точности многошагового прогноза для пополняемых выборок.

2. Определяем набор сетей, различающихся между собой множествами нейронов (вершин) V (t ) для каждого из временных отсчётов, множествами связей (соединяющих их дуг) D (t1, t2 ) и активационными функциями, и производим их начальную инициацию.

3. К каждой сети из набора применяем заданное число шагов некоторого (одного и того же) алгоритма обучения или этот алгоритм применяем к каждой сети в течение одного и того же времени. При этом алгоритм (вычисление суммарной ошибки и суммарного градиента) применяем для обучающего множества выборок, сформированного на шаге 1 в соответствии с выбранным функционалом (функционалами).

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

5. Ко всем или к некоторым сетям из набора применяем описанные в параграфе 2.4 операции мутации и транслокации. Особенность данного вида сетей состоит в том, что при добавлении связи между нейронами она должна быть направлена от нейрона на более раннем временном отсчёте к нейрону на более позднем отсчёте или от нейрона с меньшим номером к нейрону с большим номером для нейронов, отвечающих одному и тому же значению времени. Чем выше критерий, тем больше вероятность применения этих операций.

6. Повторяем пункт 3.

7. Для лучших (по вычисленному критерию) пар сетей проводим описанную в параграфе 2.4 операцию скрещивания. Можно обучать две сети на разных множествах выборок и у скрещиваемых сетей объединять входы и выходы, а создание перекрёстных связей оставить на последующие мутации.

8. Повторяем пункты 3-7, пока целевой функционал не станет достаточно малым.

Рис.2.18. Блок-схема генетического алгоритма определения структуры сети с обратными связями по набору выборок 3) Задан ряд временных последовательностей, с которыми сеть работает в режиме самообучения, например, образует кластеры.

Алгоритмы динамической кластеризации приведены в параграфе 2. 4) Есть некоторый объект, моделью которого должна стать сеть. Мы можем подавать на вход объекта некоторую временную последовательность воздействий и получать соответствующую ей выходную. По этим данным подбираются веса сети так, чтобы результат её работы был бы наиболее близок к результатам работы моделируемого объекта.

Алгоритм 2.19. Алгоритм моделирования неизвестного объекта.

1. Создаём набор выборок, подавая на вход объекта некоторую временную последовательность. Этот набор должен быть с одной стороны достаточно представительным, чтобы выявить существенные свойства поведения объекта, с другой – не слишком большим, чтобы его обработка не была чересчур длительной. Для образования этого набора можно использовать методы планирования эксперимента.

2. Производим некоторое число шагов обучения сети, например, по алгоритму 2.18. Это число шагов должно быть достаточным для значительного уменьшения минимизируемого функционала, но еще слишком малым для того, чтобы процесс сошёлся.

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

4. Повторяем шаги 2 и 3 до выполнения условий останова. Хорошим критерием является малая ошибка на вновь сгенерированном наборе выборок.

Рис.2.19. Блок-схема алгоритма моделирования неизвестного объекта 5) Поступает одна входная временная последовательность векторов и одна выходная. Задача состоит в том, чтобы в процессе поступления данных настроить (а при необходимости перестроить) веса сети таким образом, чтобы сеть наилучшим образом отражала зависимость между входными и выходными данными.

Алгоритм 2.20. Генетический алгоритм определения структуры сети с обратными связями по пополняемой выборке.

1. Определяем начальный набор сетей, различающихся между собой множествами вершин сети V (t ) для каждого из временных отсчётов, множествами соединяющих их дуг D (t1, t2 ) и активационными функциями и производим их инициацию (определение начальных весов и состояния).

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

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

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

4. Ко всем или к некоторым сетям из набора применяем мутации и транслокации. Чем выше критерий, тем больше вероятность применения этих операций.

5. Повторяем пункт 3.

6. Для лучших (по вычисленному критерию) пар сетей проводим операцию скрещивания.

7. Повторяем пункты 3-6, пока соответствующий критерий МГУА не станет достаточно малым.

Рис.2.20. Блок-схема генетического алгоритма определения структуры сети с обратными связями по пополняемой выборке 6) Если сеть моделирует некоторый объект во время его функционирования, то мы имеем ту же самую задачу, только возникает вопрос об оптимальном формировании входных сигналов. Одним из подходов к такому формированию может быть работа на уровне отрезков реальной входной последовательности, длительность которых сравнима со временем реакции объекта. При этом отрезки, для которых есть основание ожидать наибольших ошибок, включаются в выборку с большей вероятностью.

7) Поступает одна последовательность векторов, которая обрабатывается сетью в процессе самообучения. Целью такой обработки может быть, к примеру, динамическая кластеризация, при которой сеть в отличие от пункта 3, разбивает на классы не последовательности, а возникающие ситуации в одной поступающей последовательности.

Из анализа формул (1.53) и (1.54) видно, что приходится рассматривать набор сетей – сеть, у которой подставлено из опыта значение y(n-T), сеть, у которой подставлено y(n-T) и y(n-T+1), и так далее. При этом, исходя из цели обучения, минимизировать можно как ошибку одной из сетей, так и некоторую суммарную ошибку. Также возможен вариант подбора сети оптимальной глубины или генетический алгоритм, когда работает некоторый набор таких сетей.

Что касается вектора z ( n), то его из опыта в общем случае взять невозможно, в каждой из упомянутых выше сетей этот вектор свой, и для определения его начальных значений (для инициации сети) нужно воспользоваться одним из упомянутых ранее вариантов. В дальнейшем мы можем относительно вектора z (n) рассуждать так же, как и относительно y (n), т.е. подставлять в формулу (1.53) значения y (n t ), взятые из опыта или вычисленные по формуле (1.54), или часть одних, а часть – других.

При изучении конкретных видов динамических сетей (например, сети Хопфилда, Хемминга, Джордана и т.д.) легко построить специализированные варианты рассмотренных ранее алгоритмов.

Можно предложить и несколько иной способ построения сети Хопфилда для запоминания заданного набора образцов x1, x 2,..., x M, который состоит в том, чтобы подбирать элементы матрицы W (обучать сеть) в процессе минимизации ошибки распознавания. Если векторы являются (xi, y i ) бинарными и мы используем ступенчатую функцию, то для минимизации соответствующих функционалов мы не можем использовать градиентные методы. Если мы используем гладкую функцию, то можно использовать и градиентные методы, выбирая гладкий функционал. При этом следует учесть, что мы не можем получить выход сети, который не принадлежит образу отображения (см. 1.57).

Что касается функционалов, то они могут быть трёх основных видов.

• Первый, самый простой, определяется суммарной ошибкой после определённого числа циклов функционирования сети.

• Второй – суммарной ошибкой за определённое число шагов, он позволяет получить более быструю сходимость.

• Третий – скользящий, меняется в процессе функционирования, и при его использовании обучение можно рассматривать как оптимальное управление некоторой динамической системой. Соответствующие производные легко вычислить, исходя из общих формул.

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

Можно предложить и несколько более сложный подход – априорное разделение множества возможных входных векторов на подмножества U i, каждое из которых содержит некоторый образец x i, и аттрактором (множеством, к которому притягиваются все траектории из подмножества) для этого подмножества должна служить точка x i. В этом случае предыдущий подход остаётся вполне работоспособным, только нужно i выбирать таким образом, чтобы xi + i принадлежали U i.

Ещё одно развитие данного подхода состоит в том, чтобы брать аттрактор, состоящий не из одной точки, а являющийся некоторым множеством, однозначно соответствующим точке x i. Примером такого множества может служить периодическая траектория. При этом в выражении для ошибки ei ( n) нужно число y i ( n) xi заменить на расстояние от точки y i ( n ) до этого аттрактора.

Обратимся к генетическим алгоритмам. В данном случае их можно применять как к поиску оптимальной структуры, так и к подбору весов сети, т.е. к её обучению. Если в (1.43) в качестве используется отображение общего вида, то сложно описать генетические операции конкретно. Если же это отображение действует покоординатно, то транслокация и скрещивание описываются очевидным образом.

Алгоритм 2.21. Генетический алгоритм определения структуры сети Хопфилда.

1. Определяем начальный набор сетей, различающихся между собой значениями весов, функциями активации и способом функционирования (синхронное или асинхронное - см. описание в параграфе 1.4 ).

2. На каждую сеть подаём один или несколько входных векторов и отслеживаем динамику.

3. Вычисляем значение некоторого критерия МГУА (критерий баланса прогнозов, сценарный критерий) на каждой сети и отбрасываем заданное число заведомо бесперспективных сетей.

4. К каждой сети из набора применяем заданное число шагов некоторого (одного и того же) алгоритма обучения или этот алгоритм применяем к каждой сети в течение одного и того же времени.

5. Вычисляем значение выбранного критерия (критериев) МГУА на каждой сети (вообще говоря отличающегося от того критерия, что применялся на шаге 3) и отбрасываем заданное число худших сетей. Можно для отбора сетей из популяции использовать ошибку для других i или другую норму в выражении для ошибки ei ( n). Другой вариант состоит в том, что для подбора весов на шаге 4 используется одношаговое приближение (т.е. убывание En+1 по отношению к значению En ), а для отбора – многошаговое или минимум изменения весов при одношаговом приближении.

6. Ко всем или к некоторым худшим сетям из набора применяем мутации и транслокации. Мутацией может служить изменение отдельной функции активации или способа функционирования по отдельной координате или замена знака одной строки или одного столбца W (строки и столбца, если матрица симметрическая). В качестве транслокации используем набор мутаций, который может зависеть от функционирования сети (например, меняем знак строк, соответствующих наиболее быстро растущим координатам).

7. Повторяем пункт 3.

8. Для лучших (по вычисленному критерию) пар сетей проводим операцию скрещивания, которую можно задать как сложение или умножение матриц W, соответствующих скрещиваемым сетям.

9. Повторяем пункты 3-8 до тех пор, пока соответствующий критерий не станет достаточно малым или пока сеть не начнёт после заданного числа шагов динамики стабильно выдавать правильные результаты (или достаточно большую долю правильных результатов).

Рис.2.21. Блок-схема генетического алгоритма определения структуры сети Хопфилда Предложим способ построения сети Хемминга для запоминания заданного набора образцов x1, x 2,..., x M. Для этого надо рассмотреть вместо расстояния некоторую билинейную форму, коэффициенты которой будем подбирать в процессе обучения. Этот подход позволяет применить многорядный алгоритм МГУА.

Алгоритм 2.22. Многорядный алгоритм определения структуры сети Хемминга.

1. Строим набор линейных моделей для первого слоя сети, рассматривая некоторый набор пар сравниваемых координат в соответствии с линейным многорядным алгоритмом. Можно рассматривать и модели для второго слоя, при этом либо рассматриваются линейные комбинации пар входных координат для слоя Хопфилда, либо берутся пары координат, меняющихся друг за другом при асинхронном функционировании.

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

Шаг 2 повторяем для всех векторов выборки.

M Вычисляем суммарную ошибку En = ei (n). Здесь в качестве ei ( n) 3.

i = можно взять 0, если входной вектор классифицирован правильно и 1 в противоположном случае.

4. Для минимизации En применяем несколько шагов какого-либо алгоритма нелинейной оптимизации. При этом на каждом шаге итерационного процесса уточнения весов сети можно суммировать не по одному пробному вектору для каждого образца, а некоторый набор таких векторов, которые отличаются друг от друга реализациями случайных векторов i. Можно модифицировать слой Хопфилда одним из способов, рассмотренных ранее.

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

5. Задаём другие реализации случайных величин i и повторяем шаги 2 и 3.

6. В соответствии с МГУА выбираем некоторое множество лучших моделей.

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

8. Сеть готова к работе, когда соответствующий критерий МГУА становится достаточно малым.

Рис.2.22. Блок-схема многорядного алгоритма определения структуры сети Хемминга Можно рассмотреть и другие функционалы ошибки. Задачей может быть наилучшая классификация выборки, т.е. наименьшие изменения номера выхода при добавлении в исходную выборку малых случайных возмущений, или минимальное число получающихся кластеров.

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

Алгоритм 2.23. Многорядный алгоритм определения структуры сети Коско.

Строим набор линейных моделей вида zi = w1 x j + w2 xk, где каждая 1.

модель задаёт только две отличные от нуля координаты вектора z. Другими словами, определённая выше матрица W имеет отличными от 0 только четыре элемента, соответствующие двум строчкам и двум столбцам.

2. Сети функционируют заданное число шагов в соответствии с формулами (1.59).

M En = ei (n).

3. Вычисляем суммарную ошибку Здесь i = 1 ei (n) = y i ( n) y i или ei (n) = y i (n) y i.

4. Для минимизации En применяем несколько шагов какого-либо алгоритма из третьей главы.

5. В соответствии с МГУА выбираем некоторое множество моделей.

На l + 1-м шаге работа алгоритма рассматриваем модели вида 6.

zk,l +1 = wi,l zi,l + w j,l z j,l.

7. Повторяем шаг 4, подбирая коэффициенты последнего ряда.

8. В соответствии с выбранным критерием МГУА выбираем заданное множество моделей.

9. Шаги 6-8 повторяем до тех пор, пока ошибка не станет достаточно малой.

Рис.2.23. Блок-схема многорядного алгоритма определения структуры сети Коско Сеть Джордана, определяемая формулами (1.61)-(1.63), может быть настроена на определение наличия конкретной динамики, например, приближения системы к некоторому аттрактору или колебания с некоторой частотой. Если входная последовательность не слишком сильно меняется, то матрицу можно строить таким образом, чтобы она осуществляла W преобразование к главным компонентам. Матрицу W (1) можно формировать таким образом, чтобы по тем координатам, которые надо усилить, связь была положительна, а по тем, которые нужно ослабить, – отрицательна.

Алгоритм 2.24. Алгоритм выращивания сети Джордана для моделирования неизвестного объекта.

1. Создаём некоторый набор выборок, подавая на вход объекта набор временных последовательностей x i ( n). Для образования этого набора можно использовать методы планирования эксперимента. Проблема генерации обучающей выборки менее остра, если выборка создаётся заранее (до начала обучения) или формируется в процессе обучения, но по заранее заданному закону (несмотря на результаты обучения). Пусть и T – характерное минимальное и максимальное время соответственно, выраженное в числе отсчётов. Рассматриваем множество возможных входных последовательностей длины, которые могут соответствовать входным векторам (это не обязательно должен быть белый шум, скорость изменения x(n) может быть ограничена, или это может быть процесс, обладающий некоторыми фиксированными стохастическими свойствами). После этого рассматриваются T наборы из таких последовательностей, для которых соседние кусочки состыкованы определённым образом (например, ограничены скачки на стыках).

2. Производим некоторое число шагов функционирования сети и получаем набор выходных последовательностей y i ( n). Начинаем формирование сети со случая, когда обратные связи отсутствуют, т.е. задаём начальную сеть как обычный многослойный персептрон, фиксируя его структуру и начальные веса.

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

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

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

5. Создаём новый набор выборок, при этом он может зависеть от результатов предыдущего шага, т.е. мы формируем выборку в процессе обучения. При этом процедура построения выборки зависит от целей, которые мы ставим.

Одной из таких целей может быть моделирование объекта при • экстремальных значениях выхода, при этом входная последовательность подбирается так, чтобы достичь этих экстремальных значений.

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

Третьей целью может быть максимально равномерное уменьшение • ошибки моделирования. Для её достижения можно пополнять обучающую выборку векторами из тех областей входного пространства, которые соответствуют максимальным ошибкам (разности между выходом сети и выходом моделируемого объекта). Для этого можно применить метод кластеризации ошибок в рассматриваемом подмножестве пространства входных векторов, т.е. множество пар вида (x(n), y (n) y (n)) кластеризуется, и центры кластеров, соответствующие максимальным ошибкам, берутся в качестве новых входных векторов.

5. Повторяем шаги 2-5 до выполнения условий останова. Хорошим критерием является малая ошибка на вновь сгенерированном наборе выборок.

Рис.2.23. Блок-схема алгоритма выращивания сети Джордана для моделирования неизвестного объекта Аналогичные алгоритмы можно применить и к формированию сети Элмана.

Сеть Элмана можно обобщить на многослойный случай. Если взять за основу многослойный персептрон и подать на вход выходы разных слоёв, то можно получить более изощрённую динамику, чем для однослойной сети. Этот случай можно свести к тому, который был рассмотрен выше, если взять соответствующий вектор y 0 ( n) и отображение, но тогда резко возрастёт размер сети. Можно также рассмотреть комбинированный вариант, когда на вход подаются ещё и выходы сети, как в случае сети Джордана.

Несмотря на все ухищрения, генетические алгоритмы остаются достаточно медленной процедурой, на которую может не хватить времени.

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

1) МГУА с полным перебором или генетический алгоритм можно применить если время сходимости этих алгоритмов меньше T.

Если время сходимости этих алгоритмов больше T, но меньше 2) T, то можно для отбора моделей использовать критерий точности многошагового или краткосрочного прогноза, иногда перемежая их критерием минимума смещения с соответствующим пополнением (или перегенерацией с удалением устаревших точек) множеств А и В (см. параграф 1.1).

Если время сходимости алгоритмов подбора моделей больше T, то 3) необходимо предпринять меры по сокращению перебора или преобразования процесса в более адаптированный. Резкое изменение ситуации можно отследить по критерию краткосрочного прогноза. При этом число точек, по которым происходит вычисление коэффициентов моделей, не должно быть намного больше, чем число прогнозных точек, для которых этот критерий меньше 1. Для генетических алгоритмов адаптивность повышается, если принять меры против вырождения, например, повысить вероятность мутаций или обеспечить подбор разнообразных индивидов для скрещивания, хотя это и увеличивает время сходимости, но позволяет быстрей перейти к удовлетворительной модели в изменившейся ситуации. Если различные ситуации могут повторяться, то можно применить воскрешение хромосом, которые были лучшими в какой-то прежней ситуации.

Если T 4) ещё меньше, то для сокращения перебора нужно применить многорядный алгоритм МГУА с парными комбинациями на каждом ряду (это резко сокращает объём вычислений коэффициентов) и включением в перебор переменных из предыдущих рядов. Если в какой-то момент оказалась оптимальной модель не из последнего ряда селекции, то на очередном шаге перебираются модели не дальше следующего ряда.

5) Если темп поступления новых точек ещё увеличивается, то можно для образования разных моделей применить различные наборы точек, например, для одних моделей – чётные, для других – нечётные. Перебор моделей авторегрессии можно сократить до последовательного добавления (по одному) коэффициентов, соответствующих всё более дальним отсчётам.

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

Глава 3. Итерационные методы обучения нейронных сетей Для настройки весов нейронной сети при ее обучении на основе нахождения минимума функционала ошибки E, соответствующего конкретной задаче математического моделирования, обычно используется некоторый метод нелинейной оптимизации. Теория таких методов достаточно развита, однако непосредственное её применение к анализу условий сходимости процедур обучения нейронных сетей наталкивается на определённые трудности. Дело не столько в изобилии видов нейронных сетей, сколько в том, что алгоритм обучения может сочетать шаги по методу второго порядка (типа метода Ньютона) и шаги по методу первого порядка, обратный оператор в методе ньютоновского типа может вычисляться с погрешностью, минимизируемые функционалы могут меняться от шага к шагу и на некоторых шагах не допускать удобной оценки второй производной, может изменяться размерность пространства весов (к этому приводят структурные, в частности, эволюционные алгоритмы) и т.д.

Для того чтобы избежать рассмотрения всего этого множества случаев, в первом параграфе данной главы получены некоторые общие результаты по сходимости методов типа метода Ньютона [31,191,214,218], из которых можно получать в качестве частных случаев конкретные условия сходимости.


Вернёмся к задаче подбора вектора w весов нейронной сети. Будем w k +1 = ( w k, E ), искать его итерационным методом причем, выбирая отображение, получаем конкретный метод, для которого надо обеспечить сходимость к решению w k w *, где w * – точка минимума функционала E (2.1).

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

Так как обучение нейронных сетей является ресурсоёмкой процедурой, интересно распределить её по нескольким компьютерам. В седьмом и восьмом параграфах обсуждаются подходы к такому распределению в случае, характерном для сети Интернет.

Большинство описанных далее методов можно представить в виде w k +1 = w k + k p k, где вектор p k задаёт направление движения при переходе к новым значениям весов, а k – размер шага.

Алгоритм 3.1. Обобщённый алгоритм нелинейной оптимизации без ограничений.

1. Выбираем начальные значения параметров – стартовую точку w 0, начальное направление движения p 0 и начальный шаг 0.

2. На очередном шаге определяем направление движения pk, основываясь на требуемой для этого информации – например, векторе p k 1, градиенте функционала ошибки в точке и т.д.

Определяем очередной шаг k, обычно определяя минимум 3.

функционала ошибки в направлении p k с той или иной точностью.

4. Если ошибка недостаточно мала и не выполнено какое-либо иное правило останова, то шаги 2 и 3 повторяем.

Конкретизация описанных выше правил формирования направления движения и размера шага даёт определённый алгоритм. Так как выбор алгоритмов формирования k и p k в большой степени независим, мы рассмотрим их отдельно, указывая какой метод выбора шага для каких методов выбора направления подходит. При этом методы выбора p k делятся на методы нулевого порядка, не требующие вычисления градиента, методы первого порядка, в которых требуется вычислить или оценить градиент, и методы второго порядка, требующие вычисления или оценки матрицы вторых производных и её обратной.

3.1. Метод Ньютона как реализация приближений с быстрой сходимостью Итерационный процесс с ускоренной сходимостью на практике реализуется чаще всего в виде метода Ньютона или близкого к нему. Заметим, что метод такого сорта можно применять к задачам, рассматривавшимся ранее, двумя способами. Во-первых, можно решать нелинейную систему относительно искомых весов нейронной сети непосредственно, при этом если число уравнений больше числа неизвестных (обычно рассматриваемый случай), то найти точное решение можно только в вырожденных случаях. Во-вторых, можно применить метод к поиску минимума соответствующего функционала.

В этом случае метод Ньютона фактически применяется к необходимому условию экстремума – равенству нулю градиента. При этом вместо минимума процесс может сойтись к максимуму или к точке типа седла. Методы преодоления этих трудностей приведены в параграфе 3.6.

– векторные пространства, F Пусть U иV – отображение из пространства U в пространство V. Будем искать решение уравнения F ( x) = 0.

Пусть F представляется в виде F ( x) = F ( y ) + y ( x y ) + y ( x y), (3.1) где y – обратимо в некоторой окрестности нуля, y – мало (в некотором y (0) = y (0) = 0. Организуем итерационный процесс Ньютона смысле), следующим образом. Рассмотрим уравнение xn 1 ( xn xn1 ) = F ( xn1 ). Считая, что это уравнение разрешимо, будем находить из него очередное приближение к решению xn через предыдущее приближение xn1. Положив в равенстве (3.1) x = xn, y = xn 1, получаем F ( xn ) = xn 1 ( xn xn1 ) (3.2) и xn+1 xn = xn1 ( xn 1 ( xn xn1 )).

(3.3) Удачный выбор y и y позволяет в некоторых случаях доказать сходимость итерационного процесса { xn }, исходя из формулы (3.3).

Для начала рассмотрим следующую ситуацию. Пусть две последовательности вложенных друг в друга нормированных пространств:

g G0 G1... G ;

H 0 H1... H ;

g для любых i и g Gi ;

G – Gi Gi + F : G H банахово пространство. Пусть отображение непрерывно и переводит Gi в H i при всех i. Обозначим Fi – ограничение F на Gi.

Предположим, что Fi представимо в виде Fi ( x) = Fi ( y ) + i, y ( x y ) + i, y ( x y ), причём уравнение n+1, xn ( xn+1 xn ) = Fn ( xn ) разрешимо в пространстве Gn+1 для всех xn из Gn. Тогда формулы (3.2) и (3.3) запишутся в виде Fn ( xn ) = n, xn 1 ( xn xn1 ), (3.4) xn+1 xn = n+1, xn ( n, xn 1 ( xn xn1 )).

(3.5) Лемма 1. Пусть 1,x0 непрерывно в нуле, а из равенства (3.5) следует оценка n xn+1 xn cn xn xn1. (3.6) Gn +1 Gn Если cn и n удовлетворяют условиям ln cn ln n = +;

n 1;

0;

k = k k 1... 1;

0 = 1, ci 1, (3.7) n n n = то процесс последовательных приближений сходится для тех x0, для которых 0, то процесс F ( x0 ) достаточно мало. Если при этом F ( xn ) H0 H n n последовательных приближений сходится в G к решению уравнения F ( x) = 0.

Доказательство.

Легко видеть, что если {xn }+0 последовательность в полном метрическом n= (x, x пространстве с метрикой и ) +, то { xn } сходится к некоторому k + k k = пределу (обозначенному x ), и справедливо неравенство ( xn, x) ( xk, xk +1 ).

k =n Применим этот результат к метрике, индуцированной нормой в G.

Пусть выполнены неравенства Gi ( x, y ) Gi +1 ( x, y ) G ( x, y ) для тех x и y, для которых эти функции определены. Пусть дана последовательность отображений ui : Gi 1 Gi, i 1. Рассмотрим итерационную последовательность + ( xk, xk +1 ) +, : xi = ui ( xi 1 ). Если выполняется условие {x } то n n =0 Gk + k = итерационная последовательность сходится в пространстве G.

Пусть u – непрерывное отображение из пространства G в пространство G и sup G (un+1 ( x), u ( x)) 0 при n, тогда пределом каждой сходящейся xGn итерационной последовательности является неподвижная точка отображения u. Для доказательства этого достаточно рассмотреть x G – предел {xn }+0, итерационной последовательности тогда n= G ( x, u ( x )) G ( x, xn ) + G ( xn, u ( x )) G ( x, xn ) + G (un ( xn1 ), u ( xn1 )) + G (u ( xn1 ), u ( x )) 0. Следовательно, G ( x, u ( x )) = 0 u ( x ) = x.

n Пусть Gk +1 ( xk, xk +1 ) ck Gkk ( xk 1, xk ). Тогда Gk +1 ( xk, xk +1 ) Dk Gkk ( x0, x1 ), где Dk = ck ck 1ck 2k 1...c1 k k 1... 2.

k k (3.8) k = k k 1... 1;

D0 = 0 = 1, то условие сходимости Если обозначить перепишется в виде D n ( x0, x1 ) +. (3.9) n G n = Существование в пространстве G предела последовательности { xn } (который будем обозначать x ) следует из приведённых выше рассуждений, x1 x если достаточно мало, т.е. удовлетворяет условию (3.9), что выполняется в силу непрерывности 1,x0 и малости F ( x0 ). Сходимость 0 F ( x ) = влечёт из-за непрерывности F ( x). Пусть F ( xn ) H n n ln n ln cn 0, ci 1 =, e. Тогда итерационная последовательность n n =1 n + {xn }n=0 сходится. Доказательство состоит в проверке условия ln n ln n lim = lim что и доказывает n 1 n ln c n n ln cn + n... i +1 ln ci + n ln n (ln + i ) i =1 i i = лемму.

Замечание 1. Условие ci 1 может быть опущено, если в (3.7) условие m ln cn ln cn = + заменить условием = lim +.

n =1 n n =1 n m Следствие. Пусть отображения y и y таковы, что из равенства (3.5) n 1+ n следует оценка xn+1 xn Bn F ( xn ) An xn xn, а из (4.4) F ( xn ).

Gn +1 Hn Hn Gn Оценка (3.6) выполняется, если взять cn = Bn Ann ;

n = n (1 + n ), и условие сходимости переписывается в виде ln Bn + n ln An = +, (3.10) n n = n где n = i (1 + i );

ln F ( xn ) ln An + (1 + n )(ln Dn1 n1 ln ), если Hn i = выполнено условие ln An ln An = lim n = 0, lim (3.11) (1 + n ) n n n n Если Bn B 0, то (3.11) следует из (3.10). Условие (3.10) даёт 0 и, тем самым, гарантирует существование решения F ( x) = 0 в F ( xn ) H n n условиях леммы.

0, в условиях леммы Замечание 2. Доказательство того, что F ( xn ) H n n может быть получено как следствие других предположений: например, равностепенной непрерывности n, xn 1.

Замечание 3. Можно получить аналогичный результат, если функция F задана и непрерывна не на всём G, а в некоторой области, обеспечив такой выбор и, чтобы процесс приближений оказался осуществимым и сходился к точке непрерывности функции F. Подробнее этот вопрос рассмотрен ниже при анализе более частной ситуации.

Теорема 1 (метод Ньютона). Пусть выполнены следующие условия:

Каждая функция Fi задана на шаре Ri : x x0 ri в Gi и 1) Gi отображает его в область S i.

Существует производная по Фреше Fi для всех x Ri, причём 2) i Fi( x) Fi( y ), i 0;

Ai x y (3.12) Gi Hi Для всех x Ri и y Ri 1 уравнение Fi 1 ( x) = имеет решение в 3) + Ri +1 для всех Si, причём Bi.

Gi +1 Hi 4) Выполнены условия:

ln Bn + ln An n = +, где n = (1 + i );

(3.13) n n =1 i = ln n 0 (3.14) n ln An = lim (3.15) n n n для = B0 F ( x0 ) e, rn Di i + r0, (3.16) i = где Dn определяется по формуле (3.8) с константами ci = Ai Bi ;

i = 1 + i.

Тогда итерационный процесс Ньютона, начатый из любой точки R0, сходится к решению уравнения F ( x) = 0.

Доказательство.

n, y ( x y ) = Fn( y ) x, n, y ( x y ) = F ( x) F ( y ) Fn( y )( x y ).

Пусть В 1+ n условиях теоремы n, xn 1 ( xn xn1 ) An xn xn1 (эта оценка следует Gn Hn из формулы конечных приращений). Таким образом, мы попадаем в ситуацию следствия из леммы 1. Условие (3.12) гарантирует правильность определения всех участвующих в приведённых выше рассуждениях отображений. Теорема доказана.

Следствие. Пусть Fi имеет ограниченную вторую производную по Фреше, т.е. Fi ( x) Ai для всех x из шара Ri. Тогда в неравенстве (3.12) можно выбрать i = 2. При этом n = 2n. Условие (3.14) будет выполняться автоматически. Этот случай наиболее часто встречается в приложениях.

Замечание 4. В условиях теоремы x принадлежит шару с центром в точке x0 радиуса r Dn n + r0.

n = Замечание 5. В методе Ньютона в качестве отображения y можно использовать слабый дифференциал (Гато) отображения F.


В приложениях требование обратимости Fi оказывается иногда слишком ограничительным. Предположим ([181], глава 6), что Fi имеет приближённый обратный, т.е. существует такой ограниченный линейный оператор Li ( x ) : H i 1 Gi, что для всех h из Si 1 и x из Ri 1 выполняется неравенство i Fi( x) Li h h M i Fi ( x) h. (3.17) H i Hi H i Теорема 2. Пусть в условиях предыдущей теоремы обратимость Fi заменена условием (3.17), причём выполнены условия li h Li h, (3.18) Hi Gi i = i, (3.19) n rn li +1Di i + r0, (3.20) i = где Dn определяется по формуле (3.8) с константами ci = Ali1+i + M i ;

i = 1 + i i ln ln +1 ln n ln cn = 0;

= +;

e.

= lim (3.21) lim n n n =1 n n n F ( x) = Тогда уравнение имеет решение, к которому сходится итерационный процесс, начатый из любой точки R0.

Доказательство. Процесс последовательных приближений организуем в соответствии с формулами xn +1 = xn Ln+1 ( xn ) F ( xn ), (3.22) F ( xn+1 ) = F ( xn ) + Fn+1 ( xn )( xn +1 xn ) + n+1, xn ( xn+1 xn ). (3.23) Подставляя (4.22) в (4.23), получаем F ( xn+1 ) = wxn ( F ( xn )) + n+1, xn ( Ln+1 ( xn ) F ( xn )). (3.24) Здесь wxn (h) = ( Fn+1 ( xn ) Ln+1 ( xn ) E )h. В условиях теоремы справедливы 1+ n +1 1+ n + An+1ln+ n +1 F ( xn ) оценки n+1, xn ( Ln+1 ( xn ) F ( xn )) An+1 Ln+1 ( xn ) F ( xn ) + Gn +1 Hn H n + 1+ n + wxn ( F ( xn )) M n+1 F ( xn ) и, откуда получаем, используя (3.24), Hn H n + 1+ n ( Anln+ n + M n ) F ( xn1 ) Dn n, а из равенства (3.22) вытекает F ( xn ) Hn H n xn+1 xn ln +1Dn n. Для доказательства теоремы остаётся проверить выполнение условий + l Dn Dn n +.

n 0;

(3.25) n + n= Применяя логарифмический признак сходимости, убеждаемся, что в условиях теоремы требование (3.25) выполняется. Условия (3.20) и (3.21) гарантируют соответствие областей определения. Теорема доказана.

Замечание 6. В случае, когда не выполняется условие (3.25), можно получить более сильные результаты (при различных предположениях относительно скорости роста An, ln и M n ), чем получающиеся заменой i и i на число min( i,i ).

Замечание 7. Аналогичным образом можно рассмотреть случай, когда i имеет только приближённый обратный. Пусть выполнены условия (3.12), + D 1+ n 1+ n 1+n (3.17), (3.18) и (3.20). Если D0 = 1;

Dn = A l + M nD +, то D и n 1 n nn n n = процесс последовательных приближений (3.28) сходится к решению уравнения F ( x) = 0. Действительно, в указанных условиях 1+ n 1+n F ( xn ) Anln+ n F ( xn1 ) + M n F ( xn 1 ), откуда и следует требуемый результат.

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

Однако континуальный случай легко сводится к дискретному.

Определение 1. Стволом называется семейство банаховых пространств {Gt } над одним и тем же полем, параметризованное отрезком [, ]: Gt Gt при t t и g t g t для всех g Gt.

Пусть заданы стволы {Gt }1 и {H t }1. Рассмотрим отображение F из 0 пространства G0 в пространство H 0, непрерывное на Gs при всех 0 s 1.

x Gt y Gt Предположим, что для всех и выполняются условия t, t F ( x ) H ;

F ( y ) H при любых и можно построить такое разложение (3.1), что уравнение y ( x) = в Gt разрешимо для всех H ;

y Gt, если t t. Считаем также, что и непрерывны в этих условиях как по аргументам, так и по индексам.

Организуем итерационный процесс в соответствии с формулой (3.5), положив Gn = Gtn ;

H n = H n ;

tn n tn+1. Пусть из (3.10) следует оценка (3.11), где числа cn = c ( n );

n = ( n );

n = tn +1 tn ;

t0 = 1;

n выбраны надлежащим образом.

Пусть для некоторой последовательности n выполняются Лемма 2.

+ условия леммы 1 и = n 1, тогда уравнение F ( x) = 0 имеет корень в n = пространстве GT, где T = 1.

Доказательство.

В данном случае tn T, поэтому в качестве пространства G можно взять GT, а в качестве H – H при любом : 0 T. Непрерывность, а также формула (3.4) позволяют заключить, что F ( xn ) 0 для сходящейся последовательности { xn }. Тем самым получаем F ( x ) = 0 (здесь x – предел последовательности xn в пространстве GT ) ввиду непрерывности F. Лемма доказана.

Аналогичным образом можно переформулировать теорему 2 и другие приведённые выше результаты.

Процедура сглаживания позволяет распространить метод Ньютона на ситуации, когда предыдущие теоремы данного параграфа не работают. Пусть заданы такие же последовательности пространств, как и в начале предыдущего + параграфа, но F ( x ) : G H имеет вид F ( x) = g k ( x), причём g j : Gi H i k = i Fi ( x) = g k ( x).

j i.

для всех Обозначим Пусть k = Fi ( x) = Fi ( y ) + i, y ( x y ) + i, y ( x y ). Организуем итерационный процесс Ньютона со сглаживанием следующим образом. Будем определять xi +1 из уравнения Fi ( xi ) + i, xi ( xi +1 xi ) = 0. (3.26) Тогда Fi ( xi +1 ) = i, xi ( xi +1 xi ) и Fi +1 ( xi +1 ) = gi +1 ( xi +1 ) + i, xi ( xi +1 xi ). Считая уравнение (3.26) разрешимым, получаем равенство xi +1 xi = ixi ( gi ( xi ) + i 1, xi 1 ( xi xi 1 )). Если и выбраны удачно, то в данной, ситуации может оказаться применимой лемма 1. Сформулируем аналог теоремы 2.

Пусть H ( xk, xk +1 ) d k + ck H ( xk 1, xk ), (3.27) k k +1 k где – последовательность положительных чисел, для которой {d k } = 1. Считаем d 0 =. Утверждение леммы 1 остаётся в силе, если k sup d k k заменить в условии (3.9) на число. В этих условиях справедлива следующая Теорема 3. Пусть функции Fi удовлетворяют условиям теоремы 2 и ln di. Тогда итерационный процесс Ньютона со di, sup Bi g i ( xi ) i Hi i сглаживанием сходится к решению уравнения F ( x) = 0.

Доказательство.

Применяя последовательно (3.27), получаем k i k k d 1 H k +1 ( xk, xk +1 ) Dk Dk Dk, k k k i =1 Di i =1 Di i =1 Di при этом сходимость последнего ряда легко устанавливается с помощью логарифмического признака. Далее лемма доказывается, как и лемма 2, с помощью проверки условия (3.9).

Аналогичный результат можно получить и другим способом. Пусть уравнение g 0 ( x ) = 0 разрешимо в G1 и x1 – его корень. Решаем уравнение F1 ( x ) = g 0 ( x ) + g1 ( x ) = 0. x = x1, Начиная итерации с точки получаем F1 ( x1 ) = g1 ( x1 ) и так далее. Если xi – корень уравнения Fi 1 ( x) = 0, то, решая уравнение Fi = 0, начинаем итерации с точки xi, при этом Fi ( xi ) = g i ( xi ).

Соответствующий результат можно сформулировать на языке последовательностей пространств, но более ясно существо дела раскрывается в случае стволов. Пусть заданы два ствола {Gt }1, {H t }1 и отображение 0 F : G0 H 0, непрерывное на пространстве Gs при всех положительных s.

+ Пусть F ( x) = g k ( x), где g i : Gs H s для всех 0 s 1, но гарантировать k = сходимость ряда мы можем только в H 0. Сформулируем аналог теоремы 2.

Теорема 4. Пусть функции дифференцируемы и выполняется gi (t ) gi( x) gi( y ) ai (t ) x y неравенство. Предположим, что уравнение Gt Ht Fi( x ) = имеет решение в пространстве G для любых x Gt и H t ;

t.

Здесь Fi имеет тот же смысл, что и в предыдущей теореме. Предположим, что Bi (t ) решение удовлетворяет неравенству. Обозначим G Ht i Ai (t ) = ak (t ). Пусть для некоторой последовательности {tij }i+=0, tij tij при,j k = t00 = 1, (j i ) = ti, j 1 ti, j, i i j, j j j, tij tij и любых и для j = (1 + (ti,k )) выполняются условия (i ) j k = ln Bi ( (j i ) ) + ln Ai (tij ) e i i = +, di (t );

di (t ) gi ( x), Bi ( 0(i ) ) (ji ) Ht j = ln n Si +, где Si = (di (ti 0 ) Bi ( 0(i ) )e i ) (ji ) 0 1, (i ).

j (ni ) j = i = i, j Тогда рассмотренный выше итерационный процесс Ньютона сходится к решению уравнения F ( x) = 0.

Доказательство получается применением теоремы 1 счётное число раз.

Таким же образом можно получить аналоги и других результатов из раздела 3.1.

Полученные в данном параграфе результаты позволяют исследовать сходимость градиентных итерационных процессов подбора весов нейронных сетей.

3.2. Методы нулевого порядка В этом и следующих двух параграфах под порядком понимается порядок используемой производной. Методы из данного параграфа имеет смысл применять, если мы не знаем направление убывания минимизируемой функции, например, не можем вычислить её градиент. Методы, в которых градиент (вторые производные) оценивается, отнесены к методам первого (второго) порядка.

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

1) p k – случайный вектор с независимыми координатами, равномерно распределёнными на интервале [-1,1].

2) Координаты вектора p k – независимые стандартные нормально распределённые величины. В силу неограниченности нормально распределённой случайной величины такой метод можно отнести к глобальным.

3) Вектор p k имеет заданное число случайно выбранных ненулевых координат, каждая из которых независимо принимает значение +1 и -1 с равной вероятностью.

4) Начальный вектор p 0 выбирается одним из предыдущих способов. При удачном шаге следующее направление поиска берут в виде p k +1 = p k + q k, где q k – новый случайный вектор, задаваемый как и в 1)-3), при неудачном p k +1 = p k + q k, если и этот шаг окажется неудачным, то p k +1 = q k или p k +1 = q k +1.

5) Этот метод отличается от предыдущего тем, что при удачном шаге берут p k +1 = p k.

6) Более сложный вариант состоит в том, чтобы при удачном шаге взять p k +1 = p k + q k, где 1, p k – последний удачный шаг.

7) Похожий способ. Вычисляем направление по формуле p k +1 = (1 k )p k + k q k = p k + k (q k p k ), (3.28) где p k – последний удачный шаг. Варианты выбора k :

а) Можно взять k = const, тогда получается аналог забывания из второго пункта предыдущего параграфа.

б) Если k = 1/ k, то p k – среднее всех удачных направлений.

в) k = – промежуточный вариант между а) и б).

k (p k 1, p k 1 qk ) г) k =, если дробь от до 1 и или 1, если дробь 1 (p k 1 qk, p k 1 qk ) k k выходит за соответствующую границу. Условия сходимости таких методов см.

в [171] Замечание. Во всех этих методах вместо случайного можно использовать равномерно распределённый вектор – см. [210].

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

Начальный шаг 0 выбирается пользователем, кроме этого выбираются два числа 1 1 и 2 1. Если шаг удачный, т.е. ошибка убывает, то шаг умножается на 1, если неудачный – то на 2. Другой вариант заключается в том, что уменьшение производится не сразу, а после заданного числа шагов. В соответствии с замечанием в конце предыдущего параграфа, шаг можно считать удачным, если убывает ошибка в определённой доле примеров.

Приведём один конкретный вариант такого алгоритма.

Алгоритм 3.2. Алгоритм случайного поиска.

Фиксируются параметры алгоритма – начальный шаг 0, 1 1, 1.

2 1, 1, вид распределения случайных векторов и т.д.

2. Выбираем начальные значения параметров w 0.

Сделав очередной шаг величины k вдоль вектора p k, проверяем, 3.

является ли он удачным, т.е. убывает ли ошибка после него.

4. Если ошибка убывает, то в качестве нового направления берём p k +1 = p k + q k, где q k – новый случайный вектор, а в качестве величины шага выбираем k +1 = 1 k.

5. Если ошибка возрастает, то в качестве нового направления берём p k +1 = p k с прежней величиной шага.

6. Если ошибка и в этом случае возрастает, то в качестве нового направления берём p k +1 = q k, где q k – новый случайный вектор, а в качестве величины шага выбираем k +1 = 2 k.

7. Далее шаги 3-6 повторяем необходимое число раз.

8) Метод покоординатного спуска. Минимизация осуществляется по каждой координате по очереди. Простой метод, но в случае высокой размерности практически не работает. В [242] описан метод обобщённого покоординатного спуска, но он требует знания матрицы вторых производных.

9) Метод многогранника (Нелдера-Мида). Общая идея этого метода в простейшем его варианте такова. Вычисляем значение минимизируемого функционала E в n точках. Если w – худшая точка, т.е. точка, в которой E максимально, то из неё сдвигаемся в направлении вектора c w, где c – среднее значение остальных вершин.

Алгоритм 3.3. Алгоритм многогранника.

1. Выбираем начальные значения параметров w 0 и размер ребра симплекса l.

2. Строим правильный симплекс около этой точки. Если исходная точка взята за центр симплекса, то координаты его вершин wi, j можно найти по формуле w0, при j i j j wi, j = w0 + l, при j = i 1.

j 2( j + 1) 0 l w j, при j i 2 j ( j + 1) Здесь w0 – координаты w 0, wi, j – j -я координата i -й вершины j симплекса.

Вычисляем значение минимизируемого функционала E в вершинах 3.

симплекса.

E 4. Точка, в которой значение функционала максимально, отражается относительно среднего остальных вершин c :

wmax (k + 1) = 2 wi, j (k ) wmax (k ).

j j i imax Вычисляем значение функционала E в получившейся точке. Если 5.

оно снова оказывается максимальным, то отражаем относительно среднего остальных вершин точку со вторым по величине E и т.д.

6. Если отражение всех вершин оказалось неудачным, то строим симплекс меньшего размера вокруг вершины с минимальным значением E.

7. Шаги 3-6 повторяем необходимое число раз.

Данный алгоритм можно модифицировать в нескольких направлениях.

Можно операцию отражения проводить не с одной, а с несколькими худшими вершинами. Также вместо точки c можно использовать лучшую точку или взвешенное среднее, причём точки с меньшими значениями функционала имеют больший вес. При этом симплекс перестаёт быть правильным. Можно на четвёртом шаге алгоритма использовать переменный шаг, т.е. заменить соответствующую формулу выражением w (k ) + k ( wi, j (k ) wmax (k )), wmax (k + 1) = j i, j j i imax i imax где k подбирается в процессе минимизации, например, тем же способом, что и для случайного поиска.

Как правило, градиентные методы значительно эффективней, поэтому методами нулевого порядка имеет смысл пользоваться, только если градиент вычислить невозможно или очень сложно. Однако бывает, что небольшая модификация метода – см. Алгоритм 3.28 из параграфа 3.6 – позволяет случайный поиск сделать более эффективным, чем градиентный спуск, в особенности, когда обучается нейронная сеть с большим числом слоёв.

3.3. Методы первого порядка Пусть g k = E ( w k ) – антиградиент функционала ошибки, вычисленный в очередной точке. Так как он является направлением, по которому ошибка убывает быстрей всего, кажется разумным взять p k = g k, причём шаг k E ( w k + k g k ). Такой метод определить из условия минимума функции называется методом наискорейшего спуска и … он совершенно непригоден для решения рассматриваемых нами задач обучения нейронных сетей. Дело в том, что обычно гиперповерхность, являющаяся графиком E (w ), имеет очень сложный, сильно изрезанный вид, изобилующий длинными оврагами, в которых E (w ) медленно убывает в каком-либо одном направлении и быстро растёт в других.

Рис.3.1. График типичной многоэкстремальной функции Итерационный процесс минимизации такой функции, построенный по методу наискорейшего спуска, носит очень извилистый характер, движение почти перпендикулярно дну оврага, тогда как надо двигаться вдоль него.

Простейшую идею, которая уже является достаточно эффективной, содержит метод тяжёлого шарика [189], который в книгах по нейронным сетям по недоразумению называют методом Руммельхарта:

p k = g k + p k 1 ;

p 0 = g 0 = E ( w 0 ), (3.29) параметр обычно задаётся пользователем. Движение точки по поверхности E (w ) напоминает движение шарика с некоторой массой, при этом, чем больше, тем тяжелее соответствующий шарик. Такой шарик быстро скатывается на дно оврага и далее движется по нему. Наш опыт показывает, что параметр хорошо взять близким к 1: =0,99 или 0,999. Интересно сравнить (3.29) с методом 6) из предыдущего параграфа – собственно из-за этой аналогии он там и появился, хотя для случайного поиска он и не даёт такого эффекта, как метод тяжёлого шарика по сравнению с методом наискорейшего спуска.

Дальнейшее развитие метода тяжёлого шарика связано с тем, что можно взять меняющимся шаг от шага p k = g k + k p k 1. (3.30) Одними из самых известных и эффективных методов такого рода являются методы сопряжённых градиентов, которые для квадратичной функции E (w ), т.е. линейной по w функции f (w, x) теоретически сходятся к точному минимуму за число шагов, равное размерности вектора w.

Фактически из-за вычислительных погрешностей – округления и т.п. – даже в линейном случае за конечное число шагов они не сходятся, однако если функция f ( w, x) достаточно близка к линейной, то методы сопряжённых градиентов сходятся существенно быстрее метода тяжёлого шарика. Приведём несколько формул такого рода.

(g k, g k ) При выборе k =, получаем метод Флетчера-Ривса, (g k 1, g k 1 ) (g k g k 1, g k ) При значениях k = – метод Хестенса-Штифеля, (g k g k 1, p k 1 ) (g k g k 1, g k ) Если взять k = – получим метод Полака-Рибьера, (g k 1, g k 1 ) Приведём ещё две известные формулы выбора k без названия (g k g k 1, g k ) (g k, g k ) k = и k =.

(g k 1, p k 1 ) (g k 1, p k 1 ) Другие способы, называемые методом усреднённого градиента, получаются, если в (3.28) заменить q k на g k – см. [171]. Причём в предыдущем параграфе они возникли также по аналогии.

Ещё один вариант выбора k следующий:

если (g k, p k 1 ) 0, то k = k 1, где 1, (3.31) если 1 (g k, g k ) (g k, p k 1 ) 0, то k = min( k 1, ). (3.32) 2 (g k, p k 1 ) Это условие появилось в силу следующих соображений. Если (g k, p k ) 0, то – направление убывания, т.е. можно найти такой шаг, что pk E ( w k +1 ) E (w k ). Если это условие не выполнено, то в соответствии с обычным подходом приходится производить рестарт алгоритма, т.е. брать p k = g k, полностью забывая предыдущее направление. Условия (3.31) и (3.32) гарантируют, что будет направлением убывания, т.е. рестарта не pk потребуется. Смысл неравенства (g k, p k 1 ) 0 состоит в том, что антиградиент направлен в сторону, противоположную предыдущему движению, т.е. овраг делает резкий поворот, и инерцию имеет смысл уменьшить, но не до нуля, чтобы не получить движения со стенки на стенку оврага как в методе наискорейшего спуска. В итоге получается Алгоритм 3.4. Метод тяжёлого шарика регулируемой массы.

1. Выбираем начальные значения подбираемых переменных w 0 и параметры алгоритма – начальный шаг 0, и начальный момент 0.

2. Вычисляем градиент функции E (w ) в начальной точке w 0 и проводим одномерную минимизацию в направлении p 0 = g 0 = E ( w 0 ).

3. На произвольном шаге движение осуществляется одномерной минимизацией в направлении p k = g k + k p k 1, где k = k 1, если выполнено 1 (g k, g k ) условие (g k, p k 1 ) 0, и k = min( k 1, ) в противоположном случае.

2 (g k, p k 1 ) Достаточно эффективным оказался известный метод – ПАРТАН, который состоит в следующем. Из точки w 0 делается два шага методом наискорейшего спуска. Далее w 2k получается спуском по антиградиенту из точки w 2 k 1, а w 2 k + одномерным спуском из точки w 2 k 2 в направлении разности w 2 k w 2 k 2.

Более сложный метод – овражного шага [77] – оказался не столь эффективен в задачах большой размерности, тем не менее, опишем и его.



Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 10 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.