Участник: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$. Этот способ является наиболее предпочтительным и на практике показывает хорошие результаты.
• Задание $\alpha(t)$
  • $\alpha(t) = \alpha_0 \exp \left\{ -\frac{t}{\lambda} \right\}$
  • $\alpha(t) = \frac{1}{t}$
  • $\alpha(t) = \lambda^{\frac{t}{T}}, \lambda \in (0, 1)$
• Задание $h_{b,j}(t)$
  • Наиболее популярный способ: $h_{b,j}(t) = \exp \left\{ - \frac{\| \mathbf{r}_b -\mathbf{r}_j \|^2}{2\sigma(t)^2} \right\}$, где $\sigma(t)$ - убывающая функция, которую можно интерпретировать как величину пропорциональную радиусу соседства. Концептуально принцип действия такой меры соседства можно представить следующим образом: пусть в точке $\mathbf{r}_b$ задана окружность с радиусом пропорциональным $\sigma(t)$, тогда за пределом этой окружности степень соседства становится пренебрежимо мала.

Кроме онлайн алгоритма обучения часто на практике применяют более эффективную с точки зрения вычислений batch-версию. Пусть выбрано $B \in \mathbb{N}$. Тогда batch-версия алгоритма описывается следующим образом:

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

1. Задать начальные приближение весов $\mathbf{w}_{j}$, $\forall j=1, \dots, L$.
2. Случайно выбрать множество $\mathcal{B} \subset \{1, \dots, N \}$ размера $B$.
3. Для каждого объекта $\mathbf{x}_i$, $i \in \mathcal{B}$, найти нейрон-победитель $n_{b(i)}$, где $b(i) = \arg \min_{\forall j \in \{1, \dots, L\}} \rho(\mathbf{x}_i, \mathbf{w}_{j})$
4. Пересчитать веса для всех нейронов $\mathbf{w}_j \leftarrow \frac{\sum_{i \in \mathcal{B}}h_{b(i),j}\mathbf{x}_i}{\sum_{i \in \mathcal{B}}h_{b(i),j}}$, $\forall j=1, \dots, L$.
5. Проверить критерий останова. При необходимости перейти на шаг 2.

Интерпретация шага 2 состоит в следующем: веса нейронов преставляют собой выпуклую комбинацию объектов с номерами из $\mathcal{B}$.

1.3 Вычислительное ядро алгоритма

Рассмотрим batch-версию алгоритма. Основные вычисления приходятся на шаг 2, где необходимо вычислять расстояния между всеми $\mathbf{x}_i$, $i \in \mathcal{B}$ и весами нейронов $\mathbf{w}_j$, $j \in \{ 1, \dots, L \}$ и затем искать минимум:

$d_{ij} = \left\| \mathbf{x}_i - \mathbf{w}_j \right\|^2 = \left\|\mathbf{x}_i\right\|^2 - 2 \mathbf{x}_i^{T}\mathbf{w}_j + \left\|\mathbf{w}_j\right\|^2$

Так как нас будет интересовать минимум по $j$, то первое слагаемое $\left\|\mathbf{x}_i\right\|^2$ можно не учитывать. Тогда все что нам нужно это вычислить матрицу квази-расстояний $\mathbf{D} = \| \hat{d}_{ij} \|_{B \times L}$, где $\hat{d}_{ij} = \left\|\mathbf{w}_j\right\|^2 - 2 \mathbf{x}_i^{T}\mathbf{w}_j$

Сложность вычисления $\mathbf{D}$ составляет $O\left(L D B \right)$, учитывая что $\left\|\mathbf{w}_j\right\|^2$ можно вычислить за один проход по всем нейронам.

Еще одной вычислительно интенсивной частью является вычисление $\mathbf{w}_j$.

1.4 Макроструктура алгоритма

Пусть $\mathbf{X}_{\mathcal{B}}$ - матрица, строками которой являются объекты $\mathbf{x}_i$ таких, что $i \in \mathcal{B}$, а $\mathbf{W}$ - матрица, строками которой являются веса нейронов.

Тогда на макроуровне можно выделить следующие операции:

1. $\mathbf{D} \leftarrow ComputePairwiseDistances(\mathbf{X}_{\mathcal{B}}, \mathbf{W})$
2. $\mathbf{b} \leftarrow FindClosestNeurons(\mathbf{D})$
3. $\mathbf{W} \leftarrow ComputeWeightedSumsAcrossObjects(\mathbf{X}_{\mathcal{B}}, \mathbf{b})$

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

Функция $ComputePairwiseDistances$ вычисляет квазирасстояния между объектами и нейронами и возвращает матрицу $\mathbf{D} \in \mathbb{R}^{B \times L}$.

Функция $FindClosestNeurons$ в каждой строке матрицы $\mathbf{D}$ находит минимальное значение и возвращает вектор $\mathbf{b} \in \mathbb{R}^B$, такой что элемент в позиции $i$ соответствует номеру нейрона-победителя для объекта $\mathbf{x}_i$.

Функция $ComputeWeightedSumsAcrossObjects$ вычисляет новые значения весов для каждого нейрона, суммируя строки матрицы $\mathbf{X}_{\mathcal{B}}$ с весами пропорциональными их мере соседства с соответствующим нейроном-победителем. Неявно данная функция также использует вектор положений $\mathbf{r}_j$ нейронов на двумерной плоскости, но так как эти положения остаются неизменными в продолжении всего обучения, мы не будем указывать их явно в аргументах.

1.5 Схема реализации последовательного алгоритма

В этой секции, используя макрооперции из предыдущего раздела, дадим очень краткий псевдокод batch-версии алгоритма, который легко позволяет понимать основные строительные блоки данного алгоритма:

Рисунок 3. Способ инициализации $\mathbf{r}_j$ как узлов шестиугольных ячеек на плоскости

$\begin{align} \mathbf{W} := &InitializeWeights() \\ \mathbf{R} := &InitializeNeuronPositionsOnPlane() \\ \mathbf{FOR} & \ t=1 \ \mathbf{TO} \ MAX\_ITERATIONS \ \mathbf{DO} \\ & \mathcal{B} \leftarrow RandomSample\left( \{1, \dots, N\} \right) \\ & \mathbf{D} \leftarrow ComputePairwiseDistances(\mathbf{X}_{\mathcal{B}}, \mathbf{W}) \\ \quad & \mathbf{b} \leftarrow FindClosestNeurons(\mathbf{D}) \\ \quad & \mathbf{W} \leftarrow ComputeWeightedSumsAcrossObjects(\mathbf{X}_{\mathcal{B}}, \mathbf{b}) \\ \end{align}$

Здесь мы использовали $\mathbf{R} \in \mathbb{R}^{L \times 2}$ как обозначение для матрицы, строками которой являются $\mathbf{r}_j$. Способ инициализации этих векторов для решетки с шестиугольными ячейками показан на Рис. 3.

Как видно из алгоритма, основной структурой данных, которая нам потребуется, будет обычная матрица, а также вектора. Стоит отметить, что алгоритм в целом неплохо оптимизируем в терминах матричных и веторных операций. Например, вычисление матрицы $\mathbf{D}$ на языке Python с использованием библиотеки оптимизированных матричных вычислений NumPy будет выглядить следующим образом:

  W_norms = numpy.linalg.norm(W, axis=1)^2 # Вычисляем квадрат нормы для каждого вектора весов
  D = W_norms.T - 2 * numpy.dot(X, W.T) # Вычисляем матрицу квазирасстояний

А вычисление вектора $\mathbf{b}$ можно реализовать всего одной строчкой:

  b = D.argmin(axis=1)

1.6 Последовательная сложность алгоритма

В разделе 1.3 мы уже попытались дать некоторые оценки сложности алгоритма обучения самоорганизующейся карты Кохонена. Ниже мы рассмотрим последовательную сложность более подробно.

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

Пусть, как и ранее, $N$ - количество объектов в обучающей выборке, $L$ - количество нейронов в слое Кохонена, $D$ - размерность признакового пространства объектов (размерность векторов $\mathbf{x}_i$) и $B$ - количество объектов в случайной подвыборке отбираемой на каждой итерации алгоритма.

Оценим сложность одной итерации алгоритма:

1. Функция $ComputePairwiseDistances$.
   1. $L \times D$ умножений и $L \times (D - 1)$ сложений для вычисления всех норм $\left\|\mathbf{w}_j\right\|^2$;
   2. $B \times L \times D$ умножений и $B \times L \times (D - 1)$ сложений для вычисления всех скалярных произведений $\mathbf{x}_i^{T}\mathbf{w}_j$;
   3. $B \times L$ сложений для вычисления $\hat{d}_{ij}$;
   4. Итого: $L \times D + L \times (D - 1) + B \times L \times D + B \times L \times (D - 1) + B \times L = 2 \times L \times D \times (B + 1) - L$ арифметических операций над вещественными числами. Тогда асимптотическая сложность равна $O(B \times L \times D)$;
2. Функция $FindClosestNeurons$.
   1. В этой функции используются только операции сравнения между вещественными числами и их количество составляет $B \times (L - 1)$ или асимптотически $O(B \times L)$;
3. Функция $ComputeWeightedSumsAcrossObjects$.
   1. Будем считать что для вычисления $h_{b, j}(t)$ требуется некоторое константное число операций $Const$. Тогда для вычисления всех таких функций требуется $B \times L \times Const$ операций.
   2. Вычисление $\mathbf{w}_j$ делится на вычисление числителя и выисление знаменателя. В первом случае нам требуется выполнить $B \times D$ умножений и $(B - 1) \times D$ сложений. Во втором случае мы выполняем $B$ сложений.
   3. Итого: $(2 \times B \times D + B - D + 1) \times L + B \times L \times Const$ операций. Асимптотическая сложность: $O(B \times L \times D)$

В итоге асимптотическая сложность одной итерации будет составлять $O(B \times L \times D)$.

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