Нейронная сеть Кохонена

Материал из MachineLearning.

(Различия между версиями)

Версия 22:09, 9 сентября 2008

Нейронные сети Кохонена (Kohonen neural network) — класс нейронных сетей, основным элементом которых является слой Кохонена. Слой Кохонена состоит из адаптивных линейных сумматоров («линейных формальных нейронов»). Как правило, выходные сигналы слоя Кохонена обрабатываются по правилу «победитель забирает всё»: наибольший сигнал превращается в единичный, остальные обращаются в ноль.

По способам настройки входных весов сумматоров и по решаемым задачам различают много разновидностей сетей Кохонена.^[1] Наиболее известные из них:

Сети векторного квантования сигналов^[1], тесно связанные с простейшим базовым алгоритмом кластеризации (метод динамических ядер или K-средних, то есть K-means)
Самоорганизующиеся карты Кохонена (Self-Organising Maps, SOM)^[1]
Сети векторного квантования, обучаемые с учителем (Learning Vector Quantization)^[1]

Содержание

1 Слой Кохонена
- 1.1 Базовая версия
- 1.2 Геометрическая интерпретация
2 Сети векторного квантования
3 Самоорганизующиеся карты Кохонена
- 3.1 Идея и алгоритм обучения
- 3.2 Самоорганизующиеся карты и главные многообразия
4 Упругие карты
5 Сети векторного квантования, обучаемые с учителем
6 Ссылки

Слой Кохонена

Базовая версия

Слой Кохонена состоит из некоторого количества $n$ параллельно действующих линейных элементов. Все они имеют одинаковое число входов $m$ и получают на свои входы один и тот же вектор входных сигналов $x=(x_1,... x_m)$ . На выходе $j$ го линейного элемента получаем сигнал

$y_j=w_{j0} + \sum_{i=1}^m w_{ji}x_i,$

где $w_{ji}$ — весовой коэффициент $i$ го входа $j$ го нейрона, $w_{j0}$ — пороговой коэффициент.

После прохождения слоя линейных элементов сигналы посылаются на обработку по правилу «победитель забирает всё»: среди выходных сигналов $y_j$ ищется максимальный; его номер $j_{\max}={\rm arg} \max_{j}\{y_j\}$ . Окончательно, на выходе сигнал с номером $j_{\max}$ равен единице, остальные — нулю. Если максимум одновременно достигается для нескольких $j_{\max}$ , то либо принимают все соответствующие сигналы равными единице, либо только первый в списке (по соглашению). «Нейроны Кохонена можно воспринимать как набор электрических лампочек, так что для любого входного вектора загорается одна из них.»^[1]

Геометрическая интерпретация

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

Большое распространение получили слои Кохонена, построенные следующим образом: каждому ( $j$ му) нейрону сопоставляется точка $W_j = (w_{j1},...w_{jm})$ в $m$ -мерном пространстве (пространстве сигналов). Для входного вектора $x=(x_1,... x_m)$ вычисляется его расстояния $\rho_j(x)$ до точек $W_j$ и «ближайший получает всё» — тот нейрон, для которого это расстояние минимально, выдаёт единицу, остальные — нули. Следует заметить, что для сравнения расстояний достаточно вычислять линейную функцию сигнала:

$\rho_j(x)^2=\|x-W_j\|^2=\|W_j\|^2-2\sum_{i=1}^m w_{ji}x_i + \|x\|^2.$

Последнее слагаемое $\|x\|^2$ одинаково для всех нейронов, поэтому для нахождения ближайшей точки оно не нужно. Задача сводится к поиску номера наибольшего из значений линейных функций:

$j_{\max}={\rm arg} \max_{j}\left\{\sum_{i=1}^m w_{ji}x_i-\frac{1}{2}\left\|W_j\right\|^2\right\}.$

Таким образом, координаты точки $W_j = (w_{j1},...w_{jm})$ совпадают с весами линейного нейрона слоя Кохонена (при этом значение порогового коэффициента $w_{j0} =-\|W_j\|^2/2$ ).

Если заданы точки $W_j = (w_{j1},...w_{jm})$ , то $m$ -мерное пространство разбивается на соответствующие многогранники Вороного-Дирихле $V_j$ : многогранник $V_j$ состоит из точек, которые ближе к $W_j$ , чем к другим $W_k$ ( $k \neq j$ ).^[1]

Сети векторного квантования

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

$D=\sum_{j=1}^k \sum_{x \in K_j}\|x-W_j\|^2,$

где $K_j$ состоит из тех точек $x \in S$ , которые ближе к $W_j$ , чем к другим $W_l$ ( $l \neq j$ ). Другими словами, $K_j$ состоит из тех точек $x \in S$ , которые кодируются кодовым вектором $W_j$ .

Если совокупность $S$ задана и хранится в памяти, то стандартным выбором в обучении соответствующей сети Кохонена является метод K-средних. Это метод расщепления:

при данном выборе кодовых векторов (они же весовые векторы сети) $W_j$ минимизацией $D$ находим множества $K_j$ — они состоит из тех точек $x \in S$ , которые ближе к $W_j$ , чем к другим $W_l$ ;
при данном разбиении $S$ на множества $K_j$ минимизацией $D$ находим оптимальные позиции кодовых векторов $W_j$ — для оценки по методу наименьших квадратов это просто средние арифметические:

$W_j=\frac{1}{|K_j|}\sum_{x \in K_j} x,$

где $|K_j|$ — число элементов в $K_j$ .

Далее итерируем. Этот метод расщепления сходится за конечное число шагов и даёт локальный минимум искажения.

Если же, например, совокупность $S$ заранее не задана, или по каким-либо причинам не хранится в памяти, то широко используется онлайн метод. Векторы входных сигналов $x$ обрабатываются по одному, для каждого из них находится ближайший кодовый вектор («победитель», который «забирает всё») $W_{j(x)}$ . После этого данный кодовый вектор пересчитывается по формуле

$W^{\rm new}_{j(x)}=W^{\rm old}_{j(x)}(1-\theta)+x\theta,$

где $\theta \in (0,1)$ — шаг обучения. Остальные кодовые векторы на этом шаге не изменяются.

Для обеспечения стабильности используется онлайн метод с затухающей скоростью обучения: если $T$ — количество шагов обучения, то полагают $\theta =\theta(T)$ . Функцию $\theta(T)>0$ выбирают таким образом, чтобы $\theta(T) \to 0$ монотонно при $T \to \infty$ и чтобы ряд $\sum_{T=1}^{\infty}\theta(T)$ расходился, например, $\theta(T)=\theta_0/T$ .

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

Самоорганизующиеся карты Кохонена

Идея и алгоритм обучения

Задача векторного квантования состоит, по своему существу, в наилучшей аппроксимации всей совокупности векторов данных $k$ кодовыми векторами $W_j$ . Самоорганизующиеся карты Кохонена также аппроксимируют данные, однако при наличии дополнительной структуры в совокупности кодовых векторов (англ. codebook). Предполагается, что априори задана некоторая симметричная таблица «мер соседства» (или «мер близости») узлов: для каждой пары $j,l$ ( $j,l=1,...k$ ) определено число $\eta_{jl}$ ( $0 \leq \eta_{jl} \leq 1$ ) при этом диагональные элементы таблицы близости равны единице ( $\eta_{jj}=1$ ).

Векторы входных сигналов $x$ обрабатываются по одному, для каждого из них находится ближайший кодовый вектор («победитель», который «забирает всё») $W_{j(x)}$ . После этого все кодовые векторы $W_l$ , для которых $\eta_{j(x)l}\neq 0$ , пересчитываются по формуле

$W^{\rm new}_l=W^{\rm old}_l(1- \eta_{j(x)l} \theta)+x\eta_{j(x)l} \theta,$

где $\theta \in (0,1)$ — шаг обучения. Соседи кодового вектора — победителя (по априорно заданной таблице близости) сдвигаются в ту же сторону, что и этот вектор, пропорционально мере близости.

Чаще всего, таблица кодовых векторов представляется в виде фрагмента квадратной решётки на плоскости, а мера близости определяется, исходя из евклидового расстояния на плоскости.

Самоорганизующиеся карты Кохонена служат, в первую очередь, для визуализации и первоначального («разведывательного») анализа данных.^[1] Каждая точка данных отображается соответствующим кодовым вектором из решётки. Так получают представление данных на плоскости («карту данных»). На этой карте возможно отображение многих слоёв: количество данных, попадающих в узлы (то есть «плотность данных»), различные функции данных и так далее. При отображении этих слоёв полезен аппарат географических информационных систем (ГИС). В ГИС подложкой для изображения информационных слоев служит географическая карта. Карта данных является подложкой для произвольного по своей природе набора данных. Она служит заменой географической карте там, где ее просто не существует. Принципиальное отличие в следующем: на географической карте соседние объекты обладают близкими географическими координатами, на карте данных близкие объекты обладают близкими свойствами. С помощью карты данных можно визуализировать данные, одновременно нанося на подложку сопровождающую информацию (подписи, аннотации, атрибуты, информационные раскраски).^[1] Карта служит также информационной моделью данных. С её помощью можно заполнять пробелы в данных. Эта способность используется, например, для решения задач прогнозирования.

Самоорганизующиеся карты и главные многообразия

Идея самоорганизующихся карт очень привлекательна и породила массу обобщений, однако, строго говоря, мы не знаем, что мы строим: карта — это результат работы алгоритма и не имеет отдельного («объектного») определения. Есть, однако, близкая теоретическая идея — главные многообразия (principal manifolds).^[1] Эти многообразия обобщают линейные главные компоненты. Они были введены как линии или поверхности, проходящие через «середину» распределения данных, с помощью условия самосогласованности: каждая точка $x$ на главном многообразии $M$ является условным математическим ожиданием тех векторов $z$ , которые проектируются на $x$ (при условии $x=P(z)$ , где $P$ — оператор проектирования окрестности $M$ на $M$ ),

$x=\mathbf{E}(z|P(z)=x).$

Самоорганизующиеся карты могут рассматриваться как аппроксимации главных многообразий и популярны в этом качестве^[1].

Упругие карты

Метод аппроксимации многомерных данных, основанный на минимизации «энергии упругой деформации» карты, погружённой в пространство данных, был предложен А. Н. Горбанём в 1996 году, и впоследствии развит им совместно с А. Ю. Зиновьевым, А. А. Россиевым и А. А. Питенко.^[1] Метод основан на аналогии между главным многообразием и эластичной мембраной и упругой пластиной. В этом смысле он является развитием классической идеи сплайна (хотя упругие карты и не являются многомерными сплайнами).

Пусть задана совокупность входных векторов $S$ . Так же, как и сети векторного квантования и самоорганизующиеся карты, упругая карта представлена как совокупность кодовых векторов (узлов) $W_j$ в пространстве сигналов. Множество данных $S$ разделено на классы $K_j$ , состоящие из тех точек $x \in S$ , которые ближе к $W_j$ , чем к другим $W_l$ ( $l \neq j$ ). Искажение кодирования $D$

$D=\sum_{j=1}^k \sum_{x \in K_j}\|x-W_j\|^2,$

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

На множестве узлов задана дополнительная структура: некоторые пары связаны «упругими связями», а некоторые тройки объединены в «рёбра жёсткости». Обозначим множество пар, связанных упругими связями, через $E$ , а множество троек, составляющих рёбра жёсткости, через $G$ . Например, в квадратной решётке ближайшие узлы (как по вертикали, так и погоризонтали) связываются упругими связями, а ребра жёсткости образуются вертикальными и горизонтальными тройками ближайших узлов. Энергия деформации карты состоит из двух слагаемых:

энергия растяжения $U_{E}=\;\;\lambda\; \sum_{(W_i,W_j) \in E} \|W_i -W_j\|^2;$

энергия изгиба $U_{G}=\;\;\mu\; \sum_{(W_i,W_j,W_l) \in G} \|W_i -2W_j+W_l\|^2;$

где $\lambda, \mu$ — соответствующие модули упругости.

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

$U=D+U_{E}+U_{G};$

Если разбиение совокупности входных векторов $S$ на классы $K_j$ фиксировано, то минимизация $U$ — линейная задача с разреженной симметричной матрицей коэффициентов. Поэтому, как и для сетей векторного квантования, применяется метод расщепления: фиксируем $\{W_j\}$ — ищем $\{K_j\}$ — для данных $\{K_j\}$ ищем $\{W_j\}$ — для данных $\{W_j\}$ ищем $\{K_j\}$ — … Алгоритм сходится к (локальному) минимуму $U$ .

Метод упругих карт позволяет решать все задачи, которые решают самоорганизующиеся карты Кохонена, однако обладает большей регулярностью и предсказуемостью. При увеличении модуля изгиба $\mu$ упругие карты приближаются к линейным главным компонентам. При уменьшении обоих модулей упругости они превращаются в Кохоненовские сети векторного квантования. В настоящее время упругие карты интенсивно используются для анализа многомерных данных в биоинформатике.^[1] Соответствующее программное обеспечение опубликовано и свободно доступно на сайте Института Кюри (Париж).^[1]^[1]

Сети векторного квантования, обучаемые с учителем

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

Решается задача классификации. Число классов может быть любым. Изложим алгоритм для двух классов, ${\bold A}$ и ${\bold B}$ . Исходно для обучения системы поступают данные, класс которых известен. Задача: найти для класса ${\bold A}$ некоторое количество $k_{\bold A}$ кодовых векторов $W_j^{\bold A}$ , а для класса ${\bold B}$ некоторое (возможно другое) количество $k_{\bold B}$ кодовых векторов $W_l^{\bold B}$ таким образом, чтобы итоговая сеть Кохонена с $k_{\bold A}+k_{\bold B}$ кодовыми векторами $W_j^{\bold A}$ , $W_l^{\bold B}$ (объединяем оба семейства) осуществляла классификацию по следующему решающему правилу:

если для вектора входных сигналов $x$ ближайший кодовый вектор («победитель», который в слое Кохонена «забирает всё») принадлежит семейству $\{W_j^{\bold A}\}$ , то $x$ принадлежит классу ${\bold A}$ ; если же ближайший к $x$ кодовый вектор принадлежит семейству $\{W_l^{\bold B}\}$ , то $x$ принадлежит классу ${\bold B}$ .

С каждым кодовым вектором объединённого семейства $\{W_j^{\bold A}\} \cup \{W_l^{\bold B}\}$ связан многогранник Вороного-Дирихле. Обозначим эти многогранники $V_j^{\bold A}$ , $V_l^{\bold B}$ соответственно. Класс ${\bold A}$ в пространстве сигналов, согласно решающему правилу, соответствует объединению $\cup_j V_j^{\bold A}$ , а класс ${\bold B}$ соответствует объединению $\cup_l V_l^{\bold B}$ . Геометрия таких объединений многогранников может быть весьма сложной (см. Рис с примером возможного разбиения на классы).

Правила обучения сети онлайн строится на основе базового правила обучения сети векторного квантования. Пусть на вход системы подаётся вектор сигналов $x$ , класс которого известен. Если он классифицируется системой правильно, то соответствующий $x$ кодовый вектор $W$ слегка сдвигается в сторону вектора сигнала («поощрение»)

$W^{\rm new}=W^{\rm old}(1-\theta)+x\theta,$

Если же $x$ классифицируется неправильно, то соответствующий $x$ кодовый вектор $W$ слегка сдвигается в противоположную сторону от сигнала («наказание»)

$W^{\rm new}=W^{\rm old}(1+\theta)-x\theta,$

где $\theta \in (0,1)$ — шаг обучения. Для обеспечения стабильности используется онлайн метод с затухающей скоростью обучения. Возможно также использование разных шагов для «поощрения» правильного решения и для «наказания» неправильного

Это — простейшая (базовая) версия метода^[1]. Существует множество других модификаций.

Ссылки

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%9D%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%B5%D1%82%D1%8C_%D0%9A%D0%BE%D1%85%D0%BE%D0%BD%D0%B5%D0%BD%D0%B0»

@@ Строка 28: / Строка 28: @@
 === Геометрическая интерпретация ===
-[[Image:Coloured_Voronoi_2D.svg|right|thumb|222px|Разбиение плоскости на многоугольники Вороного-Дирихле для случайно выбранных точек (каждая точка указана в своём многоугольнике).]]
+[[Image:Coloured_Voronoi_2D.png|right|thumb|222px|Разбиение плоскости на многоугольники Вороного-Дирихле для случайно выбранных точек (каждая точка указана в своём многоугольнике).]]
 Большое распространение получили слои Кохонена, построенные следующим образом: каждому (<tex>j</tex>му) нейрону сопоставляется точка <tex>W_j = (w_{j1},...w_{jm})</tex> в <tex>m</tex>-мерном пространстве (пространстве сигналов). Для входного вектора <tex>x=(x_1,... x_m)</tex> вычисляется его расстояния <tex>\rho_j(x)</tex> до точек <tex>W_j</tex> и «ближайший получает всё» — тот нейрон, для которого это расстояние минимально, выдаёт единицу, остальные — нули. Следует заметить, что для сравнения расстояний достаточно вычислять линейную функцию сигнала:
 : <tex>\rho_j(x)^2=\|x-W_j\|^2=\|W_j\|^2-2\sum_{i=1}^m w_{ji}x_i + \|x\|^2.</tex>