Растущий нейронный газ - реализация на языке программирования MQL5

Alexey Subbotin | 24 сентября, 2010

Введение

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

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

Поскольку в то время уже были известны самоорганизующиеся карты и хеббовское обучение (в частности, алгоритмы, позволяющие произвести топологизацию сети, т.е. создать набор связей между нейронами, формирующий «каркас» слоя), а также были проработаны подходы к «мягкому» соревновательному обучению (при таких процедурах происходит адаптация весов не только нейрона-«победителя», но и его «соседей»), логичным шагом вперед было объединение указанных методов, что и сделал в 1995 году немецкий ученый Бернд Фритцке, создав получивший широкую известность алгоритм "Растущий нейронный газ" (Growing neural gas, GNG).

Метод оказался довольно удачным, вследствие чего породил ряд модификаций; в том числе была произведена адаптация и для обучения с учителем (Supervised-GNG). Как отмечал сам автор, S-GNG показал ощутимо большую эффективность при классификации данных, чем, скажем, сети на радиально-базисных функциях, за счет способности к уплотнению топологии в проблемных для классификации областях входного пространства. Не вызывает сомнения и превосходство GNG над «К-средних» кластеризацией.

Из биографии Б.Фритцке примечательно, что в 2001 году он завершил карьеру ученого в Рурском университете (г. Бохум, ФРГ) в связи с поступившим предложением о трудоустройстве на Немецкой фондовой бирже (Deutsche Bӧrse). Не буду скрывать, что этот факт послужил дополнительным стимулом к выбору именно его алгоритма в качестве основы для написания настоящей статьи.

1. Растущий нейронный газ

Итак, GNG – это алгоритм, позволяющий осуществлять адаптивную кластеризацию входных данных, т.е. не только разделить пространство на кластеры, но и определить необходимое их количество исходя из особенностей самих данных.

Начиная всего с двух нейронов, алгоритм последовательно изменяет (по большей части, увеличивает) их число, одновременно создавая набор связей между нейронами, наилучшим образом отвечающую распределению входных векторов, используя подход соревновательного хеббовского обучения. У каждого нейрона имеется внутренняя переменная, в которой накапливается т.н. «локальная ошибка». Соединения между узлами характеризуются переменной, называемой «возраст».

Псевдокод GNG выглядит следующим образом:

Инициализация: создать два узла с векторами весов, разрешенными распределением входных векторов, и нулевыми значениями локальных ошибок; соединить узлы связью, установив ее возраст равным 0.
Подать на вход нейросети вектор .
Найти два нейрона и , ближайших к , т.е. узлы с векторами весов и , такими, что минимальное, а второе минимальное значение расстояния среди всех узлов.
Обновить локальную ошибку нейрона-победителя путем добавления к ней квадрата расстояния между векторами и :
Сместить нейрон-победитель и всех его топологических соседей (т.е. все нейроны, имеющие соединение с победителем) в сторону входного вектора на расстояния, равные долям и от полного.
Увеличить на 1 возраст всех соединений, исходящих от победителя .
Если два лучших нейрона и соединены, обнулить возраст их связи. В противном случае создать связь между ними.
Удалить все соединения, возраст которых превышает . Если после этого имеются нейроны, не имеющие связей с другими узлами, удалить эти нейроны.
Если номер текущей итерации кратен , и предельный размер сети не достигнут, создать новый нейрон по следующим правилам:
- Найти нейрон с наибольшей локальной ошибкой.
- Среди соседей найти нейрон с максимальной ошибкой.
- Создать узел "посредине" между и :
- Заменить связь между и на связи между и , и .
- Уменьшить ошибки нейронов и , установить значение ошибки нейрона .
Уменьшить ошибки всех нейронов на долю .
Если критерий останова не выполнен, перейти к шагу 2.

Разберемся, каким же образом происходит адаптация растущего нейронного газа к особенностям входного пространства.

Первым делом, обратим внимание на увеличение переменной локальной ошибки у нейрона-победителя на шаге 4. Эта процедура приводит к тому, что наиболее часто выигрывающие узлы, т.е. те, в окрестности которых попадает наибольшее количество входных сигналов, имеют наибольшее значение ошибки, а значит, именно эти области становятся главными кандидатами на «уплотнение» путем добавления новых узлов.

Смещение узлов в сторону входного вектора на шаге 5 означает, что победитель стремится «усреднить» свое положение среди входных сигналов, расположенных в его окрестностях. При этом лучший нейрон немного «подтягивает» в сторону сигнала и своих соседей (как правило, выбирается ).

Поясним работу со связями между нейронами на шагах 6-8. Не в даваясь в подробности, скажем, что смысл старения и удаления старых связей состоит в том, чтобы топология сети в целом максимально приближалась к так называемой триангуляции Делоне, т.е. такой триангуляции (разбиению на треугольники) множества нейронов, при которой, в частности, максимизируется минимальный угол треугольников разбиения (исключается появление «тонких» треугольников).

Попросту говоря, триангуляция Делоне соответствует наиболее «красивой» в смысле максимума энтропии топологизации слоя. Следует отметить, что топологическая структура нужна нам не сама по себе, ценность представляет ее использование для определения местоположения новых узлов при их вставке на шаге 8 – они всегда располагаются посредине того или иного ребра.

9 шаг представляет собой коррекцию переменных ошибок всех нейронов слоя. Это необходимо для того, чтобы сеть «забывала» старые входные векторы и лучше реагировала на новые. Таким образом, достигается возможность использовать растущий нейронный газ для адаптации нейросети под нестационарные, а именно, медленно дрейфующие распределения входных сигналов. Это, однако, не дает ей способности отслеживать быстрые изменения в характеристиках входов (подробнее об этом ниже в разделе, где будут обсуждены недостатки алгоритма).

Пожалуй, отдельно стоит остановиться на критерии останова. Здесь алгоритм оставляет поле для фантазий разработчикам систем анализа. Возможные варианты – проверка эффективности сети на тестовом множестве, анализ динамики средней ошибки нейронов, ограничения на сложность самой сети и т.д.

Мы в ознакомительных целях ограничимся наиболее простым вариантом – поскольку целью данной статьи является демонстрация не столько алгоритма как такового, сколько возможности его реализации средствами MQL5, обучение слоя будем продолжать до тех пор, пока у нас попросту не закончатся входные сигналы (их количество, мы, естественно, зададим заранее).

2. Выбор способа организации данных

При программировании алгоритма нам, очевидно, придется столкнуться с необходимостью хранить в памяти то, что принято называть «множествами». Их у нас будет два – множество нейронов и множество связей между ними. Поскольку и та и другая структура будут видоизменяться в процессе работы программы (причем мы планируем как добавлять, так и удалять элементы), следует предусмотреть механизмы и для этого.

Конечно, можно было бы попытаться использовать динамические массивы объектов, однако при этом пришлось бы осуществлять множество операций копирования-перемещения данных, что существенно замедлило бы работу программы. Более подходящим вариантом для работы с абстракциями, обладающими указанными свойствами, являются программные графы, в частности, их простейший вариант – связный список.

Напомним читателям принцип работы связного списка (рис.1). Объекты базового класса содержат в качестве одного из членов указатель на такой же объект, что позволяет объединять их в линейные структуры, независимые от физического порядка расположения объектов в памяти. В дополнение к этому имеется класс-«каретка», в который инкапсулируются процедуры перемещения по списку, добавления, вставки и удаления узлов, поиска, сравнения и сортировки, а также, при необходимости, и другие.

Рисунок 1. Схематическое изображение организации линейных связных списков

Специалистами компании Metaquotes Software Corp. связные списки объектов класса CObject уже реализованы в стандартной библиотеке. Соответствующий программный код расположен в заголовочном файле List.mqh, который находится в папке MQL5\Include\Arrays стандартной поставки терминала MetaTrader 5.

Мы не будем изобретать велосипед и доверимся квалификации уважаемых программистов Metaquotes, взяв классы CObject и CList за основу наших структур данных. В этом нам поможет один из столпов объектно-ориентированного подхода – механизм наследования.

3. Программирование модели

Для начала определимся с программным воплощением понятия «искусственный нейрон».

Одно из правил хорошего тона при разработке ООП-приложений – всегда начинать программирование с наиболее общих структур данных. Даже когда вы пишете исключительно для себя, но, в особенности, если предполагается, что кодами будут пользоваться другие программисты, следует держать в уме тот факт, что в будущем разработчикам могут прийти в голову различные идеи по развитию и модификации логики программы, причем в каком именно месте будут внесены изменения, заранее неизвестно.

Принцип же ООП предполагает, что сторонний разработчик не будет копаться в ваших классах, вместо этого он должен иметь возможность унаследовать свои структуры данных от имеющихся в нужном месте иерархии. Таким образом, первый написанный класс должен быть максимально абстрактным, а конкретика уже пусть вносится на более низких уровнях, по мере приближения «к грешной земле».

В применении к нашей задаче сказанное означает, что написание программы мы начнем с определения класса CCustomNeuron («какой-то там нейрон»), который, как и все искусственные нейроны, будет иметь некое количество синапсов (входных весов) и выходное значение. Он будет уметь инициализироваться (присваивать значения весам), вычислять значение сигнала на своем выходе и даже адаптировать свои веса на заданную величину.

Большей абстракции (с учетом того, что мы наследуем наш класс от предельно обобщенного CObject) добиться вряд ли удастся – указанные действия должны уметь производить все нейроны.

Для описания данных создадим заголовочный файл Neurons.mqh, положив его в папку Include\GNG.

//+------------------------------------------------------------------+
//| базовый класс для представления объектов-нейронов                |
//+------------------------------------------------------------------+
class CCustomNeuron:public CObject
  {
protected:
   int               m_synapses;
   double            m_weights[];
public:
   double            NET;
                     CCustomNeuron();
                    ~CCustomNeuron(){};
   void              ZeroInit(int synapses);
   int               Synapses();
   void              Init(double &weights[]);
   void              Weights(double &weights[]);
   void              AdaptWeights(double &delta[]);
   virtual void       ProcessVector(double &in[]) {return;}
   virtual int        Type() const          { return(TYPE_CUSTOM_NEURON);}
  };
//+------------------------------------------------------------------+
//| конструктор                                                      |
//+------------------------------------------------------------------+
void CCustomNeuron::CCustomNeuron()
  {
   m_synapses=0;
   NET=0;
  }
//+------------------------------------------------------------------+
//| возвращает размерность входного вектора нейрона                  |
//| INPUT: нет                                                       |
//| OUTPUT: количество "синапсов" нейрона                            |
//+------------------------------------------------------------------+
int CCustomNeuron::Synapses()
  {
   return m_synapses;
  }
//+------------------------------------------------------------------+
//| инициализация нейрона нулевым вектором весов.                    |
//| INPUT: synapses - количество синапсов (входных весов)            |
//| OUTPUT: нет                                                      |
//+------------------------------------------------------------------+
void CCustomNeuron::ZeroInit(int synapses)
  {
   if(synapses<1) return;
   m_synapses=synapses;
   ArrayResize(m_weights,m_synapses);
   ArrayInitialize(m_weights,0);
   NET=0;
  }
//+------------------------------------------------------------------+
//| инициализация весов нейрона заданным вектором.                   |
//| INPUT: weights - вектор данных                                   |
//| OUTPUT: нет                                                      |
//+------------------------------------------------------------------+
void CCustomNeuron::Init(double &weights[])
  {
   if(ArraySize(weights)<1) return;
   m_synapses=ArraySize(weights);
   ArrayResize(m_weights,m_synapses);
   ArrayCopy(m_weights,weights);
   NET=0;
  }
//+------------------------------------------------------------------+
//| получение вектора весов нейрона.                                 |
//| INPUT: нет                                                       |
//| OUTPUT: weights - результат                                      |                        
//+------------------------------------------------------------------+
void CCustomNeuron::Weights(double &weights[])
  {
   ArrayResize(weights,m_synapses);
   ArrayCopy(weights,m_weights);
  }
//+------------------------------------------------------------------+
//| изменить веса нейрона на заданную величину                       |
//| INPUT: delta - корректирующий вектор                             |
//| OUTPUT: нет                                                      |
//+------------------------------------------------------------------+
void CCustomNeuron::AdaptWeights(double &delta[])
  {
   if(ArraySize(delta)!=m_synapses) return;
   for(int i=0;i<m_synapses;i++) m_weights[i]+=delta[i];
   NET=0;
  }

Определенные в классе функции предельно просты, поэтому останавливаться подробно на их описании нет необходимости. Отметим только, что функция обработки входного вектора ProcessVector(double &in[]) (выходное значение здесь вычисляется как у обычного персептрона) определена нами с модификатором virtual.

Сие значит, что в случае переопределения наследниками данного метода выбор подходящей процедуры будет производиться в зависимости от реального класса объекта динамически в процессе выполнения программы, что увеличивает ее гибкость, в том числе, в смысле взаимодействия с пользователем, и уменьшает трудозатраты на программирование.

Несмотря на то, что мы, кажется, еще ничего не сделали для организации нейронов в связный список, на самом деле это уже произошло в тот момент, когда мы указали, что новый класс является наследником CObject. Так, отныне в приватных (private) членах нашего класса числятся m_first_node, m_curr_node и m_last_node, которые имеют тип «указатель на CObject» и указывают, соответственно, на первый, текущий и последний элементы списка. В наличии и все функции, необходимые для навигации по списку.

Настало время очертить отличия нейрона GNG-слоя от других собратьев, определив класс CGNGNeuron:

//+------------------------------------------------------------------+
//| отдельный нейрон РНГ-сети                                        |
//+------------------------------------------------------------------+
class CGNGNeuron:public CCustomNeuron
  {
public:
   int               uid;
   double            E;
   double            U;
   double            error;
                    CGNGNeuron();
   virtual void      ProcessVector(double &in[]);
  };
//+------------------------------------------------------------------+
//| конструктор                                                      |
//+------------------------------------------------------------------+
CGNGNeuron::CGNGNeuron()
  {
   E=0;
   U=0;
   error=0;
  }
//+------------------------------------------------------------------+
//| рассчитывается "расстояние" от нейрона до входного вектора       |
//| INPUT: in - вектор данных                                        |
//| OUTPUT: нет                                                      |
//| REMARK: в переменную error помещается текущее "расстояние",      |
//|         "локальная ошибка" содержится в другой переменной,       |
//|         которая называется E                                                     
//+------------------------------------------------------------------+
void CGNGNeuron::ProcessVector(double &in[])
  {
   if(ArraySize(in)!=m_synapses) return;

   error=0;
   NET=0;
   for(int i=0;i<m_synapses;i++)
     {
      error+=(in[i]-m_weights[i])*(in[i]-m_weights[i]);
     }
  }

Итак, как можно заметить, указанные отличия заключаются в присутствии полей:

error – текущего квадрата расстояния от входного вектора до вектора весов нейрона,
E – переменной, аккумулирующей локальную ошибку и уникального идентификатора,
uid – он необходим для того, чтобы впоследствии мы смогли объединять нейроны связями в пары (простой индексации, уже существующей в классе CList, недостаточно, т.к. нам придется удалять и добавлять нейроны, что приведет к сбоям и путанице в нумерации).

Изменилась и функция ProcessVector(...) – теперь она вычисляет значение поля error.

На поле U пока не обращаем внимания, его значение будет объяснено ниже в разделе "Модификация алгоритма".

Следующий шаг – написание класса, представляющего связь между двумя нейронами.

//+------------------------------------------------------------------+
//| класс, определяющий соединение(связь) между двумя нейронами      |
//+------------------------------------------------------------------+
class CGNGConnection:public CObject
  {
public:
   int               uid1;
   int               uid2;
   int               age;
                     CGNGConnection();
   virtual int       Type() const          { return(TYPE_GNG_CONNECTION);}
  };
//+------------------------------------------------------------------+
//| конструктор                                                      |
//+------------------------------------------------------------------+
CGNGConnection::CGNGConnection()
  {
   age=0;
  }

Здесь вроде бы ничего сложного – у соединения есть два конца (нейроны, обозначенные идентификаторами uid1 и uid2) и возраст age, изначально равный нулю.

Теперь поработаем над классами-«каретками» связных списков, в которых будут заложены возможности, необходимые для реализации алгоритма GNG.

Первым делом, унаследуем от CList класс списка нейронов:

//+------------------------------------------------------------------+
//| связный список нейронов                                          |
//+------------------------------------------------------------------+
class CGNGNeuronList:public CList
  {
public:
   //--- конструктор   
                     CGNGNeuronList() {MathSrand(TimeLocal());}
   CGNGNeuron       *Append();
   void              Init(double &v1[],double &v2[]);
   CGNGNeuron       *Find(int uid);
   void              FindWinners(CGNGNeuron *&Winner,CGNGNeuron *&SecondWinner);
  };
//+------------------------------------------------------------------+
//| добавляет  "пустой" нейрон в конец списка                        |
//| INPUT: нет                                                       |
//| OUTPUT: указатель на новый нейрон                                |
//+------------------------------------------------------------------+
CGNGNeuron *CGNGNeuronList::Append()
  {
   if(m_first_node==NULL)
     {
      m_first_node= new CGNGNeuron;
      m_last_node = m_first_node;
     }
   else
     {
      GetLastNode();
      m_last_node=new CGNGNeuron;
      m_curr_node.Next(m_last_node);
      m_last_node.Prev(m_curr_node);
     }
   m_curr_node=m_last_node;
   m_curr_idx=m_data_total++;

   while(true)
     {
      int rnd=MathRand();
      if(!CheckPointer(Find(rnd)))
        {
         ((CGNGNeuron *)m_curr_node).uid=rnd;
         break;
        }
     }
//---
   return(m_curr_node);
  }
//+------------------------------------------------------------------+
//| инициализация списка путем создания двух нейронов, заданных      |
//| векторами весов                                                  |
//| INPUT: v1,v2 - векторы весов                                     |
//| OUTPUT: нет                                                      |
//+------------------------------------------------------------------+
void CGNGNeuronList::Init(double &v1[],double &v2[])
  {
   Clear();
   Append();
   ((CGNGNeuron *)m_curr_node).Init(v1);
   Append();
   ((CGNGNeuron *)m_curr_node).Init(v2);
  }
//+------------------------------------------------------------------+
//| поиск нейрона по uid                                             |
//| INPUT: uid - уникальный идентификатор нейрона                    |
//| OUTPUT: указатель на нейрон в случае удачи, NULL в противном     |
//+------------------------------------------------------------------+
CGNGNeuron *CGNGNeuronList::Find(int uid)
  {
   if(!GetFirstNode()) return(NULL);
   do
     {
      if(((CGNGNeuron *)m_curr_node).uid==uid)
         return(m_curr_node);
     }
   while(CheckPointer(GetNextNode()));
   return(NULL);
  }
//+------------------------------------------------------------------+
//| поиск двух "лучших" нейронов в мсмысле минимальной текущей ошибки|
//| INPUT: нет                                                       |
//| OUTPUT: Winner - нейрон, "ближайший" к входному вектору          |
//|         SecondWinner - второй "ближайший" нейрон                 |
//+------------------------------------------------------------------+
void CGNGNeuronList::FindWinners(CGNGNeuron *&Winner,CGNGNeuron *&SecondWinner)
  {
   double err_min=0;
   Winner=NULL;
   if(!CheckPointer(GetFirstNode())) return;
   do
     {
      if(!CheckPointer(Winner) || ((CGNGNeuron *)m_curr_node).error<err_min)
        {
         err_min= ((CGNGNeuron *)m_curr_node).error;
         Winner = m_curr_node;
        }
     }
   while(CheckPointer(GetNextNode()));

   err_min=0;
   SecondWinner=NULL;
   GetFirstNode();
   do
     {
      if(m_curr_node!=Winner)
         if(!CheckPointer(SecondWinner) || ((CGNGNeuron *)m_curr_node).error<err_min)
           {
            err_min=((CGNGNeuron *)m_curr_node).error;
            SecondWinner=m_curr_node;
           }
     }
   while(CheckPointer(GetNextNode()));
   m_curr_node=Winner;
  }

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

Поясним значения методов класса:

Метод Append() является дополнением к функциональности класса CList. При его вызове происходит дописывание узла в конец списка, либо создание первого узла, если список пуст.
Функция Init(double &v1[],double &v2[]) обязана своим появлением уже самому алгоритму GNG. Как мы помним, рост сети начинается с двух нейронов, поэтому именно такая сигнатура будет нам наиболее удобна. В теле функции при использовании идентификаторов m_curr_node, m_first_node, m_last_node необходимо явно преобразовывать их к типу CGNGNeuron*, если мы хотим использовать функциональность этого класса (помним о том, что указанные переменные мы унаследовали от CList, поэтому номинально они указывают на объект CObject).
Функция Find(int uid), как следует из ее названия, выполняет поиск нейрона по идентификатору, возвращая указатель на найденный элемент или NULL в случае отсутствия такового.
FindWinners(CGNGNeuron *&Winner,CGNGNeuron *&SecondWinner) – это также часть алгоритма. Нам придется искать в списке нейронов победителя и следующего за ним по близости к входному вектору, именно для этих целей данная функция и служит. Заметим, что параметры передаются в функцию по ссылке для того, чтобы можно было осуществить в них запись возвращаемых значений (*& означает «ссылка на указатель» - это верный синтаксис, обратная запись &* значит «указатель на ссылку», что запрещено: компилятор при этом выдаст ошибку).

Следующий класс – список соединений между нейронами.

//+------------------------------------------------------------------+
//| связный список соединений между нейронами                        |
//+------------------------------------------------------------------+
class CGNGConnectionList:public CList
  {
public:
   CGNGConnection   *Append();
   void              Init(int uid1,int uid2);
   CGNGConnection   *Find(int uid1,int uid2);
   CGNGConnection   *FindFirstConnection(int uid);
   CGNGConnection   *FindNextConnection(int uid);
  };
//+------------------------------------------------------------------+
//| добавляет "пустое" соединение в конец списка                     |
//| INPUT: нет                                                       |
//| OUTPUT: указатель на новую связь                                 |
//+------------------------------------------------------------------+
CGNGConnection *CGNGConnectionList::Append()
  {
   if(m_first_node==NULL)
     {
      m_first_node= new CGNGConnection;
      m_last_node = m_first_node;
     }
   else
     {
      GetLastNode();
      m_last_node=new CGNGConnection;
      m_curr_node.Next(m_last_node);
      m_last_node.Prev(m_curr_node);
     }
   m_curr_node=m_last_node;
   m_curr_idx=m_data_total++;
//---
   return(m_curr_node);
  }
//+------------------------------------------------------------------+
//| инициализация списка путем создания одного соединения            |
//| INPUT: uid1,uid2 - идентификаторы нейронов для соединения        |
//| OUTPUT: нет                                                      |
//+------------------------------------------------------------------+
void CGNGConnectionList::Init(int uid1,int uid2)
  {
   Append();
   ((CGNGConnection *)m_first_node).uid1 = uid1;
   ((CGNGConnection *)m_first_node).uid2 = uid2;
   m_last_node = m_first_node;
   m_curr_node = m_first_node;
   m_curr_idx=0;
  }
//+------------------------------------------------------------------+
//| проверка наличия связи между заданными нейронами                 |
//| INPUT: uid1,uid2 - идентификаторы нейронов                       |
//| OUTPUT: указатель на соединение в случае его наличия, или NULL   |
//+------------------------------------------------------------------+
CGNGConnection *CGNGConnectionList::Find(int uid1,int uid2)
  {
   if(!CheckPointer(GetFirstNode())) return(NULL);
   do
     {
      if((((CGNGConnection *)m_curr_node).uid1==uid1 && ((CGNGConnection *)m_curr_node).uid2==uid2)
         ||(((CGNGConnection *)m_curr_node).uid1==uid2 && ((CGNGConnection *)m_curr_node).uid2==uid1))
         return(m_curr_node);
     }
   while(CheckPointer(GetNextNode()));
   return(NULL);
  }
//+------------------------------------------------------------------+
//| поиск первого топологического соседа заданного нейрона, начиная  |
//| с первого элемента списка                                        |
//| INPUT: uid - идентификатор нейрона                               |
//| OUTPUT: указатель на соединение в случае его наличия, или NULL   |
//+------------------------------------------------------------------+
CGNGConnection *CGNGConnectionList::FindFirstConnection(int uid)
  {
   if(!CheckPointer(GetFirstNode())) return(NULL);
   while(true)
     {
      if(((CGNGConnection *)m_curr_node).uid1==uid || ((CGNGConnection *)m_curr_node).uid2==uid) break;
      if(!CheckPointer(GetNextNode())) return(NULL);
     }
   return(m_curr_node);
  }
//+------------------------------------------------------------------+
//| поиск первого топологического соседа заданного нейрона, начиная  |
//| с элемента списка, следующего за текущим                         |
//| INPUT: uid - идентификатор нейрона                               |
//| OUTPUT: указатель на соединение в случае его наличия, или NULL   |
//+------------------------------------------------------------------+
CGNGConnection   *CGNGConnectionList::FindNextConnection(int uid)
  {
   if(!CheckPointer(GetCurrentNode())) return(NULL);
   while(true)
     {
      if(!CheckPointer(GetNextNode())) return(NULL);
      if(((CGNGConnection *)m_curr_node).uid1==uid || ((CGNGConnection *)m_curr_node).uid2==uid) break;
     }
   return(m_curr_node);
  }

Определенные методы класса:

Append(). Реализация этого метода аналогична описанной в предыдущем классе, за исключением типа возвращаемого значения (к сожалению, в MQL5 нет шаблонов классов, поэтому такие вещи приходится писать каждый раз заново).
Init(int uid1,int uid2) – алгоритм GNG требует инициализации одного соединения в своем начале, что и производится в данной функции.
Функция Find(int uid1,int uid2), опять же, понятна интуитивно.
Различие методов FindFirstConnection(int uid) и FindNextConnection(int uid) заключается в том, что первая ищет соединение с соседом, начиная с начала списка, а вторая – с узла, следующего за текущим (m_curr_node).

На этом описание структур данных закончено. Пора приступать к программированию собственно алгоритма.

4. Класс алгоритма

Создаем новый заголовочный файл GNG.mqh, кладем его в папку Include\GNG.

//+------------------------------------------------------------------+
//|                                                          GNG.mqh |
//|                                             Copyright 2010, alsu |
//|                                                 alsufx@gmail.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2010, alsu"
#property link      "alsufx@gmail.com"

#include "Neurons.mqh"
//+------------------------------------------------------------------+
//| основной класс, представляющий собственно алгоритм РНГ           |
//+------------------------------------------------------------------+
class CGNGAlgorithm
  {
public:
   //--- связные списки объектов-нейронов и связей между ними
   CGNGNeuronList   *Neurons;
   CGNGConnectionList *Connections;
   //--- параметры алгоритма
   int               input_dimension;
   int               iteration_number;
   int               lambda;
   int               age_max;
   double            alpha;
   double            beta;
   double            eps_w;
   double            eps_n;
   int               max_nodes;

                     CGNGAlgorithm();
                    ~CGNGAlgorithm();
   virtual void      Init(int __input_dimension,
                          double &v1[],
                          double &v2[],
                          int __lambda,
                          int __age_max,
                          double __alpha,
                          double __beta,
                          double __eps_w,
                          double __eps_n,
                          int __max_nodes);
   virtual bool      ProcessVector(double &in[],bool train=true);
   virtual bool      StoppingCriterion();
  };
//+------------------------------------------------------------------+
//| конструктор                                                      |
//+------------------------------------------------------------------+
CGNGAlgorithm::CGNGAlgorithm(void)
  {
   Neurons=new CGNGNeuronList();
   Connections=new CGNGConnectionList();
   
   Neurons.FreeMode(true);
   Connections.FreeMode(true);
  }
//+------------------------------------------------------------------+
//| деструктор                                                       |
//+------------------------------------------------------------------+
CGNGAlgorithm::~CGNGAlgorithm(void)
  {
   delete Neurons;
   delete Connections;
  }
//+------------------------------------------------------------------+
//| инициализирует алгоритм с помощью двух векторов входных данных   |
//| INPUT: v1,v2 - входные векторы                                   |
//|        __lambda - количество итераций, после которого происходит |
//|        вставка нового нейрона                                    |
//|        __age_max - максимальный возраст соединения               |
//|        __alpha, __beta - используются для адаптации ошибок       |
//|        __eps_w, __eps_n - используются для адаптации весов       |
//|        __max_nodes - ограничение размера сети                    |
//| OUTPUT: нет                                                     |
//+------------------------------------------------------------------+
void CGNGAlgorithm::Init(int __input_dimension,
                         double &v1[],
                         double &v2[],
                         int __lambda,
                         int __age_max,
                         double __alpha,
                         double __beta,
                         double __eps_w,
                         double __eps_n,
                         int __max_nodes)
  {
   iteration_number=0;
   input_dimension=__input_dimension;
   lambda=__lambda;
   age_max=__age_max;
   alpha= __alpha;
   beta = __beta;
   eps_w = __eps_w;
   eps_n = __eps_n;
   max_nodes=__max_nodes;
   Neurons.Init(v1,v2);

   CGNGNeuron *tmp;
   tmp=Neurons.GetFirstNode();
   int uid1=tmp.uid;
   tmp=Neurons.GetLastNode();
   int uid2=tmp.uid;

   Connections.Init(uid1,uid2);
  }
//+------------------------------------------------------------------+
//| основная функция алгоритма                                       |
//| INPUT: in - вектор входных данных                                |
//|        train - если true, запускать обучение, в противном случае |
//|        только рассчитать выходные значения нейронов              |
//| OUTPUT: true, если выпоняется условие останова, иначе false      |
//+------------------------------------------------------------------+
bool CGNGAlgorithm::ProcessVector(double &in[],bool train=true)
  {
   if(ArraySize(in)!=input_dimension) return(StoppingCriterion());

   int i;

   CGNGNeuron *tmp=Neurons.GetFirstNode();
   while(CheckPointer(tmp))
     {
      tmp.ProcessVector(in);
      tmp=Neurons.GetNextNode();
     }

   if(!train) return(false);

   iteration_number++;
//--- Найти два нейрона, ближайших к in[], т.е. узлы с векторами весов 
//--- Ws и Wt, такими, что ||Ws-in||^2 минимальное, а ||Wt-in||^2 -    
//--- второе минимальное значение расстояния среди всех узлов .        
//--- Под обозначением ||*|| понимается евклидова норма                
   CGNGNeuron *Winner,*SecondWinner;
   Neurons.FindWinners(Winner,SecondWinner);

//--- Обновить локальную ошибку нейрона-победителя                     
   Winner.E+=Winner.error;

//--- Сместить нейрон-победитель и всех его топологических соседей(т.е.
//--- все нейроны, имеющие соединение с победителем) в сторону входного
//--- вектора на расстояния, равные долям eps_w и eps_n от полного.    
   double delta[],weights[];

   Winner.Weights(weights);
   ArrayResize(delta,input_dimension);

   for(i=0;i<input_dimension;i++) delta[i]=eps_w*(in[i]-weights[i]);
   Winner.AdaptWeights(delta);

//--- Увеличить на 1 возраст всех соединений, исходящих от победителя. 
   CGNGConnection *tmpc=Connections.FindFirstConnection(Winner.uid);
   while(CheckPointer(tmpc))
     {
      if(tmpc.uid1==Winner.uid) tmp = Neurons.Find(tmpc.uid2);
      if(tmpc.uid2==Winner.uid) tmp = Neurons.Find(tmpc.uid1);

      tmp.Weights(weights);
      for(i=0;i<input_dimension;i++) delta[i]=eps_n*(in[i]-weights[i]);
      tmp.AdaptWeights(delta);

      tmpc.age++;

      tmpc=Connections.FindNextConnection(Winner.uid);
     }

//--- Если два лучших нейрона соединены, обнулить возраст их связи.    
//--- В противном случае создать связь между ними.                     
   tmpc=Connections.Find(Winner.uid,SecondWinner.uid);
   if(tmpc) tmpc.age=0;
   else
     {
      Connections.Append();
      tmpc=Connections.GetLastNode();
      tmpc.uid1 = Winner.uid;
      tmpc.uid2 = SecondWinner.uid;
      tmpc.age=0;
     }

//--- Удалить все соединения, возраст которых превышает age_max.       
//--- Если после этого имеются нейроны, не имеющие связей с другими    
//--- узлами, удалить эти нейроны.                                     
   tmpc=Connections.GetFirstNode();
   while(CheckPointer(tmpc))
     {
      if(tmpc.age>age_max)
        {
         Connections.DeleteCurrent();
         tmpc=Connections.GetCurrentNode();
        }
      else tmpc=Connections.GetNextNode();
     }

   tmp=Neurons.GetFirstNode();
   while(CheckPointer(tmp))
     {
      if(!Connections.FindFirstConnection(tmp.uid))
        {
         Neurons.DeleteCurrent();
         tmp=Neurons.GetCurrentNode();
        }
      else tmp=Neurons.GetNextNode();
     }

//--- Если номер текущей итерации кратен lambda, и предельный размер   
//--- сети не достигнут, создать новый нейрон r по следующим правилам  
   CGNGNeuron *u,*v;
   if(iteration_number%lambda==0 && Neurons.Total()<max_nodes)
     {
      //--- 1.Найти нейрон u с наибольшей локальной ошибкой.               
      tmp=Neurons.GetFirstNode();
      u=tmp;
      while(CheckPointer(tmp=Neurons.GetNextNode()))
        {
         if(tmp.E>u.E)
            u=tmp;
        }

      //--- 2.Среди соседей u найти узел u с наибольшей локальной ошибкой. 
      tmpc=Connections.FindFirstConnection(u.uid);
      if(tmpc.uid1==u.uid) v=Neurons.Find(tmpc.uid2);
      else v=Neurons.Find(tmpc.uid1);
      while(CheckPointer(tmpc=Connections.FindNextConnection(u.uid)))
        {
         if(tmpc.uid1==u.uid) tmp=Neurons.Find(tmpc.uid2);
         else tmp=Neurons.Find(tmpc.uid1);
         if(tmp.E>v.E)
            v=tmp;
        }

      //--- 3.Создать узел r "посредине" между u и v.                      
      double wr[],wu[],wv[];

      u.Weights(wu);
      v.Weights(wv);
      ArrayResize(wr,input_dimension);
      for(i=0;i<input_dimension;i++) wr[i]=(wu[i]+wv[i])/2;

      CGNGNeuron *r=Neurons.Append();
      r.Init(wr);
      //--- 4.Заменить связь между u и v на связи между u и r, v и r       
      tmpc=Connections.Append();
      tmpc.uid1=u.uid;
      tmpc.uid2=r.uid;

      tmpc=Connections.Append();
      tmpc.uid1=v.uid;
      tmpc.uid2=r.uid;

      Connections.Find(u.uid,v.uid);
      Connections.DeleteCurrent();

      //--- 5.Уменьшить ошибки нейронов u и v, установить значение ошибки  
      //---   нейрона r таким же, как у u.                                 

      u.E*=alpha;
      v.E*=alpha;
      r.E = u.E;
     }

//--- Уменьшить ошибки всех нейронов на долю beta                     
   tmp=Neurons.GetFirstNode();
   while(CheckPointer(tmp))
     {
      tmp.E*=(1-beta);
      tmp=Neurons.GetNextNode();
     }

//--- Проверить критерий останова                                      
   return(StoppingCriterion());
  }
//+------------------------------------------------------------------+
//| Критерий останова. В данной версии файла не выполняет никаких    |
//| действий, всегда возвращая false.                                |
//| INPUT: нет                                                       |
//| OUTPUT: true, если критерий выполняется, false в противном случае|
//+------------------------------------------------------------------+
bool CGNGAlgorithm::StoppingCriterion()
  {
   return(false);
  }

В классе CGNGAlgorithm два важных поля – это указатели на связные списки нейронов Neurons и связей между ними Connections. Именно они и будут являться физическим носителем структуры нашей нейросети. Остальные поля представляют собой параметры алгоритма, задаваемые извне.

Из вспомогательных методов класса отметим Init(…), который передает экземпляру алгоритма внешние параметры и инициализирует структуры данных, а также критерий останова StoppingCriterion(), который, как мы договорились ранее, не делает ничего, всегда возвращая false.

В функции ProcessVector(…), основной функции алгоритма, реализующей обработку заданного вектора данных, никаких премудростей, в общем, уже и нет: мы смогли организовать данные и методы работы с ними так, что когда дело дошло до собственно алгоритма, остается только механически перебрать все его шаги. Их местоположение в коде обозначено соответствующими комментариями.

5. Использование в работе

Перейдем к демонстрации работы алгоритма на реальных данных терминала MetaTrader 5.

Определимся, что мы не ставим здесь перед собой цель создать работающий советник на GNG (для одной статьи это многовато), мы хотим пока лишь посмотреть, как растущий нейронный газ работает, что называется, «вживую».

Для того чтобы красиво отрисовать данные, создадим пустое окно, отмасштабировав его по оси цен в диапазоне 0-100. Для этого используем "пустой" индикатор Dummy.mq5 (других функций у него не будет):

//+------------------------------------------------------------------+
//|                                                        Dummy.mq5 |
//|                                             Copyright 2010, alsu |
//|                                                 alsufx@gmail.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2010, alsu"
#property link      "alsufx@gmail.com"
#property version   "1.00"
#property indicator_separate_window
#property indicator_minimum 0
#property indicator_maximum 100
#property indicator_buffers 1
#property indicator_plots   1
//--- plot Label1
#property indicator_type1   DRAW_LINE
#property indicator_style1  STYLE_SOLID
#property indicator_width1  1
//--- indicator buffers
double         DummyBuffer[];
//+------------------------------------------------------------------+
//| Custom indicator initialization function                         |
//+------------------------------------------------------------------+
int OnInit()
  {
//--- indicator buffers mapping
   SetIndexBuffer(0,DummyBuffer,INDICATOR_DATA);
   IndicatorSetString(INDICATOR_SHORTNAME,"GNG_dummy");
//---
   return(0);
  }
//+------------------------------------------------------------------+
//| Custom indicator iteration function                              |
//+------------------------------------------------------------------+
int OnCalculate(const int rates_total,
                const int prev_calculated,
                const datetime& time[],
                const double& open[],
                const double& high[],
                const double& low[],
                const double& close[],
                const long& tick_volume[],
                const long& volume[],
                const int& spread[])
  {
//--- пустой буфер
   ArrayInitialize(DummyBuffer,EMPTY_VALUE);

//--- return value of prev_calculated for next call
   return(rates_total);
  }
//+------------------------------------------------------------------+

В MetaEditor создаем скрипт с именем GNG.mq5 - он будет отображать сеть в окне индикатора Dummy.

Внешние параметры - число векторов данных для обучения и собственно параметры алгоритма:

//--- количество входных векторов, используемых для обучения
input int      samples=1000;

//--- параметры алгоритма
input int lambda=20;
input int age_max=15;
input double alpha=0.5;
input double beta=0.0005;
input double eps_w=0.05;
input double eps_n=0.0006;
input int max_nodes=100;

Объявляем глобальные переменные:

//---глобальные переменные
CGNGAlgorithm *GNGAlgorithm;
int window;
int rsi_handle;
int input_dimension;
int _samples;
double RSI_buffer[];
datetime time[];

Начинаем писать функцию OnStart(). Первым делом, ищем нужное окно:

void OnStart()
  {
   int i,j;
   int window=ChartWindowFind(0,"GNG_dummy");

В качестве входных данных используем значения индикатора RSI – он удобен тем, что его значения нормированы в диапазоне от 0 до 100, поэтому не придется заниматься предобработкой.

Будем считать входным вектором нейросети пару (input_dimension=2), состоящую из двух значений RSI – на текущем и на предыдущем барах (по-научному это называется «погружение временного ряда в двумерное пространство признаков»). Двумерные векторы все-таки проще отображать на плоском графике.

Итак, сначала готовим данные для инициализации и создаем экземпляр объекта алгоритма:

//--- чтобы функция CopyBuffer() работала правильно, количество векторов 
//--- должно укладываться в количество баров с запасом на длину вектора 
   _samples=samples+input_dimension+10;
   if(_samples>Bars(_Symbol,_Period)) _samples=Bars(_Symbol,_Period);

//--- получаем входные данные для алгоритма
   rsi_handle=iRSI(NULL,0,8,PRICE_CLOSE);
   CopyBuffer(rsi_handle,0,1,_samples,RSI_buffer);

//--- возвращаем заданное пользователем значение
   _samples=_samples-input_dimension-10;

//--- запоминаем времена открытия первых 100 баров
   CopyTime(_Symbol,_Period,0,100,time);

//--- создать экземпляр алгоритма и установить размерность входных данных
   GNGAlgorithm=new CGNGAlgorithm;
   input_dimension=2;

//--- векторы данных
   double v[],v1[],v2[];
   ArrayResize(v,input_dimension);
   ArrayResize(v1,input_dimension);
   ArrayResize(v2,input_dimension);

   for(i=0;i<input_dimension;i++)
     {
      v1[i] = RSI_buffer[i];
      v2[i] = RSI_buffer[i+3];
     }

Теперь инициализиуем алгоритм:

//--- инициализация
   GNGAlgorithm.Init(input_dimension,v1,v2,lambda,age_max,alpha,beta,eps_w,eps_n,max_nodes);

Рисуем прямоугольное поле и информационные метки (чтобы наглядно видеть, сколько итераций алгоритма отработано и сколько нейронов «выросло» в сети):

//-- рисуем прямоугольное поле и информационные метки
   ObjectCreate(0,"GNG_rect",OBJ_RECTANGLE,window,time[0],0,time[99],100);
   ObjectSetInteger(0,"GNG_rect",OBJPROP_BACK,true);
   ObjectSetInteger(0,"GNG_rect",OBJPROP_COLOR,DarkGray);
   ObjectSetInteger(0,"GNG_rect",OBJPROP_BGCOLOR,DarkGray);

   ObjectCreate(0,"Label_samples",OBJ_LABEL,window,0,0);
   ObjectSetInteger(0,"Label_samples",OBJPROP_ANCHOR,ANCHOR_RIGHT_UPPER);
   ObjectSetInteger(0,"Label_samples",OBJPROP_CORNER,CORNER_RIGHT_UPPER);
   ObjectSetInteger(0,"Label_samples",OBJPROP_XDISTANCE,10);
   ObjectSetInteger(0,"Label_samples",OBJPROP_YDISTANCE,10);
   ObjectSetInteger(0,"Label_samples",OBJPROP_COLOR,Red);
   ObjectSetString(0,"Label_samples",OBJPROP_TEXT,"Total samples: 2");

   ObjectCreate(0,"Label_neurons",OBJ_LABEL,window,0,0);
   ObjectSetInteger(0,"Label_neurons",OBJPROP_ANCHOR,ANCHOR_RIGHT_UPPER);
   ObjectSetInteger(0,"Label_neurons",OBJPROP_CORNER,CORNER_RIGHT_UPPER);
   ObjectSetInteger(0,"Label_neurons",OBJPROP_XDISTANCE,10);
   ObjectSetInteger(0,"Label_neurons",OBJPROP_YDISTANCE,25);
   ObjectSetInteger(0,"Label_neurons",OBJPROP_COLOR,Red);
   ObjectSetString(0,"Label_neurons",OBJPROP_TEXT,"Total neurons: 2");

В основном цикле подготавливаем вектор для подачи на вход алгоритма и отображаем его на графике в виде синей точки:

//--- главный цикл алгоритма начинаем с i=2 т.к. 2 вектора уже использовали
   for(i=2;i<_samples;i++)
     {
      //--- заполняем вектор данных (для наглядности берем отсчеты, отстоящие
      //--- на 3 бара - они меньше скоррелированы)
      for(j=0;j<input_dimension;j++)
         v[j]=RSI_buffer[i+j*3];

      //--- показываем вектор на графике
      ObjectCreate(0,"Sample_"+i,OBJ_ARROW,window,time[v[0]],v[1]);
      ObjectSetInteger(0,"Sample_"+i,OBJPROP_ARROWCODE,158);
      ObjectSetInteger(0,"Sample_"+i,OBJPROP_COLOR,Blue);
      ObjectSetInteger(0,"Sample_"+i,OBJPROP_BACK,true);

      //--- меняем информационную метку
      ObjectSetString(0,"Label_samples",OBJPROP_TEXT,"Total samples: "+string(i+1));

Передаем вектор алгоритму (да, всего одна функция – вот оно, преимущество объектно-ориентированного подхода!):

//--- передаем входной вектор алгоритму для расчета
      GNGAlgorithm.ProcessVector(v);

Стираем с графика старые и рисуем новые нейроны (красные кружки) и связи (желтые пунктиры), нейрон-победитель и второй лучший выделяем цветами Lime и Green:

      //--- на графике необходимо удалить старые нейроны и связи, чтобы потом нарисовать новые
      for(j=ObjectsTotal(0)-1;j>=0;j--)
        {
         string name=ObjectName(0,j);
         if(StringFind(name,"Neuron_")>=0)
           {
            ObjectDelete(0,name);
           }
         else if(StringFind(name,"Connection_")>=0)
           {
            ObjectDelete(0,name);
           }
        }

      double weights[];
      CGNGNeuron *tmp,*W1,*W2;
      CGNGConnection *tmpc;

      GNGAlgorithm.Neurons.FindWinners(W1,W2);

      //--- отрисовка нейронов
      tmp=GNGAlgorithm.Neurons.GetFirstNode();
      while(CheckPointer(tmp))
        {
         tmp.Weights(weights);

         ObjectCreate(0,"Neuron_"+tmp.uid,OBJ_ARROW,window,time[weights[0]],weights[1]);
         ObjectSetInteger(0,"Neuron_"+tmp.uid,OBJPROP_ARROWCODE,159);

         //--- победитель цветом Lime, второй лучший Green, остальные Red
         if(tmp==W1) ObjectSetInteger(0,"Neuron_"+tmp.uid,OBJPROP_COLOR,Lime);
         else if(tmp==W2) ObjectSetInteger(0,"Neuron_"+tmp.uid,OBJPROP_COLOR,Green);
         else ObjectSetInteger(0,"Neuron_"+tmp.uid,OBJPROP_COLOR,Red);

         ObjectSetInteger(0,"Neuron_"+tmp.uid,OBJPROP_BACK,false);

         tmp=GNGAlgorithm.Neurons.GetNextNode();
        }
      ObjectSetString(0,"Label_neurons",OBJPROP_TEXT,"Total neurons: "+string(GNGAlgorithm.Neurons.Total()));

      //--- отрисовка связей
      tmpc=GNGAlgorithm.Connections.GetFirstNode();
      while(CheckPointer(tmpc))
        {
         int x1,x2,y1,y2;

         tmp=GNGAlgorithm.Neurons.Find(tmpc.uid1);
         tmp.Weights(weights);
         x1=weights[0];y1=weights[1];

         tmp=GNGAlgorithm.Neurons.Find(tmpc.uid2);
         tmp.Weights(weights);
         x2=weights[0];y2=weights[1];

         ObjectCreate(0,"Connection_"+tmpc.uid1+"_"+tmpc.uid2,OBJ_TREND,window,time[x1],y1,time[x2],y2);
         ObjectSetInteger(0,"Connection_"+tmpc.uid1+"_"+tmpc.uid2,OBJPROP_WIDTH,1);
         ObjectSetInteger(0,"Connection_"+tmpc.uid1+"_"+tmpc.uid2,OBJPROP_STYLE,STYLE_DOT);
         ObjectSetInteger(0,"Connection_"+tmpc.uid1+"_"+tmpc.uid2,OBJPROP_COLOR,Yellow);
         ObjectSetInteger(0,"Connection_"+tmpc.uid1+"_"+tmpc.uid2,OBJPROP_BACK,false);

         tmpc=GNGAlgorithm.Connections.GetNextNode();
        }

      ChartRedraw();
     }
     
     //--- удаляем из памяти экземпляр алгоритма
     delete GNGAlgorithm;
     
     //--- пауза перед очисткой графика
     while(!IsStopped());
     
     //--- удаляем с экрана все рисунки
     ObjectsDeleteAll(0,window);
  }

Компилируем наш код, запускаем сначала индикатор Dummy, потом на том же графике скрипт GNG. На экране должна возникнуть примерно следующая картина:

Как видим, алгоритм действительно работает: сетка постепенно приспосабливается к поступающим новым данным, стараясь покрыть их пространство в соответствии с густотой синих точек.

В ролике показано лишь самое начало процесса обучения (всего 1000 итераций, притом, что реальное количество необходимых векторов для обучения GNG может составлять десятки тысяч), однако уже это дает вполне достойное представление о ходе процесса.

6. Известные проблемы

Как уже упоминалось, основной проблемой GNG является его неспособность отслеживать нестационарные ряды с быстро меняющимися характеристиками. Такие «прыгающие» распределения входных сигналов могут явиться причиной того, что значительная часть нейронов GNG-слоя, уже наработав определенную топологическую структуру, внезапно оказываются не у дел.

При этом, поскольку входные сигналы уже не попадают в область их расположения, возраст связей между этими нейронами не увеличивается, следовательно, «мертвая» часть сети, которая «помнит» старые характеристики сигнала, не делает полезной работы, а лишь расходует вычислительные ресурсы (см. рис. 2).

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

Рисунок 2. Реакция растущего нейронного газа на "прыгающее" распределение

Отдельные неактивные (мертвые) узлы могут также появиться в сети, если на входе алгоритма задана слишком высокая частота вставки новых нейронов (параметр λ).

Чересчур низкое его значение приводит к тому, что сеть начинает отслеживать статистически незначимые выбросы распределения входных сигналов, вероятность повторения которых крайне мала. Если на это место будет вставлен GNG-нейрон, он практически наверняка останется после этого неактивным на длительное время.

Кроме этого, как показывают практические исследования, низкое значение параметра вставки, хотя и способствует быстрому снижению средней ошибки сети в начале процесса обучения, в результате обучения дает худшие значения этого показателя: такая сеть более грубо кластеризует данные.

7. Модификация алгоритма

Решить проблему «прыгающего» распределения можно, определенным образом изменив алгоритм. Общепризнанной является модификация, вводящая т.н. фактор полезности нейронов (GNG with Utility factor или GNG-U). Изменения псевдокода при этом минимальны и сводятся к следующему:

каждому нейрону ставится в соответствие переменная, называемая «фактором полезности» (та самая переменная U в списке полей класса CGNGNeuron);
на шаге 4 после адаптации весов нейрона-победителя мы изменяем его фактор полезности на величину, равную разнице между ошибкой второго лучшего нейрона и самого победителя:

Физически эта добавка представляет собой величину, на которую изменилась бы суммарная ошибка сети, если бы нейрон-победитель в ней отсутствовал (тогда победителем стал бы второй лучший нейрон), т.е. действительно характеризует полезность нейрона для снижения общей ошибки.
удаление нейронов на шаге 8 происходит по иному принципу: удаляется только узел с минимальным значением полезности, причем только в том случае, если максимальное по слою значение ошибки превышает его фактор полезности более чем в раз:
при добавлении нового узла на шаге 9 его фактор полезности вычисляется как среднее арифметическое между полезностями соседних нейронов:
на шаге 10 фактор полезности всех нейронов уменьшается по тому же принципу и в тех же целях, что и переменные ошибок:

Константа здесь играет решающее значение для способности отслеживать нестационарность: слишком большое ее значение приводит к удалению не только действительно «малополезных», но и других, вполне используемых нейронов, слишком маленькое – к более редким удалениям и, следовательно, снижению скорости адаптации.

В файле GNG.mqh алгоритм GNG-U описан в качестве класса, унаследованного от CGNGAlgorithm. Читатели могут самостоятельно отследить внесенные изменения и попробовать алгоритм в действии.

Заключение

На примере создания нейросети мы рассмотрели основные возможности объектно-ориентированного программирования, встроенные в язык MQL5. Кажется достаточно очевидным тот факт, что в отсутствие таких возможностей (за которые разработчикам - огромная благодарность) написание сложных программ для автоматической торговли было бы сильно затруднено.

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

Автор статьи желает удачи всем в изучении нейроинформатики и использовании ее в трейдинге!