Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

§ 4.6. Замена одной идеальной диаграммы двухранговой сетью ненадежных вероятностных диаграмм

Не представляет затруднений подобного типа таблицу построить для любого конечного числа переменных n и решать задачу совершенно формально при помощи таблицы "вручную", либо при помощи ЭЦВМ.

Рассмотрение вопроса о возможности построения надежной сети из ненадежных вероятностных диаграмм начнем с двухранговой сети двух переменных.

Рис. 4.36
Рис. 4.36

Полный перебор всех возможных вариантов (в данном случае он невелик) построения сети, каждая диаграмма которой имеет хотя бы по одной ячейке, содержащей букву р, показывает, что надежный результат может быть получен только для двух случаев - при вычислении тавтологии или противоречия. Действительно, рассматривая, например, сеть рис. 4.36, легко убедиться, что, как бы ни переставлять букву р в диаграммах первого и второго рангов, все равно нельзя получить требуемой эквивалентности вычисляемой и заданной функции ([Φ] ≠ Φ): по крайней мере в одной из ячеек результата будет появляться буква р, что недопустимо.

Рис. 4.37
Рис. 4.37

Другое дело, если имеет место один из двух случаев, показанных на рис. 4.37. В первом из них оператор (р, 1, 1, 1) предписывает за- писать в результате единицы как в тех ячейках, где они есть в обеих диаграммах первого ранга, так и в тех, где они есть только в одной из них. Поэтому в результате [Φ] единицы есть во всех ячейках, т. е. без ошибки вычисляется тавтология.

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

Рассмотрим теперь построение по заданной идеальной диаграмме Dρ̄12, а3) двухранговой сети ненадежных вероятностных диаграмм.

Предварительно заметим, что для максимально допустимого числа ячеек ψr,i в которые может быть поставлена буква р без ухудшения требуемого результата, в работе [39] найдены выражения


где I = 2n mod n (т. е. I - остаток от деления 2n на n). Нетрудно убедиться в том, что в одних диаграммах первого ранга число Ψ1,i может быть увеличено за счет уменьшения его для других, однако из технических соображений желательно иметь Ψ1,i примерно одинаковыми для всех диаграмм сети, что позволит предъявить менее жесткие требования к массовому производству технических нейронов, Из (4.26) следует, что для всех n Ψ2,11,i. Это соотношение имеет некоторый смысл: получается, что ненадежность выходного нейрона допускается более высокой, нежели ненадежность нейрона первого ранга.

Правила построения надежной сети из ненадежных вероятностных диаграмм рассмотрим на простейшем примере, когда заданная логическая функция преобразована к СДНФ а1 а̄2 а3 ∨ а1 а2 а3 в виде диаграммы Dρ = (0, 0, 1, 0, 0, 1,0, 0).

Рис. 4.38
Рис. 4.38

1. Перенести из Dρ̄ в соответствующие ячейки более половины диаграмм первого ранга (в данном случае - не менее двух) все единицы (рис. 4.38).

2. Построить отрицания диаграмм Dρ1,i, обозначаемые через Dρ1,i по правилу: в ячейках, одинаковых по номерам с теми, в которых у Dρ1,i стоят единицы, поставить нули и во всех остальных ячейках поставить единицы.

3. В диаграммах первого ранга разместить буквы р по числу не более чем Ψ1,i = 1/2 (2n-I) (n - 1) n-1 = 2; размещение произвести так, чтобы номера ячеек, в которых размещаются буквы для разных i, не пересекались. Из рис. 4.38 видно, что такое размещение может быть произведено в различных вариантах. Для случая n ≥ 4 это обстоятельство целесообразно учесть при составлении машинного алгоритма. Остальные ячейки диаграмм заполнить нулями.

4. Составить 2n логических произведений, по результатам которых заполнить ячейки оператора Dρ2,1, придерживаясь следующих правил:

а) если логическое произведение для каждой из одинаково пронумерованных ячеек совпадает с Dρ̄, то в соответствующей по номеру ячейке оператора Dρ2,1 поставить единицу;

б) если логическое произведение тождественно равно нулю, то в соответствующей по номеру ячейке оператора Dρ2,1 поставить букву р;

в) в любом третьем случае (т. е. если логическое произведение не совпадает с Dρ̄ и не равно нулю) в соответствующую по номеру ячей-ку оператора Dρ2,1 поставить нуль.

Эти правила вытекают из тех соображений, что в случае "б" наличие 0 или 1 не изменяет результат и поэтому в ячейку может быть поставлена буква р без искажения результата, а в случае "в" в ячейку необходимо поставить нуль, иначе будет искажена результирующая диаграмма [Dρ̄] = [Φ].

Построим эти произведения для нашего примера в порядке возрастания номеров ячеек оператора:

1)


поэтому в ячейку 0 оператора ставим 0;

2)


поэтому в ячейку 1 оператора ставим 0;

3)


поэтому в ячейку 2 оператора ставим 0;

4)

Dρ1,1&Dρ1,2&Dρ1,3 ≡ 0,

поэтому в ячейку 3 оператора ставим букву р;

5)


поэтому в ячейку 4 оператора ставим 0;

6)

Dρ1,1&Dρ1,2&Dρ1,3 ≡ 0,

поэтому в ячейку 5 оператора ставим букву р;

7)

Dρ1,1&Dρ1,2&Dρ1,3 ≡ 0,

поэтому в ячейку 6 оператора ставим букву р;

8)

Dρ1,1&Dρ1,2&Dρ1,3 ≡ Dρ̄

поэтому в ячейку 7 оператора ставим 1.

На этом построение надежной сети из ненадежных вероятностных диаграмм заканчивается. Для проверки полученного результата по общим правилам работы сетей вероятностных диаграмм (§1,7) строим [Dρ̄] и убеждаемся, что [Dρ̄] = Dρ и соответствующая итоговой диаграмме логическая функция [Φ] также эквивалентна заданной Φ : [Φ] = Φ; это является необходимым и достаточным условием правильного построения сети.

Решение описанной задачи на ЭЦВМ позволило бы строить сети для n = 3 и рассмотреть при этом максимальное число вариантов сетей, удовлетворяющих предъявляемым к ним требованиям. Для синтеза сети вероятностных диаграмм по заданной диаграмме при помощи ЭЦВМ изложенную задачу формализуем в виде таблицы. Решение рассмотренной выше задачи сведено к табл. 4. 4. Таблица имеет (2n + 1) столбцов и (2n + 2n + 1) строк. В последнем столбце помещается вычисленное значение Dρ2,1. В первой строчке записывается заданная диаграмма Dρ̄ в каждой ячейке табличной строки ставится знак (0,1 или р) из соответствующей по номеру ячейки диаграммы Dρ̄. Строчки со 2-й по (n + 1) предназначены для записи Dρ1,i, с (n + 2) по (2n + 1) - для записи и с (2n + 2) по (2n + 2n + 1) - для записи логических произведений, которые в развернутом виде были показаны на стр. 235.

Работа с таблицей сводится к следующему,

1. В первую строку записывается заданная диаграмма Dρ̄.

2. Все единицы и р (если они есть*) из первой строки переносятся в строки с D1,i:

а) в первом цикле расчетов - во все n строк с Dρ1,i,

5) во втором цикле расчетов - в (n - 1) строк и т. д., но не менее чем в > n/2 строк (т. е. в данном примере не менее чем в две строки).

3. В строках с Dρ1,i ячейки, соответствующие п. 2, заполняются нулями, а все оставшиеся после этого свободные ячейки этих строк заполняются единицами.

4. Возвращаясь к строкам с ?)?/, расставляем в часть свободных ячеек буквы р**; расстановка р задается вспомогательной таблицей (табл. 4.5) и повторяется в каждом цикле вычислений в соответствии с заданной машине программой перебора. В табл. 4.5 одинаковыми цифрами показаны ячейки, в которых одновременно размещаются р, а цифра показывает очередность размещения внутри данного цикла вычислений. В заполненную ячейку буква р не ставится.

* (Оговорка относительно р касается построения многоранговой сети, которая будет рассмотрена ниже.)

** (Для ввода в машину буква р кодировалась цифрой 3 в столбцах с 1-го по 2n - 1 и цифрой 4 в последнем столбце.)

Таблица 4.4
Таблица 4.4

Таблица 4.5
Таблица 4.5

Все оставшиеся после размещения букв р ячейки заполняются нулями.

Для каждого варианта размещения р производится реализация алгоритма до конца.

5. В строках с (2n + 2) до (2n + 2n + 1) (для нашего примера строки 8-15) производятся логические умножения; при этом имеется в виду, что р×р×1 = р×р×р = р.

В зависимости от результатов, полученных в каждой строке, в последней ячейке ее, принадлежащей столбцу Dρ2,1, записывается:

а) в случае, если элементы данной строки совпадают с элементами 1-й строки (т. е. с Dρ̄),- единица;

б) в случае, если во всех ячейках данной строки стоят нули,- буква р;

в) во всех остальных случаях - нуль.

6. Если после заполнения таблицы в ячейках последнего столбца (Dρ2,1) окажется хотя бы одна единица,- результат выдается на печать.

Результатом, выдаваемым на печать, является:

а) n строк, содержащих Dρ1,i (в данном примере строки 2, 3 и 4);

б) последний столбец, содержащий Dρ2,1 (в данном примере столбец 9).

Для построения диаграмм первого ранга Dρ1,i номер ячейки каждой из строк (со 2-й по 4-й) принимается за соответствующий номер ячейки искомых диаграмм; для построения диаграммы Dρ2,1 читаем запись в ячейках последнего столбца сверху вниз и принимаем порядковый номер ячейки за соответствующий номер ячейки искомой диаграммы Dρ2,1.

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

8. После полного перебора всех предусмотренных программой вариантов расположения р возвращаемся к п. 26, т. е. к новому циклу расчетов, когда единицы (и р, если они есть) из 1-й строки переносятся теперь уже не в n последующих строк, а в (n - 1) строк; последний цикл расчетов должен закончиться, когда перенос произведен в число строк, составляющих не менее половины величины n.

Таким образом, машинная реализация алгоритма позволяет выдать на печать множество вариантов сетей диаграмм типа Dρr,i, из которых можно выбрать сети, содержащие максимально допустимое число ячеек сри выполняющих заданную логическую формулу Φ = Dρ̄ без ошибок. Проверка всех полученных таким путем сетей показывает, что [Φ] = Φ и сети, таким образом, составлены правильно.

Описанный алгоритм запрограммирован для реализации его на ЭЦВМ УРАЛ-2 для n = 4. Несколько примеров реализации функции Φ = а1234 ∨ a1a2a34 показано на рис. 4.39.

В тех случаях, когда в диаграмме Dρ̄ количество занятых единицами ячеек ≥ 2n-1, может оказаться невозможным обеспечение желательной одинаковости числа ячеек ψr,1 (в диаграммах одного ранга), в которые без искажения результата можно разместить буквы р. При этом требуемый результат может быть достигнут за счет построения выходной вероятностной диаграммы (в двухранговой сети - диаграммы Dρ2,1), количество ячеек которой, содержащих единицы, больше единицы.

Рассмотрим пример изменения изложенных правил, позволяющий построить такую сеть для n = 3.

Пусть задана диаграмма Dρ̄ = (0, 0, 0, 1; 0, 1, 1, 1). Требуется построить двухранговую сеть вероятностных диаграмм Dρr,1, у которой операторная диаграмма Dρr,1 имеет более чем одну ячейку с содержанием единицы. Построение производим при помощи стандартной таблицы по следующим правилам.

Рис. 4.39
Рис. 4.39

Таблица 4.6
Таблица 4.6

1. Записываем исходную диаграмму в первую строку таблицы (табл. 4.6).

2. Во второй строке:

а) сносим единицы из половины (по числу) ячеек первой строки, занятых единицами;

б) вместо остальных единиц первой строки сносим во вторую строку буквы р (в данном примере в ячейках 4 и 6 второй строки помещаем единицы, а в 7 и 8 - буквы р; можно принять и любой другой порядок размещения 1 и р, отвечающий этому правилу).

3. В третьей строке вместо букв р снести единицы и, наоборот, в ячейки, соответствующие тем, в которых во второй строке стоят единицы, в третьей поставить буквы р (в данном случае в ячейках 4 и 6 третьей строки помещаем буквы р, а в ячейках 7 и 8 - единицы).

4. В четвертой строке:

а) сносим все единицы из первой строки;

б) ставим в Ψ1,i любых пока свободных ячеек буквы р (здесь Ψ1,i = 2).

5. Во все оставшиеся свободными ячейки строк 2, 3, 4 ставим нули.

6. Далее действуем в соответствии с п. 5-8 правил, изложенных на стр. 238.

Рис. 4.40
Рис. 4.40

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

Варьируя размещением 1 и р в рамках правил 2 и 4, можно получить некоторое множество вероятностных сетей Dρr,i, каждая из которых выполняет заданную диаграмму Dρ̄. Исходя из каких-либо дополнительных требований или же произвольно, из них можно выбрать один вариант диаграмм Dρr,i, по которому и производить дальнейший синтез надежной нейронной сети.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"