Что такое проклятие размерности

Проклятие размерности.doc

Кафедра информационных систем и математического моделирования

1. Определение и проблемы…………. … ………………………………………4

4. Мое понимание эффекта на примере (2)…………………………………….. 6

Проклятие размерности весьма интересный эффект, который может появиться во время анализа данных в многомерных пространствах, например, при кластерном анализе 1 или при обнаружении аномалий 2 .

Казалось бы, чем больше мы знаем об объектах (чем больше у них атрибутов), тем лучше: есть больше информации, по которой можно понять, насколько объекты похожи (отнести их к одному кластеру) или насколько они отличаются (отличить кластеры, найти аномалию). Да и вообще, чем больше о чем-то знаешь, тем лучше это контролируешь.
«Проклятие размерности» приводит к обратному.

Это влечет за собой следующие трудности:

Трудоемкость вычислений;
Необходимость хранения огромного количества данных;
Увеличение доли шумов;
В линейных классификаторах увеличение числа признаков ведет к проблемам мультиколлинеарности (тесная корреляционная взаимосвязь между отбираемыми для анализа факторами, совместно воздействующими на общий результат, которая затрудняет оценивание регрессионных параметров) и переобучения (нежелательное явление, возникающее при решении задач обучения по прецедентам, когда вероятность ошибки обученного алгоритма на объектах тестовой выборки оказывается существенно выше, чем средняя ошибка на обучающей выборке ; переобучение возникает при использовании избыточно сложных моделей).

Самый простой пример (1) «проклятия размерности» связан с изобретателем шахмат. Согласно легенде, один богатый человек настолько был восхищен этой игрой, что предложил изобретателю продать доску с фигурами. Хитрый изобретатель сказал, чтобы покупатель клал на каждую клеточку шахматной доски в два раза больше зернышек, чем на предыдущую, начиная с одного зернышка. Богатый человек рассмеялся и сказал, что с легкостью исполнит это желание. Здесь он и попал под «проклятье размерности» — не смог оценить конечное количество зерна. Действительно, кажется, что зернышки такие маленькие, и их общий вес не может быть огромным.

Напомню, что шахматная доска имеет 64 клетки.

Покупатель должен был положить 1 + 2^63 зернышек!

А это получается 9 223 372 036 854 776 001 зерен .

Среднее зернышко весит 0,03 грамма.

ИТОГО: 276 701 161 105 тонн зерна!

Естественно, богач не смог купить шахматы!

Вывод: Старайтесь научиться правильно оценивать величины, которыми вы оперируете. Это поможет Вам точно оценить свои возможности и избежать неловких ситуаций.

Следующий пример (2) посложнее:

рассмотрим единичный интервал [0,1]. 100 равномерно разбросанных точек будет достаточно, чтобы покрыть этот интервал с частотой не менее 0,01.

Теперь рассмотрим 10-мерный куб. Для достижения той же степени покрытия потребуется уже 1020 точек. То есть, по сравнению с одномерным пространством, требуется в 1018 раз больше точек.

Основная идея при решении проблемы — понизить размерность пространства, а именно спроецировать данные на подпространство меньшей размерности. На этой идее, например, основан метод главных компонент.
Нужно придумывать новые алгоритмы, основанные на тензорной математике.

Мое понимание эффекта на примере (2).

При кластерном анализе или при обнаружении аномалий, объекты удобно рассматривать как точки в пространстве своих атрибутов.

Алгоритмы, исследующие это пространство, должны определить расположены ли объекты между собой «по соседству» — то есть, находятся ли они на определенном расстоянии друг от друга (или от некой точки выбранной в качестве центра).

Так вот, чем больше атрибутов (чем больше размерность пространства, в котором ведется поиск соседей), тем меньше область, которая покрывается во время поиска на заданном расстоянии.

Это легко себе представить, просто оценив соотношение объема гиперсферы с объемом гиперкуба, в который она вписана.
(Если у нас только один кластер, то гиперсфера – область, в которой объекты считаются похожими, а гиперкуб — пространство атрибутов в котором расположены объекты).

Количество охваченных объектов уменьшается по экспоненте при увеличении размерности пространства.

Это означает, что при увеличении количества атрибутов, для того чтобы охватить требуемое количество объектов, нужно по экспоненте увеличивать расстояние поиска.

А это, в свою очередь, приведет к тому, что в охват попадут далекие друг от друга объекты — совсем не «соседи».

То есть теперь, в один кластер могут попасть совсем не похожие между собой объекты, или возможен провал в определении «далекой» аномалии, так как, за счет увеличения радиуса поиска, она будет отнесена к основной группе объектов.

В данном исследовании мы получили ответ на поставленный вопрос: проклятие размерности – это проблема, связанная с экспоненциальным возрастанием количества данных из-за увеличения размерности пространства. То есть, чем выше размерность пространства, тем меньше область, которая покрывается во время поиска объектов, расположенных на заданном расстоянии.

Изучение такого эффекта необходимо, так как это поможет работе ученых в таких областях как фармакология, биоинформатика, в работе с фото- и видеоматериалами, в аэродинамике и т.д.. Без этого мы не сможем упростить, облегчить, оптимизировать нашу повседневную жизнь, что может привести к колоссальным затратам времени, ресурсов и средств.

1 — многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы.

2 — динамический метод работы антивирусов, хостовых и сетевых систем обнаружения вторжений.

Данная статья является непроверенным учебным заданием. Студент: Участник:Allegra Преподаватель: Участник:Константин Воронцов Срок: 8 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона <<Задание>>.

Содержание

Это влечет за собой следующие трудности:

Трудоемкость вычислений
Необходимость хранения огромного количества данных
Увеличение доли шумов
В линейных классификаторах увеличение числа признаков ведет к проблемам мультиколлинеарности и переобучения.
В метрических классификаторах расстояния обычно вычисляются как средний модуль разностей по всем признакам. Согласно Закону Больших Чисел, сумма n слагаемых стремится в некоторому фиксированному пределу при n→∞. Таким образом, расстояния во всех парах объектов стремятся к одному и тому же значению, а значит, становятся неинформативными.

Рассмотрим единичный интервал [0,1]. 100 равномерно разбросанных точек будет достаточно, чтобы покрыть этот интервал с частотой не менее 0,01.

Теперь рассмотрим 10-мерный куб. Для достижения той же степени покрытия потребуется уже 10 20 точек. То есть, по сравнению с одномерным пространством, требуется в 10 18 раз больше точек.

Поэтому, например, использование переборных алгоритмов становится неэффективным при возрастании размерности системы.

Основная идея при решении проблемы — понизить размерность пространства, а именно спроецировать данные на подпространство меньшей размерности.

На этой идее, например, основан метод главных компонент.

Один алгоритм может применяться к разным входным данным, описывающим условие индивидуальной задачи из некоторой серии однотипных задач. При этом в зависимости от длины входных данных может меняться число операций, которые совершает алгоритм для нахождения решения.

Рассмотрим простой пример алгоритма, переводящего запись числа M из двоичной системы счисления в шестнадцатеричную. Этот алгоритм будет брать блоки по четыре бинарных символа и определять соответствующую им цифру в шестнадцатеричной системе. Очевидно, время работы такого алгоритма будет пропорционально количеству двоичных разрядов в исходном числе, т. е. пропорционально длине входных данных (количество разрядов в числе M можно оценить как

Рассмотрим теперь алгоритм, решающий другую задачу: установить, является ли заданное число M простым. Алгоритм непосредственной проверки простоты будет перебирать все числа от 2 до

Видно, что время работы второго алгоритма после некоторого момента катастрофически возрастает, и даже существенное увеличение быстродействия компьютера не позволяет решить эту проблему: дальнейшее незначительное увеличение длины входной строки снова делает алгоритм невыполняемым за обозримое время.

Все алгоритмы разделяют на классы сложности в зависимости от характера возрастания числа выполняемых ими операций при увеличении длины входных данных N. К классу P относят алгоритмы, время которых возрастает не быстрее, чем некоторый многочлен (polynomial) от N. Частный случай полиномиальной зависимости — это линейная зависимость, пример которой мы уже видели. Алгоритмы класса P считаются быстрыми в том смысле, что могут применяться на практике. Существуют разнообразные хорошо известные алгоритмы класса P, выполняющие сортировку массивов, поиск некоторой подстроки в строке, решающие системы линейных уравнений и т. д.

Ранее говорилось о том, что универсальная машина Тьюринга может эмулировать любую другую машину с полиномиальной скоростью. Теперь видно, что это важно в том смысле, что класс сложности исполняемого алгоритма при такой эмуляции не меняется.

Любой алгоритм класса P принадлежит также и классу NP (поскольку на недетерминированной машине он также будет выполняться за полиномиальное время). Но для простоты можно считать, что алгоритмы класса NP — это алгоритмы, время работы которых возрастает по размерности задач N экспоненциально (т. е. в геометрической прогрессии).

Таких алгоритмов тоже очень много. К сожалению, плохие вычислительные свойства относятся не только к алгоритмам, но и к самим задачам. Задаче тоже можно приписать некую вычислительную сложность, которую следует определить как сложность алгоритма с самым медленным возрастанием числа операций с ростом длины входных данных, называющейся также размерностью задачи.

Почему же этому вопросу уделяется такое внимание? Время решения NP-полной задачи возрастает экспоненциально с ростом размерности задачи, поэтому такую ситуацию называют комбинаторным взрывом, пример которого мы видели в приведенной выше таблице. Это название связано с тем, что число многих комбинаторных объектов, таких как битовые строки или сочетания элементов множества, растет экспоненциально с увеличением их длины. Здесь уместно вспомнить о легенде, согласно которой мудрец, придумавший шахматы, попросил у индусского царя в качестве награды положить ему на доску зерна пшеницы: на первую клетку одно, а на каждую последующую — в два раза больше, чем на предыдущую. По легенде царь поначалу был рассержен пожеланием столь малой награды, но сейчас легко подсчитать, что число зерен было бы почти
, и если бы каждая последующая клетка заполнялась через секунду, то это выглядело бы как гигантский взрыв. Стоит отметить, что и в настоящее время на вопрос о том, какова будет толщина листа бумаги, если его сложить пополам 50 раз подряд, значительная часть людей отвечает, что толщина составит до нескольких метров (хотя, опять же, несложно ее оценить примерно как расстояние от Земли до Солнца). Также быстро растет и число требуемых операций для решения NP-полных задач.

Эти задачи, обычно сводящиеся к перебору часто встречающихся комбинаторных объектов, оказываются практически неразрешимыми при достаточно большом N, как бы быстродействие компьютеров ни возрастало и как бы ученые ни пытались придумать для них полиномиальные алгоритмы. При этом NP-полные задачи являются гораздо менее надуманными, чем алгоритмически неразрешимые проблемы. Исследователи образно охарактеризовали данную ситуацию как проклятие размерности.

Алгоритмы класса NP, как правило, не могут применяться на практике, если только объем исходных данных не является сильно ограниченным. В частности, на этом факте основаны многие методы криптографии. К примеру, пусть мы знаем два больших простых числа. Мы можем их перемножить и результат перемножения сделать открытым ключом, с помощью которого происходит шифрование, а сами простые числа сделать закрытым ключом, с помощью которого происходит дешифрование. Мы можем передать открытый ключ по незащищенному каналу связи, получить по этому же каналу зашифрованную информацию и дешифровать ее с использованием известного нам закрытого ключа. Хотя нет защищенной передачи информации, способ практически безопасен (при достаточной длине ключа), поскольку алгоритм шифрования относится к классу P, а для дешифрования потребуется алгоритм класса NP (конечно, здесь приводится лишь общая идея, а не описываются сами алгоритмы шифрования). Еще остается вопрос, откуда нам самим взять большие простые числа. Из-за сложности получения таких чисел и эффективности их использования для шифрования они составляют предмет охраняемой тайны.

Кстати, здесь виден один интересный момент, связанный с NP-полными задачами. Для них проверка правильности единичного решения обычно является весьма простой (например, деление двух чисел). И даже сама задача класса NP может быть определена как задача, единичное решение которой может быть проверено за полиномиальное время на машине Тьюринга (это определение считается эквивалентным определению через недетерминированные машины). Но поиск решения задачи сводится к перебору и проверке очень большого числа вариантов. Алгоритмы же класса P (применение которых не вызывает ощущения интеллектуальной деятельности), как правило, решение вычисляют в явном виде, без перебора.

Большинство задач в области искусственного интеллекта, если и не являются алгоритмически неразрешимыми, то, по крайней мере, являются NP-полными (строго говоря, есть разрешимые задачи, которые сложнее, чем NP-полные задачи, но они не так сильно распространены). Такие NP-полные задачи, как игра в шахматы или построение доказательства теорем, кажутся интеллектуальными. Но алгоритмы точного решения этих задач, реализуемые на компьютерах (воплощениях машины Тьюринга), являются неприменимыми на практике. Значит ли это в очередной раз, что искусственный интеллект не может быть реализован на компьютерах? Посмотрим, есть ли какие-то альтернативы, чтобы спастись от комбинаторного взрыва.