Об оптимизации структурной реализации нейронных сетей тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М В ЛОМОНОСОВА

Механико-математический факультет

На правах рукописи

Половников Владимир Сергеевич

УДК 519 95

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

01 01 09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2008

Работа выполнена на кафедре Математической теории интеллектуальных систем Механико-математического факультета Московского государственного университета имени М В Ломоносова

Научный руководитель — кандидат физико-математических наук, доцент

Анатолий Александрович Часовских

Официальные оппоненты

доктор физико-математических наук, профессор Алексей Иванович Чуличков кандидат физико-математических наук, доцент Сергей Иванович Карташов

Ведущая организация — Московский Энергетический Институт (Технический университет)

Защита диссертации состоится "18" апреля 2008 г в 16 ч 40 м на заседании диссертационного совета Д 501 001 84 при Московском государственном университете имени M В Ломоносова по адресу 119991, Российская Федерация, Москва, ГСП-1, Ленинские горы, Московский государственный университет имени M В Ломоносова, Механико-математический факультет, аудитория 14-08

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ имени M В Ломоносова (Главное здание, 14 этаж)

Автореферат разослан "18" марта 2008 г

Ученый секретарь диссертационного совета Д 501 001 84 при МГУ доктор физ -мат наук, профессор

Общая характеристика работы Актуальность темы

Многие практические проблемы могут быть решены с использованием нейронных сетей Нейронные сети хорошо зарекомендовали себя как средство решения задач для которых практически невозможно использование статических методов (без обучения, адаптации) Это задачи классификации, распознавания образов, моделирования ассоциативной памяти и другие Нейронные сети также применяются для нахождения приближенного решения NP-полных задач за приемлемое время. Однако, актуальна проблема синтеза нейронных сетей как построить нейросеть способную решать поставленную задачу Для начала необходимо представить исходные данные в виде, приемлемом для обработки нейронными сетями В идеальном варианте после предварительной обработки исходных данных мы получим линейно разделимую задачу, что значительно упрощает построение нейросети-классификатора, которой в этом случае может быть представлена персептроном Розенблатта1 Хорошо известен алгоритм обучения такой нейросети, сходимость которого математически обоснована (Розенблатт2, Новиков3) К сожалению, при решении реальных задач, как правило, такая предобработка данных невозможна Минский и Пэперт 4 в своей работе "Персептроны" доказали, что простейшие однослойные нейронные сети способны решать только линейно разделимые задачи Однако, это ограничение преодолимо при использовании многослойных нейронных сетей Значит, необходимо переходить к более сложной архитектуре, чем у персептрона В теории непрерывных нейронных сетей (с достаточно гладкой функцией активации) часто используется многослойный персептрон, а для его обучения — алгоритм обратного распространение ошибки5, который, как известно, не применим для дискретных нейронных сетей, в том числе и для сетей модели Мак-Каллока-Питтса1 К сожалению, заранее не известно, какой сложности (размера) может потребоваться сеть для достаточно точной реализации требуемого отображения К тому же может оказаться, что рассматриваемая нейронная сеть не обучаема для решения поставленной задачи

Для построения математических моделей различных процессов удобно применить понятие функциональной системы введенное впервые Кудрявцевым6 В рамках понятия функциональной системы можно рассматривать функции алгебры

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

2F Rosenblatt The perceptron a probabilistic model for information storage and organization of the brain, Psychological Review, 65 386-408, 1958

3A В J Novikoff On convergence proofs on perceptrons, Proceedings of the Symposium on the Mathematical Theory of Automata, ХП 615-622, 1962

4Minsky M L and S A Papert Perceptorns, Cambridge, MA МГГ Press, 1969

6Уосермен Ф Нейрокомпъютерная техника M Мир 1992 - 240 с

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

логики с операцией суперпозиции, конечные автоматы7 с операциями суперпозиции или композиции, однородные структуры8, схемы из функциональных элементов9 с операцией суперпозиции и т п Унифицированный подход позволил обобщить свойства и методы исследования для различных функциональных систем

Так в теории нейронных сетей, в частности при решении задачи синтеза, могут быть использованы идеи, возникающие при изучении других функциональных систем

Цель работы

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

2 Разработать аппарат исследования дискретных нейронных сетей С помощью полученного аппарата исследовать сложностные характеристики оптимальных нейронных схем

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

4 Построить канонические формы нейронных схем, реализующих функции их определенных классов

Структура и объем диссертации

Диссертационная работа изложена на 108 страницах и состоит из введения и четырех глав, разделенных на параграфы Библиография включает 23 наименования

Научная новизна

1 Доказано, что любая нейронная схема реализует кусочно-линейную функцию и наоборот, любая кусочно-линейная функция может быть реализована нейронной схемой нелинейной глубины не более двух

2. Доказано, что любая нейронная схема Мак-Каллока-Питтса реализует кусочно-параллельную функцию и наоборот, любая кусочно-праллельная функция

7Кудрявцев В Б , Алешин С В ,Подколзин А С Введение в теорию автоматов М Наука Гл ред физ -мат лит, 1985

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

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

может быть реализована нейронной схемой Мак-Каллока-Питтса нелинейной глубины не более двух

3 Получен критерий реализуемости кусочно-линейных функций нейронной схемой нелинейной глубины не более 1

4 Для функциональной системы нейронных схем Мак-Каллока-Питтса найден эффективный критерий полноты множеств функций, содержащих в замыкании все линейные функции

5 Получены оценки функции Шеннона для сложности схем Мак-Каллока-Питт-са и сложности нейронных схем, имеющих единичную нелинейную глубину I рода, которые приводят к асимптотике при фиксированной размерности признакового пространства

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

Основные методы исследования

В диссертации использованы методы теории автоматов, теории функциональных систем, комбинаторики, алгебры, математического анализа

Теоретическая и практическая ценность работы

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

Апробация работы

Результаты диссертации докладывались на конференциях и семинарах Механико-Математического факультета МГУ им М В.Ломоносова на семинаре "Теория автоматов" под руководством академика, профессора В Б Кудрявцева (неоднократно в 2005-2007 гг), на семинаре "Математические вопросы кибернетики" под руководством профессора О М Касим-Заде (ноябрь 2007 г), на семинаре "Нейронные

сети" под руководством доцента А.А Часовских (неоднократно 2002-2007 гг), на семинаре 'Теория дискретных функций и приложения" под руководством профессора Д Н Бабина (сентябрь 2002 г), а также на конференции "Ломносовские чтения" в 2006 и 2007 гг Москва, МГУ им М В Ломоносова, на IX международной конференции "Интеллектуальные системы и компьютерные науки" Москва, МГУ им МВ Ломоносова 2006 г

Публикации по теме диссертации

Основные результаты диссертации опубликованы в пяти статьях, список которых приведен в конце автореферата [1-4]

Краткое содержание работы

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

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

В параграфе 1.1 даются основные определения Вводятся следующие функции

1) постоянная функция дс = с, с 6 К,

2) сумматор Еп(ж1, , х„) = XI + . + хп, где г, б! при г = 1,2,. , га,

3) усилитель /7(х) = 7Ж1, где 7, х 6 ЗЕ,

Глава 1

Множество всех таких функций обозначается через Д'

Далее, по аналогии с автоматными схемами определяются схемы из функциональных элементов А', называемые нейронными схемами без памяти Вводятся понятия нелинейной глубины и сложности таких схем Путем в нейронной схеме называется последовательность функциональных элементов , где Рг е А' Причем один из входов Р\ является входом нейронной схемы, выход ^ является выходом нейронной схемы, а выход Д — один из входов ^,+1, г = 1, , к — 1 Рассматриваются все пути в нейронной схеме без памяти Длиной пути называется число нелинейных элементов {.Р или в), содержащихся в нем Нелинейной глубиной нейронной схемы называется длина самого длинного пути

Число нелинейных элементов в схеме называется нелинейной сложностью нейронной схемы

Множество всех линейных функций обозначается через Ь, далее определяются кусочно-линейные функции многих переменных

Пусть I, — гиперплоскость, задаваемая уравнением х аг + с, = 0, о, € Ж"\{0}, с, £ 1, ! = 1, , к Для каждой точки х 6 Кп рассмотрим вектор <т(х) = (о"1, , а к) с компонентами из множества {—1,0,1}, ег, = здп(х а, + с,), где

sgn(b) =

Две точки х,у € Ж" эквивалентны относительно гиперплоскостей Ii, ., 4 тогда и только тогда, когда er (ж) = сг(у), что обозначается х ~ у

Легко проверить, что отношение действительно является отношением эквивалентности Таким образом, пространство К" разбивается на классы эквивалентности Ri, ,RS

Сигнатурой класса R называется вектор a(R) = <т(х), где х — точка класса R Пусть Ri, ,i?s — все классы эквивалентности на которые гиперплоскости Ii, , lk разбивают Ж"

Функция / • Ж" —> Ж называется кусочно-линейной, если Vj € {1, , s} найдутся b3 G Ж" и dj € Ж, что для всех х € R3 выполняется f(x) — х b3 + d3 Множество всех кусочно-линейных функций обозначаются PL

Функция / Ж" —> Ж называется кусочно-постоянной, если Vj € {1, , s} найдутся d3 € Ж, что для всех х G R3 выполняется /(ж) = d3 Множество всех кусочно-постоянных функций обозначаются PC

В параграфе 1 2 доказывается теорема о нелинейной глубине нейронных схем без памяти и показывается, что схем нелинейной глубины один не достаточно для реализации всех кусочно-линейных функций

Теорема 1 Для любой нейронной схемы без памяти существует эквивалентная ей схема с нелинейной глубиной не больше 2

Доказательство теоремы является конструктивным

Утверждение. Существует нейронная схема, для которой нет эквивалентной схемы нелинейной глубины меньше двух

Для доказательства утверждения рассмотрена нейронная схема, реализующая следующую кусочно-линейную функцию

, . (1, х = 0иу = 0 = | о, иначе

В параграфе 1 3 подробно изучены схемы нелинейной глубины один вводятся необходимые определения и доказывается основная теорема параграфа Пусть кусочно-линейная функция / задана гиперплоскостями , Любая тройка классов эквивалентности (Д+, До, Д_), Д+, До, Д- € {Дь , Д3}, таких, что элементы векторов сигнатур этих классов удовлетворяют условиям сг*+ = <То = ПРИ * — 1, - , г — 1, г +1, , п, а а\ = 1, а^ = 0 и ах_ — —1, называется смежной тройкой к гиперплоскости 1„ где (сг+, ,сг") — <т(Д+), (сгд, ,сгд) — <т(До) и (ст1,. .,<£) = а(Н-.)

Если для гиперплоскости 1г функции / найдутся линейные функции ¿+,г(ж) = а+),ж+с+1, и = а-^ж+с-,,, такие что для всех троек (Д+, До, Д-) смежных с

1г выполняются равенства fR+ — = 1+:1 и /д_ — = то тройка (1г, 1+1,, называется переходом / через гиперплоскость ^ В противном случае переход через гиперплоскость I, не существует. Если гиперплоскость I не совпадает ни с одной из гиперплоскостей 1%,.. задающих /, то тройка (2,0,0) также является переходом для / через I Переход называется нетривиальным, если хотя бы одна из двух его последних компонент отлична от нуля

Теорема 2 Пусть f — кусочно-линейная функция, заданная гиперплоскостями ,1к Она представима нейронной схемой нелинейной глубины один с некоторой нелинейной сложностью р тогда и только тогда, когда для г = 1, , к у / существуют переход (1и 1+>и г) через гиперплоскость 1„ причем в последовательности 2_д,. , не болеер ненулевых компонент, т е выполнено соотношение

к

2к-£(х(1+,>0) + х(Ц.,0))<р

«=1

Где функция х(о, Ъ) определяется равенством

, ( 1, при а = Ь

^ = иначе

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

к, что для некоторых а+)1, а_14,6 б К" и с+1„ 6 К, г = 1, , / представима

в виде

к

/(х) = + с+[П а, ж + с,) + + с_„ -аг • ж — Сг)) + Ь х + <£,

»=1

В параграфе 1 4 подробно изучаются схемы Мак-Каллока-Питтса, получаемые из элементов базиса Д' без использования элемента "Р" Определяется множество кусочно-параллельных функций

РР = {/|/ = /е + /г, /с е РС, е £}

Для этого подкласса нейронных схем доказывается теорема, аналогичная теореме 1

Теорема 3 Множество функций, реализуемых нейронными схемами Мак-Кал-лока-Питгпса, совпадает с множеством всех кусочно-параллельных функций И для любой кусочно-параллельной функции существует нейронная схема Мак-Каллока-Питтса нелинейной глубины не более 2

Глава 2

В главе 2 рассматривается типичная для функциональных систем задача полноты Для начала вводятся необходимые определения

Функция одной переменной f(t) из РС называется С-финитной функцией, если 32/,с/ е Ж, Т} > 0 такие, что при Ь Е (—оо,—Т/) и (Т/, +оо) выполнено f(t) = Cf Обозначим класс всех С-финитных функций от 1 переменной Ф(1)

Для кусочно-постоянной функции / К" —у К и прямой 91, заданной параметрически XI = -(- ¿1, , хп = а„1 + &„, функция дЦ) = /(а^ + Ьи ,апЬ + Ь) называется сечением функции / прямой 91

Функция / € РС называется С-финитной, если сечение / любой прямой является С-финитной функцией от 1 переменной Обозначим класс всех С-финитных функций через Ф

Вводится класс С-финитно-линейных функций

ФЬ = {/\/ = ф + 1,феФ,1еЬ}

Доказывается утверждение о замкнутости рассмотренного класса

Лемма. Класс ФЬ замкнут относительно операций суперпозиции

Далее приводится доказательство основной теоремы главы

Теорема 4 Пусть замыкание множества В кусочно-параллельных функций содержит все линейные функции Тогда замыкание В по операции суперпозиции совпадает с РР в точности тогда и только тогда, когда В целиком не содержится в Ф Ь

Доказательство теоремы конструктивное и позволяет с помощью схемы из линейных элементов и любой не С-финитно-линейной функции выразить ^-функцию

Глава 3

В главе 3 приведены оценки сложности минимальных нейронных схем Через Z{S) обозначена нелинейная сложность схемы S Для произвольной кусочно-параллельной функции f(x 1, . , хп) в Ж", заданной к гиперплоскостями вводится сложность ее реализации схемами Мак-Каллока-Питтса

Ямр(Г) = а mm Z{S),

где минимум берется по всем нейронным схемам Мак-Каллока-Питтса реализующим /.

Вводится функция Шеннона ZMp{k) — max Zup(f)

f£PP /эцма h гиперплоскостями

При этом уточняется понятие нелинейной глубины Пусть для пути , Рр

схемы S выполнены следующие условия

1 Для всех г = 1, ,р — 1 выполнено, что если Fl+i является элементом "F'\ то выход F, соединен лишь с первым входом F1+1,

2 Для всех г = 1, . , р выполнено Ft ф в

Тогда рассматриваемый путь называется путем I рода Максимальное число нелинейных элементов "F", в таких путях схемы S называется нелинейной глубиной I рода для нейронной схемы 5 Рассматриваются простые нейронные схемы без памяти, нелинейная глубина I рода которых не превосходит 1

Для простых схем определяются аналогичные введенным ранее функции

Z(f) = min Z(S), где минимум берется по всем S ршпуст/

простым нейронным схемам реализующим f

Функция Шеннона Z(k) = max Z(/)

f€PL /а«дм» к гиперплоскостями

Пусть Н(п, к) — максимальное число классов эквивалентности, на которые к гиперплоскостей могут разбить Жп Известна теорема Шлефли, позволяет подсчитать число n-мерных открытых многогранных конусов, которые получаются

в результате разбиения к гиперплоскостями пространства Ж™ В работе использованы следующие вспомогательные утверждения-

Лемма. Для всех натуральных пик верно Н( 1, к) — 2к + 1, Н{п, 1) = 3 А для п > 2 и к > 2 выполнено неравенство

Н(п, к) < Н(п, к-1) + 2Н(п -1,к-1) Лемма. При к > п выполнено

п—1 к-2

Н(п, к) = 3 Y, Q-i2' + 2" Е С?'1

i=0 j=n-l

Далее в диссертации приводятся оценки для функций ZMp(k), Z{k) и их асимптотики

Теорема 5 Для функции Шеннона ZMp{k) верно

1) при к <п

3* — 1 < ZMP{k) <3*4-2к

2) при к > п

п-1 к-2 п-1 к-2

3 си2' + 2" £ с;-1 -1 < zMP(k) < 3 £ cj^y + 2" £ с?-1 + 2*

1=0 3=п— 1 t=0 J =7L— 1

Следствие. Для функции Шеннона Zup{k) при n = const, п > 1 верна асимптотика

2"

ZMp(k)---гА", А -»■ оо

п1

Теорема 6 Для функции Шеннона Z(k) верно

1) при к <п

3* - 1 < <Зк + 2к

2) при к > п

п-1 к-2 п-1 fe-2

3£qu* + 2п с--1 - 1 < ад < з^с^г + 2" с;-1 + 2А

1=0 2=п-1 г=0 j=n—1

Следствие. Для функции Шеннона Z(k) при те = const, п > 1 верна асимптотика

~ ^Jfe", fc оо п'

Глава 4

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

В параграфе 4 1 рассматриваются нейронные схемы с памятью Через 3<ю обозначим детерминированную функцию, реализующую единичную задержку с начальным состоянием оо, ао € Ж, а через Д — новый базис А = Д' и {3<ю1ао €

Схема, полученная из элементов базиса Д с использованием операции суперпозиции и обратной связи, называется нейронной схемой (с памятью)

Детерминированная функция / • (К°°)п —> К°° . г — /(®1, , хп), для которой существуют числа к € Н, . ., а§ 6 Ж и кусочно-линейные функции ., Ф* К" —» К, что выполнены канонические уравнения

называется нейронной функцией

Далее доказывается следующая лемма

Лемма. 1) Любая нейронная схема реализует некоторую нейронную функцию 2) Любая нейронная функция реализуется некоторой нейронной схемой В параграфе 4 2 приводится доказательство основной теоремы главы

Теорема 7 Пусть нейронная схема 5 реализует нейронную функцию f Тогда из элементов Д, используя лишь операцию суперпозиции, можно построить схему, однократное применение операции обратной связи к которой приводит к нейронной схеме, реализующей /.

5 — нейронная схема без обучения, если задает нейронную функцию /, удовлетворяющую каноническим уравнениям

Пусть схема 5 задает нейронную функцию /(®х, ,хп, у)

5 — нейронная схема с обучением тогда и только тогда, когда для всех р 6 N и

I

<0) = (4, . ,аЙ «г(< +1) =

*(« + !) = ад<),2(« + 1))

любых слов а € 3RP, а = (а^, , ар), существует нейронная схема S'a без обучения, задающая функцию

/а(®1. ,®п) = /(®1, • ,5я,об), гдеоб=(ах, .,аР,0,0, ) £ Ж00

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

Теорема доказывается конструктивно и позволяет по заданной нейронной функции (или схеме ее реализующей) построить схему вида описанного в теореме (с однократным применением операции обратной связи на последнем шаге)

В параграфе 4 3 к множеству А(Д') добавляется элемент "умножение", реализующий функцию М(х, у) = х • у, и рассматриваются схемы с умножением с памятью (без памяти) Вводится определение кусочно-полиномиальной функции Далее доказывается лемма о характере функций схем без памяти, реализуемых над базисом с умножением (все такие функции обозначены через 5)?)

Лемма.Множество кусочно-полиномиальных функций совпадает с множеством всех функций, реализуемых схемами над базисом А'х = Д' U {М(х, у)}

Нейронную схему с памятью с умножением (над базисом Ах = A U {М(х, у)}) можно задать системой канонических уравнений

'd(0) = (oj, ,а§)

d(t + l) = $(d(t),x(t+l)) = ^1(d(t),x(t + l)), ,

, z(t+l) = Z(d(t),x(t+l)), где Z, <3>i, , Фk~ кусочно-полиномиальные функции.

Лемма. 1) Любая нейронная схема с умножением задает нейронную функцию с умножением

2) Любая нейронная функция с умножением задается некоторой нейронной схемой с умножением

Наконец, формулируется теорема, являющаяся обобщением теоремы 7 на схемы над Ах

Теорема 8 Пусть нейронная схема с умножением S реализует нейронную функцию с умножением / Тогда из элементов Ах, используя лишь операцию суперпозиции, можно построить схему, однократное применение операции обратной связи к которой приводит к нейронной схеме, реализующей функцию f

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

Работы по теме диссертации

[1] Половников В С О некоторых характеристиках нейронных схем М , Вестн Моек Ун-та Сер 1, Математика Механика 2004 №5, стр. 65-67

[2] Половников ВС О некоторых характеристиках нейронных схем М , Интеллектуальные системы том 8, выпуск 1-4, 2004. Стр 121-145

[3] Половников В.С Критерий нелинейной однослойности нейронных схем М , Вестн Моск. Ун-та Сер 1, Математика Механика 2006 №б, стр 3-5

[4] Половников В С О нелинейной сложности нейронных схем Мак-Каллока-Питтса М , Интеллектуальные системы том 11, 2007 Стр 261-276

Издательство ЦПИ при механико-математическом факультете МГУ им М В Ломоносова

Подписано в печать /4,03 О В Формат 60x90 1/16 Уел печ л /,0 Тираж -/ОО экз Заказ /-?

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

Введение

Глава 1. Исследование нелинейной глубины

1.1. Понятие нейронных схем без памяти

1.2. Теорема о нелинейной глубине нейронных схем без памяти

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

1.4. Нейронные схемы Мак-Каллока-Питтса. Пространство кусочно-параллельных функций.

Глава 2. Задача проверки полноты в пространстве кусочно-параллельных функций.

Глава 3. Исследование нелинейной сложности

Глава 4. Нейронные схемы с памятью

4.1. Понятие нейронных схем с памятью.

4.2. Минимизация числа операций обратной связи в нейронных схемах с памятью.

4.3. Нейронные схемы с умножением.

Для построения математических моделей различных процессов удобно применить понятие функциональной системы введенное впервые Кудрявцевым [1]. В рамках понятия функциональной системы можно рассматривать формулы алгебры логики с операцией суперпозиции, конечные автоматы [2] с операциями суперпозиции или композиции, однородные структуры [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(a;, у). Было доказано, что схемы реализуют те и только те кусочно-линейные функции определенные на [0,1]п и принимающие значения на отрезке [0,1], которые являются непрерывными и задаются на всех участках линейными функциями с рациональными коэффициентами. В отличие от базисов, рассматриваемых в главе 1, базиса Мак-Ноттона не достаточно для реализации всевозможных кусочно-линейных или кусочно-параллельных функций, тем не менее легко понять, что такими функциями можно приблизить всевозможные непрерывные функции / : [0,1]п [0,1]. Позднее С.Б. Гашков в своих работах [11] и [12] подробно рассмотрел несколько кусочно-линейных и полиномиальных базисов, изучая зависимость количества элементов в схеме от точности приближения функций схемами и нашел поведение функции Шеннона при точности приблежения е 0. Помимо конечных, были рассмотрены и, похожие на исследуемые в настоящей работе, базисы континуальной мощности, например, {х + у, х • у} U R и {х - у, |ж|, 1} U {сх : 0 < с < 1}.

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

15].

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

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

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

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

Х1

-h

Рис. 1. Математическая модель нейрона. соответствуют дендритам; w\,., 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, №, 1957.

9. Касим-Заде О. М. Общая верхняя оценка сложности схем в произвольном бесконечном полном базисе.Ш.: МГУ, Вестн. Моск. Ун-та. Сер. 1. Математика. Механика. 1997. №4. С. 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.