Искусственные нейронные сети

_________________________

|| x-y || = (x₁-y₁)² + (x₂-y₂)² + … + (x_n-y_n)², (2)

Радиальные базисные функции h_i (1) выполняют предварительную обработку входных векторов, определяя их близость (подобие) к центрам X_i. Выходные значения h_i(X) - это степени сходства между входным вектором X и отдельными центрами X_i. На основе значений h_i(X) определяется взвешенная сумма.

На рис. 2 представлен принцип работы нейрона скрытого слоя.

Рис. 2. Принцип работы нейрона скрытого слоя.

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

Из (1) следует: выход нейрона i скрытого слоя тем больше, чем ближе текущий вход X к центру X_i. Выход f RBF-сети определяется в виде взвешенной суммы

K

f(X) = y = c_i h_i (X), (3)

i=1

Нейроны выходного слоя образуют, следовательно, линейную комбинацию выходов нейронов скрытого слоя (hidden layer). Их функция активации или выхода - это радиальная базисная функция (1).

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

k k

y_j = ( c_ij h_i ) / ( h_i ) (4)

i=1 i=1

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

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

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

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

5.2 Интерполяция при помощи центральных функций

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

Пусть f: Rⁿ R - функция из Rⁿ в R. Предположим, что эта функция задана своими значениями в N опорных точках (образы обучающей последовательности).

Для каждой опорной точки i задается n-мерный входной вектор

X_i = (x_i1, x_i2, … , x_in)^T

и соответствующее действительное значение функции y_i R. Для всех опорных точек X_i, i =1, 2, …, N должны быть соответственно выполнены следующие условия интерполяции:

f (X_i) = y_i (5)

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

h_i ( || X - X_i || ), i = 1, 2, … , N (6)

т.е. базисные функции h_i: Rⁿ R зависят от выбора опорных точек X_i. Свое название рассматриваемые RBF-сети получили по этим функциям, принимающим действительные значения. В качестве аргумента (входа) они используют расстояние между входным вектором X и опорным вектором X_i нейрона i скрытого слоя. При этом обычно определяется эвклидово расстояние (L₂ - норма) между обеими точками X и X_i в Rⁿ. Искомая функция представляется при этом в виде:

N

f (X) = c_i h_i ( || X - X_i ||) (7)

i=1

При решении проблемы интерполяции с помощью RBF-сетей опорными точками и соответственно весовыми векторами W_i нейронов скрытого слоя являются опорные векторы X_i: W_i = X_i, т.е. i-й скрытый нейрон в качестве весового вектора имеет i-й образ обучающей последовательности. Следовательно, задача интерполяции сводится лишь к определению коэффициентов c_i, i = 1, 2, … , N. На рис. 3 приведен пример представления функции в виде наложения (линейной суперпозиции) четырех радиальных одномерных базисных (иницептальных) функций с одинаковыми дисперсиями b².

Рис. 3. Представление функции в виде наложения четырех радиальных одномерных базисных функций.

Функция

f(x) = 0.3h (||x - 0.5||) + 0.5h (||x - 2||) + 0.4h (||x - 4||) - 0.3h (||x - 5||) (8)

представлена в виде взвешенной суммы отдельных функций Гаусса с четырьмя центрами x₁=0.5, x₂=2, x₃=4 и x₄=5 и весами c₁=0.3, c₂=0.5, c₃=0.4 и c₄= -0.3.

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

N

c_i h_i ( || X_j - X_i || ) = y_i, j = 1, 2, … , N (9)

i=1

Мы получили систему из N уравнений для N неизвестных. Можно также показать, что при выборе известных функций Гаусса в качестве центральных функций проблема интерполяции (9) непосредственно разрешима. Введем векторные обозначения:

C = (c₁, c₂, … , c_N)^T,

Y = (y₁, y₂, … , y_N)^T и

h₁ ( || X₁ - X₁ || ) … h_N ( || X₁ - X_N || )

H = … | (10)

h₁ ( || X_N - X₁ || )… h_N ( || X_N - X_N || ) ,

тогда проблему интерполяции (9) можно представить следующим образом:

H*C = Y (11)

Ее решение

C = H^-1*Y (12)

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

Однако если входные данные искажены (зашумлены), то точная интерполяция не имеет смысла. Следовательно, описанный выше метод следует модифицировать: проблема состоит в таком решении системы линейных уравнений H*C =Y (11), которое является робастным относительно шумов (помех) во входных данных. Простой и эффективный способ такого решения предложен академиком Тихоновым А. Н. и Арсениным в 1977 г. Сущность их предложения: матрица H заменяется матрицей H + I, где I - единичная матрица (identity matrix), а - "небольшой" параметр. Величина этого параметра пропорциональна силе шума во входных данных. Коэффициенты решения с помощью RBF-сети определяются при этом так:

C = (H + I )^-1 Y (13)

В соответствии с (13) решается, в сущности, задача аппроксимации, точное же решение задачи интерполяции достигается при = 0. Однако, если учесть, что входные данные на практике обычно зашумлены (содержат помехи), то решение на основе (13) является наиболее подходящим.

5.3 Интерполяция с помощью центральных функций и полиномов

В общем случае при интерполяции с помощью RBF-сетей в представлении искомой функции f учитываются дополнительно полиномы p(x). Соответственно общая форма представления функции f имеет вид:

N m

f (X) = c_i h_i (|| X - X_i ||) + d_i p_i (X), m n 14)

i=1 i=1

Полиномы p_i образуют при этом пространство полиномов _k-1(Rⁿ) из Rⁿ в R с максимальной степенью k-1, причем значение k задается. Для определенных центральных функций это дополнение полиномами является необходимым для решения проблемы интерполяции. Кроме того, введение полиномов способствует дополнительному сглаживанию функции f, т.е. таким способом могут быть существенно уменьшены колебания функции между опорными точками, следует однако учитывать, что это не относится к RBF-сетям, в которых в качестве центральных функций используются функции Гаусса. При этом можно показать, что проблема интерполяции разрешима и без циклических полиномов.

В общем случае для решения проблемы интерполяции необходимо определить коэффициенты c_i и d_i, т.е. N+m неизвестных. Условия интерполяции

f(X_j) = y_j, j = 1, 2, … , N

образуют первые N уравнений для определения параметров c_i и d_i

N m

c_i h_i (|| X_j - X_i ||) + d_i p_i (X_j) = y_j, j = 1, 2, … , N (15)

i=1 i=1

Остальные m условий могут быть выбраны свободно. Для упрощения вычислений однако 2-е слагаемое в (15) обычно полагается равным нулю.

На основе теории аппроксимации можно утверждать, что система уравнений (15) имеет решение, если функции h_i положительно определены и имеют порядок k в Rⁿ.

Для более простой системы из N уравнений (9) центральные функции h_i положительно определены, а, следовательно, система уравнений разрешима. Приведем примеры классов допустимых центральных функций:

h (z) = exp (- (z/)² )

h (z) = 1 / (c² + z²) , > 0 (16)

______

h (z) = z² + c²

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

Однако этим сетям присущ ряд недостатков:

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

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

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

Эти требования фиксированного размера сети приводит к первому расширению RBF-сетей - так называемым обобщенным RBF-сетям (generalized radial basis function networks). С математической точки зрения мы сталкивается при этом не с задачей интерполяции, а с задачей аппроксимации. При этом не требуется, чтобы искомая функция f проходила через все опорные точки. Необходимо лишь минимизировать суммарную ошибку по всем опорным точкам при выполнении некоторых условий гладкости аппроксимирующей функции.

5.4 Аппроксимация с помощью центральных функций

При аппроксимации при помощи центральных функций независимо от числа N образцов обучающей последовательности выбирается число k центров или K скрытых нейронов. Для этого в частности можно использовать соответствующее подмножество образов обучающей последовательности или другие опорные точки, предварительно определенные тем или иным способом. В силу этого эти центры теперь обозначаются не через X_j, а иначе. Часто используются векторы t_j (от teacher). В [1] обозначаются через W_j. Объяснение для этого в том, что координаты опорных точек почти во всех реализациях запоминаются в виде весов W_ij нейросети. В этом случае в частности лучше проявляется сходство с другими алгоритмами обучения.

Рис. 4. Структура обобщенной RBF-сети, содержащей один скрытый слой с фиксированным числом K нейронов.

Структура обобщенной RBF-сети, содержащей один скрытый слой с фиксированным числом K нейронов представлена на рис. 4. Данные опорных точек запоминаются обычно в виде весов w_ij скрытых нейронов.

Для K различных центров аппроксимирующая функция f принимает следующий вид:

K

f (X) = c_j h_j( || X - W_j || ) (17)

j=1

Для определения K коэффициентов c₁, c₂, … , c_K имеется N уравнений. При этом можно использовать условия интерполяции

K

c_j h_j( || X_i - W_j || ) = y_i (18)

j=1

для всех образов обучающей последовательности i = 1, 2, … , N.

Обозначим

h₁ ( || X₁ - W₁ || ) … h_K ( || X₁ - W_K || )

H = … | (19)

h₁ ( || X_N - W₁ || ) … h_K ( || X_N - W_K || ) ,

тогда проблему интерполяции можно представить так:

H*C = Y (20)

В случае N > K эта система уравнений переопределена и не имеет точного решения (интерполяция). Путем аппроксимации можно минимизировать сумму квадратов ошибок по всем образам обучающей последовательности. Это приводит к решению [ ]:

C = H⁺ * Y, (21)

где H⁺ - псевдоинверсная матрица Мура - Пенроза (Moore - Penrose Pseudoinverse) относительно матрицы H:

H⁺ = ( H^T H )^-1 H^T (22)

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

5.5 Вариационное исчисление для решения проблемы аппроксимации с помощью RBF-сетей

Другой способ решения проблемы аппроксимации - на основе вариационного исчисления. Для этого формируется функционал

N

H (f) = ( y_i - f (X_i) + || P f ||² (23)

i=1

Задача сводится к определению функции f, минимизирующей функционал H(f). Сумма в этом функционале включает условия интерполяции для всех образов X_i обучающей последовательности (i = 1, 2, … , N). Чем меньше эта сумма, тем лучше аппроксимирует функция f образы обучающей последовательности. Дифференциальный оператор P в (23) выполняет функции стабилизатора для вариационной задачи. Ее решение приведено в [1].

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

Заданы N образов обучающей последовательности X_i Rⁿ и им соответствующие значения функциями y_i R. Заданы также K центров W_j Rⁿ базисных функций h_j и порядок функции f, которая представляется в виде

K

f (X) = c_j h_j( || X - W_j || ) (24)

j=1

Неизвестные коэффициенты c_j определяются при этом следующим образом:

~

C = ( H^T H + H)^-1 H^T Y (25)

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

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

5.6 Расширение на случай многих функций

Метод радиальных базисных функций (radial basis functions) очень просто можно распространить и на случай многих функций (многомерный случай):

f: Rⁿ R^m (26)

Это равносильно (эквивалентно) аппроксимации множества из m отдельных функций R: Rⁿ R в предположении, что используются одни и те же опорные точки W_j для всех функций и одни и те же образы X_j обучающей последовательности:

K

y_k = f_k (X) = c_jk h_j ( || X - W_j || ) (27)

j=1

5.7 Расширение линейной частью

Как было отмечено выше, при использовании определенных центральных функций необходимым становится введение полинома степени K в аппроксимирующую функцию f. Лишь такое введение обеспечивает достижение оптимальных результатов. Однако для функций Гаусса, как отмечено также выше, это не является необходимым. В случае K=1 (полином первой степени) это расширение RBF-сети особо элегантно. Функция f представляется при этом в виде:

K n

f (X) = c_j h_j ( || X - W_j || ) + d_k x_k + Q (28)

j=1 k=1

где Q - порог.

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

5.8 Сети гипер-базисных функций (Hyper-Basisfunktionen-Netze = HBF-Netze)

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

h (X) = [1 + exp ( || X - X_i || / 2_i² - _i )]^-1 (29)

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

HBF-сети представляют собой другие расширения обобщенных RBF-сетей. В них путем взвешивания аргумента || X - W_j || центральной функции h обеспечивается индивидуальная обработка каждого центра, которая может быть реализована различными способами:

путем взвешивания расстояния || X - W_j || некоторым коэффициентом,

путем изменения центральной функции с помощью второго параметра P,

путем взвешивания отдельных составляющих (x_i - w_ij), i = 1, 2, … , n, расстояния и т.п.

На рис. 5 приведен общий вид HBF-сетей (HBF-сеть с одним линейным полиномом).

По соображениям наглядности на рис. 5 показаны лишь соединения для одного выходного нейрона. Линейные составляющие d_kx_k реализуются непосредственно в виде прямых соединений от входов к выходному слою. Порог реализуется с помощью "on"-нейрона с выходом 1. Другие решения - использование входа BIAS в выходном нейроне k.

Рис. 5. HBF-сеть с одним линейным полиномом.

5.9 Итеративное дополнительное обучение RBF- и HBF-сетей

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

m N

E = 1/2 * (y_ik - o_k (X_i))², (30)

k=1 i=1

где m - число выходных нейронов (или число аппроксимируемых функций), o_k (X_i) - действительный выход k-го выходного нейрона для i-го образа X_i обучающей последовательности, y_ik - требуемый выход k-го выходного нейрона для i-го образа X_i обучающей последовательности. Вид ошибки (30) типичен для алгоритмов обучения нейросетей (например, Backpropagation). Коэффициент 1/2 вводится с тем, чтобы "погасить" двойку, возникающую затем при дифференцировании суммарной ошибки (30). Вывод соотношений идентичен Backpropagation-алгоритму. Для определения изменений весов в процессе обучения сети необходимы все частные производные функции ошибки E (30) по всем свободным параметрам W_j, c_jk, d_ik, _k и P_j.

5.10 Выбор центров и радиусов в RBF-сетях

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

Для их снижения часто в качестве центров RBF- и HBF-сетей используется подмножество образов обучающей последовательности. При этом иногда предусматривается незначительная модификация входных образов и весов соединений ("шум"). Подобный "шум" необходим, например, в тех случаях, когда число K скрытых нейронов превышает число N образов обучающей последовательности. До сих пор мы обычно преполагали, что K N. Принципиально, однако, способ применим и в случае K > N.

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

Рассмотрим один из примеров простых алгоритмов кластеризации. На сонове следующей стратегии (ab-hoc-Methode) выявления кластеров.

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

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

5.10.1 Итеративный алгоритм кластеризации

Рассмотрим пример итеративных алгоритмов кластеризации. Вначале выбирается K различных опорных векторов u_i, i = 1, 2, … , K. Затем векторы X_i обучающей последовательности последовательно предъявляются сети. После каждого такого предъявления опорные векторы u_i модернизируются в направлении X_i:

Инициализация

Выбери K опорных векторов u_i

i:=1

Правило итерации

REPEAT

:=1

i

SELECT X_j T

|| u_i - X_j || || u_k - X_j || для i=1, 2, … , K, 1 k i K

u_i (t+1) : = u_i (t) + ( || u_i - X_j || )

i : = i + 1

UNTIL 1 j K : u_j (t+1) = u_j (t)

Коэффициент коррекции уменьшается с увеличением номера итерации.

Алгоритм сходится тогда, когда прототипы u_i становятся сталильными. При применении алгоритмов кластеризации следует в формуле (4) учесть числа m_i векторов в тех или иных кластерах. Модифицированные выходы рассчитываются при этом следующим образом:

K

m_i h_i c_ij

i=1

y_j = (31)

K

m_i c_ij

i=1

5.10.2 Выбор параметра

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

В практических приложениях обычно применяется метод k ближайших соседей (k-nearest-neighbor-Methode) для определения k ближайших соседей вокруг точки u_i. После этого определяется средний вектор u_i`. Расстояние между u<sub>i</sub> и u<sub>i</sub>` служит затем мерой для выбора значения _i. Для многих приложений рабочим правилом является выбор = 1 (default-установка).

Другой подход к определению оптимального множества центральных векторов для RBF-сетей может быть основан на использовании самоорганизующихся карт. Для этого в большинстве случаев образы обучающей последовательности предварительно нормируются по длине равной 1. После этого выбираются случайно K из N образов обучающей последовательности в качестве начальных (стартовых) значений центральных векторов и определяется скалярное произведение <X_i, W_j> между вектором X_i обучающей последовательности и каждым из K центральных векторов W_j, j = 1, 2, … , K. Это скалярное произведение является мерой подобия (сходства) обоих векторов, отнормированных по длине, равной 1. При этом тот центральный вектор W_j, расстояние от которого до текущего вектора обучающей последовательности минмальное (или: для которого указанное скалярное произведение максимально), объявляется "победителем". Он сдвигается затем на небольшую величину в направлении текущего вектора обучающей последовательности:

W_j (t+1) = W_j (t) + ( X_i - W_j (t)) (32)

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

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

5.10.3 Расчет выходной весовой матрицы C

После определения опорных точек u_i и параметров рассеяния _i необходимо рассчитать выходную весовую матрицу C.

Обучающая последовательность T содержит векторы v_i = (X_i, y_i), где X_i - i-я опорная точка, а y_i - значение функции в ней. Часть этих векторов v_i уже была использована для определения опорных точек u_i.

Для определения матрицы C используется алгоритм типа Backpropagation. Для этого вектор X_i обучающей последовательности подается на вход сети, затем рассчитываются активации нейронов скрытого слоя h(X_i). Выход нейронов скрытого слоя представим в виде вектора h. Вектор h "пропускается" затем через весовую матрицу

C = (c_ij), i = 1, 2, … , K, j = 1, 2, … , m,

где c_ij - вес связи нейрона i скрытого слоя и нейрона j выходного слоя. В результате получается действительный выходной вектор f, который сравнивается с требуемым выходным вектором Y. На основе сравенения этих векторов и осуществляется коррекция весовой матрицы C (подобно алгоритму Backpropagation).

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

Глава 6. Нейронные сети и генетические алгоритмы

Генетические алгоритмы были предложены Холландом (Holland, 1975) и основаны на принципах эволюции. Сущность их состоит в следующем.

Имеется некоторая популяция индивидуумов, каждый из которых может быть представлен двоичной последовательностью или строкой символов какого-либо иного алфавита. Для каждого индивидуума (фенотипа) можно определить значение некоторой функции эффективности (Fitness-Function). Задача состоит в максимизации этой функции эффективности. Цель генетических алгоритмов состоит в том, чтобы в процессе ряда операций получать каждый раз лучшие индивидуумы (индивидуумы с большими значениями функции эффективности). Формирование новых индивидуумов осуществляется в результате селекции лучших индивидуумов (индивидуумов с лучшими значениями функции эффективности) для образования потомства на основе случайного процесса отбора. При этом каждый раз выбираются два индивидуума, производится скрещивание обоих бинарных векторов на основе одного из операторов скрещивания, в результате чего возникают два новых индивидуума (ребенка). Эти новые индивиды могут быть подвергнуты затем с очень малой вероятностью операции мутации, состоящей в инвертировании одного случайно выбранного бита (разряда) двоичного слова.

Ниже мы ограничимся лишь изложением основ применений генетических алгоритмов в нейросетях.

6.1 Эволюция как способ оптимизации

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

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

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

1). величина,

2). форма,

3). структура,

4). свойства обмена веществ,

5). поведение и т.д.

Мутации могут и не влиять непосредственно на организм. Они могут вначале лишь увеличивать вариативность генетического материала некоторого вида.

Возможные формы селективных сил:

1). климат,

2). доступ к пище,

3). способность убежать от естественных врагов,

4). способность защититься от естественных врагов,

5). шансы на успех в качестве партнера для спаривания.

Чтобы сделать понятными принципы работы генетических алгоритмов, поясним также, как устроены механизмы генетического наследования в природе. В каждой клетке любого животного содержится вся генетическая информация этой особи. Эта информация записана в виде набора очень длинных молекул ДНК (ДезоксирибоНуклеиновая Кислота). Каждая молекула ДНК - это цепочка, состоящая из молекул нуклеотидов четырех типов, обозначаемых А, T, C и G. Собственно, информацию несет порядок следования нуклеотидов в ДНК. Таким образом, генетический код индивидуума - это просто очень длинная строка символов, где используются всего 4 буквы. В животной клетке каждая молекула ДНК окружена оболочкой - такое образование называется хромосомой.

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

При размножении животных происходит слияние двух родительских клеток и их ДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия - рекомбинация (cross-over, скрещивание). При рекомбинации ДНК предков делятся на две части, а затем обмениваются своими половинками.

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

6.2 Генетические алгоритмы

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

Вот как моделируется генетическое наследование:

Хромосома	Вектор (последовательность) из нулей и единиц. Каждая позиция (бит) называется геном.
Индивидуум = генетический код	Набор хромосом = вариант решения задачи.
Рекомбинация	Операция, при которой две хромосомы обмениваются своими частями.
Мутация	Случайное изменение одной или нескольких позиций в хромосоме.

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

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

Отбор в генетическом алгоритме тесно связан с принципами естественного отбора в природе следующим образом:

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

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

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

кодирование прикладной задачи,

множество операторов мутации,

критерий селекции.

Сущность их очень проста. Обычно генетический алгоритм стартует с некоторой популяцией индивидов. Каждый из них оценивается по некоторому критерию селекции. На основе значения этого критерия для отдельного индивида выносится решение о величине вероятности наследования его свойств в следующем поколении. Обычно при таком наследовании свойств применяются так называемые операторы мутации и/или рекомбинации (crossing-over). Следующее поколение индивидов также оценивается и описанный процесс стартует снова. Структура алгоритма представлена на рис. 1.

Рис. 1. Структура генетического алгоритма.

Кодирование

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

Генетические алгоритмы оказались очень эффективными при решении задач многомерной оптимизации. В этих случаях под индивидом понимается ничто иное как значение оптимизируемой функции в некоторой точке области определения. Этот индивид представляется (кодируется) бинарными кодами:

I_i = (x, y), где x, y [0,1]^k

Операторы.

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

точечная мутация и

рекомбинация (crossing-over).

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

Пример:

0100011101011 0100111101011

Здесь инвертированный разряд выделен большим размером.

При рекомбинации (crossing-over) в текущей популяции выбираются две двоичные последовательности и в них производится обмен двух соответствующих частей. Из двух возникающих при этом индивидов выбирается один индивид для следующего поколения (рис. 2).

Рис. 2. Операторы рекомбинации (первый вариант).

На рис. 3 представлен набор наиболее популярных операторов скрещивания для рекомбинации (crossing-over).

Рис. 3. Операторы рекомбинации (второй вариант).

Критерии селекции

Выбор индивида осуществляется на основе подходящего критерия селекции, измеряющего степень эффективности (Fitness, Performanz) некоторого индивида по сравнению со своими "конкурентами". В нашем примере оптимизации функций в качестве критерия селекции используется непосредственно значение функции f(x). Степень эффективности (Fitness) некоторого индивида x выражается значением функции f в этой точке x. На рис. 4 а-г представлен принцип функционирования генетического алгоритма.

Рис. 4. Принцип функционирования генетического алгоритма

Преимущества генетических алгоритмов в сравнении с другими методами оптимизации (например, градиентными методами):

Глобальная оптимизация. Вследствие случайной составляющей генетический алгоритм может исследовать все функциональное пространство. В результате этого в частности становится возможным выход из локальных минимумов. Следует однако отметить, что во многих случаях обычные методы оптимизации (hill-climbing-Methoden) используются в окрестности предполагаемого глобального оптимума, ибо последние обычно быстрее и надежнее отыскивают абсолютный оптимум.

Минимальное знание и функции цели. Генетические алгоритмы ограничиваются измерением степени эффективности (Fitness) индивида. Они используют лишь значение функции f в точке x. При этом информация о первой или второй производной для расчета градиента не используется.

Параллельность генетических алгоритмов. Генетические алгоритмы тривиально могут быть реализованы на нескольких процессорах.

6.3 Нейро-генетические способы

Комбинация генетических алгоритмов и нейросетей распространяется на следующие области:

оптимизация весовой матрицы нейросети,

оптимизация топологии нейросети.

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

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

Генетические алгоритмы для оптимизации топологии нейросети

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

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

Резюме

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

Глава 7. Система моделирования нейронных сетей Trajan 2.0

Пакет моделирования нейронных сетей "Trajan 2.0" фирмы Trajan-Software (США) - один из известных нейросетевых коммерческих продуктов. Он рассчитан на широкое использование в сфере классификации образов, прогнозирования и кластеризации.

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

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

Многослойный персептрон. Trajan позволяет использовать Алгоритм обратного распространения, включая такие параметры как скорость обучения, изменяющаяся во времени, перемещение образов, дополнительный шум, выбор функции активации, выбор условий остановки, автоматическая перекрестная проверка. Также эта система поддерживает алгоритмы Быстрого распространения, Дельта-алгоритм, а также два из наиболее современных алгоритмов обучения: Левенберга-Маркварта и Градиентного спуска. Эти алгоритмы не только быстрые, но также независимы от параметров.

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

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

Trajan позволяет выбрать специальные функции активации и функции ошибки. Также можно объединять сети или удалять некоторые слои.

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

Для запуска программы необходимо запустить файл Trajan.exe. Необходимо сказать, что оригинальная версия Trajan была русифицирована: интерфейс программы (команды меню, названия диалоговых окон и полей, а так же основные термины) приведены на русском языке. В данном проекте приводятся английские и русские эквиваленты. На экране, в зависимости от версии программы Trajan (русифицированная или оригинальная), появится главное окно программы (рис. 1). Доступной является справочная система Trajan на английском языке.

Рис. 1. Главное окно программы.

7.1 Создание сети и обучающей последовательности

7.1.1 Создание сети

Для начала необходимо создать саму нейронную сеть, т.е. ее структуру.

Создать новую ИНС можно в окне Создание ИНС (Network Creation) (см Рис. 2), которое вызывается с помощью команды меню Файл/Создать/Сеть (File/New/Network).

В поле Тип (Type) можно задать тип нейронной сети. Версия Shareware предлагает создание и использование только двух типов нейронных сетей:

многослойный персептрон (Multilayer Perceptron);

сети Кохонена (Kohonen).

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

Затем надо указать число слоев в создаваемой сети и количество элементов (нейронов) в каждом слое.

Рис. 2. Окно создания ИНС.

После нажатия кнопки Создать (Create) структура созданной сети отобразится в главном окне Главное (Main), а тип сети будет указан в Строке статуса (Status line), которая находится прямо под панелью инструментов (рис. 3).

Рис. 3. Структура созданной сети.

7.1.2 Количество и размерность слоев в сети

Программа Trajan может поддерживать до 128 слоев, а число элементов ограниченно только оперативной памятью компьютера (более 16 млн.). Однако незарегистрированная версия Unregistered Shareware ограничена всего двадцатью элементами. В большинстве случаев такого количества слоев и элементов бывает достаточно.

В программе Trajan первый слой всегда Входной слой (Input layer), он выполняет функцию представления входных данных в сеть. Входной слой не выполняет вычислений. Последний слой всегда Выходной слой (Output layer), и выходное значение элементов этого слоя считается конечным выходным значением для всей сети. Все остальные слои - это так называемые Скрытые слои (Hidden layers). Каждый элемент в каждом слое соединен с каждым элементом следующего слоя (кроме, конечно, Выходного слоя, где следующего слоя нет). Все типы сетей, поддерживаемые программой Trajan (версией Shareware), являются сетями прямого распространения сигналов, т.е. отсутствуют рекуррентные и обратные связи.

Можно указать количество элементов в каждом слое, используя матрицу диалогового окна Создание сети (Network Creation). Она выглядит как очень маленькая электронная таблица. Можно указать количество элементов в слое, изменив значение ячейки первой строки (units); слой с нулевым количеством элементов игнорируется. Нажмите мышкой (далее кликните) на первой ячейке матрицы, она отобразится белым текстом на черном фоне. Это означает, что выбрана данная ячейка.

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

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

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

В матрице есть еще и вторая строка ширина (width). Эта строка используется только в сети типа Сеть Кохонена (Kohonen network). Выходной слой сети Кохонена лежит в двумерном пространстве (имеет два измерения), программа определяет высоту слоя как отношение общего числа элементов выходного слоя к ширине слоя.

Для любого слоя любого типа сети можно задавать параметр width. Однако принципиальное значение этот параметр имеет только для сети Кохонена. В остальных сетях это только изменит отображение сети на экране.

Как только вы введете значения для всех слоев, просто нажмите кнопку Создать (Create). Это приведет к формированию сети. Она отобразится графически в главном окне программы.

7.1.3 Создание обучающей последовательности

Одно из ключевых свойств ИНС - способность обучаться на примерах для решения различных задач. Вместо того чтобы устанавливать веса в сети вручную (что вообще-то предусмотрено программой Trajan), можно задать некоторое число образцов и использовать обучающий алгоритм для подбора весов. Таким образом, сеть сможет научиться распознавать (классифицировать) образцы. В программе Trajan все обучающие образцы хранятся вместе и образуют обучающую последовательность (Pattern Set).

Вызовите диалоговое окно Создание обучающей последовательности (Pattern Set Creation) (с помощью команды меню File/New/Pattern (Файл/Новый/Образец)).

Рис.4. Диалоговое окно “Создание обучающей последовательности”

В диалоговом окне (Рис. 4) введите количество Входов (Inputs) и Выходов (Outputs) в обучающей последовательности. Количество входов должно соответствовать количеству нейронов в первом (Входном) слое сети, а количество выходов - количеству нейронов в последнем (Выходном) слое сети. Если Вы последовательно создаете сначала структуру сети, а затем обучающую последовательность, то эти значения устанавливаются по умолчанию.

Нажмите кнопку Создать (Create).

После этого программа автоматически вызывает диалоговое окно Редактор образцов (Pattern Editor).

Основным в Редакторе образцов (Pattern Editor) является Матрица образцов (Pattern Matrix), она содержит обучающую последовательность. Каждый образец представлен строкой в матрице образцов. В начале (сразу после создания) в матрице будет всего лишь одна строка, у которой все атрибуты (входы i#01...i#02 и выход o#01) установлены в нуль ( см. Рис. 5). Выходы отделены от входов жирной вертикальной чертой. Можно создавать новые образцы или редактировать уже существующие.

Рис. 5.Диалоговое окно редактора образцов

7.1.4 Редактирование набора образцов

Редактор образцов (Pattern Editor) имеет следующие возможности:

Матрица образцов (Pattern Matrix), которая позволяет изменять любой существующий образец и атрибут, добавлять и удалять образцы и атрибуты и т.д.;

Набор полей для подстройки баланса Входных (Input) и Выходных (Output) атрибутов, и обучающих и проверяющих образцов;

Возможность автоматически перемешивать порядок образцов в наборе.

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

Изменение существующих значений образца

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

Для выбора ячейки:

Кликните мышкой на ячейке;

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

Программа автоматически будет передвигать видимую область матрицы.

...