Введение

Взирая на солнце прищурь глаза свои, и ты смело различишь в нем пятна.

Козьма Прутков. Мысли и афоризмы

Создание алгоритма быстрого преобразования Фурье (БПФ) безусловно можно считать одним из выдающихся достижений второй половины XX в. Время его рождения знаменательно совпало с начальным этапом развития вычислительной техники, когда быстродействие вычислительных машин было еще крайне низким. Использование БПФ позволило кардинальным образом уменьшить количество вычислительных операций при выполнении спектральных преобразований, что значительно расширило сферу применения вычислительной техники для спектрального анализа данных. Реализация БПФ в технологии больших интегральных схем [1] привела к существенному уменьшению площади кристаллов для спектральных анализаторов, и соответственно уменьшилось их энергопотребление.

Появление алгоритма БПФ стимулировало интерес и к другим видам спектральных преобразований. В задачах фильтрации, сжатия и выделения информативных признаков широкое применение нашли такие преобразования, как Адамара–Уолша, Хаара, Виленкина–Кристенсона, Хартли, наклонное, вейвлет и другие, также обладающие быстрыми алгоритмами. Несмотря на отличия по видам функций оказалось, что большинство алгоритмов быстрых преобразований имеют подобную структуру и отличаются друг от друга разве что значениями коэффициентов базовых операций. Осознание этого факта привело к идее построения обобщенных спектральных преобразований, наделенных быстрым алгоритмом. В данном классе преобразований появилась возможность варьирования значениями коэффициентов при сохранении условий ортогональности и быстрого алгоритма, поэтому такие преобразования стали называть перестраиваемыми быстрыми спектральными преобразованиями [2].

Первый шаг в этом направлении был сделан достаточно давно. Еще до появления алгоритма БПФ Кули–Тьюки [3] (1965 г.) в исторической работе Гуда [4] (1958 г.) было приведено аналитическое описание быстрых алгоритмов для обобщенных спектральных преобразований. В последующие годы тема обобщенных спектральных преобразований развивалась в работах Г. Эндрюса, К. Каспари, А. И. Солодовникова и других авторов [2], [5]–[7].

Алгоритм БПФ обладает двумя системными ограничениями: во-первых, размерность вектора обрабатываемых данных для всех слоев должна быть одинакова и, во-вторых, значение этой размерности должно быть составным числом, т. е. разлагаться в произведение целых множителей. Первое ограничение обусловлено ортогональностью матрицы БПФ, а второе – регулярностью алгоритма, что, по-видимому, является неизбежной платой за быстродействие.

Теоретическая основа быстрых алгоритмов долгое время базировалась на всевозможных теоремах факторизации, которые доказывали возможность разложения матрицы спектрального преобразования в произведение слабозаполненных матриц, где каждая матрица соответствует одному слою быстрого алгоритма [8], [9]. Это направление породило всплеск работ по теоремам факторизации. На этом пути исследователи столкнулись с тем обстоятельством, что существует множество различных разложений для одного и того же спектрального преобразования. Когда число всевозможных теорем факторизации превысило десятки, стало ясно, что этот путь является тупиковым. Тем не менее, поток теорем не закончился и до сих пор. Проблема была чисто методическая и заключалась в смешивании понятий структуры и топологии быстрого преобразования. Структура является устойчивым системным инвариантом, свойственным всему классу быстрых алгоритмов, а топология – это не более чем допустимая реализация системного инварианта в связях между базовыми операциями. Каждая теорема факторизации соответствует одной из допустимых форм топологической реализации, а их число быстро растет с ростом размерности преобразования. Автором было показано [10], что в основу теории быстрых преобразований следует положить именно системные инварианты. Это устраняет необходимость изобретения новых теорем факторизации и позволяет предложить общий метод построения различных топологических реализаций быстрого преобразования при неизменной структуре. Более того, выделение структурного и топологического уровней дает возможность решать новые задачи, связанные с оценкой параметрической и топологической пластичности перестраиваемых преобразований. Показатели пластичности позволяют оценить разделяющую мощность перестраиваемых преобразований при использовании в задачах классификации образов. Эти вопросы исследовались Эндрюсом [11] в самом начале пути развития обобщенных преобразований, но тогда удовлетворительного решения получено не было, вернее, оно было ошибочным.

Возможность перестройки значений весовых коэффициентов и многослойная структура алгоритма роднят быстрые перестраиваемые преобразования с многослойными нейронными сетями прямого распространения. Иногда используют термин – ортогональные нейронные сети. Условие ортогональности влечет за собой совпадение размерностей входного и выходного векторов для каждого слоя алгоритма. Если отказаться от этого условия, то снимается ограничение и на равенство размерностей, причем, как оказалось, структуру быстрого алгоритма при этом можно сохранить. Предложенная автором парадигма быстрых нейронных сетей [12] (БНС) наследует структурную регулярность алгоритма БПФ, но расширяет ее возможности за счет отказа от ортогональности и жесткой схемы топологической реализации. В рамках данной парадигмы быстрые линейные перестраиваемые преобразования являются частным случаем быстрых нейронных сетей и отличаются от последних линейными функциями активации и нулевыми смещениями в нейронах.

БНС представляют собой вариант многослойных сетей, поэтому для их обучения могут быть использованы градиентные методы типа Error BackPropogation, однако структурные особенности БНС позволяют расширить постановку задачи обучения. Типичной задачей для перестраиваемого преобразования является настройка на заданную систему базисных функций, например базис Фурье, Адамара–Уолша и др. Классические системы базисных функций, как правило, имеют аналитическую форму, поэтому настройка преобразования также выполняется в аналитическом виде. Кроме параметрической настройки для перестраиваемых преобразований развивается также метод топологической настройки. В этом контексте послойная последовательность топологий сети рассматривается как траектория, обусловленная системой базисных функций, а процедура топологической настройки – как средство реализации заданной траектории. Часто достаточным уровнем топологической настройки является выполнение только граничных условий для топологической траектории. В этом случае можно потребовать, чтобы траектория топологий удовлетворяла дополнительным условиям, обеспечивающим наиболее простую форму быстрого алгоритма. Одним из таких требований может быть реализация траектории регулярной порождающей схемой.

Для построения оптимальных фильтров важной задачей является реализация базисов, приспособленных к одной или нескольким системам функций. Предлагаемые в книге алгоритмы настройки имеют заведомо известное число шагов (определяемое количеством слоев нейронной сети) и принципиально не имеют проблем сходимости и устойчивости для процесса обучения. В основе алгоритмов настройки лежит доказанное свойство структурной фрактальности БНС. Предложены методы фрактальной фильтрации и сжатия данных. Фрактальные свойства БНС позволяют реализовать регулярные фрактальные последовательности как многослойные БНС. Фрактальность порождает и особые методы настройки БНС для реализации оптимальных фильтров.

Подобие структуры быстрых преобразований со структурой тензорных произведений векторных пространств позволяет использовать ортогональные перестраиваемые преобразования для построения алгоритмов квантовых вычислений.

Вышеперечисленные вопросы составляют основное содержание настоящего издания. Цель состоит в том, чтобы дать читателю представление о системных особенностях алгоритмов быстрых преобразований, методах проектирования обобщенных перестраиваемых преобразований, способах оценки их характеристик, алгоритмов реализации и областей применения. Книга состоит из двух частей. Первая часть содержит методы структурного и параметрического проектирования быстрых преобразований, а вторая развивает предложенные решения на класс модульных нейронных сетей. Приведенные примеры программ предназначены только для подтверждения корректности математических выкладок и не в коей мере не претендуют на оптимальность реализации алгоритмов.

Автор не удержался от предваряющих эпиграфов, в какой-то мере раскрывающих содержание каждого раздела. Источниками «вдохновения» послужили Козьма Прутков [13] и законы универсальной науки – мерфологии [14].

 Литература к введению

1. Кухарев Г. А., Шмерко В. П., Янушкевич С. Н. Техника параллельной обработки бинарных данных на СБИС: Справ. пособие. Минск: Вышэйш. шк., 1991. 226 с.

2. Солодовников А. И., Спиваковский А. М. Основы теории и методы спектральной обработки информации. Л., 1986. 272 с.

3. Cooley J., Tukey J. An algorithm for the machine calculation of complex Fourier series // Math. Comput. 1965. Vol. 19. P. 297–301.

4. Good I. J. The Interaction Algorithm and Practical Fourier Analysis // J. of Royal Statistical Soseity. Ser.B. 1958. Vol. 20, No 2. P. 361–372.

5. Andrews H. C., Caspari K. L. A General Techniques for Spectral Analysis // IEEE. Tr. Computer. 1970. Vol C-19.-Jan, No 1. P. 16–25.

6. Эндрюс Г. Применение вычислительных машин для обработки изображений / Пер. с англ: Под ред. Б. Ф. Курьянова. М., 1977. 160 с.

7. Лабунец В. Г. Единый подход к алгоритмам быстрых преобразований // Применение ортогональных методов при обработке сигналов и анализе систем: Межвуз. сб. / Уральск. политехн. ин-т. Свердловск, 1980. С. 4–14.

8. Рабинер Л., Гоулд. Теория и примененение цифровой обработки сигналов / Пер. с англ. М.: Мир, 1978. 848 с.

9. Дагман Э. Е., Кухарев Г. А. Быстрые дискретные ортогональные преобразования. Новосибирск: Наука, 1983. 228 с.

10. Дорогов А. Ю. Системные инварианты быстрых преобразований // Тр. IV межрегиональной школы-семинара «Распределенные и кластерные вычисления», Красноярск, 14–16 сент. 2004.

11. Andrews H. C., Caspari K. L. Degrees of Freedom and Modular Structure in Matrix Multiplication // IEEE. Tp. Computer 1971. Vol. C-20, No – Feb. P.113–141.

12. Дорогов А. Ю. Быстрые нейронные сети. СПб.: Изд-во С.-Петерб. ун-та, 2002. 80 с.

13. Прутков К. Сочинения. М.: Худож. лит., 1976. 381 с.

14. Азбука Мерфи / Пер. с англ. и сост. С. В. Махотина; Худ. А. В. Каменчуков. Минск: ООО «Попурри», 2004. 448 с.