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

<г1

' ' МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ М. В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

Соколов Андрей Павлович О СЛОЖНОСТИ ОБУЧЕНИЯ ФОРМАЛЬНЫХ НЕЙРОНОВ

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

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

4856585

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

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

Валерий Борисович Кудрявцев

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

доктор физико-математических паук, профессор Александр Борисович Угольников

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

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

Защита диссертации состоится 11 марта 2011 г. в 16 ч. 45 м. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете им. М.В.Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

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

Автореферат разослан 11 февраля 2011 г.

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

А.О.Иванов

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

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

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

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

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

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

Пороговые функции алгебры логики являются простейшей математической моделью функционирования биологических нейронов. Данная модель была впервые предложена американскими учеными Маккаллоком и Питтсом в 1943 году1. В соответствии с данной моделью отдельная нервная клетка функционирует как логическое устройство, вычисляющее функцию взвешенного голосования входов. Более строго, функция / : {0,1}™ —> {0,1} называется пороговой, если существует линейное неравенство

Х\Ю1 + ... -I- хп-юп — а > О,

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

71

циентами, а свободный член а - порогом. Функцию ^ а^ш, — а в далыюй-

1=1

'Маккаллок У.С., Питтс V. Логическое исчисление идей, относящихся к нервной активности, Автоматы, стр. 302-384, 1050.

шсм будем называть линейной формой. Если линейная форма не обращается (! ноль ни на одном из наборов (сц,...,ап) € (0,1}п, то говорят, что она задаст пороговую функцию строгим образом.

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

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

тах(|ш1|..... |№п|,|сг|).

Также можно ввести понятие, веса линейной формы

¿К1 + И-«=1

Среди всех линейных форм, задающих пороговую функцию / строгим образом очевидно существует линейная форма минимального размаха. Ее размах назовем размахом функции /. Аналогичным образом вводится понятие веса пороговой функции. В 1961 году Мурога2 показал, что размах произвольной пороговой функции от п переменных не превосходит

Так как существует по крайней мерс 2различных пороговых функций3, то существуют пороговые функции, обладающие размахом не менее 25". С другой стороны число пороговых функций не превосходит 2" , поэтому более точных нижних оценок на величину размаха таким образом получить не удается.

В 1994 году Дж.Хастад* доказал существование пороговой функции, обладающей размахом 24п108п+0("10гп), что даст порядок логарифма при стремлении числа переменных к бесконечности. При этом, однако, явного задания данной функции линейной формой получено не было.

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

2Muroga М., Tocla I., Takasu S. Theory of majority decision elements, J. Franklin Institute, Vol. 271/5, p. 376-418, 1961.

3Muroga M. Threshold logic, Wilev-Interecience, 1971.

4Yajima S., Iliaraki T. A lower bound on the number of threshold functions, IEEE Trans. Electronic

Computers, EC-14, p. 926-929, 1965.

'Hastad .J. On the size of weights far threshold gates, SIAM J. Discr. Math. 7, p. 484-492, 1994.

многократно!! коррекции весовых коэффициентов и порога изменять свое функционирование на желаемое. Данное свойство было впервые отмечено в 1957 году Ф.Розенблаттом, разработавшим распознающую систему «пер-септроп» и предложившим алгоритм ее обучения6. После работ Розенблат-та было предложено множество различных архитектур иейросетей и алгоритмов их обучения7. Несмотря на то, что многие из данных алгоритмов обучения с успехом применяются в инженерной практике, для большинства из них ист математически строгих оценок на время работы. Более того, у такого наиболее распространенного алгоритма обучения как «метод обратного распространения ошибки»8 было даже обнаружено свойство неустойчивости по отношению к начальным значениям весовых коэффициентов9.

Из теоретических работ по сложности обучения схем из пороговых функциональных элементов отмстим работы С.Джадда10, 12. В данных работах было показано, что общая задача обучения нейронных схем является iVF-iiofliioü. Данная задача рассматривалась в различных постановках, в которых в качестве нейронов выступали как пороговые функции, так и функции, принимающие действительные значения на от]м:зке [0,1].

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

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

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

еРо'н'нблатт Ф. Принципы нейродинамики (ntpi.cnînptm и теория мехапишов молга), Автоматы, 106J.

7Хайкиц С. Нейронные сети: полный курс., Мскжва, Вильяме, 200G.

eRumelhart D.E.. Hintoii G.E., Williams R.J. Learning Repivscntation by Batk-Propayating Envrs, Nature, Vol. 323, p. 533-53G, I98G.

ílKoleri J.F.. Pollack J.B. Back Propagation is Sensitive to Initial Conditions, Proceedings of the 1990 conference on Advances ill neural information processing systems, p. 860-867, 1990.

L0Judd J.S. On the complexity of loading shallow neural networks, Journal of Complexity, Vol. 4, p. 177-192, 1988.

ll.Judd J.S. Neural Network Design and the Complexity of Learning, MIT Press, Camhridge, MA, 1990.

l2Judd J.S. Why are Neuml Networks so Wide, Aleksander, Taylor. Vol. 1, p. 45-52, 1992.

11 Muróla M., Toda I., Takasu S. Theory of majority decision elements, J. Franklin Institute, Vol. 271/5, p. 376-418, 1961.

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

Для характеризации сложности обучения нейронов в работе рассматривается более общая метрическая характеристика. Так, для каждой пары пороговых функций /' и /" вводится функция близости р (/'; /"), характеризующая минимально достаточное число единичных изменений некоторой линейной формы, задающей функцию /', для получения линейной формы, задающей функцию /". Таким образом, оценивается минимально возможная сложность перестройки исходной пороговой функции в желаемую вне зависимости от «стартовой» линейной формы.

Поведение функции близости р (/'; /") изучается в трех постановках.

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

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

Помимо худшего случая, который может возникнуть при обучении нейронов, несомненный интерес представляет задача оценки сложности обучения нейронов в большинстве случаев. Данная задача рассматривается во второй постановке. Ищется конструктивное описание достаточно больших классов пороговых функций, которые были бы максимально удалены или, наоборот, близки друг другу в терминах близости р. Также рассматривается вопрос, как ведет себя функция близости р (/'; /") для «почти всех» пар пороговых функций.

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

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

На практике, при обучении нейронов, помимо единичного изменения весовых коэффициентов могут применяться и другие операции. В свя:зи с этим очевидный интерес представляет получение рассмотренных ранее метрических характеристик сложности обучения нейронов для иных функций близости. В работе рассмотрены две модификации понятия близости пороговых функций: в первом случае к операции единичного изменения коэффициентов добавляется операция инвертирования (умножения на —1) коэффициента или порога, во втором случае также добавляется операция умножения и целочисленного деления коэффициента или порога на 2. Для каждой модификации понятия близости сложность обучения исследуется в трех постановках: в худшем случае, в большинстве случаев и для классов пороговых функций, инвариантных относительно групп перестановок.

Цель работы

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

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

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

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

1. Найдена асимптотика логарифма сложности взаимной перестройки пороговых функций в самом сложном случае.

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

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

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

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

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

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

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

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

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

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

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

Результаты диссертации неоднократно докладывались на семинарах механико-математического факультета МГУ им. М.В. Ломоносова «Теория автоматов» (2008-2010 гг.) и «Кибернетика и информатика» (2005-2010 гг.) под руководством академика В.Б. Кудрявцева.

Они докладывались также на следующих конференциях: международная конференция «Интеллектуальные системы и компьютерные науки» (Москва, МГУ им. Ломоносова, 2006г.); международный научный семинар «Дискретная математика и её приложения», посвященный 75-летию со дня рождения академика О.Б.Лупанова; международные научные конференции студентов, аспирантов и молодых ученых «Ломоносов» (Москва, МГУ им. Ломоносова, 2008, 2009 и 2010 гг.); научные конференции «Ломоносовские чтения» (Москва, МГУ им. Ломоносова, 2008 и 2009 гг.); третья научная конференция студентов и аспирантов кафедры Математической теории интеллектуальных систем механико-математического факультета МГУ (Москва, МГУ им. Ломоносова, 2007г.).

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

Основные результаты диссертации опубликованы в семи статьях [1]—[7j, список которых приведен в конце автореферата.

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

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

В главе 2 даются основные определения и сведения вспомогательного характера: вводятся понятия линейной формы и пороговой функции, определяется задание пороговой функции линейной формой. Вводится понятие близости пороговых функций />(/',/")•

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

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

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

друг другу в терминах близости р.

Для более общей характеризации типичной близости пороговых функций ставится задача поиска верхних и нижних оценок на функцию близости Р (/'; /"); имеющих место для «почти всех» пар пороговых функций /'. /".

Вводится понятие инвариантности пороговой функции относительно перестановки ж. Ставится задача описания классов пороговых функций, инвариантных относительно групп перестановок. Также ставится задача поиска верхних и нижних оценок па функцию близости р (/'; /"), имеющих место внутри данных классов.

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

В заключении главы вводятся вспомогательные понятия, используемые в дальнейшем изложении.

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

Далее, вводится понятие сигнатуры пороговой функции / как набор знаков коэффициентов некоторой линейной формы, задающей /. Оказывается, что если / существенно зависит от всех своих переменных, то сигнатура / определяется однозначным образом. Более того, отношение равенства сигнатур разбивает множество существенных пороговых функций на 2" взаимно непересекающихся равномощных класса, одним из которых является класс монотонных пороговых функций. Таким образом, структура, класса монотонных пороговых функций полностью определяет структуру класса всех пороговых функций.

Для любой пороговой функции существует бесконечное множество задающих се линейных форм. Линейные формы назовем эквивалентными, если они задают одну и ту же пороговую функцию. Множество всех существенных линейных форм с целочисленными коэффициентами и свободным членом, задающих пороговую функцию /, обозначим II (/). Легко видеть, что множество и (/) замкнуто относительно операции сложения линейных форм. В данной главе показано, что всякое множество II (/) содержит единственный базис относительно операции сложения линейных

форм, который является счетным н разрешимым, а также описан алгоритм, который последовательно строит базис множества U (/) для заданной пороговой функции /.

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

Теорема 1. При п —> оо выполнено

log2 р (п) ~ ~7i log2 п.

С содержательной точки зрения данный результат означает, что в случае использования лишь операции единичного изменения весовых коэффициентов при обучении нейронов с п входами управляющей системе может потребоваться вплоть до 22nl0gn+0("l0sn) элементарных шагов.

Интересно отметить, что получение данной теоремы было осуществлено с привлечением техники Н.Алои и В.By u, которая была разработана для решения другой задачи - оценки величины максимальпаго размаха по роговых функции от п переменных.

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

Теорема 2. Если п > 1, то линейная форма

(2 ■ Fi,2- F-2,..., 2 ■ Fn,2 ■ Fn+j - 1),

где F¡ - i-e число Фибоначчи, является линейной формой минимального размаха и веса для соответствующей пороговой функции от п перемытых.

Глава 5 посвящена исследованию сложности обучения в большинстве случаев.

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

ltAlou N., Vu V.H. Anti-IIadamar matrices. coin weighting. threshold gates and indecomposable hypergmphs, Journal of Combinatorial Theory, 70-1, 133-1GO, 1997.

класса всех пороговых функций. Это составляет утверждение следующей теоремы.

Множество всех пороговых функций от п переменных обозначим Тп. Рассмотрим матрицу D (п) = ||ру |||Г„|Х|ГП|. Элементы матрицы D (п) определим следующим образом

Ра = Р (Л, fj),

ГД° fi: fj - пороговые функции от п переменных. Будем называть D (п) матрицей близости множества пороговых функций от п переменных.

Теорема 3. Если п —> оо, то в матрице близости D (п) содержится такое подмножество R(n), что

log2|Ä(n)|xlog2|D(n)|,

и для всех pij G R (п) выполнено

log2 pij ж log2 р (п).

Далее приводится конструктивное построение такого класса пороговых фукнций, что близость функций из данного класса ограничено произвольной заранее заданной величиной, лежащей в диапазоне от 3 (п + 1) до 3-25п, где п - число переменных. При этом, мощность данного класса экспоненциально зависит от п. Данное утверждение составляет следующую теорему.

Теорема 4. Если п + 1 < с < то существует класс: M пороговых функций отп переменных, содержащий (с—п — 1)-2п_2 элементов, такой что для всех /', /" из M выполнено

Р (/'i /") < 3 ■ с.

Интересно отметить, что получение данной теоремы было осуществлено с привлечением техники В.Богоссян и Д.Брук ld, которая была разработана для решения другой задачи - построение так называемых «линейных» пороговых функций заданного веса.

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

15DohossUm V., Bruck J. On Neural Networks mth Minimal Weights, NIPS, 246-252, 1995.

Теорема 5. Если п —> оо, то для почти всех пар пороговых функций /'. /" £ Тп выполнено

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

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

Элементы a,b G fin назовем тт-эквивалентными, если о = тгг (6) для некоторого целого г. Отношение тг-эквивалснтпости рабиваст множество fln па попарно непересекающиеся классы 0\,..., Ojt. которые принято называть п-орбитами.

Далее, пусть R = {R\,R^} - некоторое разбиение множества П„. Говорят, что элементы a, b G Çïn эквивалентны относительно разбиения R. если а и b принадлежат одному и тому же подмножеству Ri разбиения R. и обозначается это так: а ~ Ь (mod R).

Будем говорить, что нсрес-гановка ж сохраняет разбиение R. если для всякого а € П„ выполнено а ~ it (a) (mod R).

Теорема 6. Если пороговая функция f еТ" инвариантна относительно перестановки п € Sn, и Oj, ...,0k - п-орбиты, то / инвариантна относительно всякой перестановки к' 6 Sn, сохраняющей разбиение 0\, ...,0k-

Данная теорема устанавливает эквивалентность между свойством инвариантности пороговой функции относительно перестановки 7г и свойством симметричности переменных входящих в соответствующие тг-орбиты.

Далее показано, что «почти псе» пороговые функции являются несимметрическими, то есть инвариантными относительно лишь тождественной перестановки. Это составляет утверждение следующей теоремы.

Теорема 7. Почти все пороговые функции несимметрические.

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

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

Теорема 8. Если к —> оо, то

m ■ 2l2kl°sk+"(kioek) <p(m,k) < тк+2 ■ 2l2hl°zk+°(kl°skl

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

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

Получены верхние и нижние оценки сложности перестройки для двух модификаций понятия близости пороговых функций. В первом случае помимо операции единичного изменения коэффициентов разрешается использование операция инвертирования (умножения на —1) коэффициента или порога. Во втором случае помимо операции инвертирования добавляется операция умножения и целочисленного деления коэффициента или порога па 2. Как и раньше под близостью пороговых функций /' и /" понимается минимально достаточное число операций над некоторой линейной формой, задающей функцию /', для получения линейной формы, задающей функцию /". Функцию близости, получаемую в первом случае обозначим рц, а во втором - рщ.

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

Теорема 9. . При n —> оо выполнено

log рц{п) ~ |nlogn; рш (n) X n2 log n.

Теорема 10. . Если п —> оо, то для почти всех пар пороговых функций /',/" € Тп выполнено

2n+o(n) < Рл (f /") < 25n'°"n+0(nl0="'-п ^ Pill (п) ~ п2 íogn.

Теорема 11. . Если к —> оо, то

Ш-2 ik\ogk+o(k\ogk) < рп (rn ty < m*:+2 . 2l^bg»:+o(fclogfc).

тк log к < pin (т, к) < \тк2 log к.

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

Благодарности

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

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

[1| А. П. Соколов. О конструктивной характеризации пороговых функций, Интеллектуальные системы 2008, Т. 12, вып. 1-4, стр. 363-388.

[2] А. П. Соколов. О конструктивной характеризации пороговых функции, Фундаментальная и прикладная математика 2009, Т. 15, стр. 189-208.

[3] А. П. Соколов. Асимптотика логарифма сложности перестройки нейронов, Интеллектуальные системы 2009, Т. 13, вып. 1-4, стр. 119-127.

[4| А. П. Соколов. Об одном семействе нейронов с ограниченной сложностью взаимной перестройки, Интеллектуальные системы 2009, Т. 13, вып. 1-4, стр. 475-488.

[5] А. П. Соколов. О сложности взаимной обучаемости почти всех нейронов, Интеллектуальные системы 2010, Т. 14, вып. 1-4, стр. 417-432.

[6] А. П. Соколов. Об одной последовательности пороговых функций, Интеллектуальные системы 2010, Т. 14, вып. 1-4, стр. 433-442.

[7| А. П. Соколов. О конструктивной характернаации пороговых функций, инвариантных относительно групп перестановок, Интеллектуальные системы 2010, Т. 14, вып. 1-4, стр. 443-460.

Подписано в печать 31.01.2011 Формат 60x88 1/16. Объем 1.0 п.л. Тираж 100 экз. Заказ № 1079 Отпечатано в ООО «Соцветие красок» 119991 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. А-102