Ассоциативная память - применение сетей Хемминга для нечеткого поиска

Принцип работы памяти у компьютера Фон-Неймановской архитектуры и человека принципиально отличаются друг от друга. Компьютер используется для поиска информации адрес, а человек ассоциации. Поэтому, если вы знаете, где искать информацию, компьютер найдет ее быстро, но если не знаете, то придется все перебирать. Хорошо еще, если данные не искажены. Вероятно, более "качественная" (если можно так выразиться) память человека позволяет при гораздо меньших вычислительных возможностях лучше анализировать. Принципиальную ограниченность современных компьютеров можно обойти при помощи различного рода систем ассоциативной памяти, например, сетей Хемминга.

Принципы работы сетей Хемминга

Алгоритм работы базируется на определении Хеммингово расстояния. Хеммингово расстояния – это количество отличающихся позиций в бинарных векторах. Результатом работы сети является нахождение образа с наименьшим расстоянием.

 – расстояние 0
 – расстояние 2
 – расстояние 5

Отсутствие сигнала кодируется как (-1), наличие (1). Сеть состоит всего из 2-х слоев.

Рис. 1. Схема сети Хэмминга

Алгоритм работы

  1. Инициализация весовых коэффициентов первого слоя.
    ,
    где Х – запоминаемые образы, i – соответствующий компонент вектора X, j – номер образа, n – размерность вектора X, m – количество запоминаемых образов.
  2. Расчет состояния нейронов первого слоя.
    ,
    где X – неизвестный образ, T = n/2 – порог активационной функции
  3. Расчет состояния нейронов второго слоя.
    ,
    где p – номер итерации, 0 < < 1/m
    ,
    где f – пороговая активационная функция.
    ,
    где F – порог активационной функции. Обычно F выбирается достаточно большим, так, чтобы при любом допустимом значении входа не наступало насыщение. На практике F обычно берется равным количеству примеров.
  4. Проверка условия выхода.
    Если выходы не стабилизировались, т.е. изменялись за последнюю итерацию, то переход на шаг 3, иначе конец.

Область применения

На ум сразу приходит задача оптического распознавания символов (OСR). Действительно, так оно и есть. При решении этой задачи сети Хемминга активно используются. Но это, так сказать, лежит на поверхности. На практике они используются для восстановления зашумленного исходного сигнала, задачах оптимизации и во многих других случаях. Рассмотрим один из таких частных случаев – нечеткий поиск.

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

А – 00001
Б – 10001
В – 10010

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

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


Алексей Стариков, Алексей Арустамов

Литература

  1. R.P.Lippman, "An introduction to computing with neural nets", IEEE ASSP Magazine. Apr. 1987.
  2. B.Muller, J.Reinhardt, "Neural networks", Springer -Verlag. 1990.
  3. Ф.Уоссермен, "Нейрокомпьютерная техника" , М.: Мир, 1992
  4. С.Короткий, "Нейронные сети Хопфилда и Хэмминга"
  5. А.Ежов, С.Шумский, "Нейрокомпьютинг и его применение в экономике и бизнесе",1998.


искусственные нейронные сети нечеткая логика Расстояние Хэмминга
Если у вас есть статья, заметка или обзор, которыми вы хотите поделиться с аудиторией нашего сайта, присылайте информацию на: neuronus.com@yandex.ru.
Гость, оставишь комментарий?
Имя:*
E-Mail:


Свежее новое
  • 10 известных вещей, которые были изобретены женщинами
  • Хоть и считается, что все изобретения в мире сделаны представителями мужского пола, есть известные вещи, которыми мы пользуемся каждый день,
  • Обнаружили новые артефакты, которые доказывают, что на Земле в древности жила очень развитая раса
  • Не так давно группе археологов удалось найти ряд интересных артефактов. Обнаруженные предметы стали причиной возникновения жарких споров между
  • Удалось сделать качественные фото первого серийного ударного вертолета Ми-28НМ
  • В интернет выложены фотоснимки выпускаемого серийно наиболее совершенного боевого вертолёта из РФ, который создан на основе Ми-28Н. В блоге центра,
  • Астроном «охотился» на секретный космоплан США X-37B и заснял его на орбите Земли
  • Космоплан Boeing X-37В — экспериментальная версия американского летательного аппарата, предположительно способного функционировать на высотах более
  • Атлантику окружил огромный «ковер» из саргассовых водорослей, испугав туристов
  • Изучая спутниковые снимки, американские ученые обнаружили, что в Атлантическом океане начиная с 2011 года постоянно образуется гигантский «ковер» из
Последние комментарии
Ученые раскрыли тайну «хабаровского метеорита»
Гиперзвуковой блок Авангард, чп случилось буквально накануне сообщения об успешных испытаниях. В сообщениях указывалось, что боевой блок был выпущен
Американский физик доказал, что Вселенная может быть двумерной
КОСМОС это Вечная, Единая, Субстанция, которая не имеет ни Массы, ни Пространства, ни Энергии. Эти понятия для Космоса Нулевые, их просто НЕТ.
Ученые раскрыли тайну «хабаровского метеорита»
Были там знакомые, и не фига не оползень и камета была, военные учение были, и не туда попала ракета
Благодаря перовскиту в ближайшем будущем может произойти переворот в энергетике
А как же управляемый термоядерный реактор? Именно освоение термоядерной энергии даст прорыв. Как в свое время (и сейчас) обеспечивает ядерная
Японцы создали энцефалитных клещей для борьбы с Россией: правда или миф
Бред, энцефалит был на ДВ всегда. Дохли от него пачками во время разных покорений Сибири, потом была специальная экспедиция(в 1937г.) и в её ходе
Мы в социальных сетях
Статистика
3  
Всего статей 2098
1  
Всего комментариев 368
0  
Пользователей 124