Алгоритм Улучшенной Самоорганизующейся Растущей Нейронной Сети (ESOINN)


    Введение


    В моей предыдущей статье о методах машинного обучения без учителя был рассмотрен базовый алгоритм SOINN — алгоритм построения самоорганизующихся растущих нейронных сетей. Как было отмечено, базовая модель сети SOINN имеет ряд недостатков, не позволяющих использовать её для обучения в режиме lifetime (т.е. для обучения в процессе всего срока эксплуатации сети). К таким недостаткам относилась двухслойная структура сети, требующая при незначительных изменениях в первом слое сети переобучать второй слой полностью. Также алгоритм имел много настраиваемых параметров, что затрудняло его применение при работе с реальными данными.

    В этой статье будет рассмотрен алгоритм An Enhanced Self-Organizing Incremental Neural Network, являющийся расширением базовой модели SOINN и частично решающий озвученные проблемы.

    Общая идея алгоритмов класса SOINN


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

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

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


    Алгоритм ESOINN


    Теперь перейдем к рассмотрению алгоритма ESOINN. Как было уже сказано ранее, алгоритм ESOINN является производным от базового алгоритма обучения самоорганизующихся растущих нейронных сетей. Как и базовый алгоритм SOINN, рассматриваемый алгоритм предназначен для онлайн (и даже lifetime) обучения без учителя и без конечной цели обучения. Главным отличием ESOINN от рассмотренного ранее алгоритма является то, что структура сети тут однослойная и как следствие имеет меньшее число настраиваемых параметров и большую гибкость при обучении в процессе всего времени эксплуатации алгоритма. Также в отличие от базовой сети, где узлы-победители всегда соединялись ребром, в расширенном алгоритме появилось условие на создание связи, учитывающее взаимное расположение классов, к которым принадлежат узлы-победители. Добавление такого правила позволило алгоритму успешно разделять близкие и частично перекрывающие друг друга классы. Таким образом, алгоритм ESOINN пытается решать проблемы, выявленные у базового алгоритма SOINN.

    Далее будет детально рассмотрен алгоритм построения сети ESOINN.

    Блок схема алгоритма




    Описание алгоритма



    Используемые обозначения


    — набор узлов графа.
    — набор ребер графа.
    — число узлов в .
    — вектор признаков объекта, поданного на вход алгоритма.
    — вектор признаков i-й вершины графа.
    — число накопленных сигналов i-й вершины графа.
    — плотность в i-й вершине графа.

    Алгоритм


    1. Инициализировать набор узлов двумя узлами с векторами признаков взятыми случайным образом из области допустимых значений.
      Инициализировать набор связей пустым множеством.
    2. Подать на вход вектор признаков входного объекта .
    3. Найти ближайший узел (победитель) и второй ближайший узел (второй победитель), как:


    4. Если расстояния между вектором признаков входного объекта и или больше некоторого заданного порога или , то он порождает новый узел (Добавить новый узел в и перейти на шаг 2).
      и вычисляются по формулам:
      (если вершина имеет соседей)
      (если вершина не имеет соседей)
    5. Увеличить возраст всех ребер исходящих из на 1.
    6. Используя Алгоритм 2, определить, нужна ли связь между и :
      1. Если необходимо: если ребро существует, то обнулить его возраст, иначе создать ребро и установить его возраст равным 0.
      2. Если в этом нет необходимости: если ребро существует, то удалить его.

    7. Увеличить число накопленных победителем сигналов по формуле: .
    8. Обновить плотность победителя по формуле: , где — средняя дистанция между узлами внутри кластера, к которому принадлежит победитель. Она вычисляется по формуле: .
    9. Адаптировать вектора признаков победителя и его топологических соседей с весовыми коэффициентами и по формулам:


      Мы применяем ту же схему адаптации, что и в базовом алгоритме SOINN:


    10. Найти и удалить те ребра, чей возраст превышает некоторое пороговое значение .
    11. Если число входных сигналов, генерируемых до сих пор, кратно некоторому параметру , то:
      1. Обновить метки классов для всех узлов, используя Алгоритм 1.
      2. Удалить узлы, являющиеся шумом, следующим образом:
        1. Для всех узлов из : если узел имеет двух соседей и , то удалить этот узел.
        2. Для всех узлов из : если узел имеет одного соседа и , то удалить этот узел.
        3. Для всех узлов из : если узел не имеет соседей, то удалить его.


    12. Если процесс обучения закончен, то классифицировать узлы различных классов (используя алгоритм выделения связанных компонент графа), а затем сообщить число классов, прототип-вектор для каждого класса и остановить процесс обучения.
    13. Перейти на шаг 2 для продолжения обучения без учителя, если процесс обучения еще не закончен.


    Алгоритм 1: Разделение композитного класса на подклассы


    1. Назовем узел вершиной класса, если он имеет максимальную плотность в окрестности. Найти все такие вершины в составном классе и присвоить им различные метки.
    2. Отнести остальные вершины к тем же классам, что и у соответствующих им вершин.
    3. Узлы лежат в области перекрытия классов, если они принадлежат разным классам и имеют общее ребро.

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

    Предположим, что у нас есть два несглаженных класса:

    Возьмем подкласс и подкласс . Предположим, что плотность вершины подкласса равна , а у подкласса равна . Объединим и в один подкласс в том случае, если выполняются следующие условия:

    или

    Здесь первый и второй победитель лежат в области перекрытия подклассов и . Параметр вычисляется следующим образом:
    , где — средняя плотность узлов в подклассе .

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

    Алгоритм 2: Построение связи между вершинами


    Соединим два узла в том случае, если:
    1. Хотя бы один из них является новым узлом (еще не определено, к какому подклассу он относится).
    2. Они принадлежат одному классу.
    3. Они принадлежат различным классам, и при этом выполняются условия на слияние этих классов (условия из Алгоритма 1).

    Иначе не соединяем эти узлы, а если связь между ними существует, то удаляем её.

    Благодаря использованию Алгоритма 1 при проверке необходимости создать ребро между узлами, алгоритм ESOINN будет стараться найти «баланс» между излишним разделением классов и объединением различных классов в один. Это свойство позволяет успешно проводить кластеризацию близко расположенных классов.

    Обсуждение алгоритма


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

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

    Эксперименты


    Для проведения экспериментов с представленным алгоритмом, он был реализован на языке C++ с применением библиотеки Boost Graph Library. Код выложен на GitHub.

    В качестве площадки для проведения экспериментов был исопльзован конкурс, по классификации рукописных цифр на базе MNIST, на сайте kaggle.com. Тренировочные данные содержат 48000 изображений рукописных цифр размером 28x28 пикселей и имеющих 256 оттенков серого, представленных в виде 784-мерных векторов.

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

    Параметры сети были взяты следующим образом:
    = 200
    = 50
    = 0.0001
    = 1.0

    В результате работы, сеть выделила 14 кластеров, центры которых выглядят следующим образом:


    На момент написания статьи, ESOINN занимал почетное 191 место в рейтинге с точностью 0.96786 на 25% тестовой выборки, что не так уж и плохо для алгоритма изначально не имеющего никакой априорной информации о входных данных.


    Заключение


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

    Литература


    1. «An enhanced self-organizing incremental neural network for online unsupervised learning» Shen Furaoa, Tomotaka Ogurab, Osamu Hasegawab, 2007.
    2. A talk on SOINN delivered by Osamu Hasegawa from Tokyo Institute of Technology at IIT Bombay.
    3. A talk on SOINN delivered by Osamu Hasegawa from Tokyo Institute of Technology at IIT Bombay(video).
    4. Сайт лаборатории Hasegawa Lab, занимающейся исследованиями самоорганизующихся растущих нейронных сетей.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 10

      +1
      Данная серия постов очень впечатляет, большое спасибо автору!
        0
        Мне не до конца понятно с какой целью 90% статьи посвящать просто переводу оригинальной статьи + рисункам из статьи и презентации — всегда можно дать ссылку на оригинальный источник, а затем рассказать о своих результатах.

        Конечно 3.2% процента ошибки на MNIST — это очень много. К тому же, насколько я понимаю, вы сами соотнесли центроиды кластеров с конкретными классами. Это не очень робастный подход — что если у Вас получились бы (и наверняка получатся на какой-нибудь другой базе типа ImageNet) смешанные кластеры?
        Я не уверен (так как не проверял), но мне кажется, что хорошо реализованный метод наподобие kernal k-means даст результат не хуже.
          0
          Мне не до конца понятно с какой целью 90% статьи посвящать просто переводу оригинальной статьи + рисункам из статьи и презентации

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

          Всегда можно дать ссылку на гугл или шпингер — там есть практически все публикуемые статьи, но цель поста именно в ознакомлении с алгоритмом, а не в том, чтобы отправить читателя в N разбросанных источников. По вашей логике и учебники люди пишут напрасно:)
          Конечно 3.2% процента ошибки на MNIST — это очень много. К тому же, насколько я понимаю, вы сами соотнесли центроиды кластеров с конкретными классами. Это не очень робастный подход — что если у Вас получились бы (и наверняка получатся на какой-нибудь другой базе типа ImageNet) смешанные кластеры?

          Вообще ESOINN в чистом виде не очень подходит для классификации, он больше для DataMining предназначен и для «предварительного» анализа данных поступающих в реальном времени. Но на основе полученного графа можно обучать, например, SVM и уже использовать как классификатор. В роботе Hero, например, вводили дополнительный ассоциативный слой, который отвечал за отображение внутренних классов во внешние.
          Я не уверен (так как не проверял), но мне кажется, что хорошо реализованный метод наподобие kernal k-means даст результат не хуже.

          А Deep Learning еще лучше будет работать на MNIST…
            0
            К счастью данный алгоритм описывается в одной статье (максимум 2-х), а не в «N разбросанных источников». И конечно под своими результатами я имел ввиду не код, а более глубокое исследование проблематики.

            По моей логике, чтобы написать учебник нужно провести колоссальную работу с литературой, отделить зерна от плевел и генерализовать знания, а не приводить краткий перевод не такой уж длинной статьи.

            Я намеренно не сравнивал результат с алгоритмами, в которых есть хотя бы какие-то шаги обучения на размеченных данных (fine-tuning в deep learning), поэтому и привел в пример алгоритм чистой кластеризации.
          0
          Это, как я понимаю, дальнейшее развитие алгоритма нейронный газ?
          Кстати, под питон есть неплохая реализация Growing Neural Gas.
            0
            Не совсем. Нейронный газ ведь по сути для представляемого ему множества стремится построить триангуляцию Делоне, а ESOINN наоборот пытается выделить топологические свойства этого множества(путем выделения областей высокой плотности и игнорирования шумов).
              0
              p.s. впринципе на «поиграться» может сгодиться и моя поделка на тему растущего нейронного газа, реализовано на C++ & Boost.
            0
            Расскажите, пожалуйста, подробнее про ваш эксперимент с MNIST.

            В условиях на kagi предлагается классический эксперимент «обучение с учителем», к векторам данных в обучающем множестве даются номера классов.В такой постановке k-NN при k=1 дает ошибку на тесте MNST 3,09% на первых 1000 векторов теста и 3,8 % на всем тесте.
            Пруфлинк: www.cs.ubc.ca/~murphyk/MLbook/pml-intro-22may12.pdf, стр. 25, Exercise 1.1.

            Если у вас происходит кластеризация и обучение без учителя то тут, конечно, спрос другой.
              +1
              Обучение шло без учителя, обучающая выборка была получена путем объединения обучающей(метки классов не учитывались)+тестовой выборок из задания конкурса(всего 70000 векторов). Алгоритм получил 14 кластеров, далее руками было построено соответствие между внутренними метками кластеров и реальными метками классов(как правильно заметили выше, не очень робастный подход и в реальных условиях так лучше если и делать, то очень осторожо) и посмотрел к каким классам отнеслись вектора из тестовой выборки и этот результат сабмитил в kaggle. Поэтому получилась такая не очень впечатляющая цифра.

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

              Only users with full accounts can post comments. Log in, please.