Комментарии 25
А можно где-то подчерпнуть полный перечень существующих на данный момент размерностей? Неплохо бы рассмотреть все! (но это уже на усмотрение))
Однако, такое наивное определение размерности геометрической фигуры (по минимальной размерности объемлющего пространства - в данном случае, двумерного) обладает очевидным недостатком: оно меняется даже при небольших деформациях нашей фигуры.
То есть, если свернуть к трубочку листок с нарисованным кругом, то нарисованный круг перестанет быть двухмерным?
Нет, просто он начнет вкладываться в трехмерное пространство, это контрпример для наивного определения, не более
для наивного определения
Вообще, размерность фигуры/множества просто очередная математическая игрушка, не имеющая отношения к реальности.
Поэтому, у них нет определения связанного с реальностью, и, как следствие, они не могут быть неверными или наивными.
И этих размерностей не одна, как можно было бы подумать из формулировки.
Итак, мы сейчас рассмотрели первое определение внутренней размерности геометрической фигуры. Она называется размерностью Минковского.
И не две, если учитывать "наивный" вариант.
Их больше и все они являются равноправными выдумками.
@tech_priestessвопрос!
for i in range(dims):
point[i] = np.random.uniform(-1, 1)
if np.sum(np.square(point)) <= 1:
points.append(point)А является ли это корректной генерацией именно равномерно в сфере распределённых точек? Изотропии же не получается, казалось бы для чистоты эксперимента нужно семплировать rejection-free способом: https://baezortega.github.io/2018/10/14/hypersphere-sampling/
Я не вижу проблемы с изотропией. В n-кубе, внутри которого находится n-шар, точки ведь распределены равномерно. Я не вижу, как можно потерять равномерность, когда мы просто ограничиваем равномерное распределение на носитель поменьше.
Другое дело, что приведенный в колабе наивный алгоритм, конечно, очень вычислительно неэффективен для шаров большой размерности. Автор приведенной статьи критикует именно этот аспект и этим мотивирует необходимость вводить rejection-free способ.
У меня же не было цели сделать алгоритм эффективным, потому что мне достаточно было показать принцип на шарах нескольких небольших размерностей, для которых наивный способ более-менее работает.
Вроде бы легко исправить генерацию, чтобы она стала более эффективной. Для этого нужно выбирать очередную координату не из [-1,1], а из [-r, r], где r вычисляется по предыдущим координатам. Там, правда, получается O(n) вычислений квадратного корня, но при больших размерностях это должно быть выгоднее, чем отсекать львиную долю точек в наивном алгоритме.
Статистика не мой конек, но что-то мне подсказывает - так не получится равномерное распределение в пространстве.
Т.е выпадение 0 и 0,5 по первой координате равновероятно, но уже выпадение 0 по второй координате будет иметь разные вероятности в первом и втором случае.
Где я ошибаюсь?
Действительно, равномерность нужно доказывать (а люди часто забывают об этом), и это не всегда тривиально. Я сначала хотел сказать, что здесь доказательство очевидно, но потом задумался. И уже засомневался, что это правильный алгоритм. ;)
> выпадение 0 и 0,5 по первой координате равновероятно
Это некорректное рассуждение — нельзя говорить о вероятности выпадения отдельных точек, поскольку распределение непрерывное, а не дискретное. Можно рассуждать о вероятности попадании в интервал.
Спасибо за статью, классно, интересно и полезно, но кровь из глаз от обозначения натурального логарифма в ТеХ: надо использовать \ln, чтобы отображался
.
При этом размерность шара неизвестна
Что-то совсем не понятное. Нам не известна размерность пространства, но мы как-то знаем расстояние между точками. Что такое расстояние м/у точками в этом случае?
Что такое расстояние м/у точками в этом случае?
С таким определением можно задавать метрику (способ вычисления расстояния между элементами множества) для чего угодно, например, для функций. Кроме того, в обычном эвклидовом пространстве можно задать расстояние способом, отличным от традиционного, при этом в двумерном пространстве окружность может иметь форму квадрата
Поэтому всегда нужно проверять, насколько оценка стабильна при изменении размера датасета, если она сильно меняется, это значит, что предположение о равномерности генерирующего распределения на малых масштабах было неверным.
Разве мы не должны говорить, что в этом случае измеряется лишь размерность многообразия в данной малой окрестности, а не всего пространства признаков (или чего там у нас)?
К сожалению, пока что я не видела более прикладных применений TwoNN. Если вы их знаете, поделитесь в комментариях!
Извольте. Очень изящная методика по определению ИИ-сгенерированности текстов
https://openreview.net/forum?id=8uOZ0kNji6
там, правда, не TwoNN, а другой метод определения размерности, но идея в общем понятная
А, так я одна из авторов этой статьи. Приятно слышать, что вам понравилось)
В самом деле, TwoNN не очень хорошо работал в контексте той статьи, поэтому мы в итоге от него отказались и в конце остановились на PH-dimension (альтернативно MLE тоже работал в том контексте, но несколько хуже).
Вот, а мне было бы интересно, где для решения прикладной задачи пригождается именно TwoNN.
Например, мы можем вложить круг в трехмерное пространство и слегка согнуть его - так, чтобы он перестал быть плоским.
В каком смысле "согнуть"? Это не физический объект. Круг можно отобразить на цилиндрической поверхности в трехмерном пространстве. Но это уже не будет круг на плоскости.
Тогда по нашему определению его размерность станет равна 3, что показывает большую ограниченность и условность такого наивного определения.
Если вы помещаете круг в трехмерное пространство, у него увеличивается количество степеней свободы. У него появляется проекция на плоскость, которая может быть овалом или линией. (при этом сам круг остается кругом). Тогда для описания состояния круга нужно вводить новый параметр, в дополнение к размеру и координатам. Например наклон.
Далее, если радиус x увеличить, то количество квадратиков, покрывающих круг тоже увеличится
Да, оно увеличится пропорционально увеличению площади. То есть вы всего-лишь показали зависимость площади от радиуса. При чем здесь размерность?
коэффициент c на картинке выше равен числу пи, а количество квадратиков, покрывающих круг, при x >> a приблизительно равно его площади; но мы не будем на этом останавливаться.
Нужно остановиться, и объяснить почему выбрана зависимость числа квадратиков именно от радиуса.
Вы не объяснили почему в качестве переменной выбрали радиус, а не длину окружности или площадь. У треугольника например нет радиуса. Как вы будете обобщать понятие размерности на другие фигуры?
Так же непонятно, почему меняется радиус круга, и не размер квадратиков.
Непонятно почему выбран круг, а не квадрат. В квадрат можно вписать целое число квадратов, а в круг нельзя. (к слову, целое число кругов в круг тоже не впишешь)
И еще к слову, для круга, квадрата, и равностороннего треугольника, достаточно использовать один параметр, для определения размера (радиус для круга, длину стороны для квадрата и треугольника). Для ромба одного параметра уже недостаточно.
Отсюда вопрос - какой изменяемый параметр, вместо радиуса, вы будете использовать в случае, например, трапеции, для ее масштабирования?
будем считать не количество покрывающих его квадратиков, а количество покрывающих его кубиков, в пределе мы снова придем к такой же формуле. То есть, количество покрывающих его кубиков в пределе будет по-прежнему пропорционально квадрату его радиуса.
А если мы будем вращать круг в трехмерном пространстве по оси диаметра, и кубики перестанут "лежать" на поверхности, а круг будет пересекать кубики по их диагонали? Как это повлияет на число кубиков "покрывающих" круг?
Но что будет, если мы попробуем таким же образом исследовать не круг или шар, а нечто более сложное, например, треугольник Серпинского
Оказывается, в этом случае количество квадратов растет быстрее, чем по линейной закономерности, но медленнее, чем по квадратичной.
Расти относительно чего? Что вы используете вместо радиуса (которого нет у треугольника)? Число итераций? Построение треугольника Серпинского производится по алгоритму, а не по формуле в которой можно менять одно значение и получать треугольник большего размера.
Итак, мы сейчас рассмотрели первое определение внутренней размерности геометрической фигуры. Она называется размерностью Минковского.
Мы рассмотрели не определение, а иллюстрацию, которая должна дать представление о том в чем смысл размерности Минковского. Иллюстрация так себе. Интуитивно это похоже не иллюстрацию кратности чего-то чему-то, и изменения кратности при масштабировании.
Надо все-таки начинать с определений размерности. И сказать о том, что размерность это аналитический инструмент, используемый при классификации объектов. Размерность это вычисляемый параметр. Вычисление размерности производится по формуле или алгоритму. Размерности существуют разные. Каждый математик может придумать свою размерность, и обосновать ее применимость для анализа математических объектов.
Таким образом, размерность Минковского любой фигуры, состоящей из конечного числа точек, тоже будет равна нулю.
Это совершенно непонятно. Фигуру можно представить как в виде конечного множества точек, так и в виде бесконечного множества. (За исключением круга. Круг представленный в виде конечного множества точек является многоугольником.)
Размерность Минковского и Two Nearest Neighbours (TwoNN)