Распознавание образов с помощью нейронных сетей (стр. 1 )

Министерство образования и науки Российской Федерации

Вятский государственный университет

Факультет автоматики и вычислительной техники

Кафедра электронных вычислительных машин

Распознавание образов

с помощью нейронных сетей

Методические указания

к самостоятельным и лабораторным работам

Дисциплина «Системы искусственного интеллекта»

Специальность 22.01, 5 курс, дневное отделение

Киров, 2008

УДК 5

Методические указания для лабораторных работ по курсу «Системы искусственного интеллекта» / Вятский государственный университет. Киров, 2008, 24с./

Составитель к. т.н., доцент кафедры ЭВМ

© Вятский государственный университет, 2008г.

Целью лабораторной работы является изучение принципов распознавания образов с помощью различных нейронных сетей, влияния параметров на качество распознавания и применения автокоррелятора.

1 Лабораторная работа №1

Тема: «Распознавание образов с помощью программ perseptr.exe, linear.exe”

Целью данной работы является знакомство с нейронными сетями некоторых видов, применяемыми для распознавания образов на основе их моделей (программные модели: perseptr.exe, linear.exe”).

Задание для выполнения лабораторной работы

Вариант задания лабораторной работы
1	2	3	4	5
12345.pbl	30124.pbl	ABCDE.pbl	FTEDC.pbl	FTKLU.pbl
6	7	8	9	10
SREKO.pbl	ADZCO.pbl	POTRE.pbl	MNBVK.pbl	NMKLR.pbl
11	12	13	14	15
TENHP. pbl	NEMHP. pbl	WENHN. pbl	OURFP. pbl	SDOHP. pbl
16	17	18	19	20
TENHM. pbl	XNMHP. pbl	WKNHD. pbl	COURD. pbl	SDOHP. pbl

Каждая программа является моделью соответствующей нейронной сети. Для обучения сети используется обучающее множество, состоящее из 5 задач. В каждой задаче может быть несколько примеров. У каждого примера может задаваться вес данного примера в процессе обучения.

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

1.2 Автокоррелятор

Входные данные задачи распознавания черно-белых изображений представляют собой последовательность 0 и 1 (есть точка - 1, нет - 0). Такие данные не всегда оптимальны для решения задачи распознавания. В связи с этим возникает задача предобработки данных. Возможны различные виды предобработки — преобразования Фурье, построение различных инвариантов и т. п. В этих программах (кроме Hopfield) предусмотрено несколько видов предобработки (выбрать тип автокореллятора можно в меню “Параметры”):

чистый образ (без предобработки);

сдвиговый автокоррелятор;

автокоррелятор сдвиг+отражение;

автокоррелятор сдвиг+вращение;

автокоррелятор сдвиг+вращение+отражение.

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

1.2.1 Сдвиговый Автокоррелятор

Основная идея этого метода предобработки — сделать вектор входных сигналов нейронной сети инвариантным относительно сдвига. Другими словами, два вектора, соответствующие одному и тому же образу, расположенному в разных местах шаблона 10*10, после предобработки этим способом должны совпадать! Рассмотрим подробно метод вычисления автокоррелятора. Пусть дано изображение X. x [i, j] — точка изображения в i-ом ряду и j-ом столбце. Будем считать x[i, j]=0, если хотя бы один индекс (i или j) находится вне пределов интервала (1,10). Элемент автокоррелятора A — a[l, k] вычисляется по формуле

.

Другими словами, a[l, k] — число точек совпадающих при наложении изображения X на это же, но сдвинутое на вектор (l, k) изображение. Легко заметить, что ненулевыми могут быть только элементы автокоррелятора A с индексами -9<=l, k<=9. Однако a[l,k]=a[-l,-k]. Таким образом, можно рассматривать только часть коррелятора с индексами -9<=i<=9 и 0<=j<=9. Если Вы задаете размер автокоррелятора m*n, то входными сигналами для сети будут служить элементы a[i, j] при -(n-1)<=i<=(n-1), 0<=j<=m-1.

1.2.2 Автокоррелятор сдвиг+отражение

Этот метод предобработки в качестве исходных данных использует сдвиговый автокоррелятор. Идея вычисления автокоррелятора сдиг+отражение (S): сложим значения, соответствующие симметричным точкам, и будем считать их новыми значениями. s[k, l]=a[k, l]+a[k,-l]. Очевидно, что автокоррелятор S инвариантен относительно сдвига и отражения. Кроме того, можно ограничиться только элементами с неотрицательными индексами. Если Вы задали размеры автокоррелятора m*n, то входными сигналами сети будут s[l, k] при 0<=l<=n-1, 0<=k<=m.

1.2.3 Автокоррелятор сдвиг+вращение

Этот метод предобработки в качестве исходных данных использует сдвиговый автокоррелятор. Идея вычисления автокоррелятора: поворачиваем автокоррелятор A на 90 градусов относительно элемента a[0,0] и получаем элемент автокоррелятора R умножением соответствующих элементов — r[p, q]=a[p, q]*a[q,-p]. Очевидно, что автокоррелятор R инвариантен относительно сдвига и поворота на 90 градусов. Кроме того, можно ограничиться только элементами с неотрицательными индексами. Если вы задали размеры автокоррелятора m*n, то входными сигналами сети будут s[l, k] при 0<=l<=n-1, 0<=k<=m.

1.2.4 Автокоррелятор сдвиг+вращение+отражение

Этот метод предобработки в качестве исходных данных использует автокоррелятор сдвиг+вращение. Идея вычисления автокоррелятора сдиг+вращение+отражение (C): сложим значения, соответствующие симметричным точкам, и будем считать их новыми значениями. c[k, l]=r[k, l]+r[k,-l]. Очевидно, что автокоррелятор C инвариантен относительно сдвига, вращения и отражения. Кроме того, можно ограничиться только элементами с неотрицательными индексами. Если вы задали размеры автокоррелятора m*n, то входными сигналами сети будут с[l, k] при 0<=l<=n-1, 0<=k<=m.

1.3 Интерфейс программы

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

® Смена активной задачи. Активная задача

отличается цветами рамки и заголовка.

­¯ Смена активного примера в поле задачи.

Home Сделать активным первый пример задачи.

End Сделать активным последний пример задачи.

ENTER Перейти в режим редактирования задачи.

DELETE Удалить пример.

F1 Вывести справочную информацию. Отметим,

что эта клавиша работает во всех режимах.

F2 Открыть стандартный задачник.

F3 Запомнить обучающее множество.

F4 Прочитать обучающее множество.

F5 Распознавание обучающего множества.

CTRL-F5 Распознавание текущего тестового примера.

ALT-F5 Распознавание тестовой задачи.

SHIFT-F5 Тест статистический.

F6 Обучение нейронной сети.

ALT-F6 Случайное изменение карты.

CTRL-F6 Контрастирование.

F7 Запомнить карту.

F8 Прочитать карту.

CTRL-F8 Редактировать карту.

F9 Выйти в меню.

F10 Закончить работу.

ALT-C Записать изображение активного примера

активной задачи в карман.

Кроме того, часть функций может быть выполнена только через выход в меню. Выбрав нужный пункт в меню и нажав “F1” Вы получите справку о выполняемой им функции.

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

®­¯ Перемещение курсора.

Пробел Поставить/стереть точку.

ENTER, ESC Выход из режима редактирования.

CTRL- Сдвинуть изображение влево.

CTRL-® Сдвинуть изображение в право.

PGUP Сдвинуть изображение в верх.

PGDOWN Сдвинуть изображение в вниз.

F1 Справочная информация.

F2 Просмотр стандартного задачника.

F3 Инвертирование изображения.

F4 Затенение изображения.

F5 Инвертирующий шум.

CTRL-F5 Изменить уровень инвертирующего шума.

F6 Добавляющий шум.

CTRL-F6 Изменить уровень добавляющего шума.

F7 Гасящий шум.

CTRL-F7 Изменить уровень гасящего шума.

DELETE Очистить изображение.

В Ввести новый вес примера.

G Повернуть изображение на 90 градусов по часовой стрелке.

О Отразить изображение относительно вертикальной

оси.

ALT-C Записать текущее изображение в карман.

ALT-P Заменить текущее изображение на хранящееся в

кармане.

При выходе из режима редактирования, если изображение изменялось, то возникает вопрос “Заменить старый пример?”. При ответе “Y” текущий редактируемый пример будет заменен, при ответе “N” — новый пример будет добавлен в текущую задачу.

1.4 PERCEPTR

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

Нейронная сеть состоит из десяти нейронов. Каждый нейрон отвечает за разделение двух образов. Нейрон 1 разделяет образы 1 и 2, 2 — 1 и 3, 3 — 1 и 4, 4 — 1 и 5, 5 — 2 и 3, 6 — 2 и 4, 7 — 2 и 5, 8 — 3 и 4, 9 — 3 и 5, 10 — 4 и 5. При каждом распознавании должен “срабатывать” только один нейрон. Все нейроны получают все входные сигналы.

Алгоритм работы нейрона:

Пусть N — число элементов входного вектора; X[k] — k-ая компонента входного вектора; M[i, k] — вес передачи k-ого сигнала i-ому нейрону (элемент синаптической карты); a[i] — сигнал i-ого нейрона.

, где i — номер нейрона.

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

Пусть M[i] — элементы фрагмента синаптической карты, отвечающего за разделение двух образов; A[i, j] — элементы вектора входных сигналов j-ого примера первого образа; w[j] — вес j-ого примера первого образа; B[i, j] — элементы вектора входных сигналов j-ого примера второго образа; W[j] — вес j-ого примера второго образа; N — число входных сигналов.

Тогда алгоритм обучения сети представляет следующую последовательность действий:

0. Счетчик проходов устанавливаем в 0.

1. Начало прохода. Счетчик проходов устанавливаем в 0.

2. Цикл по номеру примера первого образа.

3. Вычисляем решающую величину:

4. Если X<0, то решение верное, в противном случае увеличивается счетчик ошибок и предпринимается корректирующее действие:

M[i]=M[i]-A[i,j]*w[j].

5. Цикл по номеру примера второго образа

6. Вычисляем решающую величину:

7. Если X>0, то решение верное, в противном случае увеличивается счетчик ошибок и предпринимается корректирующее действие:

M[i]=M[i]+B[i,j]*W[j].

8. Если число ошибок за проход равно 0, то заканчиваем работу, иначе увеличиваем счетчик проходов и переходим к шагу 2.

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

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

1.5 LINEAR

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

Структура сети аналогична структуре в программе Perceptr.

Алгоритм работы нейрона:

Пусть N — число элементов входного вектора; X[k] — k-ая компонента входного вектора; M[i, k] — вес передачи k-ого сигнала i-ому нейрону (элемент синаптической карты); a[i] — сигнал i-ого нейрона.

, где i — номер нейрона.

Нейронная сеть, имитируемая данной программой, не обучается в точном смысле этого слова. Элементы синаптической карты не подбираются в ходе обучения, а вычисляются по заранее заданному алгоритму. Алгоритм, по которому строится карта, опирается на простую идею: если даны две "средние" точки разных образов (задач), то разделяющая гиперплоскость проводится через середину соединяющего эти точки отрезка, перпендикулярно к нему.

При формировании синаптической карты каждая задача рассматривается как одна точка в пространстве входных сигналов. Но Вы можете задать множество примеров одного образа (задачи). В этом случае при формировании синаптической карты используется некоторая "средняя" точка. Существует множество различных способов вычисления "средней" точки. В данной программе Вам предоставлены на выбор два метода вычисления "средней" точки:

простой барицентрический (, где i — номер координаты в векторе входных сигналов, j — номер примера, М — количество входных примеров);

взвешенный барицентрический (сначала вычисляется простой барицентр , где i — номер координаты, j — номер примера, W[j] — вес примера. Затем вычисляется взвешенный барицентр. Каждому примеру присваивается вес равный произведению веса примера на евклидово расстояние от соответствующей точки до Xср.:

W'[j]=W[j]*(расcтояние от X[j] до Xср),

).

1.7 Задание для выполнения лабораторной работы

Вариант задания лабораторной работы
1	2	3	4	5
12345.pbl	30124.pbl	ABCDE.pbl	FTEDC.pbl	FTKLU.pbl
6	7	8	9	10
SREKO.pbl	ADZCO.pbl	POTRE.pbl	MNBVK.pbl	NMKLR.pbl
11	12	13	14	15
TENHP. pbl	NEMHP. pbl	WENHN. pbl	OURFP. pbl	SDOHP. pbl
16	17	18	19	20
TENHM. pbl	XNMHP. pbl	WKNHD. pbl	COURD. pbl	SDOHP. pbl

1.7.1 Сформировать вариант задания и сохранить его с соответствующим именем файла, указанного в задании. Если файл задания уже создан, то загрузить его (клавиша F4, файл, указанный в таблице согласно выданному варианту) обучающее множество (например, файл АВСDE.pbl).