Макаренко Н. - Фракталы, аттракторы, нейронные сети и все такое
РОССИЙСКАЯ АССОЦИАЦИЯ НЕЙРОИНФОРМАТИКИ. МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
Введение
Предлагаемый фрагмент из еще не завершенного романа публикуется досрочно в качестве раздумья об исподней сущности переживаемого момента, чем и как может он обернуться нам под воздействием нашей неосторожности
Леонид Леонов Мироздание по Дымкову
Все фигуры, которые я исследовал и назвал фракталами, в моем представлении обладали свойством быть нерегулярными, но самоподобными, писал Бенуа Мандельброт, который в 1975 году ввел термин фрактал (от латинского fractus дробный). Позднее оказалось, что фракталами являются и давно известные в анализе нерегулярные функции, вызывавшие отвращение аналитиков прошлого века1 2. Процесс построения классических фракталов, таких как множество Кантора или ковер Сер-пинского, который можно принять за их определение, предельно прост. Сперва следует выбрать основную процедуру-генератор, а затем итеративно, до бесконечности применять ее к произвольному компакту.
То, что получится в пределе это и есть фрактал. Идея о том, что объектами геометрии могут быть предельные образы итеративной динамики, не вызывала особого восторга. Можно представить себе (и даже изобразить) на вещественной оси предел числовой последовательности. Однако, мускулы нашего тренированного воображения отказывают, когда пределом является компактный глобально несвязный объект, зачастую обладающий инфернальными свойствами: во многих случаях у него нет даже тени!
Да и сами процедуры генерации фрактала напоминали скорее хирургию с элементами садизма, нежели приемы аналитики. Фракталы были чужды уютному евклидову миру с его регулярными структурами.
'Если ссылка на примечание представляет собой число, заключенное в круглые скобки, например, (3), то она обозначает номер примечания, помещенного в конце данного текущего раздела. Ссылка в виде числа, не заключенного в такие скобки обычное подстраничное примечание.
Прим. ред.
2С омерзением и ужасом я отворачиваюсь от этой зловредной язвы непрерывных функций, нигде не имеющих производных, писал Эрмит Стилтьесу в 1893 году.
Ситуация изменилась в 1981 году, когда Хатчинсон поместил пришельцев в их родную среду пространство компактов. Именно здесь Система Итеративных Функций (СИФ) сжимающих отображений, порождает фракталы простым и естественным путем, при котором ампутация отдельных фрагментов связных множеств трансформируется в корректную форму непрерывного сжатия в подходящей метрике. Реминисценции, навеянные предельной динамикой СИФ, ведут к теории дискретных динамических систем. Аналогами аффинных СИФ являются здесь нелинейные преобразования, порожденные, например, сечениями Пуанкаре многомерных фазовых потоков.
Нелинейность приводит к существенной зависимости от начальных данных так, что малые погрешности экспоненциально растут в фазовом потоке и, начиная с некоторого момента времени, будущее состояние системы становится лишь ограниченно предсказуемым. Этот процесс чаще всего происходит в диссипативных системах, траектории которых заполняют низкоразмерное инвариантное притягивающее подмножество аттрактор в фазовом пространстве.
На аттракторе траектории разбегаются в неустойчивых направлениях и сжимаются в устойчивых. Вследствие диссипации сжатие преобладает и в устойчивых направлениях аттрактор копирует сам себя: сечение фазового потока приобретает самоподобную структуру канторова множества с дробной размерностью.
Такой аттрактор называют странным или фрактальным.
Самоподобная структура фрактала позволяет восстановить СИФ по фрагменту, по крайней мере, в приближении конечного числа итераций. В 1991 году Бресслофф и Штарк показали, что процесс аппроксимации аттрактора СИФ эквивалентен работе бинарной нейронной сети. Таким образом, термины фрактал в геометрии и странный аттрактор в динамике оказываются синонимами, а СИФ можно рассматривать как рекуррентную асимметричную нейросеть. С другой стороны, Фернандо Ниньо в 2000 году установил, что случайная итеративная нейронная сеть (гипернейрон) топологически эквивалентна динамической системе с заданным аттрактором.
Круг замкнулся, образовав Единый Контекст, объединяющий фракталы, СИФ, аттракторы и нейронные сети. Цель лекции показать взаимную связь этих предметов, потому что единое лучше, чем все вместе, но по-отдельности.
Более серьезные мотивы указаны в эпиграфе ко введению.
Основой предлагаемой Лекции послужили Заметки о фракталах3 и доклады автора на Фрактальном семинаре Института математики. В тексте опущены все доказательства, и это дает читателю восхитительную возможность видеть, но не верить!
Поскольку предварительных знаний не всегда хватает как раз для понимания предварительных сведений они помещены в конце текста, в Глоссарии. Он не обязателен для понимания основного текста: если вас начинает смущать терминология, следуйте простому правилу: никогда не жуйте пилюлю, которую вас заставляют проглотить.
В конце каждого раздела помещен путеводитель по Литературе, список которой совсем не претендует на полноту.
Автор искренне благодарен своим молодым коллегам: Светлане Ким, Кате Данилкиной и Ерболу Куандыкову, которые взяли на себя неблагодарный труд по набору и редактированию Лекции.
Размерности, площади и объемы
Необходимо число, различитель инаковости, без которого невозможно отличить одно от другого
Николай Кузанский Игра в шар
Мы начнем с идей итальянского математика Никколо Фонтана Тарта-лья (1500-1557 гг.). Известно, что на три неколлинеарные точки плоскости можно натянуть треугольник, а четырем некомпланарным точкам в R соответствует тетраэдр. Это выпуклые геометрические тела, для которых существует мера площади и объемы.
Согласно Тарталья, пространство является n-мерным, если для его n + 1 точек, не принадлежащих одной гиперплоскости, существует полиэдр ненулевого объема. Наиболее существенным здесь является то, что в основу определения размерности было положено понятие меры: именно этот момент служит основой современных конструкций.
В этом определении неявно используется предположение, что необходимые n + 1 точки могут быть всегда выбраны так, чтобы они не принадлежали одной гиперплоскости. Однако принцип общего положения, который столь широко используется в
современной математике, требует по меньшей мере понятий непрерывного отображения и многообразия. Поэтому последующие определения размерности рассматривались в именно в таком контексте.
До появления стандартной терминологии произвольное гладкое многообразие называли просто непрерывностью. Понятие размерности вводилось аналитически как минимальное число параметров, необходимых для идентификации точки в непрерывности.
На привычном физическом языке это n координат точки в Rn. Однако почти сразу же оказалось, что эта параметрическая размерность неудовлетворительна по нескольким причинам. Прежде всего выяснилось, что такое определение не различает прямую и плоскость, поскольку между ними можно установить однозначное соответствие. Впервые это показал Георг Кантор, используя следующие соображения.
Пусть точка x = (x1;x2) € I = [0,1] х [0,1]. Ее координаты 0 ^ x1;x2 ^ 1 можно представить в виде бинарных дробей: x1 = 0, а1а2...; x2 = 0,f31f32..., где в нули либо единицы. Для обеспечения единственности условимся записывать обрывающиеся разложения так, чтобы все двоичные цифры, начиная с некоторого места были тогда нулями.
Сопоставим паре разложений x1 и x2 последовательность z = 0,а1в1а2р2..., наследующую лексикографический порядок исходных оригиналов. Мы получили отображение z : I ^ [0,1]. Следовательно, существует способ параметризации точек плоскости только одной координатой извилистой линией!
Разумеется, это возможно лишь в том случае, если мы не связываем себя условием непрерывности так, чтобы двум бесконечно близким точкам прямой, соответствовали две бесконечно близкие точки плоскости. Анри Пуанкаре заметил, что отказ от непрерывности трудно примирить с интуитивными логическими принципами(1). То, что было предложено им взамен, основано на весьма остроумной концепции физической непрерывности.
Здесь аналогом точки является элемент, неотличимый от соседних, но совокупность таких элементов образует непрерывную цепь, оба конца которой легко различимы. Размерность непрерывности вводится с помощью понятия купюры. Последняя образуется совокупностью элементов, изъятых из непрерывности. Если в результате такой операции непрерывность разделяется на две части, а сама купюра состоит лишь из конечного числа элементов, не образующих связного множества, то размерность непрерывности равна единице.
Например, линия одномерна, потому что делится на две части нуль-мерной купюрой точкой. Для того, чтобы разделить плоскость, необходима одномерная купюра линия и т. д. Таким образом, математическая непрерывность имеет n измерений, если ее можно разбить на части, произведя в ней одно или несколько сечений, которые сами являются непрерывностями n 1 измерения.
Это рекуррентное определение размерности, которое предполагает, что объемы части пространства, поверхности границы объемов, линии границы поверхностей, а точки границы линий.
Формализация этих идей привели Брауэра, Урысона и Менгера к индуктивному определению топологической размерности. Размерность любого конечного или счетного множества точек есть dt = 0. Размерность любого связного множества точек есть dt + 1, если его можно разрезать на два несвязных куска, исключив как минимум dt-мерное множество точек, т. е. сделав dt-мерный разрез(2).
Ясно, что топологическая размерность всегда есть целое число.
Следующее понятие размерности опирается на идею покрытия и практические способы вычисления длин и площадей, предложенные еще Борхардом и Минковским. Рассмотрим плоскую кривую C, имеющую в каждой точке непрерывную касательную.
Начнем перемещать отрезок длины 2е так, чтобы его середина двигалась вдоль кривой, а сам он оставался нормалью: касательная определена, следовательно определена и нормаль. Отрезок заметает площадь S(e) (мы считаем, конечно, что площадь существует). То, что получается при этом, называется шарфом Минковского.
При довольно широких допущениях можно показать, что существует lim S(e)/2e, при е ^ 0, который мы и назовем длиной C. Аналогичным образом можно определить площадь как предел: lim V(е)/2е, е ^ 0, где V(е) объем тела (сосиски Минковского), заметаемого отрезками 2e, нормальными к поверхности.
Таким образом, меру геометрического объекта некоторой размерности можно определить как скорость изменения меры другого объекта, большей размерности, покрывающего исходный, при линейном убывании некоторого характерного масштаба. Заметим, что это определение не зависит от выбора координат.
Для определения размерности используется следующее обобщение. Регулярный многомерный объект можно представить в форме прямого произведения объектов низшей размерности. Тогда его мера (объем) выражается в виде степени характерного размера элемента покрытия edim.
Для сохранения аддитивности меры удобнее перейти от покрытия к разбиению. Степенная зависимость меры от е называется скейлингом.
Тогда размерность (dim) можно определить как скорость изменения меры при измельчении разбиения т. е. уменьшения е по степенному закону. Поскольку при этом нас интересует только функциональная связь, вместо суммарного объема элементов разбиения (покрытия) часто используют число таких элементов. Покрытия (разбиения) можно реализовать многими способами. Поэтому для получения корректных численных оценок берется минимальное число элементов покрытия или разбиения.
В последнем случае подсчитываются только непустые кубы или шары.
Все эти соображения лежат в основе размерности по Колмогорову, которую чаще называют емкостью. Пусть (M, р) полное метрическое пространство с метрикой р и dim M = d. Рассмотрим непустое компактное подмножество F С M. Для е 0 пусть B(x,e) замкнутый d-мерный шар с центром в точке x G M.
Подсчитаем наименьшее число N(е) таких шаров, необходимых для покрытия F: N(е) = наименьшему целому m такому, что F С U mB(xn, е) для {xn | n = 1,2,, m} С M. Такое число всегда существует, потому что F компакт, т. е. ограниченное и замкнутое множество. Следовательно, из каждого его бесконечного покрытия можно выбрать конечное подпокрытие.
Тогда искомое число есть минимальная длина всех таких конечных последовательностей.
Если существует скейлинг N(е) ~ е-^с при е ^ 0 , то dc колмогоровская емкость множества. Заметим, что dc ^ d и не обязательно целое число! Это на первый взгляд кажется парадоксальным, потому что мы использовали d-мерные шары, где d целое число. Однако, dc определяется из скейлинга, который выполняется асимптотически, в пределе исчезающих е. Для корректного определения dc следует учесть еще нормировку, равную объему d-мерной единичной сферы V(1).
Тогда емкость можно определить как такое число dc, при котором существует отличный от нуля предел(3): lim{V(1)N(е)е^} при е ^ 0. При использовании кубов вместо шаров необходимость в нормировке исчезает.
Размерность Хаусдорфа dH отличается от емкости тем, что следует брать разные шары, радиус которых ті е. Тогда крупнозернистая а-мерная мера Хаусдорфа для любого а 0 определяется как
ma(F,e) = inf ^(ті)",
i
где inf берется по всем покрытиям. Когда е убывает, сумма возрастает или, во всяком случае, не убывает.
Поэтому предел при е ^ 0, конечный или бесконечный, существует и называется а-мерной мерой Хаусдорфа для F: ma(F) = lim?^o ma(F, е). Хаусдорфова размерность F характеризует поведение ma(F) как функцию от а:
dim# F = sup^m^F) = ж} = inf{а|ша^) = 0}.
Таким образом, dimH отделяет значения а, дающие бесконечную меру, от значений а, приводящих к нулевой мере. В качестве примера рассмотрим фрагмент кривой длины L. Ясно, что для его покрытия (разбиения) требуется N = L/е шаров. Тогда мера m = (L/e)ea = Lea-1.
Если а 1, то m ^ ж при е ^ 0. Если же а 1, то m ^ 0 при е ^ 0. Единственным правильным значением будет а = 1. Заметим, что dH для некоторых относительно простых множеств может существенно отличаться от dc. Тем не менее, мы будем использовать оба термина как синонимы, полагая dc = dH.
Приведенным выше определениям можно придать информационный смысл. Представим себе кассу из двух ящиков.
В одном из них находится монета. Очевидно необходим всего один вопрос с возможными ответами да или нет, чтобы идентифицировать ее нахождение.
Четыре ящика требуют двух вопросов, а если касса состоит из 25 = 32 ящиков, таких вопросов надо задать уже 5. На первый взгляд кажется, что каждый следующий вопрос следует выбирать только после получения ответа на предыдущий. Однако, венгерский математик Реньи показал, что можно задать всего один сложный вопрос, допускающий несколько одновременных ответов да, нет, позволяющих однозначно идентифицировать необходимый номер.
Будем считать, что информация, которую содержит один ответ, равна одному биту. Тогда для идентификации системы с N возможными и равновероятными состояниями нам необходима информация в I = log2 N = lg N бит.
Мы пришли к формуле, которую впервые получил Хартли в 1928 году.
Вопросы и ответы можно реализовать по-разному. Для нас удобно представить себе вопрос как элемент покрытия (нечто вроде фишки при игре в лото), идентифицирующий точку множества с точностью е. Если N(е) минимальное число таких элементов, I = log2 N(е) количество информации, необходимое для идентификации всего множества с той же точностью. В этом контексте размерность:
dc = lim I/ log е
является скоростью изменения информации при бесконечном увеличении разрешения.
Примечания
1. А. Пуанкаре писал по поводу концепций, не согласованных с интуицией: Они заменяют определяемый предмет и интуитивное понятие этого предмета конструкцией, сделанной из более простых материалов. Мы видим, что из этих материалов действительно можно собрать такую конструкцию, но никогда непонятно, почему собрали эти материалы именно так, а не иначе.
Я не хочу сказать, что арифметизация математики плохая вещь, я утверждаю лишь, что она не составляет всего [1]. Несмотря на указанные недостатки, параметрическая размерность осталась в физике, где она согласована с числом степеней свободы.
2. Такая размерность называется большой индуктивной размерностью Ind. Кроме того, существует малая индуктивная размерность (ind) : считают, что indX = n, если ?ж G X существует сколь угодно малая окрестность U : ж G U, граница которой dU имеет ind(dU) = n 1. Начало этой индуктивной цепочки пустое множество 0, для которого ind0 = 1.
3. Точнее, при е ^ 0 существует соотношение: N(е) к V(1)ed, в котором знак к понимается в следующем смысле. Для двух функций f и д, f (е) к д(е), если lim{ln f (е)/ lnд(е)} = 1 при е ^ 0. Поэтому емкость определяется как предел, если он вообще существует, отношения
{ln N (е) ln V (1)}/{М(1/е)}.
Очевидно, что ln V(1)/ln(1/e) ^ 0 при е ^ 0, поэтому этот член обычно опускают. Существуют две теоремы [2], которые позволяют перейти к дискретному варианту для е. Первая из них утверждает, что емкость компактного подмножества F совпадает с пределом:
lim {lnN(e„)}/{ln(1/e„)}, n ^
где en = crn, 0 r 1, c 0, n =1,2,..., так что радиусы шаров можно менять дискретно. Вторая теорема позволяет использовать боксы размером 1/2n. Если Nn(F) число таких боксов, пересекающих F, то емкость определяется как предел при n те:
lim{ln Nn(F)}/{ln 2n}.
Путеводитель по литературе. Подход Пуанкаре к понятию размерности изложен им в книге [1]. О работах Минковского и Борхарда можно узнать из монографии Лебега [3].
Элементарное изложение современных понятий о математической непрерывности содержат учебные курсы [4,5]. В монографии [6] можно найти много интересного по истории вопроса. Наконец, подробное описание всевозможных размерностей можно найти в обзорах [7-9].
С информацией Шеннона и ее применением можно познакомиться по книге [10] или замечательным беседам Реньи [11].
Дробные размерности
Оставаясь на почве любой физической теории, мы не можем интерпретировать формулы, содержащие дробные показатели основных единиц.
В. Вильямс
История началась с попыток английского физика Ричардсона измерить длину побережья Британии. Располагая подробной картой, он аппроксимировал линию побережья ломаной Lb, составленной из отдельных хорд длиной b, все вершины которой лежали на берегу. Ричардсон полагал,
что в этом случае существует предел Lb ^ L при b ^ 0, как бывает для гладких кривых. Однако, оказалось, что с уменьшением b суммарная длина ломаной растет до бесконечности по закону:
Lb = Xb1-D, D 2.
Если построить на каждом звене b квадрат, то суммарная площадь квадратов: b2N = b2Lb/b = Лb2-D ^ 0 при b ^ 0 и D 2. Таким образом, береговая линия имеет бесконечную длину и порождает нулевую площадь! Первое, что приходит в голову, это сомнения в корректности такой аппроксимации.
В математике уже давно известны случаи, когда метод хорд не работал.
Классический пример привел еще Лебег: возьмем равносторонний треугольник ABC и соединим середины трех сторон (см. рис. 1).
Очевидно, AB + AC = BC1 + C1A1 + A1B1 + B1C. Продолжая процесс разбиения, мы приближаем ломаную к стороне BC. Если считать последнюю пределом ломаной, мы получим AB + AC = BC. Для того, чтобы разобраться в деталях парадокса, необходима нетривиальная математика: понятие тонкой сходимости, трансфинитные повторные пределы и т. п. Мы заменим все это здравым смыслом и простыми геометрическими соображениями.
В действительности, сторона BC не является пределом зигзагообразной ломаной эта ломаная действительно приближается к BC по положению, но не по направлению. Все
дело здесь в степени гладкости. Вспомним, что длина кривой выражается интегралом, под знаком которого стоят производные от функции, задающей кривую в параметрическом виде.
Таким образом, для вычисления длины необходима гладкость кривой по меньшей мере C1, т. е. ее уравнение имеет непрерывную первую производную. Длина спрямляемой кривой действительно ограничена верхней гранью суммарных длин вписанных ломаных. На такой кривой x = x(s),s G [0,1] конечной длины L в качестве параметра удобно выбрать длину дуги. В этом случае справедливо условие Липшица: |x(s1) x(s2)| ^ |s1 s2| или при s ^ t, s = Lt : |x(t2) x(t1 )| ^ L|t2 t1\ и касательная вдоль кривой меняется непрерывно.
Углы, которые образует произвольная хорда с касательными, не превосходят наибольшего из углов, образованного разными касательными в концах дуги. Поэтому, когда число вписанных в дугу звеньев ломаной возрастает, последняя приближается к дуге не только по положению, но и по направлению(1).
В случае, если гладкость меньше чем C1, хорды при измельчении стремятся встать перпендикулярно к стороне треугольника, что и приводит к расходящемуся пределу.
Существует аналог парадокса Лебега. В конце прошлого века Герман Шварц показал, что триангуляция цилиндра единичного радиуса и единичной высоты дает для площади боковой грани произвольную величину Причины обоих парадоксов в функциях, гладкость которых ниже той, с которой мы привыкли иметь дело в обычном анализе.
В общем случае формула линейных приращений: Ay = pAx + O(Ax2) заменяется на Ay = рн(Ax)H, где H показатель Гельде-ра, а р и рн обычная и гельдеровская производные. Показатель H =1 для гладких функций. В случае H 1 вместо касательной имеется криволинейный конус Ay AxH. Объекты, для которых H 1, а показатель D в формуле Ричардсона строго больше единицы, называются фракталами.
Рассмотрим несколько известных примеров.
Пример 1. Множество Кантора. Пусть F0 = [0,1]. Выбросим из F0 интервал (1/3,2/3), а то что останется, обозначим Fi. Затем выбросим из F1 интервалы (1/9,2/9) и (7/9,8/9) и получим F2 (рис.
2). Продолжая этот процесс, мы придем к убывающей последовательности замкнутых интервалов {Fn}. Множество F = nFn называют канторовым множеством.
Пусть 6 множество выброшенных кусков отрезка [0,1] при построении F, т.е. 6 = (1/3,2/3) U (1/9,2/9) U (7/9,8/9) U ...
Тогда лебегова мера равна сумме: 1/3 + 2 х 1/9 + 4 х 1/27 + ... = 1. Таким образом, при построении F мы выбросили всю длину отрезка! Но осталось бесконечное множество точек, канторово множество: [0,1]\, имеющее мощность континуума и лебегову меру нуль(2). Например, ему принадлежат точки {0,1,1/3,2/3,1/9,...} то есть концы выбрасываемых интервалов, но не только они!
Все точки F0 G F можно описать следующим образом. Запишем каждое из чисел х Е [0,1] в троичной системе: x = аі/3 + а2/32 + ... + an/3n + ..., где ап = 0,1 или 2. Некоторые числа в этом представлении допускают двойную запись, например: 1/3 = 1/3 + 0/32 + ... и 1/3 = 0/3 + 2/32 + 2/33 +____Легко
убедиться, что F принадлежат только те х, которые могут быть записаны хотя бы одним способом так, что в последовательности числителей а1, а2,..., ап,... ни разу не встречается единица. Совокупность таких последовательностей имеет мощность континуума(3).
Вычислим размерность самоподобия канторова множества. При первой итерации имеем е = 1/3, N = 2, при второй е = 1/9, N = 22;..., при fc-ой е = 1/3k, N = 2k.
Поэтому dH = ln2/ ln3 0,63 меньше, чем размерность исходного прообраза.
Существует функциональный аналог множества Кантора функция Кантора. Распределим равномерно на F единичную массу (меру) с плотностью + Тогда функция F(х) = d^(x) описывает распределение меры на канторовом носителе.
