Welcome to the homepage of MC# language!
MC# Project
Home page 
MC# language 
Documentation 
Publications 
 Code examples 
FAQ 

 
Downloads
MC# Programming 
System 

 
Related links
Parallel C# 
Polyphonic C# 
SKIF Project 

 
Contacts
 Contacts 


Mono powered

Microsoft .Net powered


  		  

Использование языка MC# для реализаций параллельного классификатора образов.*

Е.С.Борисов

суббота, 27 сентября 2003 г.


1 Цели и проблемы

К задаче классификации можно свести много прикладных задач : от оптического распознавания текста до выявление фальшивых кредитных карт и медицинской диагностики. Существует несколько подходов к построению классификаторов. В данной статье рассмотрен классификатор на основе искусственной нейронной сети [1]. При большой размерности нейронной сети, возникает потребность в высокопроизводительных многопроцессорных вычислительных системах [2]. Это особенно важно для классификаторов реального времени, где необходимо получать результат сразу, без существенных задержек. Для многопроцессорных вычислительных систем необходимо создавать специальные программы. В тексте такой программы определяются части (ветки), которые могут выполнятся параллельно, а также алгоритм их взаимодействия. Целью данной работы является построение классификатора для эффективного использования на многопроцессорных вычислительных системах.

2 Постановка задачи

Задача, которую мы будем рассматривать в данной статье, это классификация бинарных образов (черно-белых видеоизображений).

Постановку задачи можно сформулировать так : разработать параллельную программу классификации бинарных образов, способную одновременно обрабатывать несколько образов.

3 Решение

Для реализации классификатора будем использовать модели искусственных нейронных сетей.

3.1 Искусственная нейронная сеть

Искусственная нейронная сеть это совокупность нейронных элементов (рис. 1) и связей между ними [3].

Рисунок: математическая модель нейрона
\includegraphics[width=10cm]{pict/Image39.ps}

  • Нейронный элемент (нейрон) обладает группой однонаправленных входных связей $\overline x$, соединенных с выходами других нейронов. Каждый вход $x_i$ характеризуется величиной синаптической связи или весом $w_i$.

  • Каждый нейрон имеет текущее состояние, определяемое, как взвешенная сумма его входов1 :

    \begin{displaymath}s=\sum\limits_{i=1}^{n}x_i w_i\end{displaymath}

  • Нейрон имеет выходную связь $y$, с которой сигнал поступает на входы следующих нейронов. Выход нейрона есть функция его состояния:

    \begin{displaymath}y = f(s)\end{displaymath}

    Функция $f$ называется активационной.

Множество всех нейронов нейронной сети можно разделить на подмножества - т.н. слои. Слой искусственной нейронной сети это множество нейронов на которые в каждый такт времени параллельно поступают сигналы от других нейронов данной сети [3]. Взаимодействие нейронов происходит послойно.

3.2 Классификатор

В данной работе для реализации классификатора используется однослойная нейронная сеть (персептрон) из 10 нейронов (рис. 2).

3.2.1 Параметры сети

Рисунок: Классификатор
\includegraphics[width=12cm]{pict/Image44.ps}

  • однослойная нейронная сеть (рис. 2)
  • 35 входов
  • 10 выходов

  • состояние нейрона $i$ :
    \begin{displaymath} s_i=\sum\limits_{j=0}^{34} x_j\cdot w_{ij} \end{displaymath} (1)

  • пороговая функция активации с порогом $T=0$
    \begin{displaymath} y_i= f(s_i)= \left\{ \begin{array}{ccc} 1 &,& s_i\geq T \\ -1 &,& s_i<T \end{array} \right. \end{displaymath} (2)

3.2.2 Алгоритм работы классификатора

На вход классификатора подаются бинарные картинки (рис. 3) размером $5\times 7$ точек с изображением цифр ($0\ldots 9$), т.е. всего $5\times 7=35$ входов. На выходе получаем слово $(y_0\ldots y_9)$ , $y_i\in\{-1,1\}$, т.е. всего 10 выходов. Номер $j$, для которого выход $y_j=1$, соответствует номеру класса входного образца.

Рисунок: образы для классификации
\begin{figure}\centering\begin{verbatim}.OOO. ..O.. .OOO. .OOO. O...O .OO.. ... ......O O...O ..O.. .O... O...O .OOO. ..O.. OOOOO .OOO.\end{verbatim}\end{figure}

Важной особенностью искусственной нейронной сети есть возможность её обучения. Процесс обучения сводится к процедуре корректировки весовых коэффициентов. В качестве метода обучения используется правило Видроу-Хоффа [4]:


\begin{displaymath} w_{ij}(t+1)=w_{ij}(t)+\eta \cdot x_j\cdot e_i^n \end{displaymath} (3)

где
  • $w_{ij}$ - весовой коэффициент связи $i$-того нейрона с $j$-тым входом
  • $\eta=0.001$ - коэффициент скорости обучения
  • $x_j$ - $j$-тый вход сети
  • $e_i^n$ - ошибка нейрона $i$ на $n$-том образце
    \begin{displaymath} e_i^n=(d_i^n-s_i) \end{displaymath} (4)

    где
    • $s_i$ - состояние (1) нейрона $i$
    • $d_i^n$ - верный выход нейрона $i$ на $n$-том образце
Так же необходимо определить :
  • $E^n$ - ошибка сети на $n$-том образце
    \begin{displaymath} E^n=\frac{1}{2}\cdot\sum\limits_{i=0}^{9} (e_i^n)^2 \end{displaymath} (5)

  • $E$ - максимальная ошибка сети
    \begin{displaymath} E=\max\limits_{n=0\ldots 9}(E^n) \end{displaymath} (6)

  • $\varepsilon$$=0.0001$ - допустимая максимальная ошибка сети

Таким образом, прежде чем классификатор начнет работать его необходимо обучить на множестве учебных примеров, которое представляет собой множество пар - (картинка, выход сети).

Цикл обучения выглядит так :

  1. прогнать через сеть все образцы из множества учебных примеров и рассчитать максимальную ошибку сети $E$ по (6)

  2. если $E\leq $ $\varepsilon$ то конец

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

  4. перейти на п.1

3.3 Реализация с распараллеливанием

Соответственно представленной выше модели, на языке MC# [5][6][7] написан параллельный классификатор бинарных образов.

''Память'' сети это матрица весовых коэффициентов $W$. На этапе инициализации программы порождается начальная сеть. Эта сеть обучается на множестве пар [образ,выход_сети], которые содержатся в двух текстовых файлах : patterns.dat - обучающая выборка, targets.dat - верные выходы для обучающей выборки. Создается рабочая матрица весов, соответствующая [patterns.dat, targets.dat], которая используется, динамически создаваемыми, классификаторами для одновременного распознавания образов из файла tests.dat Таким образом, полученная система может ''читать'' словами.

Классификатор реализуется тремя классами : 

// однослойная сеть
class OneLayerNet { . . . } 

// персептрон, пороговая функция активации
class Perceptron : OneLayerNet { . . . }

// классификатор, 35 входов, 10 выходов 
// распознает бинарные картинки 5x7 точек
class Classificator : Perceptron   { . . . }

ParClassificator - класс, реализующий параллельный классификатор. На этапе инициализации программы при помощи конструктора ParClassificator(), на основе содержимого patterns.dat и targets.dat, создается рабочая матрица весов m_weight. Собственно, механизм распараллеливания заключен в двух методах recognize и Get :

  • movable recognize(double[,] W, sbyte[] I, Channel(NeuralIO)c) это перемещаемый (т.е. выполняемый параллельно с остальной программой) метод, который распознает бинарный образ I, используя матрицу весов W. Результат помещается в т.н. канал c. Конструкция c(res) в некотором смысле аналог конструкции return(res) для обычных ( последовательных ) функций.

  • void Get() & Channel m_channel( NeuralIO n )
    Стандартная конструкция языка MC#. Здесь объявляется канал m_channel типа NeuralIO и метод-обработчик канала Get, который забирает из канала данные, посланные туда, параллельно работающими методами recognize.

Параллельный классификатор ParClassificator осуществляет одновременное распознавание бинарных образов из tests.dat при помощи метода makeTestPar. Этот метод для каждого образа из tests.dat вызывает movable метод recognize и собирает результаты методом Get. 

class ParClassificator {
. . .
   protected double[,] m_weight;

   public ParClassificator() {
       Classificator nnet=new Classificator(N);
       nnet.teach("patterns.dat","targets.dat");
       m_weight=nnet.weight();
       . . .
   }
   . . .
   public void makeTestPar(string file) {
      . . .
      for(i=0;(loadPattern()==1);i++) { 
         recognize(m_weight,Copy(m_pattern), m_channel ); 
      }
      for(int j=0;j<i;j++) { Get(); }
      . . .
   }

   public movable recognize(double [,] W, sbyte[] I, Channel( NeuralIO ) c ) {
      Classificator nnet=new Classificator(N);
      NeuralIO n=new NeuralIO(IN_SIZE,OUT_SIZE);
      n.I(I);
      nnet.I(I);
      nnet.weight(W);
      nnet.step();
      n.O(nnet.O());
      c(n);
   }
  
   public void Get() & Channel m_channel( NeuralIO n ) {
      printIn(n.I());
      printOut(n.O());
   }
}

4 Результат

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

При увеличении количества процессоров, предполагается ускорение близкое к линейному. Ускорение[8] на $p$ процессорах это отношение

\begin{displaymath}s(p)=\frac{T(1)}{T(p)}\end{displaymath}

где $T(1)$ и $T(p)$- время выполнения программы на $1$ и $p$ процессорах соответственно.

Рисунок: результат работы классификатора
\begin{figure}\centering\begin{verbatim}.OOO. ..O.. .OOO. .OOO. O...O .OO.. ... ... ..O.. .O... O...O .OOO. ..O.. OOOOO .OOO. 0 1 2 3\end{verbatim}\end{figure}

Литература


1
Борисов Е.С. Искусственные нейронные сети - http://mechanoid.narod.ru/nns

2
Борисов Е.С. Вычислительные системы сверхвысокой производительности. - http://mechanoid.narod.ru/high_perf

3
Головко В.А., под ред. Галушкина А.И. Нейронные сети: обучение, организация и применение. - Москва : ИПРЖР, 2001. - 256 c.

4
Уоссермен Ф. Нейрокомпьютерная техника : Теория и практика. - Москва : Мир, 1992. - 200 c.

5
MC# - http://u.pereslavl.ru/~vadim/MCSharp

6
Адрес разработчиков языка MC# - yury@serdyuk.botik.ru

7
Борисов Е.С. Использование языка MC# для реализаций параллельных алгоритмов в 3D моделировании.

8
Дорошенко А.Е. Математические модели и методы организации высокопроизводительных параллельных вычислений. - Киев : Наукова думка, 2000. - 176 c.

Сноски

... образов*
эта статья опубликована в журнале "Кибернетика и Системный Анализ" Института Кибернетики АН Украины - [ http://www.icyb.kiev.ua/ ]
... входов1
возможны и другие определения

Об этом документе ...

Использование языка MC# для реализаций параллельного классификатора образов.

This document was generated using the LaTeX2HTML translator Version 2002 (1.67)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html index.tex

The translation was initiated by mechanoid on 2003-09-27

Evgeny S. Borisov
2003-09-27

Весь Переславль