Проклятье размерности
Рубрику #чтопочитать продолжим статьей с Medium Towards Data Science. Специалисты компании Sociaro подготовили перевод статьи с немного пугающим заголовком "The Curse of Dimensionality"
Почему же высокоразмерные данные могут вызывать такие проблемы?
У вас когда-нибудь случалось так, что вы рассказываете кому-нибудь историю или пытаетесь объяснить что-то сложное и вдруг ваш собеседник спрашивает: "Ну и в чём суть?".
Прежде всего это конечно означает, что друг у вас не очень то вежлив.
Но с другой стороны, все мы время от времени бываем на месте такого друга, всё-таки у всех нас есть важные дела и нам нужно получить информацию быстро и по сути.
В этом и заключается цель снижения размерности. При работе с большим количеством данных, мы можем использовать алгоритмы снижения размерности, для того чтобы данные "перешли к сути".
Сегодня мы поговорим не об одном определенном алгоритме, а скорее о том, зачем нам вообще нужны алгоритмы снижения размерности. А причина этому - "проклятие размерности".
Какие данные считаются высокоразмерными и почему они могут вызывать проблемы?
Проклятие размерности звучит так, будто бы мы говорим о каком-нибудь пиратском фильме, но на самом деле, этот термин означает лишь то, что данные обладают слишком большим количеством признаков.
Данный термин, приписываемый Ричарду Беллману, выражал трудность применения грубой силы (поиску по решётке) для оптимизации функций со слишком большим количеством входных переменных. Представьте что произойдет, если вы запустите оптимизацию с помощью Excel Solver со 100,000 входными переменными, иначе говоря – 100,000 различными рычагами, каждый из которых возможно надо будет потянуть (можно быть уверенными, что Excel просто вылетет).
В современном мире этот термин также может означать несколько других проблем, возникающих в ситуациях, когда данные имеют слишком высокую размерность:
- В случае, если у нас признаков больше чем наблюдений (observations), мы рискуем переобучить модель, что приведёт к неподходящим результатам её работы, так как она сможет анализировать только выборку (sample), использованную при обучении.
При слишком большом количестве признаков, разбивать наблюдения на кластеры становится тяжело. Слишком высокая размерность приводит к тому, что обучаемая модель думает, что все наблюдения находятся на равном расстоянии друг от друга. А поскольку при кластеризации для количественной оценки сходства между наблюдениями измеряются расстояния, например Евклидово расстояние, это становиться значительной проблемой. Если все расстояния примерно равны друг другу, то все наблюдения будут также похожи друг на друга, а соответственно никакие осмысленные кластеры не могут быть сформированны.
Второй пункт довольно важный поэтому давайте разберём его в деталях.
Простой пример того, как высокоразмерные данные "проклинают" нас
Представим, что наш набор данных состоит из 8 конфет, представленных ниже.
Изначально мы знаем, что в данном наборе данных есть два кластера - сладкие и кислые. Если нам важен только вкус конфеты, то как мы можем разбить эти конфеты на кластеры так, чтобы случайно не подарить кислую конфету другу, который любит только сладкие?
Мы можем разделить их вот так:
Супер! Благодаря нашей кластеризации мы можем уверенно брать конфету красного оттенка, зная что она будет кислой, или конфету синего оттенка, будучи уверенными в её сладкости.
Но на самом деле всё не так просто. Человек может легко и быстро определить цвета и вкусы конфет и прийти к выводу, что красные - кислые, а синие - сладкие. Но обучающийся алгоритм может достичь таких выводов, только в случае правильного ввода данных. Если данные выглядят так, как представлено в таблице ниже, то нам повезло - в нашем распоряжении два признака: "красная" и "синяя", благодаря которым мы получаем два идеальных кластера вкуса. ("Красная" и "Синяя" в данном случае означают оттенки данных цветов)
Но что если данные высокоразмерны как в следующей таблице?
Теперь, вместо 2 цветов, их целых 8. Как бы воспринял такую ситуацию алгоритм кластеризации? Он бы взглянул на каждую конфету и сделал бы следующие выводы:
Каждая конфета окрашена в свой собственный цвет.
- Как алгоритм, не обученный соответствующим знаниям, я не знаю, как цвета соотносятся друг с другом. Например, в отличие от человека, я не знаю, что розовый и красный ближе друг к другу, чем бирюзовый и красный.
- Опираясь на данный набор признаков, я делаю вывод, что всего есть 8 кластеров и они все одинаково похожи друг на друга.
- Также я делаю вывод, что из этих 8 кластеров, 4 из них кислые и 4 из них сладкие.
Для нас эти выводы абсолютно бесполезны. Действительно, каждая конфета имеет уникальный цвет, но данный вывод никак нам не помогает. Обратите внимание на последний вывод - это буквальная переформулировка того, что мы изначально знали о нашем наборе данных. Мы ни на шаг не приблизились к прогнозированию того, какой является случайная конфета - кислой или сладкой. Как же мы можем это исправить?
На помощь приходит снижение размерности
Ниже представлен пример того, как работает снижение размерности. Данный пример не объясняет работу определенного алгоритма, а просто демонстрирует основные принципы работы алгоритмов снижения размерности.
Для начала алгоритм находит скрытые схожести в исходных признаках, такие как "спорт" или "политика" для текстовых данных или основная схожесть в базе данных временных рядов. Для нашего набора данных, такими признаками скорее всего станут основные цвета - красный и синий. В науке о данных такие схожести называются скрытыми признаками.
Далее, алгоритм примерно определяет и переписывает все остальные признаки относительно их приближенности к скрытым признакам, как показано в таблице выше.
Давайте расположим каждую конфету на графике с точки зрения её приближенности к этим скрытым признакам (то есть, используя значения из таблицы выше). Помните, что каждая конфета имеет свой собственный цвет.
Здорово! Используя скрытые признаки мы смогли создать два правильных кластера. Теперь мы можем взглянуть на каждый отдельный кластер, посчитать количество сладких конфет и кислых конфет и использовать эту частоту в качестве основы для наших прогнозов.
В итоге, наша модель "сладкая/кислая" для конфет будет выглядеть примерно так:
- При получении новой конфеты, записать её цвет.
- Перевести её цвет в приближенность к красному признаку и к синему признаку, иначе говоря, переписать её цвет с точки зрения скрытых признаков.
Используя скрытые признаки конфеты, а также измерение расстояний (например, можно измерить Евклидово расстояние), определить к какому кластеру конфет она находится ближе - синему или красному.
- Если наша модель кладет конфету в красный кластер, мы делаем прогноз, что новая конфета кислая (так как в нашем начальном наборе данных все конфеты, находящиеся в красном кластере, были кислые). Аналогично, если модель кладет её в синий кластер, мы делаем прогноз, что данная конфета сладкая (так как в нашем начальном наборе данных все конфеты, находящиеся в синем кластере, были сладкие).
Заключение
Сегодня мы узнали, как чрезмерное количество признаков может ввести некоторые алгоритмы машинного обучения, такие как алгоритмы кластеризации, в заблуждение. А также, мы разобрали то, как мы можем использовать снижение размерности для решения данной проблемы.
В реальном мире - мире запутанных, смутных данных и сложных взаимоотношений (в отличие от наших простых конфет) - снижение размерности представляет собой компромисс между более надежной моделью и меньшей интерпретируемостью.
Так что помните, что хоть у нас и есть инструмент для борьбы с проклятием размерности, использование этого инструмента обходится недешево!