Участник: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$, где $X$ и $Y$ - количество нейронов в строках и столбцах соответственно), а также для каждого нейрона определено его положение в слое Кохонена $\mathbf(x, y)$, где $x \in \left\{ 1, \dots, X \right\}$, а $y \in \left\{ 1, \dots, Y \right\}$. Пусть $\mathbf{w}_{x,y} = \left( w_{x,y}^{(1)}, \dots, w_{x,y}^{(D)} \right) \in \mathbb{R}^D$ - вектор весов соответствующий нейрону в позиции $(x, y)$.

Алгоритм обучения:

1. Найти начальное приближение весов $\mathbf{w}_{x,y}$, для $\forall x=1, \dots, X$ и $\forall y=1, \dots, Y$.

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

3. Для всех пар $(x, y)$ найти расстояние между $\mathbf{x}_i$ и вектором весов $\mathbf{w}_{x, y}$

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

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

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

$\mathbf{w}_{x, y} \leftarrow \mathbf{w}_{x, y} + \alpha(t)h_{x^*, y^*}(t)(\mathbf{x}_i - \mathbf{w}_{x, y})$,

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