Об оптимизации структурной реализации нейронных сетей

Для построения математических моделей различных процессов удобно применить понятие функциональной системы введенное впервые Кудрявцевым [1]. В рамках понятия функциональной системы можно рассматривать формулы алгебры логики с операцией суперпозиции, конечные автоматы [2] с one-$ рациями суперпозиции или композиции, однородные структуры [3], схемы из функциональных элементов [4] с операцией суперпозиции и т. п. Подобный унифицированный подход позволил обобщить некоторые результаты и технику доказательств для различных функциональных систем. Так, рассмотрение изучаемых объектов как функциональных систем, к примеру, позволило автору провести доказательство леммы 1.1 индукцией по построению, характерной для структурных автоматов и схем из функциональных элементов, а в главе 2 рассмотреть задачу полноты, характерную для функциональных систем в дискретной математике. Применяется техника и возникают структуры типичные в теории автоматов в доказательстве леммы 4.1, а результат аналогичный сформулированному в теоремах 7 и 8 ранее для конечных автоматов был получен в дипломной работе О. Смирновой. Для описания логического устройства электронных схем обычно рассматривались схемы из элементов, реализующих некоторые простые булевские функции. Решалась задача о построении всевозможных функций, используя наименьшее количество элементов. Так в работе Лупанова [5] была получена асимптотика функции Шеннона для реализации в виде формул L{n) ~ и схем L (n) ~ — булевских функций над базисом {&, V, —}. Позднее стала бурно развиваться пороговая логика [6] привлекательная тем, что для реализации булевской функции схемой, пороговых элементов обычно необходимо меньше, чем рассматриваемых ранее булевских элементов. Однако, при таком подходе возникают технические трудности физического изготовления пороговых элементов, поэтому возникла задача, где разные пороговые элементы имеют разную сложность. При изучении схем из пороговых элементов также исследовалось не только количество элементов, но и глубина схемы (время функционирования схемы). В работе [7] подробно изучил сложность схем из пороговых элементов глубины два. Решение аналогичной задачи для изучаемых автором нейронных схем приводится в главе 3. Обзорная работа [6] замечательна еще тем, что в ней доказывается теорема Шлефли, позволяющая подсчитать число n-мерных открытых многогранных конусов, которые получаются в результате разбиения к гиперплоскостями пространства Жп. Несмотря на то, что в данной работе рассматривается аналогичная конструкция, автору пришлось передоказать в главе 3 данную теорему, ввиду n-мерных открытых многогранных конусов от классов эквивалентности. Если нет необходимости учитывать вклад некоторых элементов в исследуемый процесс, или рассматривая физическую реализацию схем, сложностью изготовления некоторых элементов в которой можно пренебречь, следует считать вес этих элементов нулевым. Такой подход к изучению сложности впервые был продемонстрирован в работе А. А. Маркова [8]. Позднее реализация схем над бесконечными базисами имеющие элементы с нулевым весом развиты в работах О.М. Касим-Заде [9]. В настоящей работе вес всех линейных элементов равен нулю. Помимо реализации функций алгебры логики, схемный подход популярен для приближения различных классов непрерывных функций. В 1951 году вышла работа Мак-Ноттона посвященная бесконечнозначной логике (переведена в [10]), в которой рассматривались схемы над базисом из следующих кусочно-линейных функций max (l — х—у, 1), 1 — х, тах (ж, т/), min (cc, у). Было доказано, что схемы реализуют те и только те кусочно-линейные функции определенные на [0,1]п и принимающие значения на отрезке [0,1], которые являются непрерывными и задаются на всех участках линейными функциями с рациональными коэффициентами. В отличие от базисов, рассматриваемых в главе 1, базиса Мак-Ноттона не достаточно для реализации всевозможных кусочно-линейных или кусочно-параллельных функций, тем не менее легко понять, что такими функциями можно приблизить всевозможные непрерывные функции /: [0,1]п —у [0,1]. Позднее С. Б. Гашков в своих работах [11] и [12] подробно рассмотрел несколько кусочно-линейных и полиномиальных базисов, изучая зависимость количества элементов в схеме от точности приближения функций схемами и нашел поведение функции Шеннона при точности приблежения е —> 0. Помимо конечных, были рассмотрены и, похожие на исследуемые в настоящей работе, базисы континуальной мощности, например, {ж + у, х • у} U Ж и {х — у, |ж|, 1} U {сх: 0 < с < 1}.

Идеи, возникающие при изучении различных функциональных систем, можно применить и к бурно развивающейся в последнее время теории нейронных сетей. Настоящая работа посвящена исследованиям так называемых нейронных схем, математического объекта, основанного на понятии искусственной нейронной сети ([13], [14]) модели Мак-Каллока-Питтса [15].

Многие проблемы можно свести к задачам, решаемым с помощью нейронных сетей. Нейронные сети хорошо зарекомендовали себя как средство решения задач сложных для решения статическими методами (без обучения, адаптации). Это задачи классификации, распознавания образов, моделирования ассоциативной памяти и другие. Нейронные сети также применяются для нахождения приближенного решения NP-полных задач за приемлемое время.

По результатам исследований биологов, мозг и нервная система состоят из особых клеток — нейронов, соединенных между собой нервными волокнами. Нервные волокна передают электрические импульсы между этими клетками. Каждый нейрон имеет отростки нервных волокон двух типов: дендриты и аксон. На аксоне может формироваться электрический импульс. Дендриты способны принимать импульсы. Аксон контактирует с дендритами других нейронов через специальные образования — синапсы, которые влияют на силу импульса. Импульсы, поступившие к нейрону одновременно по нескольким дендритам, суммируются. Если суммарный импульс превышает некоторый порог, нейрон переходит в состояние возбуждения и формирует собственный импульс, который передается далее уже по его аксону. Важной особенностью нейро-сетей является то, что чувствительность синапсов может изменяться со временем, а значит, может поменяться поведение соответствующего нейрона, которое, в свою очередь, отражается на функционировании сети в целом — сеть умеет настраиваться, обучаться.

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

На рис. 1 схематически изображена математическая модель нейрона. Где х,. :хп — являются входами нейрона и.

Х1.

X2.

Xl.

Xn.

— h.

Рис. 1. Математическая модель нейрона. соответствуют дендритамw 1,., wn — веса входов, соответствуют чувствительности синапсовh — порог активации нейрона- / — функция активации.

Согласно схеме, действие нейрона заключается в вычислении следующей функции:

Результат вычисления «появляется» на выходе нейрона и передается на входы других аналогичных структур, составляющих искусственную нейронную сеть.

Искусственная нейронная сеть — это набор нейронов, связанных между собой. Часть входов нейронов могут являться внешними входами сети, часть выходов нейронов — выходами сети. Как правило, функции активации нейронов считаются известными и одинаковыми, связи известными, а веса связей настраиваются в процессе обучения. Таким образом, работа обученной нейронной сети заключается в преобразовании входного вектора значений в выходной вектор.

Автором рассмотрены нейронные схемы с точки зрения функциональных систем. Изучены различные функциональные базисы, пригодные для представления искусственных нейронных сетей модели Мак-Каллока-Питтса (с памятью и без) схемами из функциональных элементов. Для моделирования функционирования схемы в дискретном времени, в базис был добавлен автоматный элемент единичной задержки [2]. В этих условиях удалось дать определение процесса обучения и построить каноническую форму обучающейся нейронной схемы.

При решении задач с помощью нейронных сетей, можно условно выделить следующие этапы:

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

— предварительная обработка данных: представление исходных данных в приемлемом для выбранной модели виде, интерпретация выхода нейросети;

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

— выбор модели обучения нейросети;

— обучение нейросети;

— проверка обучения, при необходимости повторные обучения;

— применение построенной нейронной сети для решения задачи.

И на каждом этапе возникают свои сложности. В выборе модели пока ограничимся пространством действительных чисел для входов и выходов,^{-функцией} Хевисайда в качестве функции активации. В идеальном варианте после предварительной обработки исходных данных мы должны получить линейно разделимую задачу, так как это значительно упрощает построение нейросети-классификатора в виде персептрона Ро-зенблатта [14]. Существует алгоритм обучения такой нейросети, сходимость которого математически обоснована ([16],[17]). К сожалению, при решении реальных задач мы, как правило, не можем провести такую предобработку данных, при которой будет достигнута линейная разделимость образцов. Значит, необходимо переходить к более сложной архитектуре, чем персептрон. В непрерывных нейронных сетях (с достаточно гладкой функцией активации) часто используется многослойный персептрон и алгоритм обратного распространение ошибки [18], который, как известно, не применим для дискретных нейронных сетей, в том числе и для сетей модели Мак-Каллока-Питтса.

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

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

К сожалению, заранее не известно, какой сложности (размера) может потребоваться сеть для достаточно точной реализации отображения. Эта сложность может оказаться чрезмерно высокой, что потребует сложной архитектуры сети. Так Минский и Пэперт в своей работе «Персептроны» [19] доказали, что простейшие однослойные нейронные сети способны решать только линейно разделимые задачи. Однако, это ограничение преодолимо при использовании многослойных нейронных сетей. Тек, в сети с одним скрытым слоем вектор, соответствующий входному образцу, преобразуется скрытым слоем в некоторое новое пространство, которое может иметь другую размерность, а затем гиперплоскости, соответствующие нейронам выходного слоя, разделяют его на классы. Таким образом сеть распознает не только характеристики исходных данных, но и «характеристики характеристик», сформированные скрытым слоем.

Задача построения архитектуры нейросети на первый взгляд кажется необозримой. Обычно к этой задаче подходят просто: сущестует несколько десятков различных нейросетевых архитектур, эффективность которых подтверждена практикой и, иногда, математической теорией. Наиболее популярные и изученные архитектуры — это многослойный персептрон, нейронная сеть с общей регрессией, нейронные сети Кохонена [20].

Из соображений оценки сложности архитектуры, автором было проведено исследование быстродействия нейронных схем: нелинейной глубины — параметра, аналогичного количеству слоев в соответствующей нейронной сети, и нелинейной сложности — аналога количества нейронов в сети. Оказалось, что любую нейронную схему можно представить схемой нелинейной глубины не более двух. Подробно были исследованы схемы нелинейной глубины один: приведен канонический вид такой схемы и алгоритм, позволяющий по характеристикам функции определить, представима ли она схемой нелинейной глубины один. Для некоторых классов схем найдена оценка функции Шеннона (минимального количества нелинейных элементов, необходимого для представления произвольной функции нейронной схемой заданного класса).

Далее в работе были оценены функциональные возможности исследуемой модели. Частично решена проблема полноты в пространстве кусочно параллельных функций — функций, представимых схемами над некоторым базисом. Проблема полноты решена для систем, замыкание которых содержит все линейные функции. Другими словами, для дискретных нейронных сетей найдены условия на функцию активации необходимые и достаточные для того, чтобы модель была эквивалентна модели Мак-Каллока-Питтса без памяти, т. е. чтобы функции задаваемые нейронными схемами в нашей модели были представимы в неросетевой модели Мак-Каллока-Питтса и наоборот. Так же рассмотрены функциональные возможности схем, содержащих элемент «умножение». Ранее полученные в данной работе результаты (для схем без умножения) пересмотрены для нейронных схем с умножением.

Автор благодарит своего научного руководителя кандидата физико-математических наук, доцента А. А. Часовских за интересную тему, постановку задачи и постоянное внимание к работе. Спасибо профессору О.М. Касим-Заде за ценные замечания и обсуждения. Автор выражает глубокую благодарность заведующему кафедрой академику, профессору В.Б.

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

1. Кудрявцев В. Б. Функциональные системы. М., Изд-во МГУ, 1982.

2. Кудрявцев В. В., Алешин С. В., Подколзин А. С.

Введение

в теорию автоматов. М.:Наука.Гл.ред.физ.-мат.лит., 1985.

3. Болотов А. А., Кудрявцев В. Б., Подколзин А. С. Основы теории однородных структур. М.: Наука, 1990.

4. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М., МГУ, 1984.

5. Лупанов О. Б. О синтезе некоторых классов управляющих систем. Проблемы кибернетики, вып. 10, М.: Физ-матгиз, 1963, стр. 63−97.

6. Зуев Ю. А. Пороговые функции и пороговые представления булевых функций. Математические вопросы кибернетики, вып. 5, М.: Физметлит, 1994, стр.5−61.

7. Редькин Н. П. О синтезе схем глубины два из пороговых элементов.

8. Марков А. А. Об инверсной сложности систем функций. ДАН СССР, том 116, № 6, 1957.

9. Касим-Заде О. М. Общая верхняя оценка сложности схем в произвольном бесконечном полном базисе.М.: МГУ, Вестн. Моск. Ун-та. Сер. 1. Математика. Механика. 1997. Ш. С. 59−61.

10. Р. Мак-Ноттон. Теорема о бесконечной логике высказываний. Кибернетический сборник. Вып. 3, М.: Изд-во иностр. лит., 1961, стр. 59−78.

11. Гашков С. Б. Сложность приближенной реализации непрерывных функций схемами и формулами в полиномиальных и некоторых других базисах. Математические вопросы кибернетики, вып. 5, М.: Физметлит, 1994, стр. 144−207.

12. Гашков С. Б. О сложности приближения функций с заданными модулями непрерывности первого и второго порядков в некоторых кусочно-линейных и полиномиальных базисах.М.: МГУ, Вестн. Моск. Ун-та. Сер. 1. Математика. Механика. № 3, 1995.

13. Автоматы. Сборник статей. Под ред. К. Э. Шеннона и Дж. Маккарти. Пер. с англ. под ред. А. А. Ляпунова. М., Изд. иностр. лит., 1956.

14. Хайкин С. Нейронные сети: полный курс, 2-е издание, Вильяме, 2006.

15. McCulloch W. S. and W. Pitts «A logical calculus of the ideas immanent in nervous activity», Bulletin of Mathematical Biophysics, vol. 5, p. 115−133, 1943.

16. F. Rosenblatt The perceptron: a probabilistic model for information storage and organization of the brain, Psychological Review, 65:386−408, 1958.

17. A. B. J. Novikoff On convergence proofs on perceptrons, Proceedings of the Symposium on the Mathematical Theory of Automata, XII:615−622, 1962.

18. Уосермен Ф. Нейрокомпьютерная техника. M.: Мир. 1992. 240 с.

19. Minsky М. L. and S. A. Papert Perceptorns, Cambridge, MA: MIT Press, 1969.

20. Kohonen T. «Self-orgaanized formation of topologically correct feature maps», Biological Cybernetics, vol. 43, p. 59−69, 1982.

21. Кофман А.

Введение

в прикладную комбинаторику. М.: Наука, 1975.

22. Карманов В. Г. Математическое программирование. М.: Наука, 1986.

23. Гельфонд А. О. Трансцендентные и алгебраические числа. Изд. 2, М.: КомКнига, 2006.