Использование нейронной сети Хопфилда для решения простейшей задачи

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

    Разговоры об искусственном интеллекте и громоздких экспертных системах — это конечно все хорошо, но как всю эту теорию приблизить к жизни, к нашим приклодным задачам?

    Немного о задаче

    Требуется написать программу, которая в «зашумленной картинке» будет распознавать эталонные образы.

    Выбор нейронной сети

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

    И так для решения нашей задачи как нельзя лучше подходит нейронная сеть Хопфилда.
    image
    Она состоит из единственного слоя нейронов, число которых является одновременно числом входов и выходов сети. Каждый нейрон связан синапсами со всеми остальными нейронами, а также имеет один входной синапс, через который осуществляется ввод сигнала. Выходные сигналы, как обычно, образуются на аксонах.

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

    В общем случае, любой сигнал может быть описан вектором X = {xi: i = 1, 2, ..., n},
    n — число нейронов в сети и размерность входных и выходных векторов. Каждый элемент хi равен либо +1, либо -1.
    Существует вектор, описывающий k-й образец. Когда сеть распознает (или «вспомнит») какой-либо образец на основе предъявленных ей данных, все выходы будут содержать именно его, т.е. Y вектор выходных значений сети: Y ={уi: i = 1, 2, ..., n}. В противном случае, если зашумление слишком сильное на выходах будет «мусор».

    На стадии инициализации сети весовые коэффициенты синапсов устанавливаются следующим образом:
    image
    Здесь i и j — индексы, соответственно, предсинаптического и постсинаптического нейронов;

    Алгоритм функционирования сети следующий (t номер итерации):
    1. На входы сети подается неизвестный сигнал. Фактически его ввод осуществляется непосредственной установкой значений:

    image
    поэтому обозначение па схеме сети входных синапсов в явном виде носит чисто условный характер. Ноль в скобке справа от yi означает нулевую итерацию в цикле работы сети.
    2. Рассчитывается новое состояние нейронов
    image
    и новые значения аксонов
    image
    3. Проверка, изменились ли выходные значения аксонов за последнюю итерацию. Если да переход к пункту 2, иначе (если выходы застабилизировались) — конец. При этом выходной вектор представляет собой образец, наилучшим образом сочетающийся с входными данными.

    Таким образом, когда подается новый вектор, сеть переходит из вершины в вершину, пока не стабилизируется. Устойчивая вершина определяется сетевыми весами и текущими входами. Если из вершины в вершину, пока не стабилизируется. Устойчивая вершина определяется сетевыми весами и текущими входами. Если входной вектор частично неправилен или неполон, сеть стабилизируется в вершине, ближайшей к желаемой.
    Доказано, что достаточным условием устойчивой работы такой сети является выполнение условий:
    Wij = Wji, Wii= 0.

    Как я уже говорил, иногда сеть не может провести распознавание и выдает на выходе несуществующий образ. Это связано с проблемой ограниченности возможностей сети. Для сети Хопфилда число запоминаемых образов N не должно превышать величины, примерно равной 0,15n. Кроме того, если два образа А и В сильно похожи, они, возможно, будут вызывать у сети перекрестные ассоциации, т.е. предъявление на входы сети вектора А приведет к появлению на ее выходах вектора В и наоборот.

    Приступим к написанию программы

    И так для нейронной сети необходима бинарная последовательность (в нашем случае -1/1).
    Пусть «1» — это черный цвет пикселя, а "-1" — это белый,
    таким образом сможем преобразовать картинку в последовательность.

    Для быстроты и точности востановления будем использовать следующую схему:
    Картинка 100х100 пикселей и на каждый пиксель приходится свой нейрон.
    Таким образом сеть будет состоять из 10 000 нейронов.

    Начнем с представления элементарный еденицы — нейрон:

    //описание нейрона
    private class Neuron       
    {
     //изменение состояние нейрона
     public void ChangeState()
     {
      if (s > 0) y = 1;
      if (s < 0) y = -1;
      if (s == 0) y = 0;
     }
     public int s;
     public int x; //вход
     public int y; //выход
     public int index;
    }


    * This source code was highlighted with Source Code Highlighter.


    Теперь рассмотри саму нейронную сеть, думаю для лучшего понимания следует привести основную часть листинга=)

    namespace Neurons
    {
      class NetHopfild
      {
        //описание нейрона
        private class Neuron       
        {
          ...
        }

        private const int size = 10000;
        public NetHopfild()
        {
          //инстанциирование нейронов, мытрицы связей
          mass = new Neuron[size];
          for (int i = 0; i < size; i++)
          {
            mass[i] = new Neuron();
          }
          matrix_of_connect = new int[size, size];
          last_y = new int[size];
          //
          for (int i = 0; i < size; i++)
          {
            mass[i].index = i;
          }
          for (int i = 0; i < size; i++)
          {
            for (int j = 0; j < size; j++)
            {
              matrix_of_connect[i,j] = 0;
            }
          }
        }

        public void Initialise(int []input)
        {
          for (int i = 0; i < size; i++)
          {
            for (int j = 0; j < size; j++)
            {
              if (i == j) matrix_of_connect[i,j] = 0;
              else matrix_of_connect[i,j] += input[i] * input[j];
            }
          }
        }

        public void FindImage(int []input)
        {
          for (int i = 0; i < size; i++)   //заносим входящие значения
             {
              mass[i].x = input[i];
              last_y[i] = mass[i].y;
             }

          for (int k = 0; k < size; k++)   //сначало вычисляем S потом У
             {
              mass[k].s = 0;
              for (int i = 0; i < size; i++)
                {
                  mass[k].s = mass[k].s + matrix_of_connect[i,mass[k].index] * mass[i].x;
                }
               mass[k].ChangeState();
             }
            bool flag = true;
            //проверяем на равенство входного и выходного векторов    
             for (int i = 0; i < size; i++)      
               {
                if(last_y[i]!=mass[i].y)
                 {
                  flag = false;
                  break;
                 }
               }
           if(flag == false)
           {
             int[] temp = new int[size];
             for (int i = 0; i < size; i++)
              {
               temp[i] = mass[i].y;
              }
             //если неустойчивое состояние, то рекурсивный вызов функции, пока не будет стабилизации сети
             FindImage(temp);
           }
        }
        private Neuron []mass;
        private int[,] matrix_of_connect;
        private int[] last_y;
        //индексатор для синапсов нейронов (выходные значения каждого нейрона)
        public int [] Synapses
        {
          ...
        }
      };
    }


    * This source code was highlighted with Source Code Highlighter.


    И так сеть готова, теперь будем с ней работать.

    В данном случае я не буду описывать весь исходник, опишу лишь основные моменты

    Преобразование картинки в бинарную последовательность

        private int [] BitmapToIntArray()
        {
          //теперь перегоняем картинку в последовательность 1 и -1
          Color currentPixel;
          int[] temp = new int[size];
          int index = 0;
          for (int i = 0; i < picture.Height; i++)
          {
            for (int j = 0; j < picture.Width; j++)
            {
              currentPixel = picture.GetPixel(j, i);
              currentPixel.ToArgb();
              if (currentPixel == Color.FromArgb(255, 255, 255))
              {
                temp[index] = -1;
              }
              else
              {
                temp[index] = 1;
              }
              index++;
            }
          }
          return temp;
        }


    * This source code was highlighted with Source Code Highlighter.


    Результаты

    Пусть есть два образа-эталона

    imageimage
    Обучаем нашу нейронную сеть

    image

    Аналогично обучаем второму образу.

    image

    Создадим помехи в картинке:

    image

    Загружаем в програмку искаженную картинку:

    image

    Жмем «Восстановить», через несколько секунд:

    image

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

    imageА так как у нас сеть оперирует только с бинарными последовательностями, то думаю не составит труда переписать эту программку, для восстановления например опечаток в словах=) и прочие вкусности=)

    Для тех кому интересно выкладываю архив с образами и зашумлениями, сама програмка

    Ну и конечно если кто-то совсем проникнится идеей и понадобятся сорцы, напишите в коментариях, я обязательно выложу=)

    UPD: Поправил страсти в коде=) На которые указали: graninas, Nagg, Peregrinus
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 29

      0
      Браво! Было очень интересно почитать! Спасибо.
        +6
        только название топика переименуй, а то «не» как-то неинформативно смотрится.
          +4
          для вашего примера банальное попиксильное сравнение работало бы куда быстрее 13 секунд :)
            0
            Или векторный квантователь… что по сути одно и то же)
              +1
              Сеть Хопфилда хороша не как техническое решение, а как новый подход к нейросетям вообще. Скажем, ядерная (kernel) ассоциативная память, которая является пракически прямой наследницей сети Хопфилда, умеет запоминать уже произвольное число образов (с автоматическим ростом сети), умеет обобщать разные примеры в один образ, и обладает множеством других приятных свойств (например, работает, при малом числе запомненных образов, заметно быстрее).
              Так что для практических применений лучше брать не концептуальные работы 30-летней давности, а свежие результаты :) Ну и как всегда с нейросетями, применять их в лоб, на неподготовленных данных, категорически не рекомендуется.
              +14
              И вы уж простите, но за наличие след. названий ф-ций надо как минимум давать по рукам:
              Neyron
              ChangeSost
              Inicialise
              FindObraz
                +2
                FindObraz, %username%!
                +2
                Я тоже занимался НС, и именно Хопфилда и Хэмминга, и именно для задачи распознавания образа; только распознавалось у меня авторство, а не рисунок, но это не суть важно. Спасибо, что еще раз напомнили, как оно все действует.

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

                Ну, поскольку вы привели код, поговорим о коде. Мне ваша реализация нейросети чем-то не нравится.

                Мнемоники смешиваются: ChangeSost, FindObraz… Я, например, терпеть этого не могу. Должны быть: ChangeState, FindImage и т.п.
                Количество элементов фиксировано:
                private const int size = 10000;

                mass = new Neyron[size];
                new int[size, size];

                А что нам делать, если картинка других размеров? Если это вообще не картинка, а иного типа образ? Количество нейронов сильно зависит от типа данных, который мы в сеть загружаем. В общем, без динамических контейнеров в нейросетях жить будет туго.
                Еще плохо то, что в коде нет delete. Или вы скажете, что Шарпе был какой-то там сборщик мусора, я точно не знаю, язык не изучал, так что поверим и простим.
                matrix_of_connect вообще-то называется матрицей весов, если не ошибаюсь, то есть, weightMatrix или weights было бы очевиднее.

                А вообще, честно признаюсь, что и сам написал очень неудачную реализацию НС Хэмминга. Было это три года назад, когда я многого в программировании не знал.

                  0
                  >реализацию НС Хэмминга.
                  Эээ, Хопфилда, конечно. И Хэмминга тоже.
                    0
                    Спасибо за развернутую критику и подробное указание на проблемы именования в коде=) Основной код был написан 2 года назад на 2 курсе, а я что-то не придал этому внимания, сейчас поправлю;)

                    Получилось прямо как в анекдоте, эта статья не должна была публиковаться, видимо была глубокая ночь, и я по классике жанра вместо «Просмотра» кликнул «Опубликовать» ) Попробую привести к приемлемому виду=)
                    0
                    Имена функций и класса доставили
                      +2
                      Что вы пристали к человеку, по поводу сложности задачи представленной им, ну не учебник же Хайкина сюда печатать, он дал начало, так сказать для размышления.
                      А по поводу наименований функций, действительно надо дать по рукам.
                      • НЛО прилетело и опубликовало эту надпись здесь
                          0
                          Ну вот предположим исходные образы те же, а попытаемся восстановить:
                          image
                          То сеть успешно «говорит» что это
                          image
                          Тут главное чтобы именно исходные образцы не были слишком похожи.
                          Вот если нарисовать по разному глаза, и при восстановление полностью убрать улыбку, то сеть будет пытаться восстановить именно по имеющимся различиям в образцах
                          • НЛО прилетело и опубликовало эту надпись здесь
                              +4
                              мои нейроны тоже не смогли однозначно определить что это ;)
                            0
                            Программа поможет эффективно взамывать капчи
                              0
                              Да, только прежде её нужно также эффективно обучить.
                              +1
                              В свое время тоже писа сеть хопфилда. Но у вас я вижу поиск только последовательным итерациями. Еще можно добавить случайную выборку изменяющегося нейрона (также выбирать до стабилизации сети) и паралелльную обработку (меняем сначала состояния всех нейронов, потом уже меняем их выходы). Плюс неплохо бы добавить инвертацию изображения, это тоже иногда помогает.
                              Плюс необходимо учитывать что сеть может зациклиться и продумать механизм поиска данной ситуации (если в двух словах, то можно смело выходить когда на полной итерации по всем нейронам не было изменено ни одного нейрона, но от зацикливания это не поможет. Если в лоб, то можно хранить все итерации и с ними сравнивать. Если идти эмперически, то можно выяснить, что количество полных итераций в наихудшем варианте распзнавания будет где-то около количества нейронов, сейчас точно не помню как вычислял).
                              И еще мой совет убрать рекурсию. А то итераций может быть дофига (особенно при зацикливании сети), а стек не резиновый.
                                0
                                Да, действительно поиск может зациклиться из-за невозможности восстановить образ и при этом стек вызова переполнится. Но я намеренно упростил алгоритм, сделал рекурсию и не стал параллелить, чтобы сосредоточить внимание читателя именно на идеи=)

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

                                Ну и конечно при моем последовательном переборе требуется много ресурсов=) Я экспериментировал с картинками 400Х400, так там уже требуется около минуты ждать.
                                Была идея как-то группировать пиксели при больших разрешениях, что бы требовалось меньше нейронов, но я так ее и не развил.
                                  0
                                  могу выслать исходники, но сразу говорю делалось в качестве курсача, поэтому там жестко прошиты ограничения изображений 16х16, но сама идея я думаю должна быть понятна. Писалось на ruby/Qt4.
                                    0
                                    Скиньте, может даст зацепки)
                                      0
                                      емейл свой в личку напишите
                                        0
                                        Так Вы лучше выложите куд-нибудь, и ссылку здесь дайте, мне бы тоже было интересно посмотреть, да и мало ли кому еще.
                                          0
                                          куда?) на гуглокод смысла нет, ибо проект мертвый и что-то с ним делать не планируется. А во всякие пасти не получится, там не один файл.
                              –1
                              >приклодным
                              Что то в туалет захотелось
                                0
                                В следующий раз картинки сохраняйте в формате без потерь png, например, а не jpg.

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

                                Самое читаемое