Верховный алгоритм. Как машинное обучение изменит наш мир - Педро Домингос

Другая причина, по которой исследователи поначалу скептически относились к ближайшему соседу, заключается в том, что было непонятно, может ли он определять истинные границы между понятиями. Но в 1967 году ученые-информатики Том Кавер и Питер Харт доказали, что при наличии достаточного количества данных ближайший сосед в худшем случае подвержен ошибкам всего в два раза больше, чем лучший вообразимый классификатор. Если, скажем, как минимум один процент тестовых примеров неизбежно будет неправильно классифицирован из-за зашумленности данных, ближайший сосед гарантированно получит максимум два процента ошибок. Это было историческое открытие. До этого момента все известные классификаторы исходили из того, что граница имеет очень четкую форму, обычно прямую линию. Это давало и плюсы, и минусы: с одной стороны, можно было доказать правильность, как в случае с перцептроном, но при этом появлялись строгие ограничения на то, что такой классификатор может узнать. Метод ближайшего соседа был первым в истории алгоритмом, который мог воспользоваться преимуществом неограниченного количества данных, чтобы обучаться произвольно сложным понятиям. Человеку не под силу проследить границы, которые он образует в гиперпространстве из миллионов примеров, но благодаря доказательству Кавера и Харта мы знаем, что они, вероятно, недалеки от истины. Рэй Курцвейл считает, что сингулярность начинается, когда люди перестают понимать, что делают компьютеры. По этому стандарту не совсем преувеличением будет сказать, что это уже происходит и началось еще в 1951 году, когда Фикс и Ходжес изобрели метод ближайшего соседа — самый маленький алгоритм, какой только можно изобрести.

Конечно, в райском саду есть и Змей. Его зовут Проклятие Размерности, и, хотя он в большей или меньшей степени поражает все алгоритмы машинного обучения, для ближайшего соседа он особенно опасен. В низких измерениях (например, двух или трех) ближайший сосед обычно работает довольно хорошо, но по мере увеличения количества измерений все довольно быстро начинает рушиться. Сегодня нет ничего необычного в обучении на тысячах или даже миллионах атрибутов. Для коммерческих сайтов, пытающихся узнать ваши предпочтения, атрибутом становится каждый клик. То же самое с каждым словом на веб-странице, с каждым пикселем в изображении. А у ближайшего соседа проблемы могут появиться даже с десятками или сотнями атрибутов. Первая проблема в том, что большая часть атрибутов не имеет отношения к делу: можно знать миллион фактов о Кене, но, вполне возможно, лишь немногие из них могут что-то сказать (например) о его риске заболеть раком легких. Для конкретно этого предсказания критически важно знать, курит Кен или нет, а информация о курении вряд ли поможет решить, понравится ли ему «Гравитация». Символистские методы со своей стороны довольно хорошо убирают неподходящие атрибуты: если в атрибуте не содержится информация о данном классе, его просто не включают в дерево решений или набор правил. Но метод ближайшего соседа неподходящие атрибуты безнадежно запутывают, потому что все они вносят свой вклад в сходство между примерами. Если не имеющих отношения к делу атрибутов будет достаточно много, случайное сходство в нерелевантных измерениях подавит имеющее значение сходство в важных, и метод ближайшего соседа окажется ничем не лучше случайного угадывания.

Еще одна большая и неожиданная проблема заключается в том, что большое число атрибутов может мешать, даже когда все они имеют отношение к делу. Может показаться, что много информации — это всегда благо. Разве это не лозунг нашего времени? Но по мере увеличения числа измерений начинает экспоненциально расти число обучающих примеров, необходимых для определения границ понятия. Двадцать булевых атрибутов дадут примерно миллион возможных примеров. С двадцать первым примеров станет два миллиона, с соответствующим числом способов прохождения между ними границы. Каждый лишний атрибут делает проблему обучения в два раза сложнее, и это если атрибуты булевы. Если атрибут высокоинформативный, польза от его добавления может превышать затраты. Но когда в распоряжении есть лишь малоинформативные атрибуты, например слова в электронном письме или пиксели изображения, это, вероятно, породит проблемы, несмотря на то что в совокупности они могут нести достаточно информации, чтобы предсказать то, что вы хотите.

Все даже хуже. Ближайший сосед основан на нахождении схожих объектов, а в высоких измерениях распадается сама идея сходства. Гиперпространство — как сумеречная зона. Наша интуиция, основанная на опыте жизни в трех измерениях, там не действует, и начинают происходить все более и более странные вещи. Представьте себе апельсин: шарик вкусной мякоти, окруженный тонкой кожицей. Мякоть в апельсине занимает, скажем, 90 процентов радиуса, а оставшиеся десять приходятся на кожуру. Это означает, что 73 процента объема апельсина — это мякоть (0,93). Теперь рассмотрим гиперапельсин: если мякоть занимает все те же 90 процентов радиуса, но, скажем, в сотне измерений, то она сократится примерно до всего лишь 3⁄1000 процента объема (0,9100). Гиперапельсин будет состоять из одной кожуры, и его никогда нельзя будет очистить!

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

Деревья решений тоже не застрахованы от проклятия размерности. Скажем, понятие, которое вы пытаетесь получить, представляет собой сферу: точки внутри нее положительные, а снаружи — отрицательные. Дерево решений может приблизить сферу самым маленьким кубом, в который она помещается. Это не идеально, но и не очень плохо: неправильно классифицированы будут только углы. Однако в большем числе измерений почти весь объем гиперкуба окажется вне гиперсферы, и на каждый пример, который вы правильно классифицируете как положительный, будет приходиться много отрицательных, которые вы сочтете положительными, а это резко снижает точность.

На самом деле такая проблема есть у всех обучающихся алгоритмов — это вторая беда машинного обучения после переобучения. Термин «проклятие размерности» был придуман в 50-е годы Ричардом Беллманом[93], специалистом по теории управления. Он заметил, что алгоритмы управления, которые хорошо работают в трех измерениях, становятся безнадежно неэффективными в пространствах с большим числом измерений, например, когда вы хотите контролировать каждый сустав манипулятора или каждую ручку на химическом комбинате. А в машинном обучении проблема не только в вычислительных затратах: с ростом размерности само обучение становится все сложнее и сложнее.