Содержание к диссертации
Введение
Глава 1. Исследование нелинейной глубины 15
1.1. Понятие нейронных схем без памяти 15
1.2. Теорема о нелинейной глубине нейронных схем без памяти 20
1.3. Каноническое представление нейронных схем без памяти нелинейной глубины один 33
1.4. Нейронные схемы Мак-Каллока-Питтса. Пространство кусочно-параллельных функций
Глава 2. Задача проверки полноты в пространстве кусочно-параллельных функций 46
Глава 3. Исследование нелинейной сложности 60
Глава 4. Нейронные схемы с памятью 79
4.1. Понятие нейронных схем с памятью 79
4.2. Минимизация числа операций обратной связи в нейронных схемах с памятью 83
4.3. Нейронные схемы с умножением 97
Литература 105
- Теорема о нелинейной глубине нейронных схем без памяти
- Нейронные схемы Мак-Каллока-Питтса. Пространство кусочно-параллельных функций
- Задача проверки полноты в пространстве кусочно-параллельных функций
- Минимизация числа операций обратной связи в нейронных схемах с памятью
Введение к работе
Для построения математических моделей различных процессов удобно применить понятие функциональной системы введенное впервые Кудрявцевым [1]. В рамках понятия функциональной системы можно рассматривать формулы алгебры логики с операцией суперпозиции, конечные автоматы [2] с one-рациями суперпозиции или композиции, однородные структуры [3], схемы из функциональных элементов [4] с операцией суперпозиции и т.п. Подобный унифицированный подход позволил обобщить некоторые результаты и технику доказательств для различных функциональных систем. Так, рассмотрение изучаемых объектов как функциональных систем, к примеру, позволило автору провести доказательство леммы 1.1 индукцией по построению, характерной для структурных автоматов и схем из функциональных элементов, а в главе 2 рассмотреть задачу полноты, характерную для функциональных систем в дискретной математике. Применяется техника и возникают структуры типичные в теории автоматов в доказательстве леммы 4.1, а результат аналогичный сформулированному в теоремах 7 и 8 ранее для конечных автоматов был получен в дипломной работе О. Смирновой. Для описания логического устройства электронных схем обычно рассматривались схемы из элементов, реализующих некоторые простые булевские функции. Решалась задача о построении всевозможных
функций, используя наименьшее количество элементов. Так в работе Лупанова [5] была получена асимптотика функции Шеннона для реализации в виде формул L(n) ~ ^-^ и схем L(n) ~ — булевских функций над базисом {&, V, —}. Позднее стала бурно развиваться пороговая логика [6] привлекательная тем, что для реализации булевской функции схемой, пороговых элементов обычно необходимо меньше, чем рассматриваемых ранее булевских элементов. Однако, при таком подходе возникают технические трудности физического изготовления пороговых элементов, поэтому возникла задача, где разные пороговые элементы имеют разную сложность. При изучении схем из пороговых элементов также исследовалось не только количество элементов, но и глубина схемы (время функционирования схемы). В работе [7] подробно изучил сложность схем из пороговых элементов глубины два. Решение аналогичной задачи для изучаемых автором нейронных схем приводится в главе 3. Обзорная работа [6] замечательна еще тем, что в ней доказывается теорема Шлефли, позволяющая подсчитать число n-мерных открытых многогранных конусов, которые получаются в результате разбиения к гиперплоскостями пространства Жп. Несмотря на то, что в данной работе рассматривается аналогичная конструкция, автору пришлось передоказать в главе 3 данную теорему, ввиду n-мерных открытых многогранных конусов от классов эквивалентности. Если
нет необходимости учитывать вклад некоторых элементов в исследуемый процесс, или рассматривая физическую реализацию схем, сложностью изготовления некоторых элементов в которой можно пренебречь, следует считать вес этих элементов нулевым. Такой подход к изучению сложности впервые был продемонстрирован в работе А.А. Маркова [8]. Позднее реализация схем над бесконечными базисами имеющие элементы с нулевым весом развиты в работах О.М. Касим-Заде [9]. В настоящей работе вес всех линейных элементов равен нулю. Помимо реализации функций алгебры логики, схемный подход популярен для приближения различных классов непрерывных функций. В 1951 году вышла работа Мак-Ноттона посвященная бесконечнозначной логике (переведена в [10]), в которой рассматривались схемы над базисом из следующих кусочно-линейных функций тах(1 — х-\-у, 1), 1-х, тах(а;,7/), тіп(ж, у). Было доказано, что схемы реализуют те и только те кусочно-линейные функции определенные на [0,1]п и принимающие значения на отрезке [0,1], которые являются непрерывными и задаются на всех участках линейными функциями с рациональными коэффициентами. В отличие от базисов, рассматриваемых в главе 1, базиса Мак-Ноттона не достаточно для реализации всевозможных кусочно-линейных или кусочно-параллельных функций, тем не менее легко понять, что такими функциями можно приблизить всевозможные непре-
рывные функции / : [0,1]п —у [0,1]. Позднее СБ. Гашков в своих работах [11] и [12] подробно рассмотрел несколько кусочно-линейных и полиномиальных базисов, изучая зависимость количества элементов в схеме от точности приближения функций схемами и нашел поведение функции Шеннона при точности приблежения є —> 0. Помимо конечных, были рассмотрены и, похожие на исследуемые в настоящей работе, базисы континуальной мощности, например, {ж + у, х у] U Ш и {х - у, \х\, 1} U {сх : 0 < с < 1}.
Идеи, возникающие при изучении различных функциональных систем, можно применить и к бурно развивающейся в последнее время теории нейронных сетей. Настоящая работа посвящена исследованиям так называемых нейронных схем, математического объекта, основанного на понятии искусственной нейронной сети ([13], [14]) модели Мак-Каллока-Питтса [15].
Многие проблемы можно свести к задачам, решаемым с помощью нейронных сетей. Нейронные сети хорошо зарекомендовали себя как средство решения задач сложных для решения статическими методами (без обучения, адаптации). Это задачи классификации, распознавания образов, моделирования ассоциативной памяти и другие. Нейронные сети также применяются для нахождения приближенного решения NP-полных задач за приемлемое время.
По результатам исследований биологов, мозг и нервная система состоят из особых клеток — нейронов, соединенных между собой нервными волокнами. Нервные волокна передают электрические импульсы между этими клетками. Каждый нейрон имеет отростки нервных волокон двух типов: дендриты и аксон. На аксоне может формироваться электрический импульс. Дендриты способны принимать импульсы. Аксон контактирует с дендритами других нейронов через специальные образования — синапсы, которые влияют на силу импульса. Импульсы, поступившие к нейрону одновременно по нескольким дендритам, суммируются. Если суммарный импульс превышает некоторый порог, нейрон переходит в состояние возбуждения и формирует собственный импульс, который передается далее уже по его аксону. Важной особенностью нейро-сетей является то, что чувствительность синапсов может изменяться со временем, а значит, может поменяться поведение соответствующего нейрона, которое, в свою очередь, отражается на функционировании сети в целом — сеть умеет настраиваться, обучаться.
Из биологического описания была построена математическая модель нейрона и процесса функционирования нейронной сети.
На рис. 1 схематически изображена математическая модель нейрона. Где х\,... :хп — являются входами нейрона и
Рис. 1. Математическая модель нейрона.
соответствуют дендритам; w\,... ,wn — веса входов, соответствуют чувствительности синапсов; h — порог активации нейрона; / — функция активации.
Согласно схеме, действие нейрона заключается в вычислении следующей функции:
/ ^2 xiwi ~h\.
г'=1
Результат вычисления "появляется" на выходе нейрона и передается на входы других аналогичных структур, составляющих искусственную нейронную сеть.
Искусственная нейронная сеть — это набор нейронов, связанных между собой. Часть входов нейронов могут являться внешними входами сети, часть выходов нейронов — выходами сети. Как правило, функции активации нейронов считаются известными и одинаковыми, связи известными, а веса связей настраиваются в процессе обучения. Таким образом, работа обученной нейронной сети заключается в преобразовании вход-
ного вектора значений в выходной вектор.
Автором рассмотрены нейронные схемы с точки зрения функциональных систем. Изучены различные функциональные базисы, пригодные для представления искусственных нейронных сетей модели Мак-Каллока-Питтса (с памятью и без) схемами из функциональных элементов. Для моделирования функционирования схемы в дискретном времени, в базис был добавлен автоматный элемент единичной задержки [2]. В этих условиях удалось дать определение процесса обучения и построить каноническую форму обучающейся нейронной схемы.
При решении задач с помощью нейронных сетей, можно условно выделить следующие этапы:
выбор модели (пространства входов и выходов, математическое представление нейронов, вид функций активации, модель функционирования во времени);
предварительная обработка данных: представление исходных данных в приемлемом для выбранной модели виде, интерпретация выхода нейросети;
построение нейросети (выбор архитектуры: количество слоев, количество нейронов на каждом слое, наличие прямых и обратных связей);
выбор модели обучения нейросети;
обучение нейросети;
проверка обучения, при необходимости повторные обучения;
применение построенной нейронной сети для решения задачи.
И на каждом этапе возникают свои сложности. В выборе модели пока ограничимся пространством действительных чисел для входов и выходов, ^-функцией Хевисайда в качестве функции активации. В идеальном варианте после предварительной обработки исходных данных мы должны получить линейно разделимую задачу, так как это значительно упрощает построение нейросети-классификатора в виде персептрона Ро-зенблатта [14]. Существует алгоритм обучения такой нейросети, сходимость которого математически обоснована ([16],[17]). К сожалению, при решении реальных задач мы, как правило, не можем провести такую предобработку данных, при которой будет достигнута линейная разделимость образцов. Значит, необходимо переходить к более сложной архитектуре, чем персептрон. В непрерывных нейронных сетях (с достаточно гладкой функцией активации) часто используется многослойный персептрон и алгоритм обратного распространение ошибки [18], который, как известно, не применим для дискретных нейронных сетей, в том числе и для сетей модели Мак-Кал-
лока-Питтса.
Автором предложен алгоритм перестроения обучающейся нейронной схемы в виде схемы с одной обратной связью. Таким образом, схема для обучения использует значения на выходах не всех элементов, а лишь одного. В этом подход аналогичен алгоритму обратного распространения ошибки.
Искусственные нейронные сети без обратных связей являются универсальным средством аппроксимации функций, что позволяет использовать их в решении таких задач, как, например, задача классификации. Обычно нейронные сети оказываются наиболее эффективным способом классификации, потому что фактически генерируют большое число регрессионных моделей (которые используются в решении задач классификации статистическими методами).
К сожалению, заранее не известно, какой сложности (размера) может потребоваться сеть для достаточно точной реализации отображения. Эта сложность может оказаться чрезмерно высокой, что потребует сложной архитектуры сети. Так Минский и Пэперт в своей работе "Персептроны" [19] доказали, что простейшие однослойные нейронные сети способны решать только линейно разделимые задачи. Однако, это ограничение преодолимо при использовании многослойных нейронных сетей. Тек, в сети с одним скрытым слоем вектор, соответствующий входному образцу, преобразуется скрытым слоем в
некоторое новое пространство, которое может иметь другую размерность, а затем гиперплоскости, соответствующие нейронам выходного слоя, разделяют его на классы. Таким образом сеть распознает не только характеристики исходных данных, но и "характеристики характеристик", сформированные скрытым слоем.
Задача построения архитектуры нейросети на первый взгляд кажется необозримой. Обычно к этой задаче подходят просто: сущестует несколько десятков различных нейросетевых архитектур, эффективность которых подтверждена практикой и, иногда, математической теорией. Наиболее популярные и изученные архитектуры — это многослойный персептрон, нейронная сеть с общей регрессией, нейронные сети Кохонена [20].
Из соображений оценки сложности архитектуры, автором было проведено исследование быстродействия нейронных схем: нелинейной глубины — параметра, аналогичного количеству слоев в соответствующей нейронной сети, и нелинейной сложности — аналога количества нейронов в сети. Оказалось, что любую нейронную схему можно представить схемой нелинейной глубины не более двух. Подробно были исследованы схемы нелинейной глубины один: приведен канонический вид такой схемы и алгоритм, позволяющий по характеристикам функции определить, представима ли она схемой нелинейной глубины один. Для некоторых классов схем найдена оценка функ-
ции Шеннона (минимального количества нелинейных элементов, необходимого для представления произвольной функции нейронной схемой заданного класса).
Далее в работе были оценены функциональные возможности исследуемой модели. Частично решена проблема полноты в пространстве кусочно параллельных функций — функций, представимых схемами над некоторым базисом. Проблема полноты решена для систем, замыкание которых содержит все линейные функции. Другими словами, для дискретных нейронных сетей найдены условия на функцию активации необходимые и достаточные для того, чтобы модель была эквивалентна модели Мак-Каллока-Питтса без памяти, т.е. чтобы функции задаваемые нейронными схемами в нашей модели были представимы в неросетевой модели Мак-Каллока-Питтса и наоборот. Так же рассмотрены функциональные возможности схем, содержащих элемент "умножение". Ранее полученные в данной работе результаты (для схем без умножения) пересмотрены для нейронных схем с умножением.
Автор благодарит своего научного руководителя кандидата физико-математических наук, доцента А.А. Часовских за интересную тему, постановку задачи и постоянное внимание к работе. Спасибо профессору О.М. Касим-Заде за ценные замечания и обсуждения. Автор выражает глубокую благодарность заведующему кафедрой академику, профессору В.Б.
Кудрявцеву и всему коллективу кафедры математической теории интеллектуальных систем за творческую атмосферу и доброжелательность, способствующую работе.
Теорема о нелинейной глубине нейронных схем без памяти
Путем в нейронной схеме назовем последовательность функциональных элементов (Si, Fi),..., (Sk, Fk), где F{ Є А . Причем один из входов Si является входом нейронной схемы, выход Sk является выходом нейронной схемы, а ВЫХОД S{ — один из входов Si+i, г = 1, ...,& — 1. Рассмотрим все пути в нейронной схеме без памяти. Длиной пути называется число нелинейных элементов, содержащихся в нем. Нелинейной глубиной нейронной схемы называется длина самого длинного пути. Множество функций Жп — Ж, реализуемых нейронными схемами без памяти, обозначим . Функция / : Жп — Ж называется линейной, если найдутся а Є Жп и с Є Ж, что f(x) — х а + с, где под операцией "" понимается скалярное произведение векторов. Множество всех линейных функций обозначим L. Пусть її — гиперплоскость, задаваемая уравнением х сц + Q = 0, сіі Є Кп\{0}, СІ Є Ж, і = 1,..., к. Для каждой точки жбі" рассмотрим вектор о (х) = ( ті,..., сгк) с компонентами из множества {—1, 0,1}, тг- = sgn(x щ + сг), где -1, 6 0 sgn(b) = { 0, 6 = 0 1, Ь 0. Две точки х, у Є Шп эквивалентны относительно гиперплоскостей li,..., Ik тогда и только тогда, когда о (х) = сг(у), что обозначается ж у. Легко проверить, что отношение " " действительно является отношением эквивалентности. Таким образом, пространство Rn разбивается на классы эквивалентности Ri,..., Rs. Сигнатурой класса R называется вектор cr(R) = а(х), где х — точка класса R. Пусть Ri,..., Rs — все классы эквивалентности на которые гиперплоскости li,..., Ik разбивают Шп. Функция / : М.п —у R называется кусочно-линейной, если V? Є {1,..., s} найдутся bj Є Шп и dj Є Ш, что для всех ж Є i?j выполняется /(ж) = x-bj + dj. Множество всех кусочно-линейных функций обозначим PL. Функция / : W1 — Ж называется кусочно-постоянной, если Vj Є {1,..., s} найдутся dj Є Ш, что для всех х Є Довыполняется /(ж) = dj. Множество всех кусочно-постоянных функций обозначим PC. Лемма 1.1 Имеет место равенство = PL. Доказательство Сначала докажем включение С PL. (1.1) Для этого рассмотрим произвольную функцию S(х) Є , S : Еп —у Ш. По определению множества существует нейронная схема без памяти (5, S(x)). Докажем, что S(x) является кусочно-линейной. Проведем доказательство методом математической индукции по построению нейронной схемы (5, S(x)). Для проверки реализации функциональными элементами кусочно-линейных функций достаточно убедиться в том, что А С PL. Рассмотрим следующие случаи: а) дс Є PL, так как постоянная функция является кусочно линейной; б) En(zi,..., хп) = х (1,..., 1) Є L\ п в) /7(ж) = 7ж Є ; г) прямая Ж. разбивается точкой х = 0 на 3 класса эквивалентности R\ = {х Є Мж 0}, R2 {х Е Мж = 0} и R3 = {x Е Щх 0}. Функция в(х) постоянна на каждом из них, а значит кусочно-линейна; д) плоскость R2 разбивается прямой Х2 = 0 на 3 класса эквивалентности Ri = {(хі,х2) Є №?\х2 0}, R2 = {(хъ х2) Є Ж2\х2 = 0} и Д3 = {Оъ ж2) Є М2, ж2 0}. Функция F(ari, #2) линейна на каждом из этих классов, а значит кусочно-линейна. Теперь покажем, что операции 1 — 5 сохраняют кусочно-линейность функций нейронных схем. Пусть (5, f(xi,... ,жп)) — нейронная схема без памяти и функция /(жі,..., хп)) кусочно-линейна. То есть гиперплоскости If. х йі -f СІ = О, где х = (xi,..., хп) и Щ = (а},..., а"), г = 1,..., к, разбивают Шп на классы эквивалентности Ri,..., Rs, и для всех х Є -Rj выполняется /(ж) = х - bj + d/, 67- = (6),... ,ьу), j = l,...,s.
1. Добавлением фиктивного входа получаем схему, реализу ющую кусочно-линейную функцию f (xi,..., жп+і). Действи тельно гиперплоскости l\\ x -a i+Ci = 0, где х — (rci,..., жп, жп+і) иа- = (а},..., о", 0), « = 1,..., к, разбивают Шп+1 на классы эк вивалентности Ді,..., . it = {ж Є Мп+1(жі,..., хп) Є Rj}, j = 1,..., s. Тогда для всех х Є Щ выполняется f (x ) = x -b,j dj,blj = (b},...,b],0):j = l,...,s.
2. Не ограничивая общности считаем, что вход, соответствующий переменной хп, является фиктивным. Рассмотрим не пустые множества, полученные сечением гиперплоскостей li,..., Ik гиперплоскостью хп = 0. Обозначим их 1 ъ...., 1 к,. Они являются гиперплоскостями в М"1 и разбивают М!1"1 на классы эквивалентности, являющимися сечениями i?i,..., Rs гиперплоскостью хп = 0, а значит на них / (жі,... , жп-і) = f(xi,..., xn-i, 0) линейна.
3. Аналогично предыдущему случаю, сечения h,..., ln ги перплоскостью Xi—Xj = 0 образуют гиперплоскости в Мп-1 (переменные xi,...,Xi:..., Xj-i, Xj+i,..., хп), которые разбивают М.п г на классы эквивалентности, являющимися не пустыми сечениями Ri,..., Rs гиперплоскостью Х{ — Xj — 0. А значит на них j yXi,..-, %i, , Xj_i, ajj+i,..., xnj = j [Xi,..., X{,..., x —i, x\, Xj+i,..., хп) линейна.
4. Переименование входов нейронной схемы приводит к переименованию переменных функции, что сохраняет ее кусочно-линейный вид.
5. Пусть l x,...,l t — гиперплоскости в Rm задающие h(xi,... ,х т). Тогда добавим в (Si,/і) фиктивные входы Я/1,..., хп, а в (5г, /) соответственно я/х,..., х т. Таким образом, /їй/ — кусочно-линейные функции переменных х г, ..., х т хі,..., хп. Гиперплоскости li,..., Ik, l[,..., l t разбивают Rm+n на классы линейности функций h и /. Операция 5 на любом классе эквивалентности (разбиения Km+n гиперплоскостями li,..., Ik, l[,. ., l t) есть суперпозиция линейных функций, то есть линейна. Причём Х{ (см. определение операции 5) является фиктивной переменной результирующей функции. Применим операцию 2.
Нейронные схемы Мак-Каллока-Питтса. Пространство кусочно-параллельных функций
Рассмотрим произвольную нейронную сеть модели Мак-Каллока-Питтса без памяти. Для представления ее в виде нейронной схемы, заменим в неиросети веса, приписанные входам нейронов, на элементы "умножение на константу". Ввиду того, что в модели нейрона, схематически представленной на рис. 1, помимо чувствительности синапсов отражены сумматор и функция активации 0, которые есть и в элементном базисе, то получится корректная нейронная схема без памяти.
В полученной таким образом нейронной схеме не будет ис пользован элемент F, а выходным элементом схемы обязательно будет элемент в. Если мы откажемся от последнего условия, т.е. будем строить нейронные схемы без элемента F с произвольным выходным элементом, то реализуемая функция будет представлять из себя линейную комбинацию нейросетевых функций модели Мак-Каллока-Питтса и линейных функций.
Ввиду близости моделей, нейронные схемы, полученные без использования элемента F, по определению раздела 1.1 главы 1, будем называть нейронными схемами Мак-Каллока-Питтса. Напомним обозначения: множество линейных функций — L, множество кусочно-постоянных функций — PC. Введем понятие множества кусочно-параллель?шх функций следующим выражением: PP = {f\f = fc + fiJcePCJlGL}. Для класса функций U обозначим подкласс, зависящих ровно от га переменных через U(m). Множество функций, реализуемых нейронными схемами Мак-Каллока-Питтса обозначим . Лемма 1.3 Пусть функция f{x) Є PL, тогда функция g{x) = 9(f(x)) — кусочно постоянна. Доказательство Дейтсвительно, пусть / задана гиперплоскостями l\:..., Ik, де лящих Жп на классы эквивалентности R\,..., Rs, на которых она линейна и для всех j — 1,..., s выполнено: при х Є Rj f(x) = f\n. =bj x + dj, где bj Є Шп, dj Є Ш. Тогда, очевидно, на классах Rj, j = 1,..., s, функция д(х) = 6(bj х + dj), то есть равна 1, при bj-x-{-dj 0 и равна 0 иначе. Таким образом, ввиду линейности условий, д[х] является кусочно-постоянной, принимает значения 0 или 1 и задается следующим набором гиперплоскостей: h,... ,h и теми l j = {x\bj х + dj = О}, где h Ф б, j = 1,..., s. Лемма доказана Теорема 3 Мноэюество функций, реализуемых нейронными схемами Мак-Каллока-Питтса, совпадает с множеством всех кусочно-параллельных функций. И для любой кусочно-параллельной функции существует нейронная схема Мак-Каллока-Питтса нелинейной глубины не более двух. Доказательство Докажем включение 2! С PP. Пусть (S, /) нейронная схема Мак-Каллока-Питтса, из строения схемы легко заключить, что функция / имеет следующий вид: /(ai) = ci/i(5) + .-.+ Cpfp(x) + fi, (1.14) где p — некоторое натуральное число, сг- Є R, г = 1,...,р, fl Є L, а функции fi,..., fp являются кусочно-постоянными по лемме 1.3, т.к. образованы подсхемами (Si, /і),..., (Sp, fp) с выходными элементами в. По определению кусочно параллельных функций, ввиду линейности пространства PC и выражения (1.14) следует, что / Є PP. Докажем обратное включение D РР, Пусть / — кусочно-параллельная функция. По определению, существуют /с Є PC и fi Є L, что f = /c + f. Если мы сможем реализовать функцию /с нейронной схемой, используя лишь сумматор, умножитель на константу и функцию в, то мы сможем построить схему и для /. Действительно, построив схему для // согласно рис. 8 и подав на входы сумматора выходы схем для fc и fi мы получим искомую схему Мак-Каллока-Питтса для /. Покажем теперь, как построить схему Мак-Каллока-Питтса для произвольной /с ЄЕ PC. Пусть /с задана гиперплоскостями 1{ : Щ-Х + СІ = 0, і = 1,..., А;, которые разбивают Шп на классы эквивалентности Ri,..., Rs, что для некоторых действительных di,... ,ds при х Є Rj выполнено f(x) = /R. = dj, j = 1,..., s. Тогда будем строить схему для fc по формуле аналогичной формуле (1.3): fc(x) = dj9 І 2х(в5п(огж + Сі),о-5) -И , (1-15) а формула построения для / будет иметь вид f{x) = Y djO [Y xisgnia, х + с,-), о)) - к ) + Д. (1.16) j=l \i=l / где alj — г-я компонента вектора сигнатуры класса Ду, г = 1,..., к, j = 1,..., s, а обозначение х раскрывается по формулам (1.4) - (1.6) и как видно из рисунков 9 - 11 не содержит элементов F. Отметим, что так же, как и в теореме 1 нелинейная глубина построенной схемы не превышает двух. Теорема доказана
Задача проверки полноты в пространстве кусочно-параллельных функций
Функция f(t) из РС{1) называется С-финитной функцией от 1 переменной, если ЭТу, с/ Є Ш, Tj О такие, что при t Є (—со,—Ту) U (Т/,+оо) выполнено f(t) — Cf. Обозначим класс С-финитных функций от 1 переменной Ф(1). Рассмотрим кусочно-постоянную функцию / : Rn 4Іи прямую ОТ заданную параметрически: Х\ = a\t + bi,...,xn = ant + bn. Функция g(t) = f{a\t + &i,..., ant + 6) называется сечением кусочно-постоянной функции f прямой ОТ. Функция / Є PC называется С-финитной, если сечение / любой прямой является С-финитной функцией от 1 переменной. Обозначим класс всех С-финитных функций через Ф. Будем называть класс эквивалентности бесконечным, если он содержит луч. Будем говорить, что прямая "идет" из одного бесконечного класса в другой или "соединяет" два бесконечных класса эквивалентности, если эти классы содержат лучи, принадлежащие данной прямой. Замечание. Не смотря на континуум возможных прямых сечения, процедура проверки принадлежности произвольной функции / Є PC классу Ф конечна. Действительно, прямые сечения идут из одного бесконечного класса эквивалентности в другой. Классов эквивалентности конечное число. Достаточно проверить невозможность проведения прямой из одного бесконечного класса в другой для классов, значения функции / в которых различны. Тем временем, задача возможности проведения прямой из класса эквивалентности Rj в класс Rj сводится к вопросу допустимости следующей задачи линейного программирования (см. [22]). Пусть функция / задана гиперплоскостями li,..., Ik, U = a-i х + СІ, і = 1,..., к] класс эквивалентности Rj имеет вектор сигнатуры T(RJ) = ( xj,..., т), а Rj — соответственно j(Rj ) = (dji,..., (Ту). Заметим, что прямая, идущая из Rj в Rj/, необходимо пересекает гиперплоскости с номерами і, для которых J\ = — alj ф 0; не пересекает гиперплоскости с номерами г, для которых т!-/ — сг ф 0; лежит в гиперплоскостях с номерами і для которых а\ — alj = 0. Других вариантов быть не может. Обратно, если мы найдем прямую обладающую вышеперечисленными свойствами, то она, очевидно, будет соединять класс Rj и Rj . Если обозначить через s направляющий вектор прямой из Rj в Щ, то эти условия можно переписать в виде условий задачи линейного программирования для вектора s: s щ = 0, для г таких, что сг -, = crj; aljS щ 0 для г таких, что т], = —oj ф 0. Лемма 2.1 Сумма двух С-финитных функций является С-фииитной функцией. Доказательство Пусть /і(ж) и /2(Ё) — С-финитные функции, / = /і + /2. Очевидно, / — кусочно-постоянна. Рассмотрим произвольную прямую 91 заданную параметрически с параметром t. Сечение #i ( ) функции /і прямой 91 имеет действительные параметры Т9х и c9l, смысл которых такой же, как в определении класса Ф(1). Аналогично, сечение 7г() функции /2 прямой 9Т обладает параметрами Тд2 и с52. Определим Тд — max {Tgi, Т52} и с5 = cgi+cg2- Легко видеть, что сечение g(t) функции / прямой 91 будет являться С-финитной функцией одного переменного с параметрами Tgicg. Ввиду произвольности выбора прямой сечения, по определению, функция / является С-финитной. Лемма доказана Введем класс С-финитно-линейных функций: ФЬ = {М = ф + і,фєФ,ієЬ]. Заметим, что ФЬ С РР, ФЬ ф PP.
Лемма 2.2 Класс ФЬ замкнут относительно операций суперпозиции. Доказательство 1. Докажем, что операции добавления или изъятия фиктивных переменных не выводят из класса ФЬ. Пусть функция /(#1,... ,жп) Є ФЬ, что означает существование функций ф$ из Ф и If из Ь таких, что / = (j)f-{-lf. Пусть функция д(х\, ... ,хп, xn+i) = f(x\,...,хп) получена из / добавлением фиктивной переменной хп+\. Рассмотрим фд(х\,..., жп+і) = g(xi,..., xn+i) — lf{x\,..., xn). Сечение функции фд произвольной прямой ОТ не параллельной оси xn+i совпадает на бесконечных классах эквивалентности с сечением функции фf, образованном прямой ОТ , проекцией ОТ на гиперплоскость хп+\ = О, а значит образует функцию из класса Ф(1). Сечения функции фд прямыми параллельными оси жп+1 представляют собой постоянные функции, которые по определению являются С-фипитными функциями от 1 переменной. Итак, доказано, что фд Є Ф, значит д Є ФЬ, так как д = фд + . Обратно, пусть /(#i,..., хп) получена из д(х\,..., хп+і) Є ФЬ изъятием фиктивной переменной хп+\. По определению д(хъ ..., хп+і) = фд(хі,..., xn+i)+lg(xi,..., хп+1), фд Є Ф, Ід Є L. Рассмотрим ф/(хі, .., жп) := f(xi,..., xn)—lg(xi, ...,хп, 0). произвольное сечение функции ф; прямой ОТ: Х\ = CL\t + bi, ..., хп = ant + Ъп совпадает с сечением фд прямой ОТ : ж і = ait + bi,... ,хп = ant + bn, xn+i = 0, а значит, как любое сечение фд прямой, лежит в классе Ф(1). Таким образом, по определению класса Ф, мы доказали, что ф$ Є Ф, а это, в силу линейности функции 1д, влечет принадлежность / классу ФЬ. 2. Докажем, что операция отождествления переменных сохраняет класс ФЬ. Пусть /(rci,..., хп) получена из д(х\,... ,хп+і) Є ФЬ отождествлением переменной хп и жп+і-По определению д{х\,..., хп+1) = фд(хъ ..., хп+1)+ 1д(х\,... ,жп+і), фд Є Ф, Ід Є L. Рассмотрим функцию ф ф/(хі, ...,хп) := f(xi, ...,хп) - lg(xi, ...,хп, хп). Произвольное сечение функции ф$ прямой 91: х\ = ait+bi,..., хп — ant+ Ьп совпадает с сечением фд прямой 91 : х\ — a\t + &i,..., жп = o-nt + 6n, хп+\ = ant + 6n, значит лежит в классе Ф(1), а функция f(xh ...,хп) = ф/(хъ ..., хп) + 1д(хи ...,хп, хп) является С-финитно-линейной. 3. Рассмотрим операцию подстановки одной функции из ФЬ в другую. Пусть функции / и д принадлежат классу ФЬ. Ввиду доказанного выше пункта 1, добавив недостающие фиктивные переменные, можно считать, что функции / и д зависят от одного набора переменных xi,..., хп.
Из С-финитности ф{х\..., хп), очевидно, будет следовать, что h Є ФЬ. Действительно, второе слагаемое (2.2) lf(xi,..., xn-i, g(xi,..., хп)) представляет собой линейную комбинацию С-фи-нитно-линейной функции д и линейных функций жі,..., хп-і, то есть является С-финитно-линейной функцией и, следовательно, представляется в виде суммы С-финитной функции и линейной. Значит, согласно (2.2), функция h представляется в виде суммы двух С-финитных функций и линейной. Сумма двух С-финитных функций по лемме 2.1 С-финитна, а значит функция h С-финитно-линейна.
Минимизация числа операций обратной связи в нейронных схемах с памятью
Докажем вспомогательную лемму: Лемма 4.2 Для любой нейронной схемы (5 , /) можно построить эквивалентную ей схему, которая получена из функциональных элементов с помощью операций суперпозиции и не более чем двух применений операции обратной связи. Начальные значения задержек блока DQ должны соответствовать вектору d(0). Начальные значения остальных задержек схемы (не входящие в блоки Н и Do) произвольны. Докажем теперь, что нейронная схема изображенная на рис. 30 будет эквивалентна исходной. То есть реализует нейронную функцию /(жі, ...,хп). Пусть для любых s s утверждение верно, докажем для s — s . По предположению индукции, в момент времени k-(s — 1) + 1 с выходов DQ на входы блока С поступает d(k (s — 1)). Тогда, по свойству 6, в моменты времени к (s — 1) + г, і = 1,..., к, на вход gi блока G\ подается значение di(k (s — 1)). Но, ввиду свойства 10, в эти моменты времени Vj = 5ij, j = 1,..., к, и по свойству 8, di(k (s — 1)) подается на вход блока В. А это по свойству 4 значит, что в момент времени t = к s на выходе В мы получаем вектор d(fc (s — 1)). По свойству 5, на входы блока Ф поступают х(к (s — 1) +1),..., х(к (s — 1) + к). По свойству 3, вход дк блока ( равен f(xi,..., хп)(1), а, по свойствам 10 и 9, выход всей схемы равен д . Так же, по свойству 3, на вход Do подается значение d(k s ). Наконец, по свойству 7, в момент времени t = к s + 1 на выходе блока Do получаем вектор d{k s ).
Докажем теперь индукцией по г, что в любой момент времени t = к s + i, s = 0,1,2,..., г = 1,..., к — 2 на входы блока Di подается вектор d(k s + і), а на выходе блока ( в моменты времени t = к s + г, s = 0,1, 2,..., г = 1,..., к — 1 получаем /( 1,... ,xn)(t), то есть значение выхода исходной схемы в момент времени t. Итак, в при г — 1, t = к s + 1 мы показали, что на выходе блока DQ получается d(k s), а значит по свойству 1 на входы D\ поступает d(k s + 1), вход д\ блока G i равен f(x\,..., ж„)(1). А используя свойства 10 и 9, получаем значение входа д\ на выходе Gi
Используя лемму 2, построим по измененным каноническим уравнениям (4.2) нейронную схему, эквивалентную исходной, дважды применяя операцию обратной связи. Попытаемся получить действие блока Н из общей схемы. То есть реализуем блок к нейронных функций, который в момент времени t = k-s + i выдает 1 на выходе г, а на остальных выходах - 0.
Для этого рассмотрим произвольную функцию S(x) Є 3, S : Rn — К. По определению множества Р существует нейронная схема с умножением без памяти (S,S(x)). Докажем, что S(x) является кусочно-полиномиальной. Проведем доказательство методом математической индукции по построению нейронной схемы с умножением (5, 5(ж)). дс, Еп(жі,..., хп), 6(х) — кусочно-линейные, а значит и кусочно полиномиальные, так как линейная функция является полиномиальной, гиперплоскости являются полиномиальными поверхностями. М(х\,Х2) = х\Х2 — полиномиальна, а следовательно и кусочно-полиномиальна с одним классом эквивалентности.
Добавлением фиктивного входа получаем схему, реализующую функцию / : Rn+1 — R тождественно равную /. Поверхности Pi,..., Pk являются полиномиальными поверхностями в Rn+1 и полиномиальные функции на классах эквивалентности Ri,...,Rn так же являются полиномиальными в Жга+1. Таким образом, f кусочно-полиномиальна в Rn+1. Не ограничивая общности считаем, что вход, соответствующий переменной хп, является фиктивным. Рассмотрим не пустые множества, полученные сечением поверхностей Pi,..., Pf- гиперплоскостью хп = 0. Обозначим их P[,..., P k,. Они являются полиномиальными поверхностями в М"-1 и разбивают Жп 1 на классы эквивалентности, являющимися сечениями R\,..., Rs гиперплоскостью хп = О, а значит на них f (xi,..., xn-i) = f(x\,..., xn-i, 0) полиномиальна. Аналогично предыдущему случаю, сечения Pi,..., Рп ги перплоскостью Xi — Xj = 0 образуют полиномиальные поверх ности в R"-1 (переменные xi,..., Xi,..., Xj-i, Xj+i,..., хп), ко торые разбивают Wl l на классы эквивалентности, являющи мися не пустыми сечениями Ri,..., Rs гиперплоскостью Xi — Xj — 0. А значит на них f (xi,... ,ХІ, ..., Xj_i, Xj+i,..., xn) = f(xi,..., Xf,..., Xj-i, Xi, Xj+i,..., xn) полиномиальна. Переименование входов нейронной схемы приводит к переименованию переменных функции, что сохраняет ее кусочно-полиномиальный вид. Пусть Р[,..., Р[ — полиномиальные поверхности в Rm задающие кусочно-полиномиальную функцию к(х г,... ,х т). Тогда добавим в (Si, h) фиктивные входы xi,..., хп, а в (S /) соответственно x i,...,x m. Таким образом, /їй/ — кусочно-полиномиальные функции переменных x i,..., х т, Xi, ..., хп. Поверхности Pi,..., Pk, Р[,..., Р[ разбивают Жт+п на классы, где функции h и / полиномиальны. Операция 5 на любом классе эквивалентности (разбиения Em+n полиномиальными поверхностями Pi,..., Pk, Р{,..., P t) есть суперпозиция полиномиальных функций, то есть полиномиальна.
Можем обобщить результаты разделов 4.1 и 4.2 на нейронные схемы с умножением, так как для доказательства леммы 4.1 важен лишь вид канонических уравнений, а не природа функций 2", Фі,..., Фь Для перечисленных функций необходима представимость в виде нейронных схем без памяти (в данном случае с умножением), что гарантируется леммой 4.3. Итак, повторяя доказательство леммы 4.1 с учетом указанных замечаний получаем: Лемма 4.4 1) Любая нейронная схема с умножением задает нейронную функцию с умножением. 2) Любая нейронная функция с умножением задается некоторой нейронной схемой с умножением. Аналогично, с помощью нейронной схемы изображенной на рис. 31, можно реализовать любую нейронную функцию с умножением, где блоки Ф, i7!,..., Fk-\ построены по лемме 4.3 методом, описанным в лемме 4.2, из кусочно-полиномиальных функций Z, Фі,..., Ф&. То есть верна теорема:
