[ЗАСТАВКА] В этом видео мы обсудим одно явление, очень важное для метрических алгоритмов. Какую роль играет расстояние в метрических методах? Оно должно показывать, насколько объекты похожи друг на друга или насколько не похожи? Таким образом, мы ожидаем, что расстояние тем больше, чем меньше чего-то общего между объектами. Но в то же время в машинном обучении признаков часто очень много. И возникает вопрос: нет ли каких-то особых свойств у расстояния в многомерном пространстве, в пространстве высокой размерности? Но вот давайте рассмотрим одно соображение на этот счет. Допустим, у нас есть некоторый вектор x1, и вектор x2 от него отличается в каждой координате, но совсем чуть-чуть. А вектор x3 отличается от x1 только в одной координате, но существенно. Вот какой из векторов будет ближе к x1? Понятно, что ответ зависит от метрики. Но в то же время понятно, что когда признаков очень много, маленькие различия могут накопиться и стать более значимыми, чем большое различие в одном признаке. А может быть вы этого не хотели. Другое соображение: на плоскости легко представить себе комбинацию из трех точек, равноудаленных друг от друга, то есть не группирующихся в какой-то одной области, которую мы, например, хотим интерпретировать как область, в которой представлены точки какого-то одного класса. В трехмерном пространстве тоже легко придумать конструкцию из четырех точек, но это будет просто правильный тетраэдр. В N-мерном пространстве можно придумать конструкцию из N + 1 точки. И все это нас наводит на мысли, что тогда, когда количество признаков сравнимо с количеством объектов, объекты в принципе могут оказаться равноудаленными друг от друга или практически равноудаленными. И еще одно соображение. Давайте представим себе вектор размерности N из бинарных признаков (ну, для простоты мы будем рассматривать бинарные признаки). Тогда всевозможных комбинаций признаков будет 2 в степени n. Это значит, что с ростом N экспоненциально увеличивается и количество объектов, которые должны быть в обучающей выборке, чтобы покрыть все возможные ситуации на ту же самую долю. Это означает, что количество необходимых данных растет экспоненциально. Ну и на эту тему есть очень хорошая, красивая иллюстрация. Давайте рассмотрим куб с ребром 1 и в нем рассмотрим куб с ребром 1/2. Ну и посмотрим, какую часть от объема большого куба будет составлять маленький куб. В одномерном пространстве всё вырождается в отрезке, и мы видим, что маленький куб, ну точнее маленький отрезок, будет составлять 1/2 от длины большого. В двумерном случае мы получаем квадраты, и видим, что площадь маленького квадрата будет составлять уже 1/4 от площади большого квадрата. В трехмерном случае объем будет составлять 1/8. И в N-мерном случае объем будет составлять все меньшую и меньшую долю. Можно рассмотреть чуть более показательный вариант, когда маленький куб будет иметь длину ребра 0,99. И понятно, что в случае N-мерного пространства часть, которая составляет маленький куб от большого, будет равна 0,99 в степени n. То есть при N, стремящемся к бесконечности, доля объема маленького куба стремится к нулю. Что это значит? Это значит, что в пространствах высокой размерности основная часть объема концентрируется вблизи границы области. То есть получается, что объекты оказываются очень часто примерно одинаково удалены друг от друга. Подведем итог. В многомерных пространствах расстояние между объектами ведет себя не совсем так, как мы привыкли. С ростом числа признаков необходимый объем обучающей выборки растет экспоненциально, и это становится серьезной проблемой для метрических алгоритмов. Объекты часто оказываются на примерно одинаковом расстоянии друг от друга. Вместе все эти наблюдения носят название «проклятие размерности». Проклятие размерности может существенно мешать применению метрических алгоритмов.