[ на главную ]

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

Е.С.Борисов

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


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

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

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

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

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

3 Решение

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

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

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

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

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

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

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

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

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

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$ , соответствует номеру класса входного образца.

Рисунок 3: образы для классификации
\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)

где Так же необходимо определить :

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

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

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

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

  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 :

Параллельный классификатор 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$ процессорах соответственно.

Рисунок 4: результат работы классификатора
\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}

Текст программы на MC# [ здесь ]


Литература


1
Борисов Е.С. Искусственные нейронные сети - http://www.mechanoid.kiev.ua

2
Борисов Е.С. Вычислительные системы сверхвысокой производительности. - http://www.mechanoid.kiev.ua/parallel-high-performance-computing.html
3
Головко В.А., под ред. Галушкина А.И. Нейронные сети: обучение, организация и применение. - Москва : ИПРЖР, 2001. - 256 c.

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

5
MC# - http://www.mcsharp.net

6
Адрес разработчиков языка MC# - [email protected]

7
Борисов Е.С. Использование языка MC# для реализаций параллельных алгоритмов в 3D моделировании. http://www.mechanoid.kiev.ua/parallel-mcs-3d-model.html

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

Evgeny S. Borisov
2003-09-27
При использовании материалов этого сайта, пожалуйста вставляйте в свой текст ссылку на мою статью.