Участник:Anton goy/Самоорганизующиеся карты Кохонена: различия между версиями
Anton goy (обсуждение | вклад) |
Anton goy (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
** Наиболее популярный способ: <math>h_{b,j}(t) = \exp \left\{ - \frac{\| \mathbf{r}_b -\mathbf{r}_j \|^2}{2\sigma(t)^2} \right\}</math>, где <math>\sigma(t)</math> - убывающая функция. | ** Наиболее популярный способ: <math>h_{b,j}(t) = \exp \left\{ - \frac{\| \mathbf{r}_b -\mathbf{r}_j \|^2}{2\sigma(t)^2} \right\}</math>, где <math>\sigma(t)</math> - убывающая функция. | ||
Кроме онлайн алгоритма обучения часто на практике применяют более эффективную с точки зрения вычислений batch-версию: | Кроме онлайн алгоритма обучения часто на практике применяют более эффективную с точки зрения вычислений batch-версию. Пусть выбрано <math>B \in \mathbb{N}</math>. Тогда batch-версия алгоритма описывается следующим образом: | ||
'''Алгоритм обучения (batch version):''' | '''Алгоритм обучения (batch version):''' | ||
# Задать начальные приближение весов <math>\mathbf{w}_{j}</math>, <math>\forall j=1, \dots, L</math>. | # Задать начальные приближение весов <math>\mathbf{w}_{j}</math>, <math>\forall j=1, \dots, L</math>. | ||
# Для каждого объекта <math>\mathbf{x}_i</math> найти нейрон-победитель <math>n_{b(i)}</math>, где <math> b(i) = \arg \min_{\forall j \in \{1, \dots, L\}} \rho(\mathbf{x}_i, \mathbf{w}_{j})</math> | # Случайно выбрать множество <math>\mathcal{B} \subset \{1, \dots, N \}</math> размера <math>B</math>. | ||
# Пересчитать веса для всех нейронов <math>\mathbf{w}_j \leftarrow \frac{\sum_{i | # Для каждого объекта <math>\mathbf{x}_i</math>, <math>i \in \mathcal{B}</math>, найти нейрон-победитель <math>n_{b(i)}</math>, где <math> b(i) = \arg \min_{\forall j \in \{1, \dots, L\}} \rho(\mathbf{x}_i, \mathbf{w}_{j})</math> | ||
# Пересчитать веса для всех нейронов <math>\mathbf{w}_j \leftarrow \frac{\sum_{i \in \mathcal{B}}h_{b(i),i}\mathbf{x}_i}{\sum_{i \in \mathcal{B}}h_{b(i),i}}</math>, <math>\forall j=1, \dots, L</math>. | |||
# Проверить критерий останова. При необходимости перейти на шаг 2. | # Проверить критерий останова. При необходимости перейти на шаг 2. | ||
Интерпретация шага 2 состоит в следующем: веса нейронов преставляют собой выпуклую комбинацию объектов с номерами из <math>\mathcal{B}</math>. | |||
== Вычислительное ядро алгоритма == | == Вычислительное ядро алгоритма == | ||
Версия от 20:17, 10 октября 2016
Автор: Гой Антон, 617 группа.
Свойства и структура алгоритмов
Общее описание алгоритма
Самоорганизующаяся карта Кохонена (англ. Self-Organizing Map или сокращено SOM) - это разновидность нейронных сетей, относящаяся к алгоритмам обучения без учителя. Основная цель - найти скрытые закономерности в данных по средством снижения размерности исходного пространства. Важным свойством карт Кохонена является то, что они строят отображение в пространство низкой размерности (обычно двумерное) таким образом, что топология исходного пространства сохраняется. Результат данного отображения - правильная решетка из обученных нейронов - называется "картой" исходного пространства. Алгоритм был разработан известным финским учёным, заслуженным академиком Финской Академии Наук Теуво Кохоненом в 1984(2) году. Карты Кохенана находят успешное применение в задачах кластеризации и визуализации, а также для снижения размерности и детектирования аномалий в данных.
Карты Кохонена и по своей архитектуре, и по методу обучения отличаются от обычных нейронных сетей прямого распространения. C точки зрения метода обучения, карты Кохонена не используют градиентные методы для минимизации ошибки (как это делается в сетях прямого распространения), поскольку являются алгоритмом обучения без учителя и никак не могут учитывать информацию и метках классов. Поэтому нейронная сеть обучается через соревнование между нейронами: на каждом шаге алгоритма для случайного объекта из обучающей выборки выбирается нейрон-победитель (best matching unit, BMU), который в определенном смысле наиболее похож на данный объект.
А архитектура карты Кохонена (Рис. 1) представляет два слоя: первый слой состоит из входных нейронов (их количество равно размерности исходного пространства), второй слой (его называют слоем Кохонена) представляет собой строго упорядоченную решетку, в узлах которой расположены нейроны-сумматоры, соедененные со всеми входами сети. Для визуализации топологии слоя Кохонена (Рис. 2) используют либо шестиугольные (Рис. 2а), либо прямоугольные (Рис. 2б) ячейки, в которых распологаются нейроны. Шестиугольные ячейки часто являются более предпочтительными, так как расстояние от центра выбранной ячейки до ее соседей одинаково.
Каждый нейрон [math]\displaystyle{ n_j }[/math] слоя Кохонена описывается вектором весов [math]\displaystyle{ \mathbf{w}_j }[/math], размерность которого совпадает с размерностью исходного пространства, и координатами нейрона на двумерной плоскости - [math]\displaystyle{ \mathbf{r}_j }[/math].
Процесс обучения состоит в настройке векторов весов [math]\displaystyle{ \mathbf{w}_j }[/math].
Математическое описание алгоритма
Пусть [math]\displaystyle{ \mathcal{L} = \left\{ \mathbf{x}_i \right\}_{i=1}^{N} }[/math] - некоторое подмножество точек пространства [math]\displaystyle{ \mathbb{R}^D }[/math], [math]\displaystyle{ \mathbf{x}_i = \left( x_{i}^{(1)}, \dots, x_{i}^{(D)} \right) \in \mathbb{R}^D }[/math]. В машинном обучении множество [math]\displaystyle{ \mathcal{L} }[/math] называют обучающей выборкой.
Пусть задано [math]\displaystyle{ L = X \times Y }[/math] общее количество нейронов в слое Кохонена. И каждому нейрону [math]\displaystyle{ n_j }[/math] поствлен в соответствие вектор весов [math]\displaystyle{ \mathbf{w}_{j} = \left( w_{j}^{(1)}, \dots, w_{j}^{(D)} \right) \in \mathbb{R}^D }[/math] и вектор [math]\displaystyle{ \mathbf{r}_j \in \mathbb{R}^2 }[/math], определющий его положение на двумерной плоскости.
Алгоритм обучения (online version):
- Задать начальные приближение весов [math]\displaystyle{ \mathbf{w}_{j} }[/math], [math]\displaystyle{ \forall j=1, \dots, L }[/math].
- Выбрать случайно номер объекта [math]\displaystyle{ i \sim Unif[1, N] }[/math].
- Найти расстояние между объектом [math]\displaystyle{ \mathbf{x}_i }[/math] и всеми векторами весов [math]\displaystyle{ \mathbf{w}_{j} }[/math]: [math]\displaystyle{ \rho(\mathbf{x}_i, \mathbf{w}_{j}) = \left\| \mathbf{x}_i - \mathbf{w}_{j} \right\|^2, \quad \forall j=1, \dots, L }[/math]
- Найти нейрон-победитель [math]\displaystyle{ n_b }[/math], [math]\displaystyle{ b = \arg \min_{\forall j \in \{1, \dots, L\}} \rho(\mathbf{x}_i, \mathbf{w}_{j}) }[/math], наиболее близкий к текущему объекту [math]\displaystyle{ \mathbf{x}_i }[/math].
- Для всех неронов [math]\displaystyle{ n_j }[/math] пересчитать их веса по следующей формуле: [math]\displaystyle{ \mathbf{w}_{j} \leftarrow \mathbf{w}_{j} + \alpha(t)h_{b, j}(t)(\mathbf{x}_i - \mathbf{w}_{j}) }[/math], где [math]\displaystyle{ \alpha(t) }[/math] - темп обучения (learning rate), монотонно убывающая функция от номера итерации [math]\displaystyle{ t }[/math], [math]\displaystyle{ h_{b, j}(t) }[/math] - функция определяющая "меру соседства" нейронов [math]\displaystyle{ n_b }[/math] и [math]\displaystyle{ n_j }[/math].
- Проверить критерий останова. При необходмости перейти на шаг 2.
Данное выше описание является довольно общим и не раскрывает некоторых деталей:
- Начальное приближение для [math]\displaystyle{ \mathbf{w}_j }[/math]
- Инициализация случайными значениями. Самый простой способ - [math]\displaystyle{ w_j^{(d)} \sim Unif[0, 1] }[/math]. Данный подход может потребовать большое количество итераций, так как вектора весов неупорядочены и могут находится на значительном расстоянии от точек обучающей выборки.
- Инициализация объектами обучающей выборки. Данный способ может позволить уменьшить количество итераций, так как вектора весов будут изначально находятся в области пространства, в которой расположены объекты выборки. Но проблема с неупорядоченностью остается.
- Инициализация при помощи PCA. При помощи PCA находятся первые две главные компоненты [math]\displaystyle{ e_1, e_2 }[/math]. Затем в плоскости натянутой на ветора [math]\displaystyle{ e_1, e_2 }[/math] выбирается регулярная сетка точек, которыми и инициализируются вектора [math]\displaystyle{ \mathbf{w}_j }[/math]. Этот способ является наиболее предпочтительным и на практике показывает хорошие результаты.
- Задание [math]\displaystyle{ \alpha(t) }[/math]
- [math]\displaystyle{ \alpha(t) = \alpha_0 \exp \left\{ -\frac{t}{\lambda} \right\} }[/math]
- [math]\displaystyle{ \alpha(t) = \frac{1}{t} }[/math]
- [math]\displaystyle{ \alpha(t) = \lambda^{\frac{t}{T}}, \lambda \in (0, 1) }[/math]
- Задание [math]\displaystyle{ h_{b,j}(t) }[/math]
- Наиболее популярный способ: [math]\displaystyle{ h_{b,j}(t) = \exp \left\{ - \frac{\| \mathbf{r}_b -\mathbf{r}_j \|^2}{2\sigma(t)^2} \right\} }[/math], где [math]\displaystyle{ \sigma(t) }[/math] - убывающая функция.
Кроме онлайн алгоритма обучения часто на практике применяют более эффективную с точки зрения вычислений batch-версию. Пусть выбрано [math]\displaystyle{ B \in \mathbb{N} }[/math]. Тогда batch-версия алгоритма описывается следующим образом:
Алгоритм обучения (batch version):
- Задать начальные приближение весов [math]\displaystyle{ \mathbf{w}_{j} }[/math], [math]\displaystyle{ \forall j=1, \dots, L }[/math].
- Случайно выбрать множество [math]\displaystyle{ \mathcal{B} \subset \{1, \dots, N \} }[/math] размера [math]\displaystyle{ B }[/math].
- Для каждого объекта [math]\displaystyle{ \mathbf{x}_i }[/math], [math]\displaystyle{ i \in \mathcal{B} }[/math], найти нейрон-победитель [math]\displaystyle{ n_{b(i)} }[/math], где [math]\displaystyle{ b(i) = \arg \min_{\forall j \in \{1, \dots, L\}} \rho(\mathbf{x}_i, \mathbf{w}_{j}) }[/math]
- Пересчитать веса для всех нейронов [math]\displaystyle{ \mathbf{w}_j \leftarrow \frac{\sum_{i \in \mathcal{B}}h_{b(i),i}\mathbf{x}_i}{\sum_{i \in \mathcal{B}}h_{b(i),i}} }[/math], [math]\displaystyle{ \forall j=1, \dots, L }[/math].
- Проверить критерий останова. При необходимости перейти на шаг 2.
Интерпретация шага 2 состоит в следующем: веса нейронов преставляют собой выпуклую комбинацию объектов с номерами из [math]\displaystyle{ \mathcal{B} }[/math].