Сети адаптивной резонансной теории

Основы искусственного интеллекта зм Лекция 3 СЕТИ АДАПТИВНОЙ РЕЗОНАНСНОЙ ТЕОРИИ Проблема стабильности-пластичности Восприятие внешнего мира человеком связано с решением определенной дилеммы. Зачастую требуется определить: является ли некоторый образ "новой" информацией, требующей сохранения в памяти, либо этот образ является "старой", уже знакомой картиной, и в этом случае запоминание этого образа не требуется. Таким образом, восприятие человека одновременно пластично, адаптировано к новой информации, и при этом оно стабильно, то есть не разрушает память о старых образах. Человеческая память, эффективно хранит и корректирует запоминаемые образы. Ни предъявление нового образа, ни изменение старых не приводит к уничтожению памяти или невозможности запоминания. Большинство нейронных сетей не приспособлены к решению этой задачи. Например, многослойный персептрон, обучающийся методом обратного распространения, запоминает весь набор обучающей информации. Образы из обучающей выборки многократно предъявляются сети в процессе обучения. Если полностью обученный персептрон должен запомнить новый обучающий образ, он может изменить веса настолько, что потребуется полное переобучение сети. Таким образом, персептрон не способен к запоминанию новой информации без разрушения памяти о ранее запомненных образах. Более того, в реальной ситуации ИНС может никогда не увидеть один и тот же обучающий образ дважды. При таких обстоятельствах сеть зачастую не будет обучаться; она будет непрерывно изменять свои веса, не достигая удовлетворительных результатов. В сетях адаптивной резонансной теории (АРТ) предпринимается попытка приблизить механизм запоминания образов в ИНС к биологическому. Результатом работы АРТ является устойчивый набор запомненных образов и возможность выборки "похожего" образа по произвольному вектору, предъявленному на вход сети. Важное качество АРТ динамическое запоминание новых образов без полного переобучения и отсутствие потерь уже запомненных образов при предъявлении новых. Математическое описание APT является сложным, но основные идеи и принципы реализации достаточно просты для понимания. АРТ включает несколько моделей, каждая из которых определяется формой входных данных и способом их обработки. Модель АРТ1 разработана для обработки двоичных входных векторов. Более поздние обобщения этой модели могут классифицировать как двоичные, так и непрерывные векторы. Здесь рассматривается только модель АРТ-1. Основы искусственного интеллекта зм Архитектура АРТ Упрощенная схема АРТ Сеть APT представляет собой векторный классификатор. Входной вектор классифицируется в зависимости от того, на какой из множества ранее запомненных образов он похож. Свое классификационное решение сеть APT выражает в форме возбуждения одного из нейронов распознающего слоя. Если входной вектор не соответствует ни одному из запомненных образов, создается новая категория посредством запоминания образа, идентичного новому входному вектору. Если входной вектор похож, с точки зрения определенного критерия сходства, на один из ранее запомненных векторов, то этот запомненный вектор будет изменяться (переобучаться) таким образом, чтобы стать более похожим на новый входной вектор. Запомненный образ не будет изменяться, если текущий входной вектор не окажется достаточно похожим на него. Таким способом решается дилемма стабильностипластичности. Новый образ может создавать дополнительные классификационные категории, однако новый входной образ не может изменить существующую память. На рис.6.1 приведена упрощенная конфигурация сети APT, представленная в виде пяти функциональных модулей. Она включает два слоя нейронов - «слой сравнения» и «слой распознавания». Приемник 1 (Пр1), Приемник 2 (Пр2) и Сброс обеспечивают управляющие функции, необходимые для обучения и классификации. Рассмотрим функции каждого модуля. Рис.6.1. Упрощенная сеть АРТ Слой сравнения Слой сравнения получает двоичный входной вектор Х и первоначально пропускает его без изменения для формирования выходного вектора C=X. На более поздней фазе распознавания двоичный вектор R, модифицирует вектор C, в результате C≠X . Каждый нейрон в слое сравнения (рис. 6.2) получает три двоичных входа (0 или 1): 1. Первая компонента - хi входного вектора X; 2. Вторая компонента - реакция распознающего слоя pi = rk tki; 3. Третья компонента - вход от Пр1 (один и тот же сигнал подается на все нейроны этого слоя). Основы искусственного интеллекта зм Рис.6.2. Слой сравнения Чтобы получить на выходе нейрона единичное значение, как минимум два из трех его входов должны равняться единице; в противном случае его выход будет нулевым, т.е. реализуется правило «2 из 3-х». Первоначально выходной сигнал Пр1 G1=1 обеспечивает один из необходимых для возбуждения нейронов входов, а все компоненты вектора R установлены в 0; следовательно, в этот момент вектор C идентичен двоичному входному вектору X. Слой распознавания Слой распознавания осуществляет классификацию входных векторов. Число нейронов этого слоя соответствует числу запомненных образов - n (категорий классификации). Значение n увеличивается по мере запоминания новых категорий. В каждый момент времени в слое распознавания возбуждается только один нейрон с наибольшим уровнем активации. На выходе этого нейрона устанавливается единичный уровень сигнала rk = 1. Все остальные нейроны заторможены и имеют нулевой уровень сигнала на выходе ri = 0, где i ≠ k. Это правило называется «победитель забирает все». Рис.6.2. Слой распознавания Основы искусственного интеллекта зм Каждый нейрон k в слое распознавания имеет соответствующий вектор весов Bk.(рис.6.3). Эти веса являются действительными числами, а не двоичными величинами. Нейрон k имеет максимальную реакцию, если вектор C, являющийся выходом слоя сравнения, наилучшим образом соответствует набору его весов. Следовательно, веса Bk представляют запомненный образ или экземпляр для категории входных векторов. Двоичная версия этого образа также запоминается в соответствующем наборе весов - Tk (рис.6.2). В процессе функционирования каждый нейрон слоя распознавания вычисляет свертку вектора собственных весов Bk и входного вектора C. Нейрон, имеющий веса, наиболее близкие вектору C, будет иметь самый большой выход, тем самым выигрывая соревнование у всех остальных нейронов в слое. Конкуренция между нейронами, как правило, реализуется введением связей с отрицательными весами lik с выхода каждого нейрона rk на входы остальных нейронов. Таким образом, если нейрон имеет большой выходной сигнал, то он тормозит все остальные нейроны в слое. Кроме того, каждый нейрон имеет связь с положительным весом со своего выхода на свой собственный вход. Если нейрон имеет на выходе большой уровень сигнала, то эта обратная связь стремится усилить и поддержать его. Для простоты, обратные связи между нейронами не показаны на схеме слоя распознавания (рис.6.3). Модули приемников и сброса Выходной сигнал Приемника1 G1=1, если хотя бы одна компонента xi двоичного входного вектора X равна единице. Однако, если хотя бы одна компонента rk вектора R равна единице, то G1=0. Правило формирования сигнала G1 определены в табл. 6.1. Выходной сигнал Приемника2 G2=1, если входной вектор Х имеет хотя бы одну единичную компоненту xi=1. Точнее, сигнал G2 является логическим «ИЛИ» от компонент вектора X (табл.6.1). Правила формирования сигналов Приемников Таблица 6.1 Логическое «ИЛИ» от компонент X x1 or …xi or…xm Логическое «ИЛИ» от компонент R r1 or …rk or…rn G1 G2 1 1 1 1 1 1 1 Модуль сброса измеряет сходство между векторами X и C. Мера сходства ρ вычисляется как отношение количества совпавших компонент в векторах C и X к количеству компонент m во входном векторе X. Если значение ρ меньше заданного порогового уровня, то вырабатывается сигнал сброса возбужденного нейрона в слое распознавания. Иначе, выходной сигнал победившего нейрона обнуляется rk=0. Основы искусственного интеллекта зм Функционирование сети АРТ В процессе классификации образов можно выделить пять основных фаз: инициализацию, распознавание, сравнение, поиск и обучение. Инициализация Перед началом процесса обучения сети АРТ все весовые векторы Bk и Tk, несвязанных нейронов, а также параметр сходства , должны быть установлены в начальные значения. Всем весам векторов Bk присваиваются одинаковые малые значения. Эти значения должны удовлетворять условию: bik < L / (L-1+m) для всех i, k, (6.1) где m – количество компонент входного вектора, L – константа, (обычно L ≥ 2). Такая установка весов гарантирует, что несвязанные нейроны не будут возбуждены более, нежели уже обученные нейроны в слое распознавания. Всем веса векторов Tk присваиваются единичные значения, так что tki = 1 для всех k,i,. (6.2) Значение параметра сходства  устанавливается в диапазоне от 0 до 1 в зависимости от требуемой степени сходства между запомненным образом и входным вектором. При высоких значениях  сеть относит к одному классу только очень слабо отличающиеся образы. Малое значение  заставляет сеть группировать образы, которые имеют слабое сходство между собой. В некоторых случаях можно изменять параметр сходства в процессе обучения. В начале процесса обучения обеспечивается грубая классификация, а затем значение  постепенно увеличивается для выработки точной классификации к концу обучения. Распознавание В начальный момент времени вектор X отсутствует на входе сети. Cледовательно, все компоненты входного вектора X можно рассматривать как нулевые xi = 0. Тем самым сигнал Пр2 устанавливается в G2=0 и, следовательно, выходы всех нейронов слоя распознавания rk = 0 (рис.6.3). Поскольку все нейроны слоя распознавания начинают работу в одинаковом состоянии, они имеют равные шансы выиграть в последующей конкуренции. Затем на вход слоя сравнения подается вектор X, который должен быть классифицирован. Этот вектор должен иметь одну или более компонент, отличных от нуля xi≠0, в результате чего сигнал Пр2 принимает значение G2=1. На этом этапе выходной вектор слоя распознавания отсутствует R = 0, поэтому сигнал Пр1 принимают значения G1=1 (табл.6.1), обеспечивая все нейроны слоя сравнения одним из двух входов с единичным значением, необходимым для их возбуждения в соответствии с правилом двух третей. Тогда любая компонента вектора X, равная единице xi=1, обеспечивает второй единичный вход. В результате, соответствующий нейрон слоя сравнения возбуждается и его выход принимает единичное значение rk=1 Таким образом, в течение этой фазы вектор С в точности дублирует вектор X: C=X. Основы искусственного интеллекта зм Каждый нейрон k в слое распознавания вычисляет свертку вектора его весов Вk и вектора C – выхода нейронов слоя сравнения: sk = (Bk • C), (6.3) В этот момент С = X; sk – возбуждение нейрона k в слое распознавания. Активационная функция нейронов слоя распознавания является пороговой, определяемой следующим образом: yk = 1, если sk ≥ θ, (6.4) yk = 0, если sk < θ, где θ представляет собой порог. Процесс конкуренции между нейронами существует, но игнорируется здесь для сохранения простоты выражении. В итоге только нейрон с максимальным значением sk будет иметь выход, равный единице yk=1; все остальные нейроны будут иметь нулевой выход. Сеть APT запоминает образы в весах нейронов слоя распознавания, один нейрон для каждой категории классификации. Нейрон слоя распознавания, веса которого наилучшим образом соответствуют входному вектору С, возбуждается. Его выход устанавливается в единичное значение, а выходы остальных нейронов этого слоя устанавливаются в ноль. Сравнение Единственный возбужденный в слое распознавания нейрон возвращает единицу обратно в слой сравнения rk=1. Эта единственная единица может быть визуально представлена в виде «веерного» выхода, подающегося через связь с весом tki на вход каждого нейрона в слое сравнения: рi = rktki Алгоритмы инициализации и обучения построены таким образом, что каждый весовой вектор Тk имеет двоичные значения весов Это означает, что все компоненты рi также являются двоичными величинами. (рi =0 или рi =1). Сигнал обратной связи rk от слоя распознавания устанавливает значение G1=0. Правило двух третей позволяет возбуждаться только тем нейронам, которые имеют равные единице соответствующие компоненты векторов рi и xi. Другими словами, обратная связь от распознающего слоя действует таким образом, чтобы установить компоненты ci = 0 в том случае, если входной вектор X не соответствует запомненному нейроном слоя распознавания образу P, т.е. если рi ≠ xi. Поэтому, в общем случае, на этой фазе С ≠ X. Блок сброса сравнивает вектор С и входной вектор X, вырабатывая сигнал сброса, когда их сходство  ниже заданного порога. Вычисление параметра сходства может осуществляться следующим образом: =l/m, (6.5) где l – количество совпавших компонент в векторах X и С, m – размерность входного вектора X. Значение  может изменяться от 1 (наилучшее соответствие) до 0 (наихудшее соответствие). Если степень сходства векторов X и P меньше заданного порогового уровня, Основы искусственного интеллекта зм вырабатывает сигнал сброса. Сигнал сброса устанавливает выход возбужденного нейрона в ноль rk=0, отключая его на время текущей классификации. Поиск Если значение параметра сходства  выигравшего нейрона превышает пороговый уровень, поиск не требуется, процесс классификации на этом завершается. В противном случае другие запомненные образы должны быть исследованы с целью поиска лучшего соответствия. При этом торможение возбужденного нейрона в распознающем слое приводит к установке всех компонент вектора R в 0, тогда G1=1 и вектор С опять становиться идентичным входному вектору X. В результате другой нейрон выигрывает соревнование в слое распознавания и другой запомненный образ P возвращается в слой сравнения. Если P не соответствует X, возбужденный нейрон в слое распознавания снова тормозится. Этот процесс повторяется до тех пор, пока не произойдет одно из двух событий: 1. Будет найден запомненный образ P, сходство которого с вектором X будет выше порогового уровня. Тогда проводится переобучение возбужденного нейрона, в процессе которого модифицируются вектора его весов Tk и Bk. 2. Будут проверены все запомненные образы и определено, что они не соответствуют входному вектору X. Тогда вводится новый несвязанный нейрон в слое распознавания. Он выделяется для запоминания входного образа X и его весовые векторы Tk и Bk устанавливаются соответствующим образом. Обучение Обучающий алгоритм используется как в случае успешного, так и в случае неуспешного поиска. Вектору весов Вk возбужденного нейрона k в распознающем слое присваиваются новые значения: bi  Lc i L  1   ci (6.6) где сi – i-я компонента выходного вектора слоя сравнения; k – номер выигравшего нейрона в слое распознавания; bik – вес связи, соединяющей нейрон i в слое сравнения с нейроном k в слое распознавания; L = const (обычно L = 2). Компонентам вектора весов Тk, присваиваются соответствующие двоичные значения компонент вектора С: tki = сi, для всех i, (6.7) где tki является весом связи между выигравшим нейроном k в слое распознавания и нейроном i в слое сравнения. Основы искусственного интеллекта зм Пример функционирования сети АРТ Исходные данные: Образец Кодировка 5 6 7 i 1 2 3 4 8 9 10 X1 1 1 1 1 1 1 1 X2 1 1 1 1 1 1 X3 1 1 1 1 1 1 1 1 X4 1 1 1 1 1 X5 1 1 1 1 1 1 1 Пороговое значение п=0,85 0) Инициализация нераспределенного нейрона: Тнi=1 Внi  L/(L-1+m)=2/1+10=2/11  Внi=1/6 Тнi 1 1 1 1 1 1 Внi 1/6 1/6 1/6 1/6 1/6 1/6 1 1/6 1 1/6 1 1/6 1) На входе сети образец Х1 Т.к. это первый образец, то запоминаем его без изменений: T1i=X1i B1i=LX1i/(L-1+X1i)=2X1i/(1+7)= X1i/4 Первый нейрон: Т1i 1 1 1 1 1 1 В1i 1/4 1/4 1/4 1/4 1/4 1/4 2) На входе сети образец Х2 Распознавание: выход нераспределенного нейрона Sн=61/6=1 (победитель) выход первого нейрона S1= X2iB1i=3/4 X2i 1 1 1 1 1 В1i 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 X2iB1i Обучение (запоминаем Х2, т.к. победил нераспределенный нейрон): T2i=X2i B2i=LX2i/(L-1+X2i)=2X2i/(1+6)=2X2i/7 Второй нейрон: Т2i 1 1 1 1 1 В2i 2/7 2/7 2/7 2/7 2/7 1 1/6 1 1/4 1 1/4 1/4 1 2/7 Основы искусственного интеллекта зм 3) На входе сети образец Х3 Распознавание: выход нераспределенного нейрона Sн=81/6=4/3 выход первого нейрона S1= X2iB1i=7/4 (победитель) выход второго нейрона S2= X2iB2i=8/7 X3i 1 1 1 1 1 1 1 1 В1i 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 X2iB1i 1/4 1/4 В2i 2/7 2/7 2/7 2/7 2/7 2/7 2/7 2/7 2/7 2/7 X2iB2i Сравнение (X3 и С): Т1i 1 1 1 1 1 1 1 X3i 1 1 1 1 1 1 1 1 Ci 1 1 1 1 1 1 1 Результат сравнения: =0,9>п  переобучение первого нейрона Переобучение: Т1i=Сi B1i=LCi/(L-1+Ci)=2Ci/(1+7)=Ci/4 Т1i 1 1 1 1 1 1 1 В1i 1/4 1/4 1/4 1/4 1/4 1/4 1/4 4) На входе сети образец Х4 Распознавание: выход нераспределенного нейрона Sн=51/6=5/6 выход первого нейрона S1= X4iB1i=1/2 выход второго нейрона S2= X4iB2i=10/7 (победитель) X4i 1 1 1 1 1 В1i 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 X4iB1i В2i 2/7 2/7 2/7 2/7 2/7 2/7 2/7 2/7 2/7 2/7 2/7 X4iB2i Сравнение (X4 и С): Т2i 1 1 1 1 1 1 X4i 1 1 1 1 1 Ci 1 1 1 1 1 Результат сравнения: =1>п  переобучение второго нейрона Переобучение: Т2i=Сi B2i=LCi/(L-1+Ci)=2Ci/(1+5)=Ci/3 Т2i 1 1 1 1 1 В2i 1/3 1/3 1/3 1/3 1/3 5) На входе сети образец Х5 Распознавание: выход нераспределенного нейрона выход первого нейрона выход второго нейрона X5i 1 В1i 1/4 1/4 Sн=71/6=7/6 S1= X5iB1i=1 S2= X5iB2i=5/3 (победитель) 1 1 1 1 1 1/4 1/4 1/4 1/4 1 1/4 Основы искусственного интеллекта зм 1/4 1/4 1/4 X5iB1i 1/4 В2i 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 X5iB2i Сравнение (X5 и С): Т2i 1 1 1 1 1 X5i 1 1 1 1 1 1 1 Ci 1 1 1 1 1 Результат сравнения: =0,8<п  новый (третий) нейрон для запоминания X5 Обучение: T3i=X5i B3i=LX5i/(L-1+X5i)=2X5i/(1+7)= X1i/4 Третий нейрон: Т3i 1 1 1 1 1 1 1 В3i 1/4 1/4 1/4 1/4 1/4 1/4 1/4 Результат: Образец i Т1 В1 1 2 1 1 1/4 1/4 3 Кодировка 4 5 6 7 1 1 1 1/4 1/4 1/4 0 Т2 В2 1 1/3 Т3 В3 1 1/4 1 1/4 8 1 1/4 9 10 1 1/4 1 1 1 1 1/3 1/3 1/3 1/3 1 1 1 1 1 1/4 1/4 1/4 1/4 1/4 Свойства сетей АРТ Сети АРТ обучаются посредством изменения весов таким образом, что предъявление сети входного вектора заставляет сеть активизировать нейроны в слое распознавания, связанные со сходным запомненным вектором. Кроме этого, обучение проводится в форме, не разрушающей запомненные ранее образы, предотвращая тем самым временную нестабильность. Эта задача решается путем выбора критерия сходства. Новый входной образ (который сети раньше не предъявлялся) не будет соответствовать ранее запомненным образам с точки зрения параметра сходства, тем самым формируя новую запоминаемую категорию образов. С другой стороны, входной образ, схожий с одним из запомненных образов, не будет формировать новой категории, он просто будет модифицировать веса того нейрона, на который он похож. Таким образом, при соответствующем выборе критерия сходства предотвращается временная нестабильность и искажение ранее изученных образов. Основы искусственного интеллекта зм К достоинствам сети АРТ можно отнести: 1. Быстрый доступ к предварительно запомненным образам, обусловленный тем, что активизация нужного нейрона в слое распознавания не требует запуска процедуры поиска. 2. Устойчивость процесса обучения, затрагивающего только один возбужденный нейрон. 3. Конечный характер процесса обучения. Любая последовательность произвольных входных векторов будет приводить к стабильному набору весов после конечного числа обучающих циклов. Повторяющиеся последовательности обучающих векторов не будут приводить к циклическому изменению весов сети. 1. У сети АРТ есть несколько существенных недостатков: Чувствительность к порядку предъявления векторов. Запоминаемые категории, сформированные сетью, принципиально меняются при различном порядке предъявления входных образов. 2. Невозможность классификации зашумленных векторов. Если сетью сформирована правильная категория, к которой относится вектор X, то как только компонента его xi примет нулевое значение за счет шума (если вектора предъявляются неоднократно), соответствующая компонента категории также будет обнулена. Т.к. случайное нулевое значение может принять любая компонента X, то с течением времени все компоненты категории будут обнулены, запомненная информация о ней - утрачена. Если после этого предъявить незашумленный вариант вектора X, то для него будет выделен новый нейрон, т.е. сформирована новая категория. Это явление называется размножением категорий. 3. Организация памяти по принципу «бабушкиных узелков». Каждый «узелок» нейрон слоя распознавания отвечает за хранение одной категории образов, что лишает память сети АРТ основного преимущества человеческой памяти – свойства распределенности. Мозг человека может пережить значительные повреждения без существенной потери памяти, за счет ее распределения по нейронам. Основы искусственного интеллекта зм САМООРГАНИЗУЮЩИЕСЯ СЕТИ Основу самоорганизации нейронных сетей составляет подмеченная закономерность, заключающаяся в том, что общее упорядочение весовых коэффициентов сети становится возможным в результате операций самообучения, проводящихся независимо друг от друга в различных локальных сегментах сети. Векторы входных образов активизируют определенные нейроны сети, которые адаптируются к обучающим примерам путем изменения своих синаптических весов. В процессе обучения наблюдается тенденция к росту значений весовых коэффициентов. Создается положительная обратная связь: большие значения входных воздействий вызывают увеличение весов активизированных нейронов, что в свою очередь вызывает большую активность нейронов. При этом происходит естественное расслоение нейронов на различные группы. Отдельные нейроны или их группы сотрудничают между собой и активизируются в ответ на возбуждение, создаваемое конкретными обучающими выборками, подавляя своей активностью другие нейроны. При этом можно говорить как о сотрудничестве между нейронами внутри группы, так и о конкуренции между нейронами внутри группы и между различными группами. Важное значение для обучения имеет избыточность исходных данных, без которых обучение просто невозможно. Самообучение на основе конкуренции В самом простом варианте самоорганизующаяся ИНС может быть однослойной сетью. Ассоциированное с каждым нейроном множество весов соединяет его с каждым входом (рис.7.1). Подобно нейронам большинства сетей каждый i-й нейрон вычисляет сумму взвешенных входов (si). si   x k wki , где (7.1) k xk – k-я составляющая входного вектора X, wki - вес связи, соединяющей k-й вход с iм нейроном Рис.7.1 Самообучающийся слой Нейрон с максимальным значением si является «победителем». Его выход равен единице, выходные значения остальных нейронов равны нулю. Такая сеть классифицирует входные векторы в группы схожих. Это достигается с помощью такой подстройки весов, что близкие входные векторы активируют один и тот же Основы искусственного интеллекта зм нейрон. В данном случае обучение протекает без учителя. Поэтому трудно предсказать, какой именно нейрон сети будет активироваться заданным входным вектором. Необходимо лишь гарантировать, чтобы в результате обучения разделялись несхожие входные векторы. Предварительная обработка входных векторов Перед тем, как предъявлять сети входные векторы их следует нормализовать. Для этого выполняется деление каждой компоненты входного вектора на его длину. Длина вектора вычисляется извлечением квадратного корня из суммы квадратов его компонент. n xi'  xi /  x k2 k 1 Нормализованный вектор x’i единичной длины ориентирован в n-мерном пространстве также как и исходный входной вектор. На рис. 7.2 показан пример нормализации двумерного вектора (n=2) Рис.7.2 Нормализация двумерного вектора На рис.7.3 показано несколько единичных двумерных векторов, что справедливо для сети с двумя входами. Они оканчиваются на окружности единичного радиуса. В случае сети с тремя входами, векторы оканчивались бы на поверхности единичной сферы. Эти представления могут быть перенесены на сети, имеющие произвольное число входов (n), где каждый входной вектор оканчивается на поверхности единичной гиперсферы. Эта абстракция не допускает непосредственной визуализации. Рис.7.3 Двумерные нормализованные входные векторы Правило самообучения Всем весам сети перед началом обучения следует придать случайные малые значения. Эти случайно выбранные весовые векторы W следует нормализовать также как и входные вектора X. Основы искусственного интеллекта зм При обучении самоорганизующейся сети на вход подается входной вектор X и вычисляются его скалярные произведения с векторами весов, связанными со всеми нейронами. Нейрон с максимальным значением скалярного произведения объявляется «победителем» и его веса подстраиваются. При нормализованных векторах X и W, скалярное произведение, используемое для вычисления взвешенных сумм нейронов (7.1) si является мерой сходства между вектором X и вектором W. Процесс обучения состоит в выборе нейрона с весовым вектором, наиболее близким ко входному вектору, и в дальнейшем приближении весового вектора W к входному вектору X. Сеть самоорганизуется таким образом, чтобы нейрон-победитель увеличивал значение взвешенной суммы si для данного входного вектора. Уравнение, описывающее процесс обучения имеет следующий вид: W(t+1) = W(t) + µ(X – W(t)), (7.2) где W(t+1) – новое значение вектора весов победившего нейрона, X – вектор входных весов; W(t) – предыдущее значение вектора весов; µ – коэффициент скорости обучения, который может варьироваться в процессе обучения. Каждый вес, связанный с выигравшим нейроном, изменяется пропорционально разности между его величиной и величиной компоненты входа, с которой он связан. Направление изменения минимизирует разность между весом и его входом. На рис.7.4 этот процесс показан геометрически для двумерного случая – сети с двумя входами. Сначала находится разность векторов X–W, для этого строится вектор из конца W в конец X. Затем этот вектор укорачивается умножением его на скалярную величину µ<1. В результате чего получается вектор изменения δ = µ(X–W). Тогда новый весовой вектор X направлен из начала координат в конец вектора δ. Отсюда можно видеть, что эффект обучения состоит во вращении весового вектора в направлении входного вектора без существенного изменения его длины. Рис.7.4 Подстройка весов нейрона Если бы с каждым нейроном ассоциировался один входной вектор, то сеть могла бы быть обучена с помощью одного вычисления на вес. Веса нейрона-победителя приравнивались бы к компонентам обучающего вектора (µ = 1). Как правило, обучающее множество включает много сходных между собой входных векторов, и сеть должна быть обучена активировать один и тот же нейрон для каждого из них. В этом случае веса этого нейрона должны получаться усреднением тех входных векторов, которые должны его Основы искусственного интеллекта зм активировать. Таким образом, веса, ассоциированные с нейроном, примут значение вблизи «центра» входных векторов, для которых данный нейрон является «победителем». Проблема мертвых нейронов При инициализации сети, ее весам присваиваются случайные значения, распределенные по равномерному закону. Это может породить серьезные проблемы при обучении, так как весовые векторы сети распределяются равномерно по поверхности гиперсферы. Входные векторы, как правило, распределены неравномерно и имеют тенденцию группироваться на относительно малой части поверхности гиперсферы. В итоге, большинство весовых векторов Wm будут так удалены от любого входного вектора X, что связанные с ними нейроны никогда не будут иметь шансов на победу. Их весовые вектора не будут корректироваться, поэтому такие нейроны остаются «мертвыми». На рис.7.5 приведен пример возможной ситуации для сети с двумя входами. Нейроны с весовыми векторами Wi и Wj активируются каждый своей группой векторов. Нейрон с весовым вектором Wm будет «мертвым». Рис. 7.5 Проблема мертвых нейронов Более того, оставшихся нейронов, имеющих наилучшие соответствия своих весовых векторов W с некоторыми входными векторами X, может оказаться слишком мало, чтобы разделить эти входные векторы на классы, которые расположены близко друг к другу на поверхности гиперсферы. Такая сеть будет иметь большую погрешность интерпретации данных, иначе называемую погрешностью квантования. Самоорганизующиеся карты Кохонена Идея сети принадлежит финскому ученому Тойво Кохонену. Отличительной особенность работы самоорганизующихся карт (Self-Organizing Maps, SOM) является введение в правило обучения нейронов информации о его расположении относительно других нейронов сети. Здесь имеет место аналогия со свойствами коры головного мозга человека. Она обладает определенными топологическими свойствами. Например, участок, ответственный за кисть руки, примыкает к участку, ответственному за движения всей руки, и таким образом все изображение человеческого тела «отображается» на поверхность коры. Карты Кохонена подразумевают использование упорядоченной структуры нейронов. Сеть состоит из одного слоя нейронов, располагающихся в узлах двумерной Основы искусственного интеллекта зм сетки с прямоугольными или шестиугольными ячейками. Каждый нейрон соединен со всеми компонентами n-мерного входного вектора X (рис.7.6) При этом каждому i-му нейрону соответствует n-мерный вектор весовых коэффициентов Wi = [w1i, w2i, …, wni]. Свойство топологической упорядоченности достигается в сети с помощью дополнительного использования понятия окрестности. Окрестность - это несколько ближайших нейронов, окружающих выигравший нейрон. Радиус окрестности определяет степень взаимодействия нейронов друг с другом. На рис.7.7 приведены примеры окрестностей с разным радиусом - R для четырехугольной и гексагональной сеток. При этом можно заметить, что для гексагональной сетки окрестность нейрона больше совпадает с понятием евклидова расстояния между нейронами, чем для четырехугольной сетки. Рис. 7.7 Окрестности нейрона для четырехугольной и гексагональной сеток На этапе инициализации сети SOM определяется конфигурация сетки (прямоугольная или шестиугольная),задается количество нейронов в сети, выбирается начальный радиус обучения нейронов. Затем производится инициализация случайными значениями весовых коэффициентов нейронов и последующая нормализация их весовых векторов. Векторы входных образов также нормализуются. После активации сети вектором X в конкурентной борьбе побеждает тот нейрон, веса которогоWj в наименьшей степени Основы искусственного интеллекта зм отличаются от соответствующих компонент этого вектора. Для j- го нейрона-победителя выполняется соотношение: d ( X , W j )  min d ( X , Wi ) , i(1, N ) где d ( X , W j ) обозначает расстояние между векторами X и Wj, а N – количество нейронов в сети. В качестве меры расстояния между векторами X и Wj чаще всего используются : n евклидова мера: d ( X , W j )   ( xi  w ji ) 2 ; (7.3) скалярное произведение: d ( X , W j )  1  X W j cos( X , W j ) (7.4) i 1 Вокруг нейрона-победителя образуется топологическая окрестность. Все нейроны, лежащие в пределах его окрестности радиуса R, подвергаются обучению, в ходе которого векторы их весов изменяются в направлении вектора X по правилу (7.2). Значение коэффициента µ уменьшается с увеличением расстояния между i-м нейроном и победителем. Доказано, что при таком обучении функция плотности распределения весовых векторов Wj нейронов сводится к дискретизированной плотности распределения векторов обучающих примеров. Обучение Целью обучения сети SOM считается такое упорядочение нейронов (подбор значений их весов), которое минимизирует погрешность аппроксимации входного вектора X значениями весов нейрона-победителя. Если используется евклидова метрика (7.3) для определения расстояния между векторами X и Wj,а P – количество входных векторов в обучающей выборке, то эта погрешность, называемая также погрешностью квантования Eq, может быть выражена в виде: Eq  1 P P 2  X p  W jp , где p 1 Wjp – весовой вектор j-го нейрона- победителя при предъявлении сети вектора Xp из обучающей выборки. Обучение сети состоит из последовательности коррекций весовых векторов нейронов. На каждом шаге обучения из обучающей выборки случайно выбирается один из векторов X, а затем производится поиск ближайшего к нему весового вектора Wj. Для определения расстояния между X и Wj используется метрика (7.3) или (7.4). Таким образом выбирается j- й нейрон-победитель и производится корректировка весов нейронов, т.е. обучение сети. Процедура корректировки весов нейронов может быть определена обобщенной зависимостью : Wi(t+1) = Wi(t) + µiG(i,X)(X – Wi(t)), (7.5) для всех i нейронов, расположенных в окрестности нейрона-победителя. В формуле (7.5) скорость обучения µi нейрона i отделена от его расстояния до предъявленного вектора X функцией G(i,X), называемой функцией соседства. Существует несколько вариантов Основы искусственного интеллекта зм алгоритмов обучения, отличающихся видом функции соседства. Рассмотрим два из них – классический алгоритм Кохонена и алгоритм нейронного газа. Алгоритм Кохонена В классическом алгоритме Кохонена сеть инициализируется путем приписывания нейронам определенных позиций в пространстве и связывания их с соседями на постоянной основе. После выбора нейрона-победителя уточняются не только его веса, но также и веса его соседей, находящихся в ближайшей окрестности. Функция соседства определяется функцией гауссовского типа: G(i, X )  exp( d 2 (i, j ) 22 ), где (7.6) d(i,j) – расстояние между i-м нейроном и j-нейроном-победителем, λ-уровень соседства. При соседстве гауссовского типа степень адаптации i-го нейрона уменьшается по мере его удаления от нейрона-победителя. Такое обучение еще называется алгоритмом типа WTM (Winner Takes Most – победитель забирает больше). В классическом алгоритме Кохонена функция соседства определяется в виде: 1, d (i, j )  R j G (i, X )   , , d ( i , j )  R j  где d(i,j) – расстояние между i-м нейроном и j-м нейроном-победителем, измеряемое количеством нейронов, т.е. величиной радиуса R окрестности нейрона j (рис. 7.7). Rj – радиус окрестности нейрона-победителя, внутри которой веса нейронов подвергаются обучению. Соседство такого рода называется прямоугольным. Частным случаем классического алгоритма Кохонена является обучение, в котором функция соседства определяется формулой: 1, i  j . G(i, X )   0, i  j В этом случае обучается только нейрон-победитель по алгоритму типа WTA (Winner Takes All – победитель забирает все). Как правило, функция соседства гауссовского типа дает лучшие результаты обучения и обеспечивает лучшую организацию сети, чем прямоугольное соседство. Значение параметра λ - уровня соседства (радиуса обучения) выбирают достаточно большим на начальном этапе обучения и постепенно уменьшают так, что в конечном итоге обучение происходит по типу WTA. Скорость обучения µi также представляет собой функцию, убывающую от времени. Наиболее часто используется функция обратно пропорциональная времени вида µi(t) = A/(t+В), где A и B это константы. Обучение состоит из двух основных фаз: на первоначальном этапе выбирается достаточно большое значение скорости обучения µi(t) и радиуса обучение λ, что позволяет расположить вектора нейронов в соответствии с распределением примеров в выборке, а Основы искусственного интеллекта зм затем производится точная подстройка весов, когда значения параметров скорости и радиуса обучения много меньше начальных. Алгоритм нейронного газа В этом алгоритме на каждой итерации все нейроны сортируются в зависимости от их расстояния до вектора X. После сортировки нейронам присваивается номер позиции m в сортированном списке: d1< d2< …dm< …dN, где (7.7) dm=|X-Wim| - расстояние между вектором X и вектором весов Wi i-го нейрона, занимающего в результате сортировки m-ю позицию в последовательности, возглавляемой нейроном-победителем, которому сопоставлено расстояние d1. Значение функции соседства для i-го нейрона определяется по формуле: G(i, X )  exp( m(i) ), где (7.8)  m(i) обозначает очередность i-го нейрона, полученную в результате сортировки (m(i)= 1,2,…N), а λ – параметр, аналогичный уроню соседства в алгоритме Кохонена. Алгоритм нейронного газа напоминает стратегию нечетких множеств, в соответствии с которой каждому i-му нейрону присваивается значение функции принадлежности G(i,X) к окрестности нейрона-победителя. Параметр λ уменьшается в процессе адаптации весов нейронов, сужая окрестность обучения. При λ=0 адаптации подвергается только нейрон-победитель, и алгоритм превращается в обычный алгоритм WTA. Изменение λ(t) в зависимости от номера итерации обучения t можно описать выражением:  (t )  max (min / max ) t / tmax , где λmax и λmin – принятые максимальное и минимальное соответственно значения параметра λ. Коэффициент tmax определяет максимальное количество итераций обучения сети. Коэффициент скорости обучения i-го нейрона µi в выражении (7.5) тоже может уменьшаться линейно или показательно по мере увеличения номера итерации обучения t. Для сокращения объема вычислений, необходимых для реализации алгоритма нейронного газа, можно включать в сортированный список (7.7) только нейроны с наиболее значимой величиной функции G(i,X), вычисляемой по формуле (7.8). Если очередность нейрона m(i)>>1, то значение G(i,X)≈0. Например, если принять K=3λ, то при сортировке нейронов и при их обучении можно ограничиться только первыми K элементами. Решение проблемы мертвых нейронов Для решения проблемы мертвых нейронов (рис. 7.5) необходимо провести активацию всех нейронов сети, включив их в процесс адаптации весовых коэффициентов. Для этого применяются следующие способы. Основы искусственного интеллекта зм Механизм утомления В алгоритме обучения можно предусмотреть учет количества побед каждого нейрона, а процесс обучения организовать так, чтобы дать шанс победить и менее активным нейронам. Идея такого подхода к обучению возникла при наблюдении за поведением биологических нейронов. Отмечен факт, что нейрон-победитель сразу после возбуждения на некоторое время теряет активность, «отдыхая» перед следующим этапом конкурентной борьбы. Такой способ учета активности нейронов называется механизмом утомления. Для учета активности нейронов используется метод подсчета потенциала pi каждого нейрона, значение которого модифицируется всякий раз после предъявления очередной реализации входного вектора X. Потенциал нейрона определяется по следующему правилу: p(t )  1 / n, i  j  pi (t  1)   ,  p(t )  p(t )  p min , i  j где j- нейрон-победитель, значение pmin определяет минимальный потенциал, разрешающий участие в конкурентной борьбе. Если фактическое значение потенциала pi< pmin, i-й нейрон «отдыхает», а победитель ищется среди оставшихся нейронов, для которых выполняется условие pi> pmin. Максимальное значение потенциала ограничивается на уровне pi=1. Выбор значения pmin позволяет установить порог готовности нейрона к конкурентной борьбе. При pmin=0 утомляемость нейронов не возникает и каждый из них сразу же после победы будет готов к продолжению соперничества (классический алгоритм Кохонена). При pmin=1 возникает другая крайность, вследствие которой нейроны побеждают по очереди, т.к. на каждой итерации обучения только один из них оказывается готов к соперничеству. На практике применяется величина порога pmin≈0,75 Механизм штрафа победителей Количество побед нейрона учитывается при подсчете эффективного расстояния dэ(X, Wi) между вектором весов Wi и обучающим вектором X. Это расстояние модифицируется пропорционально количеству побед данного нейрона в прошлом. Если обозначить количество побед i-го нейрона Pi, то такую модификацию можно представить в виде: d э ( X , Wi )  Pi d ( X , Wi ) , где d(X, Wi) – фактическое расстояние между векторами X и Wi. Активные нейроны с большим значением Pi штрафуются искусственным завышением этого расстояния. Следует отметить, что величина dэ используется только для выявления победителя. При коррекции весового вектора нейрона (7.5) учитывается фактическое расстояние. Модификация расстояния имеет целью активизировать все нейроны путем введения их в область с большим количеством данных. После решения этой задачи (обычно после двух или трех циклов обучения) модификация расстояния прекращается, что позволяет продолжить «честную» конкуренцию нейронов. Основы искусственного интеллекта зм Применение сетей Кохонена Сжатие данных Главным свойством сети Кохонена считается компрессия данных, состоящая в том, что образующие кластер большие группы данных представляются единственным вектором весов нейрона-победителя. При разделении P исходных обучающих примеров на Q кластеров и представлении каждого кластера одним из N нейронов достигается значительное сокращение объема информации, которое и называется компрессией. Это компрессия с потерей качества, которая определяется погрешностью квантования Eq. Примером использования компрессионных свойств сети Кохонена может считаться сжатие изображений. Предположим, что изображение размером KxxKy пикселов разделяется на одинаковые кадры размером kxxky пикселов (рис.7.8). Рис. 7.8 Разделение изображения на кадры Образующие кадр пикселы представляют собой компоненты входных векторов X. Каждый вектор X состоит из K= kxxky компонент, каждая компонента xi определяет интенсивность конкретного пиксела в кадре. Сеть с самоорганизацией содержит N нейронов, каждый из которых связан синаптическими весами со всеми компонентами входного вектора X. В результате обучения формируется структура сети, при которой вектору X каждого кадра соответствует вектор весов нейрона-победителя. При похожих составляющих вектора X для разных кадров побеждать будет один и тот же нейрон либо группа нейронов с близкими векторами W. В процессе предъявления сети очередного кадра выбирается номер нейрона-победителя, например, 7, 4, 7, 7, 31 и т.д. Эти номера образуют кодовую последовательность, а весовые вектора Wi нейронов представляют средние значения, соответствующие уровням интенсивности пикселов, составляющих кадр. При обучении сеть сама формирует ядра классов, т.е. набор фрагментов из которых строится восстановленное изображение. Пусть, например, при использовании двухуровневой (черно-белой) кодировке интенсивности пиксела, в двух нейронах Кохонена запомнены два фрагмента изображения –ядра классов (рис. 7.9а,б) в виде весовых коэффициентов. Предъявим в виде входного вектора фрагмент изображения (рис.7.9в). Входной вектор больше похож на вектор весов, запомненный вторым нейроном i=2, поэтому он будет активирован. При восстановлении изображения по номеру класса i=2, будет восстановлен Основы искусственного интеллекта зм фрагмент, запомненный вторым нейроном, который не полностью совпадает с исходным фрагментом. Рис. 7.9 Пример запоминания фрагментов Если количество нейронов N в сети намного меньше количества кадров, то можно получить существенную степень сжатия исходного изображения. В итоге коэффициент компрессии изображения определяется выражением: Kr = NrkxkyT/(Nrlg2N+Nkxkyt), где kx и ky – размеры кадра по горизонтали x и вертикали y, Nr – количество кадров в исходном изображении, N – количество нейронов в сети, T и t количество битов, используемых для представления соответственно градаций интенсивности пиксела и значений весов. Чем больше фрагмент и чем меньше нейронов в сети Кохонена, тем выше коэффициент компрессии, и тем больше потери при восстановлении. Этот же метод может быть применен для сжатия других типов данных, например, речевых сигналов. Типичные значения коэффициента сжатия для сети Кохонена Kr от 10 до 100. Раскраска карты Кохонена Так как карты Кохонена сочетают в себе два основных свойства – векторное квантование и проецирование, то их используют для поиска и анализа закономерностей в исходных данных. При этом, после того, как нейроны размещены на карте, полученная карта может быть отображена и раскрашена. Если имеется множество из сотен или тысяч объектов, каждый из которых описывается несколькими параметрами, то проанализировать это множество на наличие закономерностей и аномалий весьма сложно. Самоорганизующиеся карты позволяют представить множество объектов, заданных в многомерном пространстве признаков в виде двумерных карт. Близко расположенным в многомерном пространстве объектам соответствуют близко расположенные нейроны на плоской карте. Обученная сеть Кохонена позволяет получить на выходе достаточно наглядные двумерные карты, которые несложно проанализировать визуально После обучения сети будет получен набор узлов, который можно отобразить в виде двумерного изображения. При этом каждой ячейке карты можно поставить в соответствие участок на сетке, координаты которого определяются координатами соответствующего нейрона в решетке. Для визуализации определяется цвет ячеек карты. Для этого используются значения выбранной компоненты wk весового вектора W. Самый простой вариант раскраски – использование градаций серого. В этом случае ячейки, Основы искусственного интеллекта зм соответствующие узлам карты, которые имеют минимальные значениями компоненты wk, будут изображены черным цветом, а ячейки, которые имеют максимальные значениями компоненты wk, будут изображены белым цветом. Можно использовать любую градиентную палитру для раскраски. Полученные раскраски в совокупности образуют атлас, отображающий расположение компонент, связи между ними, а также относительное расположение различных значений компонент. Рассмотрим применение сети Кохонена на небольшой практической задаче из области информационной безопасности. Для анализа сетевой активности в корпоративной сети используются специальные программно-аппаратные устройства – анализаторы трафика. Эти устройства позволяют выявить вредоносное и несанкционированное программное обеспечение например, троянские программы, клиенты пиринговых сетей и другие. Как правило, анализ фиксируемых устройством данных производится в «ручном режиме», с применением простейших средств обработки протоколов. Обработать таким способом большие массивы исходных данных не представляется возможным. Поэтому целесообразно использовать сеть Кохонена для анализа исходных данных и визуального отображения полученных результатов. Входной массив данных формируется анализатором трафика пользователей корпоративной локальной вычислительной сети (ЛВС). Для упрощения задачи будем считать, что фиксируется количество пакетов по различным протоколам в единицу времени, в частности: Количество пакетов по порту 25/TCP (отправка почты) – параметр “SMTP”; Количество пакетов по порту 110/TCP (получение почты) – параметр “POP3”; Количество пакетов по порту 21/TCP (FTP-протокол) – параметр “FTP”; Количество пакетов по порту 80/TCP (http-протокол) – параметр “HTTP”; Количество пакетов по порту 3128/TCP (HTTP Proxy) – параметр «HTTP_PROXY»; В примере все пользовательские компьютеры в ЛВС работают с Интернетом через прокси-сервер. Построим карту Кохонена таким образом, чтобы количество нейронов соответствовало количеству компьютеров. Обучение сети производится на исходных данных, после чего можно приступать к анализу. Для анализа используем раскраску карт с помощью градаций серого. Шкала раскраски приводится для каждой карты, раскрашенной по одному параметру. Каждой градации серого соответствует диапазон значений, выраженный в количестве пакетов, зафиксированных по данному параметру за единицу времени (за час, за рабочий день и т.п.). На рис. 7.10 представлена раскраска обученной карты по параметру POP3 (получение почты).На ней видно, что все пользователи активно работают с почтой, но явных аномалий активности по этому параметру не прослеживается. Можно отметить, что на карте выделены области, соответствующие уровню активности пользователей в части получения ими почтовых сообщений. Распределение имеет равномерный характер. Основы искусственного интеллекта зм Рис.7.10 Раскраска карты Кохонена по параметру SMTP На рис. 7.11 представлена раскраска карты по параметру SMTP (отправка почты). На карте хорошо видно, что практически все пользователи работают с электронной почтой, но их SMTP-трафик невелик. При этом выявлена группа из нескольких компьютеров, с которых отправлено очень большое количество SMTP-пакетов. Рис.7.11 Раскраска карты Кохонена по параметру POP3 Анализ карты по параметру HTTP (здесь не представлен) также выявляет аномально высокую активность http-запросов, посылаемых с этих же компьютеров. Выявленные аномальные закономерности являются поводом для дальнейшего расследования и анализа. Это могут быть компьютеры, зараженные троянскими программами, осуществляющими автоматизированную рассылку рекламных сообщений. Таким образом, как показывают рассмотренные примеры, карты Кохонена являются удобным инструментом для анализа данных с целью поиска аномалий и закономерностей – для поиска следов деятельности злоумышленников, в борьбе с вредоносными программами. Карты могут выступать аргументом в служебном расследовании, так как записи в протоколе не отличаются наглядностью, а раскрашенная карта Кохонена очень проста и наглядна. Следует отметить, что описанные технологии в основном применяются в экономике и медицине при прогнозировании развития рынка, курсов валют, надежности компаний, при постановке диагнозов и т.п.