Верховный алгоритм - Педро Домингос

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

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

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

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

В целом нам надо справиться со многими ограничениями сразу (в случае метода опорных векторов — по одному на каждый пример). Представьте, что вы хотите подобраться как можно ближе к Северному полюсу, но не можете выйти из комнаты. Каждая из четырех стен комнаты — это ограничение, поэтому для решения задачи надо идти по компасу, пока вы не упретесь в угол, где встречаются северо-восточная и северо-западная стена. Эти стены будут активными ограничениями, потому что они не дадут вам достичь оптимума, а именно Северного полюса. Если одна из стен вашей комнаты смотрит точно на север, она станет единственным активным ограничением; для решения надо направиться в ее центр. А если вы Санта-Клаус и живете прямо на Северном полюсе, все ограничения окажутся неактивными и можно будет сесть и поразмышлять над проблемой оптимального распределения игрушек. (Бродячим торговцам легче, чем Санте.) В методе опорных векторов активные ограничения — опорные векторы, поскольку их зазоры уже наименьшие из разрешенных. Перемещение границы нарушило бы одно или больше ограничений. Все другие примеры не имеют отношения к делу и их вес равен нулю.

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

В поисках применения своему алгоритму Вапник и его сотрудники вскоре вышли на распознавание написанных от руки цифр, в котором их коллеги-коннекционисты в Bell Labs были мировыми экспертами. Ко всеобщему удивлению, метод опорных векторов с ходу справился не хуже многослойного перцептрона, который тщательно, годами оттачивали для распознавания цифр. Это подготовило почву для долгой интенсивной конкуренции между методами. Метод опорных векторов можно рассматривать как обобщение перцептрона, использование специфической меры сходства (скалярного произведения векторов) даст гиперплоскостную границу между классами. Но у метода опорных векторов имеется большое преимущество по сравнению с многослойными перцептронами: у весов есть единичный оптимум, а не много локальных, и поэтому их намного легче надежно найти. Несмотря на это, опорные векторы не менее выразительны, чем многослойные перцептроны: опорные векторы фактически действуют как скрытый слой, а их взвешенное среднее — как выходной слой. Например, метод опорных векторов может легко представлять функцию исключающего ИЛИ, имея один опорный вектор для каждой из четырех возможных конфигураций. Но и коннекционисты не сдавались без боя. В 1995 году Ларри Джекел, глава отдела Bell Labs, в котором работал Вапник, поспорил с ним на хороший обед, что к 2000 году нейронные сети будут так же понятны, как метод опорных векторов. Он проиграл. В ответ Вапник поспорил, что к 2005 году никто не будет пользоваться нейронными сетями. И тоже проиграл. (Единственным, кто бесплатно пообедал, был Янн Лекун, их свидетель.) Более того, с появлением глубокого обучения коннекционисты снова взяли верх. При условии обучаемости, сети со многими слоями могут выражать многие функции компактнее, чем метод опорных векторов, у которого всегда только один слой, а это иногда имеет решающее значение.

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