Лабораторная работа
№13. Распознавание образов данных (Сеть Хемминга).
Цель работы. Изучение функционирования нейроподобных
элементов в
виде сети Хемминга. Разработка программы для
разпознавания
образов при преобразовании
информации.
Общие сведения
В настоящее время
дальнейшее повышение производительности компонентов связывает с системами,
обладающими свойствами массового параллелизма.
Одна из таких
систем – это нейрокомпьютер, использующий искусственную нейросеть. Искусственная
нейросеть (ИНС) – это параллельная структура, которая естественным образом реализует принцип
потока данных. Обычно под ИНС понимается набор элементарных нейроподобных
преобразователей информации – нейронов, соединенных друг с другом каналами
обмена информацией для их совместной работы.
Сформировались две
ветви исследований. Первая, нейробиологическая, основывается на моделировании
работы живого мозга, имея цель объяснить, каким образом в нем отображаются
сложные объекты и связи между ними, как устанавливается соответствие между
хранящейся и поступающей извне информацией, и другие вопросы, касающиеся
функционирования мозга. Второе направление исследований направлено на решение с
помощью ИНС задач переработки информации в различных областях знаний, особенно
плохо формализованных, где существующие модели субъективны и неадекватны.
Впечатляющие результаты использования ИНС достигнуты при распознавании образов,
при построении ассоциативной памяти, при создании самообучающихся Экспертных
систем, при решении оптимизационных задач большой размерности.
Предложено и
изучено большое количество моделей нейросетей. основными являются три типа
сетей, которые соответствуют трем известным методам обучения: самоорганизации,
последовательному подкреплению знаний, обучению с учителем.
Теоретическая часть. Сеть
Хемминга (СХ)
представляет сеть с двухслойной топологией, прямой связью между
слоями и с обучением с супервизором. Число нейронов N на входном слое равно размерности
векторов памяти, а число нейронов в выходном слое равно числу M векторов
памяти.
Сеть состоит из
двух слоев. Первый и второй слои имеют по m нейронов, где m – число образцов.
Нейроны первого слоя имеют по n синапсов, соединенных со входами сети
(образующими фиктивный нулевой слой). Нейроны второго слоя связаны между собой
ингибиторными (отрицательными обратными) синаптическими связями. Единственный
синапс с положительной обратной связью для каждого нейрона соединен с его же
аксоном.
Работы сети
заключается в нахождении расстояния Хэмминга от тестируемого образа до всех
образцов. Расстоянием Хэмминга называется число отличающихся битов в двух
бинарных векторах. Сеть должна выбрать образец с минимальным расстоянием
Хэмминга до неизвестного входного сигнала, в результате чего будет
активизирован только один выход сети, соответствующий этому образцу.
На стадии
инициализации весовым коэффициентам первого слоя и порогу активационной функции
присваиваются следующие значения:
, i=0...n-1,
k=0...m-1 (5)
Tk = n / 2, k = 0...m-1
(6)
Здесь xik – i-ый элемент k-ого образца.
Весовые
коэффициенты тормозящих синапсов во втором слое берут равными некоторой
величине 0 << 1/m. Синапс нейрона, связанный с
его же аксоном имеет вес +1.
Рис.1 . Схема сети Хемминга
Ход работы. Алгоритм функционирования сети Хэмминга следующий:
1.
На
входы сети подается неизвестный вектор X = {xi:i=0...n-1}, исходя из которого
рассчитываются состояния нейронов первого слоя (верхний индекс в скобках
указывает номер слоя):
, j=0...m-1 (7)
После этого
полученными значениями инициализируются значения аксонов второго слоя: yj(2) = yj(1), j = 0...m-1
2.
Вычислить
новые состояния нейронов второго слоя:
должна быть
достаточно большой, чтобы любые возможные значения аргумента не приводили к
насыщению.
3.
Проверить,
изменились ли выходы нейронов второго слоя за последнюю итерацию. Если да –
перейди к шагу 2. Иначе – конец.
Из оценки
алгоритма видно, что роль первого слоя весьма условна: воспользовавшись один
раз на шаге 1 значениями его весовых коэффициентов, сеть больше не обращается к
нему, поэтому первый слой может быть вообще исключен из сети (заменен на
матрицу весовых коэффициентов), поэтому так можно сделать в ее конкретной
реализации,
Сеть
классифицирует произвольные бинарные или аналоговые образы x (x1...xn
) в один из M классов. При этом начальное значение y j (0) нейронов в выходном слое определяется двумя способами в
зависимости от характера векторов памяти. Но в обоих случаях вектор стимула x с начало нормируется.
Если векторы
памяти являются бинарными, то y j (0) соответствует перекрытиям нормированного вектора стимула
с нормированными векторами памяти. Если векторы памяти являются аналоговыми, то
y
j (0) выбирается в соответствии с
величиной расстояния Хемминга между нормированными векторами памяти и стимула,
с помощью пороговой функции F.
После
сформирования начальных значений нейронов выходного слоя (в этом слое все нейроны связаны между
собой) выполняются итерации, про которых самодействие каждого нейрона является
положительным, а вклад остальных нейронов этого слоя отрицателен. С помощью
итераций выделяется тот нейрон, у которого значение y j (0) было максимальным, т. е. итерации прекращаются, когда
только один из нейронов имеет ненулевое значение, а номер этого нейрона и
определяет результат классификации.
4. Алгоритм
программы
1.
Инициализация
весов (можно взять
из файла “obraz.txt”).
2.
Ввод
распознаваемого образа.
3.
Определение кодовое расстояние d[
j].
4.
Определение
максимального сходство искомого образа с одним из исходных.
y[
j] porog d[ j].
5.
Вывод
результата.
Пример результата работы сети
Хемминга при разпознавании образоа
цифры.
1. Введите образ: 1111
1111
0011
0011
0011
0011
Результат: 7
Введите образ: 1111
0011
1111
1111
1100
1111
2. Результат: 2
Вопросы
1.
Приведите
примеры использовния сети Хемминга.
2.
Сколько слоев имеет сеть Хемминга?
3.
Какую
роль играют обратные связи?
4.
Каким
образом определяется распонаваемый образ?
5.
Какой
вид имеет авктивационная функция для сети Хеммнга?
6.Совпадает ли количество входов и выходов в сети
Хемминга?
Приложение:
1. Варианты интерфейса с результатами работы программы
Рис. 2.
Зашумлённая цифра 7.
Рис. 3.
Зашумлённая цифра 5.
.
1.Листинг процедур
Процедура распознавания зашумлённого образа
void CHammingDlg::OnRecognition()
{
// TODO: Add your control notification handler
code here
Invalidate();
UpdateWindow();
int k, i, j, iter=0;
for(k=0; k<m_N; k++) {y1[k]=y2[k]=y2new[k]=tmp[k]=0.0;}
//Инициализациясети
T = m_m*m_n/2.0; srand((unsigned)time(NULL)); double e
= rand()%((m_m*m_n))/(m_m*m_n*100.0);
//Вычислениесостояниянейроновпервогослоя for(k=0; k<m_N; k++) { for(i=0; i<m_m; i++) for(j=0; j<m_n;
j++)
y1[k] += m_image[i][j] * m_w[k][i*m_n+j]; y1[k]+=T;
}
//Инициализация
значений аксонов второго слоя полученными значениями
for(k=0; k<m_N; k++) y2new[k] = y1[k];
do
{
for(k=0;
k<m_N; k++) y2[k] = y2new[k];
//Вычислить новые состояния нейронов
второго слоя for(k=0;
k<m_N; k++) {
double sum=0;
for(j=0;
j<m_N; j++) if(j!=k) sum
+= y2[j]; y2new[k] = y2[k] - e * sum;
}
//Вычислитьзначенияаксоноввторогослоя for(k=0; k<m_N; k++) { if(y2new[k]<0)
y2new[k]=0;
else if(y2new[k]>=m_m*m_n) y2new[k]=m_m*m_n;
}
iter++;
}
while(Change());
//Определениесхожихобразов double etalon=-100; int index[10], l=0; for(k=0; k<m_N;
k++) index[k] = -1;
for(k=0; k<m_N; k++) if(y2new[k]>etalon)
{etalon = y2new[k]; index[0] = k;}
for(k=0; k<m_N; k++)
if(fabs(y2new[k]-etalon)<0.001
&& k!=index[0])
index[++l] = k;
CDC *pdc2 = m_results.GetDC();
pdc2->SetBkMode(TRANSPARENT); char
str[50]={0}; int s=0; for(k=0; k<m_N;
k++) { if(index[k]>-1)
{
sprintf(str,"Образпохожнацифру
%d", index[k]); pdc2->TextOut(40, 60+20*s, str); s++;
}
}
sprintf(str,"Числоитераций:
%d", iter);
pdc2->TextOut(50,
60+20*s, str); s++; m_results.ReleaseDC(pdc2);
}
Процедура проверки изменения выходов нейронов второго слоя int CHammingDlg::Change()
{
for(int k=0; k<m_N; k++)
if(fabs(y2new[k]-y2[k])>0.001)
return 1; return
0;
}
Считывание эталонных образов из файла FILE *f;
if((f=fopen("cifir.txt","r"))==NULL){printf("Невозможно открыть файл!\n"); return FALSE;} for(int k=0; k<m_N; k++)
for(i=0; i<m_m; i++) for(int j=0; j<m_n;
j++)
fscanf(f,
"%d", &m_etalon[k][i*m_n+j]); fclose(f);
