Недавно на Хабре вышла интересная статья «Рваная, чудовищная функция, которая сломала математический анализ». В ней рассказывалось о функции Вейерштрасса — знаменитом примере непрерывной, но нигде не дифференцируемой функции, которую математики XIX века называли «безобразным злом». Это вызвало у меня интерес к другим необычным («патологическим») функциям. Мне захотелось разобраться, как подобные объекты влияют на развитие математики и даже находят отражение в современных областях, таких как машинное обучение.

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

Историческое происхождение функции Кантора

Функция Кантора (иногда ее называют канторовой лестницей или «дьявольской лестницей») была впервые описана в 1884 году Георгом Кантором​. Кантор искал контрпримеры, чтобы уточнить фундаментальные понятия математического анализа. Ему удалось построить непрерывную функцию, которая, казалось бы, «почти не растет», но при этом изменяется от 0 до 1. Этот пример опроверг излишне сильное обобщение основной теоремы анализа, предложенное Г. Гарнаком. Впоследствии функцию Кантора изучали и популяризировали другие математики, например, Феликс Шеффер, Анри Лебег и Джузеппе Витали​. Лебег в 1904 году использовал ее при создании теории меры, из-за чего эту функцию иногда называют «особой функцией Лебега».

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

Построение функции Кантора

Функция Кантора определяется на отрезке [0, 1]. Её конструкция тесно связана с множеством Кантора – знаменитым фрактальным подмножеством отрезка. Посмотрим, как строится канторово множество:

1. Начинаем с отрезка .

2. На первом шаге удаляем открытую среднюю треть . Остаются два отрезка: и .

3. На втором шаге удаляем средние трети оставшихся отрезков. То есть вырезаем интервалы и . Теперь остаются четыре небольших отрезка: , , и .

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

После бесконечного числа шагов остаётся несчётное множество точек (канторово множество ), распределённых по исходному отрезку. Интуитивно понятно, что точек бесконечно много (например, все концы вырезанных отрезков остаются), однако суммарная длина всех оставшихся отрезков стремится к нулю. Формально, множество Кантора имеет нулевую меру длины, хотя и содержит континуум точек. Его часто приводят как парадоксальный пример: множество без «длины», но не пустое и даже несчётное.

Можно задать более строго через троичное представление чисел. Любое число можно записать в виде троичного ряда. Множество Кантора состоит из всех чисел, в чьей троичной записи присутствуют только цифры 0 и 2 (цифра 1 не встречается вовсе). Например, , а (поскольку появилась цифра 1). То есть:

Теперь определим функцию Кантора  на . Интуитивно она «поднимается» от 0 до 1, но делает это только на точках из , оставаясь постоянной на вырезаемых промежутках. Зададим пошагово:

• Шаг 0: определим начальные значения: и .

• Шаг 1: на удалённой средней трети зафиксируем значение функции равным . Иными словами, при полагаем . На краях этого интервала ( и ) значение тоже будет – так мы обеспечиваем непрерывность.

• Шаг 2: рассмотрим два удалённых интервала второго шага. Для всех положим , а для – . Эти значения выбраны как середины между уже имеющимися соседними уровнями ( и для левого интервала; и для правого).

• Шаг 3 и далее: продолжаем аналогично. На каждом следующем этапе на всех новых вырезанных промежутках функция Кантора принимаeт значение, равное середине между значениями на концах этого промежутка.

Другими словами, функция на каждом «среднем удалённом» отрезке остаётся постоянной, принимая значение ровно посередине между уровнями слева и справа от этого отрезка. При бесконечном продолжении процесса мы определяем для всех . В итоге получается своеобразная лестница с бесконечным числом ступенек: функция возрастает рывками на точках из множества Кантора, а на всех остальных участках «плато» остается плоской. Тем не менее, благодаря тому что на концах каждого удаленного отрезка значения совпадают, функция выходит непрерывной на всём [0,1] и монотонно неубывающей​.

На графике хорошо видны первые крупные «ступени»: на участке функция плавно выросла с 0 до 0.5, затем на всём промежутке остается равной , и на поднимается до 1. Более мелкие ступеньки продолжают дробиться при увеличении масштаба: например, между 0 и 0.5 видны ступени высотой 0.25 (на долях 1/4 и 3/4 по оси ) шириной и т.д. Эта бесконечная самоподобная детализация — характерный признак фрактальной структуры функции Кантора.

Заметим, что можно описать и через троичные представления: возьмем число и запишем его в троичной системе. Если в троичной записи встречается единица, то (как мы делали выше) заменим все цифры после первой 1 на 0. Затем заменим все 2 на 1. Получившаяся последовательность из нулей и единиц — это двоичная запись числа . Например, (что равно ) превратится в (двоичное ), то есть . Такой алгоритм эквивалентен построенному выше геометрическому определению. Он наглядно показывает, что значение функции Кантора фактически читается как двоичное число, составленное из цифр 0/1 (вместо 0/2) исходного троичного представления . Если лежит внутри какого-то вырезанного интервала, его троичная форма содержит 1 — тогда после нее все двоичные разряды обнуляются, отражая постоянство функции на этом интервале.

Свойства и фрактальная структура

Функция Кантора обладает рядом удивительных математических свойств:

• Непрерывность и монотонность. Как было отмечено, непрерывна на всём отрезке [0,1] и неубывающая (то есть функция распределения, CDF). При этом она принимает все промежуточные значения от 0 до 1. Казалось бы, непрерывная монотонная функция должна хоть где-то «расти» в обычном смысле, однако здесь рост происходит очень необычно.

• Почти везде постоянство (особенность производной). Функция Кантора была придумана как контрпример к наивному обобщению теоремы Ньютона-Лейбница. Дело в том, что она поднимается от 0 до 1, но делает это так «бережно», что производная оказывается равной нулю на всем протяжении, кроме, формально, множества Кантора. В каждом вырезанном интервале график горизонтален, отсюда для всех вне канторова множества. С другой стороны, в точках самого множества Кантора производная не существует (там график изгибается углом при переходе с одной ступеньки на другую). Поскольку множество Кантора имеет меру ноль, говорят, что производная равна 0 почти всюду. И все же интеграл этой производной от 0 до 1 даёт 1, а не 0, ведь функция суммарно повысилась на 1. Это и есть «дьявольщина» в дьявольской лестнице. В среде математиков функция Кантора стала классическим примером особой функции: она непрерывна, но не абсолютно непрерывна и практически плоская всюду, хотя не константна​.

• Фрактальная самоподобность. Построение явно носит самоподобный характер. Если взять левую треть графика (от 0 до 1/3 по ), то она выглядит как миниатюрная копия всего графика, только «вписанная» в прямоугольник . Аналогично, правая часть (от до 1) масштабируется в копию в прямоугольнике . Такое дробное самоподобие присуще фракталам. Формально, множество Кантора обладает хаусдорфовой размерностью 
  
  ,
  
  что меньше единицы (нулевая длина соответствует этому факту). График же функции Кантора заполняет некоторое подмножество единичного квадрата на плоскости. Хотя топологически это непрерывная кривая (имеющая размерность 1), ее свойства тесно связаны с фрактальной природой множества Кантора. Каждый «излом» на графике происходит на точках из , при увеличении масштаба мы всегда снова видим лестницу, и структура ступенек повторяется в каждом масштабе. Такое поведение резко отличается от гладких кривых и сближает функцию Кантора с другими известными фрактальными объектами (например, функция Вейерштрасса — тоже фрактальная, но там кривая нигде не имеет касательной, тогда как у Кантора касательная почти везде горизонтальна).

• Теория меры и особые распределения. С точки зрения теории меры функция Кантора предоставляет интереснейший пример сингулярного распределения. Поскольку — монотонно неубывающая и непрерывная, она может выступать в роли функции распределения некоторой случайной величины​. Какое же это распределение? Оказывается, это случайная величина, принимающая значения только на множестве Кантора. Представьте себе случайный процесс: на каждом шаге выбираем, куда пойти — в левый или правый оставшийся отрезок (с равной вероятностью 50%). После бесконечного числа шагов мы попадём в случайную точку из канторова множества. Эта точка равномерно (в смысле канторовой меры) распределена по . Тогда будет равномерно распределено на отрезке [0,1]. И наоборот, фактически является накопленной функцией распределения для . Другими словами, функция Кантора переводит равномерное распределение на множестве Кантора в равномерное распределение на интервале. В прикладных терминах, вероятностная мера, соответствующая , сконцентрирована на тончайшем фрактальном множестве (имеющем нулевую длину). Ни плотности распределения (pdf), ни дискретных атомов у такой меры нет – классический пример ни непрерывного, ни дискретного, а особого распределения. Симметрия канторова множества подсказывает, что среднее такой случайной величины равно , а ее распределение симметрично относительно 0.5. Можно даже вычислить дисперсию: она оказывается равной . Такие экзотические распределения редки в базовых курсах, но важны в теории вероятностей и мере. Функция Кантора, таким образом, связала воедино идеи фрактальной геометрии (самоподобие), анализа (непрерывность при нулевой производной) и теории меры (особые распределения).

Возможные применения и параллели в машинном обучении

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

Генерация разреженных и фрактальных данных. В машинном обучении нередко приходится иметь дело с разреженными признаками или распределениями, сконцентрированными на малой подмножественности пространства. Канторово распределение дает чистый теоретический пример подобной ситуации. Мы можем сгенерировать выборку точек, равномерно распределённых на множестве Кантора (например, как описывалось выше через случайные коэффициенты 0/2 в троичном разложении​). Получается датасет, заполняющий отрезок [0,1] крайне неоднородно: все точки распределены по канторову множеству, образуя разреженный, но несчётный набор значений, избегая целые промежутки. Такой набор данных может послужить бенчмарком для алгоритмов кластеризации, оценки плотности и др., проверяя, способны ли они уловить сложную фрактальную структуру распределения. Кроме того, визуализация такого распределения красиво демонстрирует разницу между понятиями «почти всюду» и «всюду» в практике: хотя выборка бесконечно плотна в пределе (несчетно много точек), стандартные гистограммы с малым числом бинтов могут показывать нулевую частоту в большинстве из них (как если бы данные были дискретны).

Тестирование методов оптимизации (градиентные методы). Алгоритмы оптимизации, лежащие в основе обучения нейросетей (типа градиентного спуска), полагаются на информацию о градиенте функции потерь. Но что если функция имеет большие плоские области нулевого градиента, разделенные резкими «обрывами»? Функция Кантора представляет именно такую ситуацию. Если мы зададим, например, задачу максимизации на [0,1] (очевидно, максимум достигается в , где ), то классический градиентный подъем с произвольной начальной точки застрянет мгновенно: в начальной точке градиент , и алгоритм решит, что достиг экстремума, хотя до глобального максимума еще «пилить и пилить» по плато. Таким образом, искусственно сконструированная функция Кантора может использоваться как худший случай для тестирования устойчивости оптимизаторов к плато на ландшафте функции. В глубоких нейросетях похожие плато возникают, например, при насыщении сигмоидных активаций или обнулении градиентов у сверточных фильтров – то есть модель перестает обучаться, пока не выведешь систему из «болота». Канторова лестница в качестве тестового примера наглядно подчеркивает эту проблему: методам приходится полагаться на случайные возмущения или специальную инициализацию, чтобы сдвинуться с места, где . Интересно, что методы типа randomized smoothing и zero-order optimization в машинном обучении фактически усредняют функцию с шумом, чтобы смягчить такие разрывы градиента — по сути, «сглаживают» дьявольскую лестницу, делая ее пологой. Изучение столь экстремального примера может подсказать, как улучшить алгоритмы оптимизации для сложных разреженных задач.

Особые распределения и обучение на фрактальных мерах. Хотя реальные данные обычно не имеют строго нулевой плотности на целом интервале, в некоторых задачах встречаются распределения со сложной поддержкой. Например, в генеративных моделях можно попытаться научить нейросеть имитировать распределение, подобное канторовому. Это был бы испытательный полигон для моделей: обычные нормализующие потоки или вариационные автоэнкодеры, предполагающие гладкую плотность, могут плохо справиться с воспроизведением сингулярной меры. Такого рода эксперименты помогают выявить ограничения моделей и улучшить их. Более того, понятие фрактальной размерности данных находит отклик в современных исследованиях сложности задач машинного обучения. Метрики, основанные на фрактальной размерности выборки, используются для оценки обобщающей способности моделей и эффективности различных архитектур. В этом контексте канторова мера (с ненулевой фрактальной размерностью < 1) служит понятным примером: она показывает, что сложность данных не обязательно связана с размерами пространства или обычной энтропией распределения, а может быть скрыта глубже, в геометрии поддержки.

Неожиданные появления в теории обучения. Любопытно, что функции типа канторовой лестницы всплывают даже в строгом анализе некоторых алгоритмов. Например, в одной работе по обучению с подкреплением исследователи получили оптимальную ценностную функцию, обладающую свойствами самоподобия и нулевой производной почти всюду, аналогично функции Кантора​. Это показывает, что «экзотические» конструкции могут не только служить искусственными примерами, но и возникать естественно в решении прикладных задач. Знание о них позволяет вовремя распознать структуру проблемы и применить адекватные методы (например, спецпроцедуры для обработки разреженных вознаграждений или дискретизации состояний в задачах RL).

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

Вместо заключения

Функция Кантора — яркий пример того, как абстрактные конструкции из математического анализа со временем оказывают влияние на смежные области знаний. Изначально появившись как вызов устоявшимся представлениям (непрерывная функция без привычной производной), она стимулировала развитие теории меры и нашего понимания разрывов между понятиями «почти всюду» и «везде». Ее фрактальная природа предвосхитила идеи, которые спустя почти столетие стали востребованы в науке о сложности, компьютерной графике и моделировании природных процессов.

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