Использование искусственных нейронных сетей и вейвлет-анализа для повышения эффективности в задачах распознавания и классификации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Стадник, Алексей Викторович

• Стадник, Алексей Викторович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Стадник, Алексей Викторович

1.1. Искусственные нейронные сети. Их основные типы, используемые в физике.

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

• уровнем активации

• топологией связей нейронов друг с другом;

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

• выходным уровнем, который связан с уровнем активации посредством

• некоторой функции обычно сигмоидального типа; Наиболее привлекательными чертами ИНС являются:

• вся система состоит из очень большого числа одинаковых нейронов,

• причем результат работы ИНС

• малочувствителен к характеристикам конкретного нейрона;

• система допускает возможность параллельной обработки . информации.

Таким образом, если обозначить сигнал, исходящий от к-го нейрона сети как хк , вес синаптической связи j-то и к-то нейронов как w^} то общий входной сигнал, поступающий на j-й нейрон от всех остальных нейронов будет равен hj=Ijc WjkXk (1)

Выходной сигнал этогоу'-го нейрона получается путем воздействия на hj активационной функцией yj-g(hj), где g(u) - либо пороговая функция, либо сжимающая функция сигмоидального вида (см. рис. 1).

Ключевыми характеристиками сети являются: тип связей между нейронами и динамика эволюции сети, определяемая функцией активации нейронов и правилом изменения весов в процессе этой эволюции., ИНС, наиболее распространенные в физике, определяются двумя типами связей: прямоточные сети без обратных связей, например, многослойные персептроны (МСП) (см. рис.2а) или полносвязные сети, в которых все нейроны связаны друг с другом (см.рис.2Ь), как в нейронной сети Хопфилда (ХНС). Мы можем также рассматривать и клеточные автоматы [18] как специальный тип нейронных сетей с локальными связями.

Input layer

Hidden layer

Output layer

Рис.2. Прямоточная ИНС (МСП или RBF-сети) и полносвязная ИНС (сеть Хопфилда) Нейронные сети успешно применяются везде, где нужно решать задачи классификации, прогнозирования или распознавания. Этот успех определяется следующими их возможностями:

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

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

• Сравнительная простота структуры ИНС и простота применения. Это особенно касается физики, где обычно квалификации дипломированного физика-экпериментатора вполне хватает для использования программной или схемной реализации ИНС. Кроме того, благодаря распространению Монте-Карловских пакетов программ типа GEANT-3, позволяющих моделировать физические процессы в детекторах частиц в условиях, максимально приближенных к реальным, не возникает проблем с моделированием необходимой последовательности данных, требуемых для обучения сети.

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

Примечательно, что один из первых таких нейропакетов, программа JETNET была разработан именно физиками из Лундского университета [19] [18]. По этим же причинам нескольким электронным фирмам уже в начале 90-х удалось осуществить аппаратные реализации ИНС широкого применения в виде интегральных чипов, работающих параллельно и допускающих настройку сети на заранее отмоделированную конфигурацию см. например, [20] или обзор в [21]). Значительное количество статей по применению различных нейрочипов (ETANN, ТОТЕМ, ZISC036) и даже специального алгоритмического языка CNAPS для управления ими можно найти в специальном выпуске журнала "Nuclear Instruments and Methods in Physics Research" [22].

Введение диссертации (часть автореферата) на тему «Использование искусственных нейронных сетей и вейвлет-анализа для повышения эффективности в задачах распознавания и классификации»

1.2.3. Машина Больцмана Машина Больцмана была предложена и исследовалась во второй половине 1980-х годов. Этапы больцмановского обучения: 1. Определить переменную Г, представляющую искусственную температуру.

2. Предъявить сети множество входов и вычислить выходы и целевую функцию.,

3. Дать случайное изменение весу и пересчитать выход сети и изменение целевой функции в соответствии со сделанным изменением веса.

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

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

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

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

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

1.2.4. Сеть встречного распространения Сети встречного распространения созданы Робертом Хехт-Нильсоном (HNC - Hecht-Nielsen Neurocomputer and University of California, San Diego,CA). В сети встречного распространения объединены два алгоритма: самоорганизующаяся карта Кохонена и звезда Гроссберга. Их объединение приводит к появлению у модели встречного распространения свойств, которых нет у каждого из этих алгоритмов в отдельности. Нейронные сети, которые объединяют различные нейропарадигмы как строительные блоки, более близки к мозгу по архитектуре, чем однородные структуры. Считается, что в мозге именно каскадные соединения модулей различной специализации позволяют выполнять требуемые вычисления. В процессе обучения сети встречного распространения входные векторы ассоциируются с соответствующими выходными векторами. Эти векторы могут быть двоичными или непрерывными. После обучения сеть формирует выходные сигналы, соответствующие входным сигналам. Обобщающая способность сети дает возможность получать правильный выход, когда входной вектор неполон или искажен. Сеть встречного распространения имеет два слоя с последовательными связями. Первый слой - слой Кохонена, второй - слой Гроссберга. Каждый элемент входного сигнала подается на все нейроны слоя Кохонена. Веса связей wmn образуют матрицу W. Каждый нейрон слоя Кохонена соединен со всеми нейронами слоя Гроссберга. Веса связей vnp образуют матрицу весов V. Отличие сети встречного распространения от других многослойных сетей с последовательными связями состоит в операциях, выполняемых нейронами Кохонена и Гроссберга.

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

Функционирование сети: (Слой Кохонена)

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

NETj=£j WjXp где NETj- выходу-го нейрона Кохонена,

WJ=(wlj,w2j,.wmj) - вектор весову'-го нейрона Кохонена,

Х—(х1,х2,.хт) - вектор входного сигнала, или в векторно-матричной форме:

N=X*W, где N - вектор выходов NET слоя Кохонена.

Нейрон Кохонена с максимальным значением NET является "победителем".

Его выход равен единице, у остальных он равен нулю.

Слой Гроссберга функционирует в сходной манере. Его выход NET является взвешенной суммой выходов слоя Кохонена.

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

Гроссберга выдает величину веса, который связывает этот нейрон с единственным нейроном Кохонена, чей выход отличен от нуля.

Предварительная обработка входных сигналов.

Нормализация (предварительная обработка) входных векторов выполняется путем деления каждой компоненты входного вектора на длину вектора квадратный корень из суммы квадратов компонент вектора). Это превращает входной вектор в единичный вектор с тем же направлением, т.е. в вектор единичной длины в w-мерном пространстве. Слой Кохонена классифицирует входные векторы в группы схожих. Это достигается с помощью такой подстройки весов слоя Кохонена, что близкие входные векторы активируют один и тот же нейрон данного слоя. Затем задачей слоя Гроссберга является получение требуемых выходов. Слой Кохонена обучается без учителя (самообучается). В результате обучения слой приобретает способность разделять несхожие входные векторы. Какой именно нейрон будет активироваться при предъявлении конкретного входного сигнала, заранее трудно предсказать. При обучении слоя Кохонена на вход подается входной вектор и вычисляются его скалярные произведения с векторами весов всех нейронов. Скалярное произведение является мерой сходства между входным вектором и вектором весов. Нейрон с максимальным значением скалярного произведения объявляется "победителем" и его веса подстраиваются (весовой вектор приближается к входному). Уравнение, описывающее процесс обучения, имеет вид: wn=w0+a(x-w0), где wn - новое значение веса, соединяющего входную компоненту х с выигравшим нейроном, w0 - предыдущее значение этого веса, а - коэффициент скорости обучения.

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

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

Обучение слоя Гроссберга - это обучение с учителем, алгоритм использует заданные желаемые выходы.

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

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

Еще один метод повышения эффективности обучения - наделение каждого нейрона "чувством справедливости". Если нейрон становится победителем чаще, чем 1/к {к - число нейронов Кохонена), то ему временно увеличивают порог, давая тем самым обучаться и другим нейронам. Кроме "метода аккредитации", при котором для каждого входного вектора активируется лишь один нейрон Кохонена, может быть использован "метод интерполяции", при использовании которого целая группа нейронов Кохонена, имеющих наибольшие выходы, может передавать свои выходные сигналы в слой Гроссберга. Этот метод повышает точность отображений, реализуемых сетью.

Источники: [3], [105], [106].

1.2.5. MAXNET - сеть поиска максимума с прямыми связями

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

В основе лежит нейросетевой компаратор, который выполняет сравнение двух аналоговых сигналов (xj и х?). На выходе z - значение максимального сигнала (х/илихг). Выходы^/ иу2 показывают, какой именно входной сигнал имеет максимальное значение. Входные сигналы целые.

Размерности входа и выхода ограничены при программной реализации только возможностями вычислительной системы, на которой моделируется нейронная сеть, при аппаратной реализации - технологическими возможностями. Размерности входных и выходных сигналов совпадают. Число слоев в сети приблизительно log2(M)> где М - размерность входного сигнала. Число слоев сети растет с увеличением размерности входного сигнала. В отличие от сети MAXNET циклического функционирования, в рассматриваемой модели заранее известен объем вычислений, который требуется для получения решения. Источники: [51].

1.2.6. Нейросетевой гауссов классификатор Модель предложена Липпманом в 1987 году. Персептрон может быть использован для реализации гауссова классификатора по максимуму вероятности (Gaussian maximum likelihood classifier). В классическом алгоритме обучения персептрона не используются предположения относительно распределений примеров обучающих выборок, а рассматривается функция ошибки. Этот алгоритм работает более устойчиво, если входные сигналы формируются в результате нелинейных процессов и распределены несимметрично и не по гауссову закону. В основе построения Гауссова классификатора лежат предположения о распределениях входных сигналов. Считается, что эти распределения известны и соответствует закону Гаусса. Размерности входа и выхода ограничены при программной реализации только возможностями вычислительной системы, на которой моделируется нейронная сеть, при аппаратной реализации - технологическими возможностями. Области применения: распознавание образов, классификация.

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

Программные или аппаратные реализации модели очень просты. Простой и быстрый алгоритм формирования синаптических весов и смещений. Источники: [51].

1.2.7. Генетический алгоритм обучения

Впервые идея использования генетических алгоритмов для обучения (machine learning) была предложена в 1970-е годы. Во второй половине 1980-х к этой идее вернулись в связи с обучением нейронных сетей. Использование механизмов генетической эволюции для обучения нейронных сетей кажется естественным, поскольку модели нейронных сетей разрабатываются по аналогии с мозгом и реализуют некоторые его особенности, появившиеся в результате биологической эволюции.

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

Первая проблема построения алгоритмов генетической эволюции - это кодировка информации, содержащейся в модели нейронной сети. Коды называют "хромосомами". Для фиксированной топологии (архитектуры) нейронной сети эта информация полностью содержится в значениях синаптических весов (W) и смещений (В). Вектор (W,B) рассматривается как хромосома. Возможны более сложные способы кодирования информации. Для реализации концепции отбора необходимо ввести способ сопоставления (сравнения) различных хромосом в соответсвии с их возможностями решения поставленных задач. Для нейронных сетей с последовательными связями это может быть стандартная мера - сумма квадратов разностей компонент действительного и желаемого сигналов. (Эта мера используется в стандартном алгоритме обратного распространения.) В отличие от большинства других алгоритмов обучения, для генетических алгоритмов требуется не один набор начальных значений параметров, а несколько наборов, которые называются популяцией хромосом. Популяция обрабатывается с помощью алгоритмов репродукции, изменчивости (мутаций), генетической композиции. Эти алгоритмы напоминают биологические процессы. Наиболее важные среди них: случайные мутации данных в индивидуальных хромосомах, переходы (кроссенговер) и рекомбинация генетического материала, содержащегося в индивидуальных родительских хромосомах (аналогично гетеросексуальной репродукции), и миграции генов.

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

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

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

Генетические алгоритмы дают возможность оперировать дискретными значениями параметров нейронных сетей. Это упрощает разработку цифровых аппаратных реализаций нейронных сетей. При обучении на компьютере нейронных сетей, не ориентированных на аппаратную реализацию, возможность использования дискретных значений параметров в некоторых случаях может приводить к сокращению общего времени обучения. В рамках "генетического" подхода в последнее время разработаны многочисленные алгоритмы обучения нейронных сетей, различающиеся способами представления данных нейронной сети в "хромосомах", стратегиями репродукции, мутаций, отбора. Источники: [51] - [59].

1.2.8. Сеть Хемминга

Использование - вычисления расстояния Хемминга в задаче передачи двоичных сигналов фиксированной длины исследовалось в теории информации. Расстояние Хемминга между двумя бинарными векторами одинаковой длины - это число несовпадающих бит в этих векторах. Нейронная сеть, которая реализует параллельное вычисление расстояний Хемминга от входного вектора до нескольких векторов- образцов, носит название сети Хемминга. Тип выходных сигналов - целые числа. Размерности входа и выхода ограничены при программной реализации только возможностями вычислительной системы, на которой моделируется нейронная сеть, при аппаратной реализации - технологическими возможностями. Размерности входных и выходных сигналов могут не совпадать. Передаточная функция - линейная с насыщением. Число синапсов в сети равно N*M.r

Области применения: распознавание образов, классификация, ассоциативная память, надежная передача сигналов в условиях помех. Сеть способна правильно распознавать (классифицировать) только слабо запомненные входные сигналы. Возможность использования только бинарных входных сигналов существенно ограничивает область применения. Сеть работает предельно просто и быстро. Выходной сигнал (решение задачи) формируется в результате прохода через всего лишь один слой нейронов. Для сравнения: в многослойных сетях сигнал проходит через несколько слоев. В сетях циклического функционирования сигнал многократно проходит через нейроны сети, причем число итераций, необходимое для получения решения, бывает заранее не известно. В модели использован один из самых простых алгоритмов формирования синаптических весов и смещений сети. В отличие от сети Хопфилда, емкость сети Хемминга не зависит от размерности входного сигнала, она в точности равна количеству нейронов (М). Сеть Хопфилда с входным сигналом размерностью 100 может запомнить 10 образцов, при этом у нее будет 10000 синапсов. У сети Хемминга с такой же емкостью будет всего лишь 1000 синапсов. Сеть Хемминга может быть, дополнена сетью MAXNET, которая определяет, какой из нейронов сети Хемминга имеет выход с максимальным значением. Источники: [51], [73], [76].

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

Размерности входных и выходных сигналов совпадают. Несколько слов о емкости сети Хопфилда: сеть, содержащая N нейронов может запомнить не более М=0.15 *N образов. При этом запоминаемые образы не должны быть сильно коррелированы.

Области применения: ассоциативная память, адресуемая по содержанию, задачи распознавания образов, задачи оптимизации.

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

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

Сеть имеет огромное историческое значение. С этой модели началось возрождение интереса к нейронным сетям в середине 80-х годов.

Существует модель сети Хопфилда с бинарными входными сигналами.

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

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

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

Источники: [3], [51], [73], [76].

1.2.10. Сеть Кохонена

Другое название - самоорганизующаяся карта признаков

Кохонена (Kohonen's self organizing feature map).

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

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

1. Инициализация сети: Весовым коэффициентам сети присваиваются малые случайные значения. Общее число синаптических весов - M*N.

2. Предъявление сети нового входного сигнала.

3. Вычисление расстояния до всех нейронов сети.

4. Выбор нейрона с наименьшим расстоянием.

5. Производится подстройка весов для нейрона "победителя" и всех нейронов из его зоны соседства NE.

6. Возвращение к шагу 2.

Области применения: кластерный анализ, распознавание образов, классификация. Сеть может быть использована для кластерного анализа только в том случае, если заранее известно число кластеров. В отличие от сети ART Гроссберга, сеть Кохонена способна функционировать в условиях помех, так как число классов фиксировано, веса модифицируются медленно, настройка весов заканчивается после обучения (в сети ART настройка продолжается непрерывно). Одна из модификаций состоит в том, что к сети Кохонена добавляется сеть MAXNET, которая определяет нейрон с наименьшим расстоянием до входного сигнала. Источники: [3], [51], [76].

1.2.11. Однослойный персептрон Модель разработана Розенблаттом в 1959 г.

Однослойный персептрон способен распознавать простейшие образы. Отдельный нейрон вычисляет взвешенную сумму элементов входного сигнала, вычитает значение смещения и пропускает результат через жесткую пороговую функцию, выход которой равен +1 или -/. В зависимости от значения выходного сигнала принимается решение: +1 -входной сигнал принадлежит классу Л, -1 - входной сигнал принадлежит классу В. Решающие области определяют, какие входные образы будут отнесены к классу^, какие - к классу В. Персептрон, состоящий из одного нейрона, формирует две решающие области, разделенные гиперплоскостью. При этом разделяющая поверхность представляет собой прямую линию на плоскости. Входные сигналы над разделяющей линией относятся к классу А, под линией - к классу В. Уравнение, задающее разделяющую прямую, зависит от значений синаптических весов и смещения. Далее описывается классическая процедура настройки персептрона, предложенная Розенблаттом. Емкость сети совпадает с числом нейронов. Область применения: распознавание образов, классификация. Примитивные разделяющие поверхности (гиперплоскости) дают возможность решать лишь самые простые задачи распознавания. Программные или аппаратные реализации модели очень просты. Простой и быстрый алгоритм обучения. Многослойные персептроны дают возможность строить более сложные разделяющие поверхности и поэтому имеют более широкое применение при решении задач распознавания. Источники: [3], [51], [76].

1.3. Применение полносвязных ИНС Как упоминалось, в общую схему ИНС помимо широко применяемых персептронов, укладывается также сеть Хопфилда (ХНС) [26]. Это полносвязная сеть, являющаяся в простейшем случае [27] системой простых бинарных нейронов sh которые могут принимать одно из двух различных значений, например, +1, -1. Эволюция ХНС приводит ее в некоторое состояние стабильности, устойчивого равновесия. Рассматривая ИНС как динамическую систему бинарных нейронов, Хопфилд использовал билинейную функцию Ляпунова как функционал энергии сети

E(s) = -l/2Zij St WySj (2) и показал, что для симметричной матрицы весов wy = w^ с нулевой диагональю wu = 0 и асинхронной динамикой сети ее энергия в результате эволюции убывает в локальные минимумы, соответствующие точкам стабильности сети.

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

Sj=l/2(l+sign(-cE/cSj) (3)

Однако процедура итерационного решения системы для случая бинарных нейронов часто приводит в какой-нибудь локальный минимум функционала энергии. Кроме того, во многих практических приложениях. ХНС бинарные нейроны оказываются нереалистичной идеализацией. В этой связи Хопфилд в [28] предложил обобщение своей модели ИНС на случай нейронов с непрерывным множеством состояний. Стандартным путем перехода к нейронам с непрерывными состояниями является введение статистического шума в систему с последующим применением теории среднего поля (см., например, [1,31]) , что приводит к усреднению значений состояний нейронов и замене ступенчатой функции на функцию сигмоидального вида: v, =1/2(1 +tanh(-H/T) (4)

Здесь температура Г соответствует уровню статистического шума, а Щ -<Zj Щ] Sj>t- локальное среднее поле нейрона. Значения V/, переставшие быть целочисленными, определяют уровень активности нейрона, т.е. в случае v,- > vmin нейрон считается активным. Температура убывает по схеме "имитационного отжига" (simulated annealing) [30]. С помощью системы уравнений (4) состояния нейронов сети итеративно обновляются до достижения ею стабильной точки. Однако то, что нейроны Sij теперь не являются бинарными, позволяет оперативно следить за теми из них, которые соединяют точки треков и под стимулирующим воздействием весов постепенно увеличивают уровень своей активности в процессе эволюции сети. В качестве порога уровня активности обычно выбирается vmin = 0.5.

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

1.3.1 Сегментная модель ХНС Первую удачную попытку использовать нейронные сети для распознавания треков сделали Петерсон [1] и Денби [29]. Их подход, известный как метод сегментов, состоял в том, что на множестве экспериментальных точек на плоскости вводились нейроны Sy, определяющие, соединяются точки i и j или нет, т.е. принадлежит данный направленный сегмент Sy треку или нет см. рис.3). В дальнейших вычислениях в соответствии со схемой (4) состояния нейронов Vy перестают быть целочисленными. Их значения Vy

Sji>r и определяют уровень активности

Рисунок 3. Метод сегментов) гладких прямых треков без разветвлений. Поэтому первый стоимостной член выбирался так, чтобы он поощрял короткие смежные сегменты с малым углом между ними, а второй член (штрафной) устанавливал запрет разветвлений (т.е. запрет ситуаций, когда к одной точке присоединено больше одного сегмента-нейрона) и баланс между числом активных нейронов и числом экспериментальных точек. К сожалению, эта схема Денби-Петерсона, принципиально запрещающая бифуркацию трека, была неприменима в случаях распадов нейтральных и рождением заряженных частиц в объеме детектора. Поэтому, например, в работе [32], в которой исследовались данные распада нейтральных каонов и гиперонов пришлось модифицировать штрафной член энергетической функции так, чтобы он позволял осуществлять распознавание разветвлений. В тяжелых фоновых условиях и экспериментальной неэфффективности камер действующая программа обработки эксперимента EXCHARM не распознала 5.2 % событий, а программа, основанная на ИНС, - 3.2%. При этом из нераспознанных событий для разных программ совпали только 0.8% от общего числа событий, т.е. эти два множества плохо распознанных событий имеют малую область пересечения. После распознаваниями Y-проекций треков более быстрым методом опорных дорожек в программе

1 нейрона.

Энергетический функционал в работах [1,29] был определен как состоящий из двух частей: E=Ecost+Econstraint Предполагалось, что распознавание велось для обработки производится пространственная "сшивка" этих проекций. Если часть надежно найденных проекций не имеет сшивок, то включается нейросетевой алгоритм, который в большинстве случаев успешно решает задачу распознавания треков в таких событиях. Комбинированный алгоритм с использованием ИНС был опробован и на реальных данных эксперимента EXCHARM и позволил достичь 99% эффективности распознавания событий.

1.3.1 Эластичные нейронные сети В ходе многочисленных применений нейросетей в ФВЭ обнаружились такие их недостатки, отмеченные рядом исследователей (см. напр., [38,39]), как:

• слишком медленная сходимость из-за излишнего числа степеней свободы;

• с помощью ИНС решается только проблема распознавания без учета известной модели трека;

• отмечается чрезмерная чувствительность ИНС к шумам. В этой связи в работе [39] было предложено объединить этапы распознавания и подгонки кривых, максимально используя априорную информацию. С этой целью предлагалось, с учетом известного уравнение трека, создать эластичный шаблон и изгибать его меняя параметры уравнения) так, чтобы он прошел по «своим» измеренным точкам. Подобный подход немедленно порождал естественные вопросы:

• неизвестно число шаблонов;

• где взять начальные значения их параметров;

• как организовать подгонку сразу всех кривых (треков) Проблема нахождения шаблонов (templates) и грубых значений их параметров требует специального рассмотрения. Мы ограничимся здесь ссылкой на работы [38-41], в которых использовались эластичные шаблоны и отметим, что всюду для их поиска применяется тот или иной вариант преобразования Радона-Хафа [42,43]. При практической реализации это преобразование сводится к гистограммированию в пространстве параметров с последующим поиском максимального значения подобно тому, как это делалось в конце предыдущего раздела при поиске начальных значение роторов. В силу приближенного характера процедуры нахождения шаблонов их число могло превышать число реальных треков в событии. Появляющиеся из-за этого лишние, искусственные треки должны быть удалены впоследствии в ходе специальной процедуры отбраковки. Метод эластичных нейросетей был успешно применен в работах [40,41] для обработки данных, параметризуемых уравнением окружности: колец черенковского излучения и треков в однородном магнитном поле. В работе [40] методом эластичных нейросетей (ЭН) осуществлялся поиск черенковских колец с одновременной оценкой их параметров по данным RICH детектора CERES/NA-45. Глобальный поиск велся безо всяких априорных сведений о центрах и радиусах колец. Эта информация была получена с помощью сведения трехмерного преобразования Хафа к двумерному и одномерному. Вначале выполнялся перебор допустимых триплетов измеренных точек (т.е. таких троек точек, через которые можно провести окружность с радиусом и центром, удовлетворяющим заданным неравенствам). Идея метода основана на том, что все точки, принадлежащие некой окружности должны отображаться в одну точку в пространстве параметров, так что суммируя, мы должны получить пик в этом месте. Из-за наличия ошибок измерений этот пик несколько размазывается, что сказывается на размерах разбиения при гистограммировании получаемых параметров. Программирование разумнее выполнить в два этапа: сначала строится 20-гистограммы центров и находятся все пики в ней, превышающие заданный порог. Затем для каждого найденного центра выбираются точки внутри области допустимых значений радиуса и также гистограммируются. Максимальный из пиков гистограммы и принимается за оценку радиуса. Процедуры выбора порогов и тестирования полученных параметров достаточно сложны. В [40] можно найти полезные рекомендации по выбору размеров биннинга гистограмм и порогов для оценки параметров колец, полученные на основе исследования о влиянии на эффективность распознавания таких факторов, как радиальный разброс точек, общая зашумленность события и среднее число фотонов на кольцо.

Следует, однако, сделать важное замечание, касающееся издержек глобальности метода ЭНС: при попытках увеличить число колец или множественности, т.е. числа треков, в районе поиска выше 12-13, - метод перестает работать. Причина этого в наличии ошибок в преобразовании Хафа, но главным образом из-за проблем с минимизацией функционала. Поэтому в работе [41], касавшейся применения метода ЭНС в задаче распознавания и определения параметров треков в системе дрейфовых трубок, авторы отказались от глобального прослеживания сразу всех треков события и искали треки по данным Хаф-преобразования по-очереди. Каждая из газополных трубок, образующих плотные слои сотовой структуры имеет центральную электродную проволоку, так что при прохождении частицы сквозь такую трубку регистрируется не только координата этой проволоки, но и время дрейфа до нее облака ионов, образующихся в газе при прохождении частицы. При известной скорости дрейфа это время пересчитывается в радиус дрейфа, позволяющий вычислить координату пролета частицы до микронных точностей. Таким образом, данные об измеренном треке в дрейфовой камере выглядели как набор малых окружностей с центрами в зарегистрированных центральных проволоках и радиусами, равным соответствующим радиусам дрейфа. С точностью до ошибок измерения этих радиусов трек проходит по касательным ко всем этим маленьким окружностям. Главная неприятность здесь - то, что знание радиуса дрейфа не позволяет определить, слева или справа от проволоки прошла частица, возникает известная лево-право неопределенность. Ситуация усугубляется как из-за ложных срабатываний некоторых из трубок, так и из-за их неэффективности, приводящей к пропускам некоторых измерений.

1.3.2 Нейронные сети радиально-базисного типа

Нетрудно показать, что схема классификации на два класса с помощью простого МСП с пороговой функцией активации имеет простую геометрическую интерпретацию: гиперплоскость Wy Sj = 0 делит пространство на два полупространства. Таким образом, то как персептрон формирует понятия (или проводит классификацию), является процессом нахождения набора гиперплоскостей, которые обеспечивают ограничивание или оконтуривание каждого из множеств, представляющих собой отдельные классы. Как видно из формулы нейрон осуществляет преобразование вектора в действительное число путем скалярного умножения подаваемого на вход вектора на вектор весовых коэффициентов. Однако ограничение некоторого подмножества набором гиперплоскостей не является единственным способом разделения множеств. Аналогичного и не менее естественного результата можно достигнуть, описав каждое из множеств при помощи полного покрытия некоторым набором гиперсфер. Нейронные сети, реализующие такую t классификацию называются сетями с радиальной базисной функцией активации (RBF-сеть) [44]. В RBF-сетях вместо скалярного произведения двух векторов вычисляется расстояние между ними, т.е. в пространстве этих векторов вводится та или иная метрика p(xlj,x2j). В зависимости от задачи в качестве метрики можно использовать сумму модулей разностей компонент Ej |Xj - Wy\ (так называемое Манхеттенское расстояние), или максимум этих модулей тах{ \х) - или так называемое расстояние Махаланобиса d2(xl,x2) = (х1-х2^^х1рх2^, где Ду - это элементы матрицы ковариации этих векторов. В работе [45] используется квадратичная метрика L2=Xj (xj - Wy)2. Вместо функции активации сигмоидального вида в RBF-сетях используется гауссиан, т.е. скрытый, промежуточный слой состоит из радиальных элементов, каждый из которых воспроизводит гауссову поверхность отклика. Поскольку эти функции нелинейны, то для моделирования произвольной функции нет необходимости брать более одного промежуточного слоя, необходимо лишь взять достаточное число радиальных элементов. Выходной слой состоит из элементов с линейными функциями активации [44]. Это удобно, т.к. параметры линейной комбинации в выходном слое можно полностью оптимизировать с помощью хорошо известных методов линейного моделирования, которые работают быстро и не испытывают трудностей с локальными минимумами, так мешающими при обучении МСП. Поэтому сеть RBF обучается очень быстро (на порядок быстрее МСП). С другой стороны, до того, как применять линейную оптимизацию в выходном слое сети RBF, необходимо определить число радиальных элементов, положение их центров и величины отклонений. Соответствующие алгоритмы, хотя и работают быстрее алгоритмов обучения МСП, в меньшей степени пригодны для отыскания субоптимальных решений. Другие отличия работы RBF от МСП связаны с различным представлением пространства модели: "групповым" в RBF и "плоскостным" в МСП. Из-за "группового" подхода сети RBF требуют больше нейронов скрытого слоя и, соответственно, больше компьютерной памяти. Существует несколько алгоритмов обучения RBF сетей, общими чертами которых являются:

• Обучение скрытого слоя отдельно от выходного.

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

• При этом расположение центров должно

• соответствовать кластерам, реально присутствующим в исходных данных.

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

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

Глава 2

2.1 Методы классификации данных.

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

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

1) Отнесение данных (совокупности объектов, записей из информационных файлов) к заданным классам;

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

Пусть М- множество объектов Si, S2, S3,., Sq, а Kj.K2.K3; Ki - множество классов и

ТО

М = [К] ик2 икз и. KJ=i-1

Пусть задана информация о классах Ij (К^К^Кз,., К1) и информация об объектах I(S). Задача состоит в том, чтобы по информации о классах 1(К],К2,Кз, ., К]) и по описанию объектов I(S) вычислить значения предикатов G/S)->S^Kj.

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

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

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

2) Извлечение характеристик классов из данных классов и включение в них объектов;

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

Тогда приходим к третьему типу задач классификации:

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

Приведем краткий обзор существующих методов классификации.

2.1.1 Методы многомерной классификации данных.

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

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

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

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

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

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

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

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

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

2.1.3 Основная задача кластерного анализа

Пусть множество I={li, h,h,—./^обозначает множество объектов из некоторой совокупности. Для множества / имеется множество векторов измерений X—{XiX2,X3,.,Xn}, которые описывают множество /: объекту /у, соответствует вектор измерения X), объекту I2 - вектор Х2 и т.д. Множество X может быть представлено, как п точек в р-мерном евклидовом пространстве.

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

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

Задачи кластерного анализа можно классифицировать различными способами. Например, по числу объектов классификации (векторов образов), а также по числу классов, на которое разбивается множество объектов классификации. При этом возможны следующие случаи: 1. Число классов известно заранее;

2. Число классов неизвестно и его необходимо определить;

3. Число классов неизвестно и его не нужно определять.

Среди процедур кластеризации можно выделить следующие основные типы:

1. Иерархические;

2. Параллельные;

3. Последовательные.

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

Параллельные процедуры кластеризации реализуют, как правило, две основные идеи:

1. Идею оптимизации разбиения согласно заранее выбранного функционала качества разбиения;

2. Идею образования кластера по принципу определения мест наибольшей плотности точек (векторов образов в метрическом

40

РОССИЙСКАЯ ГОСУДАРСТВЕННА^ £ЛБЛЛОТ ЕЕА пространстве). В этом случае алгоритмы используют понятие эталонных точек (множеств) и оперируют одновременно со всеми векторами образов.

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

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

Наиболее трудное и наименее формализованное в задаче классификации -это определение понятия однородности объектов. В общем случае понятие однородности объектов задается либо введением правила вычислений расстояния p(XhX2>) между любой парой объектов исследуемого множества

Xi,X2,X3,. .,Xn}, либо заданием некоторой функции r(Xi,XJ, характеризующей степень близости (сходства, подобия) объектов Xt и Xj. Если задана функция p(Xi,X?), то близкие в смысле этой метрики объекты считаются однородными, принадлежащими одному классу. При этом, следовательно, необходимо сопоставление p(XbXj) с некоторым пороговым значением, определяемым в каждом конкретном случае по-своему.

Определение. Мерой близости называется действительная неотрицательная функция r(XuXj), обладающая следующими свойствами:

1) r(Xi,Xj)= r(Xj,Xj) - симметрия;

2) r(X^>= max r(Xi,Xj) - максимальное сходство объекта с самим собой;

3) Требование монотонного убывания при заданной метрике, т.е. изp(XhXl)> -p(XbXj) следует, что r(XhXl)<= г (XbXj)

Пример метрики р - обычное евклидово расстояние. Существует много метрик: расстояние Махаланобиса, различные многомерные (интегральные) меры расстояния. Евклидова метрика наиболее употребительна.

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

1) коэффициенты подобия;

2) коэффициенты связи (корреляции);

3) показатели расстояния в метрическом пространстве.

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

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

2.1.4 Методы классификации данных, основанные на использовании функции расстояния.

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

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

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

Классификация образов по критерию минимума расстояния

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

Случай единственного эталона для каждого класса.

М классов, допускающих представление с помощью эталонных образов Z i,Z Z т.

Случай множества эталонов для каждого класса.

Любой образ, принадлежащий классу, проявляет тенденцию к группировке в окрестности одного из эталонов Z1 h ., ZN\ , где Nt количество эталонных образов, представляющих f-ый класс.

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

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

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

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

2.2. Самонастраивающаяся нейронная сеть радиально базисного типа.

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

Описанный ниже алгоритм обучения СНРБ-сети, позволяет существенно сократить количество нейронов в скрытом промежуточном слое, что также увеличивает скорость работы сети.

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

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

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

2.2.1. Обучение радиальных нейронов СНРБ-сети. В качестве нейронов скрытого слоя выбраны RBF-нейроны с обратной пороговой функцией в качестве активационной, т.е. активационная функция возвращает единицу при значении аргумента меньше или равном пороговому значению, и ноль в противном случае. Аргумент активационной функции вычисляется как расстояние, зависящее от выбранной метрики, между входным вектором и вектором синаптических весов. Таким образом, понятно, что областью активации отдельного нейрона является внутренняя область гиперсферы (гипершар). Для удобства описания алгоритма обучения распределим обучающую выборку на несколько подмножеств. C,N'(-'auTent'^current В подмножество неклассифицированных элементов N будут входить образцы, которые должны быть классифицированы. В подмножество классифицированных элементов С будут соответственно относиться элементы обучающего множества, которые нейронная сеть классифицирует корректно. Такое условное деление существует во время всего процесса обучения. Очевидно, что критерием завершения обучения служит обращение множества неклассифицированных элементов в пустое множество. N=0 Оставшиеся два подмножества характеризуют процесс обучения отдельного нейрона. Это множество правильно классифицированных элементов текущим нейроном Ссиггеп1 и множество Ncurrent неправильно классифицируемых данным нейроном. Происхождение этих подмножеств понятно из следующего: при добавлении нового нейрона некоторые элементы из множества N могут попасть в область активации этого нового нейрона и следовательно должны перейти в множество С при окончании » обучения нейрона, но так как процесс итеративный, они временно помещаются в множество названное как Ccurrent. Аналогично, может случиться, что элемент множества С попадает в область активации нового нейрона, и он будет отнесет к множеству Ncurrent. Таким образом, легко подсчитать полезный вклад в классификацию, вносимый новым нейроном: ОН будет равен разности количеств элементов В множествах Ccurrent И Ncurrent' Инициализация состоит в приравнивании к пустому множеству C^Ccurrent-Ncurrent&t &N- это обучающая выборка. Дальнейшее обучение делится на два этапа.

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

Ncurrent• При этом сформированный нейрон становится частью сети только в том случае, если он вносит положительный вклад в классификацию. Q(Ccurrent) ~Q(Ncurrent) — /, где Q(x) - количество элементов множества X. После добавления нового нейрона в слой: С=С U Cogent, N=N U Ncurrenh Ccurrent=Ncurrent=0• Первый этап обучения завершается при условии, что для любого класса новый нейрон не может быть добавлен в сеть в соответствии с критерием Q(Ccun-enJ-QfNcurren,J > 1. Необходимость второго этапа обучения очевидна, поскольку описанная процедура не гарантирует полного исчерпания множества N. Второй этап обучения: Снова случайным образом выбирается элемент из множества N. Радиус нейрона, или что тоже, самое порог активации L, увеличивается до включения ближайшего соседа, при условии, что он принадлежит к тому же классу. Центр тяжести пересчитывается при включении каждого из новых элементов. Очевидно, что вклад любого из таких нейронов будет больше нуля. Таким образом, видно что все элементы N будут классифицированы за конечное время.

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

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

48 отношению к синаптическим весовым коэффициентам нейрона, поскольку известно, что такой функционал минимизируется при помощи метода сопряженных градиентов за конечное число шагов. Далее пусть тхо и тп\ соответственно максимальное значение отклика нейрона на элементах чужих классов и минимальное значение отклика нейрона на элементах своего класса. Если тхо < mrij, тогда эти классы разделимы, обучение данного нейрона успешно, и он добавляется в сеть. В противном случае, т.е. когда хотя бы у одного из выходных нейронов условие тх0 < miti не выполняется, необходим дополнительный слой RBF-нейронов. Этот слой обучается по вышеописанному алгоритму с исключением первого этапа и использованием только второго.

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

2.2.3. Сравнение МСП, RBF и СНРБ-сетей. Общеизвестна проблема (пере-/недо-)обучения нейронной сети, особенно характерная для МСП (многослойного персептрона), обучаемого по методу обратного распространения ошибки, когда малое число нейронов не позволяет адекватно обучить нейронную сеть, а слишком большое их количество формирует слишком непредсказуемую функцию отклика. Динамический рост СНРБ-сети во время процесса обучения позволяет избежать подобной проблемы. Для больших массивов данных выделяются большие области, а нейроны с небольшим порогом отслеживают малые отклонения при необходимости.

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

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

Рисунок 3. Модельная задача с классификацией множеств. Слева направо: множества, решение полученное RBF-сетью, решение полученное МСП. о о о ■ I

V . " а о °о а

Iе» • ■а •

• • . 5 • . . • ■

• •

• о в

•

• •• о о а о о а а а а о в в ввв о о • •

Рисунок 4. Модельная задача с классификацией множеств. Слева направо: множества, решение полученное RBF-сетью, решение полученное SCRBF-сетью.

Рисунок 5. Модельная задача с классификацией вложенных спиральных множеств. Слева направо: множества, решение полученное RBF-сетью, решение полученное SCRBF-сетью.

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

Для выяснения этого была рассмотрена также классическая задача о классификации ирисов Фишера.

Имеются данные измерений для 150 экземпляров ирисов, в равных частях (по 50 штук) принадлежащих к трем видам (iris setosa, iris versicolor, iris virginica). Для каждого экземпляра ириса известны 4 величины: длина чашелистика (Sepal Length), ширина чашелистика (Sepal Width), длина лепестка (Petal Length), ширина лепестка (Petal Width). Входной файл состоит из 150 строк (по 50 для каждого сорта). Пятая переменная -целевая, обозначает класс (вид) и для различных видов принимает следующие значения: 1 - setosa, 2 - versicolor, 3 - virginica. Такой способ кодировки связан с предположением Фишера, что versicolor - это гибрид setosa и virginica. Задача - подтвердить или опровергнуть это предположение. Обученная на решение этой классической задачи СНРБсеть, показала лучший с точки зрения количества кластеров результат по сравнению с другими методами кластерного анализа.

И на рисунке 5, который был сгенерен программой обучения, представлено решение также известной тестовой задачи для нейронных сетей - задачи о классификации двух вложенных спиральных множеств. Решение этой задачи персептроном с помощью метода обратного распространения ошибки требует большого объема машинного времени и не всегда приводит к положительному результату. Как видно из рисунка для СНРБ-сети эта задача не представляет значительной трудности. Можно сформулировать отличия СНРБ-сети от стандартной RBF-сети следующим образом:

• СНРБ-нейроны используют более простую в вычислении пороговую активационную функцию, вместо гауссовой как в стандартной RBF;

• динамическое добавление нейронов;

• отдельное обучение нейронов и слоев;

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

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

Глава 3

Приложение СНРБ-сети для распознавания изображений

52

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

Последняя задача была выбрана для исследования, поскольку в ней воплощались проблемы, типичные для остальных приложений, она была достаточно хорошо изучена [46-48], имелась доступная через Интернет достаточно представительная база данных с набором из 400 изображений лиц [49].

Требованиями для нейросетевого алгоритма являлось быстрое и надежное распознавание изображений человеческих лиц, полученных видеокамерой с 8-разрядной градацией серого. После обучения на 10-12 снимках каждого из этих лиц ИНС должна их уверенно распознавать и надежно отвергать изображение любого из неизвестных субъектов. Вероятностные требования:

• вероятность нераспознания «своего» лица = 0.01

• вероятность пропустить «чужого» = 0.005

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

3.1. Метод главных компонент как дополнительный слой СНРБ-сети

Объектно-ориентированная программа на языке С++, реализующая предложенный алгоритм СНРБ-сети, была вначале удачно протестирована на задаче распознавание искаженных символов алфавита, после чего была опробована на распознавании нескольких человеческих лиц. Обучения выполнялось на 3-4 снимках каждого их них в различных позах. При этом оцифровки изображений этих поз попросту усреднялись с помощью весов первого слоя нейронов.

Рисунок 6. Обучающее множество фронтальных изображений человеческих лиц (первые три колонки) и их искаженные варианты распознанные СНРБ-сетью. Программа показала 98%-ю надежность при распознавании специально зашумленных и искаженных изображений тех лиц, которые использовались при обучении. В качестве примера работы программы на рисунке приведены изображения лиц трех людей, различных по полу и возрасту, введенные в компьютер с видеокамеры, как обучающее множество и их искаженные изображения, распознанные программой. Однако при тестировании на обучающем множестве из 40 лиц, сфотографированных в десяти различных фронтальных позициях, полученных по Интернету с сайта Кембриджского университета [49], программа показала недопустимо высокий процент ошибочного "узнавания чужих" изображений. Основной причиной таких ошибок служила ситуация, когда в пространстве входных признаков с размерностью свыше 2500 множество точек, описывающих признаки человеческого лица, занимает совершенно ничтожное подпространство много меньшей размерности. В этой связи были проведены предварительные вычисления по статистической оценке ковариационной матрицы для имевшихся 400 изображений лиц, после чего с помощью метода главных компонент (МГК) были вычислены коэффициенты ортогонального преобразования Карунена-Лоева [2] в подпространство всего с 60-ю главными компонентами (на рисунке 7 показан график спадания собственных значений ковариационной матрицы с ростом их номера, послуживший обоснованием для выбора размерности подпространства).

Рисунок 7. Упорядоченные по величине собственные значения матрицы ковариации в зависимости от их номера. Преобразование Карунена-Лоэва представляет собой линейное преобразование, диагонализирующее матрицу ковариации представленных данных. Поскольку это именно линейное преобразование, то формально его можно реализовать в виде дополнительного слоя нейронной сети, с линейными активационными функциями нейронов. В этом случае задача обучения этого слоя решается отдельно от общего процесса обучения состоит в вычислении собственных значений матрицы ковариации. В силу положительной определенности ковариационной матрицы задача всегда имеет решение, для получения которого мы использовали QL-алгоритм с неявными сдвигами [50].

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

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

А 1 Г шЯ

• Г ' "■ ■■■ ЩкШЯЩ^ . t ж шВш ш к > •V

-

Рисунок 8. Изображены первые 20 собственных векторов набора из 400 лиц из базы [49]. Видно что есть сильная зависимость от освещенности. В этой связи были предприняты попытки проведения исследования по применению вейвлет-преобразований для предварительной обработки изображений с целью устранения влияния вышеназванных факторов разной освещенности и т.д.

3.2. Первые результаты После детального расчетов эффективности и вероятности ложного опознания С++ программы, реализующей комбинацию СНРБ-сети с методом главных компонент, программа была обучена на 250 изображениях и протестирована на распознавание на 190 изображениях (все лица были взяты из коллекции [49]) с очень хорошим результатом: эффективность сети - 95% и ни одно из "чужих" (не предъявленных при обучении) лиц не было пропущено. Дальнейшие исследования показали, что предварительное использование вейвлет-преобразования позволяет не только сократить размерность обучающего множества но и устранить вариации изображений связанные с изменением освещенности и наличием шумов в изображении.

Глава 4

Вейвлет-анализ и его приложения в сочетании с нейронными сетями.

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

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

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

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

Базис такого преобразования, как было отмечено, конструируется из функций ограниченных как во временной так и в частотной области,

58

1 Т 1 ,ъ

5)

Cv = 2л < со, где у/{со) - Фурье преобразование вейвлет функции. причем эти функции получаются путем растяжения (сжатия) и сдвига из одной функции, которая называется материнским вейвлетом. Таким образом, если к примеру нестационарный сигнал содержит разрыв частоты, то подобное разложение не только позволяет определить его наличие, но и указывает место на временной шкале, где он произошел. Существует много разных вейвлетов, но в нашей практике мы чаще употребляем так называемые Гауссовы вейвлеты, которые являются кратными производными функции Гаусса. Возможности вейвлет-фильтрации сигнала сложной комбинированной формы наглядно демонстрируется на рис.9-13. Исходный сигнал, изображенный на рис.9., состоит из комбинации низкочастотных колебаний с локальным i«j. *. .

Рис.9. Исходный сигнал Рис. 10. Зашумленный сигнал высокочастотным пакетом. На рис.10 показан результат зашумления этого сигнала гауссовым шумом с 20%-й амплитудой. Двумерный вейвлет-спектр результирующего сигнала при применения гауссового вейвлета g2 показан на рис.11. Большие по значению вейвлет-коэффициенты изображены точками большей светлости, меньшие - более темными.

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

1GO 200 зоо г

ЮО 200

ЗОО

400

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

4.1 Дискретное вейвлет-преобразование

Казалось бы, что идеальный инструмент анализа сигналов любого вида получен. Но, к сожалению, концепция непрерывного вейвлет-преобразования обладает своими недостатками. Параметры в а и Ь формуле (5) меняются непрерывно, что приводит к избыточному представлению спектра сигнала. В некоторых задачах это несомненно является плюсом, кроме того благодаря своей избыточности спектры непрерывного преобразования достаточно наглядны. Однако платой за эту избыточность является сравнительно невысокая скорость выполнения преобразования, требующая вычисления интегралов для каждого из значений обоих параметров а и Ь. Хотя в случае гауссовых вейвлетов интегрирование может быть выполненно аналитически, тем не менее в общем случае это не спасает от избыточности представления, и как правило соответственно невысокой скорости его выполнения. Кроме того, поскольку на практике все сигналы, с которыми имеют дело физики, и не только физики, имеют дискретную природу, то вопрос о целесообразности применения масштаба вейвлета, покрывающего к примеру полторы точки исходного сигнала остается открытым. Таким образом, мы видим, что более употребительной при компьютерных вычислениях с реальными данными должны быть дискретные вейвлет-преобразования. Необходимая дискретизация значений а и b осуществляется следующим образом: а = а™ ,b = па™;т,пеZ (6)

Видно, что с увеличением масштаба увеличивается и размер сдвига функции, поскольку интуитивно понятно, что при анализе с большим масштабом, более мелкие детали игнорируются. Дискретное вейвлет преобразование строится с помощью кратномасштабного анализа (МА — Multiresolution analysis), впервые описанного Маллатом (Mallat).

Основная идея MA состоит в представлении сигнала в виде совокупности его последовательных приближений. Теория кратномасштабного анализа относится к теории функциональных пространств. Под кратномасштабным анализом понимается описание пространства через последовательность непересекающихся иерархически вложенных подпространств Vm, объединение которых в пределе дает описываемое пространство. IКп = Y Ут = А (А) meZ meZ

Эти пространства должны обладать следующим свойством: Для любой функции f(x)e Vm принадлежащей подпространству, её сжатая версия должна принадлежать подпространству /(2*) е Vmx. Еще одно необходимое свойство, что существует такая функция ф(х) е V0, сдвиги Фо,п(х) - Ф(х -n),n<=Z которой образуют ортонормированный базис пространства. Из этого вытекает, что набор фп н (*) = 2~тП ф{2~т x-ri) функций образует ортонормированный базис соответственно пространства Vm. Следовательно, любая функция из L2(R) может быть представлена как предел к которому стремятся ее аппроксимации/^ в пространствах Vmr т.е. как видно мы имеем возможность анализа функции на различных масштабах. Фундаментальным, и до некоторой степени удивительным выводом кратномасштабного анализа является факт связи между вейвлетами и банком фильтров.

Действительно: ф{х) = $*00 е V0 с V,; ф00 = 2хп J] hJXn (х) = hj(2x - п) (7) л л

Уравнение (7) показывает эту связь и называется масштабирующим уравнением. Вейвлет-фунция возникает при рассмотрении дополнения одного из подпространств Vm до под пространства Vm.j. Vm.j=Vm® Wm. Базисную функцию обозначим через \|/. Очевидно, что поскольку Wm содержится в Vm.j, то \|/ можно представить как разложение. п

Итак, для дискретных сигналов концепция ДВП состоит в следующем: вместо первоначального набора коэффициентов мы получаем совокупность наборов, {{s„},{{dj „}}} которые и являются вейвлет-преобразованием сигнала, причем в отличие от избыточного спектра непрерывного преобразования, количество полученных коэффициентов равно их количеству в исходном массиве данных.

Коэффициенты s®„ - называются коэффициентами аппроксимации, a dp, деталями, соответствующими уровню разложения j. В итоге дискретное вейвлет-разложение функции выглядит как: (обозначения немного изменены для удобства)

N N^

2l L V = Фь,к (*,■ )+Z £ djk Wj,k (xi) (8

Ы1 7=1 k=l

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

Рис.13. Один шаг вейвлет разложения. При каждом шаге разложения, сглаженная версия сигнала, разлагается на новую, еще более сглаженную версию. Каждый из массивов вполовину меньше предыдущего. Итерируя эту процедуру, получаем разложение вида (8). Как уже упоминалось, выбор вейвлет-функций, по которым будет произведено разложение в результате итерационной процедуры, зависит от применяемых фильтров. Критериями для выбора фильтров и sO - original signal s1 - approximation | Г d1 - details s2 d2 - detailsjj s3 j d3 |

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

4.3 Разложение по вейвлет-пакетам Для частотно-временного анализа существует другой вид разложения - в вейвлет-пакеты. Главное отличие этого разложения в том, что на каждом шаге декомпозиции детали также подвергаются последующему original signal ss sd ds 1 dd ^

J | ssd | |sds || sdd | dss| |dsd| |dds| ddd| разложению. В результате каждый слой разложения покрывает примерно

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

Рис.15. Отчетливо видны составляющие сигнала.

4.4 Алгоритм распознавания номеров автомобилей по изображениям

Алгоритм распознавания номера автомобиля состоит из двух достаточно независимых этапов

• Нахождение и выделение части изображения, содержащей номер

• Непосредственное распознавание номера по его изображению.

В более детальном изложении последовательность необходимых шагов такова:

I. вейвлет-преобразование изображения; II. фильтрация в вейвлет-домене;

III. нахождение и выделение области номера;

IV. разбиение номера на сегменты и контрастирование фрагментов; V. распознавание фрагмента с помощью предварительно обученной искусственной нейронной сети

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

65 алгоритмам малоконтрастное изображение номера автомобиля с включенными фарами.(см. рисунок ниже)

Постановка нашей задачи с распознаванием номеров автомобилей, которые являются двумерными объектами, выглядит намного сложнее, чем фильтрация одномерных спектров. Поэтому мы, прежде всего, сократили размерность задачи, зафиксировав масштаб вейвлет-преобразования в значении, определяемом размерами области номера, частотой чередования черного и белого в этой области и порядком выбранного вейвлета. Например, для гауссова вейвлета 6-го порядка подходит масштаб равный 2, т.к. этого достаточно для описания номера. Кроме того, было проведено исследование нескольких типов как дискретных, так и непрерывных вейвлет-преобразований, различных семейств и порядков. Как и можно было предполагать, более результативными оказались симметричные; вейвлеты. Так среди дискретных вейвлет-преобразования наилучший результат дали вейвлеты семейства койфлетов, а среди непрерывных^ вейвлет-преобразований - гауссовы вейвлеты. Выполняя вейвлет-преобразование с фиксированным порядком каждой: строки исходного изображения, мы получаем, таким образом, не двумерный, а одномерный спектр. j- f| п м H.W4 (Mill* а) б)

Рис.16. Примеры линий вейвлет-преобразования для изображений с рис.17 и 22.

На рис.16 представлен два примера ^-преобразования для строк развертки изображения, проходящих через область номера, 16 а) - для рис.17 и 16 б) - для рис.18, где изображена машина с большой решеткой радиатора. Суммарное представление результатов g6 -преобразования для всех строк дает нам двумерный вейвлет-домен, показанный в правой части рисунков 17 и 18.

Рис.17. Изображение автомобиля и вид g6 -преобразования, выполненного для каждой строки развертки этого изображения

Рис. 18 Изображение автомобиля с большим радиатором и его вейвлет-отображение Чтобы описать чередование черных и белых полос в области номера, соответствующие вейвлет-коэффициенты должны быть достаточно большими, что на рис.16 а) отражается в виде характерного плато с крутыми склонами. Это свойство вейвлет-образа, характерное для области номера, и нужно использовать далее в процедуре поиска этой области. Пришлось сразу же отказаться от простого порогового обрезания по величине вейвлет-коэффициентов, т.к. например на рис 16 б) преобразование от изображения решетки радиатора, дало большие значения коэффициентов. Нужно было найти критерий, отражающий наличие плато определенного размера, симметричного и с крутыми склонами с обеих сторон.

4.4.2 Бинаризация пикселей в вейвлет-домене для выделение области номера

Вышеотмеченная крутизна границ области вейвлет-коэффициентов, соответствующей номеру может быть детектирована по большим значениям второй производной. Однако вместо сложной с вычислительной точки зрения процедуры вычисление вторых производных для каких-то двумерных подобластей растровых изображений мы предпочли использовать метод бинаризации вейвлет-пикселей с последующим применением специального клеточного автомата (КА) для кластеризации. При бинаризации все пиксели вейвлет-изображения упорядочиваются по уровням серого. Затем нижние 70% становятся черными (=0), а верхние 30% - белыми (=1, см. рис.19 а). Дисциплина выживания каждой белой клетки КА в зависимости от восьми ее соседей, организована так, чтобы «выживала» слитная группа единичных пикселей, соответствующая области номера, а окружающие её отдельные единицы вымирали. Как видно из рис. 19 б)-в) после работы КА на краях вейвлет-изображения могут остаться какие-то бесформенные единичные участки, но они легко а б в

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

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

Рис.20. Изображение того же автомобиля, что и на рис.17, но с включенными фарами, а также вид построчного g6 -преобразования На рис.20-21 показаны также этапы распознавания по выделению области изображения с номером автомобиля для картинки, менее контрастной из-за включенного света фар и, вдобавок, идущей под углом.

Рис.21. Этапы выделения области изображения с рис 20, содержащей номер: а) после бинаризации; б) -в) два шага эволюции клеточного автомата

4.4.3 Представление результатов первого этапа

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

Рис.22. Выделенные области с номером а) для изображения рис. 17 и б) - для изображения с рис.18.

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

Рис.23. Выделение области изображения, содержащей номер товарного вагона: а) исходное изображение, б) его вейвлет-образ, в) выделенный номер 4.4.4 Контрастирование фрагментов и разбиение номера на сегменты Контрастирование фрагмента изображения с номером позволяет увеличить эффективность распознавания. Оно производится следующим образом: строится гистограмма всех пикселей фрагмента и вычисляются среднее и стандартное отклонение их интенсивностей по цвету. Как видно из фрагментов, приведенных на рис. 22 основным на них является серый цвет, поэтому, если в гистограмме вырезать центральную часть, отстоящую влево и вправо от среднего на величину среднеквадратичного значения, и приписать черный цвет пикселям из меньшей группы, а белый - большим по амплитуде, то контрастность резко возрастет, как это показано на рис.24. предварительно обученной искусственной нейронной сети.

Рис.24. Контрастированное изображение

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

1 23 45 67 8 90 выделенной части изображения. 1 2 3 4 5 6 7 8 9 0 ^

12 3 4 5 6 7 8 9 0 Распознавание фрагмента номера с помощью 1 2 3 4 5 6 7 8 9 0 1234 56 7 В 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 Для сравнения использовались различные 1 2 3 4 5 6 7 8 9 0

1 234567 89 0 нейронные сети, в том числе

1 2 3 4 5 6 7 8 9 0 тРехсл0^ны^ персептрон, а также радиально

1 23 4 567890 базисная нейронная сеть с 1 2 3 4 5 6 7 8 9 0 самоорганизацией при обучении. Обучение нейронной сети проводилось на образцах известного шрифта программы Ms Word, предварительно "размытых" с помощью преобразования с гауссовым ядром для придания им полного сходства с реальными данными. Такое обучающее множество изображено на рисунке.

4.5 Алгоритм поиска адронных струй на основе вейвлет преобразования

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

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

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

Фильтрация в каждом из вейвлет-слоев проводится следующим образом: if\Wj\>k*RMS, Wj=0, где RMS- среднеквадратичное отклонение вейвлет коэффициентов слоя, а к - параметр зависящий от множественности. Алгоритм обладает тем преимуществом происходящим от свойств вейвлет преобразования что за один проход алгоритма находятся струи разной ширины. В случае стандартного алгоритма (CDF, UA1) размер конуса фиксируется заранее.

На простой модели с равномерным шумом было проверено, что UA1-style алгоритм, находит струи обнаруженные вейвлет алгоритмом только при ручной подстройки параметров алгоритма. encrgy(ata,pht) h2 Jet | wavclot(ola.phl) h2 Jet

ElTiif'лл 114

А -1Ш

Ч>. j i > у 17В.Т

- VS х S.H1

SVS i 104.1

Рисунок 27. Выделенная алгоритмом смоделированная струя. wavalol(61a.phi) | h-2 jet r«i"i*a §12

Mean я ^.£•5348

Moat* у 1Т9

Ш8* 5.340 у 104

Рисунок 28. Сильный статистический выброс принятый за струю.

Рисунок 29. Алгоритм выделил все четыре смоделированные струи адронов Рисунки 30-31 ниже иллюстрируют способность алгоритма работать со струями разной ширины.

I energy(Bta.phl) | h2J»t

Ел trie* 59

Mean « 2.614

Mean у 92.67

RMS* 2.51 Г

RMS у 27.35 encrgv(eta.phl) |

I h2iel J

Entne* 5Ы

Mean x -0.2586

Mean у 174.4

RMS x 5.475

RMS у Ю0.8

Рисунок 30. Слева: две смоделированные струи адронов разной ширины. Справа: к событию добавлен равномерный шум в 10 раз превосходящий полезный сигнал на событие.

Рисунок 31. Результат работы вейвлет-алгоритма. Обе струи разной ширины выделены за один проход алгоритма.

Заключение

На защиту выносятся следующие результаты:

1. СНРБ-нейронная сеть и алгоритм обучения и ее программная реализация

2. программный пакет на языке С++ реализующий дискретный вейвлет-анализ и лифтинг схему.

3. алгоритм распознавания лица человека с использованием нейронной сети и МГК в качестве дополнительного слоя нейронов

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

Основные результаты диссертации опубликованы в следующих работах:

1. G.Ososkov, A.Stadnik, Face recognition by a new type of neural networks.in: "Advances in Neural Networks and Applications", Ed. N.Mastorakis, WSES Press(2001) 304-308.

2. G.Ososkov, A.Stadnik, Neural network application for the face recognition systems, CommJINR El 1-2000-269, Dubna, 2000.

3. G.Ososkov, A.Shitov, A.Stadnik, Comparative study of some of wavelets of the first and the second generations, CommJINR El 1-2001-38, Dubna, 2001.

4. Karmanova V., Ososkov G.A., Stadnik A.V., Filimonov A.V., Artificial neural networks and their application in medicine, International Summer Student School "NUCLEAR PHYSICS METHODS AND ACCELERATORS IN BIOLOGY AND MEDICINE", Ratmino near Dubna, June 27 - July 11,2001.

5. M.Altaisky, G.Ososkov, A.Shitov, A.Stadnik, Comparative study of some wavelets of the first and the second generations, Book of abstr. MTCP'2000, (2000), JINR, Dubna, 26.

6. G.Ososkov, A.Stadnik, Novel metric approach to neural network design with some applications, Book of abstr. MTCP'2000, (2000), JINR, Dubna, 124.

7. Karmanova, G.A. Ososkov, A.V. Stadnik, A.V. Filimonov, A.V. Kalabanova, Application of the neural networks for estimating significance of forecasting symptoms in breath diseases, book of "Fundumental Science and Progress in Clinical Medicine", Moscow, vol.2, pp. 156-157,2001 (in russian)

8. M.V.Altaisky, G.A.Ososkov, A.G.Soloviev, A.V.Stadnik, A.B.Shitov, . WASP (Wavelet Analisis of Secondary Particles angular distributions) package vl.2 long write up and user's guide, CommJINR ЕЮ-2001-205, Dubna, 2001

9. M.V.Altaisky, G.A.Ososkov, A.G.Soloviev, A.V.Stadnik, WASP JINRLIB XU007, http://ww.jinr.ru/~tsap/Koi/jinrlib/xu007/Xu007e.htm,

Dubna, 2001

10.GA.Ososkov, A.V.Stadnik, Effective neural network algorithms for experimental data processing, Optical Memory & Neural Networks, #3

11.Г.А.Ососков, А.В.Стадник, Эффективные нейросетевые алгоритмы для обработки экспериментальных данных, Информационные технологии и вычислительные системы, N 1 стр. 103-125, изд-во УРСС, Москва, 2004.

12.G.A.Ososkov, A.V.Stadnik Effective training algorithms for RBF-neural networks, Nucl. Instr. Meth. A502/2-3 (2003) 529-531,2003

Автор глубоко благодарен своему научному руководителю, доктору физико — математических наук, профессору Ососкову Геннадию

Алексеевичу за постоянную поддержку и помощь в работе, кандидату исторических наук Ососковой Инне Захаровне, доктору физико — математических наук Маурину Льву Николаевичу за поддержку и кандидату физико — математических наук

Озеровой Валентине Михайловне, оппоненту доктору физико — математических наук Ясинскому Федору Николаевичу, кандидату физико — математических наук Соловьеву Алексею Геннадьевичу за оказанное содействие, кандидату физико — математических наук Багиняну Сергею Агабековичу, кандидату физико ~ математических наук Сметанину Евгению Валентиновичу, доктору физико ~ математических наук Панебратцеву Юрию Анатольевичу, а также всем сотрудникам НЭОФИ ЛВЭ ОИЯИ и и кафедры теоретической физики, математического и компьютерного моделирования ИвГУ за поддержку.

Список литературы

1]И.В.Кисель, В.Н.Нескоромный, Г.А.Ососков, Применение нейронных сетей в экспериментальной физике // ЭЧАЯ, т.24, вып.6, 1993, 1551-1595.

2] Д.Лоули, А.Максвелл, Факторный анализ как статистический Метод,// М.,Мир, 1967.

3]Уоссермен Ф. Нейрокомпьютерная техника : Теория и практика.// М.: Мир. 1992.

4] Лоскутов А.Ю., Михайлов А.С. Введение в синергетику. // М.: Наука, Гл. ред. физ.-мат. лит., 1990.

5] Новые физические принципы оптической обработки информации: // Сборник статей Под ред. С.А. Ахманова и М. А. Воронцова. - М.: Наука. Гл. ред. физ.-мат. лит., 1990.

6] Горбань А.Н. Обучение нейронных сетей. // М.: СП Параграф. 1991.

7] Барцев С.И., Гилев С.Е., Охонин В.А. Принцип двойственности в организации адаптивных сетей обработки информации // Динамика химических и биологических систем. Новосибирск: Наука, 1989, стр.655.

8] Барцев С.И., Охонин В.А. Адаптивные сети обработки информации.// Красноярск : Ин-т физики СО АН СССР, 1986. Препринт N 59Б. - 20с.

9] {barcev3 } Барцев С.И. Некоторые свойства адаптивных сетей (Программная реализация). // Красноярск: Ин-т физики СО АН СССР, 1987. Препринт No.71 Б. - 17 с.

10] Ю.К. Ахапкин, С.И. Барцев, Н.Н. Всеволодов и др. Биотехника -новое направление компьютеризации//М.: Наука, 1990. - 144 с.

11] Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. // М.: Мир, 1985. - 509 с.

12] Евтихиев Н.Н., Оныкий Б.Н., Перепелица В.В., Щербаков И.Б. Многослойная нейронная сеть и ее реализация на основе оптического вектор-матричного перемножителя // Нейрокомпьютер, No. 1-2, 1994.

13] Евтихиев Н.Н., Оныкий Б.Н., Перепелица В.В., Щербаков И.Б. Математические модели и оптические реализации многослойных и полиномиальных нейронных сетей. // Препринт/МИФИ, 004-94, 1994. -32 с.

14] Колосов А.И., Щербаков, И.Б., Кисленко Н.А., Кисленко О.П., Варивода Ю.В. и др.,"Создание аналитического обзора информационных источников по применению нейронных сетей для задач газовой технологии";//ВНИИГАЗ, 1995.

15] N.M. Astafyeva, I.M. Dremin, К.А. Kotelnikov// Mod. Phys. Lett., 1997, v. A12, p. 1185; I.M. Dremin et al.// hep-ph/0007060; И.М. Дремин // УФН, 2000, т. 170, с. 1235.

16] В.В.Ужинский, Г.А.Ососков, А.Полянский и др. Вейвлет-анализ угловых распределений вторичных частиц в ядро-ядерных взаимодействиях при высоких энергиях // Сообщ.ОИЯИ, Дубна, 2001.

17] Компьютерра, N8 (236), 1998. 18] S. Wolfram (ed.), Theory and applications of cellular automata // World Scientific, 1986.

19] C.Peterson et al, JETNET 3.0 - A versatile artificial neural network package // LU TP 93-29,1993; CERN-TH 7135/94

20] C.Lindsey et al, Experience with the IBM ZISC036 neural network chip, // Proc. of IV Intern. Workshop on Software Engineering and Artificial Intelligence and Expert Systems for High Energy and Nuclear Physics, Pisa, Italy, 3-8 April 1995, ed. by B.Denby & D.Perret-Gallix, World Sci., Singapore, (1995), pp 371 -376.

21] C.Lindsey, Th.Lindblad, Review of hardware neural networks: a user's perspective, // Intern. Journ. of Neural Systems, v.6 (Suppl.) (1995).

22] Nucl. Instr. Meth. A 389,1997.

23] Intern. Journ. of Neural Systems, v.6 (Suppl.) (1995) 269-274.

24] New Computing Techniques in Physics Research, Proc. of VI Intern. Workshop on Software Engineering, // Artificial Intelligence and Expert Systems, Heraclion Crete (Greece) April 12-16 1999, ed. by G.Athanasiu & D.Perret-Gallix, Papisianou, Athene (2000).

25] VIII International Workshop on Advanced Ccomputing and Analysis Techniques in Physics Research (ACAT2002) 24-28 June, 2002, Moscow, Russia, http://acat02.sinp.msu.ru

26] J.Hopfield, Learning Algorithms and Probability Distributions in Feedforward and Feed-back Networks // Proc.

Nat. Acad. Sci. USA, 84,1987, p.8429.

27] J.Hopfield, Neural Networks and Physical Systems with Emergent Collective Computational Abilities // Proc. Nat. Acad. Sci. USA, 79, 1982, p.2554.

28] J.Hopfield, Neurons with Graded Responces Have Collective Computational Properties Like Those of Two-State

Neurons // Proc. Nat. Acad. Sci. USA, 81,1984, p.3088.

29] Kirkpatrick S. et al: Optimization by simulated annealing // Science 220 (1983), 671-680.

30] C.Peterson, Track finding with neural networks // Nucl. Instr. and Meth. A279,p.537, 1986.

31] B.Denby, Neural networks and cellular automata in experimental high energy physics // Comput. Phys. Commun., 49, p.429,1988.

32] G.Ososkov et al, Neural Network Applications for Efficiency Improving of Geometric Reconstruction of Events Detected in the EXCHARM Experiment at the JINR // Proc. of VI Intern. Workshop on Software Engineering, Artificial Intelligence and Expert Systems, Heraclion Crete (Greece) April 12-16 1999, ed. By G.Athanasiu \& D.Perret-Gallix, Parisianou, Athene (2000) 126-131.

33] C.Peterson, Preprint.LU TP 90 - 6 // Lund (1990).

34] {18} S .Baginyan et al., Tracking by modified rotor model of neural network // Сотр. Phys. Comm., 79 (1994) 165

35] I.Galkin, P.Neshuba, G.Ososkov, B.W.Reinush, E.Zaznobina, Feedback neural networks for ARTIST ionogram processing // Radio Science v.31, n 5 (1996) 1119-1128.

36] G.Ososkov, Robust tracking by cellular automata and neural network with non-local weights, in Applications and Science of Artificial Neural Networks // S. K. Rogers, D. W. Ruck, Editors, Proc. SPIE 2492, (1995) 1180-1192.

37] Grozov V.P., Ososkov G.A., Zaznobina E.G. and Nosov V.E., Automatic Processing of Ionograms on the basis of the artifical neural network method // Proceedings of 1997 International Symposium on Radio Propagation (ISRP'97), Qingdao, China (1997) 514 - 517.

38] M.Gyulassy and M.Harlander, Elastic tracking and neural networks algorithms for complex pattern recognition // Comp.Phys.Comm. 66, 1991, 31-46.

39] M. Ohlsson, C. Peterson, A. Yuille, Track finding with deformable templates - the elastic arms approach // Comput. Phys. Commun. 71, (1992), 77.

40] L. Muresan, R. Muresan, G. Ososkov, Yu. Panebratsev, Deformable Templates for Circle Recognition // JINR Rapid Communications, 1 [81]-97, Dubna, 1997,27-44.

41] S.Baginyan, G.Ososkov, Finding tracks detected by a drift tube system // Comp.Phys.Comm, v. 108 No 1 (1998), 20-28.

42] Hough P. V. C. A Method and Means for Recognizing Complex Patterns. // US Patent: 3,069,654,1962.

43] Toft P. The Radon Transform. Theory and Implementation. // Ph.D. Thesis,Department of Mathematical Modelling, Section for Digital Signal Processing, Technical University of Denmark, 1996. http://www.ei.dtu.dk/staff/ptoft/ptoft.html

44] Haykin, Neural networks: a comprehensive foundation // MacMillan Coll.Publ.Co.,N-Y, 1994.

45] G.Ososkov, A.Stadnik, Face recognition by a new type of neural networks // in: "Advances in Neural Networks and Applications", Ed. N.Mastorakis, WSES Press, Hellenic Naval Academy, Athene, Greece, (2001) 304-308

46] RChellappa et al, // Proc.IEEE v.83 No.5,1995, pp. 704-740

47] ( H.Liu et al, // Opt.and Lasers, in Engeneer., V.30,1998, pp. 305-314

48] K.S.Yoon at al, Pattern Recogn. Vol.3,1998, pp. 283-293

49] Cambridge face data base, ftp://ftp.uk.research.att.com:pub/data/attfaces.zip

50] ROOT Library, http://www.root.cern.ch

51] Lippman R.P. An introduction to computing with neural nets // IEEE ASSP Magazine. Apr. 1987. P.4-22.

52] Holland J. Adaptation in Natural and Artificial Systems // University of Michigan Press, 1975.

53] Holland J. The dynamics of searches directed by Genetic Algorithms. // In: Lee Y.S. (ed.) Evolution, Learning and Cognition. - Word Scientific, Singapore, 1988.

54] Goldberg D. Genetic Algorithms in Machine Learning, Optimization, and Search. // Addison-Wesley, 1988.

55] Montana D.J. and Davis L. Training feedforward neural networks using genetic algorithms. // Preprint, BBN Systems and Technologies, Cambridge, Mass., 1989.

56] International workshop on combination of genetic algorithms and neural networks (1992; Baltimore, Md), June 6,1992. // COGANN-92; Ed.L.P. Whitley, J.P. Schoffer, Los Alamatic (Ca) et al.: IEEE computer, soc. press, 1992. - VIII, 262p.

57] H.M. Астафьева // УФН, 1996, т. 166, с. 1145.

58] Jones A.J. Genetic algorithms and their applications to the design of neural networks // Neural computing and applications, v.l, no. 1,1993. (Есть в фонде ГПНТБ.)

59] Radcliffe N.J. Genetic set recombination and its application to neural network topology optimization // Neural computing and applications, v.l, no. l,pp. 67-90. 1993.

60] Haines K., Hecht-Nielsen R. A BAM with increased information storage capacity // Proceedings of the International Conference on Neural Networks,vol. 1, San Diego, CA: SOS Printing, 1988, pp. 181-190.

61] Hecht-Nielsen R. Theory of the backpropagation neural network // International joint conference on neural networks, Sheraton Washington Hotel, Washington D.C., June 18-22, vol. 1, 1989, p. 593-606.

62] Ackley D.H., Hinton G.E., Sejnowski T.J. A Learning Algorithm for Boltzmann Machines.// Cognitive Science, 9, 1985, pp.147-169.

63] Almeida L.B. A learning rule for asynchronous perceptions with feedback in a combinatorial environment // Proc. 1st IEEE Intl. Conf. on Neural Networks, vol. 2, pp. 609-618, San Diego, CA, June 1987.

64] Burr D.J. Experiments with a connectionist text reader // In Proceddings of the IEEE First International Conference on Neural Networks, eds. Caudill M., Butler C. vol 4, 1987, pp. 717-724. San Diego, CA: SOS Printing.

65] Cottrell G.W., Munro P. and Zipser D. Learning Internal Representation from Gray-Scale Images: An Example of Extensional Programming. // In Proc. 9th Annual Conference of the Cognitive Science Society, 1987, pp. 461473.

66] Dennis J., Schnabel R. Numerical Methods for Unconstrained; Optimization and Nonlinear Equations. // Englewood Cliffs, NJ: Prentice-Hall, 1983.

67] Gilev S.E., Gorban A.N., Mirkes E.M. Several methods for acceleration the training process of neural networks in pattern recognition. // USSR Academy of Sciences, Siberian Branch, Institute of Biophysics, Krasnoyarsk, 1990. Preprint N 146 Б.

68] Gorman R.P., Sejnowski T.J. Analysis of Hidden Units in a Layered Network Trained to Classify Sonar Targets. // Neural Networks, 1, pp.75-89.

69] Guyon L, Poujaud I., Personnaz L., Dreyfus G., Denker J. and Le Cun Y. Comparing different neural network architectures for classifying handwritten digits. // In Proc. IEEE Int. Joint Conf. Neural Networks, June 1989.

70] Jones W.P., Hoskins J. Back-Propagation, A Generalized Delta Learning Rule // BYTE Magazine. Oct. 1987.

71] Jordan M. Generic constraints on underspecified target trajectories. // In Proc. IEEE Int. Joint Conf. Neural Networks, June 1989.

72] Kawato M. Computational schemes and neural network models for formation and control of multijoint arm trajectory. // In W.T. Miller, R. Sutton, and P. Werbos, Eds. Neural Networks for Robotics and Control. Cambridge, MA: M.I.T. Press, 1990.

73] Muller В., Reinhardt J. Neural networks.// Springer-Verlag. 1990. 267p.

74] Narendra K.S., Parthasarathy K. Identification and control of dynamical systems using neural networks. // IEEE Trans. Neural Networks, vol.1, pp.427, Mar. 1990.

75] Narendra R. Adaptive control using neural networks. // In W.T. Miller, R. Sutton, and P. Werbos; Eds. Neural Networks for Robotics and Control. Cambridge, MA: M.I.T. Press, 1990.

76] Neural Computing: NeuralWorks Professional II/Plus and NeuralWorks Explorer. // NeuralWare, Inc., 1991.355 p.

77] Nguyen D., Widrow B. The truck backer-upper:

An example of self-learning in neural networks. // In W.T. Miller, R. Sutton, and P. Werbos, Eds. Neural Networks for Robotics and Control. Cambridge, MA: M.I.T. Press, 1990.

78] Pearlmutter B. Learning state space trajectories in recurrent neural network // In Proc. 1988 Connectionist Models Summer School, D. Touretzky, G. Hinton, and T. Sejnowski, Eds. June 17-26, 1988, pp. 113-117. San Mateo, CA: Morgan Kaufmann. And in Proc. Int. Joint. Conf. Neural Networks, June 1989.

79] Pineda F.J. Generalization of backpropagation to reccurent neural. networks. // In Phys. Rev. Lett., vol. 18, pp. 2229-2232,1987.

80] Pineda F.J. Generalization of backpropagation to reccurent and higher order networks. // In Proc. IEEE Conf. Neural Inform. Processing Syst., 1987, and in Neural Information Processing Systems, ed. D.Z. Anderson, pp. 602611. New York: American Institute of Phisycs. 1988.

81] Rosenberg C.R. Revealing the structure of NETtalk's Internal Representations. // In Proc. 9th Annual Conference of the Cognitive Science Society, 1987, pp. 537-554.

82] Rumelhart D.E., Hinton G.E., Williams R. J. Learning Internal Representations by Error Propagation. // In Parallel Distributed Processing, vol. 1, pp. 318-362. Cambridge, MA, MIT Press. 1986.

83] Rumelhart D.E., HintonG.E., Williams R.J. Learning Representations by Back-propagating Errors, // Nature vol. 323, p. 533. 1986.

84] Sawai H., Waibel A., Haffner P., Miyatake M. and Shikano K. Parallelism, hierarchy, scaling in time-delay neural networks for spotting Japanese phonemes CV-syllables. // In Proc. IEEE Int. Joint Conf. Neural Networks, June 1989.

85] Sejnowski T J, Rosenberg C.R. Parallel Networks that Learn to Pronounce English Text. // Complex Systems, 1,1987, p. 145-168.

86] Shanno D. Conjugate-gradient methods with inexact searches. // Math. Oper. Res., vol. 3, Aug. 1978.

87] Shanno D. Recent advances in numerical techniques for large-scale optimization. // In W.T. Miller, R. Sutton, and P. Werbos, Eds. Neural Networks for Robotics and Control. Cambridge, MA: M.I.T. Press, 1990.

88] Stornetta W.S., Huberman B.A. An improved three-layer, backpropagation algorithm. // In Proceedings of the IEEE First Conference on

Neural Networks, eds. M. Caudill and C. Butler. San Diego, CA: SOS Printing. 1987.

89] Wasserman P.D. Combined backpropagation Cauchy machine. // Proceedings of the International Neural Network Society. New York: Pergamon Press, 1988.

90] Wasserman P.D. Experiments in transtating Chinese characters using backpropagation. // Proceedings of the Thirty-Third IEEE Computer Society International Conference. Washington, D.C.: Computer Society Press of the IEEE. 1988.

91] Watrous R., Shastri L. Learning phonetic features using connectionist networks: an experiment in speech recognition. // In Proc. 1st IEEE Int. Conf. Neural Networks, June 1987.

92] Werbos P. Applications of advances in nonlinear sensitivity analysis. // In R. Drenick and F. Kozin, Eds., Systems Modelling and Optimization: Proc. 10th IFIP Conf. (1981). New York: Springer-Verlag, 1982.

93] Werbos P. Learning how the word works: Specifications for predictive networks in robots and brains. // In Proc. 1987 IEEE Int. Conf. Syst, Ma, Cybern., 1987.

94] Werbos P. Consistency of HDP applied to a simple reinforcement learning problem// Neural Networks, Mar. 1990.

95] Werbos P. Generalization of backpropagation with application to a recurrent gas market model, // Neural Networks, Oct. 1988.

96] Werbos P.J. Backpropagation through time: what it does and how to do it // Proceedings of the IEEE, vol. 78, No. 10, October, 1990, p. 1550-1560.

97] Werbos P. Maximizing long-term gas industry profits in two minutes in Lotus using neural networks methods. // IEEE Trans. Syst., Man, Cybern., Mar./Apr. 1989.

98] Widrow В., Lehr M.A. 30 years of adaptive neural networks: perceptron, madaline, and backpropagation // Proceedings of the IEEE, vol. 78, No. 9, September, 1990, p. 1415-1442.

99] Williams R. Adaptive state representation and estimation using recurrent connectionist networks. // In W.T. Miller, R. Sutton, and P. Werbos, Eds. Neural Networks for Robotics and Control.

Cambridge, MA: M.I.T. Press, 1990.

100] Kosko B.Bi-directional associative memories // IEEE Transactions on Systems, Man and Cybernetics 18(1), 1987, pp.49-60.

101] Kosko B. Competitive adaptive bi-directional associative memories. // In Proceedings of the IEEE First International Conference on Neural Networks, eds. M. Caudill and C. Butler, vol. 2, San Diego, CA: SOS Printing, 1987, pp. 759-766. 102] Kosko В., Guest C. Optical bi-directional associative memories // SPIE Proceedings: Image Understanding, 758:11 -18,1987. 103] Kosko B. Unsupervised learning in noise // IJCNN Proc. vol. 1, San Diego, CA: SOS Printing, 1989, pp. 7-18.

104] Neural Computing: NeuralWorks Professional II/Plus and NeuralWorks Explorer. NeuralWare, Inc., 1991.355 p.

105] Hecht-Nielsen R. Counterpropagation networks // Applied Optics, 26(23), 1987, pp. 4979-84.

106] Hecht-Nielsen R. Applications of counterpropagation networks // Neural Networks, 1, 1988, pp. 131-39.

107] S.Thurner, M.Feurstein, M.Teich Multiresolution Wavelet Analysis of Heartbeat Intervals Discriminates Healthy Patients from Those with Cardiac Pathology. // Physical Review Letters, vol.80 (1998), pp. 1544-1547. 108] W.Sweldens, I.Daubechies Factoring Wavelet Transforms into Lifting Steps. // Fourier Analysis Applications, vol.4 (1998), pp.247-269.

109] W.Sweldens. Wavelets and Lifting Scheme: A 5 minute tour, I I Zeitschnift fur Angewandte Mathematik und Mechanik, vol.76(Suppl.2) (1996), pp. 41-44.

110] Mallat S. A theory for multiresolution signal decomposition: the wavelet representation. // IEEE Trans. Pattern Analysis and Machine Intelligence, 1989, N7, pp.674-693;

111] I. Daubechies Editor, Proc.of Symp. in Appl. Math, V47,1993.

112] W. Sweldens, P. Schroder. Building your own wavelets at home in "Wavelets in Computer Graphics", // ACM SIGGRAPH Course Notes, 1996, pp. 15-87.

113] G.Ososkov, A.Shitov Gaussian Wavelet Features and Their Applications for Analysis of Discretized Signals // Comp.Phys.Comm, v. 126/1-2, (2000) 149-157, см.также Сообщ. ОИЯИ PI 1-97-347, Дубна, 1997.

114] M.V.Altaisky, E.A.Kolganova V.E.Kovalenko, G.A.Ososkov // The InternationalSociety for Optical Engineering, Proc. SPIE'96, v.2847 (1996) 656-664.

115] E.Kolganova, E.Kosarev, G.Ososkov Superresolution algorithms for data analysis of discrete detectors in nuclear physics // Nucl.Instr.Meth. A443/2-3 (2000)464-477.

116] G.Ososkov, A.Shitov, A.Stadnik, Comparative study of some of wavelets of the first and the second generations // Comm.JINR El 1-2001-38, Dubna, 2001.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Стадник, Алексей Викторович

На защиту выносятся следующие результаты:

1. СНРБ-нейронная сеть и алгоритм обучения и ее программная реализация

2. программный пакет на языке С-Н- реализующий дискретный вейвлет анализ и лифтинг схему.3. алгоритм распознавания лица человека с использованием нейронной сети и МПС в качестве дополнительного слоя нейронов

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

1. G.Ososkov, A.Stadnik, Face recognition by a new type of neural networks.in: "Advances in Neural Networks and Applications", Ed. N.Mastorakis, WSES Press(2001) 304-308.2. G.Ososkov, A.Stadnik, Neural network application for the face recognition systems, Conmi.JINR El 1-2000-269, Dubna, 2000.3. G.Ososkov, A.Shitov, A.Stadnik, Comparative study of some of wavelets of the first and the second generations, Comm.JINR El 1-2001-38, Dubna, 2001.4. Karmanova v., Ososkov G.A., Stadnik A.V., Filimonov A.V., Artificial neural networks and their application in medicine, International Summer Student School "NUCLEAR PHYSICS METHODS AND ACCELERATORS IN BIOLOGY AND MEDICINE", Ratmino near Dubna, June 27 - July 11,2001.5. M.Altaisky, G.Ososkov, A.Shitov, A.Stadnik, Comparative study of some wavelets of the first and the second generations. Book of abstr. MTCP'2000, (2000), JINR, Dubna, 26.6. G.Ososkov, A.Stadnik, Novel metric approach to neural network design with some applications. Book of abstr. MTCP'2000, (2000), JINR, Dubna, 124.7. Karmanova, G.A. Ososkov, A.V. Stadnik, A.V. Filimonov, A.V. Kalabanova, Application of the neural networks for estimating significance of forecasting symptoms in breath diseases, book of "Fimdumental Science and Progress in Clinical Medicine", Moscow, vol.2, pp. 156-157,2001 (in russian)

8. M.V.Altaisky, G.A.Ososkov, A.G.Soloviev, A.V.Stadnik, A.B.Shitov, .WASP (Wavelet Analisis of Secondary Particles angular distributions) package vl.2 long write up and user's guide, Comm.JINR ElO-

2001-205, Dubna, 2001

9. M.V.Altaisky, G.A.Ososkov, A.G.Soloviev, A.V.Stadnik, WASP JINIILIB XU007, http://www.jinr.ru/tsap/Koi/jinrlib/xu007/Xu007e.htm, Dubna, 2001

10.G.A.Ososkov, A.V.Stadnik, Effective neural network algorithms for experimental data processing, Optical Memory & Neural Networks, #3

11.Г.А.0С0СК0В, А.В.Стадник, Эффективные нейросетевые алгоритмы для обработки экспериментальных данных, Информационные технологии и вычислительные системы, N 1 стр. 103-125, изд-во УРСС, Москва, 2004.12.G.A.Ososkov, A.V.Stadnik Effective training algorithms for RBF-neural networks, Nucl. Instr. Meth. A502/2-3 (2003) 529-531,2003 Автор глубоко благодарен своему научному руководителю, доктору физико — математических наук, профессору Ососкову Геннадию Алексеевичу за постоянную поддержку и помощь в работе, кандидату исторических наук Ососковой Инне Захаровне, доктору физико математических наук Маурину Льву Николаевичу за поддержку и кандидату физико — математических наук Озеровой Валентине Михайловне, оппоненту доктору физико — математических наук Ясинскому Федору Николаевичу, кандидату физико математических наук Соловьеву Алексею Геннадьевичу за оказанное содействие, кандидату физико математических наук Багиняну Сергею Агабековичу, кандидату физико математических наук Сметанину Евгению Валентиновичу, доктору физико математических наук Панебратцеву Юрию Анатольевичу, а также всем сотрудникам НЭОФИ ЛВЭ ОИЯИ и и кафедры теоретической физики, математического и компьютерного моделирования ИвГУ за поддержку.