Участник:Anton goy/Самоорганизующиеся карты Кохонена

Автор: Гой Антон, 617 группа.

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Рисунок 1. Структура самоогранизующейся карты Кохонена с шестиугольной решеткой

Самоорганизующаяся карта Кохонена (англ. Self-Organizing Map или сокращено SOM) - это разновидность нейронных сетей, относящаяся к алгоритмам обучения без учителя. Основная цель - найти скрытые закономерности в данных по средством снижения размерности исходного пространства. Важным свойством карт Кохонена является то, что они строят отображение в пространство низкой размерности (обычно двумерное) таким образом, что топология исходного пространства сохраняется. Результат данного отображения - правильная решетка из обученных нейронов - называется "картой" исходного пространства. Алгоритм был разработан известным финским учёным, заслуженным академиком Финской Академии Наук Теуво Кохоненом в 1984(2) году. Карты Кохенана находят успешное применение в задачах кластеризации и визуализации, а также для снижения размерности и детектирования аномалий в данных.

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

Рисунок 2б. Топология слоя Кохонена с прямоугольными ячейками

Рисунок 2а. Топология слоя Кохонена с шестиугольными ячейками

А архитектура карты Кохонена (Рис. 1) представляет два слоя: первый слой состоит из входных нейронов (их количество равно размерности исходного пространства), второй слой (его называют слоем Кохонена) представляет собой строго упорядоченную решетку, в узлах которой расположены нейроны-сумматоры, соедененные со всеми входами сети. Для визуализации топологии слоя Кохонена (Рис. 2) используют либо шестиугольные (Рис. 2а), либо прямоугольные (Рис. 2б) ячейки, в которых распологаются нейроны. Шестиугольные ячейки часто являются более предпочтительными, так как расстояние от центра выбранной ячейки до ее соседей одинаково.

Каждый нейрон $n_j$ слоя Кохонена описывается вектором весов $\mathbf{w}_j$, размерность которого совпадает с размерностью исходного пространства, и координатами нейрона на двумерной плоскости - $\mathbf{r}_j$.

Процесс обучения состоит в настройке векторов весов $\mathbf{w}_j$.

1.2 Математическое описание алгоритма

Пусть $\mathcal{L} = \left\{ \mathbf{x}_i \right\}_{i=1}^{N}$ - некоторое подмножество точек пространства $\mathbb{R}^D$, $\mathbf{x}_i = \left( x_{i}^{(1)}, \dots, x_{i}^{(D)} \right) \in \mathbb{R}^D$. В машинном обучении множество $\mathcal{L}$ называют обучающей выборкой.

Пусть задано $L = X \times Y$ общее количество нейронов в слое Кохонена. И каждому нейрону $n_j$ поствлен в соответствие вектор весов $\mathbf{w}_{j} = \left( w_{j}^{(1)}, \dots, w_{j}^{(D)} \right) \in \mathbb{R}^D$ и вектор $\mathbf{r}_j \in \mathbb{R}^2$, определющий его положение на двумерной плоскости.

Алгоритм обучения (online version):

1. Задать начальные приближение весов $\mathbf{w}_{j}$, $\forall j=1, \dots, L$.

2. Выбрать случайно номер объекта $i \sim Unif[1, N]$.

3. Найти расстояние между объектом $\mathbf{x}_i$ и всеми векторами весов $\mathbf{w}_{j}$

$\rho(\mathbf{x}_i, \mathbf{w}_{j}) = \left\| \mathbf{x}_i - \mathbf{w}_{j} \right\|^2, \quad \forall j=1, \dots, L$

4. Найти нейрон-победитель $n_b$, $b = \arg \min_{\forall j \in \{1, \dots, L\}} \rho(\mathbf{x}_i, \mathbf{w}_{j})$, наиболее близкий к текущему объекту $\mathbf{x}_i$.

5. Для всех неронов $n_j$ пересчитать их веса по следующей формуле:

$\mathbf{w}_{j} \leftarrow \mathbf{w}_{j} + \alpha(t)h_{b, j}(t)(\mathbf{x}_i - \mathbf{w}_{j})$,

где $\alpha(t)$ - темп обучения (learning rate), монотонно убывающая функция от номера итерации $t$;

$h_{b, j}(t)$ - функция определяющая "меру соседства" нейронов $n_b$ и $n_j$.

6. Проверить условие останова. При необходмости перейти на шаг 2.

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

• Начальное приближение для $\mathbf{w}_j$
  • Инициализация случайными значениями. Самый простой способ - $w_j^{(d)} \sim Unif[0, 1]$. Данный подход может потребовать большое количество итераций, так как вектора весов неупорядочены и могут находится на значительном расстоянии от точек обучающей выборки.
  • Инициализация объектами обучающей выборки. Данный способ может позволить уменьшить количество итераций, так как вектора весов будут изначально находятся в области пространства, в которой расположены объекты выборки. Но проблема с неупорядоченностью остается.
  • Инициализация при помощи PCA. При помощи PCA находятся первые две главные компоненты $e_1, e_2$. Затем в плоскости натянутой на ветора $e_1, e_2$ выбирается регулярная сетка точек, которыми и инициализируются вектора $\mathbf{w}_j$. Этот способ является наиболее предпочтительным и на практике показывает хорошие результаты.