[Перевод] Постдок-статистик укротил старую геометрическую задачу
Специалист по статистике к удивлению экспертов решил одну из важнейших задач выпуклой геометрии в высших измерениях
В середине 1980-х Жан Бургейн, бельгийский математик, придумал простой вопрос касательно фигур из высших измерений. А потом занимался им всю оставшуюся жизнь.
Ушедший от нас в 2018 году Бургейн был одним из выдающихся математиков современности. Лауреат Филдсовской премии 1994 года, высшей награды для математиков, он был известен, как специалист по решению задач высокого класса. С ним можно было поговорить о задачке, над которой вы бились несколько месяцев, а он мог решить её, не сходя с места. И всё же Бургейн не сумел ответить на собственный вопрос о фигурах из высших измерений.
«Жан однажды сказал мне, что на эту задачу он потратил больше времени и сил, чем на какую бы то ни было другую за всю свою карьеру», — писал Виталий Милман из Тель-Авивского университета.
За время, прошедшее с первой формулировки задачи, Милман и Боаз Клартаг из Вейцмановского научного института в Израиле, назвали её «вратами» к пониманию широкого спектра вопросов, связанных с выпуклыми фигурами из высших измерений. Выпуклая фигура всегда содержит целиком любой отрезок, соединяющий две её любые точки. Выпуклые фигуры в высших измерениях изучают не только математики, но и статистики, исследователи в области машинного обучения и другие специалисты по информатике, работающие с многомерными наборами данных.
Жан Бургейн в 1980-х годах в Институте передовых научных исследований во Франции
Задача Бургейна сводится к следующему простому вопросу: допустим, объём заданной выпуклой фигуры в ваших любимых единицах измерения равен 1. Если рассмотреть все разрезы, которым можно подвергнуть эту фигуру при помощи плоскости, имеющей на одно измерение меньше, могут ли все площади этих разрезов быть чрезвычайно малыми, или же хотя бы один из них должен иметь достаточно большую площадь?
Бургейн предположил, что некоторые из этих размеров должны иметь большую площадь. В частности, он высказал гипотезу о существовании универсальной, не зависящей от количества измерений, константы, такой, что в любой форме есть разрез с площадью, превышающей эту константу.
На первый взгляд гипотеза Бургейна кажется очевидной. Ведь если бы фигура была тонкой по всем направлениям, как она смогла бы занимать единицу объёма?
«Да что тут сложного?» — вспоминает Ронен Элдан, специалист по многомерной геометрии из Вейцмановского научного института, мысли, пришедшие к нему, когда он впервые услышал об этой задаче. «Но чем больше ты о ней думаешь, тем больше понимаешь, насколько она непростая».
Сложность в том, что многомерные фигуры часто ведут себя совершенно непонятным с точки зрения маломерной человеческой интуиции образом. К примеру, в измерениях 10 и выше можно сконструировать такие куб и шар, что объём куба будет больше, чем объём шара, но площадь любого разреза, проходящего через центр куба, будет меньше площади соответствующего разреза, проходящего через центр шара.
«Красота многомерной геометрии в том, что она вообще не похожа на двумерную», — сказал Себастиен Бабек из исследовательского центра Microsoft в Редмонде, Вашингтон.
Гипотеза Бургейна — предположение о покорности многомерных фигур, согласно которому они в чём-то соответствуют нашей интуиции.
И вот догадка Бургейна подтверждена: в ноябре была опубликована работа, доказавшая хотя и не всю гипотезу целиком, но настолько близкое к ней утверждение, что оно налагает жёсткие ограничения на всяческие вольности среди многомерных фигур — с практической точки зрения.
Клартаг сказал, что Бургейн «мог лишь только мечтать» о достижении такого сильного результата.
Новую работу написал Юанси Чен, постдок из Швейцарского федерального технологического института в Цюрихе. Он ещё только готовится войти в штат университета Дьюка. Он подступился к проблеме срезов Бургейна через ещё более далёкую от этого теорему из области выпуклой геометрии, которую называют «гипотезой КЛС» [Каннана-Ловаса-Симоновица]. 25-летняя гипотеза задаёт вопрос о том, как лучше всего разрезать фигуру на две равные части, и включает в себя гипотезу Бургейна. Кроме того гипотеза КЛС лежит в основе множества вопросов статистики и информатики — к примеру, по времени распространения тепла по сложной фигуре, или по количеству шагов, на которые нужно отойти пешеходу от начальной точки, чтобы оказаться в по-настоящему случайном месте.
Юанси Чен на горе Хезерругг в Швейцарии
По словам Элдана, случайные прогулки — это практически единственный метод выборки случайных точек. Он говорит, что в широком спектре различных задач по информатике «самой важной процедурой алгоритма является получение выборки случайных точек».
Новый результат Чена уменьшает время работы алгоритмов, решающих такие задачи, как вычисление объёма выпуклой фигуры или выборка моделей машинного обучения из большого ассортимента. Да, работа Чена не доказывает полную гипотезу КЛС. Однако, по словам Бабека, в вопросах, касающихся информатики, «полная гипотеза и не нужна».
Сам Чен не занимался геометрией выпуклых фигур — он статистик, заинтересовавшийся гипотезой КЛС потому, что хотел разобраться с выборкой случайных точек. «В нашем сообществе Юанси Чена никто не знал, — сказал Элдан. — Очень круто, что этот товарищ появился из ниоткуда, и решил одну из важнейших наших задач».
Скрытые гантели
Как и задача разрезов у Бургейна, гипотеза КЛС (названная в честь создателей — Равви Каннана, Лазло Ловача и Миклоша Симоновича) заключена в простом вопросе. Допустим, вы хотите разрезать выпуклую фигуру — например, яблоко без углублений — на две равные части, и одну отложить. На срезе яблоко потемнеет и станет неаппетитной, поэтому вам хочется сделать её площадь как можно меньшей. Какой из разрезов сможет дать минимальную площадь среза?
Если ограничиться прямыми срезами, ответить на этот вопрос не так уж сложно — по крайней мере, с определённой точностью. Но если разрешить разрезы любой формы, это будет уже совершенное другое дело. Математикам известно, что в двух измерениях лучшими вариантами всегда будут либо прямая линия, либо дуга окружности. Но в трёх измерениях лучшие разрезы известны лишь для небольшого количества простейших фигур, а в больших измерениях математики обычно и не надеются найти оптимальную форму разреза.
Кратчайший разрез, делящий двумерную выпуклую фигуру на две равные части, не всегда должен быть прямым. Это может быть, например, дуга окружности. Чем больше измерений, тем сложнее решить эту задачу.
У треугольника с единичной стороной разрез по дуге получится короче, чем прямые разрезы.
Поскольку оптимальный кривой разрез так тяжело определить, Каннан, Ловач и Симонович заинтересовались, насколько хуже будет, если разрешить только прямые разрезы. В 1995 году они выдвинули гипотезу, что такое ограничение никогда не ухудшит ситуацию слишком сильно: соотношение площади поверхности лучшего прямого разреза и площади самого идеального непрямого будет не больше, чем некая универсальная константа.
«Это была гениальная идея», — сказал Сантош Вемпала из Технологического института Джорджии, хотя Каннан, Ловач и Симонович и не смогли её доказать. Вместо универсальной константы они смогли подобрать только множитель, примерно равный квадратному корню из количества измерений фигуры. Так что для 100-мерной выпуклой фигуры площадь лучшего прямого среза будет превышать площадь идеального непрямого не больше, чем в 10 раз.
Может показаться, что поверхность в 10 раз большей площади — не ахти какое достижение. Но поскольку многие характеристики многомерных фигур растут с ростом количества измерений экспоненциально, на их фоне квадратный корень кажется довольно скромным числом. «Он уже показывает, что в высших измерениях работает какое-то интересное явление, — сказал Бабек. — И всё не так плохо, как могло бы быть».
Однако исследователям очень хотелось улучшить этот результат, и не только из теоретических побуждений. Они знали, что множитель КЛС включает в себя огромное количество характеристик поведения случайных процессов внутри выпуклой фигуры. Ведь чем меньше площадь лучшего разреза, тем сложнее случайному процессу быстро распространиться по всей фигуре.
Представьте себе нечто вроде гантели — два массивных шара, соединённых узким мостиком. То, что эту фигуру можно разделить на две равные части при помощи небольшого размера, точно схватывает суть того, что этот мостик является узким местом всей фигуры. Источник тепла или случайный ходок из одного шара не сразу дойдут до второго, поскольку ему нужно будет найти проход через узкое место.
У эллипсоида меньший из разрезов, делящий его на две равные части, очень большой, поэтому случайному ходоку очень легко попасть из одной части в другую. У гантели можно сделать крохотный разрез на две равные части.
Да, гантель не является выпуклой фигурой. У выпуклой фигуры не может быть таких непропорционально малых плоских разрезов — но, возможно, у неё можно найти непропорционально малый непрямой разрез. Гипотеза КЛС, по сути, задаёт вопрос — может ли в многомерной выпуклой фигуре притаиться невидимая гантель, замедляющая случайное перемешивание.
Квадратный корень КЛС ограничил размер таких «скрытых гантелей». В 2012 году Элдан понизил их ограничение до кубического корня из количества измерений, введя технику «стохастической локализации». Она, грубо говоря, как бы наклоняет выпуклую фигуру и сдвигает её точки то в одном, то в другом направлении, пока они не скопятся в определённом месте. Для массы высокой концентрации, максимально не похожей на гантель, гипотезу КЛС доказать легко. Показав, что процесс наклона не сильно меняет общую ситуацию, Элдан смог подсчитать КЛС-ограничение и для оригинальной фигуры. «Это очень, очень красивый процесс», — сказал Бабек.
Спустя несколько лет Вемпала и Йин-Тат Ли из Вашингтонского университета немного улучшили стохастическую локализацию Элдана, ещё сильнее опустив множитель КЛС — до корня четвёртой степени из количества измерений. В какой-то момент им даже показалось, что они нашли ещё более сильное ограничение. Если количество измерений равно d, тогда квадратный корень будет равен d1/2, кубический — d1/3, четвёртой степени — d1/4. Ли и Вемпала решили, что при помощи изобретенной ими техники «бустраппинга» им удалось понизить ограничение КЛС до d0+f, где f — совсем небольшое число. Поскольку d0 равняется 1, ограничение Ли и Вемпалы оказалось почти константой.
«Это потрясающе, — вспоминает Бабек свои слова, сказанные в ответ на рассказ Ли о результате исследования. — Мне это казалось очень важным результатом, достойным высочайшей похвалы».
Ли и Вемпала выложили свою работу в онлайн. Но уже через несколько дней Клартаг нашёл в их работе пробел, перечеркнувший результат с границей величины d0. Ли и Вемпала быстро выложили исправленную версию, с заявкой на ограничение величиной d1/4. И несколько лет исследователи считали, что это и есть финал истории.
Всё оттого, что Элдан и Клартаг ранее показали, что любое ограничение КЛС сразу же даёт ограничение разреза Бургейна — к примеру, ограничение d1/4 означает, что в задаче Бургейна о разрезе всегда существует разрез, чья площадь будет не меньше, чем 1/ d1/4. Но математикам уже были известны несколько способов доказать, что в задаче Бургейна о разрезе есть ограничение величиной в 1/ d1/4. Так что, возможно, подумали они, Ли с Вемпалой дошли до естественного предела в вопросе КЛС.
«И я уже начинал думать, что, возможно, так оно и есть», — сказал Элдан.
«Было ощущение, что над этим вопросом работали крупные специалисты, и всё, что можно было изучить, уже изучено», — сказал Клартаг. Но это было до того, как появился Юанси Чен.
Ограничивая срезы
Публикуя исправленную версию работы, Ли и Вемпала оставили в ней все идеи, касающиеся ограничения величиной около d0. Они объяснили, что из всего этого доказательства выпало только одно звено.
Их работа попалась на глаза Чену, который тогда был студентом, изучающим статистику в Калифорнийском университете в Беркли. Он занимался смешиванием различных методов построения выборок. Случайные выборки — ключевой ингредиент во многих типах статистических изысканий, таких, как байесовская статистика, система развития убеждений на основе новых доказательств. «В байесовской статистике со случайными выборками сталкиваешься ежедневно», — сказал Чен.
Работа Ли и Вемпалы познакомила Чена с идеей стохастической локализации. «Мне показалось, что это одна из самых красивых техник построения доказательств, что я видел за долгое время», — сказал Чен.
Чен погрузился в литературу, и несколько недель пытался закрыть пробел в доказательстве Ли и Вемпалы, но безуспешно. В течение нескольких следующих лет ему в голову то и дело приходили разные идеи о том, как изменить стохастическую локализацию, после чего он некоторое время размышлял над ними, но потом сдавался. И вот, наконец, одна из его идей принесла плоды: он понял, что существует способ не восстанавливать отсутствующее звено в доказательстве Ли и Вемпалы, а вообще избавить его от необходимости делать такое сильное заявление.
Чен охарактеризовал свои следующие действия, как «парочка трюков», но Вемпала назвал их «элегантной новой идеей». Чен понял, как заставить бустраппинг Ли и Вемпалы работать. Его метод уменьшает границу КЛС при помощи рекурсии, показывая, что если сделать ограничение достаточно малым, то его можно сделать ещё меньше. И после нескольких повторов такой подход достигает почти постоянной величины ограничения для гипотезы КЛС, а также и для задачи Бургейна о срезах.
Клартаг сказал, что увидев работу Чена, «просто всё бросил и сразу стал изучать её». Исследователей беспокоил тот факт, что раньше уже появлялось неправильное доказательство, а также то, что большинство из них никогда не слышали о Чене. Однако его вклад оказалось легко проверить. «Эта работа правильна на 100%, — сказал Клартаг. — Нет никаких сомнений».
Результат Чена говорит о том, что наилучший разрез выпуклой фигуры, делящий её напополам, не может быть сильно лучше лучшего из прямых срезов. Иначе говоря, в выпуклых многомерных фигурах нет никаких скрытых гантелей с узкими мостиками. С точки зрения математики «это значимый результат, поскольку он закрыл зияющий пробел в нашем понимании этого вопроса», сказал Бабек.
С определённой точки зрения это означает, что случайная прогулка гарантированно пройдёт по выпуклой фигуре гораздо быстрее, чем можно было доказать раньше. Среди прочего, это знание поможет специалистам по информатике выбирать более эффективные техники случайных выборок, чтобы понять, когда лучше подойдёт самый простой алгоритм случайного прохода, а когда лучше взять более сложный и затратный по вычислениям алгоритм.
В итоге, сказал Вемпала, учитывая, как много людей безуспешно пытались доказать, что величина ограничения равняется d0, доказательство оказалось неожиданно простым. Он считает, что Бургейн, узнав о таком доказательстве, подумал бы: «Как же я это упустил?»
Математики соглашаются с тем, что Бургейн был бы в восторге от такого развития событий. Он писал Милману вопросы о наличии какого-либо прогресса всего за несколько месяцев до своей кончины в 2018 году. «Он хотел узнать ответ перед тем, как уйти», — писал Милман.
