Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 86
Текст из файла (страница 86)
5.63): 5 (хэ! х2! ...! хе) = Р(!рэ(хэ! хт! х3)! уэт(хэ! хт! хз) ! !РЗ(ХЗ! Х4, Хб! Хе), !Р4(ХЗ! Х4! Хб! Хб)! Х4), 15,9. Сино!ее функиионольноб декомногичии т. е. получили декомпозицию исходной функции от шести переменных в виде системы одной функции от пяти переменных, двух функций от четырех переменных и двух функций от трех переменных Внешняя функция Р не удовлетворяет введенным ограни- р чеииям и ее необходимо декомпозировать дальше. Такой результат получен при последовательном способе поиска декомпозиции. Более оптимальное решение получим при параллельном способе поиска. Для этого расширение пространства Р(рэ, !р2) до пространства Р(!рэ, (рт,хб) спроектируем на расширение пространства Р(хэ, хт, хз) до пространства Р(хг, хз, хз, хв) (рис.
5.64). Граф Кенига КЩ (рис. 5.64) определяет таблицу Вейча (табл. 5.50) 482 Таблица 5.50 Таблица 5.53 Таблица 5.51 Таблица 5.52 Гл.5. Прикааднаа теорие ааеоритмов 25.10. Семантическое ороеатаирование нейронных сетей 483 с учетом расширения пространств Р(Х,), Р(ХВ), при котором га- рантируется размерность функций, декомпозирующих исходную функцию, равная 4; результат сжатия таблицы Вейча по столбцам приведен в табл. 5.51, по строкам — в табл. 5.52 и на рис. 5.65. Ф! 'РЗ О О-(ОГ21 а О 1 — (1", 5', 5~! = Ь 1 О-[2, 31=с 1 1 — (4. 61 а' Окончательно получаем оптимальную повторную декомпозицию ((х1, х21 ..., хе) в виде 2 (х1) хт~ ..., ХВ) = Р(!р1(х1, х2~ хз), ~РЗ(х1, х2, хз~ х4)) !РЗ(Х4) ХВ) ХВ) ~ ~Р4(ХЗ~ Х4) ХВ~ ХВ)) (табл.
5.53), т. е. в виде суперпознции системы трех функций от четырех переменных и двух функций от трех переменных. 8 5.10. Семантическое проектирование нейронных сетей В современных нейротехнологиях можно выделить два класса технологий: ао(1-нейротехнологии и (!аг!(-нейротехнологии.
В технологиях первого класса основной проблемой является разработка 484 Рис. 5.67 Рис. 5.66 )Ч) Л! Л)Х) Рис. 5.69 Гл.5. П иклоднол теорие олеоритмов стратегий обучения и самообучения нейронных сетей, включаюших в себя синтез сценариев обучения. Эти технологии особенно важны при решении неформализованных задач при наличии зашумленной, противоречивой, неполной входной информации.
Такими задачами являются задачи распознавания, классификации, прогнозирования, краткосрочного предсказания, которыми изобилуют финансовая и оборонная области деятельности человека. В 1)аг)1-технологиях, реализованных в виде нейроБИС, нейроплатакселераторов и работающих, как правило, в субмикронном диапазоне, одной из главных проблем является проблема разложения произвольной булевой функции Дх), хз,..., х„) в декомпозицию функций ат четырех-пяти переменных. Современный уровень технологий в электронной промышленности России и США позволяет выпускать четырехсинацтические нейроны, а в Японии— пятисинаптические нейроны при их цифровой реализации.
Рассмотрим проектирование четырехсинаптической нейронной сети на однородных нейронах гексагональной структуры, реализующей булеву функцию 7(х), хз, ..., хе) (табл. 5.54). Таблица 5.54 ПРедставим исходноб пРостРанство Р(х), хз, ..., хе) в виде декартова произведения пространства размерности 3: Р(х)> хз ...,хе) = Р (хм хз> хз) >> Й(х4 хв> хв) и зададим исходную функцию в виде графа Кенига К(у) (рис. 5.66). Столбцевой граф противоречивости Г „„р(Х1) имеет вид рис.
5.67. Граф С, „р(Х1) содержит квазиполный подграф Я(4, 0): б~ тир(Х5) Э Я(4> 0), Я(4> 0) = ((1> 2, 4, 7), АР). Следовательно, его хроматическое числа равно 4 и минимальная раскраска имеет вид а = (1), Ь = (4, 5), с = (3, 7), 4 = (О, 2, 6). 15.10. Семантическое и оектировоние неаронные сетеа 485 Кодируя краски двумя символами 711, )17: а — 00, Ь вЂ” 01, с — 10, )) — 11, получаем внутренние функции )11, )17 вида )71 (хе, хб, хе) ~ = У(0, 2, 3, 6, 7), !1 717(хе> хб, хе) = У(0, 2, 4, 5, 6).
)1 После соответствующего раскраске склеивания столбцов получаем граф Кенига нида К(х), хз,хз,)11,)17) (рис. 5.68). Строчный граф а 1 3 5 4 5 б 7 л)л)хв а 1 т 3 4 5 б 7 х)л)х) противоречивости С„р — (Р(Х,)> 1>ир) и его минимальная раскраска представлены йа рис.
5.69, а. Краски а, Ь, с, )1, е окрашивают вершины следующим образом: а = (0), Ь = (1, 7), с = (2, 3), >Е = (4, 6), е = (5). Раскраска минимальная, так как С„р(Х,) содержит квазиполный граф Щ5, 0) = ((О, 1, 3, 4, 5), )>р). 486 Гл.5. П икладнал теорие алгоритмое 55.10. Семантическое н оектироеание нейронных сетей 487 Хроматическое число, равное 5, редуцируем до 4, устраняя зацрешенную фигуру фб, О) сужением сигнатуры с помощъю уда- 5 з„, пения ребра (3, 51.
Векторы 3 и 5 пространства Р(х1, хз, хз) находятся в отношении противоречивости 13, 5) Е Ц,р, обусловленном вектором 3 пространства Р(гд, яз). Удаление ребра 13, 5) в х~ хгхг графе Оар(Х,) обеспечивается штриховкой вектора 3 в пространстве Р(171, 02). Векторы 3 и 5 отличаются друг от друга переменными х1 и х2.
Для определенности выбираем х1, тогда вектор 3 в пространстве Р(р~, 02) после штриховки имеет вид 3' = 3 х1, Зн = 3 ° х1, при этом 3' соответствует вектору 3 <+ х1хзхз, Зн — вектору 5 +~ х1хзхз (рис, 5.70). В результате сужения сигнатуры граф схлр(Х,) красится в четыре краски (см. Рис. 5.69, б): ахх 101, 6=11,7), с=(3,5), Иск(2,4,6). Кодируем краски, вводя символы ~р1~р2.
а — 00, 6 — 01, с — 10, Н вЂ” 11. После склеивания соцветных вершин получаем граф Кенига К(Р) (рис. 5.71), определяющий внешнюю ч~чгх~ функцию Р(ф1~ ~рз) 711~ пэ~ х1). Полученная внешняя функция Р('Р1 %2 тЛ 02 х1) зависит от пяти переменных, следовательно, необходимо далее либо декомпозировать ее, либо редуцировать хроматическое число столбцевого графа противореРис. 5.71 чивости Оар(Х5) (рис. 5.67) до 2. При этом запрещенными фигурами являются циклы нечетной длины.
Построим семантическую таблицу (табл. 5.55), каждой строке которой взаимно однозначно соответствует запрещенная фигура, столбцу — ребро, и в клетке (г, у) находится 1, если у-е ребро входит в 4-ю запрещенную фигуру. Покрытие строк столбцами определяет искомое сужение сигнатУРы гРафа Сар(Х5). Минимальное покРытие обРазУют столбцы 11, 4) 11, 7), 14, 7). В результате удаления соответствующих ребер граф Я„р(Х5) преобразуется в бихроматический (рис. 5.72): асх(0,2,5,61, 6=11,3,4,7).
Для определения переменных, которыми расширяется сопряженное пространство, рассматриваем вторую часть семантической таблицы (табл. 5.56; первой частью является табл. 5.55) Таблнла 5.55 Рнс. 5.72 Покрывая столбцы строками в табл. 5.56, определяем переменные, расширяющие пространство Р(Х,); покрытиями являются 1хе, х51, (хе, хе), (хб, хб) Размерность пространства Р(Х,) увеличивается на 2. Более оптимальным будет покрытие табл. 5.55, имеющее вид 112, 41, 10, 4), 11, 7Я. Действительно, мощность минималъного покрытия 1хе) табл. 5.57, аналогичной табл.
5.56, равна 1. Сужение сигнатуры графа сх„р(Х5) (см. рис. 5.68), соотТаблыла 5.55 488 Таблица $.$9 Рис. $.7$ в (о, 2, 4, 5, б) ь 11, 3, 7] Рис. $.7$ Гл.б. П иклодиол тео иа алгоритмов ветствуюшее покрытию гг = (12> 4), (О, 4Ц1, 7) ), обеспечивает редуцирование его хроматического числа Ь(1>)пр(Хь)) до 2 (рис. 5.73). Ь Таблица 5.$7 Рпк. 5.73 В результате штриховки векторов О, 3 пространства Р(х1, хт>хз) о 1 2 4 7 (Рис.
5.74) РаскРаска гРафа дпр(Хь) х>ххха и>веет ви)1 а = (1, 3, 7), Ь = (О, 2, 4, 5, 6). Кодируя краски: а — 1, Ь вЂ” О, о' ох, о" оу,з' Зх, 3' 314 получаем внутреннюю функцию вида Рис. 5.74 г)(х4, хб, хв)! = У(1 3 7). >1 Для построения внутренних функций в подпространстве Р(Х,) склеиваем соцветные вершины графа дпр(Хь); в резулътате получаем граф Кенига (рис.
5.75). г Х>Х2»3 Х> Оха О Оу 3' Зх>3 Зу 1 2 " 4 5 б 7 4 Строчный граф противоречивости схпр(Ха>), Х,' = Х, ).) гзХь, Х = (хм хз, хз), сьХь = (хв) (рис. 5.76), содержит квазиполный полграф максималъной квазиплотности, равной 4: бпр(Ха) Э Я(4> 0)> >>е>( 4> 0) = ((О > 0 > 2 > 5 )> Упр). Следовательно, Ь(схпр(Ха>)) = 4, поэтому достаточно введения двух внутренних функций, гр1 (х1, х2, хз, хв) и >р2(хь> хт, хз, хе): 15.10.
Семоитическое проектироваиие иейроииагх сетей 489 11о82Ь(схпр(Х>))) = 2. Кодируем краски а, Ь, с, гг (табл. 5.58) и получаем 11 на 0',3',3",5-,7 —, р(~1> хз> хз> Х4) ~( О на О>> 1 2 4 ( 1 на 2 —, 4-, 3', 5-, 6-, >р(Х1> ХЗ, хз> хе) = (О на О, О» 1 3» 7 » » Согласно проведенной раскраске схпр(Х>) (см. рис. 5.76) склеиваем соцветные вершины; в результате получаем табл. 5.59, определяю- Т а блиц а $.$3 щую внешнюю функцию Р оптимальной повторной декомпозиции исходной функции /(х1, хз, ..., хв): У(х1, хз, .
° ° хв) = = Р(>р1(х1> х2> хз> Х4)» р2(х1> х2> хз> х4)> г)(х4> хб> хв)) > (х1> ХЗ, хз> х4) г > (х,ь, хб> хб) = (х4). Внешняя функция Р(>р1, >рт, г)) имеет вид Р(>р1, >рт, г)) ~ = ьг(1, 2, 4, 5). В результате исходная булеза функция от шести переменных представлена в виде повторной декомпозиции двух функций (у1 и >рз) от четырех переменных и двух функций (Р и 1)) от трех переменных. Вторым способом штриховки является способ, основанный на введении специальных переменных штриховки (х;). Выше были найдены два покрытия а1 и ггз (см.
табл. 5.55): Х1 = ((1,4), (1,7), (4,7)), гг2 = ((2,4), (0,4), (1,7)). 490 Таблица 5.б1 т 4 а б Рис. 5.77 хз хз Х5 Хе Таблица 5.50 Рис. 5.78 Гл.5. Прокладках теорие алгоритмов Для определения размерности вектора штриховки строим граф зацепления С, „= (У, б„,ц, Х)), являющийся подграфом соот- 1 о ветствующего графа противоречивости. Для покрытия кь граф за- цепления (рис. 5.77, а) имеет вид а. =(У,((7.,Х)), У = 11, 4, 7), (узел — — (11, 4), (1, 7), 141 7)), для покрытия кз — вид (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
