К курсовому проекту по курсу «Архитектура компьютера» Тема: «Искусственные нейронные сети»

Нейронные сети Хопфилда и Хэмминга

35. 
    Среди различных конфигураций искусственных нейронных сетей (НС) встречаются такие, при классификации которых по принципу обучения, строго говоря, не подходят ни обучение с учителем, ни обучение без учителя. В таких сетях весовые коэффициенты синапсов рассчитываются только однажды перед началом функционирования сети на основе информации об обрабатываемых данных, и все обучение сети сводится именно к этому расчету. С одной стороны, предъявление априорной информации можно расценивать, как помощь учителя, но с другой – сеть фактически просто запоминает образцы до того, как на ее вход поступают реальные данные, и не может изменять свое поведение, поэтому говорить о звене обратной связи с "миром" (учителем) не приходится. Из сетей с подобной логикой работы наиболее известны сеть Хопфилда и сеть Хэмминга, которые обычно используются для организации ассоциативной памяти. Далее речь пойдет именно о них.
    
36. 
    Структурная схема сети Хопфилда приведена на Рис. 1. Она состоит из единственного слоя нейронов, число которых является одновременно числом входов и выходов сети. Каждый нейрон связан синапсами со всеми остальными нейронами, а также имеет один входной синапс, через который осуществляется ввод сигнала. Выходные сигналы, как обычно, образуются на аксонах.
    
37. 
    
    Рис. 1 - Структурная схема сети Хопфилда.
    
38. 
    Задача, решаемая данной сетью в качестве ассоциативной памяти, как правило, формулируется следующим образом. Известен некоторый набор двоичных сигналов (изображений, звуковых оцифровок, прочих данных, описывающих некие объекты или характеристики процессов), которые считаются образцовыми. Сеть должна уметь из произвольного неидеального сигнала, поданного на ее вход, выделить ("вспомнить" по частичной информации) соответствующий образец (если такой есть) или "дать заключение" о том, что входные данные не соответствуют ни одному из образцов. В общем случае, любой сигнал может быть описан вектором X = { x_i: i=0...n-1}, n – число нейронов в сети и размерность входных и выходных векторов. Каждый элемент x_i равен либо +1, либо -1. Обозначим вектор, описывающий k-ый образец, через X^k, а его компоненты, соответственно, – x_i^k, k=0...m-1, m – число образцов. Когда сеть распознa ет (или "вспомнит") какой-либо образец на основе предъявленных ей данных, ее выходы будут содержать именно его, то есть Y = X^k, где Y – вектор выходных значений сети: Y = { y_i: i=0,...n-1}. В противном случае, выходной вектор не совпадет ни с одним образцовым.
    
39. 
    Если, например, сигналы представляют собой некие изображения, то, отобразив в графическом виде данные с выхода сети, можно будет увидеть картинку, полностью совпадающую с одной из образцовых (в случае успеха) или же "вольную импровизацию" сети (в случае неудачи).
    
40. 
    На стадии инициализации сети весовые коэффициенты синапсов устанавливаются следующим образом:
    
41. 
     (1)
    
42. 
    Здесь i и j – индексы, соответственно, предсинаптического и постсинаптического нейронов; x_i^k, x_j^k – i-ый и j-ый элементы вектора k-ого образца.
    
43. 
    Алгоритм функционирования сети следующий (p – номер итерации):
    
44. 
    1. На входы сети подается неизвестный сигнал. Фактически его ввод осуществляется непосредственной установкой значений аксонов:
    
45. 
    y_i(0) = x_i , i = 0...n-1, (2)
    
46. 
    поэтому обозначение на схеме сети входных синапсов в явном виде носит чисто условный характер. Ноль в скобке справа от y_i означает нулевую итерацию в цикле работы сети.
    
47. 
    2. Рассчитывается новое состояние нейронов
    
48. 
    , j=0...n-1 (3)
    
49. 
    и новые значения аксонов
    
50. 
     (4)
    
51. 
    где f – активационная функция в виде скачка, приведенная на Рис. 2а.
    
52. 
    3. Проверка, изменились ли выходные значения аксонов за последнюю итерацию. Если да – переход к пункту 2, иначе (если выходы застабилизировались) – конец. При этом выходной вектор представляет собой образец, наилучшим образом сочетающийся с входными данными.
    
53. 
    Как говорилось выше, иногда сеть не может провести распознавание и выдает на выходе несуществующий образ. Это связано с проблемой ограниченности возможностей сети. Для сети Хопфилда число запоминаемых образов m не должно превышать величины, примерно равной 0.15• n. Кроме того, если два образа А и Б сильно похожи, они, возможно, будут вызывать у сети перекрестные ассоциации, то есть предъявление на входы сети вектора А приведет к появлению на ее выходах вектора Б и наоборот.
    
54. 
    
    Рис. 3. Структурная схема сети Хэмминга.
    
55. 
    Когда нет необходимости, чтобы сеть в явном виде выдавала образец, то есть достаточно, скажем, получать номер образца, ассоциативную память успешно реализует сеть Хэмминга. Данная сеть характеризуется, по сравнению с сетью Хопфилда, меньшими затратами на память и объемом вычислений, что становится очевидным из ее структуры (Рис. 3).
    
56. 
    Сеть состоит из двух слоев. Первый и второй слои имеют по m нейронов, где m – число образцов. Нейроны первого слоя имеют по n синапсов, соединенных со входами сети (образующими фиктивный нулевой слой). Нейроны второго слоя связаны между собой ингибиторными (отрицательными обратными) синаптическими связями. Единственный синапс с положительной обратной связью для каждого нейрона соединен с его же аксоном.
    
57. 
    Идея работы сети состоит в нахождении расстояния Хэмминга от тестируемого образа до всех образцов. Расстоянием Хэмминга называется число отличающихся битов в двух бинарных векторах. Сеть должна выбрать образец с минимальным расстоянием Хэмминга до неизвестного входного сигнала, в результате чего будет активизирован только один выход сети, соответствующий этому образцу.
    
58. 
    На стадии инициализации весовым коэффициентам первого слоя и порогу активационной функции присваиваются следующие значения:
    
59. 
    , i=0...n-1, k=0...m-1 (5)
    
60. 
    T_k = n / 2, k = 0...m-1 (6)
    
61. 
    Здесь x_i^k – i-ый элемент k-ого образца.
    
62. 
    Весовые коэффициенты тормозящих синапсов во втором слое берут равными некоторой величине 0 <� e < 1/m. Синапс нейрона, связанный с его же аксоном имеет вес +1.
    
63. 
    Алгоритм функционирования сети Хэмминга следующий:
    
64. 
    1. На входы сети подается неизвестный вектор X = {x_i:i=0...n-1}, исходя из которого рассчитываются состояния нейронов первого слоя (верхний индекс в скобках указывает номер слоя):
    
65. 
    , j=0...m-1 (7)
    
66. 
    После этого полученными значениями инициализируются значения аксонов второго слоя:
    
67. 
    y_j⁽²⁾ = y_j⁽¹⁾, j = 0...m-1 (8)
    
68. 
    2. Вычислить новые состояния нейронов второго слоя:
    
69. 
     (9)
    
70. 
    и значения их аксонов:
    
71. 
     (10)
    
72. 
    Активационная функция f имеет вид порога (рис. 2б), причем величина F должна быть достаточно большой, чтобы любые возможные значения аргумента не приводили к насыщению.
    
73. 
    3. Проверить, изменились ли выходы нейронов второго слоя за последнюю итерацию. Если да – перейди к шагу 2. Иначе – конец.
    
74. 
    Из оценки алгоритма видно, что роль первого слоя весьма условна: воспользовавшись один раз на шаге 1 значениями его весовых коэффициентов, сеть больше не обращается к нему, поэтому первый слой может быть вообще исключен из сети (заменен на матрицу весовых коэффициентов).
    
75. 
    
    
76. 
    6. Распознавание текста
    
77. 
    Задача: Требуется написать программу, которая будет выделять из «зашумленной картинки» образы(буквы) и будет распознавать их.
    
78. 
    Для решения данной задачи можно использовать нейронные сети Хопфилда и Хэмминга. Исследовав эти нейронные сети выбор остановился на реализации нейронной сети Хэмминга, так как она более точная и требует меньше памяти.
    
79. 
    Алгоритм решения задачи:
    

1. 
   Выделение образов из картинки
   
2. 
   Нормировка образов
   
3. 
   Распознавания каждого образа по отдельности
   

81. 
    Для того чтобы выделить образ необходимо понять «а что такое образ»?
    
82. 
    Для начала введем некоторые понятия:
    
83. 
    Функция расстояние между двумя различными цветами – функция, принимающая на вход два цвета и возвращающая некоторое численное значение(расстояние). Для решения данной задачи использовалась функция суммы квадратов разности 4-х составляющих цветов(A, R,G,B). Очевидно, чем меньше значение функции, тем более похожи цвета.
    
84. 
    Связные пиксели – 2 соседних пикселя(имеют общую сторону), функция расстояния между двумя их цветами меньше заданной точности(обычно 100).
    
85. 
    Алгоритм заключается в следующем:
    

1. 
   Строим по картинке неориентированный граф следующим образом. Вершина – пиксель. Между вершинами будет ребро в том случае, если соответствующие пиксели связные.
   
2. 
   Полученный граф разбивается на связные компоненты. Связная компонента может представлять либо образ, которых необходимо выделить, либо фон.
   
3. 
   Предполагается, что самая большая связная компонента – фон. Считаем средний цвет фона.
   
4. 
   Удаляем из рассмотрения компоненты, средний цвет которых близок к среднем цвету фона (функция расстояния меньше заданной точности).
   
5. 
   В итоге получается набор связных компонент, в которых исключен фон, однако здесь присутствуют шумы. Как правило, шумы представляют собой небольшие связные области.
   
6. 
   Фильтрация шумов:
   
   1. 
      Рассматриваем компоненты от самой большой к самой маленькой
      
   2. 
      Если размер текущей компоненты значительно отличается (задается коэффициентом) от среднего значения размера не отфильтрованных компонент, то эта компонента – является шумом и, соответственно, удаляется. Иначе – принимается.
      

86. 
    Оставшиеся связные компоненты и будут рассматриваться как выделенные образы.
    
87. 
    Пример:
    
88. 
    Пусть на вход получаем такую картинку:
    
89. 
    
    
90. 
    Получаем:
    
91. 
    
    

92. 
    Под нормировкой здесь понимается – преобразование картинки(образа) к некому эталонному размеру(увеличение, уменьшение) и составления из картинки 2-битного вектора, который будет распознаваться нейронной сетью.
    
93. 
    При выделении образа учитываются только пиксели, которые принадлежат связной компоненте. Таким образом выкидываются шумы.
    
94. 
    
    

    До	После

95. 
    
    
96. 
    Далее изменяем размер картинки до эталонного(50х50):
    
97. 
    
    
98. 
    Получаем матрицу:
    
99. 
    
    

105. 
     Матрица изображения преобразуется в линейный вектор размерности 2500. Вектор подается на вход нейронной сети. Как показала практика, примерно через 20 итераций нейронная сеть переходит в устойчивое состояние и возвращается найденный эталонный образ. Точность распознавания зависит от помех и неточностей в написании букв. Обучение сети производилось на латинских буквах шрифта Arial
     
106. 
     
     

115. 
     
     
116. 
     Как видно, в последнем примере буква “N” распозналась сразу тремя буквами, что связано с тем, что неверно выделился образ:
     
117. 
     
     
118. 
     
     

6. 
   Заключение
   

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

6. 
   Список использованной литературы
   

• 
  Lipman R. An introdaction to computing with neural nets // IEEE Acoustic,Speech and Signal Processing Magazine,1987,no 2,L.4-22.
  
• 
  МакКоннелл Дж. Основы современных алгоритмов. — М.: Техносфера, 2004. — 368 с.
  
• 
  В.А.Головко, под ред.проф.А.И.Галушкина Нейронные сети: обучение, организация и применение. - Москва : ИПРЖР, 2001
  
• 
  http://www.recognition.mccme.ru/pub/RecognitionLab.html/methods.html
  
• 
  http://www.codenet.ru/progr/alg/ai/htm/gl3_5.php
  
• 
  http://en.wikipedia.org/wiki/Artificial_neural_network