Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Информационная технология оценки динамических свойств нейронных сетей

#12 декабрь 2004

М.В. Горбатова, канд. техн. наук Московский Государственный Горный Университет

Информационная технология оценки динамических свойств нейронных сетей

Предлагается теория трасс, позволившая впервые оценить переходной процесс в нейронных сетях, функционирующих в субмикронном диапазоне. Предложенная информационная технология гарантирует 100 %-ное выявление аномалий за сверхкороткий срок.

Начиная с 80-х годов ведутся интенсивные исследования проблемы оценки динамических свойств нейронных сетей (НС), работающих в условиях субмикронной технологии.

Нормальное функционирование НС определяется не только неодновременным переключением синапсов, но задержками в аксонах. При анализе этой проблемы была выдвинута гипотеза "трех вторых" [1] — "суммарная задержка трех элементов всегда превышает задержку двух", что вызвало необходимость разработки новых методов моделирования динамических свойств НС; при решении — стала использоваться темпоральная логика [2], [3].

Кроме темпоральной логики стали разрабатываться и другие формализмы для моделирования НС: теоретико-графовые модели, семиотические (семиологические) модели. К теоретико-графовым моделям, наряду с сетями Петри, можно отнести сигнальные графы, диаграммы изменений [4], в которых вершинам-событиям ставятся в соответствие изменения переменных, дугам — причинно-следственные связи между событиями.

В качестве семиотической модели следует указать на бурно развивающееся направление — теорию трейсов [5], где под трейсом понимается последовательность символов, отражающая возможные пути в диаграммах переходов при графах допустимых маркировок при функционировании НС в заданной переключательной среде. Трейсовый подход применим на этапе эксплуатации НС, когда задано ее поведение. Другим подходом этого направления, который также применим на этапе эксплуатации НС, является логический подход [3]. При этом подходе определяется искажение выходного сигнала НС при заданных входных сигнальных последовательностях.

Для оценки динамических свойств НС на ранних стадиях проектирования — на этапе логического проектирования в рамках семиотического направления — предложен графово-трассовый подход [6].

Трассой Т(Ха, Хb) булевой функции f(Х) называется цепь решетчатого интервала I=[Хаb], включающая в себя вершины v(Хi), т.е.

("v(Xi) Î I) ((v(Ха) £ v(Xi)) & (v(Хi) ~ v(Хb))),

где v(Ха) — минимальный элемент, соответствующий вектору Ха интервала I;

у(Xb) —максимальный элемент, соответствующий вектору Хb интервала I; при этом

f(Xa) = f(Xb),

f(Xa) ¹ f(Xb), i ¹ b,

векторы Ха, Хb, Хi рассматриваются как идентификаторы соответствующих вершин, а интервал [Хa, Хb] — как решетка, в которой v(Ха) играет роль теоретике решетчатого "0", а v(Хb) — "1".

Свойства трассы Т(Хаb):

— |Х Ç Хb|=n-k в n-мерном булевом пространстве;

— Н(Хаb)=k, Н(Хаb) — расстояние по Хеммингу между точками Xa и Хb;

— | {T1(Xa,Xb)} | £ k!

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

В настоящее время подходы семиотического направления являются наиболее эффективными в смысле получения объективной информации о переходном процессе в НС.

Анализ формализмов, используемых при моделировании НС, показал необходимость применения ЭВМ и разработки соответствующих программных инструментальных средств в силу большой информационно-вычислительной трудоемкости решения задач анализа переходных процессов в НС. Из многих видов моделирования — моделирование правильности логического функционирования (в статике), моделирование временных характеристик и др. — наибольшую трудоемкость имеет моделирование динамических свойств, выявляющих риск сбоя НС, которое необходимо проводить на этапе логического проектирования НС.

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

Рассмотрим математическое обеспечение таких средств. Расширим гипотезу Мишры—Кларка [1] и сформулируем ее как "Суммарная задержка К элементов всегда превышает задержку k-i, i³1, К>2", тогда условие риска сбоя R(ха1а2,...,хаk) НС, реализующей булеву функцию f(х) при переключении k входных каналов (ха1а2,...,хаk), определяется следующей формулой:

где функция риска сбоя

R(xa1, xa2,...,xak)= { 1, если возможен сбой хотя бы на одной из k! цепей Ca(xb1,xb2,...,xbk)

0 - в противном случае;

- производная от булевой функции f по переменным ха1а2,...,хаk, единичное значение которой указывает на изменение функции I при "одновременном" изменении значений переменных xа1,xa2,...,xak;

perm (ха1, ха2, ..., хаk) — результат перестановки (permtation) индексов ха1, ха2,..., хаk;

переменные хb1, хb2, ..., хbk попарно не равны друг другу.

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

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

С учетом вероятной "фильтрации" ошибок невыходными нейронами НС предложена модель НС, представляющая собой граф GM=<VM,UM>, гомеоморфный графу GHC(каждая вершина взаимно однозначно соответствует нейрону НС, дуга — соответствующему аксону) и отличающийся от него наличием вершин Vji (i=1,2,...,КВХ — входной коэффициент нейрона НС), коинцидентных входным аксонам j-го выходного нейрона НС. Каждая вершина у соответствует линии переменной задержки, приведенной к входным аксонам j-го выходного нейрона НС:

tijmin £ tij £ tijmax

где tijmin и tijmax соответственно минимальное и максимальное время задержки прохождения сигнала (переключения) от входного аксона НС до i-го синапса j-го выходного нейрона НС, определяемое соответствующей активизируемой цепью; значение tij носит статистический характер.

Разность D (ij) = tijmax-tijmin называется временным дебалансом 1-го входного аксона относительно ]-го выходного нейрона.

Для уменьшения трудоемкости логического моделирования динамических свойств НС, в том числе и для устранения порождения "мусора" предлагается при поиске критических пар входных векторов, определяющих риск сбоя, учитывать топологические свойства структуры НС. С учетом этого, а также введенной модели НС, предложим следующую стратегию порождения критического пространства, в котором могут появляться аномалии динамических свойств НС.

1.Каждому из выходных элементов НС сопоставляем корень строящегося дерева <V,Г>. Вычисляем производные 1-го, 2-го,...,kBX-го порядков от функции fiа1а2,...,хаквх) [7], описывающей j-й выходной нейрон НС.

2.Каждому концу дуги, исходящей из корня дерева, сопоставляем "одновременное" переключение пары, тройки, ..., всех kBX аксонов j-го выходного нейрона НС.

Очевидно, что

|Г(v0) = 2kвx-kвx-1

где Г(v0) - сечение корня v0 дерева.

Определяем пары двойственных наборов

{(sa1,sa2,sap),(sa1,sa2,sap)},

p=2,3,...,Kвx; a1,a2,...,ap Î {a1,a2,..,akвx},

для которых

и имеется хотя бы одна цепь, удовлетворяющая соотношению (1).

Решетчатый интервал I(Хаb), содержащий хотя бы одну трассу Т(Хаb), называется критическим. Каждому критическому интервалу сопоставляется вершина следующего яруса дерева <V,Г>. Выделяем все трассы в каждом критическом решетчатом интервале. Каждой трассе сопоставляем висячую вершину в строящемся дереве.

Для эффективного вычисления производных булевы функции fi12,..., хn) задаются в виде соответствующих графов Кенига (двудольных графов). При этом исходное булево пространство размерности n представляется в виде декартова произведения булевых пространств размерностей [n/2], где [ ] — знак ближайшего целого, и n-[n/2]. Каждой точке булева пространства размерности [n/2] взаимно однозначно сопоставляются вершины верхней доли, каждой точке пространства размерности n-[n/2] — вершины нижней доли. Ребро графа Кенига взаимно однозначно соответствует точке исходного пространства размерности n, в которой функция fi12,...,хn) принимает единичное значение. При этом вычисление производных от булевой функции fi12,...,хn) сводится к определению нечетности частоты вхождения фиксированного ребра в графы Кенига, задающие соответствующие остаточные функции.

3. Определяем изменение значений входных аксонов НС, порождающее переключение Ха ® Хб, соответствующее критическому интервалу I[Хаб] на синапсах выходного нейрона. Для этого отображаем каждый критический интервал Ikвх=[Хаб] пространства Рkвx размерности kвx в интервал In = [Ха, Хб] заданного пространства Рn (n — число синапсов НС).

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

Если найдется элемент Вj не обеспечивающий согласованное функционирование цепей (условия поведения элемента Вj противоречивы), то соответствующий критический интервал I = [Хаб] является нереализуемым и в дальнейшем не рассматривается.

4. Для оптимального по времени выявления всех аномалий динамических свойств НС введем граф связности Gcв:

Gcв= <{Xi}, U>,

в котором каждая вершина взаимно однозначно соответствует вектору Хi, ребро {Хi Хj} — критическому решетчатому интервалу I(Хi Хj), причем

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

Для минимизации времени формирования входных векторов Хi при моделировании необходимо отсутствие их повторения, следовательно, граф Gсв должен быть гамильтоновым. Используя характеризационный анализ, можно показать, что граф связности Gсв эйлеров и гамильтонов тогда и только тогда, когда его цикломатическое число h (Gсв) равно нулю и его степень s (Gсв) не превышает двух:

(h(Gсв)=0) & (s(ССв £ 2).

При этих условиях граф Ссв является линейно упорядочиваемым.

5. Если граф Ссв эйлеров и гамильтонов, то пере ходим к п. 7, в противном случае — к п. 6.

6. Расширением носителя {DХi} в графе Gсв устраняем запрещенные фигуры. Анализ графа связности для реальных НС показал их малую связность. С учетом этого свойства был предложен следующий эффективный алгоритм расширения носителя {DХi} графа Gсв:

а) Gсв=Gi;

б) s(Gi) £ 2? "Да" — перейти к п. 3, "Нет" - перейти к п. 4;

в) h(Gi) > 0? "Да" - перейти к п. 4, "Нет" - перейти к п. 7;

г) определяем цепь максимальной длины pmax (в пределе — остов) графа Gi;

д) Gi\pmax = Gi, "штрихуя" в результирующем графе повторяющиеся векторы Хi

Переход к п. 2.

7. Линейно порядочиваем граф <Хi È DХi, U>.

Формируем входную сигнальную программу (ВС- программу) для моделирования аномалий динамических свойств НС.

8. Для оценки переходного процесса в НС предложим числовую характеристику в виде соответствующего функционала jij), учитывающего распределение трасс, функциональные и топологические свойства НС и временной дебаланс активизируемых цепей НС:

j(Xi,Xj)=maxlg(å f (T(Xi,Xj))x(H(Xi,Xj)-1).Dtmax(T(Xi,Xj))s),

                   s     i,j

где f(Т(Хi, Хj)) — частота (количество) цепей (Хi, Хj) решетчатого интервала I=[Хi, Хj], для которого функция риска сбоя s-го выходного аксона Rs(Xi, Xj)=1;

Н(Хi, Хj) — расстояние по Хэммингу между точками Хi и Хj в булевом kвxs-мерном пространстве;

Dtmax(T(Xi, Xj))s — временной дебаланс s-го выходного нейрона;

Dtmax(T(Xi, Xj))=max(tksmax-tksmin)

                            k,s

Здесь tksmax и tksmin — соответственно максимальная и минимальная величины задержки сигнала при прохождении от входного аксона до k-го синапса s-го выходного нейрона НС; k-индентификатор одного из переключающихся аксонов выходного нейрона при Хi ® Хj;

Dtmax(Т(Хi, Хj)) мажорирует длительность возможного ложного сигнала на s-м выходном аксоне НС, s=1, 2,...m, m — число выходных аксонов НС.

Для удобства практического применения оценка ji, Хj) вычисляется с использованием логарифмической шкалы.

Предложенные стратегии и алгоритмы реализованы в виде соответствующих средств, включающих в себя разработанные программные операционные модули ДИФФЕРЕНЦИРОВАНИЕ, РИСК, ТРАССА, АНТИСИНДРОМ, ПРОТИВОРЕЧИЕ, СВЯЗНОСТЬ, ЛИНЕАРИЗАЦИЯ, ОЦЕНИВАНИЕ, ВС-программа.

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

Программные средства разработаны для ПЭВМ РС/486 в МS-DОS с использованием языка Турбо СИ. Предусмотрены сервисные средства, позволяющие объявлять выходным элементом любой элемент НС. Разработанные программные средства позволяют оценивать переходные процессы НС на этапе их автоматизированного логического проектирования со сложностью до 107 вентилей при среднем времени логического моделирования динамики одного вентиля - 102 с.

Список литературы

1.Mishra B., Clarke E. Hierarchical verification of asynchronous circuits using temporal logic. - Txeor. Comput. Scl., 1985, vol. 381, 269-291

2.Milashi Y., Owicki S. Temporal specification of selftimed system - Proc. VLSI Syst. and Computx Cernegie - Mellon Univ. ConfPittsburgh, Pa. -1981. P. 203-212.

3.Bochmann D. Harddware specification with temporal logic: an example. - IEEE Jrans., 1982, vol. c-31, n3. l. 223-231.

4. Варшавский В.И., Мараховский В.И., Песчанский Л.С. Модель для спецификации и анализа асинхронных процессов в схемах // Изв. АН СССР, Техн. киберн. 1988. № 2.

5.Rem., van de Snebacheut J., Uddixg J. Trace theory and the definition of hierarchical componentx. - Proc. Caltech Conf VLSI, 1983. P. 225-239.

6. Горбатова М.В. Теория трасс // Информационные коммуни кации, сети, системы и технологии, НА, М., 1993 С 45—52

7. Горбатов В.А. Основы дискретной математики М Высшая школа, 1986, 312с.

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, №5. 1996

ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ

 

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)