Преамбула
Увязнув в бесконечном обзоре толстой моногорафии по глубокому обучению, в какой-то момент я написал эту заметку, но потом обнаружил, что на Хабре уже упоминалась кожура гиперапельсина в статье о байесовских выводах, хотя и в другом контексте. Тем не менее, эта заметка осела в черновиках. Но теперь, когда я написал большой обзор и после редактуры он будет опубликован буквально на днях, я подумал, что и эту заметку тоже опубликую. Ну, чем я рискую, в крайнем случае разоблачат и выгонят.
Когда неожиданно для себя и для всех берешься за какое-то дело, это может затронуть некие глубинные пласты мироздания и слегка заржавевший механизм приходит в движение, показывая в окошечках удивительные комбинации символов, не виданные или не узнанные ранее.
Вот она, эта заметка.
О проблеме плотности тестовых данных для моделей ИИ
Вот, к примеру, взялся я в прошлом году переводить монографию по машинному обучению в версии Deep Learning. Ничто не предвещало, просто в восьмой главе обсуждали, почему хорошо обученные модели на тестовых данных ведут себя не так хорошо, и обсуждение на примере задачи многомерной классификации привело автора к сетованию, что чем выше размерность задачи, тем разреженнее становятся тестовые данные. Выборка в 100 000 образцов выглядит прилично в трехмерной задаче, но как только размерность задачи начинает расти, плотность образцов в пространстве пар “вход/выход” падает катастрофически. Чтобы пояснить свою мысль, автор рассказывает о том, что я знал в младенческом возрасте, когда читал журнал “Квант” и мечтал поступить в МФТИ, но с тех пор уже забыл напрочь.
Пример очень простой, но наглядный, не погнушайтесь элементарной математикой. Возьмем круг, вписанный в квадрат со стороной, равной единице. Какая будет площадь круга? Ответ известен из курса школьной математики:
То есть, площадь круга, вписанного в квадрат, отъедает 0.79 площади этого квадрата.
Увеличиваем размерность на единицу. Вписываем шар в куб. Такие же школьные вычисления показывают, что шар отъедает от объема куба, в который он вписан уже только примерно 0.5235:
Когда размерность гиперкуба растет, это соотношение уменьшается катастрофически и стремится к нулю. Вот спросите себя - с какого перепугу объем многомерного гиперкуба как был, так и есть единица, а объем вписанного в него шара съеживается. Мало того, образцы выборки, которые, казалось, были равномерно распределены в двумерном и трехмерном пространстве, начинают прибиваться к поверхности гиперсферы (известная присказка, что главный объем гиперапельсина сосредоточен в его кожуре, а не в его мякоти, вполне дзенское такое наблюдение).
Об упаковке шаров в многомерном пространстве
Ну, ладно, днем, пока переводил восьмую главу, поудивлялся этому и только. Но вот ночью просыпаюсь, как обычно бывает при пятибалльной магнитной буре, и начинаю втыкать в электрические тырнеты. А там обнаруживаю новость, к которой я опоздал на два с половиной месяца (на момент описываемых событий). Новость от 5 июля 2023 года. Математику Марине Вязовской дали премию Филдса (нобелевку для математиков, условно говоря). Она стала второй женщиной, которая ее получила после персиянки Мириам Мирзахани, которая получила ее в 2014, а в 2017, в возрасте 40 лет ушла от нас от последствий рака груди.
Марина Вязовская, слава богу, жива и здорова, заведует кафедрой арифметики в политехнической школе в Лозанне, где и живет с мужем и двумя детьми.
Моя реакция на эту новость объясняется не тем, что женщина, а тем - за что дали. За решение задачи о наиболее плотной упаковке шаров в многомерном пространстве. Я про эту задачу впервые узнал от своего друга детства, который стал богат и знаменит, переехав из губернского города в России в столичный город Тель-Авив. Оказалось, что эта чисто математическая по формулировке задачка имеет применения в теории кодов, исправляющих ошибки, где мой друг детства получил серьезные результаты, которые легли в основу его научной карьеры профессора Тель-Авивского университета. Помню тогда, много лет назад, мой друг шутил, что этим делом занимается такое считанное количество людей, что в пору очередную статью с улучшением оценки плотности упаковки шаров в многомерном пространств впору начинать словами «Dear John and Pete».
Так вот, оказалось, что с тех далеких уже времен, когда этой проблемой занимался друг моего детства, очень много математиков билось об эту задачу, но все никак. А вот Марина Вязовская оказалось упорнее других и опубликовала решение этой задачи для размерности 8 и (с рядом соавторов) для размерности 24. Оказалось, что в этих двух размерностях - вообще все не так, как в других размерностях. И никто не знает - почему! Причем тут же открылся ящик Пандоры с приложениями этого открытия и похоже, что это будет как минимум не слабее, чем приложение для теории кодов, исправляющих ошибки.
Многие видные математики, прочитав доказательство Марины Вязовской на 23 страницах высказывались в том смысле, что ничего красивее этого они уже в жизни своей не планируют увидеть. Для справки, решение этой задачи для размерности 3 (гипотеза Кеплера) заняло около трехсот страниц текста, поэтому решение Марины Вязовской назвали «ошеломительно простым».
Гипершар, вписанный в гиперкуб, в простенькой задачке формирования представительной выборки тестовых данных для обучения моделей ИИ, робко прибивается ко всей этой огромной необозримой тематике.
Прорыв, достигнутый Мариной Вязовской, сравнивают с прорывами в математике XIX и XX века.
Жизнь слепо копирует литературу
Как будто мало еще совпадений в этой истории, так я еще во время управления автомобилем и приготовления пищи слушал тогда роман китайского писателя Лю Цысиня «Задача трех тел», в переводе Ольги Глушковой с английского перевода Кена Лю. Там, собственно, та же история. Чисто математическая задача, которая тоже не имеет решения в аналитическом виде, стоит в центре сюжета о внеземной цивилизации, которая возникла в системе тройной звезды альфа-Центавра, но не может выжить и погибает снова и снова только потому, что никто не может решить задачу трех тел.
Предполагают, что задача о наиболее плотной упаковке шаров в трехмерном пространстве исторически связанна с практической задачей хранения пушечных ядер, что придает ей еще более зловещий оттенок в текущей ситуации во всем мире.
Автор: DedaVova
