Еще одна большая и неожиданная проблема заключается в том, что большое число атрибутов может мешать, даже когда все они имеют отношение к делу. Может показаться, что много информации — это всегда благо. Разве это не лозунг нашего времени? Но по мере увеличения числа измерений начинает экспоненциально расти число обучающих примеров, необходимых для определения границ понятия. Двадцать булевых атрибутов дадут примерно миллион возможных примеров. С двадцать первым примеров станет два миллиона, с соответствующим числом способов прохождения между ними границы. Каждый лишний атрибут делает проблему обучения в два раза сложнее, и это если атрибуты булевы. Если атрибут высокоинформативный, польза от его добавления может превышать затраты. Но когда в распоряжении есть лишь малоинформативные атрибуты, например слова в электронном письме или пиксели изображения, это, вероятно, породит проблемы, несмотря на то что в совокупности они могут нести достаточно информации, чтобы предсказать то, что вы хотите.
Все даже хуже. Ближайший сосед основан на нахождении схожих объектов, а в высоких измерениях распадается сама идея сходства. Гиперпространство — как сумеречная зона. Наша интуиция, основанная на опыте жизни в трех измерениях, там не действует, и начинают происходить все более и более странные вещи. Представьте себе апельсин: шарик вкусной мякоти, окруженный тонкой кожицей. Мякоть в апельсине занимает, скажем, 90 процентов радиуса, а оставшиеся десять приходятся на кожуру. Это означает, что 73 процента объема апельсина — это мякоть (0,93). Теперь рассмотрим гиперапельсин: если мякоть занимает все те же 90 процентов радиуса, но, скажем, в сотне измерений, то она сократится примерно до всего лишь 3⁄1000 процента объема (0,9100). Гиперапельсин будет состоять из одной кожуры, и его никогда нельзя будет очистить!
Беспокоит и то, что происходит с нашей старой знакомой, гауссовой кривой. Нормальное распределение говорит, что данные в сущности расположены в какой-то точке (средняя распределения), но с некоторым расхождением вокруг нее (заданным стандартным отклонением). Верно? Да, но не в гиперпространстве. При нормальном распределении в высокой размерности будет выше вероятность получить пример далеко от средней, чем близко к ней. Кривая Гаусса в гиперпространстве больше похожа на пончик, чем на колокол. Когда ближайший сосед входит в этот беспорядочный мир, он безнадежно запутывается. Все примеры выглядят одинаково схожими и при этом слишком далеко отстоят друг от друга, чтобы делать полезные прогнозы. Если случайным образом равномерно рассеять примеры внутри высокоразмерного гиперкуба, большинство окажется ближе к грани этого куба, чем к своему ближайшему соседу. На средневековых картах неисследованные области обозначали драконами, морскими змеями и другими фантастическими существами или просто фразой «Здесь драконы». В гиперпространстве драконы повсюду, в том числе прямо в дверях. Попробуйте прогуляться в гости к соседу, и вы никогда туда не доберетесь: станете вечно блуждать в чужих землях и гадать, куда делись все знакомые предметы.
Деревья решений тоже не застрахованы от проклятия размерности. Скажем, понятие, которое вы пытаетесь получить, представляет собой сферу: точки внутри нее положительные, а снаружи — отрицательные. Дерево решений может приблизить сферу самым маленьким кубом, в который она помещается. Это не идеально, но и не очень плохо: неправильно классифицированы будут только углы. Однако в большем числе измерений почти весь объем гиперкуба окажется вне гиперсферы, и на каждый пример, который вы правильно классифицируете как положительный, будет приходиться много отрицательных, которые вы сочтете положительными, а это резко снижает точность.
На самом деле такая проблема есть у всех обучающихся алгоритмов — это вторая беда машинного обучения после переобучения. Термин «проклятие размерности» был придуман в 50-е годы Ричардом Беллманом[93], специалистом по теории управления. Он заметил, что алгоритмы управления, которые хорошо работают в трех измерениях, становятся безнадежно неэффективными в пространствах с большим числом измерений, например, когда вы хотите контролировать каждый сустав манипулятора или каждую ручку на химическом комбинате. А в машинном обучении проблема не только в вычислительных затратах: с ростом размерности само обучение становится все сложнее и сложнее.
Тем не менее не все потеряно. Во-первых, можно избавиться от не имеющих отношения к делу измерений. Деревья решений делают это автоматически, путем вычисления информационного выигрыша от каждого атрибута и выбора самых информативных. В методе ближайшего соседа мы можем сделать нечто похожее, сначала отбросив все атрибуты, которые дают прирост информации ниже определенного порога, а затем измерив схожесть в пространстве с меньшим числом измерений. В некоторых случаях это быстрый и достаточно хороший прием, но, к сожалению, ко многим понятиям он неприменим. Среди них, например, исключающее ИЛИ: если атрибут говорит что-то о данном классе только в сочетании с другими атрибутами, он будет отброшен. Более затратный, но хитрый вариант — «обернуть» выбор атрибута вокруг самого обучающегося алгоритма с поиском путем восхождения на выпуклые поверхности, который будет удалять атрибуты, пока это не повредит точности метода ближайшего соседа на скрытых данных. Ньютон многократно выбирал атрибуты и определил, что для предсказания траектории тела важна только его масса, а не цвет, запах, возраст и миллиард других свойств. Вообще говоря, самое важное в уравнении — все те количества, которые в нем не появляются: когда известны самые существенные элементы, часто оказывается легче разобраться, как они зависят друг от друга.
Одно из решений проблемы неважных атрибутов — определение их веса. Вместо того чтобы считать сходство по всем измерениям равноценным, мы «сжимаем» наименее подходящие. Представьте, что обучающие примеры — это точки в комнате и высота для наших целей не требуется. Если ее отбросить, все примеры спроецируются на пол. Произвести понижающее взвешивание — все равно что опустить в комнате потолок. Высота точки все еще засчитывается при вычислении расстояния до других точек, но уже меньше, чем ее горизонтальное положение. И, как и многое другое в машинном обучении, вес атрибутов можно найти путем градиентного спуска.
Может случиться, что потолок в комнате высокий, а точки данных лежат рядом с полом, как тонкий слой пыли на ковре. В этом случае нам повезло: проблема выглядит трехмерной, но в сущности она ближе к двухмерной. Мы не будем сокращать высоту, потому что это уже сделала природа. Такое «благословение неравномерности» данных в (гипер)пространстве часто спасает положение. У примеров могут быть тысячи атрибутов, но в реальности все они «живут» в пространстве с намного меньшим числом измерений. Именно поэтому метод ближайшего соседа бывает хорош, например, для распознавания написанных вручную цифр: каждый пиксель — это измерение, поэтому измерений много, но лишь мизерная доля всех возможных изображений — цифры, и все они живут вместе в уютном уголке гиперпространства. Форма низкоразмерного пространства c данными бывает, однако, довольно своенравна. Например, если в комнате стоит мебель, пыль оседает не только на пол, но и на столы, стулья, покрывала и так далее. Если можно определить примерную форму слоя пыли, покрывающей комнату, тогда останется найти координаты каждой точки на нем. Как мы увидим в следующей главе, целая субдисциплина машинного обучения посвящена открытию форм этих слоев путем, так сказать, прощупывания гиперпространства во тьме.
Змеи на плоскости
Метод ближайшего соседа оставался самым широко используемым обучающимся алгоритмом аналогистов вплоть до середины 1990-х, когда его затмили более гламурные кузены из других «племен». Но тут, сметая все на своем пути, на смену ворвался новый алгоритм, основанный на принципах сходства. Можно сказать, что это был еще один «дивиденд от мира», плод окончания холодной войны. Метод опорных векторов был детищем советского специалиста по частотному подходу
