О сложности перестройки формальных нейронов

Соколов, Андрей Павлович

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

Соколов, Андрей Павлович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «О сложности перестройки формальных нейронов»

Автореферат диссертации на тему "О сложности перестройки формальных нейронов"

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

Соколов Андрей Павлович

О СЛОЖНОСТИ ПЕРЕСТРОЙКИ ФОРМАЛЬНЫХ НЕЙРОНОВ

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

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

31 ОКГ 2013

МОСКВА - 2013

005536/»"

005536790

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

Научный руководитель

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

Величенко Владислав Викторович

доктор физико-математических наук, профессор,

Институт машиноведения РАН, ведущий научный сотрудник.

Чуличков Алексей Иванович доктор физико-математических наук, профессор, Московский государственный университет им. М.В.Ломоносова, Физический ф-т, профессор.

Ведущая организация - Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В. А. Трапезникова РАН.

Защита диссертации состоится «_£_» '' 2013 г. в / на заседании диссертационного совета Д.002.017.02 в Федеральном бюджетном учреждении науки Вычислительный центр им. A.A. Дородницына Российской академии наук (ВЦ РАН) по адресу: 119333, г.Москва, ул. Вавилова, д.40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН. Автореферат разослан « _ 2013 г.

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

В.В. Рязанов

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

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

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

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

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

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

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

Более строго, функция / : {0,1}" —> {0,1} называется пороговой, если существует линейное неравенство х\\и1 + ... + хпи)п - о > 0, с действительными коэффициентами и порогом, выполненное на тех и только тех наборах (ц, ...,£„), на которых функция / принимает значение 1. Коэффициенты к/х, ...,ги„ принято называть весовыми коэффициентами,

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

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

¿=i

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

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

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

maxflwil,.... |wn|, |<т|).

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

2 ы + и •

¿=L

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

L(n) < Тп (п+ 1)^.

Так как существует по крайней мере 2n2+0(nlog") различных пороговых функций (Зуев Ю.А.3), то существуют пороговые функции, обладающие размахом не менее 2n+0<Jl\ С другой стороны, число пороговых функций не превосходит 2" , поэтому более точных нижних оценок на величину размаха таким образом получить не удается.

В 1994 году Дж.Хастад4 доказал существование пороговой функции, обладающей размахом 2ínlosni~°(nlogn\ что дает порядок логарифма при стремлении числа переменных к бесконечности. В 2002 году Алон и By5

2Muroga S., Toda I.. Takasu S., Theory of majority decision elements, J. Franklin Institute, 271:5, p.376-418, 1961.

З3уев Ю.А., Комбинаторно-вероятностные и геометрические методы в пороговой логике. Дискретная математика, т.3:2, стр.47-57, 1991.

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

5Alon N.. Vu V.H., Anti-Hadamar matrices, coin weighting, threshold gates and indecomposable hypergraphs. Journal of Combinatorial Theory. 79:1, p.133-160, 1997.

нашли асимптотику логарифма размаха при стремлении числа переменных к бесконечности.

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

После работ Розенблатта было предложено множество различных архитектур нейросетей и алгоритмов их обучения, детальный обзор которых приведен в работе Хайкина7. Несмотря на то, что многие из данных алгоритмов обучения с успехом применяются в инженерной практике, для большинства из них нет математически строгих оценок на время работы. Более того, у такого наиболее распространенного алгоритма обучения как «метод обратного распространения ошибки» (Rumelhart D.E. Hinton G.Е„ Williams R.J.8) известно свойство неустойчивости по отношению к начальным значениям весовых коэффициентов (Kolen J F Pollack J.B.9).

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

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

6 Розенблатт Ф., Принципы нейродинамики (персептрон и теория механизмов мозга), Автоматы, Москва, Мир, 1965.

' Хайкин С., Нейронные сети: полный курс, Москва, Вильяме, 2006.

sRumeIhart D.E., Hinton G.E., Williams R.J., Learning Representation by Back-Propagatin» Errors Nature, 323, p.533-536, 1986.

9Kolen J.F., Pollack J.В., Back Propagation is Sensitive to Initial Conditions, Proceedings of the 1990 conference on Advances in neural information processing systems, p.860-867, 1990.

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

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

,2Judd J.S., Why are Neural Networks so Wide, Aleksander Taylor, 1, p.45-52, 1992.

l3Muroga S., Toda I., Takasu S., Theory of majority decision elements, J. Franklin Institute 27Г5 p 376418, 1961.

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

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

Элементарные операции перестройки линейных форм, степень воздействия которых ограничена, представляют интерес в связи с тем, что они хорошо согласуются с существующими в биологии моделями си-наптической пластичности (Zucker R.S., Regehr W.G.14, Bliss T.V., Lomo T.,15). Эти модели описывают механизмы изменения во времени силы синапсов биологических нейронов. Механизм синаптической пластичности считается основным способом, с помощью которого реализуется феномен памяти и обучения в живых организмах (Citri A., Malenka R.C.16).

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

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

l1Zucker R.S., Regehr W.G., Short-term synaptic plasticity, Annual Review of Physiology, 64, p.355-405,

2002.

l5Bliss T.V., Lomo T., Long-lasting potentiation of synaptic transmission in the dentate area of the

anaesthetized rabbit following stimulation o! the perforant path, The Journal of Physiology, 232:2, p.33l-

356, 1973.

l6Citri A., Malenka R.C., Synaptic Plasticity: Multiple Forms, Functions, and Mechanisms, Neuropsychopharmacology, 33:1, p.1-24, 2008.

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

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

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

Помимо самого сложного случая, который может возникнуть при обучении нейронов, несомненный интерес представляет задача оценки сложности обучения нейронов для почти всех случаев. Рассматривается вопрос, как ведет себя в большинстве случаев функция близости р(1, /), где I - линейная форма, а / - пороговая функция от п переменных. При этом полагается, что размах линейной формы I не превосходит величину Ь{п).

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

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

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

ченной мощности. Данная модификация является обобщением двух предыдущих случаев и в большей степени согласуется с существующими в биологии моделями синаптической пластичности (Zucker R.S., Regehr W.G.17, Bliss T.V., Lomo T.,18).

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

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

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

Цель работы

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

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

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

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

1. Введены в рассмотрение классы Tm.k пороговых функций от п переменных, где параметр m означает максимальный размер класса симмет-

17Zucker R.S., Regehr W.G., Short-term synaptic plasticity. Annual Review o[ Physiology, 64, p.355-405, 2002.

l8Bliss T.V., Lomo T., Long-lasting potentiation of synaptic transmission !n the dentate area of the anaesthetized rabbit following stimulation of the perforant path. The Journal of Physiology, 232:2, p.331-356, 1973.

ричных переменных, а параметр к - число независимых классов симметрии. Для данных классов получены верхняя и нижняя оценки сложности взаимной перестройки пороговых функций. Для этого введена величина р (т, к), характеризующая близость между наиболее удаленными пороговыми функциями/ не более чем с т взаимно симметричными переменными, и числом классов симметрии - к. При определенных соотношениях между параметрами симметрии т и к из этих оценок следует асимптотика логарифма функции близости р{тп,к). В частном случае, когда т = 1 и к = п, функция близости р(т,к) совпадает с величиной р{п). В этом случае из полученных оценок вытекает асимптотика логарифма шенно-новской функции сложности взаимной перестройки пороговых функций - р(п). Отметим, что последнее следствие может быть получено при помощи известных оценок на величину размаха, полученных в работах Муроги19 и Н.Алона и В.Ву20. Полученные оценки обобщают данный результат для классов пороговый функций, инвариантных относительно групп перестановок, а также расширяют множество случаев, для которых верна асимптотика логарифма функции р{т,к).

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

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

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

"Muroga S., Toda I., Takasu S., Theory o[ majority decision elements, J. Franklin Institute 271-5 p 376418, 1961. '

20Alon N.. Vu V.H., Anti-Hadamar matrices, coin weighting, threshold gates and indecomposable hypergraphs, Journal of Combinatorial Theory, 79:1, p.133-160, 1997.

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

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

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

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

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

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

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

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

научные конференции «Ломоносовские чтения» (Москва, МГУ им. Ломоносова, 2008, 2009 и 2012 гг.); третья научная конференция студентов и аспирантов кафедры Математической теории интеллектуальных систем механико-математического факультета МГУ (Москва, МГУ им. Ломоносова, 2007г.).

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

Основные результаты диссертации опубликованы в статье [1].

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема 1 Для достаточно больших к выполнено

т ■ 21*1°к*+°(*1°в*) <р(т, к) < тк+2 ■ 2iklosk+°(klo'kl

При определенных соотношениях между параметрами симметрии тп и к из теоремы 1 следует асимптотика логарифма функции близости р(тп, к).

Следствие Если к —> оо и log(m) = o(log(fc)), то

log р (m. к) ~ -к log к.

В частном случае, когда т = 1 и к = п, функция близости р (га, к) совпадает с величиной р{п). В этом случае из теоремы 1 вытекает асимптотика логарифма шенноновской функции сложности взаимной перестройки пороговых функций - р{п).

Следствие Если п —» оо, то log2 р (п) ~ тр log2 п.

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

Отметим, что последнее следствие может быть получено при помощи известных оценок на величину размаха, полученных в работах Муроги21 и Н.Алона и В.Ву22. Теорема 1 обобщает данный результат для классов пороговый функций, инвариантных относительно групп перестановок, а также расширяет множество случаев, для которых верна асимптотика логарифма функции р(т,к), указанная в первом следствии.

Глава 4 посвящена рассмотрению задачи обучения в большинстве случаев.

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

Теорема 2 Если п —> оо, то для почти всех пар (I, /), где f - пороговая фукнция, а I - линейная форма от п переменных такая, что L (I) < L (п), выполнено 2n+°M <p{l,f) <

2lMuroga S., Toda I.. Takasu S., Theory o[ majority decision elements, J. Franklin Institute, 271:5, p.376-418, 1961.

22Alon N.. Vu V.H., Anti-Hadamar matrices, coin weighting, threshold gates and indecomposable hypergraphs, Journal of Combinatorial Theory, 79:1, p.133-160, 1997.

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

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

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

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

Теорема 3 Если п —> оо, то

logp//(n) ~ |nlogn;

Ра (га) " п2 log п.

Теорема 4 Если тг —> оо, то для почти всех пар (/, /), где / - пороговая фукнция, а I - линейная форма от п переменных такая, что L (I) < L (п), выполнено

2п+о(п) < pn{l f) < 25"l°g"+°(*l°g");

п < Pa{l,f) < n2logn. Теорема 5 а) Для достаточно больших к выполнено

т ■ < (m> jfc) < тк+2. 2lfciog*+0(iiog*)_

б) Если к —> оо и log(m) = o(log(/c)), то

тк log к < ра (т, к) < тк2 log к.

Утверждения теорем 1,...,5 дают нижние и верхние оценки на количество элементарных операций перестройки линейных форм для перехода

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

В главе 6 рассмотрен вопрос алгоритмической сложности задачи перехода от «стартовой» линейной формы к «целевой», задающей желаемую пороговую функцию. Для этого вводится понятие множества допустимых линейных форм, весовые коэффициенты которых при стремлении числа переменных п к бесконечности по модулю ограничены величиной 0(п) Ь{п). Получены оценки сложности нахождения допустимой линейной формы для пороговой функции заданной виде множеств единиц и нулей, то есть наборов, на которых функция принимает значения 1 и О, соответственно. Показано, что в этом случае задача нахождения допустимой линейной формы имеет полиномиальную сложность от числа единиц и нулей желаемой функции. Получены оценки сложности взаимной перестройки допустимых линейных форм для различных функций близости в худшем случае. Описан алгоритм перестройки линейных форм, который имеет полиномиальную сложность как в терминах числа вспомогательных арифметических операций, так и в смысле числа элементарных шагов перестройки.

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

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

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

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

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

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

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

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

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

[4] А. П. Соколов. О сложности перестройки формальных нейронов, Интеллектуальные системы 2012, Т. 16, вып. 1-4, стр. 335-434.

23Muroga S., Threshold logic, New York, Wiley-Interscience, 1971.

24Parberry I., Circuit Complexity and Neural Networks, MIT Press, Cambridge, MA, 1994.

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

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Соколов, Андрей Павлович, Москва

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

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

04201365528

На правах рукописи УДК 519.71

Соколов Андрей Павлович

О СЛОЖНОСТИ ПЕРЕСТРОЙКИ ФОРМАЛЬНЫХ НЕЙРОНОВ

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

ДИССЕРТАЦИЯ на соискание учёной степени кандидата физико-математических наук

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

МОСКВА - 2013

Содержание

1. Введение 3

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

1.1.1. Постановка задачи......................................5

1.1.2. Основные результаты..................................8

1.1.3. Научная новизна........................................И

1.1.4. Структура диссертации................................13

2. Постановки задач, вспомогательные утверждения и конструктивная

характеризация пороговых функций 17

2.1. Постановки задач ..............................................17

2.2. Вспомогательные утверждения................................23

2.2.1. Сопряженные пороговые функции....................23

2.2.2. Изоморфные пороговые функции ....................23

2.3. Конструктивная характеризация пороговых функций ... 25

2.4. Доказательства утверждений..................................27

3. Обучение нейронов, инвариантных относительно групп перестановок

переменных 42

3.1. Основные понятия, постановки и результаты................42

3.2. Доказательства утверждений..................................43

4. Обучение в большинстве случаев 55

4.1. Основные понятия, постановки и результаты................55

4.2. Доказательства утверждений..................................55

5. Модификации понятия близости 61

5.1. Основные понятия, постановки и результаты................61

5.2. Доказательства утверждений..................................62

6. Алгоритмическая сложность обучения и

некоторые классы пороговых функций 71

6.1. Основные понятия, постановки и результаты................71

6.2. Доказательства утверждений..................................75

Список литературы 94

1. Введение

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

Более строго, функция / : {0,1}п —> {0,1} называется пороговой, если существует линейное неравенство + ... + хптп — а > 0, с действительными коэффициентами и порогом, выполненное на тех и только тех наборах (х1,...,хп), на которых функция / принимает значение 1. Коэффициенты к^,..., гип принято называть весовыми коэффициентами,

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

г=1

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

тах(|гУх| ..... |гип| , |сг|).

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

Ен + м-

г=1

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

Ь{п) < 2~п(п+ 1)^ .

Так как существует по крайней мере 2п2+0(п1о§п) различных пороговых функций [4], то существуют пороговые функции, обладающие размахом не менее 2п+°(п\ С другой стороны, число пороговых функций не превосходит 2п , поэтому более точных нижних оценок на величину размаха таким образом получить не удается.

В 1994 году Дж.Хастад [16] доказал существование пороговой функции, обладающей размахом 24п1°8?г+0(гг10ёп)) что дает порядок логарифма при стремлении числа переменных к бесконечности. В 2002 году Алон и Ву [12] нашли асимптотику логарифма размаха при стремлении числа переменных к бесконечности.

После работ Розенблатта было предложено множество различных архитектур нейросетей и алгоритмов их обучения, детальный обзор которых приведен в [9]. Несмотря на то, что многие из данных алгоритмов обучения с успехом применяются в инженерной практике, для большинства из них нет математически строгих оценок на время работы. Более того, у такого наиболее распространенного алгоритма обучения как «метод обратного распространения ошибки» [27] известно свойство неустойчивости по отношению к начальным значениям весовых коэффициентов [25].

Из теоретических работ по сложности обучения схем из пороговых функциональных элементов отметим работы С.Джадда [17], [18] и [19]. В данных работах было показано, что общая задача обучения нейронных схем является УУР-полной. Данная задача рассматривалась в различных постановках, в которых в качестве нейронов выступали как пороговые функции, так и функции, принимающие действительные значения на отрезке [0,1].

1.1. Краткое содержание работы 1.1.1. Постановка задачи

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

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

Для характеризации сложности обучения нейронов в работе рассмат-

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

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

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

Помимо самого сложного случая, который может возникнуть при обучении нейронов, несомненный интерес представляет задача оценки сложности обучения нейронов для почти всех случаев. Рассматривается вопрос, как ведет себя в большинстве случаев функция близости p(l,f), где I - линейная форма, а / - пороговая функция от п переменных. При этом полагается, что размах линейной формы I не превосходит величину L(n).

В первом случае к операции единичного изменения коэффициентов добавляется операция инвертирования (умножения на —1) коэффициента

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

1.1.2. Основные результаты

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

Теорема 1 Для достаточно больших к выполнено

т . 2^к1°ёк+°(к1°ёк) < p(jn к) < тк+2 • 22fcl0gfc+0(fcl°g*:)

При определенных соотношениях между параметрами симметрии га и к из теоремы 1 следует асимптотика логарифма функции близости р (га, к).

Следствие Если к —> оо и log(m) = o(\og(k)), то

log р (га, к) ~ -к log к.

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

Следствие Если п оо, то log2 р (п) ~ |п log2 п.

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

Отметим, что последнее следствие может быть получено при помощи известных оценок на величину размаха, полученных в работах Муро-ги [22] и Н.Алона и В.By [12]. Теорема 1 обобщает данный результат для классов пороговый функций, инвариантных относительно групп перестановок, а также расширяет множество случаев, для которых верна асимптотика логарифма функции р(т,к), указанная в первом следствии.

Теорема 2 Если п —» оо, то для почти всех пар (/, f), где f - пороговая фукнция, а I - линейная форма от п переменных такая, что L (I) < Lin), выполнено 2п+0^ <p(l,f) < 2^nl0sn+0(nl°sn).

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

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

В первом случае помимо операции единичного изменения коэффициентов разрешается использование операция инвертирования (умножения на —1) коэффициента или порога.

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

Как и ранее, под близостью между пороговыми функциями f и f" понимается минимально достаточное число операций над некоторой линейной формой, задающей функцию /', для получения линейной формы, задающей функцию /". Функцию близости, получаемую в первом случае обозначим рп, а во втором - ра.

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

Теорема 3 Если п оо, то

log рп (п) - \n log щ Pa (n) х П2 log П.

Теорема 4 Если п —> оо, то для почти всех пар (/, f), где f - пороговая фукнция, а I - линейная форма от п переменных такая, что L (/) < L (п), выполнено

2п+о{п) < Pn(l,f) < 22nl°gn+0(nl0Sn);

Pa (I J) < n2logn.

Теорема 5 а) Для достаточно больших к выполнено

т . 2ifc!ogA;+o(fclogfc) <- ^т^ ^ < rnk+2 • 2^klogk+°(klogk\

б) Если к —> сю и log(m) = o(log(/c)), то

тк log к < ра (т, к) < тк2 log к.

Утверждения теорем 1,...,5 дают нижние и верхние оценки на количество элементарных операций перестройки линейных форм для перехода от одной пороговой функции к другой. Оценки даны для различных множеств допустимых операций и для различных случаев: для самого сложного случая, для почти всех случаев и для классов пороговых функций, инвариантных относительно групп перестановок. Данные оценки характеризуют сложность, с которой столкнется всякий алгоритм, решающий задачу перестройки, с использованием рассмотренных множеств допустимых операций. При этом, данные результаты не дают описания непосредственного самого алгоритма, осуществляющего перестройку одной линейной формы в линейную форму, задающую желаемую пороговую функцию. Этот вопрос рассматривается в глав�