Теория нейронных сетей - Галушкин А.И.
ISBN 5-93108-05-8
Скачать (прямая ссылка):
3) сравнивается полученное выходное значение с корнем соответствующего пути (пути с той же вершиной) задали01,0 графа состояний, если корни совпали и подано не послеДнее выходное значение, переходим к п.1, иначе к п.4;
4) сравниваем от вершины к корню узлы обоих путей гРаФа состояний;
5) первая несовпавшая позиция укажет номер отказавшего нейрона. Если подавалось не последнее входное значение> переходим к п.1, иначе к п.6;
6) производим коррекцию отказов и переходим к п.1.
Процесс происходит до тех пор, пока не избавимся от всех
ошибочных путей. Если имеем наихудший вариант, т.е. отказавшие нейроны расположены в W слоях, то процесс повторится W раз.
Для оценки быстродействия разработанного алгоритма сравним его с методом перебора, при котором тестируется каждый нейрон сети для случая однократных отказов. Для этого представим последовательность действий при работе алгоритма локализации отказов. Пусть задан граф состояний, соответ-ствующий нейронной сети без отказов. Строим граф состоя-ний, соответствующий нейронной сети с отказами.
А. Последовательно подаем на вход нейронной сети значения из полного множества значений входной перемен#011 и для каждого значения получаем путь в графе состоя#ии и значение выхода всей нейронной сети. Сравниваем поЛУчен_ ный выход нейронной сети с соответствующим выходом нейронной сети без отказов. Если значения совпадают, на вход нейронной сети подается следующее значение, в прот#вном случае переходим к п. Б. Таким образом, после подачи на ВХ°Д нейронной сети полного множества значений, произведем0 2Н° операций элементарного сравнения бит с битом.
Б. В графе состояний обнаружен ошибочный путь. Проводим его сравнение с соответствующим путем графа состоя_ ний нейронной сети без отказов. Первая несовпавшая позиция в графе состояний указывает номер отказавшего неиР°-на. Если имеется один отказ нейрона, то после пода1111 на вход нейронной сети полного множества входных значении
W
производится 2 Н. элементарных сравнений. Таким образом> для максимального числа операций сравнения в случае алгоритма локализации отказов можно записать:
w
Величина Nx достигает максимального значения (16.7), так как предположительно отказавший нейрон имеет последний номер в последнем слое и ошибочный путь - последний.
Рассмотрим теперь тестирование нейронной сети методом перебора. Если длина полного проверяющего теста для одного нейрона есть 2Ni и проверять приходится все нейроны (N( -число входов нейронов г-го слоя; Ы.=Н^), то в случае перебора для числа элементарных сравнений можно записать:
N.
2тах
= 2 2 я,.
t—I
(16.8)
Величина N2 принимет здесь максимальное значение в том смысле, что длина теста для одного нейрона оценена величиной 2 Ni.
Покажем, что справедливо неравенство
N <N
lmax 2max‘
(16.9)
Подставляя в неравенство (16.9) значения из (16.7) и (16.8), имеем:
W W
2н° + ? я,.< 2 2 Нг'-1 Я.. i=i 1 t=i •
Раскрывая знаки сумм, имеем:
2но +Щ+- ¦ ¦ +Hw<H12ho+H22hi+-Учитывая очевидные неравенства:
(16.10)
Я2< Я22Hi
Hw< tfw2»w-i
при Hi >1, г =2, . . . , W,
перепишем неравенство (16.10) в виде
2но +Н1<Я12но.
(16.11)
Практически интересны случаи, когда Н0 >3, а Я. =2но.
Логарифмируя (16.12) получаем Н0 >1, что всегда выполняется. Неравенство (16.9) доказано.
Таким образом, получили, что при наихудших расположениях отказавшего нейрона алгоритм локализации отказов всегда быстрее, чем метод перебора.
Проведем аналогичные оценки для случая отказов произвольной кратности. Пусть в нейронной сети имеется т отказов, появившихся в к слоях. Рассмотрим наихудший случай расположения отказавших нейронов: k!=kmar:W, тогда неравенство (16.9) принимает вид:
w w
W(2Но + 2 Я.)< 2 2 Hi. (16.13)
Поскольку W<HV то неравенство (16.13) перепишется в виде
iv w
w2 Н, <2 2Н-‘Я,. (16.14)
1=1 1 i=2
При Я^ Я2 >1, W < Нг имеем
W (Нг+ Н2)< 2 н' Н2, тогда неравенство (16.14) имеет вид
W W
W 2 Я,. < 2 я. 2 н»'-1. (16.15)
i=3 ' 1=3 1
Рассматривая неравенство (16.15) для случаев Нх > Н2>.. .> Hw и Hj=. . -—Hw, делаем вывод, что оно выполняется, следовательно, выполняется и неравенство (16.13).
Оценим теперь относительный выигрыш в быстродействии по нижним оценкам при переходе к алгоритму локализации отказов от метода последовательного тестирования в случае многократных отказов:
w
^imax Щ2Ив+?