Теория нейронных сетей - Галушкин А.И.
ISBN 5-93108-05-8
Скачать (прямая ссылка):
--------=—-------------- > (16'16>
^тах 2 2 Hi
1*1
где N\m&x ~ нижняя оценка быстродействия алгоритма локализации отказов для многократных отказов. Неравенство (16.16) в случае Яг= Я2=.. .= Hw = Я принимает вид
&lmax _ 1 W
lmax
(16.17)
При Hj > ... > Hw вместо величины Н в оценку (16.17) можно подставить некоторую среднюю величину Я, например Я =
Очевидно, что при достаточно больших Я вторым слагаемым в сумме (16.17) можно пренебречь. Таким образом, выигрыш в быстродействии при применении алгоритма локализации отказов по сравнению с методом последовательного тестирования, согласно нижним оценкам, растет линейно с ростом числа нейронов в слоях.
16.3. Алгоритм построения минимального теста
для отказов типа логических констант на выходах нейронов
Предлагаемый алгоритм построения минимального проверяющего теста имеет ограниченную область применения ввиду того, что получаемый тест проверяет наличие не всех константных неисправностей, а лишь отказов типа логических констант на выходах нейронов. Он может применяться в случаях, если допустимо предположение о безотказности входов нейронов.
Рассмотрим пространство входов нейронной сети - единичный гиперкуб, который разбит на отсеки гиперплоскостями реализуемыми нейронами первого слоя. Пусть во всех отсеках кроме одного находится по одной вершине гиперкуба, а в выделенном отсеке п вершин. Пусть номер отсека есть а^.=1
Предположим, что отказ некоторого нейрона вызывает изменение некоторого значения a(1l, а поскольку рассматриваются только отказы типа логических констант на выходе нейрона, то изменится номер отсека для всех п вершин, лежащих в нем. Отсюда следует, что данный отказ оказывается
Hi +Я2+ •'' +Яуу W
индицируемым сразу на п входных значениях. Поскольку при построении теста необходимо, чтобы один отказ индицировался не более чем на одном входном значении, то процедура минимизации полного теста (тест, состоящий из 2" входных значений) будет состоять в поиске отсеков, в которых находится более одной вершины, и выбрасывании любых лишних вершин из данного отсека, чтобы там оставалось лишь одна.
Поскольку вершины гиперкуба являются одновременно и вершинами графа состояний, то процесс минимизации полного теста, описанный выше, аналогичен процессу минимизации полного графа состояний. Поясним это на примере нейронной сети, показанной на рис. 16.1 и графа состояний на рис. 16.2. Тот факт, что несколько вершин гиперкуба лежат в одном отсеке, в графе состояний соответствует тому, что все пути с этими вершинами имеют общие ветви начиная с первого уровня. Начнем выбрасывать такие вершины, в нашем примере их пять:
{ООО, 011, 101, 110, 111}. (16.18)
Из совокупности (16.18) оставляем одну вершину, например, ООО. Тогда граф состояний принимает вид, показанный на рис. 16.7. Вершины этого минимизированного графа состояний и являются входными значениями минимизированного теста
{ООО, 001, 010, 100}. (16.19)
Докажем, что полученный тест минимальный на заданном выше множестве отказов.
Утверждение 5. Для отказов типа логических констант на выходе нейрона число вершин минимизированного графа состояний сети равно длине минимального теста, выявляющего все отказы заданного класса.
Покажем справедливость этого утверждения. Тот факт, что число вершин определяет длину соответствующего теста, следует из определения графа состояний. Докажем теперь, что в случае минимизированного графа соответствующий тест будет минимальным для заданного класса отказов.
Минимизация графа состояний заключалась в последовательном переборе непустых отсеков, образуемых нейронами первого слоя и выбрасывании вторых, третьих и т. д. вершин гиперкуба входного пространства, попавших в один отсек. В результате
000001 010 100
1 о
Рис. 16.7. Минимизированный граф состояний
000001 010 100 проведения такой процедуры получа
минимизированный граф состояний, кот
рый соответствует случаю, когда в ка::
дом непустом отсеке будет находиться
/ одному значению аргумента.
00 10 11 „ J J \ Предположим, что полученный тест
минимальный. Выбросим любую из ве шин полученной совокупности. В этом cj чае появляется новый пустой отсек, и зн чение логической функции на этом отс ке становится неопределенным. Это о начает, что при тестировании нейронн сети с помощью уменьшенного теста не может появиться ои бочный путь, соответствующий выброшенной вершине, a bbj-ду однозначного соответствия любого пути в минимизирова ном графе некоторой группе отказов получается, что эта гр~ па отказов становится неиндицируемой на данном тесте (а противоречит определению теста, т.е. выявляемости всех отка зов заданного класса). Поскольку была выброшена произволь ная вершина, то отсюда следует, что тест, соответствующ минимизированному графу состояний, минимальный. Утверждение доказано.
