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

• Автор: Соколов, Андрей Павлович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 96 с.

Содержание
1. Введение
1.1. Краткое содержание работы
1.1.1. Постановка задачи
1.1.2. Основные результаты
1.1.3. Научная новизна
1.1.4. Структура диссертации
2. Постановки задач, вспомогательные утверждения и конструктивная
характеризация пороговых функций
2.1. Постановки задач
2.2. Вспомогательные утверждения
2.2.1. Сопряженные пороговые функции
2.2.2. Изоморфные пороговые функции
2.3. Конструктивная характеризация пороговых функций
2.4. Доказательства утверждений
3. Обучение нейронов, инвариантных относительно групп перестановок
переменных
3.1. Основные понятия, постановки и результаты
3.2. Доказательства утверждений
4. Обучение в большинстве случаев
4.1. Основные понятия, постановки и результаты
4.2. Доказательства утверждений
5. Модификации понятия близости
5.1. Основные понятия, постановки и результаты
5.2. Доказательства утверждений
6. Алгоритмическая сложность обучения и
некоторые классы пороговых функций
6.1. Основные понятия, постановки и результаты
6.2. Доказательства утверждений
Список литературы

1. Введение
Пороговые функции алгебры логики являются простейшей математической моделью функционирования биологических нейронов. Данная модель была впервые предложена американскими учеными Маккаллоком и Питтсом в 1943 году [6]. В соответствии с данной моделью отдельная нервная клетка функционирует как логическое устройство, вычисляющее функцию взвешенного голосования входов.
Более строго, функция / : {0,1}п ■—> {0,1} называется пороговой, если существует линейное неравенство xWi + ... + xnwn — а > 0, с действительными коэффициентами и порогом, выполненное на тех и только тех наборах (xi,..., хп), на которых функция / принимает значение 1. Коэффициенты wi,...,wn принято называть весовыми коэффициентами,

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

называть линейной формой. Если линейная форма не обращается в ноль ни на одном из наборов (ai,...,an) е (0,1}п, то говорят, что она задает пороговую функцию строгим образом.
Несмотря на свою простоту, пороговые функции обладают значительными вычислительными возможностями и, при этом, весьма просты с точки зрения технической реализации.
При задании пороговых функций могут рассматриваться линейные формы с целочисленными коэффициентами и свободным членом. В этой связи можно ввести понятие размаха линейной формы
max(|tni|,...,wn, |сг|).
Также можно ввести понятие веса линейной формы

^2 KI + kl ■

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

Так как существует по крайней мере 2п2+°(п1о§п) различных пороговых функций [4], то существуют пороговые функции, обладающие размахом не менее 2п+°(п С другой стороны, число пороговых функций не превосходит 2П , поэтому более точных нижних оценок на величину размаха таким образом получить не удается.
В 1994 году Дж.Хастад [16] доказал существование пороговой функции, обладающей размахом 24п1оёп+0(7г1°8п)) что дает ПОрЯДОК логарифма при стремлении числа переменных к бесконечности. В 2002 году Алон и Ву [12] нашли асимптотику логарифма размаха при стремлении числа переменных к бесконечности.
Понятия размаха и веса оказываются весьма полезным при изучении одного из важнейших свойств пороговых функций - способности к обучению. Обучаемость пороговых функций - это их способность в результате многократной коррекции весовых коэффициентов и порога изменять свое функционирование на желаемое. Данное свойство было впервые отмечено в 1957 году Ф.Розенблаттом, разработавшим распознающую систему «персептрон» и предложившим алгоритм ее обучения [7].
После работ Розенблатта было предложено множество различных архитектур нейросетей и алгоритмов их обучения, детальный обзор которых приведен в [9]. Несмотря на то, что многие из данных алгоритмов обучения с успехом применяются в инженерной практике, для большинства из них нет математически строгих оценок на время работы. Более того, у такого наиболее распространенного алгоритма обучения как «метод обратного распространения ошибки» [27] известно свойство неустойчивости по отношению к начальным значениям весовых коэффициентов [25].
Из теоретических работ по сложности обучения схем из пороговых функциональных элементов отметим работы С.Джадда [17], [18] и [19]. В данных работах было показано, что общая задача обучения нейронных схем является А^Р-полной. Данная задача рассматривалась в различных постановках, в которых в качестве нейронов выступали как пороговые функции, так и функции, принимающие действительные значения на отрезке [0,1].

Покажем, что для любого і є {1,...,п} найдется такой множитель С Є ЛГ, ЧТО 1у;.а ~ I'■
Из леммы 2.3 следует, что для произвольной линейной формы с целыми коэффициентами = лцац + ... + и>пхп — а, которая не проходит ни через одну точку множества Е%, существует линейная форма
Іє = ЮхХ + ... + Хг- + (и)г + є)хг + и)г+іХг+і + ... + и)пХп — (7,
где є = д Є N. такая, что ~ 1е. При этом, форма 1Е существует для любого г Є {1,...,п}.
Положим с — р ■ д, тогда
Таким образом, всегда возможно подобрать такой натуральный множитель С, ЧТО їй,,О ~ V.
Следовательно, І' Є и (/) и, значит, V представима в виде линейной комбинации элементов из Ь, то есть
Пусть I = хг. Возможны два случая: І є Ь и I £ Ь. Покажем, что второй случай невозможен. Предположим противное. Линейную форму 1ш,(т будем называть положительно-определенной, если все ее весовые коэффициенты и порог положительны. Концентрацией переменного хг в
положительно-определенной линейной форме І-ш.а = ^2 юзхз ~ а назовем

Очевидны следующие свойства концентрации:
1 0 ^ Іу],(7) ^ 1 >