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

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

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


Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 10 |

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

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

Помимо последовательности w k вводится вспомогательная последовательность u k, причём u 0 = w 0, u k +1 = w k + k g k. Шаг k определяется каким-либо одномерным методом минимизации – см. §5, w k +1 = u k +1 + k (u k +1 u k ), при этом bk 1 k 1, например, k =, b0 = 1, bk +1 = (1 + 4bk2 + 1). Доказано [77], что bk + этот метод оптимален в случае одномерного оврага, который может встретиться в задачах малой размерности. Задачи обучения нейронных сетей, как правило, содержат сотни (и более) переменных – весов сети, поэтому одномерные овраги встречаются редко.

Наконец, самый эффективный из методов подобного рода – BFGS с конечной памятью [92]. Для него (qk, qk ) (qk, g k ) + (g k, p k 1 )( k 1 + ) (qk, p k 1 ) (g k, p k 1 ) pk = gk + p k 1 qk, (3.33) (qk, p k 1 ) (q k, p k 1 ) где q k = g k g k 1.

Большое количество методов можно получить из следующей аналогии.

Рассмотрим дифференциальное уравнение w = E (w ). При достаточно общих предположениях его решение при t стремится к точке локального минимума функционала Е [125]. Для решения этого уравнения можно применить один из многочисленных известных численных методов. Самый простейший из них – метод Эйлера – получается заменой производной на отношение ( w k +1 w k ) / и эквивалентен методу градиентного спуска. На этой аналогии мы ещё остановимся позднее. Можно применить и более точные (и сложные) методы численного решения дифференциальных уравнений, например, Рунге-Кутта, получая соответствующие методы оптимизации.

Если градиент вычислить не удаётся, его можно оценить, например, по методу статистического градиента. Заметим только, что при этом получается метод, который не является релаксационным, т.е. может получиться, что E ( w k +1 ) E ( w k ). Вместо антиградиента используется вектор S [E (w ) E (w k + k i )] i, gk = (3.34) k k i = где i – независимые случайные векторы, например, как в пункте 1) параграфа 3.2, имеющие независимые координаты, равномерно распределённые в [-1,1], k, где k = – заданное пользователем положительное число, k gk + выбирается каким-либо методом одномерной минимизации – см. параграф 3.5, можно взять, к примеру, k = и т.д., k = s k 1 ;

s 1 (т.е. градиент k оценивается в более широкой области, чем делается шаг), хотя возможны и другие варианты.

Возможен гибрид метода статистического градиента и случайного поиска.

Алгоритм 3.5. Комбинированный алгоритм случайного поиска и статистического градиента.

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

2. Делаются пробные шаги алгоритма 3.2, при неудачных попытках – накапливается статистический антиградиент по формуле (3.34).

3. Удачный шаг производится, при этом статистический антиградиент забывается.

4. Если количество неудачных проб превысило заданное число – делается шаг по накопленному статистическому антиградиенту.

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

Следующая серия часто встречающихся в литературе по нейронным сетям эвристических алгоритмов, использующих градиент, отличается тем, что вычисления производятся по каждой координате по-отдельности, причём первый из них оказался на многих задачах не хуже гораздо более сложного – рассмотренного выше алгоритма BFGS с конечной памятью (см. формулу (3.33)). Обозначим wi (k ) = wi (k ) wi ( k 1).

Алгоритм 3.6. RProp.

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

Первый шаг делаем по антиградиенту wi (0) = gi (0);

– задаётся 2.

пользователем, например, = 1/ N.

3. На произвольном шаге переменные пересчитываются в соответствии с формулой 1 wi (k ) при gi (k ) gi (k 1) wi (k + 1) = 2 wi (k ) при gi (k ) gi (k 1) 0. (3.35) wi (k ) при gi (k ) gi (k 1) = Здесь 1 1, 2 1, рекомендуется 1 = 1, 2;

2 = 0,5.

Смысл метода – используется только знак координат градиента, поэтому движение получается не таким извилистым, как в методе наискорейшего спуска. Если знак координаты градиента сохраняется, то скорость движения по этой координате можно увеличить, если меняется – нужно уменьшить, если координата градиента обращается в 0, то движение не прекращается, что позволяет проскакивать локальные минимумы. Для усиления этого свойства равенство нулю в (3.35) можно заменить достаточной малостью произведения g i ( k ) g i ( k 1), т.е. первое неравенство меняется на gi ( k ) g i ( k 1), а второе – на g i ( k ) g i ( k 1), где – некоторое заранее заданное достаточно малое число.

Алгоритм 3.7. QuickProp. Отличается от предыдущего алгоритма тем, что (3.35) заменяется равенством wi (k + 1) = k wi (k), (3.36) gi (k ) при этом k =, если это выражение не превосходит по g i (k ) gi (k 1) абсолютной величине некоторого числа, которое задаётся пользователем. В gi (k ) противоположном случае k = sign( ). Смысл этого метода gi (k ) gi (k 1) состоит в покоординатном применении метода секущих к уравнению g i ( w ) = 0.

Начальное значение wi (0) задаётся так же, как и в предыдущем методе.

Алгоритм 3.8. Delta-delta.

Для этого алгоритма (3.35) заменяется равенством wi (k + 1) = i ( k ) g i ( k), (3.37) где i (k + 1) = i ( k ) + g i ( k ) g i ( k + 1), (3.38) 0 =, 0, 0 – задаются пользователем, i (0) =. Смысл тот же, что и в g (0) g i (0) i RProp, – ускорять движение, если знак компоненты градиента сохраняется, и замедлять, если меняется.

Алгоритм 3.9. Delta-bar-delta.

Отличается от предыдущего метода тем, что (3.38) заменяется равенством при Si (k ) gi (k + 1) i (k + 1) = i (k ) при Si (k ) gi (k + 1) 0. (3.39) при Si (k ) gi (k + 1) = Si ( k ) = (1 ) g i ( k ) + Si ( k 1);

0 1;

i (0) = Здесь, свободные g i (0) параметры задаются пользователем.

Для устойчивой работы последних двух методов требуется удачный подбор параметров.

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

3.4. Методы второго порядка Самым известным из этих методов является метод Ньютона. В самом общем виде он изучался в первом параграфе этой главы. Представим его в более простой форме, обычно применяемой на практике в задачах нелинейной оптимизации. Рассмотрим задачу поиска приближённого решения уравнения E (w ) = 0. Если имеется некоторое приближение к решению w k, то в окрестности этой точки E (w ) = E (w k + w w k ) E (w k ) + 2 E (w k )(w w k ).

Будем искать w k +1 как корень последнего выражения w k +1 = w k 2 E 1 (w k )E (w k ).

или w k +1 = w k + 2 E 1 (w k ) g k. (3.40) Обычно для более устойчивой работы алгоритма добавляется размер шага, т.е. метод работает в соответствии с формулой w k +1 = w k + k 2 E 1 (w k ) g k, (3.41) где k ищется каким-либо методом одномерной минимизации. При этом предполагается, что 2 E (w k ) существует (функционал ошибки Е – дважды дифференцируемая по своим аргументам w функция), а матрица 2 E (w k ) положительно определена и обратима.

Для вычисления элементов этой матрицы продифференцируем (1.9) f j f j 2 f j 2E Nk = [ + ( f j (w, x n ) ynj ) ]. (3.42) wi wl n =1 j =1 wi wl wi wl Если в (3.42) в квадратных скобках оставить только первое слагаемое и в 2 E (w k ) (3.41) вместо матрицы использовать получившуюся матрицу N k 2 E f j f jT, получается метод Ньютона-Гаусса:

n =1 j = w k +1 = w k + k 1g k. (3.43) k Этот метод примерно такой же эффективный, как и метод Ньютона, но не требует вычисления вторых производных. Недостатком его является то, что матрица k часто плохо обусловлена, что затрудняет её обращение. Для преодоления этого недостатка (3.43) заменяется равенством w k +1 = w k + k ( k + k I ) 1 g k. (3.44) Легко видеть, что такое изменение метода Ньютона-Гаусса эквивалентно добавлению в функционал слагаемого, пропорционального w w k. Другой трактовкой такой модификации является поиск минимума E (w ) в некоторой w w k, в которой можно считать эту достаточно малой окрестности функцию достаточно близкой к квадратичной форме. При выборе k = получается метод Ньютона-Гаусса, при стремлении k + направление движения приближается к антиградиенту. На практике обычно используется какое-либо промежуточное значение, т.е. считают величину k постоянной или стремящейся к нулю по заранее заданному закону. Этот метод называется методом Левенберга-Марквардта.

Аналогичного эффекта можно добиться и другими способами, например, аккуратной регулировкой шага k или иным способом регуляризации решения системы k u = g k.

Однако (3.44) по-прежнему требует обращения матрицы, что в случае большой размерности пространства параметров является весьма трудоёмкой операцией. Для обхода этой трудности пытаются получить приближение к 2 E 1 или 1 в результате итераций, без обращения матрицы. Такие методы k называются квазиньютоновскими. Общая схема этих методов заключается в вычислении направления движения по формуле pk = H k gk, (3.45) где H k – некоторая матрица. Легко видеть, что все предыдущие методы данного параграфа укладываются в эту схему при разных матрицах H k.

Алгоритм 3.10. Обобщённый алгоритм квазиньютоновского типа.

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

Очередной шаг начинаем с вычисления вектора g k = E ( w k ).

2.

3. Вычисляем матрицу H k – конкретный алгоритм получается заданием такой процедуры.

4. Вычисляем направление движения по формуле (3.45).

5. Вычисляем шаг каким-либо способом одномерной минимизации, например, одним из приведённых в следующем параграфе.

6. Повторяем шаги 2-5 необходимое число раз.

Остаётся построить алгоритм вычисления H k таким образом, чтобы H k 2 E 1 (w k ). Несколько формул такого рода приведено ниже. В них используется обозначение z k = H k (g k g k +1 ).

1) Метод сопряжённых направлений H k +1 = H k z k zT. (3.46) k (z k, g k g k +1 ) 2) Метод BFGS (z, g g k +1 ) [(k + k k H k +1 = H k + )p k pT z k pT p k zT ]. (3.47) k k k (p k, g k g k +1 ) (p k, g k g k +1 ) Следующие несколько формул описывают методы Шора [189]. Главное их достоинство состоит в том, что они работают и в случае, когда E (w ) не является дифференцируемой функцией. При этом вместо градиента E, используется субградиент, т.е. вектор для которого условие E (w + u) E (w ) + (E, u) выполняется для всех достаточно малых u.

3) В (3.46) вместо единицы в числителе дроби используется число, принимающее значение от 0 до 1.

4) H k +1 = H k p k pT. По этому методу шаг ищется по формуле k (p k, g k ) 2( E (w k ) E* ) k =, где E* – оценка минимума, например, 0.

(p k, g k ) ( E (w k ) E* ) p k pT, 0 1;

k = H k +1 = H k 5) число, k (p k, g k ) (p k, g k ) задаётся пользователем или подбирается в процессе работы алгоритма.

6) Метод эллипсоидов (применим для не очень больших размерностей).

Отличается от 5) выбором =, где n – число подбираемых параметров, n + n ) k, – радиус шара, в котором локализован экстремум, k = ( n +1 n например, если все переменные по абсолютной величине не превосходят a, то =a n.

7) Метод растяжения пространства в направлении разности двух последовательных субградиентов z k zT ;

0 1.

H k +1 = H k k (z k, g k g k +1 ) Эта формула при = 1 вырождается в формулу (3.46). Напомним, что в методе сопряжённых направлений g k – антиградиент.

Замечание. Во всех методах 1)-6) в качестве начального приближения берётся единичная матрица.

Другим способом избежать лобового обращения матрицы является применение рекуррентных процедур из [5], что особенно удобно в случае применения методов Ньютона-Гаусса и Левенберга-Марквардта.

Закончим параграф двумя методами из [242]. Эти методы были разработаны с целью преодоления недостатков предыдущих алгоритмов. В частности, метод Ньютона не работает, если матрица 2 E (w k ) не является положительно определённой и достаточно хорошо обусловленной, поведение метода Левенберга-Марквардта зависит от удачного выбора k, аналогичные проблемы возникают и для квазиньютоновских методов. Последующие два метода ведут себя значительно устойчивее, при этом в первом из них можно брать шаг k = 1.

Алгоритм 3.11. Relax.

1. Задаём начальные значения подбираемых переменных w0, достаточно малое число h0 (например, ) и параметр m7.

0, 2 E Очередной шаг начинаем с вычисления вектора g k = E ( w k ).

2.

Вычисляем 2 E (w k ) и оцениваем H k ( h0 ) по формуле 3.

m H k = h0 ( 2 Eh0 )i 1 / i !. (3.48) i = H k (2h) = H k (h)[2I 2 EH k (h)] 4. Проводим итерации по формуле или H (ki +1) = H (ki ) [2I 2 EH (ki ) ], пока функционал E (w k + H (ki )g k ) убывает.

Переходим в новую точку w k +1 = w k + k H (ki )g k.

5.

6. Повторяем шаги 2-5 необходимое число раз.

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

Алгоритм 3.12. Relch.

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

2. Производим несколько шагов метода наискорейшего спуска, пока g k + не стабилизируется около некоторого значения.

gk 3. Оцениваем степень овражности r функционала E (w ) следующим образом: r.

gk 4. Полагаем p (1) = 0 и p (2) = 2g k, где g k =.

k k gk 2 E (w k ) 5. Вычисляем и проводим итерации по формуле 2 E ( s ) s 1 ( s 1) 4 s p (ks +1) = (I 2 )p k s +1 p k + s+1 g k. (3.49) 2s s + 2 E p k = p (kM ), 6. В качестве направления движения выбираем где рекомендуется брать M 1.3 r.

7. Вычисляем шаг каким-либо способом одномерной минимизации, например, одним из приведённых в следующем параграфе.

8. Повторяем шаги 4-7, при этом оценку степени овражности r (шаги 2 и 3) можно проводить не на каждой итерации.

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

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

Алгоритм 3.13. Плавающий шаг.

Параметры алгоритма – 1 : 1 1, 2 : 0 2 1 и начальный шаг 1.

задаются в начале работы всего алгоритма. Обычно выбирают 1 = 2, 2 = 0,5.

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

3. На очередном шаге вычисляем значение функционала ошибки E (w k + k-1p k ).

4. Если это значение меньше предыдущего E (w k ), то шаг умножаем на 1 и снова вычисляем значение ошибки. Если функционал ошибки продолжает убывать, то шаг снова умножаем на число 1 и т.д., пока ошибка не начнёт возрастать. Тогда предпоследнюю точку (минимум) фиксируем, вычисляем новое направление и повторяем процедуру сначала.

Если E (w k + k-1p k ) больше E (w k ), то шаг умножаем на число 2 и 5.

продолжаем уменьшение шага, пока ошибка не станет меньше E (w k ).

Получившийся шаг фиксируем и вычисляем новое направление.

Этот метод регулировки шага удобен в простейших релаксационных алгоритмах, когда известно, что p k – направление убывания: например, в алгоритме тяжёлого шарика, ПАРТАН. Можно его применять и для BFGS.

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

Алгоритм 3.14. Парабола.

1. Первый шаг делается так же, как и в предыдущем алгоритме, т.е.

берётся шаг с предыдущей итерации.

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

3. По трём точкам (начальной и двум последним) проводим параболу.

4. Вычисляем значение ошибки в её вершине. Если обозначить предпоследний шаг за, то координата вершины легко вычисляется:

E (w k +2 p k )+3E (w k ) 4E (w k + p k ).

2 E (w k +2 p k )+2E (w k ) 4E (w k + p k ) 5. Отбрасываем крайнюю точку, которая соответствует большему значению минимизируемого функционала, и проверяем, будут ли оставшиеся три точки образовывать вогнутую кривую.

6. Если это условие выполняется, то дальше построение параболы повторяем, т.е. снова проводим шаги 3-5.

7. Если условие шага 5 не выполнено, то отбрасываем другую крайнюю точку и опять проводим шаги 3-5.

8. Критерии завершения процедуры построения парабол:

а) Заданное число шагов.

б) Изменение ошибки становятся меньше заданного числа.

в) Изменение шага становится меньше заданного числа.

9. После этого делаем шаг, соответствующий минимуму ошибки, и определяем новое направление.

10. Если первый шаг неудачный – делим его пополам и т.д., пока шаг не окажется удачным. После этого проводим ту же процедуру построения парабол, что и в первом случае.

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

Следующий алгоритм основан на том факте, что можно вычислить производную функции ( ) = E ( w k + p k ) по размеру шага (0) = (g k, p k ).

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

Алгоритм 3.15. Метод высшего порядка.

Если (0) = (g k, p k ) 0, то данное направление не является 1.

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

Если (0) 0, то данное направление является направлением 2.

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

1 = (1 ) (0) (0)1 0, 2 = 3. Если то полагаем и переходим к шагу 5. Эта ситуация означает, что точка, соответствующая шагу 1, лежит ниже прямой, проведённой через точку (0) с угловым коэффициентом (0), и построение параболы по этим данным лишено смысла.

Если 1 0, то по двум точкам и касательной в 0 строим параболу и 4.

(0) находим значение ошибки в её вершине, т.е. вычисляем 1 = 1 / 12, 2 = и ( 2 ).

5. После этого можно:

i, a. окончить процедуру, взяв в качестве искомого шага соответствующее минимальному значению из (1 ) и ( 2 ), b. продолжить построение парабол, возвратившись к пункту 3 со значением 2 вместо числа 1, c. уже по трём точкам и производной в 0 построить многочлен третьего порядка, т.е. перейти к пункту 6.

Вычисляем 2 = ( ( 2 ) (0) (0) 2 ) / 2 и 1, если оно не было 6.

вычислено ранее.

1 2 21 Вычисляем a = и b= 2 1.

7.

2 1 2 8. Находим дискриминант квадратного уравнения, которое соответствует необходимому условию минимума построенного многочлена третьего порядка по формуле d = a 2 3b (0). Если d 0, то проводим те же операции, что и в пунктах 3 и 4 (удвоение шага или переход в вершину параболы соответственно), и переходим к пункту 10.

a + d при a 3b Если d 0, то можно вычислить 3 = 9..

(0) при a a+ d Вычисляем ( 3 ) и в результате получаем четвёртую точку, 10.

которую опять можно использовать для реализации одного из вариантов пункта 5, или можно по всем четырём точкам построить многочлен четвёртой степени, перейдя к пункту 11.

Вычисляем 3 = ( ( 3 ) (0) (0) 3 ) / 32, а также 1 и 2, если 11.

они не были вычислены ранее.

1 Вычисляем выражения 1 =, 2 = 12.

( 2 1 )( 3 1 ) ( 2 1 )( 3 2 ) и 3 =.

( 3 2 )( 3 1 ) Вычисляем необходимые далее числа a = 1 2 3 21 3 + 31 2 ;

13.

b = 1 ( 2 + 3 ) + 2 (1 + 3 ) 3 ( 2 + 1 ) и c = 1 2 + 3.

ab (0) a 3b 2 b Вычисляем p = и q= 2+ 14..

2c 16c 2 32c3 8c 4c q 2 p Вычисляем D = +. Если D 0, то поступаем аналогично 15.

4 пункту 8.

Если D 0, то дальнейшие вычисления зависят от знака q. При 16.

q p 4 = ( q0 s= +D + s). q полагаем и При полагаем 2 3s q p p s = 3 + D и 4 = ( + s ). При q = 0 – 4 =.

2 3s Выбираем минимальное значение из чисел (1 ), ( 2 ), ( 3 ) и 17.

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

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

например, когда применяется метод статистического градиента или когда функция E (w ) не является дифференцируемой. Идея этого метода состоит в поиске глобального экстремума многоэкстремальной функции на отрезке [a, b] путём кусочно-линейной аппроксимации, использующей оценку постоянной Липшица, и последовательного дробления.

Алгоритм 3.16. Метод глобальной одномерной оптимизации. Опишем метод [212] в простейшем варианте. Пусть ищется экстремум функции ( x ) на интервале [a, b].

Выбираем параметр r 2 + 1, если зоны притяжения локального и 1.

глобального минимума примерно одинаковы, и r 2, если зона глобального минимума шире (обычная ситуация для рассматриваемых задач).

Вычисляем значение ( x ) на концах интервала и (возможно) в 2.

некоторых внутренних точках, выбранных по другому алгоритму (например, одному из предыдущих). Пусть уже есть точки a = x0 x1... xk = b, в которых было вычислено значение функции ( x ).

3. Вычисляем rM при M zi zi zi = ( xi );

M = max, m=. (3.50) 1 при M = xi xi 1 1i k Пусть i – номер, для которого достигает максимального значения 4.

величина ( zi zi 1 ) R(i ) = m( xi xi 1 ) + 2( zi + zi 1 ). (3.51) m( xi xi 1 ) xi + xi 1 zi zi Тогда xk +1 определяется следующим образом xk +1 =.

2 2m 5. Далее точки перенумеруем в порядке возрастания и продолжаем применять метод необходимое число раз.

Существуют два способа выбора интервала [a, b].

Пусть k 1 – размер шага в предыдущей итерации, тогда можно I.

взять a = 0 ;

b = k 1, где 1. В этом случае точка a не учитывается при нахождении минимума.

a = 1 k 1;

0 1 1;

b = 2 k 1;

2 1, II. при этом, в отличие от предыдущего варианта, точка a теперь учитывается при вычислении минимума. Этот вариант обычно предпочтительнее, так как исключает неконтролируемое уменьшение шага.

3.6. Методы глобальной оптимизации Методы, которые были описаны в предыдущих параграфах, являются локальными, т.е. позволяют найти только локальный минимум. Так как функция ошибки E (w ) в большинстве случаев многоэкстремальная, они обычно не позволяют найти наилучшее решение исходной задачи. Для нахождения такого решения требуется применить процедуру, позволяющую найти глобальный минимум. Упрощает проблему то обстоятельство, что нас интересует не сам глобальный минимум, а точка, в которой ошибка E (w ) достаточно мала. Опишем несколько подходов к такому глобальному поиску.

Методы рестарта. Можно запустить методы поиска локального экстремума с нескольких стартовых точек. Эти точки могут быть выбраны регулярно по тому или иному закону (например, равномерно в некоторой области) или случайно. Можно заменять последовательности с достаточно близкими траекториями на одну, сокращая объём вычислений. Другой, более простой подход к реализации такого алгоритма – проводим рестарт поиска локального минимума, пока E (w k ) не достигнет достаточно малого значения, – этим исключается проблема выбора числа стартовых точек. Приведём более конкретное описание алгоритмов такого рода.

Алгоритм 3.17. Метод рестартов (последовательный вариант).

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

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

3. Если требуемая величина ошибки не достигнута, то фиксируем конечное значение вектора w k и соответствующее значение функционала ошибки E (w k ).

4. Повторяем пункт 1, выбирая другой вектор w 0. При этом возможны замена локального алгоритма в целом или изменение его параметров.

5. Повторяем пункт 2, добавляя в качестве условия останова близость к достигнутым в предыдущих стартах значениям w k.

6. Повторяем пункт 3, фиксируя точку с минимальным значением E (w k ).

7. Повторяем пункты 4-6 до достижения требуемой величины ошибки, истечения времени расчётов или реализации заданного числа рестартов.

Алгоритм 3.18. Метод рестартов (параллельный вариант).

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

2. Проводим шаги выбранного локального алгоритма до выполнения условия останова в каждом из процессов.

3. Если все итерационные процессы сошлись к одной точке, то её можно считать точкой глобального минимума, если нет – за глобальный минимум можно принять точку w k с минимальным значением E (w k ).

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

А) Из каждого кластера берём по одной точке с минимальным значением E (w k ), добавляем случайно или регулярно выбранными точками до прежнего их количества, снова проводим локальный спуск и т.д.

Б) Помимо лучшей точки, берём и центр кластера, далее продолжаем так же, как и в А).

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

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

Методы облака. Эти алгоритмы похожи на предыдущий алгоритм тем, что движется не одна точка, а несколько. Их отличие состоит в том, что точки движутся не каждая сама по себе, а их движение взаимосвязано. Подобный метод приведён в [98]. Опишем один из его вариантов.

Алгоритм 3.19. Метод виртуальных частиц.

1. Выбираем начальные значения подбираемых переменных w (например, случайно в заданном множестве), алгоритм локальной оптимизации и его параметры 2. Генерируем некоторый набор точек, распределённых не во всей области изменения параметров, а в некоторой достаточно малой окрестности точки w 0, например, в шаре достаточно малого радиуса.

3. В каждой точке вычисляем градиент, эти градиенты усредняем и точки облака сдвигаем в соответствии с методом градиентного спуска (или какого-либо другого локального алгоритма).

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

Особенно удачной оказалась комбинация этого алгоритма с методом Rprop (алгоритм 3.6), т.е. каждая точка облака движется в соответствии со знаками координат суммарного градиента по всем точкам облака.

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

Алгоритм 3.20. Метод плотного облака.

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

2. Генерируем начальный набор точек, распределённых в достаточно малой окрестности точки w 0.

3. Вычисляем градиент ошибки для каждой точки облака и вычисляем сдвиги из каждой точки в направлении каждого градиента – из n точек получается n 2 новых.

4. Из получившихся точек выбираем n лучших и шаг 3 повторяем необходимое число раз.

Рис.3.2. Блок-схема алгоритма плотного облака Недостаток такого подхода состоит в том, что точки могут «слипнуться».

Для решения этой проблемы можно предложить несколько вариантов пункта 4:

а) Выбираем n кластеров и за новые точки берём их центры. Недостаток подобного выбора заключается в том, что метод становится менее устойчивым.

б) Выбрасываем определённую долю худших точек, далее проводим кластеризацию точек облака и далее как в а).

в) Выбрасываем все точки с возросшей ошибкой, если их остаётся слишком мало, то пополняем облако новыми точками (например, случайной генерацией) до того момента, когда их число снова станет n.

г) За новый центр берём среднее лучшего (в смысле средней ошибки) кластера, далее генерируем новое облако вокруг этого центра.

Можно модифицировать и пункт 3 алгоритма 3.20: например, вместо градиентного спуска использовать случайный поиск или вместо случайных векторов использовать направление из точек друг на друга, покоординатные сдвиги и т.д.

Алгоритм 3.21. Метод квадратичной оценки.

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

2. Генерируем начальный набор точек, распределённых в некоторой достаточно малой окрестности точки w 0.

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

4. Смещаемся в точку минимума соответствующей квадратичной формы, вокруг неё образуем новое облако.

5. Пункты 4 и 5 повторяем до выполнения условия останова.

Алгоритм 3.22. Метод покоординатного облака.

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

2. В качестве облака рассматриваем множество точек, отличающихся от центра только одной координатой.

3. Из каждой точки смещаемся, меняя ещё одну координату.

4. Из получившегося набора выбираем лучшую точку и повторяем пункты 2 и 3 необходимое число раз.

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

Алгоритм 3.23. Метод поколений.

1. Выбираем начальное вероятностное распределение.

2. Методом статистического моделирования получаем заданное число точек k и в них вычисляем значение E ( k ).

3. По результатам предыдущего пункта моделируем новое распределение, концентрирующееся в областях с наименьшими значениями E ( k ). В качестве такого распределения можно взять сумму гауссианов, тогда его можно представить RBF-сетью (см. 1.3).

4. Возвращаемся к пункту 2.

Этот алгоритм можно скомбинировать с локальной оптимизацией, т.е.

после пункта 2 следует производить заданное число шагов локальной оптимизации из каждой точки k – например, несколько шагов наискорейшего спуска – и по получившимся результатам моделировать новое распределение, используя для его построения все промежуточные результаты или только получившиеся минимумы.

Можно сочетать метод многогранника (алгоритм 3.3) с градиентным методом спуска из каждой вершины. Если при этом многогранник не уменьшать, т.е. худшую точку просто отображать симметрично относительно среднего остальных, то получится нелокальный метод.

Алгоритм 3.24. Модифицированный метод многогранника.

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

2. Строим правильный симплекс около этой точки (см. шаг алгоритма 3.3).

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

4. Проводим несколько шагов какого-либо градиентного метода спуска из каждой вершины.

5. Точка, в которой значение E (w ) максимально, отражается относительно среднего остальных вершин c : wmax (k + 1) = 2 wi, j (k ) wmax (k ).

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

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

Для обоснования сходимости модифицированного метода многогранника предположим, что делается достаточное число шагов градиентного метода, для того, чтобы попасть в достаточно малую окрестность локального экстремума или оврага, после этого можно применить обычные обоснования метода многогранника [108]. Для этого надо выбрать некоторую модель минимизируемой функции, например, E ( w ) = E0 (w ) + E1 (w ). Здесь E0 ( w ) – фиксированная унимодальная (имеющая единственный экстремум) функция, например, положительно определённая квадратичная форма, E1 (w ) – функция, добавление которой создаёт многоэкстремальность, например, тригонометрический полином достаточно высокой частоты, – малый параметр. Если локальная скорость изменения E (w ) определяется вторым слагаемым, то локальные методы будут приводить в окрестности точек локальных минимумов E1 (w ), и можно считать, что метод многогранника применяется к E (w ) = E0 (w ) + E1 (w ), где E1 (w ) – огибающая E (w ) по точкам локальных минимумов E1 (w ), в простейшем случае – некоторая константа.

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

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

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

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

Алгоритм 3.25. Конкуренция методов оптимизации.

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

2. Стартуем выбранные алгоритмы из точки w 0 на определённый промежуток времени (один шаг разных алгоритмов требует различных временных затрат, поэтому нет смысла запускать алгоритмы на определённое число шагов).

3. Выбираем лучший результат и снова стартуем все алгоритмы из этой точки.

4. Шаги 2 и 3 повторяем, пока не выполнится условие останова.

Если среди выбранных алгоритмов есть глобальный, то общий алгоритм тоже получается глобальным. Более продвинутый вариант алгоритма 3. получается, если перезапускаются не все алгоритмы, а только некоторая случайно выбранная часть. При этом вероятность выбора должна быть разной и зависеть от того, как показал себя алгоритм на предыдущих этапах: у лучшего на этапе алгоритма вероятность его запуска в дальнейшем увеличивается, а у худшего – уменьшается. Лучший на каком-либо этапе алгоритм логично оставить работать и на следующем этапе. Ещё более продвинутый вариант алгоритма 3.25 включает в себя не только базовые алгоритмы, но и их мутации, которые заключаются в изменении параметров. При этом наиболее интенсивно должны «мутировать» наименее удачно работающие алгоритмы. Так как информация о работе различных алгоритмов может накапливаться по мере решения разных задач, реализующая такой алгоритм программа со временем может самообучаться, т.е. с большей вероятностью выбирать наилучший алгоритм. На основе накопившейся информации – размерности задачи, объёма выборки, скорости убывания ошибки и т.д. – может обучаться вторичная нейронная сеть, которая может выбирать оптимальный поднабор алгоритмов и их параметры.

Опишем подобный алгоритм пошагово.

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

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

2. Стартуем два алгоритма из точки w 0 на определённый промежуток времени.

3. Выбираем лучший результат и увеличиваем ранг проигравшего алгоритма на 1. Проигравший алгоритм мутирует (случайно изменяются его параметры в соответствии с определёнными заранее правилами).

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

5. Шаги 2-4 повторяем, пока не выполнится условие останова.

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

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

Алгоритм 3.27. Имитация отжига [252]. Смысл этого метода состоит в моделировании хаотического перемещения молекул в остывающем теле.

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

2. Делаем шаг алгоритма (например, по антиградиенту).

3. Если в выбранном локальном методе ошибка возрастает, т.е.

E (w k ) E (w k +1 ) E (w k+1 )E (w k ), то эта точка принимается с вероятностью exp( ), Tk где Tk – «температура», Tk 0. Если ошибка убывает, то шаг делается наверняка.

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

Варианты выбора Tk :

T а) Tk =, 1+ kn б) Tk – постоянная (сходимость алгоритма вызвана убыванием шага), ), где – растущая функция своих аргументов, – в) Tk = ( E (w k ), + среднеквадратичное изменение ошибки по отвергнутым шагам, + – по принятым, г) При неудачном шаге температура возрастает, при удачном – убывает.

Метод имитации отжига близок к методу градиентного спуска, при 2Tk k [125]. Здесь в котором к вектору антиградиента g k добавляется шум качестве k обычно используют нормально распределённый случайный вектор, имеющий нулевой вектор средних и единичную ковариационную матрицу.

Этот подход можно применить не только к методу градиентного спуска, но и к другим методам, причём в качестве k можно использовать и другую случайную добавку, например, с равномерно распределёнными от -1 до координатами.

Приведём алгоритм, напоминающий имитацию отжига, но более простой.

На практике он показал себя достаточно эффективным. Идея предлагаемого подхода состоит в том, чтобы условие убывания ошибки заменить условием E (w k +1 )E (w k )+ k, где k – некоторая последовательность, сходящаяся к 0.

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

Алгоритм 3.28. Метод прыгучего шарика.

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

2. Делаем шаг алгоритма (например, по антиградиенту).

Получившаяся точка принимается, если E (w k +1 )E (w k )+ k 3.

k. Например, при выполнении неравенства 4. Модифицируем (g k, g k 1 )0 k уменьшаем, а при (g k, g k 1 ) 0 – увеличиваем. Более сложный способ модификации состоит в том, что по углу между градиентами, изменениям размера шага и ошибки делается прогноз дальнейшего движения k итерационной последовательности и, исходя из этого прогноза, модифицируется оптимальным образом.

Рис.3.5. Блок-схема алгоритма прыгучего шарика Очевидно, что метод позволяет преодолевать неглубокие (глубиной менее k ) локальные минимумы и пологие подъёмы, характерные для оврагов.

Эффективность метода сильно зависит от удачного закона формирования k.

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

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

Алгоритм 3.29. Метод СПП (спуск-подъём-перевал).

1. Каким-либо методом отыскиваем локальный минимум w * ошибки E (w ). Критерием проверки того, что это локальный минимум, может служить, например, малость градиента или изменения ошибки за один шаг.

2. Делаем шаг по направлению предыдущего движения и из получившейся точки производим несколько шагов градиентного спуска u1,..., u k. Если мы приближаемся к точке, которую заподозрили на локальный экстремум, делается вывод, что это действительно локальный экстремум и u k w* вектор p k = берётся в качестве направления подъёма.

u k w* 3. Шаги фиксированного размера в направлении p k чередуются с шагами градиентного спуска, пока выполняется условие (p k, E ( w k )) (поднимаемся на перевал).

(p k, E ( w k )) 4. При выполнении условия перевал считается пройденным и начинается поиск нового локального экстремума.

Алгоритм 3.30. Туннельный алгоритм.

Отыскивается локальный минимум w * ошибки E (w ).

1.

E (w ) E (w* ) T (w ) = 2. Формируем туннельную функцию (или w w* другую функцию подобного вида) и ищем её минимум.

3. С точки этого минимума стартуем алгоритм поиска нового локального минимума E (w ).

Для выхода из локального экстремума можно применить и другие подходы, например, минимизировать другой функционал. В частности, если используется регуляризация, и мы попали в локальный минимум 1 E = E (w ) + w, то можно из него выйти, изменив. Как правило, в процессе обучения уменьшают, чаще всего, устремляя к 0.

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

Алгоритмы глобальной оптимизации, рассмотренные в данном параграфе, достаточно эффективны в задачах обучения нейронных сетей в случаях, когда размерность вектора оптимизируемых параметров (весов сети) составляет сотни и тысячи. В этих условиях известные методы глобальной оптимизации [125] теряют свою эффективность.

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

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

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

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

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

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

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

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

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

Алгоритм 3.31. Распределённая реализация метода рестартов.

1. На каждом из компьютеров запускается процесс поиска локального экстремума из своей точки.

2. Каждый узел через определённые промежутки времени посылает в другой узел, выбранный случайно или по определённому закону, свой идентификатор и значение функционала ошибки.

3. Узел, получивший такую информацию, сравнивает присланное значение функционала с полученным локальным процессом и отсылает далее информацию о лучшем результате. Является ли адрес посылки сообщений случайным или подчиняется определённому закону, надо, чтобы информация поступала в узлы максимально равномерно.

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

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

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

Если свой результат лучше – его надо переслать в другие узлы.

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


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

Если это значение достигнуто локально, то процесс оптимизации • останавливается и происходит рассылка результатов.

Если в другом узле – то этот узел должен прислать свои результаты • – веса и т.д.

Если соответствующий узел их ещё не прислал, то их следует • запросить.

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм 3.32. Распределённый вариант метода многогранника.

На каждом из компьютеров запускается процесс поиска локального 1.

экстремума из своей точки.

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

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

Получивший эту информацию компьютер пересчитывает среднее 3.

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

Шаг 3 повторяется. Каждый новый узел в этой цепочке получает 4.

среднее значение весов сети и совокупность значений функционалов ошибки, достигнутых предыдущими компьютерами. Принявший информацию компьютер может продолжить эту цепочку, т.е. пересчитать среднее значение весов по известной рекуррентной формуле c N = c N 1 + (w N c N 1 ). Если мы N можно заменить на учитываем устаревание информации, то множитель N число : 0 1.

Если выполнены некоторые условия (например, значение ошибки в 5.

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

Если сеть ненадёжна и компьютер долго не получает таких 6.

«посланий» от других узлов, он сам инициирует новую цепочку.

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

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

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

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

Рис.3.7. Блок-схема распределённой реализации метода многогранника Распределённый вариант метода кластеризации промежуточных результатов. Аналогичной модификации можно подвергнуть и другие алгоритмы глобальной оптимизации. Одним из наиболее известных и результативных направлений повышения эффективности метода рестартов является процедура кластеризации получившихся промежуточных результатов.

После кластеризации выбирается один (например, лучший) представитель кластера, и производятся спуск из этой точки и рестарт из остальных [125].

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

Алгоритм 3.33. Распределённый алгоритм оптимизации с кластеризацией по методу k -средних.

Каждому узлу при старте минимизации присваивается некоторый 1.

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

После некоторого числа шагов локальной оптимизации этот номер 2.

вместе со значениями весов пересылается в другой – например, случайный – узел.

Если этот номер совпадает с номером получившего пакет 3.

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

Если номер другой, то полученное среднее сравнивается с 4.

последним сохранённым средним своего класса и своими текущими весами.

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

Шаги 2-4 повторяются с очевидной модификацией – сравнение 5.

происходит со всеми полученными средними в пакете.

После некоторой работы алгоритма начинают пересылаться не 6.

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

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

Рис.3.8. Блок-схема распределённого алгоритма оптимизации с кластеризацией по методу k -средних Алгоритм 3.34. Распределённое обучение сети Кохонена.

Фиксируем число нейронов, начальные веса w i (0) и способ 1.


определения функции i ( k ).

В распределённом варианте веса исходной сети, подбираемые в 2.

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

Компьютер, получивший набор весов сети, сравнивает его с весами 3.

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

Выбирается наиболее близкий вес и пересчитывается по формуле 4.

w i (k + 1) = w i (k ) + i ( k )( x n w i ( k )). (3.52) или иной формуле, соответствующей обучению сети Кохонена.

Изменённые веса сети Кохонена пересылаются дальше. При 5.

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

Каждый компьютер время от времени отсылает веса сети Кохонена 6.

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

Если пришёл нейрон, соответствующий тому же номеру кластера, 7.

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

Реализуем шаг 6 алгоритма 3.33 или некоторый его аналог.

8.

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

Распределённые варианты других глобальных алгоритмов. Для ограничения областей перебора можно попытаться применить метод ветвей и вероятностных границ [125], основная идея которого заключается в исключении заведомо неперспективных областей. Особенностью рассматриваемых задач является большая размерность, поэтому представляется разумным рассматривать перспективность некоторых комбинаций знаков весов. Таким образом, можно пересылать знаки весов и соответствующие этим знакам значения функционала ошибки. На основе получаемой таким образом информации в каждом узле реализуется некоторый алгоритм принятия решений о перспективности тех или иных комбинаций знаков на основе методов дискретной оптимизации и распознавания образов (см. [32], [169], [241] и др.).

Возможна пересылка информации, соответствующая кластеру, а не индивидуальным результатам.

Ещё одним подходом к глобальной минимизации многоэкстремальной функции является свёртка с унимодальной функцией [125]. Если E (w ) – функция ошибки, которую мы минимизируем, то вместо неё мы можем минимизировать функцию G (u) = E (w ) p (u w )dw, где p (u) – сглаживающая функция, например, плотность некоторого вероятностного распределения. Чем ближе p(u) к -функции, т.е. чем в большей степени она локализована в окрестности нуля, тем ближе G (u) к E (w ). Чем дальше p (u) от -функции, т.е. чем более она размазана, тем более гладкой получается G (u) и тем проще её минимизировать. Обычно рассматривается семейство функций G (u ) = E ( w ) p (u w ) dw, p (u) (u).

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

Такой алгоритм достаточно удобно распределяется, если свёртку вычислять методом Монте-Карло, т.е. минимизировать функцию 1N E (w k ), G (u) = (3.53) N k = где точки w k выбраны случайно в соответствии с распределением p (u w ).

Если функция p (u) выбрана достаточно удачно, то можно вычислить градиент G (u) в соответствии с формулой G (u) = E ( w )p (u w ) dw, причём этот интеграл тоже можно вычислить по методу Монте-Карло.

u 1 Например, если взять p (u) = e, что соответствует многомерному (2 ) n / нормальному распределению с нулевым математическим ожиданием и, дисперсией то для градиента получится формула uw E (w ) G (u) = e 2 (w u)dw. Метод Монте-Карло позволяет получить (2 ) n/ оценку градиента 1N E (w k )(w k u), G (u ) = (3.54) N k = где вектор w k распределён нормально с математическим ожиданием u и дисперсией.

Алгоритм 3.35. Распределённое обучение нейронной сети методом сглаживания.

Выбираем начальные значения весов u и другие параметры 1.

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

На каждом компьютере производим независимую генерацию точек 2.

w k в соответствии с распределением p (u w ).

На каждом компьютере проводим вычисления по формулам (3.53) и 3.

(3.54). При этом отдельные части сумм вычисляются на разных компьютерах.

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

4.

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

В конечном компьютере осуществляется шаг некоторого алгоритма 5.

минимизации G (u), т.е. вычисляются новые веса обучаемой сети.

Итоговые результаты пересылаются в обратном порядке.

6.

Повторяем шаги 2-6 до выполнения условий останова. При этом 7.

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

Рис.3.10. Блок-схема распределённого обучения методом сглаживания Локально могут применяться и разные унимодальные функции p (u), но при этом должны использоваться значения исходной функции (ошибки нейронной сети), полученные в других узлах, так как вычисления этих значений ресурсоёмки, хотя такой подход и затрудняет использование метода Монте-Карло.

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

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

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

Алгоритм 3.36. Распределённый генетический алгоритм определения структуры нейронной сети.

Определяем начальный набор нейронных сетей, различающихся 1.

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

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

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

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

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

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

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

Тогда, если nT nL, то сеть следует сокращать, т.е. увеличивать вероятность удаления весов и нейронов, а если nT nL, то, наоборот, увеличивать вероятность добавления весов и нейронов. Чем больше nT и nL, тем больше следует установить вероятность транслокации.

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

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

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

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

9. Повторяем пункты 3 и 4.

10. Повторяем шаги 3-8 до выполнения условий останова.

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

Алгоритм 3.37. Распределённый алгоритм популяций.

На каждом узле задаём некоторый набор нейронных сетей, 1.

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

На каждом компьютере стартует свой генетический алгоритм. Это 2.

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

В моменты времени, определяемые локальным генетическим 3.

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

Время от времени происходит скрещивание сетей, находящихся на 4.

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

Шаги 2-4 повторяются до выполнения условий останова.

5.

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

Рис.3.12. Блок-схема распределённого алгоритма популяций Можно посылать на другие узлы не сами сети, а некоторые их куски как заготовки для скрещивания, если такая работа предусмотрена локальным генетическим алгоритмом. Это уменьшает объём пересылаемых данных в случае, когда обучаемая сеть достаточно велика.

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

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

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

Проводим кластеризацию примеров для каждого компьютера 1.

отдельно.

Выбираем из каждого кластера по представителю, возможен выбор 2.

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

Рассылаем представителей по всем компьютерам.

3.

Обучаем на этом множестве примеров сеть с помощью какого-либо 4.

алгоритма из предыдущего параграфа.

Не вошедшие в обучающую выборку локальные примеры 5.

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

Примеры, на которых ошибка максимальна, включаем в 6.

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

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

7.

Рис.3.13. Блок-схема алгоритма кластерного обучения нейронной сети на распределённой базе данных с проверкой Ещё интересней применить в данной ситуации генетический алгоритм, например, построенный на идеологии МГУА.

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

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

сетей, фиксируются параметры алгоритма.

Реализуем локально некоторый генетический алгоритм, в 2.

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

На каждом узле выбираются лучшие сети и рассылаются на другие 3.

компьютеры.

Каждый узел производит скрещивание лучших локальных сетей с 4.

пришедшими сетями.

Продолжаем локальное обучение получившейся популяции, в 5.

которую худшие сети из данного узла не включаются.

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

Алгоритм 3.40. Кластерное обучение нейронной сети в случае распределённой по части узлов базы данных.

Проводим кластеризацию примеров для каждого компьютера, на 1.

котором находится часть данных.

Выбираем из каждого кластера по представителю.

2.

Рассылаем представителей по компьютерам, на которых изначально 3.

данные отсутствовали.

Компьютеры, на которые данные присылаются, используются для 4.

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

В хранилищах данных эти сети проходят проверку на полной 5.

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

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

останавливается.

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

Алгоритм 3.41. Кластерное обучение нейронной сети в случае распределённой по части узлов пополняемой базы данных.

Проводим динамическую кластеризацию примеров для каждого 1.

компьютера, на котором находится часть данных.

Время от времени выбираем из каждого кластера по представителю, 2.

причём радикально новые примеры рассылаются в экстренном порядке.

Рассылаем представителей по компьютерам, на которых изначально 3.

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

Компьютеры, на которые данные присылаются, используются для 4.

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

В хранилищах данных эти сети проходят проверку, 5.

модифицируются и рассылаются для дальнейшего обучения.

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

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

Ещё более интересный вариант получается при применении многорядного алгоритма МГУА.

Алгоритм 3.42. Многорядный МГУА-алгоритм обучения нейронной сети на распределённой базе данных.

На каждом узле, где это необходимо, переходим к главным 1.

компонентам.

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



Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 10 |
 





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

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