УДК 681.322:517.444 Опубликована в журнале «Нейрокомпьютер» №1 1999г. СТРУКТУРНЫЙ СИНТЕЗ БЫСТРЫХ НЕЙРОННЫХ СЕТЕЙ А.Ю.Дорогов Государственный электротехнический университет «ЛЭТИ». г.Санкт-Петербург Аннотация В данной статье разделе рассматривается процедура синтеза нейронных сетей, которые структурно подобны алгоритмам быстрого преобразования Фурье (БПФ). Синтез реализован как многошаговый процесс порождения нейронных слоев. Приведены примеры и количественные оценки структурных моделей. STRUCTURAL SYNTHESIS OF FAST NEURAL NETWORKS A.Ju.Dorogov The summary It is considered the procedure of neural networks synthesis with structure is similar to algorithms of fast Fourier transformation (FFT). The synthesis is realized as multistage process of neural nets creating. The examples and quantitative evaluations of structural models are indicated. Хорошо известно, какую огромную роль в обработке сигналов сыграло открытие алгоритма быстрого преобразования Фурье (БПФ). Алгоритм БПФ позволил кардинальным образом уменьшить количество вычислительных операций при выполнении спектральных преобразований, что значительно расширило сферу использования спектрального анализа при обработке данных. Реализация БПФ в технологии больших интегральных схем привела к существенному уменьшению площади кристалла для спектральных анализаторов, и соответственно уменьшилось их энергопотребление. Для нейронных сетей задача сокращения числа вычислительных операций не менее актуальна. При больших размерностях обрабатываемых данных нейронные сети с многослойной структурой требуют значительного объема вычислительных операций для реализации алгоритма нейрообработки. Это ограничивает применение подобных сетей в системах реального времени. Алгоритмы БПФ имеют выраженную многослойную структуру подобную структуре многослойных персептронов, поэтому напрашивается естественное решение – использовать идеологию БПФ для построения нейронных сетей []. Для этого достаточно в операциях «бабочка» БПФ заменить коэффициенты преобразования перестраиваемыми синаптическими весами и добавить нелинейные функции активации. Следует отметить, что первый шаг в этом направлении был сделан достаточно давно. Еще в исторической работе Гуда [] было приведено аналитическое описание быстрых алгоритмов для обобщенных спектральных преобразований. Обобщенное спектральное преобразование с позиций сегодняшнего дня можно рассматривать как нейронную сеть с линейными функциями активации. В последующие годы тема обобщенных спектральных преобразований развивалась в работах Эндрюса , Солодовникова, Лабунца и других авторов [,,,]. Алгоритмы БПФ и родственные им обобщенные спектральные преобразования имеют регулярную структуру. Регулярность порождает два ограничения: во-первых, размерность вектора обрабатываемых данных для всех слоев должна быть одинакова и, во-вторых, значение этой размерности должно быть составным числом, т.е. разлагаться в произведение целых множителей. Для нейронных сетей наиболее существенно первое ограничение, поскольку совпадение размерностей векторов по всем слоям достаточно редкий случай в практике нейронных сетей. Второе ограничение также уменьшает число допустимых вариантов выбора нейронных сетей, но, по-видимому, это неизбежная плата за быстродействие и регулярность. В данной работе будет рассмотрено построение нейронных сетей с регулярной структурой, которые наследуют высокую вычислительную эффективность алгоритмов БПФ, но допускают реализацию нейронных слоев сети с различной размерностью. 1.Структурный анализ алгоритмов БПФ. Набор алгоритмов, называемых алгоритмами быстрого преобразования Фурье вошел в практику спектрального анализа в 60-х годах начиная с работ Кули-Тьюки []. Указанная публикация появилась как раз в нужный момент и послужила катализатором применения метода спектрального анализа для цифровой обработки сигналов. Работа Гуда [2] была опубликована на несколько лет раньше, но как это часто бывает прошла почти незамеченной. В методологии Кули-Тьюки явно была выражена мысль, что БПФ надо рассматривать не как одиночный алгоритм, а как последовательность алгоритмов нарастающей сложности с убывающим вычислительными затратами. По воле разработчика может быть выбран любой алгоритм из этой последовательности. Особенно важен этот вывод для нейронных сетей, при использовании которых часто требуется найти компромиссное решение между быстродействием и способностью нейронной сети к обучению. Существует множество стратегий в построении последовательности алгоритмов БПФ, как правило, они основаны на способе разбиения входного вектора на подвекторы. Следуя работе [] рассмотрим в качестве примера стратегию синтеза последовательности алгоритмов БПФ «с прореживанием по частоте». Для вектора прямое дискретное преобразование Фурье (ДПФ) определяется выражением: , где - номер гармоники. Величину обычно называю поворачивающим множителем. Число комплексных операций умножения при выполнении ДПФ в общем случае равно . Для алгоритмов БПФ, как правило, выбирают значение , где - целое число. В стратегии с прореживанием по частоте вектор разбивается на два подвектора по правилу:
Этот прием позволяет свести вычисление - точечного преобразования к вычислению двух - точечных преобразований, при этом число комплексных операций умножения будет значительно меньше . Математические детали этой идеи подробно представлены в главе 6 работы [8]. На рис.1 в графической форме показан пример перехода от восмиточечного ДПФ к двум четырехточечным ДПФ при прореживании по частоте. На рис.2 приведена базовая операция «бабочка» для алгоритма БПФ с прореживанием по частоте. В общем случае базовая операция определяется матрицей размерности : . (Здесь и далее считается, что нумерация строк и столбцов в матрицах начинается с нулевого индекса). Для базовой операции «бабочка» значение равно двум, а для четырех точечного преобразования ДПФ . Если сопоставить каждой базовой операции вершину графа (как показано на рис. 2), а дугам - операторы связи между базовыми операциями, то получим иное структурное представление алгоритма БПФ, которое будем называть структурной моделью алгоритма. На рис.3 представлена структурная модель для алгоритма, показанного на рис.1. На графе структурной модели приведены также размеры матриц базовых операций и ранги операторов связи (для алгоритмов БПФ ранги связей всегда равны единице). Нетрудно подсчитать число вычислительных операций умножения (это число обозначается далее через ) для структурной модели, показанной на рис. 3. для этого достаточно просуммировать число умножения по всем базовым операциям: . Заметим для сравнения, что прямое восмиточечное ДПФ требует операции умножения. Каждое дискретное преобразование размерности в свою очередь может быть сведено к двум точечным преобразованиям. На рис.4 показан полный граф восмиточечного БПФ с прореживанием по частоте, а на рис.5 приведена соответствующая структурная модель. В общем случае размерность преобразования может быть составным числом: , где - целые числа (не обязательно простые). В этом случае структурная модель состоит из слоев с размерностью базовых операций в слое и числом вершин в слое . В частности для входного слоя для входного и выходного слоя число вершин определятся произведениями: , . . Обозначим через номер вершины во входном слое, а через - номер вершины в выходном слое и представим эти числа в позиционной многоосновной системе счисления []: , . где - разрядные числа. Для скрытых слоев число вершин и их нумерация будет определяться следующими выражениями: , . Структура межслойных связей может быть описана ранговыми матрицами. Элемент ранговой матрицы равен значению ранга проектирующего оператора, связывающего базовые операции смежных слоев. Например, для структурной модели показанной на рис.5 ранговые матрицы будут иметь вид: , . Обозначим через окрестность вершины , т.е. подмножество вершин непосредственно связанных с вершиной . Это подмножество целиком принадлежит слою . Номер вершины в слое определяется выражением: , а число ненулевых элементов в каждой строке ранговой матрицы равно . Разрядное число можно рассматривать как селектор вершин в окрестности , для выбранной стратегии справедливо следующее правило формирования окрестности: . Например, для структурной модели показанной на рис.5, окрестности вершин могут быть представлены в следующем виде: , . Матрицы обычно называют матрицами смежности [] или таблицами связей. Каждая строка матрицы смежности содержит окрестность соответствующей вершины. Из приведенного выше анализа можно сделать следующие выводы: Размерность быстрого преобразования является составным числом. Базовые операции определяются квадратными матрицами, которые в пределах слоя имеют одинаковый порядок. Ранги связей между базовыми операциями равны единице. Структурная модель алгоритма БПФ не содержит параллельных путей и является слабосвязанной сетью []. Перечисленные условия можно положить в основу проектирования быстрых нейронных сетей (БНС). 2.Алгоритм структурного синтеза БНС. В контексте нейронных сетей базовой операции отвечает группа нейронов которую будем называть нейронным ядром. Процесс построения последовательности алгоритмов БПФ можно представить как пошаговую процедуру деления нейронных ядер, а процедуру синтеза как генетическую программу порождения нейронной сети. Дополнительные ограничения, обусловленные регулярностью, позволяют получить удобную аналитическую форму для алгоритма структурного синтеза. В процедуре синтеза возможна реализация нескольких стратегий, выше уже была рассмотрена стратегия «с прореживанием по частоте». Рассмотрим этот вариант в применении к нейронным сетям. Пусть размерность входного рецепторного поля нейронной сети и размерность выходного аксонового поля. Будем полагать, что сомножители упорядочены, так что с возрастанием индекса монотонно возрастает значение множителей. Определим совокупность чисел рекуррентными соотношениями: и , положив начальные значения равными и . Слои нейронной сети будем нумеровать, начиная с индекса 0. Первый шаг. На первом шаге синтеза родительское ядро размерности разлагается в двухдольную структуру, содержащую ядер в рецепторной области и ядер в аксоновой области. В соответствии с принятой стратегией необходимо выбрать , поэтому примем и . При ранге связей равном единице число нейронов в порожденном слое будет равно: . Ядра рецепторной области будут иметь одинаковые размерности , где - число рецепторов, - число нейронов. Аналогично ядра аксоновой области будут иметь характеристики , где , . Ранговая матрицу, в порожденной двухдольной структуре обозначим символом, . Эта матрица будет иметь размерность . Символ “~“ в обозначении подчеркивает, что матрица будет подвержена модификации на следующем шаге. (Заметим, что алгоритм синтеза может быть остановлен и на первом шаге). В результате выполнения первого шага образуется два слоя, которые обозначим индексами 0 и 1. В слое 0 содержаться ядра рецепторной области, имеющие минимальные размеры, поэтому этот слой на следующих шагах алгоритма разлагаться не будет. Обозначим размерности ядер нулевого слоя через . Сформированный слой 0 будем называть ведомым слоем. На втором шаге разложению в двухдольную структуру будет подвержен слой 1, который назовем ведущим слоем. Второй шаг. На втором шаге разложению будет подвергаться каждое ядро 1-го (ведущего) слоя. Все ядра ведущего слоя имеют одинаковые структурные характеристики . Пусть при разложении ядра в двухдольную структуру образуется ядер в рецепторной области и ядер в аксоновой области. При выбранной стратегии необходимо выполнить условие , поэтому примем: и . Число нейронов в порожденном слое будет равно: . Ядра рецепторной области будут иметь характеристики: - число рецепторов, - число нейронов. Аналогично ядра аксоновой области будут иметь характеристики: , . Ядра рецепторной области находятся в слое 1 и имеют минимальные размеры, поэтому этот слой на следующих шагах алгоритма разлагаться не будет. Обозначим характеристики ядра 1-го слоя через . Слой с индексом 2 будет содержать ядра с характеристиками , и будет подвергаться разложению на следующем шаге. Матрица (построенная на первом шаге) после второго шага подвергается модификации, поскольку происходит увеличение числа вершин в слое 1 в раз. Правило модификации матрицы определяется принятой стратегией синтеза. Для аналитического представления алгоритма модификации удобно использовать таблицы связей. Таблица связей, отвечающая матрице , будет иметь вид: . Строка в таблице соответствует строке ранговой матрицы, и определяет окрестность вершины слоя 0. Обозначим через номер строки в таблице, а через - номер столбца. Представим число в позиционной многоосновной системе счисления с основаниями . Нетрудно заметить, что в аналитической форме элементы таблицы можно задать выражением: . При выполнении шага 2 каждое родительское ядро в слое с индексом 1 порождает ядер-потомков. Пронумеруем порожденные ядра последовательно в пределах слоя. Используя многоосновную позиционную систему счисления, номер порожденного ядра можно записать в виде: . Для растущей нейронной сети стратегию синтеза удобно интерпретировать, как правило, определяющее наследование связей. На каждом порождающем шаге вершины потомки наследуют и разделяют связи своих родителей. Правило наследования в общем случае определяется тремя условиями: приоритетом вершин окрестности наследования; приоритетом вершин потомков; процедурой наследования. Например, может быть предложено следующее соглашение о наследовании (назовем его «право младшего»): В окрестности наследования наивысшим приоритетом обладают вершины младших номеров. Среди вершин потомков наивысшим приоритетом обладают вершины младших номеров. В процедуре наследования инициатива при распределении связей принадлежит вершинам потомков, которые последовательно в порядке убывания собственного приоритета наследуют связи с наиболее приоритетными вершинами окрестности наследования. Можно показать, что «право младшего» соответствует стратегии «с прореживанием по частоте» для БПФ. Если алгоритм модификации выбрать, следуя принципу «право младшего» в наследовании связей, то придем к следующему выражению: . Число определяет номер ядра в слое 1 в позиционной системе счисления с набором оснований . Реализация второго шага алгоритма создает слой 2. Ядра слоя 2 порождаются родительскими ядрами слоя 1, число которых равно . Каждое родительское ядро создает ядер-потомков, поэтому общее число ядер в порожденном слое будет равно произведению . Следуя принципу «право младшего» элементы таблицы связей между ведущим и ведомым слоем зададим выражением: , где разрядное число принадлежит интервалу . Третий шаг. Слой с индексом 2 становиться ведущим и разлагается в двухдольную структуру. Новый ведомый слой будет состоять из ядер с весами . Число ядер в этом слое будет равно . Ведущий слой будет содержать нейронные ядра с весами и их число будет равно Модификация порождает таблицу с элементами: . По индукции можно доказать что элементы таблиц межслойных связей в общем случае будут определяться выражением: (1) где - номер слоя. В частности для последнего межслойного перехода формула примет вид: . Размерности ядер по слоям и их количество в каждом слое определяются выражениями: , , (2) Число нейронов в слое будет равно: , (3) а номер ядра в поразрядном представлении будет иметь вид: (4) 3.Пример синтеза структурной модели БНС. Рассмотрим процедуру построения регулярной структурной модели для нейронной сети с размерностью входных и выходных данных имеющих следующие числовые значения:
Регулярная сеть будет иметь три слоя. Используя (2) и (3) получим следующие структурные характеристики:
Связи между смежными слоями определяются двумя ранговыми матрицами, таблицы связей, для которых определяются выражением (1) и будут иметь следующий вид: , . В развернутом представлении ранговые матрицы и соответствующие таблицы связей будут иметь вид:
где - представляют собой нумерационные индексы ядер в пределах слоя. На рис.6 показана структурная модель синтезированной БНС. Веса всех дуг в этой структурной модели равны единице. Для данной структурной модели число операций умножения будет равно: . В то время как для полносвязанной сети с тем же количеством нейронов эта величина равна: . В рамках принятой стратегии можно варьировать структуру нейронной сети, изменяя упорядоченность на составных множителях чисел и . 4.Топология нейронной сети. Любая конкретная реализация нейронной сети связана с некоторым «пространственным размещением» нейронных ядер. Систему «пространственных координат» можно задать, определив линейные порядки на множестве рецепторов и множестве аксонов каждого нейронного слоя. Например, для нейронного слоя можно присвоить каждому рецептору порядковый номер , а каждому аксону номер , где соответственно число рецепторов и число нейронов в слое. В свою очередь для каждого нейронного ядра с числом рецепторов и числом нейронов можно ввести локальные порядковые номера и . Топологией нейронного ядра будем называть пару числовых отображений и , определяющих точное однозначное соответствие между глобальными и локальными порядковыми номерами. Данные отображения удобно задавать таблицами следующего вида: . В ядерных нейронных сетях рецепторные поля нейронных ядер не пересекаются, поэтому имеет место: для . (5) Пусть входной вектор для нейронного слоя , а - выходной вектор. На вход каждого нейронного ядра поступает компонента входного вектора, а с выхода снимается компонента . Вектора и выражаются прямыми суммами векторных компонент: , (6) что является следствием условия (5) . Обратную операцию связанную с выделением векторной компоненты из суммы будем рассматривать, как действие частичной подстановки на вектор и записывать в виде: . (7) Комбинации символов можно рассматривать и как символическое обозначение проектирующих операторов, однако, запись в виде формального произведения дает ряд преимуществ при математических выкладках. Рассмотрим теперь два смежных нейронных слоя, полагая, что слой предшествует слою . Выходной вектор слоя проектируется на вход слоя . Формально эту операцию можно записать в виде: , где - некоторая числовая подстановка, соответствующая оператору межслойного перехода. Оператор межслойного перехода индуцирует локальные связи между нейронными ядрами, так, что , где - частичные подстановки соответствующие локальным межъядерным проектирующим операторам. В работе [] изложен алгоритм построения топологии, основанный на свойствах (4), ниже приводится его краткое описание. Пусть ранговая матрица, определяющая связи между нейронными слоями и . Поскольку рецепторные поля нейронных ядер не пересекаются то , и следовательно , где - размерность выходного вектора слоя . Разместим числовое множество на ненулевых элементах ранговой матрицы . (На рис.7. показан пример такого размещения для ранговой матрицы структурной модели рис.1.) Подмножества соответствуют верхним строкам табличных отображений . Подмножества образуются «проектированием» по строкам и столбцам матрицы . В общем случае элементы подмножеств подвергаются еще действию подстановки , детали алгоритма приведены в работе [12]. Рассмотренный алгоритм определяет топологические подмножества для нейронных ядер, но не задает упорядочивание элементов в этих подмножеств. Для того чтобы установить отношение порядка достаточно выбрать некоторое правило развертки матрицы . Примем «естественный порядок» развертки: по строкам – слева направо, по столбцам – сверху вниз. Порядок развертки однозначным образом определяет нижние строки отображений , например, для матрицы показанной на рис.7 при естественном порядке развертки будем иметь: . Различные топологии можно формировать, выбирая то или иное размещение элементов множества в ранговой матрице. Обозначим через числовое значение элемента множества , через номера строк и столбцов в ранговой матрице , а через порядковые номера ненулевых элементов вдоль строк и столбцов ранговой матрицы. Произвольное размещение множества можно задать как функции или , например при монотонно-возрастающем размещении вдоль строк функция размещения будет иметь вид: , (8) а при монотонно-возрастающем размещении вдоль столбцов: . (9) Для входного рецепторного поля нейронной сети и выходного аксонового поля нет необходимости строить двумерное размещение, и топология полей задается произвольными взаимно однозначными функциями: и . В общем случае функции размещения имеют табличное представление и в таком виде должны сохраняться вместе с синаптической картой нейронной сети. Но если размещение множества удается задать в аналитическом виде некоторой формулой то тогда нет необходимости сохранять табличную форму, поскольку топология может быть однозначно восстановлена при выполнении алгоритма нейрообработки. Аналитическое представление имеет подкласс регулярных топологий которые и будут рассмотрены далее. 2.Регулярные топологии. Рассмотрим построение регулярных топологий для скрытых слоев при монотонно-возрастающем размещении вдоль строк множества . Следуя формуле (8) и, используя (4) функцию размещения множества в позиционной системе можно представить в виде: . (10) Будем полагать, что топология рецепторных полей входного слоя и аксоновых полей выходного слоя также определены монотонно-возрастающими функциями размещения: , . Глобальный номер рецептора входного слоя в позиционном представлении можно записать в виде:
Из сравнения с функцией размещения следует . Аналогично глобальный номер аксона выходного слоя представляется в виде и при выбранной функции размещения следует принять , тогда для скрытых слоев глобальный номер аксона будет определяться выражением: . (11) Последняя формула непосредственно следует из выражения (10) при подстановке новых обозначений. Будем полагать, что для любого межслойного перехода подстановка является тождественной. Из (4) следует, что номер ядра слоя будет равен (12) а для слоя . (13) Нетрудно заметить, что набор разрядных чисел в формуле (11) покрывает набор разрядных чисел для номера и включает в себя также разрядное число . Следовательно, по глобальному номеру аксона однозначно определяется номер ядра в слое и локальный номер рецептора для этого ядра. Рассмотрим процедуру построения регулярной топологии на примере трехслойной БНС показанной на рис. 6 Нумерацию ядер и топологии связей для межслойных переходов можно определить, используя выражения (12) и (11).
где соответствие разрядных чисел и оснований системы счисления определяются следующими выражениями: . Результаты представлены в таблицах 1,2. Табл. 1 Табл. 2
Для рецепторов входного слоя и аксонов выходного слоя глобальные номера определяются выражениями: (14) На рис.8 приведена граф-схема алгоритма для данной БНС. При монотонно-возрастающем размещении множества вдоль столбцов ранговой матрицы функция размещения определяется выражением (9) откуда с учетом (13) будем иметь: . (15) Формула (15) включают в себя набор разрядных чисел который покрывает набор разрядных чисел в выражении (12) и содержит также разрядное число определяющее локальный номер аксона предшествующего слоя. Поэтому по номеру координаты входного вектора слоя , однозначно определяется номер ядра предшествующего слоя и локальный номер аксона с которым данная координата непосредственно связана. Для рассматриваемого примера нумерация ядер и топологии связей для межслойных переходов определяется выражениями:
Результаты представлены в таблицах 3,4. Табл. 3 Табл. 4
Как и в предыдущем случае будем полагать, что глобальные номера рецепторов входного слоя и аксонов выходного слоя определяются выражениями (14). На рис.9 приведена граф-схема алгоритма для данного варианта топологии. Рассмотренные примеры соответствуют наиболее простым топологическим реализациям БНС. В общем случае связь между локальными порядковыми номерами и разрядными числами может выражаться через взаимно однозначные функции: . Более того, разрядные числа в выражении (10) , (15) и в формулах производных от него могут быть произвольно переставлены, при этом топология сети останется регулярной. Эти дополнительные возможности могут быть использованы при построении топологий БНС удовлетворяющих специальным требованиям.
