Может случиться, что потолок в комнате высокий, а точки данных лежат рядом с полом, как тонкий слой пыли на ковре. В этом случае нам повезло: проблема выглядит трехмерной, но в сущности она ближе к двухмерной. Мы не будем сокращать высоту, потому что это уже сделала природа. Такое «благословение неравномерности» данных в (гипер)пространстве часто спасает положение. У примеров могут быть тысячи атрибутов, но в реальности все они «живут» в пространстве с намного меньшим числом измерений. Именно поэтому метод ближайшего соседа бывает хорош, например, для распознавания написанных вручную цифр: каждый пиксель — это измерение, поэтому измерений много, но лишь мизерная доля всех возможных изображений — цифры, и все они живут вместе в уютном уголке гиперпространства. Форма низкоразмерного пространства c данными бывает, однако, довольно своенравна. Например, если в комнате стоит мебель, пыль оседает не только на пол, но и на столы, стулья, покрывала и так далее. Если можно определить примерную форму слоя пыли, покрывающей комнату, тогда останется найти координаты каждой точки на нем. Как мы увидим в следующей главе, целая субдисциплина машинного обучения посвящена открытию форм этих слоев путем, так сказать, прощупывания гиперпространства во тьме. 

Метод ближайшего соседа оставался самым широко используемым обучающимся алгоритмом аналогистов вплоть до середины 1990-х, когда его затмили более гламурные кузены из других «племен». Но тут, сметая все на своем пути, на смену ворвался новый алгоритм, основанный на принципах сходства. Можно сказать, что это был еще один «дивиденд от мира», плод окончания холодной войны. Метод опорных векторов был детищем советского специалиста по частотному подходу Владимира Вапника[94]. Вапник большую часть своей карьеры работал в московском Институте проблем управления, но в 1990 году Советский Союз рухнул, и ученый уехал в США, где устроился на работу в легендарную Bell Labs[95]. В России Вапник в основном довольствовался теоретической, бумажной работой, но атмосфера в Bell Labs была иной. Исследователи стремились к практическим результатам, и Вапник наконец решился превратить свои идеи в алгоритм. В течение нескольких лет он с коллегами по лаборатории разработал метод опорных векторов, и вскоре опорные векторы оказались повсюду и принялись ставить новые рекорды точности.

На первый взгляд метод опорных векторов во многом похож на взвешенный алгоритм k-ближайших соседей: граница между положительными и отрицательными классами определяется мерой схожести примеров и их весами. Тестовый пример принадлежит к положительному классу, если в среднем он выглядит более похожим на положительные примеры, чем на отрицательные. Среднее взвешивается, и метод опорных векторов помнит только ключевые примеры, необходимые для проведения границы. Если еще раз посмотреть на Позистан и Негативию без городов, не расположенных на границе, останется такая карта:

Примеры здесь называются опорными векторами, потому что это векторы, которые «поддерживают» границу: уберите один, и участок границы соскользнет в другое место. Также можно заметить, что граница представляет собой зубчатую линию с резкими углами, которые зависят от точного расположения примеров. У реальных понятий, как правило, границы более плавные, а это означает, что приближение, сделанное методом ближайшего соседа, вероятно, не идеально. Благодаря методу опорных векторов можно сделать границу гладкой, больше похожей на эту:

Чтобы обучить метод опорных векторов, нужно выбрать опорные векторы и их вес. Меру схожести, которая в мире опорных векторов называется ядром, обычно назначают априорно. Одним из важнейших открытий Вапника было то, что не все границы, отделяющие положительные тренировочные примеры от отрицательных, равноценны. Представьте, что Позистан воюет с Негативией и государства разделены нейтральной полосой с минными полями с обеих сторон. Ваша задача — исследовать эту ничейную землю, пройдя с одного ее конца к другому, и не взлететь на воздух. К счастью, у вас в руках карта c расположением мин. Вы, понятное дело, выберете не просто любую старую тропинку, а станете обходить мины как можно более широким кругом. Именно так поступает метод опорных векторов: мины для него — это примеры, а найденная тропа — выученная граница. Самое близкое место, где граница подходит к примеру, — ее зазор, и метод опорных векторов выбирает опорные векторы и веса так, чтобы зазор был максимальным. Например, сплошная прямая граница на этом рисунке лучше, чем пунктирная:

Пунктирная граница четко разделяет положительные и отрицательные примеры, но опасно близко подходит к минам A и B. Эти примеры — опорные векторы. Удалите один из них, и граница с максимальным зазором переместится в другое место. Конечно, граница может быть изогнутой, из-за чего зазор сложнее визуализировать, но можно представить себе, как по ничейной земле ползет змея и зазор — ее жировые отложения. Если без риска взорваться на кусочки может проползти очень толстая змея, значит, метод опорных векторов хорошо разделяет положительные и отрицательные примеры, и Вапник показал, что в этом случае можно быть уверенным, что метод не подвержен переобучению. Интуиция подсказывает, что у толстой змеи меньше способов проскользнуть мимо мин, чем у тощей, и точно так же, если зазор большой, у него меньше шансов переобучиться данным, нарисовав слишком замысловатую границу.

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

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