Нейронный газ: самоорганизующаяся нейронная сеть для анализа данных
Neural gas
Нейронная сеть Neural Gas: алгоритм поиска оптимальных представлений данных, вдохновленный самоорганизующимися картами. Применение: распознавание образов, сжатие данных.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Искусственная нейронная сеть
Artificial neural network
Нейронный газ – это искусственная нейронная сеть, вдохновлённая самоорганизующейся картой и представленная в 1991 году Томасом Мартинецом и Клаусом Шультеном. Нейронный газ – это простой алгоритм для поиска оптимальных представлений данных на основе векторных признаков. Алгоритм получил название «нейронный газ» из-за динамики векторных признаков в процессе адаптации, которые распределяются подобно газу в пространстве данных. Он применяется в задачах сжатия данных или векторного квантования, например, в распознавании речи, обработке изображений или распознавании образов. Как надёжная и устойчиво сходящаяся альтернатива k-средним, он также используется для кластерного анализа.
Neural gas is an artificial neural network, inspired by the self organizing map and introduced in 1991 by Thomas Martinetz and Klaus Schulten. The neural gas is a simple algorithm for finding optimal data representations based on feature vectors. The algorithm was coined "neural gas" because of the dynamics of the feature vectors during the adaptation process, which distribute themselves like a gas within the data space. It is applied where data compression or vector quantization is an issue, for example speech recognition, image processing or pattern recognition. As a robustly converging alternative to the k means clustering it is also used for cluster analysis.
Сравнение с SOM
По сравнению с самоорганизующейся картой, модель нейронного газа не исходит из предположения, что некоторые векторы являются соседями. Если два вектора случайно оказываются близко друг к другу, они будут стремиться двигаться вместе, а если далеко друг от друга – не будут двигаться согласованно. В отличие от этого, в SOM, если два вектора являются соседями в базовом графе, то они всегда будут стремиться двигаться вместе, независимо от того, являются ли эти два вектора близкими в евклидовом пространстве. Название "нейронный газ" дано потому, что его можно представить как SOM без базового графа, где все точки могут свободно перемещаться, не будучи связанными друг с другом.
Compared to self organized map, the neural gas model does not assume that some vectors are neighbors. If two vectors happen to be close together, they would tend to move together, and if two vectors happen to be apart, they would tend to not move together. In contrast, in an SOM, if two vectors are neighbors in the underlying graph, then they will always tend to move together, no matter whether the two vectors happen to be neighbors in the Euclidean space. The name "neural gas" is because one can imagine it to be what an SOM would be like if there is no underlying graph, and all points are free to move without the bonds that bind them together.
Варианты
В литературе существует несколько вариантов алгоритма нейронного газа, предназначенных для устранения некоторых его недостатков. Наиболее известен, пожалуй, растущий нейрогаз Бернда Фрицке, но также стоит упомянуть и другие разработки, такие как сеть Growing When Required и инкрементально растущий нейрогаз. Ориентированная на производительность модель "пластического нейронного газа" позволяет избежать риска переобучения.
A number of variants of the neural gas algorithm exists in the literature so as to mitigate some of its shortcomings. More notable is perhaps Bernd Fritzke's growing neural gas, but also one should mention further elaborations such as the Growing When Required network and also the incremental growing neural gas. A performance oriented approach that avoids the risk of overfitting is the Plastic Neural gas model.
Растущий нервный газ
Фрицке описывает растущий нейронный газ (GNG) как инкрементальную модель сети, которая изучает топологические отношения, используя "правило обучения, подобное правилу Хебба", демонстрируя свои возможности для инкрементальной кластеризации данных. GNG инициализируется двумя случайно расположенными узлами, которые первоначально соединены ребром с нулевым возрастом, а их ошибки установлены в 0. Поскольку в GNG входные данные представляются последовательно, один за другим, на каждой итерации выполняются следующие шаги:
Fritzke describes the growing neural gas (GNG) as an incremental network model that learns topological relations by using a "Hebb like learning rule", demonstrating its capabilities for clustering data incrementally. The GNG is initialized with two randomly positioned nodes which are initially connected with a zero age edge and whose errors are set to 0. Since the in the GNG input data is presented sequentially one by one, the following steps are followed at each iteration:
Вычисляются ошибки (расстояния) между двумя ближайшими узлами к текущим входным данным. Ошибка узла-победителя (только ближайшего) накапливается. Узел-победитель и его топологические соседи (соединенные ребром) перемещаются к текущему входу на различные доли своих соответствующих ошибок. Возраст всех ребер, связанных с узлом-победителем, увеличивается. Если узел-победитель и второй по близости узел соединены ребром, возраст такого ребра устанавливается в 0. В противном случае между ними создается ребро. Если есть ребра с возрастом, превышающим заданный порог, они удаляются. Узлы без соединений удаляются. Если текущая итерация является целым кратным предварительно определенному порогу частоты создания, новый узел вставляется между узлом с наибольшей ошибкой (среди всех) и его топологическим соседом с наибольшей ошибкой. Связь между первым и вторым узлами удаляется (их ошибки уменьшаются на заданный фактор), и новый узел соединяется с обоими. Ошибка нового узла инициализируется обновленной ошибкой узла, который имел наибольшую ошибку (среди всех). Накопленная ошибка всех узлов уменьшается на заданный коэффициент. Если критерий остановки не выполнен, алгоритм принимает следующий вход. Критерием может быть заданное количество эпох, то есть заранее определенное количество раз, когда все данные представлены, или достижение максимального числа узлов.
It is calculated the errors (distances) between the two closest nodes to the current input data. The error of the winner node (only the closest one) is respectively accumulated. The winner node and its topological neighbors (connected by an edge) are moving towards the current input by different fractions of their respective errors. The age of all edges connected to the winner node are incremented. If the winner node and the second winner are connected by an edge, such an edge is set to 0. Else, an edge is created between them. If there are edges with an age larger than a threshold, they are removed. Nodes without connections are eliminated. If the current iteration is an integer multiple of a predefined frequency creation threshold, a new node is inserted between the node with the largest error (among all) and its topological neighbor presenting the highest error. The link between the former and the latter nodes is eliminated (their errors are decreased by a given factor) and the new node is connected to both of them. The error of the new node is initialized as the updated error of the node which had the largest error (among all). The accumulated error of all nodes is decreased by a given factor. If the stopping criterion is not met, the algorithm takes a following input. The criterion might be a given number of epochs, i. e., a pre set number of times where all data is presented, or the reach of a maximum number of nodes.
Нейрогазы с постепенным ростом
Еще один вариант нейрогаза, вдохновленный алгоритмом GNG, – это инкрементально растущий нейрогаз (IGNG). Авторы утверждают, что основное преимущество этого алгоритма заключается в "способности к обучению новым данным (пластичность) без ухудшения качества ранее обученной сети и потери информации о старых входных данных (стабильность)". Фактически, для него были разработаны аналоговые аппаратные реализации.
Another neural gas variant inspired in the GNG algorithm is the incremental growing neural gas (IGNG). The authors propose the main advantage of this algorithm to be "learning new data (plasticity) without degrading the previously trained network and forgetting the old input data (stability)." and analog hardware were actually designed.