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

а) никакие сведения о подлежащих классификации данных в машину заранее не вводятся;

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

в) машина автоматически обрабатывает полученную информацию, после чего

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

Машины, работающие по такой схеме, называются узнающими машинами.

2.7 Подготовка данных для обучения

При подготовке данных для обучения нейронной сети необходимо обращать внимание на следующие существенные моменты. Количество наблюдений в наборе данных. Следует учитывать тот фактор, что чем больше размерность данных, тем больше времени потребуется для обучения сети. Следует определить наличие выбросов и оценить необходимость их присутствия в выборке. Обучающая выборка должна быть представительной (репрезентативной). Обучающая выборка не должна содержать противоречий, так как нейронная сеть однозначно сопоставляет выходные значения входным. Нейронная сеть работает только с числовыми входными данными, поэтому важным этапом при подготовке данных является преобразование и кодирование данных. При использовании на вход нейронной сети следует подавать значения из того диапазона, на котором она обучалась. Например, если при обучении нейронной сети на один из ее входов подавались значения от 0 до 10, то при ее применении на вход следует подавать значения из этого же диапазона или близлежащие. Существует понятие нормализации данных. Целью нормализации значений является преобразование данных к виду, который наиболее подходит для обработки, т.е. данные, поступающие на вход, должны иметь числовой тип, а их значения должны быть распределены в определенном диапазоне. Нормализатор может приводить дискретные данные к набору уникальных индексов либо преобразовывать значения, лежащие в произвольном диапазоне, в конкретный диапазон, например, [0..1]. Нормализация выполняется путем деления каждой компоненты входного вектора на длину вектора, что превращает входной вектор в единичный..

Емкость ИНС - число классов, предъявляемых на входы ИНС для распознавания. Для разделения множества входных классов, например, по двум классам достаточно всего одного выхода. При этом каждый логический уровень - "1" и "0" - будет обозначать отдельный класс. На двух выходах можно закодировать уже 4 класса и так далее. Для повышения достоверности классификации желательно ввести избыточность путем выделения каждому классу одного нейрона в выходном слое или, что еще лучше, нескольких, каждый из которых обучается определять принадлежность образа к классу со своей степенью достоверности, например: высокой, средней и низкой. Такие ИНС позволяют проводить классификацию входных данных, объединенных в нечеткие (размытые или пересекающиеся) множества. Это свойство приближает подобные ИНС к условиям реальной жизни.

2.7.1 Максимизация энтропии как цель предобработки

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

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

2.7.2 Нормировка данных

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

Индивидуальная нормировка данных.

Приведение к единому масштабу обеспечивается нормировкой каждой переменной на диапазон разброса ее значений. В простейшем варианте это - линейное преобразование:



(2.2)

в единичный отрезок [0;1]. Обобщение для отображения данных в интервал [-1;1], рекомендуемого для входных данных тривиально.

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

(2.3)

Где (2.4)

(2.5)

Единичный масштаб, т.е. типичные значения все переменных будут сравнимы.

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

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

(2.6)

нормирует основную массу данных одновременно гарантируя что значение х расположено в диапазоне от "1" до "0".

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

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

2.8 Алгоритмические построения

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

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

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

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

2.9 Обучение искусственных нейронных сетей

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

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

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

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

Рис. 2.4. Метод обратного распространения ошибки для многослойной полносвязанной нейронной сети

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



Рис. 2.5. Метод градиентного спуска при минимизации ошибки сети

2.9.1 Обучение с учителем

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

2.9.2 Обучение без учителя

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

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

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

(2.7)

где yi(n-1) - выходное значение нейрона i слоя (n-1), yj(n) - выходное значение нейрона j слоя n; wij(t) и wij(t-1) - весовой коэффициент синапса, соединяющего эти нейроны, на итерациях t и t-1 соответственно; a - коэффициент скорости обучения. Здесь и далее, для общности, под n подразумевается произвольный слой сети. При обучении по данному методу усиливаются связи между возбужденными нейронами.

Существует также и дифференциальный метод обучения Хебба.

(2.8)

Здесь yi(n-1)(t) и yi(n-1)(t-1) - выходное значение нейрона i слоя n-1 соответственно на итерациях t и t-1; yj(n)(t) и yj(n)(t-1) - то же самое для нейрона j слоя n. Как видно из формулы (2), сильнее всего обучаются синапсы, соединяющие те нейроны, выходы которых наиболее динамично изменились в сторону увеличения.

Полный алгоритм обучения с применением вышеприведенных формул будет выглядеть так:

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

2. На входы сети подается входной образ, и сигналы возбуждения распространяются по всем слоям согласно принципам классических прямопоточных (feedforward) сетей[1], то есть для каждого нейрона рассчитывается взвешенная сумма его входов, к которой затем применяется активационная (передаточная) функция нейрона, в результате чего получается его выходное значение yi(n), i=0...Mi-1, где Mi - число нейронов в слое i; n=0...N-1, а N - число слоев в сети.

3. На основании полученных выходных значений нейронов по формуле (2.7) или (2.8) производится изменение весовых коэффициентов.

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

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

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

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

(2.9)

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

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

Другой вариант - расчет расстояния между этими векторами в p-мерном пространстве, где p - размер векторов.

(2.10)

где j - индекс нейрона в слое n, i - индекс суммирования по нейронам слоя (n-1), wij - вес синапса, соединяющего нейроны; выходы нейронов слоя (n-1) являются входными значениями для слоя n. Корень в формуле (2.10) брать не обязательно, так как важна лишь относительная оценка различных Dj.

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

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

(2.11)

где xi - i-ая компонента вектора входного образа или вектора весовых коэффициентов, а n - его размерность. Это позволяет сократить длительность процесса обучения.

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

= (t) * (2.12)

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

Весовые коэффициенты устанавливаются на шаге инициализации равными величине:

(2.13)

где n - размерность вектора весов для нейронов инициализируемого слоя.

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

2.9.3 Процесс обучения нейронных сетей

Процесс обучения Искусственной Нейронной Сети (ИНС) новому классу задач включает следующие стадии:

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

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

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

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

5. Обучение повторяется до тех пор, пока суммарная ошибка во всем множестве входных значений не достигнет приемлемого уровня, либо ИНС не придет в стационарное состояние. Рассмотренный метод обучения нейроподобной сети носит название "обратное распространение ошибки" (error backpropagation) и относится к числу классических алгоритмов нейроматематики.

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

2.9.4 Алгоритм секущих плоскостей

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

Рис. 2.6. Метод секущихся плоскостей

А. Обучение

(формирование разделяющей поверхности):

Проведение секущих плоскостей;

Исключение лишних плоскостей;

Исключение лишних кусков плоскостей.

Б. Распознавание новых объектов.

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

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

Алгоритмы, основанные на методе потенциалов.

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

) (2.14)

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

Рис. 2.7 Метод потенциалов



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

Простейший алгоритм классификации, построенный на методе потенциалов, можно осуществить в два этапа:

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

Кластеризация (в процессе кластеризации производится идентификация и выдается информация, к какому кластеру принадлежит закодированная матрица).

2.10 Обучение сети Кохонена

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

Рис. 2.8. Топология нейронной сети Кохонена

Она представляет собой двухслойную сеть (рис.2.8). Каждый нейрон первого (распределительного) слоя соединен со всеми нейронами второго (выходного) слоя, которые расположены в виде двумерной решетки.

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

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

(2.15)

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

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

Рис.2.9. Функция Гаусса



(2.16)

где и - номер нейрона в двумерной решетке второго слоя сети, для которого вычисляем значение h;

c - номер нейрона-победителя в двумерной решетке второго слоя сети;

t - параметр времени;

Радиус окрестности h должен уменьшаться с увеличением параметра времени:

(2.17)

2.11 Клеточный автомат в нейронных сетях

2.11.1 Устройство клеточного автомата

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

Различные клеточные автоматы могуть демонстрировать весьма разнообразное поведение, которое может быть адаптировано для целей обработки информации за счет выбора (а) закона изменения состояния элемента и (б) конкретного определения понятия "ближайшие соседи". Внимательный читатель без труда заметит, что, например, нейронная сеть Хопфилда вполне может рассматриваться, как клеточный автомат, элементами которрого являются формальные нейроны. В качестве закона изменения состояния нейро-автомата используется пороговое преобразование взвешенной суммы входов нейронов, а ближайшими соседями каждого элемента являются все прочие элементы автомата. В мире клеточных автоматов имеется класиификация (S. Wolfram, 1983), согласно которой все автоматы делятся на четыре класса, в зависимости от типа динамики изменяющихся состояний. Автоматы первого класса по истечении конечного времени достигают однородного состояния, в котором значения всех элементов одинаковы и не меняются со временем. Ко второму классу автоматов относятся системы, приводящие к локализованным структурам стационарных или периодических во времени состояний элементов. Третий класс составляют "блуждающие" автоматы, которые с течением времени посещают произвольным (непериодическим) образом все возможные состояния элементов, не задерживаясь ни в одном из них. И, наконец, четвертый класс составляют "странные" автоматы, характер динамики которых зависит от особенностей начального состояния элементов. Некоторые начальные состояния приводят к однородному вырождению автомата, другие - к возникновению циклической последовательности состояний, третьи - к непрерывно меняющимся (как "по системе", так и без видимой системы) картинам активности элементов.

2.11.2 Клеточная нейронная сеть

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

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

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

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

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



3. Классификация данных

3.1 Постановка задачи и сложности, связанные с ее реализацией

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

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

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

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

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

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

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

Рис. 3.1 Искажения классов.

3.1.1 Выбор топологии сети

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

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

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

На первый взгляд это может показаться странным. Как сеть сможет чему-то научиться, не имея выходных значений? Ответ заключается в том, что сеть Кохонена учится понимать саму структуру данных.

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

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

Сеть Кохонена имеет всего два слоя: входной и выходной, составленный из радиальных элементов (выходной слой называют также слоем топологической карты). Элементы топологической карты располагаются в некотором пространстве - как правило двумерном (в пакете ST Neural Networks реализованы также одномерные сети Кохонена).

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

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

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

Выбрать выигравший нейрон (то есть тот, который расположен ближе всего к входному примеру);

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

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

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

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

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

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

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

Идея сети Кохонена возникла по аналогии с некоторыми известными свойствами человеческого мозга.

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

3.2 Алгоритм кластеризации данных

Обучение искусственной нейронной сети (ИНС) Кохонена относится к типу самообучающегося соревнования. При обучении методом соревнований нейроны соревнуются между собой за право активации. Это явление, известное как правило "победитель забирает все" (Winner Takes All - WTA), имеет нейрофизиологическую аналогию [23]. Подстройка весов связей в алгоритме WTA осуществляется не для всех нейронов слоя, а только для "нейрона-победителя", значение выхода которого в слое нейронов оказывается максимальным. Главная проблема алгоритма самоорганизации WTA ? наличие "мертвых" нейронов, которые ни разу не побеждают в конкурентной борьбе. Для разрешения этой проблемы применяются модифицированные методы и алгоритмы самообучения, дающие обычно лучшие результаты, чем алгоритм WTA.

Алгоритм "победитель справедливо получает все" (Conscience Winner Takes All ? CWTA) является улучшенной модификацией алгоритма WTA. Он позволяет учитывать количество побед и поощрять нейроны с наименьшей активностью для выравнивания их шансов на победу. Этот алгоритм считается одним из лучших и быстрых в классе алгоритмов самоорганизации. В алгоритме "победитель получает больше" (Winner Takes Most ? WTМ) кроме нейрона-победителя обучаются также нейроны из его ближайшего окружения. При этом чем дальше какой-либо нейрон находится от победителя, тем меньше изменяются его веса. Этот метод исключает "мертвые" нейроны и улучшает распределение плотности весов. Существуют и другие, более изощренные алгоритмы обучения ИНС Кохонена.

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

Целью диссертации является разработка нового детерминированного алгоритма обучения ИНС Кохонена с использованием непрерывного клеточного автомата, позволяющего устранить большинство перечисленных недостатков, и его практическая реализация в электронных таблицах.

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

Рис. 3.2. Топология самоорганизующейся карты слоя Кохонена для окружения фон Неймана

Состояние ячейки КА задается многомерным вектором, компоненты которого суть координаты соответствующего нейрона в пространстве обучающих образов. В соответствии с принципом "ближайшего соседа" ячейки КА (нейроны) являются центрами окрестностей Вороного, на которые, подобно многомерной мозаике, делится все пространство учебных образов [73].

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

В итерациях эпохи любой внутренний k-ый нейрон слоя (рис. 3.2) изменяет свой многомерный вектор состояния в двух случаях:

1) нейрон стал победителем;

2) нейрон является ближайшим соседом другого победившего нейрона.

Будем считать, что приращение компонент вектора состояния k-го нейрона не зависит от причины (победил он сам или победил его сосед) этого приращения. Тогда среднее суммарное приращение i-ой компоненты вектора состояния k-го нейрона за одну эпоху в окружении фон Неймана будет равно

(3.1)

где з - скорость обучения; k -номер нейрона-победителя; m={k-1,k,k+1,k-L,k+L} - номера нейронов окружения k-го нейрона; L - ширина прямоугольной самоорганизующейся карты; nm - число учебных образов, попавших в окрестность Вороного m-го нейрона; xmi(j) - i-ая координата j-го учебного образа из окрестности Вороного m-го нейрона; wki - i-ая координата k-го нейрона.

Обозначая n=, выражение (1) можно переписать в виде

(3.2)

где - i-ая координата центра тяжести окрестности Вороного m-ого нейрона.

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

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

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

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

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

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



Рис.3.3. Состояния одномерного клеточного автомата:

1) начальное; 2) после 1-ой эпохи обучения; 3) после 2-х эпох обучения; 4) после 3-х эпох обучения.

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

После второй эпохи обучения k-ый нейрон останется на месте, а нейроны k-2, k-1 и k+1, k+2 сместятся к центру тяжести учебных образов, соответственно расположенных левее и правее k-го нейрона.

После 3-ей эпохи обучения расположение нейронов станет следующим: (k-3)-ий нейрон - в центре тяжести учебных образов, расположенных левее (k-2)-го нейрона; (k-2)-ой нейрон - в центре тяжести окрестностей Вороного (k-2)-го и (k-1)-го нейронов; (k-1)-ой нейрон - в центре тяжести окрестностей Вороного (k-2)-го, (k-1)-го и k-го нейронов; k-ый нейрон - в центре тяжести окрестностей Вороного (k-1)-го, k-го и (k+1)-го нейронов; (k+1)-ый нейрон - в центре тяжести окрестностей Вороного k-го, (k+1)-го и (k+2)-го нейронов; (k+2)-ой нейрон - в центре тяжести окрестностей Вороного (k+1)-го и (k+2)-го нейронов; (k+3)-ий нейрон - в центре тяжести учебных образов, расположенных правее (k+2)-го нейрона.