Настройка одноэлементных систем и нейронных сетей для решения задач

Введение

Нейронные сети могут все. Но точно также «все» могут машины Тьюринга, интерполяционные многочлены, схемы Поста, ряды Фурье, рекурсивные функции, дизъюнктивные нормальные формы, сети Петри. В предыдущей главе было показано, что с помощью нейронных сетей можно сколь угодно точно аппроксимировать любую непрерывную функцию и имитировать любой непрерывный автомат. Это и слишком много _ никому не нужен столь широкий класс функций, и слишком мало, так как далеко не все важные задачи ставятся как задачи аппроксимации.

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

В данной работе описано несколько базовых задач для нейронных сетей и основных или исторически первых методов настройки сетей для их решения:

Классификация (с учителем) (персептрон Розенблатта.

Ассоциативная память (сети Хопфилда.

Решение систем линейных уравнений (сети Хопфилда.

Восстановление пробелов в данных (сети Хопфилда).

Кластер-анализ и классификация (без учителя) (сети Кохонена.

Начнем мы, однако, не с сетей, а с систем, состоящих из одного элемента.

1. Настройка одноэлементных систем для решения задач

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

Линейная регрессия и восстановление простейших закономерностей;

Линейная фильтрация и адаптивная обработка сигналов;

Линейное разделение классов и простейшие задачи распознавания образов.

Задача линейной регрессии состоит в поиске наилучшего линейного приближения функции, заданной конечным набором значений: дана выборка значений вектора аргументов x¹ , ..., x^m, заданы значения функции F в этих точках: F(xⁱ)=f_i, требуется найти линейную (неоднородную) функцию (x)=(,x)+₀, ближайшую к F. Чтобы однозначно поставить задачу, необходимо доопределить, что значит «ближайшую». Наиболее популярен метод наименьших квадратов, согласно которому ищется из условия

. (1)

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

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

Найдем производные минимизируемой функции H по настраиваемым параметрам:

где xⁱ_j _ j-я координата вектора xⁱ.

Приравнивая частные производные H нулю, получаем уравнения, из которых легко найти все _j (j=0,...,n). Решение удобно записать в общем виде, если для всех i=1,...,m обозначить и рассматривать n+1-мерные векторы данных xⁱ и коэффициентов . Тогда

Обозначим p n+1-мерный вектор с координатами

;

Q - матрицу размером (n+1)(n+1) с элементами

.

В новых обозначениях решение задачи линейной регрессии имеет вид:

(x)=(,x), =Q^_1p. (2)

Приведем это решение в традиционных обозначениях математической статистики. Обозначим M_о среднее значение j-й координаты векторов исходной выборки:

.

Пусть M _ вектор с координатами M_о. Введем также обозначение s_j для выборочного среднеквадратичного отклонения:

Величины s_j задают естественный масштаб для измерения j-х координат векторов x. Кроме того, нам потребуются величина s_f и коэффициенты корреляции f с j-ми координатами векторов x _ r_fj:

Вернемся к n-мерным векторам данных и коэффициентов. Представим, что векторы сигналов проходят предобработку _ центрирование и нормировку и далее мы имеем дело с векторами yⁱ:



Это, в частности, означает, что все рассматриваемые координаты вектора x имеют ненулевую дисперсию, т.е. постоянные координаты исключаются из рассмотрения _ они не несут полезной информации. Уравнения регрессии будем искать в форме: (y)=(,y)+₀. Получим:

₀=M_f, =s_fR^_1R_f, (3)

где R_f _ вектор коэффициентов корреляции f с j-ми координатами векторов x, имеющий координаты r_fj, R _ матрица коэффициентов корреляции между координатами вектора данных:

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

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

Пусть на выборке вычислены p, Q, Q^_1. При получении нового вектора данных x^m+1 и соответствующего значения F(x^m+1)=f _m+1 имеем Напомним, что для векторов x, y матрица xy имеет своими элементами x_jy_k.:

(4)

где _ ошибка на векторе данных x^m+1 регрессионной зависимости, полученной на основании выборки .

Пересчитывая по приведенным формулам p, Q, Q^_1 и после каждого получения данных, получаем процесс, в котором последовательно уточняются уравнения линейной регрессии. И требуемый объем памяти, и количество операций имеют порядок n² _ из-за необходимости накапливать и модифицировать матрицу Q^_1. Конечно, это меньше, чем потребуется на обычное обращение матрицы Q на каждом шаге, однако следующий простой алгоритм еще экономнее. Он вовсе не обращается к матрицам Q, Q^_1 и основан на уменьшении на каждом шаге величины _ квадрата ошибки на векторе данных x^m+1 регрессионной зависимости, полученной на основании выборки .

Вновь обратимся к формуле (2) и будем рассматривать n+1-мерные векторы данных и коэффициентов. Обозначим . Тогда

. (5)

Последняя элементарная формула столь важна в теории адаптивных сумматоров, что носит «именное название» _ формула Уидроу. «Обучение» адаптивного сумматора методом наискорейшего спуска состоит в изменении вектора коэффициентов в направлении антиградиента ²: на каждом шаге к добавляется hx, где h _ величина шага.

Если при каждом поступлении нового вектора данных x изменять указанным образом, то получим последовательную процедуру построения линейной аппроксимации функции F(x). Такой алгоритм обучения легко реализуется аппаратными средствами (изменение веса связи _j есть произведение прошедшего по ней сигнала x_j на ошибку и на величину шага). Возникает, однако, проблема сходимости: если h слишком мало, то сходимость будет медленной, если же слишком велико, то произойдет потеря устойчивости и сходимости не будет вовсе. Детальному изложению этого подхода и его приложений посвящен учебник [15].

Задача четкого разделения двух классов по обучающей выборке ставится так: имеется два набора векторов x¹ , ..., x^m и y¹,...,y^m . Заранее известно, что xⁱ относится к первому классу, а yⁱ - ко второму. Требуется построить решающее правило, то есть определить такую функцию f(x), что при f(x)>0 вектор x относится к первому классу, а при f(x)<0 _ ко второму.

Координаты классифицируемых векторов представляют собой значения некоторых признаков (свойств) исследуемых объектов.

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

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

1) искать дополнительные признаки, позволяющие разделить классы;

2) примириться с неизбежностью ошибок, назначить за каждый тип ошибок свой штраф (c₁₂ - штраф за то, что объект первого класса отнесен ко второму, c₂₁ - за то, что объект второго класса отнесен к первому) и строить разделяющее правило так, чтобы минимизировать математическое ожидание штрафа;

3) перейти к нечеткому разделению классов - строить так называемые "функции принадлежности" f₁(x) и f₂(x) _ f_i(x) оценивает степень уверенности при отнесении объекта к i-му классу (i=1,2), для одного и того же x может быть так, что и f₁(x)>0, и f₂(x)>0.

Линейное разделение классов состоит в построении линейного решающего правила _ то есть такого вектора и числа ₀ (называемого порогом), что при (x,)>₀ x относится к первому классу, а при (x, )<₀ - ко второму.

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

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

= (y¹+ y²+...+y^m)/m _(x¹+ x²+...+ x ⁿ)/n. (6)

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

= ((y¹+ y²+...+y^m)/m _(x¹+ x²+...+ x ⁿ)/n)/||(y¹+ y²+...+y^m)/m _(x¹+ x²+...+ x ⁿ)/n||.

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

₀=(((y¹+ y²+...+y^m)/m,)+((x¹+ x²+...+ x ⁿ)/n,))/2.

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

Можно для каждого класса построить приближенную плотность вероятностей распределения проекций его точек на прямую (это намного проще, чем для многомерного распределения) и выбирать ₀, минимизируя вероятность ошибки. Пусть решающее правило имеет вид: при (x, )>₀ x относится к первому классу, а при (x, )<₀ _ ко второму. В таком случае вероятность ошибки будет равна

где p₁, p₂ _ априорные вероятности принадлежности объекта соответствующему классу,

₁(), ₂() _ плотности вероятности для распределения проекций точек x в каждом классе.

Приравняв нулю производную вероятности ошибки по ₀, получим: число ₀, доставляющее минимум вероятности ошибки, является корнем уравнения:

p₁₁()=p₂₂(), (7)

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

Если принять гипотезу о нормальности распределений:

,

то для определения ₀ получим:

,

Если это уравнение имеет два корня y=₁, ₂, (₁<₂) то наилучшим решающим правилом будет: при ₁<(x, )<₂ объект принадлежит одному классу, а при ₁>(x, ) или (x, )>₂ _ другому (какому именно, определяется тем, которое из произведений p_ii() больше). Если корней нет, то оптимальным является отнесение к одному из классов. Случай единственного корня представляет интерес только тогда, когда ₁=₂. При этом уравнение превращается в линейное и мы приходим к исходному варианту _ единственной разделяющей точке ₀.

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

Если сразу ставить задачу об оптимальном разделении многомерных нормальных распределений, то получим, что наилучшей разделяющей поверхностью является квадрика (на прямой типичная «квадрика» _ две точки). Предполагая, что ковариационные матрицы классов совпадают (в одномерном случае это предположение о том, что ₁=₂), получаем линейную разделяющую поверхность. Она ортогональна прямой, соединяющей центры выборок не в обычном скалярном произведении, а в специальном: , где _ общая ковариационная матрица классов. За деталями отсылаем к прекрасно написанной книге [17], см. также [11,12,16].

Важная возможность усовершенствовать разделяющее правило состоит с использовании оценки не просто вероятности ошибки, а среднего риска: каждой ошибке приписывается «цена» c_i и минимизируется сумма c₁p₁₁()+c₂p₂₂(). Ответ получается практически тем же (всюду p_i заменяются на c_ip_i), но такая добавка важна для многих приложений.

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

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

(xⁱ, )>₀ (i=1,...,n)

(y^j , )<₀ (j=1,...,m).

Здесь xⁱ (i=1,..,n) - векторы из обучающей выборки, относящиеся к первому классу, а y^j (j=1,..,n) - ко второму.

Удобно переформулировать задачу. Увеличим размерности всех векторов на единицу, добавив еще одну координату _₀ к , x₀ =1 - ко всем x и y₀ =1 _ ко всем y . Сохраним для новых векторов прежние обозначения - это не приведет к путанице.

Наконец, положим zⁱ =xⁱ (i=1,...,n), z^j = _y^j (j=1,...,m).

Тогда получим систему n+m неравенств (zⁱ,)>0 (i=1,...,n+m), которую будем решать относительно . Если множество решений непусто, то любой его элемент порождает решающее правило, безошибочное на обучающей выборке.

Итерационный алгоритм решения этой системы чрезвычайно прост. Он основан на том, что для любого вектора x его скалярный квадрат (x,x) больше нуля. Пусть _ некоторый вектор, претендующий на роль решения неравенств (zⁱ,)>0 (i=1,...,n+m), однако часть из них не выполняется. Прибавим те zⁱ, для которых неравенства имеют неверный знак, к вектору и вновь проверим все неравенства (zⁱ,)>0 и т.д. Если они совместны, то процесс сходится за конечное число шагов. Более того, добавление zⁱ к можно производить сразу после того, как ошибка ((zⁱ,)<0) обнаружена, не дожидаясь проверки всех неравенств _ и этот вариант алгоритма тоже сходится [2].

2. Сети Хопфилда

Перейдем от одноэлементных систем к нейронным сетям. Пусть _ij _ вес связи, ведущей от j-го нейрона к i-му (полезно обратить внимание на порядок индексов). Для полносвязных сетей определены значения _ij при всех i,j, для других архитектур связи, ведущие от j-го нейрона к i-му для некоторых i,j не определены. В этом случае положим _ij=0.

В данном разделе речь пойдет в основном о полносвязных сетях. Пусть на выходах всех нейронов получены сигналы x_j (j-номер нейрона). Обозначим x вектор этих выходных сигналов. Прохождение вектора сигналов x через сеть связей сводится к умножению матрицы (_ij) на вектор сигналов x. В результате получаем вектор входных сигналов нелинейных элементов нейронов: .

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

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

Что можно сделать, если мы умеем вычислять градиент квадратичной формы?

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

Зададим теперь функционирование сети формулой

(8)

Нелинейных элементов вовсе не нужно! Каждый (j-й) нейрон имеет входные веса для связей с другими нейронами (ij), вес для постоянного единичного входного сигнала и вес для связи нейрона с самим собой (передачи на него его же сигнала с предыдущего шага). Выбор шага h>0 может вызвать затруднение (он зависит от коэффициентов минимизируемого многочлена). Есть, однако, простое решение: в каждый момент дискретного времени T выбирается свое значение . Достаточно, чтобы шаг стремился со временем к нулю, а сумма шагов _ к бесконечности (например, ).

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

Решение системы линейных уравнений сводится к минимизации многочлена



Поэтому решение системы может производиться нейронной сетью. Простейшая сеть, вычисляющая градиент этого многочлена, не полносвязна, а состоит из двух слоев: первый с матрицей связей , второй _ с транспонированной матрицей . Постоянный единичный сигнал подается на связи с весами на первом слое. Минимизация этого многочлена, а значит и решение системы линейных уравнений, может проводиться так же, как и в общем случае, в соответствии с формулой . Усовершенствованные варианты алгоритма решения можно найти в работах Сударикова [8].

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

следует использовать:

(9)

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

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

,

где Mx _ вектор математических ожиданий координат, , _ ковариационная матрица, n _ размерность пространства данных,

.

Напомним определение матрицы :

,

где M _ символ математического ожидания, нижний индекс соответствует номеру координаты.

В частности, простейшая оценка ковариационной матрицы по выборке дает:

где m _ число элементов в выборке, верхний индекс j _ номер вектора данных в выборке, верхний индекс Т означает транспонирование, а _ произведение вектора-столбца на вектор-строку (тензорное произведение).

Пусть у вектора данных x известно несколько координат: . Наиболее вероятные значения неизвестных координат должны доставлять условный максимум показателю нормального распределения _ многочлену второго порядка (при условии ). Эти же значения будут условными математическими ожиданиями неизвестных координат при заданных условиях.

Таким образом, чтобы построить сеть, заполняющую пробелы в данных, достаточно сконструировать сеть для поиска точек условного минимума многочлена при условиях следующего вида: . Матрица связей Q выбирается из условия , где _ ковариационная матрица (ее оценка по выборке).

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

Если же добавка имеет вид , то

(10)

Заметим, что решение задачи (точка условного минимума многочлена) не меняется при умножении Q на число. Поэтому полагаем:

где 1 _ единичная матрица, >0 _ достаточно малое число, _ k+1-й вектор данных, _ среднее значение вектора данных, уточненное с учетом :

=

В формуле для пошагового накопления матрицы Q ее изменение Q при появлении новых данных получается с помощью вектора y=, пропущенного через сеть: , где z=Qy. Параметр выбирается достаточно малым для того, чтобы обеспечить положительную определенность получаемых матриц (и, по возможности, их близость к истинным значениям Q).

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

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

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

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

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

, (11)

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

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

(12)

где верхними индексами обозначаются номера векторов-эталонов, нижними _ координаты векторов.

Функция H называется «энергией» сети, она минимизируется в ходе функционирования. Слагаемое вводится для того, чтобы со временем возрастала проекция вектора x на те эталоны, которые к нему ближе, слагаемое обеспечивает стремление координат вектора x к . Параметр определяет соотношение между интенсивностями этих двух процессов. Целесообразно постепенно менять со временем, начиная с малых <1, и приходя в конце концов к >1.

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

. (13)

Эта простая формула имеет чрезвычайно важное значение для развития теории нейронных сетей. Вклад k-го эталона в связь между i-м и j-м нейронами () равен +1, если i-я и j-я координаты этого эталона имеют одинаковый знак, и равен _1, если они имеют разный знак.

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

3. Сети Кохонена для кластер-анализа и классификации без учителя

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

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

Итак, зачем нужно строить отношения эквивалентности между объектами? В первую очередь - для фиксации знаний. Люди накапливают знания о классах объектов - это практика многих тысячелетий, зафиксированная в языке: знание относится к имени класса (пример стандартной древней формы: "люди смертны", "люди" - имя класса). В результате классификации как бы появляются новые имена и правила их присвоения.

Для каждого нового объекта мы должны сделать два дела:

1) найти класс, к которому он принадлежит;

2) использовать новую информацию, полученную об этом объекте, для исправления (коррекции) правил классификации.

Какую форму могут иметь правила отнесения к классу? Веками освящена традиция представлять класс его "типичным", "средним", "идеальным" и т.п. элементом. Этот типичный объект является идеальной конструкцией, олицетворяющей класс.

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

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

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

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

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

Пусть {x^p } - векторы значений признаков для рассматриваемых объектов и в пространстве таких векторов определена мера их близости {x,y}. Для определенности примем, что чем ближе объекты, тем меньше . С каждым классом будем связывать его типичный объект. Далее называем его ядром класса. Требуется определить набор из m ядер y¹ , y² , ... y^m и разбиение {x^p} на классы: минимизирующие следующий критерий

, (14)

где для каждого (i-го) класса _ сумма расстояний от принадлежащих ему точек выборки до ядра класса:

. (15)

Минимум Q берется по всем возможным положениям ядер и всем разбиениям {x^p}на m классов Y_i.

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

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

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

Сетевые алгоритмы классификации без учителя строятся на основе итерационного метода динамических ядер. Опишем его сначала в наиболее общей абстрактной форме. Пусть задана выборка предобработанных векторов данных {x^p}. Пространство векторов данных обозначим E. Каждому классу будет соответствовать некоторое ядро a. Пространство ядер будем обозначать A. Для каждых xE и aA определяется мера близости d(x,a). Для каждого набора из k ядер a₁,...,a_k и любого разбиения {x^p} на k классов {x^p}=P₁P₂...P_k определим критерий качества:

(16)

Требуется найти набор a₁,...,a_k и разбиение {x^p}=P₁P₂...P_k, минимизирующие D.

Шаг алгоритма разбивается на два этапа:

1-й этап - для фиксированного набора ядер a₁,...,a_k ищем минимизирующее критерий качества D разбиение {x^p}=P₁P₂...P_k; оно дается решающим правилом: xP_i, если d(x ,a_i )<d(x ,a_j ) при ij, в том случае, когда для x минимум d(x,a) достигается при нескольких значениях i, выбор между ними может быть сделан произвольно;

2-й этап - для каждого P_i (i=1,...,k), полученного на первом этапе, ищется a_iA, минимизирующее критерий качества (т.е. слагаемое в D для данного i -

Начальные значения a₁,...,a_k, {x^p}=P₁P₂...P_k выбираются произвольно, либо по какому-нибудь эвристическому правилу.

На каждом шаге и этапе алгоритма уменьшается критерий качества D, отсюда следует сходимость алгоритма - после конечного числа шагов разбиение {x^p}=P₁P₂...P_k уже не меняется.

Если ядру a_i сопоставляется элемент сети, вычисляющий по входному сигналу x функцию d(x,a_i), то решающее правило для классификации дается интерпретатором "победитель забирает все": элемент x принадлежит классу P_i, если выходной сигнал i-го элемента d(x,a_i) меньше всех остальных

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

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

В простейшем случае пространство ядер A совпадает с пространством векторов x, а мера близости d(x,a) - положительно определенная квадратичная форма от x_a, например, квадрат евклидового расстояния или другая положительно определенная квадратичная форма. Тогда ядро a_i, минимизирующее D_i, есть центр тяжести класса P_i :

, (17)

где |P_i| _ число элементов в P_i.

В этом случае также упрощается и решающее правило, разделяющее классы. Обозначим d(x,a)=(x-a,x-a), где (.,.) _ билинейная форма (если d - квадрат евклидового расстояния между x и a, то (.,.) - обычное скалярное произведение). В силу билинейности

d(x,a)=(x_a,x_a)=(x,x)_2(x,a)+(a,a).

Чтобы сравнить d(x,a_i) для разных i и найти среди них минимальное, достаточно вычислить линейную неоднородную функцию от x:

d₁(x,a_i) = (a_i,a_i)_2(x,a_i).

Минимальное значение d(x,a_i) достигается при том же i, что и минимум d₁(x,a_i), поэтому решающее правило реализуется с помощью k сумматоров, вычисляющих d(x,a) и интерпретатора, выбирающего сумматор с минимальным выходным сигналом. Номер этого сумматора и есть номер класса, к которому относится x.

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

где _ координаты векторов, (и аналогично ), n _ размерность пространства данных, (и аналогично ).

Предполагается, что данные предварительно обрабатываются (нормируются и центрируются) по правилу:

.

Точно также нормированы и центрированы векторы ядер a. Поэтому все обрабатываемые векторы и ядра принадлежат сечению единичной евклидовой сферы (||x||=1) гиперплоскостью (). В таком случае .

Задача поиска ядра для данного класса P имеет своим решением

. (18)

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

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

1. Базовый способ: для вектора данных xⁱ и каждого ядра a_i вычисляется y_i=d(x,a_i) (условимся считать, что правильному ядру отвечает максимум d, изменяя, если надо, знак d); по правилу «победитель забирает все» строка ответов y_i преобразуется в строку, где только один элемент, соответствующий максимальному y_i, равен 1, остальные _ нули. Эта строка и является результатом функционирования сети. По ней может быть определен номер класса (номер места, на котором стоит 1) и другие показатели.

2. Метод аккредитации: за слоем элементов базового метода, выдающих сигналы 0 или 1 по правилу "победитель забирает все" (далее называем его слоем базового интерпретатора), надстраивается еще один слой выходных сумматоров. С каждым (i-м) классом ассоциируется q-мерный выходной вектор zⁱ с координатами zⁱ_j . Он может формироваться по-разному: от двоичного представления номера класса до вектора ядра класса. Вес связи, ведущей от i-го элемента слоя базового интерпретатора к j-му выходному сумматору определяется в точности как zⁱ_j . Если на этом i-м элементе базового интерпретатора получен сигнал 1, а на остальных - 0, то на выходных сумматорах будут получены числа zⁱ_j.

3. Нечеткая классификация. Пусть для вектор данных x обработан слоем элементов, вычисляющих y_i=d(x,a_i). Идея дальнейшей обработки состоит в том, чтобы выбрать из этого набора {y_i} несколько самых больших чисел и после нормировки объявить их значениями функций принадлежности к соответствующим классам. Предполагается, что к остальным классам объект наверняка не принадлежит. Для выбора семейства G наибольших y_i определим следующие числа:

где число характеризует отклонение "уровня среза" s от среднего значения , по умолчанию обычно принимается =0.

Множество J={i|y_iG} трактуется как совокупность номеров тех классов, к которым может принадлежать объект, а нормированные на единичную сумму неотрицательные величины

(при iJ и f = 0 в противном случае)

интерпретируются как значения функций принадлежности этим классам.

4. Метод интерполяции надстраивается над нечеткой классификацией аналогично тому, как метод аккредитации связан с базовым способом. С каждым классом связывается q-мерный выходной вектор zⁱ. Строится слой из q выходных сумматоров, каждый из которых должен выдавать свою компоненту выходного вектора. Весовые коэффициенты связей, ведущих от того элемента нечеткого классификатора, который вычисляет f_i, к j-му выходному сумматору определяются как zⁱ_j. В итоге вектор выходных сигналов сети есть

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

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

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

Литература

1. Розенблатт Ф. Принципы нейродинамики. Перцептрон и теория механизмов мозга. М.: Мир, 1965. 480 с.

2. Минский М., Пайперт С. Персептроны. - М.: Мир, 1971.

3. Ивахненко А.Г. Персептроны. - Киев: Наукова думка, 1974.

4. Hopfield J.J. Neural Networks and Physical systems with emergent collective computational abilities//Proc. Nat. Sci. USA. 1982. V.79. P. 2554-2558.

5. Уоссермен Ф. Нейрокомпьютерная техника.- М.: Мир, 1992.

6. Итоги науки и техники. Сер. "Физ. и Матем. модели нейронных сетей" / Под ред. А.А. Веденова. - М.: Изд-во ВИНИТИ, 1990-92 - Т. 1-5.

7. Фролов А.А., Муравьев И.П. Нейронные модели ассоциативной памяти.- М.: Наука, 1987.- 160 с.

8. Cудариков В.А. Исследование адаптивных нейросетевых алгоритмов решения задач линейной алгебры // Нейрокомпьютер, 1992. № 3,4. С. 13-20.

9. Кохонен Т. Ассоциативная память. - М.: Мир, 1980.

10. Кохонен Т. Ассоциативные запоминающие устройства. - М.: Мир, 1982.

11. Фор А. Восприятие и распознавание образов.- М.: Машиностроение, 1989.- 272 с.

12. Горбань А.Н., Россиев Д.А. Нейронные сети на персональном компьютере. Новосибирск: Наука (Сиб. отделение), 1996. 276 с.

13. Кендалл М., Стьюарт А. Статистические выводы и связи.- М.: Наука, 1973.- 900 с.

14. Мостеллер Ф., Тьюки Дж. Анализ данных и регрессия.- М.: Финансы и статистика, 1982.- 239 с.

15. Уидроу Б., Стирнз С. Адаптивная обработка сигналов. М.: Мир, 1989. 440 с.

16. Айвазян С.А., Бежаева З.И., Староверов О.В. Классификация многомерных наблюдений.- М.: Статистика, 1974.- 240 с.

17. Дуда Р., Харт П. Распознавание образов и анализ сцен.- М.: Мир, 1976.- 512 с.

18. Ивахненко А.Г. Самообучающиеся системы распознавания и автоматического регулирования.- Киев: Техника, 1969.- 392 с.

19. Искусственный интеллект: В 3-х кн. Кн. 2. Модели и методы: Справочник / под ред. Д.А. Поспелова.- М.: Радио и связь, 1990.- 304 с.

20. Zurada J. M. Introduction to artificial neural systems. PWS Publishing Company, 1992. 785 P.

21. Горбань А.Н. Обучение нейронных сетей. М.: изд. СССР-США СП "ПараГраф", 1990. 160 с.