Аппроксимация функций многих переменных ИНС

Лекция 6 Тема: Аппроксимация функций многих переменных ИНС 1. Проблемы представления функции многих переменных с помощью функций одного переменного Зададимся вопросом: какие функции человек наверняка может вычислять? Если мы умеем складывать и умножать рациональные дроби (а это мы умеем), то можно точно вычислять многочлены и рациональные функции (отношения многочленов) с рациональными коэффициентами от рациональных же аргументов. Можно, однако, задавать функции с помощью уравнений. Если считать решения нескольких простых уравнений известными, то класс вычисляемых функций расширится – решения некоторых более общих уравнений удастся выразить через эти более простые функции. Классический пример: если использовать радикалы – решения уравнений n x = а, то можно явно получить решения произвольных уравнений второй, третьей и четвертой степеней. Так, функция трех переменных а, b, с — решение уравнения ax2 + bx + с = 0 – может быть точно выражена с помощью сложения, умножения, деления и функции одного переменного – квадратного корня. Эта формула знакома всем из курса алгебры средней школы. Намного более громоздкие и неизучаемые в школе формулы (но все же формулы с радикалами!) существуют для уравнений третьей и четвертой степени. Вопрос: можно ли представить решение любого алгебраического уравнения с помощью радикалов – был окончательно и отрицательно решен Н.Х. Абелем и Э. Галуа в прошлом веке: уже уравнения пятой степени неразрешимы в радикалах. Все же можно пытаться подбирать другие функции небольшого числа переменных – сложнее, чем радикалы, но проще, чем общие решения уравнений высоких степеней. Удастся ли с помощью этих функций построить решение любого уравнения? Вопрос был настолько важен, что Дж. Гильберт в списке своих проблем, которые, по его мнению, должны были определять развитие математикиXX века, под номером 13 поместил следующую задачу: Представляется ли корень уравнения x7 + ax3 + bx2 + cx + 1 = 0 (как функция коэффициентов) суперпозицией каких- либо непрерывных функций двух переменных? , В приведенной формулировке неявно предлагается и ответ на вопрос: что означает “представить одну функцию с помощью других”? Он прост: это означает, что можно подставлять значения известных функций в другие известные функции в качестве аргументов (операция суперпозиции). В результате получаем новые функции, представленные с помощью известных. Так, например, функция пяти переменных F(x1 , x2, x3, x4, x5) = f1(f1(x1, x2),f2(x3,f1(x4, x5))) представлена с помощью двух функций двух переменных f1 и f2 и операции суперпозиции (подстановки функции в функцию). Для решений уравнений пятой и шестой степени такое представление возможно не только с помощью непрерывных, но даже аналитических функций. (Напомним, что аналитической в некоторой области D называется функция, которая в окрестности каждой точки D представима сходящимся степенным рядом. Аналитические функции имеют производные всех порядков и обладают еще многими “естественными” полезными свойствами. Оказалось полезным отвлечься от уравнений и поставить общий вопрос: можно ли произвольную непрерывную функцию n переменных получить с помощью операций сложения, умножения и суперпозиции из непрерывных функций двух переменных? Ответ оказался положительным! В серии работ А.Н. Колмогоров, затем В.И. Арнольд и вновь А.Н. Колмогоров [1, 3] решили эту проблему: можно получить любую непрерывную функцию n переменных с помощью операций сложения, умножения и суперпозиции из непрерывных функций одного переменного. Последняя теорема А.Н. Колмогорова из этой серии настолько проста и изящна, что мы чуть позже приведем ее формулировку целиком. А пока несколько замечаний об условиях теоремы. От условия непрерывности можно отказаться, тогда получится довольно тривиальный результат, связанный по существу с равномощностью отрезка и куба любой размерности. Условие непрерывности нельзя значительно усилить: уже существование производных (дифференцируемость) существенно осложняет дело. Нельзя представить все l раз непрерывно дифференцируемые функции трех переменных в виде суперпозиций функций двух переменных, каждая из которых дифференцируема [2l/3] + 1 раз (выражение [2l/3] означает целую часть числа 2l/3). Это доказано А.Г. Витушкиным [2]. А теперь теорема, завершившая серию исследований для непрерывных функций. Теорема Колмогорова. Каждая непрерывная функция n переменных, заданная на единичном кубе n-мерного пространства, представима в виде (1) где функции hq(u) непрерывны, а функции φp(xp), кроме того, еще и стандартны, то есть не зависят от выбора функции f. В частности, каждая непрерывная функция двух переменных x, y представима в виде (2) Эта теорема не только элегантна, но и проста. Ее доказательство элементарно изложено в блестящей статье В.И. Арнольда [3]. Обсудим содержание теоремы. В n-мерном пространстве вводится 2n + 1 специальных (и весьма экзотических) координат (на плоскости их пять). Они являются функциями вида (3) при различных q = 1, 2, ..., 2n + 1 от обычных координат x1, x2, ..., xn. Любая непрерывная функция представляется как сумма непрерывных функций от отдельных координат, и в эту сумму входит не более одной функции для каждой координаты (3). Всюду речь идет именно о непрерывных функциях – таких гладких координатных функций не существует, функции φpq(xp), построенные Колмогоровым, не имеют производных, хотя и непрерывны (с точки зрения обычной физической интуиции это функции-монстры, которые трудно себе представить). Так существуют ли функции многих переменных? В каком-то смысле нет: в классе непрерывных функций достаточно использовать только функции одного переменного, суперпозицию функций и сложение и за конечное число операций мы получим точное выражение любой функции многих переменных. Для более узкого класса дифференцируемых функций это уже не так. 2. Приближенное представление функций с помощью более простых: теоремы Вейерштрасса и Стоуна В 13-й проблеме Гильберта и теореме Колмогорова речь шла о точном представлении функций многих переменных с помощью функций одного переменного. Оказалось, что в классе непрерывных функций такое представление возможно. Но кроме вопроса о точном представлении существует еще один – об аппроксимации. Можно даже предположить, что он важнее – вычисление большинства функций производится приближенно даже при наличии точных формул. Приближение функций многочленами и рациональными функциями имеет историю, еще более давнюю, чем проблема точного представления. Знаменитая теорема Вейерштрасса утверждает, что непрерывную функцию нескольких переменных f(x1, x2, ..., xn) на замкнутом ограниченном множестве Q можно равномерно приблизить последовательностью полиномов: для любого ε > 0 существует такой многочлен P (x1, x2, ..., xn), что максимум его отклонения от f(x1, x2, ..., xn) на Q не превосходит данного ε: Примечание. Здесь и далее мы будем использовать выражения “замкнутое ограниченное множество” и “компактное пространство X”. Можно представлять себе просто n-мерный прямоугольный параллелепипед – множество наборов переменных (x1, x2, ..., xn), удовлетворяющих неравенствам ai < x i < bi для некоторых чисел a i < bi . Чтобы сформулировать обобщения и усиления теоремы Вейерштрасса, необходимо перейти к несколько более абстрактному языку. Рассмотрим компактное пространство X и множество C(X) непрерывных функций на X с вещественными значениями. Произведение непрерывной функции на число, суммы и произведения непрерывных функций также являются таковыми. Это означает, что C(X) образует алгебру. Если X – n-мерный прямоугольный параллелепипед, то теорема Вейерштрасса о равномерном приближении функций многочленами может быть сформулирована так. Пусть – подалгебра в C(X), 1∈E и координатные функции (fi ≡ xi) принадлежат E. Тогда E плотно в C(X), то есть любая непрерывная функция на X может быть сколь угодно точно равномерно приближена элементами из E. Действительно, E – подалгебра, то есть суммы и произведения элементов E принадлежат E. Координатные функции принадлежат E, следовательно, любые их суммы, произведения, суммы произведений, то есть все многочлены, принадлежат E. По теореме Вейерштрасса это E плотно в C(X). Пусть далее X – произвольное компактное пространство. Сильным обобщением теоремы о возможности равномерного приближения непрерывных функций многочленами является Теорема Стоуна [4, 5]. Пусть – подалгебра в C(X), 1∈E и функции из E разделяют точки в X (то есть для любых различных x, y ∈ X существует такая функция g ∈ E, что . Тогда E плотно в C(X), то есть любая непрерывная функция на X может быть сколь угодно точно равномерно приближена элементами из E. Теорема Стоуна обобщает теорему Вейерштрасса по двум направлениям. Во-первых, рассматриваются функции на произвольном компакте, но не это самое важное. Во-вторых, доказано утверждение, новое даже для функций одного переменного (не говоря уже о многих): плотно не только множество многочленов от координатных функций, но вообще кольцо многочленов от любого набора функций, разделяющих точки. Следовательно, например, плотно множество тригонометрических многочленов. А вот и другой пример, очень важный для многих приложений. Рассмотрим всюду отрицательные (неположительные) многочлены второго порядка от нескольких переменных Q(x). Сумма таких многочленов тоже отрицательный (неположительный) многочлен второго порядка. Пусть E – множество линейных комбинаций вида где Ai– числа, e – основание натуральных логарифмов. (4) Легко проверить, что E – подалгебра в C(X), а множество функций из E вида при всевозможных ai разделяет точки в n-мерном пространстве (значение такой функции в точке a больше, чем во всех других точках). Поэтому множество линейных комбинаций (4) плотно среди непрерывных функций на любом ограниченном замкнутом множестве. Теорема Стоуна дает рецепт конструирования конкретных обобщений теоремы Вейерштрасса: достаточно взять произвольный набор функций, разделяющих точки, построить все многочлены от них и получится плотное в C(X) множество функций. 3. Представление функций с помощью нейронных сетей Кроме аппроксимации функций многочленами и их обобщениями из колец функций, разделяющих точки, в последнее время все большее внимание уделяется приближению функций многих переменных с помощью линейных операций и суперпозиций функций одного переменного. Такое приближение осуществляется специальными формальными устройствами – нейронными сетями. Каждая сеть состоит из формальных нейронов. Нейрон получает на входе вектор сигналов x, вычисляет его скалярное произведение на вектор весов а и некоторую функцию одного переменного φ(x, а). Результат рассылается на входы других нейронов или передается на выход. Таким образом, нейронные сети вычисляют суперпозиции простых функций одного переменного и их линейных комбинаций. Одна из наиболее распространенных задач, решаемых с помощью нейронных сетей, состоит в оценивании и аппроксимации по нескольким точкам (примерам) функций вход-выход для решения в дальнейшем задачи прогноза неизвестных значений выходов по известным входам. Актуальным становится вопрос о том, какие функции могут быть аппроксимированы с их помощью. Для описания алгоритмов и устройств в нейроинформатике выработана специальная схемотехника, в которой элементарные устройства – сумматоры, синапсы, нейроны и т.п. – объединяются в сети, предназначенные для решения задач. Интересен статус этой схемотехники. Для многих начинающих кажется неожиданным, что ни в аппаратной реализации нейронных сетей, ни в профессиональном программном обеспечении все эти элементы вовсе не обязательно реализуются как отдельные части или блоки. Используемая в нейроинформатике идеальная схемотехника представляет собой особый язык для представления нейронных сетей и их обсуждения. При программной и аппаратной реализации выполненные на этом языке описания переводятся на языки другого уровня, более пригодные для реализации. Самый заслуженный и, вероятно, наиболее важный элемент нейросистем – это адаптивный сумматор. Он вычисляет скалярное произведение вектора входного сигнала x на вектор параметров α. На схемах будем обозначать его так, как показано на рис. 1. Рис. 1. Адаптивный сумматор Адаптивным называем его из-за наличия вектора настраиваемых параметров α. Для многих задач полезно иметь линейную неоднородную функцию выходных сигналов. Ее вычисление также можно представить с помощью адаптивного сумматора, имеющего n + 1 вход и получающего на 0-й вход постоянный единичный сигнал (рис. 2). Рис. 2. Неоднородный адаптивный сумматор Нелинейный преобразователь сигнала изображен на рис. 3. Он получает скалярный входной сигнал x и переводит его в φ (x). Рис. 3. Нелинейный преобразователь сигнала Точка ветвления служит для рассылки одного сигнала по нескольким адресам. Она получает скалярный входной сигнал x и передает его всем своим выходам. Стандартный формальный нейрон составлен из входного сумматора, нелинейного преобразователя и точки ветвления на выходе (рис. 4). Линейная связь – синапс отдельно от сумматоров не встречается, однако для некоторых рассуждений бывает удобно выделить этот элемент. Он умножает входной сигнал x на “вес синапса” α. Итак, дано описание основных элементов, из которых составляются нейронные сети. Перейдем теперь к вопросу: как можно составлять эти сети? Строго говоря, как угодно, лишь бы входы получали какие-нибудь сигналы. Рис. 4 Но такой произвол необозрим, поэтому используют несколько стандартных архитектур, из которых путем вырезания лишнего или (реже) добавления строят большинство используемых сетей. Сначала следует договориться о том, как будет согласована работа различных нейронов во времени. Как только в системе возникает более одного элемента, встает вопрос о синхронности функционирования. Для привычных нам всем программных имитаторов нейронных сетей на цифровых ЭВМ такого вопроса нет только из-за свойств основного компьютера, на котором реализуются нейронные сети. Для других способов реализации такой вопрос весьма важен. Все же здесь и далее рассматриваются только нейронные сети, синхронно функционирующие в дискретные моменты времени: все нейроны срабатывают разом. В зоопарке нейронных сетей можно выделить две базовые архитектуры: слоистые и полносвязные сети. Слоистые сети. Нейроны расположены в несколько слоев. Нейроны первого слоя получают входные сигналы, преобразуют их и через точки ветвления передают нейронам второго слоя. Далее срабатывает второй слой и т.д. до k-го слоя, который выдает выходные сигналы для интерпретатора и пользователя. Если не оговорено противное, то каждый выходной сигнал i-го слоя подается на вход всех нейронов (i + 1)-го. Число нейронов в каждом слое может быть любым и никак заранее не связано с количеством нейронов в других слоях. Стандартный способ подачи входных сигналов: все нейроны первого слоя получают каждый входной сигнал. Особое распространение получили трехслойные сети, в которых каждый слой имеет свое наименование: первый — входной, второй — скрытый, третий — выходной. Полносвязные сети. Каждый нейрон передает свой выходной сигнал остальным нейронам, включая самого себя. Выходными сигналами сети могут быть все или некоторые выходные сигналы нейронов после нескольких тактов функционирования сети. Все входные сигналы подаются всем нейронам. Элементы слоистых и полносвязных сетей могут выбираться по-разному. Существует, впрочем, стандартный выбор – нейрон с адаптивным неоднородным линейным сумматором на входе (см. рис. 4). Для полносвязной сети входной сумматор нейрона фактически распадается на два: первый вычисляет линейную функцию от входных сигналов сети, второй – линейную функцию от выходных сигналов других нейронов, полученных на предыдущем шаге. Нейронные сети вычисляют линейные функции, нелинейные функции одного переменного, а также всевозможные суперпозиции – функции от функций, получаемые при каскадном соединении сетей. Что можно получить, используя только такие операции? Какие функции удастся вычислить точно, а какие функции можно сколь угодно точно аппроксимировать с помощью нейронных сетей? Чтобы изучить возможности нейронных сетей, нужно ответить на эти вопросы [6, 7]. Каждый выходной сигнал нейронной сети будем рассматривать как вычисляемую этой сетью функцию от ее входных сигналов. Пусть задана функция активации нейронов (характеристическая функция) φ — нелинейный преобразователь, преобразующий выходной сигнал сумматора (см. рис. 4). Зададимся вопросом: какие функции могут быть вычислены сетями с данной функцией активации. Множество этих функций обладает следующими свойствами: оно является линейным пространством (так как можно вычислить линейную комбинацию выходных сигналов нескольких сетей с помощью дополнительного сумматора), содержит константы и координатные функции, а также вместе с любой функцией f и суперпозицию φ(f). Оказывается, что отсюда следует, что множество таких функций плотно среди всех непрерывных функций на любом замкнутом ограниченном множестве. Это доказывается на основе следующей обобщенной теоремы Стоуна. Пусть E∈C(X) – линейное пространство, C(R) – пространство непрерывных функций на действительной оси R, f ∈ C(R) – нелинейная функция и для любого g ∈ E выполнено f(g) ∈ E. В этом случае будем говорить, что E замкнуто относительно нелинейной унарной операции f. Очевидный пример: множество функций n переменных, которые можно точно представить, используя заданную функцию f одного переменного и линейные функции, является линейным пространством, замкнутым относительно нелинейной унарной операции f. Замечание. Линейное пространство E ⊆ C(X) замкнуто относительно нелинейной операции f(x) = x2 тогда и только тогда, когда E является подалгеброй в C(X). Действительно, fg = 1/2[(f + g)2 - f2 - g2], поэтому для линейного пространства E ⊆ C(X) замкнутость относительно унарной операции f(x) = x2 равносильна замкнутости относительно произведения функций. Согласно приведенному замечанию, теорема Стоуна может быть переформулирована так. Пусть E ⊆ C(X) – линейное подпространство в C(X), 1∈E, функции из E разделяют точки в X и E замкнуто относительно нелинейной унарной операции f(x) = x2. Тогда E плотно в C(X). Требуемое обобщение теоремы Стоуна состоит в замене f(x) = x2 на произвольную нелинейную непрерывную функцию. Обобщенная аппроксимационная теорема. Пусть E ⊆ C(X) – линейное подпространство в C(X), 1 ∈ E, функции из E разделяют точки в X и E замкнуто относительно нелинейной унарной операции f ∈ C(R). Тогда E плотно в C(X). Эту теорему можно трактовать как утверждение об универсальных аппроксимационных свойствах любой нелинейности: с помощью линейных операций и каскадного соединения можно из произвольных нелинейных элементов получить любой требуемый результат с любой наперед заданной точностью [7]. В доказательстве есть только одна нетривиальная идея – рассмотреть все нелинейные операции f ∈ C(R), относительно которых замкнуто E, и показать, что это множество операций совпадает со всем пространством непрерывных функций. Дальнейшее – дело техники. Любопытно, что исследование таких множеств операций было начато более 35 лет назад [8]1 вне какой-либо связи с задачами приближения функций – поучительный пример потенциальной полезности абстрактных математических конструкций. Это интерпретируется как утверждение об универсальных аппроксимационных возможностях произвольной нелинейности: с помощью линейных операций и единственного нелинейного элемента ϕ можно получить устройство, вычисляющее любую непрерывную функцию с любой желаемой точностью. Однако данная теорема ничего не говорит о количестве слоёв нейронной сети (уровней вложенности суперпозиции) и о количестве нейронов, необходимых для аппроксимации произвольной функции. Таким образом, нейронные сети являются универсальными аппроксиматорами функций. Возможности сети возрастают с увеличением числа слоёв и числа нейронов в них. Двух-трёх слоёв, как правило, достаточно для решения подавляющего большинства практических задач классификации, регрессии и прогнозирования. Обобщенная аппроксимационная теорема об универсальных свойствах любой нелинейности является одним из математических оснований для коннекционизма: неважно, какая нелинейная функция используется в нейроне, существенны лишь факт нелинейности и свобода в построении системы связей. Список литературы: 1. Колмогоров А.Н. О представлении непрерывных функций нескольких переменных в виде суперпозиции непрерывных функций одного переменного // Докл. АН СССР. 1957. Т. 114, № 5. С. 953-956. 2. Витушкин А.Г. О многомерных вариациях. М.: Физ- матгиз, 1955. 3. Арнольд В.И. О представлении функций нескольких переменных в виде суперпозиции функций меньшего числа переменных // Мат. просвещение. 1958. Вып. 3. С. 41-61. 4. Stone M.N. The Generalized Weierstrass Approximation Theorem // Math. Mag. 1948. Vol. 21. P. 167-183, 237-254. 5. Шефер Х. Топологические векторные пространства. М.: Мир, 1971. 6. Cybenko G. Approximation by Superposition of a Sigmoidal Function // Mathematics of Control, Signals and Systems. 1989. Vol. 2. P. 303-314. 7. ГорбаньА.Н., РоссиевД.А. Нейронные сети на персональном компьютере. Новосибирск: Наука, 1996. 8. Leeuw K., Katznelson Y. Functions that Operate on Non-Self-Adjoint Algebras // J. d’Anal. Math. 1963. Vol. 11. P. 207-219. 9. Уидроу Б., Стирнз С. Адаптивная обработка сигналов. М.: Мир, 1989. 440 с.