Сегодняшний пост — это сотрудничество с моим другом детства Андресом Сильвой :-) ------- Если вы бросите случайную точку в единичный квадрат, вероятность того, что она окажется внутри вписанной окружности, составляет около 78,5%. Если бросить одну в единичный куб, вероятность того, что она окажется внутри вписанной сферы, составляет 52,4%. К десятой размерности эта вероятность падает до 0,25%. К сотой размерности она фактически равна нулю. Это и есть "проклятие размерности" — стандартная тема в любом курсе машинного обучения и предмет длинной математической литературы. Среднее расстояние между случайными точками в коробке было предложено Роббинсом и решено в 1978 году. Йохан Филип вывел полное распределение для 3D. Эти проблемы хорошо изучены. Что мы хотим сделать здесь, так это нечто немного другое: систематически сравнить гистограммы расстояний по различным геометриям (евклидова, сферическая, гиперболическая), топологиям (гиперкуб против тора) и размерностям — а затем спросить, что эти "подписи" могут рассказать о реальных пространствах встраивания в нейронных сетях. Основная идея: гистограмма парных расстояний между случайными точками — это геометрический отпечаток. Разные пространства оставляют разные следы. Вы можете использовать это, чтобы диагностировать, в какой геометрии ваши данные на самом деле находятся. История происхождения: Два Андреса заходят в бар в Койоакане... Идеи в этом посте возникли из разговора между нами (да, нас обоих зовут Андрес — bienvenidos a México). Суть: если вы и ваш друг случайным образом окажетесь в n-мерном гиперкубе, насколько далеко вы друг от друга, в среднем? И что более интересно, как выглядит распределение возможных расстояний? "Дело в том," как выразился один из нас во время обсуждения, "если вы возьмете две случайные точки в пространстве, как выглядит распределение расстояний? Я уверен, вы думали об этой проблеме?" - "да, и я задумывался о более высоких размерностях." Ответ оказывается удивительно простым для 1D случая (отрезок): распределение расстояний между двумя равномерно случайными точками на [0,1] треугольное, с пиком в 0. Большинство пар находятся близко друг к другу, и вероятность того, что они будут точно на расстоянии 1 (максимум), равна нулю — это множество меры ноль. Но что происходит, когда вы добавляете обертку? Когда вместо отрезка вы находитесь на круге? Трюк тора: без потери общности Вот здесь появляется первое красивое понимание. На отрезке [0,1] расстояние между точками x и y просто |x - y|. Но на круге (1-торе) вы можете двигаться в любом направлении. "Обёрнутое" расстояние — это min(|x - y|, 1 - |x - y|). Ключевая идея: на торе вы всегда можете предположить, что одна точка находится в начале координат без потери общности. Почему? Потому что тор однороден — каждая точка выглядит как каждая другая точка. Нет краев, поэтому нет углов. Каждое место, где вы помещаете первую точку, — это "то же самое место". Если вы бросаете две случайные точки на тор, вы всегда можете мысленно переместить пространство так, чтобы одна точка находилась в нуле. Это означает, что распределение расстояний полностью определяется распределением расстояния одной равномерной случайной точки от нуля. На 1D торе (круге) эта обёрнутая координата равномерна на [0, 0.5]. Вся проблема красиво факторизуется: в n-мерном плоском торе общее расстояние: D = sqrt(D_1^2 + D_2^2 + ... + D_n^2) где каждое D_i — это обёрнутое координатное расстояние в размерности i, независимо равномерно на [0, 0.5]. "Так что вы смотрите на распределение евклидовой нормы вектора, компоненты которого равномерны на [0, 0.5]," заметил Андрес С. во время нашего разговора. "Вы могли бы иметь множество меры 1/2 всех этих возможностей..." ...